Bugcat 正在玩一个游戏。游戏提供了一个无向图，其中每个节点都有一只怪物。 一只怪物也可能拥有零个或一个随从（minion）。只有当你击败该节点上的所有敌人（包括随从，如果存在的话）时，该节点才被视为已解锁。当且仅当一个节点与至少一个已经解锁的节点相连时，你才能移动到该节点。

然而，当你访问一个节点时，并不一定需要击败所有的敌人。具体来说，你可以选择只击败怪物的随从，然后离开前往其他节点。在这种情况下，该节点仍然保持锁定状态。

玩家开始时拥有初始生命值 $x$。当尝试击败一个生命值为 $y$ 的敌人时，如果 $x \ge y$，则敌人被击败，玩家的生命值增加 $y$（即 $x \leftarrow x + y$）。否则，玩家会立即死亡。

猫猫虫（Maomaochong）向你寻求帮助。他提供了这个无向图以及每个节点上怪物的初始生命值（初始时，没有怪物拥有随从）。存在以下两种类型的多种操作：

1. 节点 $x$ 处的怪物召唤一个生命值为 $y$ 的随从（保证在整个游戏过程中，每个节点 $x$ 处的怪物最多只会召唤一次随从）。
2. 给定一个起点 $x$ 和初始生命值 $y$，计算玩家能够达到的最大可能最终生命值。

输入格式

第一行包含三个整数 $n, m, q$（$1 \le n, m, q \le 2 \times 10^5$），分别表示节点数、边数和操作数。

第二行包含 $n$ 个整数，表示每个节点上怪物的生命值 $h_i$（$1 \le h_i \le 10^6$）。

接下来的 $m$ 行，每行包含两个整数 $x, y$，表示节点 $x$ 和 $y$ 之间的一条无向边。图中不存在自环或重边。

接下来的 $q$ 行，每行以一个操作类型 $op$ 开头：

• 如果 $op = 1$：该操作为修改操作。接下来是两个整数 $x, y$（$1 \le x \le n, 1 \le y < h_x$）。节点 $x$ 召唤一个生命值为 $y$ 的随从。保证每个节点 $x$ 最多在类型 1 的操作中出现一次。
• 如果 $op = 2$：该操作为查询操作。接下来是两个整数 $x, y$（$1 \le x \le n, 1 \le y \le 10^6$）。你从节点 $x$ 出发，初始生命值为 $y$。

输出格式

对于每个查询操作，输出一个整数，表示最大可能的最终生命值。

样例

输入样例 1

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

输出样例 1

5
27
4