Problem Description

JOI is attending IOI High School, where the final exams are approaching. The exam content involves calculating the IOI function. The IOI function maps integers in the range $[1, 10^9]$ to boolean values (i.e., $\texttt{True}/\texttt{False}$). The IOI function can be constructed from the following six rules specified by IOI High School:

1. Let $a$ be an integer in the range $[1, 10^9]$, then $\texttt{[a]}$ is an IOI function. It maps integers greater than or equal to $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 with the same mapping rules as $\texttt{f}$.

3. Let $\texttt{f}$ be an IOI function, then $\texttt{!f}$ is an IOI function. For an integer $x$, 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}$ and $\texttt{g}$ be IOI functions, then $\texttt{f\&g}$ is also an IOI function. For an integer $x$, $\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}$ and $\texttt{g}$ be IOI functions, then $\texttt{f\^ g}$ is also an IOI function. For an integer $x$, $\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}$ and $\texttt{g}$ be IOI functions, then $\texttt{f|g}$ is also an IOI function. For an integer $x$, $\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 is constructed using multiple rules, the rule with the larger number will determine the function value. For example, for $\texttt{[1]\&[2]|[3]}$, rule 6 should be applied where $\texttt{f} = \texttt{[1]\&[2]}$ and $\texttt{g} = \texttt{[3]}$ (rather than applying rule 4 where $\texttt{f} = \texttt{[1]}$ and $\texttt{g} = \texttt{[2]|[3]}$). Additionally, for rules 4, 5, and 6, the length of $\texttt{f}$ should be maximized. For example, for $\texttt{[4]ˆ[5]ˆ[6]}$, rule 5 should be applied on $\texttt{f} = \texttt{[4]ˆ[5]}$ and $\texttt{g} = \texttt{[6]}$ (rather than $\texttt{f} = \texttt{[4]}$ and $\texttt{g} = \texttt{[5]ˆ[6]}$).

To prepare for the final exam, JOI has prepared an IOI function $S$ of length $N$. He plans to practice his computational skills with $Q$ integers $X_1, X_2, \cdots, X_Q$. He has come to you, a person skilled in handling IOI functions, to solve this problem.

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

Input Format

The input is formatted as follows:

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

Output Format

Output $Q$ lines, where the $i$-th line is either $\texttt{True}$ or $\texttt{False}$, indicating the value to which $X_i$ is mapped by $S$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

True
False
True
False
False

Sample Input #2

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

Sample Output #2

True
False
False
True

Sample Input #3

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

Sample Output #3

True
True
True
False

Notes

Sample Explanation

The explanation for Sample 1 is as follows:

Sample 1 meets the conditions of Subtasks 3, 6, and 7.

Sample 2 meets the conditions of Subtasks 1, 3, 5 through 7.

Sample 3 meets the conditions of Subtasks 3, 4, 6, and 7.

Data Range

• $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, X_i$ ($1 \le i \le Q$) are all integers.

Subtasks

1. ($5$ points) $S$ does not contain $\texttt{\&}$ and $\texttt{|}$;
2. ($20$ points) $Q = 1$;
3. ($10$ points) $N \le 10\,000$;
4. ($6$ points) $S$ does not contain $\texttt{!}$ and $\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.

*Notice during the contest: If you copy the LaTeX from the problem statement, you might get ˆ, but it should actually be ^. Please pay special attention to this.

Translated by Starrykiller based on the English problem statement.

见题面 Input 部分

见题面 Output 部分