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;
namespace Quick_Function {
template <typename Temp>
void Read(Temp &x) {
  x = 0;
  char ch = getchar();
  bool op = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') op = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  if (op) x = -x;
}
template <typename T, typename... Args>
void Read(T &t, Args &...args) {
  Read(t);
  Read(args...);
}
template <typename Temp>
Temp Max(Temp x, Temp y) {
  return x > y ? x : y;
}
template <typename Temp>
Temp Min(Temp x, Temp y) {
  return x < y ? x : y;
}
template <typename Temp>
Temp Abs(Temp x) {
  return x < 0 ? (-x) : x;
}
template <typename Temp>
void Swap(Temp &x, Temp &y) {
  x ^= y ^= x ^= y;
}
}  // namespace Quick_Function
using namespace Quick_Function;
const int MAXN = 1e6 + 5;
struct edge1 {
  int To, Next;
};
edge1 edge1[MAXN << 1], edge2[MAXN << 1];
int head1[MAXN], head2[MAXN];
int edgetot1, edgetot2;
void Addedge1(int u, int v) {
  edge1[++edgetot1].Next = head1[u], edge1[edgetot1].To = v,
  head1[u] = edgetot1;
  edge1[++edgetot1].Next = head1[v], edge1[edgetot1].To = u,
  head1[v] = edgetot1;
}
void Addedge2(int u, int v) {
  edge2[++edgetot2].Next = head2[u], edge2[edgetot2].To = v,
  head2[u] = edgetot2;
  edge2[++edgetot2].Next = head2[v], edge2[edgetot2].To = u,
  head2[v] = edgetot2;
}
int w[MAXN], n, m, q;
stack<int> stk;
int dfn1[MAXN], low[MAXN];
int tim1, cnt;
void Tarjan(int u) {
  dfn1[u] = low[u] = ++tim1;
  stk.push(u);
  for (int i = head1[u]; i; i = edge1[i].Next) {
    int v = edge1[i].To;
    if (!dfn1[v]) {
      Tarjan(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn1[u]) {
        int Top = -1;
        cnt++;
        while (Top != v) {
          Top = stk.top();
          stk.pop();
          Addedge2(Top, cnt);
        }
        Addedge2(u, cnt);
      }
    } else
      low[u] = min(low[u], dfn1[v]);
  }
}
struct Segment_Node {
  int Left, Right, MinData;
};
struct Segment_Tree {
  Segment_Node segment_tree[MAXN << 2];
  void Push_Up(int pos) {
    segment_tree[pos].MinData = Min(segment_tree[(pos << 1)].MinData,
                                    segment_tree[(pos << 1 | 1)].MinData);
  }
  void Build(int pos, int l, int r) {
    segment_tree[pos].Left = l, segment_tree[pos].Right = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    Build((pos << 1), l, mid), Build((pos << 1 | 1), mid + 1, r);
  }
  void Update(int pos, int x, int k) {
    if (segment_tree[pos].Left == segment_tree[pos].Right) {
      segment_tree[pos].MinData = k;
      return;
    }
    if (x <= segment_tree[(pos << 1)].Right)
      Update((pos << 1), x, k);
    else
      Update((pos << 1 | 1), x, k);
    Push_Up(pos);
  }
  int Query_Min(int pos, int l, int r) {
    if (l <= segment_tree[pos].Left && segment_tree[pos].Right <= r)
      return segment_tree[pos].MinData;
    int res = 0x3f3f3f3f;
    if (l <= segment_tree[(pos << 1)].Right)
      res = Min(res, Query_Min((pos << 1), l, r));
    if (r >= segment_tree[(pos << 1 | 1)].Left)
      res = Min(res, Query_Min((pos << 1 | 1), l, r));
    return res;
  }
};
Segment_Tree tree1;
struct Splay_Node {
  int Child[2], Val, Cnt, Siz, Father, Belong;
};
struct Splay_Tree {
  int root[MAXN], tot;
  Splay_Node splay[MAXN * 3];
  bool Ident(int pos) { return splay[splay[pos].Father].Child[1] == pos; }
  int New(int val, int fa, int now) {
    splay[++tot].Father = fa;
    splay[tot].Cnt = splay[tot].Siz = 1;
    splay[tot].Val = val;
    splay[tot].Belong = now;
    return tot;
  }
  void Build() {
    for (int i = 1; i <= cnt - n; i++) {
      root[i] = New(-0x3f3f3f3f, 0, i);
      splay[root[i]].Child[1] = New(0x3f3f3f3f, root[i], i);
    }
  }
  void Update(int pos) {
    splay[pos].Siz = splay[pos].Cnt + splay[splay[pos].Child[0]].Siz +
                     splay[splay[pos].Child[1]].Siz;
  }
  void Connect(int pos, int fa, int flag) {
    splay[fa].Child[flag] = pos;
    splay[pos].Father = fa;
  }
  void Rotate(int pos) {
    int fa = splay[pos].Father, grand = splay[fa].Father;
    int flag1 = Ident(pos), flag2 = Ident(fa);
    Connect(splay[pos].Child[flag1 ^ 1], fa, flag1);
    Connect(fa, pos, flag1 ^ 1);
    Connect(pos, grand, flag2);
    Update(fa);
    Update(pos);
  }
  void Splay(int pos, int to) {
    for (int fa = splay[pos].Father; splay[pos].Father != to;
         Rotate(pos), fa = splay[pos].Father)
      if (splay[fa].Father != to)
        Ident(pos) == Ident(fa) ? Rotate(fa) : Rotate(pos);
    if (!to) root[splay[pos].Belong] = pos;
  }
  void Insert(int &pos, int val, int fa) {
    if (!pos) {
      pos = New(val, fa, splay[fa].Belong);
      Splay(pos, 0);
      return;
    }
    if (val == splay[pos].Val) {
      splay[pos].Cnt++;
      Splay(pos, 0);
      return;
    } else if (val < splay[pos].Val)
      Insert(splay[pos].Child[0], val, pos);
    else
      Insert(splay[pos].Child[1], val, pos);
  }
  void Remove(int pos, int val) {
    if (!pos) return;
    if (val == splay[pos].Val) {
      if (splay[pos].Cnt > 1) {
        splay[pos].Cnt--;
        Splay(pos, 0);
        return;
      }
      if (splay[pos].Child[0])
        Rotate(splay[pos].Child[0]), Remove(pos, val);
      else if (splay[pos].Child[1])
        Rotate(splay[pos].Child[1]), Remove(pos, val);
      else {
        int newroot = splay[pos].Father;
        splay[splay[pos].Father].Child[Ident(pos)] = 0;
        Splay(newroot, 0);
      }
      return;
    } else if (val < splay[pos].Val)
      Remove(splay[pos].Child[0], val);
    else
      Remove(splay[pos].Child[1], val);
  }
  int Query_Min(int pos) {
    if (!pos) return 0x3f3f3f3f;
    if (splay[splay[pos].Child[0]].Siz >= 2)
      return Query_Min(splay[pos].Child[0]);
    Splay(pos, 0);
    return splay[pos].Val;
  }
};
Splay_Tree tree2;
int dfn2[MAXN], siz[MAXN], dep[MAXN], son[MAXN], fa[MAXN], tp[MAXN];
int tim2;
void dfs1(int u, int pre) {
  dep[u] = dep[pre] + 1, fa[u] = pre, siz[u] = 1;
  int maxn = -0x3f3f3f3f;
  for (int i = head2[u]; i; i = edge2[i].Next) {
    int v = edge2[i].To;
    if (v == pre) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    if (siz[v] > maxn) son[u] = v, maxn = siz[v];
  }
}
void dfs2(int u, int Top) {
  dfn2[u] = ++tim2, tp[u] = Top;
  if (son[u]) dfs2(son[u], Top);
  for (int i = head2[u]; i; i = edge2[i].Next) {
    int v = edge2[i].To;
    if (v != son[u] && v != fa[u]) dfs2(v, v);
  }
}
int Min_Past(int x, int y) {
  int res = 0x3f3f3f3f;
  while (tp[x] != tp[y]) {
    if (dep[tp[x]] < dep[tp[y]]) Swap(x, y);
    res = Min(res, tree1.Query_Min(1, dfn2[tp[x]], dfn2[x]));
    x = fa[tp[x]];
  }
  if (dep[x] > dep[y]) Swap(x, y);
  res = Min(res, tree1.Query_Min(1, dfn2[x], dfn2[y]));
  if (x > n) res = Min(res, w[fa[x]]);
  return res;
}
int main() {
  Read(n, m, q);
  cnt = n;
  for (int i = 1; i <= n; i++) Read(w[i]);
  for (int i = 1, u, v; i <= m; i++) Read(u, v), Addedge1(u, v);
  Tarjan(1);
  dfs1(1, 0);
  dfs2(1, 1);
  tree1.Build(1, 1, tim2);
  tree2.Build();
  for (int i = 2; i <= n; i++) tree2.Insert(tree2.root[fa[i] - n], w[i], 0);
  for (int i = 1; i <= n; i++) tree1.Update(1, dfn2[i], w[i]);
  for (int i = n + 1; i <= cnt; i++)
    tree1.Update(1, dfn2[i],
                 tree2.splay[tree2.root[i - n]].Siz == 2
                     ? 0x3f3f3f3f
                     : tree2.Query_Min(tree2.root[i - n]));
  char opt[2];
  for (int i = 1, a, b; i <= q; i++) {
    scanf("%s", opt), Read(a, b);
    if (opt[0] == 'A')
      printf("%d\n", Min_Past(a, b));
    else {
      if (a != 1) {
        tree2.Remove(tree2.root[fa[a] - n], w[a]);
        tree2.Insert(tree2.root[fa[a] - n], b, 0);
        int tmp = tree2.Query_Min(tree2.root[fa[a] - n]);
        tree1.Update(1, dfn2[fa[a]], tmp);
      }
      tree1.Update(1, dfn2[a], b), w[a] = b;
    }
  }
  return 0;
}