题面描述

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

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

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

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

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

你要处理 $q$ 个操作：

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

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

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

• 一条路线是城市的序列 $[x_1,x_2,...,x_k]$，其中 $k$ 是一个正整数。
• 对于任何 $1 \le i\lt j \le k$， $x_i \ne x_j$。
• 对于任何 $1 \le i \lt k$，都有一条道路连接 $x_i$ 和 $x_i+1$。
• 路线的最低价格是 $min(w_{x_1},w_{x_2},...,w_{x_k})$。
• 所需答案是从 $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$ 类操作，输出一行表示对应的答案。

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

1
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]$。

数据范围与提示

对于 $100\%$ 的数据，$1 \le n, m, q \le 10^5$，$1 \le w_i \le 10^9$。