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;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline string get() {
  char ch[1000010];
  scanf("%s", ch);
  return ch;
}
const int MAX_LG = 60;
const long long maxn = 2e5 + 100;
const long long maxm = 1e4 + 100;
const long long base = 29;
const long long mod = 1e9 + 7;
const long long INF = 2e9 + 100;
long long n, m, q, h[maxn], l[maxn], init[maxn], pre[maxn], heavy[maxn],
    sz[maxn], tree_pos[maxn], head[maxn], stree[4 * maxn];
vector<long long> g[maxn], adj[maxn], cmp[maxn];
bool mark[maxn];
stack<long long> st;
multiset<long long> items[maxn];
inline void tarjan(long long v, long long pr = -1) {
  mark[v] = true;
  h[v] = (pr == -1 ? 0 : h[pr] + 1);
  l[v] = h[v];
  st.push(v);
  for (auto u : g[v]) {
    if (mark[u])
      l[v] = min(l[v], h[u]);
    else {
      tarjan(u, v);
      l[v] = min(l[v], l[u]);
    }
  }
  if (h[v] - 1 == l[v]) {
    long long x;
    do {
      x = st.top();
      st.pop();
      cmp[x].push_back(v + n);
    } while (x != v);
    cmp[pr].push_back(v + n);
  }
}
inline void dfs(long long v, long long pr = -1) {
  pre[v] = pr;
  h[v] = (pr == -1 ? 0 : h[pr] + 1);
  sz[v] = 1;
  long long maxi = -1;
  for (auto u : adj[v]) {
    if (u == pr) continue;
    dfs(u, v);
    sz[v] += sz[u];
    if (sz[u] > maxi) maxi = sz[u], heavy[v] = u;
  }
}
long long cur = 1;
inline void decompose() {
  memset(h, 0, (2 * n + 5) * sizeof h[0]);
  memset(pre, -1, (2 * n + 5) * sizeof pre[0]);
  memset(heavy, -1, (2 * n + 5) * sizeof heavy[0]);
  dfs(1);
  for (long long i = 1; i <= 2 * n; i++) {
    if (!adj[i].size()) continue;
    if (!(pre[i] == -1 || heavy[pre[i]] != i)) continue;
    for (long long u = i; u != -1; u = heavy[u])
      tree_pos[u] = cur++, head[u] = i;
  }
}
inline void update(long long x, long long val, long long p = 0, long long l = 1,
                   long long r = 2 * n) {
  if (l > x || r < x) return;
  if (l == r) {
    stree[p] = val;
    return;
  }
  long long mid = (l + r) >> 1;
  update(x, val, 2 * p + 1, l, mid);
  update(x, val, 2 * p + 2, mid + 1, r);
  stree[p] = min(stree[2 * p + 1], stree[2 * p + 2]);
}
inline void change(long long node, long long preVal, long long val) {
  if (node == -1) return;
  if (preVal + 1) items[node].erase(items[node].find(preVal));
  items[node].insert(val);
  long long vl = *items[node].begin();
  update(tree_pos[node], vl);
}
inline long long get(long long ql, long long qr, long long p = 0,
                     long long l = 1, long long r = 2 * n) {
  if (l > qr || r < ql) return INF;
  if (l >= ql && r <= qr) return stree[p];
  long long mid = (l + r) >> 1;
  return min(get(ql, qr, 2 * p + 1, l, mid),
             get(ql, qr, 2 * p + 2, mid + 1, r));
}
inline long long get_mini(long long v, long long u) {
  long long ret = INF;
  while (head[v] != head[u]) {
    if (h[head[u]] > h[head[v]]) swap(v, u);
    ret = min(ret, get(tree_pos[head[v]], tree_pos[v]));
    v = pre[head[v]];
  }
  if (h[u] > h[v]) swap(v, u);
  ret = min(ret, get(tree_pos[u], tree_pos[v]));
  if (u > n && pre[u] != -1) ret = min(ret, *items[pre[u]].begin());
  return ret;
}
int32_t main() {
  fill(stree, stree + 4 * maxn, INF);
  n = in(), m = in(), q = in();
  for (long long i = 1; i <= n; i++) init[i] = in();
  for (long long i = 0; i < m; i++) {
    long long v = in(), u = in();
    g[v].push_back(u);
    g[u].push_back(v);
  }
  tarjan(1);
  for (long long i = 1; i <= n; i++) {
    for (auto u : cmp[i]) {
      adj[i].push_back(u);
      adj[u].push_back(i);
    }
  }
  decompose();
  for (long long i = 1; i <= n; i++) {
    change(i, -1, init[i]);
    change(pre[i], -1, init[i]);
  }
  while (q--) {
    char tp = 0;
    do {
      tp = getchar();
    } while (tp != 'C' && tp != 'A');
    if (tp == 'C') {
      long long v = in(), vl = in();
      change(v, init[v], vl);
      change(pre[v], init[v], vl);
      init[v] = vl;
    } else {
      long long v = in(), u = in();
      printf("%d\n", get_mini(v, u));
    }
  }
}