Description

You are playing a galgame, and suddenly you hear that the Soviet Union has collapsed. So you realize that you will never see a living Soviet person again. Feeling depressed, you start writing a data structure problem:

This is a simulation problem.

You need to maintain a rooted ordered tree with $n$ nodes (that is, the children of each node have a left-to-right order). Initially, the root is $1$. You need to support the following operations:

A(x,y): Perform path compression on $x$, i.e., for every node on the path from $x$ to the root except the root, set its parent to the root. The order of these nodes among the root’s children remains the same as their order on the original path from shallow to deep.

B(x,y): Take the root’s children $x,y$ ($x$ is to the left of $y$) and all nodes between them, and expand them in order into a single path. $x$ remains connected to the root. All children that these involved nodes originally had are moved to the right side of the path.

C(x,y): Set the root of the tree to be $x$. At this time, nodes that were on the left side of the original path from the old root to $x$ remain on the left and their relative order does not change; similarly for the right side. After $x$ becomes the root, the children of $x$ are placed on the right side of the path from $x$ to the original root.

D(x,y): Add a number to the weight of every node on the path from $x$ to the root, and then query the sum of weights on the path from $x$ to the root.

E(x,y): It is guaranteed that $x$ and $y$ have the same parent and that $x$ is to the left of $y$. For every node between $x$ and $y$ (including $x,y$) among the children of $x$’s parent, add $x+y$ to its weight, and then query the sum of weights of these nodes.

F(x,y): Add $y$ as a child of $x$, at the far right. This operation is performed before all other operations and is used to describe the initial shape of the tree.

Input Format

The first line contains two integers $n,q$, representing the number of nodes in the tree and the number of operations.

The next $q$ lines each describe an operation.

Output Format

For each D or E operation, output one line: the result modulo $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

Constraints: $2\leq n\leq 10^5$，$n\leq q\leq 2\times 10^5$，$0\leq x,y \leq n$.

All operations are guaranteed to be valid.

For symmetry, all operations have two parameters $x,y$, but actually $y$ is not needed in operations A and C. The testdata guarantees that $y=0$ in these cases.

The first $n-1$ operations are all F operations, guaranteeing that after these $n-1$ operations you get a tree rooted at $1$, and no more F operations will appear afterwards.

Note that operations A, B, C, and F all have rules about the order of children. You may refer to the sample explanation for an intuitive understanding.

There are $10$ test groups.

Translated by ChatGPT 5