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;
int n, m, q, w[200010], head[200010], h[200010], cut[200010], low[200010],
    pre[200010], tot, tt, st[200010], tp, cnt, siz[200010], son[200010],
    bcc[200010], mem[200010], fa[200010], dep[200010], bct;
int mn[200010 << 2], p[200010], t[200010], top[200010];
multiset<int> s[200010];
struct Edge {
  int u, v, next;
  Edge() {}
  Edge(int _u, int _v, int _nt) : u(_u), v(_v), next(_nt) {}
} edge[200010 << 1], e[200010 << 1];
void links(int xx, int yy) {
  e[++tot] = Edge(xx, yy, h[xx]);
  h[xx] = tot;
}
void link(int xx, int yy) {
  edge[++tot] = Edge(xx, yy, head[xx]);
  head[xx] = tot;
}
void DFS(int x, int ft) {
  ++tt, pre[x] = tt, low[x] = tt;
  st[++tp] = x;
  for (int i = h[x]; i != 0; i = e[i].next) {
    int nt = e[i].v;
    if (nt == ft) continue;
    if (!pre[nt]) {
      DFS(nt, x);
      low[x] = min(low[x], low[nt]);
      if (low[nt] >= pre[x]) {
        cut[x] = 1, bct++;
        int ct = 0;
        for (int nn;;) {
          nn = st[tp];
          tp--;
          mem[++ct] = nn;
          bcc[nn] = bct;
          if (nn == nt) break;
        }
        ++cnt;
        for (int i = 1; i <= ct; i++) {
          s[cnt].insert(w[mem[i]]);
          link(cnt + n, mem[i]), link(mem[i], cnt + n);
        }
        link(x, cnt + n), link(cnt + n, x);
      }
    } else
      low[x] = min(low[x], pre[nt]);
  }
}
void DFS1(int x) {
  siz[x] = 1;
  for (int i = head[x]; i != 0; i = edge[i].next) {
    int nt = edge[i].v;
    if (nt == fa[x]) continue;
    fa[nt] = x;
    dep[nt] = dep[x] + 1;
    DFS1(nt);
    siz[x] += siz[nt];
    if (siz[son[x]] < siz[nt]) son[x] = nt;
  }
}
void DFS2(int x, int ft) {
  ++tt;
  t[tt] = x, p[x] = tt;
  top[x] = ft;
  if (son[x]) DFS2(son[x], ft);
  for (int i = head[x]; i != 0; i = edge[i].next) {
    int nt = edge[i].v;
    if (nt == fa[x] || nt == son[x]) continue;
    DFS2(nt, nt);
  }
}
void Pushup(int x) { mn[x] = min(mn[x << 1], mn[x << 1 | 1]); }
void build(int x, int l, int r) {
  if (l == r) {
    int id = t[l];
    if (id > n) {
      multiset<int>::iterator it = s[id - n].begin();
      mn[x] = *it;
    } else
      mn[x] = w[id];
    return;
  }
  int mid = (l + r) >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  Pushup(x);
}
void modify(int x, int l, int r, int td, int v) {
  if (l == r) {
    int id = t[l];
    if (id > n) {
      multiset<int>::iterator it = s[id - n].begin();
      mn[x] = *it;
    } else
      mn[x] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (td <= mid)
    modify(x << 1, l, mid, td, v);
  else
    modify(x << 1 | 1, mid + 1, r, td, v);
  Pushup(x);
}
int query(int x, int l, int r, int al, int ar) {
  int res = 1 << 30;
  if (al <= l && r <= ar) return mn[x];
  int mid = (l + r) >> 1;
  if (al <= mid) res = min(res, query(x << 1, l, mid, al, ar));
  if (ar > mid) res = min(res, query(x << 1 | 1, mid + 1, r, al, ar));
  return res;
}
void change(int x, int v) {
  int vl = w[x], id = bcc[x];
  if (id) {
    multiset<int>::iterator it = s[id].find(vl);
    s[id].erase(it);
    s[id].insert(v);
    modify(1, 1, cnt + n, p[id + n], 0);
  }
  w[x] = v;
  modify(1, 1, cnt + n, p[x], v);
}
int getmin(int x, int y) {
  int res = 1 << 30;
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) swap(x, y);
    res = min(res, query(1, 1, cnt + n, p[top[y]], p[y]));
    y = fa[top[y]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  res = min(res, query(1, 1, cnt + n, p[x], p[y]));
  if (x > n) res = min(res, w[fa[x]]);
  return res;
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  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);
    links(x, y), links(y, x);
  }
  tot = 0, cnt = 0;
  DFS(1, -1);
  tt = 0;
  DFS1(1);
  DFS2(1, 1);
  build(1, 1, cnt + n);
  while (q--) {
    static char typ[10];
    int x, y;
    scanf("%s%d%d", typ + 1, &x, &y);
    if (typ[1] == 'C')
      change(x, y);
    else
      printf("%d\n", getmin(x, y));
  }
  return 0;
}