Bajtazar 在圆周率日收到了一份礼物：一个包含 $n$ 个顶点的森林（无向无环图）。 在这个森林中，顶点编号为 $1$ 到 $n$，每条边都有一个正整数长度。此外，每个顶点都有一个用整数表示的颜色。初始时，所有顶点的颜色均为 $0$。

由于这份礼物是你送给 Bajtazar 的，你的任务是回答 Bajtazar 关于这个森林的查询。每个查询属于以下类型之一：

• $1 \ a_i \ b_i \ d_i$ – Bajtazar 在森林中添加一条连接顶点 $a_i$ 和 $b_i$ 的无向边，长度为 $d_i$。保证添加该边后，图仍不包含环。
• $2 \ a_i \ b_i$ – Bajtazar 从森林中删除连接顶点 $a_i$ 和 $b_i$ 的边。
• $3 \ v_i \ z_i \ k_i$ – Bajtazar 将所有从顶点 $v_i$ 出发，且距离 $v_i$ 不超过 $z_i$ 的可达顶点的颜色修改为 $k_i$。此处两点间的距离定义为它们之间唯一简单路径上所有边的长度之和。
• $4 \ u_i$ – Bajtazar 询问你顶点 $u_i$ 当前的颜色。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$)，分别表示森林中的顶点数、初始边数以及查询次数。

接下来的 $m$ 行描述了森林的初始边。第 $i$ 行包含三个整数 $a_i, b_i$ 和 $d_i$ ($1 \le a_i, b_i \le n$; $1 \le d_i \le 10^9$)，表示顶点 $a_i$ 和 $b_i$ 之间连接有一条长度为 $d_i$ 的边。

接下来的 $q$ 行描述了查询，格式如题目所述。在所有查询中，$1 \le a_i, b_i, v_i, u_i \le n$，$1 \le d_i \le 10^9$，$0 \le z_i \le 10^{15}$ 以及 $1 \le k_i \le 10^9$。

保证给定的 $m$ 条边构成一个合法的森林，且每次修改后图仍保持为森林。保证不会出现删除当前森林中不存在的边的查询。 同时保证至少会出现一次第四类查询。

输出格式

输出应包含与第四类查询次数相同的行数。每一行包含一个整数，即 Bajtazar 询问的顶点的颜色。

样例

输入 1

4 2 9
1 2 2
3 2 5
4 2
3 2 2 5
4 1
3 2 4 3
4 1
4 3
2 2 1
1 1 4 1
4 4

输出 1

0
5
3
0
0

子任务

• 在某些测试组中，没有第一类和第二类查询，且满足 $m = n - 1$。
• 在某些测试组中，所有第三类查询均满足 $z_i = 10^{15}$。

对于上述每种情况，至少存在一个满足该条件的测试组。这些条件对应的测试组可能重叠，也可能不重叠。