U416829 栈

**时间限制：** 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$ 行，每行一个非负整数表示对应操作应回答的结果。

### 样例 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$。 | 子任务编号 | 分值 | $n,m,w \le$ | $c \le$ | | :----: | :---: | :-----: | :-----: | | 1 |20 | $2000$ | $1$ | | 2|20 | $2000$ | $10^8$ | | 3|20 | $10^5$ | $1$ | | 4|20 | $10^5$ | $10^8$ | | 5|20 | $2 \times 10^5$ | $ 10^8$ |