Islands Connectivity and Importance Query

There are n islands in Yongwu Township, numbered from \(1\) to \(n\). Each island has a unique importance value and the islands can be ranked according to their importance from \(1\) to \(n\) (a rank of \(1\) means the most important island). Some pairs of islands are connected by huge bridges. Two islands are considered connected if one can be reached from the other by traversing zero or more bridges.

You are to process two types of operations:

• B x y: Build a new bridge connecting island \(x\) and island \(y\).
• Q x k: Query the island which is the \(k\)th smallest by importance (i.e. \(k\)th in the ranking of importance) among all islands connected with island \(x\). Output the island's number.

The importance ranking of each island is given in the input. In each query, it is guaranteed that \(k\) does not exceed the size of the connected component of \(x\).

Note: All formulas must be written in \(\LaTeX\) format. For example, an island is labeled as \(x\) and its importance as \(w_x\); the ranking is determined in ascending order of \(w\).

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5)\), representing the number of islands and the number of operations, respectively.

The second line contains \(n\) distinct integers \(w_1, w_2, \dots, w_n\), which is a permutation of \(\{1, 2, \dots, n\}\). Here, \(w_i\) denotes the importance of the \(i\)th island. A smaller \(w_i\) implies a higher importance (i.e. rank 1 is the most important).

The following \(m\) lines each contain an operation in one of the following formats:

• B x y: Build a bridge between islands \(x\) and \(y\).
• Q x k: Query the \(k\)th important island in the connected component of island \(x\).

outputFormat

For each query operation, output a single line containing the island number that is the \(k\)th important (i.e. \(k\)th smallest by \(w\)) in the connected component of island \(x\).

sample

5 7
3 5 1 4 2
B 1 2
Q 1 2
B 2 3
Q 2 1
B 4 5
Q 5 2
Q 4 1

2
3
4
5