Taco Kingdom Gold Queries

In the Kingdom of Taco, there are \(N\) villages and \(M\) one-way roads connecting them. Each village initially has a specified amount of gold. You will be given \(Q\) queries. There are two types of queries:

• Update Query: 'U v g' — update the gold amount of village \(v\) to \(g\).
• Path Query: 'Q x y' — find the maximum gold value encountered along any valid path from village \(x\) to village \(y\). A valid path is a sequence of directed roads connecting the two villages. If no such path exists, output \(-1\).

For example, if the initial gold array is [3, 4, 2, 5], and the roads are as follows:

1 \(\rightarrow\) 2, 2 \(\rightarrow\) 3, 3 \(\rightarrow\) 4, and 1 \(\rightarrow\) 3, then:

Query: Q 1 4 returns 5. After an update U 3 6, Query Q 1 4 returns 6.

You need to process these queries one by one, making sure to apply updates immediately so that subsequent queries use the updated gold values.

inputFormat

The input is given in the following format:

N M Q
G1 G2 ... GN
u1 v1
u2 v2
... (M lines, each with two integers representing a directed road from u to v)
Query1
Query2
... (Q queries, each in one line in one of the following formats: "U v g" or "Q x y")

Here, for a query of type "U", the gold value of village v is updated to g, and for a query of type "Q", you must output the maximum gold on any valid path from village x to village y. If there is no path, output -1.

outputFormat

For each query of type "Q", output the result on a separate line. There is no output for update queries.

## sample

4 4 3
3 4 2 5
1 2
2 3
3 4
1 3
Q 1 4
U 3 6
Q 1 4

5
6

</p>