A10156 | 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_{pi}$ by some positive integer $c_{i}<x_{pi}$ .

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.

The first line of the input contains integers, $n$ and $m$ ( $2<=n<=200000$ , $1<=m<=200000$ ) — 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}<=10^{18}$ ), 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}<=10^{18}$ and $1<=c_{i}<x_{pi}$ , where $x_{pi}$ represents a number written on edge $p_{i}$ at this particular moment of time that is not necessarily equal to the initial value $x_{pi}$ , 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.

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}$ .