Background

The Fractional Cascading algorithm is commonly translated as "分散层叠" in Chinese.

This problem provides a simple and classic method to verify the correctness of the algorithm. It is designed to challenge brute-force approaches, though it does not guarantee that no workaround can pass.

Problem Description

Given \( k \) sorted arrays, each of length \( n \).

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

If such a successor does not exist, it is defined as \( 0 \).

The answer to each query is defined as the XOR sum of these \( k \) successors.

You need to answer these queries online.

Due to the large number of outputs, a parameter \( d \) is provided. You only need to output the answers for queries whose indices are multiples of \( d \). The queries are numbered starting from \( 1 \).

Input Format

The first line contains four integers \( n, k, q, d \), as described in the problem statement.

The next \( k \) lines, each containing \( n \) integers, describe the arrays. All numbers in the arrays are unique and each array is strictly increasing.

The next \( q \) lines, each containing an integer \( x \), describe the queries.

The \( x \) values in the input need to be decrypted by XORing with the answer of the previous query (regardless of whether it was output). If this is the first query, no decryption is needed.

Output Format

For each query whose index is a multiple of \( d \), output a single line containing an integer, which is the XOR sum of the \( k \) successors.

Sample Input and Output

Input Sample #1

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

Output Sample #1

20
6
9
23
13
11
11
3

Input Sample #2

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

Output Sample #2

81

Input Sample #3

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

Output Sample #3

600
8156
676
1176
600
3800
8
432
8156
320

Notes

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

Data Size and Constraints

• For \( 20\% \) of the data, \( k \leq 10 \), \( n \leq 1000 \), \( q \leq 1000 \).
• For \( 50\% \) of the data, \( k \leq 10 \), \( q \leq 2 \times 10^5 \).
• For \( 100\% \) of the data, \( 1 \leq k \leq 100 \), \( 2 \leq n \leq 10^4 \), \( q \leq 5 \times 10^5 \), \( 1 \leq d \leq 10 \). The numbers in the input after decryption are within the range \([1, 5 \times 10^8)\).

见题面 Input 部分

见题面 Output 部分