2024-open-t1_Examination_2 — JOI JOI_open
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: dynamic programming, small to large, link-cut tree, segment tree, tree decomposition

# Examination 2

JOI-kun goes to IOI High School, where the final exam is held soon. In the exam, students will be tested on whether they can correctly calculate the value of an IOI function. An IOI function is a string obtained by one of the following six rules defined by IOI High School, which maps integers between 1 and 10<sup>9</sup> (inclusive) to boolean values, either `True` or `False`.

1.  Let `a` be an integer between 1 and 10<sup>9</sup> (inclusive), then `[a]` is an IOI function (`a` is the string representation of `a` in decimal notation). This IOI function maps integers greater than or equal to `a` to `True`, and integers less than `a` to `False`.
2.  Let `f` be an IOI function, then `(f)` is also an IOI function. This IOI function maps the same integers to `True` and `False` as `f` does.
3.  Let `f` be an IOI function, then `!f` is also an IOI function. This IOI function maps integers that `f` maps to `True` to `False`, and vice versa.
4.  Let `f` and `g` be IOI functions, then `f&g` is also an IOI function. This IOI function maps integers to `True` if both `f` and `g` map them to `True`, and to `False` otherwise.
5.  Let `f` and `g` be IOI functions, then `f^g` is also an IOI function. This IOI function maps integers to `True` if exactly one of `f` or `g` maps them to `True`, and to `False` otherwise.
6.  Let `f` and `g` be IOI functions, then `f|g` is also an IOI function. This IOI function maps integers to `True` if at least one of `f` or `g` maps them to `True`, and to `False` otherwise.

If an IOI function is obtained using multiple rules, the rule with the higher number determines the boolean value that the IOI function maps integers to. For example, for `[1]&[2]|[3]`, rule 6 is applied to `f = [1]&[2]` and `g = [3]` (rather than applying rule 4 to `f = [1]` and `g = [2]|[3]`). Additionally, for rules 4, 5, and 6, the rule is applied so that `f` becomes as long as possible. For example, for `[4]^[5]^[6]`, rule 5 is applied to `f = [4]^[5]` and `g = [6]` (rather than applying rule 5 to `f = [4]` and `g = [5]^[6]`).

To prepare for the exam, JOI-kun has prepared an IOI function `S` of length `N` and intends to practice determining the boolean values that this IOI function maps `Q` integers `X1`, `X2`, ..., `XQ` to. He asks for your help, as you are proficient with handling IOI functions, to create a sample solution.

Write a program which, given `N`, `Q`, `S` and `X1`, `X2`, ..., `XQ`, determines the boolean values that the IOI function `S` maps integers `X1`, `X2`, ..., `XQ` to.

#### Input

The input is given from Standard Input in the following format:

```
N Q
S
X1
X2
...
XQ

Starter code: