O firmă oarecare dintr­un oraş oarecare vrea să dezvolte o aplicaţie oarecare. Pentru aceasta, este necesară o structură de date care să efectueze rapid următoarele tipuri de operaţii asupra unui şir cu N cifre:
• 1. Modificarea unui interval: toate elementele din intervalul [st,dr] (1<=st<=dr<=N) iau valoarea x (0<=x<=9)
• 2. Interogare pe un interval: pentru un interval [st,dr] (1<=st<=dr<=N) se cere numărul format prin concatenarea cifrelor dintre pozitiile stsi dr. Deoarece această valoare poate fi prea mare, este suficient restul împărţirii acesteia la R.
Aşa cum probabil ai ghicit deja, tu va trebui să dai o mână de ajutor !!!

Cerinţă

Având N, M, R şi cele N cifre ale şirului, să se efectueze cele M operaţii.

Date de intrare

Fişierul de intrare secvnumber.in conţine pe prima linie 3 numere naturale N, M şi R cu semnificaţia din enunţ. Pe următoarea linie se află cele N cifre separate prin câte un spaţiu, reprezentând elementele şirului. Pe următoarele M linii sunt descrise operaţiile, fiecare pe câte o linie. Pe linia i+2 se află valoarea t, ce reprezintă tipul operaţiei. Dacă t este 1, pe aceeaşi linie se mai află valorile st, dr şi x, ce reprezintă modificarea tuturor elementelor din intervalul [st,dr] cu cifra x. Dacă t este 2, în continuare se află valorile st şi dr, ce reprezintă o interogare pe intervalul [st,dr].

Date de ieşire

Fişierul de ieşire secvnumber.out conţine răspunsul la interogări, câte unul pe linie, în ordinea dată.

Restricţii

• 2 <= N, M, R <= 100 000
• Pentru 30% din teste N, M < 10 000
• Din numărul ce se formează prin concatenare, se elimină cifrele de 0 (zero) de la început.

Exemplu

secvnumber.in	secvnumber.out	Explicaţie
7 5 13 1 0 2 4 5 3 7 2 1 4 2 2 5 1 1 3 0 2 1 4 2 2 5	10 11 4 6	Luăm pe rând cele 5 operaţii: 1) query: 1024 % 13 = 10 2) query: 0245 % 13 = 245 % 13 = 11 3) Se modifică şirul in: 0 0 0 4 5 3 7 4) query: 0004 % 13 = 4 % 13 = 4 5) query: 0045 % 13 = 45 % 13 = 6

stud. Cosmin-Mihai Tutunaru

Universitatea Babeş-Bolyai

cosmin@tutunaru.ro