JOI-kun навчається в IOI High School, де незабаром відбудеться підсумковий іспит. На іспиті перевірятимуть, чи вміють учні правильно обчислювати значення IOI-функції. IOI-функція — це рядок, отриманий за одним із наступних шести правил, визначених IOI High School, який відображає цілі числа від $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.