tree

给定一棵包含 $n$ 个点的树，每个点的初始权值均为 $1$。你需要对这棵树执行 $q$ 次操作，每次操作为以下四种之一：

• $+\ u\ v\ c$：将从点 $u$ 到点 $v$ 的路径上所有点的权值加上自然数 $c$；
• $-\ u_1\ v_1\ u_2\ v_2$：删除树中原有的边 $(u_1,v_1)$，并加入一条新边 $(u_2,v_2)$。保证操作完成后，图仍然是一棵树；
• $*\ u\ v\ c$：将从点 $u$ 到点 $v$ 的路径上所有点的权值乘以自然数 $c$；
• $/\ u\ v$：询问从点 $u$ 到点 $v$ 的路径上所有点的权值之和，并输出该结果对 $51061$ 取余后的值。

输入格式

第一行包含两个整数 $n,q$，分别表示树的点数和操作数。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示树中存在一条连接点 $u$ 和点 $v$ 的边。

接下来 $q$ 行，每行描述一个操作，格式如题目描述所示。

输出格式

对于每个 $/\ u\ v$ 操作，输出一行，表示对应询问的答案。

样例输入

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

样例输出

4

数据范围

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

来源与许可

本题题面与测试数据整理自 BZOJ 2631。

样例 1

输入

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

输出

4