题目描述

给定长度为 $n$ 的数列 $X=\{x_1,x_2,...,x_n\}$ 和长度为 $m$ 的数列 $Y=\{y_1,y_2,...,y_m\}$，令矩阵 $A$ 中第 $i$ 行第 $j$ 列的值 $A_{ij}=x_i \oplus y_j$，每次询问给定矩形区域 $i\in[u,d],j\in[l,r]$，找出第 $k$ 大的 $A_{ij}$。

输入格式

第一行包含两个正整数 $n,m$，分别表示两个数列的长度。

第二行包含 $n$ 个非负整数 $x_i$。

第三行包含 $m$ 个非负整数 $y_j$。

第四行包含一个正整数 $p$，表示询问次数。

随后 $p$ 行，每行均包含 $5$ 个正整数，用来描述一次询问，每行包含五个正整数 $u,d,l,r,k$，含义如题意所述。

输出格式

共 $p$ 行，每行包含一个非负整数，表示此次询问的答案。

输入样例

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

提示

对于 $100\%$ 的数据，$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$。