题目描述

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

输入

第一行包含两个正整数$n,m$，分别表示两个数列的长度； 第二行包含$n$个非负整数$x_i$； 第三行包含$m$个非负整数$y_i$； 第四行包含一个正整数$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≤X_i,Y_j<2^{31}，1≤u≤d≤n≤1000，1≤l≤r≤m≤300000； $1≤k≤(d-u+1)×(r-l+1)，1≤p≤500$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。