tetris3

Tetris3

== include(page="template/taskheader" task_id="tetris3") ==
Qwerty a inventat o nouă variantă a faimosului joc $TETRIS$. În varianta sa, jocul prezintă un şir de $N$ boluri numerotate de la $1$ la $N$ care în momentul iniţial sunt goale. Qwerty vrea să facă $M$ operaţii pe acest şir de boluri. O operaţie constă în alegerea unui interval continuu de boluri $[A, B]$ şi adăugarea în fiecare bol din acest interval a unei bomboane de culoare $C$. De asemenea, dacă în orice moment de timp într-un anumit bol se află două bomboane de aceeaşi culoare $C$ ele dispar, iar dacă $C$ este mai mare decât $1$ atunci în locul acestora apare o bomboană de culoare $C-1$.

Operaţiile pe care le va face Qwerty sunt definite prin relaţie recurentă. El începe cu numerele $A1 B1 C1$ şi pentru oricare $i$ mai mare decât $1$, utilizează apoi relaţiile:
$Ai = Min(N, (Ai-1 * i) % 1008989)$
$Bi = Min(N, (Bi-1 * i) % 1008989)$
$Ci = (Ci-1*X + Y) % 47 + 1$

Operaţiile pe care le va face Qwerty sunt definite prin relaţie recurentă. El începe cu numerele $A{~1~} B{~1~} C{~1~}$ şi pentru oricare $i$ mai mare decât $1$, utilizează apoi relaţiile:

Qwerty va pune câte o bomboană de culoare $Ci$ în toate bolurile aflate între $Min(Ai,Bi)$ şi $Max(Ai,Bi).

* $A{~i~} = Min(N, (A{~i-1~} * i) % 1008989)$
* $B{~i~} = Min(N, (B{~i-1~} * i) % 1008989)$
* $C{~i~} = (C{~i-1~}*X + Y) % 47 + 1$

h2. Cerinta

Qwerty va pune câte o bomboană de culoare $C{~i~}$ în toate bolurile aflate între $Min(A{~i~},B{~i~})$ şi $Max(A{~i~},B{~i~})$.
 
h2. Cerinţă

Deoarece Qwerty e mofturos din fire, doreşte ca înainte de a face operaţiile, să ştie care este numărul de bomboane care va ramane în boluri şi de aceea vă roagă să aflaţi acest număr pentru el.

* $1 ≤ A, B ≤ N$
* $1 ≤ C ≤ 47$
* $1 ≤ X, Y ≤ 100 000$

* Modul de generare a datelor de intrare nu influenţează în nici un fel rezolvarea problemei!

* *Modul de generare a datelor de intrare nu influenţează în nici un fel rezolvarea problemei!*

h2. Exemplu

4902