Următoarele reprezintă exemple de parantezari corecte: (), (()()), (()())(), (()())(()())
Următoarele reprezintă exemple de parantezari incorecte: )), )(, ()), ())(, (()))(

Dându-se secvenţa iniţială de paranteze, precum si operaţiile pe care Bluff vrea să le efectueze, ajutaţi-l să raspundă la operaţiile de tip 2.
 

h2. Date de intrare

Fişierul de intrare $luffpar.in$ ...

Prima linie a fişierului luffpar.in va conţine numărul n, reprezentând lungimea secvenţei de paranteze.
A doua line va conţine exact n caractere, reprezentând secvenţa de paranteze. Caracterele vor fi doar paranteze rotunde: ( sau ).
A treia linie va conţine numărul m reprezentând numărul de operaţii pe care Bluff vrea să le efectueze.
Pe următoarele m linii se vor găsi câte trei numere întregi: tip l r, care descriu fiecare operaţie ce trebuie aplicată. tip poate fi 1 sau 2, identificând tipul de operaţie care trebuie aplicată. l si r descriu subsecvenţa pe care trebuie aplicată operaţia, iar poziţiile secvenţei sunt numerotate de la 1. Se garantează că, pentru orice operaţie, 1 ≤ l ≤ r ≤ n.

h2. Date de ieşire

În fişierul de ieşire $luffpar.out$ ...

În fişierul luffpar.out afişaţi răspunsurile corespunzătoare operaţiilor de tip 2. Un răspuns poate fi 1, în cazul unei secvenţe corect parantezate, sau 0 alftel.

h2. Restricţii

* $... ≤ ... ≤ ...$

1 ≤ n ≤ 200.000
1 ≤ m ≤ 200.000
pentru 20% dintre teste: n, m ≤ 1000
pentru alte 30% dintre teste se garantează ca fiecare operaţie de tipul 1 se va aplica asupra unei subsecvenţe de lungime exact 1, deci l = r va fi adevarat pentru toate operaţiile de tipul 1

h2. Exemplu