题目描述
有一个 $n$ 个点的树，每条边有一个权值 $v$。现在给出 $q$ 组询问或操作。
每次询问：会从一个 $x$ 点走到 $y$ 点，初始在 $x$ 点我会有一个数字 $u$，然后每走过一条值为 $v$ 的边，$u$ 就会变成 $\lfloor \frac{u}{v} \rfloor$（下取整）,问最后到 $y$ 时 $u$ 变成了什么。
每次修改：将第 $d$ 条边的边权修改为 $c$ 保证修改后的权值小于等于原来的权值且不会小于 $1$。
输入
第一行两个整数 $n$ 和 $q$ 表示点个数和询问与操作个数。
接下来 $n-1$ 行每行三个整数 $a,b,v$ 表示 $a$ 与 $b$ 之间有一条边权为 $v$ 的边。
接下来 $q$ 行每行第一个数 $type$。
如果 $type=1$ 那么接下来三个数 $x,y,u$ 表示一组询问。
如果 $type=2$ 那么接下来两个数 $d,c$ 表示一组操作。
输出
对于每组询问输出一个数表示最后的答案。
样例输入输出
输入#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
提示
对于 $70\%$ 的数据，$1\leq n \leq 10^3$；
对于 $100\%$ 的数据: $1 \leq n \leq 10^5$，$1 \leq v \leq 10^{18}$。