JOI-kun học tại IOI High School, nơi sắp tổ chức kỳ thi cuối kỳ. Trong kỳ thi, học sinh sẽ được kiểm tra khả năng tính đúng giá trị của một hàm IOI. Hàm IOI là một xâu được tạo ra bằng một trong sáu quy tắc sau do IOI High School định nghĩa, ánh xạ các số nguyên từ $1$ đến $10^9$ (bao gồm hai đầu mút) tới các giá trị Boolean True hoặc False.

1. Cho $a$ là một số nguyên từ $1$ đến $10^9$ (bao gồm hai đầu mút), khi đó [a] là một hàm IOI (a là biểu diễn dạng xâu của $a$ trong hệ thập phân). Hàm IOI này ánh xạ các số nguyên lớn hơn hoặc bằng $a$ tới True, và các số nguyên nhỏ hơn $a$ tới False.
2. Cho $f$ là một hàm IOI, khi đó (f) cũng là một hàm IOI. Hàm IOI này ánh xạ các số nguyên tới True và False giống như $f$.
3. Cho $f$ là một hàm IOI, khi đó !f cũng là một hàm IOI. Hàm IOI này ánh xạ các số nguyên mà $f$ ánh xạ tới True thành False, và ngược lại.
4. Cho $f$ và $g$ là các hàm IOI, khi đó f&g cũng là một hàm IOI. Hàm IOI này ánh xạ một số nguyên tới True nếu cả $f$ và $g$ đều ánh xạ số đó tới True, và tới False trong trường hợp ngược lại.
5. Cho $f$ và $g$ là các hàm IOI, khi đó f^g cũng là một hàm IOI. Hàm IOI này ánh xạ một số nguyên tới True nếu đúng một trong hai hàm $f$ hoặc $g$ ánh xạ số đó tới True, và tới False trong trường hợp ngược lại.
6. Cho $f$ và $g$ là các hàm IOI, khi đó f|g cũng là một hàm IOI. Hàm IOI này ánh xạ một số nguyên tới True nếu ít nhất một trong hai hàm $f$ hoặc $g$ ánh xạ số đó tới True, và tới False trong trường hợp ngược lại.

Nếu một hàm IOI có thể được tạo ra bằng nhiều quy tắc, quy tắc có số thứ tự lớn hơn sẽ xác định giá trị Boolean mà hàm IOI ánh xạ các số nguyên tới. Ví dụ, với [1]&[2]|[3], quy tắc 6 được áp dụng cho $f=$ [1]&[2] và $g=$ [3] (thay vì áp dụng quy tắc 4 cho $f=$ [1] và $g=$ [2]|[3]). Ngoài ra, đối với các quy tắc 4, 5 và 6, quy tắc được áp dụng sao cho $f$ dài nhất có thể. Ví dụ, với [4]^[5]^[6], quy tắc 5 được áp dụng cho $f=$ [4]^[5] và $g=$ [6] (thay vì áp dụng quy tắc 5 cho $f=$ [4] và $g=$ [5]^[6]).

Để chuẩn bị cho kỳ thi, JOI-kun đã chuẩn bị một hàm IOI $S$ có độ dài $N$ và muốn luyện tập xác định các giá trị Boolean mà hàm này ánh xạ $Q$ số nguyên $X_1,X_2,\ldots,X_Q$ tới. Vì bạn thành thạo việc xử lý các hàm IOI, cậu nhờ bạn giúp tạo một lời giải mẫu.

Hãy viết chương trình, khi được cho $N$, $Q$, $S$ và $X_1,X_2,\ldots,X_Q$, xác định các giá trị Boolean mà hàm IOI $S$ ánh xạ các số nguyên $X_1,X_2,\ldots,X_Q$ tới.

Dữ liệu vào

Dữ liệu vào được cho từ đầu vào chuẩn theo định dạng sau:

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

Dữ liệu ra

In $Q$ dòng ra đầu ra chuẩn. Dòng thứ $i$ ($1 \le i \le Q$) phải chứa một giá trị Boolean duy nhất mà hàm IOI $S$ ánh xạ số nguyên $X_i$ tới.

Giới hạn

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ là một hàm IOI có độ dài $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N$, $Q$ và $X_i$ ($1 \le i \le Q$) là các số nguyên.

Nhiệm vụ con

1. (5 điểm) $S$ không chứa & hoặc |.
2. (20 điểm) $Q=1$.
3. (10 điểm) $N \le 10\,000$.
4. (6 điểm) $S$ không chứa ! hoặc ^.
5. (12 điểm) Khi quy tắc 4 hoặc quy tắc 6 được áp dụng trong quá trình tạo ra $S$, ít nhất một trong hai hàm $f$ hoặc $g$ là một hàm IOI được tạo ra từ quy tắc 1.
6. (20 điểm) $N \le 400\,000$.
7. (27 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

True
False
True
False
False

Ghi chú

Đối với một số hàm IOI xuất hiện trong quá trình tạo ra $S$ theo các quy tắc trong đề bài, các giá trị Boolean mà chúng ánh xạ các số nguyên $X_i$ ($1 \le i \le Q$) tới được thể hiện trong bảng sau.

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $3$, $6$ và $7$.

Dữ liệu vào 2

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

Dữ liệu ra 2

True
False
False
True

Ghi chú

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $1$, $3$, $5$, $6$ và $7$.

Dữ liệu vào 3

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

Dữ liệu ra 3

True
True
True
False

Ghi chú

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $3$, $4$, $6$ và $7$.