constant

Constant

* Daca $S[~i~]$ e $')'$, inseamna sfarsitul restrictiei anterioare (care nu are pereche);
* Daca $S[~i~]$ e $'*'$, inseamna ca nu exista niciun semn la kilometrul $i$.

Deci, notitele lui Georgel pot fi reprezentate ca un sir de caractere cum ar fi $"1*9))"$. Fiecare inceput de zona va avea o pereche corespondenta sfarsit de zona (pozitiile $2-3$ si $0-4$ in sir).

Deci, notitele lui Georgel pot fi reprezentate ca un sir de caractere cum ar fi $"1*9))"$. Fiecare inceput de zona va avea o pereche corespondenta sfarsit de zona (pozitiile $2-3$ si $0-4$ in sir). Intre kilometrii $i$ si $i+1$ se aplica restrictia impusa de ultimul semn (cu indicele ≤ $i$) caruia nu i-am intalnit perechea de sfarsit (verificati exemplul pentru clarificare).

Pe o portiune de drum se aplica ultimul semn de inceput de zona intalnit. Formal, intre kilometrul $i$ si $i + 1$ viteza maxima e $S[~j~]$, astfel incat $j$ e maxim si $j <= i$ si $S[~j~]$ e cifra. Se garanteaza ca tot timpul va exista un astfel de $j$.
 
Se dau $Q$ intrebari de forma "Care este numarul minim de perechi corespondente de semne ce trebuie eliminate astfel incat limita de viteza intre kilometrii $a$ si $b$ sa fie constanta?" si voi trebuie sa raspundeti la ele.

Georgel isi pune $Q$ intrebari de forma "Care este numarul minim de perechi corespondente de semne ce trebuie eliminate astfel incat limita de viteza intre kilometrii $a$ si $b$ sa fie constanta?" si voi trebuie sa il ajutati sa raspunda la ele.

h2. Date de intrare

h2. Restricţii

* Pentru toate testele de la evaluare T = 10
* $2 ≤ N ≤ 100000$

* Pentru toate testele de la evaluare $T = 10$
* $1 ≤ N ≤ 100000$

* $1 ≤ Q ≤ 100000$
* $0 &leq; a < b &leq; N$
* $S$ ca incepe cu o cifra si se va termina cu un caracter $')'$
* $S$ nu va contine cifra $0$
* Nu este permisa eliminarea perechii de semne de pe pozitiile $0 - N$ din sir (fiindca ar exista portiuni din drum fara restrictii)

* Sumele totale ale $N$-urilor si ale $Q$-urilor nu vor depasi $500000$

h2. Exemplu