JOI-kun は IOI 高校に通っており、もうすぐ期末試験があります。試験では、IOI 関数の値を正しく計算できるかが問われます。IOI 関数とは、IOI 高校が定めた次の 6 つの規則のいずれかによって得られる文字列で、$1$ 以上 $10^9$ 以下の整数を、True または False という真偽値に対応させるものです。

1. $a$ を $1$ 以上 $10^9$ 以下の整数とすると、[a] は IOI 関数です（ここで a は $a$ の十進表記の文字列です）。この IOI 関数は、$a$ 以上の整数を True に、$a$ 未満の整数を False に対応させます。
2. $f$ を IOI 関数とすると、(f) も IOI 関数です。この IOI 関数は、$f$ と同じ整数をそれぞれ True、False に対応させます。
3. $f$ を IOI 関数とすると、!f も IOI 関数です。この IOI 関数は、$f$ が True に対応させる整数を False に、$f$ が False に対応させる整数を True に対応させます。
4. $f,g$ を IOI 関数とすると、f&g も IOI 関数です。この IOI 関数は、$f,g$ がともに True に対応させる整数を True に、それ以外の整数を False に対応させます。
5. $f,g$ を IOI 関数とすると、f^g も IOI 関数です。この IOI 関数は、$f,g$ のちょうど一方が True に対応させる整数を True に、それ以外の整数を False に対応させます。
6. $f,g$ を IOI 関数とすると、f|g も IOI 関数です。この IOI 関数は、$f,g$ の少なくとも一方が True に対応させる整数を 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 つ出力してください。

制約

• $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$）は整数である。

小課題

1. (5 点) $S$ は & も | も含まない。
2. (20 点) $Q=1$。
3. (10 点) $N\le 10\,000$。
4. (6 点) $S$ は ! も ^ も含まない。
5. (12 点) $S$ を得る過程で規則 4 または規則 6 を適用したとき、$f,g$ の少なくとも一方は規則 1 によって得られた IOI 関数であった。
6. (20 点) $N\le 400\,000$。
7. (27 点) 追加の制約はない。

入出力例

入力 1

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

出力 1

True
False
True
False
False

注記

問題文の規則に従って $S$ を得る過程に現れる IOI 関数のうち、いくつかの IOI 関数が整数 $X_i$（$1\le i\le Q$）を対応させる真偽値を次の表に示します。

この入力例は小課題 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 の制約を満たします。