JOI-kun học tại trường trung học IOI và sắp tham gia kỳ thi cuối kỳ. Bài thi 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 bằng một trong sáu quy tắc dưới đây, do trường IOI định nghĩa. Mỗi hàm ánh xạ các số nguyên từ \(1\) đến \(10^9\) thành một trong hai giá trị logic True hoặc False.

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

Nếu một xâu có thể được tạo bằng nhiều quy tắc, chọn quy tắc có số thứ tự lớn nhất làm bước tạo hàm cuối cùng để xác định giá trị của hàm. Chẳng hạn, với [1]&[2]|[3], áp dụng quy tắc \(6\) cho f = [1]&[2], g = [3], thay vì áp dụng quy tắc \(4\) cho f = [1], g = [2]|[3]. Ngoài ra, khi áp dụng quy tắc \(4\), \(5\) hoặc \(6\), chọn f dài nhất có thể. Chẳng hạn, với [4]^[5]^[6], áp dụng quy tắc \(5\) cho f = [4]^[5], g = [6], thay vì chọn f = [4], g = [5]^[6].

Để ôn thi, JOI-kun đã chuẩn bị một hàm IOI \(S\) có độ dài \(N\) và muốn luyện xác định giá trị mà hàm này trả về cho \(Q\) số nguyên \(X_1,X_2,\ldots,X_Q\). Biết bạn thành thạo về hàm IOI, cậu nhờ bạn viết một lời giải mẫu.

Cho \(N,Q,S\) và \(X_1,X_2,\ldots,X_Q\), hãy xác định giá trị logic mà hàm IOI \(S\) trả về cho từng số \(X_i\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N Q
S
X_1
X_2
...
X_Q

Dữ liệu ra

Xuất \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(i\) (\(1\le i\le Q\)) chứa giá trị logic True hoặc False mà hàm IOI \(S\) trả về cho \(X_i\).

Ràng buộc

• \(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\) với \(1\le i\le Q\).
• \(N,Q,X_i\) (\(1\le i\le Q\)) đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

Ví dụ

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

True
False
True
False
False

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

True
False
False
True

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

True
True
True
False

Nguồn

JOI Open Contest 2024, bài Examination 2, tác giả Ryomei Sugai.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.