勤奋的学生 Alikhan 在 Batyr II 王国学习。Batyr II 王国由 $n$ 个城市和 $m$ 条道路组成，其中第 $i$ 条道路的长度为 $w_i$。此外，从王国中的任何城市出发，都可以通过这些道路到达其他任何城市。换句话说，Batyr II 王国可以表示为一个具有 $n$ 个顶点和 $m$ 条边的连通加权无向图。

Alikhan 可能对在多个城市学习感兴趣。然而，由于时间和资源的限制，他不得不将范围缩小到其中一部分。Alikhan 尚未做出最终决定，因此会发生 $q$ 次以下事件之一：

1. Alikhan 改变了他想在城市 $x$ 学习的意愿（即，如果他之前想学习，则停止，反之亦然）。
2. Alikhan 决定他想住在第 $e$ 条道路上，并希望考虑正好 $k$ 个城市进行学习。设道路 $e$ 的长度为 $W$，其两端为城市 $A$ 和 $B$。为了选择居住地，Alikhan 首先选择一个整数 $x$ ($0 \le x \le W$)，然后在道路上选择一个位置，使得该位置到城市 $A$ 的距离为 $x$，到城市 $B$ 的距离为 $W - x$。设 $l$ 为 Alikhan 想学习的城市数量，$d_1, \dots, d_l$ 为从他的住处到这些城市的最短距离。将此列表按降序排列：$d_1 \ge d_2 \ge \dots \ge d_l$。

Alikhan 对 $d_k$ 的值感兴趣。他发现确定 $x$ 的值很困难，因此他想计算所有可能的 $0 \le x \le W$ 下 $d_k$ 值的总和。

请帮助 Alikhan 找到他问题的答案。

输入格式

第一行包含三个整数 $n, m$ 和 $q$ ($2 \le n \le 10^3, 1 \le m \le \min(\frac{n(n-1)}{2}, 10^3), 1 \le q \le 5000$)，分别表示城市、道路和事件的数量。

接下来的 $m$ 行，每行包含道路的 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^7$)，表示第 $i$ 条道路连接的城市编号及其长度（所有数字均为整数）。

接下来的 $q$ 行描述事件。首先给出一个整数 $t_i$ ($1 \le t_i \le 2$)，表示事件 $i$ 的类型。

如果 $t_i = 1$，则在同一行中额外给出一个整数 $x_i$ ($1 \le x_i \le n$)，表示 Alikhan 改变学习意愿的城市编号。

如果 $t_i = 2$，则在同一行中额外给出两个整数 $e_i$ 和 $k_i$ ($1 \le e_i \le m, 1 \le k_i \le 10$)，表示 Alikhan 想居住的道路编号以及他将考虑学习的城市数量。

最初，Alikhan 不想在任何地方学习。此外，保证在任何第二类事件 $i$ 期间，至少有 $k_i$ 个 Alikhan 想学习的城市。

输出格式

对于每个第二类事件，在单独的一行中输出答案。

子任务

设边的最大权重为 $L$。设在第二类事件发生时，Alikhan 想学习的城市最大数量为 $S$（注意，在所有事件开始前 $S = 0$）。

样例

输入 1

4 3 5
1 2 10
2 3 10
3 4 10
1 1
2 1 1
1 4
2 2 1
2 2 2

输出 1

55
195
135

说明

对于第二个事件，$d_k$ 的值将为 $[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$，其总和为 $55$。

对于第四个事件，$d_k$ 的值将为 $[20, 19, 18, 17, 16, 15, 16, 17, 18, 19, 20]$，其总和为 $195$。

对于第五个事件，$d_k$ 的值将为 $[10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10]$，其总和为 $135$。