CF487E.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__x_1, _w__x_2, ..., w__x__k).
• The required answer is the minimum value of the minimum prices of all valid routes from a to b.

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,\,...,\,x_k]$，其中 $k$ 是某个正整数；
• 对任意 $1\le i<j\le k$，均有 $x_i\ne x_j$；
• 对任意 $1\le i<k$，城市 $x_i$ 与 $x_{i+1}$ 之间存在一条道路；
• 该路径的最小价格定义为 $\min(w_{x_1},\,w_{x_2},\,...,\,w_{x_k})$；
• 所求答案即为所有从 $a$ 到 $b$ 的合法路径的最小价格中的最小值。

The first line of input contains three integers n, m, q (1 ≤ n, m, q ≤ 105), separated by a single space.

Next n lines contain integers w__i (1 ≤ w__i ≤ 109).

Next m lines contain pairs of space-separated integers a__j and b__j (1 ≤ a__j, b__j ≤ n, a__j ≠ b__j).

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 ≤ a, b ≤ n, 1 ≤ w ≤ 109).

输入的第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m, q \leq 10^5$），以单个空格分隔。

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

接下来的 $m$ 行，每行包含一对以空格分隔的整数 $a_j$ 和 $b_j$（$1 \leq a_j, b_j \leq n$，且 $a_j \neq b_j$）。

保证任意两个城市之间至多有一条道路相连。任意两个城市之间始终至少存在一条有效路径。

接下来的 $q$ 行，每行描述一个查询，格式为 “C $a$ $w$” 或 “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.

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

For the second sample, an optimal routes are:

From 2 to 3 it is [2, 3].

From 6 to 4 it is [6, 5, 1, 2, 4].

From 6 to 7 it is [6, 5, 7].

From 3 to 3 it is [3].

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

从 2 到 3 的路径为 [2, 3]。

从 6 到 4 的路径为 [6, 5, 1, 2, 4]。

从 6 到 7 的路径为 [6, 5, 7]。

从 3 到 3 的路径为 [3]。