题目背景

请注意本题并不寻常的数据范围与时空限制。

题目描述

给定一个长度为 $n$ 的序列 $a_{1\sim n}$。$m$ 次查询，给定 $op,l,r,k$：

• 若 $op=0$，查询区间 $[l,r]$ 内有多少个数小于 $k$。
• 若 $op=1$，查询区间 $[l,r]$ 内第 $k$ 小的数。

强制在线。

输入格式

由于 IO 量过大，数据使用随机生成。你可以使用以下方式获取 $a_{1\sim n}$ 以及每次询问的 $op,l,r,k$：

typedef unsigned uint;
const int MAXN = 4e6 + 10;
const uint mask = 0x5f3759dfu;

uint seed, lst;

inline uint rnd() {
	seed ^= lst ^ mask;
	seed ^= seed << 13;
	seed ^= seed >> 7;
	seed ^= seed << 17;
	seed ^= lst ^ mask;
	return seed;
}

int n, m; uint a[MAXN];

int main() {
    scanf("%d%d%u", &n, &m, &seed);
    for (int i = 1; i <= n; i++) a[i] = rnd();
    for (int i = 1; i <= m; i++) {
    	uint op = rnd() & 1, l = rnd() % n + 1, r = rnd() % n + 1;
    	if (l > r) swap(l, r);
    	if (op) {
    		uint k = rnd() % (r - l + 1) + 1;
    		// do sth...
		} else {
			uint k = rnd();
			// do sth...
		}
	}
}

其中 $lst$ 表示上一次询问的答案，初始为 $0$。

输出格式

一行一个非负整数，表示所有查询的答案的异或和。

5 5 114514

1562674565

114 514 1919

903488587

5000 5000 998244353

1845377756

2000000 2000000 1004535809

1498751009

4000000 4000000 1000000007

981318194

提示

【样例 1 解释】

解密后的输入如下：

5 5
3453473247 1341133007 2686835293 4244725722 2878739094
0 3 5 4197138810
1 2 5 2
1 2 3 2
1 1 5 2
1 3 5 3

其中第一行为 $n,m$，第二行为 $a_{1\sim n}$，接下来 $m$ 行为询问。

【数据范围】

本题开启捆绑测试。

$\text{Subtask}$	$n,m\le$	分值
$1$	$500$	$10$
$2$	$5000$	$20$
$3$	$2\times 10^5$	$30$
$4$	$4\times 10^6$	$40$

对于 $100\%$ 的数据，$1\le n,m\le 4\times 10^6$，$0\le seed<2^{32}$。同一个 Subtask 内数据有梯度。

请注意常数因子对程序时空效率的影响。尤其注意 $\log$ 与 $\log$ 之间亦有分别。