In Byteland, there are ~N~ cities numbered ~1~ to ~N~, initially all disconnected. However, every once in a while, the Bytelandian government may decide to add a road between two cities ~a_i~ and ~b_i~, allowing permanent travel between these two cities from then on.

Additionally, at different points in time, someone may decide to take a trip from their city! Each city is given a prosperity level ~p_i~, and someone leaving city ~c_i~ will want to travel to the city with a strictly higher prosperity level. However, they wouldn't want to feel too inferior, so instead they'll take a tour to the city with the next strictly higher prosperity level.

Your job is to figure out, of all the cities someone can reach, what the closest prosperity level is that's also higher than their current city's prosperity level.

Constraints

~1\le N\le 10^5~

~1\le Q\le 2\times 10^5~

~1\le a_i, b_i\le N~

~a_i\ne b_i~

~1\le c_i\le N~

~1\le p_i\le 10^9~

Input Specification

The first line contains two integers, ~N~ and ~Q~.

The second line contains ~N~ integers, the ~i~-th of which denoting ~p_i~.

The next ~Q~ lines are in one of the following formats:

Output Specification

For each query of type 2, output the closest higher prosperity level the person leaving city ~c~ can reach. If the current prosperity level is maximal, output -1

Sample Input

5 7
1 2 2 3 4
B 1 2
B 2 4
B 2 3
T 2
B 3 5
T 4
T 1

Sample Output

3
4
2

Sample Explanation

The first 3 queries build bridges. Here is a model of the graph (note that the node index is followed by the node's prosperity level):

For the fourth query, notice that the second city can reach the fourth city with a prosperity level of ~3~.

After building the bridge in the fifth query, the graph looks like such:

For the sixth query, the fourth city can reach the fifth city with prosperity level ~4~.

For the seventh query, the first city can reach a prosperity level of ~2~, which is the closest prosperity level that's higher than ~1~.