Se dau doua numere naturale $N$ si $B$ si un sir de $N$ numere cu valori naturale cuprinse intre $0$ si $B-1$. Pe acest sir se pot efectua doua tipuri de operatii:

# modificarea unui element: elementul de pe pozitia $x$ $(1 &le; x &le; N)$ ia valoarea $y$ $(0 &le; y < B)$

# modificarea unui element: elementul de pe pozitia $x$ ($1 &le; x &le; N$) ia valoarea $y$ $(0 &le; y < B)$

# interogarea pe un interval: se cere restul la $P$ al numarului format in baza $B$ prin concatenarea elementelor dintre pozitiile $x$ si $y$ $(1 ≤ x ≤ y ≤ N)$.
h3. Cerinta

h2. Date de intrare

Pe prima linie a fisierului $rest.in$ se afla $3$ numere naturale $N$, $B$ si $P$ cu semnificatia din enunt. Pe urmatoarele $N$ linii se afla cate un element al sirului dat. Apoi se afla numarul $M$, ce reprezinta numarul total de operatii. Pe urmatoarele $M$ linii se afla cate $3$ numere: $a$ $x$ $y$ ($a$ este $1$ daca operatia este de modificare, $2$ daca operatia este de interogare), iar $x$ si $y$ au semnificatia corespunzatoare fiecarei operatii.

Fisierul de intrare $rest.in$ ...

h2. Date de iesire