title: Alice and Bob

description:
Alice 和 Bob 在一起玩游戏。

初始时给定一个值域在 $0$ 到 $n$ 之间的整数序列 $a$，然后他（她）们轮流进行如下操作，Alice 先操作。

- 操作：任意重排 $a_{1\sim a_1}$。

如果某一个人操作前 $a_1=0$，则他（她）立刻输，因为他（她）无法进行操作。

如果某次操作结束后某一个人存在两次**他（她）的**操作满足**操作结束后**的 $a_1$ 相同，则他（她）立刻输。

现在给定非负整数序列 $a$，假设两人足够聪明，问谁有必胜策略。

inputFormat:
**本题多测。**

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

随后输入 $T$ 组数据。对于每组数据，第一行输入一个正整数 $n$，第二行输入 $n$ 个非负整数 $a_i$。

outputFormat: 对于每一组数据，输出一行一个字符串 `Alice` 或者 `Bob`，分别表示先手必胜与后手必胜。


title: 「ALFR Round 2」A Sum

type: P

description:
给定三个整数 $n,p,q$，你需要构造一个 $n$ 个数的序列 $a$，满足：

- $\forall 1\leq i\leq n:1 \leq a_i\leq 10^7,a_i\in\mathbb{Z}$；

- $(\sum\limits_{1\leq i<j\leq n}[a_i+a_j\leq q])=p$。

通俗地说，每个数都是正整数且在 $[1, 10^7]$ 之间，且这 $n$ 个数无序选两个不同位置的数构成的 $\dfrac{n(n-1)}{2}$ 个加和中有恰好 $p$ 个和不大于 $q$。你只需要给出一种方案即可。

inputFormat: 一行三个整数 $n,p,q$。

outputFormat: 一行 $n$ 个数，表示构造的序列。


title: 「CROI · R2」在相思树下 I

background:
>年年桃树下
>
>常看一个变成俩
>
>小小心愿常比划
>
>快快实现吧
>
>却没看到他也在树下
>
>相逢二字纵使隔天涯
>
>转角总会遇上他
>
>缘分缘分啊

description:
**本题采用多组数据测试。**

现在欣欣有一个从 $1$ 到 $n$ 的序列，并想对这个序列进行如下两种操作。

操作一：删去所有的奇数项。

操作二：删去所有的偶数项。

欣欣发现她在进行 $k$ 次操作后，最后只剩下一个数，但她不知道这个数是多少，于是欣欣来找你求助，她会给你她所进行的 $k$ 次操作的种类，希望你告诉她最后的那个数是多少。

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

对于每组数据：

第一行两个整数 $n$ 和 $k$，含义如题面所示。

第二行 $k$ 个整数，代表欣欣依次进行的操作种类，其中 $1$ 代表操作一，$2$ 代表操作二。

outputFormat: 共 $T$ 行，每行一个数代表每组数据对应的答案。

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

对于第一组数据，序列的变化如下：

$\{1,2,3,4,5\} \to \{2,4\} \to \{4\}$。

**【数据范围】**

对于 $30\%$ 的数据， $n\le 5\times10^5$。

对于 $100\%$ 的数据，$1\le T \le 10$，$1\le n\le 10^{18}$。

保证对于所有的数据，操作 $k$ 次后均仅剩下一个数。


title: 「CMOI R1」Looking For Edge Of Ground／City Planning

background:
![](bilibili:BV1np4y19753)

[如何对 $n$ 个点的简单有标号无向连通图计数？](https://www.luogu.com.cn/problem/P4841)$\small\color{white}/42^{\text{nd}}\text{Problem by ArCu}.$

有一个显然错误的做法：枚举一棵树，然后在上面加边。

你需要求每张图被统计的次数的平方和。

description:
给定正整数 $n$。

一开始，$\text{ClBe}$ 会选定一棵 $n$ 个点的有标号无向无根树，将树上的边染成白色。然后他会在这棵树上加任意多条边，且满足：

* 新加的边是黑色的无向边；
* 加完边后的图忽略边的颜色后是一张简单图。

接下来 $\text{ClBe}$ 会将所有可能得到的结果放到一个集合 $S$ 中。

显然这种统计连通图个数的方法会把一个图算很多遍，所以 $\text{ClBe}$ 定义 $f(G)$：$S$ 中有 $f(G)$ 个图在忽略边的颜色后和 $G$ 相同（两个图 $A,B$ 相同指对于任意一条边 $(u,v)$，$(u,v)\in A\iff(u,v)\in B$）。

（$\sum_G$ 代表对所有可能的图 $G$ 求和。）显然

$$\sum_{G}f(G)=n^{n-2}2^\binom{n-1}2$$

所以你需要求

$$\sum_{G}f(G)^2$$

答案对 $998244353$ 取模。很可惜因为一些原因模数**不能**取 $1004535809$。

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


title: [LMXOI Round 2] Annihilation

background: LMX 和 HQZ 在研究上次被毙掉的题目 Impacter 时，他们提出了一个新的问题。

description:
给定一棵 $n$ 个节点的，以 $1$ 为根的树，每个点有权值 $a_i$。

对于一个点 $u$，定义函数 $f(u,v,d)$ 表示在 $u$ 的子树内选择一些点（至少需要选取一个点），选出的点中最大权值为 $v$，且它们编号的最大公约数为 $d$ 的方案数。

给定一个常数 $k$ 和一个序列 $b$，对于每个点 $u$，你需要求出 $ \sum\limits_{k|i}^{n}\sum\limits_{j=1}^nf(u,i,j)\times b_j$ 的值，其中 $k|i$ 表示 $k$ 可以整除 $i$。由于该值可能很大，所以你需要输出其对 $998244353$ 取模的结果。

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

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

接下来一行 $n$ 个数，第 $i$ 个数字表示 $a_i$。

接下来一行 $n$ 个数，第 $i$ 个数字表示 $b_i$。

outputFormat: 一行 $n$ 个整数，分别表示 $u=1,2,\ldots n$ 时的答案对 $998244353$ 取模的值。


title: [蓝桥杯 2024 省 A] 艺术与篮球

description:
小蓝出生在一个艺术与运动并重的家庭中。
妈妈是位书法家，她希望小蓝能通过练习书法，继承她的艺术天赋，并练就一手好字。爸爸是一名篮球教练，他希望小蓝能通过篮球锻炼身体，培养运
动的激情和团队合作的精神。
为了既满足妈妈的期望，又不辜负爸爸的心意，小蓝决定根据日期的笔画数来安排自己的练习。首先，他会将当天的日期按照 `YYYYMMDD` 的格式
转换成一个 $8$ 位数，然后将这 $8$ 位数对应到汉字上，计算这些汉字的总笔画数。如果总笔画数超过 $50$，他就去练习篮球；如果总笔画数不超过 $50$，他就去练习书法。
例如，在 $2024$ 年 $1$ 月 $1$ 日这天，日期可表示为一个 $8$ 位数字 $20240101$，其转换为汉字是“二零二四零一零一”。日期的总笔画数为 $2 + 13 + 2 + 5 + 13 +
1 + 13 + 1 = 50$，因此在这天，小蓝会去练习书法。
以下是汉字的笔画数对照表：

|汉字|笔画数|汉字|笔画数|
| -----------: | -----------: | -----------: | -----------: |
|零 |$13 $|五 |$4$|
|一 |$1$|  六 |$4$|
|二 |$2$|  七 |$2$|
|三 |$3$|  八 |$2$|
|四 |$5$| 九 |$2$|

现在，请你帮助小蓝统计一下，在 $2000$ 年 $1$ 月 $1$ 日到 $2024$ 年 $4$ 月 $13$ 日
这段时间内，小蓝有多少天是在练习篮球？

inputFormat: 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。


title: [蓝桥杯 2024 省 A] 五子棋对弈

description:
“在五子棋的对弈中，友谊的小船说翻就翻？” 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着 “友谊第一，比赛第二” 的宗旨，决定在一块 $5 × 5$ 的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场**和棋（平局）** 作为彼此友谊的见证。
比赛遵循以下规则：
1. 棋盘规模：比赛在一个 $5 × 5$ 的方格棋盘上进行，共有 $25$ 个格子供下棋使用。
2. 棋子类型：两种棋子，黑棋与白棋，代表双方。小蓝持白棋，小桥持黑棋。
3. 先手规则：白棋（小蓝）具有先手优势，即在棋盘空白时率先落子（下棋）。
4. 轮流落子：玩家们交替在棋盘上放置各自的棋子，每次仅放置一枚。
5. 胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。
6. 平局条件：当所有 $25$ 个棋盘格都被下满棋子，而未决出胜负时，游戏以平局告终。

在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况（终局不同看成不同情况，终局相同而落子顺序不同看成同一种情况），既确保棋盘下满又保证比赛结果为平局。

outputFormat: 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。


title: [LMXOI Round 2] Nirvana

background: HQZ 在摆弄 LMX 的一台机器。

description:
定义一张无向连通图是**好的**，当且仅当存在一组定向方案使得原图可以通过对每条边定向使其成为仅有 $S$ 入度为 $0$，$T$ 出度为 $0$ 的**有向无环**图。

给定一张 $n$ 个点 $m$ 条边**无自环**的**无向连通图**，定义一次操作为等概率选取两个**可重**的点 $x, y$ 且 $x \le y$，连接 $x$ 和 $y$。求一次操作后的图是**好的**的概率 $P$ 对 $998244353$ 取模的值。

若 $P > 0$，你需要在加入一条边后构造一组定向方案。

若 $P = 0$，你需要构造一组删点数量最少的方案使得原图是好的。

inputFormat:
第一行四个正整数 $n, m, S, T$，含义如题面所述。

接下来 $m$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示 $x_i$ 和 $y_i$ 之间有一条无向边。

outputFormat:
第一行一个非负整数 $P$。

若 $P > 0$，接下来两行，第一行两个正整数 $u, v$ 表示你添加的边为 $u \to v$（有向），第二行一个长度为 $m$ 的仅包含 $0$ 和 $1$ 的字符串 $s$，$s_i = 0$ 表示 $(x_i, y_i)$ 这条边的方向为 $x_i \to y_i$，否则为 $y_i \to x_i$。

若 $P = 0$，接下来输出两行，第一行包含一个正整数 $c$，表示最少要删除多少个点。第二行包含 $c$ 个正整数，表示需要删掉的点。

**评分方式：**

**在输出格式正确的情况下**，若你的程序正确回答了概率 $P$，则你能获得该测试点 $30\%$ 的分数。

**在此基础上**，若你正确构造出了方案，则你能获得该测试点 $100\%$ 的分数。

**若你的程序输出格式错误，可能会出现不可预料的错误。**


title: 双端队列

description:
Sherry 现在碰到了一个棘手的问题，有 $N(1 \le N \le 200000)$ 个整数需要排序。

Sherry 手头能用的工具就是若干个双端队列。

她从 $1$ 到 $N$ 需要依次处理这 $N$ 个数，对于每个数，Sherry 能做以下两件事：

1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；

2．将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，Sherry 将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。

请你求出最少需要多少个双端序列。

inputFormat:
第一行输入整数 $N$，代表整数的个数。

接下来 $N$ 行，每行包括一个整数 $D_i$，代表所需处理的整数。

outputFormat: 输出一个整数，代表最少需要的双端队列数。


title: 邻值查找

description:
给定一个长度为 $n$ 的序列 $A$，$A$ 中的数各不相同。

对于 $A$ 中的每一个数 $A_i$，求：

$\min_{1 \le j <i}|A_i-A_j|$

以及令上式取到最小值的 $j$（记为 $P_i$）。若最小值点不唯一，则选择使 $A_j$ 较小的那个。

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

第二行输入 $n$ 个整数 $A_1 \sim A_n$，代表序列的具体数值，数值之间用空格隔开。

outputFormat:
输出共 $n-1$ 行，每行输出两个整数，数值之间用空格隔开。

分别表示当 $i$ 取 $2 \sim n$ 时，对应的 $\min_{1 \le j <i}|A_i-A_j|$ 和 $P_i$ 的值。


title: [CCC 2007] Snowflake Snow Snowflakes

description: You may have heard that no two snowflakes are alike. Your task is to write a program to determine whether this is really true. Your program will read information about a collection of snowflakes, and search for a pair that may be identical. Each snowflake has six arms. For each snowflake, your program will be provided with a measurement of the length of each of the six arms. Any pair of snowflakes which have the same lengths of corresponding arms should be flagged by your program as possibly identical.

inputFormat: The first line of input will contain a single integer $n$, $0 < n \le 100000$ , the number of snowflakes to follow. This will be followed by $n$ lines, each describing a snowflake. Each snowflake will be described by a line containing six integers (each integer is at least $0$ and less than $10000000$) , the lengths of the arms of the snow ake. The lengths of the arms will be given in order around the snowflake (either clockwise or counterclockwise), but they may begin with any of the six arms. For example, the same snowflake could be described as $1 2 3 4 5 6$ or $4 3 2 1 6 5$ .

outputFormat:
If all of the snowflakes are distinct, your program should print the message:

`No two snowflakes are alike.`

If there is a pair of possibly identical snow akes, your program should print the message:

`Twin snowflakes found.`

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

你可能听说过没有两片雪花是相同的。你的任务是编写一个程序来确定这是否真的是正确的。你的程序将读取关于一组雪花的信息，并搜索可能相同的一对雪花。每片雪花有六条“角”。对于每片雪花，你的程序将提供每条角的长度测量。任何一对长度对应的角相同的雪花都应该被你的程序标记为可能相同。

**【输入格式】**

输入的第一行包含一个整数 $n$，$0 < n \le 100000$，表示接下来的雪花数量。接下来的 $n$ 行描述每片雪花。每片雪花由包含六个整数的一行描述（每个整数至少为 $0$ 且小于 $10000000$），表示雪花的六条角的长度。角的长度将按顺序围绕着雪花给出（顺时针或逆时针），但它们可以从六个角中的任何一条开始。例如，同一片雪花可以描述为 $1\ 2\ 3\ 4\ 5\ 6$ 或 $4\ 3\ 2\ 1\ 6\ 5$。

**【输出格式】**

如果所有的雪花都是不同的，你的程序应该打印消息：

`No two snowflakes are alike.`

如果有一对可能相同的雪花，你的程序应该打印消息：

`Twin snowflakes found.`

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: 兔子与兔子

description:
很久很久以前，森林里住着一群兔子。

有一天，兔子们想要研究自己的 DNA 序列。

我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 $26$ 个小写英文字母）。

然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。

注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

inputFormat:
第一行输入一个 DNA 字符串 $S$。

第二行一个数字 $m$，表示 $m$ 次询问。

接下来 $m$ 行，每行四个数字 $l_1, r_1, l_2, r_2$，分别表示此次询问的两个区间，注意字符串的位置从 $1$ 开始编号。

outputFormat:
对于每次询问，输出一行表示结果。

如果两只兔子完全相同输出 `Yes`，否则输出 `No`（注意大小写）。

hint: 数据保证，$1 \le |S|,m \le 1000000$。其中，$|S|$ 为字符串 $S$ 的长度。


title: 后缀数组

description:
后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者 DC3 算法实现，这超出了我们的讨论范围。

在本题中，我们希望使用快排、Hash 与二分实现一个简单的 $O(n\log^2n)$ 的后缀数组求法。

详细地说，给定一个长度为 $n$ 的字符串 $S$（下标 $0 \sim n-1$），我们可以用整数 $k(0 \le k < n)$ 表示字符串 $S$ 的后缀 $S(k \sim n-1)$。

把字符串 $S$ 的所有后缀按照字典序排列，排名为 $i$ 的后缀记为 SA[i]。

额外地，我们考虑排名为 $i$ 的后缀与排名为 $i-1$ 的后缀，把二者的最长公共前缀的长度记为 Height[i]。

我们的任务就是求出 SA 与 Height 这两个数组。

inputFormat:
输入一个字符串，其长度不超过 $30$ 万。

字符串由小写字母构成。

outputFormat:
第一行为数组 SA，相邻两个整数用 $1$ 个空格隔开。

第二行为数组 Height，相邻两个整数用 $1$ 个空格隔开，我们规定 Height[1]=0。


title: 最大异或对 The XOR Largest Pair

description: 给定 $N$ 个整数 $A_1.A_2, \cdots, A_N$ 中选出两个进行异或计算，得到的结果最大是多少？

inputFormat: 第一行一个整数 $N$，第二行 $N$ 个整数 $A_1.A_2, \cdots, A_N$。

outputFormat: 一个整数表示答案。

hint: 对于所有测试数据，$1 \le n \le 100000$，保证 $A_i$ 在 `int` 范围内。


title: 前缀统计

description:
给定 $N$ 个字符串 $S_1,S_2\cdots S_N$，接下来进行 $M$ 次询问，每次询问给定一个字符串 $T$，求 $S_1 \sim S_N$ 中有多少个字符串是 $T$ 的前缀。

输入字符串的总长度不超过 $10^6$，仅包含小写字母。

inputFormat:
第一行输入两个整数 $N，M$。

接下来 $N$ 行每行输入一个字符串 $S_i$。

接下来 $M$ 行每行一个字符串 $T$ 用以询问。

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

每个答案占一行。

hint: 数据范围满足 $1 \le N,M \le 10^5$


title: 小猫爬山

description:
Freda 和 rainbow 饲养了 $N(N\le 18)$ 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了

Freda 和 rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 $W$，而 $N$ 只小猫的重量分别是 $C_1,C2,\dots C_N$。当然，每辆缆车上的小猫的重量之和不能超过 $W(1\le C_i,W \le 10^8)$。每租用一辆缆车，Freda 和 rainbow 就要付 $1$ 美元，所以他们想知道，最少需要付多少美元才能把这 $N$ 只小猫都运送下山？

inputFormat:
第一行包含两个用空格隔开的整数，$N$ 和 $W$。
接下来 $N$ 行每行一个整数，其中第 $i+1$ 行的整数表示第 $i$ 只小猫的重量 $C_i$。

outputFormat: 输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。


title: 送礼物

description: 作为惩罚，GY 被遣送去帮助某神牛给女生送礼物 (GY：貌似是个好差事）但是在 GY 看到礼物之后，他就不这么认为了。某神牛有 $N$ 个礼物，且异常沉重，但是 GY 的力气也异常的大 (-_-b)，他一次可以搬动重量和在 $w$ 以下的任意多个物品。GY 希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。

inputFormat:
第一行两个整数，分别代表 $W$ 和 $N$。

以后 $N$ 行，每行一个正整数表示 $G_i$。

outputFormat: 仅一个整数，表示 GY 在他的力气范围内一次性能搬动的最大重量。


title: Booksort

description:
给定 $n$ 本书，编号为 $1 \sim n$。

在初始状态下，书是任意排列的。

在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。

我们的目标状态是把书按照 $1 \sim n$ 的顺序依次排列。

求最少需要多少次操作。

inputFormat:
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据包含两行，第一行为整数 $n$，表示书的数量。

第二行为 $n$ 个整数，表示 $1 \sim n$ 的一种任意排列。

同行数之间用空格隔开。

outputFormat:
每组数据输出一个最少操作次数。

如果最少操作次数大于或等于 $5$ 次，则输出 `5 or more`。

每个结果占一行。

tags: 启发式迭代加深搜索,IDA*


title: 阶乘分解

description: 给定整数 $N (3 \le N \le 10^6)$，试把阶乘 $N!$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $p_i$ 和 $c_i$ 即可。

inputFormat: 一个整数 $N$。

outputFormat: $N!$ 分解质因数后的结果，共若干行，每行一对 $p_i, c_i$，表示含有 $p_i^{c_i}$ 项。按照 $p_i$ 从小到大的顺序输出。


title: 石头游戏

description:
石头游戏在一个 $n$ 行 $m$ 列的网格上进行，每个格子对应一种操作序列，操作序列至多有 $10$ 种，分别用 $0 \sim 9$ 这 $10$ 个数字指明。

操作序列是一个长度不超过 $6$ 且循环执行、每秒执行一个字符的字符串。

每秒钟，所有格子同时执行各自操作序列里的下一个字符。

序列中的每个字符是以下格式之一：

  1. 数字 $0 \sim 9$：表示拿 $0 \sim 9$ 个石头到该格子。
  2. `NWSE`：表示把这个格子内所有的石头推到相邻的格子，`N` 表示上方，`W` 表示左方，`S` 表示下方，`E` 表示右方。
  3. `D`：表示拿走这个格子的所有石头。

给定每种操作序列对应的字符串，以及网格中每个格子对应的操作序列，求石头游戏进行了 $t$ 秒之后，石头最多的格子里有多少个石头。

在游戏开始时，网格是空的。

inputFormat:
第一行 $4$ 个整数 $n, m, t, act$。

接下来 $n$ 行，每行 $m$ 个字符，表示每个格子对应的操作序列。

最后 $act$ 行，每行一个字符串，表示从 $0$ 开始的每个操作序列。

outputFormat: 一个整数：游戏进行了 $t$ 秒之后，所有方格中石头最多的格子有多少个石头。

hint: 对于所有的测试数据， 满足 $1 \le m,n \le 8$，$1 \le t \le 10^8$，$1 \le act \le 10$。


title: 开关问题

description:
有 $N$ 个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。

你的目标是经过若干次开关操作后使得最后 $N$ 个开关达到一个特定的状态。

对于任意一个开关，最多只能进行一次开关操作。

你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）

inputFormat:
输入第一行有一个数 $K$，表示以下有 $K$ 组测试数据。

每组测试数据的格式如下：

第一行：一个数 $N$。

第二行：$N$ 个 $0$ 或者 $1$ 的数，表示开始时 $N$ 个开关状态。

第三行：$N$ 个 $0$ 或者 $1$ 的数，表示操作结束后 $N$ 个开关的状态。

接下来每行两个数 $I,J$，表示如果操作第 $I$ 个开关，第 $J$ 个开关的状态也会变化。

每组数据以 `0 0` 结束。

outputFormat:
每组数据输出占一行。

如果有可行方法，输出总数，否则输出 `Oh,it's impossible~!!` 。

hint: 对于所有测试数据，满足 $1 \le K \le 10$，$0 < N < 29$。


title: Rainbow的信号

description:
Freda 发明了传呼机之后，rainbow 进一步改进了传呼机发送信息所使用的信号。

由于现在是数字、信息时代，rainbow 发明的信号用 $N$ 个自然数表示。

为了避免两个人的对话被大坏蛋 VariantF 偷听，rainbow 把对话分成 $A、B、C$ 三部分，分别用 $a、b、c$ 三个密码加密。

现在 Freda 接到了 rainbow 的信息，她的首要工作就是解密。

Freda 了解到，这三部分的密码计算方式如下：

在 $1 \sim N$ 这 $N$ 个数中，等概率地选取两个数 $l、r$，如果 $l>r$，则交换 $l、r$。

把信号中的第 $l$ 个数到第 $r$ 个数取出来，构成一个数列 $P$。

$A$ 部分对话的密码是数列 $P$ 的 $xor$ 和的数学期望值，$xor$ 和就是数列 $P$ 中各个数异或之后得到的数； $xor$ 和的期望就是对于所有可能选取的 $l、r$，所得到的数列的 $xor$ 和的平均数。

$B$ 部分对话的密码是数列 $P$ 的 $and$ 和的期望，定义类似于 $xor$ 和。

$C$ 部分对话的密码是数列 $P$ 的 $or$ 和的期望，定义类似于 $xor$ 和。

请你帮忙计算这三个密码。

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

第二行 $N$ 个自然数，表示 Freda 接到的信号。

outputFormat: 一行三个实数，分别表示 $xor$ 和、$and$ 和、$or$ 和的期望，四舍五入保留 $3$ 位小数，相邻两个实数之间用一个空格隔开。


title: 楼兰图腾

description:
在完成了分配任务之后，西部 314 来到了楼兰古城的西部。相传很久以前这片土地上（比楼兰古城还早）生活着两个部落，一个部落崇拜尖刀（`V`），一个部落崇拜铁锹（`∧`），他们分别用 `V` 和 `∧` 的形状来代表各自部落的图腾。

西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 $N$ 个点，经测量发现这 $N$ 个点的水平位置和竖直位置是两两不同的。西部 314 认为这幅壁画所包含的信息与这 $N$ 个点的相对位置有关，因此不妨设坐标分别为 $(1,y_1),(2,y_2),\cdots,(n,y_n)$，其中 $y_1\sim y_n$ 是 $1$ 到 $n$ 的一个排列。

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

如图，图中的 $y_1=1$，$y_2=5$，$y_3=3$，$y_4=2$，$y_5=4$。

西部 314 打算研究这幅壁画中包含着多少个图腾，其中 `V` 图腾的定义如下（注意：图腾的形式只和这三个纵坐标的相对大小排列顺序有关）$1\le i<j<k\le n$ 且 $y_i>y_j$, $y_j<y_k$；

而崇拜 `∧` 的部落的图腾被定义为 $1\le i<j<k\le n$ 且 $y_i<y_j$，$y_j>y_k$；

西部 314 想知道，这 $n$ 个点中两个部落图腾的数目。因此，你需要编写一个程序来求出 `V` 的个数和 `∧` 的个数。

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

第二行是 $n$ 个正整数，分别代表 $y_1,y_2,\cdots,y_n$。

outputFormat: 输出两个数，中间用空格隔开，依次为 `V` 的个数和 `∧` 的个数


title: 磁力块

description:
在一片广袤无垠的原野上，散落着 $N$ 块磁石。

每个磁石的性质可以用一个五元组 $(x,y,m,p,r)$ 描述，其中 $x,y$ 表示其坐标，$m$ 是磁石的质量，$p$ 是磁力，$r$ 是吸引半径。

若磁石 $A$ 与磁石 $B$ 的距离不大于磁石 $A$ 的吸引半径，并且磁石 $B$ 的质量不大于磁石 $A$ 的磁力，那么 $A$ 可以吸引 $B$。

小取酒带着一块自己的磁石 $L$ 来到了这片原野的 $(x_0,y_0)$ 处，我们可以视磁石 $L$ 的坐标为 $(x_0,y_0)$。

小取酒手持磁石 $L$ 并保持原地不动，所有可以被 $L$ 吸引的磁石将会被吸引过来。

在每个时刻，他可以选择更换任意一块自己已经获得的磁石（当然也可以是自己最初携带的 $L$ 磁石）在 $(x_0,y_0)$ 处吸引更多的磁石。

小取酒想知道，他最多能获得多少块磁石呢？

inputFormat:
第一行五个整数 $x_0,y_0,p_L,r_L,N$，表示小取酒所在的位置，磁石 $L$ 磁力、吸引半径和原野上散落磁石的个数。

接下来 $N$ 行每行五个整数 $x,y,m,p,r$，描述一块磁石的性质。

outputFormat: 输出一个整数，表示最多可以获得的散落磁石个数（不包含最初携带的磁石 $L$）。


title: LCIS【数据暂时有误】

description:
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。

小沐沐说，对于两个串 $A$，$B$，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

inputFormat:
第一行 $N$，表示 $A$，$B$ 的长度。

第二行，串 $A$。

第三行，串 $B$。

outputFormat: 输出长度。

hint: $1\le N \le 3000$，$A$，$B$ 中的数字不超过 maxlongint


title: 正整数拆分

description:
给定一个正整数 $N$，要求把 $N$ 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

**注意**:

  * 拆分方案不考虑顺序；
  * 至少拆分成 $2$ 个数的和。

求拆分的方案数 $\bmod 2147483648$ 的结果。

inputFormat: 一个正整数 $N$。

outputFormat: 输出一个整数，表示结果。


title: 金字塔

description:
虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。

经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。

首先，金字塔由若干房间组成，房间之间连有通道。

如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。

并且，每个房间的墙壁都涂有若干种颜色的一种。

探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。

这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。

机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。

最后，机器人会从入口退出金字塔。

显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。

但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。

现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。

因为结果可能会非常大，你只需要输出答案对$10^9$ 取模之后的值。

inputFormat: 输入仅一行，包含一个字符串 $S$，长度不超过 $300$，表示机器人得到的颜色序列。

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


title: 环路运输

description:
在一条环形公路旁均匀地分布着 $N$ 座仓库，编号为 $1 \sim N$，编号为 $i$ 的仓库与编号为 $j$ 的仓库之间的距离定义为 $dist(i,j)=\min(|i-j|,N-|i-j|)$，也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。

每座仓库都存有货物，其中编号为 $i$ 的仓库库存量为 $A_i$。

在 $i$ 和 $j$ 两座仓库之间运送货物需要的代价为 $A_i+A_j+dist(i,j)$。

求在哪两座仓库之间运送货物需要的代价最大。

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

第二行包含 $N$ 个整数 $A_1 \sim A_N$。

outputFormat: 输出一个整数，表示最大代价。


title: 启示录

description:
古代人认为 $666$ 是属于魔鬼的数。

不但如此，只要某数字的十进制表示中有三个连续的 $6$，古代人也认为这是个魔鬼的数，比如 $666,1666,6663,16666,6660666$ 等等。

古代典籍中经常用“第 $X$ 小的魔鬼的数”来指代这些数，这给研究人员带来了极大的不便。

现在请编写一个程序，可以实现输入 $X$，输出对应的魔鬼数。

inputFormat:
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组测试数据占一行，包含一个整数 $X$。

outputFormat: 每组测试数据占一行，输出一个魔鬼数。


title: 月之谜【数据疑似有误】

description:
如果一个十进制数能够被它的各位数字之和整除，则称这个数为“月之数”。

给定整数 $L$ 和 $R$，你需要计算闭区间 $[L,R]$ 中有多少个“月之数”。

inputFormat: 多组测试数据，每组输入占一行，包含两个整数 $L$ 和 $R$。

outputFormat: 每组数据输出一行一个整数，表示月之数的个数。


title: Sightseeing trip

description:
There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place.  Your task is to write a program which finds such a route.

In the town there are $N$ crossing points numbered from $1$ to $N$ and $M$ two-way roads numbered from $1$ to $M$.  Two crossing points can be connected by multipleroads, but no road connects a crossing point with itself.  Each sightseeingroute is a sequence of road numbers $y_1$, ..., $y_k$, $k>2$. The road $y_i(1\le i\le k-1)$ connects crossing points $x_i$ and $x_{i+1}$, the road $y_k$ connectscrossing points $x_k$ and $x_1$. All the numbers $x_1$,...,$x_k$ should be different.The length of the sightseeing route is the sum of the lengths of all roads onthe sightseeing route, i.e. $L(y_1)+L(y_2)+$...$+L(y_k)$ where $L(y_i)$ is thelength of the road $y_i (1\le i\le k)$.  Your program has to find such a sightseeingroute, the length of which is minimal, or to specify that it is not possible, because there is no sightseeing route in the town.

inputFormat: The first line of input file TRIP. IN contains two positive integers: the number of crossing points $N \le 100$ and the number of roads $M\le 10000$. Each of the next $M$ lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than $500$).

outputFormat: There is only one line in output file TRIP.OUT. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers $x_1$ to $x_k$ from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.

translation:
### 题目描述

在桑给巴尔岛的阿德尔顿镇，有一家旅行社。除了许多其他景点外，这家旅行社决定为其客户提供该镇的观光旅游。为了从这个项目中获得尽可能多的收益，旅行社做出了一个精明的决定：需要找到一条始于同一地点并结束于同一地点的最短路线。你的任务是编写一个程序来找到这样的一条路线。

在该镇有 $N$ 个编号为 1 到 $N$ 的交叉点，以及 $M$ 条编号为 1 到 $M$ 的双向道路。两个交叉点可以通过多条道路连接，但没有道路连接同一个交叉点。每条观光路线是由道路编号 $y_1$, ..., $y_k$ 组成的序列，其中 $k > 2$。道路 $y_i (1 \le i \le k-1)$ 连接交叉点 $x_i$ 和 $x_{i+1}$，道路 $y_k$ 连接交叉点 $x_k$ 和 $x_1$。所有的交叉点编号 $x_1$, ..., $x_k$ 应该是不同的。观光路线的长度是该路线所有道路长度的总和，即 $L(y_1)+L(y_2)+...+L(y_k)$，其中 $L(y_i)$ 是道路 $y_i (1 \le i \le k)$ 的长度。你的程序需要找到这样一条观光路线，使其长度最小，或者指明不可能找到这样的路线，因为该镇中没有任何观光路线。

### 输入格式

输入第一行包含两个正整数：交叉点的数量 $N \le 100$ 和道路的数量 $M \le 10000$。接下来的 $M$ 行每行描述一条道路。每行包含三个正整数：第一个交叉点的编号，第二个交叉点的编号，以及道路的长度（小于 500 的正整数）。

### 输出格式

输出只有一行。如果没有任何观光路线，则输出字符串 “No solution.”；否则，输出最短观光路线中所有交叉点的编号，按通过的顺序排列（即从定义中的 $x_1$ 到 $x_k$），编号之间用单个空格分隔，**行末不应有多余空格或者换行符**。如果有多个长度相同的观光路线，可以输出其中任意一条。


title: 走廊泼水节

description:
给定一棵 $N$ 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

**注意：** 树中的所有边权均为整数，且新加的所有边权也必须为整数。

inputFormat:
第一行包含整数 $t$，表示共有 $t$ 组测试数据。

对于每组测试数据，第一行包含整数 $N$。

接下来 $N-1$ 行，每行三个整数 $X,Y,Z$，表示 $X$ 节点与 $Y$ 节点之间存在一条边，长度为 $Z$。

outputFormat:
每组数据输出一个整数，表示权值总和最小值。

每个结果占一行。

hint: 数据保证，$1\leq t\leq 10$，$1 \le N \le 6000$，$1 \le Z \le 100$。


title: 黑暗城堡

description:
在顺利攻破 Lord lsp 的防线之后，lqr 一行人来到了 Lord lsp 的城堡下方。

Lord lsp 黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。

现在 lqr 已经搞清楚黑暗城堡有 $N$ 个房间，$M$ 条可以制造的双向通道，以及每条通道的长度。

lqr 深知 Lord lsp 的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp 一定会把城堡修建成树形的。

但是，为了尽量提高自己的移动效率，Lord lsp 一定会使得城堡满足下面的条件：

设 $D[i]$ 为如果所有的通道都被修建，第 $i$ 号房间与第 $1$ 号房间的最短路径长度；而 $S[i]$ 为实际修建的树形城堡中第 $i$ 号房间与第 $1$ 号房间的路径长度；要求对于所有整数 $i$，有 $S[i]=D[i]$ 成立。

为了打败 Lord lsp，lqr 想知道有多少种不同的城堡修建方案。

保证至少存在一种可行的城堡修建方案。

你需要输出答案对 $2^{31}–1$ 取模之后的结果。

inputFormat:
第一行有两个整数 $N$ 和 $M$。

之后 $M$ 行，每行三个整数 $X，Y$ 和 $L$，表示可以修建 $X$ 和 $Y$ 之间的一条长度为 $L$ 的通道。

outputFormat: 一个整数，表示答案对 $2^{31}–1$ 取模之后的结果。


title: 异象石

description:
Adera 是 Microsoft 应用商店中的一款解谜游戏。

异象石是进入 Adera 中异时空的引导物，在 Adera 的异时空中有一张地图。

这张地图上有 $N$ 个点，有 $N-1$ 条双向边把它们连通起来。

起初地图上没有任何异象石，在接下来的 $M$ 个时刻中，每个时刻会发生以下三种类型的事件之一：

  1. 地图的某个点上出现了异象石（已经出现的不会再次出现）；
  2. 地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
  3. 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。

请你作为玩家回答这些问题。

inputFormat:
第一行有一个整数 $N$，表示点的个数。

接下来 $N-1$ 行每行三个整数 $x,y,z$，表示点 $x$ 和 $y$ 之间有一条长度为 $z$ 的双向边。

第 $N+1$ 行有一个正整数 $M$。

接下来 $M$ 行每行是一个事件，事件是以下三种格式之一：

  * `+ x` 表示点 $x$ 上出现了异象石
  * `- x` 表示点 $x$ 上的异象石被摧毁
  * `?` 表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

outputFormat: 对于每个 `?` 事件，输出一个整数表示答案。

hint: 数据保证，$1 \le N,M \le 10^5$，$1 \le x,y \le N$，$x \neq y$，$1 \le z \le 10^9$。


title: 闇の連鎖

description:
传说中的暗之连锁被人们称为 Dark。

Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。

经过研究，你发现 Dark 呈现无向图的结构，图中有 $N$ 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。

Dark 有 $N - 1$ 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。

另外，Dark 还有 $M$ 条附加边。

你的任务是把 Dark 斩为不连通的两部分。

一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。

一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。

但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。

注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

inputFormat:
第一行包含两个整数 $N$ 和 $M$。

之后 $N - 1$ 行，每行包括两个整数 $A$ 和 $B$，表示 $A$ 和 $B$ 之间有一条主要边。

之后 $M$ 行以同样的格式给出附加边。


title: Freda的传呼机

description:
为了随时与 rainbow 快速交流，Freda 制造了两部传呼机。

Freda 和 rainbow 所在的地方有 $N$ 座房屋、$M$ 条双向光缆。

每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费 $t$ 单位时间。

现在 Freda 要进行 $Q$ 次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。

$N$ 座房屋通过光缆一定是连通的，并且这 $M$ 条光缆有以下三类连接情况：

  * $A$：光缆不形成环，也就是光缆仅有 $N-1$ 条。
  * $B$：光缆只形成一个环，也就是光缆仅有 $N$ 条。
  * $C$：每条光缆仅在一个环中。

请你帮帮他们。

inputFormat:
第一行包含三个用空格隔开的整数，$N、M$ 和 $Q$。

接下来 $M$ 行每行三个整数 $x、y、t$，表示房屋 $x$ 和 $y$ 之间有一条传递时间为 $t$ 的光缆。

最后 $Q$ 行每行两个整数 $x、y$，表示 Freda 想知道在 $x$ 和 $y$ 之间传呼最少需要多长时间。

outputFormat: 输出 $Q$ 行，每行一个整数，表示 Freda 每次试验的结果。


title: 创世纪

description:
上帝手中有 $N$ 种世界元素，每种元素可以限制另外 $1$ 种元素，把第 $i$ 种世界元素能够限制的那种世界元素记为 $A[i]$。

现在，上帝要把它们中的一部分投放到一个新的空间中去建造世界。

为了世界的和平与安宁，上帝希望所有被投放的世界元素都至少有一个能够限制它的世界元素没有被投放。

上帝希望知道，在此前提下，他最多可以投放多少种世界元素？

inputFormat:
第一行是一个整数 $N$，表示世界元素的数目。

第二行有 $N$ 个整数 $A[1], A[2], \dots, A[N]$。$A[i]$ 表示第 $i$ 个世界元素能够限制的世界元素的编号。

outputFormat: 一个整数，表示最多可以投放的世界元素的数目。

hint: 数据保证，$1\le N \le 10^6$，$1 \le A[i] \le N$


title: 西瓜种植

background:
笨笨：小西瓜，小西瓜~

路人甲：不会呀，这西瓜明明就大着啊……

笨笨：那……大西瓜，大西瓜~

路人甲：这么快就改口了……

笨笨：西瓜西瓜~可爱的西瓜~

description:
  笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……

  笨笨在一番研究过后，得出了 $m$ 个结论，这 $m$ 个结论可以使他收获的西瓜最多。

  笨笨的结论是这样的：

  从西瓜地 $B$ 处到 $E$ 处至少要种植 $T$ 个西瓜，这个范围的收获就可以最大化。

  笨笨不想那么辛苦，所以他想种植的西瓜尽量少，而又满足每一个所得的结论。

inputFormat:
第一行两个数 $n$, $m$（$0<n \le 5000$，$0 \le m\le 3000$），表示笨笨的西瓜地长 $n$，笨笨得出 $m$ 个结论。

接下来 $m$ 行表示笨笨的 $m$ 个结论，每行三个数 $b$, $e$, $t$（$1 \le b\le e\le n$，$0 \le t\le e-b+1$）。

outputFormat: 输出笨笨最少需种植多少西瓜。

hint: 基本上来说，笨笨的西瓜地就是一条壮观的线……


title: 银河

description:
银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。

我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 $1$。

现在对于 $N$ 颗我们关注的恒星，有 $M$ 对亮度之间的相对关系已经判明。

你的任务就是求出这 $N$ 颗恒星的亮度值总和至少有多大。

inputFormat:
第一行给出两个整数 $N$ 和 $M$。

之后 $M$ 行，每行三个整数 $T, A, B$，表示一对恒星 $(A, B)$ 之间的亮度关系。恒星的编号从 $1$ 开始。

如果 $T = 1$，说明 $A$ 和 $B$ 亮度相等。
如果 $T = 2$，说明 $A$ 的亮度小于 $B$ 的亮度。
如果 $T = 3$，说明 $A$ 的亮度不小于 $B$ 的亮度。
如果 $T = 4$，说明 $A$ 的亮度大于 $B$ 的亮度。
如果 $T = 5$，说明 $A$ 的亮度不大于 $B$ 的亮度。

outputFormat:
输出一个整数表示结果。

若无解，则输出 $-1$。


title: 导弹防御塔

description:
Freda 的城堡遭受了 $M$ 个入侵者的攻击！

Freda 控制着 $N$ 座导弹防御塔，每座塔都有足够数量的导弹，但是每次只能发射一枚。

在发射导弹时，导弹需要 $T_1$ 秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要 $T_2$ 分钟来冷却。

所有导弹都有相同的匀速飞行速度 $V$，并且会沿着距离最短的路径去打击目标。

计算防御塔到目标的距离 $Distance$ 时，你只需要计算水平距离，而忽略导弹飞行的高度。

导弹在空中飞行的时间就是 $Distance/V$ 分钟，导弹到达目标后可以立即将它击毁。

现在，给出 $N$ 座导弹防御塔的坐标，$M$ 个入侵者的坐标，$T_1,T_2$ 和 $V$。

因为 Freda 的小伙伴 Rainbow 就要来拜访城堡了，你需要求出至少多少分钟才能击退所有的入侵者。

inputFormat:
第一行五个正整数 $N,M,T_1,T_2,V$。

接下来 $M$ 行每行两个整数，代表入侵者的坐标。

接下来 $N$ 行每行两个整数，代表防御塔的坐标。

outputFormat: 输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。与标准答案的差距相差不超过 $10^{-5}$ 即认为答案正确。

hint: 数据保证 $1 \le N,M \le 50$，坐标绝对值不超过 $10000$，$T_1,T_2,V$ 为不超过 $2000$ 的正整数。


title: 車的放置

description:
给定一个 $N$ 行 $M$ 列的棋盘，已知某些格子禁止放置。

问棋盘上最多能放多少个不能互相攻击的車。

車放在格子里，攻击范围与中国象棋的“車”一致。

inputFormat:
第一行包含三个整数 $N,M,T$，其中 $T$ 表示禁止放置的格子的数量。

接下来 $T$ 行每行包含两个整数 $x$ 和 $y$，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

保证禁止放置的格子互不相同。

outputFormat: 输出一个整数，表示结果。

hint: 数据保证，$1 \le N,M \le 200$。


title: Vani和Cl2捉迷藏

description:
Vani 和 cl2 在一片树林里捉迷藏。

这片树林里有 $N$ 座房子，$M$ 条有向道路，组成了一张有向无环图。

树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。

如果从房子 $A$ 沿着路走下去能够到达 $B$，那么在 $A$ 和 $B$ 里的人是能够相互望见的。

现在 cl2 要在这 $N$ 座房子里选择 $K$ 座作为藏身点，同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找，为了避免被 Vani 看见，cl2 要求这 $K$ 个藏身点的任意两个之间都没有路径相连。

为了让 Vani 更难找到自己，cl2 想知道最多能选出多少个藏身点。

inputFormat:
输入数据的第一行是两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行两个整数 $x,y$，表示一条从 $x$ 到 $y$ 的有向道路。

outputFormat: 输出一个整数，表示最多能选取的藏身点个数。


title: 骑士放置

description:
给定一个 $N \times M$ 的棋盘，有一些格子禁止放棋子。

问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。

inputFormat:
第一行包含三个整数 $N,M,T$，其中 $T$ 表示禁止放置的格子的数量。

接下来 $T$ 行每行包含两个整数 $x$ 和 $y$，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

outputFormat: 输出一个整数表示结果。


title: 舞动的夜晚

description:
$L$ 公司和 $H$ 公司举办了一次联谊晚会。

晚会上，$L$ 公司的 $N$ 位员工和 $H$ 公司的 $M$ 位员工打算进行一场交际舞。

在这些领导中，一些 $L$ 公司的员工和 $H$ 公司的员工之间是互相认识的，这样的认识关系一共有 $T$ 对。

舞会上，每位员工会尝试选择一名 Ta 认识的对方公司的员工作为舞伴，并且每位员工至多跳一支舞。

完成的交际舞的数量越多，晚会的气氛就越热烈。

顾及到晚会的气氛，员工们希望知道，哪些员工之间如果进行了交际舞，就会使整场晚会能够完成的交际舞的最大数量减小。

inputFormat:
第一行三个整数 $N、M、T$。

接下来 $T$ 行每行两个整数 $x、y$，表示 $L$ 公司的员工 $x$ 和 $H$ 公司的员工 $y$ 互相认识。

outputFormat:
第一行一个整数 $cnt$，表示进行了交际舞后会使整场晚会能够完成的交际舞的最大数量减小的员工有多少对。

第二行 $cnt$ 个整数，升序输出这样的一对员工的认识关系的编号（他们的认识关系是在输入数据中读入的第几条认识关系）。

如果 $cnt=0$，输出一个空行。

hint: 数据保证，$1 \le N,M \le 10000$，$1 \le T \le 100000$，$1 \le x \le N$，$1 \le y \le M$。


title: 奇数码问题

description:
你一定玩过八数码游戏，它实际上是在一个 $3 \times 3$ 的网格中进行的，$1$ 个空格和 $1 \sim 8$ 这 $8$ 个数字恰好不重不漏地分布在这 $3 \times 3$ 的网格中。

例如：

    5 2 8
    1 3 _
    4 6 7

在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。

例如在上例中，空格可与左、上、下面的数字交换，分别变成：

    5 2 8       5 2 _      5 2 8
    1 _ 3       1 3 8      1 3 7
    4 6 7       4 6 7      4 6 _

奇数码游戏是它的一个扩展，在一个 $n \times n$ 的网格中进行，其中 $n$ 为奇数，$1$ 个空格和 $1 \sim n^2-1$ 这 $n^2-1$ 个数恰好不重不漏地分布在 $n \times n$ 的网格中。

空格移动的规则与八数码游戏相同，实际上，八数码就是一个 $n=3$ 的奇数码游戏。

现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

inputFormat:
多组数据，对于每组数据：

第 $1$ 行输入一个整数 $n$，$n$ 为奇数。

接下来 $n$ 行每行 $n$ 个整数，表示第一个局面。

再接下来 $n$ 行每行 $n$ 个整数，表示第二个局面。

局面中每个整数都是 $0 \sim n^2-1$ 之一，其中用 $0$ 代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

outputFormat: 对于每组数据，若两个局面可达，输出 `TAK`，否则输出 `NIE`。


title: 货仓选址

description:
在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1 \sim A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

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

第二行 $N$ 个整数 $A_1 \sim A_N$。

outputFormat: 输出一个整数，表示距离之和的最小值。


title: [蓝桥杯 2024 省 A] 零食采购

description: 小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 $n$ 颗星球，由 $n-1$ 条航路连接为连通图，第 $i$ 颗星球卖第 $c_i$ 种零食特产。小蓝想出了 $q$ 个采购方案，第 $i$ 个方案的起点为星球 $s_i$ ，终点为星球 $t_i$ ，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。

inputFormat:
输入的第一行包含两个正整数 $n$，$q$，用一个空格分隔。
第二行包含 $n$ 个整数 $c_1,c_2,\cdots, c_n$，相邻整数之间使用一个空格分隔。
接下来 $n - 1$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，用一个空格分隔，表示一条
航路将星球 $u_i$ 与 $v_i$ 相连。
接下来 $q$ 行，第 $i$ 行包含两个整数 $s_i
, t_i $，用一个空格分隔，表示一个采购方案。

outputFormat: 输出 $q$ 行，每行包含一个整数，依次表示每个采购方案的答案。

hint:
第一个方案路线为 $\{4, 2, 1, 3\}$，可以买到第 $1, 2, 3$ 种零食；
第二个方案路线为 $\{1, 2, 4\}$，可以买到第 $1, 2$ 种零食。

对于 20% 的评测用例，$1 ≤ n, q ≤ 5000 $；
对于所有评测用例，$1 ≤ n, q ≤ 10^5，1 ≤ c_i ≤ 20，1 ≤ u_i
, v_i ≤ n，1 ≤ s_i
, t_i ≤ n$。


title: [蓝桥杯 2024 省 A] 成绩统计

description:
小蓝的班上有 $n$ 个人，一次考试之后小蓝想统计同学们的成绩，第 $i$ 名同学的成绩为 $a_i$。当小蓝统计完前 $x$ 名同学的成绩后，他可以从 $1 \sim x$ 中选出任意 $k$ 名同学的成绩，计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成
绩，才有可能选出 $k$ 名同学，他们的方差小于一个给定的值 $T$？
提示：$k$ 个数 $v_1, v_2, \cdots , v_k$ 的方差 $\sigma^2$ 定义为：$\sigma^2=\dfrac  {\sum_{i=1}^k(v_i-\bar v)^2} k$，其中 $\bar v$ 表示
$v_i$ 的平均值，$\bar v = \dfrac {\sum_{i=1}^k v_i} k$。

inputFormat:
输入的第一行包含三个正整数 $n, k, T $，相邻整数之间使用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1, a2, \cdots, a_n$ ，相邻整数之间使用一个空格分隔。

outputFormat: 输出一行包含一个整数表示答案。如果不能满足条件，输出 $-1$ 。

hint:
检查完前三名同学的成绩后，只能选出 $3, 2, 5 $，方差为 $1.56 $；

检查完前四名同学的成绩后，可以选出 $3, 2, 2 $，方差为 $0.22 < 1 $，所以答案为 $4 $。

对于 $10\%$ 的评测用例，保证 $1 ≤ n, k ≤ 10^2$；
对于 $30\%$ 的评测用例，保证 $1 ≤ n, k ≤ 10^3$ ；
对于所有评测用例，保证 $1 ≤ n, k ≤ 10^5 $，$1 ≤ T ≤ 2
^{31} -1 $，$1 ≤ a_i ≤ n $。


title: [LMXOI Round 2] Disaster

background: LMX 和 HQZ 在一起研究点的划分。

description:
给定 $n$ 个点，每个点给出了一组限制 $l_i,r_i(0 \le l_i < i < r_i \le n+1)$，定义一个划分是好的当且仅当对于每个点 $i$，$l_i,r_i$ 在划分后均不与 $i$ 在同一区间内，求好的划分的个数，答案对 $998244353$ 取模。

补充：在本题中，一组划分表示将 $n$ 个点分为若干个区间，使得每个点恰好在一个区间内，$l_i=0$ 和 $r_i=n+1$ 可以视为无限制。

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

接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$。

outputFormat: 第一行一个整数，表示答案对 $998244353$ 取模后的值。


title: [蓝桥杯 2024 省 A] 训练士兵

description:
在蓝桥王国中，有 $n$ 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 $i$ 名士兵来说，进行一次训练所需的成本为 $p_i$ 枚金币，而要想成为顶尖战士，他至少需要进行 $c_i$ 次训练。
为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 $S$ 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。
作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？

inputFormat:
输入的第一行包含两个整数 $n$ 和 $S $，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。
接下来的 $n$ 行，每行包含两个整数 $p_i$ 和 $c_i$，用一个空格分隔，表示第 $i$ 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。

outputFormat: 输出一行包含一个整数，表示使所有士兵成为顶尖战士所需的最少金币数。

hint:
花费金币最少的训练方式为：进行 $2$ 次组团训练，花费 $2 × 6 = 12$ 枚金币，此时士兵 $1, 3$ 已成为顶尖战士；再花费 $4$ 枚金币，让士兵 $2$ 进行两次训练，成为顶尖战士。总花费为 $12 + 4 = 16$。

对于 $40\%$ 的评测用例，$1 ≤ n ≤ 10^3，1 ≤ p_i
, c_i ≤ 10^5，1 ≤ S ≤ 10^7$。

对于所有评测用例，$1 ≤ n ≤ 10^5，1 ≤ p_i
, c_i ≤ 10^6，1 ≤ S ≤ 10^{10}$。


title: [蓝桥杯 2024 省 B] 拔河

description:
小明是学校里的一名老师，他带的班级共有 $n$ 名同学，第 $i$ 名同学力量值为 $a_i$。在闲暇之余，小明决定在班级里组织一场拔河比赛。

为了保证比赛的双方实力尽可能相近，需要在这 $n$ 名同学中挑选出两个队伍，队伍内的同学编号连续 $\{{a_{l_1}}, a_{l_1 + 1}, \dots, a_{r_1 - 1}, a_{r_1}\}$ 和 $\{{a_{l_2}}, a_{l_2 + 1}, \dots, a_{r_2 - 1}, a_{r_2}\}$，其中 $l_1 \le r_1<l_2 \le r_2$。

两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

inputFormat:
输入共两行。
第一行为一个正整数 $n$。
第二行为 $n$ 个正整数 $a_1, a_2, \dots a_n$。

outputFormat: 输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。


title: 【MX-X4-T3】「Jason-1」数对变换

description:
对于一个**正整数**数对 $(x, y)$，定义一次变换为：选择其中一个数 $a$，记另一个数为 $b$，同时选择一个正整数 $k \leq a$，然后将 $a$ 除以 $k$ 向下取整，同时将 $b$ 乘以 $k$。

形式化地说，对于数对 $(x,y)$，你可以执行以下两种变换：

- 类型 1：取 $1 \le k \le x$，令 $(x,y) \gets (\lfloor \frac{x}{k} \rfloor, y \cdot k)$。
- 类型 2：取 $1 \le k \le y$，令 $(x,y) \gets (x \cdot k, \lfloor \frac{y}{k} \rfloor)$。

显然，变换后的数对仍然是正整数数对。

给出两组正整数数对 $(a, b)$ 与 $(c, d)$，你需要执行**不超过 $\bm{65}$ 次**变换将 $(a, b)$ 变为 $(c, d)$，或者报告无解。**注意：你不需要最小化执行变换的次数**。

需要注意数对是有序的，即若 $x \neq y$，则 $(x,y) \neq (y,x)$。

本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。

inputFormat:
**本题输入包含多组数据。**

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

- 仅一行，四个正整数 $a, b, c, d$，表示两组数对。

outputFormat:
对于每组数据：

- 若无解，
	- 仅一行一个字符串 `-1`。
- 否则，
	- 第一行，一个非负整数 $m$，表示你执行变换的次数。**你需要保证 $\bm{0 \le m \le 65}$，但不需要最小化 $\bm m$**。
	- 接下来 $m$ 行，第 $i$ 行两个整数 $\mathit{op}, k$，表示你执行的第 $i$ 次变换。其中 $\mathit{op} \in \{1, 2\}$ 表示变换类型，$k$ 即为本次变换中选择的 $k$。

本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。


title: [蓝桥杯 2024 省 B] 填空问题

description:
## 试题 A: 握手问题

### 【问题描述】
小蓝组织了一场算法交流会议，总共有 $50$ 人参加了本次会议。在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手（且仅有一次）。但有 $7$ 个人，这 $7$ 人彼此之间没有进行握手（但这 $7$ 人与除这 $7$ 人以外的所有人进行了握手）。请问这些人之间一共进行了多少次握手？

注意 $A$ 和 $B$ 握手的同时也意味着 $B$ 和 $A$ 握手了，所以算作是一次握手。

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B: 小球反弹

### 【问题描述】
有一长方形，长为 $343720$ 单位长度，宽为 $233333$ 单位长度。在其内部左上角顶点有一小球（无视其体积），其初速度如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 $dx : dy = 15 : 17$。小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速
率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍五入保留两位小数。

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

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个小数，在提交答案时只填写这个小数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。
```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2024 省 A] 封印宝石

description:
在一次探险中，勇者小蓝发现了 $n$ 颗闪烁着奇异光芒的宝石，每颗宝石都蕴含着魔法能量，分别记作 $a_1, a_2,\cdots, a_n$。小蓝计划用 $n$ 个特制的魔法盒子来封
印这些宝石，防止其魔法能量被滥用。
封印宝石会消耗小蓝的体力，具体地，将第 $i$ 颗宝石放入第 $j$ 个盒子会消耗小蓝 $i - j$ 点体力（注：需满足 $j ≤ i$ 才能将第 $i$ 颗宝石放入第 $j$ 个盒子进行有效的封印）。小蓝也可以选择将魔法盒留空，以保存体力供后续使用。
此外，为了避免魔力相冲，每个盒子最多存放一颗宝石（每个宝石也只能放进一个盒子），且任意两个相邻盒子不能存放魔力值相同的宝石，相邻的盒子允许同时为空。
小蓝初始的体力值为 $k$。在不超出体力限制的条件下，小蓝希望找出一种宝石的放置方法，使得宝石的魔力值在这 $n$ 个盒子中的排列顺序具有最大的字典序（注：未放置宝石的盒子在此序列中记为 $-1$）。
作为勇者小蓝的追随者，请你帮他找出这一放置宝石的方法。

**字典序的解释**： 在本题中，字典序的大小是按照宝石的魔力值进行比较的。对于两个长度同为 $L$ 的魔力值序列 $a$ 和 $b$，如果存在一个位置 $i$，使得 $a_j = b_j$ 对所有 $1 ≤ j < i$ 成立，但是 $a_i < b_i$，则序列 $a$ 在字典序上小于序列 $b$。
反之，如果 $a_i > b_i$，则序列 $a$ 在字典序上大于序列 $b$。如果不存在这样的 $i$，则序列 $a$ 和序列 $b$ 的字典序相等。

inputFormat:
输入的第一行包含两个整数 $n$ 和 $k $，用一个空格分隔，分别表示宝石的数量和小蓝的初始体力值。
第二行包含 $n$ 个整数 $a_1, a_2,\cdots , a_n $，相邻整数之间使用一个空格分隔，分别表示每颗宝石的魔法能量值。

outputFormat: 输出一行包含 $n$ 个整数，相邻整数之间使用一个空格分隔，表示每个魔法盒中宝石的魔法能量值。如果某个魔法盒为空，则对应位置输出 $-1$。

hint:
在开始放置宝石之前，体力为 $3$，宝石在盒子中的排列为 $[-1, -1, -1]$。
1. 将第 $2$ 个宝石放进第 $1$ 个盒子，得到 $[3, -1, -1]$，体力剩余 $2$。
2. 将第 $3$ 个宝石放进第 $2$ 个盒子，得到 $[3, 2, -1]$，体力剩余 $1$。

最后宝石在盒子中的排列为 $[3, 2, −1]$。显然，没有比这更优的放置方法。

对于 $20\%$ 的评测用例，$1 ≤ n ≤ 5 × 10^3 ，0 ≤ k ≤ 3 × 10^6 ，1 ≤ a_i ≤ 10^5$。
对于所有评测用例，$1 ≤ n ≤ 10^5 ，0 ≤ k ≤ 10^9 ，1 ≤ a_i ≤ 10^9$。


title: [蓝桥杯 2024 省 A] 因数计数

description:
小蓝随手写出了含有 $n$ 个正整数的数组 $\{a_1, a_2,\cdots, a_n\}$，他发现可以轻松地算出有多少个有序二元组 $(i, j)$ 满足 $a_j$ 是 $a_i$ 的一个因数。因此他定义一个整数对 $(x_1, y_1)$ 是一个整数对 $(x_2, y_2)$ 的“因数”当且仅当 $x_1$ 和 $y_1$ 分别是 $x_2$ 和 $y_2$ 的因数。他想知道有多少个有序四元组 $(i, j, k, l)$ 满足 $(a_i
, a_j)$ 是 $(a_k, a_l)$ 的因数，其中 $i, j, k, l$ 互不相等。

inputFormat:
输入的第一行包含一个正整数 $n$。
第二行包含 $n$ 个正整数 $a_1, a_2,\cdots, a_n $，相邻整数之间使用一个空格分隔。

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


title: [蓝桥杯 2024 省 B] 好数

description:
一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位……）上的数字是奇数，偶数位（十位、千位、十万位……）上的数字是偶数，我们就称之为“好数”。

给定一个正整数 $N$，请计算从 $1$ 到 $N$ 一共有多少个好数。

inputFormat: 一个整数 $N$。

outputFormat: 一个整数代表答案。


title: 「ALFR Round 2」B 篮球比赛

description:
小山即将参加 $n$ 场篮球比赛，他有一个多项式函数 $f(x)=a_0+a_1x^1+a_2x^2+\dots+a_kx^k$ 与 $m$ 个和为 $1$ 的数 $p_1,p_2,p_3,\dots,p_m$。

他所在的球队有 $\dfrac{f(i)}{\sum_{j=1}^n f(j)}$ 的概率在第 $i$ 场比赛中取得**第一次**胜利，这意味着前面的 $i-1$ 场都输了。

接下来，如果第 $i$ 场比赛中小山所在球队取得了胜利，则对于 $1\le j\le m$，他们有 $p_j$ 的概率在第 $i+j$ 场比赛取得下一次胜利，这意味着如果 $j\gt1$，第 $i+1$ 场到第 $i+j-1$ 场都输了（若 $i+j>n$，则之后的比赛都输，没有再胜利）。

小山想知道他所在球队的期望胜利场数，你能帮帮他吗？

注意：在计算时，如果遇到分数（比如 $\dfrac{f(i)}{\sum_{j=1}^n f(j)}$），应使用分数取模形式。如果不知道什么是分数取模形式，参见 [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。

为了方便你的计算，输入数据将直接给出 $p_i,a_i$ 对 $998244353$ 取模的结果。

inputFormat:
第一行 $3$ 个整数 $n, m, k$，含义如上所述。

第二行 $m$ 个整数，第 $i$ 个整数表示 $p_i$ 模 $998244353$ 的值。

第三行 $k + 1$ 个整数，第 $i$ 个整数表示 $a_{i - 1}$ 模 $998244353$ 的值。

**注意是先输入 $p$ 再输入 $a$。**

outputFormat: 一行一个数，表示答案模 $998244353$ 的值。


title: [蓝桥杯 2024 省 B] R 格式

description:
小蓝最近在研究一种浮点数的表示方法：$R$ 格式。对于一个大于 $0$ 的浮点数 $d$，可以用 $R$ 格式的整数来表示。给定一个转换参数 $n$，将浮点数转换为 $R$ 格式整数的做法是：
1. 将浮点数乘以 $2^n$。
2. 四舍五入到最接近的整数。

inputFormat: 一行一个整数 $n$ 和一个浮点数 $d$。

outputFormat: 一行一个整数表示 $d$ 用 $R$ 格式表示出的值。

hint:
### 样例 1 解释

$3.14 \times 2^2 = 12.56$，四舍五入后为 $13$。

### 数据规模与约定

用 $t$ 表示将 $d$ 视为字符串时的长度。

- 对于 $50\%$ 的数据，保证 $n \le 10$，$t \le 15$。
- 对于全部的测试数据，保证 $1 \le n \le 1000$，$1 \le t \le 1024$，保证 $d$ 是小数，即包含小数点。


title: [洛谷 202406GESP 模拟 二级] 小洛的田字矩阵

type: B

description:
小洛想要构造一个 $N\times N$  的田字矩阵（$N$ 为奇数）。具体来说：

- 这个矩阵共有 $N$ 行，每行 $N$ 个字符，其中最左列、最右列都是 `|`；
- 第一行、最后一行的第 $2\sim N-1$ 个字符都是 `-`；
- 中间一行（即第 $\frac{N+1}{2}$ 行）的第 $2\sim \frac{N-1}{2}$，$\frac{N+3}{2}\sim N-1$ 个字符都是 `-`；
- 中间一列（即第 $\frac{N+1}{2}$ 列）的第 $2\sim \frac{N-1}{2}$，$\frac{N+3}{2}\sim N-1$ 个字符都是 `|`。
- 其余所有字符都是半角小写字母 `x` 。

例如，一个 $N = 5$ 田字矩阵如下:

```
|---|
|x|x|
|-x-|
|x|x|
|---|
```

请你帮小洛根据给定的 $N$ 打印出对应的“田字矩阵”。

inputFormat: 一行一个整数 $N$（$5\leq N \leq 49$，保证 $N$ 为奇数）。

outputFormat:
输出对应的“田字矩阵”。

请严格按格式要求输出，不要擅自添加任何空格、标点、空格等任何符号。你应该恰好输出 $N$ 行，每行除了换行符外恰好包含 $N$ 个字符，这些字符要么是 `-`，要么是 `|`，要么是 `x`。**你的输出必须和标准答案完全一致才能得分，请在提交前仔细检查**。


title: [蓝桥杯 2023 国 A] 圆上的连线

description:
给定一个圆，圆上有 $n=2023$ 个点从 $1$ 到 $n$ 依次编号。

问有多少种不同的连线方式，使得完全没有连线相交。当两个方案连线的数量不同或任何一个点连接的点在另一个方案中编号不同时，两个方案视为不同。

答案可能很大，请将答案对 $2023$ 求余后提交。

inputFormat: 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。


title: [蓝桥杯 2023 国 A] 2023 次方

description:
求 $2^{(3^{(4^{(\ldots ^{2023}})})}$ 的值对 $2023$ 取模的结果。

注: 上式都是指数，可写为 $2** (3**(4**(\ldots 2023\ldots))$ 其中 $**$ 表示指数。

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。


title: [蓝桥杯 2023 国 A] 切割

background: 数据提供：<https://www.luogu.com.cn/discuss/838792>

description: 给定一个 $W\times H$ 的长方形，两边长度均为整数。小蓝想把它切割为很多个边长为整数的小正方形。假设切割没有任何损耗，正方形的边长至少为 $2$，不允许出现余料，要求所有正方形的大小相等，请问最多能切割出多少个?

inputFormat: 输入一行，包含两个整数 $W, H$，用一个空格分隔。

outputFormat: 输出一行包含一个整数表示答案。如果不存在满足要求的方案，输出 $0$。

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

切割成 $5\times 10=50$ 个边长为 $2$ 的正方形。

**【评测用例规模与约定】**

对于 $30\%$ 的评测用例，$1\le W,H\le 1000$；
对于 $60\%$ 的评测用例，$1\le W,H\le 10^6$；
对于所有评测用例，$1\le W,H\le 10^9$。


title: [蓝桥杯 2023 国 A] XYZ

description: 给定一个区间 $[L,R]$，请求出有多少组 $X,Y,Z$ 满足 $X+Y=Z$ 且 $L\le X,Y,Z\le R$。

inputFormat:
本题包含多组询问。

输入的第一行包含一个整数 $T$ 表示询问组数。

接下来 $T$ 行，每行包含两个整数 $L_i,R_i$，用一个空格分隔，表示一组询问。

outputFormat: 输出 $T$ 行，每行包含一个整数，表示满足条件的 $X,Y,Z$ 的组数。


title: [蓝桥杯 2023 国 A] 第 K 小的和

description:
给定两个序列 $A,B$，长度分别为 $n,m$。

设另有一个序列 $C$ 中包含了 $A,B$ 中的数两两相加的结果 ($C$ 中共有 $n\times m$ 个数)。问 $C$ 中第 $K$ 小的数是多少。请注意重复的数需要计算多次。例如 $1,1,2,3$ 中，最小和次小都是 $1$，而 $3$ 是第 $4$ 小。

inputFormat:
输入的第一行包含三个整数 $n,m,K$，相邻两个整数之间使用一个空格分隔。

第二行包含 $n$ 个整数，分别表示 $A_1,A_2,\ldots,A_n$，相邻两个整数之间使用一个空格分隔。

第三行包含 $m$ 个整数，分别表示 $B_1,B_2,\ldots,B_m$，相邻两个整数之间使用一个空格分隔。

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

hint:
**【评测用例规模与约定】**

- 对于 $40\%$ 的评测用例，$n,m\le 5000$，$A_i,B_i\le 1000$;
- 对于所有评测用例，$1\le n,m\le 10^5$，$1\le A_i,B_i\le 10^9$，$1\le K\le n\times m$。


title: [蓝桥杯 2023 国 A] 相连的边

description: 给定一棵包含 $n$ 个结点的树，找出 $3$ 条边使得这三条边的端点仅经过这三条边即可互相到达且三条边的长度和尽可能大。

inputFormat:
输入第一行包含一个整数 $n$ 表示树的结点数。

接下来 $n−1$ 行，每行包含两个整数，用一个空格分隔。其中第 $i$ 行的两个数 $x_i,y_i$，表示编号为 $i+1$ 和 $x_i$ 的结点之间有一条长度为 $y_i$ 的边。

outputFormat: 输出一行，包含一个整数表示满足要求的三条边的长度之和的最大值。

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

结点 $2$ 和结点 $1$ 的边长为 $1$，结点 $3$ 和结点 $2$ 的边长为 $1$，结点 $4$ 和结点 $3$ 的边长为 $7$，结点 $5$ 和结点 $1$ 的边长为 $10$。

**【评测用例规模与约定】**

对于 $20\%$ 的评测用例，$4\le n\le 300$；
对于 $40\%$ 的评测用例，$4\le n\le 5000$；
对于所有评测用例，$4\le n\le 2\times 10^5$，$1\le x_i<i$，$1\le y_i\le 10^9$。


title: [蓝桥杯 2023 国 A] 01 游戏

description:
小蓝最近玩上了 $01$ 游戏，这是一款带有二进制思想的棋子游戏，具体来说游戏在一个大小为 $N\times N$ 的棋盘上进行，棋盘上每个位置都需要放置一位数字 $0$ 或者数字 $1$，初始情况下，棋盘上有一部分位置已经被放置好了固定的数字，玩家不可以再进行更改。玩家需要在其他所有的空白位置放置数字，并使得最终结果满足以下条件：

1. 所有的空白位置都需要放置一个数字 $0/1$；
2. 在水平或者垂直方向上，相同的数字不可以连续出现大于两次；
3. 每一行和每一列上，数字 $0$ 和数字 $1$ 的数量必须是相等的 (例如 $N=4$，则表示每一行/列中都需要有 $2$ 个 $0$ 和 $2$ 个 $1$)；
4. 每一行都是唯一的，因此每一行都不会和另一行完全相同；同理每一列也都是唯一的，每一列都不会和另一列完全相同。

现在请你和小蓝一起解决 $01$ 游戏吧！题目保证所有的测试数据都拥有一个唯一的答案。

inputFormat:
输入的第一行包含一个整数 $N$ 表示棋盘大小。

接下来 $N$ 行每行包含 $N$ 个字符，字符只可能是 `0`、`1`、`_` 中的其中一个 (ASCII 码分别为 $48$，$49$，$95$)，`0` 表示这个位置数字固定为 $0$，`1` 表示这个位置数字固定为 $1$，`_` 表示这是一个空白位置，由玩家填充。

outputFormat: 输出 $N$ 行每行包含 $N$ 个字符表示题目的解，其中的字符只能是 `0` 或者 `1`。

hint:
**【评测用例规模与约定】**

对于 $60\%$ 的评测用例，$2\le N\le 6$;
对于所有评测用例，$2\le N\le 10$，$N$ 为偶数。

感谢 @rui_er 提供测试数据。


title: [蓝桥杯 2024 省 B] 宝石组合

description:
在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 $n$ 枚宝石，第 $i$ 枚宝石的 “闪亮度” 属性值为 $H_i$，小蓝将会从这 $n$ 枚宝石中选出三枚进行组合，组合之后的精美程度 $S$ 可以用以下公式来衡量：

$$
S = H_a H_b H_c \cdot \frac{\operatorname{LCM}(H_a, H_b, H_c)}{\operatorname{LCM}(H_a, H_b) \cdot\operatorname{LCM}(H_a, H_c) \operatorname{LCM}(H_b, H_c)}
$$

其中 $\operatorname{LCM}$ 表示的是最小公倍数函数。

小蓝想要使得三枚宝石组合后的精美程度 $S$ 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 $S$ 值相同，优先选择按照 $H$ 值升序排列后字典序最小的方案。

inputFormat:
第一行一个整数 $n$ 表示宝石个数。
第二行有 $n$ 个整数 $H_1, H_2, \dots H_n$ 表示每个宝石的闪亮度。

outputFormat: 输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

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

- 对 $30\%$ 的数据，$n \leq 100$，$H_i \leq 10^3$。
- 对 $60\%$ 的数据，$n \leq 2 \times 10^3$。
- 对全部的测试数据，保证 $3 \leq n \leq 10^5$，$1 \leq H_i \leq 10^5$。


title: 【MX-X4-T7】「Jason-1」Ball

description:
**这是一道提交答案题。**

你有 $10$ 个盒子，每个任务会给出一个 $n$，初始时前 $n$ 个盒子内**可能**有一些球，后 $10-n$ 个盒子为空。

用小写字母表示每种颜色的球，初始时最多只有三种颜色的球，分别用 $\tt a, b, c$ 表示。而在程序中，你可以使用**任何小写字母**表示对应颜色的球。

定义一个盒子**包含**一个字符串，表示对于每种颜色的球，盒子中出现的个数不小于字符串中出现的个数。

从一个盒子中**删除**一个字符串，表示对于字符串中每一个小写字母代表的球，从盒子中取走一个相同颜色的球。删除的前提是需要满足此盒子包含该字符串。

向一个盒子中**放入**一个字符串，表示对于字符串中每一个小写字母代表的每个球，向盒子中放入一个相同颜色的球。

你需要写一个程序完成一些任务，程序包含下面几种语句可供使用：

- `change x s y t`，其中 $x, y$ 是不超过 $10$ 的非负整数，$s, t$ 是仅由小写字母或单个字符 `@` 组成的**非空**字符串（**如果为 `@` 则表示将该字符串视作空串**）。如果 $x$ 为 $0$，则将 $k$ 由 $1$ 遍历到 $10$，否则 $k = x$。如果盒子 $k$ 中包含字符串 $s$，从其中删除 $s$，并在盒子 $y$ 中放入字符串 $t$，如果 $y=0$ 则在当前的 $k$ 中（原地）放入，这样就视为成功执行命令。每当成功执行命令后，立刻回到上一个断点，无论 $k$ 是否完全遍历。如果没有成功执行命令，跳转到下一条语句。
- `#` 表示一个断点。**你必须以一行断点结束整个程序**。认为第 $0$ 行也是一个断点，此断点不计入代价。

**语句数**可简单地视为程序中 `change` 和 `#` 的数量之和，第 $0$ 行的虚拟断点不计入，最后一行的断点计入。

**断点数**可简单地视为程序中 `#` 的数量。第 $0$ 行的虚拟断点不计入，最后一行的断点计入。

你不能使用超过 $100$ 条语句，超过 $10$ 的盒子或是非小写字母的球，任意一个盒子中某种颜色的球的个数均不能超过 $10^{8}$，程序中的单个字符串长度不能超过 $200$，你的程序单组数据实际遍历的语句条数不能超过 $4 \times 10^5$，单组数据实际判断包含的字符集大小之和不能超过 $10^7$（参考下发的检验器）。

约定 $n$ 表示输入至多使用的盒子数，$mx$ 表示初始时每个盒子中每种颜色球个数的最大值，$max$ 表示初始时所有盒子中球总数的最大值，$sum$ 表示初始时所有盒子中球的总数。**任务中未提及的盒子必须保持原状**，你需要分别完成下面 $10$ 个任务。

1. $n=10, sum \le 100$，你需要将所有 $\tt a$ 颜色球放入盒子 $1$，所有 $\tt b$ 颜色球放入盒子 $2$，所有 $\tt c$ 颜色球放入盒子 $3$。

2. $n=10, sum \le 100$，你需要将所有 $\tt a$ 颜色的球改为 $\tt b$ 颜色的球，将所有 $\tt b$ 颜色的球改为 $\tt c$ 颜色的球，将所有 $\tt c$ 颜色的球改为 $\tt a$ 颜色的球，这三个操作应同时完成。

3. $n=10, sum \le 100$，你需要将所有不包含 $\tt a$ 颜色球的盒子清空。

4. $n=10, sum \le 100$，你需要给所有非空的，不包含 $\tt a$ 颜色球的盒子放入一个 $\tt a$ 颜色球。

5. $n=5, sum \le 5$，你需要将所有球按照颜色从小到大（${\tt a} < {\tt b} < {\tt c}$）依次放入盒子 $1$ 到 $sum$，每个盒子恰好只放一个球，初始的球不保留。

6. $n=10, sum \le 100$，对于每个盒子，只保留一个出现次数最多的颜色的球，如果有多种颜色出现次数最多，将其变为空集。

7. $n=10, sum \le 100$，对于每个盒子，只保留出现次数最多的颜色的球，如果有多种颜色出现次数最多，保留颜色最小的（${\tt a} < {\tt b} < {\tt c}$）。

8. $n=1, mx \le 10$，记 $\tt a, b, c$ 颜色的球的个数为 $A, B, C$，你需要对于满足 $1 \le x \le 5$ 的整数 $x$ 使得盒子 $x$ 在最终恰好有 $A+Bx+Cx^2$ 个 $\tt a$ 颜色球，不能有其它颜色球。

9. $n=5, max \le 10$，所有 $n$ 个盒子中球总数相等。将每个盒子中的球按从小到大排序，组成一个字符串，保证字符串两两不同。你需要对于每个字符串求出其字典序排名，按字典序从小到大依次将盒子改为 $\tt a, b, c, d, e$。

10. $n=5, max \le 10$，你需要对 $n$ 个盒子求前缀和，即将前面所有盒子的球复制一份放入自己。

**注：子任务按某种规则排序，与难度无关。**

inputFormat: 该题为提交答案型试题，每个测试点对应的任务见【题目描述】。

outputFormat:
针对给定的 $10$ 个任务，你需要分别将你的程序命名为 `1.out`∼`10.out`，并将这 $10$ 个文件直接压缩为 `zip` 文件提交。

每个文件中需要包含若干行。

第一行一个非负整数 $L$，代表你使用的语句数。

接下来 $L$ 行，每行一个语句。

**你必须以一个断点结尾。**

samples:
见附件 down.zip 中的 sample 文件夹
见附件 down.zip 中的 sample 文件夹

hint:
**【自定义校验器数据格式】**

第一行，两个整数 $T, V$，分别表示数据组数与评分参数。

对于接下来每组数据：

第一行，两个整数 $n,m$，表示需要描述的输入盒子数与输出盒子数。

第二行，$n$ 个字符串，描述输入时前 $n$ 个盒子的状态。

第三行，$m$ 个字符串，描述输出时前 $m$ 个盒子的状态，**你仍然需要保证其它盒子为空**。

**同样地，使用 `@` 表示空串**。

**【自定义校验器使用方法】**

将 `checker.cpp` 编译后，在命令行执行

```
checker [in] [out] [ans]
```

其中 `[in]` 为测试数据，`[out]` 为你需要测试的程序，`[ans]` 输入和 `[in]` 相同的内容。

例如你需要测试第一个样例，且你的程序名为 `1.out`，需先将 `1.in` 复制到当前目录，并执行

```
checker 1.in 1.out 1.in
```

**【评分标准】**

对于每个测试点，其内部会评测若干组测试数据。

若你的输出出现下列情况，那么该测试点不得分：

- 输出与要求不符。
- 出现无法识别或不合法的语句。
- 某个盒子中某种颜色的球数量超过 $10^8$。
- 使用超过 $100$ 条语句。
- 程序中单个字符串长度超过 $200$。
- 使用不在 $1$ 到 $10$ 之间的盒子。
- 使用非小写字母颜色的球。
- 单组数据实际语句遍历次数大于 $4 \times 10^5$。
- 单组数据实际判断包含的字符集大小之和超过 $10^7$（参考下发的检验器）。

语句数可简单地视为程序中 `change` 和 `#` 的数量之和，第 $0$ 行的虚拟断点不计入，最后一行的断点计入。

断点数可简单地视为程序中 `#` 的数量。第 $0$ 行的虚拟断点不计入，最后一行的断点计入。

一个程序的代价是你给出的断点数量乘以程序的语句数，记作 $val$。

否则设对应子任务的评分标准为 $V$，那么你的得分为：

$$\mathrm{score}=\begin{cases}11&V>val\\\Big\lfloor\frac{10}{\exp\left(1-\frac {V}{val}\right)}\Big\rfloor&\text{otherwise.}\end{cases}$$

下面给出各个任务对应的评分标准 $V$:

| 编号 | $1$ | $2$ | $3$ | $4$ | $5$| $6$ | $7$ | $8$ | $9$ | $10$ |
| :-: | :-: | :-: | :-: | :-: | :-: |  :-: | :-: | :-: | :-: | :-: |
| $V$ | $16$ | $16$ | $16$ | $16$ | $26$ | $8$ | $10$ | $18$ | $20$ | $30$ |


title: 费解的开关

description:
你玩过“拉灯”游戏吗？

$25$ 盏灯排成一个 $5 \times 5$ 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 $1$ 表示一盏开着的灯，用数字 $0$ 表示关着的灯。

下面这种状态

    10111
    01101
    10111
    10000
    11011

在改变了最左上角的灯的状态后将变成：

    01111
    11101
    10111
    10000
    11011

再改变它正中间的灯后状态将变成：

    01111
    11001
    11001
    10100
    11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 $6$ 步以内使所有的灯都变亮。

inputFormat:
第一行输入正整数 $n$，代表数据中共有 $n$ 个待解决的游戏初始状态。

以下若干行数据分为 $n$ 组，每组数据有 $5$ 行，每行 $5$ 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

outputFormat:
一共输出 $n$ 行数据，每行有一个小于等于 $6$ 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 $6$ 步以内无法使所有灯变亮，则输出 `-1`。

hint: 测试数据满足 $0 < n \le 500$。


title: [USACO03MAR] Best Cow Fences G

description:
**原题来自：USACO 2003 Mar. Green**

给定一个长度为 $n$ 的非负整数序列 $A$ ，求一个平均数最大的，长度不小于 $L$ 的子段。

inputFormat:
第一行用空格分隔的两个整数 $n$ 和 $L$；

第二行为 $n$ 个用空格隔开的非负整数，表示 $A_i$。

outputFormat: 输出一个整数，表示这个平均数的 $1000$ 倍。不用四舍五入，直接输出。


title: 七夕祭

description:
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。

矩形的祭典会场由 $N$ 排 $M$ 列共计 $N \times M$ 个摊点组成。

虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。

不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在 Vani 想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

inputFormat:
第一行包含三个整数 $N$ 和 $M$ 和 $T$，$T$ 表示 cl 对多少个摊点感兴趣。

接下来 $T$ 行，每行两个整数 $x, y$，表示 cl 对处在第 $x$ 行第 $y$ 列的摊点感兴趣。

outputFormat:
首先输出一个字符串。

如果能满足 Vani 的全部两个要求，输出 `both`；

如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多，输出 `row`；

如果只能使各列中 cl 感兴趣的摊点数一样多，输出 `column`；

如果均不能满足，输出 `impossible`。

如果输出的字符串不是 `impossible`， 接下来输出最小交换次数，与字符串之间用一个空格隔开。


title: Genius Acm

description:
Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturers in the world. 每天，该公司生产 $n$ 台 CPU 并销售到世界各地。

ACM 公司的质检部门会对生产出的 CPU 进行成组测试，对一组（若干个）CPU 进行测试的方法如下：

1. 随机从该组 CPU 中选取 $m$ 对（即 $2m$ 台），若总数不足 $2m$ 台，则选取尽量多对。

2. 对于每一对 CPU，测量它们之间的 Relative Performance Difference (RPD)，并把第 $i$ 对的 RPD 记为 $D_i$。RPD 的计算方法在后面给出。

3. 该组 CPU 的 Sqared Performance Difference (SPD） 由以下公式给出：

$SPD=\sum _i D^2_i$

4. 该组 CPU 通过质检，当且仅当 $SPD \le k,$ 其中 $k$ 是给定常数。

ACM 公司生产的 CPU 性能很好，而质检部门制定的标准更是过于严格。通常他们把 $n$ 台 CPU 作为一整组进行测试，这导致一些性能良好的 CPU 无法通过测试，生产部门对此颇有微词。作为质检部门的领导，小 S 在不更改质检测试流程的前提下，想出了这样一个主意：如果能够把 $n$ 台 CPU 恰当地分成连续的若干段，使得每段 CPU 都能够通过成组测试，就可以解决当下的问题。

现在，小 S 已经知道了 $n$ 台各自的性能表现 $P_1,\cdots ,P_n$，两台 CPU 的 RPD 被定义为它们性能表现的差的绝对值。请你帮忙计算一下，至少把这些 CPU 分成多少段，才能使得每一段都能通过成组测试。

inputFormat:
每个测试点包含多组数据，第一行整数 $T$ 给出数据组数。

对于每组数据，第一行三个整数 $n,m,k$，第二行 $n$ 个整数 $P_1,\cdots ,P_n$。

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


title: Sudoku

description:
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. in some of the cells arewriten decimal digits ftom 1 to 9. The other cels are empty. The goal is to fill the empty cels with decimal digis from 1 to 9, one digit per cell, in such waythat in each rowy, in each column and in each marked 3x3 subsquare, allthe digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.

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

inputFormat: The input data will start with the number ofthe test cases. For each test case,9 lines follow, corresponding to the rows ofthe table. On each line a string ofexactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.

outputFormat: For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. lf solutions is not unique, then the program may print any one of them.

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

数独是一个非常简单的任务。一个包含 9 行和 9 列的正方形表格被分成了 9 个小的 3x3 方块，如图所示。一些单元格中写有从 1 到 9 的十进制数字。其他单元格为空。目标是以从 1 到 9 的十进制数字填充空单元格，每个单元格一个数字，使得每行、每列和每个标记的 3x3 子方块中都出现从 1 到 9 的所有数字。编写一个程序来解决给定的数独任务。

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

**【输入格式】**

输入数据将以测试用例的数量开始。对于每个测试用例，将跟随 9 行，对应于表格的行。在每一行上，给出一个正好包含 9 个十进制数字的字符串，对应于该行中的单元格。如果一个单元格为空，则用 0 表示。

**【输出格式】**

对于每个测试用例，你的程序应该以与输入数据相同的格式打印解决方案。空单元格必须按照规则填充。如果解不唯一，则程序可以打印其中任何一个。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: Sudoku 2

description:
In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

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

Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

inputFormat: The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

outputFormat: For each test case, print a line representing the completed Sudoku puzzle.

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

在数独游戏中，给定一个大的 9 × 9 网格，分成了较小的 3 × 3 子网格。例如，

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

在给定网格中的一些数字后，你的目标是确定剩余的数字，使得数字 1 到 9 恰好出现在以下位置：(1) 九个 3 × 3 子网格中的每一个，(2) 九行中的每一个，以及 (3) 九列中的每一个。

**【输入格式】**

输入测试文件将包含多个案例。每个测试案例由一行组成，其中包含 81 个字符，这些字符代表数独网格的 81 个方格，逐行给出。每个字符可以是一个数字（从 1 到 9）或一个句点（用于表示未填充的方格）。你可以假设输入中的每个谜题都有唯一解。文件的结尾由一行包含单词“end”表示。

**【输出格式】**

对于每个测试案例，打印一行表示完成的数独谜题。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: Bloxorz I

description:
Little Tom loves playing games. One day he downloads a little computer game called 'Bloxorz' which makes him excited. It's a game about rolling a box to a specific position on a special plane. Precisely, the plane, which is composed of several unit cells, is a rectangle shaped area. And the box, consisting of two perfectly aligned unit cube, may either lies down and occupies two neighbouring cells or stands up and occupies one single cell. One may move the box by picking one of the four edges of the box on the ground and rolling the box 90 degrees around that edge, which is counted as one move. There are three kinds of cells, rigid cells, easily broken cells and empty cells. A rigid cell can support full weight of the box, so it can be either one of the two cells that the box lies on or the cell that the box fully stands on. A easily broken cells can only support half the weight of the box, so it cannot be the only cell that the box stands on. An empty cell cannot support anything, so there cannot be any part of the box on that cell. The target of the game is to roll the box standing onto the only target cell on the plane with minimum moves.

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

The box stands on a single cell

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

The box lies on two neighbouring cells, horizontally

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

The box lies on two neighbouring cells, vertically

After Little Tom passes several stages of the game, he finds it much harder than he expected. So he turns to your help.

inputFormat:
Input contains multiple test cases. Each test case is one single stage of the game. It starts with two integers R and C(3 ≤ R, C ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains R lines and C characters for each line, with 'O' (Oh) for target cell, 'X' for initial position of the box, '.' for a rigid cell, '#' for a empty cell and 'E' for a easily broken cell. A test cases starts with two zeros ends the input.

It guarantees that

- There's only one 'O' in a plane.
- There's either one 'X' or neighbouring two 'X's in a plane.
- The first(and last) row(and column) must be '#'(empty cell).
- Cells covered by 'O' and 'X' are all rigid cells.

outputFormat: For each test cases output one line with the minimum number of moves or "Impossible" (without quote) when there's no way to achieve the target cell.

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

小汤姆喜欢玩游戏。有一天，他下载了一个叫做“Bloxorz”的小电脑游戏，让他非常兴奋。这是一个关于将一个方块滚动到特定位置的游戏。准确地说，这个平面由几个单位单元格组成，是一个矩形形状的区域。而方块由两个完美对齐的单位立方体组成，可以躺下并占据两个相邻的单元格，也可以站立并占据一个单独的单元格。可以通过选择方块在地面上的四条边之一，并围绕该边旋转 90 度来移动方块，每次旋转算作一步。有三种类型的单元格，刚性单元格、易碎单元格和空单元格。刚性单元格可以支撑方块的全部重量，因此可以是方块所占据的两个单元格中的任意一个，也可以是方块完全站立在上面的单元格。易碎单元格只能支撑方块重量的一半，因此不能是方块完全站立在上面的唯一单元格。空单元格无法支撑任何东西，因此方块不可能部分位于该单元格上。游戏的目标是以最少的步数将站立的方块滚动到平面上唯一的目标单元格。

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

方块站在单个单元格上

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

方块横躺在两个相邻的单元格上

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

方块纵躺在两个相邻的单元格上

在小汤姆通过游戏的几个阶段后，他发现比他预期的要难得多。因此，他求助于你的帮助。

**【输入格式】**

输入包含多个测试案例。每个测试案例都是游戏的一个阶段。它以两个整数 R 和 C（3 ≤ R，C ≤ 500）开头，表示平面的行数和列数。接下来是平面，其中包含 R 行和每行的 C 个字符，其中 'O' 表示目标单元格，'X' 表示方块的初始位置，'.' 表示刚性单元格，'#' 表示空单元格，'E' 表示易碎单元格。一个测试案例以两个 0 结束输入。

保证：

- 平面上只有一个 'O'。
- 平面上要么有一个 'X'，要么有相邻的两个 'X'。
- 第一行（和最后一行）（以及第一列和最后一列）必须是 '#'（空单元格）。
- 'O' 和 'X' 覆盖的单元格都是刚性单元格。

**【输出格式】**

对于每个测试案例，输出一行表示移动的最小次数，或在无法达到目标单元格时输出 "Impossible"（不带引号）。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: Nightmare II

description:
Last night, little erriyue had a horrible nightmare. He dreamed that he and his girl friend were trapped in a big maze separately. More terribly, there are two ghosts in the maze. They will kill the people. Now little erriyue wants to know if he could find his girl friend before the ghosts find them.

You may suppose that little erriyue and his girl friend can move in 4 directions. In each second, little erriyue can move 3 steps and his girl friend can move 1 step. The ghosts are evil, every second they will divide into several parts to occupy the grids within 2 steps to them until they occupy the whole maze. You can suppose that at every second the ghosts divide firstly then the little erriyue and his girl friend start to move, and if little erriyue or his girl friend arrive at a grid with a ghost, they will die.
Note: the new ghosts also can devide as the original ghost.

inputFormat:
The input starts with an integer T, means the number of test cases.

Each test case starts with a line contains two integers n and m, means the size of the maze. (1<n, m<800)

The next n lines describe the maze. Each line contains m characters. The characters may be:
- ‘.’ denotes an empty place, all can walk on.
- ‘X’ denotes a wall, only people can’t walk on.
- ‘M’ denotes little erriyue
- ‘G’ denotes the girl friend.
- ‘Z’ denotes the ghosts.

It is guaranteed that will contain exactly one letter M, one letter G and two letters Z.

outputFormat: Output a single integer S in one line, denotes erriyue and his girlfriend will meet in the minimum time S if they can meet successfully, or output -1 denotes they failed to meet.

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

昨晚，小 erriyue 做了一个可怕的噩梦。他梦到自己和女朋友被困在一个大迷宫里。更可怕的是，迷宫里有两个鬼魂。它们会杀人。现在小 erriyue 想知道在鬼魂找到他们之前，他是否能找到他的女朋友。

假设小 erriyue 和他的女朋友可以向四个方向移动。在每一秒中，小 erriyue 可以移动 $3$ 步，而他的女朋友只能移动 $1$ 步。鬼魂是邪恶的，每一秒它们都会分裂成几部分，占领距离它们两步以内的网格，直到它们占领整个迷宫。你可以假设在每一秒钟，鬼魂首先分裂，然后小 erriyue 和他的女朋友开始移动，如果小 erriyue 或者他的女朋友到达一个有鬼魂的网格，他们就会死亡。

注意：新的鬼魂也可以像原来的鬼魂一样分裂。

**【输入格式】**

输入以一个整数 $T$ 开始，表示测试案例的数量。

每个测试案例以一行开头，包含两个整数 $n$ 和 $m$，表示迷宫的大小。$(1 < n, m < 800)$

接下来的 $n$ 行描述了迷宫。每行包含 $m$ 个字符。字符可能是：
- `.` 表示空地，所有人都可以走。
- `X` 表示墙，只有人类无法行走。
- `M` 表示小 erriyue。
- `G` 表示女朋友。
- `Z` 表示鬼魂。

保证迷宫中恰好有一个字母 `M`、一个字母 `G` 和两个字母 `Z`。

**【输出格式】**

在一行中输出一个整数 $S$，表示如果他们能成功相遇，小 erriyue 和他的女朋友将在最短时间 $S$ 内相遇，或者输出 $-1$ 表示他们未能相遇。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [JOISC 2024 Day1] 鱼 3

description:
JOI 君在一个大水缸中饲养着 $ N $ 条鱼，每条鱼的编号从 $ 1 $ 到 $ N $。

JOI 君有两种类型的鱼食，$ A $ 和 $ B $，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下：

- 当第 $ k $ 条鱼（$ 1 \leq k \leq N $）吃掉一块 $ A $ 型食物时，第 $ k $ 条鱼的智力恰好增加 $ D $。
- 当第 $ k $ 条鱼（$ 1 \leq k \leq N $）吃掉一块 $ B $ 型食物时，编号大于等于 $ k $ 的所有鱼的智力都恰好增加 $ 1 $。

目前，所有鱼的智力都为 $ 0 $。JOI 君希望使第 $ i $ 条鱼（$ 1 \leq i \leq N $）的智力等于其理想智力 $ C_i $，但这并不总是可能的。

因此，他考虑了 $ Q $ 个问题。第 $ j $ 个问题（$ 1 \leq j \leq Q $）如下：

- 从所有鱼的智力都为 0 的状态开始，通过重复将食物放入水族箱零次或多次的动作，是否可能达到所有鱼 $ L_j , L_j + 1 ,..., R_j $ 都拥有其精确的理想智力值的状态？此外，如果可能，需要放入水族箱的 A 型食物的最小数量是多少？

编写一个程序，给定有关 JOI 君的鱼的信息以及有关问题的信息，回答他的问题。

outputFormat: 输出共 $Q$ 行。在第 $j$ 行（$ 1 \leq j \leq Q $）中，如果可以达到所有鱼 $ L_j $，$ L_j + 1 $，...，$ R_j $ 拥有其精确的理想智力值的状态，则输出需要放入水族箱的 $A$ 型食物的最小数量。否则，输出 $-1$。

hint:
#### 样例解释 1

例如，在以下情况下，所有鱼 $1,2,3$ 最终都达到了其精确的理想智力值，且放入水族箱的 $A$ 型食物的数量为 $1$。

- 起初，鱼 $1,2,3,4$ 的智力分别为 $0,0,0,0$。
- 接下来，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $3$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $0,0,1,1$。
- 然后，JOI 君将一块 $A$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $2,0,1,1$。
- 最后，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $3,1,2,2$。
- 由于不放入任何 $A$ 型食物就无法达到所有鱼 $1,2,3$ 的精确理想智力值的状态，输出 $1$。

这个样例满足子任务 $1$ 和 $5$ 的约束条件。

### 约束条件

- $ 1 \leq N \leq 300,000 $。
- $ 1 \leq Q \leq 300,000 $。
- $ 1 \leq D \leq 10^{12} $。
- $ 0 \leq C_i \leq 10^{12} $（$ 1 \leq i \leq N $）。
- $ 1 \leq L_j \leq R_j \leq N $（$ 1 \leq j \leq Q $）。
- 给定值均为整数。

### 子任务

- （9 分）$ N \leq 3,000 $，$ Q \leq 3,000 $。
- （7 分）$ C_i \leq 1 $（$ 1 \leq i \leq N $）。
- （28 分）$ D = 1 $。
- （20 分）$ C_i \geq C_{i+1} $（$ 1 \leq i \leq N - 1 $）。
- （36 分）无额外约束。


title: [JOISC 2024 Day1] 滑雪 2

description:
JOI 先生管理着 IOI 高原上一家著名的滑雪度假村，他决定为滑雪度假村开业 15 周年庆祝活动而在相邻的 KOI 高原上建造一家新的滑雪度假村。

KOI 高原有 $N$ 个点，编号从 $1$ 到 $N$。目前，第 $i$ 个点（$1 \leq i \leq N$）的海拔高度为 $H_i$ 米，并且高原上的每个点都没有连接起来的滑道。此外，每个点都配备了一个未使用的连接设施。

JOI 先生的目标是在高原上的一个点上建造 KOI 酒店，然后建造一些滑道连接高原上的每个点，以便人们可以从任何一个点滑雪到酒店。具体来说，JOI 先生将按照以下步骤建造滑雪度假村：

1. 进行以下筑堤工作任意次数（可能为零）：选择一个点 $i$，将点 $i$ 的海拔高度增加 1 米。此工作的成本为每次操作 $K$。

2. 从 $N$ 个点中选择一个点，并在那里建造 KOI 酒店。

3. 进行以下扩展工作任意次数（可能为零）：选择一个点 $i$，在点 $i$ 建造一个连接设施。此工作的成本为每次操作 $C_i$。

4. 对于除了 KOI 酒店所在点之外的剩余 $N - 1$ 个点，执行以下构建：设 $i$ 为该点的编号。选择另一个海拔严格较低的点 $j$，并使用点 $j$ 的一个未使用的连接设施，从点 $i$ 向点 $j$ 构建单向滑道。注意，如果没有海拔严格较低且有未使用连接设施的点 $j$，则无法实现目标。

滑雪度假村的建造成本是进行堤岸工作和扩展工作的成本之和。

编写一个程序，给定 KOI 高原上每个点的信息和每次筑堤工作的成本 $K$，找到建造滑雪度假村的最小成本。

outputFormat: 输出一行，构建滑雪度假村的最小成本。

hint:
#### 样例解释 1

例如，可以按以下方式建造滑雪度假村：

1. 在点 $1$ 进行两次筑堤工作，在点 $5$ 进行一次。这些筑堤工作的总成本为 $2 \times (2 + 1) = 6$。每个点的海拔高度变为 $2, 1, 0, 2, 2$ 米。
2. 在点 $3$ 建造 KOI 酒店。
3. 在点 $2$ 进行两次扩展工作。这些扩展工作的总成本为 $1 \times 2 = 2$。结果，从点 $1$ 开始，每个点的连接设施数量变为 $1, 3, 1, 1, 1$。
4. 构建 $4$ 条滑道：一条从点 $1$ 到点 $2$，一条从点 $2$ 到点 $3$，一条从点 $4$ 到点 $2$，一条从点 $5$ 到点 $2$。

因此，构建滑雪度假村的成本为 $6 + 2 = 8$。由于无法以不超过 $7$ 的成本建造滑雪度假村，因此输出 $8$。

此样例输入满足子任务 $3,4,5,6$ 的约束条件。

#### 样例解释 2

这个样例输入与示例输入 1 的唯一区别在于 $K$ 的值。

这个样例输入满足子任务 $1, 3, 4, 5, 6$ 的约束条件。

#### 样例解释 3

此示例输入满足子任务 $2, 3, 4, 5, 6$ 的约束条件。

### 约束条件

- $1 \leq N \leq 300$
- $1 \leq K \leq 10^9$
- $0 \leq H_i \leq 10^9$（$1 \leq i \leq N$）
- $1 \leq C_i \leq 10^9$（$1 \leq i \leq N$）
- 给定的值均为整数。

### 子任务

- (5 分) $K \geq 100,000$，$H_i \leq 300$，$C_i \leq 100$（$1 \leq i \leq N$）
- (12 分) $H_1 \leq H_i$，$C_1 \leq C_i$，$H_i \leq 300$（$1 \leq i \leq N$）
- (9 分) $N \leq 10$，$H_i \leq 10$（$1 \leq i \leq N$）
- (33 分) $N \leq 40$，$H_i \leq 40$（$1 \leq i \leq N$）
- (27 分) $H_i \leq 300$（$1 \leq i \leq N$）
- (14 分) 无额外约束。


title: [JOISC 2024 Day2] 棋盘游戏

description:
有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1 ≤ j ≤ M$）双向连接着单元格 $U_j$ 和 $V_j$。

棋盘上有两种类型的单元格：重新激活单元格和停止单元格。

这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的第 $i$ 个字符（$1 ≤ i ≤ N$）是 '0' 表示单元格 $i$ 是重新激活单元格，是 '1' 表示单元格 $i$ 是停止单元格。

这个棋盘游戏由编号从 $1$ 到 $K$ 的 $K$ 个玩家进行。每个玩家都有自己的棋子，游戏从每个玩家将其棋子放在特定的单元格上开始。一开始，玩家 $p$（$1 \leq p \leq K$）将其棋子放在单元格 $X_p$ 上。注意，多个玩家的棋子可以放在同一个单元格上。

游戏随着每个玩家轮流进行而进行，从玩家 1 开始，按数字顺序进行。在玩家 $p$ 完成其回合后，玩家 $p + 1$ 开始回合（如果 $p = K$，则玩家 1 开始回合）。每个玩家在其回合上执行以下操作：

1. 选择与其棋子所在的单元格通过一条路径相连的一个单元格，并将其棋子移动到所选择的单元格上。
2. 如果目标单元格是重新激活单元格，则重复步骤 1 并继续其回合。如果目标单元格是停止单元格，则结束其回合。

代表日本参加这个棋盘游戏的包括 JOI 君在内的由 $K$ 名成员组成的团队，正在研究协作策略，以快速征服这个游戏。他们目前正在研究以下问题：

为了将玩家 1 的棋子放置在单元格 $T$ 上，$K$ 名玩家需要的最小总移动次数是多少？即使在回合中途，如果玩家 1 的棋子被放置在单元格 $T$ 上，也认为满足条件。

给定关于游戏棋盘和每个玩家棋子的初始放置位置的信息，编写一个程序来计算每个 $T = 1, 2, \ldots, N$ 对应的问题的答案。

outputFormat: 输出 $N$ 行。在第 $T$ 行（$1 ≤ T ≤ N$）上，输出 $K$ 个玩家将玩家 1 的棋子放在单元格 $T$ 上所需的最小总移动次数。

hint:
#### 样例解释 1

由于玩家 $1$ 的棋子从单元格 $1$ 开始，所以 $T = 1$ 的答案是 $0$。

对于 $T = 2$，在第一步中，玩家 $1$ 可以将他的棋子从单元格 $1$ 移动到单元格 $2$。因此，$T = 2$ 的答案是 $1$。

对于 $T = 3$，他们可以通过以下 $2$ 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：

- 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个激活单元格，因此玩家 $1$ 的回合继续。
- 在第二步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。

由于他们无法在 $1$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $2$。

类似地，可以验证 $T = 4$ 的答案为 $2$，$T = 5$ 的答案为 $3$。

这个样例输入满足子任务 $1,4,5,6,7,8$ 的约束。

#### 样例解释 2

对于 $T = 3$，他们可以通过以下 4 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：

- 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $2$。
- 在第二步中，玩家 $2$ 将他的棋子从单元格 $5$ 移动到单元格 $3$。由于单元格 $3$ 是一个激活单元格，玩家 $2$ 的回合继续。
- 在第三步中，玩家 $2$ 将他的棋子从单元格 $3$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $1$。
- 在第四步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。

由于他们无法在 $3$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $4$。

这个样例输入满足子任务 $2,4,5,6,7,8$ 的约束。

#### 样例解释 3

这个样例输入满足子任务 $3, 4, 5, 6, 7,8$ 的约束。

#### 样例解释 4

这个样例输入满足子任务 $4, 6, 7,8$ 的约束。

#### 样例解释 5

这个样例输入满足子任务 $4, 6, 7,8$ 的约束。

### 约束条件

- $2 \leq N \leq 50,000$
- $1 \leq M \leq 50,000$
- $2 \leq K \leq 50,000$
- $1 \leq U_j < V_j \leq N$（$1 \leq j \leq M$）
- $(U_j, V_j)$，$(U_k, V_k)$（$1 \leq j < k \leq M$）
- 可以通过经过多条路径从任何单元格到达任何其他单元格。
- $S$ 是长度为 $N$ 的由 '0' 和 '1' 组成的字符串。
- $1 \leq X_p \leq N$（$1 \leq p \leq K$）
- $N$、$M$ 和 $K$ 都是整数。
- $U_j$ 和 $V_j$ 是整数（$1 \leq j \leq M$）。
- $X_p$ 是整数（$1 \leq p \leq K$）。

### 子任务

1. (3 分) 没有终止单元格。
2. (7 分) 恰好有一个终止单元格。
3. (7 分) 恰好有两个终止单元格。
4. (19 分) $N \leq 3,000$，$M \leq 3,000$，$K \leq 3,000$
5. (23 分) $K = 2$
6. (9 分) $K \leq 100$
7. (23 分) $N \leq 30,000$，$M \leq 30,000$，$K \leq 30,000$
8. (9 分) 没有额外的约束。


title: [JOISC 2024 Day2] 有趣的家庭菜园 5

description:
Bitaro，一个多年来一直热衷于园艺的人，计划从今年春天开始种植一种名为 Bita-radish 的植物。

Bitaro 已经准备好了 $2N$ 个 Bita-radish 幼苗。这些幼苗从 $1$ 到 $2N$ 编号，Bitaro 计划按照这个顺序进行栽培。第 $i$ 个幼苗（$1 \leq i \leq 2N$）的大小为 $A_i$。Bitaro 希望每个幼苗都能得到足够的阳光，因此幼苗的大小满足以下条件：

- $A_1 \leq A_2 \leq \cdots \leq A_N \leq A_{N+1}$.
- $A_{N+1} \geq A_{N+2} \geq \cdots \geq A_{2N-1} \geq A_{2N} \geq A_1$.

注意，幼苗 $1$ 最小，幼苗 $N+1$ 最大。

Bitaro 还准备了 $N$ 个红色花盆和 $N$ 个蓝色花盆，每个花盆也有一定大小。第 $j$ 个（$1 \leq j \leq N$）红色花盆的大小是 $B_j$，第 $k$ 个（$1 \leq k \leq N$）蓝色花盆的大小是 $C_k$。Bitaro 在这总共 $2N$ 个花盆中各种植一株 Bita-radish 幼苗，并按某种顺序排列花盆，使幼苗按 $1,2,...,2N$ 顺序依次放入花盆中。

考虑到外观，这 $2N$ 个花盆必须被安排在一个美观的顺序中。这里，美观的顺序意味着花盆的排列使得存在连续的 $N$ 个花盆颜色相同。更确切地说，一个花盆排列被称为是美观的，当且仅当存在一个整数 $l$，满足 $1 \leq l \leq N+1$，使得种植了幼苗 $l, l+1, \ldots, l+N-1$ 的花盆颜色都相同。

当尺寸为 $y$ 的幼苗种植在尺寸为 $x$ 的花盆中时，该对的栽培难度是绝对值 $|x-y|$。Bitaro 种植 Bita-radish 的工作量是 $2N$ 对花盆和幼苗中的**最大**栽培难度。编写一个程序，给定 Bita-radish 幼苗和花盆的信息，找到种植幼苗的最小可能 Bitaro 工作量值，并且花盆需要按美观的顺序排列。

outputFormat: 输出一个值，种植幼苗以使花盆按美观顺序排列时 Bitaro 工作量的最小可能值。

hint:
#### 样例解释 1

在这个样例输入中，Bitaro 可以通过以下方式种植幼苗来实现工作量为 $2$：

- 将幼苗 $1$ 种植在第一个红色花盆中。这对的栽培难度是 $|2 - 1| = 1$。
- 将幼苗 $2$ 种植在第二个蓝色花盆中。这对的栽培难度是 $|3 - 2| = 1$。
- 将幼苗 $3$ 种植在第一个蓝色花盆中。这对的栽培难度是 $|4 - 6| = 2$。
- 将幼苗 $4$ 种植在第二个红色花盆中。这对的栽培难度是 $|5 - 3| = 2$。

种植了幼苗 $2$ 和 $3$ 的花盆的颜色都是蓝色，因此花盆是按美观顺序排列的。

当种植幼苗以使花盆按美观顺序排列时，无法实现工作量小于 $2$。因此，输出为 $2$。

这个样例输入满足所有子任务的约束条件。

#### 样例解释 2

这个样例输入满足子任务 $2,3,4,5$ 的约束条件。

#### 样例解释 3

这个样例输入满足子任务 $2,3,5$ 的约束条件。

### 约束条件

- $1 \leq N \leq 300,000$.
- $1 \leq A_i \leq 10^9$ （$1 \leq i \leq 2N$）.
- $1 \leq B_j \leq 10^9$ （$1 \leq j \leq N$）.
- $1 \leq C_k \leq 10^9$ （$1 \leq k \leq N$）.
- $A_1 \leq A_2 \leq \cdots \leq A_N \leq A_{N+1}$.
- $A_{N+1} \geq A_{N+2} \geq \cdots \geq A_{2N-1} \geq A_{2N} \geq A_1$.
- 所有输入值都是整数。

### 子任务

1. (4 分) $N \leq 5$。
2. (5 分) $N \leq 10$。
3. (21 分) $N \leq 2,000$。
4. (37 分) 所有的 $A_i$ 的值都是不同的。另外，满足 $A_N < A_{2N}$。
5. (33 分) 没有额外的约束条件。


title: [JOISC 2024 Day3] 卡牌收集

description:
JOI 君对一款卡牌游戏中的卡牌收集充满热情。卡牌游戏中的每张卡牌都有两个整数，代表其强度和成本。为了获得一张新卡牌，JOI 君将 $N$ 张卡牌带到一个卡牌交换处。每张卡牌编号从 $1$ 到 $N$。第 $i$ 张卡牌（$1 \leq i \leq N$）的强度是 $S_i$，成本是 $V_i$。

卡牌交换处有两台机器可供使用。如果你将两张卡牌 $A$ 和 $B$ 插入其中一台机器，你将能够获得满足以下条件的卡牌 $C$：

- 如果你使用第一台机器，那么 $C$ 的强度等于 $A$ 和 $B$ 的强度中的最大值，并且 $C$ 的成本等于 $A$ 和 $B$ 的成本中的最大值。
- 如果你使用第二台机器，那么 $C$ 的强度等于 $A$ 和 $B$ 的强度中的最小值，并且 $C$ 的成本等于 $A$ 和 $B$ 的成本中的最小值。

JOI 君计划使用这些机器正好 $N - 1$ 次以获得一张新卡牌。为此，他将 $N$ 张卡牌按卡牌 $1$ 到卡牌 $N$ 的顺序依次排列。然后，他重复以下操作 $N - 1$ 次：

- 选择两张相邻的卡牌，使用其中一台机器来得到一张新卡牌，并将新卡牌放在操作前所选两张卡牌的位置。

在执行 $N-1$ 次操作后，JOI 君将只剩下一张卡牌。这张卡牌的强度和成本将取决于他执行的操作。

JOI 君有一个希望在执行 $N-1$ 次操作后获得的卡牌列表。第 $j$ 张卡牌（$1 \leq j \leq M$）由一对整数 $(T_j, W_j)$ 表示，其中 $T_j$ 是第 $j$ 张卡牌的强度，$W_j$ 是第 $j$ 张卡牌的成本。编写一个程序，给定有关 JOI 君卡牌的信息以及他想获得的卡牌列表，确定在执行 $N-1$ 次操作后他可以获得的列表中的哪些卡牌。

outputFormat: 向标准输出写入一行，输出应按升序包含 JOI 君可以在执行 $N-1$ 次操作后获得的列表中所有卡牌的编号。

hint:
#### 样例解释 1

例如，JOI 君可以通过以下方式获得一张强度为 2，成本为 3 的卡牌：

- 交出卡牌 4 和卡牌 5，获得一张强度为 1，成本为 1 的卡牌。
- 交出卡牌 3 和第一次操作中获得的卡牌，获得一张强度为 1，成本为 1 的卡牌。
- 交出卡牌 1 和卡牌 2，获得一张强度为 2，成本为 3 的卡牌。
- 交出第二次和第三次操作中获得的卡牌，获得一张强度为 2，成本为 3 的卡牌。

请注意，即使在第三次操作中获得了一张强度为 2，成本为 3 的卡牌，JOI 君仍需要执行最后一次操作。即使在某些操作后获得了某张卡牌，也可能在执行 $N-1$ 次操作后无法获得它。

这个样例输入满足所有子任务的约束条件。

#### 样例解释 2

与此样例输出一样，如果在执行 $N-1$ 次操作后无法获得列表中的任何卡牌，则应输出一个空行。

这个样例输入满足所有子任务的约束条件。

#### 样例解释 3

这个样例输入满足所有子任务的约束条件。

### 约束条件

- $2 \leq N \leq 200,000$．
- $1 \leq M \leq 200,000$．
- $1 \leq S_i \leq 10^9$ ($1 \leq i \leq N$)．
- $1 \leq V_i \leq 10^9$ ($1 \leq i \leq N$)．
- $1 \leq T_j \leq 10^9$ ($1 \leq j \leq M$)．
- $1 \leq W_j \leq 10^9$ ($1 \leq j \leq M$)．
- 给定的值均为整数。

### 子任务

1. (11 分) $N \leq 20$，$M \leq 10$．
2. (38 分) $N \leq 2,000$，$M \leq 10$．
3. (22 分) $M \leq 10$．
4. (29 分) 无额外约束。


title: [JOISC 2024 Day3] 塔楼

description:
IOI Tower 是一座极其高的塔楼，配备了一条用于上升的楼梯。这个楼梯由 $10^{100}$ 个台阶组成，从底部开始依次编号为第 $0$ 级、第 $1$ 级，依此类推。JOI 君目前在第 $0$ 级，并打算爬楼梯。JOI 君可以通过以下两种方式上楼，禁止下楼。

- 上升 $1$ 级。这个动作需要 $A$ 秒。
- 从当前级别跳到上方 $D$ 级，跳过中间的台阶。这个动作需要 $B$ 秒。

目前，楼梯的几个位置正在进行施工，正在施工的台阶不能踩上去。具体来说，有 $N$ 处正在进行施工，第 $i$ 处施工（$1 \leq i \leq N$）正在进行的台阶为 $L_i$ 到 $R_i$。

IOI Tower 有 $Q$ 个房间，编号从 $1$ 到 $Q$。人们可以从楼梯的第 $X_j$ 级进入第 $j$ 个房间（$1 \leq j \leq Q$）。因此，JOI 君决定确定他是否可以到达每个房间，如果可能的话，以最短时间需要多少秒到达。

给出关于 JOI 君、施工和房间的信息，创建一个程序，确定 JOI 君是否可以到达第 $j$ 个房间（$1 \leq j \leq Q$），如果可能的话，计算需要的最短时间。

outputFormat: 输出 $Q$ 行，在第 $j$ 行（$1 \leq j \leq Q$）输出 JOI 君到达第 $X_j$ 级台阶所需的最少秒数；如果无法到达，则输出 $-1$。

hint:
#### 样例解释 1

JOI 君可以按照以下步骤在 $120$ 秒内到达楼梯的第 $13$ 阶：

- 从第 $0$ 阶到第 $1$ 阶上升。此操作需要 $10$ 秒。
- 从第 $1$ 阶到第 $2$ 阶上升。此操作需要 $10$ 秒。
- 从第 $2$ 阶到第 $3$ 阶上升。此操作需要 $10$ 秒。
- 从第 $3$ 阶跳到第 $7$ 阶，跳过中间的台阶。此操作需要 $35$ 秒。
- 从第 $7$ 阶到第 $8$ 阶上升。此操作需要 $10$ 秒。
- 从第 $8$ 阶到第 $9$ 阶上升。此操作需要 $10$ 秒。
- 从第 $9$ 阶跳到第 $13$ 阶，跳过中间的台阶。此操作需要 $35$ 秒。

由于无法在小于 $120$ 秒内到达第 $13$ 阶楼梯，输出为 $120$。

这个样例输入满足子任务 $1,2,4$ 的约束条件。

#### 样例解释 2

这个样例输入满足子任务 $1,2,4$ 的约束条件。

### 约束条件

- $1 \leq N \leq 200,000$
- $1 \leq Q \leq 200,000$
- $1 \leq D \leq 10^{12}$
- $1 \leq A \leq 1,000,000$
- $1 \leq B \leq 1,000,000$
- $1 \leq L_i \leq R_i \leq 10^{12}$（$1 \leq i \leq N$）
- $R_{i}+1 < L_{i+1}$（$1 \leq i \leq N-1$）
- $1 \leq X_j \leq 10^{12}$（$1 \leq j \leq Q$）
- 给定值均为整数。

### 子任务

1. （5 分）$R_i \leq 1,000,000$（$1 \leq i \leq N$），$X_j \leq 1,000,000$（$1 \leq j \leq Q$）
2. （38 分）$N \leq 2,000$，$Q \leq 2,000$
3. （25 分）$A = 1$，$B = D$
4. （32 分）无额外约束。


title: [JOISC 2024 Day4] 逃生路线 2

description:
IOI 王国由从西向东排列的 $N$ 座城市组成，城市按照从西向东的顺序从 $1$ 到 $N$ 编号。

在 IOI 王国，他们使用 Byou 作为时间单位。IOI 王国的一天被分为 $T$ 个时间单位。从某一天开始后的 $x$ 个 Byous（$0 \leq x < T$）被称为时间 $x$。因此，当从某一天的时间 $T - 1$ 开始经过 $1$ 个 Byou 时，将成为下一天的时间 $0$。

JOI 组织是 IOI 王国的秘密教派之一。由于它是一个秘密教派，成员必须绕过国家的检查站。因此，JOI 组织成员只能使用 JOY 航空公司运营的航班进行城市间旅行。

JOY 航空公司在城市 $i$（$1 \leq i \leq N - 1$）提供 $M_i$ 趟航班。第 $j$ 趟航班（$1 \leq j \leq M_i$）每天从城市 $i$ 在时间 $A_{i,j}$ 起飞，于当天的时间 $B_{i,j}$ 到达城市 $i + 1$。这里，满足 $A_{i,j} < B_{i,j}$。

这些航班提供了便捷的转机服务，也可以在抵达后立即起飞或在公司的机场过夜。

JOI 组织有 $Q$ 名成员，编号从 $1$ 到 $Q$。成员 $k$（$1 \leq k \leq Q$）将他们的运营基地设在城市 $L_k$，生活基地设在城市 $R_k$。因此，他们想知道通过选择从城市 $L_k$ 出发的时间和适当的航班进行，从城市 $L_k$ 出发到城市 $R_k$ 的最短时间。

给定 JOY 航空公司运营的航班和 JOI 组织成员的信息，编写一个程序，找到每个成员 $k$ 从城市 $L_k$ 到城市 $R_k$ 的最短时间。

outputFormat: 输出 $Q$ 行到标准输出。在第 $k$ 行（$1 \leq k \leq Q$），输出成员 $k$ 从城市 $L_k$ 到城市 $R_k$ 所需的最短时间。

hint:
#### 样例解释 1

作为演示，让我们将成员 $k$ 从城市 $L_k$ 出发的第一天称为第 $1$ 天。成员 $1$ 可以按照以下行动在 $500$ Byou 内从城市 $1$ 前往城市 $3$：

1. 第 $1$ 天时刻 $100$ 从城市 $1$ 出发，并在第 $1$ 天时刻 $300$ 到达城市 $2$。
2. 第 $1$ 天时刻 $300$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $3$。

由于没有更快的旅行方式，所以在第 $1$ 行输出 $500$。

成员 $2$ 可以按照以下行动在 $400$ Byou 内从城市 $2$ 前往城市 $4$：

1. 第 $1$ 天时刻 $200$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $400$ 到达城市 $3$。
2. 第 $1$ 天时刻 $500$ 从城市 $3$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $4$。

由于没有更快的旅行方式，所以在第 $2$ 行输出 $400$。

成员 $3$ 可以按照以下行动在 $10500$ Byou 内从城市 $1$ 前往城市 $4$：

1. 第 $1$ 天时刻 $100$ 从城市 $1$ 出发，并在第 $1$ 天时刻 $300$ 到达城市 $2$。
2. 第 $1$ 天时刻 $300$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $3$。
3. 第 $2$ 天时刻 $500$ 从城市 $3$ 出发，并在第 $2$ 天时刻 $600$ 到达城市 $4$。

由于没有更快的旅行方式，所以在第 $3$ 行输出 $10500$。

这个样例输入满足子任务 $2,4,5,6$ 的限制条件。

#### 样例解释 2

这个样例输入满足所有子任务的约束条件。

### 约束条件

- $2 \leq N \leq 100,000$
- $2 \leq T \leq 10^9$
- $M_i \geq 1$（$1 \leq i \leq N - 1$）
- $M_1 + M_2 + \cdots + M_{N-1} \leq 100,000$
- $0 \leq A_{i,j} < B_{i,j} < T$（$1 \leq i \leq N - 1, 1 \leq j \leq M_i$）
- $1 \leq Q \leq 300,000$
- $1 \leq L_k < R_k \leq N$（$1 \leq k \leq Q$）
- 给定值均为整数。

### 子任务

1. (6 分) $N \leq 2,000$，$M_i = 1$（$1 \leq i \leq N - 1$）
2. (8 分) $N \leq 2,000$，$M_i \leq 5$（$1 \leq i \leq N - 1$）
3. (17 分) $M_i = 1$（$1 \leq i \leq N - 1$）
4. (23 分) $M_i \leq 5$（$1 \leq i \leq N - 1$）
5. (36 分) $N \leq 90,000$，$Q \leq 90,000$，$M_1 + M_2 + \cdots + M_{N-1} \leq 90,000$
6. (10 分) 无额外约束条件。


title: [JOISC 2024 Day4] 乒乓球

description:
在 JOI 王国举办了一场乒乓球比赛。 $N$ 只编号从 $1$ 到 $N$ 的海狸参加了这场比赛，并进行了一场循环赛。

你从 Bitaro 那里得知了关于比赛结果的以下信息。

-  没有平局比赛。
- 正好有 $M$ 种选择 $3$ 只海狸形成“三元悖论”。请注意，只有当以下两个条件之一恰好满足时，$3$ 只海狸 $i, j, k$（$1 \leq i < j < k \leq N$）才形成“三元悖论”。
- - 海狸 $i$ 击败了海狸 $j$，海狸 $j$ 击败了海狸 $k$，海狸 $k$ 又击败了海狸 $i$。
- - 海狸 $i$ 击败了海狸 $k$，海狸 $k$ 击败了海狸 $j$，海狸 $j$ 又击败了海狸 $i$。

你不确定 Bitaro 提供的信息是否正确，所以你决定思考是否有任何与 Bitaro 提供的信息相符的比赛结果。编写一个程序，根据 Bitaro 提供的信息判断是否有任何比赛结果与信息相符，如果有，找出其中任意一种比赛结果。

inputFormat:
一个测试案例包括 $Q$ 个场景，编号从 $1$ 到 $Q$。每个场景指定以下数值。

- 参加比赛的海狸数量 $N$。
- 选择 $3$ 只形成“三元悖论”的海狸的方式数量 $M$。

输入数据的格式如下。

- $Q$

每个场景的输入数据格式如下。

- $N$ $M$

outputFormat:
对应各个场景，按照以下顺序将答案写入标准输出。

在某些场景中，如果有任何与信息相符的比赛结果，请按照以下方式输出。

- Yes
- $S_2$
- $S_3$
- ...
- $S_N$

这里，$S_i$（$2 \leq i \leq N$）是一个字符为 '0' 或 '1'，长度为 $i-1$ 的字符串。$S_i$ 的第 $j$ 个字符为 '0' 表示海狸 $i$ 被海狸 $j$ 打败，为 '1' 表示海狸 $i$ 打败了海狸 $j$。如果存在多个结果，可以输出任何一个。

在某些场景中，如果没有任何与信息相符的比赛结果，请输出 No。

hint:
#### 样例解释 1

有 $Q = 2$ 个场景。

在这个示例输出中，场景 $1$ 的结果是，海狸 $1$ 打败了海狸 $2$，海狸 $2$ 打败了海狸 $3$，海狸 $3$ 打败了海狸 $1$。因此，海狸 $1$、$2$、$3$ 形成了“三元悖论”。没有其他方式选择 $3$ 只海狸，所以有确切地 $1$ 种方式选择 $3$ 只形成“三元悖论”的海狸。

对应场景 $1$ 的另一个输出如下。

```
Yes
1
01
```

在场景 $2$ 中，没有任何与信息相符的比赛结果。因此，输出 No。

这个示例输入满足子任务 $2,3,4,5,6$ 的约束条件。

#### 样例解释 2

在这个示例输出中，场景 $1$ 的结果是，海狸 $1$ 打败了海狸 $4$，海狸 $4$ 打败了海狸 $3$，海狸 $3$ 打败了海狸 $1$。因此，海狸 $1,3,4$ 形成了“三元悖论”。还有两种其他方式选择 $3$ 只形成“三元悖论”的海狸：选择海狸 $2,3,4$ 和选择海狸 $3,4,5$。因此，有确切地 $3$ 种方式选择 $3$ 只形成“三元悖论”的海狸。

这个示例输入满足所有子任务的约束条件。

### 约束条件

- $1 \leq Q$．
- $3 \leq N \leq 5000$．
- $0 \leq M \leq \frac{1}{6} N(N - 1)(N - 2)$．
- $Q$ 个场景中 $N$ 的总和不超过 5000
- 给定值均为整数。

### 子任务

1. (5 分) $M \leq N - 2$．
2. (4 分) $Q$ 个场景中 $N$ 的总和不超过 7。
3. (23 分) $Q$ 个场景中 $N$ 的总和不超过 20。
4. (30 分) $Q$ 个场景中 $N$ 的总和不超过 150。
5. (15 分) $Q$ 个场景中 $N$ 的总和不超过 600。
6. (23 分) 无额外约束。


title: [USACO03Open] Lost Cows

description:
N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.Regrettably, FJ does not have a way to sort them.

Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.Given this data, tell FJ the exact ordering of the cows.

inputFormat:
Line 1: A single integer, N

Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

outputFormat: Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

translation:
### 题目描述

有 $N$ 头奶牛，已知它们的编号为 $1∼N$ 且各不相同，但不知道每头奶牛的具体编号。

现在这 $N$ 头奶牛站成一列，已知第 $i$ 头奶牛前面有 $a_i$ 头牛编号小于它，求每头奶牛的编号。

### 输入格式

第 $1$ 行，输入一个整数 $N$

第 $2...N$ 行，每行输入一个整数 $a_i$，表示第 $i$ 头奶牛前面有 $a_i$ 头奶牛的编号小于它（因为第一头奶牛前面没有奶牛，所以 $i$ 从 $2$ 开始）。

### 输出格式

输出包含 $N$ 行，每行输出一个整数表示奶牛的编号。

第 $i$ 行输出第 $i$ 头奶牛的编号。

### 数据范围

$2 \le N \le 8000$。


title: The Luckiest Number

description: Chinese people think of '8' as the lucky digit. Bob also likes digit '8'. Moreover, Bob has his own lucky number L. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of L and consist of only digit '8'.

inputFormat:
The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000).

The last test case is followed by a line containing a zero.

outputFormat: For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the length of Bob's luckiest number. If Bob can't construct his luckiest number, print a zero.

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

中国人认为“8”是幸运数字。Bob 也喜欢数字“8”。此外，Bob 有自己的幸运数字 $L$。现在，他想构造出自己的最幸运的数字，即所有仅由数字“8”组成且是 $L$ 的倍数的正整数中的最小值。

**【输入格式】**

多个测试用例组成。每个测试用例包含一行，其中包含 $L$（$1 ≤ L ≤ 2,000,000,000$）。

最后一个测试用例后跟着一行，其中包含零。

**【输出格式】**

对于每个测试用例，输出一行，包含测试用例编号（从 $1$ 开始），后跟一个整数，该整数是 Bob 最幸运的数字的长度。如果 Bob 无法构造他最幸运的数字，则输出零。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: Cutting Game

description: Urej loves to play various types of dull games. He usually asks other people to play with him. He says that playing those games can show his extraordinary wit. Recently Urej takes a great interest in a new game, and Erif Nezorf becomes the victim. To get away from suffering playing such a dull game, Erif Nezorf requests your help. The game uses a rectangular paper that consists of $W \times H$ grids. Two players cut the paper into two pieces of rectangular sections in turn. In each turn the player can cut either horizontally or vertically, keeping every grids unbroken. After $N$ turns the paper will be broken into $N+1$ pieces, and in the later turn the players can choose any piece to cut. If one player cuts out a piece of paper with a single grid, he wins the game. If these two people are both quite clear, you should write a problem to tell whether the one who cut first can win or not.

inputFormat: The input contains multiple test cases. Each test case contains only two integers $W$ and $H (2 \le W , H \le 200)$ in one line, which are the width and height of the original paper.

outputFormat: For each test case, only one line should be printed. If the one who cut first can win the game, print "WIN", otherwise, print "LOSE".

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

Urej 喜欢玩各种类型的沉闷游戏。他通常会邀请其他人和他一起玩。他说，玩这些游戏可以展现他的非凡智慧。最近，Urej 对一个新游戏产生了极大兴趣，而 Erif Nezorf 成为了牺牲品。为了摆脱玩这样一个沉闷游戏的痛苦，Erif Nezorf 请求你的帮助。这个游戏使用一个由 $W \times H$ 格网组成的矩形纸张。两名玩家轮流将纸张切割成两个矩形部分。在每个回合中，玩家可以横向或纵向切割，保持每个格网完整。经过 $N$ 轮后，纸张将被切割成 $N+1$ 片，然后在后续的回合中，玩家可以选择任意一片进行切割。如果一名玩家切割出一个只有一个格网的纸片，他就赢得了游戏。如果这两个人都非常清楚，你应该写一个问题来告诉是否先手的玩家能赢得游戏。

**【输入格式】**

输入包含多个测试用例。每个测试用例在一行中只包含两个整数 $W$ 和 $H (2 \le W , H \le 200)$，分别表示原始纸张的宽度和高度。

**【输出格式】**

对于每个测试用例，应该只输出一行。如果先手的玩家能赢得游戏，则输出 "WIN"，否则输出 "LOSE"。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: 【MX-X4-T2】「Jason-1」加法

description:
给定两个整数 $a, b$（可能为负），你可以进行任意多次操作（也可以不操作），每次操作你需要在如下两种形式中进行选择：

- 操作 1：将 $a$ 赋值为 $a$ 与 $b$ 的和，即 $a \gets a + b$。
- 操作 2：将 $b$ 赋值为 $a$ 与 $b$ 的和，即 $b \gets a + b$。

你的目标是最小化 $a$ 与 $b$ 的差的绝对值 $\lvert a-b \rvert$，请输出最小值。

inputFormat:
**本题输入包含多组数据。**

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

- 仅一行，两个整数 $a, b$。

outputFormat:
对于每组数据：

- 仅一行一个整数，表示答案。

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

对于第 1 组数据，一种可行的操作方案是：不进行任何操作，$\lvert a-b \rvert=0$。

对于第 2 组数据，一种可行的操作方案是：先使用操作 2，$b$ 被赋值为 $10$；再使用操作 1，$a$ 被赋值为 $13$，此时 $\lvert a-b \rvert=3$，可以证明这是能够达到的最小值。

对于第 3 组数据，一种可行的操作方案是：连续使用 $5$ 次操作 1，$a$ 依次被赋值为 $-3,-2,-1,0,1$，此时 $a$ 和 $b$ 相等，$\lvert a-b \rvert=0$。

对于第 4 组数据，一种可行的操作方案是：不进行任何操作，此时 $\lvert a-b \rvert=3$。

对于第 5 组数据，一种可行的操作方案是：使用操作 2，$b$ 被赋值为 $4$，此时 $\lvert a-b \rvert=0$。

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

对该样例中的两组数据，均可先使用 $1$ 次操作 2，再使用 $3$ 次操作 1，使得差的绝对值为 $0$。

**【数据范围】**

| 测试点编号 | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: |
| 1 | A | $27$ |
| 2 | B | $31$ |
| 3 | 无 | $42$ |

- 特殊性质 A：保证 $\lvert a \rvert, \lvert b \rvert \le 10$。
- 特殊性质 B：保证 $a,b \ge 1$。

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$\lvert a \rvert, \lvert b \rvert \le 10^9$。


title: 可达性统计

description: 给定一张 $N$ 个点 $M$ 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

inputFormat: 第一行两个整数 $N,M$，接下来 $M$ 行每行两个整数 $x,y$，表示从 $x$ 到 $y$ 的一条有向边。

outputFormat: 输出共 $N$ 行，表示每个点能够到达的点的数量。

hint: 测试数据满足 $1 \le N,M \le 30000$，$1 \le x,y \le N$。


title: [语言月赛 202405] 放行李

description:
小 S 推着她的行李箱走上高铁，开启了一段精彩的旅行。

这节车厢的行李架分为左右两列，每一列分别有 $n$ 个位置，从前往后按 $1$ 到 $n$ 依次编号。对于任意两个编号为 $i$ 和 $j$ 的位置（不区分是哪一列），它们之间的距离是 $\vert i - j \vert$。

$\vert x \vert$ 代表 $x$ 的绝对值。当 $x \geq 0$，$\vert x \vert = x$；当 $x < 0$，$\vert x \vert = -x$。

用 $0$ 表示行李架左边一列，用 $1$ 来表示右边一列。小 S 的座位在 $p$ 列的编号 $q$ 的位置处（$p = 0$ 或 $1$，$1 \leq q \leq n$）。

现在小 S 想要在某个位置摆放她的行李箱。然而，已经有一些位置被其它行李占用，所以那些位置是不能摆放行李箱的。小 S 只能选择一个没有行李的空位。

在此基础上，小 S 首先希望行李箱的摆放位置距离她尽可能小。其次，如果有两个**不同列**的空位置和她的位置距离最小且相同，那么小 S 会选择和她在**同一列**的那一个位置。

现在给你左右两列的行李摆放情况，请你找到一个满足条件的最佳行李摆放位置。如果没有任何空位置，请你输出 $-1$。

inputFormat:
第一行一个整数 $n$，表示每一列位置数量。
第二行 $n$ 个 $0$ 或 $1$ 的整数，第 $i$ 个整数表示**左列**第 $i$ 个位置是否已经有行李，若为 $1$ 则有行李，若为 $0$ 则没有行李。
第三行 $n$ 个 $0$ 或 $1$ 的整数，第 $i$ 个整数表示**右列**第 $i$ 个位置是否已经有行李，若为 $1$ 则有行李，若为 $0$ 则没有行李。

第四行，两个整数 $p, q$，表示小 S 所在位置是哪一列，在这一列的哪个位置。

outputFormat:
输出一行，若有可以摆放行李的位置，则输出两个整数，分别表示最佳位置在左列还是右列，最佳位置与小 S 所在位置的**距离**。

如果没有可以放行李的位置，则输出一个整数 $-1$。

hint:
### 样例 1 解释

为了方便观察，我们用$\textcolor{green}{绿色}$来表示没有行李的空位，用$\textcolor{red}{红色}$来表示有行李。

样例 1 如图：

![](https://cdn.luogu.com.cn/upload/image_hosting/nngzg0w3.png?x-oss-process=image)

此时由于右列第 $2$ 个位置距离小 S 更近，所以右列第 $2$ 个位置是最佳位置，答案是 `1 1` （表示这个位置在右列，和小 S 位置距离为 $1$）。

### 样例 2 解释

样例 2 如图：

![](https://cdn.luogu.com.cn/upload/image_hosting/5i7shnxg.png?x-oss-process=image)

此时由于两个位置距离小 S 都相同，而左列的那个位置和小 S 在同一列，所以答案是 `0 2` （表示这个位置在左列，和小 S 位置距离为 $2$）。

### 样例 3 解释

由于没有任何一个空位，所以输出 $-1$。

### 数据范围

对于前 $30 \%$ 的数据，保证小 S 一定在左列，左列所有位置一定都有行李。
对于另 $30 \%$ 的数据，保证左列有且仅有一个空位置，右列有且仅有一个空位置。
对于 $100 \%$ 的数据，保证 $1 \leq q \leq n \leq 10^6$，$p$ 为 $0$ 或 $1$，第二行、第三行读入的整数为 $0$ 或 $1$。


title: [XJTUPC2024] 交小西的礼物

background:
小西给参加这场比赛的大家都准备了精美的礼物！

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

description: 小西准备给 $a$ 名志愿者，$b$ 支单挑队，$c$ 支双人队，$d$ 支三人队的**每个人**恰好发一份奖品，她想知道一共要发几份奖品？

inputFormat: 输入数据共一行四个整数 $a,b,c,d$ ($0 \leq a, b, c, d \leq 200$)，含义如上所述。

outputFormat: 输出数据共一行一个整数，表示总共要发的奖品数。

hint: 聪慧美丽善良的交小西想提升大家的参赛体验，她提示你：ABC 题都是简单题，**后面的题目是并不保证难度递增的**。当你在某一道题卡住时，不妨看看排行榜上其他队伍在做什么题，一般来说通过人数较多的题目会更简单哦～


title: [XJTUPC2024] 转呀转

background:
乐奈：灯，你听我说

乐奈：洗衣机好有趣的

灯：诶……洗衣机……？

乐奈：衣服一直转呀转，观察那个好有意思

乐奈：灯也可以去试试

灯：诶……？好的……！

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

  "一直转呀转好有意思！"

description: rana 和 tomorin 在观察洗衣机里的衣服的时候，发现衣服做匀速圆周运动。她们知道衣服的初始位置，观察时间以及洗衣机转速，希望你能帮她们求出初始位置到观察结束时位置的位移长度。衣服可以看成质点。

inputFormat:
输入共三行。

第一行两个整数 $x,y$ ($-1000 \leq x, y \leq 1000$)，表示衣服的初始位置**在以洗衣机中心为坐标原点的平面直角坐标系下的**坐标，单位是单位长度。

第二行一个实数 $t$ ($0 \leq t \leq 100$)，表示观察时间，单位是单位时间。

第三行一个实数 $v$ ($0 \leq v \leq 100$)，表示洗衣机转速，单位是**圈**每单位时间。

outputFormat:
输出仅一行。

输出一个实数表示答案，与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 的答案视为正确。


title: [XJTUPC2024] 榕树之心

background: 你说的对，但是《榕树之心》是一款由 Corycle, HCCH, MCPlayer542, Veritas, wh 在游戏设计与开发课上研发的策略性多人对战游戏，游戏发生在一个热带雨林，在这里，你将扮演一棵榕树的「核心」，与其他榕树竞争养分和生存空间……

description:
游戏地图由若干正六边形构成，玩家可以控制榕树核心从一个六边形的**中心**移动的另一个相邻六边形的**中心**从而加固树枝、清理害虫、长出新枝条或者摧毁其他榕树。

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

平面的正六边形网格可以看做若干立方体堆叠出的立体图形的正等轴测图（如图），每个立方体的投影都是一个正六边形，于是立方体的空间坐标可以用来表示正六边形坐标。我们规定某一立方体中心位于原点，所有正方体中心坐标 $(x,y,z)$ 都满足 $x+y+z=0$，所以可以省略一维，用 $(x,y)$ 来描述其对应正六边形的中心。这种坐标系统叫做**纵向坐标**。

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

游戏使用**纵向坐标**描绘六边形的位置，为了让玩家直观地看到核心的位置，Veritas 需要将其转化为**平面直角坐标**以便在屏幕上显示，**请你帮助他将纵向坐标转换成平面直角坐标**。

纵向坐标 $(x,y)$ 到平面直角坐标 $(x^\prime,y^\prime)$ 的转换公式为：

$$x^{\prime} = \frac{1}{2} x + \frac{1}{2} y$$

$$y^{\prime} = \frac{\sqrt{3}}{2} x - \frac{\sqrt{3}}{2} y $$

inputFormat: 仅一行，有两个用空格隔开的整数 $x,y$，表示纵向坐标 $(x,y)$ ($-10^6\le x\le 10^6,-10^6\le y\le 10^6$)。

outputFormat:
一行两个实数 $x^{\prime}$ 和 $y^{\prime}$，用空格隔开，表示转换得到的平面直角坐标 $(x^\prime,y^\prime)$。

当你输出的两个实数与答案的相对误差或者绝对误差的较小者不超过 $10^{-6}$ 时视为正确。


title: [XJTUPC2024] 瑟莉姆的宴会

background:
欢迎来到瑟莉姆大人的享乐宴会！

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

description:
宴会中一共有 $n$ 个访客，编号 $1\sim n$。为了更好地控制影的力量，瑟莉姆要求有 $n-1$ 个访客都恰好受到另一个访客的支配，而剩下的那个人成为总支配者，支配其他 $n-1$ 名访客。访客间的**直接支配关系**构成了一棵有根树。

对于这棵树来说，若结点 $a$ 的父结点是 $b$，那么称 $b$ 支配了 $a$，同时称 $b$ 是 $a$ 的**直接支配者**。同时，支配的关系具有**传递性**，即若 $a$ 支配 $b$，$b$ 支配 $c$，那么 $a$ 也就支配了 $c$。

另外有 $m$ 个支配条件，一个支配条件是一个有序二元组 $(x,y)$ ($1 \le x,y \le n$，$x\neq y$)，若访客 $x$ 支配 $y$，那么影的力量会增加 $1$ 点；若 $y$ 支配 $x$ ，那么影的力量会减少 $1$ 点。若两者互不支配，那么影的力量不变。初始的影的力量是 $0$。

作为贴心仆人的松雀需要组织一场宴会，那么需要为宴会中的每个人安排支配关系。由于瑟莉姆大人不需要关心影的力量能够达到多大，只需要让影的力量保持非负，你能够帮助她构造最终的支配关系吗？

若存在多个解，你只需要输出任意一个。保证对于任何合法输入，均存在解。

inputFormat:
第一行输入两个正整数 $n,m$ ($1\le n \le 1\times 10^5,\ 1 \le m \le 2\times 10^5$)，表示访客数量和支配条件数，用空格隔开。

接下来 $m$ 行，每行两个用空格分隔的正整数 $x,y$ ($1 \le x,y \le n,\ x\neq y$)，表示一个支配条件的二元组 $(x,y)$。支配条件可能会重复，也可能会出现相反的支配条件，即既出现了 $(x,y)$，也出现了 $(y,x)$。支配条件两两互不影响。

outputFormat: 输出一行 $n$ 个数，第 $i$ 个数表示编号为 $i$ 的访客的直接支配者编号。总支配者的直接支配者编号为 $0$。

hint: 样例中最终影的力量是 $1-1-1+0+1=0$，符合非负条件。


title: [XJTUPC2024] 雪中楼

description:
西安交通大学下雪了，所有楼顶都被积雪覆盖。

在梧桐道上有 $n$ 座房子，自南向北第 $i$ 座房子的标号是 $i$，所有房子的高度互不相同。LNC 从南向北，依次登上每栋楼楼顶，然后他会回头观察他已经到达过的房子，并记录下这些房子中，比当前他所在房子矮的所有房子中，最高的房子的编号，记为 $a_i$。特殊的，当没有房子比当前房子矮的时候，$a_i=0$。

现在给你所有的 $a_i$，要求你还原出所有楼的大小关系。由于高度的具体值未知，你只需要按照高度从低到高，输出房子编号。

可以证明对于任何合法的输入，均存在唯一解。

inputFormat:
输入第一行一个正整数 $n$ ($1\le n \le 2\times 10^5$)，代表房子个数。

接下来一行 $n$ 个非负整数 $a_i$，满足 $0\le a_i <i$，两两之间用空格隔开。

outputFormat: 输出一行 $n$ 个正整数构成的排列，用空格隔开，表示最终的答案。

hint: 假设高度是一个 $1\sim n$ 的排列，那么可以发现高度为 $5, 3, 2, 1, 4$ 是唯一的解，按照高度排名输出得到 $4, 3, 2, 5, 1$。


title: [XJTUPC2024] Everyone's ALL IN

description:
女士们，先生们。

早上好，中午好，以及晚上好。

欢迎来到“好得不能再好了！泰拉大师投资课”，我是你们的坎老师。

不要 10000，不要 5000，只需要 999 源石锭，一对一指导，手把手教学，从入门到精通，让你：

——**每选必赢，每投必中**，快速实现财富自由，富甲一方！

今天我们来到的地点是——**卡西米尔骑士锦标赛**。

本次的赛事有点不同，首先， $N$ 位骑士将自行组成骑士团，其中第 $i$ 号骑士将进入第 $a_i$ 号骑士团；

然后接下来的 $M$ 天里，每天将指定两个不同的骑士团 $x$ 和 $y$ ，接下来每一位 $x$ 骑士团里的成员都和每一位 $y$ 骑士团里的成员进行一次比试。

我们每一次比试将会下注，如果两位骑士的编号分别为 $a$ 和 $b$，那么如果你下注成功了，你将获得你的本金和 $a\times b$ 的源石锭。

当然了，每次下注你需要压上你的**所有本金**！

那么请问，接下来的 $M$ 天里，在我的指导下你每天分别可以获得多少源石锭？

**数据保证答案不超过 64 位有符号整型能表达的范围。**

**赌博有风险，投资需谨慎！**

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

inputFormat:
输入第一行两个正整数 $N$ ($1\le N \le 2\times 10^5$) 和 $M$ ($1\le M \le 2\times 10^5$)，由空格隔开。

接下来一行有 $N$ 个由空格隔开的正整数 $a_i$ ($1\le a_i \le 1\times 10^6$) ，表示编号为 $i$ 的骑士所在的骑士团的编号。

接下来 $M$ 行，每行两个由空格隔开的正整数 $x_i,y_i$ ($x_i \neq y_i$)，保证 $x_i,y_i$ 出现在 $a_1 \sim a_n$ 中。

outputFormat:
输出共 $M$ 行，每行一个正整数，第 $i$ 行表示第 $i$ 天可以获得的最大收益。

**数据保证答案不超过 64 位有符号整型能表达的范围。**

hint:
骑士团 $1$ 的成员有 $\{1,2,9\}$，骑士团 $2$ 的成员有 $\{3,4,8\}$，骑士团 $3$ 的成员有 $\{5,6,7\}$。

第一天，骑士团 $1$ 和骑士团 $2$ 进行比赛。

获得的收益为：$1\times 3+1\times 4+1\times 8+2\times 3+2\times 4+2\times 8+9\times 3+9\times 4+9\times 8=180$。

第二天，骑士团 $2$ 和骑士团 $3$ 进行比赛。

获得的收益为：$3\times 5+3\times 6+3\times 7+4\times 5+4\times 6+4\times 7+8\times 5+8\times 6+8\times 7=270$。

第三天，骑士团 $1$ 和骑士团 $3$ 进行比赛。

获得的收益为：$1\times 5+1\times 6+1\times 7+2\times 5+2\times 6+2\times 7+9\times 5+9\times 6+9\times 7=216$。


title: [XJTUPC2024] 循环移位

description:
给定长度为 $2^n$ 的数组 $a_i$ ($0 \leq i < 2^n$)，你可以进行任意次循环移位。

求 $\sum_{i=0}^{2^n-1} a_i \oplus i$， $\sum_{i=0}^{2^n-1} a_i \& i$，$\sum_{i=0}^{2^n-1} a_i | i$ 的最大值。其中 $\oplus, \&, |$ 分别代表按位异或，按位与，按位或。

对于一个长度为 $m$ 的数组 $x_i$ ($0 \leq i < m$)，其进行循环移位的结果 $x'_i$ 为:

$$x'_i = \left\{
	\begin{array}{ll}
		x_{i - 1} & i \neq 0 \\
		x_{m - 1} & i = 0
	\end{array}\right.$$

inputFormat:
输入第一行包含一个整数 $n$ ($1 \leq n \leq 20$)，含义如题意所述。

接下来一行包含 $2^n$ 个整数 $a_i$ ($0 \leq a_i < 2^n$)，为给定的数组。

outputFormat: 输出一行三个整数，由空格隔开，为 $\sum_{i=0}^{2^n-1} a_i \oplus i$，$\sum_{i=0}^{2^n-1} a_i \& i$，$\sum_{i=0}^{2^n-1} a_i | i$ 的最大值。


title: [XJTUPC2024] 图上操作

description:
你有一张 $n$ 个点 $m$ 条边的**有向图**，点的下标为 $1\sim n$。每条边有一个正整数边权 $d_i$。特殊的，$1\le d_i \le 100$。

现在定义点 $i$ 的瓶颈路大小为：所有从点 $1$ 到点 $i$ 的有向路径中，最小边权的最大值。特殊的，若 $i$ 不能从 $1$ 出发到达，则其瓶颈路权值为 $0$。

有 $q$ 次修改，每次修改会指定一条边，将这条边的边权降低，保证降低后依然是正整数。

现在要求每次修改后，输出编号为 $2\sim n$ 的点的瓶颈路大小。注意，每次修改是在前面修改的基础上进行操作，并不是相互独立的。

由于输出数据量过于巨大，设每次修改完后点 $i$ 的瓶颈路大小为 $ans_i$，你只需要输出 $(\sum_{i=2}^n ans_i \times 2^i)\bmod 998244353$。

inputFormat:
第一行三个正整数 $n,m,q$ ($2\le n\le 1\times 10^5$，$1\le m \le 2\times 10^5$，$1\le q\le 2\times 10^5$) 由空格隔开，含义如题所述。

后面 $m$ 行每行两个正整数 $s_i,t_i,d_i$ ($1\le s_i,t_i\le n$，$s_i\neq t_i$，$1\le d_i \le 100$) 由空格隔开，表示存在一条 $s_i$ 到 $t_i$ 的有向边，边权为 $d_i$，这条边的编号为 $i$。保证无自环，但可能会有重边。

再后面 $q$ 行每行两个正整数 $x,y$ ($1\le x\le m$，$1\le y < d_x$) 由空格隔开，表示将编号为 $x$ 的边的权值下调 $y$，且保证下调以后大于 $0$。

outputFormat: 输出 $q$ 行每行一个非负整数，表示你求得的答案。

hint:
第一次修改后，$2$ 号点的瓶颈路大小为 $3$，$3$ 号点的瓶颈路大小为 $4$。

第二次修改后，$2$ 号点的瓶颈路大小为 $3$，$3$ 号点的瓶颈路大小为 $3$。

第三次修改后，$2$ 号点的瓶颈路大小为 $1$，$3$ 号点的瓶颈路大小为 $2$。

第四次修改后，$2$ 号点的瓶颈路大小为 $1$，$3$ 号点的瓶颈路大小为 $2$。


title: [XJTUPC2024] 命令行

description:
有 $n$ 个两两互不相同的仅由小写字符构成的命令字符串 $t_i$ ($1 \leq i \leq n$)，你需要实现一个支持命令补全的命令行。

你的输入区是一个字符串 $s$，他可以接受小写字母 $\text{'a'-'z'}$ 和 $\text{Tab}$ 键 (以 $\text{'T'}$ 表示)，$\text{Enter}$ 键 (以 $\text{'E'}$ 表示)，$\text{Backspace}$ 键 (以 $\text{'B'}$ 表示)。规则如下所述:

1. 当你接受小写字符 $c$，将把 $c$ 追加到输入区字符串 $s$ 的末尾。

1. 当你接受 $\text{Backspace}$ 键，将尝试删除最后一个字符:
   - 如果输入区字符串 $s$ 为空，则不进行任何操作。
   - 如果输入区字符串 $s$ 非空，则丢弃 $s$ 末尾的字符。
1. 当你接受 $\text{Tab}$ 键，将会对 $s$ 进行一次智能补全，补全规则如下:
	- 设以 $s$ 为前缀的命令字符串集合为 $T$。
   - 如果 $T$ 为空，则不进行任何操作。
   - 如果 $T$ 非空，则把 $s$ 置为 $\text{lcp}(T)$。这里 $\text{lcp}$ 代表最长公共前缀，含义是最长的，是 $T$ 中每一个字符串前缀的字符串。

1. 当你接受 $\text{Enter}$ 键，将会试图执行命令 $s$:
	- 如果存在命令字符串 $t_i = s$，则输出命令编号 $i$。
   - 如果不存在命令字符串 $t_i = s$，则输出 $-1$。
   - 无论是否执行成功，清空输入区 $s$。

给定你接受到的输入串 $p$，你需要输出每个 $\text{Enter}$ 键执行的结果。

inputFormat:
输入第一行为两个整数 $n$ 和 $m$ ($1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^6$)，为命令字符串的个数和输入串的长度，由空格隔开。

接下来 $n$ 行，每行一个仅由小写字符构成的字符串 $t_i$，为命令串。保证有 $\sum_{i=1}^{n} |t_i| \leq 10^6$ 且命令串互不相同。

最后一行为字符串 $p$ ($|p|=m$)，为输入串。保证 $p$ 仅由 $\text{\{'a'-'z', 'T', 'B', 'E'\}}$ 组成。

samples:
7 40
kill
killall
rm
rmdir
ifconfig
ifdown
ll
kTBlEkTaTEiTcBdTElTExjtuTExjtuBBBBBrTdTE

hint:
初始时，输入区字符串$s=""$。

输入 $\text{'k'}$ 后，输入区字符串$s="k"$。

输入 $\text{'T'}$ 后，进行智能匹配。此时 $T=\{"kill","killall"\}$，$\text{lcp}(T)="kill"$。故输入区字符串$s="kill"$。

输入 $\text{'B'}$ 后，输入区字符串$s="kil"$。

输入 $\text{'l'}$ 后，输入区字符串$s="kill"$。

输入 $\text{'E'}$ 后，因为 $t_1=s$，所以应该输出 $1$。


title: [XJTUPC2024] 最后一块石头的重量

description:
有一堆石头，用整数数组 $a$ 表示。其中 $a_i$ 表示第 $i$ 块石头的重量。

每一回合，从中选出**任意两块石头**，然后将它们一起粉碎。假设石头的重量分别为 $x$ 和 $y$，且 $x \le y$。那么粉碎的可能结果如下：

- 如果 $x = y$，那么两块石头都会被完全粉碎；
- 如果 $x \neq y$，那么重量为 $x$ 的石头将会完全粉碎，而重量为 $y$ 的石头新重量为 $y-x$。

最后，**最多只会剩下一块**石头。输出此石头**最小的可能重量**。如果没有石头剩下，就输出 $0$。

inputFormat:
输入数据共两行。

第一行输入一个整数 $n$ ($1 \leq n \leq 10000$)，表示石子的数量；

第二行输入 $n$ 个整数 $a_i$ ($1 \leq a_i \leq 5000$)，表示第 $i$ 块石头的重量。

outputFormat:
输出数据共一行。

第一行输出一个整数表示答案。


title: [XJTUPC2024] 崩坏：星穹铁道

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

Corycle 喜欢玩一个由米哈游自主研发的一款回合制战斗游戏------《崩坏：星穹铁道》。这片银河中有名为「星神」的存在，他们造就现实，抹消星辰，在无数「世界」中留下他们的痕迹。你将由此探索新的文明，结识新的伙伴，在无数光怪陆离的「世界」与「世界」之间展开新的冒险。所有你想知道的，都将在群星中找到答案。

description:
在游戏《崩坏：星穹铁道》中，你的队伍里会有四名角色轮流行动，所有角色共享用于施放战技的战技点。当战斗开始时，你会获得 $k$ 个战技点，且战技点的上限为 $5$ 个。每个角色行动时可选择进行普通攻击或者施放战技，进行普通攻击时会为全队增加一个战技点，当战技点达到上限时也可以进行普通攻击，但是此时不回复战技点。角色施放战技需要消耗一个战技点，当没有战技点时只能进行普通攻击而不可释放技能。

Corycle 想成为星穹铁道高手，为此他需要对自己的配队了如指掌。由于角色有多种职业，同时为了方便对角色类型进行定位，他把角色的行动模式分为了三种类型：

1. 当角色行动时，只会进行普通攻击。

2. 当角色行动时，若有战技点不少于 $1$ 则必定释放技能，否则进行普通攻击。

3. 不对角色的行动进行限制。

现在 Corycle 开始了一场战斗，他想知道当队伍中的四名角色一共行动 $n$ 次时，可能会有多少种不同的行动方案。我们称两个行动方案不同，当且仅当存在至少一个回合中，两个方案里角色行为不同。这个答案可能是一个很大的数，所以请将答案对 $998244353$ 取模。

inputFormat:
输入第一行有两个正整数 $n$ 和 $k$ ($1\le n\le 1\times 10^{18},0\le k\le 5$)，表示总行动次数与初始战技点数，用空格隔开。

第二行有四个用空格隔开的正整数 $a_1,a_2,a_3,a_4$ ($1 \le a_1,a_2,a_3,a_4 \le 3$)，表示四名角色的行动模式类型。

outputFormat: 输出仅一个整数，表示不同的行动方案数。


title: [XJTUPC2024] 勘探队

description:
一支勘探队从 $(0,0)$ 出发，终点是 $(0,y)$，携带着从 $1$ 号到 $n$ 号设备，每个设备的重量为 $m_i$，且必须安放在横坐标为 $x_i$ 的任意位置上（纵坐标可以是任意实数）。必须按照顺序安放所有设备，在较小编号的设备被全部放置之前，即使横坐标位置满足，也不能放置。

当勘探队身上的设备总重量为 $m$ 时，其移动一单位长度的代价是 $m+M$。问勘探队完成所有设备安装并到达终点的最小代价。

同一个坐标位置可以放置多台设备。

inputFormat:
输入第一行三个正整数 $n$ ($1\le n \le 1\times 10^4$)，$M$ ($0< M \le 30$) 和 $y$ ($0<y\le 2\times 10^5$)，代表设备个数、移动的基本代价和最终终点的纵坐标。

第二行给出 $n$ 个非负整数 $m_i$ ($0< m_i\le 30$)，表示第 $i$ 台设备的重量。两两之间用空格隔开。

第三行给出 $n$ 个整数 $x_i$ ($|x_i|\le 1\times 10^4$)，表示第 $i$ 台机器坐标的要求。

outputFormat: 输出一行一个正实数代表最终代价。如果你的答案是 $a$，我们给出的标准答案是 $b$，你的答案正确当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$。

hint: 走直线走到 $(12,5)$，距离 $13$，然后走直线走到 $(0,14)$，距离 $15$，总代价 $13\times (25+14)+15\times 25=882$。不存在一个比这个更优的解。


title: [XJTUPC2024] 生命游戏

background:
在著名的生命游戏中，二维方格中每个细胞死或活的状态由它周围的八个细胞（上、下、左、右、左上、左下、右上、右下）所决定。

具体规则如下：

孤单死亡：如果细胞的邻居小于等于 1 个，则该细胞在下一次状态将死亡；

拥挤死亡：如果细胞的邻居在 4 个及以上，则该细胞在下一次状态将死亡；

稳定：如果细胞的邻居为 2 个或 3 个，则下一次状态为稳定存活；

复活：如果某位置原无细胞存活，而该位置的邻居为 3 个，则该位置将复活一个细胞。

在此规则下也出现了很多有趣的图形，比如说下图就是"轻量级飞船"连续的五个回合的情况：它的周期是 4，每 2 个回合会向右边走一格。

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

description:
现在我们将在树上进行简化版的生命游戏，首先将给出一棵含有 $n$ 个点，$n-1$ 条边的树和一个整数 $k$。

在每回合时，当前剩余的度数为 $k$ 的点及与其连接的边会瞬间同时被删去。

形式化的，每回合都将按顺序进行如下操作：

   -  统计当前剩余每个点的度数（一个点的度数定义为为，这个点当前连接的边的条数）。
   - 将所有度数**恰好**为 $k$ 的点标记。
   - 将上一步标记的点及其连接的边全部删去。

我们希望知道在无穷多回合后，这棵树将被分为多少个连通块。若最终两个点能够直接或间接的通过若干条边相连，则认为这两个点属于同一个连通块。

inputFormat:
第一行两个整数 $n,k$ ($0\le k < n \le 10^6$)，用空格隔开。

接下来 $n-1$ 行，每行两个用空格隔开的正整数 $u_i,v_i$ ($1\le u_i, v_i \le n$) 表示 $u_i$ 和 $v_i$ 之间有一条边。

输入的数据量较大，建议使用快速的读入方式。

outputFormat: 共一行一个整数，表示无穷多回合之后剩余的连通块个数。

hint:
对于样例 1:

这棵树的初始形态为：

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

其中三个点的度数依次为 $1,2,1$。

在一回合过后，点 $1,3$ 被删除。

这棵树变为：

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

容易发现之后这棵树的形态将不会变化，所以最终的连通块个数是 $1$。

对于样例 2：

初始形态为：

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

一回合之后变为：

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

之后保持不变，最终连通块个数为 $2$。

对于样例 3：

初始形态：

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

一回合之后变为：

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

再过一回合之后变为：

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

之后保持不变，最终连通块个数为 $5$。


title: [XJTUPC2024] 圣诞树

description:
有一棵 $n$ 个点的树，点的编号为 $1\sim n$，每个树的结点都有一个颜色，用 $col_i$ 表示。不同的 $col_i$ 代表不同的颜色。

小 L 要用这棵树制作很多棵圣诞树。一棵树能够被制作成圣诞树，当且仅当它有至少 $k$ 种不同的颜色。小 L 要把树分成若干互不相交的联通块，并且取出满足条件的联通块制作圣诞树。

在给出这棵树的形态后，问最多能制作出多少棵圣诞树？

inputFormat:
输入第一行两个正整数 $n,k$ ($1\le k \le n \le 2\times 10^5$)，用空格隔开。

第二行 $n$ 个正整数 $col_i$ ($1\le col_i \le n$)，代表结点 $i$ 的颜色，两两之间用空格隔开。

接下来 $n-1$ 行，每行两个正整数 $x,y$ ($1\le x,y \le n$，$x \neq y$)，代表树上一条边的两个端点，用空格隔开。

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


title: [XJTUPC2024] 筛法

description:
在算法竞赛的数论知识中，我们接触过埃拉托斯特尼筛法、线性筛法、莫比乌斯反演、杜教筛、Powerful Number 筛、Min\_25 筛、洲阁筛等算法来帮助我们优化一些求和/连乘的复杂度，那么现在问题来了，今天这道题将会使用到上述的哪个算法呢？

现在给定正整数 $n$，需要你求

$$
\sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor \dfrac{n}{\max(i,j)}\rfloor [i \perp j]
$$

其中 $[i \perp j]$ 表示 $i,j$ 是否互素，即当 $\gcd(i,j)=1$ 时，$[i \perp j]$ 的值为 $1$，其余情况其值为 $0$。

inputFormat: 输入一行一个正整数 $n$ ($1\le n \le 10^9$)。

outputFormat: 输出一行一个整数，表示这个和式的结果。


title: 【MX-X1-T4】「KDOI-05」简单的字符串问题

description:
你有一个字符串 $S$。$q$ 个询问，每次给出 $(i,k)$，求有多少个非空字符串 $A$，使得存在可空字符串 $B_1,B_2,\dots,B_{k-1}$ 满足：

$$S[1,i]=AB_1AB_2A\dots AB_{k-1}A$$

其中 $S[1,i]$ 表示 $S$ 的长度为 $i$ 的前缀。

inputFormat:
第一行一个正整数 $n$ 表示 $S$ 的长度。

接下来一个长度为 $n$ 且仅包含小写字母的字符串表示 $S$。

接下来一行一个正整数表示 $q$。

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

outputFormat: 输出 $q$ 行，每行一个非负整数表示答案。


title: 【MX-X4-T6】「Jason-1」电梯

description:
一栋 $n$ 层的楼有 $m$ 部电梯，每部电梯有静止与运动两种状态。

初始时，第 $i$ 部电梯静止于第 $i$ 层。给定一个 $1 \sim m$ 的排列 $p$，你希望最终第 $i$ 部电梯位于 $p_i$ 层。

你可以进行以下两种操作：

- `0`：让时间向后运动一个时刻。
- `x`：其中 $x$ 为不超过 $n$ 的正整数。
	- 执行该操作时，需要满足：$x$ 层不存在静止的电梯；距离 $x$ 层距离最近的$^\dagger$ 静止的电梯存在且唯一。
	- 令 $y$ 为最近的静止的电梯编号，$z$ 为其位置。则电梯 $y$ **立刻**变为运动的电梯，并在 $\lvert x - z\rvert$ 时刻后的**所有操作前**到达楼层 $x$ 并变为静止的电梯。

$^\dagger$：位于 $a$ 层的一部电梯与楼层 $x$ 的距离为 $\lvert a - x\rvert$。

**注意：你需要保证，任何时刻不存在两个静止的电梯位于同一楼层。**

对于每组数据，有一个评分参数 $o$，你需要构造出总操作次数不超过 $o$ 的方案才能通过该组数据。

本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。

inputFormat:
**本题输入包含多组数据。**

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

- 第一行，四个正整数 $Q, n, m, o$，分别表示询问组数、楼层数、电梯数、与评分参数。
- 接下来 $Q$ 行，每行 $m$ 个整数 $p_1, \ldots, p_m$，表示电梯的目标位置。

outputFormat:
对于每组数据：

- 共 $2 Q$ 行。对于每个询问，输出两行：
- 第一行，一个非负整数 $k$，表示你的方案的操作步数；
- 第二行，$k$ 个 $[0, n]$ 中的整数，表示你的具体操作方案。

本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。


title: 物理实验 (easy)

background: 莲子为了完善她的论文，决定研究一些物体的物理性质。由于工作实在是太多，她邀请你帮忙完成其中的一个小实验。

description:
**这是该题的简单版本，两个版本之间的区别在于小球需要满足的条件不同。该题的满分为 50 分。**

莲子有一个初始在数轴 $0$ 点并向数轴正方向移动的小球。她在数轴的 $1$ 到 $n$ 这 $n$ 个点上设置了装置，当小球经过点 $i$ 时，她可以花费 $a_i$ 的代价让其改变移动方向（从数轴正方向切换为负方向，或者相反）。

莲子有 $m$ 个需要满足的条件，第 $i$ 个条件形如“小球需要从点 $x_i$ 移动到点 $y_i$ 至少一次”，**其中** $x_i$ **大于** $y_i$。更详细的说，该条件即要求小球的移动路径形如 $\ldots \to x_i\to\ldots\to y_i\to\ldots$。

莲子想要知道她至少要花费多少代价才能满足所有条件。

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

第二行 $n$ 个正整数描述序列 $a$。

接下来 $m$ 行中，第 $i$ 行依次给出两个正整数表示 $x_i$ 和 $y_i$。

outputFormat: 一行一个整数，表示莲子至少要花费多少代价才能满足所有条件。

hint:
### 样例解释

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

如图所示给出了两个样例的移动路线。数轴上方的是在每个点转向的代价，下方的是坐标。

#### 样例 \#1

莲子让小球在经过点 $2$ 时反转方向恰好能满足所有条件，总花费代价为 $2$。
#### 样例 \#2

莲子让小球在经过点 $3$ 时反转方向恰好能满足所有条件，总花费代价为 $3$。

### 数据范围

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

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,m\le } & \bm{a_i\le} & \bm{x_i,y_i\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline
1 & 10 & 10 & 100 & 10 & - &-\cr\hline
2 & 10 & 10^3 & 10^8 & 10^3 & -&1 \cr\hline
3 & 30 & 2\times 10^5 & 10^8 & 2\times 10^5 & -&1,2  \cr\hline
\end{array}
$$

对于所有数据满足：$1\le n,m\le 2\times 10^5$，$1\le a_i\le 10^8$，$1\le y_i< x_i \le n\le 2\times 10^5$。


title: 选择困难症

background:
Parviz 认为，如果一道题有一个可以显著优化复杂度的方法而不去使用，那这题就是有遗憾的。

Alice 认为，任何算法难度大于思维难度的题，出在正式比赛中都是没有意义的。

猫猫认为，ta 是学数学学的。

$\textsf{linyue}$ 认为……啊？你们在说啥？

很有喜剧效果的是这四个名字你可能都没法一下子对上号（

description:
Alice 与 Bob 在下棋之余，也需要一些娱乐活动来放松身心，比如去小吃街吃饭。作为一名绅士，Bob 每次都让 Alice 选择要去吃哪家。这却让 Alice 犯了难——她有选择困难症。

小吃街有 $n$ 家饭店，在第 $i$ 家就餐需要 $i$ 元钱。如果预算为 $a$ 元，则可以选择前 $a$ 家餐厅。

在长期的纠结后，Alice 想到一种方法：她提前在心里想好一个非负整数 $k< \text{lcm}_{i=1}^{n} i$ ，在得知预算 $a$ 之后，选择在第 $(k$ $\text{mod}$ $a)+1$ 家餐厅就餐。

由于买棋盘与棋子的市场价格浮动，每次就餐的预算未必相同，但都是 $[2,n]$ 之间的整数。Alice 想每次都换换口味，希望对于不同的 $a$，最后选定的餐厅各不相同。她想要知道满足要求的 $k$ 的个数，但又忙于与 Bob 下棋没有时间算，于是只好求助于你啦。

形式化地说，对于给定的 $n$，你需要求有多少个整数 $k \in [0, \text{lcm}_{i=1}^{n}i)$ ，满足 $k\bmod 2,k\bmod3 ,..., k\bmod n$ 各不相同。答案对 $998244353$ 取模。

inputFormat:
第一行一个整数 $T$，表示共有 $T$ 组数据。

接下来 $T$ 行，每行一个整数 $n$ ，含义见题面。

outputFormat: 共 $T$ 行，每行一个整数，表示满足要求的 $k$ 的数量。


title: 下头论文

background: 莲子一直在苦恼关于论文的灵感。她为此花了太多时间，以至于没有时间理会她的伙伴梅莉。

description:
一天，莲子发现了一个绝妙的点子，并希望通过实验等过程将其完善。具体来说，**她需要依次完成 $n$ 项任务**，其中第 $i$ 项任务需要连续的 $a_i$ 天来完成。也就是说，假设她在第 $x$ 天开始该任务，那么她会在第 $x+a_i-1$ 天结束后完成该任务，她需要保证这些天里她都是空闲的。

不幸的是，她有 $m$ 天有各种事要去做，这些非空闲的日子会以一个单调递增序列 $b$ 的形式给出。即，对于任意的 $i(1\leq i<m)$，满足 $b_i<b_{i+1}$。

莲子希望完成任务的时间越短越好。例如：不妨假设，莲子要完成 $2$ 项任务，第一项耗时 $2$ 天，第二项耗时 $3$ 天，而第 $4$ 天莲子有事情要去做。则下图呈现了一种方案，使得莲子完成任务的时间尽可能短，为 $7$ 天：

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

她想要知道，在最好情况下，她能在第几天结束后完成所有任务。

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

第二行 $n$ 个正整数描述序列 $a$。

第三行 $m$ 个正整数描述序列 $b$。保证 $b$ 为单调递增序列。

outputFormat: 一行一个整数，表示莲子最快能在第几天结束后完成所有任务。

hint:
### 样例解释

#### 样例 \#1

即在题面中提及的情况。莲子在第 $1$ 天开始第一项任务，在第 $2$ 天结束后完成第一项任务。由于第 $4$ 天有事，她不能从第 $3$ 天开始第二项任务，于是她只好从第 $5$ 天开始该任务，在第 $7$ 天结束时完成全部任务。

注意到该样例符合 $\textbf{Subtask 2}$ 的特殊性质。
#### 样例 \#2

莲子在第 $2$ 至第 $4$ 天**依次**完成了所有任务。

### 数据范围

**本题采用捆绑测试。每一个 Subtask 内的测试点均需通过才能获得该 Subtask 的分数。**

简记：$\sum a_i$ 为所有 $a_i$ 的和，即 $a_1+a_2+\dots+a_n$。其他试题中若无特殊说明也以此解释为准。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,m\le } & \bm{\sum a_i\le} & \bm{b_i\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline
1 & 20 & 10 & 100 & 100 & - &-\cr\hline
2 & 20 & 10^5 & 10^8 & 10^8 & m=1&- \cr\hline
3 & 20 & 10^3 & 10^8 & 10^8 & \mathbf{-}&-  \cr\hline
4 & 40 & 10^5 & 10^8 &  10^8& -&1,2,3 \cr\hline
\end{array}
$$

对于所有数据满足：$1\le n,m\le 10^5$，$1\le a_i \le \sum a_i\le 10^8$, $1\le b_i\le 10^8$，$b$ 为单调递增序列。


title: 双人游戏

background: 写完论文的莲子终于意识到了这么多天埋头写论文而不理会梅莉的错误，并打算约梅莉出来玩。为此，她构思了一个有趣的双人游戏。

description:
莲子构思了一个双人游戏，不妨令游戏的两个玩家为小 R 和小 M，规则如下：

有一个 $1\times n$ 的棋盘。初始时，棋盘上有一些黑色棋子，一些白色棋子，和 $m$ 个空格子。我们可以用一个长度为 $n$ 的字符串 $s$ 来描述初始时的棋盘，若 $s_i$ 为 `B` 则代表该位置为黑棋子，为 `W` 则代表白棋子，为 `_` 则代表空格子。**请注意，棋盘上可能没有空格子。**

游戏开始前，除了棋盘的初始状态，两人还会获得一个操作序列 $O=[\lang c_1,x_1\rang, \lang c_2,x_2\rang, \cdots,\lang c_m,x_m\rang]$，其中二元组 $\lang c_i,x_i\rang$ 满足 $c_i\in\{\mathtt{R}, \mathtt{M}\}$ 且 $x_i$ 位置此时是一个空格子，表示在第 $i$ 步，玩家小 $c_i$ 应该在 $x_i$ 位置放上一个黑色棋子或者白色棋子。序列 $O$ 对双方公开，也就是说双方均知道每一步是由谁在哪个位置放上一枚棋子。

游戏过程中，双方会按照该操作序列进行操作。第 $i$ 轮时小 $c_i$ 在 $x_i$ 位置放置一枚棋子，棋子的颜色由该玩家决定。在游戏结束时所有格子都被放上了恰好一枚棋子。

小 R 希望游戏结束后棋子组成的**极长同色连续段数**$^*$尽可能多，而小 M 则希望其尽可能少。试着求出两人都以最优方式摆放棋子的话最后的连续段数为几。容易证明答案是一个定值。

注：一个棋子的极长同色连续段被定义为一个二元组 $(l,r)$ 满足 $l\le r$，且从左至右数第 $l$ 个棋子到第 $r$ 个棋子颜色相同，且第 $l-1$ 个和第 $r+1$ 个棋子要么不存在，要么与前面所说的棋子颜色不同。

inputFormat:
第一行两个整数 $n,m$，其中 $m$ 代表棋盘上的空格子数量。

第二行一个长度为 $n$ 的字符串 $s$，描述棋盘的每个格子的状态。

对于接下来的 $m$ 行：第 $i$ 行一个字符 $c_i$ 和一个正整数 $x_i$，描述第 $i$ 回合操作的玩家和她放置棋子的位置。

outputFormat: 输出一行一个整数，表示两人都以最优方式摆放棋子的话最后的连续段数为几。

hint:
### 样例解释

#### 样例 \#1

最终的棋子摆放结果为 `BWW`，可以证明两人这样摆均为最优。极长连续段数为 $2$。
#### 样例 \#2

为了让连续段数尽可能大，先手摆放两个空格子的小 R 一定会让两个格子的棋子颜色不同。然后小 M 会放置一个任意颜色的棋子。有多种可能的最终摆放结果，其中一种为 `BWW`，极长连续段数为 $2$。

注意到该样例符合特殊性质 $\mathbf{B}$。
#### 样例 \#3

最终的棋子摆放结果为 `BWBWB`，极长连续段数为 $5$。

注意到该样例符合特殊性质 $\mathbf{A}$。

### 数据范围

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

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

特殊性质 $\mathbf{A}$：保证要么 $c_i$ 均为 $\tt R$，要么 $c_i$ 均为 $\tt M$。\
特殊性质 $\mathbf{B}$：保证 $s$ 中所有字母均为 $\tt \_$。

对于所有数据满足：$\red0\le m\le 2\times 10^5 $，$1\le n\le 2\times 10^5$，且有 $m\le n$，$s_i\in \{\tt{B,W,\_}\}$。