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 INF = 2000000000;
int n, m, k;
int timer = 1, root = 0;
vector<int> roads[200051];
int w[200051];
bool used[200051], cutIt[200051];
int t_in[200051], best[200051];
int iHeightThisCodeForReal[200051];
int szKSS = 0;
set<int> kss[200051];
set<int> ksscut[200051];
multiset<int> ansbcc[200051];
int anscut[200051];
int sz = 0;
set<int> gr[200051];
int link[200051];
pair<int, int> E(int v, int to) { return {min(v, to), max(v, to)}; }
void RunSomeDeepShip(int v, int p = -1) {
  int ch = 0;
  best[v] = t_in[v] = timer++;
  for (int i = 0; i < (int)roads[v].size(); ++i) {
    int to = roads[v][i];
    if (to == p) continue;
    if (!t_in[to]) {
      RunSomeDeepShip(to, v);
      best[v] = min(best[to], best[v]);
      if (best[to] >= t_in[v] && p != -1) {
        cutIt[v] = true;
      }
      ++ch;
    } else {
      best[v] = min(t_in[to], best[v]);
    }
  }
  if (ch > 1 && p == -1) cutIt[v] = true;
}
bool ANOTHERMASSIVE[200051];
stack<pair<int, int> > st;
int color, MaxColor = 1;
vector<pair<int, int> > Colors[200051];
void paint(int v, int parent) {
  used[v] = true;
  t_in[v] = best[v] = timer++;
  for (auto it = roads[v].begin(); it != roads[v].end(); ++it) {
    if (*it == parent) continue;
    if (!used[*it]) {
      st.push(E(v, *it));
      paint(*it, v);
      if (best[*it] >= t_in[v]) {
        color = MaxColor++;
        while (st.top() != E(v, *it)) {
          Colors[color].push_back(st.top());
          st.pop();
        }
        Colors[color].push_back(E(v, *it));
        st.pop();
      }
      if (best[*it] < best[v]) best[v] = best[*it];
    } else if (t_in[*it] < t_in[v])
      st.push(E(v, *it));
    if (best[v] > t_in[*it]) best[v] = t_in[*it];
  }
}
bool addedtobcc[200051];
void MakeGraph() {
  for (int i = 1; i <= n; ++i) {
    cin >> w[i];
  }
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    roads[a].push_back(b);
    roads[b].push_back(a);
  }
  RunSomeDeepShip(1, -1);
  for (int i = 1; !root && i <= n; ++i)
    if (!cutIt[i]) root = i;
  for (int i = 1; i <= 200051 - 1; ++i) {
    t_in[i] = best[i] = 0;
    used[i] = false;
  }
  timer = 1;
  paint(root, -1);
  --MaxColor;
  szKSS = MaxColor;
  for (int i = 1; i <= MaxColor; ++i) {
    for (int j = 0; j < Colors[i].size(); ++j) {
      if (!cutIt[Colors[i][j].first]) {
        link[Colors[i][j].first] = i;
        if (!addedtobcc[Colors[i][j].first]) {
          ansbcc[i].insert(w[Colors[i][j].first]);
          addedtobcc[Colors[i][j].first] = true;
        }
        kss[i].insert(Colors[i][j].first);
      } else
        ksscut[i].insert(Colors[i][j].first);
      if (!cutIt[Colors[i][j].second]) {
        link[Colors[i][j].second] = i;
        if (!addedtobcc[Colors[i][j].second]) {
          ansbcc[i].insert(w[Colors[i][j].second]);
          addedtobcc[Colors[i][j].second] = true;
        }
        kss[i].insert(Colors[i][j].second);
      } else
        ksscut[i].insert(Colors[i][j].second);
    }
  }
  sz = szKSS;
  for (int i = 1; i <= n; ++i) {
    if (cutIt[i]) {
      link[i] = ++sz;
      anscut[link[i]] = w[i];
    } else
      root = i;
  }
  for (int j = 1; j <= szKSS; ++j) {
    for (auto it = ksscut[j].begin(); it != ksscut[j].end(); ++it) {
      gr[link[*it]].insert(j);
      gr[j].insert(link[*it]);
    }
  }
}
int cnt[200051];
int pr[200051];
bool heavy[200051];
void SomeMoreDFS(int v, int p = -1) {
  cnt[v] = 1;
  for (auto it = gr[v].begin(); it != gr[v].end(); ++it) {
    int to = *it;
    if (to == p) continue;
    pr[to] = v;
    SomeMoreDFS(to, v);
    cnt[v] += cnt[to];
  }
  for (auto it = gr[v].begin(); it != gr[v].end(); ++it) {
    int to = *it;
    if (to == p) continue;
    if (cnt[to] >= (cnt[v] + 1) / 2) {
      heavy[to] = true;
    }
  }
}
int treecnt = 1;
vector<int> vert[200051];
vector<int> tr[200051];
int whatTree[200051];
int whereTree[200051];
int whyTree[200051];
void ImMadBro(int v, int tree, int height = 1, int p = -1) {
  iHeightThisCodeForReal[v] = height;
  vert[tree].push_back(v);
  for (auto it = gr[v].begin(); it != gr[v].end(); ++it) {
    int to = *it;
    if (to == p) continue;
    if (heavy[to]) {
      ImMadBro(to, tree, height, v);
    } else {
      ++treecnt;
      ImMadBro(to, treecnt, height + 1, v);
    }
  }
}
void BuildTree(int, int, int, int);
void MAKESOMEDITCH() {
  for (int i = 1; i <= treecnt; ++i) {
    tr[i].assign(4 * vert[i].size() + 4, 0);
    BuildTree(i, 1, 0, vert[i].size() - 1);
  }
}
int Weight(int x) {
  if (x <= szKSS) {
    if (ansbcc[x].size() == 0) return INF;
    return *ansbcc[x].begin();
  }
  return anscut[x];
}
void BuildTree(int id, int v, int l, int r) {
  if (l == r) {
    int to = vert[id][l];
    if (to <= szKSS) {
      for (auto it = gr[to].begin(); it != gr[to].end(); ++it)
        if (pr[*it] == to) {
          ansbcc[to].insert(Weight(*it));
        }
    }
    tr[id][v] = Weight(vert[id][l]);
    whatTree[vert[id][l]] = id;
    whereTree[vert[id][l]] = v;
    whyTree[vert[id][l]] = l;
  } else {
    int m = (l + r) >> 1;
    BuildTree(id, v << 1, l, m);
    BuildTree(id, v << 1 | 1, m + 1, r);
    tr[id][v] = min(tr[id][v << 1], tr[id][v << 1 | 1]);
  }
}
int QUETHISALREADY(int id, int v, int l, int r, int L, int R) {
  if (l > r) return INF;
  if (l == L && r == R) return tr[id][v];
  int M = (L + R) >> 1;
  return min(QUETHISALREADY(id, v << 1, l, min(M, r), L, M),
             QUETHISALREADY(id, v << 1 | 1, max(l, M + 1), r, M + 1, R));
}
void UPDATETHISDITCH(int V) {
  int NewV = V;
  int kTree = whatTree[NewV];
  int vTree = whereTree[NewV];
  int Wicanttakeitanymore = Weight(NewV);
  tr[kTree][vTree] = Wicanttakeitanymore;
  vTree >>= 1;
  while (vTree) {
    tr[kTree][vTree] = min(tr[kTree][vTree << 1], tr[kTree][vTree << 1 | 1]);
    vTree >>= 1;
  }
}
void changeInMyTree(int V, int N) {
  int NewV = link[V];
  if (cutIt[V]) {
    anscut[NewV] = N;
    UPDATETHISDITCH(NewV);
    NewV = pr[NewV];
  }
  ansbcc[NewV].erase(ansbcc[NewV].find(w[V]));
  ansbcc[NewV].insert(N);
  UPDATETHISDITCH(NewV);
  w[V] = N;
}
int ANS(int a, int b) {
  a = link[a];
  b = link[b];
  int ha, hb;
  int cATree, cBTree, cAV, cBV;
  cATree = whatTree[a];
  cBTree = whatTree[b];
  cAV = whyTree[a];
  cBV = whyTree[b];
  int Ans = INF;
  while (cATree != cBTree) {
    ha = iHeightThisCodeForReal[a];
    hb = iHeightThisCodeForReal[b];
    if (ha > hb) {
      Ans = min(Ans, QUETHISALREADY(cATree, 1, 0, whyTree[a], 0,
                                    vert[cATree].size() - 1));
      a = pr[vert[cATree][0]];
    } else {
      Ans = min(Ans, QUETHISALREADY(cBTree, 1, 0, whyTree[b], 0,
                                    vert[cBTree].size() - 1));
      b = pr[vert[cBTree][0]];
    }
    cATree = whatTree[a];
    cBTree = whatTree[b];
    cAV = whyTree[a];
    cBV = whyTree[b];
  }
  cAV = whyTree[a];
  cBV = whyTree[b];
  if (cAV > cBV) {
    swap(a, b);
    swap(cAV, cBV);
  }
  cATree = whatTree[a];
  Ans =
      min(Ans, QUETHISALREADY(cATree, 1, cAV, cBV, 0, vert[cATree].size() - 1));
  int DATPROBLEM1111 = pr[vert[cATree][0]];
  if (cAV) DATPROBLEM1111 = vert[cATree][cAV - 1];
  if (vert[cATree][cAV] <= szKSS && DATPROBLEM1111) {
    cATree = whatTree[DATPROBLEM1111];
    cAV = whyTree[DATPROBLEM1111];
    Ans = min(Ans,
              QUETHISALREADY(cATree, 1, cAV, cAV, 0, vert[cATree].size() - 1));
  }
  return Ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> k;
  MakeGraph();
  SomeMoreDFS(1);
  ImMadBro(1, 1);
  MAKESOMEDITCH();
  for (int i = 0; i < k; ++i) {
    char t;
    cin >> t;
    int tK, N, V, A, B;
    switch (t) {
      case 'C':
        cin >> V >> N;
        changeInMyTree(V, N);
        break;
      case 'A':
        cin >> A >> B;
        if (A == B)
          cout << w[A] << endl;
        else
          cout << ANS(A, B) << endl;
        break;
    }
  }
  return 0;
}