Problem Description

JOI-kun studies at IOI High School, and the final exams are coming soon. The exam topic is computing the IOI function. An IOI function maps integers in $[1,10^9]$ to boolean values (i.e., $\texttt{True}/\texttt{False}$). An IOI function can be constructed using the following six rules specified by IOI High School:

1. Let $a$ be an integer in $[1,10^9]$. Then $\texttt{[a]}$ is an IOI function. It maps integers not less than $a$ to $\texttt{True}$, and integers less than $a$ to $\texttt{False}$.

2. Let $\texttt{f}$ be an IOI function. Then $\texttt{(f)}$ is an IOI function, and its mapping rule is the same as that of $\texttt{f}$.

3. Let $\texttt{f}$ be an IOI function. Then $\texttt{!f}$ is an IOI function. Let $x$ be an integer. If $\texttt{f}$ maps $x$ to $\texttt{True}$, then $\texttt{!f}$ maps $x$ to $\texttt{False}$; otherwise, $\texttt{!f}$ maps $x$ to $\texttt{True}$.

4. Let $\texttt{f},\texttt{g}$ be IOI functions. Then $\texttt{f\&g}$ is also an IOI function. Let $x$ be an integer. Then $\texttt{f\&g}$ maps $x$ to $\texttt{True}$ if and only if both $\texttt{f}$ and $\texttt{g}$ map $x$ to $\texttt{True}$.

5. Let $\texttt{f},\texttt{g}$ be IOI functions. Then $\texttt{f\^ g}$ is also an IOI function. Let $x$ be an integer. Then $\texttt{f\^ g}$ maps $x$ to $\texttt{True}$ if and only if exactly one of $\texttt{f}$ and $\texttt{g}$ maps $x$ to $\texttt{True}$.

6. Let $\texttt{f},\texttt{g}$ be IOI functions. Then $\texttt{f|g}$ is also an IOI function. Let $x$ be an integer. Then $\texttt{f|g}$ maps $x$ to $\texttt{True}$ if and only if at least one of $\texttt{f}$ and $\texttt{g}$ maps $x$ to $\texttt{True}$.

If an IOI function can be constructed by multiple rules, the rule with the larger number determines the function value. For example, for $\texttt{[1]\&[2]|[3]}$, you should apply rule 6, where $\texttt{f} = \texttt{[1]\&[2]}$ and $\texttt{g} = \texttt{[3]}$ (instead of applying rule 4, where $\texttt{f} = \texttt{[1]}$ and $\texttt{g} = \texttt{[2]|[3]}$). In addition, for rules 4, 5, and 6, you should maximize the length of $\texttt{f}$. For example, for $\texttt{[4]ˆ[5]ˆ[6]}$, you should apply rule 5 with $\texttt{f} = \texttt{[4]ˆ[5]}$ and $\texttt{g} = \texttt{[6]}$ (instead of $\texttt{f} = \texttt{[4]}$ and $\texttt{g} = \texttt{[5]ˆ[6]}$).

To prepare for the final exams, JOI-kun has prepared an IOI function $S$ of length $N$. He plans to practice his computation skills using $Q$ integers $X_1,X_2,\cdots,X_Q$. So he asked you, who can skillfully handle IOI functions, to solve this problem.

You need to write a program. Given $N,Q,S$ and $X_1,X_2,\cdots,X_Q$, for $i=1,2,\cdots,Q$, answer whether the IOI function $S$ maps $X_i$ to $\texttt{True}$ or $\texttt{False}$.

Input Format

The input format is as follows:

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

Output Format

Output $Q$ lines. The $i$-th line should be $\texttt{True}$ or $\texttt{False}$, which is the value that $S$ maps $X_i$ to.

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

Hint

Sample Explanation

The explanation for sample $1$ is as follows:

Sample $1$ satisfies the conditions of subtasks $3,6,7$.

Sample $2$ satisfies the conditions of subtasks $1,3,5\sim 7$.

Sample $3$ satisfies the conditions of subtasks $3,4,6,7$.

Constraints

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ is an IOI function of length $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N$, $Q$, and $X_i$ ($1 \le i \le Q$) are all integers.

Subtasks

1. ($5$ points) $S$ does not contain $\texttt{\&}$ or $\texttt{|}$.
2. ($20$ points) $Q = 1$.
3. ($10$ points) $N \le 10\,000$.
4. ($6$ points) $S$ does not contain $\texttt{!}$ or $\texttt{ˆ}$.
5. ($12$ points) When applying rule 4 or 6 to construct $S$, at least one of $\texttt{f}$ and $\texttt{g}$ is obtained by rule 1.
6. ($20$ points) $N \le 400\, 000$.
7. ($27$ points) No additional constraints.

*Contest announcement: If you copy the LaTeX in the statement, you might get ˆ, but it is actually ^. Please pay special attention.

Translated from the English statement by Starrykiller.

Translated by ChatGPT 5