Description

A tree with $n$ nodes, where each node’s initial weight is $1$.
There are $q$ operations on this tree, each being one of the following four types:

• + u v c: Add a natural number $c$ to the weight of every node on the path from $u$ to $v$.
• - u1 v1 u2 v2: Delete the existing edge $(u_1, v_1)$ from the tree and add a new edge $(u_2, v_2)$. It is guaranteed that after the operation it is still a tree.
• * u v c: Multiply the weight of every node on the path from $u$ to $v$ by a natural number $c$.
• / u v: Query the sum of the weights of all nodes on the path from $u$ to $v$, and output the answer modulo $51061$.

Input Format

The first line contains two integers $n, q$.

Each of the next $n-1$ lines contains two positive integers $u, v$, describing one edge of the tree.

Each of the next $q$ lines describes one operation.

Output Format

For each query operation, output one integer per line as the answer.

3 2
1 2
2 3
* 1 3 4
/ 1 1

4

Hint

Constraints

• For $10\%$ of the testdata, $1 \le n, q \le 2000$.
• For an additional $15\%$ of the testdata, $1 \le n, q \le 5 \times 10^4$, there are no - operations, and the initial tree is a chain.
• For an additional $35\%$ of the testdata, $1 \le n, q \le 5 \times 10^4$, there are no - operations.
• For $100\%$ of the testdata, $1 \le n, q \le 10^5$, $0 \le c \le 10^4$.

By (Wu Yiming).

Translated by ChatGPT 5