Din păcate, nu toate numerele naturale permit determinarea unui număr câștigător. De exemplu, pentru numărul $21$ nu există niciun număr natural *X* din care să putem obține $21$ după regula descrisă de mama lui Iliuță.
Cu ajutorul unui program a fost generat automat un șir de *N* numere, numerotate în ordinea generării *S[~1~]*, *S[~2~]*, ..., *S[~N~]*. Programul respectiv primește patru numere naturale *A*, *B*, *C*, *D* și primul număr din șir *S[~1~]*. Al i-lea număr generat se obține după regula *Si* = (([*S[~i-1~]*] % *A* ) * *B* + *C*) % *D*, unde $1$ < i ≤ $*N*$, iar $a % b$ reprezintă restul împărțirii lui $a$ la $b (b ≠ 0)$.
Cu ajutorul unui program a fost generat automat un șir de *N* numere, numerotate în ordinea generării *S[~1~]*, *S[~2~]*, ..., *S[~N~]*. Programul respectiv primește patru numere naturale *A*, *B*, *C*, *D* și primul număr din șir *S[~1~]*. Al i-lea număr generat se obține după regula *S[~i~]* = (([*S[~i-1~]*] % *A*) * *B* + *C*) % *D*, unde $1$ < i ≤ $*N*$, iar $a % b$ reprezintă restul împărțirii lui $a$ la $b (b ≠ 0)$.
h2. Cerință
Cunoscându-se numerele naturale *N*, *S1*, *A*, *B*, *C*, *D*, scrieți un program care rezolvă următoarele cerințe:
# pentru fiecare dintre termenii șirului *S[~1~]*, *S[~2~]*, ..., *S[~N~]*, determină cel mai mare număr natural *mai mic strict* decât termenul respectiv, pentru care există un număr câștigător; programul va afișa restul împărțirii sumei numerelor obținute la $10[^18^] + 31$;
Cunoscându-se numerele naturale *N*, *S[~1~]*, *A*, *B*, *C*, *D*, scrieți un program care rezolvă următoarele cerințe:
# pentru fiecare dintre termenii șirului *S[~1~]*, *S[~2~]*, ..., *S[~N~]*, determină cel mai mare număr natural *mai mic strict* decât termenul respectiv, pentru care există un număr câștigător; programul va afișa restul împărțirii sumei numerelor obținute la $10[^18^] + 31$;
# pentru fiecare dintre termenii șirului *S[~1~]*, *S[~2~]*, ..., *S[~N~]*, determină câte numere naturale *mai mici sau egale* cu termenul respectiv *NU* au număr câștigător; programul va afișa restul împărțirii sumei rezultatelor obținute la $10[^18^] + 31$.
h2. Date de intrare
Fișierul de intrare $tombola.in$ conținepe prima linie numărul natural *p*, reprezentând cerința care trebuie rezolvată (1 sau 2). Pe a doua linie se află, în această ordine, numerele naturale $N S1 A B C D$, separate prin câte un spațiu.
Fișierul de intrare $tombola.in$ conținepe prima linie numărul natural *p*, reprezentând cerința care trebuie rezolvată (1 sau 2). Pe a doua linie se află, în această ordine, numerele naturale *N* *S[~1~]* *A* *B* *C* *D*, separate prin câte un spațiu.
h2. Date de ieșire
h2. Restricții
* $1 ≤ N ≤ 500000$
* $1 < S1, C, D ≤ 10[^17^]$
* $1 < A, B, ≤ 10[^9^]$
* $1$ ≤ *N* ≤ $500 000$
* $1$ < *S[~1~]*, *C*, *D* ≤ $10[^17^]$
* $1$ < *A*, *B* ≤ $10[^9^]$
* Se garantează că *S[~i~]* >1, oricare $1$ ≤ *i* ≤ *N*
* Pentru teste valorând 50 de puncte cerința este 1.
* Pentru 30% din numărul total de teste, *N* * *D* ≤ $10[^6^]$ și *N* * *S[~1~]* ≤ $10[^6^]$ (50% dintre acestea fiind pentru cerința 1)
* Pentru 60% din numărul total de teste, *N* ≤ $30000$ (50% dintre acestea fiind pentru cerința 1).
h2. Exemple
Există două numere mai mici sau egale cu 22
care *NU* acceptă număr câștigător, 10 și respectiv 21.
|
table(example).
|_. tombola.in |_. tombola.out |
|1
3 12345678901234567 999999999 123456789 98765432109876543 1020304050607080
|12805467424792840|
|12805467424792840
|
|
|2
3 98765432109876543 999999999 123456789 12345678901234567 1020304050607080
|9912065223185559|
|9912065223185559
|
|
== include(page="template/taskfooter" task_id="tombola") ==
