题目描述
给定长度为 n 的数列 X=x1,x2,...,xn 和长度为 m 的数列 Y=y1,y2,...,ym,令矩阵 A 中第 i 行第 j 列的值 Ai,j=xi xor yj,每次询问给定矩形区域 i∈[u,d],j∈[l,r],找出第 k 大的 Ai,j。
输入格式
第一行包含两个正整数 n,m,分别表示两个数列的长度
第二行包含 n 个非负整数 xi。
第三行包含 m 个非负整数 yj。
第四行包含一个正整数 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≤Xi,Yj<231,
- 1≤u≤d≤n≤1000,
- 1≤l≤r≤m≤300000,
- 1≤k≤(d−u+1)×(r−l+1), 1≤p≤500。