小V和gcd树

题号：NC205044
时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

VMware实习生小V有一颗有n个结点的树，第 $i$ 结点具有点权 $a_i$ 。将边 $\langle i, j\rangle$ 的边权定义为 $a_i$ 与 $a_j$ 的最大公约数，即 $\gcd(a_i, a_j)$ 。有两种要处理的询问：

将结点 $u$ 的点权修改为 $x$ ，相应的边权也会发改变
回答在 $u$ 到 ${v}$ 的路径上有多少条边的边权不超过 $k$

输入描述:

第一行有两个整数，分别表示树的结点数和要处理的操作数
第二行给出n个整数，分别表示每个点初始点权
接下来n-1行每行2个整数  ，表示结点和结点之间具有边
接下来q行每行包含一个操作：
：如果操作用先给出一个整数1，然后紧跟着2个整数u,x，表示执行操作1
：如果操作先给出一个整数2，然后紧跟着3个整数u,v,k，表示执行操作2

输出描述:

对每一个第2类询问，输出一个整数，为对应的答案。

示例1

输入

复制

6 5 
3 6 4 9 9 9 
2 1
3 2
4 2
5 4
6 5 
2 4 2 2 
2 1 3 5 
1 3 4 
2 3 6 3 
2 2 3 4

输出

复制