#P4103. [thoi2015]异或运算

    ID: 3310 传统题 2000ms 512MiB 尝试: 843 已通过: 316 难度: 7 上传者: 标签>CF2200提高+/省选-可持久化 Trie路径复制前缀版本作差Trie 上第 k 小鸣谢佚名上传

[thoi2015]异或运算

题目描述

给定长度为 nn 的数列 X={x1,x2,...,xn}X=\{x_1,x_2,...,x_n\} 和长度为 mm 的数列 Y={y1,y2,...,ym}Y=\{y_1,y_2,...,y_m\},令矩阵 AA 中第 ii 行第 jj 列的值 Aij=xi⊕yjA_{ij}=x_i \oplus y_j,每次询问给定矩形区域 i∈[u,d],j∈[l,r]i\in[u,d],j\in[l,r],找出第 kk 大的 AijA_{ij}。

输入格式

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

第二行包含 nn 个非负整数 xix_i。

第三行包含 mm 个非负整数 yjy_j。

第四行包含一个正整数 pp,表示询问次数。

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

输出格式

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

输入样例

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%100\% 的数据,0≤Xi,Yj<2310 \leq X_i,Y_j < 2^{31}, 1≤u≤d≤n≤10001 \leq u \leq d \leq n \leq 1000, 1≤l≤r≤m≤3000001 \leq l \leq r \leq m \leq 300000, 1≤k≤(d−u+1)×(r−l+1)1 \leq k \leq (d-u+1)\times(r-l+1), 1≤p≤5001 \leq p \leq 500。