title: 【MX-S3-T3】「FeOI Round 1」再演

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

jt 有一个大小为 $n$ 的集合 $S$，集合中每个元素都是一个无序二元整数对 $(x, y)$，保证集合中 $1 \sim 2n$ 共 $2n$ 个整数每个恰好出现一次。

比如当 $n = 3$ 时，合法的集合 $S$ 可能是 $\{(1, 5), (2, 3), (4, 6)\}$。

开始时你只知道 $n$ 而不知道 $S$ 具体是什么。

现在支持一种操作：你可以给出 $i, j$（$1 \le i, j \le 2n$），然后 jt 会交换 $i, j$ 在 $S$ 中的位置（如 $i, j$ 在同一个二元组内，或 $i = j$，则什么也不会发生）。

比如，当 $S = \{(1, 5), (2, 3), (4, 6)\}$ 时，执行 $i = 2, j = 6$ 后 $S = \{(1, 5), (6, 3), (4, 2)\} = \{(1, 5), (2, 4), (3, 6)\}$。

在最开始时以及每次操作过后，对于当前的集合 $S$，jt 会告诉你 $res = \min\limits_{(x, y) \in S} \max(x, y)$。

比如，当 $S = \{(1, 5), (2, 3), (4, 6)\}$ 时，$res$ 为 $\min(\max(1, 5), \max(2, 3), \max(4, 6)) = \min(5, 3, 6) = 3$。

注意，每次 jt 告诉你 $res$ 之后**不会撤销**你做的操作，即你的操作是持续有效的。

你需要在 $lim$ 次操作内猜出**初始的**集合 $S$，即进行所有交换操作之前的版本。

保证初始的 $S$ 是提前确定的，即**交互库不自适应**。

### 交互方式

**本题单个测试点内包含多组数据。**

首先读入数据组数 $T$。

接下来有 $T$ 组数据，对于每组数据进行以下过程：

输入 $S$ 的大小 $n$ 以及 $lim$ 以开始交互。

每次操作，首先读入 $res$，接下来输出一行 `^ i j` 表示你要执行操作 $i, j$。

在你确定答案后，请先输出一行一个 `!`，然后接下来 $n$ 行每行输出两个整数 `x y` 代表 $S$ 中的一个二元组，然后准备读入下一组数据。你可以以任意顺序输出这些二元组，且二元组内元素顺序可以任意。

每次在你输出一行后，请清空缓冲区：

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 其它语言请自行查阅文档。

**当你在单个测试点所有测试数据的总操作次数不超过 $\boldsymbol{2.5 \times 10^5}$ 次时**，保证交互库占用时间不超过 $1\operatorname s$，空间不超过 $128\operatorname{MB}$，也就是你至少能使用 $1 \operatorname{s}$ 的时间以及 $384\operatorname{MB}$ 的空间。

inputFormat: 见「交互方式」。

outputFormat: 见「交互方式」。


title: [ROI 2022 Day 1] 照明

type: P

background:
翻译自 [ROI 2022 D1T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day1.pdf)。

在平面直角坐标系上有一个矩形区域，它的四个角分别在 $(0, 0), (w, 0), (w, h) , (0, h)$。该区域上有 $n$ 个照明灯，第 $i$ 个照明灯位于坐标点 $(x_i, y_i)$。

每个照明灯照亮一个 $90$ 度的角，这个角的边与坐标轴平行，顶点为照明灯所在位置。因此，每个照明灯有四个可能的照亮方向:

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

description:
给定一个允许的角度方向的集合（对于所有照明灯都相同）。对于每个照明灯，选择其中一个允许的方向。需要照亮尽可能大的区域。如果一个点至少被一个照明灯照到，则认为该点被照亮。

计算使用照明灯可以照亮的区域的最大可能面积，其中每个照明灯都向其中一个允许的方向上照。

inputFormat:
每个测试点包含多组数据。

第一行给出一个整数 $k (1 \le k \le 4)$，表示每组数据中允许的角度方向的数量。

第二行给出 $k$ 个整数，表示允许的方向编号（如当灯光允许向右上或左下照时，输入为 `1 3`）。所有 $k$ 个数字是不同的，并按升序排列。

第三行给出一个整数 $t (1 \le t \le 10000)$，表示数据的组数。接下来输入 $t$ 组数据。

每个数据集的第一行给出三个整数 $n,w,h (1 \le n \le 100000, 1 \le w, h \le 10^9)$，表示区域上的照明灯数量和区域的大小。

接下来的 $n$ 行，每行两个整数 $x_i,y_i (0 \le x_i \le w, 0 \le y_i \le h)$，表示第 $i$ 个照明灯的坐标。保证任意两个照明灯不在同一点上。

outputFormat: 对于每组数据，输出一个整数，表示可以使用照明灯照亮的区域的最大可能面积。


title: [ROI 2022 Day 2] 交换

background:
翻译自 [ROI 2022 D2T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。

给定一个 $n$ 位十进制数 $x$。可以任意多次交换相邻的两个数位，每次交换会产生一个代价 $y$。如果通过 $k$ 次这样的交换得到了数字 $x_{new}$，则收益等于 $x_{new}-k\times y$。

定义：如果通过交换从 $x$ 得到了数字 $x_{new}$，并且在此过程中达到了最大可能的收益，则称数字 $x_{new}$ 为最优数字。

例如，当 $y=114$ 时，可以通过交换 $3$ 次将数字 $3327$ 中的 $7$ 移到最前面，得到最大的收益 $7332-3\times114=6990$。此时就称 $7332$ 为最优数字。

description: 众所周知，这样的最优数字可能不止一个（对于同一个 $x$，它的所有最优数字获得的收益是相等的，但它们的值不相等）。对于给定的 $x$ 和 $y$，需要确定最优数字中的最大值。

inputFormat:
第一行包含一个由 $n$ 个十进制数位组成的整数 $x$（$1\le n\le10^5$），数字 $x$ 可能有前导零。

第二行包含一个整数 $y$，表示一次交换的代价（$1\le y\le10^{16}$）。

outputFormat: 输出一个整数 $x_{new}$，表示最优数字中的最大值。数字 $x_{new}$ 的长度为 $n$，并且可能包含前导零。


title: [ROI 2022 Day 2] 天狼星探险队

background:
翻译自 [ROI 2022 D2T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。

“天狼星探险队”游戏中有 $n$ 个玩家，编号从 $1$ 到 $n$。每个玩家在之前的任务中积累了 $c_i$ 点经验。如果两个玩家具有相同的经验值，我们称他们具有相同的等级。经验更高的玩家具有更高的等级。

游戏由多个回合组成。在每个回合结束时，每个玩家都会获得经验，该经验为其他玩家中比他更高的**级别的数量**。例如，如果玩家的经验值为 $[2, 5, 5, 1, 2, 10]$，那么第一个玩家的经验将增加 $2$：存在两种更高级别的玩家——经验值分别为 $5$ 和 $10$ 的玩家。这个例子中最后一个玩家的经验不会增加。玩家的经验会同时改变，比如在这个例子中，回合结束时玩家的经验将变为 $[4, 6, 6, 4, 4, 10]$。

description:
需要回答几个问题。每个问题可以是以下三种类型之一：
1. 在进行 $k$ 个回合后，玩家将拥有多少不同的级别？
2. 在前 $k$ 个回合中，所有玩家共添加了多少经验？
3. 在第 $k$ 个回合结束时，玩家编号 $i$ 将拥有多少经验？

inputFormat:
第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le300,000$），分别表示玩家数量和需要回答的问题数量。

第二行包含 $n$ 个整数 $c_i$（$0\le c_i\le10^{12}$），表示当前游戏开始时每个玩家的经验值。

接下来有 $q$ 行问题。每行以整数 $t$（$t\in\{1，2，3\}$）开头，表示问题类型。
- 如果 $t=1$，则后面是整数 $k$（$0\le k\le10^{12}$），表示回合数。
- 如果 $t=2$，则后面是整数 $k$（$0\le k\le10^{12}$），表示回合数。
- 如果 $t=3$，则后面是两个整数 $k$ 和 $i$（$0\le k\le10^{12}，1\le i\le n$），表示回合数和玩家编号。

在所有问题中，$k=0$ 表示游戏开始时到进行第一轮之前的时刻。

outputFormat: 对于每个问题，输出一行一个数字表示其答案。


title: [ROI 2022 Day 2] 搬货

background:
翻译自 [ROI 2022 D2T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。

仓库操作员需要使用特殊叉车移动重箱。可以将仓库简化为 $n$ 个房间，通过 $m$ 条走廊连接。可以通过走廊从任意一个房间到达任意其他房间。房间编号从 $1$ 到 $n$。走廊 $i$ 直接连接房间 $u_i$ 和 $v_i$，可以双向移动。

叉车可以升降货物，如果不携带货物，可以在空房间和走廊之间移动。最初，叉车位于房间 $1$，并携带着升起的货物。叉车可以执行以下操作：

1. 如果叉车位于房间 $a$ 并且携带升起的货物，则可以将货物放置在房间 $b$，前提是房间 $a$ 和 $b$ 直接相连。完成此操作后，叉车不再携带货物并可以移动。
2. 如果叉车位于房间 $a$，货物放置在房间 $b$，并且房间 $a$ 和 $b$ 直接相连，则叉车可以在不移动的情况下升起货物。完成此操作后，叉车仍然位于房间 $a$ 并携带升起的货物，直到放下货物之前不能移动。
3. 如果叉车没有携带货物，则可以在走廊和房间之间移动，但不能通过放有货物的房间。

description: 空车在房间之间移动非常快，比升降货物的速度快得多。因此，我们假设叉车执行第一或第二操作需要一单位时间，而第三个操作是瞬时完成的。对于每个房间 $p(2 \le p \le n)$，需要确定叉车从初始位置（在第一个房间且携带升起的货物）到达房间 $p$ 并继续携带升起的货物所需的最短时间，或者确定这是不可能的。

inputFormat:
每个测试由多组数据组成。第一行给出一个整数 $t$（$1 \le t \le 100,000$），即数据的组数。接下来是每组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 500,000,1 \le m \le 500,000$），即仓库中房间和走廊的数量。

接下来的 $m$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n,u_i \ne v_i$），表示第 $i$ 条走廊连接的两个房间编号。保证每对通过走廊连接的房间只会出现一次（或者说每个走廊只输入一次）。保证如果所有房间都是空闲的，则可以通过走廊从任意房间到达任意其他房间，即由仓库简化成的图是联通的。

用 $\sum n$ 表示每一组数据中 $n$ 的总和，用 $\sum m$ 表示 $m$ 的总和，保证 $\sum n \le 500,000,\sum m \le 500,000$。

outputFormat: 对于每组输入，输出 $n - 1$ 个数字，其中第 $i$ 个数字应该等于叉车从房间 $1$ 开始到房间 $i+1$（同时继续携带升起的货物）需要升降货物的最小次数（也就是最短时间）。如果无法实现，则第 $i$ 个数字应为 $-1$。


title: 『STA - R3』存在

description:
构造一个长度为 $n$ 的序列，满足对于任意长度不小于 2 的子区间存在主元素。在此基础上，要求序列元素的种类数最大。其中序列的主元素定义为出现次数不小于序列长度的一半的数。

你构造的数列中每个元素必须是 $0$ 到 $10^9$ 之间的整数。

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

outputFormat: 一行 $n$ 个整数，表示你构造出的序列。如果有多种答案，输出任意一种即可。

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

数据范围：
- Subtask 1 (10pts)：$n\le 5$。
- Subtask 2 (40pts)：$n$ 是 $3$ 的倍数。
- Subtask 3 (50pts)：无特殊限制。

对于全部数据，$1\le n\le 10^3$。


title: [ROI 2022 Day 2] 挑战

background:
翻译自 [ROI 2022 D2T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。

在天狼星教育中心的设计班中，一个团队的成员设计了一种工业机器人。这种机器人将把零件放入标号从 $1$ 到 $n$ 的 $n$ 个容器中。每个容器最多可以放置 $a_i$ 个零件。

一共有 $m$ 台机器人。初始时，第 $j$ 台机器人有 $c_j$ 个零件。此外，第 $j$ 台机器人有一个工作范围，由两个数字 $l_j$ 和 $r_j$ 确定，表示机器人只能将零件放入编号从 $l_j$ 到 $r_j$ 的容器中（包括边界）。机器人试图尽可能多地将零件放入容器。

机器人分为两种类型。如果机器人的类型 $t_j = 0$，则其工作范围始终保持不变。而机器人类型 $t_j = 1$ 可以改变它的工作范围。如果将编号为 $x$ 的容器指定为最重要的容器，则每个类型为 $1$ 的机器人的工作范围将扩大，来使这个范围包含容器 $x$。或者说，具有类型 $1$ 的机器人 $j$ 的工作范围将改变为 $[\min(l_j,x),\max(r_j,x)]$。

description: 对于从 $1$ 到 $n$ 的每个 $x$，计算在容器 $x$ 被视为最重要的容器时，机器人们最多能够将多少零件放入容器中。

inputFormat:
本题有多组数据。第一行给出一个整数 $t$，表示数据的组数。

每组输入数据的第一行给出两个整数 $n$ 和 $m$，分别表示容器和机器人的数量。

接下来一行给出 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示容器的容量。

接下来的 $m$ 行中的每一行都包含四个整数 $l_j，r_j，c_j，t_j$，表示机器人的工作范围、刚开始携带的零件数量和机器人类型。

outputFormat: 对于每组输入数据，输出 $n$ 个整数，表示对于从 $1$ 到 $n$ 的所有 $x$ 的问题的答案。


title: 「KDOI-10」商店砍价

background:
[English Statement](https://www.luogu.com.cn/problem/T514759). You must submit your code at the Chinese version of the statement.

您可以点击 [这里](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/3jbtilzv) 下载本场比赛的选手文件。

You can click [here](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/5fzhd8sk) to download all tasks and examples of the contest.

密码 / Password：`rAnHoUyaSuoBaoMimaNijuEdefAngsHa2)2$1)0(2@0!`

**本场比赛所有题目从标准输入读入数据，输出到标准输出。**

description:
有一个正整数 $n$，保证其只由数字 $1\sim 9$ 构成。

你可以做任意多次如下操作：

- 选择 $n$ 的一个数位 $x$，花费 $v_x$ 的代价删除它，注意，此时 $n$ 的数位个数会减少 $1$，$n$ 的值也会发生相应的变化；
- 或者，花费 $n$ 的代价把剩余的所有数位删除。

求把整个数删除的最小代价。

inputFormat:
从标准输入读入数据。

**本题有多组测试数据。**

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

- 第一行一个正整数 $n$，表示这个数的初始值。
- 第二行九个正整数 $v_1,v_2,\dots,v_9$，表示删除每个数位的代价。

outputFormat:
输出到标准输出。

对于每组测试数据：

- 输出一行一个正整数，表示最小代价。


title: 子树和

type: B

description:
给你一棵 $n$ 个结点的树，树的根结点是 $1$。

每个结点的权值都是 $1$，你需要对每个结点 $i$ 求出 $i$ 的子树和，也就是子树中有多少个结点。

inputFormat:
第一行一个数 $n$ 表示树的结点数。

之后 $n-1$ 行，第 $i$ 行输入一个数 $f_{i+1}$ 表示 $i+1$ 点的父亲是 $f_{i+1}$，保证 $f_{i+1}<i+1$。

outputFormat: 输出 $n$ 行，第 $i$ 行一个数表示 $i$ 点的子树和。


title: 「MXOI Round 2」酒店

description:
小 C 开了一家酒店，叫做 CC Hotel。

一天，CC Hotel 来了 $n$ 位客人。小 C 需要把他们都安排在酒店的某一层中。每个房间中只能安排一位客人。

这一层共有 $m$ 间房间，这 $m$ 间房间都是空的，且这 $m$ 间房间形成了一个环形，即对于所有的 $1 \le x \le m$，都有第 $x$ 间房间与第 $((x \bmod m)+1)$ 间房间相邻，第 $((x \bmod m)+1)$ 间房间与第 $x$ 间房间相邻，其中 $x \bmod m$ 表示 $x$ 除以 $m$ 得到的余数。

这 $n$ 位客人都十分挑剔，他们希望与自己的房间相邻的房间中没有人。对于某一位客人，若与他的房间相邻的房间中，有 $k$ 间房间有人，则这位客人会产生 $k$ 点愤怒值。

你需要帮助小 C 安排房间，使得所有客人的愤怒值之和最小，并输出所有客人的愤怒值之和的最小值。

inputFormat: 两个整数 $n,m$。

outputFormat: 一个整数，表示所有客人的愤怒值之和的最小值。

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

对于这 $5$ 间房间，其中一组满足条件的安排方案为：不住人、住人、住人、不住人、住人。

可以证明所有客人的愤怒值之和的最小值为 $2$。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le n \le 100$，$3 \le m \le 100$，保证 $n \le m$。

|测试点编号|特殊性质|
|:---:|:---:|
|$1\sim3$|保证 $2n\le m$|
|$4\sim6$|保证 $m=n+1$|
|$7\sim10$|无|


title: 「MXOI Round 1」方格

description:
小 C 和方格是好朋友。

小 C 有一个 $n$ 行 $m$ 列的方格图，每个方格中都有一个数字，其中第 $i$ 行第 $j$ 列的方格中的数字为 $a_{i,j}$。

我们定义，在这个方格图中，两个不同的方格不相邻，当且仅当这两个方格**没有公共边**。

小 C 认为，两个不同的方格互为好朋友，当且仅当这两个方格**不相邻**且**这两个方格中的数字相同**。

小 C 想让你帮忙求出，所有方格的好朋友的数量之和是多少。

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

接下来 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个整数表示 $a_{i,j}$。

outputFormat: 一个整数，表示所有方格的好朋友的数量之和。

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

第 $1$ 行第 $1$ 列的方格共有 $3$ 个好朋友，第 $1$ 行第 $2$ 列的方格共有 $2$ 个好朋友，第 $1$ 行第 $3$ 列的方格共有 $1$ 个好朋友，第 $1$ 行第 $4$ 列的方格共有 $0$ 个好朋友；

第 $2$ 行第 $1$ 列的方格共有 $1$ 个好朋友，第 $2$ 行第 $2$ 列的方格共有 $2$ 个好朋友，第 $2$ 行第 $3$ 列的方格共有 $1$ 个好朋友，第 $2$ 行第 $4$ 列的方格共有 $1$ 个好朋友；

第 $3$ 行第 $1$ 列的方格共有 $1$ 个好朋友，第 $3$ 行第 $2$ 列的方格共有 $3$ 个好朋友，第 $3$ 行第 $3$ 列的方格共有 $1$ 个好朋友，第 $3$ 行第 $4$ 列的方格共有 $4$ 个好朋友；

所有方格的好朋友数量之和为 $20$。

#### 【样例 #2】

见附加文件中的 `square/square2.in` 与 `square/square2.ans`。

该样例满足测试点 $1$ 的限制。

#### 【样例 #3】

见附加文件中的 `square/square3.in` 与 `square/square3.ans`。

该样例满足测试点 $4$ 的限制。

#### 【样例 #4】

见附加文件中的 `square/square4.in` 与 `square/square4.ans`。

该样例满足测试点 $6$ 的限制。

#### 【样例 #5】

见附加文件中的 `square/square5.in` 与 `square/square5.ans`。

该样例满足测试点 $10$ 的限制。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le n,m \le 2000$，$1 \le a_{i,j} \le 9$。

|测试点编号|$n,m \le$|$a_{i,j} \le$|特殊性质|
|:---:|:---:|:---:|:---:|
|$1\sim3$|$80$|$9$|否|
|$4\sim5$|$2000$|$1$|否|
|$6\sim7$|$2000$|$9$|是|
|$8\sim10$|$2000$|$9$|否|

特殊性质：保证任意两个相邻的方格中的数不相等。


title: 「MXOI Round 1」城市

description:
小 C 是 F 国的总统，尽管这个国家仅存在于网络游戏中，但他确实是这个国家的总统。

F 国由 $n$ 个城市构成，这 $n$ 个城市之间由 $n-1$ 条双向道路互相连接。保证从任意一个城市出发，都能通过这 $n-1$ 条双向道路，到达任意一个城市。

当然，通过这些双向道路是要收费的。通过第 $i$ 条双向道路，需要花费 $c_i$ 元。我们称 $c_i$ 为第 $i$ 条双向道路的费用。

我们定义 $cost(x,y)$ 表示从城市 $x$ 到城市 $y$ 的简单路径上，所有经过的双向道路的费用之和。特殊地，当 $x=y$ 时，$cost(x,y)=0$。

为了促进 F 国发展，小 C 新建了一个城市 $n+1$。现在他需要再新建一条双向道路，使得城市 $n+1$ 也可以通过这 $n$ 条双向道路到达任意一个城市。

他共有 $q$ 个新建道路的方案，每个方案会给定两个参数 $k_i,w_i$；对于每一个方案，你需要求出在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和，即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$。

由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。

**方案之间相互独立**，也就是说所有方案不会影响现有的道路，这些方案不会真正被施行。

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

接下来 $n-1$ 行，第 $i$ 行三个整数 $u_i,v_i,c_i$，表示存在一条连接城市 $u_i$ 和城市 $v_i$ 的双向道路，其费用为 $c_i$。

接下来 $q$ 行，第 $i$ 行两个整数 $k_i,w_i$，表示一个新建道路的方案。

outputFormat: 共 $q$ 行，每行一个整数，第 $i$ 行的整数表示在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和对 $998244353$ 取模的结果，即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j) \bmod 998244353$。

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

在新建一条连接城市 $1$ 和城市 $5$ 且费用为 $2$ 的双向道路后，F 国的道路如下图所示：

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

例如，此时 $cost(4,5)=9$，$cost(1,3)=5$。

容易求得此时 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=100$。

#### 【样例 #3】

见附加文件中的 `city/city3.in` 与 `city/city3.ans`。

该样例满足测试点 $4$ 的限制。

#### 【样例 #4】

见附加文件中的 `city/city4.in` 与 `city/city4.ans`。

该样例满足测试点 $11$ 的限制。

#### 【样例 #5】

见附加文件中的 `city/city5.in` 与 `city/city5.ans`。

该样例满足测试点 $14$ 的限制。

#### 【样例 #6】

见附加文件中的 `city/city6.in` 与 `city/city6.ans`。

该样例满足测试点 $20$ 的限制。

#### 【数据范围】

对于 $100\%$ 的数据，$2 \le n \le 2\times10^5$，$1 \le q \le 2\times10^5$，$1 \le u_i,v_i,k_i \le n$，$1 \le c_i,w_i \le 10^6$，保证从任意一个城市出发，都能通过原本存在的 $n-1$ 条双向道路，到达任意一个城市。

|测试点编号|$n \le$|$q \le$|特殊性质|
|:---:|:---:|:---:|:---:|
|$1\sim3$|$80$|$80$|无|
|$4\sim7$|$5000$|$5000$|无|
|$8\sim10$|$5000$|$2\times10^5$|无|
|$11\sim13$|$2\times10^5$|$2\times10^5$|A|
|$14\sim16$|$2\times10^5$|$2\times10^5$|B|
|$17\sim20$|$2\times10^5$|$2\times10^5$|无|

特殊性质 A：保证对于所有的 $1 \le i \lt n$，都有 $u_i=i,v_i=i+1$。

特殊性质 B：保证对于所有的 $1 \le i \le q$，都有 $k_i=1$。


title: [ROI 2023 Day 1] 监控

background:
翻译自 [ROI 2023 D1T1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf)。

商场大楼的安全由视频监控系统提供保障。

安保人员的电脑上有一个程序，该程序在屏幕上显示出多个摄像头的视频。该程序的工作原理如下：

屏幕上显示一个由 $h$ 行 $w$ 列组成的矩形网格。每个单元格可以为空，也可以显示来自某个摄像头的图像。为了控制程序中图像的位置，安保人员可以使用“左”、“右”、“上”和“下”按钮。

- 按下“左”按钮会将每个单元格中的图像向左移动到其左边的单元格。最左边一行的图像会被移动到最右边一行的对应单元格中。
- 按下“右”按钮会将每个单元格中的图像向右移动到其右边的单元格。最右边一行的图像会被移动到最左边一行的对应单元格中。
- 按下“上”按钮会将每个单元格中的图像向上移动到其上方的单元格。最上面一行的图像会被移动到最下面一行的对应单元格中。
- 按下“下”按钮会将每个单元格中的图像向下移动到其下方的单元格。最下面一行的图像会被移动到最上面一行的对应单元格中。

网格的行由上至下编号，列由左至右编号。$(r, c)$ 表示第 $r$ 行第 $c$ 列的单元格。

下面是一个有 $3$ 行 $4$ 列和三个包含图像的单元格的网格示例，其坐标分别为 $(1, 1),(2, 4),(3, 3)$，还显示了按下四个按钮后图像的新位置。

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

description:
安保人员希望屏幕上显示图像的单元格尽可能紧凑。图像的紧凑性可以用网格中包含所有显示的图像所需的最小矩形的面积来衡量。通过按下按钮可以改变图像的紧凑性。例如，下图刚开始的图像布局紧凑性为 $12$，按下一次“右”按钮和一次“上”按钮后，图像的紧凑性变为 $4$。

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

给定一个包含 $k$ 个图像的网格，计算通过使用“左”、“右”、“上”和“下”按钮可以达到的最小紧凑性，并计算达到最小紧凑性所需的最小按钮点击次数。

inputFormat:
第一行输入三个整数 $h,w,k$，分别表示网格的尺寸和包含图像的单元格数量（$1 \le h, w \le 10^9;1 \le k \le 100,000$）。

接下来的 $k$ 行中，每行包含两个整数 $r_i$ 和 $c_i$，表示包含图像的单元格的坐标（$1 \le r_i \le h；1 \le c_i \le w$）。保证所有 $k个$ 单元格坐标均不相同。

outputFormat: 输出两个整数，分别表示使用按钮所能达到的最小图像紧凑性和实现该紧凑性所需的最小按钮点击次数。


title: [ROI 2023 Day 1] 解密

background:
**[本题目前可能无法正常在所有数据范围评测](https://www.luogu.com.cn/paste/vsbuov70)**。

翻译自 [ROI 2023 D1T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf)。

这是一道**通信题**。洛谷无法实现通信，所以这道题会使用**函数交互**的形式进行评测。

**不要使用 `C++14 (GCC 9)` 语言提交**。

Alesya 和 Boris 在计算机课上学习密码学。他们决定发明自己的一种加密消息的方法——BASE23（Boris-Alesya Super Encoding 2023）。

Alesya 从 $1$ 到 $n$ 选择了 $k$ 个不同的整数，并将得到的集合称为 $T$。

Alesya 想要以加密形式将集合 $T$ 作为消息传递给 Boris。为此，根据集合 $T$，Alesya 将构建另一个集合 $R$，并将其传递给 Boris，该集合也由整数组成，范围在 $1$ 到 $n$ 之间。

Alesya 和 Boris 不希望加密后的消息大小发生变化（不像 BASE64 一样密文比明文长约 $\frac13$），因此 $R$ 也必须恰好包含 $k$ 个数字。而且，他们认为如果 $T$ 和 $R$ 至少包含一个相同的数，则加密将不够可靠。因此，不应该存在一个既属于 $T$ 又属于 $R$ 的数字，即 $T \cap R = \varnothing$。保证 $k\le \frac{n}{2}$，因此始终可以根据集合 $T$ 构建至少一个集合 $R$。

当 Boris 收到加密消息 $R$ 时，他将需要对其进行解密并获得原始消息 $T$。

description:
帮助 Alesya 和 Boris 设计和实现 BASE23 的加密和解密算法。

在本题中，你的程序需要实现下面两个函数（**不需要编写 main 函数**）：

```cpp
std::vector<int> Encode(int n, int k, std::vector<int> T){
	// 加密过程
	return R;
}
std::vector<int> Decode(int n, int k, std::vector<int> R){
	// 解密过程
	return T;
}
```

你的 `Encode` 函数将扮演 Alesya 的角色，对数组进行加密。而 `Decode` 函数则将扮演 Boris 的角色，通过解密来得到原来的数组。**$T$ 和 $R$ 都按照递增顺序排列**。

刚开始，交互库会根据该数据点的数据调用你编写的 `Encode` 函数，根据它的返回值判断该加密算法是否合法。接着，交互库调用 `Decode` 函数，判断它的返回值是否与原来的数据相同。如果相同，则认为这一份 BASE23 加解密代码是正确的。

交互库会多次调用这两个函数，对应了原题中有多组数据。交互库会先将每组数据的 $T$ 全部加密，接着再按随机顺序把它们解密。具体的数据范围限制见“说明/提示”部分。

inputFormat: 使用函数交互，程序不需要进行输入。

outputFormat: 使用函数交互，程序不需要进行输出。

hint:
交互库调用两个函数的次数（即数据组数）都不超过 $300000$。对于每一组数据，$2\le n\le 10^9,1\le k\le300000,k\le\frac n2$。对于每一个测试点，$\sum k\le300000$。

原题的加、解密时间限制均为 $1\text{s}$，空间限制均为 $512\text{MB}$，不过由于在洛谷实现通信题的方式特殊，本题由特殊的时空限制。（目前的时空限制可能无法通过本题 qwq）

如果你在本题莫名 CE，你可以尝试换一个语言提交。

当你 UKE 时，查看你的错误提示。如果提示中含有“timeout”，应该是超时了。

交互库编写：@[cff_0102](/user/542457)。


title: 四暗刻单骑

description:
Alice 和 Bob 很喜欢打麻将。他们在对麻将规则熟悉后，开始对「四暗刻单骑」感兴趣。而在这局游戏中，Alice 和 Bob 都已经集齐了四暗刻，处于听牌状态并准备「四暗刻单骑」，于是我们将这样的局面简化如下：

- 一张麻将牌可以用一个范围在 $[1, k]$ 内的正整数表示，数字相同的牌相同，数字不同的牌不相同。
- Alice 和 Bob 手中各有 $1$ 张牌作为手牌。两人轮流进行摸牌，每次摸牌的玩家会得到一张牌堆顶部的牌，Alice 先进行。摸牌后会有 $2$ 张手牌，此时需要选择一张牌打出。打出的牌双方可见。
- 当摸牌时两张手牌相同时，或当前对方打出的牌和自己目前手牌相同时，该玩家「和牌」并获胜，游戏结束。

若牌摸完后无玩家「和牌」，则判为「荒牌流局」，此时判定两位玩家平局。

现在 Alice 和 Bob 都绝顶聪明，并且已经得知了牌堆顶部的所有牌，以及对方手牌。他们都希望自己可以「和牌」并获胜，若自己无法「和牌」就会尽可能阻止对方「和牌」。

你现在拿到了 $n$ 张麻将牌组成的 $a$ 数组，下标依次为 $1\dots n$。现在有 $m$ 次询问，每次会给定 $x, y, l, r$ 表示：若目前 Alice 手牌为 $x$，Bob 手牌为 $y$，且 **按顺序** 取出 $a$ 中下标为 $[l, r]$ 的所有牌作为游戏牌堆，其中牌 $a_l$ 位于牌堆顶部，Alice 和 Bob 按要求进行游戏，最后结局如何。

询问之间相互独立。特别地，**保证 $l$ 为奇数**。

inputFormat:
从标准输入中读入数据。

第一行三个正整数 $n, m, k$。

接下来一行 $n$ 个正整数，依次表示 $a_1, a_2 \dots a_n$。

接下来 $m$ 行，每行四个正整数 $x,y,l,r$，表示一次询问。

outputFormat:
输出到标准输出。

对于每次询问，输出一行一个字符：如果 Alice 获胜，输出 `A`；如果 Bob 获胜，输出 `B`；如果平局，输出 `D`。


title: [ROI 2023 Day 1] 峰值

background:
翻译自 [ROI 2023 D1T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf)。

如果对于所有 $1 \le j < i$，都有 $a_j < a_i$，则称 $a_i$ 为峰值。

如果对于所有 $1 \le j < i$，都有 $a_j > a_i$，则称 $a_i$ 为反峰值。

description: 给定大小为 $n$ 的排列 $p_1,p_2,\dots,p_n$。需要将其分为两个非空子序列 $q$ 和 $r$。每个元素 $p$ 必须恰好被分到一个子序列中。你需要最大化 $q$ 中的峰值数量和 $r$ 中的反峰值数量之和。

inputFormat:
每个测试点由多组数据组成。第一行包含一个整数 $t(1 \le t \le 100,000)$，表示数据组数。接下来的 $2t$ 行，每两行是一组数据。

每组数据的第一行包含一个整数 $n(2 \le n \le 200,000)$，表示排列的大小。

每个输入数据集的第二行包含 $n$ 个整数 $p_1,p_2,\dots,p_n$，表示原始排列。保证 $p$ 中的每个数字都恰好出现一次。

每组数据中 $n$ 的总和不超过 $200,000$。

outputFormat: 对于每组数据，输出一个整数，表示将 $p$ 拆分后，$q$ 中的峰值数量和 $r$ 中的反峰值数量之和的最大值。


title: [ROI 2023 Day 1] Ultra mex

background:
翻译自 [ROI 2023 D1T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf)。

假设 $A$ 是一个非负整数的集合。将 $A$ 中不存在的最小非负整数记为 $\operatorname{mex}(A)$。例如，$\operatorname{mex}(\{0, 1, 2, 4, 5, 9\}) = 3$。

我们还定义了一种在含有 $0$ 的集合 $A$ 上的操作，称为 $\operatorname{Ultra}$。假设 $m = \operatorname{mex}(A)$，因为 $0\in A$，显然 $m > 0$。按照以下方法构建新的集合 $\operatorname{Ultra}(A)$：对 $A$ 中的每个元素异或 $m-1$。例如，$\operatorname{Ultra}(\{0, 1, 2, 4, 5, 9\}) = \{0\oplus2, 1\oplus2, 2\oplus2, 4\oplus2, 5\oplus2, 9\oplus2\} = \{2, 3, 0, 6, 7, 11\} = \{0, 2, 3, 6, 7, 11\}$。

不难发现，如果集合 $A$ 包含 $0$，则集合 $\operatorname{Ultra}(A)$ 也包含 $0$。

我们选择由 $0$ 到 $2^{k-1}$ 之间的整数组成的集合 $A_0$，且 $0$ 在 $A_0$ 中。考虑以下序列：

- $m_0 = \operatorname{mex}(A_0),A_1 = \operatorname{Ultra}(A_0)$。
- $m_1 = \operatorname{mex}(A_1),A_2 = \operatorname{Ultra}(A_1)$。
- $\dots$
- $m_i = \operatorname{mex}(A_i),A_{i+1} = \operatorname{Ultra}(A_i)$。

如果从某个数 $l$ 开始，数字 $m_i$ 不再变化，也就是说，对于所有 $i \ge l$，$m_i = m_l$，则称集合 $A_0$ 是 mex-stable 的，将 $m_l$ 称为集合 $A_0$ 的 mex-limit。

description:
给定整数 $k,n,p$，计算满足以下条件的集合 $A_0$ 的数量：

- 它包含从 $0$ 到 $2^{k-1}$ 的 $n$ 个不同整数（其中 $0$ 必须包含在 $A_0$ 中）；
- 它是 mex-stable 的；
- 它的 mex-limit 等于 $p$。

由于答案可能很大，输出答案对 $M$ 取模后的结果。保证 $M - 1$ 能被 $2^{18}$（$262144$）整除。

inputFormat:
第一行包含一个整数 $M$，表示要对其取模的模数（$3 \le M \le 10^9$ 且 $M - 1$ 可被 $2^{18}$ 整除）（所以 $M$ 实际上不可能小于 $2^{18}+1$）。保证 $M$ 是一个质数。

第二行包含一个整数 $t$，表示输入数据的组数（$1 \le t \le 100000$）。

对于每组输入数据，包含三个整数 $k,n,p$（$1 \le k \le 17$，$ 1 \le n, p \le 2^k$）。

outputFormat: 对于每组输入数据，输出一行，包含一个整数，表示满足条件的集合 $A$ 的数量对 $M$ 取模后的结果。


title: [ROI 2023 Day 2] 蜗牛与富士山

background:
翻译自 [ROI 2023 D2T1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day2.pdf)。

在爬上富士山的山顶后，蜗牛想要下山。在山坡上有一个类似二叉树的小径。

该树包含 $n$ 个被 $n-1$ 个小径连接的节点。树的根位于山顶。一些节点处的小径到头了，它们是树的叶子节点。除了叶子节点外，每个节点向下山坡延伸两条小径，其中一条向左，另一条向右。

蜗牛希望从根部开始沿着树向下爬并到达其中一个叶子节点。在路径上，蜗牛可以选择两个方向之一进行进一步下降：向左或向右。

刚开始在山顶，蜗牛可以往任意方向（左或右）开始下降。在每个后续节点中，如果它选择与前一个节点选择的方向不同的方向，则它要进行转弯。

由于蜗牛转弯不太方便，所以在从根到叶子的整个路径上，蜗牛最多只准备转弯 $k$ 次。

description: 将树的节点从 $1$ 到 $n$ 编号，其中根节点编号为 $1$。给定 $q$ 个查询。每个查询给出一个节点 $u_i$，要求找出蜗牛在从根开始下降时，最多转弯 $k$ 次，且通过节点 $u_i$ 的路径上能到达的叶子节点数量。

inputFormat:
第一行给出三个整数 $n,k,q$，分别表示树中节点的数量、蜗牛准备转动的最大次数，以及查询的数量。

接下来的 $n$ 行描述了树的结构。第 $i$ 行的第一个整数 $t_i$ 表示节点 $i$ 的小径（子树）数量（$t_i = 0$ 或 $2$）。如果 $t_i = 2$，则在同一行中给出两个整数 $l_i$ 和 $r_i$，分别表示从节点 $i$ 出发的左侧和右侧小径连接到的节点编号（$1 \le l_i,r_i \le n$）。保证输入符合要求。

接下来的 $q$ 行给出了查询。第 $i$ 行给出一个整数 $u_i$，表示蜗牛路径经过的节点编号（$1 \le u_i \le n$）。

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

hint:
样例的树长这样。

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

第一次询问（灰色为可到达的叶子节点，虚线为不可到达的节点）：

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

第二次询问：

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

第三次询问：

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

第四次询问（因为最多转一次弯，所以并没有合法的路线，故输出 $0$）：

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

对于 $100\%$ 的数据，$3 \le n \le 200000$，$0 \le k \le n$，$1 \le q \le 200000$。

| Subtask | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $11$ | $n\le500,q\le500$，所有 $u_i$ 均为叶子节点 |
| $2$ | $12$ | $n\le500,q\le500$ |
| $3$ | $10$ | $k=n$ |
| $4$ | $14$ | $k=0$ |
| $5$ | $19$ | 所有 $u_i$ 均为叶子节点 |
| $6$ | $34$ | 无 |


title: [语言月赛 202308] 电脑中了满屏粉兔病毒

description:
小 F 的电脑屏幕可以被划分为 $r$ 行 $c$ 列的网格，第 $i$ 行第 $j$ 列的网格，可以用 $(i,j)$ 来表示。

突然，有一天，小 F 的电脑中了「满屏粉兔」病毒，在电脑屏幕上，出现了 $N$ 只雄粉兔和 $M$ 只雌粉兔。

假设一只粉兔位于 $(i,j)$，若其沿上、下、左、右四个方向中的一个方向行动，可以在不经过「异性粉兔」的情况下离开屏幕范围，那么，这个方向对于该粉兔就是一条「逃跑通道」。

狡兔三窟。我们定义一只粉兔是「合格的粉兔」，当且仅当其至少有三条「逃跑通道」。

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

例如，如图所示，绿色方格代表雄粉兔，粉色方格代表雌粉兔。位于 $(2,2)$ 的雌粉兔，向上、下、左，都可以不经过雄粉兔的离开屏幕，共有三条「逃跑通道」因此，位于 $(2,2)$ 的粉兔是「合格的粉兔」。而位于 $(4,4)$ 的粉兔，仅有左、右两条「逃跑通道」，因此 $(4,4)$ 的粉兔不是「合格的粉兔」。

现在，给出屏幕上粉兔的分布情况，请问，一共有多少只「合格的粉兔」？

inputFormat:
输入共 $r+1$ 行。

输入的第一行为四个整数 $r,c,N,M$。

接下来 $r$ 行，每行 $c$ 个字符，第 $i$ 行第 $j$ 个字符 $k_{i,j}$ 描述了网格 $(i,j)$ 的情况：

- 若 $k_{i,j}$ 为 `.`，则代表 $(i,j)$ 没有粉兔。
- 若 $k_{i,j}$ 为 `F`，则代表 $(i,j)$ 为雌粉兔。
- 若 $k_{i,j}$ 为 `M`，则代表 $(i,j)$ 为雄粉兔。

outputFormat: 输出一行一个整数，代表「合格的粉兔」的只数。

hint:
- 对于 $30\%$ 的测试数据，$1 \le r,c \le 30$；
- 对于 $100\%$ 的测试数据，$1 \le r,c \le 500$，$0 \le N,M \le r \cdot c$，$k_{i,j}$ 为 `.`、`F`、`M` 中的一个。


title: 『GROI-R2』 不空白的画布

description:
我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。

但是现在画布已经不再空白，因为画布上已经有了当下的风景。我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1,k]$ 范围内的正整数表示。

坦尼尔还要画他已经翻了的茶杯。每一次作画，他可以选定画布上的任意一个位置，然后将这个位置上的颜色涂改成 $[1,k]$ 范围内的任意正整数。

最后，我们都知道这幅画是有记忆的。定义画上留下的记忆碎片数量为画上的**相同颜色连续块个数**。现在坦尼尔想知道，如果给定他作画的次数**上限**，那么画上的记忆碎片个数**最多**有多少。

**形式化题面**

你有连续的 $n$ 个方格，每个方格上有一个初始颜色 $c_i$，且保证 $1\le c_i \le k$。

你可以操作**至多** $m$ 次，每个操作为改变某个方格颜色，要求改变后的颜色范围仍在 $[1,k]$ 内。

我们称一个**极长相同颜色连续段**为一块，要求求出经过至多 $m$ 次操作后的**最多**块数。

inputFormat:
本题有多组测试数据。

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

对于每组测试数据，第一行输入三个正整数 $n,m,k$，表示画布的长度，坦尼尔作画的次数上限和颜色的取值范围。

第二行输入一个长度为 $n$ 的整数序列 $c$，表示画布上每个位置的初始颜色。

outputFormat: 对于每组测试数据，输出一行一个正整数，表示记忆碎片最多有多少个。


title: 生成树

background:
> 我们是未成熟的斗士 现在绝不认输
>
> 我们是未成熟的梦想家 现在绝不哭泣

description:
现给定一个无向完全图 $G(V,E)$ 和一个长度为 $|V|$ 的权值数组 $a$．$a_i$ 表示编号为 $i$ 的节点的权值．

定义一条边 $e(u,v)$ 的边值为 $val(e)$，满足 $val(e)=a_u\oplus a_v$，也就是边连接的两个节点的权值的异或和；定义 $G$ 的一个生成树 $T(V,E_t)$ 的权值为 $Val(T)$，满足 $Val(T)=\sum_{e\in E_t}val(e)$，也就是树上边的边权和．

您需要求出 $\sum_{T}Val(T)$．即 $G$ 中所有不同生成树的权值的和．

我们认为两棵生成树是不同的，当且仅当两棵树的边集 $E_t$ 不完全相同，即至少存在一条边，满足其仅属于两棵生成树中的其中一棵．

inputFormat:
包括两行．

第一行是一个整数 $n$，表示 $|V|$，即节点个数．

第二行是 $n$ 个整数，依次为 $a_1\sim a_n$．

outputFormat: 一行一个整数．表示你的答案对 $998244353$ 取模．


title: [ROI 2023 Day 2] 会议

background:
翻译自 [ROI 2023 D2T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day2.pdf)。

秘鲁科学和教育协会正在组织一次会议，计划进行 $n$ 个活动，编号从 $1$ 到 $n$。$l_i$ 和 $r_i$ 分别表示第 $i$ 个活动的开始和结束时间。由于某些活动可能冲突，一个人不一定能参加所有会议活动。如果 $r_i < l_j$ 或者 $r_j < l_i$，则认为活动 $i$ 和 $j$ 不冲突。

如果在同一个集合中任意两个不同的活动不冲突，则称该集合为相互兼容的。假设会议中最大相互兼容集合的大小为 $m$。则将会议的饱和度定义为 $\frac{n}{m}$。由于资金减少，会议组织者决定减少一半数量的会议活动。同时，他们希望会议的饱和度保持不变，因此在减少的会议活动中，最大相互兼容集合的大小也必须减少一半。

本题保证在原始会议计划中，会议活动的数量 $n$ 和最大兼容集合的大小 $m$ 恰好都是偶数。

description: 请帮助组织者选择 $\frac{n}{2}$ 个计划中的会议活动，以使所选活动的最大兼容集合的大小为 $\frac{m}{2}$。

inputFormat:
每个测试点包含多组数据。

第一行包含一个整数 $t$，即输入数据集的数量（$1 \le t \le 50000$）。

每组数据的第一行包含一个整数 $n$，即原始计划中的活动数量（$2 \le n \le 100000$，$n$ 是偶数）。

在接下来的 $n$ 行中，对于每个数据集的描述，给出了活动的描述。每行包含两个整数 $l_i$ 和 $r_i$，分别是第 $i$ 个活动的开始和结束时间（$1 \le l_i < r_i \le 10^9$）。

保证原始计划的最大兼容集合的大小 $m$ 是偶数，且 $\sum n\le100000$。

outputFormat: 对于每组数据，在一行中输出 $\frac{n}{2}$ 个不同活动的编号，即保留下来的应该进行的活动编号。如果有多个合适的答案，可以输出任意一个。所选择的活动的最大相互兼容集合的大小应为 $\frac{m}{2}$。

hint:
样例解释：

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

上图是第一组输入数据中的初始活动集合。其中一种可能的最大相互兼容集合用粗虚线标出。

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

上图是第一组输入数据的答案的活动集合。其中一种可能的最大相互兼容集合用粗虚线标出。

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

第二组输入数据初始时的活动集合。

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

第二组输入数据答案中的活动集合。

设 $N=\sum n$。我们称活动 $i$ 完全覆盖活动 $j$，当且仅当 $l_i\le l_j<r_j\le r_i$。

| Subtask | 分值 | $N\le$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $5$ | $100000$ | 任意两项会议活动不冲突 |
| $2$ | $20$ | $20$ |  |
| $3$ | $7$ | $30$ |  |
| $4$ | $15$ | $500$ | 对于任意两项活动 $i$ 和 $j$，它们要么不冲突，要么其中一项完全覆盖另一项活动；且有一项活动完全覆盖其它所有活动 |
| $5$ | $15$ | $100000$ | 对于任意两项活动 $i$ 和 $j$，它们要么不冲突，要么其中一项完全覆盖另一项活动 |
| $6$ | $13$ | $500$ |  |
| $7$ | $13$ | $5000$ |  |
| $8$ | $12$ | $100000$ |  |


title: [ROI 2023 Day 2] 陶陶装苹果

background:
翻译自 [ROI 2023 D2T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day2.pdf)。

淘淘有 $n$ 个整数重量的苹果，它们分别为 $w_1,w_2,\dots,w_n$，这些苹果放在桌子上，同时有两个容量足够大的篮子。

淘淘选择一个整数 $k$，他可以将每个重量 $w_i \le k$ 的苹果放入其中一个篮子，也可以将其留在桌子上。重量大于 $k$ 的苹果将始终留在桌子上。

如果淘淘能够将重量不超过 $k$ 的苹果放入篮子中，使得第一个篮子中苹果的重量之和等于 $x$，而第二个篮子中苹果的重量之和等于 $y$，则称 $(x, y)$ 是 $k$ 的可达到对。如果对于所有满足 $0 \le x \le a$ 和 $0 \le y \le b$ 的 $x$ 和 $y$，$(x, y)$ 都是 $k$ 可达到的，则称 $(a, b)$ 是 $k-\!$ 完美的。

description: 淘淘会询问你 $q$ 次，请你判断对于每个 $(k,a,b)$ 三元组，$(a, b)$ 是否是 $k-\!$ 完美的。

inputFormat:
第一行给出两个整数 $n$ 和 $q$，表示淘淘拥有的苹果数量和要处理的查询数量（$1 \le n, q \le 300,000$）。

第二行给出 $n$ 个整数 $w_1,w_2,\dots,w_n$，表示陶陶拥有的苹果的重量（$1 \le w_i \le 10^{12}$）。

第三行给出一个整数 $z$，在接下来的输入中会用到（$0 \le z \le 10^6$）。

接下来的 $q$ 行给出查询的描述。查询编号从 $1$ 到 $q$。每行包含三个整数 $j,c,d$（$0 \le j, c, d \le 10^{18}$），表示这个查询中的 $k = j - v \times z,a = c - v \times z,b = d - v \times z$，其中 $v$ 是在这个查询前答案为 `Yes` 的询问的数量。保证 $k,a,b \ge 0$。

在本题中，大多数测试点的 $z$ 都等于 $0$，此时 $k,a,b$ 的值分别等于 $j,c,d$。

outputFormat: 对于每个查询，如果在该查询中 $(a, b)$ 对是 $k-\!$ 完美的，则输出 `Yes`，否则输出 `No`。


title: [ROI 2023 Day 2] 生产计划

background:
翻译自 [ROI 2023 D2T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day2.pdf)。

**这是一道 IO 交互题**。

某个国家准备制定汽车的生产计划。

该国总共有 $n$ 个城市，每个城市中有一个工厂，它们要参与汽车的生产。第 $i$ 个城市的工厂可以雇佣 $l_i$ 到 $r_i$ 个人。

一些城市之间通过双向道路相连，且道路网络呈树状结构。因此，如果要从一个城市到另一个城市，在不重复经过同一个城市的情况下，只有一种路径。

生产计划被定义为一个整数序列 $[a_1, a_2, \dots , a_n]$，其中 $a_i$ 表示在第 $i$ 个工厂工作的人数，满足 $l_i\le a_i\le r_i$。在制定生产计划后，一些工厂将被选为装配工厂，这些工厂负责装配汽车，而其它工厂则负责生产零部件。如果没有两个装配工厂所在的城市被一条道路直接连接，那么这个生产计划就是合理的。在所有可能的合理的计划中，会选择装配工厂的工人总数最大的一个计划。这个数就被称为计划 $[a_1, a_2, \dots , a_n]$ 的效率。

description:
你需要确定是否存在效率为 $v_i$ 的计划。如果存在这样的计划，则可能需要输出这样一个计划。

制定计划的过程包括两个阶段。

在第一阶段，你将获得 $v_1,v_2,\dots,v_q$ 的值。你需要确定是否存在效率为 $v_i$ 的计划，如果不存在，输出 `-1`；如果存在，输出一个非负整数 $k_i$。

对 $k$ 的定义如下：给定三个整数 $x,y,m$，定义计划 $[a_1, a_2, \dots , a_n]$ 的 $k = \bigoplus\limits^n_{j=1} ( (x\times j + y\times a_j^2) \bmod m )$，其中 $\oplus$ 为按位异或。

因为符合要求的计划可能不止一个，所以 $k_i$ 也有很多种可能，你需要输出其中一种可能的 $k_i$。

在第二阶段，某些计划的可行性将被检查。在每个查询中，你的程序会得到一个整数 $i$（$1\le i\le q$）。对于这个查询，如果不能制定效率为 $v_i$ 的计划，你需要输出 `-1`；否则，你需要输出 $n$ 个整数 $a_1,a_2,\dots,a_n$（$l_i\le a_i\le r_i$），表示一个制定的计划。这个计划计算出来的 $k$ 值应该等于你先前输出的 $k_i$，效率应该等于 $v_i$。

在程序输出每个 $k$ 之前，无法知道哪些计划会被检查。因此，你需要保证在第一阶段中输出的 $k_i$ 是正确的。

inputFormat:
本题多测，第一行输入一个整数 $t$（$1\le t\le10^4$），表示数据组数。

在每组数据中：

第一行包含两个整数 $n,q$（$2 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$），分别表示城市的数量和要制定的计划的数量。

第二行包含三个整数 $x,y,m$（$11 \le m \le 2^{30}$，$0 \le x,y < m$），即计算 $k$ 的参数。

接下来的 $n-1$ 行描述了城市之间的道路网络。在这 $n-1$ 行中，第 $i$ 行包含两个整数 $s_i,f_i$（$1 \le s_i,f_i \le n$，$s_i \ne f_i$），表示第 $i$ 条道路连接城市 $s_i$ 和 $f_i$ 的双向道路。保证这些道路能够构成一棵树。

接下来的 $n$ 行中的第 $i$ 行包含两个整数 $l_i,r_i$（$0 \le l_i \le r_i \le 10^9$），表示第 $i$ 个城市的工人数量限制。

接下来的一行包含 $q$ 个整数 $v_1,v_2,\dots,v_q$（$0 \le v_i \le \sum\limits^n_{i=1}r_i$），表示需要制定的计划的效率值。保证所有的 $v_i$ 都是不同的。

接下来，你需要输出第一部分中你需要输出的内容（具体方式见“输出格式”）。输出完成后，才可以读入第二部分的数据。

接下来若干行，每行输入一个数 $i$（$0\le i\le q$）。当 $i\ne0$ 时，$i$ 表示要检查的计划的编号。在按照输出格式的要求输出后，交互库才会继续给你下一个 $i$。当 $i=0$ 时，表示第二部分的检查结束，即这一组数据输入完成。如果这不是最后一组数据，你的程序应该立即开始读入下一组数据。

保证 $\sum n,\sum q\le2\times10^5$，且每组数据中检查计划次数 $c$ 的总和不超过 $10^4$，$\sum n\times c\le10^6$。

outputFormat:
读取完每组输入的第一部分后，需要输出 $q$ 个整数 $k_1,k_2,\dots,k_q$（$-1 \le k_i < 2^{30}$），如果 $k_i = -1$ 则表示无法制定效率值为 $v_i$ 的计划。输出后，交互库才会给你第二部分的数据。

在读入第二部分检查的计划编号 $i$（且 $i\ne0$）后，如果第 $i$ 个计划无法制定，即 $k_i=-1$ 时，则输出 `-1`。否则，需要输出 $n$ 个整数 $a_1,a_2,\dots,a_n$（$l_i \le a_i \le r_i$），表示所制定的计划。该计划的 $k$ 应等于 $k_i$，并且效率应等于 $v_i$。

IO 交互题在输出后应刷新缓冲区。

如果在 C++ 中使用了 `cout << ... << endl`，在 Java 中使用了 `System.out.println`，在 Python 中使用了 `print`，在 Pascal 中使用了 `writeln`，那么输出缓冲区会自动刷新，不需要额外操作。

如果使用了其他输出方法，建议手动刷新输出缓冲区。在刷新输出缓冲区时，可以使用 C 和 C++ 中的 `fflush(stdout)`，Pascal 中的 `flush(output)`，Java 中的 `System.out.flush()`，Python 中的 `sys.stdout.flush()`。


title: 「NnOI R2-T3」Horizon Blue

description:
小 C 喜欢在画板上画画。他进行了 $ n $ 次操作，每次操作有如下三种可能：

- ```1 k b``` 代表小 C 绘制了一条解析式为 $ y=kx+b $ 的直线。
- ```2 k b``` 代表小 C 询问你直线 $ y=kx+b $ 与多少条被绘制的直线有**恰好**一个公共点。
- ```3 k b``` 代表小 C 擦除所有与直线 $ y=kx+b $ 有**至少**一个公共点的直线。

**注意：两条重合的直线有无数个交点。**

**注意：询问时重合的直线应分别计算。**

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

接下来 $n$ 行，每行三个整数 $ 1/2/3,k,b $，代表一次操作。

outputFormat: 对每次 ```2 k b``` 操作，输出满足要求的直线数量。

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

第 1 次操作，绘制直线 $ y=x $。

第 2 次操作，绘制直线 $ y=-x $。

第 3 次操作，可以发现直线 $ y=2x+1 $ 与前两条线相交。

第 4 次操作，擦掉所有 $ y=x+3 $ 相交的线，直线 $ y=-x $ 被擦掉。

第 5 次操作，$ y=2x+1 $ 显然与 $ y=x $ 相交。

第 6 次操作，$ y=x+1 $ 与 $ y=x $ 斜率相等，是平行线，不相交。

**【数据范围】**

对于 $ 100\% $ 的数据，$ 1 \le n \le 10^5 $，$ 1 \le |k| \le 10^5 $，$ 0 \le |b| \le 10^5 $。

**提示：本题开启捆绑测试。**

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c}
\textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1& n \le 5000 & 27 \r
\textsf2& \vert k\vert,\vert b\vert \le 50 & 21 \r
\textsf3& 无第\ 3\ 类操作 & 13 \r
\textsf4& 第\ i\ 次操作满足\ k=i & 14 \r
\textsf5& 无特殊限制 & 25 \r
\end{array}
$$

在赛后新添加的 hack 测试点将放入 subtask 6。

### 题目来源

| 项目 | 人员 |
|:-:|:-:|
| idea | 船酱魔王 |
| data | 船酱魔王 |
| check | EstasTonne |
| solution | 船酱魔王 |


title: 「CROI · R1」浣熊的语言

background:
$\texttt{[2023.08.17 21:44]：}$ 为防止神奇的暴力做法通过，本题时限改为 $500\ ms$。

> 他复瞑着，沙地上的文字。\
> 词句，日忆夜诵，挥翰成风；夜幕下，星罗棋布。\
> 新意，呼之欲出，似即却离；叹气里，功败垂成。\
> 她释然一笑，潇然起身，轻叩他的后背。\
> 却见流光间，熊爪翻飞；夜风中，新词真切。\
> “你做到了……”\
> 平凡的仲夏夜，深刻的文字。\
> 忆诵的努力，闪烁着星光……

description:
小浣熊 CleverRaccoon 遵循浣熊的单词遗忘曲线，从第 $1$ 天开始背单词。

一共有 $n$ 个单词，正常情况下，第 $i$ 个单词将在第 $d_i$ 天首次学习。

同时，每个单词都会安排 $k$ 次复习，对于第 $j$ 次复习有复习点 $t_j$，表示正常情况下，每个单词在**首次学习后** $t_j$ 天都会安排这个单词的复习。换言之，第 $i$ 个单词的第 $j$ 次复习时间为第 $d_i+t_j$ 天。

另外，还有 $m$ 天为特殊情况，第 $i$ 次特殊情况发生在 $s_i$ 天。小浣熊 CleverRaccoon 在当日忘记背单词了，与当日冲突的首次学习或复习时间将顺延至第二天学习或复习。
- 若某单词的首次学习时间顺延至第二天，则该单词按**顺延后**的首次学习时间安排复习。
- 若某单词的当次复习时间顺延至第二天，则**不影响**该单词的后续复习时间。
- 若多个学习或复习时间重合于一天，则当天需要进行**多次**学习或复习。

小浣熊 CleverRaccoon 想知道：学习和复习完所有单词需要的天数、每天新学单词数、每天复习单词数。

inputFormat:
第一行，三个整数 $n,m,k$，表示需背单词的总数、特殊情况的天数、每个单词均需复习的次数。

第二行，$n$ 个整数 $d_i$，表示每个单词的首次学习时间。保证 $d$ 单调不减。

第三行，$m$ 个整数 $s_i$，表示特殊情况日期。保证 $s$ 单调递增。特别地，若 $m=0$，则没有该行数据。

第四行，$k$ 个整数 $t_i$，表示所有单词的每个复习点。保证 $t$ 单调递增。

outputFormat:
第一行，一个整数，表示小浣熊 CleverRaccoon 学习和复习完所有单词需要的天数 $x$。

接下来有 $x$ 行，每行两个整数，表示每天的学习单词数量和复习单词数量。


title: [语言月赛 202308] 四个人的排名加起来没有小粉兔高

background: 众所周知，洛谷著名管理员品客瑞比特选手在 NOI2020 中以第 $51$ 名的成绩获得了金牌并进入国家集训队。这常带来一个有趣的事实：清华大学一些四人寝室四个人的 NOI 排名加起来还没有小粉兔高。

description:
又是一年 NOI 结束了。小 A，小 B，小 C 和小 D 作为正式选手，在 NOI3202排名分别是第 $a$ 名，第 $b$ 名，第 $c$ 名和第 $d$ 名。

现在，小 A，小 B，小 C 和小 D 都被保送到清华大学，并住进同一间寝室。

如果四个人的 NOI 排名之和**小于** $51$，则我们称『四个人的排名加起来没有小粉兔高』；反之，如果四个人的 NOI 排名之和**大于或等于** $51$，我们称『四个人的排名加起来不比小粉兔低』。

现在，扶苏知道了四个人的 NOI 排名，她想请你判断是否『四个人的排名加起来没有小粉兔高』。

inputFormat: 输入只有一行四个整数，依次表示四个人的 NOI 排名 $a,b,c,d$。

outputFormat:
输出一行一个字符串表示答案：
- 如果『四个人的排名加起来没有小粉兔高』，输出 `Rabbit wins`。
- 如果『四个人的排名加起来不比小粉兔低』，输出 `Rabbit lose`。

samples:
1 2 3 4
Rabbit wins

samples:
1 1 5 4
Rabbit wins

samples:
50 49 48 47
Rabbit lose

hint:
### 数据规模与约定

对全部的测试数据，保证 $1 \leq a, b, c, d \leq 50$。排名有可能相等。


title: [ROIR 2022 Day 1] 口算比赛

background:
翻译自 [ROIR 2022 D1T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day1.pdf)。

在一个规则新奇的口算比赛中，评委在黑板上写下 $n$ 个整数 $a_1, a_2, \dots , a_n$。参赛选手需要自行决定执行以下两种类型的指令：

1. 擦除第 $i$ 个数字，并将数字 $x$ 写入该位置。也就是说，如果黑板上原本写着数字 $a_1, a_2, \dots , a_n$，那么执行该指令后，数字序列将变为 $a_1, \dots , a_{i−1}, x, a_{i+1}, \dots , a_n$。
2. 将数字序列循环右移 $k$ 位。也就是说，如果黑板上原本写着数字 $a_1, a_2, \dots , a_n$，那么执行该指令后，数字序列将变为 $a_{n−k+1}, a_{n−k+2}, \dots , a_n, a_1, a_2, \dots , a_{n−k}$。

description: 每次执行完指令后，参赛选手需要将黑板上所有数字的总和报告给评委会。为了检查参赛选手的答案，评委们需要自己计算总和。

inputFormat:
第一行包含一个整数 $n$，表示初始时黑板上的数字数量。

第二行包含 $n$ 个整数，通过空格分隔，表示初始时写在黑板上的数字 $a_1, a_2, \dots , a_n$。

第三行包含一个整数 $q$，表示需要执行的指令数量。

接下来的 $q$ 行中，每行描述一条指令，格式如下：
- `1 i x`：表示参赛选手将第 $i$ 个数字替换为 $x$。
- `2 k`：表示参赛选手将数字序列循环右移 $k$ 位。

outputFormat: 输出 $q$ 行，每行包含一个整数。第 $i$ 行应该包含执行前 $i$ 条指令后黑板上所有数字的总和。

hint:
样例 $1$ 解释：

初始时，在黑板上写有数字序列：$4, 1, 2, 1, 5, 3$。

在执行第一条指令后，数字序列向右循环移动了 $3$ 位。新的数字序列为 $1, 5, 3, 4, 1, 2$。所有数字的总和为 $1 + 5 + 3 + 4 + 1 + 2 = 16$。

在执行第二条指令后，我们需要将第三个元素替换为 $10$。新的数字序列为 $1, 5, 10, 4, 1, 2$。所有数字的总和为 $1 + 5 + 10 + 4 + 1 + 2 = 23$。

在执行第三条指令后，我们需要将第四个元素替换为 $4$。由于第四个元素已经是 $4$，数字序列没有发生改变。所有数字的总和仍然是 $23$。

在执行第四条指令后，数字序列向右循环移动了 $1$ 位，变为 $2, 1, 5, 10, 4, 1$，总和不变。

最后，在执行第五条指令后，数字序列变为 $-10, 1, 5, 10, 4, 1$。最终数字序列的总和为 $-10 + 1 + 5 + 10 + 4 + 1 = 11$。

本题使用捆绑测试。

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $22$ | $n\le1000$ 且所有指令都是第一类 |
| $2$ | $17$ | $n\le1000$ 且所有第二类指令中 $k=1$ |
| $3$ | $23$ | $n\le1000$ |
| $4$ | $38$ | 无 |

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$−10^9 \le a_i \le 10^9$，$1 \le q \le 10^5$。对于第一类指令，$1 \le i \le n$。对于第二类指令，$−10^9 \le x \le 10^9$，$1 \le k < n$。


title: [ROIR 2022 Day 1] 跳跃机器人

background:
翻译自 [ROIR 2022 D1T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day1.pdf)。

某公司正在开发一种跳跃机器人。为了测试机器人，他们在一个多边形平台上设置了一个由 $n$ 个特殊平台组成的环形路线，平台从 $1$ 到 $n$ 编号。第 $i$ 个平台与 $i+1$ 个平台之间的距离为 $d_i$，最后一个平台与第一个平台之间的距离为 $d_n$（假设长度分别为 $d_1,d_2,\dots,d_n$ 的边可以组成一个 $n$ 边形）。

机器人配备了人工智能，在测试过程中学习跳得更远。在任何时刻，机器人通过一个整数 $a$ 来表示它的灵敏度。如果 $a$ 大于等于 $d_i$，机器人可以从平台 $i$ 跳到平台 $i+1$；同样地，如果 $a$ 大于等于 $d_n$，机器人可以从最后一个平台跳到第一个平台。每次跳跃后，机器人的灵敏度增加 $1$。

description: 机器人的开发人员选择一个平台作为起始平台。如果机器人可以完成 $n$ 次跳跃，回到原来的平台，他们认为实验是成功的。开发人员需要确定机器人的最小起始灵敏度是多少，并选择哪个平台作为起始平台。

inputFormat:
第一行包含一个整数 $n$。

第二行包含一个整数 $f$。

- 如果 $f = 1$，则第三行包含 $n$ 个整数 $d_1, d_2, \dots , d_n$，意义见题目背景。
- 如果 $f = 2$，则第三行包含一个整数 $m$，以及三个整数 $x,y,z$。第四行包含 $m$ 个整数 $c_1, c_2, \dots , c_m$。此时距离值 $d_i$ 根据以下公式计算：
   - 如果 $1 \le i \le m$，则 $d_i = c_i$。
   - 如果 $m + 1 \le i \le n$，则 $d_i = ((x \times d_{i−2} + y \times d_{i−1} + z) \bmod 10^9) + 1$。

outputFormat: 输出两个整数，即最小允许的起始灵敏度 $a$ 和可用于放置机器人的起始平台编号。如果有多个最小起始灵敏度对应的起始平台，可以输出任意一个。


title: 「PHOI-1」雨纷纷

background:
**形式化题面的表述已更改。**

今夜，雨纷纷……

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

description:
在 $n$ 行 $m$ 列的空地上，有一个大小为 $x$ 行 $y$ 列的伞，雨伞不可以旋转。每天向空地随机洒下 $1 \sim k$ 滴雨，已经有雨的格子不会再降下雨，有伞的格子不会被雨淋湿。

但此伞比较特殊，它完全透明，小 X 无法直接得知伞的位置。但是每天结束后，小 X 都会得知空地上每个空格的状态，即有雨滴或无雨滴。注意，小 X 只会得知格子的状态。小 X 无法得知每天在哪里降了雨。

现在小 X 想让你求出**在最好情况下**（即天数最少时）几天可以使伞的位置唯一，以及得到伞的位置后，场上至少的雨滴数量，数据保证有解。

**形式化的讲**，有一个 $n \times m$ 的矩形，你每天可以**至多**删除 $k$ 个格子。问至少需要多少天以及至少需要删除多少格子，才能使得图中完整的 $x\times y$ 的矩形唯一。

inputFormat: 一行，$5$ 个整数，分别为 $n,m,x,y,k$。

outputFormat: 一行，分别为**在最好情况下**几天可以得知伞的位置，以及得到伞的位置后，场上至少的雨滴数量，两个数据用空格隔开。


title: 树的直径

description: 给定一棵 $n$ 个结点的树，树没有边权。请求出树的直径是多少，即树上的最长路径长度是多少。

inputFormat:
第一行输入一个正整数 $n$，表示结点个数。

第二行开始，往下一共 $n-1$ 行，每一行两个正整数 $(u,v)$，表示一条边。

outputFormat: 输出一行，表示树的直径是多少。

hint: 数据保证，$1 \leq n \leq 10^5$。


title: 「PHOI-1」路虽远

background:
$update$ $on$ $2023.8.17$ $12:25$
**数据修复&加强完成，可重新提交代码。**

路虽远，行则将至。

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

description:
**请注意本题特殊的时限。**

小 X 来到了 Z 市，Z 市有 $n$ 个交通路口，$m$ 条马路。其中第 $i$ 条马路连接着第 $u_i$ 个交通路口和第 $v_i$ 个交通路口（可以从 $u_i$ 到 $v_i$，也可以从 $v_i$ 到 $u_i$），小 X 通过这条马路时要花费 $p_i$ 秒，若有限速，则通过这条马路时要花费 $q_i$ 秒。

现在，市长要在 $k$ 条马路上添加限速，然而，要在哪 $k$ 条马路上限速是小 X 自己规定的。

同时，市长会在每个交通路口处添加红绿灯。第 $i$ 个交通路口的红绿灯先亮绿灯 $x_i$ 秒，再亮黄灯 $y_i$ 秒，之后亮红灯 $z_i$ 秒，然后再亮绿灯，黄灯，红灯，如此往复。如果一个交通路口的红绿灯不是红灯，小 X 可以从这个交通路口出发，到达另一个交通路口。若到达交通路口时，灯的颜色瞬间变了，则按照变了之后的灯计算，灯的黄灯和红灯的持续时间可能为 $0$。并且，小 X 最多只能闯 $g$ 次黄灯。

过了一会儿，市长突然发现，所有的红绿灯在某一刻都变成了绿灯。与此同时，小 X 从第 $1$ 个路口出发，前往第 $n$ 个路口。他想问你，他至少要花多少时间才能到达第 $n$ 个路口？

因为路虽远，行则将至，数据保证一定可以到达，即 $1\sim n$ 一定连通。

inputFormat:
第 $1$ 行 $4$ 个整数 $n,m,k,g$。

接下来 $n$ 行，每行 $3$ 个整数 $x_i,y_i,z_i$。

接下来 $m$ 行，每行 $4$ 个整数 $u_i,v_i,p_i,q_i$。

outputFormat: 一行，为小 X 花费的最少的时间。


title: [ROIR 2022 Day 1] n 巧板

background:
翻译自 [ROIR 2022 D1T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day1.pdf)。

有一个拼图由 $n$ 个三角形组成。要成功解出这个拼图，需要从中选择四个三角形，并按以下规则组合成一个大三角形：

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

这些三角形不能相交，它们的组合必须形成一个三角形。选择的四个三角形中恰好有三个三角形位于角落，另一个三角形位于中心。

三角形放置在桌上，可以自由旋转和移动，但**不能翻转**。

description: 需要找到所有可以按照指定规则组合成大三角形的四个不同三角形的集合。如果存在一个三角形属于其中一个集合但不属于另一个集合，则认为两个集合是不同的。

inputFormat:
第一行包含一个整数 $t$，表示当前测试点的编号。

第二行包含一个整数 $n$，表示拼图中的三角形数量（$4 \le n \le 30$）。

接下来的 $n$ 行，每行输入六个数，表示一个三角形三个顶点的坐标，按逆时针顺序给出。所有坐标都是整数，且不超过 $10^5$。保证三角形不会退化为直线段。初始位置的三角形可能相交。

outputFormat:
第一行输出一个整数，表示按照指定规则可以组合成大三角形的四个三角形的集合数量。

接下来的行输出这些集合。每个集合由其中包含的三角形的编号组成。集合内部的三角形可以以任何顺序输出。集合的输出顺序也是任意的。

hint:
本题分 $22$ 个测试点，前两个测试点为样例，通过不得分，后 $20$ 个测试点每个 $5$ 分。

| 测试点编号 | 特殊性质 |
| :----------: | :----------: |
| $1$ | 输入数据即样例 $1$ |
| $2$ | 输入数据即样例 $2$ |
| $3$ | 所有三角形全等，$n\le30$ |
| $4$ | 所有三角形都有一条水平的边和一条垂直的边且它们都是等腰三角形，$n\le10$ |
| $5$ | 所有三角形都有一条水平的边和一条垂直的边且它们都是等腰三角形，$n\le30$ |
| $6$ | 所有三角形都有一条水平的边和一条垂直的边且 $n\le10$ |
| $7$ | 所有三角形都有一条水平的边和一条垂直的边且 $n\le30$ |
| $8$ | 所有三角形都是直角三角形且 $n\le10$ |
| $9$ | 所有三角形都是直角三角形且 $n\le30$ |
| $10$ | 所有能拼成大三角形的四个小三角形均不用旋转即可拼成且 $n\le10$ |
| $11$ | 所有能拼成大三角形的四个小三角形均不用旋转即可拼成且 $n\le20$ |
| $12$ | 所有能拼成大三角形的四个小三角形均不用旋转即可拼成且 $n\le30$ |
| $13$ | $n=10$ |
| $14$ | $n=10$|
| $15$ | $n=10$ |
| $16$ | $n=20$ |
| $17$ | $n=20$ |
| $18$ | $n=20$ |
| $19$ | $n=30$ |
| $20$ | $n=30$ |
| $21$ | $n=30$ |
| $22$ | $n=30$ |


title: [ROIR 2022 Day 1] 回文数组

background:
翻译自 [ROIR 2022 D1T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day1.pdf)。

有两个自然数数组 $A = [a_1, a_2, \dots , a_n]$ 和 $B = [b_1, b_2, \dots , b_m]$。

对每个数组，随机地去掉一个可能为空的前缀和一个可能为空的后缀，使得剩下的数组部分长度相等。我们将得到的数组记作 $A'$ 和 $B'$，它们的长度为 $k$。然后，对这两个数组的相应元素求和，结果数组记作 $C = [c_1, c_2, \dots , c_k]$。

例如，假设 $n = 5,A = [4, 3, 3, 2, 1],m = 6,B = [4, 1, 5, 1, 3, 2]$，从数组 $A$ 中去掉第一个和最后一个元素，从数组 $B$ 中去掉前三个元素，得到 $A' = [3, 3, 2],B' = [1, 3, 2]$，它们的相应元素求和结果为 $C = [4, 6, 4]$。
假设 $n = 7,A = [1,9,1,9,8,1,0],m = 6,B = [1,1,4,5,1,4]$，从数组 $A$ 中去掉前两个元素和最后一个元素，从数组 $B$ 中去掉第一个和最后一个元素，得到 $A' = [1,9,8,1],B' = [1,4,5,1]$，它们的相应元素求和结果为 $C = [2,13,13,2]$。

description: 找到能够得到回文数组 $C$ 的最大长度 $k$。

inputFormat:
第一行输入两个整数 $n$ 和 $m$，分别表示第一个数组和第二个数组的元素数量 ($1 \le n, m \le 100 000$)。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数组 $A$（$1 \le a_i \le 100$）。

第三行输入 $m$ 个整数 $b_1,b_2,\dots,b_n$，表示数组 $B$（$1 \le b_i \le 100$）。

outputFormat: 输出一个整数，表示能够得到的最长回文数组的长度 $k$。


title: [ROIR 2022 Day 2] 幼儿园的新年

background: 翻译简化自 [ROIR 2022 D2T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。

description: 给出三个整数 $n,a,b$，求有多少对 $(x,y)$ 满足 $0 \le x \le a$，$0 \le y \le b$，$x+y$ 不为 $0$ 且能被 $n$ 整除。

inputFormat:
本题多测，第一行输入一个整数 $t$，表示测试数据的组数。

接下来的 $t$ 行，每行输入一组测试数据 $n,a,b$，由空格隔开。

outputFormat: 对于每组数据，输出一行一个数字，即符合条件的 $(x,y)$ 数量。


title: [ROIR 2022 Day 2] 分数排序

background: 翻译自 [ROIR 2022 D2T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。

description:
有两个由 $n$ 个不同整数组成的序列 $A = [a_1, a_2, \dots , a_n]$ 和 $B = [b_1, b_2, \dots , b_n]$。将它们组合成 $n^2$ 个分数，形式为 $\frac{a_i}{b_j}$，并将每个分数约分后按递增顺序排序。

给定一个数字 $q$ 和 $q$ 个整数 $c_1, c_2, \dots , c_q$。对于每个 $c_i$，请输出上面所说的 $n^2$ 个分数中第 $c_i$ 小的分数。

inputFormat:
第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n$ 个不同的整数 $a_1, a_2, \dots, a_n$。

第三行包含 $n$ 个不同的整数 $b_1, b_2, \dots, b_n$。

第四行包含 $q$ 个不同的整数 $c_1, c_2, \dots, c_q$。

outputFormat: 输出 $q$ 行。第 $i$ 行输出按递增顺序得到的第 $c_i$ 个分数。分数 $\frac{p}{q}$ 应以 `p q` 的格式输出，并且应为最简分数。


title: 「QFOI R1」贴贴

description:
小 R 是一个可爱的女孩子，她希望通过给洛谷题目写题解的方式跟出题人贴贴。

她发现，如果从题解界面点击“提交题解”按钮，博客中会自动生成 URL 标识符，也就是文章的链接。

其中，标识符的生成规则如下：

- 将题号的所有大写字母转为小写。
- 将上一步结果的所有下划线转为减号。
- 在上一步结果前面加上 `solution-`。

她准备给一道题目写题解，已知这道题的题号，你能求出 URL 标识符吗？

inputFormat: 一行，一个字符串 $s$，表示题号。

outputFormat: 一行，一个字符串，表示 URL 标识符。

hint:
**样例 $3$ 解释**

根据生成规则：

- 将题号的所有大写字母转为小写：`at_abc312_h`。
- 将上一步结果的所有下划线转为减号：`at-abc312-h`。
- 在上一步结果前面加上 `solution-`：`solution-at-abc312-h`。

---

**数据范围**

本题共 $10$ 个测试点，每个测试点 $10$ 分。

对于全部数据，保证题号仅包含大写字母（ASCII $65\sim 90$）、小写字母（ASCII $97\sim 122$）、数字（ASCII $48\sim 57$）、下划线（ASCII $95$），且长度不超过 $20$。

对于全部数据，答案中应当仅包含小写字母（ASCII $97\sim 122$）、数字（ASCII $48\sim 57$）、减号（ASCII $45$）。

- 对于测试点 $1$：保证为主题库题目。
- 对于测试点 $2$：保证为入门与面试题目。
- 对于测试点 $3\sim 4$：保证为 CodeForces 题目。
- 对于测试点 $5\sim 6$：保证为 SPOJ 题目。
- 对于测试点 $7\sim 8$：保证为 AtCoder 题目。
- 对于测试点 $9\sim 10$：保证为 UVA 题目。


title: [ROIR 2022 Day 2] 网络系统升级计划

background:
翻译自 [ROIR 2022 D2T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。

某国有 $n$ 个城市，从 $1$ 到 $n$ 编号，首都编号为 $1$。

这个国家的计算机网络构建如下：每个城市都有一个连接中心，可以通过有线通信渠道与其他一些中心相连。对于任意两个城市之间存在着一条唯一的通信路径，换句话说，该网络形成一棵树。对于城市 $i(i > 1)$，我们把从城市 $i$ 到首都的路径上第一个城市记为 $p_i$。

计划对网络进行升级，用更先进的光学通信渠道替换一些现有有线渠道。光学通信渠道只能在现有有线通信渠道的位置上铺设。替换连接城市 $i$ 和 $p_i$ 的通信渠道的成本为 $w_i$。由于技术限制，任何连接中心最多可以直接连接到 $k$ 个其它中心。

description:
通信部希望制定一个升级计划，以提高光学通信渠道的其连通性。因此，需要选择尽可能多的通信渠道进行升级。但是，希望在相同数量的情况下尽量减少升级成本，因此，在相同数量的情况下，选择升级具有最小总成本的通信渠道。

帮助通信部专家选择要升级的通信渠道。

inputFormat:
输入的第一行包含两个整数 $n$ 和 $k$。

接下来的 $n−1$ 行描述了通信渠道，其中第 $i−1$ 行包含两个整数：$p_i$ 和 $w_i$（$1 \le p_i < i, 0 \le w_i \le 10^9$）。

outputFormat: 输出两个整数 $cnt$ 和 $cost$，表示能够升级的最大通信渠道数量和升级这些通信渠道的最小成本。

hint:
样例 $1$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $4$。

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

样例 $2$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $6$。升级通道的成本显示在边（通信渠道）的旁边，最优解决方案中升级通道的总成本为 $27$。

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

本题原题分为 $13$ 个 Subtask，但是洛谷不支持设置 $10$ 个以上的 Subtask。本题原题分为 $321$ 个测试点，但是洛谷不支持设置 $100$ 个以上的测试点。所以本题只保留后 $100$ 个测试点，且不使用捆绑测试。

所有数据均满足 $2 \le n \le 10^5, 1 \le k \le 100$。


title: [ROIR 2022 Day 2] 礼物

background:
翻译自 [ROIR 2022 D2T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。

圣诞老人让沃瓦选择一个礼物。

在沃瓦面前有 $n$ 个礼物排成一行。每个礼物给沃瓦带来的快乐程度值用一个整数表示，第 $i$ 个礼物的值为 $a_i$。快乐程度可以是正数、负数或零。

圣诞老人让沃瓦选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le n$。沃瓦需要选择从 $l$ 到 $r$ 之间的所有礼物。然而，在所选的礼物中，沃瓦必须把具有前 $k$ 大快乐程度值的 $k$ 个礼物给他的妹妹玛莎。

description: 帮助沃瓦选择 $l$ 和 $r$，使得 $1 \le l \le r \le n,r - l + 1 \ge k$，并且他得到的礼物的总快乐程度最大化（不包括给妹妹的礼物）。

inputFormat:
第一行输入两个整数 $n$ 和 $k$，表示放在沃瓦面前的礼物数量和需要给玛莎的礼物数量。

第二行输入 $n$ 个整数，用空格分隔，第 $i$ 个数 $a_i$ 表示每个礼物带来的快乐程度。

outputFormat: 输出一个整数，表示沃瓦所选择的礼物的总快乐程度，不包括给玛莎的礼物。


title: 『PG2』弯曲半平面直线同向图最大流

description: 若能将有向图 $G=(V,E)$ 画在平面上，使得点在一条直线上，任意两条边（可以为弯曲的弧线）仅在重合顶点处相交，且边上的所有点都在直线同侧，且每条边的起点到终点的射线的方向相同，则称 $G$ 是弯曲半平面直线同向图。对于一个弯曲半平面直线同向图给定 $n$ 个点，$m$ 条有向边，给定每条边的容量，求从点 $s$ 到点 $t$ 的最大流。

inputFormat:
第一行包含四个正整数 $n$、$m$、$s$、$t$，用空格分隔，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来 $m$ 行每行包含三个正整数 $u_i$、$v_i$、$c_i$，用空格分隔，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，容量为 $c_i$。

outputFormat: 一个整数，表示 $s$ 到 $t$ 的最大流。

hint:
无重边自环。

对于 $30\%$ 的数据 $n\leq 10^3$。

对于 $70\%$ 的数据 $n\leq 10^5$。

对于 $100\%$ 的数据 $2\leq n\leq 10^6$，$1\leq m\leq \min\{2\times 10^9,\dfrac{n(n-1)}{2}\}$，$1\leq c\leq 10^{12}$，$s\neq t$。

### 样例解释 1
![](https://cdn.luogu.com.cn/upload/image_hosting/9qletk0m.png)


title: [ROIR 2023 Day 1] 矩形分割

background: 翻译自 [ROIR 2023 D1T1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。

description:
有一个大小为 $a\times b$ 的由单位方格组成的矩形，你需要通过 $k$ 次垂直或水平的切割将其分成 $m$ 个小矩形。小矩形大小不一定要相等。

每次切割不允许切割一半，必须从一边切到另外一边。只允许在网格线上进行切割。

inputFormat:
第一行输入一个整数 $t$，表示测试数据的组数。

接下来的 $t$ 行，每行一组测试数据。每组数据有四个整数 $a,b,k,m$，分别表示矩形的大小（长和宽），要求的切割次数和要求切成的小矩形数量。

outputFormat: 对于每组数据，在一行中输出能够将其切割成 $m$ 个小矩形的水平切割次数 $h$（$0 \le h < a$）和垂直切割次数 $v$（$0 \le v < b$）。如果可以以多种方式进行切割，则输出水平切割次数较少的方式。如果无法按要求进行切割，则输出 `-1`。


title: [ROIR 2023 Day 1] 斐波那契乘积

background:
翻译自 [ROIR 2023 D1T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。

斐波那契数指斐波那契数列（$f_0=1,f_1=1,f_i=f_{i-2}+f_{i-1}$）中出现的数。

description: 给定一个自然数 $n$，求出将其表示为若干个大于 $1$ 的斐波那契数的乘积的方案数。

inputFormat:
第一行一个数 $t$，表示数据组数。

接下来 $t$ 行，每行输入一个数 $n$。

outputFormat: 对于每组测试数据，输出一个数表示答案。


title: [ROIR 2023 Day 1] 扫地机器人

background:
翻译自 [ROIR 2023 D1T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。

一个扫地机器人正在清洁一个二维坐标平面。扫地机器人是一个边长 $k\times k$ 的正方形，边与坐标轴平行。初始时，扫地机器人左下角位于 $(0,0)$，右上角位于 $(k,k)$。

description: 给定一个由 $n$ 个移动操作组成的序列，第 $i$ 个移动操作由方向 $d_i$（`N` 表示向上，增加 $y$ 坐标；`E` 表示向右，增加 $x$ 坐标；`W` 表示向左，减小 $x$ 坐标；`S` 表示向下，减小 $y$ 坐标）和距离 $a_i$（机器人移动的距离）组成。根据给定的机器人移动操作，计算清扫的总面积（被机器人覆盖过的点就算被清扫过的点）。

inputFormat:
第一行包含两个整数，机器人的大小 $k$ 和操作数量 $n$。

接下来的 $n$ 行中，每行包含一个移动操作和对应的距离 $a_i$。移动操作用字母 $d_i$ 表示（`N` 即向上，`E` 即向右，`W` 即向左，`S` 即向下），且距离 $a_i$ 是一个整数。

outputFormat: 输出机器人清扫的总面积。

hint:
样例解释：下图是两个样例中机器人的移动情况。

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

本题使用捆绑测试。

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

对于 $100\%$ 数据，$1 \le k \le 10^4$，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。


title: [NICA #3] 一键三连

description:
在视频网站 Bilibili，用户可以为视频制作者的视频“投币”，以鼓励制作者创作更好的视频。

如果一个视频是从其他网站搬运而来的，那么用户最多只能投 $1$ 个硬币。

如果一个视频是原创的，那么用户“投币”时，默认会投 $2$ 个硬币。

Aya 记得自己给 $x$ 个搬运的视频，以及 $y$ 个原创的视频“投币”，请问 Aya 一共投了多少个硬币。

inputFormat: 输入两个正整数 $x$ 和 $y$，分别表示给多少个搬运的视频投币和原创的视频投币。

outputFormat: 输出一个正整数表示 Aya 一共投了多少个币。

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

Aya 一共给 $3$ 个搬运视频投币，合计 $3$ 个硬币，$4$ 个原创视频投币，每个原创视频投 $2$ 个币，因此为原创视频总共投币 $8$ 个。合计 $11$ 个硬币。

**【数据范围】**

数据保证，$1 \leq x,y \leq 100$。

tags: 语言入门（请选择[入门与面试]题库）


title: [NICA #3] 开车旅行

description:
Aya 的学校组织了一场春游，春游的目的地是滨江森林公园。由于路途遥远，他们的行程会经过高速和地面道路。

学校所承包的大巴，在高速上是以 $a$ 千米/小时的速度匀速行驶，高速上一共行驶了 $b$ 小时；在地面上是以 $c$ 千米/小时的速度匀速行驶，地面上一共行驶了 $d$ 小时。

Aya 想知道以下两个问题的答案：
- 学校到滨江森林公园的路程有多长？
- 这辆大巴在旅途中的平均速度是多少？

inputFormat: 输入一行，四个实数 $a,b,c,d$。

outputFormat:
输出两行两个实数，**均保留到小数点后一位**。

第一行一个实数，表示学校到滨江森林公园的路程有多长。

第二行一个实数，表示这辆大巴在旅途中的平均速度是多少。

**只要你的答案与标准答案的差距不超过 $0.1$，就被判作正确回答。**

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

对于样例 $1$，大巴在高速上以 $60$ 千米/小时的速度行驶 $2$ 小时，再以 $30$ 千米/小时的速度行驶 $1$ 小时，总共行驶了 $150$ 千米。平均速度 $=$ 路程 $\div$ 时间，可得平均速度为 $50$ 千米/小时。如果你输出的是 $149.9$ 和 $50.1$，也会是正确回答。

**【数据范围】**

对于所有数据，保证 $0 \leq a,b,c,d \leq 1000$，且 $b+d \neq 0$。

tags: 语言入门（请选择[入门与面试]题库）


title: [NICA #3] CPU

description:
为了在有限的芯片面积上取得更强的性能，英特尔（Intel）公司采取了混合架构 CPU 的设计。

具体而言，对于一个 CPU，其有两种核心：
- 性能核心（P 核心）有着更强的性能。每一个性能核心可以提供 $2$ 个线程。**一个 CPU 至少要有 $1$ 个性能核心**；
- 能效核心（E 核心）可以在低功耗下取得性能优势。每一个能效核心可以提供 $1$ 个线程。**一个 CPU 可以没有能效核心**；

例如，一块英特尔酷睿 i5-13600K 的 CPU，有着 $6$ 个性能核心和 $8$ 个能效核心，总计有 $14$ 个核心和 $20$ 个线程。

现在给定一块 CPU 的总核心数和线程数，问其一共有多少个性能核心、多少个能效核心。

inputFormat: 一行，输入两个正整数 $c,t$，分别表示总核心数和线程数。

outputFormat:
如果存在一种混合架构设计的 CPU 符合要求，则输出一行两个正整数 $p,e$，分别表示有多少个性能核心和多少个能效核心。

否则，输出一行字符串 $\texttt{Error}$。

samples:
12 26
Error

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

对于第一组样例，参考题目描述；

对于第二组样例，很明显不存在一种 CPU 设计满足其有 $12$ 个核心，$26$ 个线程，因此输出 $\texttt{Error}$。

**【数据范围】**

对于所有的数据，满足 $1 \leq c,t \leq 100$。


title: [NICA #3] 搬砖

description:
Aya 在工地上搬砖。她手上有 $n$ 块砖头，需要将其平分为两份运达不同的终点。注意，砖头不能切割成半块。

Aya 可以选择一块一块的搬砖，此时搬一块砖需要 $a$ 的体力。Aya 也可以选择将砖头搬上一个可以容纳 $k$ 块砖头的推车（车可以不装满），再推动推车到达终点，这整个过程需要 $b$ 的体力。Aya 可以自由选择搬砖的方式。例如说她可以一块一块地搬一些砖之后再用推车进行搬砖。

Aya 想要知道，在这个过程中，耗费体力的最小值是多少？

inputFormat: 输入 $4$ 个正整数 $n,a,k,b$，含义如题所述。

outputFormat: 输出一行一个整数，表示耗费体力的最小值是多少。如果无法将这些砖头平分成两份，则输出 $-1$。

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

对于样例 $1$，将砖平分为两份，则每份一共有 $6$ 块砖。用小推车一次可以搬 $2$ 块砖，只耗费 $2$ 的体力，比一块一块搬砖划算。因此 Aya 选择用三次小推车搬砖，耗费 $6$ 的体力。注意一共有两份砖头，因此一共是耗费 $12$ 的体力。

**【数据范围】**

对于所有数据，$1 \leq n,a,k,b \leq 10^6$。**请注意数据范围**。


title: [NICA #3] 放生鱼豆腐

description:
某地有 $k$ 个人放生鱼豆腐。Aya 在巡查的时候发现了这一匪夷所思的现状，因此上前制止。

未报备的、不合理的放生是要被处罚罚金的。Aya 制定的处罚规则如下。对于每个个人而言：

- 放生 $\leq 10$ 千克鱼豆腐，每一千克鱼豆腐惩罚 $a$ 元；
- 超出上述部分，对于放生不超过 $100$ 千克鱼豆腐的部分，超出部分每一千克鱼豆腐惩罚 $b$ 元；
- 超出上述部分，超出部分每一千克鱼豆腐惩罚 $c$ 元。

例如说，如果某人放生了 $150$ 千克鱼豆腐，则这样计算其罚金：
- 对于最开始的 $10$ 千克鱼豆腐，计算罚金 $10\times a$ 元；
- 对于不超过 $100$ 千克的鱼豆腐的部分，每一千克惩罚 $b$ 元，合计 $90\times b$ 元。
- 超出了上述部分 $50$ 千克，从而惩罚 $50\times c$ 元。

现在知道了这 $k$ 个人每个人放生的鱼豆腐的重量，问 Aya 最后需要这些人总共上交多少的罚金？

inputFormat:
第一行输入四个正整数 $k,a,b,c$，含义如题所述。

第二行输入 $k$ 个正整数 $x$，分别表示每个人的放生鱼豆腐的重量。

outputFormat: 输出一行一个正整数，表示这些人总共要上交多少的罚金。

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

每个人缴纳的罚金如下：
- 对于第一个人，要交的罚金是 $5\times 2=10$ 元；
- 对于第二个人，要交的罚金是 $10\times 2+10\times 3=50$ 元；
- 对于第三个人，要交的罚金是 $10\times 2+50\times 3=170$ 元；
- 对于第四个人，要交的罚金是 $10\times 2+90\times 3+20\times 4=370$ 元；
- 对于第五个人，要交的罚金是 $10\times 2+90\times 3+100\times 4=690$ 元；

从而，总共缴纳的罚金为 $10+50+170+370+690=1290$ 元。

**【数据范围】**

数据保证，$1 \leq k,a,b,c,x \leq 1000$。


title: [NICA #3] 抗洪救灾

description:
由于连日的暴雨，某水库在高负载下持续运行，水位已经超过保证水位，处于溃坝的边缘。

Aya 现在负责该水库的水位调度。根据气象部门和水文部门的预测和调度，她得知了未来 $n$ 小时的水库入库量 $a_i$ 和水库出库量 $b_i$。定义第 $i$ 小时的水库净入库量为该小时的水库入库量和出库量之差。

Aya 根据水库的实际运转情况认为，如果存在连续的 $k$ 小时，这 $k$ 小时之间水库净入库量之和**大于等于**阈值 $M$，那么水库就有溃坝可能，会为下游造成更危险的洪灾。

现在 Aya 想要知道，水库是否会有溃坝的可能。

inputFormat:
第一行输入三个正整数 $n,k,M$，含义如题所述。

第二行输入 $n$ 个正整数，表示每个小时的水库入库量 $a_i$。

第三行输入 $n$ 个正整数，表示每个小时的水库出库量 $b_i$。

outputFormat: 如果有溃坝的可能，则输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

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

对于样例 $2$，前三个小时的水库净入库量为 $8+6+4=18$，大于阈值 $10$，因此有发生溃坝的可能性。

**【数据规模】**

对于所有数据，$1 \leq k\leq n \leq 5000$，$1 \leq a_i,b_i,M \leq 10^9$。**请注意数据范围**。


title: 【MX-X6-T7】夏が終わる

background:
> _夏の終わりを知って$\\$
ラムネの雫に映る僕達は$\\$
見失いそうな$\\$
茜色の頬を追いかけて$\\$
来年もまた此処に来るんだ_
>
>_—— [夏が終わる - Nanatsukaze](https://music.163.com/#/song?id=2614276904)_

一年时间，走一个环，再次回到原点。

在这个世界不间断的变化中，还有机会再遇到你吗？选择一条最优的路径时，又有多大的机会呢？

description:
给定一棵 $n$ 个点的树 $T$，边带权。定义无向完全图 $G(T)$：

- 包含 $n$ 个点。
- 如果 $T$ 中包含边 $u,v$，则 $G$ 上 $u,v$ 边的权值为这条边的权值；否则为 $0$。

记 $w(T)$ 为 $G(T)$ 的权值最小的哈密顿回路的权值。

给定 $q$ 次修改操作，分为两种：

- 在 $T$ 上删去一条边再加上一条边，**保证每次操作后仍然是一棵树**；
- 给定 $T$ 上的一条路径，给路径上的每一条边的边权增加一个值。

你需要在每次操作之后计算 $w(T)$。

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

接下来 $n-1$ 行每行三个正整数 $u,v,w$ 表示树上的一条边，边按照输入顺序编号为 $1\sim n-1$。

接下来 $q$ 行每行 $4$ 或 $5$ 个整数，第一个整数表示操作编号 $opt$：

- 如果 $opt=1$，则表示删边再加边操作，接下来 $4$ 个整数依次为 $i,u,v,w$：$i$ 表示这一次操作删去的边的编号；$u,v,w$ 表示新加的边。这些新增的边按照操作顺序从 $n$ 开始依次向上编号。
- 如果 $opt=2$，则表示路径加操作，接下来 $3$ 个整数 $u,v,w$：表示给树上 $u,v$ 之间的简单路径上的每一条边的边权增加 $w$。

outputFormat: $q$ 行每行一个整数表示操作后的 $w(T)$。

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

第一次操作后，$G(T)$ 的形态如下：

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

其中树边用红色标出，最优的哈密顿回路之一为 $1-5-4-2-3-1$。

**【数据范围】**

对于所有数据，保证 $5\leq n\leq 1.5\times 10^5$，$1\leq q\leq 3\times 10^5$，$1\leq u,v\leq n$，$1\leq w\leq 2\times 10^{11}$，保证任意时刻边权不超过 $4\times 10^{11}$，保证不会重复删除已经删除的边。

**捆绑测试**，共 5 个 Subtask，具体限制如下所示：

- Subtask 1（6 pts）：$n\leq 10$，$q\leq 500$；
- Subtask 2（27 pts）：$n,q\leq 2000$；
- Subtask 3（15 pts）：所有答案均 $\geq 1$；
- Subtask 4（26 pts）：$n\leq 7.5\times 10^4$，$q\leq 1.5\times 10^5$；
- Subtask 5（26 pts）：无特殊限制。


title: [ROIR 2023 Day 1] 彩点

background:
翻译自 [ROIR 2023 D1T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。

平面上有 $n$ 个点，分别是 $P_1,P_2,P_3,\dots，P_n$。第 $i$ 个点的坐标为 $(x_i,y_i)$。

选择两个点 $P_i,P_j$（$i\ne j$）。设 $P_i$ 为起始点，$P_j$ 为终止点。**以终止点 $P_j$ 为中心**，从向量 $\overrightarrow{P_iP_j}$ **的方向**开始按照逆时针顺序将除 $P_j$ 以外的点进行排序（角度相同时按照到点 $P_j$ 的距离升序排序）。假设排序后的第 $t$ 个点为 $P_k$，则继续重复操作，设 $P_j$ 为起始点，$P_k$ 为终止点，按照相同的方法重新排序并计算新的终止点的编号。这个过程循环进行。

在下图中，刚开始时 $n=6,t=4,i=1,j=2$。按照顺序将除了 $P_2$ 以外的点排序，结果是 $P_3,P_5,P_1,P_6,P_4$，所以下一个终止点应该是 $P_6$，起始点是 $P_2$。

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

此时 $n=6,t=4,i=2,j=6$。继续按照规则排序，如左下图，结果是 $P_4,P_3,P_2,P_1,P_5$。所以下一个终止点是 $P_1$，起始点是 $P_6$。

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

此时 $n=6,t=4,i=6,j=1$。继续按照规则排序，如右上图，结果是 $P_5,P_6,P_4,P_2,P_3$。所以下一个终止点是 $P_2$，起始点是 $P_1$。此时就回到刚开始的情况，进入了一个循环。

description:
我们将 $n$ 个点中的每个点涂上三种颜色之一。第 $i$ 个点的颜色如下确定：

- 如果存在点 $j$，选取点 $i$ 作为起始点，点 $j$ 作为终止点，在上面的过程中点 $i$ 会无数次成为起始点，则将点 $i$ 涂成绿色。
- 如果点 $i$ 没有涂成绿色并且存在点 $j$，选取点 $i$ 作为起始点，点 $j$ 作为终止点，在上面的过程中点 $i$ 至少还能成为起始点一次，则将点 $i$ 涂成蓝色。
- 如果点 $i$ 既不是绿色也不是蓝色，则将点 $i$ 涂成红色。

对于每个点，确定它应该涂成哪种颜色。

inputFormat:
第一行包含两个整数 $n$ 和 $t$。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$。保证没有两个点重合。

outputFormat:
输出一行，包含 $n$ 个字符，字符串的第 $i$ 个字符表示第 $i$ 个点的颜色。

绿色点用字母 `G` 表示，蓝色点用字母 `B` 表示，红色点用字母 `R` 表示。

hint:
样例 $1$ 解释：

在前面举的例子中已经知道 $P_1,P_2,P_6$ 构成一个循环，这三个点肯定会被无限次访问，所以应被涂上绿色。

当起始点是 $P_3$ 时，可以令终止点为 $P_1$，排序后 $P_3$ 正好是第四个，这样 $P_3$ 就重回起始点了，如下图。所以应该涂蓝。

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

当起始点是 $P_4$ 时，可以选择 $P_5$ 为终止点，排序后 $P_4$ 正好是第四个。所以 $P_4$ 可以涂蓝。当 $P_5$ 是起始点时，易得它既不能被涂上绿色也不能被涂上蓝色，所以涂红。

本题使用捆绑测试。

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $n\le10$，所有点共线 |
| $2$ | $15$ | 所有点共线 |
| $3$ | $10$ | $n\le10$，没有蓝色点 |
| $4$ | $10$ | $n\le10$ |
| $5$ | $15$ | $n\le100$，没有蓝色点 |
| $6$ | $15$ | $n\le100$ |
| $7$ | $5$ | $n\ge3$，所有点构成一个严格凸 $n$ 边形，且按照逆时针顺序输入 |
| $8$ | $20$ | 无 |

对于全部数据，$2 \le n \le 1 000, 1 \le t \le n−1,−10^9 \le x_i, y_i \le 10^9$。


title: 高仿的 Migos

description:
经过刻苦的训练，ZHY 终于成为了一名说唱歌手。但这天，说唱歌手 ZHY 看到了同行说唱组合 Migos 的作品，立刻意识到了自己的差距，于是他要学习 Migos 的说唱技巧，复刻 Migos 的成功。

经过数个日夜的研究，ZHY 最终挑选出了 $n$ 部 Migos 的说唱作品，依次编号为 $1,2,\dots,n$。他认为只要学习完这 $n$ 部作品，就可以成为更加优秀的说唱歌手。于是，他会从第 $1$ 部作品，按编号从小到大的顺序依次进行学习，学习完第 $n$ 部作品就结束学习。

不过，说唱歌手 ZHY 的学习方式很特殊。对于每部作品，他只会听 $1$ 分钟。这种学习方式的问题是，对于第 $i$ 部作品，他在投入 $1$ 分钟后，有可能学习成功，也有可能会失败，具体地，如果 ZHY 学习的是作品 $i$，那么在他花一分钟的时间进行学习后：

- 有 $P_i$ 的概率，ZHY 学习成功了，那么他会接着去学习作品 $i+1$（当然如果 $i=n$ 就直接结束学习）。
- 有 $1-P_i$ 的概率，ZHY 学习失败了。不幸的是，ZHY 脑内的记忆还会因此产生混乱，导致他只会记住前 $x_i$ 部作品，即他必须从第 $x_i+1$ 部作品开始重新学习。

ZHY 在尝试了几次学习后，深受记忆混乱的困扰，于是向脑科学专家 YHZ 求助。经过脑科学专家 YHZ 的研究，他发现所有的 $x_i$ 有一定的规律。具体地，他发现有 $m$ 对自然数 $(l_i,r_i)$, 其中 $i=1,2\dots,m$，满足 $0\leq l_i<r_i\leq n$，那么 $x_i=\max\limits_{j=1}^m\{l_j
\mid l_j+1\leq i\leq r_j\}$，特别地，如果对于所有 $1\leq j\leq m$，都**不满足** $l_j+1\leq i\leq r_j$，那么 $x_i=0$。

现在，ZHY 对自己的学习能力有了充分了解，但刚才的尝试让他疲惫不堪，所以他决定休息 $1$ 秒，并希望你帮他计算一下他期望多少分钟可以结束学习。不过他意识到，自己如果每部作品只学固定的 $1$ 分钟是不够全面的，所以他决定更改一些作品他所会学习的那一分钟，这会导致他学习这一部作品的成功概率发生改变。具体地，现在 ZHY 提出了 $k$ 个要求，每个要求有两种可能：

1. 修改某个作品 $i$ 学习成功的概率 $P_i$。
1. 询问以当前的概率他学习完 $n$ 部作品期望要多少分钟。

由于 ZHY 要休息，所以他找上了你，希望你来解决他的要求。对于他的每个第二种要求，你要告诉他期望时间对 $10^9+7$ 取模的结果。ZHY 给了你 $1$ 秒的时间，因为他只能休息这么久。

inputFormat:
第一行三个整数 $n,m,k$。意思如题面所述。

接下来 $n$ 行，每行两个正整数 $p_i,q_i$，表示 $P_i=\frac{p_i}{q_i}$。

接下来 $m$ 行，每行两个整数 $l_{i},r_{i}$。

接下来 $k$ 行，每行都是以下两种格式的其中一种：

- `1 x a b` 为修改操作。表示 $P_x$ 变成了 $\frac a b$。保证 $1\le x \le n$，$1 \le a \le b < 10^9+7$ 且 $x,a,b$ 均为正整数。

- `2` 为查询操作。表示询问此时结束学习的期望时间是多少。对 $10^9+7$ 取模。

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


title: 「MXOI Round 2」游戏

description:
小 C 和小 D 正在玩一款蒸蒸日上的游戏。

这款游戏共有 $3$ 种手牌：杀、闪、斩。他们的用途分别如下：

- 杀：对对方使用，对方需要使用一张**闪**，否则对方输掉游戏；**或**回应对方的**斩**；

- 闪：回应对方的**杀**；

- 斩：对对方使用，对方需要使用一张**杀**，否则对方输掉游戏。

玩家在每使用一张牌后，都需要弃掉该使用的牌。

从小 C 开始，每个回合依次属于小 C 和小 D。在玩家的回合内，该玩家可以出**任意**张**杀**和**斩**，对方需要做出对应的回应。当然，玩家也可以不出牌，直接进入对方的回合。

现在，小 C 共有 $c_1$ 张杀、$c_2$ 张闪、$c_3$ 张斩，小 D 共有 $d_1$ 张杀、$d_2$ 张闪、$d_3$ 张斩，**双方都知道对方的手牌**。你需要求出，双方在都进行最优策略的情况下，游戏的结果会如何。

inputFormat:
**本题有多组测试数据。**

第一行输入一个整数 $T$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据，输入一行六个整数 $c_1,c_2,c_3,d_1,d_2,d_3$。

outputFormat:
对于每组测试数据，输出一行：

- 若双方在都进行最优策略的情况下，小 C 可以获胜，则输出 `C`；

- 若双方在都进行最优策略的情况下，小 D 可以获胜，则输出 `D`；

- 若双方在都进行最优策略的情况下，游戏会平局，即谁也无法获胜，则输出 `E`。

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

对于第一组数据，小 C 可以先出一张斩，并在小 D 回应一张杀后再出一张斩。此时小 D 的杀用完了，无法做出回应，输掉了游戏。

#### 【样例 #2】

见附加文件中的 `game/game2.in` 与 `game/game2.ans`。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$0 \le c_1,c_2,c_3,d_1,d_2,d_3 \le 10^9$。

|测试点编号|特殊性质|
|:---:|:---:|
|$1\sim3$|保证 $c_3=d_3=0$|
|$4\sim6$|保证 $c_1=d_2$ 且 $c_2=d_1$|
|$7\sim10$|无|


title: 「MXOI Round 2」队列

description:
小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下：

$1\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\cdots,x$；

$2\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素；

$3\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素；

$4$：这是第四种操作，表示查询队列中所有元素的最大值。

你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。

inputFormat:
第一行两个整数 $c,q$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

接下来 $q$ 行，每行 $1 \sim 2$ 个整数，表示一个操作，格式见【**题目描述**】。

outputFormat: 对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。

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

在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$。

在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$。

#### 【样例 #2】

见附加文件中的 `queue/queue2.in` 与 `queue/queue2.ans`。

该样例满足测试点 $1$ 的限制。

#### 【样例 #3】

见附加文件中的 `queue/queue3.in` 与 `queue/queue3.ans`。

该样例满足测试点 $4$ 的限制。

#### 【样例 #4】

见附加文件中的 `queue/queue4.in` 与 `queue/queue4.ans`。

该样例满足测试点 $11$ 的限制。

#### 【样例 #5】

见附加文件中的 `queue/queue5.in` 与 `queue/queue5.ans`。

该样例满足测试点 $15$ 的限制。

#### 【样例 #6】

见附加文件中的 `queue/queue6.in` 与 `queue/queue6.ans`。

该样例满足测试点 $20$ 的限制。

#### 【数据范围】

设 $\sum x$ 表示单个测试点内 $x$ 之和。

对于 $100\%$ 的数据，$1 \le q \le 2\times 10^5$，$1 \le x,y,z \le 10^9$，$0 \le \sum x \le 2\times10^{14}$，保证在进行第二种操作前队列内元素个数不小于 $y$，在进行第三种操作前队列内元素个数不小于 $z$，在进行第四种操作前队列内元素个数大于 $0$。

|测试点编号|$q \le$|$x \le$|$\sum x \le$|特殊性质|
|:---:|:---:|:---:|:---:|:---:|
|$1\sim3$|$500$|$500$|$2\times10^5$|C|
|$4\sim8$|$5000$|$5000$|$2\times10^7$|无|
|$9\sim10$|$2\times10^5$|$10^9$|$2\times10^{14}$|AB|
|$11\sim12$|$2\times10^5$|$10^9$|$2\times10^{14}$|B|
|$13\sim14$|$2\times10^5$|$10^9$|$2\times10^9$|AC|
|$15\sim16$|$2\times10^5$|$10^9$|$2\times10^9$|C|
|$17\sim18$|$2\times10^5$|$500$|$2\times10^7$|无|
|$19$|$2\times10^5$|$10^9$|$2\times10^9$|无|
|$20$|$2\times10^5$|$10^9$|$2\times10^{14}$|无|

特殊性质 A：没有第二种操作。

特殊性质 B：没有第三种操作。

特殊性质 C：没有第四种操作。


title: 「QFOI R1」头

background: 可以看看这个讨论：<https://www.luogu.com.cn/discuss/703835>。

description:
小 R 是一个可爱的女孩子。有一天，她在被摸头时，突然灵光乍现，便随手加强了一道题给你做。

这道题的名字叫涂色游戏。初始时你有一个 $n$ 行 $m$ 列的网格，所有格子上都没有颜色。有 $k$ 种颜色的刷子，颜色编号为 $1\sim k$。然后给出 $q$ 次操作，每次操作给出 $op,l,r,c,t$ 五个参数：

- 如果 $op=1$，表示将第 $l\sim r$ 行的所有格子涂成颜色 $c$。
- 如果 $op=2$，表示将第 $l\sim r$ 列的所有格子涂成颜色 $c$。
- 如果 $t=0$，意味着如果涂色时遇到已经被染色的格子，就不再进行染色。
- 如果 $t=1$，意味着如果涂色时遇到已经被染色的格子，就用新的颜色覆盖它。

在所有涂色操作结束以后，对于每种颜色，求出有多少个格子被染成了这种颜色。

inputFormat:
第一行四个整数 $n,m,k,q$，表示行数、列数、颜色数和操作数。

接下来 $q$ 行，每行五个整数 $op,l,r,c,t$，表示这次操作的参数。

outputFormat: 一行 $k$ 个整数，第 $i$ 个整数表示被染成颜色 $i$ 的格子数量。

hint:
**样例 $1$ 解释**

用浅灰色表示颜色 $1$，灰色表示颜色 $2$。

涂色过程如图所示：

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

共有 $17$ 个区域被染成颜色 $1$，$7$ 个区域被染成颜色 $2$。

---

**数据范围**

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于全部数据，保证 $1\le n,m,q\le 2\times 10^6$，$1\le k\le 5\times 10^5$，$op\in\{1,2\}$，若 $op=1$ 则 $1\le l\le r\le n$，若 $op=2$ 则 $1\le l\le r\le m$，$1\le c\le k$，$t\in\{0,1\}$。

- 对于测试点 $1\sim 3$：保证 $n,m,k,q\le 200$。
- 对于测试点 $4\sim 6$：保证 $n,m,k,q\le 2\times 10^3$。
- 对于测试点 $7\sim 9$：保证 $n,m,k,q\le 10^5$，$op=1$。
- 对于测试点 $10\sim 12$：保证 $n,m,k,q\le 10^5$，$t=1$。
- 对于测试点 $13\sim 18$：保证 $n,m,k,q\le 10^5$。
- 对于测试点 $19\sim 20$：无特殊限制。


title: [语言月赛 202308] 小粉兔还会忘记考试吗

description:
小粉兔在本学期共修读了 $N$ 门课程，第 $i$ 门课程的课程代码为 $E_i$，每门课程都需要在结课后进行课程考试。

教务开始处理粉兔的成绩。教务共录入了 $M$ 条成绩信息，一条成绩信息由课程代码和成绩组成。由于成绩可能存在调整，一门课程的成绩可能被重复录入，后录入的成绩将覆盖先录入的成绩。课程成绩在 $60$ 分及以上，该门课程为及格；否则，为不及格。

由于粉兔记性很差，很可能忘记参加某些课程的课程考试。如果教务没有录入粉兔某门课程的成绩，则代表粉兔旷考了该门课程。旷考的课程亦为不及格。

小 F 就是这名教务，小 F 对粉兔旷考和不及格的门数非常感兴趣，请你帮助她统计。

inputFormat:
输入共 $M+2$ 行。

输入的第一行为两个整数 $N,M$。

输入的第二行为 $N$ 个整数，第 $i$ 个为 $E_i$。

接下来 $M$ 行，每行两个整数 $P_i,S_i$，$P_i$ 表示课程代码，$S_i$ 表示课程成绩。

outputFormat:
输出两行。

输出的第一行为一个整数，代表小粉兔旷考的课程数。

输出的第二行为一个整数，代表小粉兔不及格的课程数。

hint: 对于 $100\%$ 的测试数据，$1 \le N,M \le 5 \times 10^3$，$1 \le E_i,P_i \le 10^9$，$E_i$ 互不相同，$0 \le S_i \le 100$。 保证存在一个整数 $j$，使得 $P_i=E_j$。


title: [语言月赛 202308] 小粉兔 Failed System Test

background:
小粉兔在某场 CF 中 -154，警示大家不能 FST。

这是一道 **hack 题**。在本题目中，你将得到两个问题和两个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于这两个问题，你需要分别提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

---
**提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言。**

description:
以下给出两个问题的题目描述：

#### 问题 1

给定 $n$ 个元素，标号为 $1, 2, \cdots, n$，你需要标记其中 $k$ 个元素。如果两个元素标号相差 $1$ 则称二者相邻。

请计算出「自身未被标记且有至少一个相邻元素被标记」的元素的**可能的最小数量**和**可能的最大数量**。

#### 问题 2

给定一个仅包含小写字母 `a`、`b`、`c` 的字符串，判断这个字符串是否符合以下所有特征：

1. 字符串中至少有一个 `a` 字母和一个 `b` 字母，且所有的 `a` 在 `b` 之前。
2. 如果字符串中有 `c`，所有的 `a` 在 `b`、`c` 之前，所有的 `b` 在 `c` 之前。
3. `c` 的数量等于 `a` 的数量或 `b` 的数量。

inputFormat:
#### 问题 1

输入共一行两个整数 $n, k$。

#### 问题 2

输入共一行一个字符串 $S$。

outputFormat:
#### 问题 1

输出共一行两个整数，依次代表可能的最小数量和可能的最大数量。

#### 问题 2

输出共一行一个字符串。如果 $S$ 符合要求，则输出 `YES`，否则输出 `NO`。

samples: aaabccc YES

hint:
### 样例组与实际输入的说明

两个样例分别对应两个问题的样例输入输出。

如果你直接采用『提交答案』的方式，请分别将两个输入数据命名为 `1.in`、`2.in`，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器可以从标准输入读入一个整数 $x$，满足 $1 \leq x \leq 2$，表示该测试点对应的问题编号，然后**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对两个问题的样例说明。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有文末回车。
2. 对于问题 $1$，$1 \leq n \leq 10 ^ 9$，$0 \leq k \leq n$。
3. 对于问题 $2$，$1 \leq \left | S \right | \leq 5000$（$\left | S \right |$ 代表字符串 $S$ 的长度），$S$ 中仅包含小写字母 `a, b, c`。

### 目标代码

你需要 hack 如下的代码：

#### 问题 1

```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
	if (k == n || k == 0) {
		cout << "0 0" << endl;
		return 0;
	}
	cout << "1 ";
	if (k * 3 <= n)
        cout << 2 * k << endl;
	else
        cout << n - k << endl;
	return 0;
}
```

#### 问题 2

```cpp
#include <bits/stdc++.h>
using namespace std;

char str[5005];
int i, n, A, B, C;

int main() {
	cin >> str;
	n = strlen(str);
	if (str[0] != 'a') {
		cout << "NO" << endl;
		return 0;
	}
	for (i = 0; i < n; ++i)
        if (str[i] != 'a') break;
	A = i;
	for (; i < n; ++i)
		if (str[i] != 'b') break;
	if (i == n || str[i] != 'c') {
		cout << "NO" << endl;
		return 0;
	}
	B = i - A;
	for (; i < n; ++i)
		if (str[i] != 'c') break;
	if (i != n) {
		cout << "NO" << endl;
		return 0;
	}
	C = n - B - A;
	if (C != A && C != B)
        cout << "NO" << endl;
	else
        cout << "YES" << endl;
	return 0;
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 Unaccepted 的结果。

#### 超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

#### 结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和**完全正确的输出**，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

#### 未定义行为判定

我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

### 样例程序

这是一份可以帮你理解你需要输出的内容的样例程序，**但它不能给出正确的 hack 数据**。直接提交此程序不会得分。

```cpp
#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "" <<endl;
  } else if (taskId == 2) {
    cout << "" << endl;
  } else { // 这个 else 不会被执行
    cout << "Stupid Fusu!" << endl;
  }
}
```

如果你使用『提交答案』功能，请务必保证打开压缩包后能且仅能**直接**看到两个 `.in` 文件。这就是说，文件结构必须是：

```plain
ans.zip
 |---1.in
 |---2.in
```

两个文件不应该被额外的文件夹包含，即文件结构不能是：

```plain
ans.zip
 |---ans(folder)
      |---1.in
      |---2.in
```

### 关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。


title: color

description:
洛谷的名字颜色和咕值直接挂钩，具体细则见 [洛谷咕值系统介绍](https://www.luogu.com.cn/discuss/83952)。

给出某洛谷用户的五项咕值指标的得分，输出该用户的名字颜色。保证该用户不是棕名和紫名。

inputFormat: 一行五个整数，分别表示该用户的基础信用、社区贡献、比赛情况、练习情况、获得成就得分。

outputFormat: 一行一个字符串，表示该用户的名字颜色。这个字符串必须为 `Gray`，`Blue`，`Green`，`Orange`，`Red` 中的一个（区分大小写）。

hint:
**【样例说明】**

三个样例的咕值分别为 $263,140,0$，名字颜色分别为红、绿、灰。

**【数据范围】**

对于 $20\%$ 的数据，满足五项指标分数均 $\le 10$；

对于另外 $20\%$ 的数据，满足五项指标分数均 $\ge 90$；

对于 $100\%$ 的数据，保证五项指标分数均 $\in [0, 100]$。


title: [语言月赛 202308] 小粉兔的挂科与压力

description:
小粉兔在 T 大学就读。在 1 月 54 日，T 大学开始了一学期一度的期末考试环节。

小粉兔本学期有 $n$ 科考试，按照时间先后顺序依次被标号为 $1, 2, \cdots, n$。每一科考试都具有一个难度系数 $a _ i$。

如果准备这么多考试，小粉兔很可能会压力激增。因此，他想要仅准备并参与一部分考试，而将剩余的科目申请缓考。具体的，他可以选择准备**前任意科**考试（可以是 $0$ 门，可以是 $n$ 门），而剩余的科目不做准备。

但是，缓考的考试在下学期仍然需要参加，所以小粉兔会对他的决策做一个评估。他会使用「压力值」去完成这一评估过程。

具体的，我们设小粉兔选择参加前 $k$ 科考试（$0 \leq k \leq n$）。给定一个压力系数 $c$，此时他的压力值 $t$ 的计算方式如下：

$$
t = \max \limits _ {i = 1} ^ {k} a _ i + c \times (n - k)
$$

其中 $\max \limits _ {i = 1} ^ {k} a _ i$ 代表 $a _ 1, a _ 2, \cdots, a _ k$ 中的最大值。特别的，如果 $k = 0$，则 $\max \limits _ {i = 1} ^ {k} a _ i = 0$。

现在，小粉兔知道了考试的科数 $n$ 和每门考试的难度系数 $a _ 1, a _ 2, \cdots, a _ n$，请你帮他计算出「压力值」最小时需要准备的考试科目数量。

inputFormat:
输入共两行。

第一行为两个整数 $n, c$，分别代表考试的科目数和压力系数。
第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，代表每门考试的难度系数。

outputFormat: 输出共一行两个整数，依次代表小粉兔「压力值」最小时需要准备的考试科目数量 $k$ 和对应的最小「压力值」。如果有多个 $k$ 对应的「压力值」相同且最小，请在相应位置输出其中最小的一个。


title: [语言月赛 202308] 小粉兔的元素反应

description:
在小粉兔所处的 Tivat（蒂瓦特）世界，有 $n$ 种元素。其中每种元素都可以蕴含一定的能量，且不同元素之间可以进行反应。

小粉兔现在掌握了这 $n$ 种元素。初始时，他所掌握的每种元素所蕴含的能量依次为 $a _ 1, a _ 2, \cdots, a _ n$。

不同元素之间的反应相关细节如下：

**反应条件**：对于任意两种元素 $i, j$（$i \neq j$），如果 $a _ i \times a _ j$ 是 $154$ 的倍数或 $147$ 的倍数，则二者可以进行反应。**元素不可与自身反应**。
**反应结果**：包含这两种元素在内，所有的 $n$ 种元素所蕴含的能量均翻倍（即，所有 $a _ i$ 均变为原来的两倍）。
**反应次数**：任意两种元素之间的反应次数均没有限制（即，同两种元素，在一直符合反应条件的情况下，可以反应多次）。

现在，小粉兔想要通过元素反应，使得自己手头的元素能量总和大于等于 $k$，从而打败 Tivat 世界最强大的怪兽——地文（Devil）。他现在想要知道，通过若干次（$0$ 次亦可）反应后，$a _ 1 + a _ 2 + \cdots + a _ n$ 是否可以大于等于 $k$。

inputFormat:
**本题单个测试点内有多组数据**。

输入共 $2 \times T + 1$ 行。

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

对于每组数据：
第一行为两个整数 $n, k$，分别代表元素种类数和小粉兔的目标。
第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，分别代表每种元素初始时所蕴含的能量值。

outputFormat:
输出共 $T$ 行。

对于每组数据：
输出一行一个字符串。如果小粉兔可以通过若干次（$0$ 次亦可）反应，使得 $a _ 1 + a _ 2 + \cdots + a _ n$ 大于等于 $k$，则输出一行 `Yes`，否则输出 `No`。


title: 「PHOI-1」晚宴筵

background:
小 X 在 Z 市长途奔波之后，他要去参加别人的晚宴。

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

description:
Z 市形如一个 $n \times n$ 的矩阵，小 X 打算仅使用瞬移机和时空穿越机到达别人的晚宴，若小 X 所在的位置 $(p,q)$ 满足 $l1_x \le p \le r1_x$ 且 $l2_y \le q \le r2_y(0 \le l1_x \le r1_x < x,0\le l2_y\le r2_y < y)$，那么小 X 就可以到达位置 $(x,y)$。

但是由于瞬移技术不太成熟以及时空穿越机的影响，瞬移时需花费 $w_p+w_q+w_x+w_y-p-q-x-y$ 秒（由于时空穿越机的特性，时间可能为负）。若下标不是正整数，瞬移机就会被损坏，所以小 X 只能到达都是正整数的下标。

现在小 X 在 $(1,1)$ 的位置，他要参加别人的晚宴，可是他目前不知道别人的晚宴在哪里，所以他想让你求，他到达每个地方 $(x,y)\text{ }\text{ }(1 \leq x,y \leq n)$ 所花费的最少时间，如果不能到达则输出 `inf`。

inputFormat:
第 $1$ 行一个整数 $n$，表示矩阵的大小。

第 $2$ 行 $n$ 个非负整数分别表示 $l1_1,l1_2 \ldots l1_n$。

第 $3$ 行 $n$ 个非负整数分别表示 $r1_1,r1_2 \ldots r1_n$。

第 $4$ 行 $n$ 个非负整数分别表示 $l2_1,l2_2 \ldots l2_n$。

第 $5$ 行 $n$ 个非负整数分别表示 $r2_1,r2_2 \ldots r2_n$。

第 $6$ 行 $n$ 个非负整数分别表示 $w_1,w_2 \ldots w_n$。

数据保证 $l1_i \leq r1_i,l2_i \leq r2_i$。

outputFormat: 输出 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数表示小 X 从 $(1,1)$ 到 $(i,j)$ 的最短路。

samples:
0 inf inf inf inf inf inf inf inf inf
inf 18 inf inf inf inf inf inf inf inf
inf 15 20 18 inf inf inf inf inf inf
inf inf 18 16 inf inf inf inf inf inf
inf inf 12 10 8 9 12 7 4 2
inf inf 13 11 9 10 13 8 5 3
inf inf 16 14 12 13 16 11 8 6
inf inf 11 7 3 4 7 2 -1 -3
inf inf 8 4 0 1 4 -1 -4 -6
inf inf 6 2 -2 -1 2 -3 -6 -8


title: [ROIR 2023 Day 2] 地铁建设

background:
翻译自 [ROIR 2023 D2T1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。

用于铺设地铁隧道的盾构机有 $n$ 个发动机。所有发动机是并联的，所以所有发动机两端的电压都相同。

每个发动机有两种模式，假设所有发动机接收到的电压都为 $x$，则当 $x\le z_i$ 时第 $i$ 个发动机在第一模式下工作，否则它在第二模式下工作。

第 $i$ 个发动机在第一模式下的单位电流为 $a_i$，在第二模式下的单位电流为 $b_i$。所以，根据 $P=UI$，当发动机处于第一模式时，每增加 $1$ 单位电压，其功率增加 $a_i$ 单位；当发动机处于第二模式时，每增加 $1$ 单位电压，其功率增加 $b_i$ 单位。换句话说，当电压为 $x$ 单位电压，如果第 $i$ 个发动机处于第一模式下，它以 $a_i\times x$ 的单位功率运行；如果处于第二模式下，它以 $a_i\times z_i + b_i\times(x - z_i)$ 的单位功率运行。

description: 最少需要提供多大的电压（电压需要是整数），才能使所有发动机的总功率大于或等于 $p$？

inputFormat:
第一行输入两个整数 $n$ 和 $p$。

接下来的 $n$ 行，每行包含三个整数 $z_i,a_i,b_i$。

outputFormat: 输出一个整数表示最小电压。


title: [NICA #3] 数计组数

description:
称一个长度为 $n$ 的数组 $a$ 是“数计的”，当且仅当存在一种将其划分成若干个区间的方案，使得每个区间的最小值恰好等于区间长度，或者说存在 $0=x_1<x_2<x_3<\cdots<x_m=n$，满足 $\forall 1\le i<m,\min\limits_{j=x_i+1}^{x_{i+1}}a_j=x_{i+1}-x_i$。

给定正整数集 $S$，询问有多少长度为 $n$ 的数组 $a$ 满足 $a_i\in S$ 且 $a$ 是“数计的”。答案对 $10^9+7$ 取模。

inputFormat:
输入第一行两个整数 $n,m$，$n$ 表示数组的长度，$m$ 表示正整数集 $S$ 的大小。

第二行包含 $m$ 个正整数 $b_1,b_2,\dots,b_m$，表示正整数集 $S$ 中包含的元素。特别的，我们保证 $1\le b_1< b_2<b_3<b_4<\cdots<b_m\le 10^6$。

outputFormat: 输出仅包含一个整数，表示答案对 $10^9+7$ 取模后的结果。


title: [ROIR 2023 Day 2] 美丽序列

background:
翻译自 [ROIR 2023 D2T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。

给定一个整数集合 $A$，其中的元素都在 $1$ 到 $8$ 之间。

一个由 $n$ 个在集合 $A$ 中的整数组成的序列 $[a_1, a_2, \dots , a_n]$，如果对于任意数字 $x$，序列中等于 $x$ 的所有元素彼此之间的距离不小于 $x$，则称这个序列是美丽的。换句话说，如果对于任意数字 $x$ 和任意的 $1 \le i < j \le n$，只要 $a_i = a_j = x$，则不等式 $j - i \ge x$ 必然成立，那么这样的序列 $a$ 就被称为美丽的序列。

例如，当 $A=\{1,2,3,4,5\}$ 时，序列 $[2,3,2,4,3,1,1,4]$ 是美丽的，而 $[1,1,4,5,1,4]$ 不是美丽的，因为这个序列中的两个 $4$ 之间的距离是 $3$。

description: 给定数字 $n$ 和集合 $A$，求出长度为 $n$ 的符合要求的美丽的序列的个数，对 $10^9 + 7$ 取模。

inputFormat:
输入的第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和集合 $A$ 的元素个数。

输入的第二行按升序给出了 $m$ 个互不相同的小于等于 $8$ 的正整数，表示集合 $A$ 的元素。

outputFormat: 输出一个整数，表示美丽序列的数量除以 $10^9 + 7$ 的余数。


title: [语言月赛 202308] 小粉兔处理题解审核志愿者轮换

background:
又到了一周的周日，扶苏又像催命一样开始催促小粉兔处理题解审核志愿者的轮换。但是懒狗小粉兔总是把这项工作拖到第二天凌晨。

【这里有一张内部群聊图，但是因为工作群信息应保密，所以这张图被和谐了】

description:
每周都有若干名题解审核志愿者处理题解审核工作。每周末轮换时，本周的志愿者中会有若干人退出工作，其余人继续下周工作；此外，还有若干新人参与下周工作。

每周末，扶苏会给小粉兔提供如下三组信息：

- 本周的题解审核志愿者名单。
- 本周有哪些题解审核志愿者退出工作。
- 下周有哪些新人参与工作。

因为小粉兔忙着玩原神，所以小粉兔求着扶苏来处理轮换。但是扶苏忙着给洛谷入门赛造题，所以请你来给出下周的题解审核志愿者名单。扶苏承诺，只要你正确地给出名单，她将把小粉兔在头图中给出的辈分分一半给你。

inputFormat:
第一行有三个整数，依次表示本周题解审核志愿者数量 $n$，退出工作的题解审核志愿者数量 $m$，和参与工作的新人数量 $l$。

接下来 $n$ 行，每行一个字符串，表示一个本周题解审核志愿者的用户名。
接下来 $m$ 行，每行一个字符串，表示一个退出下周工作的本周题解审核志愿者的用户名。
接下来 $l$ 行，每行一个字符串，表示一个下周将参与工作的新题解审核志愿者的用户名。

outputFormat:
输出若干行，每行一个字符串。

按字典序从小到大的顺序输出下周所有题解审核志愿者的用户名。

samples:
5 4 1
10circle
yltx
Buffet
Kevin
lihanwen12
yltx
Buffet
Kevin
lihanwen12
PinkieRabbitMinus154


title: [BalkanOI2018] Homecoming

background: 翻译自 BalkanOI 2018 Day1 T2「Homecoming」；由于洛谷远慢于 loj，因此将时间限制从 300ms 调整至 500ms。

description:
有 $N$ 门课程，分别编号为 $0$ 到 $N-1$。如果你 pass 了课程 $i$，你可以拿到 $A _ i$ 美刀。
有 $N$ 本教材，分别编号为 $0$ 到 $N-1$。$i$ 号教材的价格为 $B _ i$ 美刀。
如果你要 pass 课程 $i$，你需要购买编号为 $i, (i+1) \bmod N, (i+2) \bmod N, \cdots, (i+K-1) \bmod N$ 的课本。$K$ 为给定的常数。
你的目的是赚钱而非 pass 所有课程。请求出你最多能赚多少美刀。

## 交互过程

本题只支持 C++ 语言使用函数交互测评。**选手代码不需要也不能包含 `homecoming.h`，也不需要实现 `main` 函数。**

选手程序需要实现如下函数：

```
long long int solve(int N, int K, int *A, int *B);
```

在一次运行中这个函数可能会被调用多次。

## 样例

调用

```
solve(3, 2,
[40, 80, 100],
[140, 0, 20])
```

的返回值为 $60$。

inputFormat: 见「交互过程」。

outputFormat: 见「交互过程」。


title: [BalkanOI2018] Popa

background:
翻译自 BalkanOI 2018 Day2 T2「Popa」

> *"He's an outlaw and he's famous*
> *Andrii Popa the courageous.*
> *Day and night he rides,*
> *He takes his tribute from the main road*
> *And everywhere in the country*
> *The thief catchers are running away as fast as they can"*
>
> *\- ["Andrii Popa", Phoenix](https://music.163.com/song?id=508736536)*

description:
Ghiță 有一个下标从 $0$ 开始的正整数序列 $S$。因为他是喀尔巴阡的国王，所以他想要构造一个节点编号为 $0,1,\ldots ,N-1$ 的二叉树，满足：

- 树的中序遍历按节点编号升序排列。二叉树的中序遍历由以根的左子节点（如果存在）为根形成的子树的中序遍历，根的节点编号和以根的右子节点（如果存在）为根形成的子树的中序遍历顺次连接组成。
- 如果 $x$ 是 $y$ 节点的父亲，那么 $S_x$ 整除 $S_y$。

二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

不幸的是，著名的亡命之徒 Andrii Popa 偷走了序列 $S$，Ghiță 不能直接获取到。但对于任意两个连续的子序列 $[a,b]$ 和 $[c,d]$，他可以使用最先进的技术（他的手机）求出 $\gcd[a,b]$ 是否等于 $\gcd [c,d]$，其中 $\gcd[x,y]$ 指 $S_x,S_{x+1},S_{x+2},\ldots ,S_y$ 的最大公因数。不幸的是，这项技术十分昂贵——如果 Ghiță 使用超过 $Q$ 次，他将会支付一大笔罚金。请帮他在使用这项技术最多 $Q$ 次的情况下构建出他想要的树。保证这是可能的。任何合法的构建方案都可以被接受。

### 交互

本题只支持 C++ 语言使用函数交互。选手代码并不需要也不能包含 `popa.h`。

选手需实现如下函数：

```cpp
int solve(int N, int* Left, int* Right);
```

函数需返回树的根节点，并且将 `Left[i]` 和 `Right[i]` 分别赋值为 $i$ 的左子节点和右子节点。如果节点 $i$ 没有左子节点，则 `Left[i]` 应被赋为 $-1$，如果节点 $i$ 没有右子节点，则 `Right[i]` 应被赋为 $-1$。`Left` 和 `Right` 分别指向两个空间已被分配好且长度恰好为 $N$ 的数组。

函数 `solve` 在一次运行中会被调用最多 $5$ 次。我们建议谨慎使用全局变量。

选手可以调用如下函数（注意，选手须在代码中声明此函数）：

```cpp
int query(int a, int b, int c, int d);
```

这个函数当且仅当 $\gcd[a,b]=\gcd[c,d]$ 时返回 $1$，其中 $0\le a\le b<n,0\le c\le d<N$，否则返回 $0$。

### 样例

例如 $S=[12, 4, 16, 2, 2, 20]$，一组交互过程如下：

| 调用 `solve` | 调用 `query` | 调用 `solve` 之后 |
| :-----------: | :-----------: | :-----------: |
| `solve(6, Left, Right)` |  |  |
|  | `query(0, 1, 3, 5)` 返回 $0$ |  |
|  | `query(4, 5, 1, 3)` 返回 $1$ |  |
|  |  | `solve` 返回值为 $3$；`Left` 指向 $[-1, 0, -1, 1, -1, -1]$；`Right` 指向 $[-1, 2, -1, 4, 5, -1]$ |

样例中，Ghiță 国王想要的树形态如下图所示。

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

inputFormat: 见「交互」。

outputFormat: 见「交互」。


title: [JOISC2022] 监狱

background: JOISC2022 D1T1

description:
在 JOI 王国，安保最严格的地方就是 IOI 监狱。IOI 监狱中有 $N$ 个房间，以 $1,\dots,N$ 编号。其中有 $N-1$ 条通道。第 $i$ $(1\le i\le N-1)$ 条通道双向地连接房间 $A_i$ 和 $B_i$。任意两个房间都可以相互到达。

IOI 监狱中有 $M$ 个囚犯，以 $1,\dots,M$ 编号。第 $j$ $(1\le j\le M)$ 个囚犯的卧室和工作室分别是房间 $S_j,T_j$。一个囚犯可能在另一个囚犯的卧室工作。然而，每个房间最多成为一个囚犯的卧室，一个囚犯的工作室。

一天早上，这 $M$ 个囚犯需要从他们的卧室移动到他们的工作室。典狱长 APIO 先生需要按如下方式指示囚犯移动：
- **指令**：选择一个囚犯，然后命令他从当前所在的房间移动到一个与该房间有直接连边的房间。为了避免囚犯交流，不允许将囚犯移动到有其他囚犯在的房间。

为了尽早开始工作，APIO 先生想知道，是否存在一种给出任意条指令的方案使得每个囚犯以**最短路径**从卧室到达工作室。

请编写一个程序，在给定如上房间、通道和罪犯的所有信息后判断是否存在满足条件的方案。

inputFormat:
每个测试数据包含多组测试用例。

第一行一个整数 $Q$，表示这个测试数据包含 $Q$ 组测试用例。

对于每组测试用例：

第一行一个整数 $N$，表示房间个数。

接下来 $N-1$ 行每行两个整数 $A_i,B_i$ 表示通道连接房间的编号。

接下来一行一个整数 $M$ 表示囚犯个数。

接下来 $M$ 行，每行两个整数 $S_i,T_i$ 表示囚犯的卧室和工作室。

outputFormat: 输出 $Q$ 行，第 $i$ 行表示对于第 $i$ 组测试用例，如果存在一种满足题意的方案，输出 `Yes`，否则输出 `No`。

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

可以通过发送如下指令完成任务：

1. 让囚犯 $2$ 从 $4$ 号房间移动到 $5$ 号房间。
2. 让囚犯 $1$ 从 $3$ 号房间移动到 $4$ 号房间。
3. 让囚犯 $2$ 从 $5$ 号房间移动到 $6$ 号房间。
4. 让囚犯 $2$ 从 $6$ 号房间移动到 $7$ 号房间。
5. 让囚犯 $2$ 从 $7$ 号房间移动到 $8$ 号房间。

这组样例满足所有子任务的限制。

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

这组样例满足子任务 $1,3,4,5,6,7$ 的限制。

**【数据范围】**

对于所有数据，满足：

- $1\leq Q\leq 1000$。
- $1\leq N\leq 120000$。
- $1\leq A_i\lt B_i\leq N$ $(i\in [1,N-1])$。
- $2\leq M\leq N$。
- $1\leq S_i,T_i\leq N$ $(i\in [1,M])$。
- $S_i$ $(i\in[1,M])$ 互不相同。
- $T_i$ $(i\in[1,M])$ 互不相同。
- $S_j \ne T_j$ $(j\in [1, M])$。
- 任意两个房间之间可以通过给定道路互相到达。
- 对于所有测试用例，$N$ 的总和不超过 $120000$。

详细子任务附加限制及分值如下表所示：

|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$A_i=i,B_i=i+1~(i\in[1,N-1])$|$5$|
|$2$|$Q\leq 20, N\leq 250, M=2$|$5$|
|$3$|$Q\leq 20, N\leq 250, M\leq 6$|$16$|
|$4$|$Q\leq 20, N\leq 250, M\leq 100$|$28$|
|$5$|$Q\leq 20, M\leq 500$|$12$|
|$6$|任意两个房间之间都可以通过不超过 $20$ 条道路到达。|$11$|
|$7$|无附加限制|$23$|


title: 「Daily OI Round 1」Block

description:
给定一棵树，节点有颜色，在树上距离为 $2$ 的点连边（仍保留原来的边），求新图中颜色相同且连通的非空点集数量。由于答案可能非常大，您只需输出答案对 $10^9+7$ 取模的值。

点集连通的定义：对于图 $G(V,E)$，$V$ 的一个子集 $V'$ 是连通点集，当且仅当 $G(V',E')$ 是一个连通图，其中边集 $E'=\{(u,v)|(u,v)\in E\land u \in V'\land v\in V'\}$。

inputFormat:
第一行一个正整数 $n$，表示节点个数。

接下来一行 $n$ 个正整数，第 $i$ 个正整数 $c_i$ 表示第 $i$ 个节点的颜色。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示原树有一条 $u$ 到 $v$ 的边。

outputFormat: 一行一个整数，表示答案对 $10^9+7$ 取模的值。


title: [ROIR 2023 Day 2] 石头

background: 翻译自 [ROIR 2023 D2T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。

description:
Bob 面前排列着 $n$ 个黑色石头，从 $1$ 到 $n$ 编号。第 $i$ 个石头上写有一个整数 $a_i$，$n$ 个石头上写的整数构成了一个排列。我们称第 $i$ 个石头的相邻石头为第 $(i-1)$ 个和第 $(i+1)$ 个石头（如果存在的话）。

Bob 按照以下步骤进行 $n$ 次操作：

- 在第一步，选择任意的 $i$（$1\le i\le n$），并将第 $i$ 个石头涂成白色。
- 在第 $2$ 到第 $n$ 步，选取相邻石头中至少有一个白色石头的黑色石头中的 $a_i$ 最小的石头 $j$（即，可能有很多个黑色石头满足它的相邻石头中至少有一个白色石头，但是要选取其中 $a_i$ 最小的那个），并将其涂成白色。

很容易看出，在执行完所有步骤后，$n$ 个石头都是白色的。

Alice 选择了 $q$ 对值 $p_j$ 和 $k_j$。对于每对 $p$ 和 $k$ 的值，她想知道有多少种不同的选择第一步时将哪块石头涂成白色的方式，使得第 $p$ 块石头在第 $k$ 步变成白色。

帮助 Bob 回答 Alice 的 $q$ 个查询。

inputFormat:
第一行包含两个整数 $n$ 和 $q$，分别表示石头的数量和查询的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示写在石头上的整数。

接下来的 $q$ 行，每行包含一对整数 $p_j$ 和 $k_j$。

outputFormat: 对于每个查询，输出一个整数，表示查询的答案。

hint:
下面的样例解释中加粗的数是被涂成白色的。

在第一个样例中：

- 如果第一步选择第 $1$ 块石头：
  - 第 $1$ 步：$[\bold1, \gray4, \gray6, \gray5, \gray2, \gray3]$；
  - 第 $2$ 步：$[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$；
  - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$；
  - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$；
  - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$；
  - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。
- 如果第一步选择第 $2$ 块石头：
  - 第 $1$ 步：$[\gray1, \bold4, \gray6, \gray5, \gray2, \gray3]$；
  - 第 $2$ 步：$[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$；
  - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$；
  - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$；
  - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$；
  - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。
- 如果第一步选择第 $3$ 块石头：
  - 第 $1$ 步：$[\gray1, \gray4, \bold6, \gray5, \gray2, \gray3]$；
  - 第 $2$ 步：$[\gray1, \bold4, \bold6, \gray5, \gray2, \gray3]$；
  - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$；
  - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$；
  - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$；
  - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。
- 如果第一步选择第 $4$ 块石头：
  - 第 $1$ 步：$[\gray1, \gray4, \gray6, \bold5, \gray2, \gray3]$；
  - 第 $2$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \gray3]$；
  - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$；
  - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$；
  - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$；
  - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。
- 如果第一步选择第 $5$ 块石头：
  - 第 $1$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \gray3]$；
  - 第 $2$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$；
  - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$；
  - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$；
  - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$；
  - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。
- 如果第一步选择第 $6$ 块石头：
  - 第 $1$ 步：$[\gray1, \gray4, \gray6, \gray5, \gray2, \bold3]$；
  - 第 $2$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$；
  - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$；
  - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$；
  - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$；
  - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。

本题使用捆绑测试。

| 子任务编号 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $20$ | $n,q\le300$ |
| $2$ | $17$ | $n\le3000$ |
| $3$ | $12$ | $n\le50000,q\le10$ |
| $4$ | $6$ | $a_i$ 的值递增 |
| $5$ | $16$ | 所有 $k_i$ 相等 |
| $6$ | $15$ | 所有 $p_i$ 相等 |
| $7$ | $14$ | 无特殊性质 |

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le q \le 10^5$，$1 \le a_i \le n$ 且所有 $a_i$ 互不相同，$1 \le p_j,k_j \le n$。


title: [NICA #3] 图造构

description:
从一个 $n$ 个点的无向简单图 $S$（无自环无重边）可以通过以下步骤构造出另一个 $n$ 个点的无向简单图 $T$：

1. 初始 $T$ 中只有 $n$ 个点，没有任何边；
2. 选择 $S$ 中两个度数相同的点 $u,v$，然后在 $T$ 中连接 $u$ 和 $v$，同时将 $S$ 中的点 $u$ 以及 $u$ 连出去的边一同删去；
3. 重复步骤 $2$，直到 $S$ 中仅剩下一个点，此时得到的图 $T$ 即为构造出的图。

容易发现同样的一张无向简单图 $S$ 可能可以构造得出不同的图 $T$，并且我们还可以由构造出来的图 $T$ 继续构造图 $T'$ 等等。

现在给定两张点数相同的无向简单图 $S,T$，请你通过至少 $1$ 次且不超过 $3$ 次构造从 $S$ 构造出 $T$，**输入数据保证有解**。如果有多种方案，输出**任意一种**都会被判定为正确。

或者说你要做 $k(1\le k\le 3)$ 次构造 $S\to T_1\to T_2\to \cdots\to T_k$，满足 $T_k=T$。

inputFormat:
输入第一行一个整数 $n$，表示 $S$ 和 $T$ 中点的数量。

输入第二行一个整数 $m_S$，表示 $S$ 中边的数量。

接下来 $m_S$ 行每行两个整数 $u,v$，表示一条 $S$ 中的无向边。保证不存在重边和自环。

输入第 $m_S+3$ 行一个整数 $m_T$，表示 $T$ 中边的数量。

接下来 $m_T$ 行每行两个整数 $u,v$，表示一条 $T$ 中的无向边。同样地，保证不存在重边和自环。

outputFormat:
输出第一行一个整数 $k$，其中 $1\le k\le 3$，表示你使用的构造次数。

接下来你需要输出 $k(n-1)$ 行，每行两个整数 $u,v$，分别表示你这 $k$ 次构造的构造过程。

具体来说，对于某一次特定的构造过程，你需要输出 $n-1$ 行，表示题意中步骤 $2$ 中每次选择的两个点 $u,v$。

hint:
#### 样例 1 解释

初始 $T_1$ 有 $n$ 个点，没有边。

一开始 $S$ 中包含三条边 $(1,2),(2,3),(3,1)$，每个点的度数分别为 $d_1=d_2=d_3=2$。

选择 $1,2$ 这两个度数相同的点，然后将边 $(1,2)$ 加入 $T_1$，删除 $S$ 中的边 $(1,2),(3,1)$ 和点 $1$。

此时 $S$ 中包含一条边 $(2,3)$，每个点的度数分别为 $d_2=d_3=1$。

选择 $2,3$ 这两个度数相同的点，然后将边 $(2,3)$ 加入 $T_1$，删除 $S$ 中的边 $(2,3)$ 和点 $2$，并结束此次构造。

此时得到的 $T_1$ 中有两条边 $(1,2),(2,3)$，有 $T_1=T$ 满足条件。

#### 数据范围

对于所有数据，满足 $2\le n\le 10^5$，$1\le m_S,m_T\le 2\times 10^5$。


title: 「MXOI Round 1」涂色

description:
小 C 正在用彩铅给一张 $n$ 行 $m$ 列的方格纸涂色。初始时，所有方格都是空白的。

他一共要进行 $q$ 次涂色，每次涂色会选取一行或一列，给这一行或这一列的所有方格都添加 $1$ 层颜色。

小 C 喜欢浅色，所以他会在每次涂色结束后，把所有被涂上 $k$ 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。

小 C 想知道，在最终共有多少方格被涂上了颜色。

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

接下来 $q$ 行，每行两个整数 $op,x$。

若 $op=1$，则表示给第 $x$ 行的所有方格都添加 $1$ 层颜色；
若 $op=2$，则表示给第 $x$ 列的所有方格都添加 $1$ 层颜色。

outputFormat: 一个整数，表示在最终共有多少方格被涂上了颜色。

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

第 $1$ 行第 $1$ 列的方格没有被涂上颜色，第 $1$ 行第 $2$ 列的方格被涂上了 $1$ 层颜色，第 $1$ 行第 $3$ 列的方格没有被涂上颜色，第 $1$ 行第 $4$ 列的方格被涂上了 $1$ 层颜色；

第 $2$ 行第 $1$ 列的方格被涂上了 $1$ 层颜色，第 $2$ 行第 $2$ 列的方格被涂上了 $2$ 层颜色，第 $2$ 行第 $3$ 列的方格被涂上了 $1$ 层颜色，第 $2$ 行第 $4$ 列的方格被涂上了 $2$ 层颜色；

第 $3$ 行第 $1$ 列的方格被涂上了 $2$ 层颜色，第 $3$ 行第 $2$ 列的方格的颜色被擦掉了，第 $3$ 行第 $3$ 列的方格被涂上了 $2$ 层颜色，第 $3$ 行第 $4$ 列的方格的颜色也被擦掉了；

最终，共有 $8$ 个方格被涂上了颜色。

#### 【样例 #2】

见附加文件中的 `paint/paint2.in` 与 `paint/paint2.ans`。

该样例满足测试点 $1$ 的限制。

#### 【样例 #3】

见附加文件中的 `paint/paint3.in` 与 `paint/paint3.ans`。

该样例满足测试点 $5$ 的限制。

#### 【样例 #4】

见附加文件中的 `paint/paint4.in` 与 `paint/paint4.ans`。

该样例满足测试点 $20$ 的限制。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le n,m \le 2\times 10^5$，$1 \le k \le q \le 5 \times 10^5$，$op \in \{1,2\}$，保证当 $op=1$ 时 $1 \le x \le n$，当 $op=2$ 时 $1 \le x \le m$。

|测试点编号|$n,m \le$|$q \le$|特殊性质|
|:---:|:---:|:---:|:---:|
|$1\sim4$|$3000$|$3000$|无|
|$5\sim9$|$3000$|$5\times10^5$|无|
|$10\sim12$|$2\times10^5$|$5\times10^5$|A|
|$13\sim16$|$2\times10^5$|$5\times10^5$|B|
|$17\sim20$|$2\times10^5$|$5\times10^5$|无|

特殊性质 A：保证 $op=1$。

特殊性质 B：保证 $k=2$。


title: [ROIR 2023 Day 2] 一个普通的字符串问题

background:
翻译自 [ROIR 2023 D2T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。

如果对于任意长度为 $2$ 的字符串 $u$，字符串 $s$ 中 $u$ 的出现次数与字符串 $t$ 中 $u$ 的出现次数相同，则两个字符串 $s$ 和 $t$ 称为等效字符串。因此，字符串 `aaaba`、`abaaa` 和 `baaab` 彼此等效（字符串 `aa` 出现两次，字符串 `ab` 出现一次，字符串 `ba` 出现一次，字符串 `bb` 不作为子串出现），而字符串 `cff` 和 `ccf` 则不等效。一个字符串和它本身是等效的。

description: 在这个问题中，你将会得到 $Q$ 个由字符 `a`、`b` 和 `c` 组成的字符串，对于每个字符串，需要计算与它等效的由字符 `a`、`b` 和 `c` 组成的非空字符串的数量。由于这个数量可能非常大，所以要求对 $10^9 + 7$ 取余。

inputFormat:
第一行输入一个数 $G$，表示当前子任务的编号。在样例中 $G=0$，本题另设一个分值为 $0$ 的 Subtask 0 来存储样例数据。

第二行输入一个整数 $q$。

接下来 $q$ 行，每行一个字符串。

outputFormat: 对于每个字符串输出一行一个整数表示答案，记得取模 $10^9+7$。


title: [JOI Open 2023] 古代机器 2

background:
**译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T1 「[古代の機械 2](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/ancient2/2023-open-ancient2-statement.pdf) / [Ancient Machine 2](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/ancient2/2023-open-ancient2-statement-en.pdf)」**

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

**在提交本题前请务必仔细阅读以下内容。**

本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。

由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 ```#include "ancient2.h"``` 语句，并将添加以下语句粘贴到代码最开头：

```cpp
int Query(int m, std::vector<int> a, std::vector<int> b);
```

description:
Bitaro 和 Bibako 是挖掘和调查 JOI 王国废墟的考古学家。在废墟中，Bitaro 发现了一块古老的石板，Bibako 发现了一台古老的机器。

从研究结果中，Bitaro 发现石板上写有一个长为 $N$ 的字符串 $S$。字符串中每个字符要么是 `0`，要么是 `1`。然而，他还不知道字符串 $S$ 中的每个字符是什么。

另一方面，从研究结果中，Bibako 弄清了如何使用机器。为了使用它，我们需要将石板放在机器上，输入一个整数 $m$ 和两个整数序列 $a,b$，然后做一次查询。这里整数 $m$ 和整数序列 $a,b$ 需满足如下条件：

- 整数 $m$ 在 $1$ 和 $1\ 002$ 之间（包括两端）。
- 序列 $a$ 和 $b$ 的长度均为 $m$。
- 序列 $a,b$ 中的元素都是 $0$ 和 $m-1$ 之间的整数（包括两端）。

如果我们把石板放在机器上，输入一个整数 $m$ 和两个整数序列 $a,b$，然后做一次查询，机器会按如下方式操作并显示一个整数。

1. 机器对其**内存区域**置 $0$。

2. 机器进行如下的 $N$ 次操作。第 $i+1$ 次（$0\le i\le N-1$）操作按如下方式进行。

   令 $x$ 表示机器内存区域中当前的整数。机器读取字符 $S_i$。这里，$S_i$ 是字符串 $S$ 中的第 $i$ 个字符（下标从 $0$ 开始）。

   - 如果 $S_i$ 是 `0`，机器会将内存区域置为 $a_x$。其中 $a_x$ 是序列 $a$ 中第 $x$ 个元素（下标从 $0$ 开始）。
   - 如果 $S_i$ 是 `1`，机器会将内存区域置为 $b_x$。其中 $b_x$ 是序列 $b$ 中第 $x$ 个元素（下标从 $0$ 开始）。

3. 这个机器将展示内存区域中最终置为的整数。

使用这个机器，Bitaro 想要确定石板上写的字符串。然而，因为这个机器十分脆弱，查询的次数不能超过 $1\ 000$。此外，输入机器的整数 $m$ 的最大值需要越小越好。

使用这个机器，写一个程序确定石板上写的字符串。

**【实现细节】**

你需要在程序一开始使用预处理指令 `#include` 引入库 `ancient2.h`。它应当实现如下函数。

- `std::string Solve(int N)`

  这个函数在每组测试数据中仅被调用一次。这个函数需要返回和石板上所写的字符串 $S$ 相同的字符串。

  - 参数 `N` 表示石板上写的字符串 $S$ 的长度 $N$。
  - 这个函数需要返回一个长度为 $N$ 的字符串。如果字符串长度不为 $N$，你的程序会被判为 **Wrong Answer [1]**。
  - 返回值中每个字符要么是 `0`，要么是 `1`。如果该条件不满足，你的程序会被判为 **Wrong Answer [2]**。
  - 返回值应当与石板上写的字符串 $S$ 相同。如果该条件不满足，你的程序会被判为 **Wrong Answer [3]**。

  你的程序可以调用如下函数。

  - `int Query(int m, std::vector<int> a, std::vector<int> b)`

    使用这个函数，你的程序可以做一次查询。

    - 参数 `m` 是输入机器的整数 $m$。
    - 参数 `a`，`b` 是输入机器的两个整数序列 $a,b$。
    - 返回值是当我们把石板放在机器上，并输入上述整数和序列，做一次查询是机器最后显示的整数。
    - 参数 `m` 应当在 $1$ 和 $1\ 002$ 之间（包括两端）。如果该条件不满足，你的程序会被判为 **Wrong Answer [4]**。
    - 序列 `a` 和 `b` 的长度均应等于 $m$。如果该条件不满足，你的程序会被判为 **Wrong Answer [5]**。
    - 序列 `a` 和 `b` 中元素均应在 $0$ 和 $m-1$ 之间（包括两端）。如果该条件不满足，你的程序会被判为 **Wrong Answer [6]**。
    - 函数 `Query` 的调用次数不能超过 $1\ 000$ 次。如果超过 $1\ 000$ 次，你的程序会被判为 **Wrong Answer [7]**。

**【注意事项】**

- 你的程序可以实现其它函数供内部使用，或者使用全局变量。
- 你的程序禁止使用标准输入输出。你的程序禁止通过任何方式与其他文件通信。然而，你的程序可以将调试信息输出到标准错误输出。

**【编译和测试运行】**

你可以在「文件」中的「附加文件」下载样例 grader 来测试你的程序。「附加文件」中也包含一份你的程序的样例源程序。

样例交互器是文件 `grader.cpp`。为了测试你的程序，你需要将 `grader.cpp`，`ancient2.cpp` 和 `ancient2.h` 三个文件放在同一文件夹下，并且执行如下命令编译你的程序。你也可以运行 `compile.sh` 来编译你的程序。

```shell
g++ -std=gnu++17 -O2 -o grader grader.cpp ancient2.cpp
```

当编译成功时，会生成一个可执行文件 `grader`。

请注意，实际的交互器和样例不同。样例交互器会作为单进程运行，即它会从标准输入中读取输入数据，并输出结果到标准输出。

inputFormat:
第一行一个整数 $N$。

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

outputFormat:
样例交互器会输出如下内容到标准输出。

- 如果你的程序被判为正确，它会输出 `Query` 函数中参数 `m` 的最大值，如 `Accepted: 22`。然而，如果你的程序没有调用 `Query` 函数并被判为正确，它会输出 `Accepted: 0`。
- 如果你的程序被判为任一类的答案错误，样例交互器会输出其类别，如 `Wrong Answer [4]`。

如果程序满足多种答案错误的类别，样例交互器只会输出其中一个。

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

样例函数调用如下。

| 对 `Solve` 的调用 |   返回值   |           对 `Query` 的调用            |    返回值     |
| :---------------: | :--------: | :------------------------------------: | :-----------: |
|    `Solve(3)`     |            |                              |               |
|                   |   | `Query(4, [3, 3, 2, 2], [2, 2, 1, 0])` |      `3`      |
|          |            |       `Query(2, [0, 1], [1, 0])`       |      `0`      |
|                   |   |          `Query(1, [0], [0])`          | `0`  |
|          |            |    `Query(3, [1, 1, 1], [1, 1, 1])`    |      `1`      |
|                   |  `"110"`   |                                        |   |

假设写在石板上的字符串 $S$ 是 `110`。如果我们把石板放在机器上，输入 $(m,a,b)=(4,[3,3,2,2],[2,2,1,0])$ 并做一次查询，机器将按如下方式操作。

1. 机器将内存区域置为 $0$。
2. 对于第一次操作，因为 $S_0$ 是 `1`，机器会将内存区域置为 $b_0$，即 $2$。
3. 对于第二次操作，因为 $S_1$ 是 `1`，机器会将内存区域置为 $b_2$，即 $1$。
4. 对于第三次操作，因为 $S_2$ 是 `0`，机器会将内存区域置为 $a_1$，即 $3$。
5. 因为最终内存区域被置为的整数是 $3$，所以机器显示 $3$。

注意这组样例输入不满足限制 $N=1\ 000$。在文件中，`sample-02.txt` 满足这个限制。

**【数据范围】**

对于全部数据，满足：

- $N=1\ 000$
- $S$ 是一个长为 $N$ 的字符串
- $S$ 中的每个字符要么是 `0`，要么是 `1`

对于每组数据，实际的交互器 **不是**适应性的。这意味着交互器在开始时答案就已经确定了。

如果你的程序在任意一组数据上被判为任意一种答案错误，在本题你将获得 $0$ 分。

如果你的程序在所有数据上都被判为正确，你的分数由 $M$ 确定，其中 $M$ 是所有数据的 `Query` 函数中参数 `m` 的最大值。然而，如果你的程序没有调用 `Query` 函数并且被判为正确，你的分数由 $M=0$ 确定。

- 如果 $103\le M\le 1\ 002$，你的得分为 $10+\lfloor \frac{(1002-M)^2}{9000}\rfloor$
- 如果 $0\le M\le 102$，你将获得 $100$ 分。

这里 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。


title: [JOI Open 2023] 细胞自动机

background: **译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T2 「[セルオートマトン](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement.pdf) / [Cell Automaton](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement-en.pdf)」**

description:
我们有一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。

有一个单元格是坐标原点。令 $(x,y)$ 表示表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个单元格。类似地，向下移动 $a$ 个单元格意味着向上移动 $-a$ 个单元格。

在时刻 $0$，单元格 $(X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)$ 是黑色的，其余单元格是白色的。

对于 $t=0,1,2,\ldots$，根据单元格在 $t$ 时刻的颜色，单元格在 $t+1$ 时刻的颜色按如下方法确定：

- 如果在时刻 $t$ 时单元格是黑色，那么在时刻 $t+1$ 这个单元格变为灰色。
- 如果在时刻 $t$ 时单元格是灰色，那么在时刻 $t+1$ 这个单元格变为白色。
- 如果在时刻 $t$ 时单元格是白色，并且与其相邻的四个单元格（即，与其共边的四个单元格）中至少有一个在时刻 $t$ 是黑色的，那么在时刻 $t+1$ 这个单元格变为黑色。否则，它将在时刻 $t+1$ 保持白色。

你有 $Q$ 次查询。对于第 $j$ 个查询，你应该回答在时刻 $T_j$ 时有多少黑色单元格。

给定在时刻 $0$ 时的单元格颜色信息和查询，写一个程序回答询问。

inputFormat:
第一行两个整数 $N,Q$。

接下来 $N$ 行，每行两个整数 $X_i,Y_i$。

接下来 $Q$ 行，每行一个整数 $T_j$。

outputFormat: 输出 $Q$ 行，每行一个整数，表示在时刻 $T_j$ 时有多少黑色单元格。

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

下图展示了在时刻 $0$ 时的单元格情况。因为有 $2$ 个黑色单元格，所以第一个询问的回答是 $2$。

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

下图展示了在时刻 $1$ 时的单元格情况。因为有 $8$ 个黑色单元格，所以第二个询问的回答是 $8$。

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

下图展示了在时刻 $2$ 时的单元格情况。因为有 $12$ 个黑色单元格，所以第三个询问的回答是 $12$。

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

这组样例满足子任务 $1,2,6,7$ 的限制。

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

这组样例满足子任务 $1,2,4,6,7$ 的限制。

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

这组样例满足子任务 $1,2,6,7$ 的限制。

**【数据范围】**

对于所有数据，满足：

- $1\le N\le 10^5$
- $1\le Q\le 5\times 10^5$
- $|X_i|,|Y_i|\le 10^9$
- $(X_i,Y_i)\neq (X_j,Y_j)\ (1\le i < j\le N)$
- $0\le T_j\le 10^9$
- $T_j<T_{j+1}$

详细子任务附加限制及分值如下表所示。

| 子任务 |               附加限制                | 分值 |
| :----: | :-----------------------------------: | :--: |
|  $1$   |     $\lvert X_i\rvert ,\lvert Y_i\rvert \le 50,T_j\le 50$     | $4$  |
|  $2$   | $\lvert X_i\rvert ,\lvert Y_i\rvert \le 1\ 000,T_j\le 1\ 000$ | $12$ |
|  $3$   |             $X_i=Y_i,Q=1$             | $8$  |
|  $4$   |               $X_i=Y_i$               | $8$  |
|  $5$   |           $N\le 2\ 000,Q=1$           | $17$ |
|  $6$   |             $N\le 2\ 000$             | $25$ |
|  $7$   |              无附加限制               | $26$ |


title: [JOI Open 2023] 花园

background: **译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T3 「[庭園](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/garden/2023-open-garden-statement.pdf) / [Garden](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/garden/2023-open-garden-statement-en.pdf)」**

description:
JOI 王国是一个神秘的王国，疆域辽阔无边。JOI 君是 JOI 国国王，他在计划分割疆域的一部分来建造他的花园。

JOI 网络可以考虑成一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。有一个单元格是坐标原点。令 $(x,y)$ 表示表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个单元格。类似地，向下移动 $a$ 个单元格意味着向上移动 $-a$ 个单元格。

在领土内有一些艺术品。这些艺术品根据放置在领土上的方式分为 **A 类**和 **B 类**。

- 有 $N$ 种 A 类艺术品。第 $i$ 种艺术品（$1\le i\le N$）放在每个形如 $(P_i+kD,Q_i+lD)$ 的单元格上，其中 $k,l$ 为整数。
- 有 $M$ 种 B 类艺术品。第 $j$ 种艺术品（$1\le j\le M$）放在每个形如 $(R_j+kD,y)$（其中 $k,y$ 为整数）或 $(x,S_j+lD)$（其中 $l,x$ 为整数）的单元格上。

注意一个单元格中可能包含多种不同类别的艺术品。

JOI 君计划在网格中选择一个矩形区域建造花园。换句话说，他会选择四个整数 $a,b,c,d$。然后形如 $(x,y)$ 的单元格将构成 JOI 君的花园，其中 $x,y$ 是满足 $a\le x\le b,c\le y\le d$ 的整数。因为 JOI 君喜欢看到多种艺术品，对于任意 $N+M$ 种艺术品中的一种，JOI 君的花园中需要至少包含这种艺术品中的一个。另一方面，如果 JOI 君计划要建的花园过大，JOI 国的居民就会生气。因此，JOI 君希望最小化花园包含的单元格数使得满足上述条件。

给定艺术品的信息，写一个程序计算 JOI 君的花园所包含的最小单元格数。

inputFormat:
第一行三个整数 $N,M,D$。

接下来 $N$ 行，每行两个整数 $P_i,Q_i$。

接下来 $M$ 行，每行两个整数 $R_j,S_j$。

outputFormat: 输出一行一个整数，表示 JOI 君的花园所包含的最小单元格数。

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

下图展示了 JOI 国领土中的满足 $0\le x<10,0\le y<10$ 的单元格 $(x,y)$。

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

在本图中，圆形和菱形分别表示 A 类和 B 类艺术品。圆形或菱形中的整数表示艺术品的种数。如果 JOI 君选择 $a=1,b=2,c=2,d=5$，JOI 君的花园就是黑色矩形区域。这种情况下，对于这三种艺术品，JOI 君的花园中至少会有每种中的一个。花园所占单元格数为 $8$。因为没有比这个花园占地更小且满足条件的花园了，因此输出 $8$。

这组样例满足所有子任务的限制。

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

这组样例满足子任务 $1,4,5,6$ 的限制。

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

这组样例满足子任务 $1,5,6$ 的限制。

**【数据范围】**

对于所有数据，满足：

- $N,M\ge 1$
- $N+M\le 5\times 10^5$
- $1\le D\le 5\ 000$
- $0\le P_i,Q_i,R_j,S_j<D$

详细子任务附加限制及分值如下表所示。

| 子任务 |        附加限制        | 分值 |
| :----: | :--------------------: | :--: |
|  $1$   |        $M\le 8$        | $15$ |
|  $2$   | $D\le 10,N+M\le 5000$  | $6$  |
|  $3$   | $D\le 50,N+M\le 5000$  | $8$  |
|  $4$   | $D\le 100,N+M\le 5000$ | $16$ |
|  $5$   |     $N+M\le 5000$      | $30$ |
|  $6$   |       无附加限制       | $25$ |


title: 「AWOI Round 2 B」树学

background: HR 刚做完一个简单而又靓丽的题目，它想来试试这道题，可是它太蒻了，不会做，您能帮帮它吗？

description:
构造一个长度为 $n$ 的小写字母串，要求和给定的长度为 $n$ 的小写字母串 $s$ 的相似度在 $[l,r]$ 范围内。

定义两个长度都为 $n$ 的字符串 $a,b$ 的相似度为 $\sum^{n}_{i=1}[a_i=b_i]$。

您需要使构造出的字符串的字典序尽量小。

inputFormat:
第一行三个正整数 $n,l,r$。

接下来一行一个字符串，表示给定的小写字母串 $s$。

outputFormat: 输出一行一个字符串，表示您构造的字典序最小的可行字符串。


title: 「MXOI Round 2」排名

description:
小 C 有一个长度为 $n$ 的数组 $a$。

小 C 定义，$f(i)$ 为 $a_i$ 的前排名，其中 $f(i)$ 等于数组 $a$ 中大于 $a_i$ 的元素个数加 $1$。

小 C 还定义，$g(i)$ 为 $a_i$ 的后排名，其中 $g(i)$ 等于数组 $a$ 中大于等于 $a_i$ 的元素个数。

每次操作，小 C 需要选择一个不大于 $n$ 的正整数 $t$，并将 $a_t$ 的值增加 $1$。

小 C 想知道，对于每一个 $1 \le i \le n$，想要使 $f(i) \le k \le g(i)$，最少需要进行多少次操作？

可以证明一定存在一种操作方案使得 $f(i) \le k \le g(i)$。

inputFormat:
第一行三个整数 $c,n,k$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

第二行 $n$ 个整数，表示给定的数组 $a$。

outputFormat: 共 $n$ 行，每行一个整数，其中第 $i$ 行的整数表示想要使 $f(i) \le k \le g(i)$ 所至少需要进行的操作数。

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

当 $i=1$ 时，小 C 可以选择 $t=1$ 并进行 $3$ 次操作。此时 $f(i)=2$，$g(i)=4$，满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $3$ 次操作。

当 $i=4$ 时，小 C 可以选择 $t=3$ 进行 $1$ 次操作，再选择 $t=6$ 进行 $1$ 次操作。此时 $f(i)=1$，$g(i)=3$，满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $2$ 次操作。

#### 【样例 #2】

见附加文件中的 `rank/rank2.in` 与 `rank/rank2.ans`。

该样例满足测试点 $7$ 的限制。

#### 【样例 #3】

见附加文件中的 `rank/rank3.in` 与 `rank/rank3.ans`。

该样例满足测试点 $20$ 的限制。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le k \le n \le 5 \times 10^5$，$1 \le a_i \le 10^9$。

|测试点编号|$n \le$|$a_i \le$|特殊性质|
|:---:|:---:|:---:|:---:|
|$1\sim6$|$2000$|$10^9$|A|
|$7\sim10$|$2000$|$10^9$|无|
|$11\sim14$|$5\times10^5$|$10^9$|B|
|$15\sim20$|$5\times10^5$|$10^9$|无|

特殊性质 A：保证对于所有的 $1 \le i \lt n$，都有 $a_i \ge a_{i+1}$。

特殊性质 B：保证 $k=1$。


title: 「HOI R1」杂赛选比

background: 你说得对，但是小 $\iiint$ 在打 CF 时将 Earn or Unlock 错看成了下面的鬼畜样子，痛失 2h 遗憾离场，希望大家引以为戒。

description:
给定一个长度为 $n$ 的数组 $a$，初始只有 $a_1$ 是已被解锁的。现在有一个整数 $i$，初始值为 $1$。现在小 $\iiint$ 在对这个数组进行一个游戏：

- 如果 $a_i$ 未被解锁，游戏结束。
- 否则他可以将 $a_{i+1\sim i+a_i}$ 设置成已被解锁的，或是获得 $a_i$ 个金币（如果 $a_i=0$ 则无法解锁任何元素），然后将 $i$ 加 $1$。

请你求出游戏结束后你能获得的最大金币数量。

inputFormat:
**本题有多组测试数据。**

第一行一个整数 $T$，表示测试数据组数。

对于每一组数据，第一行一个正整数 $n$。

接下来一行 $n$ 个非负整数 $a_{1\sim n}$。

outputFormat: 对于每一组数据，一行一个数，表示答案。


title: 「Daily OI Round 1」Xor

description:
给定一个长度为 $n$ 的序列，一共有 $q$ 次询问，每次询问给定正整数 $x$，然后依次执行以下操作：

- 把序列中所有数异或上 $x$。
- 求长度最大的区间 $[l,r]$（$l,r$ 是非负整数）满足区间中的每个整数在序列中出现，区间的长度定义为 $r-l+1$。

**注意，在每个询问过后序列是发生变化的。**

**几个需要说明的地方：**

1. “区间”指的是数的区间，比如区间 $[1,3]$ 中的整数有 $1,2,3$，与序列无关。
2. “序列”指的是修改后的序列，同时不包括之前的序列。

inputFormat:
第一行两个正整数 $n,q$ 表示序列长度和询问个数。

第二行 $n$ 个正整数 $a_i$ 表示一开始的序列。

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

outputFormat: 输出 $q$ 行，一行一个整数表示每个询问的答案。


title: 「FSLOI Round I」迷雾

background:
**[English statement.](https://www.luogu.com.cn/problem/T500989) You must submit your code at the Chinese version of the statement.**

小 F 来到了迷雾之森。

description:
整个迷雾之森可以由一个 $n \times m$ 的矩阵表示，`X` 代表有迷雾的地块，`.` 代表空地。从上到下给每行标号为 $1,2,\cdots,n$，从左到右给每列标号为 $1,2,\cdots,m$。除此之外，还会给定一个迷雾系数 $k$。

小 F 进行了 $q$ 次移动。第 $i$ 次移动由一个字符 $c_i$，两个数字 $a_i,b_i$ 描述，更具体地说：

- $c_i$ 为 `U` 时，向上走 $a_i$ 步。
- $c_i$ 为 `D` 时，向下走 $a_i$ 步。
- $c_i$ 为 `L` 时，向左走 $a_i$ 步。
- $c_i$ 为 `R` 时，向右走 $a_i$ 步。

当然，小 F 不可以走出这个 $ n \times m $ 的范围。换句话说，若走到边界处，立即结束此次移动。

若第 $i$ 次移动**结束**后小 F 停留在有迷雾的地块上，则小 F 会对从 $i+k$ 开始，之后每 $k$ 次移动的 $c$ 进行一次修改，一共修改 $b_i$ 个移动。也就是说，小 F 会对 $c_{i+k},c_{i+2\times k},\cdots,c_{i+b_i \times k}$ 进行一次**修改**（保证 $i+b_i\times k \leq q$）。若 $b_i=0$ 则相当于不做修改。**注意所有操作的 $k$ 是一样的**。

修改 $c_x$ 即为按照以下规则替换 $c_x$：

- 若 $c_x$ 为 `U`，则替换为 `D`。
- 若 $c_x$ 为 `D`，则替换为 `U`。
- 若 $c_x$ 为 `R`，则替换为 `L`。
- 若 $c_x$ 为 `L`，则替换为 `R`。

初始时小 F 在点 $(1,1)$ 处，请输出 $q$ 次移动后小 F 所在的位置 $(x,y)$。

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

接下来 $n$ 行，每行一个长度为 $m$，由 `.` 和 `X` 构成的字符串，描述整个迷雾之森。

接下来 $q$ 行，每行先是一个字符 $c_i$，然后依次是两个整数 $a_i,b_i$，描述每次移动。

outputFormat:
共一行。

两个整数 $x,y$，表示小 F 最终的位置。

samples:
10 10 8 2
XX.XX.X...
XXX..XXX.X
XXX.X.XXXX
XXXXXXX.X.
.XX...XX.X
.XXX.X.X.X
...XXX.XXX
XX...XX...
X..XX....X
XXXXX...XX
U 2 1
L 1 3
R 3 1
L 1 2
D 2 1
R 5 1
L 4 0
D 3 0

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

小 F 的位置变化如下：

$(1,1) \rightarrow (2,1) \rightarrow (2,2)\rightarrow (1,2) \rightarrow (1,3)$

序列 $c$ 的变化如下：

$ \lbrace \texttt{D,R,D,L} \rbrace \rightarrow \lbrace \texttt{D,R,D,L} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace$

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

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

对于 $100 \%$ 的数据，保证：
- $1 \leq n,m \leq 500$
- $1 \leq k \leq 20$
- $1\leq q \leq 2 \times 10^5$
- $1 \leq a_i,b_i \leq 10^6$
- $c_i$ 为 `L`，`R`，`U`，`D` 四个字符中的一个。

|子任务|分值|特殊性质|
|:-----:|:-----:|:-----:|
|$1$|$5$|$q=1$|
|$2$|$15$|$n,m,q\leq 100$|
|$3$|$20$|$k=1$|
|$4$|$30$|$n=1$|
|$5$|$30$|无|


title: [JOISC2022] 京都观光

background: JOISC2022 D1T2

description:
京都是世界级的观光圣地，它也被称为网格城市。你来到了京都观光，并且你计划步行游览一个著名的景点。本题中，我们考虑如下的简化问题。

在城市中，有 $H$ 条东西方向的街道和 $W$ 条南北方向的街道，因此城市是一个 $(H-1)\times(W-1)$ 的网格。从北数第 $i$ 条街道和从西数第 $j$ 条街道的交叉点记作路口 $(i,j)$。

不同的街道可能有不同的材质、宽度和拥挤程度，因此你的步行速度有可能不同。对于每条街道，你的步行速度如下：

- 如果你在从北数第 $i$ 条街道上行走单位长度，需要 $A_i$ 秒。即从路口 $(i,c)~\left(i\in[1,H],c\in[1,W)\right)$ 走到路口 $(i,c+1)$ 需要 $A_i$ 秒。

- 如果你在从西数第 $j$ 条街道上行走单位长度，需要 $B_j$ 秒。即从路口 $(c,j)~\left(c\in[1,H),j\in[1,W]\right)$ 走到路口 $(c+1,j)$ 需要 $B_j$ 秒。

你现在在路口 $(1,1)$，你想前往 $(H,W)$，你必须沿着街道行走，并且你不希望走远路，即你不会向北或向西走。

你希望尽早到达目的地，请你求出，在给定的条件下，从路口 $(1,1)$ 前往路口 $(H,W)$ 所需的最少时间。

inputFormat:
第一行两个整数 $H,W$ 表示街道条数。

第二行 $H$ 个整数，第 $i$ 个整数 $A_i$ 表示从北数第 $i$ 条东西方向街道的步行速度。

第三行 $W$ 个整数，第 $i$ 个整数 $B_i$ 表示从西数第 $i$ 条南北方向街道的步行速度。

outputFormat: 一行一个整数，表示所需的最小步行时间。

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

有两条从 $(1,1)$ 到 $(2,2)$ 的路线：

1. $(1,1)\rightarrow(1,2)\rightarrow(2,2)$，所需时间为 $1+5=6$ 秒。
2. $(1,1)\rightarrow(2,1)\rightarrow(2,2)$，所需时间为 $2+3=5$ 秒。

因此最少花费时间为 $5$ 秒。

这个样例满足所有子任务的限制。

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

最优路线如下图：

![样例解释](https://cdn.luogu.com.cn/upload/image_hosting/mqsalajm.png)

这个样例满足所有子任务的限制。

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

这个样例满足子任务 $1,3$ 的限制。

**【数据范围】**

对于所有数据，满足：

- $2\leq H,W\leq 100000$。
- $1\leq A_i\leq 10^9$ $(i\in[1,H])$。
- $1\leq B_i\leq 10^9$ $(i\in[1,W])$。

详细子任务附加限制及分值如下表所示：

|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$H,W\leq 1000$|$10$|
|$2$|$A_i\leq 1000, B_i\leq 1000$|$30$|
|$3$|无附加限制|$60$|


title: 下次再见

background:
> 在逝去的季节中 遗失的宝藏
>
> 是缺失一角的 珍贵拼图
>
> 就像白雪在街道上 温柔地堆积的样子
>
> 也将回忆相簿的空白 全部填满吧

description:
有一首由 $n$ 个圆圈组成的乐曲．玩家会 **等概率随机选定** $1 \sim n$ 中的一个位置开始游玩，顺序点击那个位置和之后的所有圆圈来完成乐曲的演奏．

对于每个圆圈的点击精准度存在四种判定，分别是 $\texttt{GREAT,OK,MEH,MISS}$．

存在一种机制：当连续 $K$ 次 $\texttt{MISS}$ 后，玩家会强制退出游戏；否则玩家会一直游玩直到点击完所有圆圈．

现在给出对于每个圆圈，玩家达成每一种判定的概率：对于第 $i$ 个圆圈，判定 $\texttt{GREAT},\texttt{OK},\texttt{MEH},\texttt{MISS}$ 的概率分别为 $P_{i,0}/100,\ P_{i,1}/100,\ P_{i,2}/100,\ P_{i,3}/100$．保证 $P_{i,0}+P_{i,1}+P_{i,2}+P_{i,3}=100$．

得分是衡量整段演奏的指标，它的计算方式是，假设整段演奏中出现了 $a$ 次 $\texttt{GREAT}$，$b$ 次 $\texttt{OK}$，$c$ 次 $\texttt{MEH}$，$d$ 次 $\texttt{MISS}$，那么演奏的得分为 $300a+100b+50c$．

你需要回答玩家得分的期望．

说明：如果强制退出游戏，那么计算得分时，整段演奏包括从开始的点击到最后一次判定 $\texttt{MISS}$ 的点击为止所有的点击．

在部分数据大小范围较大的测试点上，为了减小输入输出的交互量，我们采用了不同的输入方式．您需要在您的 c++ 代码中加入题目附件中提供的数据生成器．建议在阅读接下来的内容前先浏览一下生成器中提供的函数名称，这可以帮助您更好地理解输入格式．

inputFormat:
第一行包含两个整数 $Type,seed$．

当 $Type=1$ 的时候，您需要在读入 $seed$ 之后调用 `Ge.init(seed)` 来设置数据生成器的种子．否则您可以忽视 $seed$．

第二行包括两个整数 $n,K$．

接下来分两种情况：

- $Type=0$．接下来 $n$ 行，每行包括 $4$ 个整数，表示 $P_{i,0}\ P_{i,1}\ P_{i,2}\ P_{i,3}$．

- $Type=1$．接下来没有任何输入．您第 $i$ 次调用 ``Ge.get(a,b,c,d)`` 之后，$a,b,c,d$ 的值分别为 $P_{i,0}\ P_{i,1}\ P_{i,2}\ P_{i,3}$．

outputFormat:
一行一个整数，表示答案 $\bmod\ 998244353$．

说明：可以证明，答案能够表示为 $p/q$．您需要输出 $q$ 在 $\bmod\ 998244353$ 意义下的逆元和 $p$ 的乘积对 $998244353$ 取模后的结果．


title: 「NnOI R2-T1」Khronostasis Katharsis

description:
$n$ 个气球被栓在水平地面上，初始高度均为 $0$ 米，初始时刻记为第 $0$ 秒。

每个气球被剪断栓绳后会匀速上升，第 $i$ 个气球每秒上升 $v_i$ 米。

现在已知第 $i$ 个气球会在第 $t_i$ 秒时被剪断栓绳，问第 $T$ 秒时最高的气球中编号最小的一个的编号。

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

接下来 $n$ 行，第 $i$ 行两个整数 $v_i,t_i$。

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

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

第 10 秒时，五个气球的高度分别为 9,14,9,30,21 米。

**【数据范围】**

对于 $100\%$ 的数据，保证 $1\le n,v_i\le 10^5$，$0\le t_i\le T\le 10^4$。

**提示：本题开启捆绑测试。**

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c}
\textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1& n \le 1000 & 33 \r
\textsf2& v_i\ 相等 & 10 \r
\textsf3& t_i \ 相等 & 10 \r
\textsf4& 无特殊限制 & 47 \r
\end{array}
$$

### 题目来源

|项目|人员|
|:-:|:-:|
|idea|EstasTonne|
|data|EstasTonne|
|check|船酱魔王|
|solution|EstasTonne|


title: 「PHOI-1」斗之魂

background:
**本题数据已加强。**

小 X 忙了一天，于是打起了一款叫斗之魂的游戏。

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

description:
小 X 要击败 $n$ 个 BOSS，他可以选择以下两种击败 BOSS 的方式：

1. 独自一人击败第 $i$ 个 BOSS 并获得 $k_{i,0}$ 块稀有金属，且保证 $k_{i,0}=k_{i,1}=k_{i,2}$。
2. 和小 Y 一起击败第 $i$ 个 BOSS ，小 X 理应获得 $k_{i,1}$ 块稀有金属，小 Y 理应获得 $k_{i,2}$ 块稀有金属，但是 BOSS 本身实力并没有因为人数的改变而改变，击败难度相对要简单一点，所以系统判定两人实际各获得 $k_{i,0}$ 块稀有金属，其中保证 $\dfrac{1}{k_{i,0}}=\dfrac{1}{k_{i,1}}+\dfrac{1}{k_{i,2}}$。

小 X 已经计划好用第 $b_i$ 种方式击败第 $i$ 个 BOSS，但是考虑到某些因素，小 X 有 $q$ 次询问，每次询问给定一个正整数 $m$，为小 X 击败完所有 BOSS 后获得的稀有金属总数，已知 $k_{i,0},k_{i,1},k_{i,2}$ 均为正整数，求每次询问后所有可能的 $k$ 的值的方案数，两种方案不同当且仅当至少存在一个 $k$ 的值不同，由于这个答案可能很大，你只需要输出它对 $998244353$ 取模后的结果。

inputFormat:
第一行有两个整数 $n$ 和 $q$，分别表示 BOSS 个数和小 X 的询问次数。

第二行有 $n$ 个正整数 $b_i$，表示小 X 用 $b_i$ 种方式击败第 $i$ 个 BOSS。

接下来的 $q$ 行中每行有一个整数 $m$，为该次询问中小 X 击败完所有 BOSS 后获得的稀有金属总数。

outputFormat: 输出共 $q$ 行，第 $i$ 行输出一个答案为当小 X 击败完所有 BOSS 后获得的稀有金属总数为 $m$ 时，所有可能的 $k$ 的值的方案数并对它取模 $998244353$ 后的结果。