Description

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

Input Format

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

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

Output Format

对每个 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

Hint

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$ 组数据。