题目背景

瞬间…

真要说的话，比瞬间还要短暂。

羽咲往悬崖的方向飞去。

瘦小的羽咲，比想象中更轻易地飞侠了悬崖。

我急忙跑向悬崖边。

然而，飞奔而出之后，方向并不是那么容易改变。

我失去了平衡，就这么摔倒在地。

只能一直用目光追寻着羽咲的身影。

飞出悬崖的羽咲。

身体浮在半空中。

在下一瞬间，便听任自由落体定律…径直坠下陡峭的悬崖

细长的双眼…注视着我的眼睛。

这是幻觉吗…还是现实…

卓司的指尖捅破了头盖骨…

这根本不可能的吧…人的手劲如何能够捏破头盖骨…

这毫无疑问是幻觉…不可能存在于现实中…

这种事，习武的我是最清楚不过的…

这种根本不可能的事…

尽管如此…

我的意识仍朦胧起来…

已经无法与这个世界保持联系了…

“我…收下皆守哥哥的身体了哦…”

司空见惯的风景。

比之前看到的风景更让人眼熟。

我所熟悉的风景…

“我会把他带走的…所以你走吧…”

“卓司…那个电波小子，就让我把他带走…”

“所以你就前进吧…”

“在无法登上的坡道的尽头”

“你不能停滞不前，必须前去迎接小羽”

“好啦，打起精神来…皆守”

“在这里告别吧…”

轻飘飘的感觉。

瞬间，感觉到了周围空气的急速变冷。

扬起的灰尘伴随月光的照耀，在空中废物。

告别了永不相交的平行，我和羽咲被吸进了…

垂直下落的世界。

月光映照出羽咲身体的轮廓。

地面没有影子。

宛如高空飞翔一般…

远方传来警笛声。

在苍穹之下反复回想。

我仰望无限的天空，笔直坠下。

一刻也不远看丢，在我上方的羽咲…

月在笑。

神在笑。

笑这滑稽的姿势。

笑这喜剧般的悲剧。

群星旋转。

如舞如蹈。

夜空上的神，正嘲弄着我们。

就想把空瓶子扔在地上的天真的孩子一样…

世界变得一片空虚。

望不到尽头的坡道…

遥远而模糊的坡道…

宛如…我们就漫步在这样的世界中一般…

就算在意坡道的前方也毫无用处。

我们就在这坡道上快乐地走着。

题目描述

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

输入格式

第一行两个整数 $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$ 组数据。