title: 「Wdoi-2」幻胧月睨

background:
**Problem Number:** $\textit{39}$

**背景与题目无关，选手可以直接看下面的「简要题意」。**

那是在竹取物语之后的故事了，幻想乡距离与现实隔绝也已经过去了百年时光。

地上人向月球发起了侵略战争之后，一只名叫**铃仙**的月兔舍弃了同伴，死里逃生，逃到了在幻想乡内的永远亭，来到了辉夜与永琳的身边，生活得安稳而舒适。

又过了数十年，铃仙接收到了来自月球的使唤，被要求强制返回月球。辉夜与永琳商量了下，决定不将铃仙交还予月球。但为了避免造成麻烦，辉夜与永琳决定将满月消失在地上，只留下一轮虚假的月亮。

-----

为了方便调查异变，八云紫运用自己的能力，将整个幻想乡变成了永夜。

被穿梭回异变发生当时的四组主角，共八人。除了依然留有记忆，可以来回穿梭在虚与实的境界的八云紫之外，其他的人缺乏了记忆，重新开始踏上夺回幻想乡的满月的征途。

在慧音的指引之下，她们来到了迷途竹林，在她们的面前，是一只名叫铃仙的月兔。

description:
### 简要题意

给定一个长度为 $n$ 的 01 串 $b$，要求构造一个 $n$ 阶排列 $a$，满足，对于 $a_i(2\le i\le n)$，记 $m_i=\max_{j=1}^{i-1}\{a_j\}$，则：
  - 若 $b_i=1$，则 $a_i>m_i$;
  - 否则 $a_i<m_i$。

可以证明，总存在一个数列 $a$ 满足以上条件。

**如果有多组解，输出任意一种。**

同时注意到 $b_1$ 的取值是任意的，对数列 $a$ 没有影响。

### 原始题意

铃仙拥有操纵狂气程度的能力，换而言之，就是操纵物体的波长、振幅以及相位。这种能力为主角制造了种种障碍——例如操纵光波，会让弹幕虚虚实实，甚至会出现虚假的自我，对躲避弹幕造成极大的干扰。

以符卡「幻胧月睨」为例。「幻胧月睨」中一共有 $n$ 个弹幕，每个弹幕都会有一个相位，相位非 $0$ 即 $1$。这些弹幕的相位会构成一个长度为 $n$ 的数列 $\{b_i\}$。

铃仙会操纵这些弹幕的相位，将其变得千奇百怪。具体而言，被操纵了之后的弹幕的相位是一个长度为 $n$ 的**排列** $\{a_i\}$，即 $1 \sim n$ 的数字都会**不重不漏**地出现在这个序列之中。

为了加大主角躲避弹幕的难度，铃仙会设置一个阈值。对于每一个元素 $a_i$，阈值是其**前缀**的**最大**值，即 $a_1,a_2,\dots,a_{i-1}$ 中的最大值。若原来的第 $i$ 个弹幕的相位为 $1$，则被操纵后的弹幕的相位要**大于**这个阈值，否则被操纵后的弹幕的相位要**小于**这个阈值。

显然的是，根据铃仙的操纵规则，无论原本的弹幕的相位如何，都是存在可能的操纵方案的。由于主角们失去了记忆，而找回月亮的时间已经所剩不多了，而且弹幕战对时间的把控要求极高。她们找到了你，希望你能够对铃仙原本的弹幕相位，给出**任意一种**操作后的弹幕相位，来为她们的闪避弹幕进行准备。

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

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

对于每组数据：

- 第一行一个整数 $n$，意义如题述。
- 第二行一个长度为 $n$ 的 01 串 $b$。

outputFormat:
对于每组数据，输出一行 $n$ 个整数，即你构造的数列 $a$。

**如果有多组解，输出任意一种。**

hint:
### 样例解释

- 对于数据 $1$，显然 $a_2>1,a_3>2$。
- 对于数据 $2$，显然 $a_2<2,a_3>2$。
- 对于数据 $3$，显然 $a_2>1,a_3<3,a_4>3$。\
  注意到 $a=\{2,3,1,4\}$ 同样满足要求。

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{Subtask 依赖} & \textbf{分值}\\\hline
1 & 10 & - & - & 5\\\hline
2 & 10^5 & \textbf{A} & - & 5 \\\hline
3 & 10^5 & \textbf{B} & - & 20 \\\hline
4 & 10^5 & - & 1,2,3 &70 \\\hline
\end{array}$$

- **特殊性质** $\textbf{A}$：保证 $b_i$ 都相等。
- **特殊性质** $\textbf{B}$：存在整数 $p\in[2,n]$，使得对于 $1\le i<p$，有 $b_i=1$；对于 $n\ge i\ge p$，有 $b_i=0$。

对于全部数据，满足 $1\le T\le 10^4$，$1\le n\le 10^5$，$\forall i\in[1,n],b_i\in\{0,1\}$。

保证单个测试点内 $\sum n\le 5\times 10^5$。


title: [COCI2015-2016#4] DEATHSTAR

type: P

description:
你排除万难，潜入了 Death Star。要想摧毁它，你需要一个长度为 $n$ 的数组 $a$，以启动 Death Star 的自我毁灭指令。虽然你不知道这个数组是什么，但好在，你的老朋友 Darth Vader 事先给了你一个 $n$ 阶方阵 $b$。在这个方阵中，第 $i$ 行第 $j$ 列上的元素 $b_{i,j}=a_i\operatorname{~and~} a_j$，其中 $\operatorname{and}$ 表示按位与运算。正当你以为你可以通过这个方阵直接得出数组 $a$ 时，你发现主对角线上的所有元素被激光剑给毁坏了，你无法读出这些元素的值，只能暂时以 $0$ 代替。

现在，请你根据其他没有被毁坏的元素的数值求出**任意一个**满足要求的数组 $a$。

inputFormat:
第一行输入一个整数 $n$，表示方阵 $b$ 的阶数。
随后 $n$ 行，每行输入 $n$ 个整数，描述方阵 $b$。

outputFormat:
输出一行 $n$ 个整数，表示满足条件的数组 $a$。数组中的每个元素必须是不超过 $10^9$ 的**非负整数**。

数据保证**有解**，但**不保证有唯一解**。

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

不难看出，满足要求的一个数组 $a=[1,1,1]$，但请注意，这并不是唯一可能的答案。

**【数据范围】**

对于所有数据，$1\leqslant n\leqslant 1000$，$0\leqslant b_{i,j}\leqslant 10^9$。

**本题开启 Special Judge**。如果你有可以 hack [供题人自行编写的 checker ](https://www.luogu.com.cn/paste/fzkkyhqp)的数据或者对 checker 有改进意见，欢迎在本题下方讨论区提出。

**【题目来源】**

本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T3 DEATHSTAR_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2015-2016#4] CHEWBACCA

background: **本套赛题 T3 为 [P8053](https://www.luogu.com.cn/problem/P8053)。**

description:
一棵 $n$ 个节点的 $k$ 级树是按照如下方式构造出来的：

- 首先，新建根节点，并将其编号为 $1$。
- 随后重复如下步骤直至节点总数恰好为 $n$：
  - 设上一个新增节点的编号为 $x$。
  - 在上一层中从左往右找到第一个儿子个数 $<k$ 的节点。
    - 如果该节点上没有儿子，则在该节点下新增一个儿子节点，编号为 $x+1$，并在点 $x+1$ 和我们找到的该父亲节点之间连一条长度为 $1$ 的边。
    - 否则，在该节点最近添加的儿子节点的右边新增一个儿子节点，编号为 $x+1$，并在点 $x+1$ 和我们找到的该父亲节点之间连一条长度为 $1$ 的边。
  - 如果在当前层没有找到儿子个数 $<k$ 的节点，则跳到下一层。

例如，下图为按照如上方法构造出来的包含 $9$ 个节点的 $3$ 级树：

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

现在，你得到了这棵包含 $n$ 个节点的 $k$ 级树，你需要回答 $q$ 次询问。每次询问给定两个整数 $x,y$，你需要回答在该树中节点 $x$ 到节点 $y$ 的最短路径长度。

inputFormat:
第一行输入三个整数 $n,k,q$，分别表示树的节点数、级数和询问次数。
随后 $q$ 行，每行输入两个整数 $x,y$，表示本次询问的两个节点。

outputFormat: 输出 $q$ 行，每行一个整数，表示节点 $x$ 到节点 $y$ 的最短路径长度。

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

下图是样例 1 中构造出来的树：

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

不难发现，对于第 $1$、$2$ 次询问，由于节点 $2$ 是节点 $1$ 的儿子节点，因此这两个点之间的最短路径长度恰好为 $1$。而对于第 $3$ 次询问，一条最短路径是 $4\rightarrow 2\rightarrow 1\rightarrow 3\rightarrow 7$。因此其最短路径长度为 $4$。

**【样例 2 解释】**

样例 2 构造出来的树见『题目描述』部分。

**【数据范围】**

对于 $20\%$ 的数据，保证 $1\leqslant n,q\leqslant 1000$。
对于 $50\%$ 的数据，保证 $1\leqslant n\leqslant 10^5$。
对于所有数据，$1\leqslant n\leqslant 10^{15}$，$1\leqslant k\leqslant 1000$，$1\leqslant q\leqslant 10^5$。

**【题目来源】**

本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T4 CHEWBACCA_**，按照原题数据配置，满分 $120$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2015-2016#4] GALAKSIJA

description:
很久以前，在一个很远很远的星系里，有 $n$ 颗行星和 $n−1$ 条连接所有行星的边。换句话说，行星和边形成了一棵树。此外，每条边上都有一个权值。

行星对 $(A,B)$ 是**无聊的**，当且仅当如下条件成立：

- $A\neq B$。
- 行星 $A,B$ 可以互相到达。
- 行星 $A,B$ 之间的路径上的所有边的权值的**异或和**等于 $0$。

现在，由于不可控力，该星系的所有边会**按一定顺序**摧毁。请求出初始时和每次摧毁一条边之后**无聊的**行星对数量。

inputFormat:
第一行输入一个整数 $n$，表示行星的数量。
随后 $n-1$ 行，每行三个整数 $a_i,b_i,z_i$，分别表示第 $i$ 条边连接的两个点的编号和第 $i$ 条边的权值。
随后一行输入 $n-1$ 个整数，第 $i$ 个整数 $p_i$ 表示第 $i$ 次摧毁的边的编号。

outputFormat: 输出 $n$ 行，每行一个整数，其中第 $i$ 个整数表示在按顺序摧毁了 $i-1$ 条边后**无聊的**行星对数量。

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

初始时，只有行星对 $(1,2)$ 是无聊的。在毁坏了唯一的一条边之后，就不再存在无聊的行星对了。

**【样例 2 解释】**

初始时，只有行星对 $(1,3)$ 是无聊的。在破坏了 $1$ 号边之后，由于行星 $1,3$ 之间不能互相到达，因此之后不再存在无聊的行星对了。

**【样例 3 解释】**

初始时，所有的行星对都是无聊的，因为所有行星对中的两个行星之间的路径上的所有边的权值的异或和是 $0$。

**【数据范围】**

对于所有数据，$1\leqslant n\leqslant 10^5$，$1\leqslant a_i,b_i\leqslant n$，$0\leqslant z_i\leqslant 10^9$。

本题一共 $10$ 个测试点，每个测试点的数据范围如下：

| 测试点 | $n\leqslant $ | 特殊性质 A |
| :-----------: | :-----------: | :-----------: |
| $1$ | $1000$ | $\surd$ |
| $2$ | $1000$ | $\times$ |
| $3\sim 4$ | $10^5$ | $\surd$ |
| $5\sim 10$ | $10^5$ | $\times$ |

特殊性质 A：每条边的权值为 $0$。换句话说，$\forall i\in[1,n)$，$z_i=0$。

**【题目来源】**

本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T5 GALAKSIJA_**，按照原题数据配置，满分 $140$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2015-2016#4] ENDOR

description:
如果我们相信《吉尼斯世界纪录大全》的话，在布满森林的 Endor 卫星上，有一根全银河系最长的棍子。在那根 $L$ 米长的棍子上有 $n$ 只欢快的变色龙。每只变色龙以 $1$ 米/秒的恒定速度沿着棍子在两个可能的方向（左或右）中的一个方向上移动，并以可能的 $k$ 种颜色之一着色。

众所周知，Endor 卫星上的变色龙崇拜古老的蚂蚁法则，该法则规定变色龙必须沿着棍子行走直到走到棍子的末端，并且当与另一只变色龙发生碰撞时，该变色龙必须转过 $180$ 度，继续朝相反的方向行走。此外，在向左移动着色为 $a$ 的变色龙与向右移动的着色为 $b$ 的变色龙发生碰撞后，碰撞前向左移动的变色龙采用碰撞前向右移动的变色龙的颜色 $b$，而在碰撞前向右移动的变色龙会采用新的颜色 $(a+b)\bmod k$。

如果给你所有变色龙的初始位置、颜色和运动方向，对于每种颜色，确定采用该种颜色的变色龙在离开棍子之前的总行程。

inputFormat:
第一行输入三个整数 $n,k,L$，分别表示变色龙的只数，颜色的种数和棍子的长度。
随后 $n$ 行，每行两个整数 $d_i,b_i$ 和一个字符 `L` 或 `D`，其中 $d_i,b_i$ 分别表示第 $i$ 只变色龙到棍子**左端**的距离和第 $i$ 只变色龙的颜色，字符如果是 `L`，则表示第 $i$ 只变色龙初始时面朝左边，否则表示第 $i$ 只变色龙初始时面朝右边。保证 $d_i$ 两两不同且按升序给出。

outputFormat: 输出 $k$ 行，第 $i$ 行输出一个实数，表示采用第 $i-1$ 种颜色的变色龙离开棍子之前的总行程，**保留一位小数**。可以证明，答案要么是整数，要么是形如 $\texttt{x.5}$ 的一位小数。

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

两只变色龙在行走了 $5$ 米之后发生碰撞。在此之后，$1$ 号变色龙的颜色变为 $0$，$2$ 号变色龙的颜色变为 $1$，然后它们各又继续走了 $5$ 米然后离开棍子。因此，采用第 $0$ 种颜色和第 $1$ 种颜色的变色龙各走了 $10$ 米，在此过程中不存在采用第 $2$ 种颜色的变色龙。

**【数据范围】**

对于 $50\%$ 的数据，保证 $1\leqslant n\leqslant 3000$。
对于所有数据，$1\leqslant n\leqslant 10^5$，$1\leqslant k\leqslant 40$，$1\leqslant L\leqslant 10^6$，$0\leqslant d_i\leqslant L$，$0\leqslant b_i<k$，$d_{i-1}<d_i$。

**【题目来源】**

本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T6 ENDOR_**，按照原题数据配置，满分 $160$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [BalkanOI2003] Farey 序列

description:
把所有分子和分母都 $\leq n$ 的**最简真分数**从小到大排成一行，形成的序列称为 Farey 序列。

求出 $n$ 所对应的 Farey 序列中第 $k$ 小的数。

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

outputFormat: 一行，两个整数 $p, q$，表示答案 $\frac{p}{q}$。

hint: 对于 $100\%$ 的数据，$2 \leq n \leq 4 \times 10^4$，$1 \leq k \leq$ 符合条件的分数的个数。


title: [WFOI - 02] I wanna moqueve（位移序列）

background:
> It's my fiesta.
>
> 一场前，kid 在 WFOIR1 的地图上，折戟沉沙；一场后，kid 从倒下的地方爬起。
>
> kid 成功了，他不再是从前那个他了。

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

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

description:
kid 需要在一台奇怪的电脑上排序一个 $1\sim n$ 的排列，下一个存档点才会出现。

kid 可以选择一个数 $x$，然后接下来的每次操作，kid 可以向左或向右循环位移一段长为 $x$ 的序列（最左/右边的会平移至最右/左边）（位移量是 $1$）。

如果 kid 的操作次数超过了 $23\times n$，排列就会爆炸，kid 将会再次倒下。所以，请告诉 kid 一种还原序列的方案，剩下的操作就交给 €€£ 吧！

inputFormat:
输入共 $2$ 行：

第一行一个整数 $n$，表示序列长度。

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

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

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

接下来 $m$ 行，每行两个数，前一个数表示平移区间左端点，后一个数表示方向，$0$ 为向左，$1$ 为向右；

本题采用 $\text{SPJ}$，只要循环位移操作正确即可给分。


title: [WFOI - 02] I wanna a feasitor（化验器）

background:
> 比赛时在做什么？有没有空？可以来开 longlong 吗？

kid 一脸疑惑地看着 Elgo87，Elgo87 说，通关就告诉你 ...

description:
kid 发现了一个函数 $f(x)$，它表示**除 $x$ 本身之外，$x$ 的最大约数**（$x$ 为大于 $1$ 正整数）。

下面是一些例子：

- $f(8)=4$，因为 $8$ 的约数有 $1,2,4,8$，除 $8$ 本身之外显然最大的约数为 $4$，所以 $f(8)=4$；
- $f(15)=5$，因为 $15$ 的约数有 $1,3,5,15$，除 $15$ 本身之外显然最大的约数为 $5$，所以 $f(15)=5$；

kid 还发现了两个数 $L,R$，你需要帮他求对于 $L\sim R$ 中的每一个数 $x$，$f(x)$ 的**最大值**，作为通关密码。

注意，$L\sim R$ 包括 $L$ 和 $R$。

你只需要告诉他答案，剩下的操作就交给 Elgo87 吧！

inputFormat: 一行两个整数 $L,R$，意义如题目描述。

outputFormat: 一行，表示对于 $L\sim R$ 中每个数 $x$，$f(x)$ 的最大值。

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

在 $12\sim17$，也就是 $12,13,14,15,16,17$ 这几个数中，除这些数本身之外的最大因数分别是 $6,1,7,5,8,1$，故最大值为 $8$。

**【数据范围】**

**本题采用 $\tt Subtask$ 捆绑测试。** 即你需要通过一个 $\tt Subtask$ 中的所有测试点才能得到这部分的分数。

- $\texttt{Subtask \#0 (10pts)}$：$2\le L< R\le 100$；
- $\texttt{Subtask \#1 (30pts)}$：$2\le L< R\le10^4$；
- $\texttt{Subtask \#2 (30pts)}$：$2\le L < R\le 10^9$，$R-L\le 10^6$；
- $\texttt{Subtask \#3 (30pts)}$：$2\le L < R \le 10^{18}$。


title: [POI2003] Monkeys

description:
一棵树上有 $n$ 只猴子。他们从 $1 \sim n$ 编号。编号为 $1$ 的猴子用它的尾巴盘住了一个树枝，剩下的猴子要么被其他的猴子钩住要么就是自己用手钩住其他的猴子。每只猴子都可以用两只手去钩其他的猴子，每只手最多只能钩一只。

从 $0$ 时刻开始，每一秒都有一只猴子松开它的一只手。这也许会造成一些猴子掉落到地上，我们想要知道它们掉落地上的时间（猴子掉落的速度都非常的快，可以忽略掉落的时间）。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，$n$ 代表猴子总数，$m$ 代表我们观察猴子的总时间。

接下来 $n$ 行描述初始的情形。第 $k$ 行有两个整数，分别代表猴子 $k$ 的左手和右手分别抓住了哪两只猴子，$-1$ 代表它的那只手是空的。

接下来 $m$ 行代表我们观察到的猴子的活动。第 $i$ 行有两个整数，代表在第 $i-1$ 时刻放开手的是哪只猴子和它放开的是哪只手（1 – 左，2 – 右）。

outputFormat: 输出 $n$ 个整数，每行一个整数，代表每只猴子掉落到地上的时间。如果没有掉落，输出 `-1`。

hint: 对于所有数据，$1 \le n \le 2 \times 10^5$，$1 \le m \le 4 \times 10^5$。


title: [POI2003] Sums

description:
我们给定一个整数集合 $A$。考虑一个非负整数集合 $A'$，所有属于 $A'$ 的集合的数 $x$ 满足当且仅当能被表示成一些属于 $A$ 的元素的和（数字可重复）。

比如，当 $A = \{2,5,7\}$，属于 $A'$ 的数为：$0$（$0$ 个元素的和），$2$，$4$（$2 + 2$）和 $12$（$5 + 7$ or $7 + 5$ or $2 + 2 + 2 + 2 + 2 + 2$）；但是元素 $1$ 和 $3$ 不属于 $A'$。

inputFormat:
第一行有一个整数 $n$，代表集合 $A$ 的元素个数。接下来每行一个数 $a_i$ 描述一个元素。$A = \{a_1,a_2,...,a_n\}$。

接下来一个整数 $k$，然后每行一个整数，分别代表 $b_1,b_2,...,b_k$。

outputFormat: 输出 $k$ 行。如果 $b_i$ 属于 $A'$，第 $i$ 行打印 `TAK`，否则打印 `NIE`。


title: 『JROI-4』沈阳大街 2

description:
给定两个长度为 $n$ 的序列 $A,B$，满足：

* $\forall 1\le i<n,A_i \ge A_{i+1}$

* $A_n\ge \min\limits_{i=1}^n(B_i)$

$\pi$ 是一个长度为 $n$ 的排列，定义价值函数 $f(\pi)$：

$$
f(\pi)=\prod_{i=1}^n\min(A_i,B_{\pi(i)})
$$

每种排列出现的概率相等，求 $f(\pi)$ 的期望对 $998244353$ 取模的结果。

即求:

$$
\left(\dfrac{1}{n!}\sum_\pi f(\pi)\right) \bmod 998244353
$$

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

第二行 $n$ 个整数表示 $A_i$。

第三行 $n$ 个整数表示 $B_i$。

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


title: [JSOI2016] 炸弹攻击1 - 数据加强版

background: JYY 最近迷上了一款塔防游戏，在游戏里 JYY 除了建设建筑，还可以使用炸弹对屏幕上的敌人进行范围杀伤。

description:
游戏地图可以简单认为是一个二维平面。JYY 建造了 $N $ 个建筑，每个建筑都是一个圆，其中第 $i$ 个建筑的圆心位于 $(x_i,y_i)$ 且半径为 $r_i$。地图上一共有 $M$ 个敌人，一个敌人可以近似看成一个平面上的点，其中第 $i$ 个敌人位于 $(p_i,q_i)$。JYY 可以使用一枚可以设置半径的炸弹，可以设置一个不超过 $R$ 的范围，然后选择平面上的一个点引爆，范围内的所有敌人全部消灭。

当然，由于炸弹威力巨大，如果爆炸范围接触到 JYY 的建筑，那么 JYY 的建筑也会受到损伤。（注：如果炸弹的爆炸范围仅接触到了 JYY 建筑的边界，则不会对 JYY 的建筑造成损伤；如果敌人出现在了爆炸范围的边界，则该敌人被消灭）JYY 可以自由控制炸弹的爆炸地点和爆炸半径。作为一个保守的玩家，他希望在保证自己建筑毫发无损的情况下，消灭尽量多的敌人。

inputFormat:
第一行包含三个非负整数，分别为 $N,M,R$；

接下来 $N$ 行，每行三个整数，其中第 $i$ 行 $x_i,y_i,r_i$，表示第 $i$ 个建筑的位置和半径。数据保证所有建筑不相交（但是有可能边界接触）；

接下来 $M$ 行，每行两个整数，其中第 $i$ 行为 $p_i,q_i$，表示第 $i$ 个敌人的位置。任意两个敌人的位置不同，且敌人不会出现在建筑里。

outputFormat: 输出一行一个整数，表示 JYY 最多可以消灭的敌人数量。

hint:
对于 $100\%$ 的数据，满足 $1\leq N\leq 10$，$1\leq M\leq 2000$，$1\leq R,r_i\leq 2\times 10^4$，$|p_i|,|q_i|,|x_i|,|y_i|\leq 2\times 10^4$。

数据来源于 NAIPC 2015 Problem A - Area of Effect，并有部分自造新数据。


title: [WFOI - 02] I wanna cross the grid（穿越网格）

background:
>  相信奇迹的人，本身比奇迹更伟大吧

突然，存档点落到了一个巨大的网格中，只有走过所有必经区域，才能出现下一个存档点...

description:
给定一张 $n$ 行 $m$ 列的网格图，行和列从 $1$ 开始编号，定义二元组 $(x,y)$ 表示第 $x$ 行第 $y$ 列的格子，每一行的第 $L$ 到第 $R$ 列的格子是必经区域，形式化地，设 $D$ 是必经区域集合，则 $D=\{(x,y)|1\leq x\leq n,L\leq y\leq R,x,y\in N_+\}$。

每次 kid 可以向上下左右四个方向走一步，且不能超过边界。形式化地，若现在 kid 现在在 $(x,y)$，则 kid 可以走到 $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$。

初始时 kid 在 $(S_x,S_y)$（保证 $S_y=L$），他需要走过所有的必经区域，且任何一个格子最多只经过一次。形式化地，kid 走的路径形如一个二元组序列 $P=(x_1,y_1),(x_2,y_2)...(x_k,y_k)$，需要满足 $\forall (x_0,y_0)\in D，\exist i\in[1,k]，(x_0,y_0)=(x_i,y_i)$，且 $\forall i\not= j，(x_i,y_i)\not= (x_j,y_j)$。

同时，kid 还要记录一个通关序列 $p$，当 kid 第一次进入某一行的必经区域之后，就要把行号写在当前序列的后面，且立刻经过本行所有的必经区域。同时，$p$ 必须包含一个长度为 $L_q$ 的子序列 $q$ 才是一个合法的通关序列，从而真正通关。形式化地，$p$ 合法当且仅当存在长度为 $L_q$ 的序列 $c$ 满足 $p_{c_i}=q_i$，且 $c$ 单调上升。

同时，为了给 lindongli2004 降低操作难度，lindongli2004 希望 kid 走的步数越少越好。

给定 $n,m,L,R,S_x,S_y,q$，请你为 kid 规划一条通关路线，或者告诉他不存在一条路线。剩下的操作就交给 lindongli2004 吧！

inputFormat:
第一行 $8$ 个正整数 $n,m,L,R,S_x,S_y,L_q,s$，分别表示矩阵的行数和列数，必经区域的左边界和右边界，起点的 $x$ 坐标和 $y$ 坐标，序列 $q$ 的长度和评分参数。

第二行 $L_q$ 个不重复的正整数，表示序列 $q$ 。

outputFormat:
第一行一个字符串 `YES` 或者 `NO` 表示是否存在一条路径（不包含引号）。

若存在一条路径，第二行一个正整数 $cnt$ 表示路径长度，接下来 $cnt$ 行每行两个正整数 $x,y$ 表示路径的坐标。

hint:
#### 数据范围：

$1\leq L\leq R\leq m$，$1\leq S_x\leq n$，其他详见下发文件。

#### 评分规则：

下发文件中第一行的最后一个数为 $s$，设你的操作步数为 $cnt$。那么
 - 若 $cnt\leq s$，你将获得 $10$ 分。
 - 若 $cnt> s$ 且能通关，你将获得 $9- \frac{cnt-s}{\lfloor\frac{n}{2}\rfloor}$ 分。
 - 若你不能通关，你将获得 $0$ 分。

#### checker：

[自取](/paste/c4omcrf2)

使用方法：在同一目录下，把下发的数据放到 data.in 中，把你的答案放到 data.out 中，编译运行即可。

注意事项：
 - 此 checker 默认存在一组方案，并 check 该方案是否合法。
 - 此 checker 的最大方案容量为 $2.5 \times 10^{8}$ ，也就是说，你的方案中不能有超过 $2.5 \times 10^{8}$ 个数。


title: [COCI2011-2012#4] OGRADA

description:
给定两个元素个数为 $N$ 的数组 $A,B$。

规定一个数组的权值为该数组中所有相邻元素的大小差的绝对值之和。现可将 $B$ 数组变成其任意的一个排列 $B'$，使得对 $\forall i \in [1,N) \cap \Z$ 满足：

- 若 $A_i \lt A_{i+1}$，则 $B'_i \lt B'_{i+1}$。
- 若 $A_i \gt A_{i+1}$，则 $B'_i \gt B'_{i+1}$。

求在所有方案中权值最大的排列 $B'$ 及最大权值。

inputFormat:
第一行，一个整数 $N$。

第二行，$N$ 个正整数 $A_i$。

第三行，$N$ 个正整数 $B_i$。

outputFormat:
第一行，一个正整数表示最大权值。

第二行，$N$ 个用空格分开的正整数，表示 $B'$ 中的元素。如果有多种符合题意的 $B'$，请输出任意一种。

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

合法的数组 $B'$ 有：

- $\{1,3,2,4\}$，权值为 $2+1+2=5$
- $\{1,4,2,3\}$，权值为 $3+2+1=6$
- $\{2,3,1,4\}$，权值为 $1+2+3=6$
- $\bf \{2,4,1,3\}$ **，权值为** $\bf2+3+2=7$
- $\{3,4,1,2\}$，权值为 $1+3+1=5$

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

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

**【提示与说明】**

如果只答对第一行而第二行错误或为空，则可以获得对应测试点 $50\%$ 的分数。

欢迎通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/xuyueqnf) 进行 hack。

**题目译自 [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 4 OGRADA_。**

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


title: [COCI2011-2012#4] BROJ

description: 求最小质因数为 $P$ 的不超过 $10^9$ 的第 $N$ 小正整数。

inputFormat: 第一行，两个整数 $N,P$。保证 $P$ 为质数。

outputFormat: 输出所求的不超过 $10^9$ 的第 $N$ 小正整数。如果答案超过 $10^9$，则输出 $0$。

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

- 对于 $30\%$ 的数据，输出小于 $10^5$（含 $0$）。
- 对于另外 $30\%$ 的数据，$P \gt 1000$。
- 对于 $100\%$ 的数据，$1 \le N,P \le 10^9$。

**【提示与说明】**

**题目译自 [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 5 BROJ_。**

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


title: [COCI2011-2012#4] KRIPTOGRAM

description:
现有一段明文和一部分密文。明文和密文都由英文单词组成，且密文中的一个单词必然对应着明文中的一个单词。

求给出的密文在明文中可能出现的最早位置。

inputFormat:
第一行，若干个英文单词和一个 $\texttt \$$，表示明文。

第二行，若干个英文单词和一个 $\texttt \$$，表示密文。

每行末尾的 $\texttt \$$ 用于表示该行结束。数据保证没有多个 $\texttt \$$ 出现在同一行的情况。

outputFormat: 输出密文在明文中可能出现的最早位置，即密文的第一个单词在明文中可能出现的最早位置。

samples:
a b c x c z z a b c $
prvi dr prvi tr tr x $

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

- 对于 $100\%$ 的数据，明文和密文所对应字符串的长度不超过 $10^6$，输入的单词均由小写字母组成。

**【提示与说明】**

**题目译自 [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 6 KRIPTOGRAM_。**

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


title: [WFOI - 02] I wanna escape the shadow（阴影）

background:
> Define adventure with death
>
> You are the shadow to my life

背景突然阴沉了下来，但是 kid 清楚，这是最黑暗的时刻，也是黎明之前...

description:
现在 kid 身处一个**圆心为 $(0,0)$，半径为 $r$ 的**圆中，并且学会了一种新的操作 `mklig(X,Y,Z)` 来消除黑暗，具体如下：

$X,Y,Z$ 是三个不同的点，作射线 $XY,ZY$，设两条射线与圆周交于 $d_1,d_2$，那么将 弧 $d_1d_2$，线段 $Yd_1,Yd_2$ 围成的区域照亮。

现在圆内有一些点，记 $S_{光}$ 是圆的半径为 $r$ 的时候被照亮的总面积，现在 kid 想知道在使 $\lim\limits_{r \to \infty} \dfrac{S_{光}}{\pi r^2}$ （可以理解为 r 无穷大时）最大时，最少需要多少次 `mklig` 操作。你只需要给出答案，剩下的操作就交给 €€£ 吧！

数据保证不存在三点共线。

inputFormat:
**本题有多组数据**

第一行一个整数 $T$，表示数据组数；

对于每组数据：

第一行一个正整数 $n$；

接下来 $n$ 行，每行两个整数，分别表示一个点的横纵坐标。

outputFormat: 共 $T$ 行，每行一个整数，表示答案。

hint:
- ####  样例解释

![](https://s1.ax1x.com/2022/03/14/bXTM01.png)

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

- $\texttt{Subtask \#0 (30pts)}$：$n = 10^3$ 且数据随机；
- $\texttt{Subtask \#1 (30pts)}$：$n \le 5$ ；
- $\texttt{Subtask \#2 (40pts)}$：$n \le 10^6$；

对于每个测试点，保证 $T \le 5 ，\sum n\le 10^6$，点的坐标的绝对值不超过 $10^9$。


title: [COCI2009-2010#7] SPAVANAC

description: 给定 $24$ 小时制下的时间 $H:M$，输出 $24$ 小时制下比该时间早 $45$ 分钟对应的时刻。

inputFormat: 第一行，两个正整数 $H,M$。

outputFormat: 输出两个整数，表示早 $45$ 分钟后的时刻。

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

- 对于 $100\%$ 的数据，$0 \le H \le 23$，$0 \le M \le 59$。

**【提示与说明】**

**题目译自 [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 1 SPAVANAC_。**

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


title: [COCI2009-2010#7] COKOLADA

description:
顾客急需大小为 $K$ 个单位的巧克力，但现在你**只能选择一块**大小为 $2$ 的非负整数幂（即 $1,2,4,8,16,\cdots$）的巧克力进行购买。

为了满足顾客需求，可以采取切割的方式，将一块大小为 $D$ 个单位的巧克力切成两块大小为 $\dfrac{D}{2}$ 个单位的巧克力。

为了降低成本，你需要求出所需的巧克力大小的最小值和最小切割次数。

inputFormat: 第一行，一个正整数 $K$，表示顾客所需的巧克力大小。

outputFormat: 输出两个整数，分别表示巧克力大小的最小值和所系的最少切割次数。

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

- 对于 $100\%$ 的数据，$1 \le K \le 10^6$。

**【提示与说明】**

**题目译自 [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 2 COKOLADA_。**

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


title: [COCI2009-2010#7] BAKICE

description:
有轨电车上总会出现诸多问题，其中包括人群抢夺座位的乱象——他们总会以飞快的速度去抢距离自己最近的座位。

当多名乘客同时瞄准同一个座位准备入座时，问题将会产生。如果只有一名乘客离该座位最近（对于此题，两个点的距离定义为**欧几里得距离**，即 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$），那么他就会入座而其他乘客将会另选最近的座位；如果多名乘客与座位的欧几里得距离都是最近的，那么将会产生「爆炸事件」。「爆炸事件」后，涉及到的乘客和座位都将会「爆炸」（即后续无需继续考虑）。

给定电车中座位、乘客和地板的 $R \times C$ 地图，用 $\texttt .$ 、$\texttt X$ 和 $\texttt L$ 分别表示地板、乘客和座位。求在所有乘客都落座或「爆炸」和座位被抢光最先发生的一个事件之前，发生了多少次「爆炸事件」。

inputFormat:
第一行，两个整数 $R,C$。

接下来的 $R$ 行，每行 $C$ 个字符 $\texttt .$ / $\texttt X$ / $\texttt L$。

数据保证，至少存在一个 $\texttt X$ 和一个 $\texttt L$。同时，不存在两个 $\texttt L$ 和某一个 $\texttt X$ 的距离相等的情况。

outputFormat: 输出「爆炸事件」的次数。

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

- 对于 $100\%$ 的数据，$1 \le R,C \le 100$。

**【提示与说明】**

**题目译自 [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 3 BAKICE_。**

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


title: [COCI2009-2010#7] SVEMIR

description:
太空帝国要通过建造隧道来联通它的 $N$ 个星球。

每个星球用三维坐标 $(x_i,y_i,z_i)$ 来表示，而在两个星球 $A,B$ 之间建造隧道的价格为 $\min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\}$。

现要建造 $N-1$ 条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。

inputFormat:
第一行，一个整数 $N$。

接下来的 $N$ 行，每行三个整数 $x_i,y_i,z_i$，表示第 $i$ 个星球的坐标。

数据保证不存在两个具有相同坐标的星球。

outputFormat: 输出所需的最小总价。

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

- 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$-10^9 \le x_i,y_i,z_i \le 10^9$。

**【提示与说明】**

**题目译自 [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 4 SVEMIR_。**

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


title: [COCI2009-2010#7] KRALJEVI

description:
Mirko 和 Slavko 在一个 $R \times C$ 的棋盘上游戏。他们各自在棋盘上摆放一定数量的王——王每步可以任选 $8$ 个方向中的一个移动 $1$ 步。现规定：

- 两个王之间的「距离」为其中一个王移动到另一个王所在棋格所需的最少步数。
- 一个玩家的「扩张度」为该玩家所有的王两两之间距离总和。

分别求出 Mirko 和 Slavko 的「扩张度」。

inputFormat:
第一行，两个整数 $R,C$。

接下来的 $R$ 行，每行 $C$ 个字符 $\texttt M$ / $\texttt S$ / $\texttt .$，分别表示 Mirko 的王、Slavko 的王和空位。数据保证每一方在棋盘上至少有一个王。

outputFormat: 输出两个整数，分别表示 Mirko 和 Slavko 的「扩张度」。

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

- 对于 $20\%$ 的数据，棋盘上王的总数不超过 $5000$。
- 对于 $60\%$ 的数据，$R,C \le 300$。
- 对于 $100\%$ 的数据，$1 \le R,C \le 1000$。

**【提示与说明】**

**题目译自 [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 5 KRALJEVI_。**

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


title: [COCI2009-2010#7] RESTORAN

description:
给定一张含 $N$ 个结点、$E$ 条边的无向图。

现可将这 $E$ 条边染成红色或蓝色。求一种染色方式，使得所有度数不小于 $2$ 的结点都能连接两种颜色的边。若无解，则输出 $0$。

inputFormat:
第一行，两个整数 $N,E$。

接下来的 $E$ 行，每行两个整数 $A_i,B_i$，表示第 $i$ 条边连接 $A_i,B_i$ 两个结点。数据保证不存在重边。

outputFormat:
若无解，请输出 $0$。

否则输出 $E$ 行，每行输出一条边所染成的颜色（与输入顺序对应）。红色用 $1$ 表示，蓝色用 $2$ 表示。

如果存在多解，请输出任意一种。

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

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

- Subtask 1（78 pts）：$N \le 1000$，$E \le 5000$。
- Subtask 2（52 pts）：无特殊限制。

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

**【提示与说明】**

欢迎通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/omg15jba) 进行 hack。

**题目译自 [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 6 RESTORAN_。**

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


title: 「RdOI R3.5 附加」ACP-II

background: 在 1951 年，第 -32 届全国青少年信息学奥林匹克冬令营结束后，打了一上午比赛的小 A 疲惫不堪，想放松一下。于是他又借助时空传输接口（**T**ime **T**ransport **I**nterface）连接了一台 2015 年的计算机，获取到了最新的游戏「**AC** **P**roject 15 / Legacy of DWT AKing IOI」来游玩。

description:
**这是一道传统题。**

你需要控制机器人玩躲避子弹的游戏。游戏的画面是一个在第一象限，坐标范围从 $(0,0)$ 至 $(n,m)$ 的矩形。机器人初始生成在坐标 $(0,0)$。你可以通过以下几种指令来控制这个机器人：

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|l|}\hline
\textsf{\textbf{指令}} & \textsf{\textbf{描述}} \cr\hline
\bm 0 & \textsf{机器人静止不动} \cr\hline
\bm 1 & \textsf{机器人向左移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x-1,y)$} \cr\hline
\bm 2 & \textsf{机器人向下移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x,y-1)$} \cr\hline
\bm 3 & \textsf{机器人向上移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x,y+1)$} \cr\hline
\bm 4 & \textsf{机器人向右移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x+1,y)$} \cr\hline
\end{array}
$$

你构造的指令用一个数字串 $C'$ 表示。每种指令都会耗费一定的费用。具体来讲，你构造的**原始指令** $C'$ 中每包含一个 $i$ 号命令，就会耗费 $P_i$ 的费用。

你的指令会被重复 $k$ 遍，作为机器人的移动指令 $C$。例如当 $C'=1123$，$k=3$ 时，机器人收到的指令 $C= 112311231123$。

游戏中会生成 $b$ 个子弹，每个子弹用一个有序六元组 $(l_i,r_i,x_i,y_i,p_i,q_i)$ 表示。它的意思是这颗子弹在 $l_i$ 秒生成，第 $r_i$ 秒销毁。生成时的坐标为 $(x_i,y_i)$。每秒沿着 $x$ 轴正方向移动 $p_i$ 单位长度，沿着 $y$ 轴正方向移动 $q_i$ 单位长度。

游戏共进行 $d$ 秒，若 $d$ 秒内机器人碰撞到子弹或者移动到画面以外，机器人就会爆炸，游戏失败。如果在第 $d$ 秒结束时机器人没有爆炸，则游戏胜利。

游戏中的每一秒分为五个阶段，每个阶段结束后才会执行下一个阶段：

1. 机器人移动阶段。机器人会在第 $i$ 秒执行 $C_i$ 指令。若 $C$ 的长度 $< i$，也就是说所有指令都执行完了，则静止不动。
1. 子弹移动阶段，所有已经生成且还未销毁的子弹会进行一次移动。具体来讲，设当前是第 $c$ 秒，对于满足 $l_i<c\le r_i$ 的每个子弹 $(l_i,r_i,x_i,y_i,p_i,q_i)$，它的坐标会变为 $(x_i+(c-l_i)p_i,y_i+(c-l_i)q_i)$。
1. 子弹生成阶段。设当前是第 $c$ 秒，对于所有 $l_i=c$ 的子弹，将它们生成进画面，放置各自的初始位置 $(x_i,y_i)$ 上。
1. 判定阶段。若此时机器人的位置超出了画面，或者碰撞到了任意一颗已经被生成且尚未销毁的子弹，则机器人就会受击爆炸。具体来说，对于每一颗在画面上的子弹，设这颗子弹在这一秒初的位置为 $P=(x',y')$，当前的位置为 $Q=(x'',y'')$。若子弹是在这一秒内刚生成的则 $P=Q$。连接线段 $PQ$，若当前机器人的坐标在这条线段上（包括在线段的端点上），则视为机器人碰撞到了子弹。
1. 子弹销毁阶段。设当前是第 $c$ 秒，对于所有 $r_i=c$ 的子弹，将它们销毁。

inputFormat:
- 第一行输入六个整数 $n,m,b,d,k,maxc$。
- 第二行输入五个整数 $P_0,P_1,P_2,P_3,P_4$。
- 第三行至第 $b+2$ 行，每行输入六个整数。其中第 $i+2$ 行输入的整数分别代表 $l_i,r_i,x_i,y_i,p_i,q_i$。

outputFormat:
- 若 $maxc\ge 0$，则你需要输出一行一个字符串，表示你构造的指令，你需要保证指令费用 $\le maxc$。
- 否则，你需要输出一行一个整数，表示在所有可以成功完成游戏的指令中费用最少的指令的费用是多少。

hint:
### 样例解释

示意图里用 `0` 表示子弹，`1` 表示机器人，`.` 表示空位。

第 $1$ 秒钟：机器人移动到了 $(0,1)$；在 $(0,0)$ 和 $(1,0)$ 分别生成了一颗子弹。

```
1.
00
```

第 $2$ 秒钟：机器人移动到了 $(1,1)$；在 $(0,0)$ 处的子弹移动到了 $(0,1)$；在 $(0,1)$ 生成了一颗子弹。所以现在在 $(0,1)$ 处有两颗子弹（在下图中因为子弹重合只标出了一颗）。

```
01
.0
```

第 $3$ 秒钟：机器人位置不变；其中一颗位于 $(0,1)$ 的子弹飞出了画面；另外一颗位于 $(0,1)$ 的子弹被销毁。

```
.1
.0
```

第 $4$ 秒至第 $100$ 秒：机器人没有移动；位于画面外的子弹移动后仍然在画面之外，在画面内的那颗子弹没有移动，画面情况同第三秒的情况。

综上所述，这个指令可以成功完成游戏，费用为 $1\times 3+ 1 \times2=5$。

---

### 数据范围及限制

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

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline
\textbf{subtask} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\cr\hline
\textbf{分值} & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15\cr\hline
\end{array}
$$

对于 $100\%$ 的数据，保证 $n,m,b,d,P_i\ge0$，$k\ge 1$，$1\le l \le r$，$maxc\ge-1$。

你可能会想，这算什么数据范围？怎么没有上界？而且表格里怎么没有 subtask 的特殊限制？实际上，出题人也不知道数据的上界和特殊限制。

由于出题人的误操作，数据生成器源代码意外丢失，只剩下可执行程序。下发文件中提供了在 Windows / Linux / Mac 下编译的可执行程序。不同操作系统下编译的文件名如下：

- 对于 Windows 系统（文件名 genX-w32）：`g++ genX.cpp -o genX -O3 -std=c++14`，在 Windows10，Dev-C++ 5.50，TDM-GCC 4.9.2 32bit 下编译。
- 对于 Linux/Mac 系统（32 位，文件名 genX-l32）：`g++ genX.cpp -o genX -O3 -std=c++14 -m32`，在 NOI Linux 2.0，GCC 9.3.0 下编译。
- 对于 Linux/Mac 系统（64 位，文件名 genX-l64）：`g++ genX.cpp -o genX -O3 -std=c++14 -m64`，在 NOI Linux 2.0，GCC 9.3.0 下编译。

数据生成器需要在运行后输入一个 $[1,2^{30})$ 范围内的整数作为随机数种子，它会生成一份输入至 `0.in` 中。出题人无法保证生成的数据范围，但是可以保证：

- 同一个生成器所生成出的数据拥有同一个特殊限制。
- 所有生成器在 NOI Linux 2.0，处理器 i5-4200m 下运行，所用时间不超过 3s，内存占用不超过 2G。
- 生成出来的数据只与你输入的种子有关，与当前时间、操作系统等其它可变因素无关。
- 部分数据生成器会有极小概率生成一个无解数据，但保证 OJ 上的所有数据均有解。
- 你输入的种子只会当作随机数的种子使用，生成器不会出现特判种子生成干扰数据等行为。

数据中的每个 subtask 分别对应一个数据生成器所生成的数据。编号为 $X$ 的 subtask 对应的生成器是 `genX`。

**注意：由于输入格式中没有要求输入「subtask 编号」，你需要自己判断当前数据所对应的 subtask。且本题的 subtask 为乱序排布，你需要自己判断每个 subtask 的难易程度。**

同时，在下发文件分发有 `checker.cpp`。使用 `g++ checker.cpp -o checker -std=c++14` 将 `checker.cpp` 编译为可执行文件后运行 `./checker <inputfile> <outputfile>`，`checker` 就会给出游戏的输赢情况。其中 `<inputfile>` 为数据生成器生成的 `.in` 文件；`<outputfile>` 中存放你的输出。**本 checker 仅供理解游戏规则使用，和实际使用的 checker 有所不同，且不保证 checker 的时间复杂度正确。**


title: [WFOI - 02] I wanna reverse to reserve（翻转）

background:
> 君子不器

“我最擅长解谜了，你说是吧，kid。”

“嗯...”

description:
kid 走进了一个 $n$ 行 $m$ 列的矩阵，**不**保证矩阵中有 $n$ 个数字 $1$，$n$ 个数字 $2$，$\dots$ , $n$ 个数字 $m$ 但 $n,m$ 均为偶数。

现有两种改变矩阵的方式：

- 选择任意一行，将这一行上的数翻转；
- 选择任意一列，将这一列上的数翻转。

每次操作可以选择任意一种方式。

现在需要通过若干次操作，将矩阵变为：

$$
n\;行\left\{
\begin{array}{l}
1\quad2\quad3\quad\cdots\quad m\\
\\
1\quad2\quad3\quad\cdots\quad m\\

\\
\cdots\\
\\
1\quad2\quad3\quad\cdots\quad m\\
\end{array}
\right.

$$

这样才会出现下一个存档点。

你需要帮 kid 解决这个问题。

你只需要给出答案，剩下的操作就交给 Uvocde 吧！

inputFormat: 第一行两个正整数 $n$ 和 $m$，以下 $n$ 行，每行 $m$ 个正整数，表示该矩阵。

outputFormat:
第一行一个字符串，若不可能有可行的操作方式，则输出 `NO`，否则输出 `YES`；

如果输出 `YES`，下一行输出一个非负整数 $ans$，表示一种共需要 $ans$ 次操作。接下来输出 $ans$ 行，每行一个字符和一个数 $k$（中间有空格），这个字符表示这一次操作是翻转行还是翻转列，若是对某一行进行翻转则为 `0`，若翻转某一列则为 `1`，$k$ 表示翻转第几行或是第几列。

若存在可行方案，则只需输出一组可行解即可（不需要使 $ans$ 最小），但你要使 $ans \le n \times m$。

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

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

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

- $\texttt{Subtask \#0 (20pts)}$：最多只有 $2$ 个数不在规定位置上；
- $\texttt{Subtask \#1 (20pts)}$：$n=2$；
- $\texttt{Subtask \#2 (20pts)}$：$m=2$；
- $\texttt{Subtask \#3 (40pts)}$：$1\le n\le 100$，$1\le m\le 100$；

全部数据满足 $1\le n\le 100$，$1\le m\le 100$。


title: [CQOI2016] 伪光滑数 加强版

background: 原题链接：[P4359 [CQOI2016] 伪光滑数](https://www.luogu.com.cn/problem/P4359)

description:
若一个大于 $1$ 的整数 $m$ 的**不去重**质因数分解有 $k$ 项，其最大的质因子为 $a_k$，并且满足 $a_{k}^{k} \leq n$，$a_k \leq 397$，我们就称整数 $m$ 为 $n$ - 伪光滑数。

给定整数 $n$，求出第 $k$ 大的 $n$ - 伪光滑数。

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

outputFormat: 一行，一个整数，表示所求的值。

hint: 对于 $100\%$ 的数据，$1 < n \leq 10^{11}$，$k \geq 1$，保证至少有 $k$ 个满足要求的数。


title: 极寒之地

background:
238 神教 #1

在古老的传说中，南极企鹅是全知全能的真神，它们能轻易做到任何我们做不到的事情。在南极洲的广袤大陆上，没有任何生物能对它们构成威胁。

所幸，神并不是高高在上，对尘世不屑一顾的。经常有果敢的人类来到这里，运气好的话，能和神结为挚友——这是幸运的，因为神不需要从你这里得到什么，而它的力量却会一直庇佑你，直到永远。

而你是一位探险家，对传说的内容十分向往。在经历了不知多久的苦索之后，你终于找到了些许神迹，并成功地找到了传说中的“神”。

——并且是两位，但是……

description:
神正在辅导孩子做数学题。在神批评孩子的心算结果从低到高第
```plain
17409488245517115276142322168576189279543123341138742779319865028602486509006138934460661849637882913598407636154209737260165754120014607177773359981826603801250947835120164061898414398808778383710734965109968348499255333743808806819897228289078158612425862653924618211976295200391819532525867722941969825549125083939679976935766582544161633553282536186214629150364929344059634288758125744444293077873038252037297534321132535122264070340053106750045495648216831484920706070567384926577457983022367155402606111730048301290388577089307478371008345014562035666767719162727651399592653244427923731578583241159510645308913474636528103155221748236303528072259108507905341048592541395827961771903417533241290874568077431363019042931482055932874814355268929594505880132227031337095583783793918280184860930087635658394839764586155196454253268266394562535661446268255101517600243362823434368473980088051436392198234023198989135142538928701481935979801475550928245044051159083872693810338480154137358569089360697894156
```
位就错了并且居然花了
```plain
0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000215055865
```
秒才算完的时候，神的孩子发现了你，并要求你来验算一遍。

你当然做不到，于是你请求缩小数据范围，而神同意了。神说，你是个勇敢的探险者，在把这道题算完之后，会与你成为朋友。

现在，你只需要解决的是这么一个问题了：

给定一个正整数 $n$ 和自然数序列 $a_1,a_2,\cdots,a_n$。你需要对每一个 $0\le S\le 2^n-1$，求出数 $S$ 的“权值”。

一个数 $S$ 的权值 $v(S)$ 的计算方式是：把它写成二进制，如果它从低到高第 $x$ 位为 $1$，就把答案异或（xor）上 $a_x$。

神不想刻意刁难你，他只希望你把所有 $v(S)$ 求出来之后，把答案分别乘上对应的 $S$，然后异或起来，取模 $2^{64}$ 再交给他就好了。

你心知这个问题是很好算的。但是你还是希望尽量快地把结果求出，以成为神的朋友。

那么，加油吧！

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

第二行 $n$ 个自然数 $a_1,a_2,\cdots,a_n$。

outputFormat: 一行一个自然数如题。

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

|数据点编号|$n$|分值|空间限制|子任务编号|
|----|----|----|----|----|
|$1\sim3$|$=20$|$10$|$\texttt{256MB}$|0|
|$4\sim6$|$=25$|$40$|$\texttt{256MB}$|1|
|$7\sim10$|$\le30$|$50$|$\texttt{8MB}$|2|

对于 $100\%$ 的数据，$1\le n\le 30,0\le a_i\le 2^{64}-1$。

---

### 样例解释

用 $\bigoplus$ 表示 异或。

对于第一个样例，$\text{Ans}=(0\times 0)\bigoplus(1\times 1)\bigoplus(2\times 2)\bigoplus(3\times 3)\bigoplus(4\times 3)\bigoplus(5\times 2)\bigoplus(6\times 1)\bigoplus(7\times 0)\bigoplus(8\times 4)\bigoplus(9\times 5)\bigoplus(10\times 6)\bigoplus(11\times 7)\bigoplus(12\times 7)\bigoplus(13\times 6)\bigoplus(14\times 5)\bigoplus(15\times 4)=16$。

---

本题不需要刻意卡常，$\texttt{1.4s}$ 已经是出题人最大的善良了，如果还跑不过那基本就一定是算法不优了。


title: 『JROI-5』Interval

background: 小 C 喜欢带有区间操作的数据结构，因为这样的题总会有一档好写的 $\mathcal{O}\left(n^2\right)$ 部分分。

description:
**本题读入量较大，建议使用较快的读入方式，可以参考 [赛时公告板](https://www.luogu.com.cn/paste/lueudpd5)**

小 C 有一个长度为 $n$ 的序列 $a$，第 $i$ 项为 $a_i$。

$a$ 是一个 $1\sim n$ 的排列（即 $1\sim n$ 在 $a$ 中各出现一次）。

定义 $\operatorname{Mex}_{l,r}$ 为 $\{a_l,a_{l+1},
\cdots,a_{r-1},a_r\}$ 中**没有出现过的最小正整数**。

例如，$\operatorname{Mex}\{2,3\}=1,\operatorname{Mex}\{1,2,3\}=4$。

小 C 还有一个长度为 $n$ 的数列 $f$。

定义一个区间 $\left[l,r\right]$ 是合法的当且仅当
$$f_{r-l+1}< \operatorname{Mex}_{l,r}$$

小 C 希望你告诉他，最短的合法区间的长度是多少，特别的，如果没有区间合法，则输出 `0`。

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

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

第三行 $n$ 个正整数 $f_1,f_2,\cdots,f_n$。

outputFormat: 一行一个整数，表示最短的合法区间长度。

samples: 见附件 见附件

hint:
【样例解释】

对于 #1，容易发现 $\left[1,3\right]$ 是最短的合法区间。

对于 #2，容易发现 $\left[3,3\right]$ 是最短的合法区间。

对于 #3，容易发现没有合法的区间。

---

对于 $10\%$ 的数据，满足 $1\leq n\leq 100$。

对于 $20\%$ 的数据，满足 $1\leq n\leq 1000$。

对于另外 $10\%$ 的数据，满足 $f$ 不升，即满足 $f_1\geq f_2\geq\cdots\geq f_n$，且 $1\leq n\leq 10^6$。

对于 $100\%$ 的数据，满足 $1\leq n\leq 4\times 10^6,1\leq f_i\leq 10^9$。


title: 『JROI-5』Music

background:
**请注意到并不正常的时间限制**。

**本题读入量较大，建议使用较快的读入方式。**

小 C 每年都要给丁总氪钱。

description:
小 C 喜欢在网易云听歌，她希望你能帮助她计算一下她的网易云的听歌时间。

小 C 有 $n$ 条听歌记录，每条形如 `x t`，表示小 C 听了编号为 $x$ 的音乐 $t$ 分钟。听歌时间为所有有效记录的 $t$ 的总和。

首先，如果某条记录的 $t\leq1$，那么这条记录是无效的。

其次对于某一首歌，只有**第一条有效记录会被计算**，之后重复听这首歌的记录将不会被累计到听歌时间中。

inputFormat:
第一行一个正整数 $n$，同题意。

接下来 $n$ 行每行两个正整数 $x, t$，表示一条听歌记录。

outputFormat: 一行一个整数，表示听歌时间。

hint:
【样例解释】

第一条记录：`1 114514` ，有效记录，可以累计。

第二条记录：`2 1` ，$t\leq1$，无效记录。

第三条记录：`2 1919180` ，有效记录，可以累计。

第四条记录：`1 10` ，编号为 $1$ 的音乐在第一条记录已经累计，本条记录有效，但不能累计。

第五条记录：`3 2` ，有效记录，可以累计。

答案即为 $114514+1919180+2=2033696$。

___

对于 $40\%$ 的数据，保证 $1\leq x\leq n\leq 10^4$。

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^7,1\leq x,t_i\leq 10^7$。


title: 『JROI-5』Autumn

background: 感谢 @[王熙文](/user/353688) 提供了一种优于标算的做法。

description:
**本题读入量较大，建议使用较快的读入方式，可以参考 [赛时公告板](https://www.luogu.com.cn/paste/lueudpd5)**

给定 $n$ 个数列，每个数列有 $m$ 个元素，第 $i$ 个数列第 $j$ 个元素为正整数 $a_{i,j}$。

你每次可以选择 $i_1,j_1$ 和 $i_2,j_2$，交换 $a_{i_1,j_1}$ 和 $a_{i_2,j_2}$。你至多可以进行 $x$ 次交换。

定义 $d_i$ 为第 $i$ 个数列中第 $k$ 大的元素。

请最小化 $\max\limits_{i=1}^n \{d_i\}$。（表示 $d_1,d_2,\cdots,d_n$ 中的最大值）

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

接下来 $n$ 行每行 $m$ 个正整数，表示数列。

最后一行两个正整数 $k,x$。

outputFormat: 一行一个数，输出最小化的 $\max\limits_{i=1}^n \{d_i\}$。

hint:
对于样例 1，将 $a_{2,5}$ 和 $a_{1,5}$ 交换，可以证明，没有更优策略。
***
对于 $30\%$ 的数据，$x = 10^6,1\leq k\leq m$。

对于另外 $10\%$ 的数据，**所有的数都相等**。

对于另外 $30\%$ 的数据，$1\leq n,m\leq 2\times 10^3,1\leq k\leq m,a_{i,j}\leq 10^6,0\leq x\leq n\times m$。

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^3,1\leq k\leq m,1\leq a_{i,j}\leq 10^{18},0\leq x\leq n\times m$。


title: 『JROI-5』Color

background:
【被三月删除的图片】

泷泽三月 Orz

---
被删除图片会偷偷展示给报名讲评的同学（

description:
**请注意到并不正常的时间限制。**

小 C 有一棵 $dep$ 层 $n$ 个节点的**完全二叉树**，她希望选择其中一个**包含根节点**的**连通块**染色，她想知道有几种不同的染色方案，答案对 $998,244,353$ 取模。

inputFormat:
多测，第一行一个整数 $T$，表示测试组数。

**对于每组数据**

第一行一个整数 $dep$，同题意。

第二行一个整数 $s$，表示最底层叶子结点数目，特别的，他们将用二进制表示，你将读入一个 $dep$ 位 $\texttt{01}$ 串，用以表示 $s$，若转换为二进制后不足 $dep$ 位则用前缀 $0$ 补充。

**保证数据合法。**

outputFormat: 对于每组数据，一行一个整数，表示合法的染色方案的个数，需要**换行**。

hint:
你可以通过学习 [OI-Wiki 树基础](https://oi-wiki.org/graph/tree-basic/) 来了解题面中的名词。

【样例解释】

对于样例 #1，可以画出如下所示二叉树。

![7sc6Yj.png](https://s4.ax1x.com/2022/01/19/7sc6Yj.png)

我们对该二叉树按照**前序遍历标号**（如图），得到点集 $\left(1,2,3\right)$。

则仅有 $\left(1,2,3\right),\left(1,2\right),\left(1,3\right),\left(1\right)$ 是合法的染色方案。
****
对于样例 #3，可以画出如下所示二叉树。

![7sc1eO.png](https://s4.ax1x.com/2022/01/19/7sc1eO.png)

我们对该二叉树按照**前序遍历标号**（如图），得到点集 $\left(1,2,3,4,5\right)$。

则仅有 $\left(1,2,3,4,5\right),\left(1,2,3,4\right),\left(1,2,3\right),\left(1,2,4\right),\left(1,2\right),\left(1,2,3,5\right),\left(1,2,4,5\right),\left(1,2,5\right),\left(1,5\right),\left(1\right)$ 是合法的染色方案。

显然 $\left(2,3,4\right),\left(1,3,4\right)$ 不是合法的染色方案，前者没有包含根节点，后者染色的点集不是联通的。
***
对于 $30\%$ 的数据，$1\leq T\leq 10, 1\leq dep \leq 20$。

对于另外 $20\%$ 的数据，树是满二叉树（即完美二叉树，perfect binary tree）。

对于 $100\%$ 的数据，$1\leq T\leq 10, 1\leq dep \leq 10^6$。


title: [WC2022] 秃子酋长

background: 5s 512M -O2

description:
传说在明斯克航空航天局中，有一名强大的秃子酋长。

秃子酋长法力无边，他的头上没有头发，而且头特别硬，跑得还不慢。

这一天，豌豆射手来到了明斯克航空航天局。

秃子酋长为了考验这一位新人，给他出了这样一道题：

给一个长为 $n$ 的排列 $a_1,\dots, a_n$，有 $m$ 次询问，每次询问区间 $[l, r]$ 内，排序后相邻的数在原序列中的位置的差的绝对值之和。

inputFormat:
第一行两个数表示 $n, m$；

之后一行 $n$ 个数依次表示序列 $a$ 中的元素；

之后 $m$ 行，每行两个数 $l, r$ 表示一次查询。

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

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

第一个询问，$2,3$ 排序后为 $2,3$，在原序列中的位置为 $3,4$，相邻元素在原序列中位置差的绝对值之和为 $|3 - 4| = 1$。

第二个询问，$4, 2, 3, 1$ 排序后为 $1, 2, 3, 4$，在原序列中的位置为 $5, 3, 4, 2$，相邻元素在原序列中位置差的绝对值之和为 $|5 - 3| + |3 - 4| + |4 - 2| = 5$。

**【数据范围】**

对 $10\%$ 的数据，$n, m \leq 10^3$；
对另外 $10\%$ 的数据，$n, m \leq 5 \times 10^4$；
对另外 $10\%$ 的数据，$n, m \leq 10^5$；
对另外 $10\%$ 的数据，$n, m \leq 2 \times 10^5$；
对另外 $20\%$ 的数据，$|a_i - i| \leq 10$；
对另外 $20\%$ 的数据，$m=\dfrac{n(n-1)}{2}$；
对其余数据，无特殊限制。

对于 $100\%$ 的数据，满足 $1 \leq n, m \leq 5\times 10^5$，$1 \leq a_i \leq n$，$a_i$ 互不相同，$1 \leq l \leq r \leq n$，所有数值为整数。


title: [WC2022] 猜词（民间数据）

background:
**滥用本题评测将直接封号。**

**由于评测机环境限制，请勿使用 C++14 (GCC 9) 语言提交本题，否则可能导致编译错误。**

使用了 出题人 发送的官方数据，但是由于存在争议先保留民间数据称号。

60 s, 1 GiB, -O2, 交互

在洛谷提交时请注意以下两点：

- **请去除代码中的 `word.h` 头文件。**

- **不要使用 `rand()` 进行随机。** 请更换为 `mt19937` 。注意不要重名了，不然会 CE。具体请查看[此处](https://www.luogu.com.cn/discuss/405355)。

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

description:
在本题中，你需要和交互库玩一款经典的游戏。在每局游戏中，交互库会从词库中生成一个 $5$ 个字母的单词，并告诉你它的首字母，你需要在 $5$ 次机会内猜中它。

每次猜测都需要猜一个词库中存在的单词。如果猜对了，游戏结束；在每次猜错后，交互库会返回哪些字母的位置是正确的（以金色表示），以及哪些字母在待猜单词中出现了但位置是错误的（以银色表示）。

具体来说，交互库会返回两个布尔类型的数组 $\texttt{gold}$ 和 $\texttt{silver}$。`gold[i]`（$0 \leq i < 5$，下同）表示第 $i$ 个字母是否猜对了（位置和内容均正确）；`silver[i]` 表示如果第 $i$ 个字母没猜对（即不为金色），这个字母是否在本次猜测非金色字母的部分出现过。

例如，待猜单词为 $\texttt{panic}$，猜测 $\texttt{paper}$ 后交互库会返回 `gold[0] = true`（$\texttt{p}$ 正确），`gold[1] = true`（$\texttt{a}$ 正确），其余均为 `false`（注意 $\texttt{paper}$ 中的第二个 $\texttt{p}$ 虽然在 $\texttt{panic}$ 中出现过，但出现位置为本次猜测中的金色字母部分，因此 `silver[2] = false`）。

又如，待猜单词为 $\texttt{apple}$，猜测 $\texttt{paper}$ 后交互库会返回 `gold[2] = true`（$\texttt{p}$ 正确），`silver[0] = true`（$\texttt{p}$ 在本次猜测非金色字母的部分出现过），`silver[1] = true`（$\texttt{a}$ 出现过），`silver[3] = true`（$\texttt{e}$ 出现过），其余均为 `false`。

**【评分方式】**

由于每局游戏具有较高的随机性，在本题中，你需要连续玩 $T = 1000$ 局游戏。每局游戏的评分标准如下：

- 如果任意一次猜测单词的长度不等于 $5$，或者**猜测的单词不在词库中**，得 $0$ 分；
- 如果第 $1$ 次猜测猜对，得 $150$ 分；
- 如果第 $2$ 次猜测猜对，得 $120$ 分；
- 如果第 $3$ 次猜测猜对，得 $100$ 分；
- 如果第 $4$ 次猜测猜对，得 $90$ 分；
- 如果第 $5$ 次猜测猜对，得 $85$ 分；
- 如果 $5$ 次猜测均错，得 $0$ 分。你在本题中的得分为【$1000$ 局游戏的平均分】和 $100$ 分的较小值。

**【如何使用交互库】**

本题只支持 C++。

你只能提交一个源文件 `word.cpp` 实现下列函数，并且遵循下面的命名和接口。

你需要包含头文件 `word.h`。

你不需要，也不应该实现主函数。

你需要实现的函数有：

```cpp
const char *guess(int num_testcase, int remaining_guesses, char initial_letter, bool *gold, bool *silver);
void init(int num_scramble, const char *scramble);
```

其中，第 $i$ 局游戏的 `num_testcase` 参数为 $i$（$1 \leq i \leq T$），每局游戏会调用 $1 \sim 5$ 次 `guess` 函数，第 $j$ 次调用的 `remaining_guesses` 参数为 $6-j$（$1 \leq j \leq 5$）。`initial_letter` 参数为当前局游戏待猜单词的首字母（保证为小写字母）。保证每次调用 `guess` 函数的 `num_testcase` 单调不降；保证 `num_testcase` 相同时 `initial_letter` 不变且 `remaining_guesses` 单调递降。如果某次猜测猜对或非法，则该局游戏结束，下次调用 `guess` 函数为下一局游戏。

`gold` 和 `silver` 为如上所述的两个布尔数组。当 `remaining_guesses` 参数为 $5$ 时，`gold` 和 `silver` 数组不可用（即，可能为空指针），请避免使用它们；当 `remaining_guesses` 参数小于 $5$ 时，`gold` 和 `silver` 为两个大小为 $5$ 的布尔数组，存储着上一次猜测的结果。

`guess` 函数的返回值需要是一个长度为 $5$ 的字符串，表示猜测的单词。该单词需要在词库中。

`init` 函数会在调用所有 `guess` 函数之前调用恰好一次。其中 `num_scramble` 参数是词库大小，`scramble` 是一个长度为 $\texttt{num\_scramble} \times 5$ 的字符串，存储着词库中的所有单词，每个单词长度为 $5$，中间没有任何分隔符。

**【附加文件】**

本题下发的文件有 `word.h, word_sample.cpp, play.cpp, grader.cpp, scramble.txt, scramble.csv, scramble_pure.txt`。

`word_sample.cpp` 是你要实现的 `word.cpp` 的一个样例。

`grader.cpp` 为示例评测程序（编译命令：`g++ ‐o grader grader.cpp word.cpp`）。

`scramble.txt, scramble.csv, scramble_pure.txt` 均为本题所使用的词库文件，其中 `scramble.txt` 以换行符分隔单词，`scramble.csv` 以逗号分隔单词，`scramble_pure.txt` 不分隔单词（即，与 `init` 函数中的 `scramble` 参数内容相同）。

`play.cpp` 是一个可以让你和你的程序玩这个游戏的程序（编译命令：`g++ ‐o play play.cpp word.cpp`）。下面介绍 `play.cpp` 的输入与输出格式。

inputFormat:
**【样例输入格式】**

输入第一行包含一个正整数 $T$，表示游戏局数。

接下来 $T$ 局游戏，每局游戏第一行输入一个小写字母，表示待猜单词的首字母。

接下来 $0 \sim 4$ 行，每行一个长度为 $5$ 的由 $\texttt{g}$、$\texttt{s}$、$\texttt{-}$ 组成的字符串，其中第 $i$ 位（$0 \leq i < 5$，下同）是 $\texttt{g}$ 表示 `gold[i] = true`，第 $i$ 位是 $\texttt{s}$ 表示 `silver[i] = true`，第 $i$ 位是 $\texttt{-}$ 表示 `gold[i] = silver[i] = false`。如果猜对或猜测单词非法，则该局游戏结束，因此输入的行数是可变的。

outputFormat:
**【样例输出格式】**

对于除了第一行游戏局数以外的每行输入，输出一个长度为 $5$ 的字符串，表示猜测的单词。样例输出加入了额外的空行以便阅读。

samples:
7
p
gg---
gg---
ggg--
a
g----
ssgs-
a
g---g
gggg-
a
g---g
g---g
g---g
g---g
a
a
c
-sss-

samples:
paper
paths
panda
panic

aargh
paper
apple

afore
apply
apple

apple
apple
apple
apple
apple

abcde

apple

kraal
cobra

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

对于第 $1$ 局游戏，待猜单词为 $\texttt{panic}$，在第 $4$ 次猜测猜对。

对于第 $2$ 局游戏，待猜单词为 $\texttt{apple}$，在第 $3$ 次猜测猜对。

对于第 $3$ 局游戏，待猜单词为 $\texttt{apple}$，在第 $3$ 次猜测猜对。注意即使每个位置都有至少一次猜测为金色，也需要额外一次猜测才算猜对。

对于第 $4$ 局游戏，待猜单词为 $\texttt{above}$，$5$ 次猜测均错。注意第 $5$ 次猜测的结果并不需要输入，也不会传入 `guess` 函数。

对于第 $5$ 局游戏，待猜单词为 $\texttt{apple}$，第 $1$ 次猜测非法（不在词库内），该局游戏直接结束。注意样例程序并不会自动识别这种情况。

对于第 $6$ 局游戏，待猜单词为 $\texttt{apple}$，在第 $1$ 次猜测猜对。

对于第 $7$ 局游戏，待猜单词为 $\texttt{cobra}$。注意猜测 $\texttt{kraal}$ 时两个 $\texttt{a}$ 均为银色。注意由于样例程序并不知道待猜单词是什么，需要手动结束程序。

**【数据范围】**

对于 $100\%$ 的数据，$T = 1000$，$\texttt{num\_scramble} = 8869$。每次待猜的单词均在词库中所有单词这一范围内独立均匀随机生成，这些单词在调用 `guess` 函数之前已经完全确定，不会根据和你的程序的交互过程动态构造。交互库本身使用的时间不超过 $1$ 秒，使用的内存不超过 16 MiB。

由于本题只有 $1$ 组评测数据，运行错误、超时、内存超限等错误都会导致本题总分为 $0$ 分。建议仔细检查避免此类错误。


title: 伟大的神

background:
伟大的神 $\text{T}\color{red}\text{nyieldingUrilobite}$ （以下简称 TU）喜欢字符串，在 AK 了 IOI 后的第 $998244353$ 天后，伟大的神 TU 勒令小 s 找出他喜欢的字符串。

否则，小 s 就要被吊打 $10^{998244353}$ 年。（虽然找出来了也要被吊打）

description:
伟大的神 TU 认为 ，一个所有出现的字符的数量相等的字符串是属于神的，他称之为神之字符串。

对于一个字符串 $S$，如果它的一个子串为神之字符串，即称这个子串为神之子串。

神 TU 认为，他喜欢的字符串只能由 `l` 和 `r` 构成，并且还要满足以下条件：

   - 字符串的长度为 $n$。
   - 字符串中最长神之子串长度为 $m$。
   - 字符串中连续的相同的字符的数量不能超过 $k$。

弱小的神小 s 找不出神 TU 喜欢的字符串，现在他找到了你，你能帮帮他吗？

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

题目保证输入的 $m$ 是偶数。

outputFormat:
请输出任意一种神 TU 喜欢的字符串。

数据保证可以找出神 TU 喜欢的字符串。

samples:
10 6 3
lllrrlrlll

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

对于 $100\%$ 的数据，保证 $1\le k\le10^5$，$4\le m\le n \le 10^5$。

数据保证可以找出神 TU 喜欢的字符串。

Subtask 1：对于 $5\%$ 的数据，保证 $k=1$。

Subtask 2：对于另外 $10\%$ 的数据，保证 $n=m$。

Subtask 3：对于另外 $30\%$ 的数据，保证 $k \ge 3$。

Subtask 4：无特殊性质。


title: 「Wdoi-1.5」旅人 1977

background:
深邃的星空中划出了一道灿烂的弧线，而后又同这广袤境界溶为一体，二十世纪的旅行者，承载着期待与不安向着外太空飞去。这是一份来自一个遥远的小小世界的礼物。上面记载着我们的声音、我们的科学、我们的影像、我们的音乐、我们的思想和感情。我们正努力生活过我们的时代，进入你们的时代。或许人类将失去对它的联系，它也将像一个漂流瓶一样，向着宇宙深处孤独的走下去，直到被「另一个人」所捡起。而它为我们留下的最后一张「自拍」，也只是一个 $0.12$ 像素大的、淡蓝色的光点 —— 这是我们迄今所知的唯一家园。

$\kern{80pt}$![](https://cdn.luogu.com.cn/upload/image_hosting/qbelj85l.png)
$$\\[-1em]\scriptscriptstyle\text{暗淡蓝点，旅行者 1 号，1990年 2 月 14 日}$$
「已经分不清现实与梦境了呢。」
「或许，梦与现之间的境界，本就没有那么明晰。」

……

「真是的，莲子你不是自称亲近星光与月亮的嘛，怎么也不抬头看看。」

正欲向笔记本上添加几行，借以目视的月光陡然暗淡。眼前垂落的金色长发挡住了我的视线。轻咳了一声，抬起手在面前挥舞，把他们从视野中赶走，我转头看着后背。
眼前戴着白色帽子的少女便是我的同伴梅莉。我常常打趣她有着奇异的眼睛，可以看到我们所看不到的「境界」。尽管我自己的眼睛也十分特殊——我有着通过星光与月亮就知道我们现处何时何地的能力。忘了说了，我们是学生秘密社团『秘封俱乐部』，专门探寻科学世纪下的隐藏结界。
在这个夏夜，我本着履行对她承诺的想法，来到野外，观察天体的运行。

「在想什么呢？」
这个问题不好回答呢。不过，既然今天和梅莉约好出来观赏星空，那么，思路被引向人们曾经的探索和求知，便是十分自然的了。
「唔，我在想，我们现今，科学世纪的起源。」
「嗯？莲子你不是研究物理的吗，怎么突然思考其这种问题了？」
梅莉把头朝右侧一歪，我指指天空，她随即坐在了一旁，把目光投向灿烂的星海。
「唔，我在想，我们现今，科学世纪的起源。还记得我和你说过的那两位旅人吗？」
「旅行者一号与旅行者二号？」
「没错。直到如今都没有人为任何深空计划取名为旅行者。带着如此诗意而感性名称的它们代表的是人们对未来的期许与对真理的渴望。面对未知与迷茫，义无反顾冲向了星海。」

梅莉站了起来，举起了双筒望远镜。她的身影在暗淡而幽静的夜色中来回移动，皎白得似有彩色光晕的月光从穹顶透过树叶与树枝的缝隙在她身上落下光斑，看着让人心醉。

超新星爆发是恒星生命的终点，也是新生恒星生命的起点。谁能说科学已经到了尽头，无法解释的事物不存在呢？科学的核心在于那些被视为空花阳焰，藏在迷雾中的东西，而绝非那些狂妄自大的老头们所说，科学是我们掌握的一切已知。
对我们而言，这是不言而喻的。我们追随那位初代社长的脚步，探寻遍布四处的结界，寻求隐藏在未知背后真理的一角，正是出于这样的信念。

晷刻渐移，点点星尘围绕着北极星作着圆周运动。仔细看的话，北极星也在微微运动。在我的视线前方，梅莉兴奋地对着从英仙座辐射而出，偶尔划过天穹的流星发出惊叹。我不禁思索起来，现在勾陈一作为最接近北天极的恒星行使着为旅人指点方向的责任，但在永恒的运动中，永远会有新的谜题，新的未知，新的探索等着我们去发现。

物如此，事犹是，人亦然。前路永远有着未知的事物等着我们去探索。如果解明了所有的秘密，之后就会什么都不剩。知晓万物什么的，只不过是空空如也的虚无罢了。未知，才是驱动人类的原动力 $\scriptscriptstyle{}^{[{\color{grey}{1}}]}$。我们希冀着如同那两位先行者一般，作为开拓者，唤起根植于人们心中对未知的好奇与探索精神，并将它薪火相传。
身虽位于苍穹一粟，心亦向往若尘繁星。
身旁的梅莉靠在一棵树下，已经发出规律的鼾声，身体规律地微微起伏着。我伸手拨开她的手掌，撩开她垂下的头发，拿出她的笔记本。
>从夜晚走向清晨。
从清晨走向夜晚。
从现实走向梦境。
从梦境走向现实。
终有一天，我们会在梦中，邂逅那片未经观测的星空。$\scriptscriptstyle{}^{[{\color{grey}{2}}]}$

$\scriptscriptstyle{[1],[2]}\text{：引用自 }$ [here](https://bbs.nyasama.com/forum.php?mod=viewthread&tid=308054&page=2)

description:
深邃的星空可以被视作一张有向图，图上的节点就是点点恒星。点无点权，边有边权。图的点数为 $n$，边数为 $m$，图可能有重边自环。但保证至少有一条路径可以从 $s$ 走到 $t$（$s$、$t$ 在输入中给定）。第 $i$ 条有向边起点为 $u_i$，终点为 $v_i$，它的权值用一个有序三元组 $(l_i,r_i,w_i)$ 表示。

莲子要从点 $s$ 出发，经过了若干条边到达点 $t$。她带有一个初始值均为 $0$ 的长度为 $k$ 的数组 $a$，每次经过编号为 $i$ 的边，就会执行将 $a$ 数组的区间 $[l_i,r_i]$ 加 $w_i$ 的操作。她使用了一棵**带懒标记**的线段树来维护这一操作。线段树的写法会在接下来给出。

你需要构造一条从 $s$ 到 $t$ 的路径，满足达到结点 $t$ 时，其线段树上所有标记的和的最小。输出这个最小值。

以下是线段树的伪代码：（为了方便选手阅读，题目附件中给出了线段树的 C++ 源代码）

$$
\begin{array}{l}\hline\hline\\[-0.8em]
\textbf{Algorithm: }\text{SegTree}\\\hline\\[-0.5em]
\begin{array}{rl}
1& \mathbf{Input.} \text{ 长度为 $k$ 的 $a$ 数组，初始全为 $0$}\\
2& \mathbf{Output.} \text{ $a$ 数组进行若干次区间加操作后得到的结果}\\
3& \mathbf{Method.}\\
4& \mathrm{Add}(L,R,x)\\
5& \quad\mathrm{Add0}(L,R,x,root,1,k)\\
6& \mathrm{Add0}(L,R,x,u,l,r)\\
7& \quad\mathbf{if}\ L \le l\ \mathbf{and}\ r\le R\\
8& \quad\quad \mathrm{tag}(u) \gets \mathrm{tag}(u) + x\\
9& \quad\quad \mathbf{return}\\
10& \quad mid \gets \lfloor\frac{l+r} 2\rfloor\\
11& \quad \mathrm{tag}(\mathrm{lson}(u)) \gets \mathrm{tag}(\mathrm{lson}(u))+\mathrm{tag}(u)\\
12& \quad \mathrm{tag}(\mathrm{rson}(u)) \gets \mathrm{tag}(\mathrm{rson}(u))+\mathrm{tag}(u)\\
13& \quad \mathrm{tag}(u) \gets 0\\
14& \quad\mathbf{if}\ L \le mid\\
15& \quad\quad\mathrm{Add0}(L,R,x,\mathrm{lson}(u),l,mid)\\
16& \quad\mathbf{if}\ mid < R\\
17& \quad\quad\mathrm{Add0}(L,R,x,\mathrm{rson}(u),mid+1,r)\\
\end{array}\\\hline\hline
\end{array}
$$

inputFormat:
- 第一行五个整数 $n,m,k,s,t$。
- 接下来 $m$ 行，每行五个整数 $u_i,v_i,l_i,r_i,w_i$。

outputFormat: - 共一行一个整数，表示沿着你构造的路径从 $s$ 到达 $t$ 后线段树上所有懒标记的权值之和。

hint:
### 样例解释

#### 样例 \#1

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

容易发现，样例 $1$ 中有且仅有两条可能的路径：$1\to 2\to 4$ 与 $1\to 3\to 4$。下面分别计算这两条路径最终 $\text{tag}$ 的权值和。

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

考虑画出这棵 $k=5$ 的线段树。

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

走了边 $1\to 2$ 后，$[1,2]$ 节点被打上了权值为 $2$ 的 $\text{tag}$。

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

走了 $2\to 4$ 后，$[2,2]$ 节点和 $[3,3]$ 节点被打上了值为 $1$ 的 $\text{tag}$；但是 $[1,2]$ 节点的标记进行了下推（因为使 $[2,3]$ 区间 $+1$ 的时候会访问到 $[1,2]$ 节点，而 $[1,2]\nsubseteq[2,3]$，故而发生标记下推），因此 $[1,1]$ 节点和 $[2,2]$ 节点的 $\text{tag}$ 分别加上了 $2$，最终成了如图所示的模样。

因此走到 $4$ 之后所有结点的 $\text{tag}$ 之和为 $2+3+1=6$。

---

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

对于另外一条路径，首先对 $[4,5]$ 加上 $1$。

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

接着对 $[3,5]$ 加上 $2$。未发生带有 $\text{tag}$ 的节点的标记下推，因此最终的权值为 $2+3=5$。

由于 $6>5$，因而最终的答案为 $5$。

### 数据范围及约定

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|}\hline
\textbf{subtask}& \textbf{分值}& {\bm n\le} & {\bm m\le} & {\bm k\le} & \textbf{特殊性质} & \textbf{subtask 依赖}\cr\hline
1 & 10& 10 & 30 & 5 & - & -\cr\hline
2 & 5&30 & 30 & 12 & \textbf{AB} &-\cr\hline
3 & 20&30 & 500 & 12 & \textbf{B} &2 \cr\hline
4 & 15&200 & 3\times 10^3 & 25 & \textbf{B}&3\cr\hline
5 & 50&200 & 3\times 10^3 & 25 & - &4\cr\hline
\end{array}
$$

- **特殊性质** $\textbf{A}$：保证有且仅有一条从 $s$ 到 $t$ 的路径。
- **特殊性质** $\textbf{B}$：保证图中不存在环。

对于 $100\%$ 的数据，有 $1 \le s,t,u_i,v_i \leq n \leq 200$，$1 \leq m \leq 3\times 10^3$，$1 \leq l_i\le r_i \leq k \leq 25$，$1 \leq w_i \leq 10^3$。

### 提示

在附件中有两个版本的线段树。$\text{Lite}$ 版本**仅**包含了在本题中你会用到的下推标记的操作，而标准版则较为完整地支持区间加、区间求和。选手可根据自己的喜好使用。


title: [FOI2021] 幸运区间

background: 2021 年福建省青少年信息学编程水平认证 第四题。

description:
一个抽奖活动正在进行。每个参加活动的人拿到了 $n$ 个序列，每个序列包含了 $d$ 个正整数，以及一个数字 $k$，代表这些正整数中，存在 $k$ 个幸运数字。

每个拿到序列的人，会从自己手中的序列中选出连续的若干个序列形成一个区间，称之为待选区间。如果待选区间中的每一个序列都包含至少一个幸运数字，则称该区间为幸运区间。当然幸运区间可能不止一个。游戏规定，其中包含的序列最多的即总长度最长的那个幸运区间称为超级幸运区间。

例如：$d=2,k=3$ 时，序列如下：

- 序列 $0$：``115 120``。
- 序列 $1$：``50 80``。
- 序列 $2$：``199 30``。
- 序列 $3$：``40 40``。
- 序列 $4$：``30 30``。
- 序列 $5$：``25 40``。

从序列 $0$ 到序列 $2$ 的区间是幸运区间，因为从 $0$ 到 $2$ 中的每个序列都包含了 $120,50$ 或 $30$，共 $3$ 个幸运数字。从序列 $1$ 到序列 $5$ 的区间也是幸运区间，因为 $1$ 到 $5$ 的所有序列都包含 $80,30$ 或 $40$，并且包含了 $5$ 个序列，是总长度最大的超级幸运区间。

每个有序列的人都想知道自己的超级幸运区间是怎样的。编程任务就是对于每个拿到序列的人，输出总长度最大的超级幸运区间的第一个元素的下标和最后一个元素的下标。如果有多个长度一样的，输出第一个元素下标最小的。请注意下标从 $0$ 开始。

inputFormat:
第一行包含一个整数 $T$，表示拿到序列的人的数量。

接下来 $T$ 组数字，每组描述的是每个人的序列信息。

每组数据的第一行是三个正整数 $n,d,k$，描述如上。接下来一行，包含 $n\times d$ 个整数，前 $d$ 个整数表示第 $0$ 个序列，接下来 $d$ 个表示第 $1$ 个序列，以此类推。

outputFormat:
对于每个人，输出一行，``Case #x: y z``，$x$ 表示 $\text{case}$ 标号（从 $1$ 开始），$y$ 和 $z$ 是答案区间的第一个和最后一个元素的下标。

（``Case`` 与 ``#`` 之间有一个空格，``#`` 与 ``x`` 之间没有空格，``:`` 后面 ``y`` 之前有一个空格，``y`` 与 ``z`` 之间有一个空格）

hint:
#### 数据范围

对于 $45\%$ 的数据，$n\le1000$。

对于 $50\%$ 的数据，$k=2$。

前两部分数据共计 $70\%$。

对于 $100\%$ 的数据，$2\le k\le 3$。

输入文件在 $\text{4.8M}$ 以内，$T=10,1\le d\le 4,1\le$ 每个序列中的数字 $\le10^5$。

对于最多 $6$ 个 $\text{case}$，$1\le n\le 10^5$，对于其他所有的 $\text{case}$，$1\le n\le 10^3$。


title: 「GLR-R3」谷雨

background:
  「几枝新叶萧萧竹，数笔横皴淡淡山」

---

  十几天前的那条路，还好，两个人一起。

  “很幸运呢”，阿绫悄悄嘬一口才破涕为笑的天依，“上天保佑我们要在一……”

  鼓着腮掐着软软的腰，天依却又不觉流露笑意，是很幸运呢，刚好入围……

  鳞次栉比的尽头，天空似云下起伏的山，皴擦着淡青墨样的欣喜。

  她们的故事还在继续，正如谷物正当在今日生长。

---

  **谷雨** 「我翻过一座高山　前方依然　山路漫漫」

description:
老 V 为发挥不错的大家办了场小 party，为了活跃气氛，同时贯彻安全环保的理念，~~（主要还是因为编不出来了，）~~ 老 V 带来了一个高大上的“电子烟花”，美其名曰，火**树**银花。

物如其名，这是一棵含有 $n$ 个结点的树，结点 $u$ 上有点权 $l_u$，表示该结点上所设烟花样式的**绚丽度**。好奇的大家一共对它进行了 $q$ 次操作，不妨记树上从 $u$ 到 $v$ 的路径上的结点（含 $u,v$）构成集合 $P(u,v)$，则每次操作形如：

0. 给定结点编号 $u,v$ 和新的绚丽度 $k$，意为将所有 $\in P(u,v)$，**或者**存在一个邻接点 $\in P(u,v)$ 的结点 $w$ 的绚丽度 $l_w$ **赋值**为 $k$。

1. 给定 $u,v$，点燃这一串烟花最“耀眼”的子段。具体地，维护一个**序列** $S$，从 $u$ 出发沿着树边走向 $v$，当走到结点 $w$（$w$ 可能为 $u$ 或 $v$） 时：

    - 将 $l_w$ 加入序列 $S$ 的末尾；
    - **按标号从小到大**枚举 $w$ 的邻接点 $x$，若 $x\notin P(u,v)$，将 $l_x$ 加入 $S$ 的末尾；
    - 最后，走向下一个结点。

得到最终的 $S$ 后，系统将自动点燃 $S$ 中绚丽度之和最大的子段，子段可能为空。而你需要求出这一和的最大值，即对于每次 1. 操作，求出 $S$ 的**最大可空子段和**。

inputFormat:
第一行一个整数 $T$，表示该测试数据所属的子任务编号。

第二行一个整数 $n$，表示树的结点个数。

第三行 $n$ 个整数，第 $i$ 个整数 $l_i$ 表示结点 $i$ 的初始权值。

第四行 $n-1$ 个整数，**为方便选手处理数据，此处假设 $1$ 号结点为树的根。** 第 $i$ 个整数 $p_i$ 表示结点 $i+1$ 的父亲，即表述一条边 $(p_i,i+1)$。**保证 $p_i<i+1$**。

第五行一个整数 $q$，表示需要处理的操作数量。

接下来 $q$ 行，每行格式为 $0~u~v~k$ 或者 $1~u~v$，分别对应了「题目描述」中的两种操作。

outputFormat: 输出有若干行，第 $i$ 行应包含一个整数 $a_i$，表示第 $i$ 次 1. 操作的答案。


title: 「GLR-R3」清明

background:
  「       ，       」

---

  “你非说这不是我的实力，那凭什么一个偶然错音就不能毁了我的命运？！”

  天依没有注意到，心中所哭嚎向的那个人，同她一样撑着伞，身后十来步而已。

---

  **清明**　「你在名为弱小的深渊　究竟看见过什么」

description:
雨打在窗沿，下坠，一级一级。

这里一共有 $n$ 级窗沿，从高到低编号，最高层编号为 $1$，最底层编号为 $n$。假设在某一瞬间，第 $i$ 级窗沿上有 $a_i$ 单位体积的雨水。由于奇妙的物理原因，第 $i$ 级的雨水将在「下一个瞬间」滴向第 $i+1,i+2,\dots,\min\{i+k,n\}$ 级，也可能留在第 $i$ 级，但是每一种去向的雨水的单位体积都应是非负整数，且总和为 $a_i$。

设在「下一个瞬间」，第 $i$ 级窗沿上有 $a_i'$ 单位的雨水，那么称此时雨水的**奇妙度**为 $\prod_{i=1}^n a_i'$。现在，悲伤的人儿想知道，对于所有**本质不同的**「下一个瞬间」，雨水的奇妙度之和对素数 $P=998244353$ 取模的结果。

两个「下一个瞬间」本质不同，当且仅当存在编号 $i<j$ 的两级窗沿，从窗沿 $i$ 滴向窗沿 $j$ 的雨水的单位体积不同。

inputFormat:
第一行输入两个正整数 $n,k$，分别表示窗沿的数量、限制雨点滴落距离的常数。

第二行输入 $n$ 个非负整数 $a_1,a_2,a_3,\cdots,a_n$，其中 $a_i$ 表示第 $i$ 级窗沿在这一瞬间的雨水体积。

outputFormat: 输出一行一个整数，表示所有本质不同的「下一个瞬间」，雨水的奇妙度之和对 $P$ 取模后的结果。


title: [eJOI2021] AddK

description:
给定一个包含 $N$ 个整数 $A_1,\dots,A_N$ 的数组 $A$ 和一个整数 $K$。你需要进行 $Q$ 次操作，包括下列两种类型：

- $1$ $i_1$ $i_2$ $\dots$ $i_K$：将 $A_{i_1},A_{i_2},\dots,A_{i_{K-1}},A_{i_K}$ 的值依次替换为 $A_{i_2},A_{i_3},\dots,A_{i_K},A_{i_1}$ 的值。其中，$i_1,\dots,i_k$ 互不相同。
- $2$ $l$ $r$ $m$：输出 $[l,r]$ 区间内所有长度为 $m$ 的连续子序列的元素和。

inputFormat:
第一行两个整数 $N,K$。

第二行 $N$ 个整数，表示数组 $A$ 的 $N$ 个整数。

第三行一个整数 $Q$，表示操作次数。

接下来 $Q$ 行，每行若干个整数，表示一次操作。

outputFormat: 输出包含若干行整数，即为所有操作 $2$ 的结果。


title: [eJOI2021] Kpart

description:
当一个只包含正整数的数组 $A$ 的所有长度为 $K$ 的连续子序列都能够被分成元素和相等的两部分时，数组 $A$ 就被称为 $K$ 数组。例如，$\{1,2,1,3\}$ 是一个 $3$ 数组，因为 $\{1,2,1\}$ 可被分为 $\{1,1\}$ 和 $\{2\}$ 且和均为 $2$，而 $\{2,1,3\}$ 可被分为 $\{1,2\}$ 和 $\{3\}$ 且和均为 $3$。但该数组不是 $2$ 数组，因为 $\{1,2\}$ 不能分成元素和相等的两个部分。

给定 $T$ 个只包含正整数的数组，分别求每个数组为 $K$ 数组时所有 $K$ 的取值。

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

接下来将描述 $T$ 个数组。其中第一行包含整数 $N$，第二行 $N$ 个整数，表示数组的元素。

outputFormat: 输出 $T$ 行，每行输出对应数组所有 $K$ 的取值。

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

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

- Subtask 1（10 pts）：$1 \le N \le 30$。
- Subtask 2（20 pts）：$31 \le N \le 120$。
- Subtask 3（70 pts）：$121 \le N \le 1000$。

对于 $100\%$ 的数据，$1 \le T \le 120$，每个数组的元素和均不超过 $10^5$。

#### 说明

本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 1 B Kpart。


title: 再会 | Sayounara

background:
「过去的都已经无所谓了吗？」

“还没有达到那种地步。”

「想做的事都已经完成了吗？」

“如今的自己，也好像只能在取舍中前行。”

「道过再会了吗？」

“… 还没有，但我正尝试着。”

> I have
>
> 我仍有
>
> plenty want to say
>
> 无数未道尽的言语
>
> Before
>
> 在离开之前
>
> I leave this world
>
> 在再会之前

description:
「这是…？」

“啊… 我自己写的日记管理程序。”

「噗… ‘正常人谁写日记啊’，平时的你应该会这样说吧？」

“… 别拿我说笑。”

「好吧好吧。不过看上去你不记得密码了呢？」

“…… 我自有手段。”

「咦…？这什么，恢复软件吗？」

“嗯… 密码可以被表示为一个长为 $n$ 的非负整数序列，**其中每个元素都互不相同** 。这个软件可以执行两种操作：一是，询问一个连续区间的总和减去这个区间最小值的结果；二是，询问一个位置的值。现在我需要找回密码的话…”

「欸？为什么不直接用 $n$ 次第二种操作呢？」

“这是试用版… 所以第二种操作只有两次使用的体验权限… 而且第一种操作似乎也有一定的限制，所以…”

「这… 话说为什么恢复个密码这么麻烦啊？不应该会有‘找回密码’之类方便的机制吗？」

“… 多半还是那个人的安排吧。”

### 简要题意

有一个元素互不相同的非负整数序列 $a$，其长度为 $n$。你可以多次进行以下两种询问之一：

- 给出 $l,r$，得到 $\left(\sum_{k=l}^r a_k\right)-\left(\min_{k=l}^r a_k\right)$。

- 给出 $k$，得到 $a_k$ 的值。这种询问最多只能进行两次。

你需要在尽可能少的询问次数内推断出该序列的内容。

**本题询问均以 $1$ 为初始下标，但你返回答案时需要返回以 $0$ 为初始下标的 `vector`，请留意。**

### 交互说明

本题仅限 C++11 / C++17 提交。你需要实现以下的函数：

```cpp
#include <cstdint>
#include <vector>

std::vector<uint32_t> recover(int n);
```

该函数接收密码长度 $n$，返回还原的密码（返回值应该是一个大小为 $n$ 的 `vector`）。你可以使用以下两个函数

```cpp
#include <cstdint>

uint64_t query(int l, int r);
uint32_t get(int x);
```

其中 `query` 对应题目中的第一种操作，`get` 对应题目中的第二种操作。

下面是一个示例程序（仅演示交互库操作）：

```cpp
#include <cstdint>
#include <vector>

uint64_t query(int l, int r);
uint32_t get(int x);

std::vector<uint32_t> recover(int n) {
	std::vector<uint32_t> ans(n);
	int what = query(1, n), hey = get(1);
	for (int i = 0; i < n; ++i) ans[i] = i + 1;
	return ans;
}
```

题目提供了示例交互库 `lib.cpp`（并非交互库真实实现）。你可以在本地使用命令 `g++ -o code code.cpp lib.cpp` 来编译运行。

inputFormat:
**这是交互库的输入格式，选手不需要，也无法从标准输入中读取任何信息。**

第一行，一个正整数 $n$ 表示密码长度。

第二行，$n$ 个非负整数表示密码。

outputFormat:
**这是交互库的输出格式，选手不需要，也无法向标准输出中写入任何信息。**

输出有四种：

- `0 A B`：选手答案正确。其中 `A` 代表操作一的使用次数，`B` 代表操作二的使用次数。

- `-1`：选手函数成功执行，但答案不正确。

- `-2`：选手在调用操作一时传入的 $l,r$ 不满足要求。

- `-3`：选手调用了超过 $2n$ 次操作一。

- `-4`：选手调用了超过两次操作二。

hint:
### 得分细则

本题没有子任务。所有测试点保证 $n=10^6$。

如果你在任何一个测试点中答案错误或超出询问限制，则本题你会得到 0 分的好成绩。

如果你成功通过了所有测试点，记你在所有数据中调用操作一最多一次的次数为 $x$，则你本题的分数为：

$$
\begin{cases}
\frac{60}{e^7-1}\left(e^{10-\max\left\{\frac{x-10^6}{100},3\right\}}-1\right)+40,&x\le 1001000\\
25,&\mathrm{otherwise.}
\end{cases}
$$


title: [eJOI2021] XCopy

description:
给定正整数 $N,M$。

请构造一个 $N \times M$ 的只包含非负整数的矩阵，使得每个元素互不相同且相邻（上下左右）元素在二进制下只有一位不同，同时保证矩阵的最大元素最小。

inputFormat: 一行两个正整数 $N,M$。

outputFormat: 一个 $N \times M$ 的只包含非负整数的矩阵。**Special Judge 对输出格式要求非常严格，每行行末不能有空格等多余字符。**

hint:
#### 评分规则

本题采用部分分计分，分数取决于输出答案和正确答案的大小。其中「答案」指的是矩阵中的最大元素。

设 $S$ 为该测试点的总分，$O$ 为正确答案。那么当 $G$ 为输出答案时，得分为：

$$S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0)$$

由于洛谷评分机制，每个测试点的实际得分为上式下取整的结果，即 $\lfloor S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0) \rfloor$。例如，当 $S=7,G=15,O=10$ 时，按上式得分约为 $4.14$ ，但在洛谷上得分为 $4$。

如果输出矩阵不满足要求（即元素互不相同且相邻元素在二进制下只有一位不同），那么该测试点计 $0$ 分。

注意，由于 Special Judge 对于格式要求较高，请在输出答案时**不要在每行末尾添加多余空格**，否则对应测试点会被计为 $0$ 分。另外，请不要输出超出 $[0,2^{63})$ 范围（long long）的整数，否则会被判为格式错误，计 $0$ 分。

#### 样例解释

样例矩阵如下：

|$0101_2=5_{10}$|$0100_2=4_{10}$|$0110_2=6_{10}$|
| :----------: | :----------: | :----------: |
|$0001_2=1_{10}$|$0000_2=0_{10}$|$0010_2=2_{10}$|
|$1001_2=9_{10}$|$1000_2=8_{10}$|$1010_2=10_{10}$|

通过观察不难发现，每两个相邻元素在二进制下都只有一位不同。这种做法的答案为 $10$（即最大元素），是所有做法中最小的。当然，其它的最大元素为 $10$ 的矩阵也是符合题意的（例如将输入矩阵进行翻转操作等）。

一种可以获得部分分的做法是：

|$0110_2$|$0111_2$|$0101_2$|
| :----------: | :----------: | :----------: |
|$1110_2$|$1111_2$|$1101_2$|
|$1010_2$|$1011_2$|$1001_2$|

该矩阵的最大元素为 $15$。根据评分规则，这种做法在下取整前可以获得对应测试点 $\max(1-\sqrt{\dfrac{\frac{15}{10}-1}{3}},0)=1-\dfrac{\sqrt{6}}{6} \approx 59\%$ 的分数。

#### 数据规模与约定

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

- Subtask 1（7 pts）：$N=1$。
- Subtask 2（9 pts）：$N,M$ 是 $2$ 的整数幂。
- Subtask 3（14 pts）：$N$ 是 $2$ 的整数幂。
- Subtask 4（70 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,M \le 2000$。

#### 说明

本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 1 C XCopy。欢迎通过私信或发帖的方式对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/cbrnaqp0) 进行 hack。


title: [eJOI2021] BinSearch

description:
```cpp
bool binary_search(int n, int p[], int target){
    int left = 1, right = n;
    while(left < right){
        int mid = (left + right) / 2;
        if(p[mid] == target)
            return true;
        else if(p[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    if(p[left] == target) return true;
    else return false;
}
```

众所周知，当上述函数在传入一个单调不递减的数组 $\texttt p$ 且 $\texttt{target}$ 在数组 $\texttt p$ 中出现过，那么会返回 $\texttt{true}$。然而，当 $\texttt p$ 不存在单调性时则不然。

给定正整数 $n$ 和一个数组 $b_1,\dots,b_n \in \{\texttt{true},\texttt{false}\}$。数据保证存在一个正整数 $k$，使得 $n=2^k-1$。

规定 $S(p)$ 为 $i \in \{1,\dots,n\}$ 时 $\texttt{binary\_search(n, p, i)}$ 返回值不为 $b_i$ 的个数。你的任务是求一个 $\{1,\dots,n\}$ 的排列 $p$，使得 $S(p)$ 尽可能小（具体请见评分规则）。

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

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

每组数据的第一行包含一个正整数 $n$。第二行包含一个长度为 $n$ 的字符串（只含有字符 `0` 和 `1` 且无空格）。其中当第 $i$ 个字符为 `1` 时，则 $b_i=\texttt{true}$，否则 $b_i=\texttt{false}$。

outputFormat: 输出 $T$ 行，每行输出求得的排列 $p$。**Special Judge 对输出格式要求非常严格，每行行末不能有空格等多余字符。**

hint:
#### 评分规则

- 当一个子任务中的所有排列 $p$ 均满足 $S(p) \le 1$ 时，得分为该子任务总分的 $100\%$。
- 否则当一个子任务中的所有排列 $p$ 均满足 $0 \le S(p) \le \lceil \log_2 n \rceil$ 时，得分为该子任务总分的 $50\%$。

由于洛谷评分机制，每个测试点的实际得分为上式下取整的结果。例如，当该子任务的总分为 $3$ 且该子任务中的所有排列 $p$ 均满足 $0 \le S(p) \le \lceil \log_2 n \rceil$ 时，得分为 $1$ 而不是 $1.5$。

#### 样例 1 解释

前两组数据满足 $S(p)=0$。

第三组数据中 $S(p)=1$，因为 $\texttt{binary\_search(n, p, 2)}=\texttt{true} \neq b_2$。

第四组数据中 $S(p)=1$，因为 $\texttt{binary\_search(n, p, 4)}=\texttt{true} \neq b_4$。

#### 样例 2 解释

两组数据均满足 $S(p)=0$。

#### 数据规模与约定

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

- Subtask 1（3 pts）：$b_i=\texttt{true}$。
- Subtask 2（4 pts）：$b_i=\texttt{false}$。
- Subtask 3（16 pts）：$1 \le n \le 7$。
- Subtask 4（25 pts）：$1 \le n \le 15$。
- Subtask 5（22 pts）：$n=2^{16}-1$ 且 $b_i$ 数据随机。
- Subtask 6（30 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le T \le 7000$，$1 \le \sum n \le 10^5$，$\forall n \in \{n|n=2^k-1,k \in \N^*\}$。

#### 说明

本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 2 A BinSearch。欢迎通过私信或发帖的方式对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/5fdi0fvc) 进行 hack。


title: [eJOI2021] Dungeons

description:
你需要在一个 $N \times M$ 的地图进行游戏。地图的每个位置包括下列类型：

- $\texttt .$：空地。
- $\texttt \#$：墙壁。
- $\texttt o$：金币。
- $\texttt X$：炸弹。
- $\texttt S$：起始位置。

每张地图包含一个或多个 $\texttt S$。当游戏开始时，你的起点将会被选定为任意一个 $\texttt S$。由于地图视野较暗，因此你只能看到以自身为中心的 $3 \times 3$ 正方形内的位置。同时，$\texttt X$ 和 $\texttt S$ 在视野中会被视为是空地（$\texttt .$）。注意，你不可以进入墙壁（$\texttt \#$）。

你每一步可以向上下左右四个方向进行移动。当你进入 $\texttt o$ 格时，你会获得 $1$ 枚金币，同时该格的 $\texttt o$ 消失。当你进入 $\texttt X$ 格时，你失去所有金币且游戏结束。

求最坏情况下能够获得金币数量的最大值。

inputFormat:
第一行两个正整数 $N,M$。

接下来的 $N$ 行用来描述地图。数据保证地图外围（即第一行、最后一行、第一列、最后一列）都是 `#` 字符。

outputFormat: 一个整数，表示最坏情况下能够获得金币数量的最大值。

hint:
#### 样例 1 解释

由于 $\texttt S$ 只有一个，因此起点固定，可以获得所有金币。

#### 样例 2 解释

分别以左侧和右侧 $\texttt S$ 为起点时的初始视野（$\texttt @$ 为起点）：

$$\texttt{\#\#\#\,\,\,\,\,\,\,\,\#\#\#} \\ \texttt{\#@o\,\,\,\,\,\,\,\,o@\#} \\ \texttt{\#\#\#\,\,\,\,\,\,\,\,\#\#\#}$$

以左侧的 $\texttt S$ 为起点时可获得 $1$ 枚金币，以右侧的为起点时可获得 $2$ 枚。因此在最坏情况下最多可获得 $\min(1,2)=1$ 枚金币。

#### 样例 3 解释

无论起点是哪一个 $\texttt S$，初始视野均为：

$$\texttt{...} \\ \texttt{.@.} \\ \texttt{...}$$

由于不知道当前位置具体在地图上是哪里，因此最坏情况是踏入起点旁边的 $\texttt X$（视野中为 $\texttt .$）。这种情况下不能获得任何金币，答案为 $0$。

#### 样例 4 解释

分别以左上和右下的 $\texttt S$ 为起点时的初始视野：

$$\texttt{\#..\,\,\,\,\,\,\,\,...} \\ \texttt{.@.\,\,\,\,\,\,\,\,.@.} \\ \texttt{...\,\,\,\,\,\,\,\,..\#}$$

由于初始视野不同，因此可以通过 $\texttt \#$ 位置的不同判断在地图上的具体位置。因此可以获得所有金币，答案为 $6$。

#### 样例 5 解释

不妨先向左走 $2$ 步。如果能够看到 $\texttt o$，那么可以判断出位于第四行，同时捡起左侧的金币。

否则仍无法判断位于第二行还是第六行。因此可以在向左 $2$ 步的基础上往右 $4$ 步（即走到起点右侧 $2$ 步的位置）。如果视野右上是 $\texttt .$（在地图中为 $\texttt \#$），那么可以判断位于第六行。这时可以安全地一直向左获得第二列的金币。如果视野不是 $\texttt .$，那么只需一直向右即可获得第十六列和第十七列的金币。

按这种方案得到的答案是最优的，为 $\min\{1,1,2\}=1$。

不难发现，如果直接向右，那么可能直接进入 $\texttt X$——这种方案得到的答案为 $0$。

#### 数据规模与约定

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

设地图中 $\texttt S$ 的数量为 $S$。

- Subtask 1（3 pts）：$S=1$，不存在 $\texttt X$ 且只有地图外围有 $\texttt \#$。
- Subtask 2（7 pts）：$N=3$。
- Subtask 3（12 pts）：$S=1$。
- Subtask 4（23 pts）：$S=2$。
- Subtask 5（41 pts）：$1 \le N,M \le 250$，$1 \le S \le 12$。
- Subtask 6（14 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,M \le 400$，$1 \le S \le 60$。

#### 说明

本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 2 B Dungeons。


title: [eJOI2021] Waterfront

description:
现有 $N$ 丛初始高度为 $\textit{height}_i$ 的灌木。每丛灌木每天都会生长 $\textit{dailyGrowth}_i$ 的高度。

每天在**灌木生长完毕后**，园丁将对灌木剪枝 $k$ 次。每次可以将任意一丛高度不小于 $x$ 的灌木剪短 $x$ 个单位。

求 $M$ 天后最高的一丛灌木的高度的最小值。

inputFormat:
第一行四个正整数 $N,M,k,x$。

接下来的 $N$ 行，每行两个非负整数 $\textit{height}_i,\textit{dailyGrowth}_i$。

outputFormat: 一个非负整数，表示 $M$ 天后最高的一丛灌木的高度的最小值。


title: 「GLR-R3」雨水

background:
  「天将化雨舒清景，萌动生机待绿田」

---

  在天依面前口口声声说着习惯了，才开学没几天，文化课和乐队训练的压力可是又让阿绫头疼呢。

  浓缩为一个晚上的周末。站在阳台上，摸索朦胧于雨声的城市轮廓。雨水之日的雨，对于眼前的高楼大厦——们，恐怕也难有一些别样的意境吧。

  “雨水节令的雨、白露节令的露、霜降节令的霜、小雪节令的雪各十二钱……”

  胡乱想着，阿绫噗嗤一声笑了出来，“但是不管在哪里，雨中的空气，雨后的初阳，总是清新得叫人欢喜。”向着雨幕笑笑，拨弄这手里的旧吉他，不知不觉哼起那首歌来。

---

  **雨水** 「等凉雨　的温度　将不安燥热中和　寻觅着　风的波折」

description:
身后的门被敲响，接过天依包回来的一大盒多肉，放下东西贴贴一会儿之后，她们决定把多肉们在阳台上排成一排。

多肉们的高度不尽相同，天依先将一共 $n$ 盆多肉随意排成一排，从左到右第 $i$ 盆的高度为 $a_i$。为了美观，她希望交换某些多肉的位置，使得由高度组成的序列 $A$ 的**字典序**尽可能小，不过，为了照顾多肉们的感受（？）她要求阿绫只能选取 $A$ 的一个**长度为偶数的子序列**（长度可以为 $0$），交换序列里第 $1$ 盆和第 $2$ 盆，第 $3$ 盆和第 $4$ 盆……的位置，然后放回它们原来的位置中。

苦活交给了阿绫，思考的工作自然交给你啦！请告诉阿绫，仅使用**一次**选取子序列的操作，她能够得到的字典序最小的新高度序列 $A'$。

#### 形式化题意

给定一个长为 $n$ 的整数序列 $A$，下标从 $1$ 开始。你可以**任取一个**自然数 $k$ 以及一个序列 $\lang 1,2,\dots,n\rang$ 的，长度为 $2k~(k\in\mathbb N)$ 的**子序列** $P$，并对于所有 $i=1,2,\dots,k$，交换 $A_{P_{2i-1}}$ 与 $A_{P_{2i}}$ 的值。求在所有可能得到的新序列 $A'$ 中，**字典序** 最小的序列。

**字典序**：对于长度为 $n$ 的序列 $A$ 和 $B$，定义 $A$ 的字典序小于 $B$，当且仅当：

$$
\exists i\in[1,n], (\forall j\in[1,i), A_j=B_j)\land A_i<B_i.
$$

**注意**：本题输入输出方式具有特殊性。详见「输入格式」与「输出格式」。

inputFormat:
为节省程序输入耗时，序列 $A$ 将在你的程序内部由 `xorShift128Plus` 和提供的种子生成。下面给出 C++ 语言下的示例程序：

```cpp
#include <cstdio> // scanf

const int MAXN = 712; // Set a right value according to your solution.
int n, a[MAXN + 1];

namespace Generator {

unsigned long long k1, k2;
int thres;

inline unsigned long long xorShift128Plus() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

inline void generate() {
    for (int i = 1; i <= n; ++i) {
        a[i] = xorShift128Plus() % thres;
    }
}

} // namespace Generator.

int main() {
    scanf("%d", &n);
    scanf("%llu %llu %d", &Generator::k1, &Generator::k2, &Generator::thres);
    Generator::generate();
    // Now array a[1..n] represents the sequence A in the statement.
    return 0;
}
```

输入文件仅有一行，包含四个整数 $n,k_1,k_2,\textit{thres}$。

程序读入序列长度 $n$，种子 $k_1,k_2$ 和序列值上限 $\textit{thres}$，用 `xorShift128Plus` 连续生成 $n$ 个随机数，将它们对 $\textit{thres}$ 取模的值依次赋给 $a_1,a_2,\cdots,a_n$，得到序列 $A$。请使用其他语言的选手自行查阅相关信息实现生成器。

outputFormat: 为节省程序输出耗时，你的程序应当输出一行一个整数，表示 $\left(\sum_{i=1}^ni\times A_i'\right)\bmod2^{64}$ 的值。


title: [JRKSJ R5] Jalapeno and Garlic

description:
一个 $n$ 个点的环，点有点权 $a$，编号依次从 $1\sim n$。点 $1$ 与点 $n$ 相邻。

你希望只存在一个 $x\in[1,n]$ 满足 $a_x\ne 0$。为此，你需要按下面流程进行操作：

1. 选定一个 $x$，表示最终使得 $a_x\ne 0$。**此后不能更改 $x$ 的选择。**
2. 进行若干次修改操作，每次操作你可以选定一个 $y\in[1,n]$，将 $a_y\gets a_y-1$。同时在与点 $y$ 相邻的两个点中**等概率选择**一个，其点权将被 $+1$。

你希望期望的修改次数最少，所以求在最优策略下的期望操作次数（操作 1 不计入）。

inputFormat:
第一行一个整数 $n$。\
第二行 $n$ 个整数表示 $a_{1\dots n}$。

outputFormat: 一个整数，表示答案。输出时答案对 $1004535809$ 取模。


title: [USACO22JAN] Minimizing Haybales P

description:
Bessie 感到无聊，于是又在 Farmer John 的牛棚里制造麻烦。FJ 有 $N$（$1 \le N \le 10^5$) 堆草堆。对于每个 $i \in [1,N]$，第 $i$ 堆草堆有 $h_i$（$1 \le h_i \le 10^9$）的草。Bessie 不想让任何的草倒下来，所以她唯一可以执行的操作为：

- 如果两个相邻的草堆的高度相差不超过 $K$（$1 \le K \le 10^9$），她可以交换这两堆草堆。

Bessie 在一系列这样的操作之后可以得到的的字典序最小的高度序列是什么？

inputFormat: 输入的第一行包含 $N$ 和 $K$。第 $i+1$ 行包含第 $i$ 堆草堆的高度。

outputFormat: 输出 $N$ 行，第 $i$ 行包含答案中第 $i$ 堆草堆的高度。

hint:
【样例解释】

一种 Bessie 可以交换草堆的方式如下：

```plain
   7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3
```

【数据范围】

- 所有测试点的 $10\%$ 满足 $N \le 100$。
- 所有测试点的另外 $20\%$ 满足 $N \le 5000$。
- 其余 $70\%$ 的测试点没有额外限制。

供题：Daniel Zhang，Benjamin Qi


title: [USACO22JAN] Counting Haybales P

description:
如同往常一样，奶牛 Bessie 正在 Farmer John 的牛棚里制造麻烦。FJ 有 $N$（$1 \le N \le 5000$）堆草堆。对于每个 $i \in [1,N]$，第 $i$ 堆草堆有 $h_i$（$1 \le h_i \le 10^9$）的草。Bessie 不想让任何的草倒下来，所以她唯一可以执行的操作为：

如果两个相邻的草堆的高度相差恰好为 $1$，她可以将较高的草堆中最上方的草移到较低的草堆之上。

执行有限多次上述操作后，可以得到多少种不同的高度序列，对 $10^9+7$ 取模？两个高度序列被认为是相同的，如果对于所有 $i$，第 $i$ 堆草堆在两者中具有相同数量的草。

inputFormat:
输入的第一行包含 $T$，为独立的子测试用例的数量，必须全部回答正确才能通过整个测试用例。

每个子测试用例包含 $N$，以及一个 $N$ 个高度的序列。输入保证所有子测试用例的 $N$ 之和不超过 $5000$。

outputFormat: 输出 $T$ 行，每行输出一个子测试用例的答案。

hint:
【样例解释】

对于第一个子测试用例，四个可能的高度序列为：

$(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2)$

对于第二个子测试用例，四个可能的高度序列为：

$(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2)$

【数据范围】

- 测试点 1-3 满足 $N \le 10$。
- 测试点 4 满足对于所有 $i$，有 $1 \le h_i \le 3$。
- 测试点 5-7 满足对于所有 $i$，有 $|h_i-i| \le 1$。
- 测试点 8-10 满足对于所有 $i$，有 $1 \le h_i \le 4$，且 $N \le 100$。
- 测试点 11-13 满足 $N \le 100$。
- 测试点 14-17 满足 $N \le 1000$。
- 测试点 18-21 没有额外限制。

供题：Daniel Zhang


title: [USACO22JAN] Multiple Choice Test P

description:
奶牛们正在参加一个选择题测试。在通常的测试中，对每个问题你的选项会被单独评分然后累加，而在此测试中，你的选项在累加之后再评分。

具体地说，你被给定二维平面上的 $N$（$2 \le N \le 10^5$）组整数向量，其中每个向量用一个有序对 $(x,y)$ 表示。从每组中选择一个向量，使向量的总和尽可能远离原点。

输入保证向量的总数不超过 $2 \times 10^5$。每组至少包含 $2$ 个向量，并且一组内所有向量各不相同。输入同时保证每个 $x$ 和 $y$ 坐标的绝对值不超过 $\dfrac{10^9}{N}$。

inputFormat:
输入的第一行包含 $N$，为向量的组数。

每一组的第一行包含 $G$，为组中的向量数。以下 $G$ 行包含组中的向量。相邻组之间用空行分隔。

outputFormat: 输出最大可能的欧几里得距离的平方。

hint:
【样例解释】

最优方案是从第一组选择 $(1,0)$，从第二组中选择 $(0,1)$，从第三组选择 $(10,10)$。这些向量之和等于 $(11,11)$，与原点的距离平方等于 $11^2+11^2=242$。

【数据范围】

- 测试点 1-5 中，向量的总数不超过 $10^3$。
- 测试点 6-9 中，每一组恰好包含 $2$ 个向量。
- 测试点 10-17 没有额外限制。

供题：Benjamin Qi


title: [USACO22JAN] Herdle B

description:
奶牛们发明了一种名为 Herdle 的新型解谜游戏，在牛界引起了轰动。

每天都会有一个新谜题发布供奶牛解决。游戏采用 $3\times 3$ 方阵的形式表示农场的一块田地，田地的每个方格都由特定品种的奶牛占据。总共只有 $26$ 种可能的品种，每一种由 $\text{A}$ 到 $\text{Z}$ 中的不同大写字母标识。玩家不会被告知田地中的奶牛品种排列方式——游戏目标是通过一系列猜测确定它们。

每次猜测，奶牛们输入一个 $3\times 3$ 的大写字母方阵，表示该田地可以用奶牛填充的可能方式。猜测的某些方格可能是正确的。这些方格以绿色高亮显示，让奶牛们知道这些是正确的。猜测的另一些方格可能填入了品种正确但位置错误的奶牛。这些以黄色高亮显示。

黄色高亮显示的方格的数量可以帮助指示某个品种的奶牛数量。 例如，假设猜测方阵包含 $4$ 头品种 $\text{A}$ 的奶牛，而答案方阵包含 $2$ 只品种 $\text{A}$ 的奶牛，其中没有正确位置上的 $\text{A}$ （即，它们都不应该是绿色的）。 在这种情况下，猜测方阵中只有两个 $\text{A}$ 应以黄色高亮显示。 更准确地说，如果猜测方阵中有 $x$ 个特定品种的奶牛，并且 答案方阵中有 $y \le x$ 头该品种奶牛（不包括位置正确而得到绿色高亮显示的奶牛），那么猜测方阵的 $x$ 头奶牛中只有 $y$ 头奶牛应该以黄色高亮显示。

给定正确答案的方阵和一个表示对该答案的猜测的方阵，请计算绿色和黄色高亮显示的方格的数量。

inputFormat: 输入的前 3 行给定了正确答案的方阵。以下 3 行表示对该答案的猜测。

outputFormat: 输出两行。输出的第一行包含应当以绿色高亮显示的方格的数量。输出的第二行包含应当以黄色高亮显示的方格的数量。

hint:
【样例解释 1】

在这个例子中，最后一行中间的 O 是正确的，所以这个方格以绿色高亮显示。字母 W 位于错误的位置，所以它以黄色高亮显示。

【样例解释 2】

在这里，其中一个 A 位于正确的位置，所以它以绿色高亮显示。余下的 A 均不在正确位置上，由于答案方阵中有两个 A，所以有两个 A 应当以黄色高亮显示。


title: [USACO22JAN] Non-Transitive Dice B

description:
为了消磨牛棚里的时光，奶牛们喜欢玩简单的骰子游戏。其中一种游戏使用两个骰子 X 和 Y 进行。两个骰子均被投掷，获胜的骰子是显示的数字较大的骰子。如果两者显示相同的数字，则重新投掷（只要持续打平，骰子可能会被重新投掷多次）。我们称骰子 X 击败骰子 Y，如果骰子 X 比骰子 Y 更有可能赢得这局游戏。

考虑以下的 $4$ 面骰子：

骰子 A 在各面上有数字 $4$，$5$，$6$ 和 $7$。

骰子 B 在各面上有数字 $2$，$4$，$5$ 和 $10$。

骰子 C 在各面上有数字 $1$，$4$，$8$ 和 $9$。

这些骰子满足一个相当奇妙的性质：A 击败 B，B 击败 C，并且 C 也击败 A。特别地，三个骰子都不是「最佳的」，可以击败其他两个。在这种情况下，当没有两个骰子打平，也没有一个骰子是最佳的，我们称这三个骰子的集合为「非传递的」。在非传递的三个骰子的集合中，每个骰子击败一个其他骰子，并输给另一个其他骰子。

给定两个 $4$ 面骰子 A 和 B 各面上的数字，请帮助奶牛们求出是否有方法为第三个骰子 C 的各面分配数字，使得这个骰子的集合是非传递的。所有骰子面上的数字必须是 $1$ 到 $10$ 的整数。

inputFormat:
每个测试用例包含多个独立的子测试用例，必须全部回答正确才能通过整个测试用例。输入的第一行包含 $T$（$1\le T\le 10$），为你需要求解的子测试用例的数量。

以下 $T$ 行，每行描述了一个子测试用例，包含 $8$ 个整数：骰子 A 的 $4$ 面上的整数，以及骰子 B 的 $4$ 面上的整数。所有的数均在 $1$ 到 $10$ 之间，不一定排序。可能同一个数会出现多次，即使在同一个骰子上也可能出现多个相同的数。

outputFormat: 输出 $T$ 行。如果有可能为骰子 C 分配数字使得第 $k$ 个测试用例成为一个非传递的骰子集合，则第 $k$ 行输出 `yes`，否则输出 `no`。

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

第一个子测试用例对应题目中的例子。在第二个子测试用例中，不存在骰子 C 可以使得这个骰子集合是非传递的。同理第三个子测试用例的答案也是 `no`。


title: [USACO22JAN] Drought B

description:
Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，Farmer John 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。

FJ 的 $N$ 头奶牛（$1 \leq N \leq 10^5$）排成一行，队伍中的第 $i$ 头奶牛的饥饿度为 $h_i$（$0 \leq h_i \leq 10^9$）。由于奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 $i$ 和 $i+1$ 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。

FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。请帮助 FJ 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 $-1$。

inputFormat:
每个测试用例包含多个独立的子测试用例，必须全部回答正确才能通过整个测试用例。

输入的第一行包含 $T$（$1\le T\le 100$），为你需要求解的子测试用例的数量。

以下是 $T$ 个子测试用例，每个子测试用例包含两行。

第一行包含 $N$，第二行包含 $h_1,h_2,\ldots,h_N$。输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。

每个子测试用例的 $N$ 的值可能不同。

outputFormat: 输出 $T$ 行，每个测试用例输出一行。

hint:
【样例解释】

对于第一个子测试用例，给奶牛 $2$ 和 $3$ 各两袋玉米，然后给奶牛 $1$ 和 $2$ 各五袋玉米，可以使得所有奶牛的饥饿度均为 $3$。

对于第二个子测试用例，给奶牛 $1$ 和 $2$ 各两袋玉米，奶牛 $2$ 和 $3$ 各两袋玉米，奶牛 $4$ 和 $5$ 各两袋玉米，奶牛 $5$ 和 $6$ 各两袋玉米，可以使得所有奶牛的饥饿度均为 $2$。

对于余下的子测试用例，均不可能使得奶牛们的饥饿度相等。

【数据范围】

- 测试点 2 的所有子测试用例满足 $N \leq 3$ 以及 $h_i\le 100$。

- 测试点 3-8 的所有子测试用例满足 $N\le 100$ 以及 $h_i\le 100$。

- 测试点 9-14 的所有子测试用例满足 $N\le 100$。

- 测试点 15 没有额外限制。

- 此外，测试点 3-5 和 9-11 中的 $N$ 均为偶数，测试点 6-8 和 12-14 中的 $N$ 均为奇数。


title: [USACO22JAN] Searching for Soulmates S

description:
Farmer John 的每头奶牛都想找到她们的灵魂伴侣——另一头具有相似特点的奶牛，与她们最大程度地相容。每头奶牛的性格由一个整数 $p_i$（$1 \leq p_i \leq 10^{18}$）描述。两头性格相同的奶牛就是灵魂伴侣。奶牛可以通过「改变操作」，对她的性格乘以 $2$，除以 $2$（当 $p_i$ 是偶数时），或者加上 $1$。

Farmer John 最初以任意方式配对了他的奶牛。他很好奇为使每对奶牛成为灵魂伴侣需要进行多少次改变操作。对于每对奶牛，求配对中的第一头奶牛所必须进行的最小改变操作次数，从而可以与第二头奶牛成为灵魂伴侣。

inputFormat: 输入的第一行包含 $N$（$1\le N\le 10$），为奶牛配对的数量。以下 $N$ 行每行描述了一对奶牛，包含两个整数，为她们的性格值。第一个整数是需要被改变与另一头奶牛相匹配的奶牛的性格。

outputFormat: 输出 $N$ 行。对于每一对奶牛，输出第一头奶牛需要进行的最小操作次数，使得她的性格与第二头奶牛相匹配。

hint:
【样例解释】

对于第一个子测试用例，一个最优的操作序列为 $31 \implies 32 \implies 16 \implies 8 \implies 9 \implies 10 \implies 11 \implies 12 \implies 13$。

对于第二个子测试用例，一个最优的操作序列为 $12 \implies 6 \implies 7 \implies 8$.

【数据范围】

- 测试点 1-4 满足 $p_i \le 10^5$。
- 测试点 5-12 没有额外限制。


title: [USACO22JAN] Cow Frisbee S

description:
Farmer John 的 $N\ (N\le 3\times 10^5)$ 头奶牛的高度为 $1, 2, \ldots, N$。一天，奶牛以某个顺序排成一行玩飞盘；令 $h_1 \ldots h_N$ 表示此顺序下奶牛们的高度（因此 $h$ 是 $1 \ldots N$ 的一个排列）。

队伍中位于位置 $i$ 和 $j$ 的两头奶牛可以成功地来回扔飞盘当且仅当她们之间的每头奶牛的高度都低于 $\min(h_i, h_j)$。

请计算所有可以成功地来回扔飞盘的奶牛所在的位置对 $i\le j$ 之间的距离总和。位置 $i$ 和 $j$ 之间的距离为 $j-i+1$。

inputFormat: 输入的第一行包含一个整数 $N$。第二行包含 $h_1 \ldots h_N$，用空格分隔。

outputFormat: 输出可以成功地来回扔飞盘的奶牛所在的位置对 $i\le j$ 之间的距离总和。注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C 或 C++ 中的 "long long"）。


title: [USACO22JAN] Cereal 2 S

description:
Farmer John 的奶牛们的早餐最爱当然是麦片了！事实上，奶牛们的胃口是如此之大，每头奶牛一顿饭可以吃掉整整一箱麦片。

最近农场收到了一份快递，内有 $M$ 种不同种类的麦片（$2\le M\le 10^5$）。不幸的是，每种麦片只有一箱！$N$ 头奶牛（$1\le N\le 10^5$）中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程：

- 如果她最爱的麦片还在，取走并离开。

- 否则，如果她第二喜爱的麦片还在，取走并离开。

- 否则，她会失望地哞叫一声然后不带走一片麦片地离开。

当你最优地排列这些奶牛时，求饥饿的奶牛的最小数量。同时，求出任意一个可以达到此最小值的 $N$ 头奶牛的排列。

inputFormat:
输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。

对于每一个 $1\le i\le N$，第 $i$ 行包含两个空格分隔的整数 $f_i$ 和 $s_i$（$1\le f_i,s_i\le M$，且 $f_i\neq s_i$），为第 $i$ 头奶牛最喜爱和第二喜爱的麦片。

outputFormat: 输出饥饿的奶牛的最小数量，并输出任意一个可以达到此最小值的 $1\ldots N$ 的排列。如果有多个符合要求的排列，输出任意一个。

hint:
【样例解释】

在这个例子中，有 $8$ 头奶牛和 $10$ 种麦片。

注意我们对前三头奶牛独立于后五头奶牛求解，因为她们没有共同喜欢的麦片。

如果前三头奶牛按顺序 $[1,2,3]$ 进行选择，则奶牛 $1$ 会选择麦片 $2$，奶牛 $2$ 会选择麦片 $3$，奶牛 $3$ 会饥饿。

如果前三头奶牛按顺序 $[1,3,2]$ 进行选择，则奶牛 $1$ 会选择麦片 $2$，奶牛 $3$ 会选择麦片 $3$，奶牛 $2$ 会选择麦片 $4$；没有奶牛会饥饿。

当然，还存在其他排列使得前三头奶牛均不饥饿。例如，如果前三头奶牛按顺序 $[3,1,2]$ 选择，则奶牛 $3$ 会选择麦片 $2$，奶牛 $1$ 会选择麦片 $1$，奶牛 $2$ 会选择麦片 $3$；同样，奶牛 $[1,2,3]$ 均不会饥饿。

可以证明在后五头奶牛中，至少一头会饥饿。

【数据范围】

- $14$ 个测试点中的 $4$ 个测试点满足 $N,M\le 100$。

- $14$ 个测试点中的 $10$ 个测试点没有额外限制。

【说明】

本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/hi36jkwh)。如果对此有疑问或想要 hack，请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或[发帖](https://www.luogu.com.cn/discuss/lists?forumname=P8095)。


title: [USACO22JAN] Drought G

description:
Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，FJ 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。

FJ 的 $N$ 头奶牛（$1 \leq N \leq 100$）排成一行，队伍中的第 $i$ 头奶牛的饥饿度为一个非负整数 $h_i$。由于 FJ 的奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 $i$ 和 $i+1$ 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。

FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。尽管他不知道他的奶牛们具体的饥饿度，他知道每一头奶牛的饥饿度上界；具体地说，第 $i$ 头奶牛的饥饿度 $h_i$ 至多为 $H_i$（$0\le H_i\le 1000$）。

你的工作是计算符合上述上界的 $N$ 元组 $[h_1,h_2,\ldots,h_N]$ 的数量，使得 FJ 有可能达到他的目标，答案对 $10^9+7$ 取模。

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

第二行包含 $H_1,H_2,\ldots,H_N$。

outputFormat: 输出符合条件的饥饿度的 $N$ 元组数量，对 $10^9+7$ 取模。

hint:
【样例解释】

共有 $(9+1)\cdot (11+1)\cdot (7+1)$ 个 $3$ 元组 $h$ 与 $H$ 相符合。

$h=[8,10,5]$ 是其中一个元组。在这个情况中，有可能使得所有的奶牛具有相同的饥饿度：给奶牛 $2$ 和 $3$ 各两袋玉米，然后给奶牛 $1$ 和 $2$ 各五袋玉米，可以使得所有奶牛的饥饿度均为 $3$。

$h=[0,1,0]$ 是另一个元组。在这个情况中，不可能使得奶牛们的饥饿度相等。

【数据范围】

- 编号为偶数的测试点中的 $N$ 均为偶数，编号为奇数的测试点中的 $N$ 均为奇数。

- 测试点 3-4 满足 $N\le 6$ 以及 $H_i \le 10$。

- 测试点 5-10 满足 $N\le 50$ 以及 $H_i \le 100$。

- 测试点 11-20 没有额外限制。


title: [USACO22JAN] Farm Updates G

description:
Farmer John 经营着总共 $N$ 个农场（$1\le N\le 10^5$），编号为 $1\ldots N$。最初，这些农场之间没有道路连接，并且每个农场都在活跃地生产牛奶。

由于经济的动态性，Farmer John 需要根据 $Q$ 次更新操作（$0\le Q\le 2\cdot 10^5$）对他的农场进行改造。更新操作有三种可能的形式：

- `(D x)` 停用一个活跃的农场 $x$，使其不再生产牛奶。

- `(A x y)` 在两个活跃的农场 $x$ 和 $y$ 之间添加一条道路。

- `(R e)` 删除之前添加的第 $e$ 条道路（$e = 1$ 是添加的第一条道路）。

一个农场 $x$ 如果正在活跃地生产牛奶，或者可以通过一系列道路到达另一个活跃的农场，则称之为一个「有关的」农场。对于每个农场 $x$，计算最大的 $i$（$0\le i\le Q$），使得农场 $x$ 在第 $i$ 次更新后是有关的。

inputFormat:
输入的第一行包含 $N$ 和 $Q$。以下 $Q$ 行每行包含如下格式之一的一次更新操作：

```
D x
A x y
R e
```

输入保证对于 R 类更新，$e$ 不超过已经添加的道路的数量，并且没有两次 R 类更新具有相等的 $e$ 值。

outputFormat: 输出 $N$ 行，每行包含一个 $0\ldots Q$ 范围内的整数。

hint:
【样例解释】

在这个例子中，道路以顺序 $(2,3), (1,2), (2,4)$ 被删除。

- 农场 $1$ 在道路 $(1,2)$ 被删除之前是有关的。

- 农场 $2$ 在道路 $(2,4)$ 被删除之前是有关的。

- 农场 $3$ 在道路 $(2,3)$ 被删除之前是有关的。

- 农场 $4$ 和 $5$ 在所有更新结束后仍然是活跃的。所以它们一直保持为有关的，两者的输出均应为 $Q$。

【数据范围】

- 测试点 2-5 满足 $N\le 10^3$，$Q\le 2\cdot 10^3$。

- 测试点 6-20 没有额外限制。


title: [USACO22JAN] Tests for Haybales G

description:
Farmer John 的奶牛们决定为 Farmer Nhoj 农场的奶牛们举办一场编程竞赛。为了使问题尽可能有趣，他们花费了大量时间来构造具有挑战性的测试用例。特别是对于一个问题，「Haybales」，奶牛们需要你的帮助来设计具有挑战性的测试用例。这有关解决以下这个有些奇妙的问题：

有一个有序整数数组 $x_1 \leq x_2 \leq \dotsb \leq x_N$（$1 \leq N \leq 10^5$），和一个整数 $K$。你不知道这个数组以及 $K$，但你知道对于每个索引 $i$ 使得 $x_{j_i} \leq x_i + K$ 的最大索引 $j_i$。保证有 $i\le j_i$ 以及 $j_1\le j_2\le \cdots \le j_N\le N$。

给定这些信息，Farmer John 的奶牛需要构造任意一个数组以及整数 $K$ 与该信息一致。构造需要满足对于所有 $i$ 有 $0 \leq x_i \leq 10^{18}$，并且 $1 \leq K \leq 10^{18}$。

可以证明这一定是可行的。请帮助 Farmer John 的奶牛们解决这一问题！

inputFormat: 输入的第一行包含 $N$。第二行包含 $j_1,j_2,\ldots,j_N$。

outputFormat: 输出 $K$，然后在下一行输出 $x_1,\ldots,x_N$。任何合法的输出均正确。

hint:
【样例解释】

输出样例为数组 $a=[1,6,17,22,27,32]$ 以及 $K=6$。 $j_1=2$ 被满足是由于 $a_2=6 \le 1+6=a_1+K$ 而 $a_3=17>1+6=a_1+K$，从而 $a_2$ 是最大的不超过 $a_1+K$ 的元素。类似地：

- $j_2=2$ 被满足是由于 $a_2=6 \le 6+6$ 而 $a_3=17>6+6$；
- $j_3=4$ 被满足是由于 $a_4=22 \le 17+6$ 而 $a_5=27>17+6$；
- $j_4=5$ 被满足是由于 $a_5=27 \le 22+6$ 而 $a_5=32>22+6$；
- $j_5=6$ 被满足是由于 $a_6=32 \le 27+6$ 且 $a_6$ 是数组的最后一个元素；
- $j_6=6$ 被满足是由于 $a_6=32 \le 32+6$ 且 $a_6$ 是数组的最后一个元素。

对于输入样例，这并不是唯一正确的输出。例如，你也可以输出数组 $[1,2,4,5,6,7]$ 和 $K=1$。

【数据范围】

- 所有测试点的 $50\%$ 满足 $N \le 5000$。
- 其余测试点没有额外限制。

【说明】

本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/kzgvkesl)。如果对此有疑问或想要 hack，请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或[发帖](https://www.luogu.com.cn/discuss/lists?forumname=P8098)。


title: 【模板】字典树

description:
给定 $n$ 个模式串 $s_1, s_2, \dots, s_n$ 和 $q$ 次询问，每次询问给定一个文本串 $t_i$，请回答 $s_1 \sim s_n$ 中有多少个字符串 $s_j$ 满足 $t_i$ 是 $s_j$ 的**前缀**。

一个字符串 $t$ 是 $s$ 的前缀当且仅当从 $s$ 的末尾删去若干个（可以为 0 个）连续的字符后与 $t$ 相同。

输入的字符串大小敏感。例如，字符串 `Fusu` 和字符串 `fusu` 不同。

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

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

对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数 $n$ 和询问的个数 $q$。
接下来 $n$ 行，每行一个字符串，表示一个模式串。
接下来 $q$ 行，每行一个字符串，表示一次询问。

outputFormat:
按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。

samples:
3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9

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

对于全部的测试点，保证 $1 \leq T, n, q\leq 10^5$，且输入字符串的总长度不超过 $3 \times 10^6$。输入的字符串只含大小写字母和数字，且不含空串。

### 说明
std 的 IO 使用的是关闭同步后的 cin/cout，本题不卡常。


title: [CoE R4 A/Stoi2041] 娘子

description:
给定两个长度均为 $n$ 的 $0$，$1$ 序列 $a$，$b$，**首先**，你可以选择一些 $a_i$ 取反，即 $0$ 变为 $1$，$1$ 变为 $0$，**然后**，任意排列序列 $a$。

要求上述过程结束后 $a_i$ **等于** $b_i$，求取反的最少次数。

inputFormat: 第一行一个正整数 $n$。第二行 $n$ 个数字表示序列 $a$。第三行 $n$ 个数字表示序列 $b$。

outputFormat: 一个整数表示答案。

hint:
### 样例解释

输入 #1：将 $a = 110$ 重排为 $a = 101$ 即可达到题目要求，故取反的最少次数为 $0$。

输入 #2：将 $a = 10010$ 的第四位取反（从左往右计数），得 $a=10000$，然后再重排得到 $a=00100$ 即可达到题目要求，故取反的最少次数为 $1$。

---

### 数据规模

- 对于 $10\%$ 的数据，$n = 1$；
- 对于另外 $20\%$ 的数据，$b_i = 0$；
- 对于另外 $20\%$ 的数据，$b_i = 1$；
- 对于 $100\%$ 的数据，$1 \le n \le 10^3$，$a_i \in \{0, 1\}$，$b_i \in \{0, 1\}$。


title: 「WHOI-1」ymh  是 AK 哥！！！

background:
$2077$ 年春。$15$ 岁的 miku 正在对着你谷发呆，突然看到一个奇怪的问题，你能帮帮他么？？

----

你要先学会一些定义。

我们约定一个字符串下标从 $1$ 开始，$s[l,r]$ 表示 $s_ls_{l+1}\dots s_r$ 拼接成的一个字符串。

---

定义括号匹配串如下：

- 空串是括号匹配串。
- 如果 $A$ 是括号匹配串，则 $(A)$ 是括号匹配串。
- 如果 $A,B$ 是括号匹配串，则 $AB$ 是括号匹配串。

---

括号匹配前缀长度是指最大的 $k$ 使得 $s[1,k]$ 是一个括号匹配串。

比如：
- $s=\text{(())(()}$ 时括号匹配前缀长度是 $4$。
- $s=\text{()()()(()))(}$ 时括号匹配前缀长度是 $10$。

description:
给你一个括号串 $s$。定义一次操作是交换他们当中相邻的两个字符。

你的任务是找出若干次操作后 $s$ 的括号匹配前缀长度最大值。

inputFormat:
一行一个正整数 $n$ 表示字符串长度。

接下来一行一个字符串表示 $s$。

outputFormat: 一行一个自然数表示答案。


title: T1 三角形面积

type: B

background: **请尽量在 20min 之内写完题目。这是指「写代码」的时间；「读题」时间不计算在内。**

description:
给定平面直角坐标系上的三个整点 $A, B, C$ 的坐标，求其围成的三角形面积。

**数据保证答案一定是整数。所以如果你采用了浮点数来计算，请四舍五入到整数**。

---

**两点之间的距离公式：** $(x_1, y_1), (x_2, y_2)$ 之间的距离是 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

**海伦公式：** 若三角形的边长为 $a, b, c$，则三角形的面积是 $\sqrt{s(s-a)(s-b)(s-c)}$，其中 $s=\frac12(a+b+c)$.

inputFormat:
共三行，每行表示一个三角形上的点。
每行包含两个正整数，表示点的坐标，形式为 `x y`。

outputFormat: 共一行，一个整数，表示三角形面积。


title: T2 点亮灯笼

description:
有 $n$ 个灯笼环形摆放。最开始，这些灯笼都是关闭的状态。

操作台上有 $n$ 个按钮，按下第 $x$ 个按钮时，会反转灯笼 $x$ 以及相邻两个灯笼的状态。「反转」是指关闭变成点亮、点亮变成关闭。

举一个例子：如果按下第 $5$ 个按钮，则 $4$、$5$、$6$ 号灯笼都会反转；如果按下第 $n$ 个按钮，则 $n-1, n, 1$ 这三个灯笼状态反转。这是因为灯笼放置为环形，$n-1$ 和 $1$ 是与 $n$ 相邻的灯笼。

我们依次按下了一些按钮。你需要编程求出当我们的操作完成后，最终这些灯笼的状态。

inputFormat:
第一行，两个正整数 $n, m$，分别表示共有 $n$ 个灯笼、我们按了 $m$ 次按钮。

接下来 $m$ 行，每行一个正整数，表示我们在那一次操作中按下了哪个按钮。

outputFormat: 仅一行，$n$ 个整数，依次表示 $n$ 个灯笼的状态，用空格隔开。以 `0` 代表灯笼关闭，以 `1` 代表灯笼点亮。

hint:
#### 样例解释
灯笼序列的状态如下：
```plaintext
0 0 0 0 0  # 初始状态
1 1 0 0 1  # 按下 1 之后的状态
1 0 1 1 1  # 按下 3 之后的状态
0 1 1 1 0  # 按下 1 之后的状态
1 0 0 1 0  # 按下 2 之后的状态
```

因此你应当输出 `1 0 0 1 0`。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $n\leq 1000$，$m\leq 1000$。


title: T3 句子反转

background: **请尽量在 30min 之内写完题目。这是指「写代码」的时间；「读题」时间不计算在内。**

description:
给定一行句子，每个词之间用空格隔开，要么是全小写英文单词，要么是全大写英文单词，要么是自然数。

要求将这些单词倒序输出。而且对于每个单词，如果是小写词，应当转为大写；如果是大写词，应当转为小写；如果是自然数，应该倒转输出。

举一个例子：
```plaintext
we choose TO go 2 the 123 moon
```

程序应当输出：
```plaintext
MOON 321 THE 2 GO to CHOOSE WE
```

inputFormat: 仅一行，即需要反转的句子。

outputFormat: 仅一行，表示程序对句子的处理结果。

samples:
we choose TO go 2 the 123 moon
MOON 321 THE 2 GO to CHOOSE WE

hint:
#### 样例解释

首先应当按单词逆序，即：
```plaintext
moon 123 the 2 go TO choose we
```

小写变大写、大写变小写、倒转自然数之后，得到最终结果：
```plaintext
MOON 321 THE 2 GO to CHOOSE WE
```

#### 数据规模与约定
对于 $100\%$ 的数据，句子中包含的单词数量不超过 $1000$，每个单词长度不超过 $6$。


title: EXTRA 方程求解

background:
本题是**附加题**，供有兴趣的同学挑战。

**请尽量在 40min 之内写完题目。这是指「写代码」的时间；「读题」时间不计算在内。**

description:
给定二元一次方程组，要求解出 $x, y$.

方程以 `ax+by=c` 的形式提供。其中 $a, b, c$ 都是整数，可能为负数。方程的解也一定为整数。

下面举一个例子。对于方程组
```plaintext
-2x+3y=4
x-y=-1
```

您应该解出 $x=1, y=2$。

inputFormat:
两行，表示两个方程。

每个方程可能是这样的形式：

- `ax+by=c`
- `ax-by=c`
- `-ax+by=c`
- `-ax-by=c`

其中，`c` 可能是正数、负数或 0。可能出现形如 `x` 或 `-x` 的项。

outputFormat: 两行，两个整数，分别表示 $x, y$。

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

对于 $100\%$ 的数据，系数的绝对值不超过 $100$，$x, y$ 的绝对值不超过 $100$。保证方程有唯一解。

**提示**

分类讨论越复杂，程序出 bug 的可能性越大。


title: 「GLR-R3」惊蛰

background:
  「微雨众卉新，一雷惊蛰始」

---

  中午，休息室，阿绫肩膀上。

  “我有一个愿望，参加全国音乐祭，获奖，和阿绫一起，摆脱这训练的苦海。”

  “为热爱而到来，为抽身而努力……吗”。

  正午的阳光渗过窗帘，抚上困倦的人儿的脸颊。天依的左手悄悄搭上阿绫怀里的吉他，

  “铮——”

  蛰虫被雷声唤醒，没人向他们保证雨的降临。

---

  **惊蛰** 「我愿把岁月磨成望镜寻遍这星空　将微光聚焦手心紧紧握住不放松」

description:
比赛临近，各式测试也丰富了起来，作为天依他们的专业分析师，你的工作是统计分析队员们表现情况——总之，某领导要来慰问，所以你被要求修改出一份令人赏心悦目的分析报告。

在已有的 $n$ 次测试中，对于某位特定的选手，他在第 $i$ 次测试的**波动值**是非负整数 $a_i$。波动值越小表示选手在测试中的心态和发挥越稳定，所以你需要“略微调整”波动值序列 $\{a_n\}$，得到另一个非负整数序列 $\{b_n\}$。不过，做人不能昧良心，但报告又必须好看，所以 $\{b_n\}$ 有如下要求：

- $\{b_n\}$ **单调不递增**，选手越来越厉害嘛；

- 对于每个 $i$，如果 $b_i<a_i$，老师会不高兴，所以你需要花费 $C$ 单位的精力说服老师（其中 $C$ 为给定常数）；
- 对于每个 $i$，如果 $a_i\le b_i$，选手会不高兴，而且可能很不高兴，所以你需要花费 $b_i-a_i$ 单位的精力安慰选手。

你希望在满足条件的情况下，**最小化**花费的精力之和。作为成熟的信竞选手，你自然需要自己动手，求出这一最小化的结果。

#### 形式化题意

给定非负整数序列 $\{a_n\}$，定义函数 $f(x,y)$ 为

$$
f(x,y)=\begin{cases}
x-y,&x\ge y\\
C,&x< y
\end{cases},
$$

其中 $C$ 是给定常数。请构造一个**不增**非负整数序列 $\{b_n\}$，最小化

$$
\sum_{i=1}^nf(b_i,a_i).
$$

你仅需输出这一最小化的结果。

inputFormat:
第一行两个整数，表示序列长度 $n$ 和给定常数 $C$。

接下来一行表示序列 $\{a_n\}$ 。

outputFormat: 输出一行一个整数，表示最小化的结果。


title: [ICPC2020 WF] Cardiology

background: ICPC2020 WF A

description:
The Great Cardoni, Master Prestidigitator, has a deck of 21 numbered cards which he uses in a
trick as follows:

> A spectator secretly selects a number between $1$ and $21$, inclusive, after which
> Cardoni deals the $21$ cards, face-up, row by row in order from $1$ to $21$,
> into a
> $3$-column grid. The spectator then indicates which of the three
> columns contains the selected card, at which point the magician picks up
> the cards by columns, picking up the specified column second (the
> order of collecting the other two columns is unimportant).
> Cards are collected face up, beginning with the top card in each column and
> placing each succeeding card immediately beneath the previously collected card.
> The cards are then redealt by rows into a $3$-column grid, starting from the
> top of the face-up deck. The process is
> repeated two more times; each time, the column indicated by the spectator
> is the second column picked up by the magician. After three such
> iterations, Cardoni announces, "I have penetrated to the heart of your
> mind; your card lies at the heart of this display." And it's true---the
> selected card is located at the "heart" of the array (row four, column
> two). Moreover, the selected card will always remain in this stable
> location for any further iterations of the column indication and card
> redealing process.

The process always works, no matter the number selected, provided that
the column containing the secret number is the second column to be
picked up and redealt.

Cardoni would like to expand his trick to use different numbers of
cards, rows, and columns, and to experiment with different orderings
of picking up the columns after the spectator indicates a
column. However, it is not a trivial problem. For instance, when using $24$
cards in $8$ rows and $3$ columns, and always picking up the indicated
column as the second one to redeal, the number $5$ eventually
ends up in stable location row $4$, column $3$, while the number $20$
ends up in stable location row $5$, column $1$. Also, neither location
is one of the two "heart" positions in column $2$ of rows $4$ or
$5$.  Moreover, Cardoni is uncertain of how many iterations of the
"indicate column and redeal" process are needed before a
selected card reaches a stable location.

Given the number of rows and columns of cards, help Cardoni set up his
trick in such a way that there is a unique stable location that is as
close to the center as possible.

inputFormat:
The input consists of a single line with two integers $r$ and $c$ ($2 \le r, c \le 10^6$), the number of rows and columns used in the trick.
The cards are numbered from $1$ to $r \cdot c$ and are initially dealt row by row in increasing order.

outputFormat:
Output a line containing four integers $p$, $i$, $j$, and $s$, where:

- the column indicated by the spectator should be picked up as the $p^{\text{th}}$ column,
- using this value of $p$ causes all cards to eventually end up in the stable location at row $i$ column $j$, and
- $s$ is the maximum number of iterations required for any card to reach the stable location.

The value of $p$ should be chosen so that the stable location $(i, j)$
is as close as possible to any of the one, two or four central
positions in the grid, where the distance between locations $(i, j)$
and $(i', j')$ is $|i-i'| + |j-j'|$.  If more than one value of $p$
results in the same minimum distance, choose the smallest such $p$.

translation:
观众秘密地选择一个介于1和21之间（包括1和21）的数字，然后卡多尼将这21张牌面朝上，按1到21的顺序逐行放入一个3列的网格中。然后观众指出三列中的哪一列包含所选的牌，此时魔术师逐列拾取牌，然后拾取指定的列（收集其他两列的顺序不重要）。卡片收集时面朝上，从每列中最上面的卡片开始，然后将随后的每张卡片放在之前收集的卡片的正下方。然后，从正面朝上的卡片组顶部开始，将卡片按行重新排列到3列的网格中。该过程再重复两次；每一次，观众指示的柱是魔术师拾取的第二个柱。在三次这样的反复之后，卡多尼宣布：“我已经深入到了你的内心；你的牌位于这张展示的核心。”这是真的——所选的卡位于数组的“中心”（第四行，第二列）。此外，所选卡将始终保持在该稳定位置，以便进一步迭代列指示和卡重新调整过程。

只要包含机密号的列是要拾取和重新替换的第二列，则无论选择的数字是多少，该过程始终有效。

卡多尼想扩展他的技巧，使用不同数量的卡片、行和列，并在观众指示一列后，尝试不同的顺序拾取列。然而，这不是一个微不足道的问题。例如，当在8行3列中使用24张卡，并始终将指示列作为第二个重新指定的列时，数字5最终会在稳定位置第4行第3列结束，而数字20最终在稳定位置第5行第1列结束。此外，两个位置都不是第4行或第5行第2列中的两个“心脏”位置之一。此外，Cardoni不确定在选定的卡到达稳定位置之前，需要多少次“指示列和重新指定”过程的迭代。

考虑到卡片的行数和列数，帮助卡多尼设置他的技巧，使其有一个独特的稳定位置，尽可能靠近中心。

#### 数据范围
$2 \le r, c \le 10^6$（r行c列）


title: [ICPC2020 WF] The Cost of Speed Limits

background: ICPC2020 WF B

description:
By the year 3031, the ICPC has become so popular that a whole new town has to be built to house all the
World Finals teams.
The town is beautifully designed, complete with a road network.
Unfortunately, when preparing the budget, the town planners forgot to take into account the cost of speed-limit signs.
They have asked you to help them determine the minimum additional funds they will need.

The ICPC road network consists of roads, each connecting two intersections. Each road is two-way
and has already been assigned a speed limit, valid for both directions.
To save money, the minimum possible number of roads was used. In other words, there is exactly
one route from any intersection to any other intersection.

The speed-limit signs need to be installed
in all places where the speed limit may change for any driver that follows any route.
More precisely, if there exists an intersection where at least two roads meet with different speed limits,
then *all* of the roads going from that intersection need a speed-limit sign installed at that intersection.
Note that some roads might need two speed-limit signs, one at each end.

It costs $c$ dollars to install one speed-limit sign. It is also possible to improve the safety and quality of
any road so that its speed limit can be increased, which may in turn reduce the number of speed-limit signs required.
It costs $x$ dollars to increase the speed limit of one road by $x$ km/h (in both directions).
To avoid complaints, the town council does not allow decreasing any of the already-assigned speed limits.

Figure B.1 illustrates the situation given in both Sample Input 1 and Sample Input 2.

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

inputFormat:
The first line of input contains two integers $n$ and $c$, where $n$ ($1 \le n \le 20\,000$) is the number of intersections
and $c$ ($1 \le c \le 10^5$) is the cost of installing one sign.
Each of the remaining $n-1$ lines contains three integers $u$, $v$, and $s$, where $u$ and $v$ ($1 \le u, v \le n; u \ne v$)
are the intersections at the ends of a road, and $s$ ($1 \le s \le 10^5$) is the current speed limit of that
road in kilometers per hour.

outputFormat:
Output the minimum cost to upgrade roads and install speed-limit signs such that the town
plan satisfies all the rules above.

translation:
到 3031 年，ICPC 已经变得如此受欢迎，以至于必须建造一个全新的 ICPC 镇来容纳所有参加 World Finals 的队伍。这座城镇设计精美，有完整的道路网。不幸的是，在编制预算时，城市规划者忘记了考虑限速标志的成本。他们要求你帮助他们确定他们需要的最低额外资金。

ICPC 镇的道路网由道路组成，每条道路连接两个十字路口。每条道路都是**双向**的，并且已经指定了一个速度限制 $s$，对两个方向都有效。为了省钱，ICPC 镇使用了尽可能少的道路。换句话说，从任何交叉口到任何其他交叉口只有一条路线。

限速标志需要安装在所有可能改变任何路线驾驶员限速的地方。更准确地说，如果存在至少两条道路满足不同限速要求的交叉口，那么从该交叉口出发的所有道路都需要在该交叉口安装限速标志。请注意，有些道路可能需要两个限速标志，每端一个。

安装一个限速标志需要花费 $c$ 美元。还可以提高任何道路的安全性和质量，从而提高其限速，从而减少所需限速标志的数量。将一条道路的限速提高 $x$ 公里每小时（**双向**）需要 $x$ 美元。为了避免投诉，市议会**不允许降低任何已经指定的限速**。

数据范围：

- $1\leqslant n\leqslant 2\times 10^4$，$1\leqslant c\leqslant 10^5$。
- $1\leqslant s\leqslant 10^5$。

Translated by Eason_AC


title: [ICPC2020 WF] Domes

background: ICPC2020 WF C

description:
Saint Basil's Cathedral is the best-known landmark of Moscow and maybe even of all of Russia. Built under Ivan the Terrible in the $16$$^{\text {th }}$ century, the cathedral is known for its colorful domes. No visit to the city is complete without taking a photo of the former church in Red Square.

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

The Moscow Tourism Board (MTB) wants to make it as safe as possible for tourists to take the perfect shot of the cathedral. Depending on where you stand when you take a picture, the relative positions of the domes will be different (see Figure C.1). The MTB is concerned that for some desired configurations of domes the region in Red Square where such a photo is possible will be so small as to lead to a dangerous overcrowding of photographers. Wanting to avoid the inevitable pushing, shoving, injury, and Covid that this could cause, the MTB would like to find the area of the region where a photo is possible for any desired ordering of the domes.

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

For simplicity, assume that cameras have a $180$-degree viewing angle. As an illustration consider Figure C.2, which shows the location of the domes (labeled $1$$\sim$$5$) and the photographer (green dot) in the plane. If the photographer shoots a picture aiming the camera straight towards the left (directly at dome $5$), then everything in the shaded area will be visible in the photograph. Note that in this photograph, the domes will appear in order $4, 3, 5, 2, 1$ from the left to the right.

Given the location of the domes within Red Square and a desired left-to-right order of the domes in the photograph, MTB wants to know the area of the region within Red Square from which such a photograph can be taken. You can assume that the domes are points, so that they do not block each other unless they are in a straight line from the photographer's view.

inputFormat:
The first line of input contains three integers $d_x$, $d_y$, and $n$, where $d_x$ and $d_y$ $(2 \leq d_x, d_y \leq 10^5)$ are the dimensions of Red Square, and $n$ $(1 \leq n \leq 100)$ is the number of domes. The bottom-left corner of Red Square is at the origin $(0,0)$ and the top-right corner is at coordinate $(d_x,d_y)$.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ $(0 < x_i < d_x, 0 < y_i < d_y)$, giving the locations $(x_i, y_i)$ of the domes. The $i^{\text {th }}$ line describes dome number $i$. No two domes are in the same location.

The last line contains a permutation of the numbers $\{1, \ldots, n\}$ specifying the desired left-to-right viewing order of the domes in the picture.

outputFormat: Output the area of the region within Red Square from which one can take a photo that shows the domes in the requested order.  Note that the area may be $0$ if there is no position from which to take the requested photo.  Your answer should have an absolute or relative error of at most $10^{-3}$.

translation:
**对于图 C.2（样例 $1$ 解释）：** 绿点为摄影师，相机视角为 $180$ 度，黑点为圆顶，规定从左到右依次为 $4, 3, 5, 2, 1$，蓝色区域为能拍摄到的部分，假设所有圆顶均为一个点，即不会互相遮挡，除非圆顶与摄影师位于同一直线上。

**简要题意：** 给定一张长为 $d_x$， 宽为 $d_y$，有 $n$ 个点的地图，设地图左下角坐标为 $(0, 0)$，右上角坐标为 $(d_x, d_y)$；给出 $n$ 个点的坐标 $(x_i, y_i)$（依次为 $1$ 到 $n$），保证任意两点不重合；最后一行给出要求拍摄出的圆顶顺序（从左到右）。输出所有符合要求的摄影师站位点的集合图形的面积，若不存在则输出 $0$。答案的相对或绝对误差不能超过 $10^{-3}$。

对于全部数据，$2 \le d_x, d_y \le 10^5$，$1 \le n \le 100$，$0 < x_i <d_x$，$0 < y_i <d_y$。


title: [ICPC2020 WF] Gene Folding

background: ICPC2020 WF D

description:
International Cell Processing Company (ICPC) is a world leader in the analysis of genetic
sequences. A genetic sequence is a sequence of nucleotides, which in this problem is
represented by a string containing only the letters $\texttt{A}$, $\texttt{C}$, $\texttt{G}$, and $\texttt{T}$
in some combination, each letter representing a single nucleotide
($\textbf{A}$denine, $\textbf{C}$ytosine, $\textbf{G}$uanine, and $\textbf{T}$hymine, respectively).

One of the key discoveries made by ICPC is that through a process called Genetically Optimized
Organic Folding (GOOF), they can take a genetic sequence and transform it into a simpler one,
while preserving many of the properties of the sequence that ICPC wants to analyze.

A single application of GOOF works as follows. Find a point between two adjacent
nucleotides in the nucleotide sequence, such that the sequence reads the same from that point in
both directions, up until the nearer end of the sequence. For instance, in the sequence $\texttt{ATTACC}$,
there are two such points: $\texttt{AT-TACC}$ and $\texttt{ATTAC-C}$. Then pick one of these points
(say, the first one), and fold the genetic sequence at that point, merging the identical nucleotides (so, in this
case the $\texttt{AT}$ and $\texttt{TA}$ would become merged, and the resulting sequence would be $\texttt{CCAT}$
or $\texttt{TACC}$).

Through repeated application of GOOF, a nucleotide can potentially be made much shorter.
However, manually searching for the appropriate folding points is very time-consuming.  ICPC
reached out to you to write a program that would automate the process of finding the folding
points and choosing them so as to obtain the shortest possible genetic sequence from a given
input sequence.

inputFormat:
The input contains a single string $s$ representing the nucleotide sequence to be analyzed.
The string consists of characters $\texttt{A}$, $\texttt{C}$, $\texttt{G}$, and $\texttt{T}$ only.
The length of $s$ is between $1$ and $4 \cdot 10^6$, inclusive.

outputFormat:
Output the smallest possible length of a sequence obtained from
the input by applying GOOF zero or more times.

translation:
### 题目描述
国际细胞加工公司(ICPC)在基因序列分析方面处于世界领先地位。遗传序列是核苷酸的序列，在这个问题中，它由一个只包含字母$\texttt{A}$、$\texttt{C}$、$\texttt{G}$和$\texttt{T}$的某种组合的字符串来表示，每个字母分别代表一个核苷酸腺嘌呤（$\textbf{A}$denine）、胞嘧啶（$\textbf{C}$ytosine）、鸟嘌呤（$\textbf{G}$uanine）和胸腺嘧啶（$\textbf{T}$hymine）。

ICPC的一个重要发现是，通过一种被称为基因优化有机折叠(GOOF)的过程，他们可以将一个基因序列转化为一个更简单的序列，同时保留ICPC想要分析的序列的许多属性。

以下是GOOF的一个应用。在核苷酸序列中两个相邻核苷酸之间找到一个点，使从该点开始的序列在两个方向上都是相同的，直到序列的最后一个点。例如，在序列$\texttt{ATTACC}$中，有两个这样的点:$\texttt{AT-TACC}$和$\texttt{ATTAC-C}$。然后选择其中一个点(比如第一个点)，在那个点折叠基因序列，合并相同的核苷酸(因此，在这种情况下，$\texttt{AT}$和$\texttt{TA}$会合并，得到的序列将是$\texttt{CCAT}$或$\texttt{TACC}$)。

通过重复使用GOOF，可以使核苷酸变得更短。但是，手工寻找合适的折叠点非常耗时。ICPC找到你，让你写一个程序来自动找到折叠点并选择它们，从而从给定的输入序列中获得尽可能短的基因序列。

### 输入格式
输入包含一个表示要分析的核苷酸序列的字符串。只包含$\texttt{A}$、$\texttt{C}$、$\texttt{G}$和$\texttt{T}$。 _s_ 长度在$1$ ~ $4\cdot10^6$之间。

### 输出格式
输出从输入中应用零次或多次GOOF得到的序列的最小可能长度。


title: [ICPC2020 WF] Landscape Generator

background: ICPC2020 WF E

description:
Interactive Creative Players Collective (ICPC) is working on a new computer game for which they want to generate realistic landscapes.
One of the ICPC engineers proposed an algorithm inspired by geological processes.
The algorithm starts with a flat landscape and repeatedly modifies it by lifting or lowering continuous blocks, thus forming *horsts* (lifted blocks) and *grabens* (lowered blocks).
The blocks to be lifted or lowered are selected at random.
ICPC hopes to obtain realistic landscapes this way.

Your task is to interpret any sequence of such modifications and output the resulting landscape.
The landscape is represented by a sequence of $n$ integer height values, one for each integer point from $1$ to $n$ on the $x$-axis.
Figure E.1 illustrates an example by connecting the height values with line segments.

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

Initially the height is $0$ at all $n$ points.
This flat shape is subjected to a sequence of modifications.
Each modification applies one of the following four operations with two integer parameters $x_1 \leq x_2$:

- $\texttt{R}$: Raise -- increase the height by $1$ at all points between $x_1$ and $x_2$ inclusive.
- $\texttt{D}$: Depress -- decrease the height by $1$ at all points between $x_1$ and $x_2$ inclusive.
- $\texttt{H}$: Hill -- add a new linearly shaped hill between $x_1$ and $x_2$.
- $\texttt{V}$: Valley -- add a new linearly shaped valley between $x_1$ and $x_2$.

Adding a hill to the current landscape works as follows.
The heights at points $x_1$ and $x_2$ are increased by $1$.
If $x_2 - x_1 > 1$, the heights at points $x_1 + 1$ and $x_2 - 1$ are increased by $2$.
If $x_2 - x_1 > 3$, the heights at points $x_1 + 2$ and $x_2 - 2$ are increased by $3$, and so on.
Figure E.2 shows an example.
Adding a valley works in the same way except the heights are decreased instead.
The maximal change of height happens in the middle between $x_1$ and $x_2$.
If $x_2 - x_1$ is odd, there will be two neighboring points with maximal change, otherwise just one.

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

inputFormat:
The first line of input contains two integers $n$ and $k$, where $n$ ($1 \leq n \leq 200\,000$) is the number of points, and $k$ ($0 \leq k \leq 200\,000$) is the number of modifications.
The $n$ points along the $x$-axis are numbered from $1$ to $n$.
The next $k$ lines describe the modifications.
Each line contains one character $c$ and two integers $x_1$ and $x_2$, where $c$ (one of $\texttt{R}$, $\texttt{D}$, $\texttt{H}$ or $\texttt{V}$) designates the operation and $x_1$ and $x_2$ ($1 \leq x_1 \leq x_2 \leq n$) specify its parameters.

outputFormat: Output $n$ lines, where the $i^{\text{th}}$ line contains the height at point $i$ after applying all modifications in the given order.


title: [ICPC2020 WF] Ley Lines

background: ICPC2020 WF F

description:
In 1921, the amateur archaeologist Alfred Watkins coined the term
"ley lines" to refer to straight lines between numerous places of
geographical and historical interest. These lines have often been
associated with mysterious and mystical theories, many of which still
persist.

One of the common criticisms of ley lines is that lines one draws on a
map are actually of non-zero width, and finding "lines" that connect
multiple places is trivial, given a sufficient density of points and a
sufficiently thick pencil. In this problem you will explore that
criticism.

For simplicity, we will ignore the curvature of the earth, and just assume
we are dealing with a set of points on a plane, each of which has a
unique $(x, y)$ coordinate, and no three of which lie on a single
straight line. Given such a set, and the thickness of your pencil,
what is the largest number of points through which you can draw a
single line?

inputFormat:
The first line of input consists of two integers $n$ and $t$, where
$n$ ($3 \le n \le 3\,000$) is the number of points in the set
and $t$ ($0 \le t \le 10^9$) is the thickness of the pencil.
Then follow $n$ lines,
each containing two integers $x$ and $y$ ($-10^9 \le x, y \le 10^9$),
indicating the coordinates of a point in the set.

You may assume that the input is such that the answer would not change
if the thickness $t$ was increased or decreased by $10^{-2}$, and that no
three input points are collinear.

outputFormat:
Output the maximum number of points that lie on a single "line" of
thickness $t$.

translation:
1921 年，业余考古学家 Alfred Watkins 提出了 _Ley lines_ 的概念，指的是连接众多地理和历史名胜的直线。这些线常常与神秘的理论联系在一起，其中许多至今仍在流传。

对 _Ley lines_ 的一个常见争议是，人们在地图上绘制的线的宽度实际上并非为 $0$，考虑到足够密集的点和足够宽的铅笔，找到连接多个地方的“线”是很容易的。为了探讨这种争议，你决定亲自在一个二维平面上亲自实践。

现在，这个二维平面上有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$，并且没有三个点在同一条直线上。你有一个宽度为 $t$ 的铅笔，你想知道你用这支铅笔画一条线，最多能够连接多少个不同的点。你可以假设在 $t$ 增加或减少 $10^{-2}$ 的情况下，答案是不会改变的。

数据范围：

- $3\leqslant n\leqslant 3000$，$0\leqslant t\leqslant 10^9$。
- $-10^9\leqslant x_i,y_i\leqslant 10^9$。

Translated by Eason_AC


title: [ICPC2020 WF] Opportunity Cost

background: ICPC2020 WF G

description:
As with most types of products, buying a new phone can be difficult.
One of the main challenges is that there are a lot of different
aspects of the phone that you might care about, such as its price, its
performance, and how user-friendly the phone is.
Typically, there will be no single phone that is simultaneously the
best at all of these things: the cheapest phone, the most powerful
phone, and the most user-friendly phone will likely be different phones.

Thus when buying a phone, you are forced to make some sacrifices by
balancing the different aspects you care about against each other and
choosing the phone that achieves the best compromise (where "best"
of course depends on what your priorities happen to be).  One way of
measuring this sacrifice is known as the *opportunity cost*,
which (for the purposes of this problem) we define as follows.

Suppose that you have bought a phone with price $x$, performance $y$,
and user-friendliness $z$. For simplicity, we assume that these three
values are measured on a comparable numeric scale where higher is
better. If there are $n$ available phones, and the values
$(x_i,y_i,z_i)$ represent the (price, performance, user-friendliness)
of the $i^{\text{th}}$ phone, then the opportunity cost of your phone
is defined as

$$\max _{1 \leq i \leq n}\left(\max \left(x_{i}-x, 0\right)+\max \left(y_{i}-y, 0\right)+\max \left(z_{i}-z, 0\right)\right)$$

Write a program that, given the list of available phones, finds a
phone with the minimum opportunity cost.

inputFormat:
The first line of input contains an integer $n$ ($2 \leq n \leq
200\,000$), the number of phones considered. Following that are $n$ lines.
The $i^{\text{th}}$ of these lines contains three integers $x_i$, $y_i$, and $z_i$,
where $x_i$ is the price, $y_i$ is the performance, and $z_i$ is the
user-friendliness of the $i^{\text{th}}$ phone ($1 \leq x_i, y_i, z_i \leq
10^9$).

outputFormat:
Output a single line containing two integers: the smallest possible
opportunity cost and an integer between $1$ and $n$ indicating the
phone achieving that opportunity cost. If there are multiple such
phones, output the one with the smallest index.

translation:
与大多数类型的产品一样，购买一部新手机可能很困难。其中一个主要困难是，你可能会关心手机的许多不同方面，比如价格、性能以及手机的用户友好程度（**本题中仅考虑这三种因素**）。通常情况下，不会有一款手机同时在所有这些方面都是最好的，也就是说，最便宜的手机、功能最强大的手机和用户最友好的手机可能是不同的手机。因此，在购买手机时，你不得不做出一些牺牲，平衡彼此关心的不同方面，并选择实现最佳折衷的手机（当然，“最佳”取决于你的优先级）。衡量这种牺牲的一种方法称为**机会成本**（为了解决这个问题），我们将其定义如下：

某商店里一共有 $n$ 部手机，其中第 $i$ 部手机的价格为 $x_i$，性能为 $y_i$，用户友好程度为 $z_i$。假设你购买了一个价格为 $x$，性能为 $y$，用户友好程度为 $z$ 的一台手机，那么购买这台手机的机会成本用如下公式表示：

$$\max\limits_{1\leqslant i\leqslant n}(\max(x_i-x,0),\max(y_i-y,0),\max(z_i-z,0))$$

现在，请求出所有 $n$ 部手机的机会成本的最小值，并找到机会成本最小的**编号最小**的手机的编号。

数据范围：

- $2\leqslant n\leqslant 2\times 10^5$。
- $1\leqslant x_i,y_i,z_i\leqslant 10^9$。

Translated by Eason_AC