JOI-kun est élève à IOI High School, où l'examen de fin d'année aura bientôt lieu. Cet examen vérifiera si les élèves savent calculer correctement la valeur d'une fonction IOI. Une fonction IOI est une chaîne obtenue par l'une des six règles suivantes, définies par IOI High School. Elle associe à chaque entier compris entre $1$ et $10^9$, bornes incluses, une valeur booléenne, soit True, soit False.

1. Soit $a$ un entier compris entre $1$ et $10^9$, bornes incluses. Alors [a] est une fonction IOI (a est la représentation décimale de $a$ sous forme de chaîne). Cette fonction IOI associe True aux entiers supérieurs ou égaux à $a$, et False aux entiers inférieurs à $a$.
2. Soit $f$ une fonction IOI. Alors (f) est également une fonction IOI. Elle associe les mêmes valeurs True et False aux mêmes entiers que $f$.
3. Soit $f$ une fonction IOI. Alors !f est également une fonction IOI. Elle associe False aux entiers auxquels $f$ associe True, et inversement.
4. Soient $f$ et $g$ deux fonctions IOI. Alors f&g est également une fonction IOI. Elle associe True à un entier si $f$ et $g$ lui associent toutes deux True, et False sinon.
5. Soient $f$ et $g$ deux fonctions IOI. Alors f^g est également une fonction IOI. Elle associe True à un entier si exactement l'une des fonctions $f$ et $g$ lui associe True, et False sinon.
6. Soient $f$ et $g$ deux fonctions IOI. Alors f|g est également une fonction IOI. Elle associe True à un entier si au moins l'une des fonctions $f$ et $g$ lui associe True, et False sinon.

Si une fonction IOI peut être obtenue par plusieurs règles, la règle de plus grand numéro détermine la valeur booléenne que cette fonction associe aux entiers. Par exemple, pour [1]&[2]|[3], on applique la règle $6$ à $f=$ [1]&[2] et $g=$ [3] (plutôt que la règle $4$ à $f=$ [1] et $g=$ [2]|[3]). De plus, pour les règles $4,5,6$, la règle est appliquée de façon que $f$ soit aussi longue que possible. Par exemple, pour [4]^[5]^[6], on applique la règle $5$ à $f=$ [4]^[5] et $g=$ [6] (plutôt que la règle $5$ à $f=$ [4] et $g=$ [5]^[6]).

Pour préparer l'examen, JOI-kun a préparé une fonction IOI $S$ de longueur $N$ et souhaite s'entraîner à déterminer les valeurs booléennes que cette fonction associe à $Q$ entiers $X_1,X_2,\ldots,X_Q$. Comme vous maîtrisez les fonctions IOI, il vous demande de l'aider en créant une solution de référence.

Écrivez un programme qui, étant donnés $N,Q,S$ et $X_1,X_2,\ldots,X_Q$, détermine les valeurs booléennes que la fonction IOI $S$ associe aux entiers $X_1,X_2,\ldots,X_Q$.

Entrée

L'entrée est fournie sur l'entrée standard au format suivant :

$$ \begin{array}{l} N\ Q\\ S\\ X_1\\ X_2\\ \vdots\\ X_Q \end{array} $$

Sortie

Affichez $Q$ lignes sur la sortie standard. La $i$-ème ligne ($1 \le i \le Q$) doit contenir une unique valeur booléenne : celle que la fonction IOI $S$ associe à l'entier $X_i$.

Contraintes

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ est une fonction IOI de longueur $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N,Q$ et $X_i$ ($1 \le i \le Q$) sont des entiers.

Sous-tâches

1. ($5$ points) $S$ ne contient ni & ni |.
2. ($20$ points) $Q=1$.
3. ($10$ points) $N \le 10\,000$.
4. ($6$ points) $S$ ne contient ni ! ni ^.
5. ($12$ points) Chaque fois que la règle $4$ ou la règle $6$ est appliquée lors de la construction de $S$, au moins l'une des fonctions $f$ et $g$ est une fonction IOI obtenue par la règle $1$.
6. ($20$ points) $N \le 400\,000$.
7. ($27$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

True
False
True
False
False

Remarque

Pour certaines des fonctions IOI apparaissant lors de la construction de $S$ selon les règles de l'énoncé, les valeurs booléennes associées aux entiers $X_i$ ($1 \le i \le Q$) sont données dans le tableau suivant.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $3,6,7$.

Entrée 2

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

Sortie 2

True
False
False
True

Remarque

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1,3,5,6,7$.

Entrée 3

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

Sortie 3

True
True
True
False

Remarque

Cet exemple d'entrée satisfait les contraintes des sous-tâches $3,4,6,7$.