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 N = 2e5 + 5;
struct Graph {
  int head[N], nxt[N * 2], v[N * 2], cnt;
  Graph() {
    memset(head, 0, sizeof(head));
    cnt = 1;
  }
  void add(int ux, int vx) {
    nxt[++cnt] = head[ux];
    head[ux] = cnt;
    v[cnt] = vx;
    nxt[++cnt] = head[vx];
    head[vx] = cnt;
    v[cnt] = ux;
  }
} G, Gx;
int n, m, a[N], x, Q, y, w, ax[N], dfx[N];
multiset<int> ms[N];
inline void read(int &v) {
  v = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') {
    v = v * 10 + c - '0', c = getchar();
  }
}
void write(int x) {
  if (x > 9) write(x / 10);
  int xx = x % 10;
  putchar(xx + '0');
}
int dfn[N], low[N], st[N], top = 0, BH = 0, Tx = 0;
void Tarj(int x, int fa) {
  low[x] = dfn[x] = ++Tx;
  st[++top] = x;
  for (register int i = G.head[x]; i; i = G.nxt[i]) {
    int vv = G.v[i];
    if (!dfn[vv]) {
      Tarj(vv, x);
      low[x] = min(low[x], low[vv]);
      if (low[vv] >= dfn[x]) {
        int now = ++BH, lst;
        Gx.add(now, x);
        do {
          lst = st[top--];
          Gx.add(now, lst);
        } while (vv != lst);
      }
    } else if (vv != fa)
      low[x] = min(low[x], dfn[vv]);
  }
}
int siz[N], Xson[N], topF[N], dep[N], ID = 0, fa[N];
void DFS1(int x) {
  siz[x] = 1;
  int mx = 0;
  for (register int i = Gx.head[x]; i; i = Gx.nxt[i]) {
    int vv = Gx.v[i];
    if (vv == fa[x]) continue;
    if (x > n) ms[x].insert(a[vv]);
    fa[vv] = x;
    dep[vv] = dep[x] + 1;
    DFS1(vv);
    siz[x] += siz[vv];
    if (siz[vv] > mx) Xson[x] = vv, mx = siz[vv];
  }
}
void DFS2(int x, int tF) {
  dfx[x] = ++ID;
  if (x <= n)
    ax[ID] = a[x];
  else
    ax[ID] = a[x] = *ms[x].begin();
  topF[x] = tF;
  if (!Xson[x]) return;
  DFS2(Xson[x], tF);
  for (register int i = Gx.head[x]; i; i = Gx.nxt[i]) {
    int vv = Gx.v[i];
    if (vv == fa[x] || vv == Xson[x]) continue;
    DFS2(vv, vv);
  }
}
int Mn[N * 4];
void Build(int o, int l, int r) {
  if (l == r) {
    Mn[o] = ax[l];
    return;
  }
  int m = (l + r) >> 1;
  Build(o << 1, l, m);
  Build(o << 1 | 1, m + 1, r);
  Mn[o] = min(Mn[o << 1], Mn[o << 1 | 1]);
}
void Chg(int o, int l, int r, int px, int dt) {
  if (l == r) {
    Mn[o] = dt;
    return;
  }
  int m = (l + r) >> 1;
  if (px <= m)
    Chg(o << 1, l, m, px, dt);
  else
    Chg(o << 1 | 1, m + 1, r, px, dt);
  Mn[o] = min(Mn[o << 1], Mn[o << 1 | 1]);
}
int Qry(int o, int l, int r, int lx, int rx) {
  if (lx <= l && rx >= r) return Mn[o];
  int m = (l + r) >> 1;
  int t1, t2;
  t1 = t2 = 2147483600;
  if (lx <= m) t1 = Qry(o << 1, l, m, lx, rx);
  if (rx > m) t2 = Qry(o << 1 | 1, m + 1, r, lx, rx);
  return min(t1, t2);
}
int Ask(int x, int y) {
  int ans = 2147483600;
  while (topF[x] != topF[y]) {
    if (dep[topF[x]] < dep[topF[y]]) swap(x, y);
    ans = min(ans, Qry(1, 1, BH, dfx[topF[x]], dfx[x]));
    x = fa[topF[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  ans = min(ans, Qry(1, 1, BH, dfx[x], dfx[y]));
  if (x > n && fa[x]) {
    ans = min(ans, Qry(1, 1, BH, dfx[fa[x]], dfx[fa[x]]));
  }
  return ans;
}
void Change(int x, int w) {
  if (fa[x]) {
    int fx = fa[x];
    ms[fx].erase(ms[fx].find(a[x]));
    a[x] = w;
    ms[fx].insert(a[x]);
    int Nax = *ms[fx].begin();
    if (a[fx] != Nax) Chg(1, 1, BH, dfx[fx], Nax);
    a[fx] = Nax;
  }
  Chg(1, 1, BH, dfx[x], w);
}
int main() {
  read(n);
  read(m);
  read(Q);
  BH = n;
  for (int i = 1; i <= n; ++i) read(a[i]);
  for (int i = 1; i <= m; ++i) {
    read(x);
    read(y);
    G.add(x, y);
  }
  for (int i = 1; i <= n; ++i)
    if (!dfn[i]) Tarj(i, 0);
  DFS1(1);
  DFS2(1, 1);
  Build(1, 1, BH);
  for (int i = 1; i <= Q; ++i) {
    char c = getchar();
    while (c != 'C' && c != 'A') c = getchar();
    if (c == 'C') {
      read(x);
      read(w);
      Change(x, w);
    }
    if (c == 'A') {
      read(x);
      read(y);
      int Fn = Ask(x, y);
      write(Fn);
      putchar('\n');
    }
  }
  return 0;
}