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 N = 2e5 + 10;
inline int read() {
  int r = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = getchar();
  return r;
}
inline char readc() {
  char c = getchar();
  while (c != 'A' && c != 'C') c = getchar();
  return c;
}
struct edge {
  int next, to;
} e[N << 1];
int head[N], sum;
inline void add(int x, int y) {
  e[++sum].next = head[x];
  head[x] = sum;
  e[sum].to = y;
}
int low[N], dfn[N], n, m, q, cnt, ext, st[N], top, val[N];
struct YFS {
  struct edge {
    int next, to;
  } e[N << 1];
  int head[N], sum;
  inline void add(int x, int y) {
    e[++sum].next = head[x];
    head[x] = sum;
    e[sum].to = y;
  }
  int t[N << 2];
  inline void pushup(int now) {
    t[now] = std::min(t[now << 1], t[now << 1 | 1]);
  }
  void update(int now, int l, int r, int pos, int k) {
    if (l == r) return t[now] = k, void();
    int mid = l + r >> 1;
    if (pos <= mid)
      update(now << 1, l, mid, pos, k);
    else
      update(now << 1 | 1, mid + 1, r, pos, k);
    pushup(now);
  }
  int query(int now, int l, int r, int L, int R) {
    if (l >= L && r <= R) return t[now];
    int mid = l + r >> 1, ret = t[0];
    if (L <= mid) ret = query(now << 1, l, mid, L, R);
    if (R > mid) ret = std::min(ret, query(now << 1 | 1, mid + 1, r, L, R));
    return ret;
  }
  int size[N], hson[N], top[N], dep[N], id[N], fa[N], cnt;
  std::multiset<int> st[N];
  void dfs1(int now) {
    size[now] = 1;
    dep[now] = dep[fa[now]] + 1;
    for (int i = head[now]; i; i = e[i].next) {
      int to = e[i].to;
      if (to == fa[now]) continue;
      fa[to] = now;
      dfs1(to);
      size[now] += size[to];
      if (size[to] > size[hson[now]]) hson[now] = to;
      if (now > n) st[now].insert(val[to]);
    }
  }
  void dfs2(int now, int linetop) {
    top[now] = linetop;
    id[now] = ++cnt;
    if (now > n)
      update(1, 1, ext, cnt, *st[now].begin());
    else
      update(1, 1, ext, cnt, val[now]);
    if (!hson[now]) return;
    dfs2(hson[now], linetop);
    for (int i = head[now]; i; i = e[i].next) {
      int to = e[i].to;
      if (to == fa[now] || to == hson[now]) continue;
      dfs2(to, to);
    }
  }
  int Query(int x, int y) {
    int ret = t[0];
    while (top[x] != top[y]) {
      if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
      ret = std::min(ret, query(1, 1, ext, id[top[x]], id[x]));
      x = fa[top[x]];
    }
    if (dep[x] > dep[y]) std::swap(x, y);
    ret = std::min(ret, query(1, 1, ext, id[x], id[y]));
    if (x > n) ret = std::min(ret, val[fa[x]]);
    return ret;
  }
  void Update(int x, int k) {
    if (fa[x]) {
      st[fa[x]].erase(st[fa[x]].find(val[x]));
      val[x] = k;
      update(1, 1, ext, id[x], val[x]);
      st[fa[x]].insert(val[x]);
      update(1, 1, ext, id[fa[x]], *st[fa[x]].begin());
    } else
      val[x] = k, update(1, 1, ext, id[x], val[x]);
  }
  void init() {
    memset(t, 0x3f, sizeof(t));
    ext = n;
  }
} T;
void tarjan(int now) {
  low[now] = dfn[now] = ++cnt;
  st[++top] = now;
  for (int i = head[now]; i; i = e[i].next) {
    int to = e[i].to;
    if (!dfn[to]) {
      tarjan(to);
      low[now] = std::min(low[now], low[to]);
      if (low[to] >= dfn[now]) {
        ++ext;
        while (st[top] != to) {
          T.add(ext, st[top]);
          T.add(st[top], ext);
          --top;
        }
        T.add(ext, to);
        T.add(to, ext);
        --top;
        T.add(ext, now);
        T.add(now, ext);
      }
    } else
      low[now] = std::min(low[now], dfn[to]);
  }
}
int main() {
  n = read();
  m = read();
  q = read();
  for (int i = 1; i <= n; i++) val[i] = read();
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    add(x, y);
    add(y, x);
  }
  T.init();
  tarjan(1);
  T.dfs1(1);
  T.dfs2(1, 1);
  for (int i = 1; i <= q; i++) {
    char inp = readc();
    int x = read(), y = read();
    if (inp == 'A')
      printf("%d\n", T.Query(x, y));
    else
      T.Update(x, y);
  }
  return 0;
}