In Bruce's class, there are ~N~ students, numbered from ~1~ to ~N~. Bruce ranks his students in increasing order according to the number of questions they have solved on DMOJ. The student who solves the least number of questions is ranked 1st. Conveniently, no two students have solved the same number of questions, i.e. each student has a unique rank.
Bruce finds that some students are friends. Note that friendship is a bidirectional relationship. For example, if Alex is Tim's friend, then conversely, Tim is also Alex's friend. Students are grouped together through friendship. Now, Bruce wants to motivate his students to solve more questions on DMOJ. He will perform a sequence of operations, each of which is one of the following:
~B\ x\ y~, build a friendship between student ~x~ and student ~y~;
~Q\ x\ k~, query the student number who has the ~k~-th lowest rank in the group that contains student ~x~ (note that the group of student ~x~ includes student ~x~ himself).
The first line of input will consist of two integers ~N~ and ~M~ (~1 \leq N \leq 100\,000~, ~0 \leq M \leq N~). ~N~ is the number of students and ~M~ is the number of initial friendships.
The second line of input is a permutation of ~1~ to ~N~, representing the rankings of all ~N~ students.
The next ~M~ lines of input will contain the initial friendships. It is guaranteed that the numbers of the students that are friends will be valid.
The next line of input is a single integer ~q~ (~1 \leq q \leq 300\,000~), which is the total number of operations. Each of the next ~q~ lines will contain an operation, starting with ~Q~ or ~B~ as described above.
For each query operation, i.e. ~Q\ x\ k~, output an integer on a single line. The integer is the number of the student who ranks the ~k~-th lowest in the group of student ~x~. If there is no such student, output
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
-1 2 5 1 2