Namlei

namlei

== include(page="template/taskheader" task_id="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).

Poveste si cerinta...

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

h2. Date de intrare

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)$.

h2. Date de iesire

h2. 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 $w$ muchii sunt numerotate $0 ... w - 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 ... w - 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.

...

h2. Restrictii