Fișierul intrare/ieșire	tombola.in, tombola.out	Sursă	ONI 2019 baraj gimnaziu
Autor	Dana Lica	Adăugată de	Mircea Rebengiuc • mircea_007
Timp de execuție pe test	0.75 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	3.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Tombola (baraj gimnaziu)

Aflat într-o vizită cu părinții, Iliuță primește un bilet la tombolă pe care este scris un număr natural S. Pentru a câștiga un premiu, Iliuță trebuie să afle, plecând de la numărul S, un număr câștigător X. Pentru a-l ajuta să ghicească numărul câștigător, mama îi spune lui Iliuță că numărul S de pe biletul său este suma dintre numărul câștigător X și toate numerele obținute plecând de la numărul câștigător X, prin ștergerea cifrei unităților numărului X, apoi, succesiv, prin ștergerea cifrei unităților numărului obținut la pasul anterior, până se ajunge la un număr de o singură cifră.

De exemplu, dacă numărul X este 2019, atunci din X se pot obține după regula de mai sus trei numere: 201, 20 și 2. Suma tuturor acestor numere este S = 2019 + 201 + 20 + 2 = 2242. Deci, dacă pe biletul lui Iliuță se află numărul S = 2242, atunci numărul câștigător corespunzător lui S este X = 2019.

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₁, S₂, ..., S_N. Programul respectiv primește patru numere naturale A, B, C, D și primul număr din șir S₁. 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).

Cerință

Cunoscându-se numerele naturale N, S₁, A, B, C, D, scrieți un program care rezolvă următoarele cerințe:

1. pentru fiecare dintre termenii șirului S₁, S₂, ..., 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¹⁸ + 31;
2. pentru fiecare dintre termenii șirului S₁, S₂, ..., 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¹⁸ + 31.

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 S₁ A B C D, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire tombola.out va conține un singur număr natural care reprezintă rezultatul la cerința p.

Restricții

• 1 ≤ N ≤ 500 000
• 1 < S₁, C, D ≤ 10¹⁷
• 1 < A, B ≤ 10⁹
• 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 ≤ 106 și N * S₁ ≤ 106 (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).

Exemple