Array Query Processor

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

• update x y: Update the element at the 1-based index x to the new value y.
• kth_one l r k: Find the $k$-th smallest element in the subarray from index l to r inclusive. (Note that the index is 1-based.)

For each kth_one query, output the answer on a new line.

More formally, let \(A\) be the given array. For a query \(kth\_one\ l\ r\ k\), let \(S = [A_l, A_{l+1}, \dots, A_r]\). When \(S\) is sorted in non-decreasing order, output the element at the \(k\)-th position (with 1-based indexing).

inputFormat

The input is given from stdin and has the following format:

 n
 a1 a2 ... an
 q
 query1
 query2
 ...
 queryq

Here, n is the number of elements in the array, followed by n integers. Then, q is the number of queries, followed by q lines each describing a query. Each query is either in the format update x y or kth_one l r k.

outputFormat

For each kth_one query, print the result on a new line to stdout.

## sample

6
1 5 2 6 3 4
3
update 3 7
kth_one 2 5 3
kth_one 1 6 4

6
5

</p>