JOI-kun 就讀的 IOI 高中即將舉行期末考。考試將測驗學生能否正確計算 IOI 函數的值。IOI 函數是依照 IOI 高中定義的下列六條規則之一得到的字串，會將 $1$ 到 $10^9$（含兩端）之間的整數對應到布林值 True 或 False。
- 設 $a$ 是 $1$ 到 $10^9$（含兩端）之間的整數，則
[a]是 IOI 函數（其中的a是 $a$ 的十進位字串表示）。這個 IOI 函數將大於等於 $a$ 的整數對應到True，小於 $a$ 的整數對應到False。 - 設 $f$ 是 IOI 函數，則
(f)也是 IOI 函數。這個 IOI 函數將各個整數對應到的True或False與 $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$ 的限制。