题目描述

一棵 在 $n$ 个点的树，每个点的初始权值为 $1$。对于这棵树有 $q$ 个操作，每个操作为以下四种操作之一：

1. + u v c：将u到v的路径上的点的权值都加上自然数 $c$；

2. - u_1 v_1 u_2 v_2：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$ ，保证操作完之后仍然是一棵树；

3. * u v c：将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$；

4. / u v ：询问 $u$ 到 $v$ 的路径上的点的权值和，求出答案对于 $51061$ 的余数。

输入格式

第一行两个整数 $n$，$q$。
接下来 $n-1$ 行每行两个正整数 $u$，$v$，描述这棵树。
接下来 $q$ 行，每行描述一个操作。

输出格式

对于每个 / 对应的答案输出一行一个整数表示答案。

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

4

数据规模和约定

$10\%$ 的数据保证，$1 \leq n$，$q \leq 2000$；
另外 $15\%$ 的数据保证，$1 \leq n,q \leq 5 \times 10^4$，没有 - 操作，并且初始树为一条链；
另外 $35\%$ 的数据保证，$1 \leq n,q \leq 5 \times 10^4$，没有 - 操作；
$100\%$ 的数据保证，$1 \leq n,q \leq 10^5$，$0 \leq c \leq 10^4$。