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 MAX = 200010;
int val[MAX];
priority_queue<pair<int, int> > Q[MAX];
namespace BCT {
vector<int> ed[MAX];
bool cut[MAX];
int tot, Time, low[MAX], st[MAX];
vector<int> bcc[MAX];
stack<int> S;
void popBCC(int s, int x) {
  cut[s] = 1;
  bcc[++tot].push_back(s);
  while (bcc[tot].back() ^ x) {
    bcc[tot].push_back(S.top());
    S.pop();
  }
}
void dfs(int s, int p = -1) {
  S.push(s);
  int ch = 0;
  st[s] = low[s] = ++Time;
  for (int x : ed[s]) {
    if (!st[x]) {
      ch++;
      dfs(x, s);
      low[s] = min(low[s], low[x]);
      if (p != -1 && low[x] >= st[s])
        popBCC(s, x);
      else if (p == -1)
        if (ch > 1) popBCC(s, x);
    } else if (p != x)
      low[s] = min(low[s], st[x]);
  }
  if (p == -1 && ch > 1) cut[s] = 1;
}
void processBCC(int n) {
  for (int i = 1; i <= n; i++) bcc[i].clear();
  memset(st, 0, sizeof(st));
  memset(cut, 0, sizeof(cut));
  Time = tot = 0;
  for (int i = 1; i <= n; i++) {
    if (!st[i]) {
      dfs(i, -1);
      if (!S.empty()) ++tot;
      while (!S.empty()) {
        bcc[tot].push_back(S.top());
        S.pop();
      }
    }
  }
}
int nn;
vector<int> tree[MAX];
int compNum[MAX];
void buildTree(int n) {
  processBCC(n);
  nn = tot;
  for (int i = 1; i <= n; i++)
    if (cut[i]) compNum[i] = ++nn;
  for (int i = 1; i <= tot; i++) {
    for (int v : bcc[i]) {
      if (cut[v]) {
        tree[i].push_back(compNum[v]);
        tree[compNum[v]].push_back(i);
      } else {
        compNum[v] = i;
      }
    }
  }
}
};  // namespace BCT
bool isArt(int nd) {
  if (nd > BCT::tot) return true;
  return false;
}
namespace HLD {
int ptr, ara[MAX], par[MAX];
int sz[MAX], h[MAX], pos[MAX], head[MAX], base[MAX];
struct SegmentTree {
  struct node {
    int mn;
  } tree[4 * MAX];
  node Merge(node a, node b) {
    node ret;
    ret.mn = min(a.mn, b.mn);
    return ret;
  }
  void build(int n, int st, int ed) {
    if (st == ed) {
      tree[n].mn = ara[base[st]];
      return;
    }
    int mid = (st + ed) / 2;
    build(2 * n, st, mid);
    build(2 * n + 1, mid + 1, ed);
    tree[n] = Merge(tree[2 * n], tree[2 * n + 1]);
  }
  void update(int n, int st, int ed, int id, int v) {
    if (id > ed || id < st) return;
    if (st == ed && ed == id) {
      tree[n].mn = v;
      return;
    }
    int mid = (st + ed) / 2;
    update(2 * n, st, mid, id, v);
    update(2 * n + 1, mid + 1, ed, id, v);
    tree[n] = Merge(tree[2 * n], tree[2 * n + 1]);
  }
  node query(int n, int st, int ed, int i, int j) {
    if (st >= i && ed <= j) return tree[n];
    int mid = (st + ed) / 2;
    if (mid < i)
      return query(2 * n + 1, mid + 1, ed, i, j);
    else if (mid >= j)
      return query(2 * n, st, mid, i, j);
    else
      return Merge(query(2 * n, st, mid, i, j),
                   query(2 * n + 1, mid + 1, ed, i, j));
  }
} st;
void dfs(int u, int far) {
  sz[u] = 1, h[u] = far;
  for (int v : BCT::tree[u])
    BCT::tree[v].erase(find(BCT::tree[v].begin(), BCT::tree[v].end(), u));
  for (int &v : BCT::tree[u]) {
    par[v] = u;
    dfs(v, far + 1);
    sz[u] += sz[v];
    if (sz[v] > sz[BCT::tree[u][0]]) swap(v, BCT::tree[u][0]);
  }
}
void hld(int u) {
  pos[u] = ++ptr;
  base[ptr] = u;
  for (int v : BCT::tree[u]) {
    head[v] = (v == BCT::tree[u][0] ? head[u] : v);
    hld(v);
  }
}
inline int query(int n, int u, int v) {
  int res = 2000000000;
  while (head[u] != head[v]) {
    if (h[head[u]] > h[head[v]]) swap(u, v);
    res = min(res, st.query(1, 1, n, pos[head[v]], pos[v]).mn);
    v = par[head[v]];
  }
  if (h[u] > h[v]) swap(u, v);
  res = min(res, st.query(1, 1, n, pos[u], pos[v]).mn);
  if (!isArt(u) and par[u]) res = min(res, -Q[par[u]].top().first);
  return res;
}
inline void update(int n, int u, int v) {
  ara[u] = v;
  st.update(1, 1, n, pos[u], v);
}
void build(int n, int root, int x) {
  h[root] = 0, head[root] = root, ptr = 0;
  dfs(root, 0);
  hld(root);
  for (int i = 1; i <= x; i++) {
    Q[BCT::compNum[i]].push({-val[i], i});
    if (BCT::cut[i]) {
      if (par[BCT::compNum[i]]) {
        Q[par[BCT::compNum[i]]].push({-val[i], i});
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    ara[i] = -Q[i].top().first;
  }
  st.build(1, 1, n);
}
};  // namespace HLD
void update(int id) {
  while (true) {
    pair<int, int> c = Q[id].top();
    if (val[c.second] == -c.first) {
      HLD::update(BCT::nn, id, -c.first);
      return;
    } else
      Q[id].pop();
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q, a, b;
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) cin >> val[i];
  for (int i = 1; i <= m; i++) {
    cin >> a >> b;
    BCT::ed[a].push_back(b);
    BCT::ed[b].push_back(a);
  }
  BCT::buildTree(n);
  HLD::build(BCT::nn, 1, n);
  string cmd;
  for (int i = 1; i <= q; i++) {
    cin >> cmd >> a >> b;
    if (cmd == "A") {
      if (a == b)
        cout << val[a] << "\n";
      else
        cout << HLD::query(BCT::nn, BCT::compNum[a], BCT::compNum[b]) << "\n";
    } else {
      val[a] = b;
      Q[BCT::compNum[a]].push({-b, a});
      update(BCT::compNum[a]);
      if (BCT::cut[a]) {
        int p = HLD::par[BCT::compNum[a]];
        if (p) {
          Q[p].push({-b, a});
          update(p);
        }
      }
    }
  }
  return 0;
}