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>
void read(T& a) {
  static char c;
  static bool b;
  for (c = getchar(), b = false; !isdigit(c); c = getchar())
    if (c == '-') b = true;
  for (a = 0; isdigit(c); c = getchar()) a = a * 10 + (c - '0');
  if (b) a = -a;
}
template <>
void read<char>(char& c) {
  do {
    c = getchar();
  } while (isspace(c));
}
template <typename T, typename... Args>
void read(T& a, Args&... args) {
  read(a);
  read(args...);
}
const int MAXN = 2e5 + 10;
const int MAXM = MAXN;
const int INF = 0x3f3f3f3f;
template <typename T>
struct Segment {
  struct Node {
    int l, r, lc, rc;
    T v;
  } t[MAXN << 2];
  int cnt;
  void maintain(int x) { t[x].v = min(t[t[x].lc].v, t[t[x].rc].v); }
  int create() { return ++cnt; }
  int build(int l, int r, T* origin) {
    int x = create();
    t[x].l = l, t[x].r = r;
    if (l != r) {
      int mid = l + r;
      mid >>= 1;
      t[x].lc = build(l, mid, origin);
      t[x].rc = build(mid + 1, r, origin);
      maintain(x);
    } else
      t[x].v = origin[l];
    return x;
  }
  T query(int x, int l, int r) {
    if (l <= t[x].l && t[x].r <= r) return t[x].v;
    int mid = t[x].l + t[x].r;
    mid >>= 1;
    if (r <= mid)
      return query(t[x].lc, l, r);
    else if (l > mid)
      return query(t[x].rc, l, r);
    return min(query(t[x].lc, l, r), query(t[x].rc, l, r));
  }
  void modify(int x, int l, int v) {
    if (t[x].l == t[x].r) {
      t[x].v = v;
      return;
    }
    int mid = t[x].l + t[x].r;
    mid >>= 1;
    if (l <= mid)
      modify(t[x].lc, l, v);
    else
      modify(t[x].rc, l, v);
    maintain(x);
  }
};
struct BaseGraph {
  struct Lfs {
    int to, nxt;
  } t[MAXM << 1];
  int head[MAXN], cnt;
  void add(int x, int y) {
    ++cnt;
    t[cnt].to = y;
    t[cnt].nxt = head[x];
    head[x] = cnt;
  }
  void add2(int x, int y) { add(x, y), add(y, x); }
};
struct Graph : BaseGraph {
  int dfn[MAXN], low[MAXN], tm, n;
  stack<int> st;
  BaseGraph* gh;
  void tarjan(int x) {
    dfn[x] = low[x] = ++tm;
    st.push(x);
    for (int i = head[x]; i; i = t[i].nxt) {
      int v = t[i].to;
      if (dfn[v]) {
        low[x] = min(low[x], dfn[v]);
      } else {
        tarjan(v);
        low[x] = min(low[x], low[v]);
        if (low[v] >= dfn[x]) {
          ++n;
          int y;
          gh->add2(x, n);
          do {
            y = st.top();
            st.pop();
            gh->add2(y, n);
          } while (y != v);
        }
      }
    }
  }
  void tarjan(int n, BaseGraph* p) {
    this->n = n;
    this->gh = p;
    tarjan(1);
  }
} G;
struct NewGraph : BaseGraph {
  multiset<int> R[MAXN];
  int sz[MAXN], son[MAXN], top[MAXN];
  int dfn[MAXN], dep[MAXN], fa[MAXN], id;
  int w[MAXN], v[MAXN], rt;
  int bn, n;
  Segment<int> S;
  void prepare(int bn, int n) {
    fa[1] = id = 0;
    dep[1] = 1;
    dfs(1);
    deal(1, 1);
    this->bn = bn;
    this->n = n;
    for (int x = bn + 1; x <= n; ++x) {
      for (int i = head[x]; i; i = t[i].nxt) {
        int v = t[i].to;
        if (v == fa[x]) continue;
        R[x].insert(this->v[v]);
      }
      if (R[x].empty()) {
        v[x] = INF;
      } else
        v[x] = *R[x].begin();
    }
    for (int i = 1; i <= n; ++i) w[dfn[i]] = v[i];
    rt = S.build(1, n, w);
  }
  void dfs(int x) {
    sz[x] = 1;
    son[x] = 0;
    for (int i = head[x]; i; i = t[i].nxt) {
      int v = t[i].to;
      if (v == fa[x]) continue;
      dep[v] = dep[x] + 1;
      fa[v] = x;
      dfs(v);
      sz[x] += sz[v];
      if (sz[son[x]] < sz[v]) son[x] = v;
    }
  }
  void deal(int x, int topf) {
    if (!x) return;
    dfn[x] = ++id;
    top[x] = topf;
    deal(son[x], topf);
    for (int i = head[x]; i; i = t[i].nxt) {
      int v = t[i].to;
      if (v == fa[x]) continue;
      if (v == son[x]) continue;
      deal(v, v);
    }
  }
  void modify(int x, int val) {
    int f = fa[x];
    if (f) {
      R[f].erase(R[f].find(v[x]));
      R[f].insert(val);
      v[f] = *R[f].begin();
      S.modify(rt, dfn[f], v[f]);
    }
    v[x] = val;
    S.modify(rt, dfn[x], val);
  }
  int query(int x, int y) {
    int ans = INF;
    while (top[x] != top[y]) {
      if (dep[top[x]] < dep[top[y]]) swap(x, y);
      ans = min(ans, S.query(rt, dfn[top[x]], dfn[x]));
      x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans = min(ans, S.query(rt, dfn[x], dfn[y]));
    if (x > bn) ans = min(ans, v[fa[x]]);
    return ans;
  }
} G2;
int main() {
  int n, m, T;
  read(n, m, T);
  for (int i = 1; i <= n; ++i) read(G2.v[i]);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    read(x, y);
    G.add2(x, y);
  }
  G.tarjan(n, &G2);
  G2.prepare(n, G.n);
  while (T--) {
    char c;
    int x, y;
    read(c, x, y);
    switch (c) {
      case 'A':
        printf("%d\n", G2.query(x, y));
        break;
      case 'C':
        G2.modify(x, y);
        break;
    }
  }
  return 0;
}