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 函数将整数映射为与 $f$ 相同的布尔值。
3. 若 $f$ 是一个 IOI 函数，则 $!f$ 也是一个 IOI 函数。该 IOI 函数将 $f$ 映射为 True 的整数映射为 False，反之亦然。
4. 若 $f$ 和 $g$ 是 IOI 函数，则 $f\&g$ 也是一个 IOI 函数。该 IOI 函数在 $f$ 和 $g$ 同时将整数映射为 True 时将其映射为 True，否则映射为 False。
5. 若 $f$ 和 $g$ 是 IOI 函数，则 $f\hat{}g$ 也是一个 IOI 函数。该 IOI 函数在 $f$ 或 $g$ 中恰有一个将整数映射为 True 时将其映射为 True，否则映射为 False。
6. 若 $f$ 和 $g$ 是 IOI 函数，则 $f|g$ 也是一个 IOI 函数。该 IOI 函数在 $f$ 或 $g$ 中至少有一个将整数映射为 True 时将其映射为 True，否则映射为 False。

如果一个 IOI 函数通过多条规则得到，则编号较大的规则决定了该 IOI 函数映射整数的布尔值。例如，对于 $[1]\&[2]|[3]$，规则 6 应用于 $f = [1]\&[2]$ 和 $g = [3]$（而不是将规则 4 应用于 $f = [1]$ 和 $g = [2]|[3]$）。此外，对于规则 4、5 和 6，应用规则时会使 $f$ 尽可能长。例如，对于 $[4]\hat{}[5]\hat{}[6]$，规则 5 应用于 $f = [4]\hat{}[5]$ 和 $g = [6]$（而不是将规则 5 应用于 $f = [4]$ 和 $g = [5]\hat{}[6]$）。

为了准备考试，JOI-kun 准备了一个长度为 $N$ 的 IOI 函数 $S$，并打算练习确定该 IOI 函数将 $Q$ 个整数 $X_1, X_2, \dots, X_Q$ 映射到的布尔值。他请求你的帮助，因为你擅长处理 IOI 函数，请编写一个示例解决方案。

编写一个程序，给定 $N, Q, S$ 以及 $X_1, X_2, \dots, X_Q$，确定 IOI 函数 $S$ 将整数 $X_1, X_2, \dots, X_Q$ 映射到的布尔值。

输入格式

输入通过标准输入按以下格式给出：

$N \ Q$ $S$ $X_1$ $X_2$ $\vdots$ $X_Q$

输出格式

向标准输出打印 $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$ 是一个长度为 $N$ 的 IOI 函数。
• $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$ 中至少有一个是由规则 1 得到的 IOI 函数。
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

样例输入 2

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

样例输出 2

True
False
False
True

样例输入 3

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

样例输出 3

True
True
True
False