P10626 [JOI Open 2024] Examination 2 / Examination 2

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}$.

The input format is as follows: > $N$ $Q$\ > $S$\ > $X_1$\ > $X_2$\ > $\vdots$\ > $X_Q$

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

### Sample Explanation The explanation for sample $1$ is as follows: | $X_i$ | $\texttt{![2]}$ | $\texttt{[3]}$ | $\texttt{![2]\char124[3]}$ | $\texttt{![4]}$ | $\texttt{(![2]\char124[3])\&![4]}$ | | :--: | :--: | :--: | :--: | :--: | :--: | | $1$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ | | $2$ | $\texttt{False}$ | $\texttt{False}$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{False}$ | | $3$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ | | $4$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{False}$ | | $5$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{False}$ | 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