CRB and Queries

Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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.

Sample Input

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

Sample Output

3 4

Hint

wange2014

Source

2015 Multi-University Training Contest 10

提交代码