---

4163. 「JOI Open 2024」考试 2

题目描述

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

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

1. 把 $1$ 到 $10^{9}$ 之间的整数 $a$ 写成 [a] 的形式，就是一个 IOI 函数（其中，a 是用十进制表示 $a$ 得到的字符串）。这个 IOI 函数把大于等于 $a$ 的整数对应到 True，把小于 $a$ 的整数对应到 False。
2. 如果 f 是一个 IOI 函数，那么 (f) 也是一个 IOI 函数。这个 IOI 函数把 f 对应到 True 的整数对应到 True，把 f 对应到 False 的整数对应到 False。
3. 如果 f 是一个 IOI 函数，那么 !f 也是一个 IOI 函数。这个 IOI 函数把 f 对应到 True 的整数对应到 False，把 f 对应到 False 的整数对应到 True。
4. 如果 f 和 g 都是 IOI 函数，那么 f&g 也是一个 IOI 函数。这个 IOI 函数把 f 和 g 都对应到 True 的整数对应到 True，把其他的整数对应到 False。
5. 如果 f 和 g 都是 IOI 函数，那么 f^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]^[5]^[6]，就按照规则 $5$ 来处理，把 f=[4]^[5]，g=[6]，而不是按照规则 $5$ 来处理，把 f=[4]，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}$ 的真假值。

---

样例 1

输入

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

输出

True
False
True
False
False

解释

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

| $X_{i}$ | ![2] | [3] | ![2]|[3] | ![4] | (![2]|[3])&![4] | |---------|--------|-------|-------------|---------|-------------------| | 1 | True | False | True | True | True | | 2 | False | False | False | True | False | | 3 | False | True | True | True | True | | 4 | False | True | True | False | False | | 5 | False | True | True | False | False |

---

样例 2

输入

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

输出

True
False
False
True

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

---

样例 3

输入

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)$ 都是整数

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

子任务	附加限制	分值
1	$S$ 不包含 & 和 `	`
2	$Q=1$	20
3	$N \leq 10000$	10
4	$S$ 不包含 ! 和 ^	6
5	$S$ 在得到的过程中，如果应用了规则 $4$ 或规则 $6$，那么 f 和 g 中至少有一个是由规则 $1$ 得到的 IOI 函数	12
6	$N \leq 4\times 10^5$	20
7	无附加限制	27

---