Los habitantes de IslaGrande consideran que una cadena ~W~ de paréntesis está balanceada si la cadena está vacía, si ~W=(W_1)~ o si ~W=W_1W_2~, donde ~W_1~ y ~W_2~ están balanceadas. Por ejemplo, las cadenas \(“(())”, “()()”, “(()())”\) están balanceadas y las cadenas \(“)”, “))((”, “(()(()”\) no lo están. Ellos necesitan construir un programa que actualice dinámicamente una cadena de paréntesis de acuerdo a dos tipos de solicitudes: el primero averigua si una secuencia de la cadena en un intervalo está balanceada o no mientras que el segundo tipo de solicitud cambia los paréntesis cerrados por abiertos y viceversa en un determinado intervalo de la cadena de paréntesis.

Tarea

Hacer un programa que permita:

• Leer desde la entrada la longitud y cadena de paréntesis así como la cantidad de solicitudes y las solicitudes propiamente.
• Ejecutar cada solicitud.
• Escribir hacia la salida para cada solicitud del primer tipo, un uno si la secuencia de la cadena está balanceada o un cero en caso contrario.

Entrada

La entrada contiene en la:

• Linea 1: ~N~, la longitud de la cadena de paréntesis.
• Linea 2: ~W~, una cadena de paréntesis de longitud ~N~. El primer carácter de la cadena está en la posición 1 y el último en la posición ~N~.
• Linea 3: ~S~, el número de solicitudes.

• Linea 4..S+4: cada una de estas líneas contiene una solicitud, en uno de los formatos siguientes:

  q a b devuelve si la secuencia está o no balanceada en el intervalo ~[a,b]~ de la cadena ~W~.

  u a b invierte todos los paréntesis en el intervalo ~[a,b]~ de la cadena ~W~.

La secuencia de caracteres en el intervalo ~[a,b]~ consiste de los todos los caracteres en las posiciones entre la ~a~ y la ~b~ incluyendo ambos.

Salida

La salida contiene para cada solicitud de tipo ~q~ (del primer tipo definido), una línea con un entero: ~1~ si la cadena está balanceada y ~0~ si la cadena no lo está.

Restricciones

• ~1 \leq N, S \leq 200 000~.
• En el 20% de los casos de prueba, ~N, S \leq 50 000~.

Ejemplo de Entrada

6
((()))
8
q 1 6
q 2 6
u 3 4
q 2 3
q 4 5
u 1 2
q 4 5
q 1 6

Ejemplo de Salida

1
0
1
1
1
0