markdown

E. 游客

时间限制：每个测试点 $2$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

---

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$。他会选择一条路线，并且不希望重复访问同一座城市。他会在沿途纪念品最便宜的城市（可能是城市 $a$ 或 $b$）购买纪念品。你需要输出他在这次旅行中可能买到纪念品的最小价格。

更正式地，我们可以如下定义路线：

• 一条路线是一个城市序列 $[x_1, x_2, \dots, x_k]$，其中 $k$ 是某个正整数。
• 对于任意 $1 \le i < j \le k$，有 $x_i \neq x_j$。
• 对于任意 $1 \le i < k$，存在一条连接 $x_i$ 和 $x_{i+1}$ 的道路。
• 路线的最小价格为 $\min(w_{x_1}, w_{x_2}, \dots, w_{x_k})$。
• 所需答案是所有从 $a$ 到 $b$ 的合法路线中，最小价格的最小可能值。

---

输入

第一行包含三个整数 $n, m, q$（$1 \le n, m, q \le 10^5$），用单个空格分隔。

接下来 $n$ 行，每行包含一个整数 $w_i$（$1 \le w_i \le 10^9$）。

接下来 $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（$1 \le a, b \le n$，$1 \le w \le 10^9$）。

---

输出

对于每个类型为 A 的查询，输出对应的答案。

---

样例

样例 1

输入

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

输出

1
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
1
5
3

---

注释

对于第二个样例，最优路线如下：

• 从 $2$ 到 $3$：路线为 $[2, 3]$。
• 从 $6$ 到 $4$：路线为 $[6, 5, 1, 2, 4]$。
• 从 $6$ 到 $7$：路线为 $[6, 5, 7]$。
• 从 $3$ 到 $3$：路线为 $[3]$。