subsir

Fie $S = (S_1, S_2, \dots, S_N$) un şir format din $N$ numere naturale mai mici decât $10$ şi $x$ un număr natural cu $p$ cifre, reprezentat în baza $10$ prin $x$ = $x_1 x_2 \dots x_p$. Observaţi că poziţiile din şirul $S$ sunt numerotate de la stânga la dreapta de la $1$ la $N$, iar cifrele numărului $x$ sunt numerotate de la stânga la dreapta de la $1$ la $p$ (cifra $p$ fiind cifra unităţilor).

Vom spune că $x$ apare ca subșir în șirul $S$ dacă există pozițiile $1 \leq j_1 < j_2 < \dots < j_p \leq N$ astfel încât să avem $S_{j_i} = x_i$ pentru orice $1 \leq i \leq p$. De exemplu, pentru $S=(2,3,7,9)$, $27$ apare ca subșir în $S$, dar $93$ nu apare ca subșir în $S$.

Numim prefix de lungime $j$ al lui $S$, secvența $S_1, S_2, \dots, S_j$ (secvenţa care începe la poziţia $1$ şi se termină la poziţia $j$).

Cerință

Scrieţi un program care, cunoscând şirul $S$, rezolvă următoarele două cerinţe:

1. fiind date $Nr$ perechi de forma $x \ j$, determină pentru fiecare pereche dacă numărul $x$ apare ca subșir în prefixul de lungime $j$ al lui $S$ şi afişează valoarea $1$ în caz afirmativ, respectiv valoarea $0$ în caz contrar;
2. fiind date $Nr$ perechi de forma $a \ b$, determină şi afişează pentru fiecare pereche numărul de numere naturale din intervalul închis [$a, b$] care apar ca subșir în șirul S.

Date de intrare

Fișierul de intrare subsir.in conține pe prima linie un număr natural $C$ care reprezintă cerinţa care urmează a fi rezolvată ($1$ sau $2$). Pe a doua linie se află numărul natural $N$. Pe a treia linie se află $N$ numere naturale mai mici decât $10$, $S_1, S_2, \leq, S_N$, reprezentând elementele şirului $S$. Pe linia a patra se află un număr natural $Nr$ care reprezintă numărul de perechi. Pe următoarele $Nr$ linii se află câte o pereche de numere naturale. Numerele scrise pe aceeaşi linie în fişierul de intrare sunt separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire subsir.out va conține $Nr$ linii, pe cea de a $i$-a linie fiind scris rezultatul pentru cea de a $i$-a pereche dintre cele $Nr$ perechi din fişierul de intrare, conform cerinţei $C$.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$;
• $1 \leq Nr \leq 10 \ 000$;
• $0 \leq x < 10^7$;
• $1 \leq j \leq N$;
• $0 \leq a \leq b < 10^7$;
• Pentru teste valorând $30$ de puncte cerinţa este $1$.
• Pentru teste valorând $70$ de puncte cerinţa este $2$.

Exemplul 1

subsir.in

1
10
5 6 1 0 3 2 5 2 3 1
5
1 4
1 2
153 6
153 9
72 8

subsir.out

1
0
0
1
0

Explicație

Cerinţa este $1$, deci trebuie să verificăm pentru fiecare dintre cele $Nr=5$ perechi $x \ j$ specificate dacă $x$ apare ca subşir în prefixul de lungime $j$ al lui $S$.
Prima pereche este $1 \ 4$. Numărul $1$ apare ca subşir în prefixul $5 \ 6 \ 1 \ 0$, deci se afişează $1$.
A doua pereche este $1 \ 2$. Numărul $1$ nu apare ca subşir în prefixul $5 \ 6$, deci se afişează $0$.
A treia pereche este $153 \ 6$. Numărul $153$ nu apare în prefixul $5 \ 6 \ 1 \ 0 \ 3 \ 2$, deci se va afişa $0$.
A patra pereche este $153 \ 9$. De data aceasta numărul $153$ apare ca subşir în prefixul $5 \ 6 \ 1 \ 0 \ 3 \ 2 \ 5 \ 2 \ 3$, deci se afişează $1$.
A cincea pereche este $72 \ 8$. Numărul $72$ nu apare ca subşir în niciun prefix al lui $S$, deci nici în cel de lungime $8$ și se va afişa $0$.

Exemplul 2

subsir.in

2
10
5 6 1 0 3 2 5 2 3 1
3
0 20
40 105
81 99

subsir.out

11
15
0

Explicație

Cerinţa este $2$, deci trebuie să determinăm pentru fiecare dintre cele $Nr = 3$ perechi $a \ b$ specificate câte numere naturale din intervalul $[a, b]$ apar ca subşir în $S$.
Pentru intervalul $[0, 20]$ există $11$ numere, acestea fiind $0, 1, 2, 3, 5, 6, 10, 11, 12, 13, 15$.
Pentru intervalul $[40, 105]$ există $15$ numere, acestea fiind $50, 51, 52, 53, 55, 56, 60, 61, 62, 63, 65, 101, 102, 103, 105$.
Pentru intervalul $[81, 99]$ răspunsul este $0$, deoarece nu există niciun număr în acest interval care să fie subşir al lui $S$.