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;
template <class T>
inline void read(T& num) {
  bool start = false, neg = false;
  char c;
  num = 0;
  while ((c = getchar()) != EOF) {
    if (c == '-')
      start = neg = true;
    else if (c >= '0' && c <= '9') {
      start = true;
      num = num * 10 + c - '0';
    } else if (start)
      break;
  }
  if (neg) num = -num;
}
struct edge {
  int next, to;
};
const int maxn = (int)(1e6) + 5;
int fr[maxn];
edge e[maxn << 1];
vector<int> nxt[maxn];
int tote, n, m, q;
inline void addone(int u, int v) {
  ++tote;
  e[tote].next = fr[u];
  fr[u] = tote;
  e[tote].to = v;
}
inline void addedge(int u, int v) {
  addone(u, v);
  addone(v, u);
}
int dfn[maxn], low[maxn], pa[maxn];
int ai[maxn], bi[maxn], ci[maxn];
int be[maxn];
int rt, idx;
int Find(int x) { return pa[x] == x ? x : pa[x] = Find(pa[x]); }
void _dfs(int x, int f) {
  int cnt = 0;
  dfn[x] = low[x] = ++idx;
  for (int i = fr[x]; i != -1; i = e[i].next) {
    if (!dfn[e[i].to]) {
      _dfs(e[i].to, i >> 1);
      ++cnt;
      low[x] = min(low[x], low[e[i].to]);
      if (low[e[i].to] >= dfn[x])
        bi[x] = 1;
      else
        pa[Find(i >> 1)] = Find(f);
    } else if (dfn[e[i].to] < dfn[x]) {
      low[x] = min(low[x], dfn[e[i].to]);
      pa[Find(i >> 1)] = Find(f);
    }
  }
  if (x == rt) bi[x] = (cnt > 1);
}
inline void printG() {
  printf("=== All Ge Dian ===\n");
  for (int i = (1); i <= (n); i++)
    if (bi[i]) printf("%d ", i);
  putchar('\n');
}
inline void printC() {
  printf("== All BCC ===\n");
  for (int i = (1); i <= (n); i++)
    if (1) {
      printf("node %d : ", i);
      for (int j = 0; j < nxt[i].size(); j++) printf("%d ", nxt[i][j]);
      putchar('\n');
    } else
      printf("node %d : belong to %d\n", i, be[i]);
}
int fa[maxn], siz[maxn], son[maxn];
int dep[maxn], tp[maxn];
void dfs(int x, int f) {
  siz[x] = 1;
  son[x] = 0;
  fa[x] = f;
  dep[x] = dep[f] + 1;
  for (int i = fr[x]; i != -1; i = e[i].next)
    if (e[i].to != f) {
      dfs(e[i].to, x);
      siz[x] += siz[e[i].to];
      if (siz[e[i].to] > siz[son[x]]) son[x] = e[i].to;
    }
}
void link(int x, int tx) {
  dfn[x] = ++idx;
  tp[x] = tx;
  if (son[x]) link(son[x], tx);
  for (int i = fr[x]; i != -1; i = e[i].next)
    if (e[i].to != fa[x] && e[i].to != son[x]) link(e[i].to, e[i].to);
}
multiset<int> H[maxn];
int mi[maxn << 2];
void M(int x, int l, int r, int ps, int v) {
  if (l == r) {
    mi[x] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (ps <= mid)
    M(x << 1, l, mid, ps, v);
  else
    M(x << 1 | 1, mid + 1, r, ps, v);
  mi[x] = min(mi[x << 1], mi[x << 1 | 1]);
}
int Q(int x, int l, int r, int s, int t) {
  if (s <= l && r <= t) return mi[x];
  int mid = (l + r) >> 1, res = (int)(1e9) + 100;
  if (s <= mid) res = min(res, Q(x << 1, l, mid, s, t));
  if (mid < t) res = min(res, Q(x << 1 | 1, mid + 1, r, s, t));
  return res;
}
inline int Qs(int u, int v) {
  int res = (int)(1e9) + 100;
  while (1) {
    if (dep[u] > dep[v]) swap(u, v);
    int tu = tp[u], tv = tp[v];
    if (tu == tv) {
      if (u > n && fa[u]) res = min(res, (*H[fa[u]].begin()));
      res = min(res, Q(1, 1, idx, dfn[u], dfn[v]));
      return res;
    } else if (dep[tp[u]] > dep[tp[v]]) {
      res = min(res, Q(1, 1, idx, dfn[tp[u]], dfn[u]));
      u = fa[tp[u]];
    } else {
      res = min(res, Q(1, 1, idx, dfn[tp[v]], dfn[v]));
      v = fa[tp[v]];
    }
  }
}
char opt[10];
int main() {
  read(n);
  read(m);
  read(q);
  for (int i = (1); i <= (m); i++) pa[i] = i;
  for (int i = (1); i <= (n); i++) read(ai[i]);
  memset(fr, -1, sizeof(fr));
  ++tote;
  for (int i = (1); i <= (m); i++) {
    int u, v;
    read(u);
    read(v);
    addedge(u, v);
  }
  for (int i = (1); i <= (n); i++)
    if (!dfn[i]) rt = i, _dfs(i, 0);
  for (int i = (1); i <= (m); i++)
    if (Find(i) == i) ci[i] = ++idx;
  for (int x = (1); x <= (n); x++)
    if (bi[x]) {
      for (int i = fr[x]; i != -1; i = e[i].next) {
        nxt[x].push_back(ci[Find(i >> 1)]);
      }
      sort(nxt[x].begin(), nxt[x].end());
      nxt[x].erase(unique(nxt[x].begin(), nxt[x].end()), nxt[x].end());
    } else if (fr[x] != -1)
      nxt[x].push_back(ci[Find(fr[x] >> 1)]);
  memset(fr, -1, sizeof(fr));
  tote = 0;
  for (int i = (1); i <= (n); i++)
    for (int j = 0; j < nxt[i].size(); j++) addedge(i, nxt[i][j]);
  memset(dfn, 0, sizeof(dfn));
  idx = 0;
  for (int i = (1); i <= (n); i++)
    if (!dfn[i]) dfs(i, 0), link(i, i);
  for (int i = (1); i <= (n); i++) {
    H[i].insert(ai[i]);
    if (fa[i]) H[fa[i]].insert(ai[i]);
  }
  for (int i = (1); i <= (idx); i++) {
    M(1, 1, idx, dfn[i], (*H[i].begin()));
  }
  for (int i = (1); i <= (q); i++) {
    scanf("%s", opt);
    if (opt[0] == 'C') {
      int x, w;
      read(x);
      read(w);
      H[x].erase(H[x].find(ai[x]));
      if (fa[x]) H[fa[x]].erase(H[fa[x]].find(ai[x]));
      ai[x] = w;
      H[x].insert(ai[x]);
      if (fa[x]) H[fa[x]].insert(ai[x]);
      M(1, 1, idx, dfn[x], (*H[x].begin()));
      if (fa[x]) M(1, 1, idx, dfn[fa[x]], (*H[fa[x]].begin()));
    } else {
      int a, b;
      read(a);
      read(b);
      if (a == b)
        printf("%d\n", ai[a]);
      else
        printf("%d\n", Qs(a, b));
    }
  }
  return 0;
}