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;
const int INF = 1e9 + 7;
int W[200007], dep[200007], low[200007], bcc_id[200007], cut_id[200007];
int n, cnt, bcc_cnt;
vector<int> G[200007], bcc[200007], tree[200007];
bool vis[200007], cut[200007];
stack<int> st;
int w_tree[200007];
multiset<int> bcc_w[200007];
void tarjan(int x, int p) {
  vis[x] = true;
  dep[x] = low[x] = dep[p] + 1;
  st.push(x);
  int child_cnt = 0;
  for (int i : G[x]) {
    if (i != p) {
      if (vis[i])
        low[x] = min(low[x], dep[i]);
      else {
        child_cnt++;
        tarjan(i, x);
        low[x] = min(low[x], low[i]);
        if (low[i] >= dep[x]) {
          cut[x] = true;
          bcc[++cnt].push_back(x);
          bcc_id[x] = cnt;
          int k;
          do {
            k = st.top();
            bcc[cnt].push_back(k);
            if (!cut[k]) {
              bcc_id[k] = cnt;
              bcc_w[cnt].insert(W[k]);
            }
            st.pop();
          } while (k != i);
        }
      }
    }
  }
  if (p == 0 && child_cnt == 1) {
    cut[x] = false;
    bcc_w[bcc_id[x]].insert(W[x]);
  }
  bcc_cnt = cnt;
}
void build_tree() {
  for (int i = 1; i <= n; i++) {
    if (cut[i]) {
      cut_id[i] = ++cnt;
      w_tree[cnt] = W[i];
    }
  }
  for (int i = 1; i <= bcc_cnt; i++) {
    for (int j : bcc[i]) {
      if (cut[j]) {
        tree[cut_id[j]].push_back(i);
        tree[i].push_back(cut_id[j]);
      }
    }
  }
}
int pr[200007], sz[200007], to[200007], hld_id[200007], head[200007];
int hld_cnt;
void dfs(int x, int p) {
  pr[x] = p;
  sz[x] = 1;
  dep[x] = dep[p] + 1;
  for (int i : tree[x]) {
    if (i != p) {
      dfs(i, x);
      sz[x] += sz[i];
      if (sz[i] > sz[to[x]]) to[x] = i;
    }
  }
}
void link(int x, int h) {
  head[x] = h;
  hld_id[x] = ++hld_cnt;
  if (to[x] > 0) link(to[x], h);
  for (int i : tree[x]) {
    if (i != pr[x] && i != to[x]) link(i, i);
  }
}
int seg_tree[800007];
void modify(int id, int l, int r, int pos, int val) {
  if (l == r) {
    seg_tree[id] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(id * 2, l, mid, pos, val);
  else
    modify(id * 2 + 1, mid + 1, r, pos, val);
  seg_tree[id] = min(seg_tree[id * 2], seg_tree[id * 2 + 1]);
}
int query(int id, int l, int r, int ql, int qr) {
  if (ql > r || qr < l) return INF;
  if (ql <= l && r <= qr) return seg_tree[id];
  int mid = (l + r) >> 1;
  return min(query(id * 2, l, mid, ql, qr),
             query(id * 2 + 1, mid + 1, r, ql, qr));
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int m, q;
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) cin >> W[i];
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  tarjan(1, 0);
  build_tree();
  dfs(1, 0);
  link(1, 1);
  for (int i = 1; i <= n; i++) {
    if (cut[i]) {
      bcc_id[i] = pr[cut_id[i]];
      bcc_w[bcc_id[i]].insert(W[i]);
    }
  }
  for (int i = 1; i <= bcc_cnt; i++) w_tree[i] = *(bcc_w[i].begin());
  for (int i = 1; i <= cnt; i++) modify(1, 1, cnt, hld_id[i], w_tree[i]);
  while (q--) {
    char c;
    cin >> c;
    if (c == 'C') {
      int a, w;
      cin >> a >> w;
      bcc_w[bcc_id[a]].erase(bcc_w[bcc_id[a]].find(W[a]));
      W[a] = w;
      bcc_w[bcc_id[a]].insert(w);
      w_tree[bcc_id[a]] = *(bcc_w[bcc_id[a]].begin());
      modify(1, 1, cnt, hld_id[bcc_id[a]], w_tree[bcc_id[a]]);
      if (cut[a]) {
        w_tree[cut_id[a]] = w;
        modify(1, 1, cnt, hld_id[cut_id[a]], w);
      }
    } else {
      int a, b;
      cin >> a >> b;
      if (a == b) {
        cout << W[a] << '\n';
        continue;
      }
      int mn = INF;
      int u, v;
      u = cut[a] ? cut_id[a] : bcc_id[a];
      v = cut[b] ? cut_id[b] : bcc_id[b];
      while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        mn = min(mn, query(1, 1, cnt, hld_id[head[u]], hld_id[u]));
        u = pr[head[u]];
      }
      if (dep[u] > dep[v]) swap(u, v);
      mn = min(mn, query(1, 1, cnt, hld_id[u], hld_id[v]));
      if (u <= bcc_cnt && pr[u] != 0) mn = min(mn, w_tree[pr[u]]);
      cout << mn << '\n';
    }
  }
}