长度为 k 的数组的中位数是将元素按非降序排列后,位于第 ⌊(k+1)/2⌋ 个位置的元素(这里的排序位置从 1 开始)。例如,[5,1,2,3] 的中位数是 2,[2,1,1] 的中位数是 1。
Little Cyan Fish 给你长度为 n 的数组 a 和长度为 m 的数组 b。这两个数组的下标都从 0 开始。
对于整数 X0,定义 (a,b,X0) 的“快速中位数变换” FMT(a,b,X0) 如下:
- 令变量 X 的初始值为 X0。
- 按照 i=0,1,…,nm−1 的顺序,依次执行:求 [aimodn,bimodm,X] 的中位数 Y,再令 X=Y。
- 过程结束时的 X 就是 FMT(a,b,X0)。
你需要处理 q 次询问。每次询问给出三个整数 x,y′,X0′,按以下顺序执行:
- 将 ax 修改为 y′⊕lastans。其中 ⊕ 表示按位异或,lastans 是上一次询问的答案,初始为 0。
- 计算并输出 FMT(a,b,X0′⊕lastans),并把它作为下一次询问使用的 lastans。
询问相互依赖,必须依次处理,修改会保留。只有 y′ 和 X0′ 需要异或,x 不需要。
输入格式
第一行包含三个整数 n,m,q(1≤n,m,q≤3×105),分别表示 a 的长度、b 的长度和询问次数。
第二行包含 n 个非负整数 a0,a1,…,an−1(0≤ai<229)。
第三行包含 m 个非负整数 b0,b1,…,bm−1(0≤bi<229)。
随后 q 行,第 i 行包含三个非负整数 x,y′,X0′(0≤x<n,0≤y′,X0′<229),表示第 i 次询问。
输出格式
输出 q 行。第 i 行包含一个整数,表示第 i 次询问的 FMT(a,b,X0′⊕lastans)。
原样例
2 3 1
1 3
4 2 3
0 1 2
3