Graph Queries with Value Updates

You are given an undirected graph with N nodes and M edges. Each node has an initial value. You will be given Q queries. There are two types of queries:

• update X V: Update the value of node X to V.
• sum A B: Find a path from node A to node B using a depth-first search (DFS) strategy and output the sum of the values of nodes along this path. It is guaranteed that there exists at least one path between any two nodes for which a query is asked.

Note: The DFS should stop as soon as it reaches the target node, and the sum is the accumulation of node values along that DFS path. All queries must be processed sequentially.

inputFormat

The first line of input contains three integers N, M, and Q, where N is the number of nodes, M is the number of edges, and Q is the number of queries.

The second line contains N integers representing the initial values of the nodes (1-indexed).

The following M lines each contain two integers u and v representing an edge between nodes u and v.

The next Q lines each contain a query in one of the following formats:

• update X V
• sum A B

outputFormat

For each sum query, output the sum of the node values along the DFS path from node A to node B on a separate line.

## sample

5 4 5
3 2 1 4 5
1 2
2 3
3 4
4 5
sum 1 5
update 3 10
sum 1 5
update 5 7
sum 1 5

15
24
26

</p>