有 $n$ 种物品，其中第 $i$ 种物品的重量为 $w_i$，每一种物品的数量都是无限的。

是否能恰好选 $n$ 个物品，使得所选物品的重量之和为 $m$。

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

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

This is an interactive problem.

一个机器人在一个无限大的二维平面的第一象限内移动。最初机器人位于坐标 $(s_x, s_y)$。最初所有单元格都是白色的。

游戏包含了若干次操作，最多 $T = 1000$ 次操作。每次操作都会按照以下顺序发生事件：

1. 你的操作：你可以选择一个整点坐标 $(x, y)$，其中 $1 \leq x, y \leq T$，你会将该单元格标记成黑色。
2. 机器人的操作：机器人可以移动到与其所在单元格八连通的单元格（由交互器决策）。
3. 结果检查：机器人移动到下一个单元格之后，系统会检查该单元格是否是黑色。

• 如果是黑色，机器人爆炸。
• 如果是白色，则进行下一次操作。

你的目标是在 $T$ 次操作之内使机器人爆炸。

数据范围 $1 \leq s_x, s_y \leq 20$。

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

给出一个长度为 $n$ 的数组 $a$，其中数组中的元素均为 $1 \sim m$ 中的正整数。

你需要找到四个不同的索引 $p, q, r, s$，使得 $\gcd(a_p, a_q) = 1$ 且 $\gcd(a_r, a_s) = 1$。

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

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

有 $n$ 个点，第 $i$ 个点的初始坐标为整点 $(x_i, y_i)$。

接下来有 $m$ 轮移动，每一轮中的所有 $n$ 个点 $(x, y)$ 都需要移动到 $(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)$ 四个位置的其中一个。

你需要求出有多少种不同的移动点的方式，使得最终 $n$ 个点两两曼哈顿距离小于等于 $k$。其中 $(x_1, y_1), (x_2, y_2)$ 的曼哈顿距离为 $|x_1 - x_2| + |y_1 - y_2|$。

数据范围：$1 \leq n \leq 50$，$1 \leq m \leq 10^5$，$0 \leq k \leq 10$，$0 \leq |x_i|, |y_i| \leq 10^5$。

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

给出一棵包含 $n$ 个点的树，每个节点有一种颜色 $c_i$。

有 $m$ 次查询，每次查询给出三个参数 $l, r, x$，表示询问只保留编号在 $[l, r]$ 范围内的点时，$x$ 所在连通块的颜色种类数。

数据范围：$1 \leq n, m \leq 10^5$，$1 \leq c_i \leq n$，$1 \leq l \leq x \leq r \leq n$。

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

对于一个包含字符串 $s_1, s_2, \cdots, s_k$ 的字符串可重集 $T$，定义 $T$ 的价值为

$$\sum\limits_{1 \leq i < j \leq k} \mathrm{LCP}(s_i, s_j)$$

给出一个长度为 $n$ 的字符串 $S$，下标从 $1$ 到 $n$。有一个初始为空的字符串集合 $T$。

有 $m$ 次操作，每次操作给出两个正整数 $l, r(1 \leq l \leq r \leq n)$，你需要将字符串 $S[l : r]$ 的所有前缀都加入集合 $T$。形式化地，对于所有 $l \leq i \leq r$，你需要将 $S[l : i]$ 加入集合 $T$。

每次操作过后，你都需要求出此刻集合 $T$ 的价值。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n, m \leq 10^5$。

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

给出一棵包含 $n$ 个节点的树，以 $1$ 为根，边带权。

定义 $\mathrm{dep}_x$ 表示节点 $x$ 到根的简单路径上的边权和。

有 $Q$ 次查询，每次查询给出两个参数 $l, r$，对于所有满足 $l \leq i, j \leq r$ 的二元组 $(i, j)$，你需要求出有多少种不同的 $\mathrm{dep}_{\mathrm{LCA}(i, j)}$。

数据范围：$1 \leq n \leq 10^5$，$1 \leq Q \leq 5 \times 10^5$，$-10^9 \leq w \leq 10^9$，$1 \leq l \leq r \leq n$。

时空限制：$500$ms / $512$MiB。

给出一个长度为 $n$ 的字符串 $S$。定义字典为 $S$ 的所有本质不同的子串构成的集合，定义单词为字典中的字符串。

有 $Q$ 次操作，每次操作会给出两个参数 $l, r$，你将会在字典中，学习以 $S[l : r]$ 为前缀的所有单词。每次操作结束后，你需要求出有多少个单词被你学习过。

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

数据范围：$4$s / $1024$MiB。

给出一棵包含 $n$ 个节点的树，以 $1$ 为根。

定义 $\mathrm{dep}_u$ 表示节点 $u$ 的深度，定义 $\mathrm{LCA}^{*}(l, r)$ 表示区间 $[l, r]$ 中所有节点的最近公共祖先。

有 $Q$ 次查询，每次查询给出三个整数 $l, r, k$，你需要求出

$$\max\limits_{l \leq l' \leq r' \leq r \land r' - l' + 1 \geq k} \mathrm{dep}_{\mathrm{LCA}^{*}(l', r')}$$

数据范围：$1 \leq n, Q \leq 5 \times 10^5$，$1 \leq l \leq r \leq n$，$1 \leq k \leq r - l + 1$。

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

给出一个长度为 $n$ 仅包含小写字符的字符串 $s$。

定义后缀 $i$ 的权值为 $w_i$，定义两个不同后缀 $i, j(i \neq j)$ 的贡献为 $\mathrm{LCP}(i, j) + (w_i \operatorname{xor} w_j)$。其中 $\mathrm{LCP}(i, j)$ 表示后缀 $i$ 和后缀 $j$ 的最长公共前缀长度。

你需要求出任意两个不同后缀 $i, j(i \neq j)$ 的贡献最大值。

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

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