赛博乐园有n个城市，从1到n编号，由m条双向道路连接。第j条路连接a_j市和b_j市。

对于游客来说，赛博乐园的每个城市都有纪念品出售。第i个城市的纪念品以w_j的价格出售。

现在有q个查询需要处理。有两种类型的查询：

• “C a w”：城市a的价格改为w。

• “A a b”：现在游客将从城市a旅行到b。他会选择一条路线，他也不想两次访问一个城市。他会在纪念品最便宜的城市（可能正是在城市a或b）购买纪念品。你应该输出他在旅行期间可以购买纪念品的最低价格。

我们将路线定义如下：

路线是一系列城市[x_1， x_2, ..., x_k]，其中k是某个正整数。

对于任何1 ≤ i < j ≤ k, x_i ≠ x_j.

对于任何1 ≤ i < k、 有一条路连接$xi和x{i+1}$.

路线的最低价格是min(w_{x1}， w{x2}, ..., w{xk}).

所需答案是从a到b的所有有效路线的最低价格的最小值。

第一行输入包含三个整数n， m, q（1≤n， m, q ≤ 10^5),用空格隔开。

接下来的n行包含整数w_i（1≤w_i ≤ 10^9).

接下来的m行包含成对的空间分隔整数a_j和b_j（1≤a_j， b_j ≤ n, a_j ≠ b_j).

保证最多有一条道路连接同一对城市。任何两个城市之间总是至少有一条有效路线。

接下来的q行分别描述一个查询。格式为“C a w”或“A a b”（1≤a， b ≤ n, 1 ≤ w ≤ 10^9).

对于每个操作A输出一行，为路线上纪念品最便宜的城市的价格

对于第二个样例，最佳路线是：

从2到3是[2,3]。

从6到4，它是[6,5,1,2,4]。

从6到7是[6,5,7]。

从3到3是[3]。

Codeforces