Roman Emperor's Murder Game

The Roman Emperor is bored and decides to play a twisted game with his soldiers. Initially, there are n soldiers, each in their own team, and each soldier has received a unique score from a geometric test. The Emperor, fond of plane geometry, despises the soldiers who scored poorly.

The Emperor issues two types of commands:

• M i j: Merge the teams containing soldier i and soldier j. This command is ignored if either soldier is dead.
• K i: In the team containing soldier i, kill the soldier who has the minimum score. If soldier i is already dead, this command is ignored.

For every K i command, the Emperor expects the general to report the score of the soldier that was just killed. If the command is ignored, output 0.

It is guaranteed that all soldier scores are distinct.

Note (in \(\LaTeX\)): When describing the problem mathematically, let the initial scores be \(a_1, a_2, \dots, a_n\) with \(a_i \neq a_j\) for \(i \neq j\).

inputFormat

The first line contains two integers n and q (the number of soldiers and the number of commands).

The second line contains n distinct integers \(a_1, a_2, \dots, a_n\) representing the scores of the soldiers.

Each of the following q lines contains a command in one of the following two formats:

• M i j
• K i

Soldiers are numbered from 1 to n.

outputFormat

For each K i command, output a line containing the score of the soldier that was killed. If the command is ignored, output 0.

sample

3 5
10 5 8
K 1
M 1 2
K 2
M 2 3
K 3

10
5
8