JOI-kun учится в старшей школе IOI, где скоро состоится итоговый экзамен. На экзамене проверят, умеют ли ученики правильно вычислять значение IOI-функции. IOI-функция — это строка, полученная по одному из следующих шести правил, определённых школой IOI. Она отображает целые числа от $1$ до $10^9$ включительно в логические значения True или False.

1. Пусть $a$ — целое число от $1$ до $10^9$ включительно. Тогда [a] — IOI-функция (здесь a — строковое представление числа $a$ в десятичной записи). Эта IOI-функция отображает целые числа, большие либо равные $a$, в True, а целые числа, меньшие $a$, — в False.
2. Пусть $f$ — IOI-функция. Тогда (f) — тоже IOI-функция. Эта IOI-функция отображает целые числа в те же значения True и False, что и $f$.
3. Пусть $f$ — IOI-функция. Тогда !f — тоже IOI-функция. Эта IOI-функция отображает целые числа, которые $f$ отображает в True, в False, и наоборот.
4. Пусть $f$ и $g$ — IOI-функции. Тогда f&g — тоже IOI-функция. Эта IOI-функция отображает целое число в True, если и $f$, и $g$ отображают его в True, и в False в противном случае.
5. Пусть $f$ и $g$ — IOI-функции. Тогда f^g — тоже IOI-функция. Эта IOI-функция отображает целое число в True, если ровно одна из функций $f$ и $g$ отображает его в True, и в False в противном случае.
6. Пусть $f$ и $g$ — IOI-функции. Тогда f|g — тоже IOI-функция. Эта IOI-функция отображает целое число в True, если хотя бы одна из функций $f$ и $g$ отображает его в True, и в False в противном случае.

Если IOI-функцию можно получить с помощью нескольких правил, то логическое значение, в которое она отображает целое число, определяется правилом с большим номером. Например, для [1]&[2]|[3] правило $6$ применяется к $f=$[1]&[2] и $g=$[3] (а не правило $4$ к $f=$[1] и $g=$[2]|[3]). Кроме того, правила $4$, $5$ и $6$ применяются так, чтобы $f$ была как можно длиннее. Например, для [4]^[5]^[6] правило $5$ применяется к $f=$[4]^[5] и $g=$[6] (а не правило $5$ к $f=$[4] и $g=$[5]^[6]).

Чтобы подготовиться к экзамену, JOI-kun приготовил IOI-функцию $S$ длины $N$ и собирается потренироваться определять логические значения, в которые она отображает $Q$ целых чисел $X_1,X_2,\ldots,X_Q$. Поскольку вы хорошо умеете работать с IOI-функциями, он просит вас помочь и составить образец решения.

Напишите программу, которая по заданным $N$, $Q$, $S$ и $X_1,X_2,\ldots,X_Q$ определяет логические значения, в которые IOI-функция $S$ отображает целые числа $X_1,X_2,\ldots,X_Q$.

Входные данные

Данные поступают из стандартного ввода в следующем формате:

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

Выходные данные

Выведите в стандартный вывод $Q$ строк. Строка $i$ ($1 \le i \le Q$) должна содержать одно логическое значение, в которое IOI-функция $S$ отображает целое число $X_i$.

Ограничения

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ — IOI-функция длины $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N$, $Q$ и $X_i$ ($1 \le i \le Q$) — целые числа.

Подзадачи

1. ($5$ баллов) $S$ не содержит & или |.
2. ($20$ баллов) $Q=1$.
3. ($10$ баллов) $N \le 10\,000$.
4. ($6$ баллов) $S$ не содержит ! или ^.
5. ($12$ баллов) Когда в процессе получения $S$ применяется правило $4$ или $6$, хотя бы одна из функций $f$ и $g$ является IOI-функцией, полученной по правилу $1$.
6. ($20$ баллов) $N \le 400\,000$.
7. ($27$ баллов) Дополнительных ограничений нет.

Примеры

Входные данные 1

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

Выходные данные 1

True
False
True
False
False

Примечание

Для некоторых IOI-функций, возникающих в процессе получения $S$ по правилам из условия, логические значения, в которые они отображают целые числа $X_i$ ($1 \le i \le Q$), приведены в следующей таблице.

Этот пример входных данных удовлетворяет ограничениям подзадач $3$, $6$ и $7$.

Входные данные 2

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

Выходные данные 2

True
False
False
True

Примечание

Этот пример входных данных удовлетворяет ограничениям подзадач $1$, $3$, $5$, $6$ и $7$.

Входные данные 3

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

Выходные данные 3

True
True
True
False

Примечание

Этот пример входных данных удовлетворяет ограничениям подзадач $3$, $4$, $6$ и $7$.