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 = 1e5 + 50;
const int inf = 0x3f3f3f3f;
int n, m, q, col;
int x, y, z, a[N << 1];
char S[5];
inline int min(int u, int v) { return u < v ? u : v; }
inline int max(int u, int v) { return u > v ? u : v; }
int to[N << 1], las[N << 1], fir[N << 1], cnt;
inline void add_edge(int u, int v) {
  to[++cnt] = v;
  las[cnt] = fir[u];
  fir[u] = cnt;
  to[++cnt] = u;
  las[cnt] = fir[v];
  fir[v] = cnt;
}
int _to[N << 2], _las[N << 2], _fir[N << 2], _cnt;
inline void Add_edge(int u, int v) {
  _to[++_cnt] = v;
  _las[_cnt] = _fir[u];
  _fir[u] = _cnt;
  _to[++_cnt] = u;
  _las[_cnt] = _fir[v];
  _fir[v] = _cnt;
}
int dfn[N], low[N], Cnt;
int zn[N], Tot;
multiset<int> s[N << 1];
void tj(int u) {
  dfn[u] = low[u] = ++Cnt;
  zn[++Tot] = u;
  for (int i = fir[u]; i; i = las[i]) {
    if (!dfn[to[i]]) {
      tj(to[i]);
      low[u] = min(low[u], low[to[i]]);
      if (dfn[u] <= low[to[i]]) {
        ++col;
        do {
          z = zn[Tot];
          Add_edge(col, z);
          s[col].insert(a[z]);
          --Tot;
        } while (z != to[i]);
        Add_edge(col, u);
        s[col].insert(a[u]);
      }
    } else
      low[u] = min(low[u], dfn[to[i]]);
  }
}
int fa[N << 1], dep[N << 1], siz[N << 1], son[N << 1];
void dfs1(int u, int v) {
  fa[u] = v;
  dep[u] = dep[v] + 1;
  siz[u] = 1;
  for (int i = _fir[u]; i; i = _las[i])
    if (_to[i] != v) {
      dfs1(_to[i], u);
      siz[u] += siz[_to[i]];
      if (siz[son[u]] < siz[_to[i]]) son[u] = _to[i];
    }
}
int top[N << 1], bh[N << 1], rnk[N << 1], BH;
void dfs2(int u, int v) {
  top[u] = v;
  bh[u] = ++BH;
  rnk[BH] = u;
  if (son[u]) dfs2(son[u], v);
  for (int i = _fir[u]; i; i = _las[i])
    if (_to[i] != fa[u] && _to[i] != son[u]) dfs2(_to[i], _to[i]);
}
int tre[N << 4];
void mktree(int now, int ls, int rs) {
  if (ls == rs) {
    tre[now] = a[rnk[ls]];
    return;
  }
  int noww = now << 1, nrs = ls + rs >> 1;
  mktree(noww, ls, nrs);
  mktree(noww | 1, nrs + 1, rs);
  tre[now] = min(tre[noww], tre[noww | 1]);
}
int qmin(int now, int ls, int rs, int zuo, int you) {
  if (ls > you || rs < zuo) return inf;
  if (ls >= zuo && rs <= you) return tre[now];
  int noww = now << 1, nrs = ls + rs >> 1;
  return min(qmin(noww, ls, nrs, zuo, you),
             qmin(noww | 1, nrs + 1, rs, zuo, you));
}
void Qmin(int u, int v) {
  int ret = inf;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) z = u, u = v, v = z;
    ret = min(ret, qmin(1, 1, col, bh[top[u]], bh[u]));
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) z = u, u = v, v = z;
  ret = min(ret, qmin(1, 1, col, bh[v], bh[u]));
  if (v > n) ret = min(ret, a[fa[v]]);
  printf("%d\n", ret);
}
void change(int now, int ls, int rs, int mb, int val) {
  if (ls > mb || rs < mb) return;
  if (ls == rs) {
    z = tre[now];
    tre[now] = a[rnk[ls]] = val;
    return;
  }
  int noww = now << 1, nrs = ls + rs >> 1;
  change(noww, ls, nrs, mb, val);
  change(noww | 1, nrs + 1, rs, mb, val);
  tre[now] = min(tre[noww], tre[noww | 1]);
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    add_edge(x, y);
  }
  col = n;
  tj(1);
  dfs1(1, 0);
  dfs2(1, 1);
  for (int i = n + 1; i <= col; i++) {
    s[i].erase(s[i].find(a[fa[i]]));
    a[i] = *s[i].begin();
  }
  mktree(1, 1, col);
  for (int i = 1; i <= q; i++) {
    scanf("%s%d%d", S, &x, &y);
    if (S[0] == 'A') {
      Qmin(x, y);
    } else {
      change(1, 1, col, bh[x], y);
      if (x == 1) continue;
      s[fa[x]].erase(s[fa[x]].find(z));
      s[fa[x]].insert(y);
      change(1, 1, col, bh[fa[x]], *s[fa[x]].begin());
    }
  }
  return 0;
}