title: [CEOI2021] Stones

background: 译自 CEOI2021 Day2 T1. [Stones](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf)。

description:
Ankica 终于抓住 Branko，但他拒绝给 Ankica 买报纸并且要求自己提出一个新的游戏因为上一个是不公平的。Ankica 故作天真地提出了另一个石子游戏，但 Branko 内心存疑，并决定完全改变它的规则。

游戏包含 $N$ 堆石子，其中第 $i$ 堆有 $a_i$ 个石子，玩家轮流移除一堆石子中的若干个，取到最后一个石子的玩家获胜。

但在该游戏中每个玩家从哪堆石子中取石子是由另一名玩家固定的。

具体来说，游戏的回合数从 $1$ 开始每次递增，增量为 $1$，而游戏将会以如下方式进行：

- 在奇数回合，Branko 将指定一个非空石子堆。Ankica 将移除这堆石子至少一个，至多所有石子。
- 在偶数回合，Ankica 将指定一个非空石子堆。Branko 将移除这堆石子至少一个，至多所有石子。

作为专业的游戏玩家，在 Branko 摆完石子后，Ankica 很快意识到这个游戏对她有必胜策略。

如果你是 Ankica，你能否获胜呢？

#### 交互方式

这是一道交互题，你的程序必须与官方给出的扮演 Branko 的程序交换信息。当然，你的程序应该扮演 Ankica 的角色并确保她能获胜。

你的程序应先从标准输入读入游戏的初始状态。初始状态有两行，第一行包含一个整数 $N$ ，第二行包含 $N$ 个空格隔开的整数，其中第 $i$ 个表示 $a_i$，含义如题面所示。

你的程序应根据现在是奇数或偶数轮给出不同的输出，具体地：

**在奇数轮：**

- 你的程序应先读入一个整数 $k$。如果此时所有的石子堆都是空的，$k=-1$，你应结束程序因为你已经输了。否则 $k\in[1,N]$ ，代表你现在必须从第 $k$ 堆石子取走至少一个至多所有石子。保证第 $k$ 堆石子此时不为空。令当前第 $k$ 堆石子有 $s_k$ 个石子。
- 你的程序应输出一行一个 $[1,s_k]$ 中的整数，代表你从第 $k$ 堆石子希望取走的石子个数，**然后刷新缓冲区**。

**在偶数轮：**

- 你的程序应先输出一个整数 $k$，**然后刷新缓冲区**。如果此时所有的石子堆都是空的，$k$ 应为 $-1$，你应结束程序因为你已经赢了。否则 $k\in[1,N]$，代表你希望 Branko 从第 $k$ 堆石子取石子。你应保证第 $k$ 堆石子此时不为空。令当前第 $k$ 堆石子有 $s_k$ 个石子。
- 你的程序应读入一行一个 $[1,s_k]$ 中的整数，代表 Branko 从第 $k$ 堆石子取走的石子个数。

保证给出的初始状态使得无论 Branko 怎么操作你都有必胜策略。

#### 交互样例1

|    输出     |     输入     |                 解释                  |
| :---------: | :----------: | :-----------------------------------: |
|             | $\texttt{1}$ |          游戏只有一堆石子           |
|             | $\texttt{4}$ |      这一堆石子堆包含 $4$ 个石子      |
|             |  $\texttt1$  | Branko 只能指定 Ankica 从第一堆取石子 |
| $\texttt4$  |              |       Ankica 拿走第一堆所有石子       |
| $\texttt-1$ |              |    现在没有剩余的石子，Ankica 获胜    |

#### 交互样例2

|     输出      |       输入       |               解释                |
| :-----------: | :--------------: | :-------------------------------: |
|               |   $\texttt{3}$   |         游戏有三堆石子          |
|               | $\texttt{1 1 5}$ |  三堆石子依次包含 $1,1,5$ 个石子  |
|               |   $\texttt{3}$   | Branko 指定 Ankica 从第三堆取石子 |
| $\texttt{5}$  |                  |     Ankica 拿走第三堆所有石子     |
| $\texttt{1}$  |                  | Ankica 指定 Branko 从第一堆取石子 |
|               |   $\texttt{1}$   |   Branko 只能拿走第一堆所有石子   |
|               |   $\texttt{2}$   | Branko 指定 Ankica 从第二堆取石子 |
| $\texttt{1}$  |                  |     Ankica 拿走第二堆所有石子     |
| $\texttt{-1}$ |                  |  现在没有剩余的石子，Ankica 获胜  |


title: [ZYOI Round1] Bird/鸟

type: P

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/hdzxjtsk.png)

江豚吹浪立，沙鸟得鱼闲。

description:
有一只鸟在 $n$ 棵树之间飞行，第 $i$ 棵树的高度为 $a_i$，从左到右排列。这只鸟太肥了，不能往高处飞，只能朝左或右两个方向滑翔。

若这只鸟现在站着的树高度为 $a_i$，那么这只鸟可以飞到的树高度必须小于 $a_i$，且飞行时经过的树高度也都需要小于 $a_i$。

这只鸟有 $k$ 张瞬移卡，第 $i$ 张卡的魔力值为 $b_i$。这只鸟可以在任意一棵树上选择使用瞬移卡，瞬移到高度不超过该瞬移卡魔力值的一棵树上（如果鸟当前所在的树高度不超过瞬移卡的魔力值，则它可以瞬移到当前所在的树上）。但是它只能按照给出的顺序使用瞬移卡。数据保证所有瞬移卡都可以使用（即不存在一张瞬移卡，魔力值小于所有树的高度）。

这只鸟初始位置在第一棵树上，请求出它最多可以飞行几次（不包含瞬移）。

注意：鸟可以重复经过同一棵树。

inputFormat:
第一行，包含两个整数 $n,k$，表示树的棵数和鸟瞬移卡的数量。

接下来一行，$n$ 个整数，表示每棵树的高度。

接下来一行，$k$ 个整数，表示每张瞬移卡的魔力值。按照使用顺序给出。

outputFormat: 一行，一个整数，表示这只鸟最多飞行次数。


title: [ZYOI Round1] Chessboard game/棋盘游戏

background: 子衿有一个游戏棋盘，此时准备拿出来玩玩。

description:
她的棋盘是 L 字形的，由上面一个 $n_1 \times m_1$ 的小长方形和下面一个 $n_2 \times m_2$ 的大长方形组成。棋盘初始状态所有格子上的数都为 $k$。

比如，当 $n_1 = 2$，$m_1 = 2$，$n_2 = 3$，$m_2 = 4$，$k = 0$ 时，棋盘初始是这样的：

```
0 0
0 0
0 0 0 0
0 0 0 0
0 0 0 0
```

现在她要进行若干次操作：将相邻的两个格子中的数同时加 $1$ 或减 $1$。操作完成后她会记住这些格子上的数。

可是她有一次不小心，经过若干次操作后忘掉了其中某一个数是多少了，于是在上面打了一个 $999999$。请你通过编程求出被打上 $999999$ 的数应该是多少。保证有且仅有一个格子被打上了 $999999$。

inputFormat:
第一行输入五个整数 $n_1,m_1,n_2,m_2,k$，分别表示组成 L 字形棋盘小长方形的行数和列数，大长方形的行数和列数，以及初始格子上的数。

接下来 $n_1$ 行，每行输入 $m_1$ 个整数，表示操作后的棋盘小长方形中每个格子中的数。

接下来 $n_2$ 行，每行输入 $m_2$ 个整数，表示操作后的棋盘大长方形中每个格子中的数。

未知的数以 $999999$ 代替。

outputFormat:
一行，一个整数，表示被打上 $999999$ 的数原本的值。

数据保证有解。


title: [NOIP2021] 报数

description:
报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 $7$ 的倍数，或十进制表示中含有数字 $7$，就必须跳过这个数，否则就输掉了游戏。

在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 r 和小 z 闲得无聊玩起了这个报数游戏。但在只有两个人玩的情况下计算起来还是比较容易的，因此他们玩了很久也没分出胜负。此时小 z 灵光一闪，决定把这个游戏加强：任何一个十进制中含有数字 $7$ 的数，它的所有倍数都不能报出来！

形式化地，设 $p(x)$ 表示 $x$ 的十进制表示中是否含有数字 $7$，若含有则 $p(x) = 1$，否则 $p(x) = 0$。则一个正整数 $x$ 不能被报出，当且仅当存在正整数 $y$ 和 $z$ ，使得 $x = yz$ 且 $p(y) = 1$。

例如，如果小 r 报出了 $6$ ，由于 $7$ 不能报，所以小 z 下一个需要报 $8$；如果小 r 报出了 $33$，则由于 $34 = 17 \times 2$，$35 = 7 \times 5$ 都不能报，小 z 下一个需要报出 $36$ ；如果小 r 报出了 $69$，由于 $70 \sim 79$ 的数都含有 $7$，小 z 下一个需要报出 $80$ 才行。

现在小 r 的上一个数报出了 $x$，小 z 想快速算出他下一个数要报多少，不过他很快就发现这个游戏可比原版的游戏难算多了，于是他需要你的帮助。当然，如果小 r 报出的 x 本身是不能报出的，你也要快速反应过来小 r 输了才行。

由于小 r 和小 z 玩了很长时间游戏，你也需要回答小 z 的很多个问题。

inputFormat:
第一行，一个正整数 $T$ 表示小 z 询问的数量。

接下来 $T$ 行，每行一个正整数 $x$，表示这一次小 r 报出的数。

outputFormat: 输出共 $T$ 行，每行一个整数，如果小 r 这一次报出的数是不能报出的，输出 $-1$，否则输出小 z 下一次报出的数是多少。

samples:
见附件中的 number/number3.in
见附件中的 number/number3.ans

samples:
见附件中的 number/number4.in
见附件中的 number/number4.ans

hint:
**【样例解释 #1】**

这一组样例的前 $3$ 次询问在题目描述中已有解释。

对于第 $4$ 次询问，由于 $300 = 75 \times 4$，而 $75$ 中含有 $7$ ，所以小 r 直接输掉了游戏。

**【数据范围】**

对于 $10\%$ 的数据，$T \leq 10$，$x \leq 100$。
对于 $30\%$ 的数据，$T \leq 100$，$x \leq 1000$。
对于 $50\%$ 的数据，$T \leq 1000$，$x \leq 10000$。
对于 $70\%$ 的数据，$T \leq 10000$，$x \leq 2 \times {10}^5$。
对于 $100\%$ 的数据，$1 \le T \leq 2 \times {10}^5$，$1 \le x \leq {10}^7$。


title: [NOIP2021] 方差

description:
给定长度为 $n$ 的非严格递增正整数数列 $1 \le a_1 \le a_2 \le \cdots \le a_n$。每次可以进行的操作是：任意选择一个正整数 $1 < i < n$，将 $a_i$ 变为 $a_{i - 1} + a_{i + 1} - a_i$。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 $n^2$ 的结果。

其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 $D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2$，其中 $\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i$。

inputFormat:
输入的第一行包含一个正整数 $n$，保证 $n \le {10}^4$。

输入的第二行有 $n$ 个正整数，其中第 $i$ 个数字表示 $a_i$ 的值。数据保证 $1 \le a_1 \le a_2 \le \cdots \le a_n$。

outputFormat: 输出仅一行，包含一个非负整数，表示你所求的方差的最小值的 $n^2$ 倍。

samples:
见附件中的 variance/variance2.in
见附件中的 variance/variance2.ans

samples:
见附件中的 variance/variance3.in
见附件中的 variance/variance3.ans

samples:
见附件中的 variance/variance4.in
见附件中的 variance/variance4.ans


title: [NOIP2021] 数列

description:
给定整数 $n, m, k$，和一个长度为 $m + 1$ 的正整数数组 $v_0, v_1, \ldots, v_m$。

对于一个长度为 $n$，下标从 $1$ 开始且每个元素均不超过 $m$ 的非负整数序列 $\{a_i\}$，我们定义它的权值为 $v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}$。

当这样的序列 $\{a_i\}$ 满足整数 $S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$ 的二进制表示中 $1$ 的个数不超过 $k$ 时，我们认为 $\{a_i\}$ 是一个合法序列。

计算所有合法序列 $\{a_i\}$ 的权值和对 $998244353$ 取模的结果。

inputFormat:
输入第一行是三个整数 $n, m, k$。

第二行 $m + 1$ 个整数，分别是 $v_0, v_1, \ldots, v_m$。

outputFormat: 仅一行一个整数，表示所有合法序列的权值和对 $998244353$ 取模的结果。

samples:
见附件中的 sequence/sequence2.in
见附件中的 sequence/sequence2.ans


title: [NOIP2021] 棋局

background:
在输了一晚上的麻将之后，小 z 和小 c 卸掉了手机上的所有牌类游戏。不过这怎么可能阻挡得了他们上课颓废的决心呢？现在他们的目光盯在了棋类游戏上，但他们两个除了天天下飞行棋以外，几乎所有棋类游戏都只懂个大概规则。

“既然我们都会玩但只能玩一点点，不如我们自己搞个缝合怪出来吧！”

于是，在他们的精心脑洞之下，一个融合了围棋、象棋与军棋的奇妙游戏诞生了……

description:
游戏在一张长 $n$ 行宽 $m$ 列的网格形棋盘上进行，棋子落在网格的交叉点上，我们不妨记左上角的交叉点的坐标为 $(1,1)$，右下角的交叉点坐标为 $(n,m)$。

棋子分为黑白两色，对局双方各执一方棋子。

每个棋子除了颜色以外还有等级，不妨设 $\mathit{col}_i$ 为棋子 $i$ 的颜色，$\mathit{lv}_i$ 为棋子 $i$ 的等级。另外，棋盘上的网格线共有 $4$ 种状态，对于第 $i$ 条网格线，设其状态为 $\mathit{opt}_i$。

轮到每方下棋时，他可以选择棋盘上的一个己方棋子沿网格线进行移动到另一个交叉点，称为走子。形式化定义走子的过程如下：选择一个坐标序列 $(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)$，其中 $k$ 是任意选定的正整数，$(x_0,y_0)$ 是棋子初始的位置，$(x_k,y_k)$ 是棋子最终走到的位置，需要满足：

- 对于任意 $i=0,1,\ldots,k-1$，坐标 $(x_i,y_i)$ 和 $(x_{i+1},y_{i+1})$ 之间必须有网格线直接相连，也就是说**走子必须沿着网格线走**；
- 对于任意 $i\not=j$，必须有 $(x_i,y_i)\ne(x_j,y_j)$，也就是说走子过程中不能经过重复位置，特别地 $(x_0,y_0)\ne(x_k,y_k)$，也就是说**不能原地不动（或走回原地）**；
- 对于任意 $i=1,\ldots,k-1$，坐标 $(x_i,y_i)$ 上必须没有棋子，也就是说**走子时不能越过已有的棋子**；
- 若 $(x_k,y_k)$ 上没有棋子，称为普通走子，否则称为吃子。在吃子过程中，设正在走的棋子颜色为 $\mathit{col}_1$，等级为 $\mathit{lv}_1$，被吃的棋子颜色为 $\mathit{col}_2$，等级为 $\mathit{lv}_2$，则必须满足 $\mathit{col}_1\ne\mathit{col}_2,\mathit{lv}_1\geq\mathit{lv}_2$，换句话说**只能吃与自己颜色不同，且等级不高于自己等级的棋子**。

需要注意的是，由上述定义可以得出，不允许棋子在吃子后继续向前走。

网格线的状态含义如下所述：

- 如果 $\mathit{opt}_i=0$，代表此路不通，走子时不能经过这条网格线；
- 如果 $\mathit{opt}_i=1$，代表这条网格线是一条“普通道路”，每次走子时棋子最多只能经过 $1$ 条普通道路。
- 如果 $\mathit{opt}_i=2$，代表这条网格线是一条“直行道路”，每次走子时棋子可以经过任意条直行道路，但只能**一直沿横向或一直沿纵向走，不能转弯**。如沿直行道路从 $(1,1)$ 经过 $(1,2)$ 走到 $(1,3)$ 是可以的，但是从 $(1,1)$ 经过 $(1,2)$ 走到 $(2,2)$ 不行。
- 如果 $\mathit{opt}_i=3$，代表这条网格线是一条“互通道路”，每次走子时棋子可以经过任意条互通道路，且中途可任意转弯。

同时规定在一次走子过程中，**棋子经过的网格线的状态必须全部相同**，比如从 $(1,1)$ 经过直行道路走到 $(1,2)$ 再经过互通道路走到 $(1,3)$ 是不允许的。

至于如何判断胜负等其它细节，与本题无关，故略去。

小 z 和小 c 开发出这款棋类游戏后，为了提升水平，想了一个训练的策略：一开始棋盘是空的，然后小 c 会每次往棋盘的某个空交叉点上放一枚棋子，小 z 需要快速计算出：若选择这枚新放上的棋子进行一次走子，棋盘上一共有多少个位置是能被走到的？注意：因为这只是思维训练，他们并不会真的走这枚棋子。

可怜的小 z 发现他的计算力不足以算出这个问题，只好向你求助。

inputFormat:
每个测试点由多组数据组成。

第一行：一个正整数 $T$ 表示数据组数。

对于每组数据：

第一行：三个正整数 $n, m, q$，分别表示棋盘的行数、列数和游戏的轮数。

接下来 $n$ 行，每行为一个长 $m - 1$ 的字符串，每个字符为 $\texttt{0}$、$\texttt{1}$、$\texttt{2}$、$\texttt{3}$ 中的一个，第 $i$ 行第 $j$ 个字符表示交叉点 $(i, j)$ 连向交叉点 $(i, j + 1)$ 的网格线状态。

接下来 $n - 1$ 行，每行为一个长 $m$ 的字符串，每个字符为 $\texttt{0}$、$\texttt{1}$、$\texttt{2}$、$\texttt{3}$ 中的一个，第 $i$ 行第 $j$ 个字符表示交叉点 $(i, j)$ 连向交叉点 $(i + 1, j)$ 的网格线状态。

接下来 $q$ 行，每行 $4$ 个非负整数 $\mathit{col}_i , \mathit{lv}_i , x_i , y_i$，表示在第 $i$ 轮有一枚颜色为 $\mathit{col}_i$，等级为 $\mathit{lv}_i$ 的棋子放在了交叉点 $(x_i , y_i)$ 上。其中 $\mathit{col}_i = 0$ 表示黑子，$\mathit{col}_i = 1$ 表示白子。保证之前交叉点 $(x_i , y_i)$ 上没有棋子。

outputFormat: 对于每组数据输出 $q$ 行，每行一个非负整数，表示第 $i$ 枚棋子放置后能走到的交叉点数量。

samples:
见附件中的 chess/chess3.in
见附件中的 chess/chess3.ans

samples:
见附件中的 chess/chess4.in
见附件中的 chess/chess4.ans


title: [COCI2021-2022#2] Kaučuk

description:
Kaučuk 程序只有下列三种命令：

- $\texttt{section}$：创建新的一级标题，序号从 $1$ 开始标记。
- $\texttt{subsection}$：创建新的二级标题，序号在每个一级标题的基础上从 $1$ 开始标记。
- $\texttt{subsubsection}$：创建新的三级标题，序号在每个二级标题的基础上从 $1$ 开始标记。

给定 $n$ 组命令及标题名称，输出所有标题序号及其名称。

inputFormat:
第一行一个正整数 $n$，表示命令的数量。

接下来的 $n$ 行，每行输入命令名称（$\texttt{section}$、$\texttt{subsection}$、$\texttt{subsubsection}$ 之一）和标题名称。标题名称由不超过 $20$ 个小写英文字母组成。

outputFormat: 共 $n$ 行，表示所有标题序号及其名称。

samples:
3
section zivotinje
section boje
section voce

samples:
4
section zivotinje
subsection macke
subsection psi
subsubsection mops

samples:
1 zivotinje
1.1 macke
1.2 psi
1.2.1 mops

samples:
4
section zivotinje
subsection psi
section voce
subsection ananas

hint:
**【数据规模与约定】**

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：$1 \le n \le 3$。
- Subtask 2（10 pts）：只包含 $\texttt{section}$ 命令。
- Subtask 3（10 pts）：只包含 $\texttt{section}$ 和 $\texttt{subsection}$ 命令。
- Subtask 4（20 pts）：无特殊限制。

对于 $100\%$ 的数据，$n \le 100$。

**【提示与说明】**

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 1 Kaučuk_。**

**本题分值按 COCI 原题设置，满分 $50$。**


title: [COCI2021-2022#2] Magneti

description:
给定 $n$ 个磁铁和 $l$ 个空位，其中相邻空位之间的距离为 $1$，每个空位可放置一个磁铁。所有 $n$ 个磁铁都必须被放置。每个磁铁可以吸引距离小于 $r_i$ 的其它磁铁。

求所有磁铁互不吸引的方案总数对 $10^9+7$ 取模的结果。

inputFormat:
第一行两个正整数 $n,l$，分别表示磁铁和空位数量。

第二行 $n$ 个整数 $r_i$。

outputFormat: 输出方案总数对 $10^9+7$ 取模的结果。

hint:
**【样例 2 解释】** 四个磁铁的所有排列都符合题意。

**【样例 3 解释】**

用 $\texttt{1,2,3}$ 表示磁铁，$\texttt \_$ 表示空位，则所有方案为：$\texttt{13\_2}$、$\texttt{31\_2}$、$\texttt{2\_13}$ 和 $\texttt{2\_31}$。

**【数据规模与约定】**

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：$r_1=r_2=\cdots=r_n$。
- Subtask 2（20 pts）：$1 \le n \le 10$。
- Subtask 3（30 pts）：$1 \le n \le 30$，$n \le l \le 300$。
- Subtask 4（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 50$，$n \le l \le 10000$，$1 \le r_i \le l$。

**【提示与说明】**

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 4 Magneti_。**

**本题分值按 COCI 原题设置，满分 $110$。**


title: [COCI2021-2022#2] Osumnjičeni

description:
现有 $n$ 个嫌疑人。由于其身高的不确定性，只知道每个嫌疑人的身高范围 $[l_i,r_i]$。

每次调查可以选取编号范围为 $[a,b]$ 内的所有嫌疑人，要求他们的身高范围没有交集。若嫌疑人在某次调查中出现，则目击者可以立即作出正确的判断。

给定 $q$ 组询问，每次给出 $p_i,q_i$。求在嫌疑人锁定在 $[p_i,q_i]$ 范围内的前提下，最多需要进行多少次调查。

inputFormat:
第一行一个正整数 $n$，表示嫌疑人的数量。

接下来的 $n$ 行，每行两个正整数 $l_i,r_i$，表示第 $i$ 个嫌疑人的身高范围。

接下来的一行，一个正整数 $q$，表示询问组数。

接下来的 $q$ 行，每行两个正整数 $p_i,q_i$，表示一组询问。

outputFormat: 共 $q$ 行，表示每组询问的答案。

hint:
**【样例 3 解释】**

- 询问 $1,3$：在 $[1,1],[2,3],[4,5]$ 范围内进行调查即可，答案为 $3$。
- 询问 $2$：调查 $[3,5]$ 即可，答案为 $1$。

**【数据规模与约定】**

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：$q=p_1=1$，$q_1=n$。
- Subtask 2（10 pts）：$1 \le n,q \le 5000$。
- Subtask 3（20 pts）：$1 \le n \le 5000$。
- Subtask 4（20 pts）：$1 \le q \le 100$。
- Subtask 5（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,q \le 2 \times 10^5$，$1 \le a \le b \le n$，$1 \le l_i \le r_i \le 10^9$，$1 \le p_i \le q_i \le n$。

**【提示与说明】**

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 5 Osumnjičeni_。**

**本题分值按 COCI 原题设置，满分 $110$。**


title: [COCI2021-2022#2] Hiperkocka

description:
给定一个 $n$ 维的超正方体。

将该超正方体抽象为一个含 $2^n$ 个结点的图，结点分别用序号 $0,1,\cdots,2^n-1$ 表示。两个结点 $x,y$ 联通，当且仅当 $x \oplus y$ 为 $2$ 的整数幂。

现需将若干棵含有 $n$ 条边的树 $T$ 放置于该超正方体中。结点分别用序号 $0,1,\cdots,n$ 表示。给定每棵树的 $n$ 条边所连接的点的序号，则每一棵树需满足下列条件：

- 每个树上的结点都与超正方体的其中一个结点一一对应
- 每个结点互不相同
- 每一棵树的每一条边所连接的两个结点在超正方体中所对应的两个结点在超正方体中有边相连（即对应的两个结点的异或值为 $2$ 的整数幂）
- 每两棵树的边集在超正方体中所对应的边集不交，即超正方体中的每条边最多包含于一棵树中

请给定一种放置方案，使得放在超正方体中的每一棵树都符合题意。

inputFormat:
第一行一个正整数 $n$，表示超正方体的维数。

接下来的 $n$ 行，每行两个整数 $x,y$，表示在每棵树 $T$ 中，有一条连接 $x,y$ 的边。

outputFormat:
第一行输出放置的树的数目 $k$。

接下来的 $k$ 行，每行输出 $n+1$ 个整数，表示这棵树的对应结点在超正方体中的结点编号。

hint:
**【样例 3 解释】**

![](https://cdn.luogu.com.cn/upload/image_hosting/58a0p43i.png)

**【数据规模与约定】**

对于 $100\%$ 的数据，$1 \le n \le 16$，$0 \le x,y \le n$，$x \neq y$。

**【提示与说明】**

如果程序正确地放置了 $k$ 棵树，则每个测试点的得分为 $f(k) \cdot 110$，其中：

$$f(k)=\begin{cases}
\dfrac{0.7k}{2^{n-1}} & (k \lt 2^{n-1}) \cr
1 & (k=2^{n-1}) \cr
\end{cases}$$

若放置方式错误，则该测试点得分为 $0$。可以证明，总存在一种方式可以放置 $2^{n-1}$ 棵树。

因评分方式特殊，本题启用自行编写的 [Special Judge](https://www.luogu.com.cn/discuss/738608)，欢迎大家 hack。

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 3 Hiperkocka_。**

**本题在 COCI 原题中满分 $110$，但由于为了计算方便，将满分修改为 $26 \times 5=130$。**


title: [COCI2021-2022#2] Kutije

description:
Matrin 有 $n$ 个箱子的玩具。箱子分别用序号 $1,2,3,\cdots,n$ 表示。初始状态下，每个箱子中有一个与箱子编号相同的玩具。

Matrin 邀请了 $m$ 位朋友来家玩玩具。他注意到，每一位朋友在玩完玩具之后，都会将原先位于 $i$ 号箱子内的玩具放入 $p_i$ 号箱内。

给定 $q$ 组询问，每次可随意邀请朋友并自由选择顺序，同时每位朋友可以邀请任意多次。问是否存在一种方案，使得 $a$ 号玩具最终被放入 $b$ 号箱子中。

inputFormat:
第一行三个正整数 $n,m,q$，分别表示箱子 / 玩具、朋友和询问的数量。

接下来的 $m$ 行，每行 $n$ 个整数 $p_i$。数据保证 $p_i$ 是 $1 \sim n$ 的一个排列。

接下来的 $q$ 行，每行两个整数 $a,b$。

outputFormat: 共 $q$ 行，每行输出一个字符串 $\texttt{DA}$（是）或 $\texttt{NE}$（否）。

hint:
**【样例 1 解释】**

- 询问 $1$：初始状态下，$1$ 号玩具已经在 $1$ 号箱子内，故输出 $\texttt{DA}$。
- 询问 $2$：第二组询问：无符合题意的方案，输出 $\texttt{NE}$。
- 询问 $3$：邀请 $1$ 号朋友前来即可，输出 $\texttt{DA}$。

**【数据规模与约定】**

**本题采用子任务捆绑测试。**

- Subtask 1（15 pts）：$m=1$。
- Subtask 2（10 pts）：$1 \le n,m,q \le 100$；对于每组询问，若答案为 $\texttt{DA}$，则保证存在一种邀请朋友数量不超过 $2$ 的方案。
- Subtask 3（10 pts）：$1 \le n,m,q \le 100$。
- Subtask 4（35 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$1 \le q \le 5 \times 10^5$，$1 \le a,b \le n$。

**【提示与说明】**

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 2 Kutije_。**

**本题分值按 COCI 原题设置，满分 $70$。**


title: [KSN2021] Self Defence

description:
定义一个字符串的权值为它长度为 $M$ 且只包含一种字符的子串数量。

例如字符串 ``ABBB``，在 $M=2$ 时的权值为 $2$。

给定一个长度为 $N$ 的字符串，每个字符为 ``?``，``A`` 和 ``B`` 中的一个，你需要求出将每个 ``?`` 替换为 ``A`` 或 ``B`` 后，可以得到多少个权值为 $K$ 的字符串。

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

inputFormat:
第一行输入三个整数 $N,M,K$。

第二行输入一个长度为 $N$ 的字符串 $S$。

outputFormat: 输出一个整数代表答案。

hint:
**【样例解释】**

对于第一组样例，以下为所有合法字符串：

```plain
AAAAB
ABBBB
BAAAA
BBBBA
```

对于第二组样例，以下为所有合法字符串：

```plain
AAABA
AABAA
AABBA
ABAAA
ABBAA
ABBBA
```

**【数据范围】**

**本题采用捆绑测试。**

* Subtask 1（5 points）：只存在一组数据，满足 $N=10$，$M=3$，$K=5$，$S=\texttt{????A???B?}$。
* Subtask 2（9 points）：$N\le 20$。
* Subtask 3（11 points）：$N\le 200$。
* Subtask 4（6 points）：$M=2$，$K=0$。
* Subtask 5（9 points）：$K=0$。
* Subtask 6（8 points）：$K\le 1$。
* Subtask 7（27 points）：$S$ 只包含 ``?``.
* Subtask 8（25 points）：无特殊限制。

对于所有数据，$1\leq N\leq 3000$，$1\leq M\leq N$，$0\leq K\leq N$。


title: [KSN2021] Binary Sea

description:
有一个 $N\times M$ 的网格，行列从 $0$ 开始，从左上到右下编号。

第 $i$ 行，第 $j$ 列的格子是黑格当且仅当 $i\text{ and }j=0$。

两个黑格联通当且仅当它们都是黑格且它们可以经过若干个有**邻边**的黑格到达。

给定 $Q$ 个矩形，左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$，你需要对于每个矩形求出所有的黑格形成了多少连通块。

inputFormat:
第一行输入三个整数 $N,M,Q$，代表网格大小和询问数量。

接下来 $Q$ 行，每行输入四个整数 $x_1,y_1,x_2,y_2$，代表询问矩形。

outputFormat: 对于每组数据输出一行，包含一个整数，代表答案。

hint:
**【样例解释】**

以下为样例中四个询问的图示：

![](https://api.tlx.toki.id/api/v2/problems/JIDPROGSepzakraFyFK27n5u3QV/render/sample-q1.png) ![](https://api.tlx.toki.id/api/v2/problems/JIDPROGSepzakraFyFK27n5u3QV/render/sample-q2.png) ![](https://api.tlx.toki.id/api/v2/problems/JIDPROGSepzakraFyFK27n5u3QV/render/sample-q3.png) ![](https://api.tlx.toki.id/api/v2/problems/JIDPROGSepzakraFyFK27n5u3QV/render/sample-q4.png)

**【数据范围】**

**本题采用捆绑测试。**

* Subtask 1（5 points）：只存在一组数据，满足 $N = M=12$，$Q=3$，每次询问的 $(x_1,y_1,x_2,y_2)$ 依次为 $(1,1,9,8)$，$(8,8,11,11)$ 和 $(4,3,5,9)$。
* Subtask 2（11 points）：$N,M,Q\le 200$。
* Subtask 3（10 points）：$N,M,Q\le 2000$，$x_1=x_2$。
* Subtask 4（20 points）：$N,M,Q\le 2000$。
* Subtask 5（4 points）：$x_1=x_2=0$。
* Subtask 6（6 points）：保证对于每个询问存在整数 $k$ 使得 $x_1=x_2=2^k$。
* Subtask 7（29 points）：$x_1=x_2$。
* Subtask 8（15 points）：无特殊限制。

对于所有数据，$0\leq x_1\leq x_2<N\leq 10^9$，$0\leq y_1\leq y_2<M\leq 10^9$，$1\leq Q\leq 10^5$。


title: [KSN2021] Colouring Balls

description:
**这是一道交互题。**

有 $N$ 个小球，从 $1$ 到 $N$ 编号。

你每次可以询问编号在 $[l,r]$ 之间的小球有几种不同的颜色，你需要求出每个小球的颜色。由于你并不知道具体颜色是什么，你只要将同种颜色用同一个数字表示即可。

## 交互格式

第一行输入一个正整数 $T$，**代表 Subtask 编号（而不是测试数据组数）**。

第二行输入两个整数 $N,Q$，代表小球数量和询问次数限制。

接下来你可以提出不超过 $Q$ 个询问并读取交互库返回的答案，每个询问的格式为 ``? l r``，代表你询问 $[l,r]$ 中小球颜色的数量。

当你确认所有小球的颜色后，你需要输出 ``! a1 a2 ... an`` 代表所有小球的颜色。你需要保证：

* $1\leq a_i\leq N$ 且 $a_i$ 均为整数。
* 相同颜色的小球的 $a_i$ 相同。
* 不同颜色的小球的 $a_i$ 不同。

你的每次输出后都需要刷新缓冲区，你可以使用如下语句来清空缓冲区：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

inputFormat: 见“交互格式”。

outputFormat: 见“交互格式”。

hint:
**【数据范围】**

**本题采用捆绑测试。**

* Subtask 1（8 points）：$Q=10000$, 保证每种颜色的球的编号连续。
* Subtask 2（7 points）：$Q=2000$，保证每种颜色的球的编号连续。
* Subtask 3（19 points）：$Q=2000$，保证球只有至多 $3$ 种颜色。
* Subtask 4（14 points）：$Q=2000$，保证球只有至多 $4$ 种颜色。
* Subtask 5（12 points）：$Q=2000$，保证球有至少 $(N-1)$ 种颜色。
* Subtask 6（21 points）：$Q=10000$，保证 $N\le 100$。
* Subtask 7（19 points）：$Q=10000$。

对于所有数据，保证 $1\leq T\leq 7$，$2\leq N\leq 10^3$。


title: [KSN2021] Self Permutation

description:
给定一个长度为 $N$ 的排列 $a_i$，你可以执行若干次操作：

* 选择两个相邻的数，删除它们中较大的那个。

问最后可能得到序列的数量，答案对 $10^9+7$ 取模。

注意如果两个数中间所有的数被删除了，它们会变成相邻的。

inputFormat:
第一行输入一个正整数 $N$。

第二行输入 $N$ 个正整数 $a_i$。

hint:
**【样例解释】**

对于第一组样例，以下为所有可能得到的序列：

- $[2,3,1]$
- $[\bold2,\bold3,1]\to[2,1]$
- $[\bold2,\bold3,1]→[\bold2,\bold1]→[1]$

对于第二组样例，以下为所有可能得到的序列：

- $[2,1,4,3]$
- $[\bold2,\bold1, 4, 3]\to[1, 4, 3]$
- $[\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[1, 3]$
- $[\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[\bold1,\bold3]\to[1]$
- $[2, 1,\bold4,\bold3]\to[2, 1, 3]$
- $[2, 1,\bold4,\bold3]\to[2,\bold1,\bold3]\to[2, 1]$

**【数据范围】**

**本题采用捆绑测试。**

- Subtask 1（8 points）：只存在一组数据，满足 $N=6$，$A=[2,5,1,3,4,6]$。
- Subtask 2（20 points）：$N\leq 200$。
- Subtask 3（13 points）：$N\leq 2000$，$A_i=i$。
- Subtask 4（9 points）：$A_i=i$。
- Subtask 5（23 points）：$N\leq 2000$。
- Subtask 6（27 points）：无特殊限制。

对于所有数据，$N\leq 3\times 10^5$，保证输入的 $a_i$ 能构成一个排列。


title: [KSN2021] Binary Land

description:
给定一张 $N$ 个点的图，每个点有权值 $A_i$ 和价值 $B_i$。

两个点 $x,y$ 之间存在一条无向边当且仅当 $A_x\text{ xor }A_y>\max(A_x,A_y)$。

你需要对于 $i=1,2,\cdots n$ 依次求出点 $i$ 所在连通块中所有点的价值和。

inputFormat:
第一行输入一个正整数 $N$。

第二行输入 $N$ 个正整数 $A_i$。

第三行输入 $N$ 个正整数 $B_i$。

outputFormat: 输出 $N$ 行，第 $i$ 行包含一个整数，代表点 $i$ 所在连通块中所有点的价值和。

hint:
**【数据范围】**

**本题采用捆绑测试。**

- Subtask 1（8 points）：只存在一组数据，满足 $N=8$，$A=[6,39,11,63,3,39,1,43]$，$B=[4,8,3,7,9,1,2,2]$。
- Subtask 2（13 points）：保证 $N \leq 200$。
- Subtask 3（10 points）：保证 $N \leq 2000$。
- Subtask 4（4 points）：保证 $A_1=A_2=\cdots=A_n$。
- Subtask 5（7 points）：保证存在非负整数 $k$ 使得 $A_i=2^k$。
- Subtask 6（19 points）：$A_i\leq 2^{12}-1$。
- Subtask 7（39 points）：无特殊限制。

对于所有数据，$1 \leq N \leq 10^5$，$1 \leq A_i \leq 2^{30}-1$，$1 \leq B_i \leq 10^9$。


title: [KSN2021] Delivering Balls

description:
给定一个长度为 $N$ 的序列 $H$ 和 $Q$ 次询问。

第 $i$ 次询问中，你初始在第 $S_i$ 列 $H_{S_i}$ 行，想要到第 $T_i$ 列第 $H_{T_i}$ 行。

你可以进行若干次移动。每次移动你可以选择以下两种参数：

* 列 $-1$，列不变，列 $+1$。
* 行 $-1$，行不变，行 $+1$。

如果你选择行 $-1$，消耗 $1$ 体力，如果你选择行不变，消耗 $2$ 体力，如果你选择行 $+1$，消耗 $4$ 体力。

你需要保证每次移动后，你的列数 $x$ 在 $[1,N]$ 之间，且你的行数 $y$ 不小于 $H_x$。

对于每个询问，你需要求出你消耗体力的最小值。

inputFormat:
第一行输入一个正整数 $N$。

第二行输入 $N$ 个正整数 $H_i$。

接下来 $Q$ 行，每行输入两个正整数 $S_i,T_i$。

outputFormat: 对于每个询问，输出一行，包含一个整数，代表消耗体力的最小值。

hint:
**【样例解释】**

以下为第一个样例中两个询问的图示：

![](https://sandalphon.tlx.toki.id/api/v2/problems/JIDPROG92Su7ScrLh6DkhILekKA/render/roket-q-1.png) ![](https://sandalphon.tlx.toki.id/api/v2/problems/JIDPROG92Su7ScrLh6DkhILekKA/render/roket-q-2.png)

**【数据范围】**

- Subtask 1（7 points）：只存在一组数据，满足 $N=8$，$Q=4$，$H=[,9,3,3,5,4,8,2]$，$(S_i,T_i)$ 依次为 $(1,8)$，$(3,6)$，$(6,4)$ 和 $(7,2)$。
- Subtask 2（5 points）：$S_i+1=T_i$。
- Subtask 3（6 points）：$H_i=i$。
- Subtask 4（18 points）：$N,Q,H_i\leq 100$。
- Subtask 5（24 points）：$N,Q\leq 1000$。
- Subtask 6（13 points）：$S_i=1$。
- Subtask 7（27 points）：无特殊限制。

对于所有数据，$2\leq N\leq 2\times 10^5$，$H_i\leq 10^9$，$Q\leq 2\times 10^5$，$1\leq S_i,T_i\leq N$。


title: [BalticOI 2002 Day2] Bicriterial routing

description:
给定一张 $n$ 个点、$m$ 条边的无向图。边 $e$ 的长度为二元组 $(c_e, t_e)$。

一条途径 $w$ 的长度 $(c_w, t_w) = (\sum_{e \in w} c_e, \sum_{e \in w} t_e)$。

一条途径 $w$ 比另一条途径 $w'$ 短，当且仅当二者长度不同且 $c_w \le c_{w'}, t_w \le t_{w'}$。

显然可能有两条途径无法比较长短，进而两点间可能出现多条长度不同的最短路径。

求 $s$ 至 $e$ 的最短路径的长度取值的种类数。

inputFormat:
第一行四个整数 $n, m, s, e$。

接下来 $m$ 行，每行四个整数 $p, r, c, t$，分别表示一条边的两个端点与长度。

outputFormat: 一行一个整数，你的答案。

hint:
#### 样例说明

![](https://cdn.luogu.com.cn/upload/image_hosting/2x4o606g.png)

考虑其中四条途径：

0. $1 \to 2 \to 4$（长度为 $(4, 5)$）；
1. $1 \to 3 \to 4$（长度为 $(4, 5)$）；
2. $1 \to 2 \to 3 \to 4$（长度为 $(6, 4)$）；
3. $1 \to 3 \to 2 \to 4$（长度为 $(4, 10)$）。

途径 0、途径 1 均短于途径 3。最短路长度共有两种：$(4, 5)$（途径 0、途径 1）、$(6, 4)$（途径 2）。

#### 数据范围

$1 \le s, e, p, r \le n \le 100$，$0 \le m \le 300$，$s \ne e$，$0 \le c, t \le 100$。

#### 提示

[BalticOI](https://boi.cses.fi/contests.php) 2002 Day2 A.

由于自定义计分脚本参数配置，暂不支持 AC WA TLE MLE 外的评测状态显示。如果你得到了此外任何一种评测状态，你将得到 UKE。

Subtask #0 为样例；Subtask #1 为数据。


title: [BalticOI 2002 Day2] L Game © Edward de Bono

description:
L 棋是一种双人棋类游戏，在 $4 \times 4$ 的正方形棋盘上进行。

共有两种棋子：
- L 形棋：大小为 $4$，双方各有一枚；
- 中性棋：大小为 $1$，共两枚，中立。

任意时刻，棋盘上任意格子上方应至多有一枚棋子。

双方轮流操作。一次合法的操作是：先移动己方 L 形棋至一个合法的与当前位置不同的位置，再移动至多一枚中性棋。

无法进行合法操作者败。

![](https://cdn.luogu.com.cn/upload/image_hosting/pmca33zr.png)

记标有网格的 L 形棋操作者为 A，标有斜线者为 B。

若处于上图三种局面之一且 A 先手，则能且仅能将己方 L 形棋移至另外两种局面。此后，A 可以将中性棋之一移至某空格子，或不移动中性棋。故 A 共有 $2 \times (6 + 6 + 1)$ 种操作方案。

若处于下图局面且 A 先手，则 A 由于无法移动其 L 形棋而败，B 胜。

![](https://cdn.luogu.com.cn/upload/image_hosting/9j9uia3u.png)

「妙棋」指：先手进行后存在必胜策略的操作。「败局」指：先手无论如何操作，后手都存在必胜策略的局面。「和棋」指：先手不存在妙棋且不为败局的局面。

尽管棋盘很小，但 L 棋存在超过 $18 \thinspace 000$ 种可能的局面；且在同一时刻先手可能存在多达 $195$ 种操作方案，但其中仅有一种妙棋。

对于给定局面，找到一步妙棋，或判定该局面为败局或和棋。若存在多种妙棋，输出任意一种即可。

inputFormat:
四行，每行四个字符，表示棋局。

- `#` 表示先手棋子所在位置；
- `*` 表示后手棋子所在位置；
- `x` 表示中性棋子所在位置；
- `.` 表示空格子。

outputFormat:
- 若存在妙棋，则输出移动后的局面，格式同输入格式。注意 `#` 依然表示操作前的先手，`*` 同理。

- 否则第一行一个字符串 `No winning move`。
  - 若为和棋，则第二行输出一个字符串 `Draw`；
  - 若为败局，则第二行输出一个字符串 `Losing`。

注意：虽然 Special Judge 忽略行末回车与文末换行，但请不要输出多于 $64$ 个字符，否则会被判为 Wrong Answer。

hint:
#### 数据范围

保证给出局面合法。

#### 提示

[BalticOI](https://boi.cses.fi/contests.php) 2002 Day2 B.

你能在不存在妙棋的测试点得分，当且仅当你通过了至少一半存在妙棋的测试点。（注：原题面中为至少一个，但这里取原题解中说法即「一半」。）

由于自定义计分脚本参数配置，暂不支持 AC WA TLE MLE 外的评测状态显示。如果你得到了此外任何一种评测状态，你将得到 UKE。

Subtask #0 为样例；Subtask #1 为数据。


title: [BalticOI 2002 Day2] Moving Robots

description:
一些机器人在二维平面上根据指令移动。机器人移动互不影响，甚至同一时刻同一点可能有多个机器人。

移动有两种：
- `S`：向前一步。
  记当前位置为 $(x, y)$，当前方向为 $C$：若 $C = 0$ 移至 $(x + 1, y)$；若 $C = 90$ 移至 $(x, y + 1)$；若 $C = 180$ 移至 $(x - 1, y)$；若 $C = 270$ 移至 $(x, y - 1)$。

- `T D`：方向增加 $D$。
  即令当前方向 $C \gets (C + D) \bmod 360$。

给定各机器人预设的指令序列，移除一些指令使所有机器人最终位于同一位置，并最小化移除指令数。

inputFormat:
第一行一个整数 $R$，表示机器人数。

接下来对于每个机器人：

- 第一行四个整数 $x, y, C, n$，表示初始位置、初始方向、指令序列长度。
- 接下来 $n$ 行，每行一个指令，格式见题目描述。

outputFormat:
若能够使所有机器人最终位于同一位置，输出两行：
- 第一行一个整数，表示最小移除指令数；
- 第二行两个整数，表示在移除指令数最小的情况下最终位置坐标（若有多种可能答案输出任意一种即可）。

若无法使所有机器人最终位于同一位置，输出一行一个整数 $-1$。

注意：虽然 Special Judge 忽略行末回车与文末换行，但请不要输出多于 $64$ 个字符，否则会被判为 Wrong Answer。

hint:
#### 样例说明

有两个机器人。第一个初始位于 $(2, 0)$，初始方向 $270$，指令序列长度为 $5$；第二个初始位于 $(1, -1)$，初始方向 $0$，指令序列长度为 $8$。至少需要移除两个指令。例如移除第一个机器人第三个指令与第二个机器人第五个指令，此时最终位置为 $(2, 1)$。

#### 数据范围

$2 \le R \le 10$，$1 \le n \le 50$，$-50 \le x, y \le 50$，$C, D \in \lbrace 0, 90, 180, 270 \rbrace$，保证指令格式如题目描述。

#### 提示

[BalticOI](https://boi.cses.fi/contests.php) 2002 Day2 C.

由于自定义计分脚本参数配置，暂不支持 AC WA TLE MLE 外的评测状态显示。如果你得到了此外任何一种评测状态，你将得到 UKE。

Subtask 设置与题目无关，仅为便于自定义积分脚本运行。


title: 约定（Promise）

background:
在化为废墟的城市中，大雨倾盆而降。

「魔女之夜」被击败后，圆和焰也已遍体鳞伤，因魔力不足而倒地不起。

「我们，也已经完了......」圆轻叹道。

「那悲叹之种呢？」焰的语气中还带着一丝希望。

圆沉默不语，望着天空，只是无奈地摇了摇头。

「是吗...... 我说，我们就这样一起变成怪物，把这世界的一切都搞得一团糟吧。」焰说着，不由地啜泣起来。「把那些讨厌的事和悲伤的事，全都和没发生过一样，破坏掉、破坏掉、破坏殆尽...... 你不觉得，这样也很好吗？」

随着一声清脆的碰撞，焰感觉到魔力流入了自己的灵魂宝石内。她转头看见圆正微笑着，拿着一枚悲叹之种。

「刚才那是骗你的，」圆的笑容依旧那么甜美，「我还留着一个呢。」

焰慌忙抱住了圆的手臂，问到：「为什么，为什么要给我？」

「因为有件我做不到，但是小焰能做到的事，我想拜托你...... 小焰，你可以回到过去对吧？你说过，为了避免这样的结局，而改写过历史的吧......」

「嗯...」

圆也终于忍不住悲伤，晶莹的泪珠从她脸上滑落。「你能去救救那个还没被丘比欺骗的，笨蛋的我吗？」

**「我答应你，一定会救你的！无论重复多少次，我都会保护好你！」**

「太好了......」圆平静了下来，但下一瞬间，她的灵魂宝石中就散出了黑雾，她的表情也痛苦地扭曲了起来。「再......拜托你一件事可以吗？」

焰轻轻点头答应。

「我，不想变成魔女......」圆的声音更加虚弱，「就算有讨厌的事和悲伤的事，但我想守护的东西，在这世上还有很多。」圆艰难地抬起手臂，支撑着手中漆黑的灵魂宝石。

「小圆......」焰拔出手枪，对准了圆的灵魂宝石。在焰的痛哭声中，她扣下了扳机。

description:
澪正陪着铃一起 N 刷《魔法少女小圆》，看到全剧最催人泪下的情节之一时，家长却突然推门进来了。澪不想被发现自己在摸鱼，就迅速切换界面，假装她们在做一道计数题：

> 定义一棵有标号、有根、不区分左右儿子的二叉树的权值是：以「根节点的所有儿子节点」为根的子树的权值之和加上 $d$，特别定义只有一个节点的树权值为 $1$。求所有 $n$ 个节点的这种树权值的 $k$ 次方和，答案对 $998244353$ 取模。

「这不是那个什么 [NaCly_Fish's Math Contest](https://www.luogu.com.cn/contest/53104) 的题... 吗？」铃看了看题，小声说道，「好无聊哦，不看这题。」

inputFormat: 输入一行三个正整数 $n,k,d$。

outputFormat: 输出一行一个整数，表示答案。

hint:
【样例 $1$ 解释】

$3$ 个节点的有标号有根二叉树有 $9$ 种，分别如下，其中标红的节点表示树根。
![](https://cdn.luogu.com.cn/upload/image_hosting/266knse0.png)
由于 $k=0$，所有树权值的 $k$ 次方和就等于树的总数，故答案为 $9$。

【样例 $2$ 解释】
接上图，图中第一行的树权值都为 $5$，第二行的树权值为 $4$，故答案为 $6\times 5^2+3\times 4^2=198$。

【数据范围】

**本题采用捆绑测试。**

Subtask1（5 pts）：$n \le 6$；
Subtask2（9 pts）：$k=0$，$n\le 10^7$；
Subtask3（14 pts）：$n\le 10^5$；
Subtask4（18 pts）：$k \le 4000$，$n\le 10^7$；
Subtask5（23 pts）：$k \le 10^5$；
Subtask6（31 pts）：无特殊限制。

对于 $100\%$ 的数据，$2\le n,d \le 9\times 10^8$，$0\le k \le 5\times 10^6$。


title: [BalkanOI 2012] Fan Groups

background: BOI 世界杯即将开始，有球迷们在城市中宣传他们支持的队伍。

description:
有 $n$ 个城市广场（标记为 $1$ 到 $n$）和其中一些之间的 $m$ 条单向街道，每个广场上初始有一群球迷（每个广场上的球迷支持不同球队）。

这 $n$ 群球迷按照某个特定的顺序进行以下操作：

- 占领他们所在的广场（如在 $1$ 广场的人会先占领 $1$ 广场）。
- 从他们占领的某个广场 $u$ 出发，走到与其相邻的每个广场 $v$。如果广场 $v$ 已经被人占领，他们会在边 $(u,v)$ 上发生冲突，并不再在这个方向上前进；否则，他们会占领广场 $v$，并重复这一步，直到没有能到达的广场为止。
- 如果他们所在的广场在此前被别的人群占领，他们不会与那群人发生冲突。在这种情况下，他们什么都不做。

给定该城市，以及发生冲突的边集。求一种球迷的行动顺序，使得发生冲突的边集与输入相符。

inputFormat:
输入的第一行包含两个整数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行三个整数 $A_i,B_i,C_i$，表示有向边 $A_i\rightarrow B_i$，如果 $C_i=1$，则这条边上发生了冲突。

outputFormat:
一个排列，球迷的行动顺序。

若无合法方案，输出 `-1`。

hint:
Special Judge 由 [TOBapNw](https://www.luogu.com.cn/user/185864) 提供，若 SPJ 有误，请联系他。

#### 数据范围：
Subtask#0 为样例。

$3\le N\le 2\times10^4$，$M\le\min(\frac{N\times(N-1)}{2},2\times10^5)$，$1\le A_i,B_i\le N$，$C_i\in\{0,1\}$。

#### 样例解释：

$8$ 号广场的球迷首先行动，占领广场 $8$；

接下来 $5$ 号广场的球迷行动，占领广场 $4,5,6$；

接下来 $6$ 号广场的球迷行动，因为广场 $6$ 已经被占领，他们什么都不做；

接下来 $2$ 号广场的球迷占领广场 $2,3$；

$3$ 号广场的球迷什么都不做；

接下来 $1$ 号广场的球迷行动，占领广场 $1$，并在边 $(1,4),(1,8)$ 上引发冲突；

$7$ 号广场的球迷占领广场 $7$，并在边 $(7,1),(7,4)$ 上引发冲突；

注意合法的顺序可能不止一种，样例中，$(2,3,8,4,1,7,5,6)$ 也是一种合法的方案。

注意 $(8,5,6,3,2,1,7,4)$ 不是合法的方案，因为按照这个方案，$(2,3)$ 上也会发生冲突，与输入不符。


title: [BalkanOI 2012] The Best Teams

background: 你是国家队教练，你要选择一支最佳队伍去参加 BOI 世界杯。

description:
你麾下有 $N$ 名球员，编号为 $1\dots N$，第 $i$ 名球员有一个年龄 $age_i$，和技能值 $skill_i$。

一个队伍的优秀程度为技能值之和。尽管如此，你认为把两名技能值相似的球员放在团队中是不行的，他们会产生矛盾。

- 我们称两个球员 $x,y$ 技能值相似，当且仅当不存在第三个球员 $z$ 使得 $skill_x<skill_z<skill_y$。

球队要参加 $T$ 场比赛。每场比赛有一个年龄限制 $A$，这意味着对于参加这场比赛的任意一个球员 $x$ 满足 $age_x\le A$。此外，对于每场比赛还有一个人数限制 $K$，意味着参赛人数 $\le K$。

一个球员可多次参赛。

inputFormat:
输入的第一行包含一个整数 $N$，代表球员的数量。

接下来的 $N$ 行中的每一行都包含两个空格分隔的整数 $age_i,skill_i$。

下一行包含一个整数 $T$，表示比赛的数量。

接下来 $T$ 行，每行两个整数 $A,K$，分别表示每场比赛的年龄限制和球员人数限制。

outputFormat: 对于每场比赛，输出你选择的队伍的优秀程度。

hint:
#### 数据范围：
Subtask#0 为样例。

$1\le N,T\le 3\times 10^5$，$1\le age_i,skill_i\le10^9$。

对于所有 $i\neq j$ 满足 $skill_i\neq skill_j$。

#### 样例解释：
共有 $6$ 对球员技能值相似，分别为 $(6,7)$ $(7,3)$ $(3,4)$ $(4,1)$ $(1,2)$ $(2,5)$。

第一次比赛派出球员 $1,3,6$。

第二次比赛派出球员 $1,5$。

第三次比赛派出球员 $1,3,5,6$。

第四次比赛无法派出球员，因为没有一个球员年龄 $\le10$。


title: [BalkanOI 2012] Spiral

background: 你心血来潮，去公园里骑车。

description:
公园可以看成一个 $N\times N$ 的网格，第 $i$ 行，第 $j$ 列的格子坐标为 $(i,j)$。每个格子是可以走的道路或不能走的喷泉。

你想骑出一条螺旋路径。

- 螺旋路径的定义为：从一个格子出发，向一个方向走至少 $1$ 格，进行右转，再走至少 $1$ 格，进行右转，再走至少 $1$ 格，进行右转，再走至少 $1$ 格（只右转三次）。
- 在螺旋路径中不能经过喷泉。

现在你想找出你能骑的最长螺旋路径（路径长度为经过的格子数，含首尾）。

保证存在一条螺旋路径。

inputFormat:
输入的第一行包含两个整数 $N$ 和 $K$，分别是公园的大小和喷泉的数量。

接下来 $K$ 行每行 $2$ 个整数 $x$ 和 $y$，表示在坐标为 $(x,y)$ 的格子上有一个喷泉。

outputFormat: 一行一个整数，你能骑的最长路线（即最长螺旋路径）。

hint:
#### 数据范围：
Subtask#0 为样例。

$2\le N\le 1000$，$0\le K\le \min(2000,N^2)$，$1\le x,y\le N$。

#### 样例解释：
公园如图所示，最右边图是最长螺旋路径，路径长度为 $14$，没有更长的路径。

![](https://s4.ax1x.com/2021/12/07/ockbBq.md.jpg)

注：前两幅图均为合法螺旋路径，帮助理解。


title: D ToPTree

background: ToPTree 即 **To**oth**P**aste **Tree**，它的工作方式就如同挤牙膏——挤一下它才动一下。

description:
你有 $n$ 个数组成的序列 $[a_1\sim a_n]$，初始时 $a_i=0$。

有 $q$ 次操作组成的操作序列 $A$，第 $i$ 次操作在所有可能的 $nN(n+1)$ 种操作之内均匀随机：

- 在以下两种操作之中以一半的概率随机选择一种操作，作为这次操作。
- 随机选取满足条件的正整数 $l,r,x\ (1\le l\le r\le n,1\le x\le N)$，把 $[l,r]$ 区间内的数加上 $x$。
- 随机选取满足条件的正整数 $l,r,x\ (1\le l\le r\le n,1\le x\le N)$，把 $[l,r]$ 区间内的数改为 $x$。
- 容易发现每次操作共有 $nN(n+1)$ 种可能。

由于这棵树是 ToothPaste Tree，只有在你询问的时候，它才会执行与你这次询问有关且还没执行的操作。具体地，假设你依次询问了 $a_{p_1\sim p_m}$ 的值，则

- 询问 $a_{p_i}$ 时，把所有 $A$ 中与这个数有关的操作（即这次操作的 $[l,r]$ 包含 $p_i$）按时间顺序（即按 $A$ 中的顺序）执行了，并从 $A$ 中删除它们。然后输出 $a_{p_i}$ 当前的值。

> 比如 $A$ 中目前按顺序有以下四个操作，且 $a$ 中所有元素目前都是 $0$：
>
> 1. 给区间 $[2,3]$ 加一。
> 2. 给区间 $[3,4]$ 加一。
> 3. 把区间 $[2,4]$ 赋值为一。
> 4. 给区间 $[2,3]$ 加一。
>
> 现在询问了 $a_2$ 的值，那么操作 $1,3,4$ 会被顺序执行，导致 $a_1\sim a_4$ 分别变为 $[0,2,2,1]$。因此 ToPTree 输出 $2$。操作序列变为：
>
> 1. 给区间 $[3,4]$ 加一。
>
> 再询问 $a_3$ 的值，操作 $1$ 会被执行，导致操作序列变为空，并且 $a_1\sim a_4$ 变为 $[0,2,3,2]$，故输出 $3$。注意这个输出结果与按照顺序执行所有操作 $1\sim 4$ 得到的结果并不一致。

给定 $n,m,q,N$ 以及序列 $p$，ToPTree 一共会按询问顺序输出 $m$ 个值，求这 $m$ 次输出分别的期望，对 $998244353$ 取模。

（第一次询问之前，没有任何操作被执行了。）

inputFormat:
第一行四个正整数 $n,m,q,N$。

接下来一行 $m$ 个正整数 $p_1\sim p_m$。

outputFormat: 输出一行 $m$ 个非负整数，用空格隔开，为答案，对 $998244353$ 取模。

hint:
**【数据范围】**

**本题采用捆绑测试。**

对于所有数据：$1\le n,N,q\le 9\times 10^8$，$1\le m\le 10^6$，$1\le p_i\le n$。详细数据范围如下：

- Subtask #1 (4 pts): $n,m,q,N\le 3$。
- Subtask #2 (10 pts): $n,m,q,N\le 5$。
- Subtask #3 (3 pts): $n=1$，$m,q\le 123456$。
- Subtask #4 (3 pts): $q=1$，$m\le 123456$。
- Subtask #5 (12 pts): $m=1$，$q\le 123456$。
- Subtask #6 (27 pts): $n,m,q,N\le 50$。
- Subtask #7 (9 pts): $m,q\le 5000$。
- Subtask #8 (16 pts): $m,q\le 123456$。
- Subtask #9 (16 pts): 没有任何附加限制。


title: [BalkanOI 2012] Shortest paths

background: Bit 镇的你要去 Hex 镇找你的 npy。

description:
你所在的国家有 $n$ 个镇（镇从 $1$ 到 $n$ 编号），$m$ 条双向道路，Bit 镇在 $a$ 点，Hex 镇在 $b$ 点。每条道路有一个长度。你很了解周围的地图，所以找到了两个镇之间的最短路径，而且，决定将这条路径称为幸运路径。

有一天，政府决定在公路上施工，为了维持交通，决定每次只关闭一条道路（关闭后道路不可通行）。

对于这条幸运路径上的每一条道路，你想知道当这条道路正在关闭时从 Bit 镇到 Hex 镇的最短距离。

inputFormat:
输入的第一行由 4 个整数组成：$n,m,a,b$，分别表示城镇数量，道路数量，Bit 镇编号，Hex 镇编号。

接下来的 $m$ 行，第 $i$ 行包含三个整数 $u_i,v_i,w_i$ ：城镇 $u_i$ 和城镇 $v_i$ 由长度为 $w_i$ 的道路连接。

输入的最后一行由数字 $k$ 和 $k$ 个数字组成：$(v_1(=a),v_2,\dots,v_{k}(=b))$ ，表示幸运路径。 $v_i(1\le i\le k)$ 表示幸运路径上的第 $i$ 个点的编号。

outputFormat:
输出共 $k-1$ 行。

对于每个 $t=1\dots k-1$，输出一行一个整数：道路 $(v_t,v_{t+1})$ 施工时，Bit 镇和 Hex 镇之间的最短路径的长度。如果路径不存在，则输出 `-1`。

hint:
#### 数据范围：
Subtask#0 为样例。

$1\le n\le 2000$，$1\le m\le10^5$，$1\le u_i,v_i\le n$，$1\le w_i\le10^5$。

对于 $i\neq j$，满足 $u_i\neq u_j$ 或 $v_i\neq v_j$。

#### 样例解释：

![](https://s4.ax1x.com/2021/12/07/ochxxA.jpg)

封闭道路 $(1,2)$ 后从点 $1$ 的 Bit 镇无法到达点 $5$ 的 Hex 镇。

封闭道路 $(2,3)$ 后从点 $1$ 的 Bit 镇到点 $5$ 的 Hex 镇的最短路为 $1\rightarrow 2\rightarrow5$，长度 $1+100=101$。

封闭道路 $(3,5)$ 后从点 $1$ 的 Bit 镇到点 $5$ 的 Hex 镇的最短路为 $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow5$，长度 $1+3+3+3=10$。


title: [BalkanOI 2012] handsome

background: 你是 OIer 中最帅的，所以你要做一道跟帅有关的题。

description:
一个 $N$ 位数是帅气的，当且仅当每一个数位上的数为 $1,2,3$ 中的一个。而且相邻的两个数位上的数字构成的有序数对不是“危险数对”。

- $N$ 位数 $X$ 在排列 $p$ 的意义下字典序小于 $N$ 位数 $Y$，当且仅当存在一个 $k$ 使得 $X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{k}}<Y_{p_{k}}$。

- $N$ 位数 $X$ 在排列 $p$ 的意义下字典序等于 $N$ 位数 $Y$，当且仅当$X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{N}}=Y_{p_{N}}$。

- $N$ 位数 $X$ 在排列 $p$ 的意义下字典序大于 $N$ 位数 $Y$，当且仅当存在一个 $k$ 使得 $X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{k}}>Y_{p_{k}}$。

请你输出在排列 $p$ 意义下小于等于 $B$ 的帅气数的个数模 $10^9+7$ 的值。

inputFormat:
输入的第一行包含一个整数 $N$，表示数字位数。

第二行包含 $N$ 个空格分隔的整数，表示排列 $p$。该行的第 $i$ 个整数表示 $p_i$。

第三行包含一个整数 $M$，表示危险数对个数。

第四行 $M$ 个空格分隔的两位整数，第 $i$ 个两位整数 $\overline{a_ib_i}$ 表示 $(a_i,b_i)$ 为危险数对。

第五行一个正整数 $B$ 表示给定帅气数。

outputFormat: 输出一行，表示在排列 $p$ 意义下小于等于 $B$ 的帅气数个数模 $10^9+7$。


title: 「DAOI R1」Fireworks

background:
> 俯首，满城灯火交辉。
>
> 回眸，漫天流星逆飞。

description:
人们以前通常会放烟花，而每个烟花都有它本身的美观度。

$ \texttt{Iratis} $ 想要在户外放烟花，但是有烟花之间有一些关系：

- 关系一：对于烟花 $ x $ ，有一个对应烟花 $ a_x $ ，若烟花 $ x $ 与烟花 $ a_x $ 一起燃放，就会使烟花 $ x $ 的美观度减少 $ b_x $ 。

- 关系二：有一些烟花是一个系列，必须同时燃放，其中有一个是主烟花，**每个烟花只会属于一个系列**。

特别地，若有一系列 $ S_1 $ （主烟花为 $ p_1 $ ） 。 $ p_1 $ 关系一所对应的烟花为系列 $ S_2 $ 中的烟花。而 $ S_1 $ 系列中的其他烟花与非 $ S_1,S_2 $ 系列中的烟花形成关系一。**那么对于这条关系一，它不会降低美观度。**

$ \texttt{Iratis} $ 家里有 $ n $ 个烟花，他希望选择其中的一些烟花燃放，使得这些**烟花的美观度总和**最大。

inputFormat:
第一行包含两个整数 $ n,m $，分别描述烟花的个数和和关系二的个数。

接下来 $ n $ 行，每行三个整数 $ v_i,a_i,b_i $ ，分别是这个烟花的美观度、关系一对应的烟花、关系一降低的美观度。

最后 $ m $ 行，每行先读入两个数 $ p_i,k_i $，然后是 $ k_i $ 个数，表示这 $ k_i $ 个烟花是一个系列，编号为 $ p_i $ 的烟花为主烟花。

outputFormat: 输出一行一个整数，表示烟花的美观度总和。


title: [BalkanOI 2012] balls

background: 你在玩物理画线。

description:
有 $N$ 个球和 $N$ 个杯子，从左到右编号依次为 $1\dots N$。开始时第 $i$ 个球对准第 $i$ 个杯子（不受影响的情况下第 $i$ 个球落入第 $i$ 个杯子）。第 $i$ 个杯子有一个分值 $c_i$，一个球落入一个杯子可以获得该杯子的分数（杯子容量视为无限），分数可能为负数。

你可以画两种线，线的两端点必须对准某个杯子。：
1. 从左上到右下，设左上对准的杯子编号为 $i$，右下对准的杯子编号为 $j$，使编号为 $i\dots j$ 的球全部落入第 $j$ 号杯子。

1. 从右上到左下，设左下对准的杯子编号为 $i$，右上对准的杯子编号为 $j$，使编号为 $i\dots j$ 的球全部落入第 $i$ 号杯子。

现在你想知道你只用**恰好一根**第一种线、**恰好一根**第二种线，分别能获得的最大分数。

inputFormat:
输入的第一行包含一个整数 $N$。

接下来一行 $N$ 个整数，表示 $c_1\dots c_N$。

outputFormat:
输出第一行一个整数——只使用第一种的最大分数。

输出第二行一个整数——只使用第二种的最大分数。

hint:
#### 数据范围：
Subtask#0 为样例。

$3\le N\le3\times10^5$，$|c_i|\le10^9$。

#### 样例解释：

![](https://s4.ax1x.com/2021/12/08/ogquFI.jpg)

第一幅图为第一种线，分数：$6+10+5+5+5+(-12)=19$，可以证明是最大值。

第二幅图为第二种线，分数：$6+10+10+10+10+10=56$，可以证明是最大值。


title: [JRKSJ R4] kth

background:
> 时刻记住自己是人类，不是动物。

在吃玉米番茄炖山羊肉之前，你需要回答一个问题。

description:
给定 $n,m$，称一个“合法”的整数序列为（设该序列为 $s$）：

* $s$ 长度为 $m$。
* $\forall i\in[1,m],s_i\in[1,n]$。
* $\forall i\in[2,m],|s_i-s_{i-1}|=1$。

给定一个 $[1,n]$ 的排列 $p$，并定义一个整数序列 $s$ 的“对应序列” $s'$：$s'$ 的长度和 $s$ 相同；设其长度为 $l$，那么 $\forall i\in [1,l],s'_i=p_{s_i}$。

再给定 $k$，求所有不同的合法的整数序列的对应序列中，字典序第 $k$ 小的对应序列中所有元素的和对 $2^{32}$ 取模的值。

若不存在第 $k$ 小的对应序列，输出 $-1$。

inputFormat:
第一行三个整数 $n,m,k$。\
第二行 $n$ 个整数表示 $p$。

outputFormat: 一个整数，表示答案。


title: 「EZEC-11」Tyres

background: 这道题曾经有有趣的题目背景。

description:
有 $n$ 套轮胎，滴叉需要用这些轮胎跑 $m$ 圈。

使用第 $i$ 套轮胎跑的第 $j$ 圈（对每套轮胎单独计数）需要 $a_i+b_i(j-1)^2$ 秒。在本题中，你不需要担心爆胎，安全车，红旗或者不同的比赛策略。

滴叉需要进入维修站来更换轮胎，所消耗的时间为 $t$ 秒。特别地，滴叉使用的**第一套**轮胎不需要进站更换。

为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每圈的时间之和加上进站所花费的时间。

inputFormat:
第一行输入三个整数 $n,m,t$。

接下来 $n$ 行，每行输入两个整数 $a_i,b_i$。

outputFormat: 输出一个整数，代表总时间的最小值。

hint:
**【样例解释】**

对于第一个样例：

* 你先让滴叉用第一套轮胎跑一圈，消耗 $10$ 秒。
* 然后进站更换第二套轮胎，消耗 $50$ 秒。
* 然后用第二套轮胎跑三圈。第一圈消耗 $100$ 秒，第二圈消耗 $100+1\times 1^2=101$ 秒，第三圈消耗 $100+1\times 2^2=104$ 秒。
* 总时间为 $10+50+100+101+104=365$ 秒。

对于第二个样例，滴叉每圈更换一次新轮胎。

注意一套轮胎被卸下后并不会重置它跑的圈数。

对于第三个样例，滴叉先使用第一套轮胎跑 $4$ 圈，然后更换第二套轮胎跑 $6$ 圈。

**【数据范围】**

**本题采用捆绑测试**。

- Subtask 1（7 pts）：$n=1$。
- Subtask 2（9 pts）：$n\leq10$，$m\leq 100$。
- Subtask 3（13 pts）：$t=0$。
- Subtask 4（21 pts）：保证 $a_i,b_i$ 随机生成。
- Subtask 5（50 pts）：无特殊限制。

对于前 $100\%$ 的数据，$1\leq n,b_i\leq 500$，$0\leq t\leq 500$，$1\leq m\leq 2 \times 10^5$，$1\leq a_i\leq 10^9$。


title: [COCI2013-2014#4] NASLJEDSTVO

description:
有若干个金币，一个人将这堆金币尽量 $N$ 等分并拿走了一份，剩下 $O$ 个金币。

所谓『尽量 $N$ 等分』，是指将这堆金币分成 $N$ 堆，每堆所含的金币数是整数，且每两对金币的数量相差不超过 $1$。

我们约定这个人拿走的那一份金币是比较少的一份。

请你分别求出这堆金币原来最少有多少个和最多有多少个。

inputFormat:
第一行，一个正整数 $N$，表示分成了 $N$ 等份；

第二行，一个正整数 $O$，表示拿走 $N$ 份中的 $1$ 份后剩下 $O$ 个金币。

outputFormat: 一行，两个正整数，分别表示这堆金币原来最少有多少个和最多有多少个。

hint:
**【样例解释 #1】**

这堆金币可能原来有 $9$ 个，这个人可能将其分成 $4+5$ 个，自己拿走 $4$ 个；

这堆金币可能原来有 $10$ 个，这个人可能将其分成 $5+5$ 个，自己拿走 $5$ 个。

**【数据范围】**

对于 $100\%$ 的数据，$2\le N\le 15$，$N\le O\le 100$。

**【来源】**

本题分值按 COCI 原题设置，满分 $50$。

题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T1 NASLJEDSTVO**_。


title: [COCI2013-2014#4] GMO

description:
给定一个由 `A` `C` `G` `T` 组成的字符串，你需要在这个字符串中插入若干个 `A` `C` `G` `T`，使字符串中包含目标字符串，并使花费的代价最少。

其中插入不同的字符花费的代价也是不同的。

inputFormat:
第一行，一个字符串 $N$，代表原字符串；

第二行，一个字符串 $M$，代表目标字符串；

第三行，四个正整数 $a,c,g,v$，分别表示插入一个 `A` 花费的代价，插入一个 `C` 花费的代价，插入一个 `G` 花费的代价，插入一个 `T` 花费的代价。

outputFormat: 一行，一个正整数，表示最小花费。

hint:
**【样例解释 #1】**

可能的方法中有：`GTCAT`，花费 $10$，可以证明是最小花费。

**【数据范围】**

对于 $80\%$ 的数据，$1\le |N|,|M|\le 2000$；

对于 $100\%$ 的数据，$1\le |N|\le 10000$，$1\le |M|\le 5000$，$0\le a,c,g,v\le 1000$。

**【来源】**

本题分值按 COCI 原题设置，满分 $80$。

题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T2 GMO**_。


title: [COCI2013-2014#4] SUMO

description:
有 $N$ 个选手参加 $M$ 场 $1$ 对 $1$ 的比赛，比赛顺序已经定好。

现在让你将这些选手分成 $2$ 队，使选手尽可能晚地碰到同队的选手。

输出最优方案下第一次有选手碰到同队的的选手的比赛序号。

inputFormat:
第一行，一个正整数 $N$，表示有 $N$ 个选手；

第二行，一个正整数 $M$，表示有 $M$ 场比赛；

接下来 $M$ 行，每行两个正整数 $A_i$ 和 $B_i$，表示序号为 $i$ 的比赛参与的选手是序号为 $A_i$ 和 $B_i$ 的两位选手。

outputFormat: 一行，一个正整数，表示最优分队方案下第一次有选手碰到同队的的选手的比赛序号。

hint:
**【样例解释 #1】**

$[1,3,5]$ 一队， $[2,4]$ 一队。

可以证明这是最优方案。

**【数据范围】**

对于 $100\%$ 的数据，$1\le A_i,B_i\le N\le 10^5$，$1\le M\le 3\times 10^5$。

**【来源】**

本题分值按 COCI 原题设置，满分 $100$。

题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T3 SUMO**_。


title: [COCI2013-2014#4] GUMA

description:
给出一个 $N+1$ 列的矩形，第 $i$ 列必须通过水平切割 $A_i-1$ 次被等分成 $A_i$ 份，请你求出最少需要几次切割才能按要求分割完。

$Tips:$ 一次切割一次可以在一个或多个不一定连续的列上进行分割。

inputFormat:
第一行，一个正整数 $N$，表示这个矩形有 $N+1$ 列；

接下来 $N+1$ 行，每行一个正整数 $A_i$，表示第 $i$ 列必须通过水平切割 $A_i-1$ 次被等分成 $A_i$ 份。

outputFormat: 一行，一个正整数，表示最小分割数。

hint:
**【样例解释 #3】**

![](https://cdn.luogu.com.cn/upload/image_hosting/v45dq77p.png)

共 $7$ 次切割。

**【数据范围】**

对于 $20\%$ 的数据，$1\le N\le 100$；

对于 $100\%$ 的数据，$1\le N,A_i\le 10^5$。

**【来源】**

本题分值按 COCI 原题设置，满分 $120$。

题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T4 GUMA**_。


title: 声海 | Sea of Voices

background:
「真是，如梦似幻呢。」

“怎么？”

「我看见你从开始到现在的一切记忆；看见你，从一次次或欢喜或失落中走来。那些场景在我眼前浮现，像梦，却又那么模糊——我只听见那些声音，只感到那片声音的海洋将我环围… 你听得见吗？」

“当然。毕竟，它们是我的记忆啊。”

「或许，一次生命，便是一场发声的历程吧。我们诞生时的啼哭，便在向世界发出宣告降临的声音；在一次次挑战的过程中，我们向一切阻碍我们的事物唱出不屈的战歌；在日常的点滴中，我们向所珍视之人倾诉内心深处的话语… 这样的声音，这样的感情，是不是就是我们所生存世界的本质呢？」

“或许就是这样吧。纵使一路走来，我们看见了无尽的景色，但只有那些与我们内心共鸣的声音——或来自于自然、或来自于他人的灵魂——才会真正地改变我们自己。”

「是啊… 但愿，在这片声音的海洋里，你不会迷失你的方向。我期许着听见更多，关于你的声音。怀揣着这种信念，向前走下去吧。」

“你也一样。”

> We'll see creation come undone
>
> 我们会见证自己存在的印记被世界拂去
>
> These bones that bound us will be gone
>
> 而那些既有的束缚将不再留存
>
> We'll stir our spirits till we're one
>
> 我们会洗涤自己的灵魂直至合为一体
>
> Then soft as shadows we'll become
>
> 然后成为掠影，散失在虚无之中

description:
“但是… 曾有一些人，在我的生命里留下了重要的声音，我却无法回忆起了…”

「为什么呢？」

“不妨让我们把问题变得形式化一点。我想回忆起的声音有 $n$ 个，它们的共鸣度——非负整数 $a_i$，是单调不降的。最初它们互不干涉，但随着时间的推移，多个相邻的声音会交织在一起形成新的声音——也就是说，对于任意的 $1\le l\le r\le n$，第 $l$ 一直到第 $r$ 个声音会交织在一起形成新的声音，而这个声音的共鸣度便是这些声音共鸣度的总和。”

「也就是说，例如 $n=3$，$a=[1,2,4]$，那么最终 $\dfrac{3\times(3+1)}2=6$ 个声音的共鸣度分别是 $1,2,4,3,6,7$？」

“没错。现在我把最终所有声音的共鸣度无序地告诉你，你能帮我还原最开始 $n$ 个声音的共鸣度吗？”

「乐意之至。」

### 简要题意

$a$ 为长度为 $n$ 的非负整数序列，满足 $\forall 1<i\le n,a_{i-1}\le a_i$。现 **无序** 地给出 **可重集** $S=\left\{\sum_{k=l}^r a_k|1\le l\le r\le n\right\}$，试还原 $a$。

inputFormat:
第一行一个正整数 $n$，代表最初声音的个数。

接下来一行 $\dfrac{n\times(n+1)}2$ 个非负整数，表示现在所有声音的共鸣度（输入无序）。

outputFormat: 一行 $n$ 个非负整数，表示最初 $n$ 个声音共鸣度 $a_i$。

hint:
对于全部数据，有 $1\le n\le 2000$，$0\le a_i\le 10^5$。

Subtask 1（5 pts）：保证 $n=2$。

Subtask 2（15 pts）：保证 $n=3$。

Subtask 3（30 pts）：保证 $n\le 100$。

Subtask 4（50 pts）：无特殊限制。


title: 泪光 | Tears

background:
「为什么哭呢？」

“因为自己的期许和现实相去甚远。”

「哭能改变什么呢？」

“什么都不能。正如同既成事实的过去一样。”

「那么为何不抹去泪水向前迈进呢？」

“… 我在等我的灵魂追上时间。”

> After night
>
> 长夜之后
>
> In boundless light
>
> 无垠光中
>
> He calls my name
>
> 他呼唤着我
>
> I do the same
>
> 我望向彼方，回应

description:
「不想回忆的事，就别再去想了吧。为了分散你的注意力，正好我有一道与人的感情相关的题目，你看看怎么样？」

“… 真是令人想吐槽呢。怎么，又是那个人在支配吗？”

「什么嘛，令人不快… 你以前对这种事不是有很大的热情吗？」

“… 说不准。”

「咳咳… 那么听好了。现在共有 $n$ 个人，每个人都有一个情绪值：用 **实数** $v_i$ 表示。现在由于一些特殊的变化，使得这些人的情感发生了纠缠…」

“嗯哼？”

「第一种纠缠有四个参数 $a,b,c,d$，表示：现在已知存在无穷个 $f:\R\rightarrow\R$，使得 $\frac{f(v_a)}{f(v_b)}=\frac{v_c}{v_d}$。」

“等等等等一下！这数学公式是怎么说出来的啊？！还有什么 $f:\R\rightarrow\R$ 是什么意思啊！”

「你瞧，你不也说出来了吗？」

“… 可恶，果然是你吗，那个人…”

「简单来说，$f:\R\rightarrow\R$ 就是代表一个定义域和值域都是实数的函数。如果这都不能理解的话，我要开始怀疑你作为高中生的身份了哦…」

“好吧… 继续吧。”

「第二种纠缠有两个参数 $a,b$，表示：现在已知存在有穷个 $f:\R\rightarrow\R$，使得 $f(v_a)\ne f(v_b)$。」

“什么叫‘有穷个’？”

「就是有一个确切的数目啦… 只要有一个自然数 $k$ 能表示这样函数的数目，那么就叫‘存在有穷个函数’哦？」

“嗯…”

「接下来，在纠缠不断增加的过程中，你也需要回答一些问题。第一种是，给出 $a,b$，你需要判断 $v_a$ 是否总是等于 $v_b$；第二种是，给出 $a$，你需要计算有多少个 $b$（$1\le b\le n$，$b$ 可以等于 $a$）使得 $v_a=v_b$ 恒成立。」

“… 题目我明白了，但是这跟人的情感有什么关系吗？”

「哈哈… 就是想逗你开心嘛，别那么严肃。」

“… 无聊。”

### 简要题意

有 $n$ 个 **正实数** 变量 $v_1,\dots,v_n$。你需要根据当前已知的条件作出判断。每次给出两种条件之一：

- 给出常数 $a,b,c,d$：表示现在已知存在无穷个 $f:\R\rightarrow\R$，使得 $\frac{f(v_a)}{f(v_b)}=\frac{v_c}{v_d}$。

- 给出常数 $a,b$：表示现在已知存在有穷个 $f:\R\rightarrow\R$，使得 $f(v_a)\ne f(v_b)$。

或者两种询问之一：

- 给出常数 $a,b$：询问 $v_a=v_b$ 是否恒成立。

- 给出常数 $a$：询问有多少个 $b$（$1\le b\le n$，$b$ 可以等于 $a$）使得 $v_a=v_b$ 恒成立。

inputFormat:
第一行两个正整数 $n,m$，分别表示变量的数量和操作的次数。

接下来 $m$ 行，每行表示一次操作，有四种可能：

- `1 a b c d`：表示现在已知存在无穷个 $f:\R\rightarrow\R$，使得 $\frac{f(v_a)}{f(v_b)}=\frac{v_c}{v_d}$。

- `2 a b`：表示现在已知存在有穷个 $f:\R\rightarrow\R$，使得 $f(v_a)\ne f(v_b)$。

- `3 a b`：询问 $v_a=v_b$ 是否恒成立。

- `4 a`：询问有多少个 $b$（$1\le b\le n$，$b$ 可以等于 $a$）使得 $v_a=v_b$ 恒成立。

outputFormat:
对于每次操作三，输出一行字符串 `entangled` 表示 $v_a=v_b$ 恒成立；反之输出一行字符串 `separate`。

对于每次操作四，输出一行一个整数表示符合条件的 $b$ 的数目。

hint:
对于全部数据，有 $1\le n,m\le 6\times 10^5$。保证操作一中 $a\ne b,c\ne d$，操作二中 $a\ne b$，操作三中 $a\ne b$。

Subtask 1（5 pts）：保证不出现操作一和操作二。

Subtask 2（10 pts）：保证不出现操作一。

Subtask 3（35 pts）：保证 $n\le 5000$。

Subtask 4（50 pts）：无特殊限制。


title: 彼岸 | To See the Next Part of the Dream

background:
「“看见梦境的下一个部分”…？」

“是啊… ‘尽管身体已是成年人，但内心却依旧是那个不切实际的小孩，依旧是那个相信自己有着无尽可能的小孩——即使是在认清了现实和理想的鸿沟后，还仍是如此。年少时那个成为摇滚巨星的梦，如今已显得分外不可及，只能在一次次前行中看见梦的下一个部分’… 不觉得作者和我很像吗？”

“曾经年少的自己对一切的未知都怀揣着好奇与欣喜，但如今仿佛只是在如同抓住救命稻草一般抓住自己背离现实的梦想，然后在生活的洋流中逐渐看见梦的下一个部分… 明知自己的失败，却仍在仿佛为了看见什么、达成什么一样向上登攀，这样一来，和作者所描述的‘active loser’也没什么两样吧…”

「所以，你所期望看见的、期望达成的，究竟是什么呢？」

“…”

“现在的我，已经不知道了。”

> 나의 어리고 멍청했던 날들은 사라져줬으면
>
> 如果那些年少无知的日子消失掉就好了
>
> 나의 소중한 인연들 이제는 추억속으로만
>
> 珍贵的感情 现在仅仅存在于在记忆中
>
> 만약 이 세상이 전부 누군가의 또다른 꿈이었다면
>
> 如果这个世界 只是别人的梦
>
> 언젠가 깨어나게 될때 나는 지금과는 달라져있을까
>
> 某天醒来时 我会变得不一样吗

description:
「那么，你相信宿命吗？」

“那种东西，顶多只是什么励志故事里的抒情工具吧。”

「是吗… 那么要玩玩塔罗牌吗？」

“谁会对那种事情感兴趣…”

「真是的，你要再一副对什么事情都漠不关心的态度我要生气了…！」

“好好好… 所以呢？塔罗牌呢？”

「这个嘛… 嘿嘿，自己想象咯～」

“什么毛病…”

「现在有 $n$ 叠塔罗牌放在桌上，每一叠都有 $2^n$ 张，从桌面向上分别是 $1$ 号、$2$ 号… $n$ 号。现在作为宿命的管理者的我们——要洗一遍这些塔罗牌！」

“怎么… 中二病开始传染了吗…”

「那么，洗牌的过程是，将牌均匀地分成两半，下面一半和上面一半分别放在左右手；接着，右手从底部放下一张牌，左手从底部放下一张牌，右手又从底部放下一张牌… 这样交错重复，于是一次洗牌就完成了！」

“例如 $n=2$ 时，假设原来的牌从下往上看是 $[1,2,3,4]$，洗一次牌后就会变成 $[3,1,4,2]$——是这样吗？”

「是的！然后对于这 $n$ 叠初始时都按顺序从下到上摆放的塔罗牌，我会不操作第一叠牌，然后洗一次第二叠牌，洗两次第三叠牌… 洗 $n-1$ 次第 $n$ 叠牌。接下来，我会把这 $n$ 叠牌都从下到上地发给 $2^n$ 个人——也就是说第一个人会拿到每叠牌的第一张，第二个人会拿到每叠牌的第二张… 每一个人都恰好会拿到 $n$ 张牌。」

「现在，定义一个人拿到和自己号码相同的牌的张数为这个人的幸运值。你能算出这 $n$ 个人幸运值的总和是多少吗？」

“嗯… 撇开你粗制滥造的题面不谈，这个题目还是很有趣的。”

「适可而止啊喂！」

“… 我想了想，好像还挺简单的。不妨让我们记 $n=k$ 的时候的幸运值总和为 $f(k)$。现在你需要对 $l\le k\le r$ 的 $f(k)$ 求和，你看怎么样？”

「… 不是很会了…」

### 简要题意

对于长度为 $2k$ 的序列 $a$，定义函数 $S_q(a)$，其中

$$
S_q(a)=
\begin{cases}
a,&q=0\\
[a_{k+1},a_1,a_{k+2},a_2,\dots,a_{2k},a_k],&q=1\\
S_{q-1}(S_1(a)),&\text{otherwise.}
\end{cases}
$$

现在给定正整数 $l,r$，求 $\sum_{k=l}^r f(k)$，其中

$$
f(n)=\sum_{q=0}^{n-1}\sum_{k=1}^{2^n}\left[S_q([1,2,3,\dots,2^n])_k=k\right]
$$

inputFormat: 一行两个正整数 $l,r$，代表求和的起始和终点。

outputFormat: 输出一行一个正整数，代表 $\sum_{k=l}^rf(k)$。答案对 $998244353$ 取模。

hint:
### 样例解释

以样例一中计算 $f(2)$ 为例。最初有 $2$ 叠牌，从下到上的牌都是 $[1,2,3,4]$。然后现在对第一叠牌不操作，第二叠牌洗一次，于是第二叠牌从下到上变成了 $[3,1,4,2]$。现在把两叠牌发给 $4$ 个人。第一个人拿到 $[1,3]$，第二个人拿到 $[2,1]$，第三个人拿到 $[3,4]$，第四个人拿到 $[4,2]$。发现每个人的幸运值都为 $1$（都恰好拿到了一张和自己号码相同的牌），于是幸运值总和就是 $4$，继而 $f(2)=4$。

### 数据范围

对于全部数据，有 $1\le l\le r\le 10^{10}$。

Subtask 1（10 pts）：保证 $l=r$ 且 $r\le 12$。

Subtask 2（35 pts）：保证 $l=r$。

Subtask 3（15 pts）：保证 $1\le l\le r\le 10^6$。

Subtask 4（40 pts）：无特殊限制。


title: [WFOI - 01] 循环节（circle）

background:
简化题意：[$\texttt{Link}$](https://www.luogu.com.cn/paste/v7gqdh44)。

出题人注：これは非常に嫌な質問なので、あまり時間をかけたくない場合は、この質問を見る前に他の質問を終えることをお勧めします。

description:
给你一个坐标系上的点集 $a$，你需要找出一个子点集 $b$ 和一个向量 $x$，使得 $\exist\ z\in N^+,\{b\cup b+x\cup b+2x\cup\dots\cup b+zx=a\}$。

现在想让你求出任意一对 $b_0,x_0,z_0$，其中 $z_0$ 为所有满足条件的三元组中 $z$ 最大的，$b_0$ 中任意三点不共线，任意四点不构成梯形或平行四边形且 $b_0\cap b_0+x_0=\varnothing,b_0\cap b_0+2x_0=\varnothing,\dots,b_0\cap b+yx_0=\varnothing|{y\to+\infty}$。

其中 $b+x$ 的意思是，$b$ 中的所有点都平移向量 $x$ 后组成的点集。

inputFormat:
第一行一个正整数 $n$。

接下来 $n$ 行，每行 $2$ 个整数，表示一个点。

outputFormat:
输出共 $4$ 行：

第一行一个整数 $|b|$。

第二行 $|b|$ 个整数 $b_1,b_2,\dots,b_{|b|}$（对应编号）。

第三行两个整数 $x$。

第四行一个整数 $z$。

hint:
由于本题有样例解释也只是照着念一遍，并且相信既然您都做到这一题来了应该能读懂题目含义，所以本题不提供样例解释（~~其实是出题人懒~~）。

**本题采用 Subtask 捆绑测试。**
Subtask 编号 | 数据规模与约定
:-: | :-:
**Subtask #0($\text{20 pts}$)** | $1\le n\le10$；$-10\le x_i,y_i \le 10$
**Subtask #1($\text{20 pts}$)** | $1\le n\le10^3$
**Subtask #2($\text{30 pts}$)** | $z>1$
**Subtask #3($\text{30 pts}$)** | 无特殊限制

对于 $100\%$ 的数据，$1\le n\le10^5$，点的坐标范围 $\in\left(-10^9,10^9\right)$，数据保证有解。


title: [WFOI - 01]  刷题 （problem）

background: 简化题意：[$\texttt{Link}$](https://www.luogu.com.cn/paste/ievt77rm)。

description:
你初始能力为 $0$。

现在有 $n$ 个题库，每个题库的题有同一个难度 $a_i$，并且题目数量可以视为无限多。现在你要刷 $m$ 道题，每道题都是所有题中你选择出来的一道。

假设你目前做到的题目难度是 $x$，则：

当你的能力比这个题大或等于此题时，你将花费你的能力以攻破此题（此时你的能力减去 $x$）；否则，你将认真钻研此题，钻研出此题后能力增加 $x$（此时不会导致能力减少）。

现在你想知道你做 $m$ 题后能力最大值。由于你的小伙伴也要刷题，所以**有多次询问**，询问之间相互独立，也就是说每次询问的能力初值为 $0$。

inputFormat:
第一行输入 $2$ 个数 $n,T$；

第二行输入 $n$ 个数，表示数组 $a$；

接下来 $T$ 行，每行一个整数，表示询问。

outputFormat: 对于每一个询问，输出相应的结果。


title: [WFOI - 01] 猜数（guess）

background:
**这是一道交互题。交互库自适应。请注意特殊的时间限制。**

**每次输出后请记得清空缓存**

简化题意：[$\texttt{Link}$](https://www.luogu.com.cn/paste/xx7sa8go)。

description:
你需要猜一个正整数 $q$，保证 $q\in [1,n]$；

你每次可以用诸如 `? x y` 的询问，交互库会在 $[x,y]$ 中指定选择一个数 $z$；

然后交互库会输出形如 `u v` 的回答，表示指定的数是 $u$，其与 $q$ 的关系为 $v$；

具体地，
- 当交互库返回的 $v=0$ 时，表示 $u<q$；
- 当交互库返回的 $v=1$ 时，表示 $u=q$；
- 当交互库返回的 $v=2$ 时，表示 $u>q$。

而一次询问的代价是 $\dfrac{1}{y-x+1}$；

你可以通过 `! x` 输出你认为正确的答案。

现在你要求出 $q$。

------------

设你的代价为 $x$，你每个测试点获得的分数和你的总代价有如下关系（每个测试点满分 $10$ 分）：

- 若 $x\le 1.9813035$，则你可以得到 $\text{10 pts}$；
- 若 $1.9813035 < x \le 12$，则你可以得到 $\lfloor(12-x)\times0.7 \div 1.00186965\rfloor  \text{ pts}$。
- 若 $x\ge12$，则你可以得到 $\text{0 pts}$。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

### 交互格式

一开始交互库会给你 $n$，

然后你可以按题目描述中的方式进行询问或回答答案；

在回答后请立即退出程序。

inputFormat: 见交互格式。

outputFormat: 见交互格式。


title: [WFOI - 01] 翻转序列（requese）

background:
简化题意：[$\texttt{Link}$](https://www.luogu.com.cn/paste/kmmn8pyd)。

为什么做完这题你不去做做[这题](https://www.luogu.com.cn/problem/P8223)呢

description:
你需要在一台奇怪的电脑上排序一个 $1\sim n$ 的排列。

你可以选择一个数 $x$，然后你每次可以翻转一段长为 $x+1$ 或一段长为 $x-1$ 的序列。

请在 $20\times n$ 次内还原成 $1\sim n$ 的序列。

（出题人注：现在最优可以达到15000次以下，请尝试优化您的算法）

inputFormat:
输入共 $2$ 行：

第一行一个数 $n$。

第二行 $n$ 个数，表示序列 $a$。

outputFormat:
输出共 $m + 2$ 行。

前两行每行 $1$ 个数，分别是 $x,m$。$m$ 表示操作次数。

接下来 $m$ 行，每行两个数，表示翻转区间的左、右端点。

本题采用 $\text{SPJ}$，只要翻转操作正确即可给分。


title: [WFOI - 01] 硬币（coin）

description:
你面前有一排 $n$ **堆**硬币排成一线，**同一堆硬币**的面值相同，记第 $i$ 堆硬币的面值为 $a_i$。而**每堆硬币**的数量都相同，记为 $x$。

现在你知道每第 $i$ 堆硬币的面值 $a_i$，你需要确定一个**正整数** $x$，使得**每堆硬币的总金额的**方差最接近于一个**正整数** $k$。

两数 **“最接近”** 的定义：两数之差的绝对值最小。

方差定义：方差 $s ^ 2 = \cfrac{(a_1 - \bar x)^2 + (a_2 - \bar x) ^ 2 + \cdots + (a_n - \bar x) ^ 2}{n}$，其中 $\bar x$ 代表 $x$ 的平均值。

inputFormat:
第一行两个数 $n,k$。

第二行 $n$ 个数，第 $i$ 个数表示 $a_i$，表示第 $i$ 堆硬币的面值 $a_i$。

outputFormat: 一行一个**正整数**，表示符合题意的 $x$ 值。如果有不同的答案，输出最小的一个。如果无论 $x$ 取什么值方差都为 $0$，输出一行 `No answer!`。

hint:
**【样例 $\#1$ 解释】**

  当 $x=3$ 时，第 $i$ 个堆的硬币金额为 $3\times a_i$，这些硬币堆的金额分别为 $21,6,12,18,9,21,30$，可以计算得这些硬币金额的方差约为 $58.78$，可以证明当 $x=3$ 时方差最接近 $47$。

**【样例 $\#2$ 解释】**

  可以发现，无论 $x$ 的取值，方差都会为 $0$，所以输出 `No answer!`。

**【数据规模】**

**本题采用 Subtask 捆绑测试。**

Subtask 编号 | $n,\forall a_i\le$ | $k\le$ | $\footnotesize\texttt{测试点数目}$ |
:-: | :-: | :-: | :-:
**Subtask #0 $(20\texttt{pts})$** | $10^3$ | $10^9$| $6$ |
**Subtask #1 $(25\texttt{pts})$** | $10^5$ | $10^{12}$| $6$ |
**Subtask #2 $(25\texttt{pts})$** | $10^5$ | $10^{18}$| $6$ |
**Subtask #3 $(30\texttt{pts})$** | $7\times10^6$ | $3\times 10^{18}$| $6$ |

对于 $100\%$ 的数据，$1\le n,\forall a_i\le7\times10^6$，$1\le k\le3\times10^{18}$。记原来 $a$ 数组的方差为 $p$，则数据满足 $p=0$ 或 $p\in[0.25,\ 2^{63}-1]$ 。

**【提示】**

  本题读入量较大，请使用合适的读入方式。此处推荐[快速读入模板](https://www.luogu.com.cn/paste/bcfvgxr7)，对于 $\texttt{C/C++}$ 语言，你也可以使用 `scanf` 语句完成读入。

  为避免卡精度，建议 `C/C++` 选手使用 $\texttt{double}$ 类型，并不建议使用 `eps`。


title: [COCI2013-2014#4] ČOKOLADE

description:
Mirko 举行了 $N$ 场聚会，每天举行一场，对于第 $i$ 场聚会他会邀请每桌 $i$ 个人。

Mirko 准备了 $N$ 张桌子，第 $i$ 张桌子上放了 $V_i$ 颗糖。

当每个被邀请的人入座后，坐在同一桌的人会平分这个桌子上的糖。或者说，对于第 $i$ 天的第 $j$ 个桌子，坐在这个桌子的每个人会得到 $\lfloor \dfrac{V_j}{i} \rfloor$ 颗糖。

糖果数量每天都会更新，不会因为平分而减少。

只有人均得到糖果相同的桌子才会社交。

现在，Mirko 想让你对于 $1$ 到 $N$ 中的每一个正整数 $s$，求出正好有 $s$ 桌社交的最早的一天是第几天。

inputFormat:
第一行，一个正整数 $N$，表示聚会场数；

第二行，$N$ 个正整数 $V_i$，表示第 $i$ 个桌子上放了 $V_i$ 颗糖。

outputFormat: 共 $N$ 行，每行一个正整数，第 $i$ 行表示正好有 $i$ 桌社交的最早的一天是第几天，若没有正好 $i$ 桌社交的情况则输出 `-1`。

hint:
**【样例解释 #1】**

第一天，所有桌都不会跟别的桌交流；

第二天，$1,2$ 号桌每个人都拿到了 $5$ 颗糖，故这两桌的人会交流；

第三天，$1,2,3$ 号桌每个人都拿到了 $3$ 颗糖，故这三桌的人会交流；

第六天，$1,2,3,4$ 号桌每个人都拿到了 $1$ 颗糖，故这四桌的人会交流；

第十二天，$1,2,3,4,5$ 号桌每个人都拿到了 $0$ 颗糖，故这五桌的人会交流；

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 100$，$1\le V_i\le 10^8$。

**【来源】**

本题分值按 COCI 原题设置，满分 $140$。

题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T5 ČOKOLADE**_。


title: [COCI2013-2014#4] UTRKA

description:
Mirko 和 Slvako 参加了一次竞速比赛，这次比赛的地图有 $N$ 个村庄和 $M$ 条路。对于第 $i$ 条路有两个参数 $M_i$ 和 $S_i$，分别表示 Mirko 和 Slvako 通过这条路所需的时间。

比赛以同一个村庄为起点和终点。现在请你求出一条路线，使得 Mirko 通过这条路线所需的时间尽可能地优于 Slvako 通过这条路线所需的时间。

换句话说，令 $X$ 为 Mirko 通过路线所需的时间，$Y$ 为 Slvako 通过路线所需的时间，你需要求出一条路线，使这条路线通过的村庄数尽可能少的同时使 $Y-X$ 尽可能大。

inputFormat:
第一行，两个正整数 $N$ 和 $M$，表示共 $N$ 个村庄和 $M$ 条道路；

接下来 $M$ 行，每行四个正整数 $A_i,B_i,M_i,S_i$，分别表示第 $i$ 条道路连接村庄 $A_i$ 与 $B_i$，Mirko 通过这条路线所需的时间为 $M_i$，Slvako 通过这条路线所需的时间为 $S_i$。

outputFormat: 一行，两个正整数，分别表示所求道路通过的村庄数以及在这些通过村庄数最小的道路中使 $Y-X$ 最大的那条道路的 $Y-X$ 的值。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$2\le A_i,B_i\le N\le 300$，$A_i\ne B_i$，$2\le M\le N\times (N-1)$，$0\le M_i,S_i\le 10^6$。

**【来源】**

本题分值按 COCI 原题设置，满分 $160$。

题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T6 UTRKA**_。


title: [JRKSJ R4] Stirling

background:
可能对您无用的提示：

$$f(n)=\sum_{i=0}^n \begin{Bmatrix} n\\i\end{Bmatrix}g(i) \leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} \begin{bmatrix} n\\i\end{bmatrix} f(i)$$

description:
对于 $[1,n]$ 的排列 $p$，定义其“生成图”为：该图有 $n$ 个点，且 $\forall 1\le i\le n$，无向边 $(i,p_i)$ 存在且仅存在这些边。

给定 $n$，求有多少个 $[1,n]$ 的排列满足其生成图恰有偶数个环（自环同样计入）。

inputFormat: 一个整数 $n$。

outputFormat: 一个整数，表示答案。答案对 $998244353$ 取模。


title: [传智杯 #4 初赛] 小卡和质数

background:
小卡最近迷上了质数，所以他想到了一个和质数有关的问题来考考你。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

description:
小卡有 $T(1\le T\le 10^5)$ 组询问。每次询问给你两个正整数 $x,y(1\le x,y\le 10^9)$。

小卡想知道，第 $x$ 个质数和第 $y$ 个质数是否满足 $p_x \oplus p_y =1$，即第 $x$ 个质数和第 $y$ 个质数的异或值是否是$1$。

inputFormat:
第一行一个正整数 $T$，表示询问的数量。

接下来 $T$ 行，每行两个正整数 $x,y$，表示询问的是第 $x$ 个质数和第 $y$ 个质数。

outputFormat: $T$ 行，每行一个字符串`Yes`或`No`，分别表示两个质数的异或值是 $1$ 或不是 $1$。


title: [传智杯 #4 初赛] 小卡与落叶

background:
坐在飞驰的火车上，望着窗外泛黄的树叶，“又是一个冬天”，小卡心想。这是一个万物凋零的季节，一阵寒风刮过，树叶就被染黄了，再一阵寒风刮过，便是满地金黄。

百无聊赖之际，小卡发现，树叶变黄是有规律的，每一颗树，只有下面一半是黄的，上半部分都是绿的。小卡心想，该怎么统计黄色的叶子个数呢？

description:
给你一棵有 $n(1\le n\le 10^5)$ 个结点的有根树，根结点标号为 $1$，根节点的深度为 $1$，最开始整棵树的所有结点都是绿色的。

小卡有 $m(1\le m \le 10^5)$ 个操作。

操作一：把整棵树都染绿，之后让深度 $\ge x$ 的结点变黄。

操作二：询问一个结点 $x$ 的子树中有多少个黄色结点。

inputFormat:
第一行两个正整数 $n,m$，表示树的结点个数和操作个数。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示树上的一条边。

接下来 $m$ 行，每行两个正整数 $op,x(1\le x\le n)$，如果 $op=1$ 则表示操作一，否则表示操作二。

outputFormat: 对于每个操作二，输出一行一个正整数，表示 $x$ 的子树中黄色结点的个数。

hint:
样例一中的树如下：

![](https://cdn.luogu.com.cn/upload/image_hosting/5paln9hs.png)

第一次染色将 $4$ 和 $5$ 染为黄色，查询 $5,2,1$ 三个点的子树，答案分别为 $1,2,2$。

第二次染色将 $2,3,4,5$ 染为黄色，查询 $1,4,5,2$ 四个点的子树，答案分别为 $4,2,1,3$。


title: [传智杯 #4 初赛] 竞争得分

description:
为了鼓励大家写出更好的作业，花栗鼠科技大学（Hualishu University of Science and Technology, HUST）的组原实验采用了竞争得分的方式。

具体来说，假设有 $n$ 个人提交了作业，并且其中原始得分最低的人记作 $a_{min}$ ，原始得分最高的人记作 $a_{max}$，第 $i$ 个人的原始得分为 $a_i$，那么第 $i$ 个人的得分就是：
$$100 \times \frac{a_i-a_{min}}{a_{max}-a_{min}}$$

由于成绩系统的问题，最终录入的成绩只能是整数，**采用直接去掉小数部分的方法**。

inputFormat:
第一行一个整数 $n$ 表示人数。（$1 \leq n \leq 1000$）

第二行共$n$ 个整数，为序列 $a$ ，其中 $a_i$ 表示第 $i$ 个人的原始作业得分。（$1 \leq a_i \leq 1000$）

outputFormat: 一行，共 $n$ 个整数，表示经过更新后每个人的得分。


title: [传智杯 #4 初赛] 小卡与质数 2

background: 小卡迷上了质数！

description:
小卡最近迷上了质数，所以他想把任何一个数都转化为质数！

小卡有 $T$ 次询问，每次给你一个数字 $x$，问有多少个比 $x$ 小的非负整数 $y$，使得 $x\oplus y$ 是质数，其中 $\oplus$ 表示按位异或。

inputFormat:
第一行一个正整数 $T(1\le T\le10^5)$，表示有 $T$ 组询问。

接下来 $T$ 行，每行一个正整数 $x(1\le x\le 10^6)$。

outputFormat: 对于每组询问，输出一行一个整数，表示答案。


title: [传智杯 #4 初赛] 组原成绩

description:
花栗鼠科技大学（Hualishu University of Science and Technology, HUST）的计算机组成原理快要出分了。你现在需要计算你的组原成绩如何构成。

具体来说，组原成绩分为三部分，分别是平时出勤 $t$ ，作业 $h$ 和考试 $e$ 。总成绩 $w$ 由如下公式计算：

$$w=t \times 20\% +h \times 30\%+e \times 50\%$$

其中我们保证 $0 \leq h,e,t \leq 100$

现在你知道了你的组原考试的 $t,h,e$ ，你希望计算你的总成绩。

由于教务系统的特殊性，最终成绩只能是整数，采取 **直接去掉小数部分** 的办法。

inputFormat: 一行三个整数，表示 $t,h,e$

outputFormat: 一行一个整数，为 $w$


title: [传智杯 #4 初赛] 报告赋分

description:
花栗鼠科技大学的计算机组成原理实验最终的结课考核方式是提交一份报告。

然而作为任课老师，萝老师不希望大家过于内卷，所以指定了如下规定：

每份报告有一个卷面基础分 $a$。

在此基础上：

- 若是报告字数低于 $16$ 页，则扣 $10$ 分，如果分数低于 $0$ 分了，则记作 $0$ 分。

- 若是报告字数超过 $20$ 页，每超过 $1$ 页扣 $1$ 分 ，直到分数扣到 $0$ 分为止。

现在你知道了一份报告的卷面基础分 $a$ 和它的页数 $p$ ，请你计算这份报告的最终得分。我们保证 $1 \leq a \leq 100,1 \leq p \leq 50$.

inputFormat:
本题有多组数据。

第一行一个整数 $T(1 \leq T \leq 1000)$ ，表示数据组数。

接下来 $T$ 行，每行两个整数 $a,p$，意义如题所示。

outputFormat: 共 $T$ 行，每行一个整数，表示该次询问的数据最终的得分。


title: [传智杯 #4 初赛] 萝卜数据库

description:
花栗鼠很喜欢偷吃生产队的大萝卜，因此花栗鼠科技大学正在研究一种新型的数据库，叫做萝卜数据库。

具体来说，它支持 $k(1 \leq k \leq 100)$ 个字段，每个字段名都是整数，里面存储的数值也都是整数。

现在你支持如下操作：

- 向数据库中插入一个记录，它可能只会包含 $k$ 个字段的某一部分。具体的操作格式详见“输入格式”。

- 在数据库中查询有多少条符合条件的记录。

现在你总共有 $n$ 次操作（$1 \;\leq n \leq 1000$）,请你对每个回答操作，输出结果。

inputFormat:
第一行两个整数 $n,k$ ，意义如题所述。

接下来的若干行，每行代表一次操作，具体如下：

- $1\ p\ x_1\ \ y_1,...,x_p\ y_p$ :表示一个插入操作，其中共有 $p$ 个字段，第 $i$ 字段的名字是 $x_i$ ，值为 $y_i$ .此处我们保证 $1 \leq x_i \leq k, 1\leq y_i  \leq 1000$，并且 $x_i,y_i$ 均为整数。

- $2\ x\ y_{min}\ y_{max}$：表示一次查询操作，表示查询所有满足 字段 $x$ 的值在 $[y_{min},y_{max}]$ 之间的记录有多少个。

outputFormat: 对于每个查询操作，输出一行一个整数，表示符合条件的记录个数。


title: 「PMOI-5」棋盘

description:
给定一个无限大的棋盘（可以看做平面直角坐标系）和黑白子各 $n$ 颗，要求将黑白子不重叠地摆在棋盘的整点上，使得**恰好**存在 $n$ 条直线使得：

- 其穿过且**仅**穿过黑白子**共** 4 颗。

- 其按顺序穿过黑，白，白，黑子。

给出任意一种方案即可。

inputFormat: 输入数据仅一行，为题目中所述的 $n$。

outputFormat:
如果无法构造出方案，则输出 `NO`。

否则输出 $2n+1$ 行：第一行输出 `YES`。第 $2\sim n+1$ 行每行两个整数，为白子坐标 $x_i,y_i$。第 $n+2\sim 2n+1$ 行每行两个整数，为黑子坐标 $x_j,y_j$。

你需要保证 $-5\times 10^5\le x_i,y_i,x_j,y_j\le 5\times 10^5$。

hint:
【样例解释】

样例 2 解释：（输出按顺序为点 $A\sim N$（点 $A\sim G$ 为白子，点 $H\sim N$ 为黑子），直线如图所示）。

![](https://cdn.luogu.com.cn/upload/image_hosting/zyo823p8.png)

【数据范围】

**本题采用捆绑测试。**

- Subtask 1（10 pts）：$n\equiv 0 \pmod{7}$；
- Subtask 2（20 pts）：$40\le n\le 400$；
- Subtask 3（30 pts）：$1\le n\le 9$；
- Subtask 4（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 10^3$。

[SPJ地址](https://www.luogu.com.cn/paste/eamtmrw5)

使用方法：编译为 `checker.exe` 后命令行同一目录下输入 ```checker.exe chessboard.in chessboard.out chessboard.ans```

需要搭配 `testlib.h` 一起使用，[testlib下载地址](https://github.com/MikeMirzayanov/testlib)。

如果发现 SPJ 出锅了请找出题人。


title: 「PMOI-5」一道防不住 AK 的水题

background: 本题加强版在[这](https://www.luogu.com.cn/problem/U203487)。

description:
有 $m$ 个盒子和 $n$ 个操作，盒子编号为 $0\dots m-1$。第 $i$ 个操作一共会进行 $r_i-l_i+1$ 轮，第 $j$ 轮会在编号为 $(k(j-1+l_i)+b_i)\bmod m$ 的盒子里放 $a_i$ 个球（$j$ 从 $1$ 开始枚举）。

在所有操作完成后，你需要选出 $p$ 个不同的且编号不相邻的盒子，定义一次选择的价值为 $p$ 个盒子里面球个数的乘积。求所有选择方案的价值和模 $10^9+7$。

inputFormat:
第一行四个整数 $n,k,m,p$，表示操作个数，两种关于操作参数和选出的盒子个数。
接下来 $n$ 行，第 $i$ 行四个非负整数 $l_i,r_i,b_i,a_i$ 表示一次操作的参数。

outputFormat: 一个整数表示价值和对 $10^9+7$ 取模的结果。

hint:
**本题采用捆绑测试。**

- Subtask 1（10pts）：$m\le 10^6$;
- Subtask 2（5pts）：$p=1$;
- Subtask 3（30pts）：$n\le 10$，$m\le 10^9$;
- Subtask 4（30pts）：保证 $k$ 和 $m$ 互质;
- Subtask 5（25pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 7000$，$1\le m\le 10^{18}$，$1\le p\le 4$，$0\le b_i< m$，$0<k<m$，$0\le l_i\le r_i< m$，$0\le a_i<10^9+7$。


title: 『MdOI R5』Jump

description:
数轴上有一个人，设他所在的位置为 $x$，初始时 $x=0$。第 $i$ 秒中他可以选择往左或往右跳 $2^{i-1}$ 单位长度，即将 $x$ 增大或减小 $2^{i-1}$。问他至少需要多少秒才能到达 $n$，即在某一秒结束的时刻使得 $x=n$。如果永远都不可能到达 $n$，那么输出 $-1$。

**本题每个测试点中有多组数据。**

inputFormat:
第一行，一个整数，表示数据组数 $T$。

接下来 $T$ 行，每行一个整数，表示一组测试数据中的 $n$。

outputFormat: 共 $T$ 行，每行一个数，依次表示每组数据的答案。

hint:
对于 $100\%$ 的数据，$1\le T\le 10^3$，$1\le n\le 10^9$。

$\operatorname{Subtask} 1(30\%)$：$n\le 100$。

$\operatorname{Subtask} 2(40\%)$：$n=2^k$，其中 $k$ 是一个非负整数。

$\operatorname{Subtask} 3(30\%)$：无特殊限制。

#### 样例说明 1

$n=1$ 时只需要在第一秒中往右跳即可。

$n=2$ 时可以证明永远都不可能到达 $n$。


title: 「EZEC-11」Circle

description:
有 $n$ 个人，编号为 $1$ 到 $n$，坐在环上玩约瑟夫。

他们从 $1$ 到 $m$ 循环报数，与正常约瑟夫不同的是，没有报到 $1$ 的人都会被淘汰，直至只有一个人活下来为止。

设活下来的人编号为 $x$，则记 $J_m(n)=x$。

给定 $m,l,r$，求 $\sum_{i=l}^{r}J_m(i)$，输出对 $998244353$ 取模。

inputFormat:
**本题有多组数据**。

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

一行三个整数，依次为 $m,l,r$。

outputFormat:
对于每组数据：

输出一行一个整数，表示答案对 $998244353$ 取模的结果。

hint:
**本题采用捆绑测试。**

- Subtask 1（4 pts）：$T=1$，$m \leq 10$，$r \leq 200$。
- Subtask 2（8 pts）：$T=1$，$m \leq 10^6$，$r\leq 10^7$。
- Subtask 3（8 pts）：$\sum (r-l+1) \leq 2 \times 10^6$。
- Subtask 4（10 pts）：$m=2$。
- Subtask 5（25 pts）：$T \leq 5$，$m \leq 10^6$。
- Subtask 6（45 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq T \leq 10^4$，$2 \leq m \leq 10^{12}$，$1 \leq l \leq r \leq 10^{18}$。


title: 「DTOI-4」排列

background:
**Update on 2023.2.1：新增一组针对 @[yuanjiabao](https://www.luogu.com.cn/user/455558) 的 Hack 数据，放置于 #21。**

**Update on 2023.2.2：新增一组针对 @[CourtesyWei](https://www.luogu.com.cn/user/664070) 和 @[bizhidaojiaosha](https://www.luogu.com.cn/user/613616) 的 Hack 数据，放置于 #22。**

------------

~~构造一个排列 $p$，使得~~$\small\color{white}{下标为奇数的项之和 \geq a 且下标为偶数的项之和 \geq b。}$

description: 小 L 给你一个**偶数** $n$ 和两个整数 $a, b$，请你构造一个长为 $n$ 的排列 $p$，使得其满足 $\displaystyle\sum_{i = 1}^{\frac{n}{2}} p_i \geq a$ 且 $\displaystyle\sum_{i = \frac{n}{2} + 1}^{n} p_i \geq b$。

inputFormat:
**本题有多组测试数据。**

第一行，一个整数 $T$，表示数据组数。

对于每组数据：

一行，三个整数 $n, a, b$。

outputFormat:
对于每组数据，如果无解，输出 $-1$；否则，输出一行，$n$ 个整数，表示你构造出的排列 $p$。

**如有多解，输出任意一组均可。**


title: [USACO21DEC]  Tickets P

description:
Bessie 正在参加远足旅行！她当前正在旅行的路线由编号为 $1\ldots N$（$1\le N\le 10^5$）的 $N$ 个检查点组成。

有 $K$（$1\le K\le 10^5$）张票可供购买。第 $i$ 张票可以在检查站 $c_i$（$1\le c_i\le N$）以 $p_i$（$1\le p_i\le 10^9$）的价格购得，并且可以用其进入所有检查站 $[a_i,b_i]$（$1\le a_i\le b_i\le N$）。在进入任何检查站之前，Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站，她就可以在未来的任何时候回到该检查站。

对于每一个 $i\in [1,N]$，如果 Bessie 最初只能进入检查点 $i$，输出使得可以进入检查点 $1$ 和 $N$ 所需的最低总价。如果无法这样做，输出 $-1$。

inputFormat:
输入的第一行包含 $N$ 和 $K$。

以下 $K$ 行，对于每一个 $1\le i\le K$，第 $i$ 行包含四个整数 $c_i$，$p_i$，$a_i$ 和 $b_i$。

outputFormat: 输出 $N$ 行，每行输出一个检查点的答案。

hint:
【样例解释】

如果 Bessie 从检查点 $i=4$ 开始，那么一种购得进入检查点 $1$ 和 $N$ 的方法如下：

在检查点 $4$ 购买第一张票，使 Bessie 可以进入检查点 $2$ 和 $3$。

在检查点 $2$ 购买第三张票，使 Bessie 可以进入检查点 $7$。

回到检查点 $4$ 购买第二张票，使 Bessie 可以进入检查点 $5$ 和 $6$。

在检查点 $6$ 购买第四张票，使 Bessie 可以进入检查点 $1$。

【数据范围】

- 测试点 1-7 满足 $N,K\le 1000$。
- 测试点 8-19 没有额外限制。


title: [USACO21DEC] Paired Up P

description:
数轴上总计有 $N$（$1\le N\le 5000$）头奶牛，每一头奶牛都是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一。第 $i$ 头奶牛的品种为 $b_i\in \{H,G\}$，第 $i$ 头奶牛的位置为 $x_i$（$0 \leq x_i \leq 10^9$），而第 $i$ 头奶牛的重量为 $y_i$（$1 \leq y_i \leq 10^5$）。

根据 Farmer John 的信号，某些奶牛会组成对，使得

- 每一对包含位置相差不超过 $K$ 的一头荷斯坦牛 $h$ 和一头更赛牛 $g$（$1\le K\le 10^9$）；也就是说，$|x_h-x_g|\le K$。

- 每一头奶牛要么包含在恰好一对中，要么不属于任何一对。
- 配对是**极大的**；也就是说，没有两头未配对的奶牛可以组成对。

你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，

- 如果 $T=1$，计算未配对的奶牛的最小重量和。

- 如果 $T=2$，计算未配对的奶牛的最大重量和。

inputFormat:
输入的第一行包含 $T$，$N$ 和 $K$。

以下 $N$ 行，第 $i$ 行包含 $b_i,x_i,y_i$。输入保证 $0\le x_1<x_2<\cdots<x_{N}\le 10^9$。

outputFormat: 输出未配对的奶牛的最小或最大重量和。

hint:
【样例解释1】

奶牛 $2$ 和 $3$ 可以配对，因为她们的距离为 $1$，不超过 $K = 4$。这个配对方案是极大的，因为奶牛 $1$，唯一余下的更赛牛，和奶牛 $4$ 的距离为 $5$，和奶牛 $5$ 的距离为 $7$，均大于 $K = 4$。未配对的奶牛的重量和为 $1 + 6 + 9 = 16$。

【样例解释2】

奶牛 $1$ 和 $2$ 可以配对，因为她们的距离为 $2 \leq K = 4$，同时奶牛 $3$ 和 $5$ 可以配对，因为她们的距离为 $4 \leq K = 4$。这个配对方案是极大的，因为只剩下了奶牛 $4$。未配对的奶牛的重量和即为唯一未配对的奶牛的重量，即为 $6$。

【样例解释3】

这个例子的答案为 $18+465+870+540=1893$。

【数据范围】

- 测试点 4-7 满足 $T=1$；
- 测试点 8-14 满足 $T=2$ 且 $N\le 300$；
- 测试点 15-22 满足 $T=2$。

**注意：本题的内存限制为 $\text{512MB}$，是通常限制的两倍。**


title: [USACO21DEC] HILO P

description:
Bessie 有一个数 $x+0.5$，其中 $x$ 是某个 $0$ 到 $N$ 之间的整数（$1\le N\le 5000$）。

Elsie 正试着猜这个数。她可以以如下形式对于某个 $1$ 到 $N$ 之间的整数提问：「$i$ 是大了还是小了？」如果 $i$ 大于 $x+0.5$，Bessie 会回答 "HI!"，如果 $i$ 小于 $x+0.5$ 则回答 "LO!"。

Elsie 想到了以下猜测 Bessie 的数的策略。在进行任何猜测之前，她创建了一个包含 $N$ 个整数的序列，其中从 $1$ 到 $N$ 的每个数均恰好出现一次（换句话说，这个序列是长为 $N$ 的一个排列）。然后她遍历这一列表，按列表中的数的顺序依次猜数。然而，Elsie 会跳过所有不必要的猜测。也就是说，如果 Elsie 将要猜某个数 $i$，而 Elsie 之前已经猜过了某个 $j < i$ 并且 Bessie 回答 "HI!"，Elsie 不会再猜 $i$，而是继续猜序列中的下一个数。类似地，如果她将要猜某个数 $i$，而她之前已经猜过了某个 $j > i$ 并且 Bessie 回答 "LO!"，Elsie 不会再猜 $i$，而是继续猜序列中的下一个数。可以证明，使用这一策略，对于 Elsie 创建的任意序列，她都可以唯一确定 $x$。

如果我们将所有 Bessie 回答的 "HI" 或 "LO" 拼接成一个字符串 $S$，那么 Bessie 说 "HILO" 的次数为 $S$ 等于 "HILO" 的长为 $4$ 的子串数量。

Bessie 知道 Elsie 将要使用这一策略，并且已经选定了值 $x$，但她不知道 Elsie 会使用什么排列。你的目标是对于所有 Elsie 可能选用的排列，计算 Bessie 说 "HILO" 的次数之和，对 $10^9+7$ 取模。

inputFormat: 输入一行，包含 $N$ 和 $x$。

outputFormat: 输出 HILO 的总数，对 $10^9+7$ 取模。

hint:
【样例解释1】

在这个测试用例中，Bessie 的数是 $2.5$。

例如，如果 Elsie 的排列是 $(4,1,3,2)$，那么 Bessie 会说 ""HILOHILO"，总计两次 "HILO"。又例如，如果 Elsie 的排列是 $(3,1,2,4)$，那么 Bessie 会说 "HILOLO"，总计一次 "HILO"。

【样例解释2】

确保输出总和对 $10^9+7$ 取模的结果。

【数据范围】

- 测试点 3-10 满足 $N\le 50$；
- 测试点 11-18 满足 $N\le 500$；
- 测试点 19-26 没有额外限制。


title: [USACO21DEC] Paired Up G

description:
数轴上总计有 $N$（$1\le N\le 10^5$）头奶牛。第 $i$ 头奶牛的位置为 $x_i$（$0 \leq x_i \leq 10^9$），而第 $i$ 头奶牛的重量为 $y_i$（$1 \leq y_i \leq 10^4$）。

根据 Farmer John 的信号，某些奶牛会组成对，使得

- 每一对包含位置相差不超过 $K$ 的两头不同的奶牛 $a$ 和 $b$（$1\le K\le 10^9$）；也就是说，$|x_a-x_b|\le K$。

- 每一头奶牛要么包含在恰好一对中，要么不属于任何一对。

- **配对是极大的**；也就是说，没有两头未配对的奶牛可以组成对。

你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，

- 如果 $T=1$，计算未配对的奶牛的最小重量和。

- 如果 $T=2$，计算未配对的奶牛的最大重量和。

inputFormat:
输入的第一行包含 $T$，$N$ 和 $K$。

以下 $N$ 行，第 $i$ 行包含 $x_i$ 和 $y_i$。输入保证 $0\le x_1< x_2<\cdots<x_{N}\le 10^9$。

outputFormat: 输出未配对的奶牛的最小或最大重量和。

hint:
【样例解释1】

在这个例子中，奶牛 $2$ 和 $4$ 可以配对，因为她们的距离为 $2$，不超过 $K = 2$。这个配对方案是极大的，因为奶牛 $1$ 和 $3$ 的距离为 $3$，奶牛 $3$ 和 $5$ 的距离为 $3$，奶牛 $1$ 和奶牛 $5$ 的距离为 $6$，均大于 $K = 2$。未配对的奶牛的重量和为 $2 + 2 + 2 = 6$。

【样例解释2】

在这里，奶牛 $1$ 和 $2$ 可以配对，因为她们的距离为 $2 \leq K = 2$，同时奶牛 $4$ 和 $5$ 可以配对，因为她们的距离为 $2 \leq K = 2$。这个配对方案是极大的，因为只剩下了奶牛 $3$。未配对的奶牛的重量和即为 $2$。

【样例解释3】

这个例子的答案为 $693+992+785=2470$。

【数据范围】

- 测试点 4-8 满足 $T=1$。
- 测试点 9-14 满足 $T=2$ 且 $N\le 5000$。
- 测试点 15-20 满足 $T=2$。


title: [USACO21DEC] HILO G

description:
Bessie 有一个数 $x+0.5$，其中 $x$ 是某个 $0$ 到 $N$ 之间的整数（$1\le N\le 2 \cdot 10^5$）。

Elsie 正试着猜这个数。她可以以如下形式对于某个 $1$ 到 $N$ 之间的整数提问：「$i$ 是大了还是小了？」如果 $i$ 大于 $x+0.5$，Bessie 会回答 "HI"，如果 $i$ 小于 $x+0.5$ 则回答 "LO"。

Elsie 想到了以下猜测 Bessie 的数的策略。在进行任何猜测之前，她创建了一个包含 $N$ 个整数的序列，其中从 $1$ 到 $N$ 的每个数均恰好出现一次（换句话说，这个序列是长为 $N$ 的一个排列）。然后她遍历这一列表，按列表中的数的顺序依次猜数。

然而，Elsie 会跳过所有不必要的猜测。也就是说，如果 Elsie 将要猜某个数 $i$，而 Elsie 之前已经猜过了某个 $j < i$ 并且 Bessie 回答 "HI"，Elsie 不会再猜 $i$，而是继续猜序列中的下一个数。类似地，如果她将要猜某个数 $i$，而她之前已经猜过了某个 $j > i$ 并且 Bessie 回答 "LO"，Elsie 不会再猜 $i$，而是继续猜序列中的下一个数。可以证明，使用这一策略，对于 Elsie 创建的任意序列，她都可以唯一确定 $x$。

如果我们将所有 Bessie 回答的 "HI" 或 "LO" 拼接成一个字符串 $S$，那么 Bessie 说 "HILO" 的次数为 $S$ 等于 "HILO" 的长为 $4$ 的子串数量。

Bessie 知道 Elsie 将要使用这一策略；此外，她还知道 Elsie 将要使用的排列。然而， Bessie 尚未决定选用哪个值 $x$。

帮助 Bessie 对于每个值 $x$ 求出她会说 "HILO" 的次数。

inputFormat:
输入的第一行包含 $N$。

第二行包含 Elsie 的长为 $N$ 的排列。

outputFormat: 对于从 $0$ 到 $N$ 的每一个 $x$，输出一行，包含 Bessie 会说 HILO 的次数。

hint:
【样例解释】

对于 $x=0$，Bessie 会说 "HIHI"，总计零次 "HILO"。

对于 $x=2$，Bessie 会说 "HILOLOHIHI"，总计一次 "HILO"。

对于 $x=3$，Bessie 会说 "HILOLOHILO"，总计两次 "HILO"。

【数据范围】

- 测试点 1-4 满足 $N \leq 5000$。
- 测试点 5-8 为均匀随机的排列。
- 测试点 9-20 没有额外限制。


title: [USACO21DEC] Bracelet Crossings G

description:
奶牛 Bessie 喜欢手工艺。在她的空闲时间，她制作了 $N$（$1\le N\le 50$）个手链，编号为 $1 \ldots N$。第 $i$ 个手链涂有颜色 $i$，是 $N$ 种不同的颜色之一。制作完手链后，Bessie 将它们放在桌子上进行展示（我们可以将其视为二维平面）。她精心布置这些手链，以满足以下三个条件：

- 每个手链是一个简单闭合折线——一组顶点（点）依次用线段连接，并且第一个点和最后一个点相同（欢迎查阅维基百科页面了解更多详情：[Polygonal_chain](https://en.wikipedia.org/wiki/Polygonal_chain)，或百度百科：[折线](https://baike.baidu.com/item/%E6%8A%98%E7%BA%BF/486302)），

- 没有手链与自身相交（这对应「简单」折线）；

- 以及没有两条手链相交。

不幸的是，就在 Bessie 如此小心翼翼地布置好手链之后，Farmer John 开着拖拉机经过，桌子晃动起来，导致手链四处移动甚至可能断成了多个（不一定是闭合的或简单的）折线！在那之后，Bessie 还是想检查以上三个条件是否仍然成立。然而，天色已暗，她现在无法看清手链。

幸好 Bessie 有一个手电筒。她选择了 $M$（$1\le M\le 50$）条垂直线 $x=1, x=2, \ldots, x=M$，并且对于每条线，她用手电筒的光沿着那条线从 $y=-\infty$ 扫至 $y=\infty$，按照出现的顺序记录她看到的所有手链的颜色。幸运的是，没有光束穿过任何折线的顶点或同时穿过两条线段。此外，对于每一束光，所有出现的颜色都恰好出现了两次。

你能帮助 Bessie 使用此信息来确定手链是否仍然满足上述所有三个条件吗？

inputFormat:
每个测试用例的输入包含 $T$ 个子测试用例（$1 \leq T \leq 50$），所有子测试用例必须全部回答正确才能通过整个测试用例。相邻的子测试用例之间用空行分隔。

输入的第一行包含 $T$。之后是 $T$ 个子测试用例。

每个子测试用例的第一行包含两个整数 $N$ 和 $M$。此后每个子测试用例还包含 $M$ 行。对 $1$ 到 $M$ 的每一个 $i$，第 $i$ 行包含一个整数 $k_i$（$0\le k_i\le 2N$，$k_i$ 为偶数），然后是 $k_i$ 个整数 $c_{i1}, c_{i2},\ldots, c_{ik_i}$（$c_{ij}\in [1,N]$，每个 $c_{ij}$ 出现零次或两次)。这表示当 Bessie 将手电筒从 $(i,-\infty)$ 扫至 $(i,\infty)$ 时，她按顺序 $c_{i1}, c_{i2},\ldots, c_{ik_i}$ 看到了这些颜色。

outputFormat: 对每个子测试用例，如果有可能使得以上三个条件均满足则输出 YES。否则，输出 NO。

hint:
【样例解释】

对于第一个子测试用例，一组可行的手链位置为：

![](https://cdn.luogu.com.cn/upload/image_hosting/q3mohld2.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

对于第四个子测试用例，一组可行的手链位置为：

![](https://cdn.luogu.com.cn/upload/image_hosting/8m2hcgbb.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

【数据范围】

- 测试点 2 满足 $N = 1$。
- 测试点 3-5 满足 $N=2$。
- 测试点 6-8 满足 $M=1$。
- 测试点 9-14 满足 $M=2$。
- 测试点 15-20 没有额外限制。


title: [USACO21DEC] Closest Cow Wins S

description:
Farmer John 沿着一条高速公路拥有一个很长的农场，可以被看作类似于一维数轴。沿着农场有 $K$ 块草地（$1 \leq K \leq 2\cdot 10^5$）；第 $i$ 块草地位于位置 $p_i$ 并具有美味值 $t_i$（$0\le t_i\le 10^9$）。Farmer John 的死对头 Farmer Nhoj 已经将他的 $M$ 头奶牛（$1 \leq M \leq 2\cdot 10^5$）放在了位置 $f_1 \ldots f_M$ 。所有这些 $K+M$ 个位置均是 $[0,10^9]$ 范围内的不同整数。

Farmer John 需要选择 $N$（$1\le N\le 2\cdot 10^5$）个位置（不一定是整数）放置他的奶牛。这些位置必须与 Farmer Nhoj 的奶牛已经占用的位置不同，但是 Farmer John 可以将他的奶牛放在与草地相同的位置。

拥有最靠近某个草地的奶牛的农夫拥有这一草地。如果来自两方农夫的两头奶牛距这一草地相等，则 Farmer Nhoj 拥有该草地。

给定 Farmer Nhoj 的奶牛的位置以及草地的位置和美味值，求 Farmer John 的奶牛以最优方式放置时可以达到的最大总美味值。

inputFormat:
输入的第一行包含 $K$、$M$ 和 $N$。

以下 $K$ 行每行包含两个空格分隔的整数 $p_i$ 和 $t_i$。

以下 $M$ 行每行包含一个整数 $f_i$。

outputFormat: 输出一个整数，表示最大总美味值。注意这个问题的答案可能无法用 32 位整数型存储，你可能需要使用 64 位整数型（例如，C 或 C++ 中的 "long long"）。

hint:
【样例解释】

如果 Farmer John 将奶牛放在位置 $11.5$ 和 $8$ 则他可以得到总美味值 $10+12+14=36$。


title: [USACO21DEC] Connecting Two Barns S

description:
Farmer John 的农场由 $N$ 块田地（$1 \leq N \leq 10^5$）组成，编号为 $1 \ldots N$。在这些田地之间有 $M$ 条双向道路（$0 \leq M \leq 10^5$），每条道路连接两块田地。

农场有两个牛棚，一个在田地 1 中，另一个在田地 $N$ 中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。 他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素，在田地 $i$ 和 $j$ 之间建造新道路的花费是 $(i-j)^2$。

请帮助 Farmer John 求出使得牛棚 $1$ 和 $N$ 可以相互到达所需要的最小花费。

inputFormat:
每个测试用例的输入包含 $T$ 个子测试用例（$1\le T\le 20$），所有子测试用例必须全部回答正确才能通过整个测试用例。

输入的第一行包含 $T$，之后是 $T$ 个子测试用例。

每个子测试用例的第一行包含两个整数 $N$ 和 $M$。以下 $M$ 行，每行包含两个整数 $i$ 和 $j$，表示一条连接两个不同田地 $i$ 和 $j$ 的道路。输入保证任何两个田地之间至多只有一条道路，并且所有子测试用例的 $N+M$ 之和不超过 $5 \cdot 10^5$。

outputFormat: 输出 $T$ 行。第 $i$ 行包含一个整数，为第 $i$ 个子测试用例的最小花费。

hint:
【样例解释】

- 第一个子测试用例中，最优的方式是用一条道路连接田地 2 和 3，用一条道路连接田地 3 和 4。
- 第二个子测试用例中，最优的方式是用一条道路连接田地 3 和 4。不需要第二条道路。

【数据范围】

- 测试点 2 满足 $N \le 20$。
- 测试点 3-5 满足 $N \le 10^3$。
- 测试点 6-10 没有额外限制。


title: [USACO21DEC]  Convoluted Intervals S

description:
奶牛们正在努力尝试发明有趣的新游戏来玩。他们目前的工作之一与一组 $N$ 个区间（$1\le N\le 2\cdot 10^5$）有关，其中第 $i$ 个区间从数轴上的 $a_i$ 位置开始，并在位置 $b_i \geq a_i$ 结束。$a_i$ 和 $b_i$ 均为 $0 \ldots M$ 范围内的整数，其中 $1 \leq M \leq 5000$。

这个游戏的玩法是，Bessie 选择某个区间（假设是第 $i$ 个区间），而她的表妹 Elsie 选择某个区间（假设是第 $j$ 个区间，可能与 Bessie 所选的的区间相同）。给定某个值 $k$，如果 $a_i + a_j \leq k \leq b_i + b_j$，则她们获胜。

对范围 $0 \ldots 2M$ 内的每个值 $k$，请计算使得 Bessie 和 Elsie 可以赢得游戏的有序对 $(i,j)$ 的数量。

inputFormat: 输入的第一行包含 $N$ 和 $M$。以下 $N$ 行每行以整数 $a_i$ 和 $b_i$ 的形式描述一个区间。

outputFormat: 输出 $2M+1$ 行，依次包含范围 $0 \ldots 2M$ 中的每一个 $k$ 的答案。

hint:
【样例解释】

在这个例子中，对于 $k=3$，有三个有序对可以使得 Bessie 和 Elsie 获胜：$(1, 1)$，$(1, 2)$，和 $(2, 1)$。

【数据范围】

- 测试点 1-2 满足 $N\le 100, M\le 100$。
- 测试点 3-5 满足 $N\le 5000$。
- 测试点 6-20 没有额外限制。


title: [USACO21DEC] Lonely Photo B

description:
Farmer John 最近购入了 $N$ 头新的奶牛（$3 \le N \le 5 \times 10^5$），每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。 在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。

给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。如果两张照片以不同的奶牛开始或结束，则认为它们是不同的。

inputFormat:
输入的第一行包含 $N$。

输入的第二行包含一个长为 $N$ 的字符串。如果队伍中的第 $i$ 头奶牛是更赛牛，则字符串的第 $i$ 个字符为 G。否则，第 $i$ 头奶牛是荷斯坦牛，该字符为 H。

outputFormat: 输出 Farmer John 会扔掉的孤独的照片数量。

hint:
【样例解释】

这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer John 扔掉。所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。

【数据范围】

- 测试点 2-4 满足 $N \le 50$。
- 测试点 5-10 满足 $N \le 5000$。
- 测试点 11 没有额外限制。

注意这个测试点的答案可能无法用标准的 32 位整数型存储，你可能需要使用更大的整数类型（例如，C++ 中 64 位的 "long long int" 类型）。


title: [USACO21DEC] Air Cownditioning B

description:
Farmer John 的 $N$ 头奶牛对他们牛棚的室温非常挑剔。有些奶牛喜欢温度低一些，而有些奶牛则喜欢温度高一些。

Farmer John 的牛棚包含一排 $N$ 个牛栏，编号为 $1 \ldots N$，每个牛栏里有一头牛。 第 $i$ 头奶牛希望她的牛栏中的温度是 $p_i$，而现在她的牛栏中的温度是 $t_i$。为了确保每头奶牛都感到舒适，Farmer John 安装了一个新的空调系统。该系统进行控制的方式非常有趣，他可以向系统发送命令，告诉它将一组连续的牛栏内的温度升高或降低 1 个单位——例如「将牛栏 $5 \ldots 8$ 的温度升高 1 个单位」。一组连续的牛栏最短可以仅包含一个牛栏。

请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量，使得每头奶牛的牛栏都处于其中的奶牛的理想温度。

inputFormat: 输入的第一行包含 $N$。下一行包含 $N$ 个非负整数 $p_1 \ldots p_N$，用空格分隔。最后一行包含 $N$ 个非负整数 $t_1 \ldots t_N$。

outputFormat: 输出一个整数，为 Farmer John 需要使用的最小指令数量。

hint:
【样例解释】

一组最优的 Farmer John 可以使用的指令如下：

```
初始温度     ：1 2 2 2 1
升高牛棚 2..5：1 3 3 3 2
升高牛棚 2..5：1 4 4 4 3
升高牛棚 2..5：1 5 5 5 4
降低牛棚 3..4：1 5 4 4 4
降低牛棚 3..4：1 5 3 3 4
```

【数据范围】

- 测试点 2-5 满足 $N \leq 100$。
- 测试点 6-8 满足 $N \leq 1000$。
- 测试点 9-10 满足 $N \leq 100,000$
- 测试点 1-6 和 9 中，温度值不超过 $100$
- 测试点 7-8 和 10 中，温度值不超过 $10,000$。


title: [USACO21DEC] Walking Home B

description:
奶牛 Bessie 正准备从她最喜爱的草地回到她的牛棚。

农场位于一个 $N \times N$ 的方阵上（$2 \leq N \leq 50$），其中她的草地在左上角，牛棚在右下角。Bessie 想要尽快回家，所以她只会向下或向右走。有些地方有草堆（haybale），Bessie 无法穿过；她必须绕过它们。

Bessie 今天感到有些疲倦，所以她希望改变她的行走方向至多 $K$ 次（$1 \leq K \leq 3$）。

Bessie 有多少条不同的从她最爱的草地回到牛棚的路线？如果一条路线中 Bessie 经过了某个方格而另一条路线中没有，则认为这两条路线不同。

inputFormat:
每个测试用例的输入包含 $T$ 个子测试用例，每个子测试用例描述了一个不同的农场，并且必须全部回答正确才能通过整个测试用例。输入的第一行包含 $T$（$1 \leq T \leq 50$）。每一个子测试用例如下。

每个子测试用例的第一行包含 $N$ 和 $K$。

以下 $N$ 行每行包含一个长为 $N$ 的字符串。每个字符为 $\texttt{.}$，如果这一格是空的，或 $\texttt{H}$，如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。

outputFormat: 输出 $T$ 行，第 $i$ 行包含在第 $i$ 个子测试用例中 Bessie 可以选择的不同的路线数量。

hint:
【样例解释】

我们将使用一个由字符 D 和 R 组成的字符串来表示 Bessie 的路线，其中 D 和 R 分别表示 Bessie 向下（down）或向右（right）移动。

第一个子测试用例中，Bessie 的两条可能的路线为 DDRR 和 RRDD。

第二个子测试用例中，Bessie 的四条可能的路线为 DDRR，DRRD，RDDR 和 RRDD。

第三个子测试用例中，Bessie 的六条可能的路线为 DDRR，DRDR，DRRD，RDDR，RDRD 和 RRDD。

第四个子测试用例中，Bessie 的两条可能的路线为 DDRR 和 RRDD。

第五和第六个子测试用例中，Bessie 不可能回到牛棚。

第七个子测试用例中，Bessie 的六条可能的路线为 DDRDRR，DDRRDR，DDRRRD，RRDDDR，RRDDRD 和 RRDRDD。

【数据范围】

- 测试点 2 满足 $K = 1$。
- 测试点 3-5 满足 $K = 2$。
- 测试点 6-10 满足 $K = 3$。


title: [ONTAK2015] OR-XOR

description: 给定一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$，请将它划分为 $m$ 段连续的区间，设第 $i$ 段的费用 $c_i$ 为该段内所有数字的异或和，则总费用为 $c_1 \operatorname{or} c_2 \operatorname{or} \cdots \operatorname{or} c_m$。请求出总费用的最小值。

inputFormat:
第一行，两个整数 $n, m$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$。

outputFormat: 一行，一个整数，表示所求的值。

hint: 对于 $100\%$ 的数据，$1 \leq m \leq n \leq 5 \times 10^5$，$0 \leq a_i \leq 10^{18}$。


title: [ONTAK2015] Badania naukowe

description: 给定三个数字串 $A, B, C$，请找到一个 $A, B$ 的最长公共子序列，满足 $C$ 是该子序列的子串。

inputFormat:
第一行，一个整数 $n$，表示 $A$ 的长度；

第二行，$n$ 个整数，表示数字串 $A$；

第三行，一个整数 $m$，表示 $B$ 的长度；

第四行，$m$ 个整数，表示数字串 $B$；

第五行，一个整数 $k$，表示 $C$ 的长度；

第六行，$k$ 个整数，表示数字串 $C$。

outputFormat: 一行，一个整数，如果无解，输出 $-1$；否则，输出满足条件的最长公共子序列的长度。

hint: 对于 $100\%$ 的数据，$1 \leq n,m \leq 3 \times 10^3$，$0 \leq k \leq 3 \times 10^3$。


title: [ONTAK2015] Bajtman i Okrągły Robin

background: **警告：滥用本题评测将被封号！**

description: 有 $n$ 个强盗，其中第 $i$ 个强盗会在 $[a_i, a_i + 1], [a_i + 1, a_i + 2], \cdots, [b_i - 1, b_i]$ 这么多段长度为 $1$ 的时间中选出一个时间进行抢劫，并计划抢走 $c_i$ 元。作为保安，你在每一段长度为 $1$ 的时间内最多只能制止一个强盗，那么你最多可以挽回多少损失呢？

inputFormat:
第一行，一个整数 $n$；

接下来 $n$ 行，每行三个整数 $a_i, b_i, c_i$。

outputFormat: 一行，一个整数，表示所求的值。

hint: 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^3$，$1 \leq a_i < b_i \leq 5 \times 10^3$，$1 \leq c_i \leq 10^4$。


title: [ONTAK2015] Cięcie

description:
给定一个长度为 $k$ 的数字串 $N$ 以及三个**质数** $p, q, r$，请你将 $N$ 划分为三段非空字符串，使得第一段能被 $p$ 整除，第二段能被 $q$ 整除，第三段能被 $r$ 整除，且每一段都不含前导 $0$。

注：**单独的 $0$ 是允许的**。

inputFormat:
第一行，四个整数 $k, p, q, r$；

第二行，长度为 $k$ 的数字串 $N$。

outputFormat: 输出一个整数，即合法的划分方案的总数。


title: [ONTAK2015] Tasowanie

description: 给定两个数字串 $A$ 和 $B$，通过将 $A$ 和 $B$ 进行二路归并得到一个新的数字串 $T$，请找到字典序最小的 $T$。

inputFormat:
第一行，一个整数 $n$，表示 $A$ 的长度；

第二行，$n$ 个整数，表示 $A$；

第三行，一个整数 $m$，表示 $B$ 的长度；

第四行，$m$ 个整数，表示 $B$；

outputFormat: 一行，$n + m$ 个正整数，表示字典序最小的 $T$。

hint:
对于 $100\%$ 的数据，$1 \leq n, m \leq 2 \times 10^5$，组成 $A, B$ 的每个数字为不超过 $10^3$ 的正整数。

- 2023.9.10 添加两组 hack 数据。


title: [ONTAK2015] Stumilowy sad

background: Subtask 0 为原数据，Subtask 1 为 hack 数据。

description:
在一条笔直的道路上从左到右一共有 $n$ 片区域，每一片区域一开始都种着一棵树，其中第 $i$ 片区域种着高度为 $h_i$ 的树。接下来你需要处理 $q$ 个操作：

- `1 l r c`：将第 $l$ 片区域到第 $r$ 片区域内的所有树的高度拔高 $c$ 个单位。
- `2 l r h`：将一把刀固定在高度为 $h$ 的空中，对第 $l$ 片区域到第 $r$ 片区域内的所有树进行砍伐。
- `3 l r h`：往第 $l$ 片区域到第 $r$ 片区域内的每个区域种上一棵高度为 $h$ 的树。
- `4 l r`：查询第 $l$ 片区域到第 $r$ 片区域内最高的树的高度。

注：本题中的高度为相对于某个水平面的高度，也就是说**可能会有负数的出现**。

inputFormat:
第一行，两个整数 $n, q$；

第二行，$n$ 个整数 $h_1, h_2, \cdots, h_n$；

接下来 $q$ 行，每行三或四个整数 $op, l, r, c$、$op, l, r, h$ 或 $op, l, r$。

outputFormat: 若干行，每行一个整数，表示对应查询的结果。

hint: 对于 $100\%$ 的数据，$1 \leq n, q \leq 5 \times 10^5$，$1 \leq h_i \leq 10^9$，$1 \leq l \leq r \leq n$，$0 \leq |c| \leq 500$，$1 \leq h \leq 10^9$。


title: [ONTAK2015] Związek Harcerstwa Bajtockiego

description: 给定一棵 $n$ 个点的无根树，相邻的点之间的距离为 $1$，一开始你位于 $m$ 点。之后你将依次收到 $k$ 个指令，每个指令包含两个整数 $d$ 和 $t$，你需要沿着最短路在 $t$ 步之内（包含 $t$ 步）走到 $d$ 点，如果不能走到，则停在最后到达的那个点。请在每个指令之后输出你所在的位置。

inputFormat:
第一行，三个整数 $n, m, k$；

接下来 $n - 1$ 行，每行两个整数 $x, y$，表示一条树边；

接下来 $k$ 行，每行两个整数 $d, t$，表示一条指令。

outputFormat: 一行，$k$ 个整数，表示执行对应指令后你所在的位置。

hint: 对于 $100\%$ 的数据，$1 \leq m \leq n \leq 10^6$，$1 \leq k \leq 10^6$，$1 \leq x, y, d \leq n$，$0 \leq t \leq 10^9$。


title: [ONTAK2015] Bajtocja

description: 给定 $d$ 张无向图，每张图都有 $n$ 个点。一开始，在任何一张图中都没有任何边。接下来有 $m$ 次操作，每次操作会给出 $a, b, k$，意为在第 $k$ 张图中的点 $a$ 和点 $b$ 之间添加一条无向边。你需要在每次操作之后输出有序数对 $(a, b)$ 的个数，使得 $1 \leq a, b \leq n$，且 $a$ 点和 $b$ 点在 $d$ 张图中都连通。

inputFormat:
第一行，三个整数 $d, n, m$；

接下来 $m$ 行，每行三个整数 $a, b, k$。

outputFormat: $m$ 行，每行一个整数，表示所求的值。

hint: 对于 $100\%$ 的数据，$1 \leq d \leq 200$，$1 \leq n \leq5 \times 10^3$，$1\leq m \leq 10^6$，$1 \leq a, b \leq n$，$1 \leq k \leq d$。


title: 「PMOI-5」奇怪的方程

description:
给出一个 $n$，现在有 $n\times n$ 个未知数 $a_{1},a_{2},\cdots,a_{n\times n}$。

给出 $2\times n$ 个方程，方程共有两种，每种分别有 $n$ 个。

第一种方程的 $i$ 个方程为 $\sum_{j=1}^na_{(i-1)\times n+j}=A_i$。
第二种方程的 $i$ 个方程为 $\sum_{j=1}^na_{i+(j-1)\times n}=B_i$。

可这太简单了，给出 $m$ 个限制，你需要保证 $a_{p_i}=q_i$。

请求出任意一组合法的解。无解输出 `No Solution`，否则先输出 `OK`，接着给出解，其中 $\forall i\in[1,n^2]$，$a_i \in[-2^{63},2^{63})$ 且是个整数。

inputFormat:
**本题多组数据。**

第一行一个整数 $T$，表示数据组数。
对于每组数据：
第一行两个整数 $n$ 和 $m$。
第二行 $n$ 个整数，第 $i$ 个整数表示 $A_i$。
第三行 $n$ 个整数，第 $i$ 个整数表示 $B_i$。
接下来 $m$ 行，每行两个整数，表示 $p_i,q_i$。

outputFormat:
对于每组数据：
第一行一个字符串，表示是否有解。
如果有解，接下来一行 $n\times n$ 个整数，第 $i$ 个整数表示 $a_i$。

hint:
**本题采用捆绑测试。**

- Subtask1（1pts）：$n=1$；
- Subtask2（4pts）：$n\le3$；
- Subtask3（10pts）：$n\le 10$；
- Subtask4（15pts）：$n\le 100$；
- Subtask5（20pts）：$m\le n-1$；
- Subtask6（10pts）：$m=0$；
- Subtask7（20pts）：$T\le 10$，$n\le 500$；
- Subtask8（20pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n \le 2000$，$1\le \sum n^2\le 4\times 10^6$，$-5\times 10^{12}\le A_i,B_i\le 5\times 10^{12}$，$0\le m\le n^2$，$1\le p_i\le n^2$，$-10^9\le q_i\le 10^9$。保证 $p_i$ 互不相同。


title: [COCI2016-2017#5] Strelice

description:
Hansel 和 Gretel 正在玩「箭头游戏」。

该游戏在一个 $R$ 行 $S$ 列的棋盘上进行。其中每一个棋格内有一个箭头（$\leftarrow$、$\rightarrow$、$\uparrow$、$\downarrow$ 之一）。

游戏开始后，Hansel 可以选择任意 $K$ 个**不位于最后一列的**棋格进行填涂。接着，Gretel 可以选择**第一列的**任意一个棋格，作为机器人的初始棋格。机器人在放置到初始棋格后将按照箭头的指示自动行走。机器人一旦走到了最后一列，它将立即停止行走。

判定输赢的方式如下：

- 如果机器人在有限的时间内停在了最后一列，那么：当且仅当机器人恰好经过一个有色棋格时，判定 Hansel 获胜，否则 Gretel 获胜。
- 如果机器人无法停止行走（即处于无限循环的状态），那么判定 Hansel 获胜。

规定机器人经过的棋格包括初始棋格、终止棋格以及路径上的其它所有棋格。同时，数据保证箭头不会指向棋盘外部。

你的任务是判断 Hansel 是否有必胜的方案（即对于 Gretel 所选择的任意一个合法的初始棋格，Hansel 的填涂方案都可以使自己获胜）。如果有必胜的方案，输出该方案；否则输出 $-1$。

inputFormat:
第一行，三个整数 $R,S,K$。

接下来的 $R$ 行，每行 $S$ 个字符 $\texttt L$、$\texttt U$、$\texttt R$ 或 $\texttt D$，分别表示对应棋格内的箭头为 $\leftarrow$、$\rightarrow$、$\uparrow$ 和 $\downarrow$。

outputFormat:
如果没有必胜的方案，输出 $-1$。

否则输出 $K$ 行，每行两个整数 $A,B$，表示选择的 $K$ 个将要涂色的棋格。棋格必须互不相同。如果存在多种方案，请输出任意一种。

Special Judge 对输出格式要求较严，因此**请勿在每行行尾添加多余空格。**

hint:
**【样例 1 解释】**

填涂 $(4,2)$ 后，无论初始棋格位于第一列的哪里，机器人都会经过 $(4,2)$。

**【样例 2 解释】**

由于需要填涂 $2$ 个棋格，因此至少有一行没有有色棋格。只要 Gretel 选择没有有色棋格的那一行的第一列放置机器人，Gretel 就会获胜。

**【样例 3 图解】**

![](https://cdn.luogu.com.cn/upload/image_hosting/oy6p59p5.png?x-oss-process=image/resize,m_lfit,h_200)

**【数据规模与约定】**

对于 $100\%$ 的数据，$1 \le R \times S \le 10^6$，$1 \le K \le 50$，$1 \le A \le R$，$1 \le B \lt S$。

**【提示与说明】**

欢迎大家通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/k9jt7zoy) 进行 hack。

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T6 Strelice_。**

**本题分值按 COCI 原题设置，满分 $160$。**


title: [COCI2016-2017#7] BAZA

description:
Mirko 在一家大型的 IT 公司获得了暑期实习的机会。这家公司建造了一个大型数据库，包含 $N$ 行 $M$ 列，第 $i$ 行第 $j$ 列上的整数是 $A_{i,j}$。

在他实习的第一天，他收到了 $Q$ 次询问，每一次询问包含 $M$ 个整数 $B_1,B_2,\dots,B_M$。但不幸的是，有些数在传输的过程中丢失了，数据库将它们替换为 $-1$。Mirko 需要回答数据库中有多少行和询问中的所有数匹配。形式化的说，Mirko 需要回答在范围 $[1,N]$ 内有多少个整数 $i$，满足 $\forall j\in[1,M]$，$B_j=-1$ 或 $B_j=A_{i,j}$。例如，如果 $M=3$，某一次询问为 $-1~3~2$，那么 Mirko 需要找到所有满足第一列为任意整数，第二列为 $3$，第三列为 $2$ 的行数。

Mirko 毕竟是刚开始实习的新人，因此他希望能够得到你的帮助。现在，请你帮助他回答这些询问！

inputFormat:
第一行输入两个整数 $N,M$，分别表示数据库的行数和列数。
随后 $N$ 行，每行输入 $M$ 个整数，描述这个数据库。
随后一行输入一个整数 $Q$，表示询问次数。
随后 $Q$ 行，每行输入 $M$ 个整数，描述一次询问。

outputFormat: 对于每次询问，输出一行一个整数，表示满足要求的行数。

hint:
**【样例 1 解释】**

对于第一次询问，第一行和第三行满足询问中第三列是 $2$ 的要求。
对于第二次询问，只有第三行满足询问中第二列是 $3$，第三列是 $2$ 的要求。
对于第三次询问，由于并没有对每一列上的数作出要求，因此所有行都满足要求。

**【数据范围】**

对于所有数据，$1\leqslant N,M\leqslant 10^3$，$1\leqslant Q\leqslant 50$，$1\leqslant A_{i,j}\leqslant 10^6$，$B_j=-1$ 或 $1\leqslant B_j\leqslant 10^6$。

**【题目来源】**

本题来源自 **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T1 BAZA_**，按照原题数据配置，满分 $50$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2016-2017#7] UZASTOPNI

background: **本题和 [P1147](https://www.luogu.com.cn/problem/P1147) 的区别仅在于连续自然数和的数据范围和输出格式。**

description: 求出所有的和为 $N$ 的长度 $\geqslant 2$ 的连续自然数段。

inputFormat: 输入仅一行一个整数 $N$，表示连续自然数段的和。

outputFormat:
输出若干行，每行两个整数，表示满足条件的连续自然数段中的第一个数和最后一个数，**按第一个数的值降序排列**。

对于给定的输入数据，保证至少有一个解。

hint:
**【样例 1 解释】**

$10=1+2+3+4$，可以发现和为 $10$ 的满足要求的连续自然数段有且仅有一个。

**【数据范围】**

对于所有数据，$3\leqslant N\leqslant 10^{10}$。

**【题目来源】**

本题来源自 **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T2 UZASTOPNI_**，按照原题数据配置，满分 $80$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2016-2017#7] IGRA

background: Mirko 和 Slavko 对他们的滑雪旅行感到十分厌烦，于是他们开始玩一个新游戏。

description:
首先，Mirko 指定了一个整数 $N$，然后 Slavko 写下了 $N$ 个字母，Mirko 写下了一个长度为 $N$ 的单词。Slavko 需要他写下的 $N$ 个字母组成一个单词，并且他的单词中没有一个位置上的字母与 Mirko 写下的单词中相同位置的字母相同。为了使得这个游戏具有挑战性，Mirko 还要求 Slavko 写下的单词是所有满足要求的单词中字典序最小的。这个单词**必定会存在**。介于 Mirko 和 Slavko 还很年轻，他们只知道 `a`、`b`、`c` 三个字母，因此他们写下的单词也都只会包含这三个字母。

请帮助 Slavko 找到这样的单词。

inputFormat:
第一行输入一个整数 $N$，表示 Mirko 和 Slavko 写下的单词包含的字母数。
第二行输入一个长度为 $N$ 的字符串，表示 Slavko 写下的单词中包含的所有字母。
第三汉输入一个长度为 $N$ 的字符串，表示 Mirko 写下的单词。

outputFormat:
输出一行一个长度为 $N$ 的字符串，表示满足要求的字典序最小的字符串。

对于两个长度为 $N$ 的字符串 $a,b$，当且仅当存在一个整数 $p\in[1,N]$，使得 $\forall i\in[1,p)$，$a_i=b_i$，且 $a_p<b_p$ 时，$a$ 的字典序小于 $b$。

hint:
**【数据范围】**

对于 $40\%$ 的数据，保证 $1\leqslant N\leqslant 20$。
对于所有数据，$1\leqslant N\leqslant 5000$，所有字符串仅可能包含字母 `a`、`b`、`c`。

**【题目来源】**

本题来源自 **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T3 IGRA_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2016-2017#7] POKLON

description:
今天，Kile 在庆祝他的生日。他最好的朋友 Ivan 决定送给他一个特殊的天平。这种天平的特点是它是递归的，即在每个梁的末端，要么有一个砝码，要么有一个新的天平，要么什么都没有。当然，如果天平左梁上的总质量大于右梁上的总质量，则天平会向左倾斜。类似地，如果右侧梁上的质量较大，则天平向右倾斜。否则，我们说天平是平衡的。注意这里和我们平常所了解的天平的平衡条件是不同的。下图是一个该类天平的例子。

![](https://cdn.luogu.com.cn/upload/image_hosting/vupj9ham.png)

Kile 真的很喜欢这份礼物，作为一名真正的计算机科学家，他立即尝试使用总质量尽可能小的新的砝码来平衡这份礼物。新砝码的重量应该是**正实数**。如果某一个天平本身是平衡的，并且它的所有子天平都是平衡的，那么我们说这个天平是平衡的。

成功平衡天平后，Kile 决定在胸前纹上天平上砝码的总质量，以二进制表示，不带前导零。可以证明总质量必然是一个**正整数**。我们想知道 Kile 在胸前纹的的号码是多少，即以质量尽可能小的新的砝码来平衡这个天平之后，天平上所有砝码的总质量的二进制表示。

inputFormat:
第一行输入一个整数 $N$，表示天平里面包含的子天平数量。根天平的编号为 $1$。
随后 $N$ 行，第 $i$ 行两个整数 $a,b$，其中，如果 $a$ 是正数，那么就表示 $i$ 号天平左端是一个天平，否则表示 $i$ 号天平左端是一个质量为 $-a$ 的砝码；如果 $b$ 是正数，那么就表示 $i$ 号天平右端是一个天平，否则表示 $i$ 号天平右端是一个质量为 $-b$ 的砝码。

outputFormat: 输出仅一行，表示以质量尽可能小的新的砝码来平衡这个天平之后，天平上所有砝码的总质量的二进制表示。**不包含前导零**。

hint:
**【样例 1 解释】**

天平的初始状态见题目描述中的图片。Kile 将会在 $2$ 号天平的左侧放一个质量为 $1$ 的砝码，右侧放一个质量为 $2$ 的砝码。此时，两个天平都处于平衡状态，可以证明这种方案增加的新的砝码的质量是最小的。此时，天平上所有砝码的总质量是 $5+5+10=20$，其二进制表示为 $10100$。

**【数据范围】**

对于所有数据，$1\leqslant N\leqslant 10^6$，$-10^9\leqslant a,b\leqslant N$。

**【题目来源】**

本题来源自 **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T4 POKLON_**，按照原题数据配置，满分 $120$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2015-2016#7] Nizovi

description:
一种编程语言中的数组按如下方式定义：

- 数组的开头和结尾分别用大括号（$\texttt \{$ 和 $\texttt \}$）表示。
- 每组大括号内有若干个（可能为 $0$）用逗号分隔开来的**元素**（每个数组的最后一个元素后面没有逗号）。
- 每个元素可以是一个**单词**（由小写字母组成的字符串）或一个数组。
- 一些合法的数组：$\texttt {\{\}}, \texttt{\{a,b,c\}}, \texttt{\{abc,znj,\{novi,niz\},pozz\}}$。

你需要采用下列码风使得程序更加美观：

- 遇到单词或大括号时另起一行。
- 逗号应直接放置于一个数组元素的后面。
- 每遇到一个 $\texttt{\{}$，增加 $2$ 个空格的缩进。
- 每遇到一个 $\texttt{\}}$，减少 $2$ 个空格的缩进。

现给定一个数组，输出上述码风下该数组的样式。

inputFormat: 一个字符串 $S$，表示给定的数组。

outputFormat: 给定码风下的数组。

hint:
**【数据规模与约定】**

- 对于 $50\%$ 的数据，元素只包含单词。
- 对于 $100\%$ 的数据，$1 \le |S| \le 1500$。

**【提示与说明】**

Checker 选自 [Testlib 库](https://github.com/MikeMirzayanov/testlib/blob/master/checkers/fcmp.cpp)，见附件。

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 1 Nizovi_。**

**本题分值按 COCI 原题设置，满分 $50$。**


title: 「TFOI R1」Average Number

background:
**题目背景与题意无关，可直接阅读题目描述。**

有一种人叫做「别人家的妹妹」，小 A 对此感触颇深。

小 A 的妹妹——小 L——经常把小 A 的藏书偷走看，小 A 对此很是头疼。

这一次，强迫症小 A 正在收拾他的藏书，小 L 趁小 A 不注意偷走了一本。

「还给我。」

『不给。不过。。。如果你能猜出我手上的书的编号，我就还给你。』

小 A 为了方便拿取和整理他的藏书，特意给每本书从一开始编了号。

「开玩笑，我的书这么多，我怎么猜？」

『嗯。这样吧，我告诉你剩下的那堆书的编号平均值。怎么样，这个提示够了吧。』

「。。。」

小 A 的藏书多到他都不知道有多少本，但是作为一个合格的 OIer，小 A 借助计算机成功算出了答案。只不过，他想要以这个问题来考验你一下。

description:
你知道 $\dfrac{\left(\sum\limits^{n}_ {i = 1}i \right) - m}{n - 1}$ 的值，其中 $m \in [1, n]$，$n$ 和 $m$ 均为正整数，你要求出 $n$ 和 $m$ 的值，保证有解。

如果有多种可行解，那么请输出 $n$ 较小的那一组解。

多组测试数据。

inputFormat:
第一行，一个正整数 $T$ 表示数据组数。

接下来 $T$ 行，每行三个非负整数 $a, b, c$ ，表示平均值为 $a + \dfrac{b}{c}$ 。

outputFormat: 共 $T$ 行，每行两个正整数，分别表示 $n$ 和 $m$。

hint:
**本题采用捆绑测试**。

- Subtask 1（5 points）：$T \leqslant 10$，$n \leqslant 10^3$。
- Subtask 2（5 points）：$T \leqslant 10^3$，$n \leqslant 10^3$。
- Subtask 3（5 points）：$T \leqslant 10$，$n \leqslant 5\times 10^5$。
- Subtask 4（40 points）：$T \leqslant 10^3$，$n \leqslant 10^{18}$。
- Subtask 5（45 points）：无特殊限制。

对于所有数据，$1 \leqslant m \leqslant n \leqslant 10 ^ {18}$，$n \not = 1$，$1 \leqslant T \leqslant 2 \times 10 ^{5}$，$1 \leqslant a \leqslant 10 ^{18}$，$0 \leqslant b < c \leqslant 10 ^ {18}$ 。

**保证 $\dfrac{b}{c}$ 是最简真分数。特别的，当 $b=0$ 时，$c=1$。**

---

**题目背景（续）**

『你。。你是怎么猜出来？』

小 L 说话之际，看着小 A 的眼神中的惊讶又多了一份崇拜。

「呵，这种难度的问题怎么可能难得到我？」

『啊。既然是这样子的话，那就再来玩一次吧！』

「。。。」


title: [COCI2015-2016#7] Prozor

description:
一扇规模为 $R \times S$ 的窗户上有若干只苍蝇。现有一把苍蝇拍，它可以消灭 $K \times K$ 矩形区域内（不含边界）的所有苍蝇。

请选择一种苍蝇拍的放置位置，使得被消灭的苍蝇数量最多。输出消灭的苍蝇的最大值和该方案。如果有多种符合的方案，请输出任意一种。

inputFormat:
第一行，三个整数 $R,S,K$。

接下来的 $R$ 行，每行 $S$ 个字符 $\texttt *$（表示苍蝇）或 $\texttt .$（表示空白区域）。数据保证至少能消灭一只苍蝇。

outputFormat:
第一行，输出能消灭苍蝇数量的最大值。当程序只答对该值时，可以获得 $50\%$ 的分数。

接下来的 $R$ 行，每行 $S$ 个字符。在输入的字符矩阵的基础上，将所选定的 $K \times K$ 矩形的四个角改为 $\texttt +$、横向边改为 $\texttt -$、纵向边改为 $\texttt |$ 即可。选定的矩形区域必须完全在整个矩阵内部。

**注：如果只想获得 $\mathbf{50\%}$ 的部分分，请只输出一个整数，即消灭苍蝇数量的最大值。此时，** $\red {\mathbf{请不要输出任何多余的字符（包括但不限于空格和换行符），否则会被判错。}}$

hint:
**【数据规模与约定】**

- 对于 $100\%$ 的数据，$3 \le K \le R,S \le 100$。

**【提示与说明】**

欢迎大家通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/luaa2ic5) 进行 hack。

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 2 Prozor_。**

**本题分值按 COCI 原题设置，满分 $80$。**


title: [COCI2015-2016#7] Ozljeda

description:
给定一个元素个数为 $K$ 的数列 $\{a\}$。现规定一个无穷数列 $\{x\}$ 如下：

$$x_i=\begin{cases}
a_i, & 1 \le i \le K, \cr
\bigoplus_{i=n-1}^{n-K} x_i, & n \ge K
\end{cases}$$

给定 $Q$ 组询问 $l_i,r_i$，求 $\bigoplus_{i=l}^r x_i$ 的值。

inputFormat:
第一行，一个整数 $K$。

第二行，$K$ 个整数 $a_i$。

第三行，一个整数 $Q$。

接下来的 $Q$ 行，每行两个整数 $l_i,r_i$。

outputFormat: 输出 $Q$ 行，每行对应一次询问的答案。

hint:
**【数据规模与约定】**

- 对于 $100\%$ 的数据，$1 \le K \le 10^5$，$0 \le a_i \lt 10^{18}$，$1 \le Q \le 10^6$，$1 \le l_i \le r_i \le 10^{18}$。

**【提示与说明】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 3 Ozljeda_。**

**本题分值按 COCI 原题设置，满分 $100$。**


title: [COCI2015-2016#7] Otpor

description:
众所周知，电阻的连接包括串联和并联两种。而一条电路的所有电阻可以视为这条电路的等效电阻 $R_{ekv}$。当电阻串联时，可以这样表示：

$$\text{(R1-R2-R3-...-RK)}$$

同时满足公式：

$$R_{ekv}=\sum_{i=1}^K R_i$$

并联时可以这样表示：

$$\text{(R1|R2|R3|...|RK)}$$

同时满足公式：

$$R_{ekv}=\frac{1}{\sum_{i=1}^K \frac{1}{R_i}}$$

现有一个包含 $N$ 种阻值为 $R_i$ 的电阻和足够多的导线。给定这些电阻的连接方式，求整条电路的等效电阻值。

inputFormat:
第一行，一个整数 $N$。

第二行，$N$ 个实数 $R_i$。

第三行，一个字符串 $S$，表示电路。字符串只包含 $\texttt R$、$\texttt 1 \sim \texttt 9$、$\texttt ($、$\texttt )$、$\texttt -$ 和 $\texttt |$。数据保证不会有括号不匹配或不合法的现象，同时括号的数量将会最小化。任何一对括号内都不会同时出现 $\texttt -$ 和 $\texttt |$。电路只包含给定的 $N$ 种电阻，且可能出现任意（包括 $0$）次。

outputFormat: 输出整条电路的等效电阻值。输出与标准答案相差不超过 $10^{-5}$ 则视为正确。

hint:
**【数据规模与约定】**

- 对于 $20\%$ 的数据，$N=3$ 且电路恰好包含这三种电阻。
- 对于 $40\%$ 的数据，$S$ 中只包含一对括号。
- 对于 $100\%$ 的数据，$1 \le N \le 9$，$0 \lt R_i \lt 100$，$1 \le |S| \le 10^5$。

**【提示与说明】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 4 Otpor_。**

**本题分值按 COCI 原题设置，满分 $120$。**


title: [COCI2015-2016#7] Prosti

description:
现有 $Q$ 组询问，每次给出正整数 $K,L,M$。定义全体高兴数的集合为 $\{x|x \le M$ 或 $x$ 为质数$\}$。

对于每次询问，求一个正整数 $i$，使得 $[i,i+K-1]$ 内恰好有 $L$ 个高兴数。如果不大于 $10^7$ 的 $i$ 值不存在，输出 $-1$。

inputFormat:
第一行，一个整数 $Q$。

接下来的 $Q$ 行，每行三个整数 $K_i,L_i,M_i$。

outputFormat: 输出 $Q$ 行，每行对应一次询问的答案。

hint:
**【数据规模与约定】**

- 对于 $100\%$ 的数据，$1 \le Q \le 10^5$，$1 \le K_i,M_i \le 150$，$0 \le L_i \le K_i$。

**【提示与说明】**

欢迎大家通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/rj308p4r) 进行 hack。

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 5 Prosti_。**

**本题分值按 COCI 原题设置，满分 $140$。**


title: [COCI2015-2016#7] Prokletnik

description:
定义魔法序列为满足所有元素的大小均在第一个元素和最后一个元素之间的序列。

现有一个元素个数为 $N$ 的数组 $a$。给出 $Q$ 次询问 $L,R$，求 $a$ 中下标在 $[L,R]$ 之间的最长的子魔法区间。

inputFormat:
第一行，一个整数 $N$。

第二行，$N$ 个整数 $a_i$。

第三行，一个整数 $Q$。

接下来的 $Q$ 行，每行两个整数 $L,R$。

outputFormat: 输出 $Q$ 行，每行对应一次询问的答案。

hint:
**【数据规模与约定】**

- 对于 $50\%$ 的数据，$N,Q \le 3 \times 10^4$。
- 对于 $100\%$ 的数据，$1 \le N,Q \le 5 \times 10^5$，$1 \le a_i \le 10^9$，$1 \le L \le R \le N$。

**【提示与说明】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 6 Prokletnik_。**

**本题分值按 COCI 原题设置，满分 $160$。**


title: [COCI2010-2011#5] DVONIZ（加强版）

background: 题面与[原题P7635 [COCI2010-2011#5] DVONIZ](https://www.luogu.com.cn/problem/P7635)无异，仅有数据范围，时空限制与分值不同。

description:
当前 $K$ 个元素的和或最后 $K$ 个元素的和都不大于 $S$ 时，我们说这个 $2\times K$ 个元素的序列是有趣的。

给出一个长度为 $N$ 的序列 $A$。对于每个元素，输出从该元素开始的最长的有趣的子序列。

inputFormat:
第一行包含整数 $N$ 和 $S$。

下面的 $N$ 行，每行包含序列 $A$ 中的一个整数 $A_i$。这些整数都是正的且它们的和不超过 $2\times 10^9$。

outputFormat:
输出共 $N$ 行。第 $i$ 行包含一个整数，表示从第 $i$ 元素开始的最长的有趣的子序列的长度。

如果当前位置上没有有趣的子序列，输出 `0`。

hint:
**【样例解释#1】**

对于样例 $1$ 的第一个位置，一共有 $4$ 个子序列，且都满足条件，故取最长的长度为 $4$ 的子序列。

**【数据范围】**

对于 $30\%$ 的数据，$2\le N \le 200$。

对于 $50\%$ 的数据，$2\le N \le 5 \times 10^3$。

对于 $70\%$ 的数据，$2 \le N \le 2 \times 10^5$。

对于 $100\%$ 的数据，$2\le N \le 3 \times 10^6$，$1\le S \le 10^9$，$1\le A_i \le 10^9$。


title: [COCI2016-2017#7] PARALELOGRAMI

description:
最近，一个叫 _Parallelograms_ 的游戏迅速在网络上流行。游戏一开始有 $N$ 个点，每个点的坐标**互不相同**。每次操作你可以选择三个**不共线**的点 $A,B,C$，然后，画出点 $D$，使得四边形 $ACBD$ 是以 $AB$ 为对角线的平行四边形，然后把点 $C$ 移动到点 $D$。注意这样的点 $D$ 有且仅有一个。

虽然在一开始所有点的坐标都互不相同，但是，你可以通过若干次操作使得某些点的坐标相同。与此同时，所有点的坐标的绝对值不能超过 $10^9$。

现在，请你通过最多 $2500$ 次操作，使得最终所有点都在第一象限，或者报告不存在操作方案。请注意，**你并不需要求出操作次数最少的操作方案**，你只需要求出操作次数不超过 $2500$ 且满足题目要求的方案即可。

inputFormat:
第一行输入一个整数 $N$，表示点的个数。
随后 $N$ 行，每行两个整数 $X_i,Y_i$，分别表示第 $i$ 个点的横坐标和纵坐标。

outputFormat:
如果无解，输出一行 `-1`。

否则，第一行输出一个整数 $M$，表示操作次数。
随后 $M$ 行，每行三个整数 $A,B,C$，表示一次操作中选择的三个点的编号。点 $C$ 按照题目描述部分所述规则变换，而点 $A,B$ 不做任何变换。

hint:
**【数据范围】**

对于所有数据，$3\leqslant N\leqslant 400$，$-10\leqslant X_i,Y_i\leqslant 10$。

**【题目来源】**

本题来源自 **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T5 PARALELOGRAMI_**，按照原题数据配置，满分 $140$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。

感谢 [mutton](https://www.luogu.com.cn/user/137367) 提供本题的 [SPJ](https://www.luogu.com.cn/paste/ck8tv23j)，如有 hack 数据，请直接私信给 mutton。


title: [COCI2016-2017#7] KLAVIR

description:
年轻的 Alisa 喜欢只用一根手指弹钢琴。但是，由于 Alisa 从来都没学过弹钢琴，因此她的弹琴过程完全是随机的。更准确地说，她会**等概率**选择钢琴的 $N$ 个音调上的任意一个，并且**独立于之前所有选择的音调**。

Alisa 的好朋友 Mirta 想要听一个连续的包含 $M$ 个音调 $A_1,A_2,\dots,A_M$ 的曲子，但由于 Alisa 弹琴过程是完全随机的，Mirta 只想知道，对于所有的 $1\leqslant i\leqslant M$，Alisa 选择音调使 Mirta 第一次听到连续的音调 $A_1,A_2,\dots,A_i$ 的**期望次数**。为了防止精度丢失，**答案对 $\bf 10^9+7$ 取模**。

inputFormat:
第一行输入一个整数 $N$，表示音调个数。
第二行输入一个整数 $M$，表示 Mirta 想要听的曲子包含的音调个数。
随后 $M$ 行，每行一个整数 $A_i$，表示曲子的第 $i$ 个音调。

outputFormat: 输出 $M$ 行，每行一个正整数，第 $i$ 行表示 Alisa 选择音调使 Mirta 第一次听到连续的音调 $A_1,A_2,\dots,A_i$ 的期望次数对 $\bf 10^9+7$ 取模之后的结果。

hint:
**【数据范围】**

对于 $40\%$ 的数据，保证 $1\leqslant M\leqslant 200$。
对于所有数据，$1\leqslant N\leqslant 100$，$1\leqslant M\leqslant 10^6$，$1\leqslant A_i\leqslant N$。

**【题目来源】**

本题来源自 **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T6 KLAVIR_**，按照原题数据配置，满分 $160$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: 「PMOI-5」送分题/Yet Another Easy Strings Merging

background:
**本题征集假做法和 hack 数据，如果您用假做法 AC 了，欢迎私信出题人提供 hack。**

> 信息可能有冗余。

——command_block 《考前小贴士》

djy 在看 P8001，看错题了，很自闭，然后就有了这个题。

description:
给定 $n$ 个 01 串，每次你可以从某个串开头移除一个字符并把**剩下的字符串**加入一个新串 $S$ 的末尾。最大化 $S$ 中相邻两个字符相同的对数。

例如你有 `1010 111` 两个串，如果你移除第一个串的第一个字符，则 `010` 被加入到 $S$ 中。

**串可以重复使用。**

inputFormat:
第一行一个正整数 $n$ 表示串的个数。

接下来 $n$ 行，每行一个 01 字符串。

outputFormat: 一行一个整数表示答案。

hint:
【样例解释】

依次取走第一个字符，$S$ 的变化过程为 `100->10000->100000`，答案为 $4$。

【数据范围】

记 $|s|$ 为字符串 $s$ 的长度，$s_i$ 为第 $i$ 个字符串  。
**本题采用捆绑测试。**

- Subtask 1（30 pts）：$n,\sum|s_i|\le 11$；
- Subtask 2（30 pts）：$n,\sum|s_i|\le 10^3$；
- Subtask 3（30 pts）：$n,\sum|s_i|\le 10^5$；
- Subtask 4（10 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 10^6$，$n\le \sum |s_i|\le 10^6$，$\forall i\in [1,n]$，$|s_i|\ge 1$。


title: 「GMOI R1-T3」Number Pair

description:
我们定义满足如下条件的数对 $(x,y)$ 叫做奇妙数对：

$k \times \gcd(x,y)=\operatorname{lcm}(x,y)$ 并且 $P \le \gcd(x,y) \le Q$（保证 $P \le Q$）。

有 $T$ 组数据，对于每一组数据，给定 $k,P,Q$ 三个数，求符合条件的数对 $(x,y)$ 的对数。

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

inputFormat:
**本题有多组数据。**

第一行一个整数 $T$，表示数据数量。

接下来 $T$ 行，每行三个整数 $k,P,Q$。

outputFormat: 对于每一组数据，给出对应答案，每组数据一行。


title: 串串题

description:
给定长度分别为 $n,m$ 的整数序列 $A,B$ 和常数 $W,d$，序列从 $1$ 开始标号，保证 $A_i,B_i \in [1,W]$。

容易发现，我们有 $\binom{W}{d}$ 种方案选择 $[1,W]$ 中的 $d$ 个互不相同的整数。

对于每一种选择的方案，我们删去 $A$ 中出现的对应的 $d$ 种整数，令此时序列 $B$ 在序列 $A$ 中的出现次数为这次选择方案的权值。

你需要求所有的选择方案的权值和，对 ${10}^9+7$ 取模。

若对题意有疑问，请阅读样例及样例解释。

注：$\binom{a}{b}$ 表示组合数，含义为在 $a$ 个物品中**无序**地选择出 $b$ 个物品的方案数。

**请注意：我们并不会删除序列 $\bm{B}$ 中出现的对应整数。**

inputFormat:
**本题有多组数据。**

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

第一行，四个正整数 $n, m, W, d$，保证 $d \le W$。

第二行，$n$ 个正整数 $A_1, A_2, \ldots, A_n$，表示序列 $A$。

第三行，$m$ 个正整数 $B_1, B_2, \ldots, B_m$，表示序列 $B$。

outputFormat: 对于每组数据，输出一个整数表示答案对 ${10}^9+7$ 取模的结果。


title: 邮箱题

background: 邮箱，一种历史悠久的接信箱子。西方的邮箱以红色为主，东方的邮箱以绿色为主。

description:
有一张 $n$ 个点和 $m$ 条边构成的**有向**图。每个点内都有一把另一个点的钥匙，$i$ 号点内有 $k_i$ 号点的钥匙。你能进入一个点当且仅当你有该点的钥匙。保证 $k_i$ 构成排列。

只要进入了一个点，就获得了这个点内有的钥匙。一旦获得钥匙就不会被消耗。

现在你拿到了 $i$ 号点的钥匙并到了 $i$ 号点。你需要对每个 $i$ 求出：

1. 有多少点能被你到达。
2. 有多少点能被你到达并返回起点 $i$。

**请注意：给出的边均是有向边！**

inputFormat:
**本题有多组数据。**

第一行，一个正整数 $T$，表示数据的组数。对于每组数据：

第一行，两个整数 $n,m$，表示图的点数和边数。

第二行，$n$ 个整数 $k_1, k_2, \ldots, k_n$，表示 $i$ 号点内有 $k_i$ 号点的钥匙。保证 $k_i$ 构成排列。

接下来 $m$ 行，每行两个整数 $x, y$，表示图上的一条从 $x$ 指向 $y$ 的有向边。保证不含重边或自环。

outputFormat: 对于每组数据，输出 $n$ 行，每行两个整数，第 $i$ 行的整数分别表示从 $i$ 号点出发，能到达的点数和能到达并返回起点的点数。

hint:
**【样例解释】**

以下是第一组数据的解释：（图中括号内的内容为点上的钥匙编号）

![](https://cdn.luogu.com.cn/upload/image_hosting/hrserkw2.png)

1. $1$ 能到达的结点集合为 $\{1,2,3,4\}$，$1$ 能到达且能返回 $1$ 的结点集合为 $\{1,2,3,4\}$；
2. $2$ 能到达的结点集合为 $\{2,3\}$，$2$ 能到达且能返回 $2$ 的结点集合为 $\{2\}$；
3. $3$ 能到达的结点集合为 $\{3\}$，$3$ 能到达且能返回 $3$ 的结点集合为 $\{3\}$；
4. $4$ 能到达的结点集合为 $\{4\}$，$4$ 能到达且能返回 $4$ 的结点集合为 $\{4\}$。

这是一个合法的遍历过程：从 $1$ 开始，初始钥匙为 $2$，到达结点 $2$ 并获得钥匙 $3$，到达结点 $3$ 并获得钥匙 $4$，回到结点 $1$，到达结点 $4$ 并获得钥匙 $1$，到达结点 $3$，回到结点 $1$。

**【数据范围】**

对于 $100\%$ 的数据，满足 $n \ge 3$，$m\ge 0$，$\sum n\le 1.5\times{10}^6$，$\sum m\le 3\times{10}^6$，$1 \le T\le 2\times{10}^4$，$1 \le x, y \le n$，保证图中不含重边或自环。

**本题采用捆绑测试且开启子任务依赖！**

|子任务|对 $n$ 的约束|对 $m$ 的约束|分值|依赖|
|-|-|-|-|-|
|1|$n\le 6$|$m\le 12$|$20$|\ |
|2|$\sum n^3\le {10}^7$|$\sum m^3\le 2\times {10}^7$|$25$|\ |
|3|$\sum n^2\le {10}^8$|$\sum m^2\le {10}^8$|$25$|子任务 1、2|
|4|||$30$|子任务 1、2、3|


title: 签到题

background:
著名的【数据删除】是一个热爱旅游的人！这一天他来到了神秘的 ZYL 国度。

入海关的时候他被问到了一个题目，如果答对他就可以顺利到达 ZYL 的首都 ZY 了！身为堂堂【数据删除】，他居然还花了 $10^{-233}$ 秒才想出来做法，实在是有点难的！于是他决定拿来考考你。

description:
给定长度为 $n$ 的序列 $a$，保证 $a_i$ 是**正整数**。你需要选择一个位置 $i$ 并将 $a_i$ 修改为一个**任意的整数**。最大化最长**严格**上升子串的长度。

所谓严格上升子串，就是从序列中选出位置**连续**的若干个数字，满足后一个数字比前一个大（而不能相等或小于）。

如序列 $[1,4,2,3,5]$ 中，子序列 $[2,3,5]$ 就是严格上升子串，而 $[4,2,3]$（不上升）和 $[1,2,3]$（不连续）则不是。

inputFormat:
第一行，一个正整数 $n$，表示序列的长度。

第二行，$n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示序列 $a$。

outputFormat: 输出一行一个整数，表示修改后，你最大化的最长严格上升子串的长度。

hint:
**【样例解释 \#1】**

对于样例 \#1，我们可以将序列 $[1,4,2,2,3]$ 中的第三个位置修改为 $5$，得到新序列 $[1,4,5,2,3]$。这个序列的最长严格上升子串是 $[1,4,5]$，长度为 $3$。

容易证明，不存在一种修改方案使得修改后的序列的最长严格上升子串的长度大于 $3$。

---

**【样例解释 \#4】**

对于样例 \#4，我们可以将序列 $[8,2,3,1,4,5]$ 中的第三个位置修改为 $0$，得到新序列 $[8,2,0,1,4,5]$。这个序列的最长严格上升子串是 $[0,1,4,5]$，长度为 $4$。

容易证明，不存在一种修改方案使得修改后的序列的最长严格上升子串的长度大于 $4$。

---

**【数据范围】**

对于前 $20\%$ 的数据，满足 $n \le 5$，$a_i \le 5$。
对于前 $40\%$ 的数据，满足 $n \le 10$，$a_i \le 10$。
对于前 $70\%$ 的数据，满足 $n \le 300$。
对于 $100 \%$ 的数据，满足 $1 \le n \le {10}^6$，$1 \le a_i \le {10}^9$。


title: 「RdOI R3.5」Table

background: 小 A 想要打表过题，但是代码长度过长。他想到了把数字用十六进制表示有时比用十进制表示更短，决定把答案表用十六进制进行改写。

description:
我们定义下文中的「十六进制」均用数字 $0\sim 9$ 和大写英文字母 $\tt A\sim F$ 表示，且每个十六进制数字都包含前缀 $\colorbox{#ddd}{\tt 0x}$。

给出若干个用大括号包裹，用逗号分隔的十进制整数，代表小 A 的答案表。你需要对答案表内的每个数字进行改写：

- 若该整数使用十六进制表示所占字符数小于或等于十进制表示，则将该数改写为十六进制。
- 否则，该数保留十进制不变。

输出改写后的答案表。

inputFormat: - 输入一行一个字符串，字符串中仅包含大括号、逗号和数字，不包含空格和其他字符等。具体格式可以参考 C++ 语言的数组定义格式。代表小 A 的答案表，保证答案表格式正确。

outputFormat: - 输出一行一个字符串，表示改写后的答案表。

hint:
### 样例解释

#### 样例 \#1

- $1$ 用十六进制表示为 $\tt 0x1$，共 $3$ 个字符，长度大于十进制的 $1$ 个字符。
- $314159$ 用十六进制表示为 $\tt 0x4CB2F$，共 $7$ 个字符，长度大于十进制的 $6$ 个字符。
- $3141592653589793$ 用十六进制表示为 $\tt 0xB29430A256D21$，共 $15$ 个字符，长度小于十进制的 $16$ 个字符。

#### 样例 \#2

输入为空数组，所以输出也应为空数组。

### 数据范围及约定

本题共五个测试点，每个测试点 20 分，总分数为各测试点分数之和。

记答案表中共有 $n$ 个整数，这些整数分别为 $a_1,a_2,\cdots,a_n$。则对于 $100\%$ 的数据，$0\le n\le10^3$，$0\le a_i < 2^{64}$。


title: 『JROI-4』少女幻葬

background:
[该题原题目背景](https://www.luogu.com.cn/paste/imhwx32x)

[少女幻葬](https://thwiki.cc/%E5%B0%91%E5%A5%B3%E5%B9%BB%E8%91%AC_%EF%BD%9E_Necro-Fantasy)是八云蓝的主题曲，同样也是东方妖妖梦 extra stage 的 boss 战音乐。

是使用 ZUN 号的音乐中最为经典的一首之一。钢琴声仿佛在描绘一个强大而又美丽的妖兽的形象，而嘹亮的 ZUN 号配合蓝华丽的弹幕将死亡的主题表现到了极致。

description:
给定一个长度为 $n$ 的序列 $a$，并给出序列第 $i$ 个数 $a_i$ 的取值范围 $[l_i,r_i]$。现在蓝想知道有多少个序列 $a$ 满足对于给定的常数 $k$，有：

- 任意相邻两数的最大公因数都不为 $k$；

- 任意相邻三数的最大公因数都恰好为 $k$。

 由于答案可能很大，请输出其 $\bmod \space998244353$ 的值。

inputFormat:
第一行两个数 $n,k$。

接下来 $n$ 行，每行两个数分别表示 $l_i,r_i$。

outputFormat: 一行，答案对 $998244353$ 取模的结果。

hint:
【样例解释】

对于样例 $1$，可行的序列有：$[2,6,3],[3,6,4],[4,6,3]$。

【数据范围及约定】

- Subtask1（7pts）$3 \leq n \leq 5$，$1 \leq m \leq 10$。
- Subtask2（23pts）$3 \leq n \leq 100$，$1 \leq m \leq 100$。
- Subtask3（25pts）$3 \leq n \leq 1000$，$1 \leq m \leq 1000$。
- Subtask4（45pts）无特殊限制。

对于 $100\%$ 的数据，满足 $3 \leq n \leq 2000$，$1 \leq l_i \leq r_i \leq 5000$，$1 \leq k \leq 5000$。

其中 $m=\max_{i=1}^{n}r_i$。


title: 「REOI-1」调整圣剑

background:
威廉从仓库搬出了瑟尼欧里斯。

六十八号悬浮岛的边陲，稍稍隆起的小山丘上。

风势平稳，空气澄净，星光柔和，各方面条件都合适的夜晚。

他掀开盖着瑟尼欧里斯的布，让剑身透风。

威廉注入些许魔力。太阳穴稍微会痛，不过这种程度还没什么大不了。

瑟尼欧里斯顿时绽发柔和光芒。

「——调整开始。」

description:
具体而言，圣剑瑟尼欧里斯由 $n$ 个护符组成，每个护符有一个权值 $a_i$。威廉会进行 $k$ 次调整，每次调整一个护符，并获得与护符权值相等的疲惫值。

然而由于护符间的某种奇怪联系，威廉调整护符时有一些限制，这些限制形如 $(i,j,x,y)$，表示威廉必须在第 $i$ 次调整时调整前 $x$ 个护符中的一个 **或** 在第 $j$ 次调整时调整后 $y$ 个护符中的一个，否则圣剑就会崩溃。

现在，珂朵莉想知道威廉在调整完所有护符后的最小疲惫值是多少。

**注意每个护符可以调整不止一遍。**

inputFormat:
第一行三个正整数 $n,k,q$。

接下来一行 $n$ 个正整数 $a_1,a_2,a_3...a_n$。

接下来 $q$ 行，每行 $4$ 个正整数 $i,j,x,y$。

outputFormat: 一个数表示威廉疲惫值的最小值。

hint:
样例解释：

对于第一组样例，第一次选取 $a_2$ ，第二次选取 $a_2$ 。可以证明这是满足限制的最小值。

对于第二组样例，第一次选择 $a_1$ ，第二次选择 $a_2$ 是为满足限制的最小值。

对于 $24\%$ 的数据：$1\le n \le 20,1\le k,q \le 14$ ；

对于 $56\%$ 的数据：$1\le n \le 100,1\le k,q \le 60$ ；

对于 $80\%$ 的数据：$1\le n \le 10^5, 1\le k,q\le 10^3$ ；

对于 $100\%$ 的数据：$1\le n \le 10^5,1\le k,q\le 10^4,1\le a_i\le 10^5$。

对于每一次询问有 $1 \le i,j \le k$ , $1 \le x,y \le n$。


title: 「REOI-p1」打捞

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/0ukve6wl.png)

出题人：XL4453

验题人：犇犇犇犇

文案：小糯米

upd：注意，先取模再取max

description:
“别介意，我和那些家伙都是打捞者。我们在头一次追寻梦想降落到地表时，就做好丧命的准备和赴死的觉悟了。”

葛力克一行人在一次打捞中，时来运转，获得了不少的宝藏。在归途之路，言及谁的功劳最大之时，大家却起了冲突。有人说自己的宝藏是史上绝无仅有，是在鬼门关前绕了一大圈才好不容易抢到的一个；有人说自己惨淡经营，虽然没有获得那么珍贵的宝物，但数量可观，也足以与之相提并论；也有人说自己的收获二者兼有，应当综合评价云云：总之，场面一片混乱，颇有生死与共的患难之交从此决裂的危险。

于是，大家把目光投到了葛力克的身上，这让他十分为难。思索良久，他决定这样来评价大家的贡献：

假设一共有 $n$ 名打捞者，第 $i$ 位打捞者 $a_i$ 取得的宝物数量为 $l_i$ ，而其中第 $p$ 件宝物对应的价值则为 $a_{i,p}$ ，那么在计算的时候只需要将每个序列相加求和即可。但是葛力克并不满足于现状，他现在想知道，如果是将两个人的贡献放在一起看待，那么又将如何计算呢？
一番激烈的头脑风暴后，他决定这样来计算两位打捞者 $i,j$ 之间的贡献 $g(i,j)$ ：将 $a_i$ 与$a_j$ 分别复制数遍使得两堆宝物的数量都为 $k$ ，得到两个序列 $a_i',a_j'$ ，则 $g(i,j)= \sum\limits_{p=1}^k a'_{i,p}\times a'_{j,p}$ 。

现在葛力克想知道，这个贡献值的最大值是多少。

因为贡献值可能会很大，超出了正常生物大脑的运算能力，所以我们对它进行 $998244353$ 的取余。

----------
形式化题面：给定一个整数 $n$，和 $n$ 个序列，第 $i$ 个序列 $\{a_i\}$ 长度为 $l_i$，将每个 $a_i$ 复制 $\dfrac k{l_i}$ 遍得到 $\{a'_i\}$ 使得 $\{a'_i\}$ 的长度为 $k$。

试求：$\max\limits_{i=1,j=i+1}^{i,j\leq n}\{g(i,j)\bmod 998244353\}$，其中$g(i,j)= \sum\limits_{p=1}^k a'_{i,p}\times a'_{j,p}$ 。

inputFormat:
第一行两个整数 $n$，$k$。

接下来输入 $n$ 行。第 $i + 1$ 行第一个数为 $l_i$，接下来输入 $l_i$ 个数，表示打捞者的宝藏 $a_i$。

outputFormat: 一个整数，表示所求的最大值。