JOI-kun estudia en IOI High School, donde pronto se celebrará el examen final. En el examen se comprobará si los estudiantes pueden calcular correctamente el valor de una función IOI. Una función IOI es una cadena obtenida mediante una de las seis reglas siguientes definidas por IOI High School, que asigna a los enteros entre $1$ y $10^9$, ambos inclusive, valores booleanos, True o False.

1. Sea $a$ un entero entre $1$ y $10^9$, ambos inclusive. Entonces [a] es una función IOI (donde a es la representación de $a$ en notación decimal). Esta función IOI asigna True a los enteros mayores o iguales que $a$ y False a los enteros menores que $a$.
2. Sea $f$ una función IOI. Entonces (f) también es una función IOI. Esta función asigna True y False a los mismos enteros que $f$.
3. Sea $f$ una función IOI. Entonces !f también es una función IOI. Esta función asigna False a los enteros a los que $f$ asigna True, y viceversa.
4. Sean $f$ y $g$ funciones IOI. Entonces f&g también es una función IOI. Esta función asigna True a un entero si tanto $f$ como $g$ le asignan True, y False en caso contrario.
5. Sean $f$ y $g$ funciones IOI. Entonces f^g también es una función IOI. Esta función asigna True a un entero si exactamente una de $f$ y $g$ le asigna True, y False en caso contrario.
6. Sean $f$ y $g$ funciones IOI. Entonces f|g también es una función IOI. Esta función asigna True a un entero si al menos una de $f$ y $g$ le asigna True, y False en caso contrario.

Si una función IOI se puede obtener mediante varias reglas, la regla con el número mayor determina el valor booleano que la función asigna a los enteros. Por ejemplo, para [1]&[2]|[3], se aplica la regla 6 con $f=$ [1]&[2] y $g=$ [3] (en lugar de aplicar la regla 4 con $f=$ [1] y $g=$ [2]|[3]). Además, en las reglas 4, 5 y 6, la regla se aplica de modo que $f$ sea lo más larga posible. Por ejemplo, para [4]^[5]^[6], se aplica la regla 5 con $f=$ [4]^[5] y $g=$ [6] (en lugar de aplicar la regla 5 con $f=$ [4] y $g=$ [5]^[6]).

Para prepararse para el examen, JOI-kun ha preparado una función IOI $S$ de longitud $N$ y quiere practicar el cálculo de los valores booleanos que esta función asigna a $Q$ enteros $X_1,X_2,\ldots,X_Q$. Como se te da bien manejar funciones IOI, te pide ayuda para crear una solución de ejemplo.

Escribe un programa que, dados $N,Q,S$ y $X_1,X_2,\ldots,X_Q$, determine los valores booleanos que la función IOI $S$ asigna a los enteros $X_1,X_2,\ldots,X_Q$.

Entrada

La entrada se proporciona por la entrada estándar con el siguiente formato:

N Q
S
X_1
X_2
...
X_Q

Salida

Imprime $Q$ líneas en la salida estándar. La línea $i$ ($1 \le i \le Q$) debe contener un único valor booleano, el que la función IOI $S$ asigna al entero $X_i$.

Restricciones

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ es una función IOI de longitud $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N,Q$ y $X_i$ ($1 \le i \le Q$) son enteros.

Subtareas

1. (5 puntos) $S$ no contiene & ni |.
2. (20 puntos) $Q=1$.
3. (10 puntos) $N \le 10\,000$.
4. (6 puntos) $S$ no contiene ! ni ^.
5. (12 puntos) Cuando se aplicó la regla 4 o la regla 6 en el proceso de obtener $S$, al menos una de $f$ y $g$ era una función IOI obtenida mediante la regla 1.
6. (20 puntos) $N \le 400\,000$.
7. (27 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

15 5
(![2]|[3])&![4]
1
2
3
4
5

Salida 1

True
False
True
False
False

Nota

Para algunas de las funciones IOI que aparecen en el proceso de obtener $S$ según las reglas del enunciado, los valores booleanos que asignan a los enteros $X_i$ ($1 \le i \le Q$) se muestran en la tabla siguiente.

Este ejemplo de entrada cumple las restricciones de las subtareas $3,6,7$.

Entrada 2

20 4
(!![23])^((([116])))
54
1
200
89

Salida 2

True
False
False
True

Nota

Este ejemplo de entrada cumple las restricciones de las subtareas $1,3,5,6,7$.

Entrada 3

32 4
[2]|[5]&[1]|(([1000000000])|[7])
4
10
6
1

Salida 3

True
True
True
False

Nota

Este ejemplo de entrada cumple las restricciones de las subtareas $3,4,6,7$.