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\ne b_j$）

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

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

输出格式

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

样例一

input

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

output

1
2

样例二

input

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

output

2
1
5
3

explanation

一种可能的最优路径是：

• 2, 3
• 6, 5, 1, 2, 4
• 6, 5, 7
• 3

限制与约定

$1\le n,m,q\le {10}^5$，$1\le w_i\le {10}^9$

时间限制：$2\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载