题目描述

译自 JOI Open 2024 T1 「試験 2 / Examination 2」

JOI 君就读的 IOI 高中计划在近期举行期末考试。考试的内容是能否正确地计算出 IOI 高中自己制定的规则下的 IOI 函数的值。IOI 函数是指由以下 6 种规则中的任意一种得到的字符串，它们可以把 $1$ 到 $10^{9}$ 之间的整数对应到 True 或 False 的真假值。

1. 把 $1$ 到 $10^{9}$ 之间的整数 $a$ 写成 $\texttt{[a]}$ 的形式，就是一个 IOI 函数（其中，$\texttt{a}$ 是用十进制表示 $a$ 得到的字符串）。这个 IOI 函数把大于等于 $a$ 的整数对应到 True，把小于 $a$ 的整数对应到 False。
2. 如果 $\texttt{f}$ 是一个 IOI 函数，那么 $\texttt{(f)}$ 也是一个 IOI 函数。这个 IOI 函数把 $\texttt{f}$ 对应到 True 的整数对应到 True，把 f 对应到 False 的整数对应到 False。
3. 如果 $\texttt{f}$ 是一个 IOI 函数，那么 $\texttt{!f}$ 也是一个 IOI 函数。这个 IOI 函数把 $\texttt{f}$ 对应到 True 的整数对应到 False，把 $\texttt{f}$ 对应到 False 的整数对应到 True。
4. 如果 $\texttt{f}$ 和 $\texttt{g}$ 都是 IOI 函数，那么 \texttt{f&g} 也是一个 IOI 函数。这个 IOI 函数把 $\texttt{f}$ 和 $\texttt{g}$ 都对应到 True 的整数对应到 True，把其他的整数对应到 False。
5. 如果 $\texttt{f}$ 和 $\texttt{g}$ 都是 IOI 函数，那么 \texttt{f^g} 也是一个 IOI 函数。这个 IOI 函数把 $\texttt{f}$ 和 $\texttt{g}$ 中只有一个对应到 True 的整数对应到 True，把其他的整数对应到 False。
6. 如果 $\texttt{f}$ 和 $\texttt{g}$ 都是 IOI 函数，那么 $\texttt{f|g}$ 也是一个 IOI 函数。这个 IOI 函数把 $\texttt{f}$ 和 $\texttt{g}$ 中至少有一个对应到 True 的整数对应到 True，把其他的整数对应到 False。

如果一个 IOI 函数可以由多个规则得到，那么就按照规则的编号越大越优先的原则来确定 IOI 函数对应的真假值。例如，对于 \texttt{[1]&[2]|[3]}，就按照规则 6 来处理，把 \texttt{f=[1]&[2]}，$\texttt{g=[3]}$，而不是按照规则 4 来处理，把 $\texttt{f=[1]}$，$\texttt{g=[2]|[3]}$。另外，对于规则 4，5，6，要尽量让 $\texttt{f}$ 的长度更长。例如，对于 \texttt{[4]^[5]^[6]}，就按照规则 5 来处理，把 \texttt{f=[4]^[5]}，$\texttt{g=[6]}$，而不是按照规则 5 来处理，把 $\texttt{f=[4]}$，\texttt{g=[5]^[6]}。

JOI 君为了考试复习，准备了一个长度为 $N$ 的 IOI 函数 $S$，想要练习计算出 $Q$ 个整数 $X_{1}, X_{2}, \ldots, X_{Q}$ 对应的这个函数的真假值。于是，他请擅长处理 IOI 函数的你来帮他做一个参考答案。

给定 $N, Q, S$ 和 $X_{1}, X_{2}, \ldots, X_{Q}$，请你编写一个程序，求出 JOI 君准备的 IOI 函数对 $X_{1}, X_{2}, \ldots, X_{Q}$ 的真假值。

输入格式

第一行两个整数 $N,Q$。

接下来一行，包含一个字符串 $S$。

接下来 $Q$ 行，每行一个整数 $X_i$。

输出格式

输出 $Q$ 行。第 $i\ (1 \leq i \leq Q)$ 行输出 JOI 君准备的 IOI 函数对整数 $X_{i}$ 的真假值。

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

True
False
True
False
False

按照问题文中的规则得到 $S$ 的过程中出现的一部分 IOI 函数，它们对各个 $X_{i}(1 \leq i \leq Q)$ 的真假值如下表所示。

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

True
False
False
True

这组样例满足子任务 $3,6,7$ 的限制。

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

True
True
True
False

这组样例满足子任务 $3,4,6,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 2\times 10^5$
• $S$ 是一个长度为 $N$ 的 IOI 函数
• $1 \leq X_{i} \leq 10^{9}\ (1 \leq i \leq Q)$
• $N, Q$ 和 $X_{i}\ (1 \leq i \leq Q)$ 都是整数

详细子任务附加限制及分值如下表所示。