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;
inline int read() {
  int sum = 0, ff = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') ff = -1;
    ch = getchar();
  }
  while (isdigit(ch)) sum = sum * 10 + (ch ^ 48), ch = getchar();
  return sum * ff;
}
const int N = 2e5 + 5;
const int Inf = INT_MAX;
int n, m, stak[N], low[N], dfn[N], b[N], sum, top, Tim;
int tim, cnt, ans, f[N], tp[N], son[N], a[N], id[N];
int siz[N], dep[N], head[N], tot, t[N << 2];
multiset<int> yzc[N];
vector<int> New[N];
struct Node {
  int nex, to;
};
Node e[N << 1];
inline void jia(int u, int v) {
  e[++cnt].nex = head[u];
  head[u] = cnt;
  e[cnt].to = v;
}
inline void tarjan(int u) {
  low[u] = dfn[u] = ++tim;
  stak[++top] = u;
  for (int i = 0; i < New[u].size(); i++) {
    int v = New[u][i];
    if (!dfn[v]) {
      tarjan(v);
      if (dfn[u] <= low[v]) {
        a[++tot] = Inf;
        int y;
        a[tot] = min(a[tot], a[u]);
        do {
          y = stak[top];
          top--;
          jia(y, tot);
          jia(tot, y);
        } while (v != y);
        jia(u, tot);
        jia(tot, u);
      } else
        low[u] = min(low[u], low[v]);
    } else
      low[u] = min(low[u], dfn[v]);
  }
}
inline void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  siz[u] = 1;
  f[u] = fa;
  for (int i = head[u]; i; i = e[i].nex) {
    int v = e[i].to;
    if (v == fa) continue;
    dfs(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}
inline void dfs2(int u, int Tp) {
  tp[u] = Tp;
  id[u] = ++Tim;
  if (son[u]) dfs2(son[u], Tp);
  for (int i = head[u]; i; i = e[i].nex) {
    int v = e[i].to;
    if (v == f[u] || v == son[u]) continue;
    dfs2(v, v);
  }
}
inline void build(int x, int l, int r) {
  if (l == r) {
    t[x] = b[l];
    return;
  }
  int mid = (l + r) / 2;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  t[x] = min(t[x << 1], t[x << 1 | 1]);
}
inline int ask(int x, int l, int r, int ll, int rr) {
  if (ll > r || rr < l) return Inf;
  if (ll <= l && r <= rr) return t[x];
  int mid = (l + r) / 2;
  int ans = Inf;
  if (ll <= mid) ans = ask(x << 1, l, mid, ll, rr);
  if (rr > mid) ans = min(ans, ask(x << 1 | 1, mid + 1, r, ll, rr));
  return ans;
}
inline void fix(int x, int l, int r, int pos, int v) {
  if (l == r) {
    t[x] = v;
    return;
  }
  int mid = (l + r) / 2;
  if (pos <= mid)
    fix(x << 1, l, mid, pos, v);
  else
    fix(x << 1 | 1, mid + 1, r, pos, v);
  t[x] = min(t[x << 1], t[x << 1 | 1]);
}
inline int query(int x, int y) {
  int ans = Inf;
  while (tp[x] != tp[y]) {
    if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
    ans = min(ans, ask(1, 1, tot, id[tp[x]], id[x]));
    x = f[tp[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  ans = min(ans, ask(1, 1, tot, id[x], id[y]));
  if (x > n) ans = min(ans, a[f[x]]);
  return ans;
}
inline void Fix(int x, int val) {
  int ff = f[x];
  if (ff) {
    yzc[ff].erase(yzc[ff].find(a[x]));
    yzc[ff].insert(val);
    a[ff] = *yzc[ff].begin();
    fix(1, 1, tot, id[ff], a[ff]);
  }
  a[x] = val;
  fix(1, 1, tot, id[x], val);
}
int main() {
  n = tot = read();
  m = read();
  int test = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1, x, y; i <= m; i++) {
    x = read(), y = read();
    New[x].push_back(y);
    New[y].push_back(x);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i);
  dfs(1, 0);
  dfs2(1, 1);
  for (int i = 1; i <= n; i++) b[id[i]] = a[i];
  for (int i = n + 1; i <= tot; i++) {
    for (int j = head[i]; j; j = e[j].nex) {
      int v = e[j].to;
      if (v == f[i]) continue;
      yzc[i].insert(a[v]);
    }
    if (yzc[i].empty())
      a[i] = Inf;
    else
      a[i] = *yzc[i].begin();
    b[id[i]] = a[i];
  }
  build(1, 1, tot);
  for (; test--;) {
    char opt[5];
    int x, y;
    scanf("%s", opt + 1);
    x = read(), y = read();
    if (opt[1] == 'C')
      Fix(x, y);
    else
      printf("%d\n", query(x, y));
  }
  return 0;
}