{"raw_statement":[{"iden":"statement","content":"给定一棵 $n$ 个点的树。\n\n- 称点集 $S$ **连通**，当且仅当 $\\forall u,v \\in S$，所有 $u$ 到 $v$ 的简单路径上的点均在 $S$ 中。\n- 称点集 $S$ 是 $[l,r]$ 的**虹**，当且仅当 $S$ **连通**，且 $S$ 包含 $[l,r]$ 中的所有点。\n- 称点集 $S_0$ 是 $[l,r]$ 的**最小虹**，当且仅当 $S_0$ 是 $[l,r]$ 的所有**虹**中大小最小的。可以证明，$S_0$ 是唯一的。\n\n点带权，点 $u$ 的权值为 $w_u$，初始所有点权均为 $0$。同时，给定序列 $\\{z_1,z_2,\\cdots,z_n\\}$。\n\n给定 $q$ 次命令，每次命令形如以下两类之一：\n\n- `1 l r`：令 $S_0$ 为 $[l,r]$ 的**最小虹**，$\\forall u \\in S_0$，将 $w_u$ 加 $1$。\n- `2 l r u`：求 $\\left(\\sum_{i=l}^r 19901991^{z_{\\gcd(i,u)} w_i} \\right) \\bmod {20242024}$ 的值。"},{"iden":"input","content":"第一行两个正整数 $n,q$。\n\n第二行 $n$ 个非负整数，依次表示 $z_1,z_2,\\cdots,z_n$。\n\n接下来 $n-1$ 行，每行两个正整数 $u,v$，描述一条树上从 $u$ 到 $v$ 的边。\n\n最后 $q$ 行，每行 $3$ 或 $4$ 个正整数，描述一次命令。\n\n**注意：本题输入文件行末有 `\\r`，请选手自行过滤。**"},{"iden":"output","content":"对于每次询问（即第二类命令）输出答案。"},{"iden":"note","content":"**本题采用捆绑测试**。\n\n对于所有测试数据保证：$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)$ 随机生成**。随机生成方式如下：\n- 在 $[1,n] \\cap \\mathrm{Z}$ 中等概率随机生成 $l$。\n- 在 $[1,n] \\cap \\mathrm{Z}$ 中等概率随机生成 $r$。\n- 若 $l>r$，则交换 $l,r$。\n\n| 子任务编号 | 分值 | $n \\le$ | $q \\le$ | 特殊性质 | 子任务依赖 |\n| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :----------: |\n| $1$ | $10$ | $10^3$ | $10^3$ | 无 | 无 |\n| $2$ | $20$ | $65536$ | $65536$ | A, B | 无 |\n| $3$ | $20$ | $65536$ | $65536$ | A | 依赖于子任务 $2$ |\n| $4$ | $30$ | $65536$ | $65536$ | 无 | 依赖于子任务 $1,2,3$ |\n| $5$ | $20$ | $80000$ | $80000$ | 无 | 依赖于子任务 $1,2,3,4$ |\n\n特殊性质 A：保证所有第二类命令均在所有第一类命令之后。\n\n特殊性质 B：保证第二类命令次数 $\\le 20$。"}],"translated_statement":null,"sample_group":[["5 4\n1 0 0 0 1\n1 2\n1 3\n3 4\n3 5\n1 2 3\n2 1 3 3\n1 4 5\n2 3 5 3","19561959\n19561959"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}