Just a random problem.

Cho ma trận \(A \in \mathbb{Z}_q^{N \times n}\), dãy \(N\) số \(b\) và \(K\) bản ghi. Mỗi bản ghi là một cặp \((u, v)\) với \(u\) là dãy \(n\) số, \(v\) là một số thuộc \(\mathbb{Z}_q\), được sinh như sau: tồn tại dãy ẩn \(r\) gồm \(N\) số (mỗi số chỉ là \(0\) hoặc \(1\)) và số nguyên ẩn \(m \in \{0, \ldots, 255\}\) sao cho:

Trong đó \(m \in \{0 \ldots 255\}\), \(\delta = \lfloor q/256 \rfloor\), và \(e\) thỏa \(|e| < \delta/4\).

Với:

• \(\sum_{i=0}^{N-1} r_i \cdot x_i\) là ký hiệu tổng cộng dồn, tức \(r_0 \cdot x_0 + r_1 \cdot x_1 + \ldots + r_{N-1} \cdot x_{N-1}\).
• \(\delta = \lfloor q/256 \rfloor\) là phần nguyên của \(q\) khi chia cho \(256\), là dạng encode trước khi mã hóa \(m\).
• \(\mathbb{Z}_q = \{0, 1, \ldots, q-1\}\) là tập số nguyên modulo \(q\) (mọi phép tính thực hiện theo modulo \(q\)); \(\mathbb{Z}_q^{N \times n}\) là tập ma trận \(N\) hàng \(n\) cột có phần tử thuộc \(\mathbb{Z}_q\); \(\lfloor x \rfloor\) là phần nguyên của \(x\); và \(a \equiv b \pmod{q}\) nghĩa là \(q \mid (a - b)\).
• modulo là phép chia lấy dư thay vì thương

Yêu cầu: Từ \((q, N, n, K, A, b)\) và danh sách \(K\) cặp \((u, v)\), khôi phục \(m\) của từng bản ghi theo thứ tự và in ra dưới dạng chuỗi ASCII.

Input

• Dòng \(1\): \(N\ n\ q\ K\)
• \(N\) dòng tiếp theo: mỗi dòng gồm \(n\) số nguyên — hàng thứ \(i\) của \(A\)
• \(1\) dòng: \(N\) số nguyên — dãy \(b\)
• \(K\) nhóm, mỗi nhóm gồm \(2\) dòng:
  • Dòng \(1\): \(n\) số nguyên \(u_0 \ldots u_{n-1}\)
  • Dòng \(2\): số nguyên \(v\)

Output

• Một dòng duy nhất: chuỗi ký tự ASCII thu được từ \(K\) bản ghi theo thứ tự.

Constraints

• \(1 \le n \le 16\)
• \(1 \le N \le 80\)
• \(q \le 2^{56}\)
• \(1 \le K \le 16\)

Example

22 7 39746316 4
18040172 33498820 27772788 33380458 5216341 32497015 13346694
32032596 19590394 1627521 33606008 641382 18251414 9912985
20847335 32913919 35640446 9733113 27894205 14407077 9627064
19947885 1593416 8485318 15434800 33762463 17770595 9247798
7197072 27151376 35218403 34298980 12164566 23818804 28746023
14994771 414952 5307397 35992109 565112 29816037 25748198
31662847 17449825 28426422 32131856 18820323 20132776 18662049
19180979 24326842 21766161 7200701 37655835 33932824 6566653
15200228 25219849 35609215 34211923 26067045 28301377 2519329
34159662 1810181 34736609 7774034 13283257 19008841 7371864
37224948 19764269 35555464 37023988 36605380 30596196 29302121
16898327 13565858 21529731 21915052 24991401 13865630 25126663
21035099 3574149 4812419 28464611 22948135 1316114 8894211
6562624 1373904 25530110 22422881 14435903 33686394 39160433
38428928 32024429 19310408 25594736 1358457 21693179 15713982
22450945 25798198 14984990 2484702 26682191 11229956 36317912
6209977 7499472 21315616 22659307 20703697 16741126 21257273
5841282 17647146 25860158 11408903 10182335 30375972 95473
38507328 1372167 33918580 36097323 6004641 1103712 6152704
10764137 1134198 36817212 39477737 24418314 6709934 21598735
34042014 35013323 14727544 21042494 38611638 29926343 35121274
29190418 12987964 6447272 30074950 28673411 22661715 9865967
1250507 25129034 11119635 2947574 3244801 34095179 16715830 18323623 25150261 29958423 8048766 492191 24962809 3298573 34440104 20648188 39493313 31852580 22045398 7283880 10389536 30570084
31427510 36112360 10231521 38479412 39476606 36233820 10140581
24875592
33129766 19148375 388549 22313940 2774479 23022060 29270554
39402793
28382109 3028492 27512446 1344747 34825377 33552842 22542085
14844257
36175167 12485927 22853940 19702289 7425708 25703038 16869050
36825522

Rk>.

Scoring

• Subtask 1 (\(20\%\) điểm): \(N \le 24,\ n \le 8,\ K \le 4\)
• Subtask 2 (\(30\%\) điểm): \(N \le 48,\ n \le 12,\ K \le 8\)
• Subtask 3 (\(50\%\) điểm): Không có ràng buộc bổ sung