JOI-kun estuda na IOI High School, onde o exame final será realizado em breve. No exame, será avaliado se os alunos conseguem calcular corretamente o valor de uma função IOI. Uma função IOI é uma string obtida por uma das seis regras a seguir, definidas pela IOI High School, que associa inteiros entre $1$ e $10^9$ (inclusive) a valores booleanos, True ou False.

1. Seja $a$ um inteiro entre $1$ e $10^9$ (inclusive). Então [a] é uma função IOI (a é a representação de $a$ em notação decimal). Essa função IOI associa os inteiros maiores ou iguais a $a$ a True e os inteiros menores que $a$ a False.
2. Seja $f$ uma função IOI. Então (f) também é uma função IOI. Essa função IOI associa os mesmos inteiros a True e a False que $f$.
3. Seja $f$ uma função IOI. Então !f também é uma função IOI. Essa função IOI associa a False os inteiros que $f$ associa a True, e vice-versa.
4. Sejam $f$ e $g$ funções IOI. Então f&g também é uma função IOI. Essa função IOI associa um inteiro a True se tanto $f$ quanto $g$ o associam a True, e a False caso contrário.
5. Sejam $f$ e $g$ funções IOI. Então f^g também é uma função IOI. Essa função IOI associa um inteiro a True se exatamente uma entre $f$ e $g$ o associa a True, e a False caso contrário.
6. Sejam $f$ e $g$ funções IOI. Então f|g também é uma função IOI. Essa função IOI associa um inteiro a True se pelo menos uma entre $f$ e $g$ o associa a True, e a False caso contrário.

Se uma função IOI puder ser obtida usando várias regras, a regra de maior número determina o valor booleano ao qual a função IOI associa os inteiros. Por exemplo, para [1]&[2]|[3], a regra 6 é aplicada a $f=$ [1]&[2] e $g=$ [3] (em vez de aplicar a regra 4 a $f=$ [1] e $g=$ [2]|[3]). Além disso, nas regras 4, 5 e 6, a regra é aplicada de modo que $f$ seja o mais longo possível. Por exemplo, para [4]^[5]^[6], a regra 5 é aplicada a $f=$ [4]^[5] e $g=$ [6] (em vez de aplicar a regra 5 a $f=$ [4] e $g=$ [5]^[6]).

Para se preparar para o exame, JOI-kun preparou uma função IOI $S$ de comprimento $N$ e pretende praticar a determinação dos valores booleanos aos quais essa função associa $Q$ inteiros $X_1,X_2,\ldots,X_Q$. Como você tem habilidade para lidar com funções IOI, ele pede sua ajuda para criar uma solução de exemplo.

Escreva um programa que, dados $N$, $Q$, $S$ e $X_1,X_2,\ldots,X_Q$, determine os valores booleanos aos quais a função IOI $S$ associa os inteiros $X_1,X_2,\ldots,X_Q$.

Entrada

A entrada é fornecida pela entrada padrão no seguinte formato:

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

Saída

Imprima $Q$ linhas na saída padrão. A linha $i$ ($1 \le i \le Q$) deve conter um único valor booleano ao qual a função IOI $S$ associa o inteiro $X_i$.

Restrições

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ é uma função IOI de comprimento $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N$, $Q$ e $X_i$ ($1 \le i \le Q$) são inteiros.

Subtarefas

1. (5 pontos) $S$ não contém & nem |.
2. (20 pontos) $Q=1$.
3. (10 pontos) $N \le 10\,000$.
4. (6 pontos) $S$ não contém ! nem ^.
5. (12 pontos) Sempre que a regra 4 ou a regra 6 foi aplicada no processo de obtenção de $S$, pelo menos uma entre $f$ e $g$ era uma função IOI obtida pela regra 1.
6. (20 pontos) $N \le 400\,000$.
7. (27 pontos) Sem restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

True
False
True
False
False

Nota

Para algumas funções IOI que aparecem no processo de obtenção de $S$ segundo as regras do enunciado, os valores booleanos aos quais elas associam os inteiros $X_i$ ($1 \le i \le Q$) são mostrados na tabela a seguir.

Esta entrada de exemplo satisfaz as restrições das subtarefas $3,6,7$.

Entrada 2

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

Saída 2

True
False
False
True

Esta entrada de exemplo satisfaz as restrições das subtarefas $1,3,5,6,7$.

Entrada 3

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

Saída 3

True
True
True
False

Esta entrada de exemplo satisfaz as restrições das subtarefas $3,4,6,7$.