Taju Kage Bunshin No Jutsu

Naruto Uzumaki is one of the strongest ninja of RUET (Rasengan University of Ebisu and Tobi), possessing unnaturally huge amount of chakra (a kind of energy). Due to this, he can create a lot of shadow clones (duplicates of himself) with his Shadow Clone Jutsu. Right now, Naruto is bored so he’s just playing around with his shadow clones.

Naruto has already created $N$ shadow clones and lined them up in a row. The $i$-th clone has $C^i$ amount of chakra in it. Naruto can do the following operations in his whim.

1. Add $V$: Makes a new shadow clone with V amount of chakra and adds him to the end of the line.
2. Remove: Destroys the last shadow clone of the line.
3. Query $L$ $R$ $K$ – Finds the shadow clone with $K$-th largest chakra in $[L, R]$ range i.e. the $K$-th shadow clone if you sort the clones with position between L and R in the line according to their chakra in descending order.

Being a big fan of Naruto, you want to make a video game on Naruto following these 3 operations. In this problem, you have to do exactly that.

Input

The first line contains one integer $N$ ($1 \le N \le 10^5$), the number of shadow clones that has been already created. The next line contains $N$ space separated integers denoting an array $A$ ($1 ≤ A[i] ≤ 10^9$). Then there will be an integer $Q$ ($1 \le Q \le 10^5$) - the number of operation Naruto performs. Then next $Q$ lines contains one of the following types:

• $\texttt{1 V}$: Add a shadow clone with $V$ ($1 \le V \le 10^9$) amount chakra to the end of the line
• $\texttt{2}$: Destroys the last shadow clone of the line
• $\texttt{3 L R K}$: Finds the shadow clone with $K$-th ($1 \le K \le R-L+1$) largest chakra in $[L, R]$ ($1 \le L, R \le \texttt{Total Number of Current Shadow Clones}$) range i.e. the $K$-th shadow clone if you sort the clones with position between $L$ and $R$ in the line according to their chakra in descending order. It is guaranteed that shadow clones will always exist in $[L, R]$ range.

Output

For each 3rd type of operation you have to print a single integer that denotes the $K$-th largest chakra in $[L, R]$ range.

Sample

Input	Output
3 7 3 5 7 3 1 3 2 1 10 3 1 4 2 2 2 1 1 3 2 3 2	5 7 1