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;
namespace zyt {
template <typename T>
inline void read(T &x) {
  char c;
  bool f = false;
  x = 0;
  do c = getchar();
  while (c != '-' && !isdigit(c));
  if (c == '-') f = true, c = getchar();
  do x = x * 10 + c - '0', c = getchar();
  while (isdigit(c));
  if (f) x = -x;
}
inline void read(char &c) {
  do c = getchar();
  while (!isgraph(c));
}
template <typename T>
inline void write(T x) {
  static char buf[20];
  char *pos = buf;
  if (x < 0) putchar('-'), x = -x;
  do *pos++ = x % 10 + '0';
  while (x /= 10);
  while (pos > buf) putchar(*--pos);
}
const int N = 1e5 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, q, cnt, w[N], head[N], ecnt;
struct edge {
  int to, next;
} e[M << 1];
inline void add(const int a, const int b) {
  e[ecnt] = (edge){b, head[a]}, head[a] = ecnt++;
}
namespace Block_Tree {
const int TN = N << 1, TNB = 18;
edge te[TN << 1];
int sta[M << 1], top, dfn[N], low[N], dfncnt, thead[TN], tecnt, num;
bool vis[M << 1];
int viss[N];
inline void tadd(const int a, const int b) {
  te[tecnt] = (edge){b, thead[a]}, thead[a] = tecnt++;
}
void Tarjan(const int u, const int from) {
  dfn[u] = low[u] = ++dfncnt;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (vis[i] || (~from && i == (from ^ 1))) continue;
    sta[top++] = i;
    if (dfn[v])
      low[u] = min(low[u], dfn[v]);
    else {
      Tarjan(v, i), low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        int t;
        thead[++num] = -1;
        tadd(num, u), tadd(u, num);
        viss[u] = num;
        do {
          t = sta[--top];
          vis[t] = vis[t ^ 1] = true;
          if (viss[e[t].to] < num) {
            tadd(num, e[t].to), tadd(e[t].to, num);
            viss[e[t].to] = num;
          }
        } while (t != i);
      }
    }
  }
}
void build() {
  num = n;
  memset(thead, -1, sizeof(int[n + 1]));
  for (int i = 0; i < (m << 1); i++)
    if (!vis[i]) Tarjan(e[i].to, -1);
}
}  // namespace Block_Tree
namespace Segment_Tree {
using Block_Tree::TN;
using Block_Tree::TNB;
int val[TN];
struct node {
  int minn;
} tree[1 << (TNB + 1) | 11];
inline void update(const int rot) {
  tree[rot].minn = min(tree[rot << 1].minn, tree[rot << 1 | 1].minn);
}
void build(const int rot, const int lt, const int rt) {
  if (lt == rt) {
    tree[rot].minn = val[lt];
    return;
  }
  int mid = (lt + rt) >> 1;
  build(rot << 1, lt, mid);
  build(rot << 1 | 1, mid + 1, rt);
  update(rot);
}
int query(const int rot, const int lt, const int rt, const int ls,
          const int rs) {
  if (ls <= lt && rt <= rs) return tree[rot].minn;
  int ans = INF, mid = (lt + rt) >> 1;
  if (ls <= mid) ans = min(ans, query(rot << 1, lt, mid, ls, rs));
  if (rs > mid) ans = min(ans, query(rot << 1 | 1, mid + 1, rt, ls, rs));
  return ans;
}
void change(const int rot, const int lt, const int rt, const int pos,
            const int x) {
  if (lt == rt) {
    tree[rot].minn = x;
    return;
  }
  int mid = (lt + rt) >> 1;
  if (pos <= mid)
    change(rot << 1, lt, mid, pos, x);
  else
    change(rot << 1 | 1, mid + 1, rt, pos, x);
  update(rot);
}
}  // namespace Segment_Tree
namespace Tree_Chain_Cut {
using namespace Block_Tree;
multiset<int> s[N];
int dep[TN], size[TN], fa[TN], top[TN], son[TN], dfn[TN], dfncnt;
void dfs1(const int u, const int f) {
  size[u] = 1;
  dep[u] = dep[f] + 1;
  fa[u] = f;
  for (int i = thead[u]; ~i; i = te[i].next) {
    int v = te[i].to;
    if (v == f) continue;
    dfs1(v, u);
    size[u] += size[v];
    if (size[v] > size[son[u]]) son[u] = v;
    if (u > n) s[u - n].insert(w[v]);
  }
}
void dfs2(const int u, const int t) {
  top[u] = t;
  dfn[u] = ++dfncnt;
  if (u <= n)
    Segment_Tree::val[dfncnt] = w[u];
  else
    Segment_Tree::val[dfncnt] = *s[u - n].begin();
  if (son[u]) dfs2(son[u], t);
  for (int i = thead[u]; ~i; i = te[i].next) {
    int v = te[i].to;
    if (v == fa[u] || v == son[u]) continue;
    dfs2(v, v);
  }
}
void build() {
  for (int i = 1; i <= num; i++)
    if (!dfn[i]) {
      dfs1(i, 0);
      dfs2(i, i);
    }
  Segment_Tree::build(1, 1, dfncnt);
}
void change(const int pos, const int x) {
  if (fa[pos]) {
    int tmp = fa[pos] - n;
    s[tmp].erase(s[tmp].find(w[pos]));
    s[tmp].insert(x);
    Segment_Tree::change(1, 1, dfncnt, dfn[fa[pos]], *s[tmp].begin());
  }
  w[pos] = x;
  Segment_Tree::change(1, 1, dfncnt, dfn[pos], x);
}
int query(int a, int b) {
  using Segment_Tree::query;
  int ans = INF;
  while (top[a] != top[b]) {
    if (dep[top[a]] < dep[top[b]]) swap(a, b);
    ans = min(ans, query(1, 1, dfncnt, dfn[top[a]], dfn[a]));
    a = fa[top[a]];
  }
  if (dep[a] < dep[b]) swap(a, b);
  ans = min(ans, query(1, 1, dfncnt, dfn[b], dfn[a]));
  if (b > n && fa[b]) ans = min(ans, w[fa[b]]);
  return ans;
}
}  // namespace Tree_Chain_Cut
int work() {
  read(n), read(m), read(q);
  memset(head, -1, sizeof(int[n + 1]));
  for (int i = 1; i <= n; i++) read(w[i]);
  for (int i = 0; i < m; i++) {
    int a, b;
    read(a), read(b);
    add(a, b), add(b, a);
  }
  Block_Tree::build();
  Tree_Chain_Cut::build();
  while (q--) {
    char opt;
    read(opt);
    if (opt == 'C') {
      int a, w;
      read(a), read(w);
      Tree_Chain_Cut::change(a, w);
    } else {
      int a, b;
      read(a), read(b);
      write(Tree_Chain_Cut::query(a, b)), putchar('\n');
    }
  }
  return 0;
}
}  // namespace zyt
int main() { return zyt::work(); }