P6466 Fractional Cascading

The `Fractional Cascading` algorithm is often translated in Chinese as “分散层叠”. This problem only provides a simple and classic way to verify the correctness of the algorithm. In principle, it will try to rule out relatively brute-force solutions, but it does not guarantee that random hacks cannot pass.

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$.

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.

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.

#### Sample Explanation For Sample 1, the decrypted data is: ```cpp 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