rest

Rest

== include(page="template/taskheader" task_id="rest") ==

Poveste si cerinta...

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)$
# interogarea pe un interval: se cere restul la $P$ al numarului format in baza $B$ prin concatenarea elementelor dintre pozitiile $x$ si $y$ $(1 &le; x &le; y &le; N)$.
 
h2. Cerinta
 
Pentru fiecare interogare afisati restul cerut.

h2. Date de intrare

Fisierul de intrare $rest.in$ ...

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.

h2. Date de iesire

In fisierul de iesire $rest.out$ ...

In fisierul $rest.out$ se vor afla raspunsurile la interogari, cate un numar pe linie, in ordinea data.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 250 000$
* $2 ≤ B, P ≤ 30 000$
* In urma concatenarii, pozitia cea mai semnificativa din numarul obtinut este $x$, pozitia $x+1$ este urmatoarea, etc.

h2. Exemplu
table(example). |_. rest.in |_. rest.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 10 7
1
3
9
0
7
3
2 2 3
1 3 0
2 3 5
| 4
0

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="rest") ==

3240