[国家集训队] Tree II

题目描述

一棵 $n$ 个点的树,每个点的初始权值为 $1$。 对于这棵树有 $q$ 个操作,每个操作为以下四种操作之一: - `+ u v c`:将 $u$ 到 $v$ 的路径上的点的权值都加上自然数 $c$; - `- u1 v1 u2 v2`:将树中原有的边 $(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$,描述这棵树的每条边。 接下来 $q$ 行,每行描述一个操作。

输出格式


对于每个询问操作,输出一行一个整数表示答案。

输入输出样例

输入样例 #1

3 2
1 2
2 3
* 1 3 4
/ 1 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$。 By (伍一鸣)