C1546 [Ynoi]2016-F

您在打 galgame，突然听说苏联解体了，于是您发现您永远看不到一个活着的苏联人了，很郁闷，于是开始写一道数据结构题：

这是一道模（du）拟（liu）题。

你需要维护一棵包含 $n$ 个结点有根有序树（也就是说每个点的孩子是有“从左到右”的顺序的），初始根为 $1$，支持以下几个操作：

A(x,y)：对 $x$ 进行路径压缩，即将 $x$ 到根路径上除了根之外的点的父亲设为根，这些点在根的孩子中的顺序保持原先路径上从浅到深的顺序

B(x,y)：将根的孩子 $x,y$（$x$ 在 $y$ 左边）以及之间的点按顺序展开成一条路径，$x$ 仍与根相连，涉及到的点原先的孩子都移至路径右侧

C(x,y)：将树的根设为 $x$，此时原先在根到x路径左侧的点仍在左侧且先相对顺序不变，右侧同理，$x$ 的孩子在 $x$ 成为根后在 $x$ 到原先的根的路径的右侧

D(x,y)：给 $x$ 到根的路径上每个点的点权同时加一个数，并在这之后求 $x$ 到根的路径上的点权和

E(x,y)：保证 $x$ 和 $y$ 父亲相同且 $x$ 在 $y$ 左侧，对在 $x$ 的父亲的孩子中，$x$ 到 $y$ 之间（含 $x,y$）的每个点的点权加上 $x+y$，并在这之后求这些点的点权和

F(x,y)：给 $x$ 添加一个孩子 $y$，在最右边，这个操作在其它所有操作之前进行，用于描述树的初始形态

样例输入 1

20 30
F(1,2)
F(1,3)
F(1,7)
F(1,9)
F(9,5)
F(3,8)
F(3,20)
F(3,6)
F(8,15)
F(8,19)
F(20,14)
F(20,12)
F(6,13)
F(6,18)
F(13,4)
F(12,11)
F(12,17)
F(17,10)
F(17,16)
E(3,9)
E(8,6)
A(12,0)
D(4,6)
E(2,7)
B(3,12)
D(4,6)
C(8,0)
D(13,5)
D(1,7)
E(12,14)

样例输出 1

36
42
56
89
95
105
90
61