#P18550. Fast Median Transform

Fast Median Transform

Fast Median Transform

长度为 kk 的数组的中位数是将元素按非降序排列后,位于第 ⌊(k+1)/2⌋\lfloor(k+1)/2\rfloor 个位置的元素(这里的排序位置从 1 开始)。例如,[5,1,2,3][5,1,2,3] 的中位数是 22,[2,1,1][2,1,1] 的中位数是 11。

Little Cyan Fish 给你长度为 nn 的数组 aa 和长度为 mm 的数组 bb。这两个数组的下标都从 0 开始。

对于整数 X0X_0,定义 (a,b,X0)(a,b,X_0) 的“快速中位数变换” FMT⁡(a,b,X0)\operatorname{FMT}(a,b,X_0) 如下:

  1. 令变量 XX 的初始值为 X0X_0。
  2. 按照 i=0,1,…,nm−1i=0,1,\ldots,nm-1 的顺序,依次执行:求 [ai mod n,bi mod m,X][a_{i\bmod n},b_{i\bmod m},X] 的中位数 YY,再令 X=YX=Y。
  3. 过程结束时的 XX 就是 FMT⁡(a,b,X0)\operatorname{FMT}(a,b,X_0)。

你需要处理 qq 次询问。每次询问给出三个整数 x,y′,X0′x,y',X'_0,按以下顺序执行:

  1. 将 axa_x 修改为 y′⊕lastansy'\oplus\mathrm{lastans}。其中 ⊕\oplus 表示按位异或,lastans\mathrm{lastans} 是上一次询问的答案,初始为 00。
  2. 计算并输出 FMT⁡(a,b,X0′⊕lastans)\operatorname{FMT}(a,b,X'_0\oplus\mathrm{lastans}),并把它作为下一次询问使用的 lastans\mathrm{lastans}。

询问相互依赖,必须依次处理,修改会保留。只有 y′y' 和 X0′X'_0 需要异或,xx 不需要。

输入格式

第一行包含三个整数 n,m,qn,m,q(1≤n,m,q≤3×1051\le n,m,q\le3\times10^5),分别表示 aa 的长度、bb 的长度和询问次数。

第二行包含 nn 个非负整数 a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1}(0≤ai<2290\le a_i<2^{29})。

第三行包含 mm 个非负整数 b0,b1,…,bm−1b_0,b_1,\ldots,b_{m-1}(0≤bi<2290\le b_i<2^{29})。

随后 qq 行,第 ii 行包含三个非负整数 x,y′,X0′x,y',X'_0(0≤x<n0\le x<n,0≤y′,X0′<2290\le y',X'_0<2^{29}),表示第 ii 次询问。

输出格式

输出 qq 行。第 ii 行包含一个整数,表示第 ii 次询问的 FMT⁡(a,b,X0′⊕lastans)\operatorname{FMT}(a,b,X'_0\oplus\mathrm{lastans})。

原样例

2 3 1
1 3
4 2 3
0 1 2
3