Description

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.

Input Format

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 Format

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

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

6
5
1

Hint

For $100\%$ of the data:

• $0\leq X_i,Y_j<2^{31}$.
• $1\leq u\leq d\leq n\leq 1000$.
• $1\leq l\leq r\leq m\leq 300000$.
• $1\leq k\leq (d-u+1)\times (r-l+1)$, $1\leq p\leq 500$.

Translated by ChatGPT 5