A9742 | Tourists

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_{1},x_{2},...,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 \leq n, m, q \leq 10^5)$, separated by a single space.

Next n lines contain integers $w_i (1 \leq w_i \leq 10^9)$.

Next m lines contain pairs of space-separated integers $a_j$ and $b_j$ $(1 \leq a_j, b_j \leq n, aj \neq 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 \leq a, b \leq n, 1 \leq w \leq 10^9)$.

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