Neverland contains $n$ islands, numbered from $1$ to $n$. Each island has a unique importance value, and based on these importance values, the $n$ islands can be ranked, with ranks represented by integers from $1$ to $n$. Some islands are connected by massive bridges, allowing travel from one island to another. If one can travel from island $a$ to island $b$ by crossing zero or more bridges, we say that island $a$ and island $b$ are connected. There are two types of operations: B x y represents building a new bridge between island $x$ and island $y$. Q x k represents a query asking for the island with the $k$-th smallest importance rank among all islands currently connected to island $x$. Please output the number of that island.

Input

The first line contains two space-separated positive integers $n$ and $m$, representing the number of islands and the number of initially existing bridges, respectively. The next line contains $n$ space-separated integers, describing the importance rank of islands $1$ through $n$ in order. The following $m$ lines each contain two space-separated positive integers $a_i$ and $b_i$, representing an initially existing bridge between island $a_i$ and island $b_i$. The remaining part describes the operations: the first line of this part is a positive integer $q$, representing the total number of operations. The next $q$ lines describe each operation in the format mentioned above, starting with an uppercase letter Q or B, followed by two positive integers not exceeding $n$. The letter and the numbers, as well as the two numbers, are separated by spaces.

For $20\%$ of the data: $n \le 1000, q \le 1000$. For $100\%$ of the data: $n \le 100000, m \le n, q \le 300000$.

Output

For each Q x k operation, output one line containing a single integer representing the number of the queried island. If such an island does not exist, output -1.

Examples

Input 1

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

Output 1

-1
2
5
1
2