Programming Competition Queries

You are given a programming competition where there are N participants. Each participant has solved a certain number of problems initially. There are two types of queries to process:

• Update Query: "1 X Y" – add Y to the number of problems solved by the participant at index X (indices are 1-indexed).
• Query for K-th Smallest: "2 K L R" – within the range of participants from L to R (inclusive), report the k-th smallest number of problems solved. Mathematically, if the subarray is denoted by \( A_{L:R} \), sort it and return the element at position \( K \) (i.e. the \( k\text{-th} \) smallest element).

The problem requires you to process all queries sequentially. Only queries of the second type produce an output.

inputFormat

The input is given from standard input (stdin) in the following format:

N
p1 p2 ... pN
Q
query1
query2
...
queryQ

Where:

• N (1 ≤ N ≤ 10⁵) is the number of participants.
• p1, p2, ..., pN are the initial numbers of problems solved by each participant.
• Q is the number of queries.
• Each query is in one of two forms:
  • 1 X Y: Update the problems solved of participant X by adding Y.
  • 2 K L R: Output the K-th smallest number among participants in the range [L, R].

outputFormat

For each query of type 2, output the result as a separate line to standard output (stdout).

## sample

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

3
4
3

</p>