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 inf = 0x3f3f3f3f;
struct SegmentTree {
  int data[100005 << 3];
  void build(int, int, int);
  void update(int, int, int, int, int);
  int query(int, int, int, int, int);
};
void Tarjan(int, int);
void dfs1(int);
void dfs2(int);
int N, M, Q, w[100005], dfn[100005 << 1], low[100005], idx, tot;
int fa[100005 << 1], top[100005 << 1], size[100005 << 1], pre[100005 << 1],
    dep[100005 << 1], heavy[100005 << 1];
int stk[100005], stop;
SegmentTree sgt;
std::multiset<int> sqrnode[100005];
std::vector<int> bel[100005], G[100005 << 1];
int main() {
  scanf("%d%d%d", &N, &M, &Q);
  tot = N;
  for (int i = 1; i <= N; ++i) scanf("%d", w + i);
  for (int i = 1; i <= M; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v), G[v].push_back(u);
  }
  Tarjan(1, 0);
  for (int i = 1; i <= N; ++i) G[i].clear();
  for (int i = 1; i <= N; ++i)
    for (int j = 0; j < bel[i].size(); ++j) {
      int u = i, v = bel[i][j];
      G[u].push_back(v), G[v].push_back(u);
    }
  dfs1(1);
  idx = 0, top[1] = 1;
  dfs2(1);
  sgt.build(1, 1, tot);
  while (Q--) {
    char s[3];
    int a, b;
    scanf("%s%d%d", s, &a, &b);
    if (s[0] == 'C') {
      sgt.update(1, 1, tot, dfn[a], b);
      if (fa[a]) {
        sqrnode[fa[a] - N].erase(sqrnode[fa[a] - N].find(w[a]));
        sqrnode[fa[a] - N].insert(b);
        sgt.update(1, 1, tot, dfn[fa[a]], *sqrnode[fa[a] - N].begin());
      }
      w[a] = b;
    } else {
      int ans = inf;
      while (top[a] ^ top[b]) {
        if (dep[top[a]] < dep[top[b]]) std::swap(a, b);
        ans = std::min(ans, sgt.query(1, 1, tot, dfn[top[a]], dfn[a]));
        a = fa[top[a]];
      }
      if (dep[a] > dep[b]) std::swap(a, b);
      ans = std::min(ans, sgt.query(1, 1, tot, dfn[a], dfn[b]));
      if (fa[a] && fa[a] <= N) ans = std::min(ans, w[fa[a]]);
      printf("%d\n", ans);
    }
  }
  return 0;
}
void Tarjan(int u, int fa) {
  dfn[u] = low[u] = ++idx;
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i];
    if (v == fa) continue;
    if (!dfn[v]) {
      stk[stop++] = v;
      Tarjan(v, u);
      low[u] = std::min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        int p;
        ++tot;
        do {
          p = stk[--stop];
          bel[p].push_back(tot);
        } while (p ^ v);
        bel[u].push_back(tot);
      }
    } else
      low[u] = std::min(low[u], dfn[v]);
  }
}
void dfs1(int u) {
  dep[u] = dep[fa[u]] + 1;
  size[u] = 1;
  for (int i = 0; i < G[u].size(); ++i)
    if (G[u][i] ^ fa[u]) {
      fa[G[u][i]] = u, dfs1(G[u][i]);
      size[u] += size[G[u][i]];
      if (!heavy[u] || size[G[u][i]] > size[heavy[u]]) heavy[u] = G[u][i];
      if (u > N) sqrnode[u - N].insert(w[G[u][i]]);
    }
}
void dfs2(int u) {
  dfn[u] = ++idx, pre[idx] = u;
  if (heavy[u]) {
    top[heavy[u]] = top[u];
    dfs2(heavy[u]);
  }
  for (int i = 0; i < G[u].size(); ++i)
    if (G[u][i] != fa[u] && G[u][i] != heavy[u])
      top[G[u][i]] = G[u][i], dfs2(G[u][i]);
}
void SegmentTree::build(int rt, int L, int R) {
  if (L == R)
    data[rt] = (pre[L] <= N ? w[pre[L]] : *sqrnode[pre[L] - N].begin());
  else {
    int mid = (L + R) >> 1;
    build(rt << 1, L, mid);
    build(rt << 1 | 1, mid + 1, R);
    data[rt] = std::min(data[rt << 1], data[rt << 1 | 1]);
  }
}
void SegmentTree::update(int rt, int L, int R, int p, int v) {
  if (L == R)
    data[rt] = v;
  else {
    int mid = (L + R) >> 1;
    if (p <= mid)
      update(rt << 1, L, mid, p, v);
    else
      update(rt << 1 | 1, mid + 1, R, p, v);
    data[rt] = std::min(data[rt << 1], data[rt << 1 | 1]);
  }
}
int SegmentTree::query(int rt, int L, int R, int l, int r) {
  if (L >= l && R <= r) return data[rt];
  int mid = (L + R) >> 1, res = inf;
  if (l <= mid) res = std::min(res, query(rt << 1, L, mid, l, r));
  if (r > mid) res = std::min(res, query(rt << 1 | 1, mid + 1, R, l, r));
  return res;
}