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: 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 . 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. 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 ≤ 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. 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