JOI-kun 喺 IOI High School 讀書，學校就快舉行期末考試。考試會測試學生可唔可以正確計出 IOI 函數嘅值。IOI 函數係按照 IOI High School 定義嘅以下六條規則之一得到嘅字串，會將 $1$ 至 $10^9$（包括兩端）嘅整數對應到布林值 True 或 False。
- 設 $a$ 係 $1$ 至 $10^9$（包括兩端）嘅整數，咁
[a]就係 IOI 函數（當中a係 $a$ 嘅十進制字串表示）。呢個 IOI 函數會將大於或等於 $a$ 嘅整數對應到True，將小於 $a$ 嘅整數對應到False。 - 設 $f$ 係 IOI 函數，咁
(f)都係 IOI 函數。呢個 IOI 函數對每個整數嘅對應值都同 $f$ 一樣。 - 設 $f$ 係 IOI 函數，咁
!f都係 IOI 函數。呢個 IOI 函數會將 $f$ 對應到True嘅整數對應到False，反之亦然。 - 設 $f$ 同 $g$ 係 IOI 函數，咁
f&g都係 IOI 函數。如果 $f$ 同 $g$ 都將一個整數對應到True，呢個 IOI 函數就會將佢對應到True；否則就對應到False。 - 設 $f$ 同 $g$ 係 IOI 函數，咁
f^g都係 IOI 函數。如果 $f$ 同 $g$ 之中恰好有一個將一個整數對應到True，呢個 IOI 函數就會將佢對應到True；否則就對應到False。 - 設 $f$ 同 $g$ 係 IOI 函數，咁
f|g都係 IOI 函數。如果 $f$ 同 $g$ 之中至少有一個將一個整數對應到True，呢個 IOI 函數就會將佢對應到True；否則就對應到False。
如果一個 IOI 函數可以用多條規則得到，就由編號較大嘅規則決定呢個 IOI 函數將整數對應到邊個布林值。例如，對於 [1]&[2]|[3]，會對 $f=$ [1]&[2] 同 $g=$ [3] 套用規則 $6$（而唔係對 $f=$ [1] 同 $g=$ [2]|[3] 套用規則 $4$）。另外，對於規則 $4,5,6$，套用規則時會令 $f$ 盡可能長。例如，對於 [4]^[5]^[6]，會對 $f=$ [4]^[5] 同 $g=$ [6] 套用規則 $5$（而唔係對 $f=$ [4] 同 $g=$ [5]^[6] 套用規則 $5$）。
為咗準備考試，JOI-kun 準備咗一個長度為 $N$ 嘅 IOI 函數 $S$，打算練習判斷呢個 IOI 函數會將 $Q$ 個整數 $X_1,X_2,\ldots,X_Q$ 對應到邊啲布林值。你擅長處理 IOI 函數，所以佢請你幫手寫一份參考答案。
畀定 $N,Q,S$ 同 $X_1,X_2,\ldots,X_Q$，請寫一個程式，判斷 IOI 函數 $S$ 會將整數 $X_1,X_2,\ldots,X_Q$ 對應到邊啲布林值。
輸入格式
輸入會由標準輸入按以下格式畀出：
$$ \begin{array}{l} N\ Q\\ S\\ X_1\\ X_2\\ \vdots\\ X_Q \end{array} $$
輸出格式
向標準輸出印出 $Q$ 行。第 $i$ 行（$1 \le i \le Q$）應該只包含一個布林值，表示 IOI 函數 $S$ 將整數 $X_i$ 對應到嘅值。
資料範圍
- $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$）都係整數。
子任務
- （$5$ 分）$S$ 唔包含
&或|。 - （$20$ 分）$Q=1$。
- （$10$ 分）$N \le 10\,000$。
- （$6$ 分）$S$ 唔包含
!或^。 - （$12$ 分）喺得到 $S$ 嘅過程中，每次套用規則 $4$ 或規則 $6$ 時，$f$ 同 $g$ 之中至少有一個係用規則 $1$ 得到嘅 IOI 函數。
- （$20$ 分）$N \le 400\,000$。
- （$27$ 分）冇額外限制。
樣例
輸入格式 1
15 5 (![2]|[3])&![4] 1 2 3 4 5
輸出格式 1
True False True False False
說明
按照題目規則得到 $S$ 嘅過程中出現嘅部分 IOI 函數，會將整數 $X_i$（$1 \le i \le Q$）對應到嘅布林值如下表所示。
| $X_i$ | ![2] |
[3] |
`![2]\ | [3]` | ![4] |
`(![2]\ | [3])&![4]` |
|---|---|---|---|---|---|---|---|
| $1$ | True |
False |
True |
True |
True |
||
| $2$ | False |
False |
False |
True |
False |
||
| $3$ | False |
True |
True |
True |
True |
||
| $4$ | False |
True |
True |
False |
False |
||
| $5$ | False |
True |
True |
False |
False |
呢筆樣例輸入符合子任務 $3,6,7$ 嘅限制。
輸入格式 2
20 4 (!![23])^((([116]))) 54 1 200 89
輸出格式 2
True False False True
說明
呢筆樣例輸入符合子任務 $1,3,5,6,7$ 嘅限制。
輸入格式 3
32 4 [2]|[5]&[1]|(([1000000000])|[7]) 4 10 6 1
輸出格式 3
True True True False
說明
呢筆樣例輸入符合子任務 $3,4,6,7$ 嘅限制。