Process Queries on an Array

You are given an array of n integers and q queries. There are two types of queries:

• 1 x y: Add y to the element at index x.
• 2 l r k: Find the kth smallest element in the subarray from index l to r (inclusive). This can be represented mathematically as finding the element at position \(k\) in the sorted subarray \(A[l \ldots r]\).

It is guaranteed that the queries are valid. If there is no query of type 2, nothing is printed. Use 0-indexing for the array.

inputFormat

The input is given in the following format from stdin:

1. The first line contains two integers n and q: the size of the array and the number of queries, respectively.
2. The second line contains n space-separated integers, representing the initial array.
3. The following q lines each contain a query in one of the two formats:
• 1 x y: Add y to the element at index x.
• 2 l r k: Output the kth smallest element in the subarray from index l to index r (inclusive).

Note that indices are 0-indexed.

outputFormat

For each query of type 2, print the result (the kth smallest number) on a new line to stdout. If there are no type 2 queries, output nothing.

## sample

6 5
3 2 5 1 6 4
2 0 5 3
1 3 3
2 1 4 2
1 5 -1
2 0 5 4

3
4
4

</p>