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>
const int MAX = 2e5 + 10;
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
using namespace std;
int a[MAX], n, m, Q, head[MAX], tot = 0;
int dfn[MAX], low[MAX], num, sta[MAX], new_id[MAX];
vector<int> dcc[MAX];
int cnt, ctop, cut[MAX], root;
int top[MAX], son[MAX], fa[MAX], sz[MAX], dep[MAX], id[MAX], rk[MAX], cnt2;
int fa2[MAX], fbk[MAX];
multiset<int> S[MAX];
multiset<int>::iterator it;
struct Edge {
  int u, v, nxt;
} edge[MAXN];
void add(int u, int v) {
  edge[++tot] = {u, v, head[u]};
  head[u] = tot;
}
int dfs1(int u, int ff) {
  sz[u] = 1;
  dep[u] = dep[ff] + 1;
  fa[u] = ff;
  for (int i = head[u]; i; i = edge[i].nxt) {
    int v = edge[i].v;
    if (v == ff) continue;
    sz[u] += dfs1(v, u);
    if (sz[v] > sz[son[u]]) {
      son[u] = v;
    }
  }
  return sz[u];
}
void dfs2(int u, int ff) {
  top[u] = ff;
  id[u] = ++cnt2;
  rk[cnt2] = u;
  if (son[u]) {
    dfs2(son[u], ff);
  }
  for (int i = head[u]; i; i = edge[i].nxt) {
    int v = edge[i].v;
    if (v != son[u] && v != fa[u]) dfs2(v, v);
  }
}
void tarjan(int x) {
  dfn[x] = low[x] = ++num;
  sta[++ctop] = x;
  if (x == root && head[x] == 0) {
    dcc[++cnt].push_back(x);
    return;
  }
  int flg = 0;
  for (int i = head[x]; i; i = edge[i].nxt) {
    int y = edge[i].v;
    if (!dfn[y]) {
      tarjan(y);
      low[x] = min(low[x], low[y]);
      if (low[y] >= dfn[x]) {
        flg++;
        if (x != root || flg > 1) cut[x] = 1;
        cnt++;
        int z;
        do {
          z = sta[ctop--];
          S[cnt].insert(a[z]);
          dcc[cnt].push_back(z);
        } while (z != y);
        dcc[cnt].push_back(x);
        S[cnt].insert(a[x]);
      }
    } else
      low[x] = min(low[x], dfn[y]);
  }
}
struct SEGT {
  int minv[MAX << 2];
  void pushup(int rt) { minv[rt] = min(minv[rt << 1], minv[rt << 1 | 1]); }
  void build(int rt, int l, int r) {
    if (l == r) {
      minv[rt] = *S[rk[l]].begin();
      if (minv[rt] == 0) {
        printf("%d--Size:%d\n", l, S[rk[l]].size());
      }
      return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
  }
  void change1(int rt, int l, int r, int x, int v) {
    if (l == r) {
      S[rk[x]].insert(v);
      int minn = *(S[rk[x]].begin());
      minv[rt] = minn;
      return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
      change1(rt << 1, l, mid, x, v);
    else
      change1(rt << 1 | 1, mid + 1, r, x, v);
    pushup(rt);
  }
  int querymin(int rt, int l, int r, int L, int R) {
    if (L > R) return 0x3f3f3f3f;
    int ans = 0x3f3f3f3f;
    if (L <= l && r <= R) {
      ans = min(ans, minv[rt]);
      return ans;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) ans = min(ans, querymin(rt << 1, l, mid, L, R));
    if (R > mid) ans = min(ans, querymin(rt << 1 | 1, mid + 1, r, L, R));
    return ans;
  }
} T;
char op[3];
void query(int x, int y) {
  int ans = 0x3f3f3f3f;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    ans = min(ans, T.querymin(1, 1, num, id[top[x]], id[x]));
    x = fa[top[x]];
  }
  if (dep[x] < dep[y]) swap(x, y);
  if (y <= cnt && fa2[y] != 0) {
    ans = min(ans, *(S[fa2[y]].begin()));
  }
  ans = min(ans, T.querymin(1, 1, num, id[y], id[x]));
  printf("%d\n", ans);
}
void build_new_val(int x, int f) {
  fa2[x] = f;
  for (int i = head[x]; i; i = edge[i].nxt) {
    int y = edge[i].v;
    if (y == f) continue;
    build_new_val(y, x);
    if (y > cnt) {
      S[x].insert(fbk[y]);
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &Q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  int u, v;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  for (int i = 1; i <= n; i++) {
    if (!dfn[i]) {
      root = i;
      tarjan(i);
    }
  }
  num = cnt;
  if (cnt == 1) {
    S[1].clear();
    for (int i = 1; i <= n; i++) S[1].insert(a[i]);
    for (int i = 1; i <= Q; i++) {
      int x, w, y;
      scanf("%s", op);
      if (op[0] == 'C') {
        scanf("%d%d", &x, &w);
        if ((it = S[1].find(a[x])) != S[1].end()) S[1].erase(it);
        a[x] = w;
        S[1].insert(w);
      } else {
        scanf("%d%d", &x, &y);
        if (x == y)
          printf("%d\n", a[x]);
        else
          printf("%d\n", *S[1].begin());
      }
    }
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    if (cut[i]) {
      new_id[i] = ++num;
      S[num].insert(a[i]);
      if (a[i] == 0) {
        printf("gedian\n");
      }
    }
  }
  memset(head, 0, sizeof(head));
  tot = 0;
  for (int i = 1; i <= cnt; i++) {
    for (auto x : dcc[i]) {
      if (cut[x]) {
        add(i, new_id[x]);
        add(new_id[x], i);
        if ((it = S[i].find(a[x])) != S[i].end()) S[i].erase(it);
        fbk[new_id[x]] = a[x];
      } else {
        new_id[x] = i;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!cut[i]) {
      build_new_val(new_id[i], 0);
      dfs1(new_id[i], 0);
      dfs2(new_id[i], new_id[i]);
      break;
    }
  }
  memset(T.minv, 0x3f3f3f3f, sizeof(T.minv));
  T.build(1, 1, num);
  for (int i = 1; i <= Q; i++) {
    int x, w, y;
    scanf("%s", op);
    if (op[0] == 'C') {
      scanf("%d%d", &x, &w);
      if (!cut[x]) {
        int t = new_id[x];
        if ((it = S[t].find(a[x])) != S[t].end()) S[t].erase(it);
        T.change1(1, 1, num, id[t], w);
        a[x] = w;
      } else {
        int t = new_id[x];
        if ((it = S[t].find(a[x])) != S[t].end()) S[t].erase(it);
        T.change1(1, 1, num, id[t], w);
        if (fa2[t] > 0) {
          if ((it = S[fa2[t]].find(a[x])) != S[fa2[t]].end())
            S[fa2[t]].erase(it);
          T.change1(1, 1, num, id[fa2[t]], w);
        }
        a[x] = w;
      }
    } else {
      scanf("%d%d", &x, &y);
      if (x == y) {
        printf("%d\n", a[x]);
        continue;
      } else {
        query(new_id[x], new_id[y]);
      }
    }
  }
  return 0;
}