Description

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.

Input Format

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 Format

Output the answer for each query operation in order.

5 12
0 0 0 0 0
2 1 1 1
2 1 1 2
2 1 1 3
3 1 1 3
4 1 2
2 1 1 4
2 1 1 5
0 1 2 4
2 2 1 4
3 2 2 4
1 1 2
4 1 3

3
2
4
3

Hint

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

std by

t tree split).

Tested by

tree, but the merge complexity was incorrectly assumed; the second-to-last test point is hack testdata).

Testdata by

Translated by ChatGPT 5