Tiểu Z đang tự học kiến thức về máy tính lượng tử. Gần đây, khi nghiên cứu chương truyền thông lượng tử, cậu gặp một bài toán thú vị. Alice và Bob đang liên lạc lượng tử, dùng ngôn ngữ là một từ điển $S$ gồm $n$ từ. Mỗi từ $s_i$ ($1\le i\le n$) được biểu diễn bằng một xâu nhị phân dài $256$ bit. Trong bài này, có thể sinh $s_i$ bằng hàm gen trong tệp gen.cpp của thư mục bài; các tham số n, a1, a2 được cho trong dữ liệu vào.

Alice và Bob sẽ liên lạc $m$ lần, mỗi lần Alice truyền cho Bob đúng một từ trong từ điển. Nhưng kênh truyền không đáng tin cậy, có thể bị nhiễu. Với lần truyền thứ $i$, gọi từ gốc Alice gửi là $x_i$. Nhiễu có thể lật nhiều nhất $k_i$ bit của xâu này. Nghĩa là xâu $y_i$ Bob nhận được có thể khác $x_i$ ở nhiều nhất $k_i$ bit, và $y_i$ có thể không nằm trong $S$.

Bob còn biết kẻ xấu Eve đã xâm nhập kênh truyền và chuẩn bị can thiệp. Eve có thể đổi xâu Bob nhận được thành một xâu nhị phân $256$ bit bất kỳ, có thể không nằm trong $S$. Eve rất xảo quyệt và không nhất thiết can thiệp vào mọi lần liên lạc.

Bob nhờ bạn giúp đỡ. Với mỗi lần liên lạc tiếp theo, dựa vào xâu Bob nhận được cuối cùng và ngưỡng nhiễu $k_i$ ($0\le k_i\le15$), hãy xác định có khả năng lần liên lạc này không bị Eve can thiệp hay không (tức là xâu Bob nhận có thể được tạo từ một từ trong từ điển bằng cách lật nhiều nhất $k_i$ bit). Nếu có khả năng không bị can thiệp, in ra $1$; nếu không, in ra $0$. Bob rất tin tưởng bạn nên bạn phải trả lời trực tuyến; yêu cầu cụ thể ở phần dữ liệu vào.

Để giảm thời gian đọc, xâu Bob nhận được được cho dưới dạng xâu thập lục phân dài $64$, gồm các chữ số từ 0 đến 9 và chữ cái in hoa A đến F; A đến F lần lượt biểu thị giá trị $10\sim15$.

Có thể đổi từng chữ số thập lục phân thành xâu nhị phân. Ví dụ: 5 ứng với 0101, A ứng với 1010, C ứng với 1100.

Dữ liệu vào

Đọc dữ liệu từ tệp qi.in.

Dòng đầu tiên chứa bốn số nguyên không âm $n,m,a_1,a_2$, lần lượt là kích thước từ điển, số lần liên lạc và giá trị ban đầu của các tham số a1, a2 trong hàm gen.

Bạn cần gọi hàm gen đã nêu để sinh danh sách từ trong chương trình của mình. Có thể sao chép và sử dụng mã trong gen.cpp; mảng boolean s[N+1][256] trong chương trình chứa tất cả các từ.

Mỗi dòng trong $m$ dòng tiếp theo chứa một xâu thập lục phân dài $64$ và một số nguyên không âm $k_i$, lần lượt mô tả xâu Bob nhận cuối cùng ở lần liên lạc thứ $i$ và ngưỡng nhiễu.

Để buộc trả lời trực tuyến, sau khi khôi phục xâu nhị phân $256$ bit từ xâu thập lục phân, bạn phải XOR từng bit với $lastans$ để nhận xâu thực sự Bob nhận trong lần liên lạc này. $lastans\in\{0,1\}$ là đáp án của truy vấn trước; trước truy vấn đầu tiên, $lastans$ được khởi tạo bằng $0$.

Lưu ý: khi dùng scanf và printf để đọc hoặc in biến kiểu unsigned long long, ký hiệu định dạng tương ứng là llu.

Dữ liệu ra

Ghi kết quả vào tệp qi.out.

Kết quả gồm $m$ dòng, mỗi dòng chứa số nguyên $0$ hoặc $1$, là đáp án cho truy vấn hiện tại.

Ví dụ truy vấn

Để dễ giải thích, xét trường hợp đơn giản hóa: cho trực tiếp các từ trong từ điển, giảm độ dài từ xuống $4$ và cho phép trả lời ngoại tuyến.

Xét từ điển có $n=2$, chứa 1010 và 0111.

Với truy vấn B = 1011 và $k_1=1$, đáp án là $1$, vì có thể lật bit thứ $4$ của 1010 để thu được xâu đó (đếm từ bit cao đến bit thấp, các ví dụ sau cũng vậy).

Với truy vấn 1 = 0001 và $k_2=2$, đáp án là $1$, vì có thể lật bit thứ $2,3$ của 0111.

Với truy vấn 1 = 0001 và $k_3=1$, đáp án là $0$.

• Lật nhiều nhất $1$ bit của 1010 có thể thu được 1010, 0010, 1110, 1000, 1011.
• Lật nhiều nhất $1$ bit của 0111 có thể thu được 0111, 1111, 0011, 0101, 0110.
• Không thể thu được 1 = 0001, nên nó chắc chắn là kết quả Eve can thiệp.

Ví dụ

Ví dụ 1

Xem các tệp qi/qi1.in và qi/qi1.ans trong thư mục của thí sinh.

Ví dụ 2

Xem các tệp qi/qi2.in và qi/qi2.ans trong thư mục của thí sinh.

Ví dụ 3

Xem các tệp qi/qi3.in và qi/qi3.ans trong thư mục của thí sinh.

Giới hạn

Với mọi bộ kiểm thử: $1\le n\le4\times10^5$, $1\le m\le1.2\times10^5$, $0\le k\le15$. $a_1,a_2$ được sinh ngẫu nhiên đều trong $[0,2^{64}-1]$.