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 Input {
inline char Sc() {
  static const int LEN = 100000;
  static char Buf[LEN], *OP = Buf, *ED = Buf;
  if (OP == ED) ED = (OP = Buf) + fread(Buf, 1, LEN, stdin);
  return *OP++;
}
template <class T>
inline void rd(T &x) {
  static char c;
  for (x = 0, c = Sc(); c < 48; c = Sc())
    if (c == -1) {
      x = -1;
      return;
    }
  for (; c > 47; c = Sc()) x = (x << 1) + (x << 3) + (c ^ 48);
}
inline void rd(char *s) {
  static int c, h;
  h = 0;
  for (c = Sc(); c < 33; c = Sc())
    if (c == -1) {
      s[0] = 0;
      return;
    }
  for (; c > 32; c = Sc()) s[h++] = c;
  s[h] = 0;
}
}  // namespace Input
namespace Output {
const int LEN = 100000;
char buffer[LEN];
char *s = buffer;
inline void flush() {
  fwrite(buffer, 1, s - buffer, stdout);
  s = buffer;
  fflush(stdout);
}
inline void pt(const char ch) {
  if (s - buffer > LEN - 2) flush();
  *s++ = ch;
}
inline void pt(char *str, int t = 0) {
  while (*str != 0) pt(*str++);
  if (t == 0)
    pt('\n');
  else
    pt(' ');
}
template <class T>
inline void pt(T x, int t = 0) {
  static char buf[25] = {0}, *p = buf;
  if (x < 0) pt('-'), x = -x;
  if (x == 0) pt('0');
  while (x) *(++p) = x % 10, x /= 10;
  while (p != buf) pt(char(*(p--) ^ 48));
  if (t == 0)
    pt('\n');
  else
    pt(' ');
}
}  // namespace Output
struct edge {
  int nxt, t;
} e[100010 << 1];
int head[100010], edge_cnt;
void add_edge(int x, int y) {
  e[edge_cnt] = (edge){head[x], y};
  head[x] = edge_cnt++;
}
int dfn[100010], low[100010], Tar_cnt, stk[100010], stk_top, ID[100010],
    VBC_cnt;
bool CutV[200010];
vector<int> E[200010];
void Tarjan(int x, int f) {
  dfn[x] = low[x] = ++Tar_cnt;
  stk[++stk_top] = x;
  int i, son = 0;
  for (i = head[x]; ~i; i = e[i].nxt) {
    int to = e[i].t;
    if (to == f) {
      continue;
    }
    if (dfn[to] == 0) {
      son++;
      Tarjan(to, x);
      low[x] = min(low[x], low[to]);
      if (low[to] >= dfn[x]) {
        CutV[x] = 1;
        VBC_cnt++;
        int y;
        do {
          y = stk[stk_top--];
          ID[y] = VBC_cnt;
          E[VBC_cnt].push_back(y);
          E[y].push_back(VBC_cnt);
        } while (to != y);
        ID[x] = VBC_cnt;
        E[VBC_cnt].push_back(x);
        E[x].push_back(VBC_cnt);
      }
    } else {
      low[x] = min(low[x], dfn[to]);
    }
  }
  if (f == 0 && son == 0) {
    CutV[x] = 0;
  }
}
int pre[200010];
multiset<int> G[200010];
struct Segment_Tree {
  int Mn[200010 << 2];
  inline void Up(int p) { Mn[p] = min(Mn[(p << 1)], Mn[(p << 1 | 1)]); }
  void build(int l, int r, int p) {
    if (l == r) {
      Mn[p] = *G[pre[l]].begin();
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, (p << 1));
    build(mid + 1, r, (p << 1 | 1));
    Up(p);
  }
  void Update(int l, int r, int p, int x) {
    if (l == r) {
      Mn[p] = *G[pre[x]].begin();
      return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
      Update(l, mid, (p << 1), x);
    } else {
      Update(mid + 1, r, (p << 1 | 1), x);
    }
    Up(p);
  }
  int Query(int l, int r, int p, int pl, int pr) {
    if (l == pl && r == pr) {
      return Mn[p];
    }
    int mid = (l + r) >> 1;
    if (pr <= mid) {
      return Query(l, mid, (p << 1), pl, pr);
    } else if (pl > mid) {
      return Query(mid + 1, r, (p << 1 | 1), pl, pr);
    } else {
      return min(Query(l, mid, (p << 1), pl, mid),
                 Query(mid + 1, r, (p << 1 | 1), mid + 1, pr));
    }
  }
} T;
int A[100010], fa[200010], dep[200010], siz[200010], son[200010], Top[200010],
    Tid[200010], dfs_cnt;
void dfs_pre(int x, int f) {
  fa[x] = f;
  dep[x] = dep[f] + 1;
  siz[x] = 1;
  int i;
  for (i = 0; i < (int)E[x].size(); i++) {
    int to = E[x][i];
    if (to == f) {
      continue;
    }
    dfs_pre(to, x);
    siz[x] += siz[to];
    if (siz[to] > siz[son[x]]) {
      son[x] = to;
    }
  }
}
void dfs_top(int x, int tp) {
  Tid[x] = ++dfs_cnt;
  pre[dfs_cnt] = x;
  Top[x] = tp;
  if (son[x] > 0) {
    dfs_top(son[x], tp);
  }
  int i;
  for (i = 0; i < (int)E[x].size(); i++) {
    int to = E[x][i];
    if (to == fa[x] || to == son[x]) {
      continue;
    }
    dfs_top(to, to);
  }
}
void Change(int x, int y, int z) {
  int tmp = *G[x].begin();
  G[x].erase(G[x].find(y));
  G[x].insert(z);
  if (tmp != *G[x].begin()) {
    T.Update(1, VBC_cnt, 1, Tid[x]);
  }
}
int Query(int x, int y) {
  int res = (0x3f3f3f3f);
  while (Top[x] != Top[y]) {
    if (dep[Top[x]] < dep[Top[y]]) {
      swap(x, y);
    }
    res = min(res, T.Query(1, VBC_cnt, 1, Tid[Top[x]], Tid[x]));
    x = fa[Top[x]];
  }
  if (dep[x] < dep[y]) {
    swap(x, y);
  }
  res = min(res, T.Query(1, VBC_cnt, 1, Tid[y], Tid[x]));
  if (fa[y] > 0 && CutV[fa[y]]) {
    res = min(res, *G[fa[y]].begin());
  }
  return res;
}
using namespace Input;
using namespace Output;
int main() {
  int n, m, q, i;
  rd(n), rd(m), rd(q);
  memset(head + 1, -1, sizeof(int) * 1 * n);
  VBC_cnt = n;
  for (i = 1; i <= n; i++) {
    rd(A[i]);
  }
  for (i = 1; i <= m; i++) {
    int x, y;
    rd(x), rd(y);
    add_edge(x, y);
    add_edge(y, x);
  }
  Tarjan(1, 0);
  dfs_pre(1, 0);
  dfs_top(1, 1);
  for (i = 1; i <= n; i++) {
    if (CutV[i]) {
      ID[i] = i;
      if (fa[i] > 0) {
        G[fa[i]].insert(A[i]);
      }
    } else {
      G[i].insert((0x3f3f3f3f));
    }
    G[ID[i]].insert(A[i]);
  }
  T.build(1, VBC_cnt, 1);
  for (i = 1; i <= q; i++) {
    char op[5];
    int x, y;
    rd(op), rd(x), rd(y);
    if (op[0] == 'C') {
      Change(ID[x], A[x], y);
      if (CutV[x] && fa[x] > 0) {
        Change(fa[x], A[x], y);
      }
      A[x] = y;
    } else {
      if (x == y) {
        pt(A[x]);
      } else {
        pt(Query(ID[x], ID[y]));
      }
    }
  }
  flush();
  return 0;
}