XorTransform

A matrix consisting of natural numbers with $N$ rows and $M$ columns is given. Through a transformation, we can obtain another matrix of $N$ rows and $M$ columns as follows: each element at coordinates $(i, j)$ with $0 ≤ i < N$, $0 ≤ j < M$, in the newly obtained matrix will be equal to the xor sum of the values from the following four positions $(i, j)$, $(i+1, j)$, $(i, j+1)$, $(i+1, j+1)$ in the initial matrix (if any of these positions are outside the matrix, the value at that position will be considered $0$).

Task

Given a matrix with $N$ rows and $M$ columns, answer queries of the form: what is the value at the first row and first column if we apply $K$ transformations to the initial matrix.

Interaction

You need to implement the following functions:

void initialize(int N, int M, int **matrix);

The function receives as parameters the dimensions of the matrix and the matrix itself. It does not need to return anything.

int query(int K);

The function receives as a parameter the value $K$ for a query, and it needs to return the answer to the query, as described in the statement.
The Interactor will read the data from the input file xortransform.in and will display the answers to the query function in the output file xortransform.out in the format described below.

Constraints and Restrictions

• $1 ≤ N \times M ≤ 2\ 500\ 000$
• $1 ≤ matrix[x][y] ≤ 2^{30}$, for any $0 ≤ x < N$ and $0 ≤ y < M$.
• $1 ≤ K ≤ 1\ 000\ 000\ 000$
• The query function will be called at most $1\ 000\ 000$ times during a test.

Example

xortransform.in

4 5 3
9 8 1 3 6
1 2 5 2 5
3 4 3 7 7
7 8 3 5 1
3
18
100

xortransform.out

13
8
15

Explanations

Input data format

N M Q
A0,0 A0,1 ... A0,M-1
A1,0 A1,1 ... A1,M-1
...
AN-1,0 AN-1,M-1
K1
K2
...
KQ