给定一棵 $ n $ 个点的树。
- 称点集 $ S $ 连通，当且仅当 $ \forall u,v \in S $，所有 $ u $ 到 $ v $ 的简单路径上的点均在 $ S $ 中。
- 称点集 $ S $ 是 $ [l,r] $ 的虹，当且仅当 $ S $ 连通，且 $ S $ 包含 $ [l,r] $ 中的所有点。
- 称点集 $ S_0 $ 是 $ [l,r] $ 的最小虹，当且仅当 $ S_0 $ 是 $ [l,r] $ 的所有虹中大小最小的。可以证明，$ S_0 $ 是唯一的。
点带权，点 $ u $ 的权值为 $ w_u $，初始所有点权均为 $ 0 $。同时，给定序列 $ \{z_1,z_2,\cdots,z_n\} $。
给定 $ q $ 次命令，每次命令形如以下两类之一：
1 l r：令 $ S_0 $ 为 $ [l,r] $ 的最小虹，$ \forall u \in S_0 $，将 $ w_u $ 加 $ 1 $。2 l r u：求 $ \left(\sum_{i=l}^r 19901991^{z_{\gcd(i,u)} w_i} \right) \bmod {20242024} $ 的值。
输入格式
第一行两个正整数 $ n,q $。
第二行 $ n $ 个非负整数，依次表示 $ z_1,z_2,\cdots,z_n $。
接下来 $ n-1 $ 行，每行两个正整数 $ u,v $，描述一条树上从 $ u $ 到 $ v $ 的边。
最后 $ q $ 行，每行 $ 3 $ 或 $ 4 $ 个正整数，描述一次命令。
输出格式
对于每次询问（即第二类命令）输出答案。
样例一
input
5 4
1 0 0 0 1
1 2
1 3
3 4
3 5
1 2 3
2 1 3 3
1 4 5
2 3 5 3
output
19561959
19561959
限制与约定
本题采用捆绑测试。
对于所有测试数据保证：$ 1 \le n, q \le 8 \times 10^4,0 \le z_i \le 10^9 $，所有命令满足 $ 1 \le l \le r \le n, 1 \le u \le n $，保证第一类命令的 $ (l,r) $ 随机生成。随机生成方式如下：
- 在 $ [1,n] \cap \mathrm{Z} $ 中等概率随机生成 $ l $。
- 在 $ [1,n] \cap \mathrm{Z} $ 中等概率随机生成 $ r $。
- 若 $ l>r $，则交换 $ l,r $。
| 子任务编号 | 分值 | $ n \le $ | $ q \le $ | 特殊性质 | 子任务依赖 |
|---|---|---|---|---|---|
| $ 1 $ | $ 10 $ | $ 10^3 $ | $ 10^3 $ | 无 | 无 |
| $ 2 $ | $ 20 $ | $ 65536 $ | $ 65536 $ | A, B | 无 |
| $ 3 $ | $ 20 $ | $ 65536 $ | $ 65536 $ | A | 依赖于子任务 $ 2 $ |
| $ 4 $ | $ 30 $ | $ 65536 $ | $ 65536 $ | 无 | 依赖于子任务 $ 1,2,3 $ |
| $ 5 $ | $ 20 $ | $ 80000 $ | $ 80000 $ | 无 | 依赖于子任务 $ 1,2,3,4 $ |
特殊性质 A：保证所有第二类命令均在所有第一类命令之后。
特殊性质 B：保证第二类命令次数 $ \le 20 $。