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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
typedef struct G {
  int n, m;
  int w[100000];
  int fst[100000];
  int nxt[200000];
  int to[200000];
  int stck[100000], nstck;
  int vis[100000], nvis;
  bool been[100000];
  int d[100000], mind[100000];
  int cur[100000];
  int par[100000];
  int comp[100000], ncomp;
  int cfst[100000], cnxt[100000];
  void tarjan() {
    nstck = nvis = ncomp = 0;
    for (int i = (0); i < (n); ++i) been[i] = false;
    for (int i = (0); i < (n); ++i) par[i] = -1;
    for (int i = (0); i < (m); ++i) comp[i] = -1;
    stck[nstck++] = 0;
    d[0] = 0;
    par[0] = -2;
    while (nstck > 0) {
      int at = stck[--nstck];
      if (!been[at]) {
        been[at] = true;
        cur[at] = fst[at];
        mind[at] = d[at];
      } else {
        int nat = to[cur[at]];
        if (mind[nat] >= d[at]) {
          cfst[ncomp] = -1;
          while (true) {
            int now = vis[--nvis];
            comp[now / 2] = ncomp;
            cnxt[now / 2] = cfst[ncomp];
            cfst[ncomp] = now / 2;
            if (now == cur[at]) break;
          }
          ++ncomp;
        }
        if (mind[nat] < mind[at]) mind[at] = mind[nat];
        cur[at] = nxt[cur[at]];
      }
      while (cur[at] != -1) {
        int nat = to[cur[at]];
        if (been[nat]) {
          if (par[at] != nat && d[nat] < d[at]) {
            vis[nvis++] = cur[at];
            if (d[nat] < mind[at]) mind[at] = d[nat];
          }
          cur[at] = nxt[cur[at]];
        } else {
          stck[nstck++] = at;
          stck[nstck++] = nat;
          vis[nvis++] = cur[at];
          par[nat] = at;
          d[nat] = d[at] + 1;
          break;
        }
      }
    }
  }
} G;
G g;
typedef struct T {
  int onlycomp[100000];
  int lastcomp[100000];
  int n, m;
  int cutid[100000];
  int fst[200000];
  int nxt[400000];
  int to[400000];
  void create() {
    for (int i = (0); i < (g.n); ++i) {
      onlycomp[i] = -1;
      for (int x = g.fst[i]; x != -1; x = g.nxt[x]) {
        int now = g.comp[x / 2];
        if (onlycomp[i] == -1)
          onlycomp[i] = now;
        else if (onlycomp[i] != now)
          onlycomp[i] = -2;
      }
    }
    n = g.ncomp, m = 0;
    for (int i = (0); i < (g.n); ++i)
      if (onlycomp[i] != -2)
        cutid[i] = -1;
      else
        cutid[i] = n++;
    for (int i = (0); i < (g.n); ++i) lastcomp[i] = -1;
    for (int i = (0); i < (n); ++i) fst[i] = -1;
    for (int i = (0); i < (g.ncomp); ++i)
      for (int x = g.cfst[i]; x != -1; x = g.cnxt[x])
        for (int j = (0); j < (2); ++j) {
          int at = g.to[2 * x + j];
          if (cutid[at] == -1 || lastcomp[at] == i) continue;
          lastcomp[at] = i;
          nxt[2 * m + 0] = fst[i];
          fst[i] = 2 * m + 0;
          to[2 * m + 0] = cutid[at];
          nxt[2 * m + 1] = fst[cutid[at]];
          fst[cutid[at]] = 2 * m + 1;
          to[2 * m + 1] = i;
          ++m;
        }
  }
  int par[200000];
  int d[200000];
  int q[200000], qhead, qtail;
  int sz[200000];
  int heavy[200000];
  int id[200000], nid;
  int off[200000];
  int start[200000];
  int cnt[200000];
  int at[200000];
  int val[200000];
  int sval[1 << 19];
  void init() {
    for (int i = (0); i < (n); ++i) par[i] = -1;
    qhead = qtail = 0;
    q[qhead++] = 0;
    par[0] = -2;
    d[0] = 0;
    while (qtail < qhead) {
      int at = q[qtail++];
      for (int x = fst[at]; x != -1; x = nxt[x]) {
        if (par[to[x]] != -1) continue;
        par[to[x]] = at;
        d[to[x]] = d[at] + 1;
        q[qhead++] = to[x];
      }
    }
    for (int i = qhead - 1; i >= 0; --i) {
      int at = q[i];
      sz[at] = 1;
      for (int x = fst[at]; x != -1; x = nxt[x])
        if (par[to[x]] == at) sz[at] += sz[to[x]];
      heavy[at] = -1;
      for (int x = fst[at]; x != -1; x = nxt[x])
        if (par[to[x]] == at && 2 * sz[to[x]] >= sz[at]) heavy[at] = to[x];
    }
    nid = 0;
    for (int i = (0); i < (n); ++i)
      if (par[i] == -2 || heavy[par[i]] != i) {
        start[nid] = nid == 0 ? 0 : start[nid - 1] + cnt[nid - 1];
        cnt[nid] = 0;
        for (int x = i; x != -1; x = heavy[x]) {
          id[x] = nid, off[x] = cnt[nid]++;
          at[start[nid] + off[x]] = x;
        }
        ++nid;
      }
  }
  void up1(int &a, int &ret) {
    int cur = val[start[id[a]] + off[a]];
    if (cur < ret) ret = cur;
    a = par[a];
  }
  void upmany(int &a, int cnt, int &ret) {
    int cur = sgetmin(0, 0, n - 1, start[id[a]] + off[a] - cnt + 1,
                      start[id[a]] + off[a]);
    if (cur < ret) ret = cur;
    a = at[start[id[a]] + off[a] - cnt];
  }
  int solve(int a, int b) {
    int ret = INT_MAX;
    if (d[a] < d[b]) swap(a, b);
    while (d[a] != d[b]) {
      if (heavy[par[a]] != a) {
        up1(a, ret);
      } else {
        upmany(a, min(off[a], d[a] - d[b]), ret);
      }
    }
    while (a != b) {
      if (heavy[par[a]] != a || heavy[par[b]] != b) {
        up1(a, ret);
        up1(b, ret);
      } else {
        int cnt = min(off[a], off[b]);
        upmany(a, cnt, ret);
        upmany(b, cnt, ret);
      }
    }
    up1(a, ret);
    if (a >= g.ncomp) up1(a, ret);
    return ret;
  }
  int sgetmin(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sval[x];
    int m = l + (r - l) / 2;
    if (R <= m) return sgetmin(2 * x + 1, l, m, L, R);
    if (m + 1 <= L) return sgetmin(2 * x + 2, m + 1, r, L, R);
    return min(sgetmin(2 * x + 1, l, m, L, R),
               sgetmin(2 * x + 2, m + 1, r, L, R));
  }
  void supdate(int x, int l, int r, int KEY) {
    if (l == r) {
      sval[x] = val[l];
      return;
    }
    int m = l + (r - l) / 2;
    if (KEY <= m) supdate(2 * x + 1, l, m, KEY);
    if (m + 1 <= KEY) supdate(2 * x + 2, m + 1, r, KEY);
    sval[x] = min(sval[2 * x + 1], sval[2 * x + 2]);
  }
  void sinit(int x, int l, int r) {
    if (l == r) {
      sval[x] = val[l];
      return;
    }
    int m = l + (r - l) / 2;
    sinit(2 * x + 1, l, m);
    sinit(2 * x + 2, m + 1, r);
    sval[x] = min(sval[2 * x + 1], sval[2 * x + 2]);
  }
  void setval(int at, int nval) {
    val[start[id[at]] + off[at]] = nval;
    supdate(0, 0, n - 1, start[id[at]] + off[at]);
  }
  void print() {
    for (int i = (0); i < (g.n); ++i)
      if (cutid[i] != -1)
        printf("%d: cut %d\n", i, cutid[i]);
      else
        printf("%d: comp %d\n", i, onlycomp[i]);
    printrec(0, 0);
  }
  void printrec(int at, int d) {
    for (int i = (0); i < (d); ++i) printf("  ");
    printf("%d %c (%d,%d)\n", at,
           par[at] != -2 && heavy[par[at]] == at ? 'H' : '.', id[at], off[at]);
    for (int x = fst[at]; x != -1; x = nxt[x])
      if (par[to[x]] == at) printrec(to[x], d + 1);
  }
} T;
T t;
typedef struct PQ {
  int id[100000];
  int off[100000];
  int at[100000];
  int start[100000];
  int cnt[100000];
  void init() {
    for (int i = (0); i < (g.ncomp); ++i) cnt[i] = 0;
    for (int i = (0); i < (g.n); ++i) {
      int cid = t.cutid[i] == -1 ? t.onlycomp[i] : t.par[t.cutid[i]];
      id[i] = cid;
      off[i] = cnt[cid]++;
    }
    for (int i = (0); i < (g.ncomp); ++i)
      start[i] = i == 0 ? 0 : start[i - 1] + cnt[i - 1];
    for (int i = (0); i < (g.n); ++i) {
      at[start[id[i]] + off[i]] = i;
      up(i);
    }
    for (int i = (0); i < (g.ncomp); ++i)
      t.val[t.start[t.id[i]] + t.off[i]] = g.w[at[start[i] + 0]];
    for (int i = (0); i < (g.n); ++i) {
      int j = t.cutid[i];
      if (j != -1) t.val[t.start[t.id[j]] + t.off[j]] = g.w[i];
    }
    t.sinit(0, 0, t.n - 1);
  }
  void up(int x) {
    int cid = id[x], base = start[cid], len = cnt[cid];
    while (true) {
      int coff = off[x], noff = (coff - 1) / 2, y = at[base + noff];
      if (g.w[y] <= g.w[x]) break;
      change(x, y);
    }
  }
  void down(int x) {
    int cid = id[x], base = start[cid], len = cnt[cid];
    while (true) {
      int coff = off[x], y = x, noff1 = 2 * coff + 1, noff2 = 2 * coff + 2;
      if (noff1 < len) {
        int z = at[base + noff1];
        if (g.w[z] < g.w[y]) y = z;
      }
      if (noff2 < len) {
        int z = at[base + noff2];
        if (g.w[z] < g.w[y]) y = z;
      }
      if (x == y) break;
      change(x, y);
    }
  }
  void update(int x) {
    up(x);
    down(x);
  }
  void change(int x, int y) {
    assert(id[x] == id[y]);
    int px = start[id[x]] + off[x], py = start[id[y]] + off[y];
    assert(at[px] == x && at[py] == y);
    swap(at[px], at[py]);
    swap(off[x], off[y]);
  }
  int minval(int x) {
    int y = at[start[id[x]] + 0];
    return g.w[y];
  }
} PQ;
PQ pq;
typedef struct IN {
  int n, m, nq;
  int w[100000];
  int a[100000], b[100000];
  char type[100000];
  int x[100000], y[100000];
  void gen() {
    int seed = time(NULL);
    printf("seed=%d\n", seed);
    srand(seed);
    n = 20000;
    m = n - 1;
    nq = 100000;
    int LIM = 100000;
    for (int i = (0); i < (n); ++i) w[i] = rand() % LIM + 1;
    for (int i = (1); i < (n); ++i) a[i - 1] = 1, b[i - 1] = 1 + i;
    for (int i = (n - 1); i < (m); ++i) do {
        a[i] = 1 + rand() % n, b[i] = 1 + rand() % n;
      } while (a[i] == b[i]);
    for (int i = (0); i < (nq); ++i) type[i] = rand() % 2 == 0 ? 'A' : 'C';
    for (int i = (0); i < (nq); ++i) {
      x[i] = 1 + rand() % n;
      y[i] = 1 + rand() % (type[i] == 'A' ? n : LIM);
    }
  }
} IN;
IN in;
void input() {
  scanf("%d%d%d", &in.n, &in.m, &in.nq);
  for (int i = (0); i < (in.n); ++i) scanf("%d", &in.w[i]);
  for (int i = (0); i < (in.m); ++i) scanf("%d%d", &in.a[i], &in.b[i]);
  for (int qi = (0); qi < (in.nq); ++qi)
    scanf(" %c%d%d", &in.type[qi], &in.x[qi], &in.y[qi]);
}
void run() {
  g.n = in.n;
  g.m = in.m;
  for (int i = (0); i < (g.n); ++i) g.w[i] = in.w[i];
  for (int i = (0); i < (g.n); ++i) g.fst[i] = -1;
  for (int i = (0); i < (g.m); ++i) {
    int a = in.a[i], b = in.b[i];
    --a, --b;
    g.nxt[2 * i + 0] = g.fst[a];
    g.fst[a] = 2 * i + 0;
    g.to[2 * i + 0] = b;
    g.nxt[2 * i + 1] = g.fst[b];
    g.fst[b] = 2 * i + 1;
    g.to[2 * i + 1] = a;
  }
  g.tarjan();
  t.create();
  t.init();
  pq.init();
  for (int qi = (0); qi < (in.nq); ++qi) {
    char type = in.type[qi];
    if (type == 'A') {
      int a = in.x[qi], b = in.y[qi];
      --a, --b;
      int oa = a, ob = b;
      int ret = -1;
      if (a == b) {
        ret = g.w[a];
      } else {
        a = t.cutid[a] == -1 ? t.onlycomp[a] : t.cutid[a];
        b = t.cutid[b] == -1 ? t.onlycomp[b] : t.cutid[b];
        ret = t.solve(a, b);
      }
      printf("%d\n", ret);
    } else if (type == 'C') {
      int a = in.x[qi], w = in.y[qi];
      --a;
      g.w[a] = w;
      int b;
      if (t.cutid[a] != -1) {
        t.setval(t.cutid[a], w);
        b = t.par[t.cutid[a]];
      } else {
        b = t.onlycomp[a];
      }
      pq.update(a);
      int bw = pq.minval(a);
      t.setval(b, bw);
    }
  }
}
int main() {
  input();
  run();
  return 0;
}