Dynamic Tree Path Queries

You are given a tree with n nodes. Initially, every node has a weight of $$1$$. There will be q operations on the tree. The operations are one of the following four types:

• + u v c: For every node on the simple path from node u to node v, add the natural number $$c$$ to its weight.
• - u1 v1 u2 v2: Remove the edge between nodes $$u_1$$ and $$v_1$$, and add a new edge between nodes $$u_2$$ and $$v_2$$. It is guaranteed that after this operation the graph remains a tree.
• * u v c: For every node on the simple path from node u to node v, multiply its weight by the natural number $$c$$.
• / u v: Query the sum of the weights of all nodes on the simple path from node u to node v and output the result modulo $$51061$$.

Note: The simple path between two nodes in a tree is unique.

inputFormat

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

The next $$n-1$$ lines each contain two integers, which represent an edge connecting two nodes in the tree.

The following $$q$$ lines describe the operations. Each operation is one of the following:

+ u v c
- u1 v1 u2 v2
* u v c
/ u v

outputFormat

For each query operation of type / u v, output the result (the sum of weights in the path from u to v modulo $$51061$$) on a new line.

sample

5 5
1 2
2 3
3 4
4 5
+ 1 3 2
* 2 5 3
/ 1 5
- 2 3 2 5
/ 1 4

27
18