题目背景

“我是在表扬你们”

“直接把你们从窗户扔到流亭小学”

“连电脑都不会修你们信息是不是白学了”

题目描述

你是一名信息学奥赛生，语文老师正追着你去修电脑。

你来到了流亭小学，语文老师为了阻拦你，在流亭小学操场中央生成了一个由 $n$ 个点组成的魔法点阵，由于语文老师不会修电脑，魔法点阵的点权永远无法超过 $m$ 且会自行对 $m$ 取模，且只有 $n-1$ 条边。紧接着，点阵开始变化，在接下来的 $t$ 秒内，每秒进行一次操作，具体操作如下：

• C x y u v 将 $u$ 和 $v$ 两个点之间的边删除（若不存在则无需更改），并将 $x$ 和 $y$ 两个点连接起来（若已经存在一条边则无需连接）。

• P x y z 将从 $x$ 到 $y$ 的路径上的所有点权值加 $z$。

• M x y z 将从 $x$ 到 $y$ 的路径上的所有点权值乘 $z$。

• O x y 将从 $x$ 到 $y$ 的路径上的所有点魔法值之和对 $m$ 取模后输出。

情势危急，为了逃离语文老师，请你尽快完成这个任务。

输入格式

第一行输入三个整数 $n$，$t$，$m$；

接下来 $n - 1$ 行每行输入两个数 $u$，$v$，表示两个点之间有连边；

接下来 $t$ 行每行输入一次操作（见题目描述）。

输出格式

对于每个 O 操作，输出魔法值之和。

样例1

3 2 3
1 2
2 3
M 1 3 4
O 1 1

1

样例2

3 30 47
2 1
3 2
M 3 3 6
M 1 3 3
P 2 1 2
M 1 1 9
M 3 1 3
M 2 1 1
M 3 3 2
O 2 3
M 1 3 7
P 2 2 6
O 1 3
P 3 1 5
P 2 2 6
P 3 2 2
O 1 2
M 3 1 1
M 2 3 7
P 3 1 5
M 3 2 7
P 2 3 8
M 2 2 8
P 2 2 3
O 3 2
O 1 3
M 3 1 5
O 3 1
P 1 1 8
P 3 2 3
M 3 2 4
M 2 1 10

29
26
40
46
14
23

样例3

见选手目录下的 standing/standing.in 和 standing/standing.out。

提示

对于前 $10\%$ 的数据，$1\le n，t \le 2000$；

对于另外 $30\%$ 的数据，$1 \le n，t \le 1\times 10^4$ 且满足特殊性质

对于另外 $40\%$ 的数据，$1 \le n，t \le 5\times 10^4$ 且满足特殊性质

对于 $100\%$ 的数据，$1\le n，t \le 10^5$，$0\le z \le 10^4$，$m$ 在 $\text{int}$ 范围内。

特殊性质：由于语文老师 ppt 坏掉了，无法进行 C 操作。