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 i64 = long long;
constexpr int inf = 1e9;
struct SegmentTree {
  int n;
  std::vector<int> info;
  SegmentTree(int n) : n(n), info(4 * n) {}
  void pull(int p) { info[p] = std::min(info[2 * p], info[2 * p + 1]); }
  void modify(int p, int l, int r, int x, int v) {
    if (r - l == 1) {
      info[p] = v;
      return;
    }
    int m = (l + r) / 2;
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int x, int v) { modify(1, 0, n, x, v); }
  int rangeMin(int p, int l, int r, int x, int y) {
    if (l >= y || r <= x) {
      return inf;
    }
    if (l >= x && r <= y) {
      return info[p];
    }
    int m = (l + r) / 2;
    return std::min(rangeMin(2 * p, l, m, x, y),
                    rangeMin(2 * p + 1, m, r, x, y));
  }
  int rangeMin(int l, int r) { return rangeMin(1, 0, n, l, r); }
};
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<int> w(n);
  for (int i = 0; i < n; i++) {
    std::cin >> w[i];
  }
  std::vector<std::vector<int>> e(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    std::cin >> u >> v;
    u--;
    v--;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  int cnt = 0;
  std::vector<std::vector<int>> e1(n);
  std::vector<int> dfn(n, -1), low(n);
  int timeStamp = 0;
  std::vector<int> stk;
  std::function<void(int)> tarjan = [&](int u) {
    dfn[u] = low[u] = timeStamp++;
    stk.push_back(u);
    for (auto v : e[u]) {
      if (dfn[v] == -1) {
        tarjan(v);
        low[u] = std::min(low[u], low[v]);
        if (low[v] == dfn[u]) {
          int x;
          e1.push_back({});
          do {
            x = stk.back();
            stk.pop_back();
            e1[n + cnt].push_back(x);
          } while (x != v);
          e1[u].push_back(n + cnt);
          cnt++;
        }
      } else {
        low[u] = std::min(low[u], dfn[v]);
      }
    }
  };
  tarjan(0);
  e = std::move(e1);
  std::vector<std::multiset<int>> s(cnt);
  int N = n + cnt;
  std::vector<int> in(N), dep(N), top(N), siz(N), parent(N);
  parent[0] = -1;
  std::function<void(int)> dfs1 = [&](int u) {
    siz[u] = 1;
    for (auto &v : e[u]) {
      dep[v] = dep[u] + 1;
      parent[v] = u;
      dfs1(v);
      siz[u] += siz[v];
      if (siz[v] > siz[e[u][0]]) {
        std::swap(v, e[u][0]);
      }
    }
  };
  timeStamp = 0;
  dfs1(0);
  std::function<void(int)> dfs2 = [&](int u) {
    in[u] = timeStamp++;
    for (auto v : e[u]) {
      top[v] = v == e[u][0] ? top[u] : v;
      dfs2(v);
    }
  };
  dfs2(0);
  for (int i = 1; i < n; i++) {
    s[parent[i] - n].insert(w[i]);
  }
  SegmentTree t(N);
  for (int i = 0; i < n; i++) {
    t.modify(in[i], w[i]);
  }
  for (int i = 0; i < cnt; i++) {
    t.modify(in[n + i], *s[i].begin());
  }
  auto pathMin = [&](int u, int v) {
    int ans = inf;
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) {
        std::swap(u, v);
      }
      ans = std::min(ans, t.rangeMin(in[top[u]], in[u] + 1));
      u = parent[top[u]];
    }
    if (dep[u] > dep[v]) {
      std::swap(u, v);
    }
    ans = std::min(ans, t.rangeMin(in[u], in[v] + 1));
    return ans;
  };
  auto lca = [&](int u, int v) {
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) {
        std::swap(u, v);
      }
      u = parent[top[u]];
    }
    if (dep[u] > dep[v]) {
      std::swap(u, v);
    }
    return u;
  };
  while (q--) {
    char op;
    int x, y;
    std::cin >> op >> x >> y;
    if (op == 'A') {
      x--;
      y--;
      int ans = pathMin(x, y);
      int l = lca(x, y);
      if (l >= n) {
        ans = std::min(ans, w[parent[l]]);
      }
      std::cout << ans << "\n";
    } else {
      x--;
      if (x != 0) {
        int p = parent[x] - n;
        s[p].erase(s[p].find(w[x]));
        s[p].insert(y);
        t.modify(in[p + n], *s[p].begin());
      }
      w[x] = y;
      t.modify(in[x], y);
    }
  }
  return 0;
}