This is a simulation problem.

You need to maintain a rooted ordered tree with $n$ nodes (meaning the children of each node have a "left-to-right" order). The initial root is $1$. The following operations are supported:

A(x,y): Perform path compression on $x$. That is, set the parent of every node on the path from $x$ to the root (excluding the root itself) to be the root. The order of these nodes among the root's children remains the same as their shallow-to-deep order on the original path.

B(x,y): Expand the children of the root between $x$ and $y$ (inclusive, where $x$ is to the left of $y$) into a path in order. $x$ remains connected to the root, and the original children of the involved nodes are moved to the right side of the path.

C(x,y): Set the root of the tree to $x$. Nodes originally to the left of the path from the root to $x$ remain on the left with their relative order unchanged, and similarly for the right side. The children of $x$ will be on the right side of the path from $x$ to the original root after $x$ becomes the root.

D(x,y): Add a value to the node weights of all nodes on the path from $x$ to the root, then calculate the sum of node weights on the path from $x$ to the root.

E(x,y): It is guaranteed that $x$ and $y$ have the same parent and $x$ is to the left of $y$. For all nodes between $x$ and $y$ (inclusive) among the children of their parent, add $x+y$ to their node weights, then calculate the sum of the node weights of these nodes.

F(x,y): Add a child $y$ to $x$, placed at the rightmost position. This operation is performed before all other operations to describe the initial structure of the tree.

Input

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

The next $q$ lines each represent an operation.

Output

For each D or E operation, output one line representing the result modulo $2^{32}$.

Examples

Input 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)

Output 1

36
42
56
89
95
105
90
61

Subtasks

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$.

All operations are guaranteed to be valid.

For symmetry, all operations have two parameters $x$ and $y$, but in practice, the A and C operations do not require $y$; the data guarantees $y=0$ in these cases.

The first $n-1$ operations are always F operations, which are guaranteed to form a tree rooted at $1$ after $n-1$ operations, and no further F operations will occur.

Note that the A, B, C, and F operations all have rules regarding the order of children; you can refer to the example explanation for an intuitive understanding.

There are 10 test cases in total.