Given an array $A$ of $n$ integers, there are $q$ queries, each falling into one of two types:
- `1 l r k`: Find the $k$-th smallest number in the subarray $A_{l...r}$.
- `2 l r x`: For every $l \le i \le r$, increment $A_i$ by $x$.
Find the answers for each query of type `1`.
### Input
- The first line contains two integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines each contain a query in the specified format.
### Output
- Print an integer as the answer for each query of type `1`.
### Constraints
- $1 \le n, q \le 10^5$.
- $0 \le |A_i|, |x| \le 2 \times 10^4$.
- $1 \le k \le r - l + 1$.
### Example
Input:
```
1 1
1
1 1 1 1
```
Output:
```
1
```
