CF593D.Happy Tree Party

Bogdan has a birthday today and mom gave him a tree consisting of n vertecies. For every edge of the tree i, some number x__i was written on it. In case you forget, a tree is a connected non-directed graph without cycles. After the present was granted, m guests consecutively come to Bogdan's party. When the i-th guest comes, he performs exactly one of the two possible operations:

1. Chooses some number y__i, and two vertecies a__i and b__i. After that, he moves along the edges of the tree from vertex a__i to vertex b__i using the shortest path (of course, such a path is unique in the tree). Every time he moves along some edge j, he replaces his current number y__i by , that is, by the result of integer division y__i div x__j.
2. Chooses some edge p__i and replaces the value written in it x__p__i by some positive integer c__i < x__p__i.

As Bogdan cares about his guests, he decided to ease the process. Write a program that performs all the operations requested by guests and outputs the resulting value y__i for each i of the first type.

今天是博格丹的生日，妈妈送给他一棵包含 $n$ 个顶点的树。对于树中的每条边 $i$，其上写有一个数 $x_i$。提醒一下：树是一种无向、连通且无环的图。礼物赠送完毕后，依次有 $m$ 位客人来到博格丹的派对。第 $i$ 位客人到来时，恰好执行以下两种操作之一：

1. 选择一个数 $y_i$ 和两个顶点 $a_i$、$b_i$。随后，他沿着树中从顶点 $a_i$ 到顶点 $b_i$ 的最短路径（注意：树中任意两点间的最短路径唯一）遍历各条边。每当他经过某条边 $j$ 时，就将其当前数 $y_i$ 替换为 ，即整数除法 $y_i \div x_j$ 的结果。
2. 选择某条边 $p_i$，并将该边上原先写的值 $x_{p_i}$ 替换为某个正整数 $c_i$，其中 $c_i < x_{p_i}$。

由于博格丹十分关心他的客人，他决定简化这一过程。请编写一个程序，依次执行所有客人提出的操作，并对每一位执行第一类操作的客人 $i$，输出其最终得到的数值 $y_i$。

The first line of the input contains integers, n and m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000) — the number of vertecies in the tree granted to Bogdan by his mom and the number of guests that came to the party respectively.

Next n - 1 lines contain the description of the edges. The i-th of these lines contains three integers u__i, v__i and x__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i, 1 ≤ x__i ≤ 1018), denoting an edge that connects vertecies u__i and v__i, with the number x__i initially written on it.

The following m lines describe operations, requested by Bogdan's guests. Each description contains three or four integers and has one of the two possible forms:

• 1 a__i b__i y__i corresponds to a guest, who chooses the operation of the first type.
• 2 p__i c__i corresponds to a guests, who chooses the operation of the second type.

It is guaranteed that all the queries are correct, namely 1 ≤ a__i, b__i ≤ n, 1 ≤ p__i ≤ n - 1, 1 ≤ y__i ≤ 1018 and 1 ≤ c__i < x__p__i, where x__p__i represents a number written on edge p__i at this particular moment of time that is not necessarily equal to the initial value x__p__i, as some decreases may have already been applied to it. The edges are numbered from 1 to n - 1 in the order they appear in the input.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 200\,000$，$1 \leq m \leq 200\,000$）——分别表示 Bogdan 的妈妈赠予他的树的顶点数以及来参加派对的客人数量。

接下来的 $n-1$ 行描述树的边。其中第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $x_i$（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$，$1 \leq x_i \leq 10^{18}$），表示一条连接顶点 $u_i$ 与 $v_i$ 的边，其上初始写有数字 $x_i$。

随后的 $m$ 行描述客人们提出的操作请求。每行包含三个或四个整数，且具有以下两种形式之一：

• 1 a_i b_i y_i：表示一位客人选择第一类操作；
• 2 p_i c_i：表示一位客人选择第二类操作。

保证所有查询均合法，即满足：$1 \leq a_i, b_i \leq n$，$1 \leq p_i \leq n-1$，$1 \leq y_i \leq 10^{18}$，且 $1 \leq c_i < x_{p_i}$，其中 $x_{p_i}$ 表示在当前时刻边 $p_i$ 上所写的数字（该值不一定等于输入中给出的初始值 $x_{p_i}$，因为此前可能已对该边执行过若干次减法操作）。边按其在输入中出现的顺序编号为 $1$ 至 $n-1$。

For each guest who chooses the operation of the first type, print the result of processing the value y__i through the path from a__i to b__i.

对于每个选择第一种操作的客人，请输出将值 $y_i$ 沿从 $a_i$ 到 $b_i$ 的路径进行处理后得到的结果。

Initially the tree looks like this:

The response to the first query is: = 2

After the third edge is changed, the tree looks like this:

The response to the second query is: = 4

In the third query the initial and final vertex coincide, that is, the answer will be the initial number 20.

After the change in the fourth edge the tree looks like this:

In the last query the answer will be: = 3

最初，树的结构如下所示：

对第一个查询的回答是： = 2

在第三条边被修改后，树的结构如下所示：

对第二个查询的回答是： = 4

在第三个查询中，起点与终点重合，因此答案即为初始值 20。

在第四条边被修改后，树的结构如下所示：

在最后一个查询中，答案为： = 3