Description

You need to maintain $n$ multisets of integers, numbered from $1$ to $n$.
All sets are initially empty. There are $m$ operations:

• 1 l r c: Add $c$ to every set with index in $[l,r]$.
• 2 l r c: Query the $c$-th largest number in the union of all sets with indices in $[l,r]$.

Note that the union of multisets does not remove duplicates, e.g., $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$.

Input Format

The first line contains two positive integers $n, m$, the number of sets and the number of operations.
Each of the next $m$ lines contains four integers describing one operation.

Output Format

For each operation of type 2, output one line with a single integer, the answer.

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

1
2
1

Hint

[Sample Explanation]
The 1st operation adds one $1$ to sets $1$ and $2$.
The 2nd operation adds one $2$ to sets $1$ and $2$.
The 3rd operation queries the 2nd largest number in set $1$, which is $1$.
The 4th operation queries the 1st largest number in set $1$, which is $2$.
The 5th operation queries the 3rd largest number in the union $\{1,2,1,2\}$ of sets $1$ and $2$, which is $1$.

Constraints
$1 \le n,m \le 5\times 10^4$
$1 \le l,r \le n$
In operation 1, $|c| \le n$
In operation 2, $1 \le c < 2^{63}$, and the $c$-th largest number exists.

$\text{upd 2023.8.23}$：Added a new set of hack testdata.

Translated by ChatGPT 5