P15107 [Template] Wavelet Matrix / Wavelet Matrix.

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

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.

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$: ```cpp typedef unsigned uint; const int MAXN = 4e6 + 10; const uint mask = 0x5f3759dfu; uint seed, lst; inline uint rnd() { seed ^= lst ^ mask; seed ^= seed > 7; seed ^= seed

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

#### Sample 1 Explanation The decrypted input is as follows: ```cpp 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.** |$\text{Subtask}$|$n, m \le$|Score| |:-:|:-:|:-:| |$1$|$500$|$10$| |$2$|$5000$|$20$| |$3$|$2\times 10^5$|$30$| |$4$|$4\times 10^6$|$40$| 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