给出一棵包含 $n$ 个点的树。

有 $Q$ 次询问，每次询问给出三个整数 $k, m, r$，随后给出 $k$ 个树上的节点 $a_1, a_2, \cdots, a_k$。假设树的根为 $r$，我们需要将这 $k$ 个节点划分成至多 $m$ 组，并且：

• 每个节点必须恰好属于一个组，每个组至少包含一个节点。
• 在任意组内，不能存在两个不同的节点，使得其中一个点是另一个点的祖先。

你需要求出分组的方案数，答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n, Q \leq 10^5$，$1 \leq k, r \leq n$，$1 \leq m \leq \min(300, k)$，$1 \leq \sum k \leq 10^5$。

时空限制：$1.5$s / $256$MiB。

维护 $n$ 个初始为空的可重集。有 $Q$ 次操作，每次操作形如以下四种之一：

• 1 x v：令集合 $x$ 等于 $\{v\}$。
• 2 x y z：令集合 $x$ 等于集合 $y$ 与 $z$ 的并。
• 3 x y z：令集合 $x$ 等于集合 $y$ 与 $z$ 的积，$A \times B = \{\gcd(a, b) \mid a \in A, b \in B\}$。
• 4 x v：询问 $v$ 在集合 $x$ 中出现次数模 $2$ 的结果。

数据范围：$1 \leq n \leq 10^5$，$1 \leq q \leq 10^6$，$1 \leq v \leq 7000$。

时空限制：$3$s / $250$MiB。

给出一个长度为 $n$ 的数组 $a$，记 $s_i = \sum_{j = 1}^i a_j$。

有 $Q$ 次操作，每次操作给出两个整数 $p, x$，表示将 $a_p$ 赋成 $x$。每次操作后，你都需要判断是否存在一个位置 $i$ 满足 $a_i = s_{i - 1}$。若存在，输出任意一个满足条件的 $i$。

数据范围：$1 \leq n, Q \leq 2\times 10^5$，$0 \leq a_i \leq 10^9$，$1 \leq p \leq n$，$0 \leq x \leq 10^9$。

时空限制：$3$s / $256$MiB。

对于一个长度为 $n$ 的排列 $p$，定义 $f(p)$ 表示：令 $g_i$ 表示 $p_1, \cdots, p_i$ 的最大公约数，则 $f(p)$ 表示 $g_1, g_2, \cdots, g_n$ 中不同元素的个数。

令 $f_{\max}(n)$ 表示所有关于 $n$ 的排列 $p$ 中的 $f(p)$ 最大值，求有多少个关于 $n$ 的排列 $p$ 满足 $f(p) = f_{\max}(n)$。答案对 $10^9 + 7$ 取模。

数据范围：$2 \leq n \leq 10^6$。

时空限制：$2$s / $256$MiB。

给出一棵包含 $n$ 个点的树，编号 $1 \sim n$。根节点为 $1$。

有 $Q$ 次操作，每次操作形如以下的三种之一：

• 1 u：设本次操作之前共有 $n'$ 个点，则新加入一个编号为 $n' + 1$ 的点，并且新点有一条连向 $u$ 的无向边。
• 2 u v c k：对于在从 $u$ 到 $v$ 的简单路径上的所有点，都会增加 $k$ 个类型 $c$ 的物品。
• 3 u c：查询点 $u$ 的子树内，有多少个物品的类型 $\leq c$。

本题强制在线。

数据范围：$1 \leq n \leq 3 \times 10^4$，$0 \leq Q \leq 10^5$，节点总数不超过 $5 \times 10^4$，$1 \leq k \leq 10^7$，$1 \leq c \leq 10^9$。

时空限制：$8$s / $1024$MiB。

给出一棵包含 $n$ 个点的树，初始时所有点均为白色。

有 $Q$ 次操作，每次操作形如一下的两种：

• 1 x：将点 $x$ 改成黑色。
• 2 x：对于点 $x$，找出编号最小的点 $y$，使得 $y$ 位于 $x$ 到某个黑色顶点的简单路径上。

**本题强制在线。**保证第一次操作的类型为操作 1。

数据范围：$3 \leq n, Q \leq 10^6$。

时空限制：$3$s / $256$MiB。

有 $n$ 个元素，第 $i$ 个元素有五个参数 $x_i, a_i, b_i, c_i, d_i$。

你需要求出一个 $1 \sim n$ 的排列 $p$，满足 $p_1 = s, p_n = e$，同时最小化这个排列的权值。一个排列的权值定义为 $\sum_{i = 1}^{n - 1} f(p_i, p_{i + 1})$，其中

• 若 $i > j$，则 $f(i, j) = x_i - x_j + c_i + b_j$。
• 若 $i < j$，则 $f(i, j) = x_j - x_i + d_i + a_j$。

你只需要求出排列的最小权值即可。

数据范围：$1 \leq n \leq 5 \times 10^3$，$s \neq e$，$1 \leq x_1 < x_2 < \cdots < x_n \leq 10^9$，$1 \leq a_i, b_i, c_i, d_i \leq 10^9$。

时空限制：$4$s / $250$MiB。

给出一个长度为 $n$ 的数组 $a$。

有 $Q$ 次查询，每次查询给出两个正整数 $l, r$ ($1 \leq l \leq r \leq n$)，你需要求出

$$\varphi \left( \prod_{i = l}^{r} a_i \right)$$

答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n, Q \leq 2 \times 10^5$，$1 \leq a_i \leq 10^6$，$1 \leq l \leq r \leq n$。

时空限制：$3$s / $256$MiB。

有 $m$ 个孩子，编号为 $1 \sim m$。

圣诞老人会 $n$ 种魔法，第 $i$ 种魔法可以给所有编号在区间 $[L_i, R_i]$ 内的孩子各发一个糖果。每种魔法最多使用一次，并且已知如果所有魔法都使用，每个孩子至多收到 $k$ 个糖果。

你可以控制这 $n$ 种魔法的使用情况，请你求出最多有多少个孩子收到奇数个糖果。

数据范围：$1 \leq n \leq 10^5$，$1 \leq m \leq 10^9$，$1 \leq k \leq 8$。

时空限制：$2$s / $500$MiB。

有 $n$ 个王子与 $m$ 个公主。每个公主有喜欢的两个王子，编号分别为 $a_i, b_i$，但一个王子只能娶一个公主，一个公主也只能嫁给一个王子。每个公主有一个嫁妆价值 $w_i$。

求国王能够得到的嫁妆最大值（允许有王子或公主无伴侣）。

数据范围：$2 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 2 \times 10^5$。

时空限制：$1.5$s / $500$MiB。