Rooted Ordered Tree Operations Simulation

You are given a rooted ordered tree with n nodes. The tree is rooted at node \(1\) and every node maintains an order among its children (from left to right). Each node also has an integer weight (initially 0). Initially the tree is built by a series of operations described below. After the tree is built, you must process a sequence of operations which modify the tree structure or perform queries.

The following operations are supported. In every operation, parameters x and y are given (even if one of them is not used by the operation):

• F(x, y): Add a new node with id y as a child of node x as its rightmost child. These operations are performed first to describe the initial tree structure.
• A(x, y): Path Compression. Let the path from node \(x\) to the root be \(x = v_0, v_1, \ldots, v_k\) where \(v_k=1\). For every \(v_i\) with \(0 \le i < k\), change its parent to be the root \(1\). When adding these nodes as children of the root, preserve their order from shallow (closer to the root) to deep (closer to \(x\)).
• B(x, y): Path Expansion. Assume that both x and y are children of the root and that x is to the left of y among the root's children. Remove the consecutive block of children from x to y (inclusive) from the root and reconnect them as a chain: set x as a direct child of the root; then for every \(i\) (starting from 1 in the block), set the parent of the \(i\)th node to be the previous node. (Any children that these nodes had remain attached to them.)
• C(x, y): Change Root. Change the root of the tree to node x. The unique simple path from the old root to \(x\) is inverted. In the new tree, the nodes that were to the left/right of the old path remain on the left/right respectively, and the old children of \(x\) will be placed to the right of the new chain. (See note below.)
• D(x, y): Path Weight Update. For every node on the simple path from \(x\) to the root (inclusive), add \(y\) to its weight. Then, output the sum of the weights on this path.
• E(x, y): Sibling Segment Update. Assume that nodes x and y have the same parent and that x is to the left of y in their parent's children ordering. For all nodes in the parent's children list between x and y (inclusive), add \(x+y\) (i.e. the sum of the identifiers) to each node's weight, and then output the sum of their weights.

Note: It is guaranteed that the operations are valid. In particular, the tree will always be nonempty and the structural operations (A, B, C) will be such that the described nodes exist and satisfy the stated conditions.

Input Format: The first line contains an integer Q, the number of operations. Each of the following Q lines contains an operation in the format: Op x y, where Op is one of the letters F, A, B, C, D, E. Operations are given in the order they should be processed. The F operations will come first to build the initial tree, followed by a mix of the other operations. For operations D and E, your program should output a result.

inputFormat

The input begins with a single integer \(Q\) representing the number of operations. Each of the next \(Q\) lines contains an operation in the format:

Op x y

where Op is one of {F, A, B, C, D, E}. The operations guarantee that:

• For F(x, y): node x already exists and node y is a new node.
• For A(x, y): node x exists in the tree.
• For B(x, y): both x and y are children of the root, with x to the left of y.
• For C(x, y): node x exists in the tree.
• For D(x, y): node x exists.
• For E(x, y): both nodes have the same parent and x is to the left of y.

outputFormat

For each operation of type D and E, output the corresponding computed integer on a separate line.

sample

5
F 1 2
F 1 3
F 1 4
D 2 10
E 2 3

20
20