P2

Considerând două numere naturale $X$ și $Y$ , spunem că $X$ este prefix pentru $Y$ , dacă $X$ se poate obține din $Y$ prin ștergerea a $0$, $1$ sau mai multor cifre de la sfârșitul lui $Y$.
Exemple :

• $1024$ este prefix pentru $1024789056$
• $526$ este prefix pentru $526$

Se dau numerele naturale $Q$, $L$ și apoi o succesiune de $Q$ interogări de următoarele $3$ tipuri:

unde $M, N , A$ și $B$ sunt numere naturale.

Cerință

Date fiind $Q, L$ şi o succesiune de $Q$ interogări, să determine răspunsurile pentru interogările date.

Date de intrare

Fişierul de intrare p2.in conţine pe prima linie numerele naturale $Q$ și $L$, separate prin spaţiu.
Pe următoarele $Q$ linii sunt scrise cele $Q$ interogări, câte o interogare pe o linie, în forma descrisă în tabel.

Date de ieșire

Fişierul de ieşire p2.out va conţine $Q$ linii.
Pe linia $i$ va fi scris răspunsul pentru cea de a $i$-a interogare din fișierul de intrare.

Restricții și precizări

• $1 \leq Q \leq 100 \ 000$
• $1 \leq L \leq 1 \ 000 \ 000$
• $0 \leq M \leq 999 \ 999$
• $0 \leq N \leq L$
• $0 \leq A \leq B \leq L$

Exemplu

p2.in

4 13
1 8
2 81 13
2 64 7
3 1 0 13

p2.out

3
1
0
4

Explicație

Valorile pentru $2^0$, $2^1$,..., $2^{13}$ sunt $1$, $2$, $4$, $8$, $16$, $32$, $64$, $128$, $256$, $512$, $1 \ 024$, $2 \ 048$, $4 \ 096$, $8 \ 192$.
Pentru prima interogare avem $M=8$, iar cel mai mic $N \leq 13$ cu prefix egal cu $8$ pentru $2^N$ este $3$, $2^3 = 8$.
Pentru a doua interogare avem $M=81$ și $N=13$ și deoarece $2 ^ {13} = 8 \ 192$ avem rezultatul $1$.
Pentru a treia interogare avem $M=64$ și $N=7$ și deoarece $2 ^ 7 = 128$, avem că rezultatul este $0$.
Pentru a patra interogare avem $M=1$, $A=0$ și $B=13$, iar valorile lui $N$ pentru care $1$ apare ca prefix în $2^N$ sunt $0$, $4$, $7$, $10$ deci răspunsul este $4$.