题面翻译

Cyberland 有 $n$ 座城市，编号从 $1$ 到 $n$，有 $m$ 条双向道路连接这些城市。第 $j$ 条路连接城市 $a_j$ 和 $b_j$。每天，都有成千上万的游客来到 Cyberland 游玩。

在每一个城市，都有纪念品售卖，第 $i$ 个城市售价为 $w_i$。这个售价有时会变动。

每一个游客的游览路径都有固定起始城市和终止城市，且不会经过重复的城市。

他们会在路径上的城市中，售价最低的那个城市购买纪念品。

你能求出每一个游客在所有合法的路径中能购买的最低售价是多少吗？

你要处理 $q$ 个操作：

C a w： 表示 $a$ 城市的纪念品售价变成 $w$。

A a b： 表示有一个游客要从 $a$ 城市到 $b$ 城市，你要回答在所有他的旅行路径中最低售价的最低可能值。

输入格式

第一行包含用一个空格隔开的三个数 $n, m, q$。

接下来 $n$ 行，每行包含一个数 $w_i$。

接下来 $m$ 行，每行包含用一个空格隔开的两个数 $a_j$,$b_j$。（$1 \le a _ j, b _ j \le n,a _ j \neq b _ j$）

数据保证没有两条道路连接同样一对城市，也没有一条道路两端是相同的城市。并且任意两个城市都可以相互到达。

接下来 $q$ 行，每行是 C a w 或 A a b ，描述了一个操作。

输出格式

对于每一个 A 类操作，输出一行表示对应的答案。

题目描述

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.

样例 #1

样例输入 #1

3 3 3
1
2
3
1 2
2 3
1 3
A 2 3
C 1 5
A 2 3

样例输出 #1

1
2

样例 #2

样例输入 #2

7 9 4
1
2
3
4
5
6
7
1 2
2 5
1 5
2 3
3 4
2 4
5 6
6 7
5 7
A 2 3
A 6 4
A 6 7
A 3 3

样例输出 #2

2
1
5
3

提示

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$ .