I. Bugcat's Adventure
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bugcat is playing a game. The game provides an undirected graph where each node contains a monster. A monster may also have zero or one minion. A node is considered unlocked only after you defeat all enemies (including the minion, if it exists) at that node. You can move to a node if and only if it is connected to at least one already unlocked node.

However, you do not necessarily need to defeat all enemies when you visit a node. Specifically, you may choose to defeat only the monster's minion and then leave for other nodes. In this case, the node remains locked.

The player starts with an initial HP $$$x$$$. When attempting to kill an enemy with HP $$$y$$$, if $$$x \ge y$$$, the enemy is defeated and the player's HP increases by $$$y$$$ (i.e., $$$x \leftarrow x + y$$$). Otherwise, the player dies immediately.

Maomaochong asks for your help. He provides the undirected graph and the initial HP of the monster at each node (initially, no monsters have minions). There are multiple operations of two types:

  1. The monster at node $$$x$$$ summons a minion with HP $$$y$$$ (it is guaranteed that each monster at node $$$x$$$ will summon at most one minion throughout the game).
  2. Given a starting node $$$x$$$ and an initial HP $$$y$$$, calculate the maximum possible final HP the player can achieve.
Input

The first line contains three integers $$$n, m, q$$$ ($$$1 \le n, m, q \le 2 \times 10^5$$$), representing the number of nodes, edges, and queries.

The second line contains $$$n$$$ integers representing the health of the monster at each node $$$h_i$$$ ($$$1 \le h_i \le 10^6$$$).

The next $$$m$$$ lines each contain two integers $$$x, y$$$ representing an undirected edge between node $$$x$$$ and $$$y$$$. There are no self-loops or multiple edges.

The next $$$q$$$ lines start with an operation type $$$op$$$:

  • If $$$op = 1$$$: The operation is modify. Two integers $$$x, y$$$ follow ($$$1 \le x \le n, 1 \le y \lt h_x$$$). Node $$$x$$$ summons a minion with health $$$y$$$. It is guaranteed that each node $$$x$$$ will appear in a Type 1 query at most once.
  • If $$$op = 2$$$: The operation is query. Two integers $$$x, y$$$ follow ($$$1 \le x \le n, 1 \le y \le 10^6$$$). You start at node $$$x$$$ with health $$$y$$$.
Output

For each Query, output a single integer representing the maximum possible final health.

Example
Input
5 5 5
1 2 6 6 8
1 2
1 3
1 4
4 5
3 5
2 2 2
1 3 2
2 2 2
1 4 5
2 4 4
Output
5
27
4