There are n cities in Cyberland, numbered from 1 to n, connected by m bidirectional roads. The j-th road connects city a_j and b_j.

For tourists, souvenirs are sold in every city of Cyberland. In particular, city i sell it at a price of w_i.

Now there are q queries for you to handle. There are two types of queries:

• "C a w": The price in city a is changed to w.
• "A a b": Now a tourist will travel from city a to b. He will choose a route, he also doesn't want to visit a city twice. He will buy souvenirs at the city where the souvenirs are the cheapest (possibly exactly at city a or b). You should output the minimum possible price that he can buy the souvenirs during his travel.

More formally, we can define routes as follow:

• A route is a sequence of cities [x₁, x₂, ..., x_k], where k is a certain positive integer.
• For any 1 ≤ i < j ≤ k, x_i ≠ x_j.
• For any 1 ≤ i < k, there is a road connecting x_i and x_i + 1.
• The minimum price of the route is min(w_x1, w_x2, ..., w_xk).
• The required answer is the minimum value of the minimum prices of all valid routes from a to b.

The first line of input contains three integers n, m, q (1 ≤ n, m, q ≤ 10⁵), separated by a single space.

Next n lines contain integers w_i (1 ≤ w_i ≤ 10⁹).

Next m lines contain pairs of space-separated integers a_j and b_j (1 ≤ a_j, b_j ≤ n, a_j ≠ b_j).

It is guaranteed that there is at most one road connecting the same pair of cities. There is always at least one valid route between any two cities.

Next q lines each describe a query. The format is "C a w" or "A a b" (1 ≤ a, b ≤ n, 1 ≤ w ≤ 10⁹).

For each query of type "A", output the corresponding answer.