title: [PA 2022] Bakterie

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Bakterie](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/bak/)**

Albert Bynstein 教授目前正在研究一种新发现的细菌菌株，他给它起了一个代号叫 *Algorithmic Proeliis*。在他的下一个实验中，他准备了一个大的矩形实验台，他将其分为 $n\cdot m$ 个区域，排列成 $n$ 行，每行 $m$ 个区域。

然后对于每个区域，教授将从三个选项中选择一个：要么他一定会在其中放置一个培养皿，要么他一定不放培养皿，要么他将抛出一枚均匀的硬币来决定放不放培养皿。一旦培养皿放置完毕，为了进行实验就需要选择一个正整数 $k$，并在每个培养皿里放置恰好 $k$ 个细菌。

这种细菌的特点是十分敌视其他菌落，因此实验过程如下：只要有一对相邻的、非空的培养皿，就会随机选出一对这样的培养皿（概率分布相等），之后两个培养皿中各有一个细菌死亡。我们假定，当且仅当两个培养皿所处的区域有一条公共边时，两区域相邻。

考虑到抛硬币决定将培养皿放在某些区域里的随机性，和选择相邻培养皿并让其中的细菌死亡的随机性，令 $f(k)$ 表示在整个实验中存活的细菌的期望数量。显然，当不再有一对相邻的培养皿各含有至少一个细菌时，实验就会结束。

一次在培养皿里放几个细菌很难，但一次性放置很多细菌就会容易得多。为此，教授沉思了一下，然后在黑板上写下了如下表达式：
$$
\lim_{k\to \infty}\frac{f(k)}{k}
$$
你作为他的助手，任务是计算上述极限的值。可以证明这个值总是一个可测的数字，所以你需要用一个不可约分数的形式表达这个值。

inputFormat:
输入第一行包含两个整数 $n,m$，表示这个矩形实验台的大小。

接下来 $n$ 行描述试验台。第 $i$ 行包含 $m$ 个字符，第 $j$ 个字符记为 $a_{i,j}$。如果 $a_{i,j}$ 是 `.`，则第 $i$ 行的第 $j$ 个区域一定不放培养皿。如果 $a_{i,j}$ 是 `O`（大写的 `o`），则第 $i$ 行的第 $j$ 个区域一定放培养皿。如果 $a_{i,j}$ 是 `?`，则第 $i$ 行的第 $j$ 个区域会用投硬币的方式决定放不放培养皿。

outputFormat: 输出一行，表示对教授问题的回答。按 $a/b$ 的形式输出，其中 $b\ge 1$ 且 $\gcd(a,b)=1$。

hint:
对于 $100\%$ 的数据，满足：

$1\le n,m\le 200$。


title: [PA 2022] Drzewa rozpinające

type: P

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Drzewa rozpinające](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/drz/)**

给定一个长为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。根据这个序列你可以生成一个 $n$ 个节点的无向图：节点 $i$ 和 $j$ 之间（对于 $i\neq j$）有 $\gcd(a_i,a_j)$ 条可区分的边将这两个节点相连。你的任务是计算这个图的生成树数量。如果对于两棵树，其中一棵树包含另一棵树中不存在的边，那么就认为这两棵树不同。因为生成树数量很大，请输出它对 $10^9+7$ 取模后的值。

inputFormat:
输入第一行一个整数 $n$，表示整数序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示这个整数序列。

outputFormat: 输出一行一个整数，表示生成的图的生成树个数，对 $10^9+7$ 取模。


title: [PA 2022] Chodzenie po linie

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Chodzenie po linie](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/lin/)**

Byteasar 是世界著名的马戏团演员，他擅长走钢丝，并在钢丝之间穿行。在他著名的表演中，马戏团帐篷的天花板下拉了 $n$ 条钢丝。如果我们俯瞰帐篷，并将其放置在坐标系中，第 $i\ (i=1,2,\ldots,n)$ 条钢丝连接点 $(i,0)$ 和点 $(p_i,1)$，其中序列 $p_1,p_2,\ldots,p_n$ 是 $1$ 到 $n$ 整数的一个排列。

Byteasar 站在其中一条钢丝上开始表演，并让观众给他一些钢丝的编号。他的目标是站在观众所说的那条钢丝上面。Byteasar 非常善于沿钢丝移动，但从一条钢丝移动到另一条钢丝是相当复杂的。因为他非常勇敢，但并不愚蠢，只有两条钢丝相交时，他才能从一条钢丝移到另一条钢丝上。所有的钢丝都悬挂在相似的高度，所以这样的移动总能成功，但这是相当累人的。出于这个原因，Byteasar 将选择一条不同钢丝之间交点个数最少的路线。唯一的例外是当以这种方式不可能到达目标钢丝的情况——在这种情况下，Byteasar 将礼貌地感谢观众并回到后台，从而不进行任何穿越。

然而，Byteasar 不确定他应该从哪根钢丝开始他的表演。对于这些钢丝的每一根，他都想知道对于观众所有可能的选择，他最少经过交点个数的和。帮他写一个程序来计算这些值。

inputFormat:
输入第一行一个整数 $n$，表示钢丝数量。

第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，，意义如题目描述。

outputFormat: 输出一行 $n$ 个整数，第 $i$ 个整数表示如果 Byteasar 从第 $i$ 根钢丝出发，对于观众所有可能的选择，他最少经过交点个数的和。

hint:
对于 $100\%$ 的数据，满足：

$1\le n\le 2 \times 10 ^ 5, 1\le p_i\le n$，

保证对于任意 $i,j\ (i\neq j)$，满足 $p_i\neq p_j$。


title: [PA 2022] Nawiasowe podziały

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Nawiasowe podziały](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/naw/)**

我确信你是知道括号序列的，但是以防万一，并且作为回顾，让我们回忆一下它的定义：

- `()` 是一个合法的括号序列。
- 如果 $S$ 是一个合法的括号序列，那么 `(S)` 也是一个合法的括号序列。
- 如果 $S_1$ 和 $S_2$ 都是合法的括号序列，那么 $S_1S_2$ 也是一个合法的括号序列。
- 不符合上述规则的括号序列都不是合法的括号序列。

给出一个长度为 $n$ 且仅由字符 `(` 和 `)` 组成的字符串，以及一个数字 $k$，这个字符串不一定是合法的括号序列。你的任务是把它分成 $k$ 个非空段（每个字符必须恰好属于一段内），使得每段中是合法括号序列的子串个数之和最小。

inputFormat:
第一行两个整数 $n,k$，分别表示字符串长度和要分成的段数。

第二行一个长度为 $n$ 的字符串，保证字符串仅由 `(` 和 `)` 组成。

outputFormat: 输出一行一个整数，表示所有段中是合法括号序列的子串个数之和的最小值。

hint:
对于 $100\%$ 的数据，满足：

$1\le k\le n\le 10 ^ 5$。


title: [PA 2022] Walizki

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Walizki](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/wal/)**

有没有想过，你在机场办理完了登机手续，你的行李箱会去哪里？就在它们消失的帘子后面，有一个巨大的大厅，里面布满了错综复杂的平台和传送带，对你的行李进行相应的分类。

Byteasar 负责评估新规划的 Byteburg Bitom 机场的行李大厅的设计。根据规划，大厅里将有 $n$ 个平台，用 $1$ 到 $n$ 的整数编号，每个行李箱最初都要运输到第一个平台。一些单向传送带可以从平台出发，连接到编号严格更大的平台。如果一个平台没有传送带出口，在这个平台的行李箱将由机场工作人员手动拿走并转移到相应的飞机上。另一方面，如果平台接有多条出口传送带，那么传送带的顺序就很重要——第一个行李箱遇到这样的平台，就会从第一条传送带上离开，第二个就会从第二条上离开，以此类推。当行李箱从最后一条传送带离开平台时，下一个行李箱又会从第一条传送带离开，如此循环往复。

一旦一个行李箱被送到第一个平台，它在传送带上的运输和工作人员的收集都在下一个行李箱放在第一个平台之前进行。换句话说，在任何时候，最多只有一个行李箱在传送带上运输。

可以想见，在处理了一定数量的行李箱后，这个行李系统会「复位」，即回到对于每个有出口传送带的平台，行李箱到达平台后都从第一条出口传送带离开的状态。Byteasar 想知道最少处理多少行李箱之后，系统将自我复位。请帮他计算出这个值！

inputFormat:
第一行一个整数 $n$，表示平台个数。

接下来 $n$ 行描述平台。第 $i$ 行开头一个非负整数 $r_i$，表示从第 $i$ 个平台离开的传送带条数。如果 $r_i=0$，表示工作人员从这个平台取行李。如果 $r_i>0$，这一行接着有 $r_i$ 个整数 $l_{i,1},l_{i,2},\ldots,l_{i,r_i}$，按顺序表示出口传送带连接的平台编号（到达的平台编号也同样是递增的）。

outputFormat: 输出一行一个整数，表示最少处理多少行李箱之后，系统将自我复位。


title: [PA 2022] Wieczór gier

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Wieczór gier](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/wie/)**

Bytie 喜欢在晚上玩他最喜欢的棋盘游戏。幸运的是，这个游戏是单人游戏，Bytie 不需要和朋友一起玩这个游戏。

棋盘共 $n$ 行，每行有 $m$ 个方格，整个棋盘共有 $nm$ 个方格。棋盘上有 $k$ 个无法区分的棋子，最多只有 $8$ 个。 棋盘的边缘有装饰性的标记，这些标记表明了棋盘的上下左右方位。每个方格可能是空的，也可能放有一个棋子，但棋盘上总是至少有一个棋子，而且至少有一个方格是空的。换句话说，满足 $1\le k\le nm-1$。游戏中一步棋指的是选择一个包含棋子的方格和与之相邻的另一个不包含棋子的方格，然后将棋子从这个方格移到相邻的空方格中。

Bytie 喜欢这个不复杂但令人兴奋的规则，他可以花几个小时来移动棋子。一天晚上，他坐在棋盘前，在棋盘上摆了 $k$ 个棋子，并想到了一种棋子的排布方式，这种排布方式也许与开始时不同。他说，每次他要走一步棋时，他都会确定现在所有棋子的所有可能走法，并从这些走法中随机选出他要怎么走棋。例如，如果棋盘上有两个棋子，第一个棋子有一种走法，第二个棋子有两种走法，那么 Bytie 将以 $\frac{1}{3}$ 的概率从这三种走法中选出一种来走下一步棋。

Bytie（正如我们已经提到的）非常喜欢玩这个游戏，所以他已经确定他会正好走 $100^{100^{100^{100}}}$ 步棋。在走了这么多步之后，棋盘上的棋子排布和目标排布相同的概率是多少？

inputFormat:
第一行两个整数 $n,m$，分别表示棋盘的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，表示初始的棋盘排布。如果第 $i$ 行第 $j$ 个字符是 `.`，那么棋盘第 $i$ 行第 $j$ 列的方格是空的。否则，这个字符将是 `O`（大写的 `o`），表示第 $i$ 行第 $j$ 列的方格中有一个棋子。

接下来空一行，再接下来 $n$ 行描述目标状态，格式如初始状态。

保证两个棋盘上的棋子个数相同，并且这个个数属于区间 $[1,nm-1]$。此外，保证棋子数不超过 $8$。

outputFormat:
输出一行一个实数，表示在恰好走了 $100^{100^{100^{100}}}$ 步棋后，棋盘上的棋子排布和目标排布相同的概率。如果输出与答案的**绝对**误差不超过 $10^{-13}$，那么输出将被认为是正确的。

注意：由于技术原因，输出小数点后位数多于 $18$ 位，或输出科学计数法形式的小数均将被判为「答案错误」。

hint:
对于 $100\%$ 的数据，满足：

$1\le n,m\le 8$。


title: [ROIR 2021 Day 1] 两台机器

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day1 T1 [ Два станка](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。

description:
有两台机器，第一台机器需要 $a$ 分钟启动，接下来每分钟会制造 $x$ 个零件，第二台机器需要 $b$ 分钟启动，接下来每分钟会制造 $y$ 个零件，两个机器不能同时位于启动过程中。

共有 $k$ 分钟，问最多能制造多少个零件。

inputFormat:
第一行为一个整数 $k$。

第二行为两个整数 $a,x$。

第三行为两个整数 $b,y$。

outputFormat: 仅一行一个整数，表示最多能制造的零件个数。


title: [ROIR 2021 Day 1] 分割数表

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day1 T2 [ Разбиение таблицы](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。

description:
有一个 $n\times m$ 的数表 $a$，$a_{i,j}=(i-1)\times m+j$。

现在将这个数表分成两个数表 $x,y$，使得 $\max\{\sum x,\sum y\}$ 最小。

形象化地来说，您可以确定一个 $i$，然后在数表的第 $i-1$ 列与第 $i$ 列间竖切一刀，或者在第 $i-1$ 行与第 $i$ 行间横切一刀，所得到的两个数表分为 $x,y$。

请构造一组方案。

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

第一行为一个整数 $t$。

接下来 $t$ 行，一行两个整数 $n,m$，表示本次询问的数表大小。

outputFormat:
对于每一个询问，输出一个字符 $c$ 和一个整数 $x$。

如果您想要竖切，$c$ 为 `V`，$x$ 为您确定的 $i$。

如果您想要横切，$c$ 为 `H`，$x$ 为您确定的 $i$。

如果有多解，请输出竖切的一种，如果还有多解，输出 $x$ 最小的一种。


title: [ROIR 2021 Day 1] 基因突变

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day1 T3 [ Изменённая ДНК](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。

description:
我们规定，一个合法的基因串仅包括 `A`、`G`、`C` 与 `T`。

我们规定，任何一个合法基因串都有一个压缩串，压缩串将原基因字符串中连续的字母压缩成这个字母的个数后跟这个字母，个数如为 $1$，则省略。

例子：`AAAAACAAAAACC` 的压缩串为 `5AC5A2C`。

现在有一个合法基因串 $S$，其压缩串为 $T$，您可以对这个合法基因串做一次操作，操作可以有如下三种：

- 在 $S$ 的第 $x$ 个字符后插入一个字符 $Z$。
- 删除 $S$ 的第 $x$ 个字符。
- 将 $S$ 的第 $x$ 个字符替换为另一个字符 $Z$。

设 $S$ 经过操作后变为 $S'$，$S'$ 的压缩串为 $T'$，求使得 $T'$ 的长度最小化或最大化的一种操作方案。

inputFormat: 一行一个字符串 $T$。

outputFormat:
输出共两行，第一行为使 $T'$ 长度最小化的一种方案，第二行为使 $T'$ 长度最大化的一种方案。

方案输出格式如下：

- 如果您想要使用 $1$ 操作，输出格式类似 `1 x Z`。
- 如果您想要使用 $2$ 操作，输出格式类似 `2 x`。
- 如果您想要使用 $3$ 操作，输出格式类似 `3 x Z`。

hint:
【样例解释】：

$S=$ `AAAAACAAAAACC`。

使用 `3 6 A` 的操作后 $S'=$ `AAAAAAAAAAACC`，$T'=$ `11A2C`。

使用 `1 2 C` 的操作后 $S'=$ `AACAAACAAAAACC`，$T'=$ `2AC3AC5A2C`。

【数据范围】：

对于所有子任务，有 $1\le |T|\le 10^5$，$1\le |S|\le 10^9$。

| 子任务编号 |数据范围| 分值 |
|:-:|:-:|:-:|
|$1$|$\lvert T\rvert\le \lvert S\rvert\le 10$|$9$ |
|$2$|$\lvert T\rvert\le 100$，$\lvert S\rvert\le 10^4$|$17$|
|$3$|$\lvert T\rvert\le 10^3$，$\lvert S\rvert\le 10^5$|$21$|
|$4$|$\lvert S\rvert\le 10^7$|$11$|
|$5$|无特殊限制|$42$|


title: [ROIR 2021 Day 1] 绳子

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day1 T4 [ Антенна](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。

description:
有 $n$ 根绳子，第 $i$ 根绳子长 $s_i$ cm，有 $m_i$ 个节点，第 $j$ 个节点在离绳子左端点 $p_{i,j}$ cm 处。

试构造一组从左至右连接绳子的方案，设该方案的绳子顺序为 $q$，$q$ 显然会是 $1\sim n$ 的一个排列，且满足如下要求：将第 $q_i$ 根绳子的右端点与第 $q_{i+1}$ 根绳子的左端点相接后 $(1\le i<n)$，相邻的节点间的距离相等。

显然有可能没有方案，这个时候请输出 `No`。

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

接下来共 $2\times n$ 行：

- 第 $2\times i(1\le i\le n)$ 行为两个整数 $m_i$ 与 $s_i$。
- 第 $2\times i+1(1\le i\le n)$ 行为 $m_i$ 个整数 $p_{i,j}$。

outputFormat:
若可以构造一组方案，输出 `Yes`，接下来再输出一行 $n$ 个整数 $q_i$。

若无解，输出 `No`。


title: [ROIR 2021 Day 2] 日期

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day2 T1  [Календарь на Альфе Центавра](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。

description:
在一颗外星球上，一年有 $m$ 个月，一个月有 $d$ 天，一周有 $w$ 天。

为了区分每一周的每一天，人类使用了星期几来说明，而这颗外星球上的居民使用小写英文字母 `a`$\sim$`z` 来表示每一周的每一天。

已知 $1$ 年 $1$ 月 $1$ 日对应星期 `a`，求 $k$ 年 $j$ 月 $i$ 日对应星期几。

inputFormat:
第一行为三个整数 $d,m,w$。

第二行为三个整数 $i,j,k$。

outputFormat: 仅一行一个字母，表示 $k$ 年 $j$ 月 $i$ 日对应星期几。


title: [ROIR 2021 Day 2] 染色

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day2 T3  [Хорошие раскраски](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。

description:
用 $c$ 种颜色对一个 $n\times m$ 的矩阵染色，要求对于任意 $1\le x_1<x_2\le n$，$1\le y_1<y_2\le m$，$(x_1,y_1)$，$(x_2,y_1)$，$(x_1,y_2)$，$(x_2,y_2)$ 所染的颜色不完全相同。

试构造一组方案。

数据保证有解。

inputFormat: 一行三个整数 $n,m,c$。

outputFormat: 输出 $n$ 行，每一行 $m$ 个范围在 $1\sim c$ 的整数，表示染色的颜色种类。

hint:
- 对于 $25\%$ 的数据，$c=2$。
- 对于另外 $75\%$ 的数据，$c=3$。
- 对于 $100\%$ 的数据，$2\le n,m\le 10$，$2\le c\le 3$。

注：附件为本题的 Special Judge，供大家调试。


title: [ROIR 2021 Day 2] A+B

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day2 T4  [A+B](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。

description:
有三个长为 $n$ 的可能含前导零的整数 $a,b,c$，按如下方式排成三行 $n$ 列：

```
a
b
c
```
问有多少种不同的**列**的排列方式，使得被横着念出来的三个整数 $x,y,z$ 有 $x+y=z$ 成立且三个整数均没有前导零。

排列方式的个数可能很多，输出其 $\bmod \ 10^9+7$ 即可。

inputFormat:
第一行为一个长 $n$ 的整数 $a$。

第二行为一个长 $n$ 的整数 $b$。

第三行为一个长 $n$ 的整数 $c$。

outputFormat: 一行一个整数，表示不同的排列方式的个数对 $10^9+7$ 取模的结果。


title: [ROIR 2021 Day 2] 好数

background: **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day2 T2  [Числа](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。

description:
定义第一类好数为所有数位上的数字均相同的数。

定义第二类好数为满足如下任意一个条件的数：
- 为第一类好数。
- 设 $t$ 为数的位数，则有 $t-1$ 位数上的数字相同，且无前导零。

现给定一个 $x$，求出 $\ge x$ 的第一个第 $k+1$ 类好数 $y$。

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

第二行一个整数 $k$。

outputFormat: 一行一个整数 $y$。


title: [CCC 2023 S2] Symmetric Mountains

description:
Rebecca is a tour guide and is trying to market the Rocky Mountains for her magazine. She recently took a beautiful picture consisting of $N$ mountains where the $i\text{-th}$ mountain from the left has a height $h_i$. She will crop this picture for her magazine, by possibly removing some mountains from the left side of the picture and possibly removing some mountains from the right side of the picture. That is, a crop consists of consecutive mountains starting from the $l\text{-th}$ to the $r\text{-th}$ mountain where $l \leq r$. To please her magazine readers, Rebecca will try to find the most symmetric crop.

We will measure the $asymmetric\ value$ of a crop as the sum of the absolute difference for every pair of mountains equidistant from the midpoint of the crop. To help understand that definition, note that the absolute value of $a$ number $v$, written as $|v|$, is the non-negative value of v: for example $\lvert -6 \rvert = 6$ and $|14| = 14$. The asymmetric value of a crop is the sum of all $|h_{l+i} - h_{r-i}|$ for $0 \leq i \leq \frac{r-l}{2}$. To put that formula in a different way, we pair up the mountains working from the outside in toward the centre, calculate the absolute difference in height of each of these pairs, and sum them up.

Because Rebecca does not know how wide the picture needs to be, for all possible crop lengths, find the asymmetric value of the most symmetric crop (the crop with the minimum asymmetric value).

inputFormat:
The first line consists of an integer $N$, representing the number of mountains in the picture.

The second line consists of $N$ space-separated integers, where the $i\text{-th}$ integer from the left represents $h_i$.

The following table shows how the available 15 marks are distributed:

| Marks | Bounds on $N$ | Bounds on $h_i$ | Additional Constraints |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $5$ | $1 \leq N \leq 300$ | $0 \leq h_i \leq 10^5$ | None. |
| $5$ | $1 \leq N \leq 5000$ | $0 \leq h_i \leq 10^5$ | Height of mountains are in non-decreasing order from left to right. |
| $5$ | $1 \leq N \leq 5000$ | $0 \leq h_i \leq 10^5$ | None. |

outputFormat: Output on one line $N$ space-separated integers, where the $i\text{-th}$ integer from the left is the asymmetric value of the most symmetric picture of crops of length $i$.

translation:
Rebecca 有一张落基山脉的照片，上面排列着 $N(1\leq N \leq 5000)$ 座山，从左向右的第 $i$ 座山的高度是 $h_i(1\leq h_i \leq 10^5)$。Rebecca 截图保留照片的一个连续段，这张截图的不对称性定义为：处于截图上对称位置的山的高度差的绝对值之和（截图最左和最右的山的高度差，左数第二和右数第二的山的高度差，诸如此类的和）。

Rebecca 想要知道对于长度为 $i$ 的截图，拥有的最小不对称性。请你对于 $1\leq i \leq N$，输出这个值。

hint:
Explanation of Output for Sample Input $1$:

We will show why the fifth value from the left is $2$.Let us try to compute all the asymmetric values of crops with length $5$.

The height of the mountains in the first crop is $[3, 1, 4, 1, 5]$. The asymmetric value of this crop is $|3 - 5| + |1 - 1| + |4 - 4| = 2$.

The height of the mountains in the second crop is $[1, 4, 1, 5, 9]$. The asymmetric value of this crop is $|1 - 9| + |4 - 5| + |1 - 1| = 9$.

The height of the mountains in the last crop is $[4, 1, 5, 9, 2]$. The asymmetric value of this crop is $|4 - 2| + |1 - 9| + |5 - 5| = 10$.

Hence, the most symmetric crop of length $5$ is $2$.

Explanation of Output for Sample Input $2$:

This sample satisfies the second subtask. Note that the only crop of length $4$ is $[1, 3, 5, 6]$ which has asymmetric value of $|1 - 6| + |3 - 5| = 7$.

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

- Subtask 1（5 points）：$1\leq N \leq 300$，$0\leq h_i \leq 10^5$。

- Subtask 2（5 points）：$1 \leq N \leq 5000$，$0 \leq h_i \leq 10^5$，保证山的高度从左到右单调不减。

- Subtask 3（5 points）：$1\leq N\leq 5000$，$0 \leq h_i \leq 10^5$。


title: [CCC 2023 S3] Palindromic Poster

description:
Ryo and Kita are designing a new poster for Kessoku Band. After some furious brainstorming, they came to the conclusion that the poster should come in the form of a $2\text{-D}$ grid of lowercase English letters (i.e. `a` to `z`), with $N$ rows and $M$ columns.

Furthermore, it is known that Ryo and Kita both have peculiar tastes in palindromes. Ryo will only be satisfied with the poster if exactly $R$ of its rows are palindromes, and Kita will only be satisfied with the poster if exactly $C$ of its columns are palindromes. Can you design a poster that will satisfy both Ryo and Kita, or determine that it is impossible to do so?

**Note**: A string is considered a palindrome if it is the same when read forwards and backwards. For example, `kayak` and `bb` are palindromes, whereas `guitar` and `live` are not.

inputFormat:
The first and only line of input consists of $4$ space-separated integers $N, M, R$, and $C$.

The following table shows how the available $15$ marks are distributed.

| Marks | Bounds on $N$ | Bounds on $M$ | Bounds on $R$ | Bounds on $C$ |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| $2$ marks | $2 \leq N \leq 2000$ | $2 \leq M \leq 2000$ | $R = 1$ | $C = 1$ |
| $2$ marks | $N = 2$ | $M = 2$ | $0 \leq R \leq N$ | $0 \leq C \leq M$ |
| $4$ marks | $N = 2$ | $2 \leq M \leq 2000$ | $0 \leq R \leq N$ | $0 \leq C \leq M$ |
| $7$ marks | $2 \leq N \leq 2000$ | $2 \leq M \leq 2000$ | $0 \leq R \leq N$ | $0 \leq C \leq M$ |

outputFormat:
If it is impossible to design a poster that will satisfy both Ryo and Kita, output `IMPOSSIBLE` on a single line.

Otherwise, your output should contain $N$ lines, each consisting of $M$ lowercase English letters, representing your poster design. If there are multiple possible designs, output any ofthem.

translation:
Ryo 和 Kita 正在为 Kessoku 乐队设计一张新的海报，他们两个人都有各自不同的审美，但都同时认为一份符合他们审美的海报的内容应该都为小写字母，且大小为 $N \times M$。Ryo 认为当有 $R$ 数量的行是回文时，这个海报是符合其审美的；Kita 认为当有 $C$ 数量的列是回文时，这个海报是符合其审美的。

现在分别给出 $N,M,R,C$，问你是否可以构造出一个 $N \times M$ 的海报满足要求，可以就输出你的方案，不行的话输出 `IMPOSSIBLE`。

samples:
2 2 2 1
IMPOSSIBLE

hint:
Explanation of Output for Sample Input $1$：

In the given design, only the second row (namely `radar`) and the second and third columns (namely `naan` and `iddi`) are palindromes. Since exactly $R = 1$ of the rows and $C = 2$ of the
columns are palindromes, this is an acceptable design.

Explanation of Output for Sample Input $2$：

In this case, it can be proven that it is impossible to satisfy both Ryo and Kita.

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

- Subtask 1（2 points）：数据保证 $2 \leq N \leq 2000$，$2\leq M\leq 2000$，$R = 1$，$C = 1$。

- Subtask 2（2 points）：数据保证 $N = 2$，$M = 2$，$0\leq R\leq N$，$0\leq C\leq M$。

- Subtask 3（4 points）：数据保证 $N = 2$，$2\leq M \leq2000$，$0\leq R\leq N$，$0\leq C\leq M$。

- Subtask 4（7 points）：数据保证 $2\leq N\leq 2000$，$2\leq M \leq2000$，$0\leq R\leq N$，$0\leq C\leq M$。


title: [CCC 2023 S4] Minimum Cost Roads

description:
As the newly elected mayor of Kitchener, Alanna's first job is to improve the city's road plan.

Kitchener's current road plan can be represented as a collection of $N$ intersections with $M$ roads, where the $i\text{-th}$ road has length $l_i$ meters, costs $c_i$ dollars per year to maintain, and connects intersections $u_i$ and $v_i$. To create a plan, Alanna must select some subset of the $M$ roads to keep and maintain, and that plan's cost is the sum of maintenance costs of all roads in that subset.

To lower the city's annual spending, Alanna would like to minimize the plan's cost. However, the city also requires that she minimizes travel distances between intersections and will reject any plan that does not conform to those rules. Formally, for any pair of intersections $(i, j)$, if there exists a path from $i$ to $j$ taking $l$ meters on the existing road plan, Alanna's plan must also include a path between those intersections that is at most $l$ meters.

inputFormat:
The first line contains the integers $N$ and $M$.

Each of the next $M$ lines contains the integers $u_i,v_i,l_i$ and $c_i$, meaning that there currently exists a road from intersection $u_i$ to intersection $v_i$ with length $l_i$ and cost $c_i$$(1 \leq u_i, v_i \leq N, u_i \neq v_i)$.

The following table shows how the available 15 marks are distributed.

| Marks | Bounds on $N$ and $M$ | Bounds on $l_i$ | Bounds on $c_i$ | Additional Constraints |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| $3$ marks | $1 \leq N\leq 2000$, $1\leq M \leq 2000$ | $l_i = 0$ | $1 \leq c_i \leq 10^9$ | None. |
| $6$ marks | $1 \leq N\leq 2000$, $1\leq M \leq 2000$ | $1 \leq l_i \leq 10^9$ | $1 \leq c_i \leq 10^9$ | There is at most one road between any unordered pair of intersections. |
| $6$ marks | $1 \leq N\leq 2000$, $1\leq M \leq 2000$ | $0 \leq l_i \leq 10^9$ | $1 \leq c_i \leq 10^9$ | None. |

outputFormat: Output one integer, the minimum possible cost of a road plan that meets the requirements.

translation:
给定一张 $N(1\leq N \leq 2000)$ 个点的无向图和 $M(1\leq M \leq 2000)$ 条无向边，第 $i$ 条边连接点 $u_i$ 和 $v_i$，长度为 $l_i(0\leq l_i \leq 10^9)$，维护费用是 $c_i(1\leq c_i \leq 10^9)$。你需要选择费用总和最小的边集，使得只保留这些边后，任意两点间的最短路长度不变。

输出最小的费用总和。

hint:
Explanation of Output for Sample Input：

Here is a diagram of the intersections along with a valid road plan with minimum cost.

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

Each edge is labeled with a pair $(l, c)$ denoting that it has length $l$ meters and cost $c$ dollars.

Additionally, the roads that are part of the plan are highlighted in blue, with a total cost of $7 + 1 + 6 + 7 + 4 = 25$.

It can be shown that we cannot create a cheaper plan that also respects the city’s requirements.

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

- Subtask 1（3 points）：数据保证 $1\leq N \leq 2000$，$1\leq M \leq 2000$，$l_i = 0$，$1\leq c_i \leq 10^9$。

- Subtask 2（6 points）：数据保证 $1\leq N\leq 2000$，$1\leq M \leq 2000$，$1\leq l_i \leq 10^9$，$1\leq c_i \leq 10^9$，且在任何一对十字路口之间最多只有一条路。

- Subtask 3（6 points）：数据保证 $1\leq N\leq 2000$，$1\leq M \leq 2000$，$0\leq l_i \leq 10^9$，$1\leq c_i \leq 10^9$。


title: [CCC 2023 S5] The Filter

description:
Alice, the mathematician, likes to study real numbers that are between $0$ and $1$. Her favourite tool is the filter.

A filter covers part of the number line. When a number reaches a filter, two events can happen. If a number is not covered by the filter, the number will pass through. If a number is covered, the number will be removed.

Alice has infinitely many filters. Her first $3$ filters look like this:

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

In general, the $k\text{-th}$ filter can be defined as follows:

- Consider the number line from $0$ to $1$.

- Split this number line into $3^k$ equal-sized pieces. There are $3^k + 1$ points and $3^k$ intervals.

- The $k\text{-th}$ filter consists of the $2^{\text{nd}}$ interval, $5^{\text{th}}$ interval, $8^{\text{th}}$ interval, and in general, the $(3i-1)^{\text{th}}$ interval. The points are **not** part of the $k\text{-th}$ filter.

Alice has instructions for constructing the Cantor set. Start with the number line from $0$ to $1$. Apply all filters on the number line, and remove the numbers that are covered. The remaining numbers form the Cantor set.

Alice wants to research the Cantor set, and she came to you for help. Given an integer $N$, Alice would like to know which fractions $\frac{x}{N}$ are in the Cantor set.

inputFormat:
The first line contains the integer $N$.

The following table shows how the available $15$ marks are distributed.

| Marks | Bounds on $N$ | Additional Constraints |
| :----------: | :----------: | :----------: |
| $3$ marks | $3 \leq N \leq 3^{18}$ | $N$ is a power of $3$. |
| $4$ marks | $2 \leq N \leq 2 \times 10^5$ | None. |
| $8$ marks | $2 \leq N \leq 2 \times 10^9$ | None. |

outputFormat:
Output all integers $x$ where $0 \leq x \leq N$ and $\frac{x}{N}$ is in the Cantor set.

Output the answers in increasing order. The number of answers will not exceed $10^6$.

translation:
Alice 有无穷个筛子，筛子从 $1$ 开始标号。第 $k$ 个筛子作用如下：

- 考虑数轴上大于等于 $0$ 小于等于 $1$ 部分。
- 将这部分均分为 $3^k$ 个同样长的段。此时将获得 $3^k+1$ 个端点和 $3^k$ 个段。
- 筛子将筛除形如第 $2,5,8,(3 \times i-1)$ 个段。注意，端点不会被筛去。

给定正整数 $N(1\leq N \leq 2 \times 10^9)$，你需要从小到大输出所有的 $x(0\leq x \leq N)$，满足 $\frac x N$ 没有被筛去。

保证合法的 $x$ 的数量小于等于 $10^6$ 个。

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

$\frac{5}{12},\frac{6}{12},\frac{7}{12}$ are not in the Cantor set because they were covered by the 1st filter.
Furthermore, $\frac{2}{12}$ and $\frac{10}{12}$
are not in the Cantor set because they were covered by the $2^{\text{nd}}$ filter.

It can be shown that the remaining fractions will pass through all filters.

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

- Subtask 1（3 points）：$3 \leq N \leq 3 ^{18}$，$N$ 是 $3$ 的整数次幂。

- Subtask 2（4 points）：$2 \leq N \leq 2\times 10^5$。

- Subtask 3（8 points）：$2 \leq N \leq 2 \times 10^9$。


title: [EGOI2021] Number of Zeros / 零的个数

background:
Day 1 Problem A.

题面译自 [EGOI2021 zeros](https://stats.egoi.org/media/task_description/2021_zeros_en.pdf)。

description:
圣诞老人已经在准备 $2021$ 年圣诞节。他希望买正整数个礼物，使得可以平均分给所有不淘气的孩子。然而，他不知道具体有多少不淘气的孩子，只知道数量一定在 $a$ 和 $b$ 之间。他希望买最少的正整数个礼物，使得可以被任何 $x\in\{a,a+1,\ldots,b\}$ 个孩子平分。

他已经计算出这（可能很大的）礼物数量，但他不确定计算是否正确，希望你可以进行一些基本的正确性检查。你可以告诉他答案的后导零个数吗？

inputFormat: 一行，两个整数 $a,b$。

outputFormat: 一行，一个整数，表示答案的后导零个数。

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

如果可能有 $1$ 至 $6$ 个不淘气的孩子，圣诞老人至少需要 $60$ 个礼物（这是最小的能被 $1,2,3,4,5,6$ 整除的正整数），而 $60$ 有一个后导零。

---

**样例 $2$ 解释**

如果可能有 $10$ 或 $11$ 个不淘气的孩子，圣诞老人会买 $110$ 个礼物。

---

**数据范围**

对于全部数据，$1\le a\le b\le 10^{18}$。

- 子任务一（$6$ 分）：$b\le 16$。
- 子任务二（$7$ 分）：$b\le 40$。
- 子任务三（$9$ 分）：$a=1$，$b\le 200$。
- 子任务四（$12$ 分）：$b-a\le 10^6$。
- 子任务五（$17$ 分）：$a=1$。
- 子任务六（$49$ 分）：无特殊限制。


title: [EGOI2021] Luna likes Love / 卢娜爱磕 cp

background:
Day 1 Problem B.

题面译自 [EGOI2021 luna](https://stats.egoi.org/media/task_description/2021_luna_en.pdf)。

description:
卢娜想出了一个不同寻常的点子。她让 $2n$ 个朋友排成一条长队，并给他们每人一个 $1\sim n$ 的整数。每个整数恰好出现两次。每一对有相同数字的朋友组成一对情侣。

卢娜希望让每一对情侣去一次约会。然而，并没有这么简单。为了让一对情侣去约会，双方在队伍中必须互相紧挨着，也就是说不能有任何人站在他们中间。

卢娜可以进行两种操作：

- 她可以让任意两个紧挨着的人交换位置。
- 如果一对情侣互相紧挨着，卢娜可以让他们去约会。这一对情侣将从队伍中离开，后面的人会补上他们的位置。

所有操作可以以任意的顺序进行。例如，她可以交换几次，然后让几对情侣去约会，再交换几次。

请求出让所有人去约会的最少操作次数。

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

第二行 $2n$ 个整数 $a_i$，依次表示队伍中朋友拿到的数字。

outputFormat: 一行，一个整数，表示最少操作次数。

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

卢娜先让第三个人和第四个人交换位置，得到 $3,1,1,2,2,3$。

然后她可以让数字 $1$ 和 $2$ 的情侣去约会。之后，数字 $3$ 的情侣会互相紧挨着，卢娜可以让他们也去约会。

综上，共需要 $4$ 次操作：一次交换和三次让情侣去约会。

---

**数据范围**

对于全部数据，$1\le n\le 5\times 10^5$，$1\le a_i\le n$。

- 子任务一（$7$ 分）：任意一对情侣都紧挨着，$n\le 100$。
- 子任务二（$8$ 分）：任意一对情侣之间至多有一个人，$n\le 100$。
- 子任务三（$11$ 分）：前 $n$ 个人的数字构成一个 $1\sim n$ 的排列，$n\le 3\times 10^3$。
- 子任务四（$16$ 分）：前 $n$ 个人的数字构成一个 $1\sim n$ 的排列。
- 子任务五（$22$ 分）：$n\le 3\times 10^3$。
- 子任务六（$36$ 分）：无特殊限制。


title: [EGOI2021] Twin Cookies / 姐妹分饼干

background:
Day 1 Problem C.

题面译自 [EGOI2021 twincookies](https://stats.egoi.org/media/task_description/2021_twincookies_en.pdf)。

本题官方没给交互库，由于交互库实现原因，数据可能较弱。如果您会写自适应交互库，可以与 rui_er 取得联系。

description:
**本题是一道 I/O 交互题。**

索菲在准备她们姐妹的生日派对。她们都喜欢饼干。这次生日，她们准备尝试一些新东西：不同饼干口味公司（UCTC）生产的饼干。

UCTC 生产的每一个饼干都有一个在 $1$ 到 $10^{16}$ 之间的整数美味度。索菲姐妹会嫉妒彼此，因此她们收到的饼干的总美味度必须相同。

UCTC 只接受**恰好 $n$ 个**饼干的订单。在每个订单中，顾客详细说明他们想要的每个饼干的美味度。

顾名思义，不同饼干口味公司拒绝为同一个顾客生产两块美味度相同的饼干。索菲必须确保她从不订购同一种美味度两次——不管是同一个订单或者两个不同的订单。索菲以前从来没有从 UCTC 订购过，所以她可以购买每种口味的饼干最多一次。

还有一件事阻碍着索菲：众所周知 UCTC 的物流服务极为糟糕。当一个顾客订购 $n$ 个饼干，只有其中一个会被送达。其余的饼干都被物流的员工偷吃了。顾客无法决定到底哪块饼干会被送达。

鉴于生日临近，索菲只有时间订购至多 $101$ 次。你的任务是帮助她。

具体地，你需要做的事情如下：

1. 首先，订购饼干。你可以订购至多 $101$ 次，每次包含恰好 $n$ 个想要的美味度。你可以分多次订购。**在每笔订单发出后，你会立刻知道送达的饼干的美味度。**

    请记住你不能多次订购同一个美味度的饼干，即使在不同订单中也不行。（特别地，如果你订购了一些美味度的饼干但没有送达，你也**不能**重复订购同一美味度的饼干。）

2. 然后，分饼干。当你收到足够多饼干的时候，你应该给姐妹分配**一些**饼干。每个人应该收到至少一个饼干，并且她们收到的饼干的总美味度应该相同。**你不需要分配所有送达的饼干。**

outputFormat:
你的程序每次输出后，你必须**刷新输出流**。为了保证交互库立即得到你的输出，这是必须的。

一些例子：

- 在 C++ 语言中，有多种选择：
    - `fflush(stdout);`
    - `std::cout << std::flush;`
    - `std::cout << std::endl;`（注意这会打印一个换行）
    - 从 `std::cin` 读入也会刷新输出流。
- 在 Java 语言中，你可以使用 `System.out.flush()`
- 在 Python 语言中，你可以使用 `sys.stdout.flush()`

---

**交互方式**

你的程序应该进行如下的若干操作：

1. 从标准输入读入 $n$。
2. 至多 $101$ 次：
    1. 首先，向标准输出打印一行描述 $n$ 个饼干的一个订单。
    2. 然后，输入送达的饼干美味度。

        保证这个数在当前订单的 $n$ 个美味度当中。
3. 输出三行，描述一种给姐妹分配一些饼干的方式。

交互库会在每一行写一个整数。

为了订购饼干，输出一行，以 `?` 打头并跟着 $n$ 个整数：订购的饼干美味度。在每个整数之前输出一个空格。

请记住你可以订购至多 $101$ 次，并且不被允许多次订购相同美味度的饼干。

当你订购了足够多的饼干的时候，输出最后三行描述分配方式。

第一行的格式是 `! m k`，其中 $m,k>0$：两个人分别分到饼干的数量。

第二行包含 $m$ 个正整数，用一个空格隔开：第一个人收到的饼干美味度。

第三行包含 $k$ 个正整数，用一个空格隔开：第二个人收到的饼干美味度。

输出必须满足以下要求：

1. 每个人至少收到一个饼干。
2. 每个人收到饼干的总美味度相同。
3. 你只能使用送达的饼干。
4. 每个饼干只能分给至多一个人。

任何符合要求的输出都将被判为 AC。特别地，你可以以任意顺序输出选择的饼干。

在你输出完最后三行后，最后刷新一次输出流，并正常结束程序。

hint:
**提示**

样例输入输出应该一行一行阅读。你的程序交替从标准输入读一个整数以及向标准输出打印一行（或最后三行）。

交互库任意地选择送达的饼干。这意味着在某些测试点中，交互库可能是自适应的；但在另一些测试点中，交互库可能随机选择。特别地，对于 $n=2$，如果你跟样例 $2$ 输出相同的订单，你可能得到不同的结果。

---

**数据范围**

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

- 子任务一（$8$ 分）：$n=1$。
- 子任务二（$9$ 分）：$n\le 2$。
- 子任务三（$18$ 分）：$n\le 25$。
- 子任务四（$16$ 分）：$n\le 200$。
- 子任务五（$13$ 分）：$n\le 10^3$。
- 子任务六（$36$ 分）：无特殊限制。


title: [EGOI2021] Lanterns / 灯笼

background:
Day 1 Problem D.

题面译自 [EGOI2021 lantern](https://stats.egoi.org/media/task_description/2021_lantern_en.pdf)。

description:
农夫约翰带着他的奶牛群在阿尔卑斯山进行了一次徒步旅行！一段时间后，天色转暗，旅行结束了。然而，一些奶牛仍然被困在山脉的各个地方，现在约翰需要营救它们！

现在牛群正在穿越的山脉用平面直角坐标系中的 $n$ 个点表示。我们称这些点为“山峰”。山峰被依次编号为 $1\sim n$。第 $i$ 座山峰的坐标为 $(i,h_i)$。值 $h_i$ 代表第 $i$ 座山峰的**海拔高度**。保证 $h_1,h_2,\ldots h_n$ 构成一个 $1\sim n$ 的排列。

山峰 $i$ 和山峰 $i+1$ 用一条线段相连。

由于现在是晚上，约翰必须携带至少一盏正常工作的灯笼才能上山。幸运的是，有 $k$ 个灯笼可供购买。第 $j$ 个灯笼可以在山峰 $p_j$ 以 $c_j$ 法郎的价格购买。

不幸的是，第 $j$ 个灯笼只有在约翰的海拔在 $[a_j,b_j]$ 时才能正常工作。换句话说，如果约翰的海拔严格低于 $a_j$ 或严格高于 $b_j$，第 $j$ 个灯笼不会正常工作。需要注意的是，灯笼在离开海拔范围时不会损坏。例如，当约翰的海拔超过 $b_j$ 时，第 $j$ 个灯笼会停止工作，但只要约翰返回到海拔 $b_j$，灯笼会重新开始工作。

如果约翰现在在山峰 $p$，他可以执行以下三种操作之一：

- 他可以买一个在 $p$ 处售卖的灯笼。购买灯笼后，他可以永久使用。
- 如果 $p > 1$，他可以走到山峰 $p-1$。
- 如果 $p < n$，他可以走到山峰 $p+1$。

约翰在没有正常工作的灯笼时不能移动。他必须保证每个时刻都有至少一盏灯笼正常工作，才能在两座山峰间移动。（在行走过程中不必是同一盏灯笼。）

例如，假设农夫约翰目前在海拔为 $4$ 的山峰上，希望走到高度为 $1$ 的相邻山峰。如果约翰有海拔范围为 $[1,3]$ 和 $[3,4]$ 的两盏灯笼，他可以从一个山峰走到另一个山峰。

但是，如果约翰只有海拔范围为 $[1,1]$ 和 $[2,5]$ 的两盏灯笼，他无法在这两座山峰间行走：例如，他没有灯笼能在海拔 $1.47$ 处正常工作。

你需要给出多个独立问题的答案。

对于每个满足 $a_j\le h_{p_j}\le b_j$ 的 $1\le j\le k$，假设约翰一开始在山峰 $p_j$ 并买下第 $j$ 个灯笼。为了搜索整个山脉，他必须重复执行上面提到的三种操作。对于每个 $j$，求出约翰至少需要花几法郎，才能搜索整个山脉。（这个花费包括初始时买的第 $j$ 个灯笼。）

inputFormat:
第一行两个整数 $n,k$——山峰个数和灯笼个数。

第二行 $n$ 个整数 $h_1,h_2,\ldots,h_n$：每座山峰的海拔。保证 $h_i$ 构成一个 $1\sim n$ 的排列。

接下来 $k$ 行，每行四个整数 $p_j,c_j,a_j,b_j$——第 $j$ 个灯笼的售卖位置、价格和海拔范围。

outputFormat:
对于每个 $1\le j\le k$，输出一行：

- 若 $h_{p_j}$ 不在 $[a_j,b_j]$ 内，输出 $-1$。
- 否则，如果约翰一开始购买第 $j$ 个灯笼，无法搜索整个山脉，输出 $-1$。
- 否则，输出此时的最少花费。

hint:
**样例解释**

如果约翰从第 $3$ 座山峰开始，购买第 $1$ 个灯笼，他可以如下操作：

- 向左走两次，到达山峰 $1$。
- 购买灯笼 $2$。
- 向右走到山峰 $4$。
- 购买灯笼 $3$。
- 向右走到山峰 $7$。

此时，约翰到达了每座山峰至少一次，花费了 $1+2+4=7$ 法郎。

约翰不能从购买灯笼 $2,6,7$ 开始，因为它们在购买的海拔处不工作。因此，它们的答案为 $-1$。

如果约翰从购买灯笼 $3,4$ 开始，他不用购买其他灯笼就可以访问每座山峰。

如果约翰从购买灯笼 $5$ 开始，他必须购买灯笼 $4$。

如果约翰从购买灯笼 $8$ 开始，他会被困在山峰 $7$。即使他购买了灯笼 $7$，他依然无法从山峰 $7$ 走到山峰 $6$。

---

**数据范围**

对于全部数据，$1\le n,k\le 2\times 10^3$，$1\le h_i\le n$ 且 $h_i$ 构成一个 $1\sim n$ 的排列，$1\le p_j\le n$，$1\le c_j\le 10^6$，$1\le a_j\le b_j\le n$。

- 子任务一（$9$ 分）：$n\le 20$，$k\le 6$。
- 子任务二（$12$ 分）：$n,k\le 70$。
- 子任务三（$23$ 分）：$n,k\le 300$，$h_i=i$。
- 子任务四（$16$ 分）：$n,k\le 300$。
- 子任务五（$40$ 分）：无特殊限制。


title: [EGOI2021] Shopping Fever / 购物热

background:
Day 2 Problem A.

题面译自 [EGOI2021 shoppingfever](https://stats.egoi.org/media/task_description/2021_shoppingfever_en.pdf)。

description:
海蒂在一个大商店中。她希望购买 $n$ 个商品。

今天是她的幸运日。商店正在进行促销活动：对于每笔账单，顾客获得以下两种优惠之一：

1. 如果买了至少 $3$ 件商品，最便宜的一个免费。
2. 如果买了少于 $3$ 件商品，这笔账单获得 $q\%$ 的折扣。

海蒂希望不重复地买所有 $n$ 件商品。她可以分成任意笔账单购买。对于每笔账单，将会按照对应的优惠政策打折。

她买所有 $n$ 件商品至少需要多少钱？

inputFormat:
第一行两个整数 $n,q$——商品数和买少于 $3$ 件时的折扣比例。

第二行 $n$ 个整数 $p_i$——商品的价格。

另外，保证商品价格可以被 $100$ 整除。因此，每笔账单折扣的价格永远为整数。

outputFormat: 一行，一个整数——至少需要的钱数。

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

海蒂先购买三个价格为 $200$ 元的商品，花费 $400$ 元（免费获得了一个商品）。再购买三个价格为 $300$ 元的商品，花费 $600$ 元（同样免费获得一个）。最后，她购买剩余的价格为 $100$ 元的商品，获得 $10\%$ 的折扣。

---

**样例 $2$ 解释**

如果海蒂用一笔账单购买三个商品，她获得 $100$ 元的折扣。然而，如果她分三次购买三个商品，获得的折扣变为 $(1000+500+100)\cdot\frac{20}{100}=320$ 元。

---

**数据范围**

对于全部数据，$1\le n\le 10^5$，$0\le q\le 100$，$100\le p_i\le 10^5$ 且 $100\mid p_i$。

- 子任务一（$8$ 分）：$n=3$，$100\le p_i\le 10^3$。
- 子任务二（$18$ 分）：$q=0$。
- 子任务三（$16$ 分）：$q=40$。
- 子任务四（$22$ 分）：$100\le p_i\le 10^3$。
- 子任务五（$36$ 分）：无特殊限制。


title: [EGOI2021] Railway / 瑞士铁路

background:
Day 2 Problem B.

题面译自 [EGOI2021 railway](https://stats.egoi.org/media/task_description/2021_railway_en.pdf)。

description:
有一条连接苏黎世和卢加诺的长度为 $s$ 千米的铁路。铁路穿过了美丽的阿尔卑斯山，造就了旅程中壮观的景色。由于一些山口对铁路来说太高了，在线路上修剪了 $t$ 条隧道。第 $i$ 条隧道在距离苏黎世 $a_i$ 千米处开始，在 $b_i$ 千米处结束。（因此，第 $i$ 条隧道的长度为 $b_i-a_i$。）

你有一份两地之间的列车时刻表。从苏黎世到卢加诺有 $m$ 班列车，第 $j$ 班列车在 $c_j$ 分钟发车；从卢加诺到苏黎世有 $n$ 班列车，第 $k$ 班列车在 $d_k$ 分钟发车。所有运行中的列车，无论其方向和是否在隧道内，速度均恒为 $1$ 千米每分钟。路程中没有车站，列车也不会在信号灯处停车。因此，每班列车恰好花费 $s$ 分钟到达终点站。

与铁路的长度相比，列车的长度可以忽略不计，所以在本题中，**请假设每班列车是一个沿铁路移动的点**。

通常情况下，铁路有两条轨道：两个方向各有一条。唯一的例外是隧道。每个隧道只有一条轨道，可以从任何方向通行。

无论何时，只要两班反向运行的列车在隧道外相遇时，他们总是可以安全地经过对方。这包括列车正好在隧道的端点处相遇。但另一方面，如果两班反向运行的列车在隧道内严格$^\dagger$相遇，就会发生碰撞。

已知隧道信息和列车时刻表，请判断是否会发生碰撞。

$^\dagger$严格：原文如此（strictly）。

inputFormat:
第一行四个整数 $s,t,m,n$——铁路长度、隧道个数、从苏黎世和卢加诺发车的列车数量。

第二行 $t$ 个整数 $a_i$——每个隧道的起点。

第三行 $t$ 个整数 $b_i$——每个隧道的终点。

第四行 $m$ 个整数 $c_j$——从苏黎世发车的时间。

第五行 $n$ 个整数 $d_k$——从卢加诺发车的时间。

outputFormat: 一行，一个为 `YES` 或 `NO` 的字符串，代表是否会发生碰撞。

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

在长度为 $100$ 千米的铁路上，有两条隧道：距离苏黎世 $20\sim 30$ 千米处和 $50\sim 60$ 千米处。唯一一班从苏黎世发车的列车避开了所有从卢加诺发车的列车，如下：

- 与第一班车在距离苏黎世 $5$ 千米处相遇。
- 与第二班车在两个隧道间相遇。
- 与第三班车在距离卢加诺 $10$ 千米处相遇。
- 第四班车在该班车到站后很久才发车。

---

**样例 $2$ 解释**

两班列车在唯一的隧道中间相撞。

---

**样例 $3$ 解释**

两班列车在隧道靠近苏黎世的一端相遇。

---

**样例 $4$ 解释**

两班列车在隧道靠近卢加诺的一端相遇。

---

**数据范围**

对于全部数据，$1\le s\le 10^9$，$0\le t\le 10^5$，$0\le m,n\le 2\times 10^3$，$0\le a_i < s$，$0 < b_i\le s$，$a_i < b_i$，$b_i < a_{i+1}$，$0\le c_j,d_k\le 10^9$，$c_j < c_{j+1}$，$d_k < d_{k+1}$。

在前三个子任务中，保证 $s,c_j,d_k$ 均为偶数。

- 子任务一（$14$ 分）：$t,m,n\le 100$，$s\le 5\times 10^3$。
- 子任务二（$16$ 分）：$t\le 5\times 10^3$，$s\le 10^6$。
- 子任务三（$41$ 分）：无特殊限制。
- 子任务四（$29$ 分）：无特殊限制。另外，$s,c_j,d_k$ 不一定是偶数。


title: [EGOI2021] Double Move / 二选一游戏

background:
Day 2 Problem D.

题面译自 [EGOI2021 doublemove](https://stats.egoi.org/media/task_description/2021_doublemove_en.pdf)。

description:
爱丽丝和鲍勃在玩游戏，克莱尔在帮助他们。共有 $n$ 颗石子，编号从 $1$ 到 $n$。游戏分为三个阶段。

在第一阶段，爱丽丝和鲍勃轮流操作，爱丽丝先手。在每次操作中，玩家宣布他们要拿的石头，但不直接说出拿哪一个，而是给出两个选项。两个选项可能是相同的。也有可能说出已经说过的石头。第一阶段不取石子——玩家只是宣布他们在第二阶段的意图。第一阶段在宣布 $n+1$ 次后结束。

下面是 $n=3$ 的第一阶段的例子：

1. 爱丽丝：“我会取走 $1$ 或 $3$”
2. 鲍勃：“我会取走 $2$ 或 $2$”
3. 爱丽丝：“我会取走 $3$ 或 $2$”
4. 鲍勃：“我会取走 $1$ 或 $3$”

在第二阶段，对于 $n+1$ 次宣布的每一个，克莱尔用说“前者”或“后者”的方式从两个选项中选择一个。我们称克莱尔做出的 $n+1$ 次选择的序列为一个*方案*。可以发现，恰好有 $2\cdot 2\cdot 2\cdot\cdots\cdot 2=2^{n+1}$ 种可能的方案。（即使在一些宣布中，两个选项是完全相同的，我们认为“前者”“后者”选择不同为不同的方案。）

下面是克莱尔可能选择的 $16$ 种方案之一：

1. “前者”：爱丽丝将取 $1$。
2. “前者”：鲍勃将取 $2$。
3. “后者”：爱丽丝将取 $2$。
4. “前者”：鲍勃将取 $1$。

在第三阶段，爱丽丝和鲍勃根据克莱尔的选择开始取石子。第一个无法做出要求的操作的人——因为那个石子已经被取走——输掉游戏。注意到有 $n$ 个石子和 $n+1$ 次操作，一个玩家必然最终输掉游戏。

在上面的例子中，爱丽丝先取走 $1$。鲍勃接着取走 $2$。爱丽丝希望继续取走 $2$，但它已经被取走了，所以爱丽丝输掉了游戏，鲍勃因此获胜。

你已知整数 $n$，和第一阶段某一时刻的游戏状态：一个长度为 $k$ 的已经做出的宣布序列。这些宣布可以是完全随意的。

从此时开始，爱丽丝和鲍勃会以最优方式玩游戏，也就是说：

无论爱丽丝和鲍勃怎么玩，克莱尔都均匀随机地从 $2^{n+1}$ 种可能的方案中选择一个。爱丽丝和鲍勃知道这一点，因此当以最优方式玩游戏时，他们都尽力最小化他们输的方案数。

假设爱丽丝和鲍勃会按照上面描述的方式继续游戏。请分别求出两个人赢得游戏的方案数。

inputFormat:
第一行两个整数 $n,k$：石头数和已经做出的宣布数。

接下来 $k$ 行，每行按照顺序描述一次宣布。每行两个整数：两个石头的编号（在 $1\sim n$ 且不一定不同）。

注意到当 $k < n+1$ 时，下一个做出宣布的玩家由 $k$ 的奇偶性决定。

outputFormat:
一行，两个整数：爱丽丝赢的方案数、鲍勃赢的方案数，假设他们都按照上面描述的方式继续玩游戏。

注意到这两个整数的和应当为 $2^{n+1}$。

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

这个样例与【题目描述】中给出的相同。不需要做出更多的宣布了，因此我们只需要计算多少种方案会导致爱丽丝赢，多少种方案会导致鲍勃赢。爱丽丝赢当且仅当克莱尔在第一步选择了 $1$，且在第三步选择了 $3$。其他方案都会导致爱丽丝输。

---

**样例 $2$ 解释**

如果爱丽丝先宣布 $(1,1)$，鲍勃会宣布 $(2,2)$，无论爱丽丝接下来宣布什么，她都会输，因为克莱尔会在第一步选择 $1$，在第二步选择 $2$，第三步就没有剩下的石头给爱丽丝取了。然而，这不是爱丽丝第一步的最优方案：她应该首先宣布 $(1,2)$。然后，无论鲍勃和爱丽丝在后两步如何宣布，他们都会赢 $8$ 种方案中的 $4$ 种。

---

**数据范围**

对于全部数据，$1\le n\le 35$，$0\le k\le n+1$。

- 子任务一（$15$ 分）：$n\le 4$。
- 子任务二（$34$ 分）：$n\le 10$。
- 子任务三（$20$ 分）：$n\le 25$。
- 子任务四（$10$ 分）：$k=0$。
- 子任务五（$21$ 分）：无特殊限制。


title: [EGOI2022] SubsetMex / 子集 mex

background:
Day 1 Problem A.

题面译自 [EGOI2022 subsetmex](https://stats.egoi.org/media/task_description/2022_subsetmex_en.pdf)。

description:
一个*可重集*是元素可以重复出现的集合。例如，$\{0,0,1,2,2,5,5,5,8\}$ 是一个可重集。

给定一个可重集 $S$，值域为 $\N$，和一个目标自然数 $n$（$n\notin S$），你的目标是通过重复进行若干次以下的操作，使得 $n\in S$：

1. 选择一个（可以为空的）子集 $T\subseteq S$，其中 $T$ 不包含重复元素。
2. 在 $S$ 中删除 $T$ 中的元素。（重复元素只删除一个。）
3. 将 $\operatorname{mex}(T)$ 插入 $S$，其中 $\operatorname{mex}(T)$ 是最小的不在 $T$ 中的自然数。$\operatorname{mex}$ 意味着“最小不包含”的值。

你需要求出最少的能使得 $n\in S$ 的操作次数。

由于 $|S|$ 可能很大，它将以一个大小为 $n$ 的列表 $(f_0,\ldots f_{n-1})$ 的形式给出，其中 $f_i$ 代表 $i$ 在 $S$ 中的出现次数。（请回忆 $n$ 是我们想要插入 $S$ 的元素。）

inputFormat:
第一行一个整数 $t$——数据组数。之后每两行描述一组数据：

- 每组数据的第一行一个整数 $n$，表示要插入 $S$ 的元素。
- 每组数据的第二行 $n$ 个整数 $f_0,f_1,\ldots,f_{n-1}$，按照上述方式描述了集合 $S$。

outputFormat: 对于每组数据，输出一行一个整数，表示最少操作次数。


title: [EGOI2022] Lego Wall / 乐高墙

background:
Day 1 Problem B.

题面译自 [EGOI2022 legowall](https://stats.egoi.org/media/task_description/2022_legowall_en.pdf)。

description:
有两种乐高积木，大小分别为 $1\times 1\times 1$ 和 $2\times 1\times 1$（宽、高、长）。两种积木你都有无限个，每种积木的所有积木块没有任何区别。

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

一个积木块总是以正确的方向使用。四周的面是用同一种材料制成的，除了大小以外没有区别。

我们称两个积木块**锁死**，当且仅当一个块在另一个块的正上方。称两个积木块 $b_0$ 和 $b_k$ **连通**，当且仅当存在一个积木块序列 $b_0,b_1,\ldots,b_k$，使得任意相邻积木块 $b_{i-1}$ 和 $b_i$ 锁死。我们称一组积木块**连通**，当且仅当组内的每一对积木块都连通。

你希望搭建一个大小为 $w\times h\times 1$ 的积木墙，使得这面墙**没有洞**且**连通**。以下是 $4\times 3\times 1$ 的积木墙的例子：

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

另一方面，下面的 $4\times 3\times 1$ 的积木墙不连通，因此不被需要：

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

有多少种搭建**没有洞**且**连通**的积木墙的方案呢？答案可能很大，请输出它对 $10^9+7$ 取模的结果。

注意一个积木墙的镜像版本（旋转 $180^\circ$）和原来的版本被认为不同，除非他们看起来一模一样。

inputFormat: 一行，两个整数 $w,h$——积木墙的宽度和高度。

outputFormat: 一行，一个整数，表示方案数对 $10^9+7$ 取模的结果。

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

三种方案如图所示：

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

---

**数据范围**

对于全部数据，$1\le w\le 2.5\times 10^5$，$2\le h\le 2.5\times 10^5$，$w\times h\le 5\times 10^5$。

- 子任务一（$14$ 分）：$w=2$。
- 子任务二（$12$ 分）：$h=2$。
- 子任务三（$18$ 分）：$w,h\le 100$。
- 子任务四（$30$ 分）：$w\le 700$。
- 子任务五（$20$ 分）：$h\le 700$。
- 子任务六（$6$ 分）：无特殊限制。


title: [EGOI2022] Tourists / 乌托邦旅行团

background:
Day 1 Problem D.

题面译自 [EGOI2022 tourists](https://stats.egoi.org/media/task_description/2022_tourists_en.pdf)。

description:
乌托邦有 $n$ 个城市，编号从 $1$ 到 $n$，还有 $n-1$ 条双向公路连接这些城市。只需使用这些道路就可以在每对城市之间旅行。由于乌托邦非常美丽，目前有 $m$ 个游客，编号从 $1$ 到 $m$，正在访问这个国家。最初，第 $i$ 个游客正在访问城市 $a_i$。多个游客可能在同一个城市；也就是说，对于 $i\ne j$，可能有 $a_i=a_j$。

每个游客都有一个关于他们目前在乌托邦的游览有多有趣的评分，用一个数字表示，初始的评分均为 $0$。为了鼓励游客进一步游览，乌托邦政府希望通过在选定的城市组织活动来提高游客的评分。当一个活动在城市 $c$ 举行时，所有目前在那里的游客的评分将增加 $d$，其中 $d$ 是一个取决于活动类型的值。

一些游客计划在乌托邦逗留期间在各城市之间旅行。尽管从一个城市到另一个城市几乎不需要花时间（由于高效的乌托邦道路），但它仍然是一种不便，从而导致游客评分的降低。具体地，一个游客如果走了一条由 $k$ 条道路组成的路径，他们的评分会降低 $k$（游客总是会选择两个城市之间最短的路径）。

乌托邦政府要求你记录下游客们旅行时的评分。作为要求的一部分，你将得到 $q$ 个查询作为输入的一部分。你应该按照输入的顺序回答所有的询问。

inputFormat:
第一行三个整数 $n,m,q$——城市数、游客数、询问数。

第二行 $m$ 个整数 $a_1,a_2,\ldots,a_m$，其中 $a_i$ 为第 $i$ 个游客初始所在的城市。

接下来 $n-1$ 行，每行两个整数 $v,w$，表示 $v,w$ 之间有一条双向边。

接下来 $q$ 行，每行描述一个询问。每行的格式是以下三种之一：

- 首先一个字母 `t`，接着三个整数 $f_i,g_i,c_i$：所有编号在 $[f_i,g_i]$ 的游客都前往城市 $c_i$。
- 首先一个字母 `e`，接着两个整数 $c_i,d_i$：城市 $c_i$ 举办一个给评分增加 $d$ 的活动。
- 首先一个字母 `q`，接着一个整数 $v_i$：询问现在游客 $v_i$ 的评分。

保证输入中至少有一个操作 `q`。

outputFormat: 对于所有操作 `q` 输出一行一个整数。

hint:
**数据范围**

对于全部数据，$2\le n\le 2\times 10^5$，$1\le m,q\le 2\times 10^5$，$1\le a_i\le n$，保证输入构成一棵树。操作 `t` 中，$1\le f_i\le g_i\le m$，$1\le c_i\le n$。操作 `e` 中，$1\le c_i\le n$，$0\le d_i\le 10^9$。操作 `q` 中，$1\le v_i\le m$。

- 子任务一（$10$ 分）：$n,m,q\le 200$。
- 子任务二（$15$ 分）：$n,m,q\le 2\times 10^3$。
- 子任务三（$25$ 分）：$m,q\le 2\times 10^3$。
- 子任务四（$25$ 分）：不存在操作 `e`。
- 子任务五（$25$ 分）：无特殊限制。


title: [EGOI2022] Data Centers / 数据中心

description:
贡卡软件（贡软）是一家互联网公司，经营许多服务，在全球有 $n$ 个数据中心。每个数据中心都有一些可用的机器。出于安全和冗余的原因，每个服务都有一个或多个副本同时运行。每个副本在一个不同的数据中心运行，并需要一些机器来运行。一个服务的所有副本需要相同数量的机器。

当贡软计划推出一项需要 $c_i$ 个副本，每个副本在 $m$ 台机器上运行的新的服务 $i$ 时，它按照当前可用机器对数据中心降序排序，然后在前 $c_i$ 个数据中心各使用 $m$ 台机器。

请求出在推出 $s$ 个服务后，每个数据中心剩余的机器数量。

inputFormat:
第一行两个整数 $n,s$，表示数据中心数和服务数。

第二行 $n$ 个整数 $a_i$，表示每个数据中心初始可用机器数。

接下来 $s$ 行，每行两个整数 $m_i,c_i$，表示需要的机器数、副本数。

outputFormat: 一行，**降序排列**的 $n$ 个整数，表示每个数据中心剩余的机器数。


title: [EGOI2022] Superpiece / 超级棋子

background:
Day 2 Problem B.

题面译自 [EGOI2022 superpiece](https://stats.egoi.org/media/task_description/2022_superpiece_en.pdf)。

description:
你有一个无限大的棋盘。在本题中，棋盘是一个无限大的二维方格，每个方格用 $(r,c)$ 表示，分别代表行和列。目前棋盘上有唯一一个棋子，叫做**超级棋子**。你有你的超级棋子的合法移动列表，它是一个非空字符串，是 `QRBNKP` 的子集。在每个回合中，超级棋子可以作为给定的棋子之一移动。超级棋子初始位于 $(a,b)$，请求出到达 $(c,d)$ 的最少移动次数。

在本题中可能用到的国际象棋规则如下：

共有六种棋子：皇后、车、象、马、国王、兵。他们的移动方式如下：

- **皇后**（`Q`）可以移动到同行、同列、同对角线的方格。形式化地，对于任意整数 $k\ne 0$，皇后可以从 $(a,b)$ 移动到 $(a+k,b),(a,b+k),(a+k,b+k),(a+k,b-k)$。

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

- **车**（`R`）可以移动到同行、同列的方格。形式化地，对于任意整数 $k\ne 0$，车可以从 $(a,b)$ 移动到 $(a+k,b),(a,b+k)$。

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

- **象**（`B`）可以移动到同对角线的方格。形式化地，对于任意整数 $k\ne 0$，象可以从 $(a,b)$ 移动到 $(a+k,b+k),(a+k,b-k)$。

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

- **马**（`N`）可以移动一个 `L` 形，也就是：先在一个方向移动两格，再在与之垂直的方向移动一格。形式化地，马可以从 $(a,b)$ 移动到 $(a+1,b+2),(a+1,b-2),(a+2,b+1),(a+2,b-1),(a-2,b+1),(a-2,b-1),(a-1,b+2),(a-1,b-2)$。

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

- **国王**（`K`）可以移动到相邻的八个格子。形式化地，国王可以从 $(a,b)$ 移动到 $(a,b+1),(a,b-1),(a+1,b),(a-1,b),(a+1,b+1),(a+1,b-1),(a-1,b+1),(a-1,b-1)$。

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

- **兵**（`P`）可以向上移动一格。形式化地，兵可以从 $(a,b)$ 移动到 $(a+1,b)$。

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

请注意，你可能知道的关于国际象棋的其他规则并不适用于本题；请只使用上面列出的那些规则。

inputFormat:
第一行一个整数 $q$，表示数据组数。之后每两行描述一组数据：

- 每组数据的第一行一个非空字符串，是超级棋子的合法移动列表。这个字符串是 `QRBNKP` 的一个子集，所有字符**按相同顺序**出现。换句话说，它是 `QRBNKP` 的一个子序列。
- 每组数据的第二行四个整数 $a,b,c,d$——超级棋子的初始和目标位置。保证 $(a,b)\ne (c,d)$，也就是初始位置和目标位置不同。

outputFormat: 对于每组数据，输出一行一个整数 $m$，表示最少移动次数。如果不可能到达目标位置，输出 $-1$。

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

在第一组数据中，我们需要从 $(3,3)$ 走到 $(5,1)$，合法移动有马、国王、兵。有很多种需要两次移动的方案，例如：

- 兵走到 $(4,3)$，马走到 $(5,1)$。
- 马走到 $(5,2)$，国王走到 $(5,1)$。
- 国王走到 $(4,2)$，国王走到 $(5,1)$。

不存在少于两次移动的方案——我们需要象或者皇后才能做到。

在第二组数据中，我们需要从 $(2,6)$ 走到 $(5,3)$。同样地，最优方案需要两次移动。此时，每一步都必须是马，利用 $(4,5)$ 或 $(3,4)$ 作为中转站。

---

**样例 $2$ 解释**

在第一组数据中，我们需要从 $(2,8)$ 走到 $(3,6)$。只能按照象的方式走棋，这是不可能的。

在第二组数据中，我们需要从 $(2,8)$ 走到 $(5,5)$，只能按照象的方式走棋。可以在两次移动内实现，例如，利用 $(4,4)$ 作为中转站。

---

**样例 $3$ 解释**

在第一组数据中，我们需要从 $(3,3)$ 走到 $(4,5)$，只能按照皇后的方式走棋。可以利用 $(4,4)$ 为中转站两次移动到达。

在第二组数据中，我们需要从 $(4,1)$ 走到 $(1,4)$，只能按照皇后和车的方式走棋。可以一次移动到达。

---

**数据范围**

对于全部数据，$1\le q\le 10^3$，$-10^8\le a,b,c,d\le 10^8$。

- 子任务一（$12$ 分）：保证存在 `Q`，保证不存在 `N`。
- 子任务二（$9$ 分）：保证存在 `QN`。
- 子任务三（$13$ 分）：保证存在 `R`，保证不存在 `Q`。
- 子任务四（$8$ 分）：保证只存在 `B`。
- 子任务五（$6$ 分）：保证存在 `B`，保证不存在 `QR`。
- 子任务六（$31$ 分）：保证只存在 `N`。
- 子任务七（$8$ 分）：保证存在 `N`，保证不存在 `QRB`。
- 子任务八（$7$ 分）：保证存在 `K`，保证不存在 `QRBN`。
- 子任务九（$6$ 分）：保证只存在 `P`。

注意子任务**并不**按难度顺序排序。


title: [EGOI2022] Toy Design / 玩具设计

background:
Day 2 Problem C.

题面译自 [EGOI2022 toydesign](https://stats.egoi.org/media/task_description/2022_toydesign_en.pdf)。

description:
**本题是一道 Grader 交互题。**

你在一个设计玩具的公司工作。一个将被制作的玩具如下：有 $n$ 个大头针，编号从 $1$ 到 $n$，从盒子中伸出。几对大头针被铁丝在盒子中相连。（换句话说，大头针和铁丝组成了一个无向图，其中大头针是节点、铁丝是边。）铁丝无法从盒子外部看到，唯一获得关于他们的信息的方法是对大头针使用一个**检测器**：我们选择两个大头针 $i,j$（$i\ne j$），检测器会告诉你这两个大头针是否连通，包括直接和间接。（因此，检测器告诉你图中这两个大头针之间是否有一条路径。）

我们称一组连接方式为玩具的**设计方案**。

你正在使用一个专用的软件来查询和进行设计。软件工作方式如下：从某个称为“$0$ 号方案”的设计方案开始。他不会告诉你盒子内部的铁丝是什么样的。你需要重复进行以下的三步操作：

1. 选择一个设计方案 $a$ 和两个大头针 $i,j$（$i\ne j$）。
2. 软件告诉你对这两个大头针使用检测器的结果。换句话说，它告诉你在设计方案 $a$ 中 $i$ 与 $j$ 是否（直接或间接地）连通。
3. 同时，如果这两个大头针在设计方案 $a$ 中没有被直接或间接地连接，它会创建一个新的设计方案，包含设计方案 $a$ 中的所有铁丝，同时添加一个直接连接 $i,j$ 的铁丝。这个设计方案的编号为下一个可用的编号。（所以，第一个创建的设计方案是 $1$ 号方案，然后是 $2$ 号，以此类推。）请注意这不会修改设计方案 $a$，只会新建一个设计方案包含新的铁丝。

你的目标是使用这种操作获取尽可能多的 $0$ 号方案的信息。

请注意并不总是可能求出 $0$ 号方案的准确的铁丝连接方式，因为无法区分直接和间接的连接。例如，考虑如下的两种 $n=3$ 的设计方案：

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

检测器会认为两种方案中任意一对大头针都连通，所以我们无法利用上述软件区分它们。

你的目标是求出任何一种设计方案，使得它与 $0$ 号方案等价。两种设计方案**等价**当且仅当对于任意一对大头针，检测器在两种方案中都返回相同结果。

outputFormat:
**交互方式**

你需要实现一个函数：

```cpp
void ToyDesign(int n, int max_ops);
```

作用是给出一种与 $0$ 号方案*等价*的设计方案。你可以调用以下两个函数来实现这一点。你可以调用的第一个函数为：

```cpp
int Connected(int a, int i, int j);
```

其中 $1\le i,j\le n$，$i\ne j$，$a\ge 0$，且 $a$ 不能超过目前已有的设计方案数。如果在设计方案 $a$ 中，大头针 $i,j$ 是（直接或间接地）连通的，它的返回值是 $a$。否则，它的返回值是已有的设计方案数加一，就是包含 $a$ 的所有铁丝以及一根连接 $i,j$ 的铁丝的新的设计方案的编号。函数 `Connected` 可以被调用最多 `max_ops` 次。

当你的程序完成了需要的 `Connected` 调用，它应该描述一种等价于 $0$ 号方案的设计方案。为了描述一个方案，程序应当调用：

```cpp
void DescribeDesign(std::vector<std::pair<int, int>> result);
```

参数 `result` 是整数对的向量，描述大头针之间的直接铁丝连接。每对数描述一根铁丝，包含被连接的两个大头针的编号。在任意一对（无序的）大头针对之间必须只有至多一根铁丝，且不能有铁丝连接一个大头针和它自己。一旦调用这个函数，你的程序将被终止。

hint:
**样例交互过程**

|选手程序|Grader|解释|
|:-|:-|:-|
||`ToyDesign(4, 20)`|玩具中有 $4$ 个大头针。你需要在 $20$ 次 `Connected` 调用内，给出任何一种等价于 $0$ 号方案的设计方案。|
|`Connected(0, 1, 2)`|返回 $1$。|大头针 $1,2$ 在 $0$ 号方案中不直接或间接地连通。新的设计方案是 $1$ 号。|
|`Connected(1, 3, 2)`|返回 $2$。|大头针 $3,2$ 在 $1$ 号方案中不直接或间接地连通。新的设计方案是 $2$ 号。|
|`Connected(0, 3, 4)`|返回 $0$。|大头针 $3,4$ 在 $0$ 号方案中直接或间接地连通。没有新的设计方案。|
|`DescribeDesign({{3, 4}})`||描述一个只有一根铁丝的设计方案：连接大头针 $3,4$。|

---

**数据范围**

对于全部数据，$2\le n\le 200$。

- 子任务一（$10$ 分）：$n\le 200$，`max_ops` 为 $20000$。
- 子任务二（$20$ 分）：$n\le 8$，`max_ops` 为 $20$。
- 子任务三（$35$ 分）：$n\le 200$，`max_ops` 为 $2000$。
- 子任务四（$35$ 分）：$n\le 200$，`max_ops` 为 $1350$。


title: [语言月赛202305] 团体程序设计天梯赛

type: B

description:
七海参加了天梯赛。天梯赛的赛制较为独特，以下是天梯赛规则的节选。

>竞赛题目分 $3$ 个梯级：
>
> - 基础级设 $8$ 道题，其中 $5$ 分、$10$ 分、$15$ 分、$20$ 分的题各 $2$ 道，满分为 $100$ 分；
> - 进阶级设 $4$ 道题，每道题 $25$ 分，满分为 $100$ 分；
> - 登顶级设 $3$ 道题，每道题 $30$ 分，满分为 $90$ 分。

> 参赛队员的个人总分由其每题得分构成。但只有当该队员的基础题总分超过 $80$ 分时，其进阶部分的题目分数才被判为对其个人有效；其进阶题总分超过 $40$ 分时，其登顶部分的题目分数才被判为对其个人有效。

**请注意，这里的超过，指大于等于。**

现在，依照基础级-进阶级-登顶级的顺序给出某选手共 $15$ 题的分数，请你计算该名选手的有效得分。

inputFormat:
输入共三行。

输入的第一行为 $8$ 个整数，代表该选手基础级试题的得分。

输入的第二行为 $4$ 个整数，代表该选手进阶级试题的得分。

输入的第三行为 $3$ 个整数，代表该选手登顶级试题的得分。

outputFormat: 输出一行一个整数，代表该选手的有效得分。

hint: 对于 $100\%$ 的测试数据，输入的数据均为整数且符合题目实际情景。


title: [POI 2020/2021 R3] Kolekcjoner Bajtemonów 2

background:
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Kolekcjoner Bajtemonów 2](https://szkopul.edu.pl/problemset/problem/yI8VISW680r7ktJAPvA5QPkl/statement/)。

试机题。

description: 给你 $n$ 个数对，你要进行 $n$ 次二选一，这样你就有了 $n$ 个数，最大化这 $n$ 个数的 $\gcd$。

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

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

outputFormat: 一行一个数：最大的 $\gcd$。

hint:
对于所有数据，$1\leq n\leq 10^6$，$1\leq a_i\leq 5\times 10^5$，$1\leq b_i<2^{63}$。

对于 $42pts$ 的数据，$n\leq 5000$。


title: [语言月赛 202409] 转盘

description:
有一个转盘是这样的：上面写着一等奖到 $n$ 等奖，令 $s=1+2+\dots+n$，将这个转盘平均分成 $s$ 份，其中 $n$ 等奖占 $n$ 份，也就是说中 $n$ 等奖的概率为 $\frac{n}{s}$。$1$ 等奖是最好的奖，次好的奖是 $2$ 等奖，以此类推。

例如，当 $n=3$ 的时候，有 $\frac{1}{6}$ 的概率获得 $1$ 等奖，有 $\frac{2}{6}=\frac{1}{3}$ 的概率获得 $2$ 等奖，有 $\frac{3}{6}=\frac{1}{2}$ 的概率获得 $3$ 等奖。

迅风现在想知道获奖概率**不低于** $m\%$ 的奖中，最好的奖是几等奖。也就是找到一个**最小**的 $k$ ，使得获得 $k$ 等奖的概率 $\ge m\%$。如果没有中奖率不低于 $m\%$ 的奖，则输出 $-1$。

inputFormat: 共 $1$ 行，包含一个**整数** $n$ 和一个**浮点数** $m$，含义见题目描述。

outputFormat: 共 $1$ 行，包含一个数字 $k$，含义见题目描述。


title: [语言月赛202305] 线性代数初步

description:
我们定义一种名为「行列式」的新运算：

对于四个整数 $a, b, c, d$，我们定义 $\begin{vmatrix} a & b \\ c & d \end{vmatrix}$ 为 $a, b, c, d$ 的行列式，其等于 $a \times d - b \times c$。

现在，给定 $a, b, c, d$，请你帮忙计算 $\begin{vmatrix} a & b \\ c & d \end{vmatrix}$ 的值是多少。

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

outputFormat: 输出共一行一个整数，代表 $\begin{vmatrix} a & b \\ c & d \end{vmatrix}$ 的值。

hint:
### 样例 1 说明

$\begin{vmatrix} 3 & 7 \\ 4 & 9 \end{vmatrix} = 3 \times 9 - 4 \times 7 = -1$。

### 数据规模与约定

对于 $100\%$ 的数据，保证 $-10 ^ 9 \leq a, b, c, d \leq 10 ^ 9$。


title: [JOISC 2023 Day1] Two Currencies

description:
There are $N$ cities in JOI Kingdom, numbered from $1$ to $N$. There are $N - 1$ roads in JOI Kingdom, numbered from $1$ to $N - 1$. The road $i \ (1 \le i \le N - 1)$ connects the city $A_i$ and the city $B_i$ bi-directionally. It is possible to travel from any city to any other city by passing through some of the roads.

There are checkpoints on some of the roads in JOI Kingdom. There are $M$ checkpoints, numbered from $1$ to $M$. The checkpoint $j \ (1 \le j \le M)$ is located on the road $P_j$. In order to pass through it, you need to pay either one gold coin or $C_j$ silver coins.

There are $Q$ citizens in JOI Kingdom, numbered from $1$ to $Q$. The citizen $k \ (1 \le k \le Q)$ has $X_k$ gold coins and $Y_k$ silver coins, and wants to travel from the city $S_k$ to the city $T_k$. Since gold coins are valuable, all the citizens want to keep as many gold coins as possible.

Write a program which, given information of the cities, the roads, the checkpoints, and the citizens in JOI Kingdom, for each $k \ (1 \le k \le Q)$, determines whether it is possible for the citizen $k$ to travel from the city $S_k$ to the city $T_k$, and, if it is possible, calculates the maximum possible number of gold coins the citizen $k$ can keep.

outputFormat: Write $Q$ lines to the standard output. In the $k$-th line $(1 \le k \le Q)$, if the citizen $k$ can travel from the city $S_k$ to the city $T_k$, output the maximum possible number of gold coins the citizen $k$ can keep. Otherwise, output $-1$ in the $k$-th line.

translation:
#### 题目描述

在 JOI 王国中，有 $n$ 个城市，编号从 $1$ 到 $n$。JOI 王国有 $n−1$ 条双向道路，编号从 $1$ 到 $n−1$。第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$。

在 JOI 王国中，一些道路上放有检查站。有 $m$ 个检查站，编号从 $1$ 到 $m$。第 $j$ 个检查站位于道路 $p_j$ 上。通过该检查站需要支付 $1$ 枚金币或 $c_j$ 枚银币。

在 JOI 王国有 $q$ 名公民，编号从 $1$ 到 $q$。第 $k$ 名公民持有 $x_k$ 枚金币和 $y_k$ 枚银币，并希望从城市 $s_k$ 前往城市 $t_k$。由于金币具有较高的价值，所有公民都希望尽可能多地保留金币。

编写一个程序，给定 JOI 王国中的城市、道路、检查站和公民信息，对于每个 $k (1≤k≤q)$，判断公民 $k$ 是否能够从城市 $s_k$ 前往城市 $t_k$，并在此条件成立时计算公民 $k$ 所能保留的最多金币数。

#### 输入格式

从标准输入读入以下数据。
> $N \ M \ Q$
>
> $A_1 \ B_1$
>
> $A_2 \ B_2$
>
> $\vdots$
>
> $A_{N - 1} \ B_{N - 1}$
>
> $P_1 \ C_1$
>
> $P_2 \ C_2$
>
> $\vdots$
>
> $P_M \ C_M$
>
> $S_1 \ T_1 \ X_1 \ Y_1$
>
> $S_2 \ T_2 \ X_2 \ Y_2$
>
> $\vdots$
>
> $S_Q \ T_Q \ X_Q \ Y_Q$
#### 输出格式

向标准输出打印 $q$ 行。在第 $k$ 行 $(1≤k≤q)$ 中，如果公民 $k$ 可以从城市 $s_k$ 前往城市 $t_k$，请输出公民 $k$ 可以保留的最多金币数。否则，在第 $k$ 行中输出 $−1$。

Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

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

The citizen $1$ can travel from the city $3$ to the city $4$ as follows. After the travel, the citizen $1$ keeps one gold coin.

1.  The citizen $1$ travels from the city $3$ to the city $1$ by passing through the road $2$. There are the checkpoints $1, 2$ on the road $2$. The citizen $1$ pays one gold coin at the checkpoint $1$ and passes through it, and $4$ silver coins at the checkpoint $2$ and passes through it, respectively. After that, the citizen $1$ keeps one gold coin and $7$ silver coins.
2. The citizen $1$ travels from the city $1$ to the city $2$ by passing through the road $1$. Since there is no checkpoint on the road $1$, the citizen $1$ keeps one gold coin and $7$ silver coins.
3. The citizen $1$ travels from the city $2$ to the city $4$ by passing through the road $3$. There is the checkpoint $3$ on the road $3$. The citizen $1$ pays $5$ silver coins at the checkpoint $3$ and passes through it. After that, the citizen $1$ keeps one gold coin and $2$ silver coins.

Since it is impossible for the citizen $1$ to travel by finally keeping more than or equal to $2$ gold coins, output $1$ in the first line.

The citizen $2$ can travel from the city $5$ to the city $3$ as follows. After the travel, the citizen $2$ keeps two gold coins.

1. The citizen $2$ travels from the city $5$ to the city $2$ by passing through the road $4$. There is the checkpoint $4$ on the road $4$. The citizen $2$ pays one gold coin at the checkpoint $4$ and passes through it. After that, the citizen $2$ keeps $3$ gold coins and $5$ silver coins.
2. The citizen $2$ travels from the city $2$ to the city $1$ by passing through the road $1$. Since there is no checkpoint on the road $1$, the citizen $2$ keeps $3$ gold coins and $5$ silver coins.
3. The citizen $2$ travels from the city $1$ to the city $3$ by passing through the road $2$. On the road $2$, there are the checkpoints $1, 2$. The citizen $2$ pays one gold coin at the checkpoint $1$ and passes through it, and $4$ silver coins at the checkpoint $2$ and passes through it, respectively. After that, the citizen $2$ keeps $2$ gold coins and one silver coin.

Since it is impossible for the citizen $2$ to travel by finally keeping more than or equal to $3$ gold coins, output $2$ in the second line.

Since it is impossible for the citizen $3$ to travel from the city $2$ to the city $3$, output $-1$ in the third line.

该样例满足子任务 $1, 4$ 的限制。

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

该样例满足子任务 $1, 2, 4$ 的限制。

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

该样例满足子任务 $1, 3, 4$ 的限制。

**【样例解释 #4】**

该样例满足子任务 $1, 4$ 的限制。

**【数据范围】**

对于所有测试数据，满足 $2 \le N \le 10 ^ 5$，$1 \le M, Q \le 10 ^ 5$，$1 \le A_i, B_i \le N$，$1 \le P_j \le N - 1$，$1 \le C_j \le 10 ^ 9$，$1 \le S_k, T_k \le N$，$S_k \ne T_k$，$0 \le X_k \le 10 ^ 9$，$0 \le Y_k \le 10 ^ {18}$，保证给定的道路使所有城市连通，保证所有输入均为整数。

|子任务编号|分值|限制|
|:-:|:-:|:-:|
|$1$|$10$|$N, M, Q \le 2000$|
|$2$|$28$|$C_1 = C_2 = \dots = C_M$|
|$3$|$30$|$A_i = i$，$B_i = i + 1$|
|$4$|$32$|无|


title: [NAPC-#1] rStage5 - Hard Conveyors

background:
**本题新增两组 hack 数据。**

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

更硬，所以可能就更脆，所以更容易被击破（确信）。

您只花了两个小时就秒掉了正城 s1~s10，来秒逆城了。

description:
**本题与 Stage5 的区别是合法路径定义不同**（简要题意中加粗部分不同）。~~（其实还有：样例不同，数据不同，部分分不同。）~~

### 【简要题意】

给定一棵 $n$ 个节点的无根树以及树上的 $k$ 个关键节点，边有边权（即边的长度）。$q$ 次询问，每次给出 $s,t$，问从 $s$ 到 $t$ 且经过**至少一个**关键节点的路径的最短长度。

inputFormat:
第一行三个正整数 $n, q, k$，表示树的节点个数，询问次数和关键节点个数。

接下来 $n-1$ 行，每行三个正整数 $u, v, w$，表示树中存在边 $(u, v)$，边权为 $w$。保证输入构成一棵树。

接下来一行 $k$ 个两两不同的正整数，表示关键节点的编号。

接下来 $q$ 行，每行两个正整数 $s, t$，表示一次询问。

outputFormat:
对于每次询问输出一行一个非负整数，表示此次询问的最短合法路径长度。

注意，合法路径可以不经过任何边，此时路径长为 $0$。

hint:
### 【数据范围】

upd at `2023-6-25`：新增了两组 hack 数据，将其置于 $\text{Sub}\textsf6$ 中，不记分数。

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

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c|c}
\textbf{Subtask} & \text{测试点编号} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1&1\sim2 & k=n & 5 \r
\textsf2&16\sim20 &k=1,n\leqslant10^3,q\leqslant10^3 & 15 \r
\textsf3&21\sim25 & n\leqslant10^3,q\leqslant10^3 & 15 \r
\textsf4&3\sim7 & q=1 & 15 \r
\textsf5&8\sim15 & - & 50 \r
\textsf6&26\sim27 & - & 0 \r
\end{array}
$$

对于 $100\%$ 的数据，$1\leqslant n\leqslant 10^5$，$1\leqslant q\leqslant 10^5$，$1\leqslant k\leqslant n$，$1\leqslant w\leqslant 10^4$，$1\leqslant u,v,s,t\leqslant n$。

### 【样例解释 #1】
![](https://cdn.luogu.com.cn/upload/image_hosting/3hvr33bz.png)

图中加粗节点表示关键点。

对于每组询问，以下为一种最优路径（最优路径可能有多条）：
1. $2\to1\to3$。
2. $2\to1$。
3. $7\to1\to2\to1$。
4. $4\to3\to5$。
5. $6\to2\to6$。
6. $2$（合法路径可以不经过任何边，此时路径长为 $0$）。


title: [JOISC 2023 Day1] Festivals in JOI Kingdom 2

description:
In JOI Kingdom, a national festival is held once a year. During the period of the festival, there are $N$ events in total. The schedule for each event is already fixed. The schedule of the $N$ events are described by sequences $a, b$ of length $N$ satisfying the following conditions.

- Every integer between $1$ and $2N$, inclusive, appears as an element of $a$ or $b$.
- $a_i < b_i \ (1 \le i \le N)$.
- $a_i < a_{i + 1} \ (1 \le i \le N - 1)$.

The $i$-th event will start at $a_i$ minutes after the beginning of the festival, and end at $b_i$ minutes after the beginning of the festival.

Participants of the festival may choose any events in which they will participate. However, it is not allowed to participate in two events whose schedules overlap. (Note that the starting times and the ending times of the events are different from each other.)

JOI-kun wants to participate in as many events as possible. Until last year, he chose the events in which he participated by the following procedures on a computer.

> For $i = 1, 2, \dots, N$，the following are done in this order.
> > If the schedule of the $i$-th event does not overlap the schedules of the other events in which he already chose to participate, he will participate in the $i$-th event. Otherwise, he will not participate in the $i$-th event.

However, after studying computer science, JOI-kun noticed that the above algorithm does not necessarily maximize the number of events in which JOI-kun will participate. From this year, JOI-kun will use an improved algorithm. Using the improved algorithm, JOI-kun will be able to maximize the number of events in which JOI-kun will participate.

JOI-kun wants to know the number of cases where the improved algorithm produces a larger number of events.

Write a program which, given the integer $N$ and a large prime number $P$, calculates the number of pairs of sequences $a, b$ describing the schedules of the $N$ events for which the improved algorithm produces a larger number of events. Since the answer can be very large, your program should output the remainder of the answer when divided by $P$.

inputFormat:
Read the following data from the standard input.

> $N \ P$

outputFormat: Write one line to the standard output. The output should contain the remainder of the answer, the number of pairs of sequences $a, b$ describing the schedules of the $N$ events for which the improved algorithm produces a larger number of events, when divided by $P$.

translation:
对于以下问题：
> 给定长度为 $n$ 的序列 $a$、$b$，满足以下条件：
> - 在序列 $a$ 与序列 $b$ 中，$1$ 到 $2n$ 的整数各出现恰好一次；
> - 对于 $1\le i\le n$，$a_i<b_i$；
> - 对于 $1\le i<n$，$a_i<a_{i+1}$。
>
> 求：最多能在 $[a_i,b_i]$ 中选出多少个两两不交的区间。

考虑以下算法：
> 从 $1$ 到 $n$ 枚举 $i$，若 $[a_i,b_i]$ 与所有已经选择的区间都不交，则选择该区间。最后输出选择的区间数。

给定 $n$，求：有多少个满足条件的序列对 $(a,b)$，使得以上算法无法求出正确的结果。答案对 $p$ 取模。

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

For example, consider the case where $a = (1, 2, 4)$ and $b = (6, 3, 5)$. If JOI-kun uses the algorithm used until last year, he will participate in the first event only. On the other hand, if he uses a correct algorithm to maximize the number of events, he will participate in the second event and the third event. Thus, he will participate in two events. In this case, the improved algorithm produces a larger number of events.

The following are the pair of sequences $a, b$ for which the improved algorithm produces a larger number of events.

- $a = (1, 2, 4), b = (6, 3, 5)$
- $a = (1, 2, 4), b = (5, 3, 6)$

Therefore, output $2$, which is the remainder of $2$ when divided by $100000007$.

该样例满足所有子任务的限制。

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

There are $28$ pairs of sequences $a, b$ satisfying the condition. Therefore, output $28$, which is the remainder of $28$ when divided by $100000007$.

该样例满足所有子任务的限制。

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

There are $5295044602247148$ pairs of sequences $a, b$ satisfying the condition. Therefore, output $935834920$, which is the remainder of $935834920$ when divided by $999999937$.

该样例满足子任务 $3 \sim 6$ 的限制。

**【数据范围】**

对于所有测试数据，满足 $1 \le N \le 2 \times 10 ^ 4$，$10 ^ 8 < P < 10 ^ 9$，保证 $P$ 是质数，保证所有输入均为整数。

|子任务编号|分值|$N \le$|
|:-:|:-:|:-:|
|$1$|$5$|$5$|
|$2$|$5$|$8$|
|$3$|$27$|$30$|
|$4$|$14$|$300$|
|$5$|$36$|$3000$|
|$6$|$13$|$2 \times 10 ^ 4$|


title: [JOISC 2023 Day1] Passport

description:
Passport is a certificate which is used worldwide when a traveler enters foreign countries.

In a planet, there are $N$ countries, numbered from $1$ to $N$. Each country issues a passport. When a traveler has a passport issued by the country $i \ (1 \le i \le N)$, the traveler can enter the countries $L_i, L_{i + 1}, \dots, R_i$. **Here, it is guaranteed that the traveler can enter the country where the passport was issued. Namely, $L_i \le i \le R_i$ is satisfied.**

You have a friend who likes traveling. Although he dreams of traveling around the world, he does not have a passport in the beginning. Thus, he plans to visit all of the $N$ countries by repeating the following two actions.

- He gets a passport issued by the country where he is currently staying.
- He moves to a country where he can enter using a passport he currently has.

When you hear about his plan, you are wondering whether it is possible to realize the plan, and, if it is possible, what is the minimum number of passports he needs to get. Since you do not know where he lives, you consider $Q$ possible countries $X_1, X_2, \dots, X_Q$ where he lives.

Write a program which, given information of the passports and the possibilities of his living place, for each possibility, determines whether it is possible for him to visit all of the $N$ countries, and, if it is possible, calculates the minimum number of passports he needs to get.

inputFormat:
Read the following data from the standard input.

> $N$
>
> $L_1 \ R_1$
>
> $L_2 \ R_2$
>
> $\vdots$
>
> $L_N \ R_N$
>
> $Q$
>
> $X_1$
>
> $X_2$
>
> $\vdots$
>
> $X_Q$

outputFormat: Write $Q$ lines to the standard output. The $j$-th line $(1 \le j \le Q)$ corresponds to the case where your friend lives in the country $X_j$. If it is possible for him to visit all of the $N$ countries, this line should contain the minimum number of passports he needs to get. Otherwise, this line should contain $-1$.

translation:
## 题目描述

护照是旅行家进入他国时使用的证件。

在一个星球上有 $N$ 个国家，从 $1$ 到 $N$ 编号。每个国家都签发一种护照。当旅行家获得由国家$i \ (1 \le i \le N)$ 签发的护照后，他能够进入国家 $L_i, L_{i + 1}, \dots, R_i$。**这里保证旅行家能够进入其签证的签发国。形式上地说, $L_i \le i \le R_i$ 必然成立。**

你有一个爱旅行的朋友。即使他奢望能环游世界，但他最初一种护照也没有。因此，他想通过一下重复以下两项行为来环游这 $N$ 个国家。

- 获得他当前所在国家签发的护照。
- 用他现有的护照进入某个国家。

知道他的计划后，你想知道这个计划的是否可行，和如果可行的话，他最少需要的护照数量。因为你并不清楚他现在身处何国，所以你预测了 $Q$ 个他可能正居住在那的国家 $X_1, X_2, \dots, X_Q$。

现在给定各国护照的信息 $L_i, R_i$ 和他可能居住的 $Q$ 个国家，您需要写一个程序，对于每一个可能居住的国家，判断他是否可能环游这 $N$ 个国家，如果可能的话，计算出他需要的最少护照种数。

## 输入格式

从标准输入读入：

> $N$
>
> $L_1 \ R_1$
>
> $L_2 \ R_2$
>
> $\vdots$
>
> $L_N \ R_N$
>
> $Q$
>
> $X_1$
>
> $X_2$
>
> $\vdots$
>
> $X_Q$

## 输出格式

输出 $Q$ 行至标准输出，第 $j \ (1 \le j \le Q)$ 行一个整数代表若你的朋友位于国家 $X_j$ 的答案。若他能环游这 $N$ 个国家，则输出他需要的最少护照种数，否则输出 $-1$。

## 提示

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

假设你的朋友居住在国家 $X_1 = 1$，一种可行的方式如下，最后他获得了 $2$ 种护照：

1. 获得国家 $1$ 签发的护照。
2. 用国家 $1$ 签发的护照去国家 $2$ 旅行。
3. 获得国家 $2$ 签发的护照。
4. 用国家 $1$ 签发的护照去国家 $3$ 旅行。
5. 用国家 $2$ 签发的护照去国家 $4$ 旅行。

可以证明不存在使用护照种数更小的方案，故输出 $2$。

该样例满足所有子任务的限制。

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

假设你的朋友居住在国家 $X_1 = 3$。一种可行的方式如下，最后他获得了 $4$ 种护照：

1. 获得国家 $3$ 签发的护照。
2. 用国家 $3$ 签发的护照去国家 $2$ 旅行。
3. 获得国家 $2$ 签发的护照。
4. 用国家 $2$ 签发的护照去国家 $4$ 旅行。
5. 获得国家 $4$ 签发的护照。
6. 用国家 $4$ 签发的护照去国家 $5$ 旅行。
7. 获得国家 $5$ 签发的护照。
8. 用国家 $5$ 签发的护照去国家 $1$ 旅行。

可以证明不存在使用护照种数更小的方案，故输出 $4$。

该样例满足子任务 $2 \sim 5$ 的限制。

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

例如，如果你的朋友居住在 $X_3 = 3$，一种可行的方案书获得国家 $3$ 签发的护照，并用它来依次去国家 $1, 2, 4, 5$ 旅行。故第三行输出 $3$。

但如果你的朋友居住在国家 $X_5 = 5$，即使他获得了国家 $5$ 签发的护照，他也不可能进入任何其他国家，因此，他无法实现自己的旅行计划。故第五行输出 $-1$。

该样例满足子任务 $4 \sim 5$ 的限制。

**【样例解释 #4】**

该样例满足子任务 $4 \sim 5$ 的限制。

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

Assume that your friend lives in the country $X_1 = 1$. It is possible for him to visit all of the $4$ countries if he acts in the following way. Then, he gets $2$ passports.

1. He gets a passport issued by the country $1$.
2. Using the passport issued by the country $1$, he moves to the country $2$.
3. He gets a passport issued by the country $2$.
4. Using the passport issued by the country $1$, he moves to the country $3$.
5. Using the passport issued by the country $2$, he moves to the country $44.

Since it is impossible to realize the plan if he gets less than or equal to $1$ passport, output $2$.

该样例满足所有子任务的限制。

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

Assume that your friend lives in the country $X_1 = 3$. It is possible for him to visit all of the $5$ countries if he acts in the following way. Then, he gets $4$ passports.
1. He gets a passport issued by the country $3$.
2. Using the passport issued by the country $3$, he moves to the country $2$.
3. He gets a passport issued by the country $2$.
4. Using the passport issued by the country $2$, he moves to the country $4$.
5. He gets a passport issued by the country $4$.
6. Using the passport issued by the country $4$, he moves to the country $5$.
7. He gets a passport issued by the country $5$.
8. Using the passport issued by the country $5$, he moves to the country $1$.

Since it is impossible to realize the plan if he gets less than or equal to $3$ passports, output $4$.

该样例满足子任务 $2 \sim 5$ 的限制。

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

For example, if your friend lives in the country $X_3 = 3$, it is possible to realize the plan if he gets a passport issued by the country $3$, and uses it to visit the countries $1, 2, 4, 5$ in this order. Therefore, output $1$ in the third line.

On the other hand, if your friend lives in the country $X_5 = 5$, it is impossible for him to enter other countries even if he gets a passport issued by the country $5$. Thus, he cannot realize the plan. Therefore, output $-1$ in the fifth line.

该样例满足子任务 $4 \sim 5$ 的限制。

**【样例解释 #4】**

该样例满足子任务 $4 \sim 5$ 的限制。

**【数据范围】**

对于所有测试数据，满足 $2 \le N \le 2 \times 10 ^ 5$，$1 \le L_i \le i \le R_i \le N$，$1 \le Q \le N$，$1 \le X_1 < X_2 < \dots < X_Q \le N$，保证所有输入均为整数。

|子任务编号|分值|限制|
|:-:|:-:|:-:|
|$1$|$6$|$Q = 1$，$X_1 = 1$|
|$2$|$16$|$N \le 300$，$Q = 1$|
|$3$|$24$|$N \le 2500$，$Q = 1$|
|$4$|$8$|$N \le 2500$|
|$5$|$46$|无|


title: [KMOI R1] 集合 First

description:
有一个集合 $A=\{1,2,3\dots,n\}$。

定义交替和 $G(B)$ 如下：

- 把集合 $B$ 中的元素从大到小排序，得到 $B=\{b_1,b_2\dots,b_{cnt}\}$（$cnt$ 为集合元素个数）。则 $G(B)=\sum\limits_{i=1}^{cnt}\Big((-1)^{i+1}\times b_i\Big)$。

例如 $G(\{1,2,4,6,9\})=9-6+4-2+1=6$。

特别地，$G(\empty)=0$。

现在，给定集合 $A=\{1,2,3,\dots,n\}$，小谢想知道对于 $A$ 的**任意子集 $P$**，求出 $G(P)$ 的总和。

由于小谢太菜了，所以请你帮帮忙，**答案对 $911451407$ 取模。**

inputFormat: 一个正整数 $n$，表示给定的集合 $A=\{1,2,3,\dots,n\}$。

outputFormat:
一个正整数 $ans$，表示对于 $A$ 的**任意子集 $P$**，$G(P)$ 的总和。

**答案对 $911451407$ 取模。**


title: [JOISC 2023 Day2] Belt Conveyor（交互，无法评测）

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

**由于技术原因，本题暂不支持提交与评测。**

**如果您能够提供官方数据对应的 grader，请与 @[_RSY_](/user/46197) 联系。**

description:
**【题目描述】**

In the factory of JOI Co., Ltd., there are $N$ tables, numbered from $0$ to $N - 1$. In the factory, there are $N - 1$ belt conveyors, numbered from $0$ to $N - 2$. The belt conveyor $i \ (0 \le i \le N - 2)$ connects the table $A_i$ and the table $B_i$. It transports products from one table to the other table. However, we cannot see the direction of transportation. If we ignore the directions of the belt conveyors, every pair of tables is connected by a number of belt conveyors.

IOI-kun is the director of the factory. Since he forgets the direction of transportation of every belt conveyor, he will perform the following sequential operations several times.

1. He chooses a number of belt conveyors, and reverses the directions of transportation of the chosen belt conveyors.
2. He chooses a number of tables, and puts a product on each chosen table.
3. For every table where a product is put, one of the following happens simultaneously.
    - If there is no belt conveyor transporting products from it, nothing happens.
    - If there are belt conveyors transporting products from it, the product on the table is transported by one of such belt conveyors. The product stops at the destination of the belt conveyor. The product will not move anymore.
4. IOI-kun confirms whether there are one or more products on each table. If there are products on a table, IOI-kun takes all of them.
5. For every belt conveyor whose direction is reversed in the operation 1., IOI-kun reverts its direction. Its direction becomes the original direction.

IOI-kun wants to specify the original direction of every belt conveyor by performing the above sequential operations at most $30$ times.

Write a program which, given information of the tables connected by the belt conveyors, implements IOI-kun’s strategy to specify the original direction of every belt conveyor by performing the above sequential operations at most $30$ times.

**【实现细节】**

You need to submit one file.

The file is `conveyor.cpp`. It should implement the following function. The program should include `conveyor.h` using the preprocessing directive `#include`.

In `conveyor.cpp`, the following function should be implemented.

```cpp
void Solve(int N, std::vector<int> A, std::vector<int> B)
```

This function is called only once for each test case.

- The parameter `N` is the number of tables $N$.
- The parameters `A，B` are arrays of length $N - 1$, describing the tables connected by the belt conveyors.

Your program can call the following function.

```cpp
std::vector<int> Query(std::vector<int> x, std::vector<int> y)
```

Using this function, IOI-kun performs the operations in the factory.

- The parameter `x` is an array of length $N - 1$. For $0 \le \texttt{i} \le N - 2$, IOI-kun reverses the direction of the belt conveyor `i` if `x[i] = 1`, and does not reverses the direction of the belt conveyor `i` if `x[i] = 0`.
- The parameter `y` is an array of length $$. For $0 \le \texttt{j} \le N - 1$, IOI-kun puts a product on the table `j` if `y[j] = 1`, and does not put a product on the table `j` if `y[j] = 0`.
- Let `z` be the return value of this function. It is an array of length $N$. For $0 \le \texttt{j} \le N - 1$, there are one or more products on the table `j` if `z[j] = 1`, and there is no product on the table `j` if `z[j] = 0`.
- The length of the array `x` should be equal to $N - 1$. If this condition is not satisfied, your program is judged as `Wrong Answer [1]`.
- Every element of the array `x` should be `0` or `1`. If this condition is not satisfied, your program is judged as `Wrong Answer [2]`.
- The length of the array `y` should be equal to $N$. If this condition is not satisfied, your program is judged as `Wrong Answer [3]`.
- Every element of the array `y` should be `0` or `1`. If this condition is not satisfied, your program is judged as `Wrong Answer [4]`.
- The function Query should not be called more than $30$ times. If it is called more than $30$ times, your program is judged as `Wrong Answer [5]`.

```cpp
void Answer(std::vector<int> a)
```

Using this function, IOI-kun reports the original direction of each belt conveyor.

- The parameter `a` is an array of length $N - 1$. For $0 \le \texttt{i} \le N - 2$, the belt conveyor `i` transports products from $A_i$ to $B_i$ if `a[i] = 0`, and it transports products from $B_i$ to $A_i$ if `a[i] = 1`.
- The length of the array `a` should be equal to $N - 1$. If this condition is not satisfied, your program is judged as `Wrong Answer [6]`.
- Every element of the array `a` should be `0` or `1`. If this condition is not satisfied, your program is judged as `Wrong Answer [7]`.
- If IOI-kun reports wrong direction of a belt conveyor, your program is judged as `Wrong Answer [8]`.
- The function `Answer` should be called exactly once. If the function `Answer` is called more than once, your program is judged as `Wrong Answer [9]`. When the function `Solve` terminates, if the function `Answer` is not called, your program is judged as `Wrong Answer [10]`.

#### Important Notices

- Your program can implement other functions for internal use, or use global variables.
- Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

**【评测方式】**

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file `grader.cpp`. In order to test your program, put `grader.cpp`, `conveyor.cpp`, `conveyor.h` in the same directory, and run the following command to compile your programs. Instead, you may run `compile.sh` contained in the archive file.

```plain
g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp
```

When the compilation succeeds, the executable file `grader` is generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

inputFormat:
The sample grader reads the following data from the standard input.

> $N$
>
> $A_0 \ A_1 \ \cdots \ A_{N - 2}$
>
> $B_0 \ B_1 \ \cdots \ B_{N - 2}$
>
> $C_0 \ C_1 \ \cdots \ C_{N - 2}$

For $0 \le i \le N - 2$, we have $C_i = 0$ if the belt conveyor $i$ transports products from the table $A_i$ to the table $B_i$. Otherwise, we have $C_i = 1$.

outputFormat:
The sample grader outputs the following information to the standard output (quotes for clarity).

- If your program is judged as correct, it reports the number of function calls to `Query` as `Accepted: 22`.
- If your program is judged as any type of Wrong Answer, the sample grader writes its type as `Wrong Answer [4]`.

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.

In sample grader, among the belt conveyors transporting products from the table where a product is put, the belt conveyor transporting the product is chosen uniformly and randomly determined by pseudorandom numbers whose results do not change for different executions. In order to change the seed of pseudorandom numbers, run the sample grader with the first integer argument as follows.

```plain
./grader 2023
```

translation:
### 题目描述

在 JOI 有限公司的工厂里，有 $N$ 张桌子，从 $0$ 到 $N-1$ 编号。工厂里有 $N-1$ 条皮带输送机，从 $0$ 到 $N-2$ 编号。第 $i$ 条 $(0 \le i \le N-2)$ 皮带输送机连接桌子 $A_i$ 和桌子 $B_i$。它将产品从一张桌子运输到另一张桌子。然而，我们**不知道**运输的方向。

IOI-kun 是工厂的经理。由于他忘记了每条皮带输送机的运输方向，他将多次按照以下顺序执行操作。
1. 选择几条输送带，并反转所选输送带的运输方向。
2. 选择几张桌子，并在每张选定的桌子上放一件商品。
3. 每当把产品放在一张桌子上时，就会发生以下情况之一。

- 如果没有输送带将产品从该桌子运走，则不会发生任何事情。
- 如果有输送带将产品从该桌子运走，则桌子上的产品将由其中一条输送带运输。产品将在输送带的目的地停止，并且产品将不再移动。
4. IOI-kun 会确认每张桌子上是否有产品。如果有产品在桌子上，IOI-kun 会把它们全部拿走。
5. 对于每个在操作 1 中改变了方向的皮带输送机，IOI-kun 都会将其方向恢复到原来的方向。IOI-kun 希望通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

请编写一个程序，根据皮带输送机之间的连接表，实现 IOI-kun 的策略，以通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

### 实现细节

你需要实现一份 C++ 程序，提交时**不需要**包含 `conveyor.h`。

你应该实现以下函数。

```cpp
void Solve(int N, std::vector<int> A, std::vector<int> B)
```

该函数仅在每个测试用例中被调用一次：

- 参数 $N$：传送带连接的桌子的数量。
- 参数 $A$ 和 $B$ 是长度为 $N - 1$ 的数组，描述由皮带输送机连接的桌子。

您的程序可以调用以下函数：

```cpp
std::vector<int> Query(std::vector<int> x, std::vector<int> y)
```

使用这个函数，IOI-kun 在工厂中执行操作。

- 参数 $x$ 是一个长度为 $N - 1$ 的数组。对于 $0\le i\le N - 2$，如果 $x_i = 1$，IOI-kun 将反转第 $i$ 个传送带的方向，否则不反转该传送带的方向。
- 参数 $y$ 是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $y_j = 1$，IOI-kun 将在第 $j$ 个桌子上放置一个产品，否则不会在该桌子上放置产品。
- 设 $z$ 是该函数的返回值。它是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $z_j = 1$，则第 $j$ 个桌子上有产品，如果 $z_j = 0$，则第 $j$ 个桌子上没有产品。
- 数组 $x$ 的长度应等于 $N - 1$。如果不满足此条件，您的程序将被评为 `Wrong Answer[1]`。
- 数组 $x$ 中的每个元素都应为 $0$ 或 $1$。如果不满足此条件，您的程序将被评为 `Wrong Answer[2]`。
- 数组 $y$ 的长度应等于 $N$。如果不满足此条件，您的程序将被评为 `Wrong Answer[3]`。
- 数组 $y$ 中的每个元素都应为 $0$ 或 $1$。如果不满足上述条件，您的程序将被评为 `Wrong Answer[4]`。
- 函数 Query 最多只能被调用 $30$ 次。如果被调用次数超过 $30$ 次，您的程序将被评为 `Wrong Answer[5]`。

```cpp
void Answer(std::vector<int> a)
```

使用这个函数，IOI-kun 会报告每个输送带的原始方向。

- 参数 $a$ 是一个长度为 $N - 1$ 的数组。对于 $0 \le i \le N - 2$，如果 $a_i = 0$，则输送带 $i$ 将产品从 $A_i$ 运输到 $B_i$，如果 $a_i = 1$，则将产品从 $B_i$ 运输到 $A_i$。
- 数组 $a$ 的长度必须等于 $N - 1$。如果条件不满足，您的程序将被评为 `Wrong Answer[6]`。
- 数组 $a$ 中的每个元素都必须为 $0$ 或 $1$。如果条件不满足，您的程序将被评为 `Wrong Answer[7]`。
- 如果 IOI-kun 报告了输送带的错误方向，您的程序将被评为 `Wrong Answer[8]`。
- 函数 `Answer` 必须被**恰好调用一次**。如果函数 `Answer` 被调用多次，您的程序将被评为 `Wrong Answer[9]`。当函数 `Solve` 结束时，如果函数 `Answer` 尚未被调用，您的程序将被评为 `Wrong Answer[10]`。

### 输入格式
样例评测库将读入以下格式的数据：
```
N
A[0] A[1] ... A[N - 2]
B[0] B[1] ... B[N - 2]
C[0] C[1] ... C[N - 2]
```
对于 $0\le i\le N - 2$，如果第 $i$ 条传送带会将产品从 $A_i$ 运输至 $B_i$，那么 $C_i$ 为 $0$，否则 $C_i$ 为 $1$。

### 输出格式
样例评测库将以下信息输出到 stdout。

-如果你的程序被判断为正确，它报告的函数 `Query` 调用的数量为 `Accepted: 22` 。

-如果你的程序被判定为任何类型的错误答案，样例评分员将其类型写为 `Wrong Answer[4]`。

如果您的程序满足几种类型的错误答案的条件，则样例评测库只报告其中一种。

### 输入输出样例
#### 样例 #1
```plain
3
0 2
2 1
1 0
```

### 说明/提示
|函数调用|函数调用|返回值|
|:-|:-|:-|
|`Solve(3, [0, 2], [2, 1])`|||
||`Query([0, 0], [0, 0, 1])`|`[1, 0, 0]`|
||`Query([1, 0], [1, 0, 1])`|`[0, 1, 1]`|
||`Query([1, 1], [0, 0, 1])`|`[0, 0, 1]`|
||`Query([0, 1], [1, 1, 1])`|`[1, 0, 1]`|
||`Answer([1, 0])`||

对于对 `Query` 的第一次调用，另一个可能的返回值是 `[0,1,0]`。

对于对 `Query` 的第二次调用，位置为 $0$ 上的产品通过传送带 $0$ 被传送到位置 $2$，并停在那里。请注意，该产品不会被传送带 $1$ 输送到位置 $1$。

注意，这个示例输入**不满足任何子任务**的限制条件。

下发文件中，`sample-02.txt` 满足 Subtask $1$ 的限制条件，`sample-03.txt` 满足 Subtask $2$ 的限制条件。

对于某些测试用例，实际的评测程序**是自适应的**。这意味着评测程序在开始时没有固定的答案，并根据先前对 `Query` 函数的调用进行响应。

Translate by @[tbdsh](/user/752485).

hint:
**【评测程序示例】**

Here is a sample input for the sample grader and corresponding function calls.

**Sample Input 1:**

```plain
3
0 2
2 1
1 0
```

|Function Calls|Function Calls|Return Values|
|:-|:-|:-|
|`Solve(3, [0, 2], [2, 1])`|||
||`Query([0, 0], [0, 0, 1])`|`[1, 0, 0]`|
||`Query([1, 0], [1, 0, 1])`|`[0, 1, 1]`|
||`Query([1, 1], [0, 0, 1])`|`[0, 0, 1]`|
||`Query([0, 1], [1, 1, 1])`|`[1, 0, 1]`|
||`Answer([1, 0])`||

For the first function call to `Query`, another possible return value is `[0, 1, 0]` other than `[1, 0, 0]`.

For the second function call to `Query`, the product on the table $0$ is transported to the table $2$ by passing through the belt conveyor $0$, and stops there. Note that this product will not be transported to the table $1$ by passing through the belt conveyor $1$.

Note that this sample input **does not satisfy the constraints of any subtask**.

Among the files which can be obtained from the contest webpage, `sample-02.txt` satisfies the constraints of Subtask $1$, and `sample-03.txt` satisfies the constraints of Subtask $2$.

#### Notices for Grading

For some of the test cases, the actual grader is adaptive. This means the grader does not have a fixed answer in the beginning, and responds according to previous function calls to Query. It is guaranteed that there is at least one answer which does not contradict all the responses of the the grader.

**【数据范围】**

对于所有测试数据，满足 $0 \le A_i, B_i \le N - 1$，保证忽略所有传送带的方向后所有机器连通，保证所有输入均为整数。

|子任务编号|分值|$N =$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1$|$1$|$2$|无|
|$2$|$14$|$30$|无|
|$3$|$10$|$10 ^ 5$|$A_i = i$，$B_i = i + 1$|
|$4$|$75$|$10 ^ 5$|无|


title: [JOISC 2023 Day2] Council

description:
In the council of JOI City, there are $N$ assembly members, numbered from $1$ to $N$. The council will open a meeting, and the assembly members will take votes on $M$ proposed ordinances, numbered from $1$ to $M$. If $A_{i, j} = 1$, the assembly member $i \ (1 \le i \le N)$ will cast an affirmative vote on the proposed ordinance $j \ (1 \le j \le M)$. If $A_{i, j} = 0$, the assembly member $i$ will cast a negative vote on the proposed ordinance $j$.

The council of JOI City will be performed as follows.

1. Among the $N$ assembly members, they will randomly choose a chairperson by drawing lots.
2. The chairperson will choose a deputy chairperson among the $N - 1$ assembly members except for the chairperson.
3. The votes will be taken on $M$ proposed ordinances. Each of the $N - 2$ assembly members except for the chairperson and the deputy chairperson will cast an affirmative vote or a negative vote on each proposed ordinance. The council will approve a proposed ordinance if a majority of the assembly members (i.e., more than or equal to $\lfloor \frac{N}{2} \rfloor$ assembly members) cast affirmative votes on it. Here, $\lfloor x \rfloor$ is the largest integer not exceeding $x$.

Mayor K, the mayor of JOI City, wants the council to approve as many proposed ordinances as possible. Mayor K collected information on assembly members. Mayor K knows, on each proposed ordinance, who will cast an affirmative vote and who will cast a negative vote.

Write a program which, given information of the votes of the assembly members, calculates, for each assembly member, the maximum possible number of proposed ordinances approved by the council if that assembly member is chosen as the chairperson.

outputFormat: Write $N$ lines to the standard output. The $i$-th line $(1 \le i \le N)$ of output should contain the maximum possible number of proposed ordinances approved by the council if the assembly member $i$ is chosen as the chairperson.

translation:
#### 题目翻译

在 JOI 市议会中，有 $N$ 名议员，编号从 $1$ 到 $N$。议会将召开会议，议员们将对 $M$ 项提案进行表决，编号为 $1$ 到 $M$。如果 $A_{i,j}=1$，则议员 $i (1≤i≤N)$ 将对提案 $j (1≤j≤M)$ 表决肯定票。如果 $A_{i,j}=0$，则议员 $i$ 将对提案 $j$ 表决否定票。

JOI 市议会的程序如下所示。

+ 在 $N$ 名议员中，通过抽签随机选择主席。

+ 主席将在除了主席以外的其他 $N−1$ 名议员中选择副主席。

+ 将对 $M$ 项提案进行表决。除了主席和副主席以外的其他 $N−2$ 名议员，每人对每个提案均投票支持或反对。如果大多数议员（即肯定票大于等于 $⌊\dfrac{N}{2}⌋$）投票赞成，则议会将批准该提案。其中 $⌊x⌋$ 表示不超过 $x$ 的最大整数。

市长 K 希望议会尽可能地批准更多的提案。市长 K 收集了议员的信息并知道每个议员在每个提案上的表决结果。

请编写程序，在给定议员投票信息的情况下，计算每个议员作为主席时议会可以批准的提案数量的最大可能值。

#### 输入格式

从标准输入读取以下数据。

> $N \ M$
>
> $A_{1, 1} \ A_{1, 2} \ \cdots \ A_{1, M}$
>
> $A_{2, 1} \ A_{2, 2} \ \cdots \ A_{2, M}$
>
> $\vdots$
>
> $A_{N, 1} \ A_{N, 2} \ \cdots \ A_{N, M}$

#### 输出格式

输出 $N$ 行。输出的第 $i$ 行（$1≤i≤N$）应包含议员 $i$ 作为主席时议会可以批准的提案数量的最大可能值。

#### 样例解释 #1
+ 假设议员 $1$ 被选为主席。如果议员 $2$ 被选为副主席，则议会将批准三个提案，即提案 $1,2,3$。如果议员 $3$ 被选为副主席，则议会将批准两个提案，即提案 $1,2$。因此，议会批准的提案数量的最大值是 $3$。在第一行输出 $3$。

+ 假设议员 $2$ 被选为主席。如果议员 $1$ 被选为副主席，则议会将批准三个提案，即提案 $1,2,3$。如果议员 $3$ 被选为副主席，则议会将批准一个提案，即提案 $1$。因此，议会批准的提案数量的最大值是 $3$。在第二行输出 $3$。

+ 假设议员 $3$ 被选为主席。如果议员 $1$ 被选为副主席，则议会将批准两个提案，即提案 $1,2$。如果议员 $2$ 被选为副主席，则议会将批准一个提案，即提案 $1$。因此，议会批准的提案数量的最大值是 $2$。在第三行输出 $2$。

Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

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

- Let’s consider the case where the assembly member $1$ is chosen as the chairperson. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the first line.
- Let’s consider the case where the assembly member $2$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the
council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the second line.
- Let’s consider the case where the assembly member $3$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $2$. Output $2$ in the third line.

该样例满足子任务 $1, 2, 4, 5, 6, 7$ 的限制。

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

该样例满足子任务 $1, 2, 5, 6, 7$ 的限制。

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

该样例满足子任务 $1, 2, 4, 5, 6, 7$ 的限制。

**【样例解释 #4】**

该样例满足所有子任务的限制。

**【数据范围】**

对于所有测试数据，$3 \le N \le 3 \times 10 ^ 5$，$1 \le M \le 20$，$0 \le A_{i, j} \le 1$，保证所有输入均为整数。

|子任务编号|分值|限制|
|:-:|:-:|:-:|
|$1$|$8$|$N \le 300$|
|$2$|$8$|$N \le 3000$|
|$3$|$6$|$M \le 2$|
|$4$|$19$|$M \le 10$|
|$5$|$15$|$M \le 14$|
|$6$|$22$|$M \le 17$|
|$7$|$22$|无|


title: [JOISC 2023 Day2] Mizuyokan 2

description:
Mizuyokan is a Japanese confectionery made of azuki beans paste. It was made by cooking azuki beans paste with agar, and solidifying them in a rectangular-shaped form.

Now, JOI-kun has a mizuyokan machine. Using it, JOI-kun can make a horizontally long rectangular-shaped mizuyokan with $N - 1$ vertical cutlines. The length of the mizuyokan and the positions of the cutlines are determined by the $N$ parameters $d_1, d_2, \dots, d_N$ set on the machine. The length of the mizuyokan is $d_1 + d_2 + \dots + d_N$. The distance between the $(i - 1)$-th cutline $(1 \le i \le N)$ from the left and the $i$-th cutline from the left is $d_i$. Here, we consider the leftmost edge of the mizuyokan as the $0$-th cutline, and the rightmost edge of the mizuyokan as the $N$-th cutline. In the beginning, the parameters of the mizuyokan machine satisfy $d_i = L_i \ (1 \le i \le N)$.

JOI-kun has a plan to organize $Q$ tea parties. The $j$-th tea party $(1 \le j \le Q)$ is described by the integers $X_j, Y_j, A_j, B_j$. It proceeds as follows.

1. The parameter $d_{X_j}$ of the mizuyokan machine is updated, and it is set as $Y_j$.
2. JOI-kun makes a new mizuyokan using the mizuyokan machine. He takes the part of the mizuyokan 0between the $A_j$-th cutline and the $B_j$-th cutline, and uses it for the tea party. He eats the rest.
3. JOI-kun cuts the part of the mizuyokan for the tea party along some of the cutlines. He cuts the part of the mizuyokan into one or more pieces. In this process, the following condition should be satisfied: if the pieces are ordered from the left as in the original positions, the sequence of the lengths of the pieces is **zigzag**.

Here, a sequence is called zigzag if the elements of the sequence increase and decrease alternately. For example, the sequences $(2, 9, 2, 7), (7, 1, 9, 4, 6), (5), (2, 1)$ are zigzag, but the sequences $(1, 2, 3), (7, 1, 4, 4, 6), (2, 2)$ are not zigzag. Precisely, a sequence $(x_1, x_2, \dots, x_m)$ is called zigzag if one (or the both) of the following conditions are satisfied:

- For $k = 1, 2, \dots, m - 1$, the inequality $x_k < x_{k + 1}$ is satisfied if $k$ is odd, and the inequality $x_k > x_{k + 1}$ is satisfied if $k$ is even.
- For $k = 1, 2, \dots, m - 1$, the inequality $x_k > x_{k + 1}$ is satisfied if $k$ is odd, and the inequality $x_k < x_{k + 1}$ is satisfied if $k$ is even.

Since JOI-kun wants to give mizuyokan to as many friends as possible, he wants to maximize the number of pieces obtained by the procedure 3. of the tea party.

Write a program which, given information of the initial parameters of the mizuyokan machine and the plan of the tea parties, calculates, for each tea party, the maximum possible number of pieces obtained by cutting the part of the mizuyokan so that the condition is satisfied. Note that, under the constraints of this task, it is always possible to cut the part of the mizuyokan so that the condition is satisfied.

inputFormat:
Read the following data from the standard input.

> $N$
>
> $L_1 \ L_2 \ \cdots \ L_N$
>
> $Q$
>
> $X_1 \ Y_1 \ A_1 \ B_1$
>
> $X_2 \ Y_2 \ A_2 \ B_2$
>
> $\vdots$
>
> $X_Q \ Y_Q \ A_Q \ B_Q$

outputFormat: Write $Q$ lines to the standard output. The $j$-th line $(1 \le j \le Q)$ of output corresponds to the $j$-th tea party. It contains the maximum possible number of pieces obtained by cutting the part of the mizuyokan in the $j$-th tea party so that the condition is satisfied.

translation:
#### 题目描述

水羊羹是一种日本甜点，是用红豆糊和琼脂制成的。它的做法是先将红豆糊与琼脂混合后搅拌均匀，然后倒入长方形模具中，等待它们凝固成型。

现在，JOI 君有了一个制作水羊羹的机器。他可以用该机器制作一块长度为 $d_1+d_2+⋯+d_N$ 的水羊羹。JOI 君可以让这块水羊羹沿着 $N−1$ 条垂直的切割线（不包括两端）分割成 NN 段长度为 $d_1,d_2,…,d_N$ 的竖条形状的小片。

JOI 君希望在有 $Q$ 场茶会上送给尽可能多的朋友水羊羹。每场茶会对应 $(X_j,Y_j,A_j,B_j)$，其中：

+ JOI 君会更新机器上第 $X_j$ 条切割线的位置为 $Y_j$，以此生成一个新的水羊羹。

+ JOI 君挑选出原水羊羹中从第 $A_j$ 条切割线到第 $B_j$ 条切割线之间的部分，作为茶会中的水羊羹。剩余部分被他自己吃掉。

+ JOI 君需将所选小片沿着一些切割线分割成若干段让朋友品尝。在这一过程中应当满足如下条件：如果按顺序排列，分割后每个小片长度的大小应当是一个“之”字形，即连续两个片段长度先递增再递减，亦或者先递减再递增。

具体地，令 $(x_1,x_2,…,x_m)$ 是分割后小片长度组成的序列，$(x_1,x_2,…,x_m)$ 是“之”字形当且仅当它满足以下一个或两个条件：

+ 对于所有 $k=1,2,…,m−1$，如果 $k$ 为奇数，则 $x_k<x_{k+1}$，否则 $x_k>x_{k+1}$。

+ 对于所有 $k=1,2,…,m−1$，如果 $k$ 为奇数，则 $x_k>x_{k+1}$，否则 $x_k<x_{k+1}$。

因为 JOI 君希望给尽可能多的朋友品尝到水羊羹，所以他希望供品的小片数量最大化。

请完成一个程序，它会读入水羊羹机器的参数和茶会计划，并对每一场茶会输出可供品尝的小片的最大数量。请注意，在任务的限制下，可以总是找到一种合适的方法将所选小片分割成符合“之”字形条件的若干小片。

#### 输入格式

从标准输入中读入以下数据：

> $N$
>
> $L_1 \ L_2 \ \cdots \ L_N$
>
> $Q$
>
> $X_1 \ Y_1 \ A_1 \ B_1$
>
> $X_2 \ Y_2 \ A_2 \ B_2$
>
> $\vdots$
>
> $X_Q \ Y_Q \ A_Q \ B_Q$

#### 输出格式

程序应该在标准输出中输出 $Q$ 行。第 $j$ 行 $(1≤j≤Q)$ 应当包含第 $j$ 场茶会中的所选小片的最大数量。

Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

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

In the first tea party, the parameters of the mizuyokan machine is set as $(d_1, d_2, d_3, d_4, d_5, d_6) = (5, 6, 8, 7, 4, 9)$.

JOI-kun uses the part of the mizuyokan between the $0$-th cutline and the $5$-th cutline as in Figure 1.

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

For example, JOI-kun can cut the part of the mizuyokan as follows.

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

In Method 1, the lengths of the pieces are $5, 14, 7, 4$. Since this sequence is not zigzag, it does not satisfy the condition. On the other hand, in Method 2, the lengths of the pieces are $11, 8, 11$. Since this sequence is zigzag, it satisfies the condition. In Method 3, the length of the piece is $30$. Since this sequence is zigzag, it also satisfies the condition.

If JOI-kun cuts the part of the mizuyokan by Method 2, he gets $3$ pieces. Since it is not possible for him to cut the part of the mizuyokan so that the condition is satisfied and he gets more than or equal to $4$ pieces, output $3$ in the first line.

该样例满足所有子任务的限制。

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

In the first tea party, the length of the part of the mizuyokan for the tea party is $4$. There is a cutline whose distance is $2$ from the leftmost edge. If JOI-kun uses the mizuyokan without cutting it, he gets one piece. The sequence of the lengths of the pieces is $(4)$, which is zigzag. Since he cannot obtain more than one pieces, output $1$.

In the second tea party, the length of the part of the mizuyokan for the tea party is $9$. There are two cutlines whose distances are $2, 4$ from the leftmost edge. If JOI-kun cuts the mizuyokan at the cutline whose distance is $4$ from the leftmost edge, he gets two pieces. The sequence of the lengths of the pieces is $(4, 5)$, which is zigzag. Since he cannot obtain more than two pieces, output $2$.

In the third tea party, the length of the part of the mizuyokan for the tea party is $10$. There are three cutlines whose distances are $1, 3, 5$ from the leftmost edge. If JOI-kun cuts the mizuyokan at the cutlines whose distances are $3, 5$ from the leftmost edge, he gets three pieces. The sequence of the lengths of the pieces is $(3, 2, 5)$, which is zigzag. Since he cannot obtain more than three pieces, output $3$.

该样例满足子任务 $1, 2, 3, 5, 6$ 的限制。

**【数据范围】**

对于所有测试数据，满足 $1 \le N \le 2.5 \times 10 ^ 5$，$1 \le L_i \le 10 ^ 9$，$1 \le Q \le 5 \times 10 ^ 4$，$1 \le X_j \le N$，$1 \le Y_j \le 10 ^ 9$，$0 \le A_j < B_j \le N$，保证所有输入均为整数。

|子任务编号|分值|限制|
|:-:|:-:|:-:|
|$1$|$6$|$N \le 200$，$Q \le 10$|
|$2$|$9$|$N \le 2000$，$Q \le 10$|
|$3$|$13$|$Q \le 10$|
|$4$|$32$|$Y_j = L_{X_j}$|
|$5$|$29$|$L_i, Y_j \le 1.2 \times 10 ^ 5$|
|$6$|$11$|无|


title: [JOISC 2023 Day4] Bitaro's Travel

description:
There is a very long road in JOI City, which can be considered as the real number line. A position on the road is represented by a real number coordinate. In JOI City, there are $N$ sightseeing spots along the road, numbered from $1$ to $N$ in ascending order of the coordinates. The coordinate of the $i$-th sightseeing spot $(1\le i\le N)$ is $X_i$.

Bitaro will visit all the sightseeing spots in JOI City. Since "greedy" is the slogan of his life, he will repeat the following procedures until he visits all the sightseeing spots.

- Let $x$ be Bitaro’s current coordinate. Among the sightseeing spots he has not yet visited, take the sightseeing spot $i$ where the distance $|x − X_i|$ from Bitaro's current position takes a minimum value. Then Bitaro moves to the position of the sightseeing spot $i$, and visits it. If there are more than one such sightseeing spots, he moves to the sightseeing spot whose coordinate is smaller than the others. Here, $|t|$ is the absolute value of $t$.

However, thanks to long years of experience, Bitaro knows that if he moves by repeating the above procedures, the total traveling distance may be longer than he expected. Since the total traveling distance varies according to the starting coordinate, he wants to know the total traveling distance until he visits all the sightseeing spots if he starts from each of $Q$ candidates of starting coordinates $S_1, S_2,\dots, S_Q$.

To help Bitaro, write a program which calculates the total traveling distance if he starts from each of the candidates of starting coordinates, given information of JOI City and candidates of starting coordinates.

inputFormat:
Read the following data from the standard input.

> $N$
>
> $X_1\ X_2\cdots X_N$
>
> $Q$
>
> $S_1$
>
> $S_2$
>
> $\vdots$
>
> $S_Q$

outputFormat: Write $Q$ lines to the standard output. The $j$-th line $(1 \le j \le Q)$ of output should contain the total traveling distance if Bitaro starts from the coordinate $S_j$.

translation:
#### 题目描述
在 JOI 市里，有一条长度非常长的路，可以看做一个实数数轴。这条路上有 $N$ 个景点 $1,2,\dots,N$，它们按照坐标递增的顺序编号。第 $i$ 个景点位于坐标为 $X_i$ 处。

Bitaro 打算参观 JOI 市的所有景点。因为贪心是他人生的口号，所以他会按以下方式不断前往最近的未参观过的景点，直到参观完毕：

令 $x$ 表示 Bitaro 当前所在的位置。从尚未参观过的景点中选取距离 Bitaro 的当前位置最近的景点 $i$，使得 $|x-X_i|$ 的值最小。然后将 Bitaro 移动到第 $i$ 个景点并参观它。如果有多个最近的景点，则移动到它们中编号最小的那个。其中 $|t|$ 表示 $t$ 的绝对值。
但是，由于多年的经验，Bitaro 知道如果只按上述方式移动，那么他的总路程可能会比预想的更长。由于总路程和起始坐标有关，他想知道从 $Q$ 个起始坐标 $S_1,S_2,\dots,S_Q$ 出发，分别需要走多少路程才能参观完所有的景点。

为了帮助 Bitaro，你需要编写一个程序，给出在每个起始坐标处开始前往参观所有景点时所需走的总路程。

#### 输出格式
共输出 $Q$ 行。对于每一行，输出从该起点开始走过所有景点后的总路程。

Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

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

If Bitaro starts from the coordinate $7$, he visits all the sightseeing spots as follows.
1. He has not yet visited the sightseeing spots $1, 2, 3, 4, 5$, and the distances from Bitaro’s current position are $7, 2, 1, 0, 2$, respectively. Since the sightseeing spot $4$ is the nearest sightseeing spot from Bitaro, he stays at the coordinate $7$ and visits the sightseeing spot $4$.
2. He has not yet visited the sightseeing spots $1, 2, 3, 5$, and the distances from Bitaro’s current position are $7, 2, 1, 2$, respectively. Since the sightseeing spot $3$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $7$ to the coordinate $6$ and visits the sightseeing spot $3$.
3. He has not yet visited the sightseeing spots $1, 2, 5$, and the distances from Bitaro’s current position are $6, 1, 3$, respectively. Since the sightseeing spot $2$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $6$ to the coordinate $5$ and visits the sightseeing spot $2$.
4. He has not yet visited the sightseeing spots $1, 5$, and the distances from Bitaro’s current position are $5, 4$, respectively. Since the sightseeing spot $5$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $5$ to the coordinate $9$ and visits the sightseeing spot $5$.
5. He has not yet visited the sightseeing spot $1$. Since the sightseeing spot $1$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $9$ to the coordinate $0$ and visits the sightseeing spot $1$.

Since Bitaro’s total traveling distance is $15$, output $15$.

该样例满足所有子任务的限制。

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

该样例满足子任务 $3, 4$ 的限制。

**【数据范围】**

对于所有测试数据，满足 $1\le N,Q\le2\times10^5$，$0\le X_i\le10^9$，$X_i<X_{i+1}$，$0\le S_j\le10^9$，保证所有输入均为整数。

|子任务编号|分值|限制|
|:-:|:-:|:-:|
|$1$|$5$|$Q=1,N\le2\times10^3$|
|$2$|$10$|$Q=1$|
|$3$|$30$|$X_{i+1}-X_i\le100$|
|$4$|$55$|无|


title: [JOISC 2023 Day3] Chorus

description:
On the stage, $2N$ beavers are standing in a row. They are members of the chorus. Each beaver sings either the alto part or the bass part of the chorus. This information is given by a string $S$. Precisely, the $i$-th beaver ($1\le i\le 2N$) from the stage right (i.e., from left when seen from the audience seats) sings the alto part if the $i$-th character of $S$ is $\text{`\texttt{A}'}$. The $i$-th beaver sings the bass part if the $i$-th character of S is $\text{`\texttt{B}'}$. There are $N$ beavers singing the alto part, and $N$ beavers singing the bass part.

From now, the beavers will sing $K$ songs. However, since all the songs are very difficult, each beaver sings exactly one song only, and does not sing other songs. Moreover, in order to make singing voice more beautiful, for every song, the following conditions should be satisfied.

- At least one beaver sings the song.
- The number of beavers singing the alto part of the song is equal to the number of beavers singing the bass part of the song.
- If we consider the beavers singing the song only, every alto beaver stands the stage right of every bass beaver.

Bitaro, the conductor, tried to find a way to allot songs to beavers which satisfies the conditions. Since Bitaro is bright, he notices that it might be impossible to allot songs to beavers.

In order to cope with this issue, Bitaro will perform the following operation several times so that there is a way to allot songs to beavers which satisfies the conditions.

- Swap the position of two adjacent beavers.

Since Bitaro thinks efficiency is important, he wants to minimize the number of operations. However, it turns out to be a surprisingly difficult problem. Since you are a brilliant programmer, Bitaro asks you to solve this problem.

Write a program which, given information of the chorus and the number of songs $K$, calculates the minimum
number of operations Bitaro needs to perform. Note that, under the constraints of this task, it is possible to perform the operations several times so that there is a way to allot songs to beavers which satisfies the conditions.

inputFormat:
Read the following data from the standard input.

> $N\ K$
>
> $S$

outputFormat: Write one line to the standard output. The output should contain the minimum number of operations Bitaro needs to perform.

translation:
#### 题目描述
在舞台上，有 $2N$ 只海狸排成一列。它们是合唱团的成员。每只海狸唱着高音部或低音部。这些信息由一个字符串 $S$ 给出。具体地，如果 $S$ 的第 $i$ 个字符是 $A$，编号为 $i$ 的海狸（从右边看台来看）唱高音。如果 $S$ 的第 $i$ 个字符是 $B$，编号为 $i$ 的海狸唱低音。有 $N$ 只海狸唱高音，有 $N$ 只海狸唱低音。

从现在起，这些海狸将要演唱 $K$ 首歌。然而，因为所有歌曲非常复杂，每只海狸只唱一首歌曲，不会唱其他歌曲。此外，为了使歌声更加美妙，每首歌曲必须满足以下条件：

+ 至少有一只海狸唱这首歌。

+ 唱这首歌的唱高音和唱低音的海狸数量应当相等。

+ 如果只考虑唱这首歌的海狸，所有唱高音的海狸都在唱低音的海狸的右边。

指挥家 Bitaro 想找到一种方案，给出哪些海狸唱哪首歌，满足以上所有条件。由于 Bitaro 特别聪明，他注意到这可能无法实现。为了应对这个问题，Bitaro 将交换相邻两只海狸的位置多次，以便有一种方式可以调配海狸，从而满足上述条件。

由于 Bitaro 认为效率很重要，所以他想最小化要执行的操作数。然而，这是一个非常困难的问题。由于您是一位出色的程序员，Bitaro 请求您解决此问题。

编写一份程序，在给出合唱与演唱歌曲数量 $K$ 的信息时，计算 Bitaro 需要执行的最小操作数。请注意，在本任务的限制下，可以执行操作多次，以便有一种方式可以在海狸之间分配歌曲，满足上述条件。
#### 输入格式

从标准输入读取以下数据:

> $N\ K$
>
> $S$

#### 输出格式

向标准输出写入一行。输出应该包含 Bitaro 需要执行的最小操作数。

#### 样例解释

在输入样例 1 中，例如 Bitaro 可以执行以下操作。这里下划线表示由 Bitaro 交换的两只岛狸的位置：

+ 交换第三只海狸和从右侧舞台开始的第四只海狸。此操作之后，字符串表示从右侧到左侧的海狸部分变为 $\text{`\texttt{AA\underline{AB}BABBAB}'}$。

+ 交换第八只海狸和从右侧舞台开始的第九只海狸。此操作之后，字符串表示从右侧到左侧的海狸部分变为 $\text{`\texttt{AAABBAB\underline{AB}B}'}$。

经过这些操作之后，Bitaro 可以如下分配海狸唱哪首歌：

+ 从右往左数，第 $1,2,3,4,5,7$ 只海狸唱第一首歌。

+ 从右往左数，第 $6,8,9,10$ 只海狸唱第二首歌。

这种方式使所有条件均得到满足。

如果操作次数少于 $2$，则不存在一种满足条件的海狸分配方式。因此输出 $2$。

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

In this sample input, for example, Bitaro can perform the following operations. Here, the underline denotes the positions of the two beavers swapped by Bitaro.

1. Swap the third beaver and the fourth beaver from the stage right.
  After this operation, the string which denotes the parts of the beavers from the stage right becomes
$\text{`\texttt{AA\underline{AB}BABBAB}'}$.
2. Swap the eighth beaver and the ninth beaver from the stage right.
  After this operation, the string which denotes the parts of the beavers from the stage right becomes
$\text{`\texttt{AAABBAB\underline{AB}B}'}$.

After these operations, Bitaro can allot songs to beavers as follows.

- From the stage right, the $1, 2, 3, 4, 5, 7$-th beavers sing the first song.
- From the stage right, the $6, 8, 9, 10$-th beavers sing the second song.

This way to allot songs to beavers satisfies the conditions.

If the number of operations is less than $2$, there does not exist a way to allot songs to beavers which satisfies the conditions. Therefore, output $2$.

该样例满足所有子任务的限制。

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

Without performing operations, Bitaro can allot songs to beavers as follows.

- From the stage right, the $1, 2, 3, 5$-th beavers sing the first song.
- From the stage right, the $4, 6, 7, 8$-th beavers sing the second song.
- From the stage right, the $9, 10$-th beavers sing the third song.

This way to allot songs to beavers satisfies the conditions. Therefore, output $0$.

该样例满足所有子任务的限制。

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

该样例满足所有子任务的限制。

**【样例解释 #4】**

该样例满足所有子任务的限制。

**【数据范围】**

对于所有测试数据，满足 $1\le N\le 10^6$，$1\le K\le N$，$S$ 是一个长度为 $2N$ 的字符串，且在 $S$ 中，字母 $\verb!A!$ 和 $\verb!B!$ 均出现了 $N$ 次。保证 $N,K$ 均为整数。

| 子任务编号 | 分值 | 限制 |
| :----------: | :----------: | :----------: |
| $1$ | $16$ | $N\le 10$ |
| $2$ | $24$ | $N\le 500$ |
| $3$ | $21$ | $N\le 5000$ |
| $4$ | $26$ | $N\le 10^5$ |
| $5$ | $13$ | 无 |