Background

Please note that this problem has unusual Constraints and time/memory limits.

Problem Description

Given a sequence $a_{1\sim n}$ of length $n$. There are $m$ queries, each given $op, l, r, k$:

• If $op = 0$, query how many numbers in the range $[l, r]$ are less than $k$.
• If $op = 1$, query the $k$-th smallest number in the range $[l, r]$.

Forced online.

Input Format

Because the IO volume is too large, the testdata is generated randomly. You can use the following method to obtain $a_{1\sim n}$ and each query’s $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...
		}
	}
}

Here, $lst$ denotes the answer of the previous query, and its initial value is $0$.

Output Format

Output one non-negative integer per line, which is the XOR sum of the answers to all queries.

5 5 114514

1562674565

114 514 1919

903488587

5000 5000 998244353

1845377756

2000000 2000000 1004535809

1498751009

4000000 4000000 1000000007

981318194

Hint

Sample 1 Explanation

The decrypted input is as follows:

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

The first line is $n, m$, the second line is $a_{1\sim n}$, and the next $m$ lines are the queries.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n, m \le 4\times 10^6$, $0 \le seed < 2^{32}$. Within the same Subtask, the testdata has multiple levels.

Please pay attention to the effect of constant factors on time and memory efficiency. In particular, note that there are also differences between $\log$ and $\log$.

Translated by ChatGPT 5