Description

You are given $k$ sorted arrays, each of length $n$.

Now there are $q$ queries: given a number $x$, for each array, find the smallest number in that array that is greater than or equal to $x$ (the non-strict successor).

If the successor does not exist, define it as $0$.

The answer to each query is defined as the bitwise XOR sum of the $k$ successors.

You need to answer these queries online.

Since there would be too much output, a parameter $d$ is given. You only need to output the answers for queries whose indices are multiples of $d$. Query indices start from $1$.

Input Format

The first line contains four integers $n,k,q,d$, with meanings as described above.

The next $k$ lines each contain $n$ integers describing an array. All numbers that appear across all arrays are distinct, and each array is guaranteed to be strictly increasing.

The next $q$ lines each contain one integer $x$, describing a query.

Each input $x$ needs to be XOR-decrypted with the answer of the previous query (whether it was output or not). If this is the first query, no operation is needed.

Output Format

For each query whose index is a multiple of $d$, output one line containing one integer, which is the XOR sum of the $k$ successors.

6 3 8 1
1 4 6 7 10 20 
2 3 8 11 14 18 
5 9 12 13 15 17 
20
6
9
4
29
5
14
9

20
6
9
23
13
11
11
3

2 4 1 1
64 65
25 26
44 62
35 81
81

81

20 4 10 1
553 897 1333 1949 2261 2541 2901 3133 3209 3713 4373 4749 5761 7405 8733 10417 13013 15185 16825 16981 
246 750 806 1534 2274 2470 2486 3278 3954 4618 5306 5638 6114 6310 7106 7522 7734 8170 8702 8974 
1047 1275 2347 2711 3607 4719 5911 6051 7099 7519 8087 8435 8499 8687 8835 10151 10491 11159 11915 12483 
548 1392 2188 3260 3404 3768 5076 5668 5732 6612 7284 7492 8900 9008 9536 9768 11160 12096 12300 13100 
3133
3331
4139
2685
2229
1163
3228
2694
3913
7058

600
8156
676
1176
600
3800
8
432
8156
320

Hint

Sample Explanation

For Sample 1, the decrypted data is:

6 3 8 1
1 4 6 7 10 20
2 3 8 11 14 18
5 9 12 13 15 17
20
18
15
13
10
8
5
2

Constraints and Conventions

• For $20\%$ of the testdata: $k\leq 10$, $n\leq 1000$, $q\leq 1000$.
• For $50\%$ of the testdata: $k\leq 10$, $q\leq 2\times 10^5$.
• For $100\%$ of the testdata: $1 \leq k\leq 100$, $2\leq n\leq 10^4$, $q\leq 5\times 10^5$, $1\leq d\leq 10$, and after decryption all numbers in the input are in the range $[1,5\times 10^8)$.

Translated by ChatGPT 5