Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Una cadena de paréntesis $($ y $)$ se dice que está balanceada si está incluida en alguno de los siguientes casos:

• Es la cadena $()$.
• Es la concatenación de dos cadenas balanceadas.
• Es una cadena de la forma $(s)$ donde $s$ es una cadena balanceada.

De esta definición se deriva, por ejemplo, que la cantidad de paréntesis abiertos $($ debe ser igual a la cantidad de paréntesis cerrados $)$.

Fito se ha encontrado con la tarea de lograr que una cadena se mantenga balanceada, a pesar de que su primita Fitiña se ha dedicado a invertir el estado de algunos paréntesis.

Inicialmente Fito tiene una cadena balanceada de paréntesis y cada vez que su primita haga un cambio é l se va a enterar de la posición del mismo. Nuestra tarea es decirle a Fito cuál es el paréntesis más a la izquierda que él debe invertir para que su cadena se mantenga balanceada.

La figura a continuación se corresponde con la primera operación del primer caso de prueba. Fitiña cambió el cuarto paréntesis y luego para mantener balanceada la cadena Fito cambió el segundo.

Input

La primera línea de entrada va a tener dos enteros $N$ $(1 \le N \le 300000)$ y $Q$ $(1 \le Q \le 150000)$, que representan la cantidad de paréntesis de la cadena y la cantidad de cambios que hizo Fitiña respectivamente. En la segunda línea estará la cadena de paréntesis y después habrá $Q$ líneas con las posiciones de los paréntesis que Fitiña fue cambiando.

Output

Para cada cambio que hizo Fitiña se debe imprimir una línea con la posición del paréntesis que Fito debe cambiar.

Nota : Los cambios son acumulativos, o sea, los cambios que se realizan en la cadena se mantienen para las próximas operaciones.

Sample test(s)