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>
#pragma GCC optimize(3)
namespace IO {
class istream {
  char pool[1 << 23], *in = pool - 1;

 public:
  inline istream() { std::fread(pool, 1, 1 << 23, stdin); }
  inline istream& operator>>(int& RHS) {
    RHS = 0;
    while (std::isspace(*++in))
      ;
    do RHS = 10 * RHS + (*in ^ 48);
    while (std::isdigit(*++in));
    return *this;
  }
  inline void get(char& RHS) { RHS = *++in; }
} cin;
class ostream {
  char pool[1 << 21], *out = pool - 1;

 public:
  inline ostream& operator<<(int RHS) {
    static char pool_[10], *out_ = pool_;
    do *out_++ = RHS % 10 ^ 48;
    while (RHS /= 10);
    while (out_ > pool_) *++out = *--out_;
    return *this;
  }
  inline void operator<<(const char& RHS) { *++out = RHS; }
  inline ~ostream() { std::fwrite(pool, 1, out - pool + 1, stdout); }
} cout;
}  // namespace IO
int n;
using AI = int[100000 << 1];
AI w;
using PII = std::pair<int, int>;
const int inf = std::numeric_limits<int>::max();
inline void chkmin(int& x, int y) {
  if (x > y) x = y;
}
inline void chkmax(int& x, int y) {
  if (x < y) x = y;
}
namespace seg_tree0 {
AI w, L, R, root;
struct {
  int LS, RS, val;
} node[1900000];
void build(int& cur, int L, int R) {
  static int idx;
  cur = ++idx;
  if (L < R - 1) {
    const int mid = L + R >> 1;
    build(node[cur].LS, L, mid), build(node[cur].RS, mid, R);
    node[cur].val = std::min(node[node[cur].LS].val, node[node[cur].RS].val);
  } else
    node[cur].val = w[L];
}
inline int query(int cur) { return node[cur].val; }
void modify(int cur, int L, int R, int pos, int val) {
  if (L < R - 1) {
    const int mid = L + R >> 1;
    if (pos < mid)
      modify(node[cur].LS, L, mid, pos, val);
    else
      modify(node[cur].RS, mid, R, pos, val);
    node[cur].val = std::min(node[node[cur].LS].val, node[node[cur].RS].val);
  } else
    node[cur].val = val;
}
}  // namespace seg_tree0
namespace seg_tree1 {
AI w, R, root;
struct {
  int LS, RS, val;
} node[1900000];
void build(int& cur, int L, int R) {
  static int idx;
  cur = ++idx;
  if (L < R - 1) {
    const int mid = L + R >> 1;
    build(node[cur].LS, L, mid), build(node[cur].RS, mid, R);
    node[cur].val = std::min(node[node[cur].LS].val, node[node[cur].RS].val);
  } else
    node[cur].val = w[L];
}
void modify(int cur, int L, int R, int pos, int val) {
  if (L < R - 1) {
    const int mid = L + R >> 1;
    if (pos < mid)
      modify(node[cur].LS, L, mid, pos, val);
    else
      modify(node[cur].RS, mid, R, pos, val);
    node[cur].val = std::min(node[node[cur].LS].val, node[node[cur].RS].val);
  } else
    node[cur].val = val;
}
int query(int cur, int L, int R, int L_, int R_) {
  if (L_ > L || R > R_) {
    const int mid = L + R >> 1;
    int res = inf;
    if (L_ < mid) chkmin(res, query(node[cur].LS, L, mid, L_, R_));
    if (R_ > mid) chkmin(res, query(node[cur].RS, mid, R, L_, R_));
    return res;
  }
  return node[cur].val;
}
}  // namespace seg_tree1
namespace tree {
AI idx;
PII edge[(100000 << 2) - 3];
inline void link(int u, int v) {
  static int cnt;
  edge[++cnt] = {v, idx[u]}, idx[u] = cnt;
}
AI BFN;
int q[(100000 << 1) - 1];
AI dep, fa;
void BFS() {
  static int clock;
  seg_tree0::w[BFN[1] = ++clock] = w[1];
  int h = 0, t = 1;
  q[0] = 1, dep[1] = 1;
  while (h < t) {
    const int& cur = q[h++];
    for (int i = idx[cur]; i; i = edge[i].second) {
      const int& to = edge[i].first;
      seg_tree0::w[BFN[to] = ++clock] = w[to];
      q[t++] = to, fa[to] = cur, dep[to] = dep[cur] + 1;
    }
  }
}
AI size;
void DFS(int cur) {
  size[cur] = 1;
  for (int i = idx[cur]; i; i = edge[i].second) {
    const int& to = edge[i].first;
    DFS(to), size[cur] += size[to];
  }
}
AI DFN, top;
void HLD(int cur, int top) {
  static int clock;
  seg_tree1::w[DFN[cur] = ++clock] = w[cur];
  tree::top[cur] = top;
  int m = 0;
  for (int i = idx[cur]; i; i = edge[i].second) {
    const int& to = edge[i].first;
    if (size[to] > size[m]) m = to;
  }
  if (m) {
    HLD(m, top);
    for (int i = idx[cur]; i; i = edge[i].second) {
      const int& to = edge[i].first;
      if (to != m) HLD(to, to);
    }
  }
}
inline void modify(int pos, int val) {
  const int& pos_ = top[pos];
  seg_tree1::modify(seg_tree1::root[pos_], DFN[pos_], seg_tree1::R[pos_],
                    DFN[pos], w[pos] = val);
  const int& fa = tree::fa[pos];
  seg_tree0::modify(seg_tree0::root[fa], seg_tree0::L[fa], seg_tree0::R[fa] + 1,
                    BFN[pos], val);
  const int& fa_ = top[fa];
  seg_tree1::modify(seg_tree1::root[fa_], DFN[fa_], seg_tree1::R[fa_], DFN[fa],
                    w[fa] = seg_tree0::query(seg_tree0::root[fa]));
}
int query(int u, int v) {
  int ans = inf;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    const int& u_ = top[u];
    chkmin(ans, seg_tree1::query(seg_tree1::root[u_], DFN[u_], seg_tree1::R[u_],
                                 DFN[u_], DFN[u] + 1)),
        u = fa[u_];
  }
  if (DFN[u] > DFN[v]) std::swap(u, v);
  const int& u_ = top[u];
  chkmin(ans, seg_tree1::query(seg_tree1::root[u_], DFN[u_], seg_tree1::R[u_],
                               DFN[u], DFN[v] + 1));
  if (u > ::n) chkmin(ans, w[fa[u]]);
  return ans;
}
}  // namespace tree
namespace graph {
using AI_ = int[100000 + 1];
AI_ idx;
PII edge[100000 << 1 | 1];
inline void link(int u, int v) {
  static int cnt;
  edge[++cnt] = {v, idx[u]}, idx[u] = cnt;
}
int n;
AI_ DFN, low;
int stack[100000];
void tarjan(int cur, int fa) {
  static int clock;
  DFN[cur] = low[cur] = ++clock;
  static int top;
  stack[top++] = cur;
  for (int i = idx[cur]; i; i = edge[i].second) {
    const int& to = edge[i].first;
    if (to != fa)
      if (!DFN[to]) {
        tarjan(to, cur), chkmin(low[cur], low[to]);
        if (low[to] >= DFN[cur]) {
          ++n;
          int x;
          do {
            x = stack[--top];
            tree::link(n, x);
          } while (x != to);
          tree::link(cur, n);
        }
      } else
        chkmin(low[cur], DFN[to]);
  }
}
}  // namespace graph
int main() {
  int m, q;
  IO::cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) IO::cin >> w[i];
  while (m--) {
    int a, b;
    IO::cin >> a >> b;
    graph::link(a, b), graph::link(b, a);
  }
  graph::n = n, graph::tarjan(1, 0);
  tree::BFS();
  for (int i = n + 1; i <= graph::n; ++i) {
    seg_tree0::L[i] = inf;
    for (int j = tree::idx[i]; j; j = tree::edge[j].second) {
      const int& _ = tree::BFN[tree::edge[j].first];
      chkmin(seg_tree0::L[i], _), chkmax(seg_tree0::R[i], _);
    }
    seg_tree0::build(seg_tree0::root[i], seg_tree0::L[i], seg_tree0::R[i] + 1),
        w[i] = seg_tree0::query(seg_tree0::root[i]);
  }
  tree::DFS(1), tree::HLD(1, 1);
  for (int i = 1; i <= graph::n; ++i)
    if (tree::size[i] == 1) {
      const int& i_ = tree::top[i];
      seg_tree1::build(seg_tree1::root[i_], tree::DFN[i_],
                       seg_tree1::R[i_] = tree::DFN[i] + 1);
    }
  while (q--) {
    char op;
    IO::cin.get(op);
    if (op == 'C') {
      int a, w;
      IO::cin >> a >> w, tree::modify(a, w);
    } else {
      int a, b;
      IO::cin >> a >> b, IO::cout << tree::query(a, b) << '\n';
    }
  }
}