You have $$N$$ pieces of candies. Every day, a piece of candy is replaced with another one. The order of replacement is described by $$Q$$ queries containing the following:

• $$i$$: The index of a candy to be replaced 
• $$x$$: The sweetness of the replacement candy
• $$K$$: An integer

For each query find the \(K^{th}\) smallest value of sweetness of candy after replacement.

Input format

• The first line of input contains N, the number of candies.
• Next line contains N numbers (\(a_1, a_2....a_N\)), where \(a_i\) denotes the sweetness of \(i^{th}\) candy.
• The third line of input contains two integers $$Q$$ and $$R$$, the number of queries and \(R = 3\) for, number of integers in each query.
• Followed by $$Q$$ lines each containing three integers $$i$$, $$x$$ and $$K$$.

Output format

For each query output the K^th smallest value of sweetness among the candies.

Constraints

\(1 \le N, Q \le 100000\)
\(1 \le a_i \le 1000000\)
\(1 \le i \le N\)
\(1 \le x, K \le 1000000\).