Ursus

În România, populația de urși este în continuă creștere. Cercetătorii de la Institutul Viitorului (IV) au hotărât să studieze mai îndeaproape acest fenomen, analizând comportamentul unei mici populații de urși în condiții speciale și într-un spațiu restrâns.

Ei au constatat că o „familie” formată din 2 urși (mascul și femelă) are, în medie, $a$ pui. Presupunem că se nasc un număr egal de masculi și femele. Astfel, într-un model matematic simplist, numărul de urși se înmulțește cu $\frac{a}{2}$ de la o generație la alta. În plus, există și mici mase migratoare de urși. Aceștia nu participă la propagarea speciei și sunt tratați separat. Cercetătorii au observat că de la o generație la alta în spațiul studiat ajung, în medie, $b$ urși „străini” și pleacă $c$ urși „străini”.

Pe scurt, dacă într-o generație există $x$ urși „băștinași” și $y$ urși „străini”, în următoarea generație vor exista $\frac{ax}{2}$ urși „băștinași” și $y + b - c$ urși „străini”.

Cea mai importantă concluzie pe care au tras-o cercetătorii este că atât populația de urși „băștinași”, cât și cea de urși „străini” crește strict.

Cerință

La începutul studiului (generația 1) există $x$ urși „băștinași” și niciun urs „străin”.

Se dau: numărul cerinței ($t$) și $q$ întrebări, fiecare conținând un număr $n$. În funcție de numărul cerinței, trebuie determinat:

1. Câți urși vor exista în total în generația $n$?
2. Spațiul, fiind restrâns, permite un număr de maximum $n$ urși în total. Până la a câta generație se poate desfășura experimentul fără depășirea limitei de $n$ urși?

Date de intrare

Prima linie conține două numere naturale, $t$ (numărul cerinței) și $q$ (numărul de întrebări).

A doua linie conține un număr natural, $x$ (numărul inițial de urși) și trei numere reale (zecimale) pozitive, $a$, $b$ și $c$, cu semnificația din enunț (caracterizează creșterea populației).

Pe următoarele $q$ linii se găsește câte un număr natural $n$ (numărul generației pentru cerința 1 și numărul maxim de urși pentru cerința 2).

Date de ieșire

Pe cele $q$ linii ale ieșirii se vor afișa răspunsurile la întrebări. Linia $i$ va conține răspunsul la întrebarea $i$. Toate numerele afișate vor fi numere naturale. În cazul primei cerințe, se va afișa răspunsul la întrebare rotunjit la cel mai apropiat număr întreg.

Pentru a afișa variabila x de tip double rotunjită la cel mai apropiat număr întreg, includeți biblioteca cmath și folosiți instrucțiunea std::cout << (long long)std::round(x);.

Restricții și precizări

• Se recomandă folosirea tipului de date double (în loc de float) pentru reprezentarea numerelor reale.
• $t \in \{1, 2\}$
• $1 \leq q \leq 10^6$
• $2 \leq x \leq 10$
• $2 < a < 4$
• $0 \leq c < b \leq 10^9$
• Studiul durează maximum $500$ de generații.
• Numărul maxim de urși într-o generație este de $10^{14}$.
• Pentru cerința 1, se garantează că $n$ este cel puțin egal cu $1$ și strict mai mic decât numărul primei generații în care numărul de urși depășește $10^{14}$ pentru fiecare întrebare.
• Pentru cerința 2, se garantează că $n$ este cel puțin egal cu $x$ și cel mult egal cu numărul de urși din generația $500$ pentru fiecare întrebare.
• Se acordă 40 de puncte pentru rezolvarea cerinței 1 și 60 de puncte pentru rezolvarea cerinței 2.
• Pentru citirea și afișarea rapidă, se recomandă folosirea acestor linii de cod la începutul funcției main:

ios::sync_with_stdio(false);  
cin.tie(NULL);  
cout.tie(NULL);  

Exemplul 1

stdin

1 4
6 2.45 7.55 3.88
3
1
5
2

stdout

16
6
28
11

Explicație

Se rezolvă prima cerință; avem patru întrebări. Inițial există 6 urși „băștinași”, iar $a = 2.45$; $b = 7.55$; $c = 3.88$.

În cea de-a doua generație vor fi aproximativ $\frac{6\cdot 2.45}{2} = 7.35$ urși „băștinași” și $0 + 7.55 - 3.88 = 3.67$ urși „străini”.
În cea de-a treia generație vor fi aproximativ $\frac{7.35\cdot 2.45}{2} = 9.00375$ urși „băștinași” și $3.67 + 7.55 - 3.88 = 7.34$ urși „străini”. În total, $9.00375 + 7.34 = 16.34375$ urși. Acest număr rotunjit la cel mai apropiat întreg este $16$, deci se va afișa $16$.

Se procedează similar și pentru celelalte întrebări.

Exemplul 2

stdin

2 3
6 2.45 7.55 3.88
12
8
29

stdout

2
1
5

Explicație

Se rezolvă cea de-a doua cerință; avem trei întrebări. Inițial există 6 urși „băștinași”, iar $a = 2.45$; $b = 7.55$; $c = 3.88$.

Folosind calculele făcute anterior, în prima generație există $6$ urși, în cea de-a doua există $7.35 + 3.67 = 11.02$, iar în cea
de-a treia $16.34375$. Experimentul se poate desfășura doar până la cea de-a doua generație fără a depăși limita de $12$ urși.

Se procedează similar și pentru celelalte întrebări.