你需要维护一棵带颜色的树并处理查询。

初始时，树上只有一个编号为 1 的顶点，其颜色为 $C$。随后有 $q$ 次操作，按顺序进行，操作分为两类：

• 0 x c d：向树中添加一个编号为 $(n + 1)$ 的新顶点，其颜色为 $c$，其中 $n$ 是当前已有的顶点数。同时添加一条连接顶点 $x$ 和 $(n + 1)$ 的边，长度为 $d$。
• 1 x c：将顶点 $x$ 的颜色修改为 $c$。

在每次操作后，你需要找到当前树中一对颜色不同的顶点 $u$ 和 $v$ ($1 \le u, v \le n$)，使得它们之间的距离尽可能大。

两个顶点 $u$ 和 $v$ 之间的距离是树上从 $u$ 到 $v$ 的最短路径长度。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $q$ 和 $C$ ($1 \le q \le 5 \times 10^5$, $1 \le C \le q$)，分别表示操作次数和顶点 1 的初始颜色。

接下来的 $q$ 行，每行描述一个按顺序进行的操作，包含 3 或 4 个整数。

• 如果第 $i$ 行包含 4 个整数 0、$x_i$、$c_i$ 和 $d_i$ ($1 \le x_i \le n$, $1 \le c_i \le q$, $1 \le d \le 10^9$)，则第 $i$ 次操作会添加一个颜色为 $c_i$ 的新顶点 $(n + 1)$，并将其与顶点 $x_i$ 连接，边长为 $d_i$。
• 如果第 $i$ 行包含 3 个整数 1、$x_i$ 和 $c_i$ ($1 \le x_i \le n$, $1 \le c_i \le q$)，则第 $i$ 次操作会将顶点 $x_i$ 的颜色修改为 $c_i$。

保证所有测试数据的 $q$ 之和不超过 $5 \times 10^5$。

输出格式

对于每次操作，输出颜色不同的两个顶点之间的最大距离。如果不存在符合条件的顶点对，则输出 0。

样例

输入 1

2
1 1
0 1 1 1
5 1
0 1 1 1
0 1 2 1
0 3 3 1
1 4 1
1 3 1

输出 1

0
0
2
3
2
0