最自律的松鼠

Problem Description

松鼠的家住在一棵树上，这棵树有些特别。 树由 主干道 和 分支 构成，每条边有正边权，且：

• 树上初始只有两个点 $1, 2$，以及连接 $1,2$ 的一条边。
• 主干道初始为 $1,2$，起点为 $1$，初始末端为 $2$。 操作分为三种：
• 主干道拓宽：1 w，表示添加一个编号为 “总节点数+1” 的节点，与当前主干道的末端连接，边权为 $w$。新节点将成为新的主干道末端。
• 分支增加：2 x w，表示添加一个编号为 “总节点数+1” 的节点，连接在某个节点 $x$ 上，边权为 $w$，成为一个叶子。
• 查询：3，表示小松鼠提出一次提问。小松鼠每天需要进行跑步健身，它只会选择最长的树上路径去运动（但不一定是主干道）。而你作为小松鼠的粉丝，想知道，在哪些边上去等待小松鼠，才能保证遇到它。你需要回答一定能遇到小松鼠的边权总和。 任意时刻，保证主干道一定是树上最长的路径之一。

Input

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。 对于每组测试数据：

• 第一行两个正整数 $n, w$，表示操作数，以及初始 $1,2$ 的边权。
• 接下来 $n$ 行，每行形如：
• 1 w 表示主干道拓宽操作。
• 2 x w 表示分支增加操作。
• 3 表示查询操作。

Output

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

Sample Input

1
5 5
1 6
2 2 5
3
1 3
3

Sample Output

6
9

Hint

对于所有数据，$1\leq T\leq 5, 1\leq n\leq 5\times 10^5$，$1\leq w\leq 10^9$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）