Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: brackets.in

Rezultatų failas: brackets.out

Jei norite pateikti savo sprendimą - prisijunkite.

Brackets

Matijošius turi skliaustelių seką s_1,s_2,...,s_n arba kitais žodžiais, n ilgio eilutę s, sudarytą iš simbolių "(" ir ")".

Matijošius turi atsakyti m užklausų, aprašytų dviem sveikaisiai skaičiais l_i,r_i(1\\leql_i\\leqr_i\\leqn). Užklausos atsakymas - ilgiausio sekos s taisyklingo skliaustelių posekio ilgis.

Tuščia skliaustelių seka "" yra taisyklinga; Jeigu seka "a" yra taisyklinga, tai seka "(a)" irgi yra taisyklinga; Jeigu sekos "a" ir "b" yra taisyklingos, tai seka "ab" irgi yra taisyklinga; Visais kitais atvejais seka yra netaisyklinga.

Pradiniai duomenys

Pirmoje eilutėje pateikta neatskirtų tarpais simbolių '(' ir ')' seka s.

Antroje eilutėje pateiktas sveikasis skaičius 1\\leqm\\leq100000 - užklausų skaičius.

Kiekvienoje sekančioje m eilučių pateikiama pora sveikųjų skaičių l_i,r_i(1\\leql_i\\leqr_i\\leqn) - užklausos aprašymas.

Rezultatai

Jums reikia išvesti kiekvienos užklausos rezultatą po vieną į eilutę.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
 
0
0
2
10
4
6
6