gWheels (Large)

A typical mountain bike has two gear groups: one attached to the pedals and one attached to the rear tire. A group holds several gears, and the gears inside a group usually have different tooth counts. A chain links one gear of the pedal group to one gear of the tire group, and that pair fixes the ratio between the pedaling speed and the tire speed. For example, if the chain links a 5 tooth gear on the pedals to a 10 tooth gear on the tire, the ratio is $1/2$, because the rider has to turn the pedal gear twice to turn the tire once. The rider can move the chain to link any gear of the pedal group to any gear of the tire group.

You just bought a special mountain bike with three gear groups: one on the pedals, one on the tire, and one extra group between them. This bike has two chains. The first chain always links one gear of the pedal group to one gear of the extra group, and the second chain always links one gear of the extra group to one gear of the tire group. The two chains cannot use the same gear of the extra group.

Given the tooth counts of the gears in the pedal group, the extra group, and the tire group, decide whether the ratio between the pedaling speed and the tire speed can be exactly $P/Q$. For one set of gears you have to answer several such questions.

The first line contains the number of test cases $T$. Each test case begins with a line holding three integers $N_p$, $N_e$, and $N_t$, the number of gears in the pedal group, the extra group, and the tire group. Three lines follow, containing $N_p$, $N_e$, and $N_t$ integers: the tooth counts of the gears in the pedal group, the extra group, and the tire group. The tooth counts inside one group are all distinct. The next line contains one integer $M$, the number of questions. Finally $M$ lines follow, each with two integers $P$ and $Q$, the target ratio. $P/Q$ is not necessarily in lowest terms.

For each test case, first print one line containing "Case #x:", where x is the test case number starting from 1. Then print one line per question, in the order the questions were given: Yes if the ratio $P/Q$ can be made, No if it cannot.

• $1 \le T \le 100$
• $1 \le$ tooth count of each gear $\le 10000$
• $1 \le P \le 10^9$ and $1 \le Q \le 10^9$
• $1 \le M \le 10$
• $1 \le N_p \le 2000$ and $1 \le N_t \le 2000$
• $2 \le N_e \le 2000$

Take a pedal group with a single 5 tooth gear, an extra group with gears of 4 and 6 teeth, and a tire group with gears of 3, 5, and 7 teeth.

The ratio $1/1$ cannot be made. Making it would force both chains onto the same gear of the extra group, which is not allowed.

The ratio $5/2$ can be made. Put the first chain on the 5 tooth pedal gear and the 4 tooth extra gear, and put the second chain on the 6 tooth extra gear and the 3 tooth tire gear.