2092 - Actualizare Element, Produs Interval, Matrice

Enunt

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 ≤ 100000
• 1 ≤ M ≤ 100000
• 1 ≤ A ≤ B ≤ N
• 2 ≤ K ≤ 3
• elementele șirului dat sunt indexate de la 1

Exemplul 1

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