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>
template <class T>
inline void chkmin(T &x, T y) {
  if (x > y) x = y;
}
template <class T>
inline void chkmax(T &x, T y) {
  if (x < y) x = y;
}
template <class T>
inline void read(T &x) {
  char c;
  int f = 1;
  x = 0;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  if (c == '-')
    f = -1;
  else
    x = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
  x *= f;
}
int outn;
char out[10000000];
template <class T>
inline void write(T x) {
  if (x < 0) out[outn++] = '-', x = -x;
  if (x) {
    int tmpn = 0;
    char tmp[20] = {0};
    while (x) tmp[tmpn++] = x % 10 + '0', x /= 10;
    while (tmpn) out[outn++] = tmp[--tmpn];
  } else
    out[outn++] = '0';
}
const int N = 2e5, M = 2 * N;
const int INF = 1e9;
int n, m, qn;
std::multiset<int> w[N + 9];
struct graph {
  int sz, head[N + 9], to[M + 9], ne[M + 9];
  graph() { sz = 1, memset(head, 0, sizeof head); }
  inline void addedge(int u, int v) {
    to[sz] = v, ne[sz] = head[u], head[u] = sz++;
    to[sz] = u, ne[sz] = head[v], head[v] = sz++;
  }
} g, tr;
int dfn[N + 9], low[N + 9], tot;
int st[N + 9], sttop;
int bel[N + 9], bccn;
int sz[N + 9];
int hvy[N + 9];
int fa[N + 9];
int dep[N + 9];
int top[N + 9];
int arr[N + 9];
int loc[N + 9];
int min[N * 4 + 9];
void tarjan(int x, int fa) {
  st[++sttop] = x, dfn[x] = low[x] = ++tot;
  for (int i = g.head[x], y; i; i = g.ne[i])
    if (!dfn[y = g.to[i]]) {
      tarjan(y, x);
      chkmin(low[x], low[y]);
      if (low[y] == dfn[x]) {
        ++bccn;
        while (st[sttop] != x) {
          int t = st[sttop--];
          bel[t] = bccn + n;
          w[bccn + n].insert(*w[t].begin());
          tr.addedge(t, bccn + n);
          if (t == y) break;
        }
        tr.addedge(x, bccn + n);
      }
    } else
      chkmin(low[x], dfn[y]);
}
void dfs1(int x, int fa) {
  sz[x] = 1;
  for (int i = tr.head[x], y; i; i = tr.ne[i])
    if ((y = tr.to[i]) != fa) {
      dfs1(y, x);
      sz[x] += sz[y];
      if (!hvy[x] || sz[hvy[x]] < sz[y]) hvy[x] = y;
    }
}
void dfs2(int x, int fa) {
  ::fa[x] = fa, dep[x] = dep[fa] + 1;
  arr[++tot] = x, loc[x] = tot;
  if (hvy[x]) {
    top[hvy[x]] = top[x];
    dfs2(hvy[x], x);
  }
  for (int i = tr.head[x], y; i; i = tr.ne[i])
    if ((y = tr.to[i]) != fa && y != hvy[x]) top[y] = y, dfs2(y, x);
}
inline void pushup(int x) { min[x] = std::min(min[x << 1], min[x << 1 | 1]); }
void maketree(int x, int l, int r) {
  if (l == r) {
    min[x] = *w[arr[l]].begin();
    return;
  }
  int mid = (l + r) >> 1;
  maketree(x << 1, l, mid);
  maketree(x << 1 | 1, mid + 1, r);
  pushup(x);
}
inline void build() {
  dfs1(1, 0);
  tot = 0, top[1] = 1;
  dfs2(1, 0);
  maketree(1, 1, tot);
}
void mdf(int x, int l, int r, int p) {
  if (l == r) {
    min[x] = *w[arr[l]].begin();
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    mdf(x << 1, l, mid, p);
  else
    mdf(x << 1 | 1, mid + 1, r, p);
  pushup(x);
}
inline void mdf(int x, int y) {
  int v = *w[x].begin();
  w[x].erase(w[x].begin()), w[x].insert(y);
  mdf(1, 1, tot, loc[x]);
  if (bel[x]) {
    w[bel[x]].erase(w[bel[x]].find(v));
    w[bel[x]].insert(y);
    mdf(1, 1, tot, loc[bel[x]]);
  }
}
int qry(int x, int l, int r, int tl, int tr) {
  if (l == tl && r == tr) return min[x];
  int mid = (l + r) >> 1;
  if (tr <= mid)
    return qry(x << 1, l, mid, tl, tr);
  else if (tl > mid)
    return qry(x << 1 | 1, mid + 1, r, tl, tr);
  else
    return std::min(qry(x << 1, l, mid, tl, mid),
                    qry(x << 1 | 1, mid + 1, r, mid + 1, tr));
}
inline int qry(int x, int y) {
  int ret = INF;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
    chkmin(ret, qry(1, 1, tot, loc[top[x]], loc[x]));
    x = fa[top[x]];
  }
  if (dep[x] < dep[y]) std::swap(x, y);
  chkmin(ret, qry(1, 1, tot, loc[y], loc[x]));
  if (y > n) chkmin(ret, *w[fa[y]].begin());
  return ret;
}
int main() {
  read(n), read(m), read(qn);
  for (int i = 1; i <= n; ++i) {
    int x;
    read(x);
    w[i].insert(x);
  }
  for (int i = 1; i <= m; ++i) {
    int u, v;
    read(u), read(v);
    g.addedge(u, v);
  }
  tarjan(1, 0);
  build();
  while (qn--) {
    char s[3];
    int x, y;
    scanf("%s", s), read(x), read(y);
    if (s[0] == 'A')
      write(qry(x, y)), out[outn++] = '\n';
    else
      mdf(x, y);
  }
  puts(out);
  return 0;
}