Description

The Roman emperor enjoys a killing game. His army has $n$ soldiers, and each soldier initially forms an independent group. A recent plane geometry test was held, and each soldier received a score. The emperor loves plane geometry and despises soldiers with low scores.

He decides to play the following game. He can issue two types of commands:

• M i j Merge the groups containing $i$ and $j$ into one group. If either $i$ or $j$ is already dead, ignore this command.
• K i Kill the lowest-scoring soldier in the group containing $i$. If soldier $i$ is already dead, ignore this command.

After each K i command, the general should report the score of the soldier who was killed (if the command is ignored, report $0$).

It is guaranteed that all soldiers’ scores are pairwise distinct.

Input Format

The first line contains an integer $n$, the number of soldiers.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the score of the soldier with index $i$.

The third line contains an integer $m$.

The $(3 + i)$-th line describes the $i$-th command, which is either M i j or K i.

Output Format

For each K i command, output the score of the killed soldier (if such a person does not exist, output $0$).

5
100 90 66 99 10
7
M 1 5
K 1
K 1
M 2 3
M 3 4
K 5
K 4

10
100
0
66

Hint

Constraints:

• For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le m \le 10^5$, $0 \le a_i \le 10^7$. Note: In the testdata, in the command M i j, $i$ and $j$ may already be in the same group.

Translated by ChatGPT 5