Description

A 国要举办世界杯了！

为了迎接世界杯的到来，A 国打算修建高铁连接所有举办城市。（A 国目前还没有修建高铁）

A 国有 $n$ 个城市，$m$ 条线路有条件修建高铁，每条线路有各自的修建难度系数。

为了更好地施工，A 国打算进口一台高级设备。但由于经费紧张，只能进口一台。如果进口了一台价格为 $V$ 的设备，那么该设备可以修所有难度系数不超过 $V$ 的路线。

此外，每个城市有一个繁荣程度。为了展现国家实力，A 国肯定要在最繁荣的几个城市举办比赛。但随着时间的推移，每个城市的繁荣程度也在不断发生变化。

作为 A 国元首，你想知道，在当前局面下，若选择最繁荣的 $k$ 个城市举办比赛，想用高铁连接这些城市，至少需要花费多少经费（购买设备）。

Format

Input

第一行三个整数 $n,m,q$ ($1\le n,q\le 5\times 10^5$; $n-1\le m\le \min\{\frac{n(n-1)}{2},5\times 10^5\}$)，分别表示城市的数量，线路的数量，询问的次数。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$)，表示每个城市的繁荣程度。

接下来 $m$ 行，每行三个正整数 $x_i,y_i,d_i$ ($1\le x_i,y_i\le n$; $x_i\ne y_i$; $1\le d_i\le 10^9$)，分别表示第 $i$ 条线路连接的两个城市的编号，以及该线路修建的难度系数。保证图联通，无重边自环。

接下来 $q$ 行，每行先输入一个正整数 $op_i$ ($1\le op_i\le 2$)。

如果 $op_i=1$，则接下来输入两个正整数 $c_i,t_i$ ($1\le c_i\le n$; $1\le t_i\le 10^9$)，表示编号为 $c_i$ 的城市繁荣程度变为了 $t_i$；

如果 $op_i=2$，则接下来输入一个正整数 $k_i$ ($1\le k_i\le n$)，询问当前局面下选择最繁荣的 $k_i$ 个城市举办比赛，至少需要花费多少经费。（如果两个城市的繁荣程度相同，则优先选择编号较小的城市）。

Output

对于每个询问，输出一行一个整数表示答案。

Samples

4 4 8
4 3 2 1
1 2 4
3 2 1
3 4 2
4 1 3
2 2
1 3 4
1 4 4
2 2
1 3 5
1 4 6
2 2
2 1

3
3
2
0