Yuno is not very good at playing poker.

Therefore, she created a data structure problem.

You are given a sequence $a$ of length $n$. You need to support $m$ operations of two types:

1. Query the $k$-th smallest value in the range $[l, r]$.
2. Add $k$ to all elements in the range $[l, r]$.

Input

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers, where the $i$-th integer represents $a_i$.

The next $m$ lines each contain four integers $opt, l, r, k$, where $opt$ represents the type of operation.

Output

For each query, output a single number representing the answer. If there is no solution, output $-1$.

Examples

Input 1

1 1
1
1 1 1 1

Output 1

1

Subtasks

Idea: nzhtl1477,

Solution: nzhtl1477 ($O( m\sqrt{n}( \Delta + \log n ) )$) solution, ccz181078 ($O( m\sqrt{n \log n} )$) solution

Code: nzhtl1477 ($O( m\sqrt{n}( \Delta + \log n ) )$) code, ccz181078 ($O( m\sqrt{n \log n} )$) code

Data: nzhtl1477

$1\leq n, m\leq 10^5$, $-2\times 10^4\leq$ each added value and the values in the original sequence $\leq 2\times 10^4$.