P5795 [THUSC 2015] XOR Operation

Given a sequence $X=\{x_1,x_2,\ldots,x_n\}$ of length $n$ and a sequence $Y=\{y_1,y_2,\ldots,y_m\}$ of length $m$, define a matrix $A$ where the value in row $i$ and column $j$ is $A_{i,j}=x_i\ \operatorname{xor}\ y_j$. For each query, you are given a rectangular region $i\in[u,d],\, j\in[l,r]$. Find the $k$-th largest value among all $A_{i,j}$ in this region.

The first line contains two positive integers $n,m$, representing the lengths of the two sequences. The second line contains $n$ non-negative integers $x_i$. The third line contains $m$ non-negative integers $y_j$. The fourth line contains a positive integer $p$, representing the number of queries. The next $p$ lines each contain five positive integers $u,d,l,r,k$, describing one query. The meanings are as stated above.

Output $p$ lines. Each line contains one non-negative integer, the answer to the corresponding query.

For $100\%$ of the data: - $0\leq X_i,Y_j