一棵 在 个点的树，每个点的初始权值为 。对于这棵树有 个操作，每个操作为以下四种操作之一：
+ u v c：将u到v的路径上的点的权值都加上自然数 ；
+ 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
第一行两个整数 ，。 接下来 行每行两个正整数 ，，描述这棵树。 接下来 行，每行描述一个操作。
对于每个 / 对应的答案输出一行一个整数表示答案。
/
3 2 1 2 2 3 * 1 3 4 / 1 1
4
的数据保证，，； 另外 的数据保证，，没有 - 操作，并且初始树为一条链； 另外 的数据保证，，没有 - 操作； 的数据保证，，。
-
