P5494 [Template] Segment Tree Split

Given a multiset $a$ (ID $1$), it supports the following operations: `0 p x y`: Move all values in multiset $p$ that are greater than or equal to $x$ and less than or equal to $y$ into a new multiset (the new multiset ID starts from $2$ and is the previous newly created multiset ID plus $1$). `1 p t`: Put all numbers in multiset $t$ into multiset $p$, and clear multiset $t$ (the testdata guarantees that multiset $t$ will not appear in subsequent operations). `2 p x q`: Add $x$ copies of the number $q$ into multiset $p$. `3 p x y`: Query the number of values in multiset $p$ that are greater than or equal to $x$ and less than or equal to $y$. `4 p k`: Query the $k$-th smallest number in multiset $p$. If it does not exist, output `-1`.

The first line contains two integers $n, m$, meaning the numbers in the multiset are in the range $1 \sim n$, and there are $m$ operations. The next line contains $n$ integers, representing the number of occurrences of each number $1 \sim n$ in $a$ $(a_{i} \leq m)$. The next $m$ lines each contain several integers. The first integer is the operation ID $opt$ $(0 \leq opt \leq 4)$, as described in the **Description**.

Output the answer for each query operation in order.

For $30\%$ of the testdata, $1 \leq n \leq {10}^3$, $1 \le m \le {10}^3$. For $100\%$ of the testdata, $1 \le n \le 2 \times {10}^5$, $1 \le x, y, q \le m \le 2 \times {10}^5$. The testdata is guaranteed to be valid. If you do not use `long long`, you will regret it. --- Statement by @[Limit](https://www.luogu.com.cn/user/86625). std by @[Limit](https://www.luogu.com.cn/user/86625) (segment tree split). Tested by @[Froggy](https://www.luogu.com.cn/user/100285) (balanced tree, but the merge complexity was incorrectly assumed; the second-to-last test point is hack testdata). Testdata by @[Froggy](https://www.luogu.com.cn/user/100285). Translated by ChatGPT 5