给出一个长度为 $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。

给出两个森林，节点数均为 $n$，节点编号均为 $1 \sim n$。

你可以进行加边操作。每次操作，你需要选择两个不同的正整数 $x, y$，然后在两个森林中都加上 $(x, y)$。你需要保证两个森林在加边后仍然是森林。

求最多可以加几条边。并给出加边方案。

数据范围：$1 \leq n \leq 10^5$，$0 \leq m_1, m_2 < n$。

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

对于一个二进制字符串 $v$，定义其分数为

$$\max_{0 \leq i \leq |v|} \{ F(v, 1, i) \times F(v, i + 1, |v|) \}$$

其中 $F(v, l, r) = r - l + 1 - 2 \times \mathrm{zero}(v, l, r)$，这里 $\mathrm{zero}(v, l, r)$ 表示子串 $v[l : r]$ 中 0 的数量。

给出一个长度为 $n$ 的二进制字符串 $s$。

有 $Q$ 次操作，每次操作都会给出一个 $i$ ($1 \leq i \leq n$)，你需要将 $s_i$ 取反。每次操作结束后，你都需要求出 $s$ 的所有非空子序列的得分之和。答案对 $998244353$ 取模。

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

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

给出一个 $n \times m$ 的矩阵 $a$。

你可以进行若干次操作。每次操作，你可以选择任意一列，并循环移位该列中的元素。

设 $r_i$ 表示第 $i$ 行的最大值，求 $\sum_{i = 1}^n r_i$ 的最大值。

数据范围：$1 \leq n \leq 12$，$1 \leq m \leq 2000$，$1 \leq a_{i, j} \leq 10^5$。

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

给出一个包含 $n$ 个点 $m$ 条边的简单无向连通带权图。节点编号为 $1 \sim n$，其中恰好有 $k$ 个充电中心，编号为 $1 \sim k$。

有一个电池容量为 $c$ 的机器人在图中移动，任意时刻电量 $x$ 必须为区间 $[0, c]$ 中的整数。经过一条长度为 $w$ 的边需要消耗 $w$ 的电量，每当到达一个充电中心时，其电池将会充满。

有 $Q$ 次询问，每次询问给出 $a, b$，你需要求出机器人从 $a$ 到 $b$ 至少需要的电池容量 $c$ 是多少。

数据范围：$2 \leq k \leq n \leq 10^5$，$1 \leq m, Q \leq 3 \times 10^5$，$1 \leq w \leq 10^9$，$1 \leq a, b \leq k$，$a \neq b$。

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