Cyberland中有n个城市,编号从1到n,由m条双向道路连接。第 j 条路连接 aj 市和 bj 市。
对于游客来说,赛博兰的每个城市都出售纪念品。特别是,city i 以 wi 的价格出售。
现在有 q 个查询需要您处理。有两种类型的查询:
- “C a w”:a城市的价格改为w。
- “A a b”:现在一名游客将从城市a前往城市b。他会选择一条路线,他也不想去一个城市两次。他会在纪念品最便宜的城市购买纪念品(可能正好在a城市或b城市)。你应该输出他在旅行期间可以购买纪念品的最低可能价格。
更正式地说,我们可以定义路由如下:
- 路线是一系列城市 [x1, x2, ..., xk],其中 k 是某个正整数。
- 对于任意 1 ≤ i < j ≤ k, xi ≠ xj。
- 对于任意 1 ≤ i < k,存在一条连接 xi 和 xi + 1 的道路。
- 路线的最低价格为 min(wx1, wx2, ..., wxk)。
- 所需答案是从 a 到 b 的所有有效路线的最低价格中的最小值。
输入
输入的第一行包含三个整数 n, m, q (1 ≤ n, m, q ≤ 105),用一个空格分隔。
接下来的 n 行包含整数 wi (1 ≤ wi ≤ 109)。
接下来 m 行包含一对空格分隔的整数 aj 和 bj (1 ≤ aj, bj ≤ n, aj ≠ bj)。
保证最多有一条道路连接同一对城市。任意两个城市之间始终至少有一条有效路线。
接下来的 q 行每行描述一个查询。格式为“C a w”或“A a b”(1 ≤ a、b ≤ n、1 ≤ w ≤ 109)。
输出
对于每个“A”类型的查询,输出相应的答案。
示例
输入 #1
3 3 3 1 2 3 1 2 2 3 1 3 A 2 3 C 1 5 A 2 3
输出 #1
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
2 1 5 3
注意
对于第二个样本,最佳路线是:
从2到3是[2, 3]。
从6到4是[6,5,1,2,4]。
从6到7是[6,5,7]。
从3到3是[3]。