K-th Largest XOR Query in Matrix

You are given two sequences: X of length \(n\) and Y of length \(m\). Let the matrix \(A\) be defined as:

\[ A_{i,j} = x_i \oplus y_j, \quad 1 \le i \le n, \quad 1 \le j \le m \]

You will be given \(q\) queries. Each query is specified by five integers \(u, d, l, r, k\) and represents a rectangular submatrix defined by the rows \(i \in [u, d]\) and columns \(j \in [l, r]\). Your task is to find the \(k\)-th largest element among all \(A_{i,j}\) in the specified rectangle.

Note: The operation \(\oplus\) denotes the bitwise XOR operation.

inputFormat

The first line of input contains three integers \(n\), \(m\), and \(q\) separated by spaces.

The second line contains \(n\) integers \(x_1, x_2, \ldots, x_n\) separated by spaces.

The third line contains \(m\) integers \(y_1, y_2, \ldots, y_m\) separated by spaces.

Each of the next \(q\) lines contains five integers \(u, d, l, r, k\), representing a query.

outputFormat

For each query, output a single line containing the \(k\)-th largest element in the corresponding submatrix.

sample

3 3 1
1 2 3
4 5 6
1 3 1 3 4

6