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>
int n, m, Q;
int cntp;
struct Edge {
  int fr[222222];
  int ne[433333];
  int to[433333];
  int w[222222];
  int cnt;
  void add(int a, int b) {
    ne[++cnt] = fr[a], fr[a] = cnt, to[cnt] = b;
    ne[++cnt] = fr[b], fr[b] = cnt, to[cnt] = a;
  }
} A, B;
void input() {
  scanf("%d %d %d", &n, &m, &Q);
  cntp = n;
  for (int i = 1; i <= n; i++) scanf("%d", &A.w[i]);
  for (int i = 1, a, b; i <= m; i++) {
    scanf("%d %d", &a, &b);
    A.add(a, b);
  }
}
int dfn[222222];
int low[222222];
int sta[433333];
int be[222222];
int Top, cntd;
void tarjan(int a, int Fa) {
  dfn[a] = low[a] = ++cntd;
  sta[++Top] = a;
  for (int i = A.fr[a]; i; i = A.ne[i]) {
    if (A.to[i] == Fa) continue;
    if (!dfn[A.to[i]]) {
      sta[++Top] = a;
      tarjan(A.to[i], a);
      low[a] = (((low[a]) < (low[A.to[i]])) ? (low[a]) : (low[A.to[i]]));
      if (low[A.to[i]] >= dfn[a]) {
        ++cntp;
        do {
          if (be[sta[Top]] != cntp) {
            B.add(sta[Top], cntp);
            be[sta[Top]] = cntp;
          }
        } while (sta[Top--] != a);
      }
    } else
      low[a] = (((low[a]) < (dfn[A.to[i]])) ? (low[a]) : (dfn[A.to[i]]));
  }
}
struct Seg_Tree {
  int t[888888];
  void modify(int now, int l, int r, int p, int v) {
    if (l == r) {
      t[now] = v;
      return;
    }
    int mid = l + r >> 1;
    if (p <= mid)
      modify(now << 1, l, mid, p, v);
    else
      modify(now << 1 | 1, mid + 1, r, p, v);
    t[now] = (((t[now << 1]) < (t[now << 1 | 1])) ? (t[now << 1])
                                                  : (t[now << 1 | 1]));
  }
  int query(int now, int l, int r, int L, int R) {
    if (L <= l && R >= r) return t[now];
    int mid = l + r >> 1, ta = 1000000007, tb = 1000000007;
    if (L <= mid) ta = query(now << 1, l, mid, L, R);
    if (R > mid) tb = query(now << 1 | 1, mid + 1, r, L, R);
    return (((ta) < (tb)) ? (ta) : (tb));
  }
} T;
struct Data {
  int p, v;
  bool operator<(const Data a) const { return v > a.v; }
};
std::priority_queue<Data> h[222222];
int siz[222222];
int son[222222];
int dep[222222];
int top[222222];
int fa[222222];
void dfs1(int a) {
  dep[a] = dep[fa[a]] + 1;
  int ts = -1, tp = 0;
  for (int i = B.fr[a]; i; i = B.ne[i]) {
    if (B.to[i] == fa[a]) continue;
    fa[B.to[i]] = a;
    dfs1(B.to[i]);
    siz[a] += siz[B.to[i]];
    if (siz[B.to[i]] > ts) ts = siz[B.to[i]], tp = B.to[i];
  }
  son[a] = tp;
  siz[a]++;
}
void dfs2(int a, int tp) {
  top[a] = tp;
  dfn[a] = ++cntd;
  if (!son[a]) return;
  dfs2(son[a], tp);
  for (int i = B.fr[a]; i; i = B.ne[i]) {
    if (B.to[i] == fa[a] || B.to[i] == son[a]) continue;
    dfs2(B.to[i], B.to[i]);
  }
}
void pre() {
  cntd = 0;
  dfs1(1);
  dfs2(1, 1);
  B.w[202020] = 1000000007;
  for (int i = 1; i <= cntp; i++) h[i].push((Data){202020, 1000000007});
  for (int i = 1; i <= n; i++) {
    B.w[i] = A.w[i];
    h[i].push((Data){i, B.w[i]});
    if (i != 1) h[be[i]].push((Data){i, B.w[i]});
  }
  for (int i = 1; i <= cntp; i++) {
    T.modify(1, 1, cntp, dfn[i], h[i].top().v);
  }
}
void Mdf(int a, int fro, int b) {
  int k = h[a].top().v;
  while (B.w[h[a].top().p] != h[a].top().v) h[a].pop();
  h[a].push((Data){fro, b});
  if (h[a].top().v != k) T.modify(1, 1, cntp, dfn[a], h[a].top().v);
}
int Qry(int a, int b) {
  int tmp = 1000000007, tpp;
  while (top[a] != top[b]) {
    if (dep[top[a]] > dep[top[b]]) {
      tpp = T.query(1, 1, cntp, dfn[top[a]], dfn[a]);
      tmp = (((tmp) < (tpp)) ? (tmp) : (tpp));
      a = fa[top[a]];
    } else {
      tpp = T.query(1, 1, cntp, dfn[top[b]], dfn[b]);
      tmp = (((tpp) < (tmp)) ? (tpp) : (tmp));
      b = fa[top[b]];
    }
  }
  if (a == b) {
    tmp = (((h[a].top().v) < (tmp)) ? (h[a].top().v) : (tmp));
    if (a > n)
      tmp = (((h[fa[a]].top().v) < (tmp)) ? (h[fa[a]].top().v) : (tmp));
  } else {
    if (dep[a] > dep[b]) std::swap(a, b);
    tpp = T.query(1, 1, cntp, dfn[a], dfn[b]);
    tmp = (((tmp) < (tpp)) ? (tmp) : (tpp));
    if (a > n)
      tmp = (((tmp) < (h[fa[a]].top().v)) ? (tmp) : (h[fa[a]].top().v));
  }
  return tmp;
}
void work() {
  char op[3];
  for (int i = 1, a, b; i <= Q; i++) {
    scanf("%s", op);
    scanf("%d %d", &a, &b);
    if (op[0] == 'C') {
      B.w[a] = b;
      Mdf(a, a, b);
      Mdf(be[a], a, b);
    } else
      printf("%d\n", Qry(a, b));
  }
}
int main() {
  input();
  tarjan(1, 0);
  pre();
  work();
  return 0;
}