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>
template <class T>
inline void read(T &x) {
  x = 0;
  bool f = 0;
  char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) f = (c == '-');
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  x = f ? -x : x;
}
const int MAXN(100010), MAXM(200010), INF(0x7fffffff);
int n, m, q, a, b, val[MAXM];
struct Node {
  int nd, nx;
} bot[MAXN << 1];
int tot, first[MAXN];
void add(int a, int b) {
  bot[++tot] = (Node){b, first[a]};
  first[a] = tot;
}
int dfn[MAXM], low[MAXN], cnt, st[MAXN], tp, vis[MAXN], flag[MAXN], ant;
std::vector<int> Edge[MAXM];
void addedge(int a, int b) { Edge[a].push_back(b); }
int min(int a, int b) { return a > b ? b : a; }
void swap(int &a, int &b) {
  int t(a);
  a = b;
  b = t;
}
std::multiset<int> H[MAXM];
void Tarjan(int x, int f) {
  vis[x] = flag[x] = 1;
  st[++tp] = x;
  dfn[x] = low[x] = ++cnt;
  for (int v = first[x]; v; v = bot[v].nx) {
    if (!vis[bot[v].nd]) {
      Tarjan(bot[v].nd, x);
      low[x] = min(low[x], low[bot[v].nd]);
      if (low[bot[v].nd] >= dfn[x]) {
        for (val[++ant] = INF; flag[bot[v].nd]; tp--) {
          flag[st[tp]] = 0;
          addedge(ant, st[tp]);
          H[ant].insert(val[st[tp]]);
          val[ant] = min(val[ant], val[st[tp]]);
        }
        addedge(x, ant);
      }
    } else if (bot[v].nd != f)
      low[x] = min(low[x], dfn[bot[v].nd]);
  }
}
int depth[MAXM], Siz[MAXM], son[MAXM], top[MAXM], fa[MAXM], num[MAXM];
void Dfs1(int x, int f) {
  depth[x] = depth[f] + 1;
  Siz[x] = 1;
  fa[x] = f;
  for (int v = 0, sz = Edge[x].size(); v < sz; v++) {
    Dfs1(Edge[x][v], x);
    Siz[x] += Siz[Edge[x][v]];
    if (Siz[son[x]] < Siz[Edge[x][v]]) son[x] = Edge[x][v];
  }
}
void Dfs2(int x, int up) {
  dfn[x] = ++cnt;
  num[cnt] = x;
  top[x] = up;
  if (son[x]) Dfs2(son[x], up);
  for (int v = 0, sz = Edge[x].size(); v < sz; v++)
    if (Edge[x][v] != son[x]) Dfs2(Edge[x][v], Edge[x][v]);
}
struct SMT {
  int nx[MAXM << 1][2], sl[MAXM << 1], sr[MAXM << 1], small[MAXM << 1], stot,
      root;
  void update(int k) { small[k] = min(small[nx[k][0]], small[nx[k][1]]); }
  void build(int &k, int l, int r) {
    k = ++stot;
    sl[k] = l;
    sr[k] = r;
    if (l == r) {
      small[k] = val[num[l]];
      return;
    }
    int mid = (l + r) >> 1;
    build(nx[k][0], l, mid);
    build(nx[k][1], mid + 1, r);
    update(k);
  }
  void modfiy(int k, int x, int y) {
    if (sl[k] == x && sr[k] == x) {
      small[k] = y;
      return;
    }
    int mid = (sl[k] + sr[k]) >> 1;
    modfiy(nx[k][x > mid], x, y);
    update(k);
  }
  int query(int k, int l, int r) {
    if (sl[k] == l && sr[k] == r) return small[k];
    int mid = (sl[k] + sr[k]) >> 1;
    if (r <= mid)
      return query(nx[k][0], l, r);
    else if (l > mid)
      return query(nx[k][1], l, r);
    else
      return min(query(nx[k][0], l, mid), query(nx[k][1], mid + 1, r));
  }
} tree;
int ask(int a, int b) {
  int Ans = INF;
  for (; top[a] != top[b]; a = fa[top[a]]) {
    if (depth[top[a]] < depth[top[b]]) swap(a, b);
    Ans = min(Ans, tree.query(tree.root, dfn[top[a]], dfn[a]));
  }
  if (depth[a] > depth[b]) swap(a, b);
  Ans = min(Ans, tree.query(tree.root, dfn[a], dfn[b]));
  if (a > n) Ans = min(Ans, val[fa[a]]);
  return Ans;
}
void change(int a, int b) {
  tree.modfiy(tree.root, dfn[a], b);
  if (fa[a]) {
    H[fa[a]].erase(H[fa[a]].find(val[a]));
    val[a] = b;
    H[fa[a]].insert(val[a]);
    tree.modfiy(tree.root, dfn[fa[a]], *(H[fa[a]].begin()));
  } else
    val[a] = b;
}
int main() {
  read(n);
  read(m);
  read(q);
  for (int i = 1; i <= n; i++) read(val[i]);
  for (int i = 1; i <= m; i++) {
    read(a);
    read(b);
    add(a, b);
    add(b, a);
  }
  ant = n;
  Tarjan(1, 0);
  cnt = 0;
  Dfs1(1, 0);
  Dfs2(1, 1);
  tree.build(tree.root, 1, cnt);
  for (int i = 1; i <= q; i++) {
    char ch[10];
    scanf("%s", ch);
    read(a);
    read(b);
    if (ch[0] == 'C')
      change(a, b);
    else
      printf("%d\n", ask(a, b));
  }
  return 0;
}