E. Touriststime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere are n cities in Cyberland, numbered from 1 to n, connected by m bidirectional roads. The j-th road connects city aj and bj.For tourists, souvenirs are sold in every city of Cyberland. In particular, city i sell it at a price of wi.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 [x1, x2, ..., xk], where k is a certain positive integer. For any 1 ≤ i < j ≤ k, xi ≠ xj. For any 1 ≤ i < k, there is a road connecting xi and xi + 1. The minimum price of the route is min(wx1, wx2, ..., wxk). The required answer is the minimum value of the minimum prices of all valid routes from a to b.InputThe first line of input contains three integers n, m, q (1 ≤ n, m, q ≤ 105), separated by a single space.Next n lines contain integers wi (1 ≤ wi ≤ 109).Next m lines contain pairs of space-separated integers aj and bj (1 ≤ aj, bj ≤ n, aj ≠ bj).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 ≤ 109).OutputFor each query of type "A", output the corresponding answer.ExamplesInput3 3 31231 22 31 3A 2 3C 1 5A 2 3Output12Input7 9 412345671 22 51 52 33 42 45 66 75 7A 2 3A 6 4A 6 7A 3 3Output2153NoteFor the second sample, an optimal routes are:From 2 to 3 it is [2, 3].From 6 to 4 it is [6, 5, 1, 2, 4].From 6 to 7 it is [6, 5, 7].From 3 to 3 it is [3].  
Input3 3 31231 22 31 3A 2 3C 1 5A 2 3
Output12
['data structures', 'dfs and similar', 'graphs', 'trees', '*3200']