题目描述

给定一棵 $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$ 个正整数，描述一次命令。

注意：本题输入文件行末有 \r，请选手自行过滤。

输出格式

对于每次询问（即第二类命令）输出答案。

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

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$。

特殊性质 A：保证所有第二类命令均在所有第一类命令之后。

特殊性质 B：保证第二类命令次数 $\le 20$。