给你一个有向图。图中的每条边都有其权重（weight）和优先级（priority）。如果第一条路径的边优先级序列在字典序上小于第二条路径的边优先级序列，则称第一条路径在字典序上小于第二条路径。

你需要编写一个程序来处理以下两种类型的询问：

1. 找到在所有从顶点 $v$ 出发的路径中，字典序第 $k$ 小的路径的边权重之和（空路径也包含在计数中），或者确定该路径不存在。
2. 将边 $e$ 的权重修改为 $w$。

输入格式

第一行包含三个整数 $n$、$m$ 和 $q$ —— 分别表示顶点数、边数和询问数（$1 \le n, q \le 10^5$；$1 \le m \le 10^6$）。

接下来的 $m$ 行，每行包含四个整数，描述一条边：$x_i$、$y_i$、$p_i$ 和 $c_i$ —— 分别表示起点顶点编号、终点顶点编号、优先级和权重（$1 \le x_i, y_i \le n$；$1 \le p_i \le m$；$0 \le c_i \le 10^6$）。所有优先级均不相同。

注意，允许存在自环和重边。

接下来的 $q$ 行，每行描述一个询问。第一个数字 $t_i$ 描述询问的类型。

• 如果 $t_i = 1$，则接下来有两个整数 $v_i$ 和 $k_i$ —— 顶点编号和路径排名（$1 \le v_i \le n$；$1 \le k_i \le 10^{12}$）。
• 如果 $t_i = 2$，则接下来有两个整数 $e_i$ 和 $w_i$ —— 边的编号和新的权重（$1 \le e_i \le m$；$0 \le w_i \le 10^6$）。

输出格式

对于每个第 1 类询问，在单独的一行中输出一个数字 —— 该询问的答案。如果不存在这样的路径，输出 -1。

样例

输入样例 1

3 4 6
1 2 2 1
2 2 4 10
2 3 3 100
1 3 1 1000
1 1 1
1 1 2
1 1 8
2 2 0
1 1 8
1 3 2

输出样例 1

0
1000
121
101
-1