JOI-kun besucht die IOI High School, an der bald die Abschlussprüfung stattfindet. In der Prüfung wird getestet, ob die Schüler den Wert einer IOI-Funktion korrekt berechnen können. Eine IOI-Funktion ist eine Zeichenkette, die nach einer der folgenden sechs von der IOI High School festgelegten Regeln gebildet wird und ganze Zahlen zwischen $1$ und $10^9$ (einschließlich) auf boolesche Werte, entweder True oder False, abbildet.

1. Sei $a$ eine ganze Zahl zwischen $1$ und $10^9$ (einschließlich). Dann ist [a] eine IOI-Funktion (a ist die Darstellung von $a$ als Zeichenkette in Dezimalschreibweise). Diese IOI-Funktion bildet ganze Zahlen größer oder gleich $a$ auf True und ganze Zahlen kleiner als $a$ auf False ab.
2. Sei $f$ eine IOI-Funktion. Dann ist auch (f) eine IOI-Funktion. Diese IOI-Funktion bildet dieselben ganzen Zahlen auf True beziehungsweise False ab wie $f$.
3. Sei $f$ eine IOI-Funktion. Dann ist auch !f eine IOI-Funktion. Diese IOI-Funktion bildet ganze Zahlen, die $f$ auf True abbildet, auf False ab und umgekehrt.
4. Seien $f$ und $g$ IOI-Funktionen. Dann ist auch f&g eine IOI-Funktion. Diese IOI-Funktion bildet ganze Zahlen auf True ab, wenn sowohl $f$ als auch $g$ sie auf True abbilden, und andernfalls auf False.
5. Seien $f$ und $g$ IOI-Funktionen. Dann ist auch f^g eine IOI-Funktion. Diese IOI-Funktion bildet ganze Zahlen auf True ab, wenn genau eine der Funktionen $f$ und $g$ sie auf True abbildet, und andernfalls auf False.
6. Seien $f$ und $g$ IOI-Funktionen. Dann ist auch f|g eine IOI-Funktion. Diese IOI-Funktion bildet ganze Zahlen auf True ab, wenn mindestens eine der Funktionen $f$ und $g$ sie auf True abbildet, und andernfalls auf False.

Kann eine IOI-Funktion mithilfe mehrerer Regeln gebildet werden, bestimmt die Regel mit der höheren Nummer den booleschen Wert, auf den die IOI-Funktion ganze Zahlen abbildet. Beispielsweise wird bei [1]&[2]|[3] Regel 6 auf $f=$ [1]&[2] und $g=$ [3] angewendet (anstatt Regel 4 auf $f=$ [1] und $g=$ [2]|[3] anzuwenden). Außerdem werden die Regeln 4, 5 und 6 so angewendet, dass $f$ möglichst lang ist. Beispielsweise wird bei [4]^[5]^[6] Regel 5 auf $f=$ [4]^[5] und $g=$ [6] angewendet (anstatt Regel 5 auf $f=$ [4] und $g=$ [5]^[6] anzuwenden).

Zur Vorbereitung auf die Prüfung hat JOI-kun eine IOI-Funktion $S$ der Länge $N$ vorbereitet und möchte üben, die booleschen Werte zu bestimmen, auf die diese IOI-Funktion die $Q$ ganzen Zahlen $X_1,X_2,\ldots,X_Q$ abbildet. Da du dich gut mit IOI-Funktionen auskennst, bittet er dich, eine Musterlösung zu erstellen.

Schreibe ein Programm, das für gegebene $N$, $Q$, $S$ und $X_1,X_2,\ldots,X_Q$ die booleschen Werte bestimmt, auf die die IOI-Funktion $S$ die ganzen Zahlen $X_1,X_2,\ldots,X_Q$ abbildet.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

$$ \begin{gathered} N\ Q\\ S\\ X_1\\ X_2\\ \vdots\\ X_Q \end{gathered} $$

Ausgabe

Gib $Q$ Zeilen auf der Standardausgabe aus. Die $i$-te Zeile ($1 \le i \le Q$) soll genau den booleschen Wert enthalten, auf den die IOI-Funktion $S$ die ganze Zahl $X_i$ abbildet.

Beschränkungen

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ ist eine IOI-Funktion der Länge $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N$, $Q$ und $X_i$ ($1 \le i \le Q$) sind ganze Zahlen.

Teilaufgaben

1. (5 Punkte) $S$ enthält weder & noch |.
2. (20 Punkte) $Q=1$.
3. (10 Punkte) $N \le 10\,000$.
4. (6 Punkte) $S$ enthält weder ! noch ^.
5. (12 Punkte) Wenn bei der Bildung von $S$ Regel 4 oder Regel 6 angewendet wurde, war mindestens eine der Funktionen $f$ und $g$ eine nach Regel 1 gebildete IOI-Funktion.
6. (20 Punkte) $N \le 400\,000$.
7. (27 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

True
False
True
False
False

Hinweis

Für einige der IOI-Funktionen, die bei der Bildung von $S$ nach den Regeln in der Aufgabenstellung auftreten, zeigt die folgende Tabelle die booleschen Werte, auf die sie die ganzen Zahlen $X_i$ ($1 \le i \le Q$) abbilden.

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 3, 6 und 7.

Eingabe 2

20 4
(!![23])^((([116])))
54
1
200
89

Ausgabe 2

True
False
False
True

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 3, 5, 6 und 7.

Eingabe 3

32 4
[2]|[5]&[1]|(([1000000000])|[7])
4
10
6
1

Ausgabe 3

True
True
True
False

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 3, 4, 6 und 7.