Cinema Ticket Price Queries

You are given n cinemas and m bidirectional roads connecting some pairs of these cinemas. Each cinema has an associated ticket price. You need to handle q queries of two types:

• T a p: Update the ticket price of cinema a to p.
• B a b: Report the minimum ticket price encountered along a special path from cinema a to cinema b. The path is computed via a modified Dijkstra algorithm, where the cost of a path is the minimum ticket price seen on that path. More precisely, starting from cinema a with its ticket price, when moving to a neighbor cinema, the new cost is the minimum of the current cost and the neighbor's ticket price. The answer for the query is the value computed for cinema b using this procedure.

Note: If there is a direct road connecting a to b, one possible path is simply [a, b] with cost min(price[a], price[b]). However, the algorithm selects the first computed value using the above procedure. After any update query, the internal cached results (if any) are invalidated and subsequent queries will reflect the new ticket prices.

It is guaranteed that the graph is such that a path exists between any two cinemas queried with a 'B' query.

inputFormat

The input is given from stdin as follows:

1. The first line contains three integers n, m, and q — the number of cinemas, roads, and queries, respectively.
2. The second line contains n integers, where the i-th integer represents the initial ticket price of the i-th cinema.
3. The next m lines each contain two integers a and b, representing a bidirectional road between cinemas a and b.
4. The following q lines each represent a query in one of the following formats:
   • B a b — a query asking for the computed ticket price along the path from cinema a to cinema b.
   • T a p — an update query that sets the ticket price of cinema a to p.

outputFormat

For each query of type B, output the resulting ticket price on a separate line to stdout.

## sample

3 3 3
5 3 7
1 2
2 3
1 3
B 1 3
T 2 1
B 1 3

3
1

</p>