时间限制： 1.0 秒

空间限制： 512 MB

题目描述

给定 $n$ 个初始为空的栈，你需要维护 $m$ 个操作，每个操作为以下三种之一：

• $1~x~w~c$：在第 $x$ 个栈中加入 $c$ 个 $w$, 你需要回答加入后第 $x$ 个栈内的所有数之和；
• $2~x~c$：第 $x$ 个栈中弹出末尾 $c$ 个数（保证第 $x$ 个栈内有至少 $c$ 个数），你需要回答弹出 $c$ 个数之和；
• $3~x~y$：依次将第 $x$ 个栈的数弹出并加入到第 $y$ 个栈，你需要回答加入后第 $y$ 个栈内的所有数之和。

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n,m$，分别表示栈的个数和需要执行的操作个数。

接下来 $m$ 行，每行按上述格式描述一个操作。

输出格式

输出到标准输出。

输出 $m$ 行，每行一个非负整数表示对应操作应回答的结果。

3 7
1 1 3 2
1 2 2 3
1 2 4 1
3 2 3
2 3 2
3 3 1
2 1 4

6
6
10
10
4
12
12

样例 1 解释

• 第 $1$ 次操作后，第 $1$ 个栈变为 $3,3$，答案为 $3+3=6$；
• 第 $2$ 次操作后，第 $2$ 个栈变为 $2,2,2$，答案为 $2+2+2=6$；
• 第 $3$ 次操作后，第 $2$ 个栈变为 $2,2,2,4$，答案为 $2+2+2+4=10$；
• 第 $4$ 次操作依次弹出 $4,2,2,2$，操作后第 $2$ 个栈为空，第 $3$ 个栈变为 $4,2,2,2$，答案为 $4+2+2+2=10$；
• 第 $5$ 次操作依次弹出 $2,2$，操作后第 $3$ 个栈变为 $4,2$，答案为 $2+2=4$；
• 第 $6$ 次操作依次弹出 $2,4$，操作后第 $3$ 个栈变为空，第 $1$ 个栈变为 $3,3,2,4$，答案为 $3+3+2+4=12$；
• 第 $7$ 次操作依次弹出 $4,2,3,3$，操作后第 $1$ 个栈变为空，答案为 $4+2+3+3=12$。

子任务

对于所有测试数据，满足 $1\le n,m,w\le 2\times 10^5,~1\le x,y\le n,~x\ne y,~1\le c\le 10^8$。