有 $n$ 座金矿排成一行，每座金矿有一个属性 $a_i$，表示该金矿一天产出的金币数量。每座金矿都潜伏着一只有属性 $b_i$ 的哥布林，代表该哥布林的贪婪值。

每天夜晚都会发生以下的事件：你将从第 $1$ 座金矿走到第 $n$ 座金矿，初始金币为 $0$，每走过一座金矿 $i$，以下两件事情依次发生：

• 你将获得 $a_i$ 金币。
• 哥布林向你索要 $b_i$ 金币，若你没有 $b_i$ 金币则需要将所有金币交给哥布林。

你需要在这里 $m$ 天，每天都会进行以下操作中的一种：

• 1 x y：令 $a_x = y$，修改是持久的。
• 2 x y：令 $b_x = y$，修改是持久的。
• 3 x：版本回到第 $x$ 天。
• 4 k p1 p2 ... pk：有 $k$ 个位于金矿 $p_1, p_2, \cdots, p_k$ 的哥布林向你索要金币的方式变为“若你目前拥有 $s$ 金币，它们将要向你索要 $\left\lceil \frac{s}{2} \right\rceil$ 金币”，变化是临时的。你需要求出当晚要交给哥布林多少金币。

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