O firmă oarecare dintrun 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.
