博格丹今天过生日,妈妈送给他一棵由 n 个顶点组成的树。对于树 i 的每条边,上面都写有一些数字 xi 。如果您忘记了,树是一个没有循环的连通无向图。礼物送完后,陆续有m位客人来到博格丹的聚会上。当第 i 位客人到来时,他执行以下两种可能操作之一:
1. 选择一些数字 yi 和两个顶点 ai 和 bi。之后,他使用最短路径沿着树的边从顶点ai移动到顶点bi(当然,这样的路径在树中是唯一的)。每次他沿着某条边 j 移动时,他都会将当前的数字 yi 替换为 $$y_i = \left\lfloor \frac{y_i}{x_j} \right\rfloor$$,即整数除法 yi div xj 的结果。
2. 选择某个边 pi 并将其中写入的值 xpi 替换为某个正整数 ci < xpi。
由于博格丹关心他的客人,他决定简化流程。编写一个程序,执行客人请求的所有操作,并输出第一种类型的每个 i 的结果值 yi 。
输入
输入的第一行包含整数 n 和 m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000) - 分别是 Bogdan 的妈妈授予他的树中的顶点数和参加聚会的客人数。
接下来的 n - 1 行包含边的描述。其中第 i 行包含三个整数 ui、vi 和 xi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ xi ≤ 1018),表示连接顶点 ui 和 vi 的一条边,上面最初写有数字 xi。
以下 m 行描述了博格丹的客人要求的操作。每个描述包含三个或四个整数,并具有两种可能的形式之一:
- 1 ai bi yi 对应一位客人,选择第一种操作。
- 2 pi ci 对应一位客人,选择第二种操作。
输出
对于每个选择第一种操作的客人,通过ai到bi的路径打印处理值yi的结果。
示例
输入 #1
6 6 1 2 1 1 3 7 1 4 4 2 5 5 2 6 2 1 4 6 17 2 3 2 1 4 6 17 1 5 5 20 2 4 1 1 5 1 3
输出 #1
2 4 20 3
输入 #2
5 4 1 2 7 1 3 3 3 4 2 3 5 5 1 4 2 100 1 5 4 1 2 2 2 1 1 3 4
输出 #2
2 0 2
注意
最初,树看起来像这样: 第一个查询的响应是: $$\left\lfloor \frac{\left\lfloor \frac{17}{4} \right\rfloor}{2} \right\rfloor$$ = 2第三条边更改后,树看起来像这样: 第二个查询的响应是: $$\left\lfloor \frac{\left\lfloor \frac{17}{2} \right\rfloor}{2} \right\rfloor$$ = 4在第三个查询中,初始顶点和最终顶点重合,即答案将是初始数字 20。在第四条边发生变化后,树如下所示: 在最后一个查询中,答案将是: $$\left\lfloor \frac { 3 } { 1 } \right\rfloor$$ = 3