There are $n$ positions and $m$ operations. There are two types of operations:

• If an operation is in the form 1 a b c, it means adding the number $c$ to each position from $a$ to $b$.
• If an operation is in the form 2 a b c, it means querying the $c$-th largest number in the range from position $a$ to position $b$.

Input

The first line contains two integers $n$ and $m$, as described above. The next $m$ lines each contain an operation in the form 1 a b c or 2 a b c, as described above.

Output

For each query, output the $c$-th largest number.

Examples

Input 1

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

Output 1

1
2
1

Note

After the first operation, position 1 contains only 1, and position 2 contains only 1. After the second operation, position 1 contains 1 and 2, and position 2 contains 1 and 2. The third query asks for the 2nd largest number in the range [1, 1], which is 1. The fourth query asks for the 1st largest number in the range [1, 1], which is 2. The fifth query asks for the 3rd largest number in the range [1, 2], which is 1.

Constraints

• 30% of the data: $n=m=1000$
• 100% of the data: $n, m \le 50000$. For the last 7 test cases, the range of $n$ and $m$ increases approximately as an arithmetic progression from 32000 to 50000.
• $a \le b \le n$
• In operation 1, $|c| \le n$
• In operation 2, $|c| \le \text{maxlongint}$