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 JAVA):

Solution:
import java.util.*;

import java.io.*;
import java.awt.Point;
import java.math.BigInteger;


public class tourists {
	
	static int[] w;
	static ArrayList<Integer> normalEdges[];
	static int[] disc, low, parentDFS;
	static boolean visited[];
	static HashSet<Integer> treeEdges[];
	static boolean isArticulationID[];
	
	static int[] size, p, chainHead, chainIndex, toChain;
	static MINTree tree;
	
	static int[] toPreorder, fromPreorder, firstOccurence;
	static MINTree lca;
	
	public static void main(String[] args) throws Exception {
		FastIO sc = new FastIO(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int Q = sc.nextInt();
		
		w = new int[N+1];
		w[N] = 1000000000;
		for(int i = 0; i < N; i++) w[i] = sc.nextInt();
		
		normalEdges = new ArrayList[N];
		for(int i = 0; i < N; i++) normalEdges[i] = new ArrayList<Integer>();
		for(int i = 0; i < M; i++) {
			int a = sc.nextInt()-1;
			int b = sc.nextInt()-1;
			normalEdges[a].add(b);
			normalEdges[b].add(a);
		}
		
		//BCC and block-cut tree
		disc = new int[N];
		low = new int[N];
		parentDFS = new int[N];
		visited = new boolean[N];
		
		treeNode = new int[N];
		isArticulation = new boolean[N];
		isArticulationID = new boolean[2*N];
		treeEdges = new HashSet[2*N];
		for(int i = 0; i < 2*N; i++) treeEdges[i] = new HashSet<Integer>();
		
		getBiconnected(0);
		//BCC and block-cut tree
		
		/*
		System.out.println(Arrays.toString(treeNode));
		System.out.println(Arrays.toString(isArticulation));
		System.out.println(Arrays.toString(isArticulationID));
		*/
		
		//HLD
		size = new int[ID];
		p = new int[ID];
		dfs_size(0, -1);
		
		chainHead = new int[ID];
		chainIndex = new int[ID];
		toChain = new int[ID];
		Arrays.fill(chainHead, -1);
		
		tree = new MINTree(ID);
		hld(0, -1);
		//HLD
		//System.out.println(Arrays.toString(toChain));
		
		//LCA
		time = 0;
		toPreorder = new int[ID];
		fromPreorder = new int[ID];
		firstOccurence = new int[ID];
		lca = new MINTree(2*ID);
		Arrays.fill(firstOccurence, Integer.MAX_VALUE);
		
		preorder(0, -1);
		eulerTour(0, -1);
		//LCA
		
		pqs = new TreeSet[ID];
		for(int i = 0; i < ID; i++) {
			pqs[i] = new TreeSet<Integer>(comp);
			pqs[i].add(N);
		}
		
		for(int i = 0; i < N; i++) {
			pqs[treeNode[i]].add(i);
			if(isArticulationID[treeNode[i]] && p[treeNode[i]] != -1) pqs[p[treeNode[i]]].add(i);
		}
		for(int i = 0; i < ID; i++) update(i);
		
		
		
		for(int i = 0; i < Q; i++) {
			if(sc.next().equals("C")) {
				int node = sc.nextInt()-1;
				int weight = sc.nextInt();
				pqs[treeNode[node]].remove(node);
				if(isArticulationID[treeNode[node]] && p[treeNode[node]] != -1) pqs[p[treeNode[node]]].remove(node);
				w[node] = weight;
				pqs[treeNode[node]].add(node);
				if(isArticulationID[treeNode[node]] && p[treeNode[node]] != -1) pqs[p[treeNode[node]]].add(node);
				update(treeNode[node]);
				
				/*
				for(int k = 0; k < ID; k++) {
					System.out.println(k + ": ");
					for(int j : pqs[k]) {
						System.out.println("\t" + w[j]);
					}
				}
				*/
			} else {
				int a = sc.nextInt()-1;
				int b = sc.nextInt()-1;
				if(a != b)
					pw.println(query(treeNode[a], treeNode[b]));
				else 
					pw.println(w[a]);
			}
		}
		
		pw.close();
		
	}
	
	static TreeSet<Integer> pqs[];
	static Comparator<Integer> comp = new Comparator<Integer>() {
		public int compare(Integer a, Integer b) {
			if(w[a]==w[b]) return a-b;
			return w[a]-w[b];
		}
	};
	
	//HLD
	static int chain = 0;;
	static int index = 0;
	
	static void hld(int vert, int parent) {
		if(chainHead[chain] == -1) chainHead[chain] = vert;
		chainIndex[vert] = chain;
		toChain[vert] = index++;
		
		int heavyIndex = -1;
		int weight = -1;
		for(int next : treeEdges[vert]) {
			if(next == parent) continue;
			if(size[next] > weight) {
				weight = size[next];
				heavyIndex = next;
			}
		}
		
		if(heavyIndex >= 0) hld(heavyIndex, vert);
		
		for(int next : treeEdges[vert]) {
			if(next == parent) continue;
			if(next != heavyIndex) {
				chain++;
				hld(next, vert);
			}
		}
	}
	
	static void update(int u) {
		/*
		System.out.println(u);
		System.out.println(toChain[u]);
		System.out.println(pqs[u].first());
		System.out.println(w[pqs[u].first()]);
		System.out.println("ASDASDASD");
		*/
		tree.update(1, 0, ID-1, toChain[u], w[pqs[u].first()]);
		if(isArticulationID[u] && p[u] != -1) tree.update(1, 0, ID-1, toChain[p[u]], w[pqs[p[u]].first()]);
	}
	
	static int query(int u, int v) {
		int lca = getLCA(u, v);
		int ret = Integer.MAX_VALUE;
		ret = Math.min(ret, query_up(u, lca));
		ret = Math.min(ret, query_up(v, lca));
		ret = Math.min(ret, query_top(lca));
		if(!isArticulationID[lca] && p[lca] != -1) ret = Math.min(ret, query_top(p[lca]));
		
		return ret;
	}
	
	static int query_top(int u) {
		return tree.query(1, 0, ID-1, toChain[u], toChain[u]);
	}
	
	static int query_up(int u, int v) {
		int ret = Integer.MAX_VALUE;
		while (true) {
			if (chainIndex[u] == chainIndex[v]) {
				if(u == v) break;
				ret = Math.min(ret, tree.query(1, 0, ID - 1, toChain[v]+1, toChain[u]));
				break;
			}
			ret = Math.min(ret, tree.query(1, 0, ID - 1, toChain[chainHead[chainIndex[u]]], toChain[u]));
			u = p[chainHead[chainIndex[u]]];
		}
		
		return ret;
	}
	
	static int dfs_size(int node, int parent) {
		p[node] = parent;
		int sz = 1;
		
		for(int adj : treeEdges[node]) {
			if(adj != parent) sz += dfs_size(adj, node);
		}
		
		return size[node] = sz;
	}
	//HLD
	
	//LCA
	static void preorder(int vert, int parent) {
		toPreorder[vert] = time;
		fromPreorder[time] = vert;
		time++;
		
		for(int next : treeEdges[vert]) {
			if(next != parent) {
				preorder(next, vert);
			}
		}
	}
	
	static int tour_index = 0;
	
	static void eulerTour(int vert, int parent) {
		int preorder = toPreorder[vert];
		lca.update(1, 0, 2*ID-1, tour_index, preorder);
		firstOccurence[preorder] = tour_index;
		tour_index++;
		for(int next : treeEdges[vert]) {
			if(next != parent) {
				eulerTour(next, vert);
				lca.update(1, 0, 2*ID-1, tour_index, preorder);
				tour_index++;
			}
		}
		
	}
	
	static int getLCA(int u, int v) {
		int start = Math.min(firstOccurence[toPreorder[u]], firstOccurence[toPreorder[v]]);
		int end = Math.max(firstOccurence[toPreorder[u]], firstOccurence[toPreorder[v]]);

		return fromPreorder[lca.query(1, 0, 2 * ID - 1, start, end)];
	}
	//LCA
	
	//Segment Tree
	static class MINTree {
		
		int min[];
		
		public MINTree(int N) {
			min = new int[4*N];
		}
		
		public void update(int vert, int i, int j, int v, int a) {
			if(inside(i, j, v, v)) {
				min[vert] = a;
				return;
			}
			
			int mid = (i+j)/2;
			
			if(intersects(i, mid, v, v)) {
				update(vert*2, i, mid, v, a);
			}
			if(intersects(mid+1, j, v, v)) {
				update(vert*2+1, mid+1, j, v, a);
			}
			
			min[vert] = Math.min(min[vert*2], min[vert*2+1]);
		}
		
		public int query(int vert, int i, int j, int l, int r) { 
			if(inside(i, j, l, r)) {
				return min[vert];
			}
			
			int mid = (i+j)/2;
			int ret = Integer.MAX_VALUE;
			
			if(intersects(i, mid, l, r)) {
				ret = Math.min(ret, query(vert*2, i, mid, l, r));
			}
			if(intersects(mid+1, j, l, r)) {
				ret = Math.min(ret, query(vert*2+1, mid+1, j, l, r));
			}
			
			return ret;
		}
		
	}
	
	static boolean intersects(int i, int j, int l, int r) {
		return (j >= l) && (i <= r);
	}

	static boolean inside(int inI, int inJ, int l, int r) {
		return (inI >= l) && (inJ <= r);
	}
	//Segment Tree
	
	//BCC and Block-cut Tree
	
	static int ID = 0;
	static int time = 0;
	static int[] treeNode;
	static boolean[] isArticulation;
	
	static void dfs(int node) {
		disc[node] = low[node] = time++;
		visited[node] = true;
		int children = 0;
		
		for(int next : normalEdges[node]) {
			if(visited[next]) {
				if(parentDFS[next] != node && disc[next] < disc[node]) {
					low[node] = Math.min(low[node], disc[next]);
					s.push(new Edge(node, next));
				}
			} else {
				children++;
				Edge e = new Edge(node, next);
				
				s.push(e);
				
				parentDFS[next] = node;
				dfs(next);
				low[node] = Math.min(low[node], low[next]);
				
				if(parentDFS[node] == -1 && children > 1) {
					if(!isArticulation[node]) {
						isArticulation[node] = true;
						isArticulationID[ID] = true;
						treeNode[node] = ID++;
					}
					create(e);
				}
				if(parentDFS[node] != -1 && low[next] >= disc[node]) {
					if(!isArticulation[node]) {
						isArticulation[node] = true;
						isArticulationID[ID] = true;
						treeNode[node] = ID++;
					}
					create(e);
				}
			}
		}
	}
	
	static void addEdge(int artID, int bccID) {
		treeEdges[artID].add(bccID);
		treeEdges[bccID].add(artID);
	}
	
	static void create(Edge stop) {
		while(!s.peek().equals(stop)) {
			Edge e = s.poll();
			if(!isArticulation[e.a]) treeNode[e.a] = ID;
			else addEdge(treeNode[e.a], ID);
			if(!isArticulation[e.b]) treeNode[e.b] = ID;
			else addEdge(treeNode[e.b], ID);
		}
		Edge e = s.poll();
		if(!isArticulation[e.a]) treeNode[e.a] = ID;
		else addEdge(treeNode[e.a], ID);
		if(!isArticulation[e.b]) treeNode[e.b] = ID;
		else addEdge(treeNode[e.b], ID);
		ID++;
	}
	
	static void getBiconnected(int start) {
		parentDFS[start] = -1;
		
		dfs(start);
		
		while(!s.isEmpty()) {
			Edge e = s.poll();
			if(!isArticulation[e.a]) treeNode[e.a] = ID;
			else addEdge(treeNode[e.a], ID);
			if(!isArticulation[e.b]) treeNode[e.b] = ID;
			else addEdge(treeNode[e.b], ID);
		}
		ID++;
	}
	
	static ArrayDeque<Edge> s = new ArrayDeque<Edge>(); 
	
	static class Edge {
		
		int a, b;
		public Edge(int a, int b) {
			this.a = a;
			this.b = b;
		}
		
		public boolean equals(Edge e) {
			return (e.a == a && e.b == b);
		}
		
		public String toString() {
			return (a+1) + " " + (b+1);
		}
		
	}
	
	//BCC and Block-cut Tree

	static class FastIO {

		//Is your Fast I/O being bad?

		InputStream dis;
		byte[] buffer = new byte[1 << 17];
		int pointer = 0;

		public FastIO(String fileName) throws Exception {
			dis = new FileInputStream(fileName);
		}

		public FastIO(InputStream is) throws Exception {
			dis = is;
		}

		int nextInt() throws Exception {
			int ret = 0;

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}

			return (negative) ? -ret : ret;
		}

		long nextLong() throws Exception {
			long ret = 0;

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}

			return (negative) ? -ret : ret;
		}

		byte nextByte() throws Exception {
			if (pointer == buffer.length) {
				dis.read(buffer, 0, buffer.length);
				pointer = 0;
			}
			return buffer[pointer++];
		}

		String next() throws Exception {
			StringBuffer ret = new StringBuffer();

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			while (b > ' ') {
				ret.appendCodePoint(b);
				b = nextByte();
			}

			return ret.toString();
		}

	}
}