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ť.
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.
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}$.
Na $i$-ty riadok vypíšte odpoveď na $i$-tu otázku, teda $n_i$-te číslo množiny.
Sú $4$ sady vstupov po $2$ body. Platia v nich takéto obmedzenia:
| Sada | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1 \leq n_i \leq$ | $100$ | $10\,000$ | $10^{6}$ | $10^{9}$ |
| $1 \leq m \leq$ | $100$ | $100\,000$ | $100\,000$ | $100\,000$ |
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++).
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
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete