Problem Description

There are $N$ boys in CodeLand.
Boy $i$ has his coding skill $A_{i}$.
CRB wants to know who has the suitable coding skill.
So you should treat the following two types of queries.
Query 1: 1 $l\ v$
The coding skill of Boy $l$ has changed to $v$.
Query 2: 2 l $r$ $k$
This is a report query which asks the $k$-th smallest value of coding skill between Boy $l$ and Boy $r$(both inclusive).

Input

There are multiple test cases.
The first line contains a single integer $N$.
Next line contains $N$ space separated integers $A_{1}$, $A_{2}$, …, $A_{N}$, where $A_{i}$ denotes initial coding skill of Boy $i$.
Next line contains a single integer $Q$ representing the number of queries.
Next $Q$ lines contain queries which can be any of the two types.
1 ≤ $N$, $Q$ ≤ $10^{5}$
1 ≤ $A_{i}$, $v$ ≤ $10^{9}$
1 ≤ $l$ ≤ $r$ ≤ $N$
1 ≤ $k$ ≤ $r\ –\ l$ + 1

Output

For each query of type 2, output a single integer corresponding to the answer in a single line.

5
1 2 3 4 5
3
2 2 4 2
1 3 6
2 2 4 2

3
4

Author

KUT（DPRK）