题目描述

JOI 君在 IOI 高中上学，期末考试即将来临。考试的内容是计算 IOI 函数。IOI 函数是将 $[1,10^9]$ 之间的整数映射到布尔值（即 $\texttt{True}/\texttt{False}$）的函数。IOI 函数可以从以下六条 IOI 高中规定的规则中构造：

1. 设 $a$ 为 $[1,10^9]$ 之间的整数，则 $\texttt{[a]}$ 是一个 IOI 函数。它将不小于 $a$ 的整数映射成 $\texttt{True}$，将小于 $a$ 的整数映射成 $\texttt{False}$。

2. 记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{(f)}$ 是一个 IOI 函数，它的映射规则与 $\texttt{f}$ 的映射规则相同。

3. 记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{!f}$ 是一个 IOI 函数。设 $x$ 为整数，若 $\texttt{f}$ 将 $x$ 映射为 $\texttt{True}$，则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{False}$；否则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{True}$。

4. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\&g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\&g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 都将 $x$ 映射为 $\texttt{True}$。

5. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\^ g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\^ g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中恰好有一个将 $x$ 映射为 $\texttt{True}$。

6. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f|g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f|g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中至少有一个将 $x$ 映射为 $\texttt{True}$。

如果某个 IOI 函数用多条规则构造出，数字更大的规则将决定函数值。例如，对于 $\texttt{[1]\&[2]|[3]}$ 应当应用规则 6，其中 $\texttt{f} = \texttt{[1]\&[2]},\texttt{g} = \texttt{[3]}$（而非应用规则 4，其中 $\texttt{f} = \texttt{[1]},\texttt{g} = \texttt{[2]|[3]}$）。额外地，对于规则 4，5，6，应当最大化 $\texttt{f}$ 的长度。例如，对于 $\texttt{[4]ˆ[5]ˆ[6]}$，应当在 $\texttt{f} = \texttt{[4]ˆ[5]},\texttt{g} = \texttt{[6]}$ 上应用规则 5（而非 $\texttt{f} = \texttt{[4]},\texttt{g} = \texttt{[5]ˆ[6]}$）。

为备战期末考试，JOI 君准备好了一个长度为 $N$ 的 IOI 函数 $S$。他打算用 $Q$ 个整数 $X_1,X_2,\cdots,X_Q$ 来练习他的计算技能。于是他找来了你——能够熟练处理 IOI 函数的人，来解决这个问题。

你需要写一个程序。给定 $N,Q,S$ 以及 $X_1,X_2,\cdots,X_Q$，对于 $i=1,2=\cdots,Q$，回答 IOI 函数 $S$ 会将 $X_i$ 映射成 $\texttt{True}$ 还是 $\texttt{False}$。

输入格式

输入格式如下所示：

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

输出格式

输出 $Q$ 行，第 $i$ 行为 $\texttt{True}$ 或者 $\texttt{False}$，即 $X_i$ 被 $S$ 映射成的值。

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

True
False
True
False
False

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

True
False
False
True

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

True
True
True
False

提示

样例解释

样例 $1$ 解释如下：

$X_i$	$\texttt{![2]}$	$\texttt{[3]}$	$\texttt{![2]|[3]}$	$\texttt{![4]}$	$\texttt{(![2]|[3])\&![4]}$
$1$	$\texttt{True}$	$\texttt{False}$	$\texttt{True}$	$\texttt{True}$	$\texttt{True}$
$2$	$\texttt{False}$		$\texttt{False}$		$\texttt{False}$
$3$		$\texttt{True}$			$\texttt{True}$
$4$				$\texttt{False}$
$5$

样例 $1$ 满足子任务 $3,6,7$ 的条件。

样例 $2$ 满足子任务 $1,3,5\sim 7$ 的条件。

样例 $3$ 满足子任务 $3,4,6,7$ 的条件。

数据范围

• $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$ points）$S$ 中不含 $\texttt{\&}$ 和 $\texttt{|}$；
2. （$20$ points）$Q = 1$；
3. （$10$ points）$N \le 10\,000$；
4. （$6$ points）$S$ 中不含 $\texttt{!}$ 和 $\texttt{ˆ}$；
5. （$12$ points）当应用规则 4 或 6 来构造 $S$ 时，$\texttt{f}$ 和 $\texttt{g}$ 中至少有一个是用规则 1 得到的；
6. （$20$ points）$N \le 400\, 000$；
7. （$27$ points）无额外约束。

*赛时公告：如果你复制题面中的 LaTeX，可能会得到 ˆ，但实际上是 ^。请特别注意。

由 Starrykiller 根据英文题面翻译。