松鼠的家住在一棵树上，这棵树有些特别。

树由主干道和分支构成，每条边有正边权，且：

• 树上初始只有两个点 $1,2$，以及连接 $1,2$ 的一条边。
• 主干道初始为 $1,2$，起点为 $1$，初始末端为 $2$。

操作分为三种：

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

任意时刻，保证主干道一定是树上最长的路径之一。

输入格式

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

对于每组测试数据：

第一行两个正整数 $n,w$，表示操作数，以及初始 $1,2$ 的边权。

接下来 $n$ 行，每行形如：

• 1 w 表示主干道拓宽操作。
• 2 x w 表示分支增加操作。
• 3 表示查询操作。

输出格式

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

样例

输入

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

输出

6
9

提示

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