Description

In YQH's dream, he saw his past memories constantly surfacing in his mind. These memories brought him overwhelming bitterness. He wants to forcibly forget some of them to reduce his bitterness.

YQH's brain can be divided into $n$ sections. Each section is like a multiset that stores memories, and it is initially empty. He will perform $m$ operations of the following three types:

Operation 1: In every section in the interval $l \sim r$, a memory with bitterness value $k$ appears.

Operation 2: YQH starts cleaning the memories in sections $l \sim r$. If a section $k \in [l,r]$ and the maximum bitterness value in section $k$ is equal to the maximum bitterness value among all sections $l \sim r$, then forget one such memory with the maximum bitterness value in that section. If there are multiple memories with the same maximum bitterness value in the same section, only one is forgotten. If a section has no memory, ignore it.

Operation 3: YQH wants to know the maximum bitterness value of memories among sections $l \sim r$. If it does not exist, output -1.

Input Format

The first line contains two numbers, $n, m$.

The next $m$ lines: the first number represents the operation type $op$. For operation 1, there are three numbers $l, r, k$. For operation 2 or 3, there are two numbers $l, r$.

Output Format

For each operation 3, output one line representing the answer.

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

3

6 6
1 1 6 2
1 3 3 2
1 3 4 3
2 3 4
3 3 3
3 4 4

2
2

Hint

Sample Explanation

Sample Explanation 1

Below is the state of YQH's brain after each operation: After the first operation: $\{2\},\{2\},\{2\},\varnothing,\varnothing$
After the second operation: $\{2\},\{2,3\},\{2,3\},\{3\},\varnothing$
After the third operation: $\{2\},\{2,3\},\{2\},\{3\},\varnothing$
The fourth operation queries the maximum value in interval $1 \sim 3$, so the answer is $3$.

Sample Explanation 2

Below is the state of YQH's brain after each operation: After the first operation: $\{2\},\{2\},\{2\},\{2\},\{2\},\{2\}$
After the second operation: $\{2\},\{2\},\{2,2\},\{2\},\{2\},\{2\}$
After the third operation: $\{2\},\{2\},\{2,2,3\},\{2,3\},\{2\},\{2\}$
After the fourth operation: $\{2\},\{2\},\{2,2\},\{2\},\{2\},\{2\}$
The fifth operation queries the maximum value of section $3$, so the answer is $2$.
The sixth operation queries the maximum value of section $4$, so the answer is $2$.

Constraints

For $100\%$ of the testdata, $n, m \le 2 \times 10^5$, $k \le 10^9$.

Translated by ChatGPT 5