Fie S = (S1, S2, ..., SN) 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 = x1x2...xp. 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 ≤ j1 < j2 < ... < jp ≤ N astfel încât să avem Sji = xi pentru orice 1 ≤ i ≤ 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 S1, S2, …, Sj (secvenţa care începe la poziţia 1 şi se termină la poziţia j, 1 ≤ j ≤ N).

Cerința

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

• 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;
• 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, S1, S2, …, SN, 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 ≤ N ≤ 10.000
• 1 ≤ Nr ≤ 10.000
• 0 ≤ x < 10.000.000
• 1 ≤ j ≤ N
• 0 ≤ a ≤ b < 10.000.000
• 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.