3. Dobré hádanie

Pytón Python sa rozhodol, že pri príležitosti 30. výročia vybudovania jeho štvrte usporiada veľkolepú online párty, na ktorej si všetci účastníci zahrajú novú hru s názvom Háda, Hádaš, Hádate. Princíp tejto hry spočíva v tom, že Python si pripraví množinu čísel, o ktorej nikto z účastníkov nič netuší, a súťažiacim prezradí niekoľko čísel z tejto množiny s ich pozíciami (pri zoradení od najmenšieho) v tejto množine. Vyhráva ten hádač, ktorý prvý príde na to, akým receptom Python zostrojil množinu.

Nie sme si úplne istí, ako veľmi a či vôbec budú účastníci párty z tejto Pythonovej hry nadšení, ale čo už.

Python ale potrebuje vašu pomoc. Už má vymyslený recept na zostrojenie množiny čísel, no teraz potrebuje nejaký program, do ktorého zadá pozíciu čísla v jeho množine a on mu vypíše, aké číslo sa na tejto pozícii nachádza, aby vedel súťažiacim dávať tieto indície a nemusel to sám ručne počítať.

Úloha

Pre čísla \(a, b, c\) sa Pythonova množina skladá práve z takých \(x\), ktoré spĺňajú práve jednu z dvoch podmienok:

• \(a\) delí \(x\), no \(b\) nedelí \(x\).
• \(a\), \(b\) aj \(c\) delia \(x\).

Poznáte čísla \(a, b, c\) a \(m\). Python sa vás postupne opýta na \(m\) pozícií v jeho množine. Pre každú z nich zistite, aké číslo sa nachádza na danej pozícii (pri usporiadaní od najmenšieho). Pomôžete mu tak s prípravou hry a okorenením výročnej párty.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú 4 čísla \(a, b, c\) (parametre množiny) a \(m\) (počet otázok), pričom platí, že \(1 \leq a, b, c \leq 1\,000\) a \(1 \leq m \leq 100\,000\). Nasleduje \(m\) riadkov. Na \(i\)-tom z nich je číslo \(n_i\), čiže pozícia čísla v množine, na ktorú sa Python pýta v \(i\)-tej otázke. Platí, že \(1 \leq n_i \leq 10^{9}\).

Formát výstupu

Na \(i\)-ty riadok vypíšte odpoveď na \(i\)-tu otázku, teda \(n_i\)-te číslo množiny.

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich takéto obmedzenia:

Pozor, vstupné a výstupné údaje sa nemusia zmestiť do 32 bitovej premennej, odporúčame preto použiť 64 bitovú premennú (napr. long long v C++).

Príklad

Input:

3 6 7 3
1
2
8

Output:

3
9
42

Pre \(a=3, b=6, c=7\) vyzerá prvých 8 prvkov množiny tako: {3, 9, 15, 21, 27, 33, 39, 42}. Každé číslo je buď deliteľné všetkými troma alebo je deliteľné 3 ale nie 6.

Input:

151 993 103 3
1893
2499
24

Output:

285994
377651
3624