Problem: There are n cities in Cyberland, numbered from 1 to n, connected by m bidirectional roads. The j-th road connects city aj and bj.

For tourists, souvenirs are sold in every city of Cyberland. In particular, city i sell it at a price of wi.

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 [x1, x2, ..., xk], where k is a certain positive integer.
  * For any 1 ≤ i < j ≤ k, xi ≠ xj.
  * For any 1 ≤ i < k, there is a road connecting xi and xi + 1.
  * The minimum price of the route is min(wx1, wx2, ..., wxk).
  * The required answer is the minimum value of the minimum prices of all valid routes from a to b.

Input

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 wi (1 ≤ wi ≤ 109).

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

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).

Output

For each query of type "A", output the corresponding answer.

Examples

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

Note

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].

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 400000 + 100;
int G[N], G2[N], to2[N], ne2[N], ne[N], to[N], sz[N], fa[N], dp[N], tp[N],
    das[N * 2], n, m, q;
int hc[N], xb, xb2, cnt, w[N], dfn[N], dft[N], clk;
int q1, q2, ans;
void modify(int o, int l, int r) {
  if (l == r) {
    das[o] = w[dft[l]];
    return;
  }
  int mid = (l + r) >> 1;
  if (q1 <= mid)
    modify(o << 1, l, mid);
  else
    modify(o << 1 | 1, mid + 1, r);
  das[o] = min(das[o << 1], das[o << 1 | 1]);
}
void qry(int o, int l, int r) {
  if (q1 <= l && r <= q2) {
    ans = min(ans, das[o]);
    return;
  }
  int mid = (l + r) >> 1;
  if (q1 <= mid) qry(o << 1, l, mid);
  if (q2 > mid) qry(o << 1 | 1, mid + 1, r);
}
void bt(int o, int l, int r) {
  if (l == r) {
    das[o] = w[dft[l]];
    return;
  }
  int mid = (l + r) >> 1;
  bt(o << 1, l, mid);
  bt(o << 1 | 1, mid + 1, r);
  das[o] = min(das[o << 1], das[o << 1 | 1]);
}
int query(int x, int y) {
  ans = 0x3f3f3f3f;
  for (; tp[x] != tp[y]; x = fa[tp[x]]) {
    if (dp[tp[x]] < dp[tp[y]]) swap(x, y);
    q1 = dfn[tp[x]];
    q2 = dfn[x];
    qry(1, 1, clk);
  }
  if (dp[x] < dp[y]) swap(x, y);
  q1 = dfn[y];
  q2 = dfn[x];
  qry(1, 1, clk);
  if (fa[y] && fa[y] <= n) ans = min(ans, w[fa[y]]);
  return ans;
}
void add2(int x, int y) {
  ne2[xb2] = G2[x];
  to2[xb2] = y;
  G2[x] = xb2++;
  ne2[xb2] = G2[y];
  to2[xb2] = x;
  G2[y] = xb2++;
}
multiset<int> st[N];
int S[N];
int pre[N], no[N];
int s_cnt;
int dfs(int u, int fa) {
  int lowu = pre[u] = ++clk;
  S[s_cnt++] = u;
  for (int i = G[u]; ~i; i = ne[i]) {
    int v = to[i], y;
    if (!pre[v]) {
      int lowv = dfs(v, u);
      lowu = min(lowu, lowv);
      if (lowv >= pre[u])
        for (add2((++cnt) + n, u), y = 0; y != v; st[cnt].insert(w[y]))
          no[y = S[--s_cnt]] = cnt, add2(cnt + n, y);
    } else if (v != fa)
      lowu = min(lowu, pre[v]);
  }
  return lowu;
}
void dfs2(int x) {
  sz[x] = 1;
  for (int i = G2[x]; ~i; i = ne2[i])
    if (!sz[to2[i]]) {
      fa[to2[i]] = x;
      dp[to2[i]] = dp[x] + 1;
      dfs2(to2[i]);
      sz[x] += sz[to2[i]];
      if (sz[to2[i]] > sz[hc[x]]) hc[x] = to2[i];
    }
}
void dfs3(int x, int y) {
  tp[x] = y;
  dfn[x] = ++clk;
  dft[clk] = x;
  if (hc[x]) dfs3(hc[x], y);
  for (int i = G2[x]; ~i; i = ne2[i])
    if (!dfn[to2[i]]) dfs3(to2[i], to2[i]);
}
void init() {
  dfs(1, -1);
  clk = 0;
  dfs2(1);
  dfs3(1, 1);
  for (int i = 1; i <= cnt; i++) w[i + n] = *st[i].begin();
  bt(1, 1, clk);
}
void add(int x, int y) {
  ne[xb] = G[x];
  to[xb] = y;
  G[x] = xb++;
}
char s[100];
int main() {
  scanf("%d%d%d", &n, &m, &q);
  memset(G, -1, sizeof(G));
  memset(G2, -1, sizeof(G2));
  for (int i = 1; i <= n; i++) scanf("%d", w + i);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
  }
  init();
  while (q--) {
    int x, y;
    scanf("%s%d%d", s, &x, &y);
    if (s[0] == 'C') {
      if (fa[x] > n) {
        st[fa[x] - n].erase(st[fa[x] - n].lower_bound(w[x]));
        st[fa[x] - n].insert(y);
        w[fa[x]] = *st[fa[x] - n].begin();
        q1 = dfn[fa[x]];
        modify(1, 1, clk);
      }
      w[x] = y;
      q1 = dfn[x];
      modify(1, 1, clk);
    } else {
      printf("%d\n", query(x, y));
    }
  }
  return 0;
}