[THUSC2015] 异或运算

题目描述

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

输入输出格式

输入格式


第一行包含两个正整数 $n,m$,分别表示两个数列的长度。 第二行包含 $n$ 个非负整数 $x_i$。 第三行包含 $m$ 个非负整数 $y_j$。 第四行包含一个正整数 $p$,表示询问次数。 随后 $p$ 行,每行均包含 $5$ 个正整数,用来描述一次询问,每行包含五个正整数 $u,d,l,r,k$,含义如题意所述。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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$。