Marius Nicoli (mariusn) Se dă un șir de matrice pătratice asupra căruia se pot face două tipuri de operații: actualizare a unui element (se înlocuiește matricea de pe acea poziție cu alta) și interogarea unui interval de indici (determinarea produsului matricelor memorate între cei doi indici, inclusiv).
Cerința
Afișați răspunsul la fiecare interogare.
Date de intrare
Prima linie a fisierului aepim.in conține două numere: N, ce reprezintă lungimea șirului dat și K ce reprezintă dimensiunea matricelor pătratice. Linia a doua, conține, separate prin câte un spațiu, matricele din șirului dat. Atât matricele date în șirul inițial cât și cele de la actualizări conțin doar 1 și 2 și sunt date la intrare codificat, ca un șir de K*K caractere, conform parcurgerii crescător după linii și apoi crescător după coloane (fără spații). De exemplu, matricea:
1 2 2 1 1 1 1 2 1
se codifică prin 122111121.
Codificările matricelor de pe a doua linie se separă prin câte un spațiu.
Pe linia a treia e află un număr M ce reprezintă numărul de operații ce se efectuează asupra șirului dat. Pe fiecare din următoarele M linii se găsesc câte 3 numere naturale separate prin câte un spațiu: T A B. Dacă T = 1 operația este de interogare iar A și B sunt capetele inrervalului. Dacă T = 2 operația este de actualizare cu semnificația: elementul de pe poziția A devine B (B reprezintă codificarea unei matrice).
Date de ieșire
Fișierul aepim.out conține pe câte o linie răspunsul la căte o operațe de tip 1, în ordinea în care acestea apar în datele de intrare. Elementele matricelor rezultat se scriu modulo 9901, se afișează, ca ordine, după aceeași regulă ca la codificarea din datele de intrare și se separă prin câte un spațiu.
Restricții și precizări
1 ≤ N ≤ 1000001 ≤ M ≤ 1000001 ≤ A ≤ B ≤ N2 ≤ K ≤ 3- elementele șirului dat sunt indexate de la
1
Exemplu:
aepim.in
4 2 1121 1221 1121 1121 3 1 2 4 2 2 2112 1 2 4
aepim.out
11 8 10 7 10 7 11 8
Explicație
Matricele sunt de ordin 2. Pe prima linie a fișierului deieșire este codifictă matricea
11 8 10 7