这是一道模(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$，在最右边，这个操作在其它所有操作之前进行，用于描述树的初始形态。

输入格式

第一行两个整数 $n,q$，分别表示树的结点数和操作次数。

接下来 $q$ 行，每行表示一个操作。

输出格式

对每个 D 或 E 操作，输出一行，表示答案对 $2^{32}$ 取模的结果。

样例数据

样例输入

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)

样例输出

36
42
56
89
95
105
90
61

子任务

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

$2\leq n\leq 10^5$，$n\leq q\leq 2\times 10^5$，$0\leq x,y \leq n$。

保证操作合法。

为了对称，所有操作都有两个参数 $x,y$，但实际上 A，C 操作中不需用到 $y$，数据保证此时 $y=0$。

前 $n-1$ 个操作一定是 F 操作，保证 $n-1$ 次操作后得到一棵以 $1$ 为根的树，且以后不会再出现 F 操作。

注意到 A，B，C，F 操作都有关于孩子顺序的规定，可以参照样例解释进行直观的理解。

共 $10$ 组数据。