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 MAX_N = 100000 + 2;
const int MAX_M = 100000 + 2;
int weight[MAX_N];
struct Edge {
  int v, x;
} E[MAX_M * 10];
int tot;
template <int N>
struct AdjList {
  int l[N];
  inline void addEdge(int u, int v) {
    E[tot] = (Edge){v, l[u]};
    l[u] = tot++;
  }
  void init() { memset(l, -1, sizeof l); }
};
AdjList<MAX_N> adj;
namespace BCC {
const int N = MAX_N;
const int M = MAX_M;
set<int> p2c[N];
set<pair<int, int> > c2e[N];
map<pair<int, int>, int> e2c;
pair<int, int> S[M], tmp;
int cut[N], dep[N], low[N], ori[N + N];
int *l;
Edge *E;
int n, bcc_cnt, top;
void dfs(int u, int D, int ind);
void Pop(pair<int, int> y);
int rebuild(AdjList<N + N> &adj);
void init(int _n, int *_l, Edge *_E) {
  n = _n;
  l = _l;
  E = _E;
  for (int i = 0; i < n; i++) dep[i] = cut[i] = -1;
  for (int i = 0; i < n; i++) p2c[i].clear(), c2e[i].clear();
  e2c.clear();
  bcc_cnt = top = 0;
  for (int i = 0; i < n; i++)
    if (dep[i] == -1) {
      dfs(i, 0, -1);
    }
}
void dfs(int u, int D, int ind) {
  dep[u] = low[u] = D;
  int child = 0;
  for (int i = l[u]; ~i; i = E[i].x) {
    if (ind == (i ^ 1)) continue;
    int v = E[i].v;
    S[top++] = {u, v};
    if (dep[v] >= 0) {
      if (dep[v] > dep[u]) top--;
      low[u] = min(low[u], dep[v]);
      continue;
    }
    child++;
    dfs(v, D + 1, i);
    low[u] = min(low[u], low[v]);
    if (low[v] >= dep[u]) {
      cut[u] = 1;
      Pop(pair<int, int>(u, v));
    }
  }
  if (child == 1 && ind < 0) cut[u] = -1;
}
void Pop(pair<int, int> y) {
  do {
    tmp = S[--top];
    p2c[tmp.first].insert(bcc_cnt);
    p2c[tmp.second].insert(bcc_cnt);
    if (tmp.first > tmp.second) swap(tmp.first, tmp.second);
    c2e[bcc_cnt].insert(tmp);
    e2c[tmp] = bcc_cnt;
  } while (top && S[top] != y);
  bcc_cnt++;
}
int rebuild(AdjList<N + N> &adj) {
  int c = bcc_cnt;
  for (int i = 0; i < n; i++)
    if (cut[i] != -1) {
      cut[i] = c++;
      ori[c - 1] = i;
    }
  adj.init();
  set<int>::iterator it;
  for (int u = 0; u < n; u++) {
    if (cut[u] == -1) continue;
    for (it = p2c[u].begin(); it != p2c[u].end(); it++) {
      adj.addEdge(cut[u], *it);
      adj.addEdge(*it, cut[u]);
    }
  }
  return c;
}
};  // namespace BCC
namespace Solve {
const int N = MAX_N + MAX_N;
const int inf = 1e9;
AdjList<N> adj2;
multiset<int> value[N];
int n, m;
int dep[N], top[N], fa[N], heavy[N], siz[N];
int ID[N];
int *l;
Edge *E;
void Label(int u, int anc);
void dfs(int u);
int query(int a, int b);
struct segTree {
  int Min[N << 1];
  inline int getID(int l, int r) { return l + r | l != r; }
  void up(int l, int r) {
    int mid = l + r >> 1;
    Min[getID(l, r)] = min(Min[getID(l, mid)], Min[getID(mid + 1, r)]);
  }
  void build(int l, int r) {
    int o = getID(l, r);
    if (l == r) {
      if (value[l].empty()) {
        puts("empty bug");
        Min[o] = inf;
      } else {
        Min[o] = *value[l].begin();
      }
    } else {
      int mid = l + r >> 1;
      build(l, mid);
      build(mid + 1, r);
      up(l, r);
    }
  }
  void update(int l, int r, int ql, int preValue, int nowValue) {
    if (l == r) {
      auto it = value[l].lower_bound(preValue);
      if (it == value[l].end()) {
        puts("delete bug");
        return;
      }
      value[l].erase(it);
      value[l].insert(nowValue);
      Min[getID(l, r)] = *value[l].begin();
    } else {
      int mid = l + r >> 1;
      if (ql <= mid)
        update(l, mid, ql, preValue, nowValue);
      else
        update(mid + 1, r, ql, preValue, nowValue);
      up(l, r);
    }
  }
  int getMin(int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return Min[getID(l, r)];
    }
    int mid = l + r >> 1;
    if (qr <= mid) return getMin(l, mid, ql, qr);
    if (ql > mid) return getMin(mid + 1, r, ql, qr);
    return min(getMin(l, mid, ql, qr), getMin(mid + 1, r, ql, qr));
  }
} segs;
void dfs(int u) {
  siz[u] = 1;
  heavy[u] = -1;
  for (int i = l[u], v; ~i; i = E[i].x) {
    v = E[i].v;
    if (fa[u] != v) {
      dep[v] = dep[u] + 1;
      fa[v] = u;
      dfs(v);
      siz[u] += siz[v];
      if (heavy[u] == -1 || siz[heavy[u]] < siz[v]) {
        heavy[u] = v;
      }
    }
  }
}
void Label(int u, int anc) {
  ID[u] = m++;
  top[u] = anc;
  if (~heavy[u]) Label(heavy[u], anc);
  for (int i = l[u], v; ~i; i = E[i].x) {
    v = E[i].v;
    if (v != fa[u] && v != heavy[u]) {
      Label(v, v);
    }
  }
}
int query(int a, int b) {
  int ret = inf;
  while (top[a] != top[b]) {
    if (dep[top[a]] < dep[top[b]]) {
      swap(a, b);
    }
    ret = min(ret, segs.getMin(0, m - 1, ID[top[a]], ID[a]));
    a = fa[top[a]];
  }
  if (dep[a] < dep[b]) {
    swap(a, b);
  }
  ret = min(ret, segs.getMin(0, m - 1, ID[b], ID[a]));
  if (b < BCC::bcc_cnt && fa[b] != -1) {
    ret = min(ret, weight[BCC::ori[fa[b]]]);
  }
  return ret;
}
void init(int _n, Edge *_E, int _m) {
  n = _n;
  for (int u = 0; u < n; u++) value[u].clear();
  l = adj2.l;
  E = _E;
  dep[0] = -1;
  fa[0] = -1;
  m = 0;
  dfs(0);
  Label(0, 0);
  for (int u = 0; u < _m; u++) {
    if (BCC::cut[u] == -1) {
      value[ID[*BCC::p2c[u].begin()]].insert(weight[u]);
    } else {
      value[ID[BCC::cut[u]]].insert(weight[u]);
      value[ID[fa[BCC::cut[u]]]].insert(weight[u]);
    }
  }
  segs.build(0, m - 1);
}
void modify(int u, int pre, int now) {
  if (u >= BCC::bcc_cnt && fa[u] != -1) {
    modify(fa[u], pre, now);
  }
  segs.update(0, m - 1, ID[u], pre, now);
}
void gao(int q) {
  char op;
  int a, b, w, x, y;
  while (q--) {
    scanf(" %c %d %d", &op, &a, &b);
    if (op == 'C') {
      a--;
      x = BCC::cut[a];
      if (x == -1) {
        if (BCC::p2c[a].size() != 1) {
          puts("build bug");
        }
        x = *BCC::p2c[a].begin();
      }
      modify(x, weight[a], b);
      weight[a] = b;
    } else {
      a--;
      b--;
      if (a == b) {
        printf("%d\n", weight[a]);
        continue;
      }
      x = BCC::cut[a];
      y = BCC::cut[b];
      if (x == -1) {
        if (BCC::p2c[a].size() != 1) {
          puts("build bug");
        }
        x = *BCC::p2c[a].begin();
      }
      if (y == -1) {
        if (BCC::p2c[b].size() != 1) {
          puts("build bug");
        }
        y = *BCC::p2c[b].begin();
      }
      printf("%d\n", query(x, y));
    }
  }
}
};  // namespace Solve
int main() {
  int n, m, q, u, v, w;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", weight + i);
  }
  tot = 0;
  adj.init();
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    u--;
    v--;
    adj.addEdge(u, v);
    adj.addEdge(v, u);
  }
  BCC::init(n, adj.l, E);
  int bcc_cnt = BCC::rebuild(Solve::adj2);
  Solve::init(bcc_cnt, E, n);
  Solve::gao(q);
  return 0;
}