#751. [Thu Summer Camp 2015]异或运算

[Thu Summer Camp 2015]异或运算

题目描述

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

输入格式

第一行包含两个正整数 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\% 的数据

  • 0Xi,Yj<2310\leq X_i,Y_j<2^{31},
  • 1udn10001\leq u\leq d\leq n\leq 1000,
  • 1lrm3000001\leq l\leq r\leq m\leq 300000,
  • 1k(du+1)×(rl+1)1\leq k\leq (d-u+1)\times (r-l+1), 1p5001\leq p\leq 500