Fişierul intrare/ieşire:	namlei.in, namlei.out	Sursă	Stelele Informaticii 2006, clasele 11-12
Autor	Tiberiu-Lucian Florea	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.3 sec	Limită de memorie	36096 kbytes
Scorul tău	N/A	Dificultate	5/5

Vezi solutiile trimise | Statistici

Namlei

Exista N + 1 orase dispuse in linie, numerotate in intervalul [0..N], fiecare avand cate K obiective strategice numerotate in intervalul [0..K - 1]. Astfel, orice obiectiv poate fi identificat printr-o pereche (i, j), i reprezentand numarul orasului in care se afla respectivul obiectiv, iar j numarul de ordine al obiectivului. Avand in vedere aceste notatii, pot exista muchii doar intre un obiectiv (i, x) si un obiectiv (i + 1, y) (adica din orase consecutive).

Intre doua obiective (i, x) si (i + 1, y) exista cel putin o muchie (posibil mai multe).

Operatiile care se pot face sunt urmatoarele:

• U: Toate muchiile dintre orasele i si i + 1 sunt eliminate. Se introduc alte muchii, astfel incat sa se pastreze conditia precedenta.
• Q: Se calculeaza si se afiseaza numarul de drumuri distincte formate din j - i muchii intre obiectivele (i, x) si (j, y).

Date de intrare si de iesire

Pe prima linie a fisierului namlei.in se afla numerele N si K, separate de un spatiu. Pe a doua linie a fisierului se afla numerele X si Y, separate de un spatiu. Pe fiecare din urmatoarele N linii se afla cate un triplet de numere (cnt, j, k). Acest triplet de pe linia a i-a (i intre 0 si N - 1) inseamna ca intre orasele i si i + 1 exista (in afara de cele K * K muchii obligatorii) cnt muchii dintre care prima este (i, j) - (i + 1, k). Daca a (w - 1)-a muchie este (i, j) - (i + 1, k), a w-a muchie (i, j') - (i + 1, k') se calculeaza dupa urmatoarea formula:

j' = (j * X + k * w * Y) % K
k' = (j * w * X + k * Y) % K

Cele cnt muchii sunt numerotate 0 .. cnt - 1.

Pana la sfarsitul fisierului, fiecare pereche de doua linii reprezinta o operatie U sau Q. Pe prima dintre linii se afla tipul operatei, iar pe a doua parametrii care determina aceasta operatie.

In cazul unei operatii de tipul U:

A doua linie contine numerele i, cnt, j, k separate prin cate un spatiu. Acest cvadruplet inseamna ca (dupa eliminarea muchiilor care existau deja) intre orasele i si i + 1 exista (in afara de cele K * K muchii obligatorii) cnt muchii dintre care prima este (i, j) - (i + 1, k). Daca a (w - 1)-a muchie este (i, j) - (i + 1, k), a w-a muchie (i, j') - (i + 1, k') se calculeaza dupa urmatoarea formula:

j' = (j * X + k * w * Y + 1) % K
k' = (j * w * X + k * Y + 1) % K

Cele w muchii sunt numerotate 0 .. cnt - 1.

ATENTIE ! Din cauza unor considerente intim legate de natura problemei, aceste formule difera printr-un +1 de formulele precedente.

In cazul unei operatii de tipul Q:

A doua linie contine numerele i, x, j, y separate prin cate un spatiu. In acest caz trebuie afisat numarul de drumuri distincte de exact j - i muchii intre obiectivele (i, x) si (j, y). i este strict mai mic decat j. Toate rezultatele se vor afisa modulo 997. Raspunsurile vor fi afisate in fisierul namlei.out in ordinea in care sunt puse intrebarile, fiecare raspuns pe o linie separata.

Restrictii

• 1 ≤ N ≤ 30 000
• 3 ≤ K ≤ 8
• 1 ≤ cnt ≤ 120
• Exista cel mult 1 000 de operatii din fiecare tip
• X si Y sunt numere naturale strict pozitive reprezentabile pe variabile de 32 biti.

Exemplu

Cum se trimit solutii?