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;
template <typename _T>
inline void _prt(_T _d) {
  cerr << _d << ' ';
}
template <typename _T, typename... Args>
inline void _prt(_T _d, Args... _a) {
  _prt(_d), _prt(_a...);
}
template <typename _T, typename... Args>
inline void prt(_T _d, Args... _a) {
  _prt(_d), _prt(_a...), cerr << '\n';
}
template <typename _T, typename... Args>
inline void prt(_T _d) {
  cerr << _d << '\n';
}
template <typename _T>
inline void rd(_T &_d) {
  signed _f;
  char _c;
  _f = 1, _d = 0;
  while (_c = getchar(), !isdigit(_c))
    if (_c == '-') _f = -1;
  while (isdigit(_c)) _d = _d * 10 + _c - '0', _c = getchar();
  _d = _f * _d;
}
template <typename _T, typename... Args>
inline void rd(_T &_d, Args &..._a) {
  rd(_d);
  rd(_a...);
}
const int N = 2e5 + 5;
int cnt, rnk[N], m, a[N], n, q, tot = 0, hd[N * 2], ver[N * 2], nxt[N * 2],
                                cut[N], ntot;
int c[N / 2];
vector<int> v[N];
multiset<int> s[N / 2];
void add_e(int u, int v) {
  nxt[++tot] = hd[u], hd[u] = tot, ver[tot] = v;
  nxt[++tot] = hd[v], hd[v] = tot, ver[tot] = u;
}
struct segtree {
  int l, r, mn, add;
} seg[4 * N];
struct node {
  int sz = 1, dep, fa, hson, dfn, bot, top;
} t[N];
void build(int l, int r, int p) {
  seg[p].l = l, seg[p].r = r;
  if (l == r) {
    if (rnk[l] > n)
      seg[p].mn = *s[rnk[l] - n].begin();
    else
      seg[p].mn = 1e9;
    return;
  }
  build(l, (l + r) / 2, p * 2), build((l + r) / 2 + 1, r, p * 2 + 1);
  seg[p].mn = min(seg[p * 2].mn, seg[p * 2 + 1].mn);
}
int que(int l, int r, int p) {
  if (seg[p].l >= l && seg[p].r <= r) return seg[p].mn;
  int ans = 1e9, mid = (seg[p].l + seg[p].r) / 2;
  if (l <= mid) ans = min(ans, que(l, r, p * 2));
  if (r > mid) ans = min(ans, que(l, r, p * 2 + 1));
  return ans;
}
void change(int p, int pos) {
  if (seg[p].l == seg[p].r) {
    seg[p].mn = *s[rnk[pos] - n].begin();
    return;
  }
  int mid = (seg[p].l + seg[p].r) / 2;
  if (pos <= mid)
    change(p * 2, pos);
  else
    change(p * 2 + 1, pos);
  seg[p].mn = min(seg[p * 2].mn, seg[p * 2 + 1].mn);
}
void dfs1(int x, int fa) {
  int y, mx = 0;
  t[x].dep = t[fa].dep + 1, t[x].fa = fa, t[x].sz = 1;
  for (int i = hd[x]; i; i = nxt[i]) {
    if ((y = ver[i]) == fa) continue;
    dfs1(y, x);
    if (t[y].sz > mx) mx = t[y].sz, t[x].hson = y;
    t[x].sz += t[y].sz;
  }
}
void dfs2(int x, int fa, int top) {
  int y;
  t[x].top = top, t[x].dfn = ++cnt, rnk[cnt] = x, t[x].bot = t[x].dfn;
  if (!t[x].hson) return;
  dfs2(t[x].hson, x, top), t[x].bot = max(t[x].bot, t[t[x].hson].bot);
  for (int i = hd[x]; i; i = nxt[i]) {
    if ((y = ver[i]) == fa || y == t[x].hson) continue;
    dfs2(y, x, y), t[x].bot = max(t[x].bot, t[y].bot);
  }
}
int list_que(int x, int y) {
  int ans = 1e9;
  while (t[x].top != t[y].top) {
    if (t[t[x].top].dep < t[t[y].top].dep) swap(x, y);
    ans = min(ans, que(t[t[x].top].dfn, t[x].dfn, 1));
    x = t[t[x].top].fa;
  }
  if (t[x].dep > t[y].dep) swap(x, y);
  ans = min(ans, que(t[x].dfn, t[y].dfn, 1));
  if (t[x].fa <= n && t[x].fa) ans = min(ans, a[t[x].fa]);
  if (x <= n) ans = min(ans, a[x]);
  return ans;
}
struct {
  stack<int> s;
  int low[N], dfn[N], cnt;
  void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    s.push(x);
    int count = 0, y;
    for (int y : v[x]) {
      if (!dfn[y]) {
        tarjan(y), low[x] = min(low[y], low[x]);
        if (low[y] >= dfn[x]) {
          ++ntot;
          while (s.top() != y) add_e(ntot, s.top()), s.pop();
          s.pop(), add_e(ntot, x), add_e(ntot, y);
          if (x != 1 || count != 0) cut[x] = 1;
          ++count;
        }
      } else
        low[x] = min(low[x], dfn[y]);
    }
  }
} tar;
void Add() {
  int x, y;
  for (signed i = (signed)(1); i <= (signed)(m); ++i)
    rd(x, y), v[x].push_back(y), v[y].push_back(x);
}
int main() {
  int u, v;
  rd(n, m, q);
  for (signed i = (signed)(1); i <= (signed)(n); ++i) rd(a[i]);
  Add();
  ntot = n;
  tar.tarjan(1);
  dfs1(1, 0);
  dfs2(1, 0, 1);
  for (signed i = (signed)(1); i <= (signed)(n); ++i)
    if (t[i].fa > n) s[t[i].fa - n].insert(a[i]);
  build(1, ntot, 1);
  int l, r;
  char opt;
  while (q--) {
    scanf(" %c%d%d", &opt, &l, &r);
    if (opt == 'A')
      printf("%d\n", l == r ? a[l] : list_que(l, r));
    else {
      if (l == 1) {
        a[l] = r;
        continue;
      }
      s[t[l].fa - n].erase(s[t[l].fa - n].find(a[l])),
          a[l] = r, s[t[l].fa - n].insert(a[l]);
      change(1, t[t[l].fa].dfn);
    }
  }
  return 0;
}