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>
const int ri_top = 1e7;
char ri[ri_top], *rich = ri;
void read_int(int& x) {
  while (!isdigit(*rich)) ++rich;
  for (x = *rich - '0'; isdigit(*++rich); x = x * 10 + *rich - '0')
    ;
}
void read_ch(char& ch) {
  while (isspace(*rich)) ++rich;
  ch = *rich++;
}
const int maxn = 100001 << 1;
const int maxm = maxn << 1;
inline void smin(int& x, const int& y) {
  if (y < x) x = y;
}
int tr[maxn << 3], N;
void set(int x, int y) {
  tr[x + N] = y;
  for (register int i = (x + N) >> 1; i; i >>= 1)
    tr[i] = std::min(tr[i << 1], tr[i << 1 | 1]);
}
void sum(int x, int y, int& s) {
  for (register int i = x + N - 1, j = y + N + 1; i ^ j ^ 1; i >>= 1, j >>= 1) {
    if (~i & 1) smin(s, tr[i ^ 1]);
    if (j & 1) smin(s, tr[j ^ 1]);
  }
}
int n, m, q, val[maxn], u, v;
int h[maxn], to[maxm], nxt[maxm], cnt = 1;
int h1[maxn], to1[maxm], nxt1[maxm], cnt1 = 1;
void add_edge(int u, int v) {
  to[++cnt] = v;
  nxt[cnt] = h[u];
  h[u] = cnt;
}
void add_edge1(int u, int v) {
  to1[++cnt1] = v;
  nxt1[cnt1] = h1[u];
  h1[u] = cnt1;
}
std::multiset<int> mm[maxn];
int dfn[maxn], low[maxn], bcc, sk[maxn], top;
void tarjan(int u) {
  dfn[u] = ++dfn[0];
  low[u] = dfn[u];
  sk[++top] = u;
  for (register int i = h1[u]; i; i = nxt1[i])
    if (!dfn[to1[i]]) {
      tarjan(to1[i]);
      smin(low[u], low[to1[i]]);
      if (low[to1[i]] >= dfn[u]) {
        ++bcc;
        val[bcc] = 0x7fffffff;
        do {
          add_edge(bcc, sk[top]);
          mm[bcc].insert(val[sk[top]]);
          smin(val[bcc], val[sk[top]]);
        } while (sk[top--] != to1[i]);
        add_edge(u, bcc);
      }
    } else
      smin(low[u], dfn[to1[i]]);
}
int sz[maxn], f[maxn], mxs[maxn];
void dfs1(int u) {
  sz[u] = 1;
  for (register int i = h[u]; i; i = nxt[i])
    if (!sz[to[i]]) {
      f[to[i]] = u;
      dfs1(to[i]);
      sz[u] += sz[to[i]];
      if (sz[mxs[u]] < sz[to[i]]) mxs[u] = to[i];
    }
}
int ck, tp[maxn];
void dfs2(int u) {
  dfn[u] = ++ck;
  if (mxs[u]) {
    tp[mxs[u]] = tp[u];
    dfs2(mxs[u]);
  }
  for (register int i = h[u]; i; i = nxt[i])
    if (!tp[to[i]]) {
      tp[to[i]] = to[i];
      dfs2(to[i]);
    }
}
int spsum(int x, int y) {
  int s = 0x7fffffff;
  for (; tp[x] != tp[y]; x = f[tp[x]]) {
    if (dfn[tp[x]] < dfn[tp[y]]) std::swap(x, y);
    sum(dfn[tp[x]], dfn[x], s);
  }
  if (dfn[x] > dfn[y]) std::swap(x, y);
  sum(dfn[x], dfn[y], s);
  if (x > n) smin(s, val[f[x]]);
  return s;
}
int main() {
  fread(ri, 1, ri_top, stdin);
  read_int(n);
  read_int(m);
  read_int(q);
  for (register int(i) = (1); (i) <= (n); ++(i)) read_int(val[i]);
  for (register int(i) = (0); (i) < (m); ++(i)) {
    read_int(u);
    read_int(v);
    add_edge1(u, v);
    add_edge1(v, u);
  }
  bcc = n;
  tarjan(1);
  for (N = 1; N <= bcc + 1; N <<= 1)
    ;
  for (register int i = 1; i <= N * 2; ++i) tr[i] = 0x7fffffff;
  dfs1(1);
  tp[1] = 1;
  dfs2(1);
  for (register int i = 1; i <= bcc; ++i) set(dfn[i], val[i]);
  char opt;
  int x, y;
  for (register int(i) = (0); (i) < (q); ++(i)) {
    read_ch(opt);
    read_int(x);
    read_int(y);
    if (opt == 'C') {
      set(dfn[x], y);
      if (f[x]) {
        mm[f[x]].erase(mm[f[x]].find(val[x]));
        mm[f[x]].insert(y);
        set(dfn[f[x]], val[f[x]] = *mm[f[x]].begin());
      }
      val[x] = y;
    } else
      printf("%d\n", spsum(x, y));
  }
  return 0;
}