There 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*_{*x*_{1}}, *w*_{*x*_{2}}, ..., *w*_{*x*_{*k*}})$.
• 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.

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