JOI-kun chodzi do IOI High School, gdzie wkrótce odbędzie się egzamin końcowy. Na egzaminie sprawdzane będzie, czy uczniowie potrafią poprawnie obliczać wartość funkcji IOI. Funkcja IOI jest napisem otrzymanym za pomocą jednej z sześciu poniższych reguł zdefiniowanych przez IOI High School. Przyporządkowuje ona liczbom całkowitym od $1$ do $10^9$ włącznie wartości logiczne True lub False.

1. Niech $a$ będzie liczbą całkowitą od $1$ do $10^9$ włącznie. Wtedy [a] jest funkcją IOI (litera a oznacza zapis dziesiętny liczby $a$). Ta funkcja IOI przyporządkowuje liczbom całkowitym większym lub równym $a$ wartość True, a liczbom mniejszym od $a$ wartość False.
2. Niech $f$ będzie funkcją IOI. Wtedy (f) również jest funkcją IOI. Przyporządkowuje ona wartości True i False tym samym liczbom całkowitym co $f$.
3. Niech $f$ będzie funkcją IOI. Wtedy !f również jest funkcją IOI. Przyporządkowuje ona wartość False liczbom, którym $f$ przyporządkowuje True, i odwrotnie.
4. Niech $f$ i $g$ będą funkcjami IOI. Wtedy f&g również jest funkcją IOI. Przyporządkowuje ona liczbie całkowitej True, jeśli zarówno $f$, jak i $g$ przyporządkowują jej True, a w przeciwnym razie False.
5. Niech $f$ i $g$ będą funkcjami IOI. Wtedy f^g również jest funkcją IOI. Przyporządkowuje ona liczbie całkowitej True, jeśli dokładnie jedna z funkcji $f$ i $g$ przyporządkowuje jej True, a w przeciwnym razie False.
6. Niech $f$ i $g$ będą funkcjami IOI. Wtedy f|g również jest funkcją IOI. Przyporządkowuje ona liczbie całkowitej True, jeśli przynajmniej jedna z funkcji $f$ i $g$ przyporządkowuje jej True, a w przeciwnym razie False.

Jeśli funkcję IOI można otrzymać za pomocą wielu reguł, o przyporządkowywanych wartościach logicznych decyduje reguła o większym numerze. Na przykład dla [1]&[2]|[3] regułę 6 stosuje się do $f=$ [1]&[2] i $g=$ [3] (zamiast stosować regułę 4 do $f=$ [1] i $g=$ [2]|[3]). Ponadto w regułach 4, 5 i 6 regułę stosuje się tak, aby $f$ było jak najdłuższe. Na przykład dla [4]^[5]^[6] regułę 5 stosuje się do $f=$ [4]^[5] i $g=$ [6] (zamiast stosować regułę 5 do $f=$ [4] i $g=$ [5]^[6]).

Aby przygotować się do egzaminu, JOI-kun przygotował funkcję IOI $S$ długości $N$ i zamierza ćwiczyć wyznaczanie wartości logicznych, które ta funkcja przyporządkowuje $Q$ liczbom całkowitym $X_1,X_2,\ldots,X_Q$. Ponieważ dobrze radzisz sobie z funkcjami IOI, prosi cię o pomoc w stworzeniu przykładowego rozwiązania.

Napisz program, który na podstawie $N$, $Q$, $S$ oraz $X_1,X_2,\ldots,X_Q$ wyznacza wartości logiczne, które funkcja IOI $S$ przyporządkowuje liczbom całkowitym $X_1,X_2,\ldots,X_Q$.

Wejście

Dane są podane na standardowym wejściu w następującym formacie:

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

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. $i$-ty wiersz ($1\le i\le Q$) powinien zawierać jedną wartość logiczną, którą funkcja IOI $S$ przyporządkowuje liczbie całkowitej $X_i$.

Ograniczenia

• $1\le N\le1\,000\,000$.
• $1\le Q\le200\,000$.
• $S$ jest funkcją IOI długości $N$.
• $1\le X_i\le10^9$ ($1\le i\le Q$).
• $N$, $Q$ i $X_i$ ($1\le i\le Q$) są liczbami całkowitymi.

Podzadania

1. (5 punktów) $S$ nie zawiera & ani |.
2. (20 punktów) $Q=1$.
3. (10 punktów) $N\le10\,000$.
4. (6 punktów) $S$ nie zawiera ! ani ^.
5. (12 punktów) Gdy w procesie otrzymywania $S$ stosowano regułę 4 lub regułę 6, przynajmniej jedna z funkcji $f$ i $g$ była funkcją IOI otrzymaną za pomocą reguły 1.
6. (20 punktów) $N\le400\,000$.
7. (27 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

True
False
True
False
False

Uwagi

Dla niektórych funkcji IOI pojawiających się w procesie otrzymywania $S$ zgodnie z regułami z treści zadania wartości logiczne przyporządkowane liczbom całkowitym $X_i$ ($1\le i\le Q$) są przedstawione w poniższej tabeli.

Ten przykład spełnia ograniczenia podzadań 3, 6 i 7.

Wejście 2

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

Wyjście 2

True
False
False
True

Uwagi

Ten przykład spełnia ograniczenia podzadań 1, 3, 5, 6 i 7.

Wejście 3

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

Wyjście 3

True
True
True
False

Uwagi

Ten przykład spełnia ograniczenia podzadań 3, 4, 6 i 7.