Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Tourists

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are *n* cities in Cyberland, numbered from 1 to *n*, connected by *m* bidirectional roads. The *j*-th road connects city *a*_{j} and *b*_{j}.

For tourists, souvenirs are sold in every city of Cyberland. In particular, city *i* sell it at a price of *w*_{i}.

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 [
*x*_{1},*x*_{2}, ...,*x*_{k}], where*k*is a certain positive integer. - For any 1 ≤
*i*<*j*≤*k*,*x*_{i}≠*x*_{j}. - For any 1 ≤
*i*<*k*, there is a road connecting*x*_{i}and*x*_{i + 1}. - The minimum price of the route is
*min*(*w*_{x1},*w*_{x2}, ...,*w*_{xk}). - 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* ≤ 10^{5}), separated by a single space.

Next *n* lines contain integers *w*_{i} (1 ≤ *w*_{i} ≤ 10^{9}).

Next *m* lines contain pairs of space-separated integers *a*_{j} and *b*_{j} (1 ≤ *a*_{j}, *b*_{j} ≤ *n*, *a*_{j} ≠ *b*_{j}).

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* ≤ 10^{9}).

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].

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/24/2019 06:22:42 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|