title: [语言月赛 202401] 跳房子

background: 跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一，趣味性、娱乐性极强，曾深受广大儿童的喜爱。

description:
现在我们给出一种简易跳房子游戏的玩法：

$n$ 个格子从左到右一字形排开，从左到右依次被标号为 $1, 2, \cdots, n$。每一个格子上都有一个正整数，$i$ 号格子上的正整数是 $a _ i$。

这个游戏的规则如下：初始时玩家站在 $1$ 号格子上，需要做若干次跳跃。每一次跳跃时，玩家需要从当前格子向前跳「当前格子上写的整数」数量的格子。形式化地讲，如果玩家当前处于 $x$ 号格子，玩家需要跳到 $x + a _ x$ 号格子上。

  如果玩家跳到 $n$ 号格子右侧的位置，称玩家出界；如果玩家**恰好**跳到 $n$ 号格子上，称玩家胜利。这两种情况下玩家都需要停止跳跃。

现在给定格子数量和格子上的整数，你需要求解：

1. 在停止跳跃后，玩家是否胜利。即，玩家是否能够恰好跳到 $n$ 号格子上。
2. 在停止跳跃后，玩家跳跃的总次数。

inputFormat:
输入共两行。

第一行为一个整数 $n$，代表格子的数量。
第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，代表每个格子上的数字。

outputFormat:
输出共两行。

第一行为一个字符串。如果玩家在停止跳跃后恰好跳到 $n$ 号格子上，输出 `Yes`，否则输出 `No`。
第二行一个整数，代表玩家的总跳跃次数。


title: [CCO2023] Binaria

type: P

description:
你被廉价通信组织（CCO）雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法是这样的。

给定一个长度为 $N$ 的二进制字符串和一个满足 $K \leq N$ 的正整数 $K$，该字符串的 SMS 由 $N-K+1$ 个整数组成。序列中的第一个数是前 $K$ 位的和，第二个数是第 $2$ 位到第 $K+1$ 位的和，依此类推，最后一个数是第 $N-K+1$ 位到第 $N$ 位的和。

例如，如果 $K=4$，那么二进制字符串 $110010$ 的 SMS 是 $2,2,1$。这是因为 $1+1+0+0=2,1+0+0+1=2$，以及 $0+0+1+0=1$。

由于你是一个新手，你的工作不是从给定的 SMS 中找到原始的二进制字符串，而是找到可能形成这个 SMS 的二进制字符串的数量。

inputFormat:
第一行包含两个用空格分隔的整数 $N$ 和 $K$。

第二行包含 $N-K+1$ 个用空格分隔的整数，保证它至少是一个二进制字符串的 SMS。

outputFormat: 输出 $T$ 对 $10^{6}+3$ 取模的结果，其中 $T$ 是等于与给定 SMS 对应的可能的二进制字符串的总数的正整数。


title: [CCO2023] Real Mountains

description:
在你的帮助下，Rebecca 的风景照现在登上了她的杂志的最新一期的封面。然而，似乎有些读者对这张照片还不满意。特别是，他们似乎认为照片中的山是假的！

为了简单起见，我们可以把这张照片描述为一个由 $N$ 列像素组成的序列。在第 $i$ 列，从底部开始的前 $h_{i}$ 个像素是山。她的读者只有在照片中包含一个山峰时，才会相信这是一座真正的山。也就是说，如果存在某个下标 $p$，满足 $1 \leq p \leq N$，使得 $h_{1} \leq h_{2} \leq \cdots \leq h_{p} \geq \cdots \geq h_{N-1} \geq h_{N}$。

幸运的是，Rebecca 还可以付钱给她的编辑修改照片并重新印刷杂志。不过，她的倒霉的是，编辑们对他们的工作有一个非常奇怪的定价方案。Rebecca 唯一能编辑照片的方法是给她的编辑发送包含三个整数 $(i, j, k)$ 的电子邮件，满足 $1 \leq i<j<k \leq N$ 且 $h_{i}>h_{j}<h_{k}$。编辑们会在第 $j$ 列添加一个额外的山的像素（即 $h_{j}$ 增加 $1$），费用是 $h_{i}+h_{j}+h_{k}$。注意 $h_{j}$ 的变化可能会影响未来编辑的费用。

为了取悦她的读者，Rebecca 想要编辑照片，让他们相信这里有一座真正的山。你能告诉她需要花费的最小费用吗？

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

第二行包含 $N$ 个用空格分隔的整数，表示 $h_{1}, h_{2}, \ldots, h_{N}$。

outputFormat: 输出 $T$ 对 $10^{6}+3$ 取模的结果，其中 $T$ 是 Rebecca 为了取悦她的读者而需要花费的最小费用。


title: [语言月赛 202401] 区间函数最大值

type: B

description:
给定 $A, B, C, D, E, F, G, P, X_1, X_2, Y_1, Y_2$，求当 $X _ 1 \leq x \leq X _ 2$，$Y _ 1 \leq y \leq Y _ 2$ 且 $x, y$ 均为整数时

$$
f(x, y) = (A x ^ 3 + B y ^ 3 + C x ^ 2 y + Dxy ^ 2 + Exy + Fx + Gy) \bmod P
$$

的最大值。

$x \bmod K$ 代表 $x$ 除以 $K$ 的余数，例如 $7 \bmod 3 = 1$。

inputFormat: 输入共一行十二个整数 $A, B, C, D, E, F, G, P, X_1, X_2, Y_1, Y_2$。

outputFormat: 输出一个整数，代表 $f(x, y)$ 的最大值。


title: [CCO2023] Line Town

description:
线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为 $h_{1}, h_{2}, \ldots, h_{N}$。

你是线条小镇的镇长，你正在实施你的名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。在一次交换中，你可以让两个相邻的居民交换他们在线中的位置。但是，这次交换会导致两个居民的幸福值取反。

你想要知道是否能进行一些交换，使得居民的幸福值从左到右按非递减的顺序排列。如果可能，需要的最少交换次数是多少。

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

第二行包含 $N$ 个整数 $h_{1}, \ldots, h_{N}$，表示从左到右的居民的幸福值。

outputFormat: 输出一行一个整数，表示最少的交换次数，如果任务不可能完成输出 $-1$。

hint:
**样例解释 1**

可以进行 3 次交换，如下所示：

- 交换第 2 和第 3 个居民，幸福值变成了 $[-2,1,-7,-8,2,8]$。
- 交换第 4 和第 5 个居民，幸福值变成了 $[-2,1,-7,-2,8,8]$。
- 交换第 3 和第 4 个居民，幸福值变成了 $[-2,1,2,7,8,8]$。

居民们现在按照要求的幸福值非递减的顺序排列了。没有比 3 次更少的交换次数可以得到非递减的排列。

**样例解释 2**

没有一系列的交换可以使居民按照幸福值非递减的顺序排列。

对于所有的数据，有 $1\leq N\leq 5\times 10^5，-10^{9} \leq h_{i} \leq 10^{9}$。

- 额外限制 A：对于所有的 $i$，$\left|h_{i}\right| = 1$。
- 额外限制 B：对于所有的 $i$，$\left|h_{i}\right| \leq 1$。
- 额外限制 C：对于所有的 $i \neq j$，$\left|h_{i}\right| \neq\left|h_{j}\right|$。

子任务编号|	分值|	$N$ 的范围	|额外限制|
|:-:|:-:|:-:|:-:|
| 1	|12|	$1 \leq N \leq 2000$ |A|
|2	|12	|$1 \leq N \leq 5\times 10^5$|A|
|3	|12|	$1 \leq N \leq 2000$|B	|
|4	|16	|$1 \leq N \leq 5\times 10^5$|B|
|5	|16	|$1 \leq N \leq 2000$|	C|
|6	|12	|$1 \leq N \leq 5\times 10^5$|C |
|7|8	|$1 \leq N \leq 2000$ |	|
|8|12	|$1 \leq N \leq 5\times 10^5$ |	|


title: [CCO2023] Flip it and Stick it

description:
Finn 正在玩一款叫做「Flip it and Stick it」的游戏，简称为 FiSi。FiSi 是一款单人游戏，玩法是在两个由 0 和 1 组成的字符串 $S$ 和 $T$ 上进行操作。Finn 可以进行以下形式的操作：

选择 $S$ 的一个子串并将其翻转，然后将字符串的各部分按照原来的顺序粘贴在一起，形成新的字符串 $S$。
例如，Finn 可以取字符串 $S=101100$，取从第 2 位开始的子串 $011$（字符串的编号是从 $1$ 开始的），并在一次操作中创建字符串 $S=111000$。

如果 $S$ 不包含 $T$ 作为子串，Finn 就赢得了游戏。你的任务是帮助 Finn 确定赢得游戏所需的最短操作序列的长度，或者告诉他游戏无法获胜。

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

第二行一个字符串 $T$。

outputFormat: 输出一行一个整数，表示如果能赢得游戏所需的最少操作次数，否则输出 $-1$。

hint:
**样例解释 1**

Finn 从字符串 $100110$ 开始。他无法通过一次操作后使得 $10$ 不为子串，但他可以在两次操作后做到。

例如，他的第一次操作可以是翻转从第 4 位到第 6 位的子串（$110$），得到 $100011$。然后，他的第二次操作可以是翻转从第 1 位到第 4 位的子串（$1000$），得到 $000111$，它不包含 $10$ 作为子串。

**样例解释 2**

无论 Finn 进行多少次操作，字符串 $T$ 总会是 $S$ 的子串。

对于所有的数据，有 $1 \leq|S| \leq 2\times 10^5$，$1 \leq|T| \leq 3$。

设 $|T|=l$。

| 子任务编号 |	分值	| $l$ 的限制 |
| :-:|:-:|:-:|
|1|	4|	$l=1$|
|2|	12|	$l=2, T_{1} \neq T_{2}$|
|3|	16|	$l=2$|
|4|	20|	$l=3, T_{1} \neq T_{3}$|
|5|	20|	$l=3,T_{1} \neq T_{2}$|
|6|	28|	$l=3$|


title: [CCO2023] Travelling Trader

description:
一个商人想要在城市之间做生意，把货物从一个城市运到另一个城市来获得利润。有 $N$ 个城市，用 $1, \ldots, N$ 表示。有 $N-1$ 条道路，每条道路连接两个城市，每条道路需要一天的时间来穿越。使用这些道路，可以从任何一个城市到达另一个城市。

如果商人当前在第 $i$ 个城市并选择做生意，那么商人可以获得 $p_{i}$ 的利润，但是对于每个城市这个利润只能获得一次。商人从第 $1$ 个城市开始做生意，沿着道路访问城市，以最大化他们的总利润。但是如果商人太久没有获得利润，商人的老板会变得不高兴。具体地说，一旦商人连续超过 K 天没有获得利润，老板就会解雇商人。注意：无论商人是否在其中一个城市做生意，商人在相邻的城市之间移动都需要一天的时间。你需要求出商人可以获得的最大利润和能够获得这个利润的路线。

求出商人能得到的可能的最大总利润，并构造一种方案。

inputFormat:
第一行包含两个用空格分隔的整数 $N$ 和 $K$。

接下来的 $N-1$ 行，每行包含两个用空格分隔的整数 $u_{i}$ 和 $v_{i}$，表示一条道路。

最后一行包含 $N$ 个整数 $p_{1}, \ldots, p_{N}$，表示选择在相应的城市做生意所给的利润。

outputFormat:
第一行输出一个整数，表示可能的最大总利润。

第二行输出一个整数 $M\ (1 \leq M \leq N)$，表示在最优路线上商人做生意的城市的数量。

第三行，输出 $M$ 个用空格分隔的整数 $x_{1}, \ldots, x_{M}$，表示商人按顺序在最优路线上做生意的城市，从 $x_1=1$ 开始。

如果有多个正确方案，你可以输出任何一个。

hint:
**样例解释 1**

在第 $1$ 天，商人从第 $1$ 个城市开始做生意，获得 $3$ 的利润。

在第 $2$ 天，商人移动到第 $3$ 个城市，并在那里做生意，获得 $4$ 的利润。

在第 $3$ 天，商人无法在被解雇之前到达另一个他们没有做过生意的城市，所以他们的总利润是 $7$。

**样例解释 2**

商人按照 $1,2,4,2,5,2,1,3$ 的顺序访问它们，可以在每个城市获得利润。

注意，商人为了确保他们不会超过 $2$ 天没有获得利润，推迟了在第 $2$ 个城市做生意的时间。

对于所有数据，有 $2 \leq N \leq 2\times 10^5，1\leq K\le 3，1 \leq u_{i}, v_{i} \leq N，u_{i} \neq v_{i}，1 \leq p_{i} \leq 10^{9}$。

|子任务编号	|分值|	$N$ 的范围	|$K$ 的范围|
|:-:|:-:|:-:|:-:|
|1	|8	|$2 \leq N \leq 2\times 10^5$|	$K=1$|
|2	|28	|$2 \leq N \leq 200$|	$K=2$|
|3	|12	|$2 \leq N \leq 2000$|$K=2$|
|4	|16	|$2 \leq N \leq 2\times 10^5$|$K=2$|
|5	|16	|$2 \leq N \leq 2000$|	$K=3$|
|6 | 20 | $2 \leq N \leq 2\times 10^5$|$K=3$|


title: [CCO2023] Triangle Collection

description:
Alice 有一些棍子。一开始，对于每个 $l=1, \ldots, N$，她有 $c_{l}$ 根长度为 $l$ 的棍子。

Alice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $l$ 的棍子和一根长度在 $1$ 和 $2 l-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道用她的棍子最多能做出多少等腰三角形。

有 $Q$ 个事件改变了她拥有的棍子的数量。第 $i$ 个事件包含两个整数 $l_{i}$ 和 $d_{i}$，表示长度为 $l_{i}$ 的棍子的数量变化了 $d_{i}$。注意，$d_{i}$ 可以任意整数，但是 Alice 永远不会有负数或者超过 $10^{9}$ 根长度为 $l$ 的棍子。

你需要求出在每个事件之后，Alice 用她的棍子最多能做出多少等腰三角形。

inputFormat:
第一行包含两个用空格分隔的整数 $N$ 和 $Q$。

第二行包含 $N$ 个用空格分隔的整数 $c_{1}, c_{2}, \ldots, c_{N}$，表示 Alice 的开始时拥有的棍子。

接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $l_{i}$ 和 $d_{i}$，表示一个事件。

保证在每个事件之前和之后，对于每个 $l=1, \ldots, N$，长度为 $l$ 的棍子的数量都在 $0$ 和 $10^{9}$ 之间。

outputFormat: 输出 $Q$ 行，每行包含一个整数，表示每个事件之后的答案。

hint:
在第一个事件之后，Alice 可以用长度为 $ (1,1,1)$ 的棍子做一个三角形。

在第二个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形。

在第三个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形，并用长度为 $(2,2,3)$ 的棍子做一个三角形。

对于所有的数据，有 $1 \leq N, Q \leq 2\times 10^5$，$0 \leq c_{i} \leq 10^{9}$，$1 \leq l_{i} \leq N$，$-10^{9} \leq d_{i} \leq 10^{9}$。

|子任务编号|	分值|	N, Q 的范围|	额外限制|
| :-: | :-: |:-:|:-:|
|1|	20|	$1 \leq N, Q \leq 2000$|	在所有时刻，总共最多有 $2000$ 根棍子。|
|2|	20|	$1 \leq N, Q \leq 2000$|没有额外的限制|
|3|	20|	$1 \leq N, Q \leq 2\times 10^5$|	在所有时刻，每种长度的棍子的数量只会是 $1,2,3$ |
|4|	20|	$1 \leq N, Q \leq 2\times 10^5$| $d_{i}=1,-1$ |
|5|	20| $1 \leq N, Q \leq 2\times 10^5$|没有额外的限制|


title: [语言月赛 202401] 装满葡萄汁的酒杯

description:
小 H 有五个酒杯可供选择，它们的容量分别为 $100\text{mL}$、$150\text{mL}$、$300\text{mL}$、$400\text{mL}$ 和 $1000\text{mL}$。

现在，小 H 想要在这五个酒杯中选择一个来喝葡萄汁。小 H 打算喝 $a\text{ mL}(a \leq 1000)$ 的葡萄汁。请问，小 H 至少需要选择多大容量的酒杯，才能装下 $a\text{ mL}$ 的葡萄汁（葡萄汁不能溢出）。

inputFormat: 输入一行共一个整数 $a$，表示小 H 打算喝的葡萄汁的量（以 $\text{ mL}$ 为单位）。

outputFormat: 输出一行共一个整数，表示小 H 至少需要选择的酒杯容量（以 $\text{ mL}$ 为单位），以确保能够装下 $a\text{ mL}$ 的葡萄汁。

hint:
### 样例解释 #1

如果要装 $50\text{ mL}$ 的葡萄汁，那么用 $100\text{ mL}$ 的酒杯就可以了。

### 数据规模与约定

对于 $100\%$ 的数据，满足 $1 \leq a \leq 1000$。


title: [入门赛 #19] 分饼干 II

description:
老师有 $N$ 块饼干，要分给 $k$ 名小朋友。

每名小朋友至少拿到一块饼干，老师想让每名小朋友拿到的饼干数量都不一样多，请问老师能否实现这个目标。

inputFormat:
**本题单个测试点内有多组测试数据。**

输入共 $T + 1$ 行。

输入第一行为一个整数 $T$，代表测试数据组数。
接下来 $T$ 行，每行两个整数，分别为 $N,k$。

outputFormat:
输出共 $T$ 行，依次对应 $T$ 组测试数据。如果该组测试数据

- 可以实现，输出 `Yes`。
- 无法实现，输出 `No`。


title: [语言月赛 202406] 编程学习

description: 小 B 喜欢学习编程，他已经做了 $x$ 道题目。在接下来的一段时间，小 B 每天可以做 $1$ 道或 $2$ 道编程题。小 B 至少还需要多少天，才能做到 $y$ 道题？

inputFormat: 输入一行两个整数 $x,y$。

outputFormat: 输出一行一个整数，表示最小的天数。

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

- 对于 $20\%$ 的测试数据，$1 \leq x < y \leq 10$；
- 对于 $60\%$ 的测试数据，$1 \leq x < y \leq 10^6$；
- 对于 $100\%$ 的测试数据，$1 \leq x < y \leq 10^{18}$。


title: [语言月赛 202402] 射箭

description:
bj12z_jiasiyuan 看到了三个人 A、B、C 正在射箭。

他们分别射中了 $x$ 环，$y$ 环，$z$ 环。如果一个人射中的环数**大于**另外两个人射中的环数之和，那么发生一次「神秘事件」。

请你告诉 bj12z_jiasiyuan「神秘事件」发生的次数。

inputFormat: 输入共一行三个整数 $x,y,z$，分别代表 A、B、C 射中的环数。

outputFormat: 输出共一行一个整数，代表发生「神秘事件」的次数。

hint:
### 样例解释

- 对于样例 1，因为 $7 > 4 + 2$，所以发生一次「神秘事件」。
- 对于样例 2，没有「神秘事件」发生。

### 数据规模与约定

对于 $100\%$ 的数据，$1 \leq x, y, z \leq 10$。


title: [GDKOI2024 普及组] 刷野 I

description:
Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。

Zayin 率先使用一种攻击方式攻击，攻击过后所有血量小于等于 $0$ 的怪物死亡。在 Zayin 攻击一次后，所有存活的怪物对 Zayin 造成 $1$ 点伤害。以上步骤不断循环，直到 Zayin 击杀所有怪物为止。

Zayin 一共有三种攻击方式：

- 普通攻击: 消耗 $0$ 点能量值，选择一只怪物并使其血量减少一点。

- 天音波: 消耗 $1$ 点能量值，选择一只怪物并使其血量减少两点。

- 天雷破: 消耗 $1$ 点能量值，使所有怪物血量减少一点。

现在 Zayin 一共有 $m$ 点能量，现在他想知道在最优的策略下，击败 $n$ 只怪物所损失的最少血量。

inputFormat:
输入的第一行包含两个正整数 $n, m(1 \leq n, m \leq 10^5)$，$n$ 表示怪物的个数，$m$ 表示 Zayin 拥有的能量值。

输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n(1 \leq a_i \leq 10^9)$，$a_i$ 表示第 $i$ 只怪物的血量。

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

hint:
对于 $30\%$ 的数据，$1 \leq n, m \leq 5$。

对于另外 $15\%$ 的数据，$m = 0$。

对于另外 $15\%$ 的数据，所有 $a_i$ 全部相等。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq a_i \leq 10^9$。


title: [GDKOI2024 普及组] 刷野 II

description:
Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。

Zayin 知道许多被压制的咒语，在这场战斗中，他决定使用一个名为” 闪电连击” 的咒语来一口气击败所有的怪物。让我们看看这个咒语是如何工作的。

- 首先，Zayin 选择一个怪物 $i(1 \leq i \leq n)$ 以及咒语的初始力量 $x$。
- 然后这个咒语会首先击中怪物 $i$，随后对于除第一个目标怪物外，Zayin 可以选择一个没有被该咒语击中过，并且与其中一个已经被击中的怪物相邻的怪物。
- 第一个被击中的目标怪物会受到 $x$ 的伤害，第二个目标怪物会受到 $x-1$ 的伤害，第三个受到 $x-2$ 的伤害，以此类推。不难看出，每个怪物都会被击中恰好一次。

如果一个怪物受到的伤害不低于其生命值，则视为死亡。

Zayin 想展示他作为一个高级巫师的能力，所以他希望在只使用一次咒语就能杀死所有怪物的前提下，使用最少的初始力量 $x$。

现在你需要求出所需的最少的初始力量，并给出一个方案。如果有多个不同的方案，只需要给出任意一个就可以了。

inputFormat:
第一行包含两个整数 $d, n$，表示测试点编号和怪物数。

接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个怪物的血量。

outputFormat:
第一行输出一个整数 $x$，表示最少的初始力量。

接下来第二行输出 $n$ 个用空格分割的下标 $monster_i(1 \leq i \leq n)$，其中 $monster_i$ 表示第 $i$ 个击中的目标怪物。


title: [GDKOI2024 普及组] 刷野 III

description:
Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。

但是由于某种神秘原因，Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 $n$ 的排列 $p$，Zayin 每次攻击第 $i$ 只怪物时，实际上是在攻击第 $p_i$ 只怪物。

Zayin 每次可以选择一个 $[1, n]$ 的整数 $k$，让第 $p_k$ 只怪物的血量减少 $1$ 点，当某只怪物的血量小于等于 $0$ 时这只怪物死亡。

然而 Zayin 并不知道这个排列 $p$ 具体是什么，也无法看到每个怪物剩余的具体血量，仅可以知道每次攻击完后怪物是否死亡。

现在 Zayin 想知道，在他采取最优策略的情况下，最多需要攻击多少次，才可以杀死 $m$ 只怪物。

inputFormat:
输入的第一行包含两个正整数 $n, m(1 \leq m \leq n \leq 2000)$，$n$ 表示怪物的个数，$m$ 表示 Zayin 所需要击杀的怪物个数。

输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n(1 \leq a_i \leq 10^9)$，$a_i$ 表示第 $i$ 只怪物的血量。

outputFormat: 输出一个整数，最少的攻击次数。

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

在第一个样例，Zayin 会一直攻击某一只怪物，直到怪物死亡。

在第二个样例，Zayin 先攻击某一个怪物 $10$ 次，如果没有死亡，则说明攻击的是 $30$ 血的怪物。这时 Zayin 会选择攻击第二只怪物，攻击 $10$ 次后另一只怪物一定死亡，故最差需要 $20$ 次。

**【数据范围】**

对于 $10\%$ 的数据，$1 \leq n, m \leq 5$。

对于另外 $20\%$ 的数据，所有 $a_i$ 全部相等。

对于另外 $30\%$ 的数据，$1 \leq m \leq n \leq 500$。

对于 $100\%$ 的数据，$1 \leq m \leq n \leq 2000$，$1 \leq a_i \leq 10^9$。


title: [GDKOI2024 普及组] 切割

description:
给定一张 $n$ 个点 $m$ 条边的无向连通图，**有**重边无自环。

ymqOAO 现在有 $k$ 个询问。每次询问如果删去图中的 $c_i$ 条边，剩下的图是否还是连通的。

注意：询问之间是相互独立的，即一个询问的删边不会影响之后的询问。

注解：
- 连通图：一个图中任意两个顶点都有路径相连。

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

接下来 $m$ 行，每行包含两个正整数 $x_i, y_i$，表示第 $i$ 条边为 $x_i$ 与 $y_i$ 所连的边。

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

接下来 $k$ 行，第 $i$ 行的第一个整数 $c_i$ 表示所切割的边的条数，接下来 $c_i(1 \leq c_i \leq 4)$ 个整数，表示所切割的边的编号，其中边的编号范围为 $[1, m]$。

outputFormat: 对于每组询问，如果图不连通，则输出 `Bob`，否则输出 `ymqOAO`。（不包括引号）


title: [GDKOI2024 普及组] 捉迷藏

description:
Zayin 和 Ziyin 正在玩有趣的捉迷藏游戏。

该游戏在一颗具有 $n$ 个节点（编号从 $1$ 到 $n$）的树上进行。

在游戏的开始，Zayin 在节点 $a$，而 Ziyin 在节点 $b$。他们轮流操作，Zayin 先移动。在每次移动中，Zayin
能移动到距离当前所在点不超过 $da$ 的节点上，而 Ziyin 能移动到距离当前所在点不超过 $db$ 的节点上（注意
可以保持在当前点不动）。

当某次移动后，其中一人抓住了另外一人，即移动到了另外一人的节点上，则游戏结束，被抓住的人输掉游戏。

当 Zayin 和 Ziyin 都按最优策略移动的话，谁会是最后赢家呢。

注解：
- 一颗具有 $n$ 个节点的树是指一个具有 $n$ 个节点，$n - 1$ 条边的连通无向图。
- 树上两个节点的距离定义为连接该两点的最短路径所包含的边数。

inputFormat:
每个测试点包含多个测试用例。

第一行包含两个整数 $d, t$，表示测试点编号，和测试用例的数量。每个测试用例的描述如下。

第一行包含两个整数 $n, q$ —— 分别为顶点数、询问数。

接下来 $n-1$ 行每行包含两个整数 $u, v (1 \leq u, v \leq n, u \neq v)$，表示顶点 $u$ 和 $v$ 之间具有一条直接相连的边，保证这些边形成一棵树。

接下来 $q$ 行每行包含四个整数 $a, b, da, db(1 \leq a, b, da, db \leq n)$ 作为一次游戏，分别表示 Zayin 初始节点、Ziyin 初始节点、Zayin 最大移动距离、Ziyin 最大移动距离。

outputFormat:
对于每个测试用例的每次游戏，输出一行 `Zayin` 或 `Ziyin` 表示最后赢家，特别地如果在 $10^{10^5}$ 轮内游
戏没有仍结束，则输出 `Draw` 表示平局。

samples:
Ziyin
Zayin
Zayin
Ziyin
Ziyin
Zayin
Zayin
Zayin
Draw
Ziyin


title: [GDKOI2024 普及组] 读书

description:
Zayin 是一个热爱读书的学生。

最近，Zayin 收到了一本有 $n$ 个章节的书，其中每个章节 $i$ 都有一个限制：她必须至少阅读了其他 $a_i$ 个
章节，才能够获取足够的智慧来读懂该章节。

每天，Zayin 都会从头到尾开始阅读这本书。对于她还不能读懂的章节（由于限制）或是已经阅读过的章节，Zayin 会在那天跳过它们。

现在，Zayin 想要知道至少需要多少天才能阅读完所有的 $n$ 个章节。

inputFormat:
第一行包含两个整数 $d, n$，表示测试点编号和章节数。

第二行包含 $n$ 个整数 $a_i (0 \leq a_i < n)$，表示限制。

outputFormat:
输出一行包含一个整数，表示最少需要的天数。

如果 Zayin 无法阅读完所有的 $n$ 个章节，输出 $-1$。

hint:
**本题使用子任务捆绑测试。**

对于所有测试数据，保证 $1 \leq n \leq 5 \times 10^5
, 0 \leq a_i < n$。

- Subtask 1（10%）：$1 ≤ n ≤ 10$，$d = 1$。
- Subtask 2（10%）：$1 ≤ n ≤ 500$，$d = 2$。
- Subtask 3（20%）：$1 ≤ n ≤ 5000$，$3 \leq d \leq 4$。
- Subtask 4（20%）：$1 ≤ n ≤ 10^5$，$5 \leq d \leq 6$。
- Subtask 5（40%）：$1 ≤ n ≤ 5 \times 10^5$，$7 \leq d \leq 10$。


title: [GDKOI2024 普及组] 正方形扩展

description:
现在，在笛卡尔坐标系（无限大二维平面）上有 $n$ 个种类互不相同的细菌，它们所在的坐标也互不相同。

随着时间的增加，细菌们不断繁殖，以正方形的形状、用相同的正方形扩张速度，同时扩张自己的领地。

具体来说对于任意时刻 $t$、平面上任意一点 $p$，假设该点 $p$ 上存在第 $i$ 种细菌，那么有以下两种情况：

- 如果以点 $p$ 为中心的任意正方形都含有其他种类的细菌，则该点的细菌将不会扩张（可以称之为“接触抑制”）。

- 如果存在一个以 $p$ 为中心的正方形不含有其他种类的细菌，则该点的细菌将会进行扩张。

注意，扩展出去的同种细菌也具备一样的扩展能力。

以下是一些简单的关于正方形扩展的例子：

若初始时，平面只有唯一的一个细菌位于 $(0, 0)$，那么过一个单位时间后，这一类细菌将占领 $(1, 1) (1, -1) (-1, -1) (-1, 1)$ 围成的正方形。

若初始时，平面有两个细菌分别位于 $(0, 0)$ 和 $(1, 0)$，那么最终 $(0.5, 0)$ 会成为他们领地的分界线，一开始位于 $(0, 0)$ 的细菌会占领 $(0.5, 0)$ 左侧的全部区域，位于 $(1, 0)$ 的细菌会占领 $(0.5, 0)$ 右侧的全部区域。

现在询问对于第 $i$ 种细菌，询问其占领面积能否趋于无穷大。

inputFormat:
第一行一个正整数 $n(1 \leq n \leq 10^6)$ 表示细菌母体的数量。

接下来输入 $n$ 行，每行输入两个整数，表示点的坐标 $(x_i, y_i)$，即种类为 $i$ 的细菌母体的位置。

outputFormat: 输出一个长度为 $n$ 的 $01$ 串，对于其中第 $i$ 个数字，$1$ 表示种类为 $i$ 的细菌的占领面积可以扩张到无穷大，$0$ 则表示最终面积有限。

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

在第二个样例，点 $(0, 0)$ 最终拥有的领地是直线 $x = -1$ 与 $x = 1$ 夹的中间部分，面积趋于无穷大。

**【数据范围】**

对于 $25\%$ 数据，$n \leq 10^2$。

对于 $50\%$ 数据，$n \leq 10^3$。

对于 $75\%$ 数据，$n \leq 10^5$。

对于 $100\%$ 数据，$1\leq n \leq 10^6$，$-10^9 \leq x_i, y_i \leq 10^9$。


title: [GDKOI2024 普及组] EX 中缀表达式

description:
Alice 最近学习了表达式，现在他想写一个属于自己的表达式计算器。

规定：

- 单个数字：由若干数字（至少一个）连续拼接，最后必须跟一个 `.` 字符（不含引号）。例如：`00123.` `0.` `789.` 都是合法的数字。
- 单个操作符：由若干数字连续拼接，最后跟一个字符。
- 操作符的字符：表示该操作符的操作。该字符必须是 `+`、`*`、`^` 之一，分别表示加法，乘法和乘方。特别约定 `0^0=1`。
例如：`000000789+`，`123^`，如果前面的数值合法，那么它们就都是合法的操作符。
- 操作符的数字：表示该操作符的优先级，优先级的取值是 $[1, n]$ 之间的正整数，数字越大表示优先级越高。
- 对于优先级相同的操作符，题目将给出一个长度为 $n$ 的 $01$ 串 $C$，用于说明对应优先级的操作符之间，是左结合还是右结合。
其中 $0$ 表示左结合，$1$ 表示右结合。
例如 $C=111011$，其中第 $4$ 个字符为 `0`，表示优先级为 $4$ 的操作符是左结合的。
- 左结合：表示该运算符从左往右计算。下面给出左结合的例子：`1.4+2.4^3.4^4.` 等价于 `((1.4+2.)4^3.)4^4.`，其结果与 `((1+2)^3)^4` 相同
- 右结合：表示该运算符从右往左运算。下面给出右结合的例子：`1.6+2.6^3.6^4.` 等价于 `1.6+(2.6^(3.6^4.))`，其结果与 `1+(2^(3^4))` 相同。
- 中缀表达式：
1. 单个数字是合法的中缀表达式。
2. 若 A 是合法的中缀表达式，则 (A) 也是合法的中缀表达式。
3. 若 A、B 均是合法的中缀表达式，c 是合法的单个操作符，则 AcB 也是合法的中缀表达式。
4. 其余情况均不合法。

现在给出一个长度为 $n$ 的 $01$ 串 $C$，用于说明，相同优先级的操作符之间，是左结合还是右结合。

给出一个中缀表达式，判断该表达式是否合法，不合法则输出 `error`（不包括引号），合法则输出该表达式的值对 $998244353$ 取模的结果。

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

第二行一个长度为 $n$ 的 $01$ 串 $C$。

第三行一个字符串 $S$，表示一个中缀表达式。

保证表达式中不会存在空格。

outputFormat: 若中缀表达式不合法则输出 `error`，否则输出该表达式的值对 $998244353$ 取模的结果。

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

`243640717 = ((1+2)^(3*(4^((5*6)+7)))) mod 998244353`

**【数据范围】**

特殊性质 1：不会出现 ^ 字符。

特殊性质 2：不会出现 + 和 * 字符。

特殊性质 3：不会出现 ( 和 )。

对于 $8\%$ 的数据，$n = 1$，$1 \leq |S| \leq 100$，且满足特殊性质 $1$ 和特殊性质 $3$。

对于另外 $8\%$ 的数据，$n = 1$，$1 \leq |S| \leq 100$，且满足特殊性质 $1$。

对于另外 $20\%$ 的数据，$n = 1$，$1 \leq |S| \leq 100$，且满足特殊性质 $2$ 和特殊性质 $3$。

对于另外 $24\%$ 的数据，$n = 1$，$1 \leq |S| \leq 1000$,，且满足特殊性质 $2$。

对于 $100\%$ 的数据，$1 \leq n \leq 9$，$1 \leq |S| \leq 10000$。


title: [GDKOI2024 提高组] 匹配

description:
给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \sim n$，右部点编号为 $n + 1 \sim 2n$。

给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。

如果你对二分图的定义有疑问：

- 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。
- 一个完美匹配是一个大小为 $n$ 的边的集合，使得每个点都恰好与集合里的一条边相连。

inputFormat:
第一行一个正整数 $T$，表示数据组数。每组数据的格式如下：

第一行两个正整数 $n, m$，表示图的点数和边数。接下来 $m$ 行，每行三个整数 $u_i, v_i, c_i(1 \leq u_i \leq n, n+1 \leq v_i \leq 2n, 0 \leq c_i \leq 1)$，表示一条连接 $u_i$, $v_i$ 的边，颜色为 $c_i$。$c_i = 0$ 表示白色，$c_i = 1$ 表示黑色。

outputFormat: 对于每组数据：如果无解，输出一行 $-1$。否则，输出一行 $n$ 个正整数，表示你找到的完美匹配里每条边的编号。边按照输入顺序编号为 $1 \sim m$。

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

在第一组数据中，一个合法的完美匹配是 $(1, 6),(2, 5),(3, 4)$，且里面有恰好两条黑色边。

在第二组数据中，虽然存在完美匹配，但每个完美匹配都有奇数条黑色边。

**【数据范围】**

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

对于所有数据，保证 $1 \leq T \leq 250$，$2 \leq n,\sum n \leq 500$，$1 \leq m \leq n^2$。保证图中不存在重边，即对于 $i \neq j$ 有 $(u_i, v_i)\neq (u_j , v_j)$。

- Subtask 1（20%）：$n ≤ 8$，$T ≤ 10$。
- Subtask 2（20%）：$n ≤ 18$，$T ≤ 10$。
- Subtask 3（20%）：$c_i$ 在 $\{0, 1\}$ 里独立均匀随机。
- Subtask 4（40%）：无特殊限制。


title: [GDKOI2024 提高组] 新本格魔法少女

description:
给定一个长度 $n$ 的整数序列 $a_1,\dots, a_n$；

给定一个由 $m$ 次操作构成的操作序列，操作从 $1$ 开始编号，到 $m$ 结束。操作序列中包含修改操作和求和操作，修改操作给定 $l, r, v$，将 $a_l, a_{l+1}, \dots, a_r$ 修改为 $v$，求和操作给定 $l,r$ ，查询 $\sum \limits_{i=l}^r a_i$。

共 $q$ 次查询，每次查询给出 $L,R$ ，询问将序列 $a$ 初始化为 $0$ 后，依次进行操作序列中的第 $L, L+1, \dots , R$ 次操作，每次求和操作的答案之和。

inputFormat:
第一行三个整数 $n, m, q$；

接下来 $m$ 行，每行 $1, l, r, v$ 或 $2, l, r$ 表示一次操作；

接下来 $q$ 行，每行两个整数 $L, R$ 表示一次查询。

outputFormat: 共 $q$ 行，每行一个整数，依次表示每次查询的答案。

hint:
对所有数据，满足 $1 \leq l \leq r \leq n$，$1 \leq v \leq n$，$1 \leq L \leq R \leq m$，$1 \leq n, m, q \leq 5 \times 10^5$。

对 $10\%$ 的数据，$n, m, q \leq 10^2$。

对另外 $20\%$ 的数据，$n, m, q \leq 5 \times 10^3$。

对另外 $10\%$ 的数据，每次操作都是求和操作。

对另外 $20\%$ 的数据，每次查询满足 $L = 1$。

对另外 $20\%$ 的数据，$n, m, q \leq 2 \times 10^5$。

对于其余数据，无特殊限制。


title: [GDKOI2024 提高组] 鸡

description:
对于一个非负整数序列 $a$，定义它对应的独立集序列 $f(a)$：

- 假设将 $a_i$ 改为 $0$，此时选出若干个两两不相邻的数使得它们的和最大，则 $f(a)_i$ 表示和的最大值。

现在给定 $n, m$，求有多少个长度为 $b$ 的非负整数序列 $b$ 满足以下条件：

- 存在至少一个长度为 $n$，值域为 $[0, m]$ 的非负整数序列 $a$ 使得 $f(a) = b$。

答案对给定的质数 $\textit{MOD}$ 取模。

inputFormat: 共一行，三个数，表示 $n, m, \textit{MOD}$。

outputFormat: 共一行，一个数，表示答案。

hint:
**本题使用子任务捆绑测试。**

对于 $100\%$ 的数据，$1 \leq n, m \leq 3 \times 10^3$，$n \geq 2$，$10^9 < \textit{MOD} < 1.01 \times 10^9$，$\textit{MOD}$ 为质数。

- Subtask 1（10%）：$n, m \leq 5$。
- Subtask 2（15%）：$n \leq 300$，$m = 1$。
- Subtask 3（25%）：$n \leq 300$，$m ≤ 5$。
- Subtask 4（20%）：$n, m \leq 50$。
- Subtask 5（15%）：$n, m \leq 300$。
- Subtask 6（15%）：无特殊限制。


title: [GDKOI2024 提高组] 不休陀螺

description:
有 $n$ 张牌组成一个序列，每张牌用一个二元组 $(a_i
, b_i)$ 表示，意味着打出这张牌需要消耗 $a_i$ 点费用，打出后可以获得 $b_i$ 点费用。

接下来你可以选择一个区间 $[l, r]$ 将这个区间中的卡取出来作为你的卡组。

开始时你的卡组会按照随机顺序排列并且你有 $E$ 点费用，然后你会依次从前往后打出这个排列中的卡。

当你打完这个排列中的卡后你的卡组又会重新随机排列然后你再依次打出，直到你无法再打出下一张牌（当前费用小于下一张牌需要消耗的费用）时停止。

如果一个卡组无论在什么情况下都能够无限打下去，我们则称这卡组可以“陀螺无限”。

现在求有多少个区间组成的卡组能够“陀螺无限”。

inputFormat:
第一行输入两个非负整数 $n, E$ 分别表示卡牌序列长度和初始能量值 $E(1 \leq n \leq 10^6, 0 \leq E \leq 10^9)$。

接下来一行 $n$ 个非负整数 $a_i(0 \leq a_i \leq 10^9)$ 表示每张卡牌打出需要消耗的能量。

接下来一行 $n$ 个非负整数 $b_i(0 \leq b_i \leq 10^9)$ 表示每张卡牌打出后能获得的能量。

outputFormat: 输出一行一个整数表示有多少个区间组成的卡组能够“陀螺无限”。

hint:
**本题使用子任务捆绑测试。**

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$0 \leq E, a_i, b_i \leq 10^9$。

- Subtask 1（20%）：$1 \leq n \leq 5000$。
- Subtask 2（10%）：$b_i \geq a_i$。
- Subtask 3（10%）：$E = 0$。
- Subtask 4（10%）：$0 \leq a_i, b_i \leq 1$。
- Subtask 5（20%）：$a_i \times b_i = 0$。
- Subtask 6（30%）：无特殊限制


title: [GDKOI2024 提高组] 计算

description:
定义 $F(x, a, b) = \gcd(x^a - 1, x^b - 1) + 1, x > 0$。

特别的，如果 $a = 0$ 或 $b = 0$，$F(x, a, b) = 0$。

现在给出五个非负整数 $m, a, b, c, d$。

令 $L = F(m, a, b) + 1$，$R = F(m, c, d)$。

问集合 $\{L, L + 1, L + 2, \dots, R - 2, R - 1, R\}$ 有多少个子集和是 $m$ 的倍数。

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

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

接下来一行 $T$ 行，每行五个非负整数 $m, a, b, c, d$。

outputFormat: 对于每组数据，输出答案。


title: [GDKOI2024 提高组] 染色

description:
Alice 非常喜欢二进制，她认为事物只有和二进制有关才是美的。

一天，她奇思妙想了一种图案，并打算在长宽都为 $2^n$ 的网格上画出她心中所想的图案。
网格的格子只有黑色和白色两种，一开始都是白色。

现在 Alice 规定一种绘画操作为：选定一个格子，使它自己和相邻上下左右的网格颜色反转，即原本黑色会变成白色，白色会变成黑色。

Alice 还规定网格的第一行和最后一行相邻，第一列和最后一列也相邻。

现在 Alice 希望你给出一个操作方案或告诉无解。如果有多个方案，输出任意一个即可。

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

接下来一个 $2^n \times 2^n$ 的矩阵，表示 Alice 所想的图案。其中 $0$ 表示白色，$1$ 表示黑色。

outputFormat:
第一行一个数 $\mathit{ans}$ 表示操作次数，或输出 $-1$ 表示无解。

接下来 $\mathit{ans}$ 行，每行一个坐标表示操作位置。其中每一维坐标范围均为 $[0, 2^n - 1]$。


title: 「Daily OI Round 4」Square

description:
小 A 给了你一个边长为 $n$ 的正方形网格，你需要把 $1 \sim n \times n$ 这些编号填入这个网格里面，满足每一行的编号加起来都是奇数，每一列的编号加起来都是偶数。

在填之前，你想知道是否有任何一种解法满足上述条件，如果可以，输出 `Yes`；否则，输出 `No`。

inputFormat: 一行一个正整数 $n$，表示正方形网格的边长。

outputFormat: 一行一个字符串，`Yes` 或 `No`。


title: [GDKOI2023 提高组] 矩阵

description:
多次给定三个 $n \times n$ 的矩阵 $A, B, C$，你需要判断 $A \times  B$ 在模 $998244353$ 意义下是否等于 $C$。
其中 $×$ 为矩阵乘法，$C_{i,j} = \sum_{k=1}^{n}A_{i,k}B_{k,j}$。

本题读入量较大，建议使用快速读入。

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

接下来包含 $T$ 组数据，每组数据第一行为一个正整数 $n$，表示矩阵大小。

接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $A$。

接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $B$。

接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $C$。

outputFormat: 输出 $T$ 行 Yes 或 No，表示 $A \times  B$ 在模 $998244353$ 意义下是否等于 $C$。

hint:
对于 20% 的数据，满足 $\sum n ≤ 300$。

对于另外 20% 的数据，满足 $A_{i,j} \ne 0$ 的位置不超过 $n$ 个。

对于 100% 的数据，满足 $1 ≤ T, n ≤ 3000,\sum n ≤ 3000, 0 ≤ A_{i,j} , B_{i,j} , C_{i,j} < 998244353$。


title: [GDKOI2023 提高组] 错排

description:
小 X 最近学习了错排问题，于是开始思考一个关于它的变种问题：有多少个长度为 $n$ 的排列 $p$，满足对
于 $i \le m$ 的位置满足 $p_i > m$，且对于所有位置 $i$ 都满足 $p_i \ne i$？

小 X 一共想出了 $T$ 个这样的问题，你能告诉他每个问题的答案吗？

由于答案可能过大，你只需要求出答案对 $998244353$ 取模后的值即可。

inputFormat:
第一行输入一个整数 $T$，表示询问组数。

接下来的 $T$ 行，每行输入两个整数 $ n, m$。

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

hint:
对于 100% 的数据，$0 ≤ T ≤ 2 \times 10^5$，$0 ≤ m ≤ n ≤ 2 \times 10^5$。

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

- Subtask 1 (1pts)：保证 $T = 0$。
- Subtask 2 (9pts)：保证 $T ≤ 10$，$n, m ≤ 8$。
- Subtask 3 (10pts)：保证 $m = 0$。
- Subtask 4 (20pts)：保证 $n, m ≤ 5000$。
- Subtask 5 (20pts)：保证 $T ≤ 10$。
- Subtask 6 (40pts)：无特殊性质。


title: [GDKOI2023 提高组] 异或图

description:
给定一张 $n$ 个点 $m$ 条边的无向图和一个长度为 $n$ 的数组 $a_1, a_2, \cdots , a_n$ 以及一个整数 $C$，你需要求出有多少个长度为 $n$ 的数组 $b$ 满足：

1. $0 ≤ b_i ≤ a_i,\forall 1 ≤ i ≤ n$。
2. 对于每条边 $(u, v)$，$b_u \ne b_v$。
3. $b_1 ⊕ b_2 ⊕ \cdots  ⊕ b_n = C$，其中 $\oplus$ 代表异或。

答案对 $998244353$ 取模。

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

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

接下来的 $m$ 行，每行输入两个正整数 $u, v$，表示一条无向边。


title: [GDKOI2023 提高组] 游戏

description:
你正在树上玩游戏。

给定一棵 $n$ 个结点的树，有 $Q$ 次询问，每次给定 $x, y, z$，你要找到三个点 $(u, v, w)$ 满足 $\operatorname{dis}(u, v) =
x, \operatorname{dis}(u, w) = y, \operatorname{dis}(v, w) = z$。其中 $\operatorname{dis}(u, v)$ 表示树上 $u$ 和 $v$ 两点唯一简单路径所包含的边数，$\operatorname{dis}(u, u) = 0$。
保证有解。

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

接下来 $n - 1$ 行每行两个点 $u, v$ 表示一条 $u$ 到 $v$ 的边。

接下来一个整数 $Q$，表示询问次数。

接下来 $Q$ 行，每行三个整数 $x, y, z$ 表示一组询问。

outputFormat:
输出 $Q$ 行，每行三个整数 $u, v, w$，满足 $\operatorname{dis}(u, v) = x, \operatorname{dis}(u, w) = y, \operatorname{dis}(v, w) = z$。如果多组合法的
$(u, v, w)$，输出任意一组，保证有解。

hint:
对于 10% 的数据，满足 $n, Q ≤ 500$。

对于 20% 的数据，满足 $n, Q ≤ 2 \times 10^3$。

对于另外 20% 的数据，满足 $Q = 1$。

对于另外 20% 的数据，满足 $Q \le 10$。

对于另外 10% 的数据，满足第 $i$ 条边连接 $i$ 和 $i + 1$。

对于另外 10% 的数据，满足 $x = 0$。

对于 100% 的数据，满足 $1 ≤ n, Q ≤ 2 \times 10^5, 0 ≤ x, y, z ≤ 2 \times 10^5$。

下发 checker 和 checker.exe，分别用于 64 位 linux 以及 windows 下的答案校验。

你可以使用 `./checker < 输入文件名 > < 输出文件名 > < 答案文件名 >` 来检测你的输出文件是否合
法。

实际上下发的 checker 并不会用到答案文件，所以你只需要随便选择一个文件作为答案文件即可。

你需要保证输入文件合法，即格式正确并且有解，否则可能会出现未知错误。

根据你的输出文件的问题，checker 分别会返回一下信息：

1. 如果你的输出文件正确，则 checker 会返回 `Accepted!`。
2. 如果在第 $t$ 组数据，答案错误，则 checker 会返回 `Wrong answer on test t!`。
3. 如果你的格式错误，则 checker 会返回 `wrong output format` 后接相关错误信息。


title: [GDKOI2023 提高组] 马戏团里你最忙

description:
你正在马戏团里表演一个节目。

有一个数字，初始是 $x_0$。进行 $K$ 次操作，第 $i$ 次操作从 $[0, 2^n)$ 均匀随机一个数字 $x$，$x_i$ 有 $p$ 的概率是 $x_{i - 1} \operatorname{or} x$，有 $1 - p$ 的概率是 $x_{i - 1} \operatorname{and} x$。

一种方案的权值是 $\sum_{i=1}^k c_{x_{i}}$。对每个 $i \in [0, 2^n)$ 求出，$x_K = i$ 的所有方案中，权值乘概率之和，对 $998244353$ 取模。

inputFormat:
第一行四个整数 $n, p', K, x_0$。$p'$ 为 $p$ 在模 $998244353$ 意义下的值。

第二行 $2^n$ 个整数，第 $i$ 个表示 $c_{i - 1}$。

outputFormat: 输出一行 $2^n$ 个用空格隔开整数，第 $i$ 个表示 $x_K = i - 1$ 的所有方案中，权值乘概率之和，对 $998244353$ 取模。

hint:
对于 20% 的数据，满足 $K ≤ 20$。

对于 40% 的数据，满足 $K ≤ 10^3$。

对于另外 10% 的数据，满足 $n = 1$。

对于另外 10% 的数据，满足 $n ≤ 8$。

对于另外 10% 的数据，满足 $p' = 499122177$。

对于另外 10% 的数据，满足 $c_i = 1$。

对于 100% 的数据，满足 $0 ≤ n ≤ 17$，$ 1 ≤ K ≤ 10^9$，$ 0 ≤ x_0 < 2^n$，$ 0 ≤ p', c_i < 998244353$。


title: [GDKOI2023 提高组] 树

description:
给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。

有 $Q$ 次询问，对于一次询问，给定 $(x, k)$，设 $x$ 号结点的子树内（包含 $x$ 自身）的所有满足距离 $x$ 号结点不超过 $k$ 的结点编号为 $c_1, c_2, . . . , c_k$，则这次询问的答案为：

$$(v_{c_1} ⊕ d(c_1, x)) + (v_{c_2} ⊕ d(c_2, x)) + \cdots + (v_{c_k} ⊕ d(c_k, x))$$

其中 $d(x, y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$⊕$ 表示异或运算。

inputFormat:
第一行一个整数 $n$ 表示树的大小。

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

第三行 $n - 1$ 个整数，依次表示 $2$ 号结点到 $n$ 号结点，每个结点的父亲编号 $p_i$。

第四行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $x, k$，表示一个 $(x, k)$ 的查询。

outputFormat: 输出共 $Q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案。

hint:
对于 10% 的数据，满足 $n, Q ≤ 2 \times 10^3$。

对于 20% 的数据，满足 $n, Q ≤ 10^5$。

对于另外 20% 的数据，满足 $p_i = i - 1$。

对于另外 10% 的数据，满足 $k ≤ 20$。

对于另外 20% 的数据，满足 $k = n$。

对于另外 10% 的数据，满足 $v_i = 0$。

对于 100% 的数据，满足 $1 ≤ n, Q ≤ 10^6$，$ 0 ≤ v ≤ 10^9$，$ 1 ≤ p_i < i$，$ 1 ≤ x, k ≤ n$。


title: 『FLA - I』庭中有奇树

background:
**[English statement.](/problem/U458239) You must submit your code at the Chinese version of the statement.**

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

某天晚上小 G 和小 Y 本打算激情 CF 但过掉两题就下班了，然后他们准备玩一个游戏。

description:
给定一棵有 $n$ 个节点的无根树，边带权，树上有一个起始节点 $S$ 和一个终止节点 $T$。

有一枚可以沿着边在节点之间移动的棋子，它每次移动花费的硬币数量等于经过的边的权值。

如果当前棋子所在节点为 $u$ 且节点 $v$ 与节点 $u$ 之间连有一条权值为 $w$ 的边，小 G 就能花费 $w$ 个硬币把棋子移动到节点 $v$。游戏开始时棋子位于节点 $S$，我们的小 G 要控制棋子移动到节点 $T$。

由于曾经有人告诉小 G 玩某游戏不开挂等于没玩，小 G 决定开挂。他的外挂可以花费 $k$ 个硬币把棋子从当前节点传送到任意一个**没有和当前节点连边**的节点，小 G 只能用这个外挂至多一次。

正义的小 Y 不能坐视不管，在小 G 开始行动之前，小 Y 可以封锁至多 $m$ 条可能的传送路线。假设小 Y 封锁了从节点 $x$ 向节点 $y$ 的传送路线，小 G 把棋子从节点 $x$ 传送到节点 $y$ 花费的硬币数量就会变成 $10^9$。由于外挂功能强大，小 G 知道小 Y 都封锁了哪些路线。**请注意传送路线是单向的，封锁节点 $x$ 向节点 $y$ 的传送路线不影响小 G 从节点 $y$ 向节点 $x$ 传送。**

有趣的是，游戏中小 G 不仅负责控制棋子移动到节点 $T$，还想**最小化**花费的硬币数量；而小 Y 想要**最大化**小  G 花费的硬币数量。

如果两人都采取最优策略，小 G 总共会花掉多少硬币？

inputFormat:
第一行输入五个整数 $n,m,k,S,T$。

接下来 $n-1$ 行，第 $i$ 行输入三个正整数 $u_i,v_i,w_i$ 表示节点 $u_i$ 和节点 $v_i$ 之间有一条边权为 $w_i$ 的边。

outputFormat: 输出一行一个整数，表示在两人都采取最优策略的情况下小 G 花费的硬币数量。


title: 龙逐千灯幻

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

龙年到，帆帆也举起了自己的彩龙灯，他自己也要变成大彩龙啦！

description:
帆帆一共有 $n$ 盏龙灯，第 $i$ 盏的颜色是 $a_i$。

帆帆认为一段区间 $[l,r]$ 的美观度 $f(l,r)$ 为 $a_l\cdots a_r$ 中的不同颜色个数。

帆帆准备带着自己的龙灯去玩，他一共计划去玩 $m$ 天，第 $i$ 天，他会带着自己的 $1\cdots x_i$ 号龙灯，但是他发现如果把很多龙灯装在一起，那么别人只会注意到其中有多少种不同的颜色。

因此帆帆准备把这 $x_i$ 个龙灯按照编号顺序分成恰好 $k_i$ 个区间，满足每盏灯恰好在一个区间内。

那么帆帆这次出行的美观度就为所有区间的美观度的和。

请你帮帮帆帆最大化每一次出行的美观度。

inputFormat:
第一行五个整数 $n,m,id,seed,limx$，分别代表序列长度，询问次数，以及 $\texttt{subtask}$ 编号（样例中的 $id=0$），随机数种子，以及一个和询问有关的参数 $limx$。

因为本题输入量过大，因此采用如下方式生成询问：

我们使用下面的代码生成一个伪随机数列：

```cpp
uint64_t PRG_state;
uint64_t get_number()
{
    PRG_state ^= PRG_state << 13;
    PRG_state ^= PRG_state >> 7;
    PRG_state ^= PRG_state << 17;
    return PRG_state;
}
int readW(int l,int r)
{
	return get_number()%(r-l+1)+l;
}
```

一开始 `PRG_state=seed`，你每次调用 `readW(l,r)` 会返回一个 $[l,r]$ 内的随机数。

第二行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。

设 $x_i,k_i,c_i$ 表示第 $i$ 组询问需要的参数 $x,k,c$，其中 $c$ 的作用见输出格式，那么所有询问的参数可以用以下程序生成：

```cpp
for (int i = 1; i <= m; ++i) {
	x[i] = readW(limx, n);
	k[i] = readW(1, x[i]);
	c[i] = readW(0, 1e7);
}
```

注：**请不要在运行上述代码段获得各组询问的参数之前调用 `readW()` 函数，否则无法获得正确的询问信息。** 本题不需要利用该伪随机数生成器的特殊性质，你只需将  `get_number()` 视为一个每次调用独立且均匀随机地生成一个无符号 $64$ 位整数的生成器即可。本题也不需要优化伪随机数生成器的内部实现。

outputFormat:
为了减少输出量，我们使用如下方式进行信息压缩：

如果第 $i$ 组询问的答案为 $ans_i$，其生成参数为 $c_i$，那么你需要输出：

$$\bigoplus\limits_{i=1}^m(ans_i\times c_i)$$

其中 $\bigoplus $ 为异或运算，该值显然一定位于 `long long` 能表示的整数范围内。

tags: 凸完全单调性, wqs 二分


title: 一径入繁华

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

伴随龙年到来的，还有帆巨很喜欢的九省联考。为了爆踩压轴题。帆巨狠狠地重温了数论。

数论所生，繁华之地！

description:
帆巨觉得求 $x^a$ 在 $\bmod\ p$ 意义下的值太简单了，所以他想求 $\sigma_0^s(x^t)$ 在 $\bmod\ p$ 意义下的值。

帆帆不满足于只计算一次，于是他列了一个 $n\times n$ 的数表 $A$，保证第 $i$ 行第 $j$ 列（$1\le i,j\le n$）中的元素 $a_{i,j}$ 满足：

$$
a_{i,j}=\sum_{d\mid \gcd(i,j)}\mu\left(\dfrac{\gcd(i,j)}{d}\right)\times (\sigma_0(d^s))^t
$$

帆帆想知道这个数表长什么样子，但这个数表实在太大了，所以请你告诉他 $\det A$ 对 $10^9+7$ 取模后的结果。

注释：

1. 表达式中的各种函数含义在 **[这里](https://oi-wiki.org/math/number-theory/basic/#%E4%BE%8B%E5%AD%90)（$\mu$ 表示莫比乌斯函数，$\sigma_0$ 表示约数个数函数）**。
2. $\det A$ 表示方阵 $A$ 的 **[行列式](https://baike.baidu.com/item/%E8%A1%8C%E5%88%97%E5%BC%8F/2010180)**。

inputFormat: 一行，输入三个整数 $n,s,t$。

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


title: 「CZOI-R1」进制

description:
你有一个数 $x$，你需要对它进行 $n$ 次操作。

每次操作，你可以选择 $y$ 进制下的数 $x$ 的某一个有效位上数值增加 $1$。
第一个非零数位及其后面的数位是有效位。

注意：
* **对于每次操作**，你可以任意取 $y\in[2,+\infty)$；
* 你需保证增加操作不会使 $y$ 进制下的数 $x$ 产生进位。

现在你需要求 $n$ 次操作后这个数最大是多少。

答案以十进制输出，并对 $10^9+7$ 取模。你需要输出的是这个数的最大值对 $10^9+7$ 取模的结果，而并非对 $10^9+7$ 取模后的最大值。

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

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

接下来 $T$ 行，每行两个整数 $x,n$，分别表示初始数字、操作次数。

outputFormat: 对于每组测试数据，输出一行一个整数，表示 $x$ 进行 $n$ 次操作后的最大值。

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

很明显，$2$ 在二进制时为 $10$，在三或更高进制时为 $2$。

二进制时，在第一位 $+1$ 会导致二进制产生进位，只能在第二位 $+1$，此时得到的结果为 $11$，转换为十进制为 $3$。

在三或更高进制时，只能往末位 $+1$，三进制下会产生进位，舍去。四或更高进制时得到结果均为 $3$，转化为十进制的结果也是 $3$。

**【数据范围】**

**本题采用捆绑测试。**
- Subtask #1（$20\text{ pts}$）：$x\le 2$。
- Subtask #2（$20\text{ pts}$）：$n=1$。
- Subtask #3（$60\text{ pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1\le x,n\le10^9$，$1\le T\le10^6$。


title: [语言月赛 202402] 翻转和反转

background: bj12z_jiasiyuan 喜欢翻转与反转。

description:
bj12z_jiasiyuan 有一个长度为 $n$ 的 $01$ 串 $s$，第 $i$ 位表示为 $s_i$。他要操作 $q$ 次，每次操作的内容如下：

- $\textbf{1}$，将 $01$ 串 $s$ **翻转**，即将字符串中的字符顺序颠倒过来。例如 $s$ 串原来是 `10010`，翻转（颠倒）后变为 `01001`。

- $\textbf{2}$，将 $01$ 串 $s$ **反转**，即逐位取反。对于每个 $i$（$1\leq i\leq n$），如果 $s_i = 0$，则令 $s_i$ 变成 $1$；否则令 $s_i$ 变成 $0$。

请你告诉 bj12z_jiasiyuan 操作 $q$ 次后的 $01$ 串 $s$。

inputFormat:
输入共三行。

第一行两个整数 $n,q$。
第二行一个长度为 $n$ 的 $01$ 串 $s$。
第三行一个长度为 $q$ 的字符串 $w$，其中 $w_i$ 表示第 $i$ 次操作的内容。如果 $w_i=1$，表示进行翻转操作；如果 $w_i=2$，表示进行反转操作。

outputFormat: 输出操作 $q$ 次后的 $01$ 串 $s$。


title: 『STA - R5』消失的计算机

description:
**本题为提交答案题。**

后台有一个正整数 $n$（你不知道 $n$ 具体的值）。

你有 $10^3$ 个变量 $p_1,p_2,\cdots,p_{10^3}$，初始 $p_1=n$，$p_2=p_3=\cdots=p_{10^3}=0$。

你需要写一个程序完成一些任务，程序包含下面几种语句可供使用：
- `new x`，令 $n\gets n+1$，$p_x\gets n$。
- `dec x`，令 $p_x\gets p_x-1$。
- `assign x y`，令 $p_x\gets p_y$。
- `iftry x goto l`，如果 $p_x \ge 0$，跳转到第 $l$ 条语句。
- `ifeq x y goto l`，如果 $p_x = p_y$，跳转到第 $l$ 条语句。
- `ifneq x y goto l`，如果 $p_x\neq p_y$，跳转到第 $l$ 条语句。

对于后三种语句，**如果当前语句是第 $\bm{l_0}$ 条，那么要求 $\bm{l<l_0}$。**

你不得使用超过 $1000$ 条语句或是标号超过 $1000$ 的变量。你的程序实际语句运行次数不得超过 $10^5$。

令程序执行前的 $n$ 值为程序的输入，程序执行后的 $n$ 值为程序的输出，你需要分别完成下面 $10$ 个任务：

1. 输入 $n$，输出 $2n$。
1. 输入 $n$，输出 $\binom n2$。
1. 输入 $n$，输出 $600$。
1. 输入 $n$，输出 $n + 1$。
1. 输入 $n$，输出 $n^2 - 1$。
1. 输入 $n$，输出 $n + 2000$。
1. 输入 $n$，输出 $n + \lfloor \log_2 n\rfloor$。
1. 输入 $n$，输出 $n + \left(n \bmod 2\right) + 1$。
1. 输入 $n$，输出 $n+\gcd(n, n - 4) + 1$。
1. 输入 $n$，输出一个满足 $|x-n\ln n|\le 30$ 的正整数 $x$。

**注：子任务按长度排序，与难度无关。**

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

outputFormat:
针对给定的 $10$ 个任务，你需要分别提交你的输出文件 ``1.out`` ~ ``10.out``。

每个文件需要输出若干行。

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

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


title: [yLCPC2024] A. dx 分计算

background:
你说的对，但舞萌 DX 是一款由 SEGA 开发，华立科技代理，形似洗衣机的街机音乐游戏。

只要看准时机拍到所有的音符就好啦！

description:
在舞萌 DX 中，每个音符根据完成击打的时刻，会得到如下五种判定：

- `Critical Perfect`：简记为 `P`，可得 $3$ 分 dx 分。
- `Perfect`：简记为 `p`，可得 $2$ 分 dx 分。
- `Great`：简记为 `G`，可得 $1$ 分 dx 分。
- `Good`：简记为 `g`，不能得到 dx 分。
- `Miss`：简记为 `m`，不能得到 dx 分。

扶苏游玩了一局舞萌 DX，她将她各个音符的判定情况按顺序使用上面的简记规则记为了一个字符串 $s$。规定这个字符串最左边的字符表示第一个音符的判定结果，最右边的字符表示第 $|s|$ 个音符的判定结果，这里 $|s|$ 表示字符串 $|s|$ 的长度，也即整首歌的音符数。

现在，扶苏有 $q$ 次询问，每次询问会给出两个整数 $l, r$，对每个询问你需要回答：这首歌的第 $l$ 个音符到第 $r$ 个音符（包含第 $l$ 个和第 $r$ 个）的判定结果共能得到多少 dx 分数？

乐曲一段区间内的音符得到的 dx 分数是这些音符分别能得到的 dx 分数之和。

inputFormat:
**本题单个测试点内有多组测试数据**，输入的第一行是一个正整数，表示数据组数 $T$。对每组测试数据：

第一行是一个字符串 $s$（$1 \leq |s| \leq 10^7$），表示一首歌各个音符的判定结果。保证 $s$ 中只含字符 `P`，`p`，`G`，`g`，`m`。
第二行有一个整数 $q$（$1 \leq q \leq 10^4$），表示询问的数量。
接下来 $q$ 行，每行两个整数 $l, r$（$1 \leq l \leq r \leq |s|$），表示一组询问。

数据保证单个测试点内 $s$ 的长度之和不超过 $10^7$，$q$ 之和不超过 $10^4$。

outputFormat: 对每组测试数据，按询问的顺序依次给出每个询问的答案。每个询问输出一行一个整数表示答案。


title: [yLCPC2024] B. 找机厅

background:
扶苏正在出发去打 mai！

但是商场内部实在太复杂了，她在里面迷路了。已经在地铁站迷路过一次的扶苏看着商场的地图实在是不懂怎么走，你能帮帮她吗？

description:
给定一个 $n$ 行 $m$ 列的 $01$ 矩阵，记矩阵第 $i$ 行第 $j$ 列的格子是 $(i, j)$（$1 \leq i \leq n$，$1 \leq j \leq m$）。

你要从矩阵的左上角出发到达右下角。行走规则如下：

- 如果你在格子 $(i, j)$，你下一步只能走到：$(i - 1, j)$、$(i + 1, j)$、$(i, j - 1)$、$(i, j + 1)$ 四个格子的其中之一。
- 任意时刻你不能走出这个矩阵，即你的位置 $(i, j)$ 必须时刻满足 $1 \leq i \leq n$，$1 \leq j \leq m$。
- 如果你想从一个格子走到另一个格子，除了满足上述的要求外，还必须保证：这两个格子对应的数字不同。即：写着 $0$ 的格子只能走到写着 $1$ 的格子，反之亦然。

你每走一步就需要花费一个单位的时间。你需要用最短的时间从 $(1, 1)$ 到达 $(n, m)$。除了给出最短时间外，你还必须给出一种可行的最短用时的行走方法。

inputFormat:
**本题单个测试点内有多组测试数据**。第一行是一个正整数 $T$，表示数据组数。对每组数据：

第一行是两个整数 $n, m$（$1 \leq n, m \leq 2 \times 10^3$），表示矩阵的行数和列数。
接下来 $n$ 行，每行一个长度为 $m$ 的仅含字符 `0` `1` 的字符串，表示这个矩阵。

数据保证每组数据内的 $n$ 之和、$m$ 之和均不超过 $2 \times 10^3$。

outputFormat:
对每组数据，输出一行或两行：

如果从 $(1, 1)$ 无法到达 $(n, m)$，输出一行一个 $-1$ 表示无解。

否则按如下规则输出：

- 第一行输出一个整数 $t$，表示从左上角走到右下角的最短用时。
- 第二行输出一个长度为 $t$ 的仅含字符 `L` `R` `U` `D` 的字符串 $s$，表示你给出的行走方法：
  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i - 1, j)$，则 $s_i = \texttt{U}$。
  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i + 1, j)$，则 $s_i = \texttt{D}$。
  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i, j-1)$，则 $s_i = \texttt{L}$。
  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i, j + 1)$，则 $s_i = \texttt{R}$。

你第二行输出的字符串长度必须恰好为第一行给出的最短用时 $t$。如果有多种方案符合要求，你可以输出任意一种。


title: [USACO18OPEN] Team Tic Tac Toe B

description:
Farmer John 有 $26$ 头奶牛，恰好她们名字都以不同的字母开头，所以 Farmer John 用每头奶牛的名字的首字母来指代她——一个 `A-Z` 之间的字母。

这些奶牛最近沉迷于井字游戏，但是由于她们并不满足只有两头奶牛可以一起玩，她们改编了这个游戏，可以让许多奶牛可以一块儿玩！就像常规的井字游戏一样，这个游戏是在一块 $3×3$
的棋盘上进行的，只是与仅用 `X` 和 `O` 不同，每个格子用一个 `A-Z` 之间的字母标记，表示占有这个格子的奶牛名字的首字母。

以下是一个棋盘的例子：

```plain
COW
XXO
ABC
```

这些奶牛会在她们迷惑于如何判断胜负之前就占满这九个格子。显然，就像常规的井字游戏一样，如果任何一头奶牛占有了一整行、一整列，或是一整条对角线，那么这头奶牛就获胜了。然而，由于奶牛认为多牛游戏中这并不容易出现，所以她们决定允许奶牛组成两牛一队，如果某一行、一列，或是一条对角线仅包含一队的两头奶牛的字母，并且同时包含了这两头奶牛（不仅仅是一头）的字母，那么这一队就获胜。

请帮助奶牛们判断有多少头奶牛或是两头奶牛组成的队伍可以获胜。注意棋盘上的同一个格子可能在不同奶牛或队伍的获胜中均被用到。

inputFormat: 输入包含三行，每行三个 `A-Z` 之间的字符。

outputFormat: 输出包含两行。第一行，输出能够获胜的单独的奶牛的数量。第二行，输出能够获胜的两头奶牛组成的队伍的数量。

hint: 在这个例子中，没有单独的奶牛可以获得胜利。但是，如果奶牛 `C` 和奶牛 `X` 组队，她们可以通过 `C-X-C` 对角线获胜。同样地，如果奶牛 `X` 和 `O` 组队，她们可以通过中间一行取胜。


title: [USACO18OPEN] Milking Order B

description:
Farmer John 的 $N$ 头奶牛（$2\le N\le 100$），方便起见仍然编号为 $1\ldots N$，正好闲得发慌。因此，她们发展了一个与 Farmer John 每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会结构。经过若干周的研究，Farmer John 发现这个结构基于两个关键特性。

首先，由于奶牛们的社会阶层，某些奶牛会坚持要在其他奶牛之前挤奶，基于她们的社会地位等级。比方说，如果奶牛 $3$ 有最高的地位，奶牛 $2$ 位于中等地位，奶牛 $5$ 是低地位，那么奶牛 $3$ 会最早挤奶，然后是奶牛 $2$，最后是奶牛 $5$。

然后，有些奶牛只允许她们在排队顺序中一个特定的位置挤奶。比方说，奶牛 $4$ 可能坚持要在所有奶牛中的第二位挤奶。

幸运的是，Farmer John 总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。

不幸的是，奶牛 $1$ 最近生病了，所以 Farmer John 想要尽早给这头奶牛挤奶，使得她可以回到牛棚获得急需的休息。请帮助 Farmer John 求出奶牛 $1$ 可以在挤奶顺序中出现的最早位置。

inputFormat:
第一行包含 $N$，$M$（$1\le M<N$），和 $K$（$1\le K<N$），表示 Farmer John 有 $N$ 头奶牛，其中 $M$ 头形成了社会阶层，$K$ 头需要在挤奶顺序中处于一个特定的位置。下一行包含 $M$ 个不同的整数 $m_i$（$1\le m_i\le N$）。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。下面 $K$ 行，每行包含两个整数 $c_i$（$1\le c_i\le N$）和 $p_i$（$1\le p_i\le N$），表示奶牛 $c_i$ 一定要在第 $p_i$ 位进行挤奶。

输入数据保证在这些限制之下，Farmer John 能够建立一个符合要求的挤奶顺序。

outputFormat: 输出奶牛 $1$ 可以在挤奶顺序中出现的最早位置。

hint:
在这个例子中，Farmer John 有六头奶牛，其中奶牛 $1$ 生病了。他的挤奶顺序应该为奶牛 $4$ 在奶牛 $5$ 之前，奶牛 $5$ 在奶牛 $6$ 之前。此外，Farmer John 必须要第一个给奶牛 $3$ 挤奶，第三个给奶牛 $5$ 挤奶。

FJ 必须第一个给奶牛 $3$ 挤奶，由于奶牛 $4$ 必须要在奶牛 $5$ 之前，奶牛 $4$ 一定是第二个挤奶的，然后奶牛 $5$ 第三个。于是，奶牛 $1$ 最早在挤奶顺序中出现的位置是第四个。


title: 高洁（Purity）

background:
简洁、准确而永恒的美丽 —— 高洁。
****
「高洁之光」拉姆，身为精灵王的他可以完美使用《阿梅斯草纸书》的力量。

description:
拉姆使用「暴风箭雨」一次射出了 $n$ 支箭，其中第 $i$ 支箭的原始攻击力是 $i$。不过，这些箭会经过一些强化。

对于常数 $d$，设原始攻击力为 $i$ 的箭，其**能级**为 $v(i)$：

- 若不存在正整数 $k$ 使得 $i^k$ 是 $d$ 的整数倍，则 $v(i)=0$；
- 否则 $v(i)$ 为**最小的**、使得 $i^k$ 是 $d$ 的整数倍的正整数 $k$。

那么这支箭强化后的攻击力为 $i^{v(i)+1}$。

拉姆想知道所有箭在**强化后**的攻击力之和，由于答案可能很大，你只需要求出答案对 $998244353$ 取模的结果。（即求出答案除以 $998244353$ 的余数）

inputFormat:
第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行两个正整数 $n,d$，意义如题目描述。

outputFormat: 输出 $T$ 行，每行对应一组数据的答案。

hint:
【样例解释】
对于第一组数据，$d=12$。其中 $v(6)=2$，因为 $12$ 能整除 $6^2$，而不整除 $6^1$，同样也能得到 $v(12)=1$。
可以发现 $n=15$ 以内的其它数能级都为 $0$，故答案为：

$$\left(\sum_{i=1}^{15}i\right)-6-12+6^3+12^2=462$$

对于第二组数据，可以证明 $n$ 以内只有 $v(210)=3$ 非零，由此可以算出答案为 $1944889990$，对 $998244353$ 取模后为 $946645637$。

【数据范围】
**本题采用捆绑测试。**

Subtask 1（15 pts）：$1 \le n,d \le 10^4$；
Subtask 2（15 pts）：$d$ 为质数；
Subtask 3（20 pts）：$d$ 为质数的正整数幂；
Subtask 4（20 pts）：不存在大于 $1$ 的整数 $x$，使得 $x^4$ 整除 $d$；
Subtask 5（30 pts）：无特殊限制。

对于全部数据，$1\le T \le 1000$，$1\le n < 2^{63}$，$1\le d \le 10^8$。

【提示】
此题的时间限制较为宽松，即使你的代码在某些细节上没有优化，也可以正常通过此题。


title: 「XSOI-R1」跳跃游戏

background: 本来可怜的 $\texttt{MhxMa}$ 想出这道题，但是已经被 $\texttt{Ferm\_Tawn}$ 抢了，此时 $\texttt{MhxMa}$ 坐在电脑面前，看着马上要造好的数据，想象着自己的题难倒一大片选手的梦想破灭了。

description:
这是一个跳跃游戏。在游戏中你可以跳到任意位置，其中有 $n$ 个点：$1 , 2 , 3, \cdots , n$，跳到那里会有奖励分数 $a_1 , a_2 , \cdots , a_n$。

显然，这个游戏很简单，$\texttt{MhxMa}$ 没过多久就获得了所有分数，于是改进了代码，添加了经验值这个参数。

对于有奖励分数的 $n$ 个点，若从点 $x$ 跳到点 $y$，会获得经验值 $\operatorname{score}_{x , y}(1\le x\le y\le n)$：

$$\operatorname{score}_{x,y}=\begin{cases}\operatorname{len}  & \operatorname{gcd}(a_x , a_{x+1} , \dots , a_y)=2 , \operatorname{len \ mod} 2 = 0  \\ \operatorname{len} &\gcd(a_x , a_{x + 1} , \dots , a_y)=3 , \operatorname{len \ mod} 2 = 1\\ 0 & \operatorname{others} \end{cases}$$

其中，$\operatorname {len}$ 表示区间的长度，即 $y-x+1$。

**对于每一对位置 $(x,y)$，多次跳跃只会获得一次经验值。**

为了向 $\texttt{MhxMa}$ 展现你的编程实力，你决定写一个代码算出这个游戏能刷到的最大经验值。

inputFormat:
输入共两行。

输入第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_i$。

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

hint:
### 样例解释 #1

$\operatorname{score_{2 , 2}}= 1$。

$\operatorname{score_{2 , 4}}= 3$。

$\operatorname{score_{3 , 5}}= 3$。

$\operatorname{score_{4 , 4}}= 1$。

$1+3+3+1=8$。

### 样例解释 #2

$\operatorname{score_{1 , 2}}= 2$。

$\operatorname{score_{1 , 4}}= 4$。

$\operatorname{score_{2 , 3}}= 2$。

$\operatorname{score_{2 , 5}}= 4$。

$\operatorname{score_{3 , 4}}= 2$。

$\operatorname{score_{4 , 5}}= 2$。

$2+ 4 + 2 + 4 + 2 + 2 = 16$。

------------
### 数据规模与约定

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

- Subtask 0（20 pts）：$n \le 10^2$。

- Subtask 1（10 pts）：$n \le 2 \times 10^3$。

- Subtask 2（20 pts）：$n \le 10^4$。

- Subtask 3（50 pts）：$n \le 6 \times 10^5 $。

对于所有测试数据，$1 \le n \le 6 \times 10^5$，$1 \le a_i \le 10^7$。


title: [语言月赛 202402] 陨石

background: 卷王来到了他的好朋友 bj12z_jiasiyuan 的农场，打算在那里过上一晚。但是在看新闻时，他们获得了一个不幸的消息，一场陨石雨就快要降临了……

description:
bj12z_jiasiyuan 的农场里有 $n$ 间牛棚，编号为 $1$ 到 $n$。第 $i$ 间牛棚的防御值为 $a_i$。

陨石雨将会**在 $t$ 秒后**来临。在陨石雨来临的时候，会有 $m$ 块陨石撞击牛棚，第 $i$ 块陨石会撞击到第 $x_i$ 间牛棚。当一块陨石撞击一间牛棚时，牛棚的防御值**会减去 $2$ 点**。而当一间牛棚的防御值 $\leq 0$ 时，牛棚会被破坏。

bj12z_jiasiyuan 有很多补给，每个补给可以给一间牛棚**增加 $1$ 点防御值**。幸运的是，卷王可以从一间牛棚瞬移到另一间牛棚（瞬移**不需花费任何时间**），用补给给牛棚增加防御值。每次补给需要 $1$ 秒的时间。

卷王只有 $t$ 秒种的时间可以出去补给，他希望让被破坏的牛棚越少越好。请你输出**最优策略下**被保护的牛棚的数量。

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

第一行一个整数 $T$，代表测试数据组数。接下来 $T$ 组数据，每组数据共三行。

第一行三个整数 $n,t,m$，分别表示牛棚的数量，卷王补给的时间和陨石的数量。
接下来一行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示第 $i$ 间牛棚的防御值。
最后一行 $m$ 个整数 $x_1, x_2, \cdots, x_m$，表示第 $i$ 块陨石将会撞击第 $x_i$ 间牛棚。

outputFormat: 输出 $T$ 行，每行一个整数，分别表示每组测试数据中最优策略下被保护的牛棚的数量。

hint:
### 样例 1 解释

一种最优的补给方法是补给 $1$ 号牛棚 $1$ 点防御值，补给 $2$ 号牛棚 $2$ 点防御值。

在这种情况下，各牛棚防御值变化如下，其中蓝色数字代表初始防御值，绿色数字代表补给，红色数字代表陨石撞击：

- $1$ 号：${\color{blue} 2} + {\color{green}1} - {\color{red}2} = 1$；
- $2$ 号：${\color{blue} 1} + {\color{green}2} - {\color{red}2} = 1$；
- $3$ 号：${\color{blue} 3} - {\color{red}2} - {\color{red}2} = -1$；
- $4$ 号：${\color{blue} 5} - {\color{red}2} = 3$。

有且仅有 $3$ 号牛棚被破坏，可保护三个牛棚。

### 数据规模与约定

对于 $100\%$ 的数据，$1\leq x_i \leq n\leq 5 \times10^3$，$1\leq m\leq 10^6$，$0\leq t\leq 10^6$，$1\leq a_i \leq 10^6$，$1 \leq T \leq 5 \times 10^3$。
保证单个测试点内所有测试数据 $n$ 的总和不超过 $5 \times 10^4$，所有测试数据 $m$ 的总和不超过 $3 \times 10^6$。

| 测试点编号 | 特殊限制 |
| :----------: | :----------: |
| $1, 2$ | $T = 1$，$n = 1$ |
| $3, 4$ | $T = 1$，每间牛棚恰好被击中一次 |
| $5$ | $T = 1$，$1\leq x_i \leq n \leq 100$ |
| $6$ | $T = 1$ |
| $7$ | $1\leq x_i \leq n \leq 100$ |
| $8 \sim 10$ | 无特殊限制 |


title: [语言月赛 202402] 分配工资

description:
经过小 A 和卷王的一番忙活，公开赛通过了审核。比赛顺利的结束后，她们领到了一笔 $m$ 元的工资。现在她们遇到了一个棘手的问题：工资怎么分呢？

公开赛有 $n$ 道题，第 $i$ 道题的出题人是 $a_i$。$a_i$ 为 $1$ 表示卷王，为 $2$ 表示小 A。

在谷洛的工资分发规则里，一道题的出题人会获得**这道题的所有工资**。每道题有一个工资权重 $b_i$，也就是说，各个题能获得的工资比例是 $b_1:b_2:b_3\dots :b_{n-1}:b_n$。

现在，卷王想知道，按照如上的方法计算自己获得的工资，她会分到多少工资？

**提示：建议结合样例解释理解题意。**

inputFormat:
第一行两个整数 $n,m$，表示比赛的题量以及小 A 和卷王获得的工资。

接下来 $n$ 行，每行两个整数 $a_i,b_i$，分别表示第 $i$ 道题的出题人和工资权重。

outputFormat: 一行一个小数，表示卷王获得的工资，保留小数点后 $3$ 位。


title: 理性（Rationality）

background:
数学之善，统治宇宙的根本原理 —— 理性。
****
「理性之光」伊奥，是古代精灵图形术士。已经千岁的她总能不受感情的干扰，以理性做出最优的决策。

description:
赛时更新：请注意，对于一组确定的 $v_1,\cdots,v_n$，都可以求出 $\text{RSS}$ 的最小值。**它是关于随机变量  $v_1,\cdots,v_n$ 的一个随机变量**，将其记为 $X$，则要求的是 $\mathbb E[X]$。
笔误改正：残差平方和的英文为 $\text{RSS}$。
****
伊奥的思绪回到了千年前的一场大战中。

她记得那场战斗中有 $n$ 个敌人，第 $i$ 个敌人在距离她 $d_i$（$d_i$ 之间互不相同）的位置上。这些敌人都带有一个**正整数**标记 $v_i$，只要以**恰好** $v_i$ 的攻击力击中它就可以将其消灭。

她只要设定一个一次函数 $f(x)=ax+b$，就能在距离她 $d_i$ 的位置放出 $f(d_i)$ 的攻击力。好在她的队友会辅助她攻击，她只用考虑确定 $a,b$ 使得 $f(x)$ 的效果最优，即最小化 $\text{RSS}$（残差平方和）：
$$\text{RSS}=\sum_{i=1}^n(f(d_i)-v_i)^2$$
当然了，这只是她的回忆。她能清晰记得每个敌人到她的距离 $d_i$，而对于 $v_i$ 她只记得满足 $l_i\leq v_i \leq r_i$。

她想知道假设每个 $v_i$ 都对应在 $[l_i,r_i]$ 范围内**均匀随机**的情况下，「$\text{RSS}$ **的最小值」的期望**。
可以证明答案总是有理数，你只需要告诉她答案对 $998244353$ 取模的结果即可。

inputFormat:
第一行一个正整数 $n$，表示敌人的个数。
接下来 $n$ 行，每行三个正整数 $d_i,l_i,r_i$，分别表示第 $i$ 个敌人到伊奥的距离，其标记 $v_i$ 的下界和上界。

为了方便你的计算，伊奥保证 $d_i< d_{i+1}$（$1\leq i <n$），并且：

$$n\sum_{i=1}^nd_i^2 \not \equiv \left(\sum_{i=1}^nd_i \right)^2 \pmod{998244353}$$
**即确保答案在模 $998244353$ 意义下一定存在。**

outputFormat: 输出一行一个整数，表示所有情况下 $\text{RSS}$ 最小值的期望。

hint:
【样例 $1$ 解释】

此样例中有 $l_i=r_i$，即情况已经确定，只需要求出此时最优的 $a,b$ 即可。容易发现 $(1,4),(3,7),(5,10)$ 这三组数据可以用一次函数完美拟合：即 $f(x)=\dfrac 32 x+\dfrac{5}{2}$，与每个点偏差都是 $0$，故 $\text{RSS}$ 最小值的期望，也就是答案为 $0$。

【样例 $2$ 解释】

这里同样有 $l_i=r_i$。$5$ 个敌人的数据 $(d_i,v_i)$ 分别为 $(1,4),(2,5),(3,7),(4,8),(9,8)$，可以证明取
$$a=\frac{87}{194} \ , \ b=\frac{911}{194}$$
是一组使得 $\text{RSS}$ 最小的解，代入计算得
$$\text{RSS}=\sum_{i=1}^n\left( \frac{87}{194}d_i+\frac{911}{194}-v_i\right)^2=\frac{1047}{194}$$
在模 $998244353$ 意义下答案为 $488831003$。

【数据范围】

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

Subtask 1（10 pts）：$n \leq 3$；
Subtask 2（10 pts）：$l_i=r_i$；
Subtask 3（15 pts）：$n\le500$，$r_i\leq 500$；
Subtask 4（15 pts）：$n\le 5000$；
Subtask 5（20 pts）：$n\le 10^5$；
Subtask 6（30 pts）：无特殊限制。

对于全部的数据，$2\le n \le 5\times 10^5$，$1\leq l_i \leq r_i \leq 10^8$，$1\leq d_i \leq 10^8$， $d_i<d_{i+1}$（$1\leq i <n$），并且有：
$$n\sum_{i=1}^nd_i^2 \not \equiv \left(\sum_{i=1}^nd_i \right)^2 \pmod{998244353}$$

【提示】

题目中要求出「$\text{RSS}$ 的最小值」期望值。对于离散随机变量 $X$，假设其可以取值为 $a_1,a_2,\cdots,a_n$，对应概率为 $p_1,p_2,\cdots,p_n$（$p_1+\cdots+p_n=1$），则其期望值可以定义为：
$$\mathbb E[X]=\sum_{i=1}^np_i a_i$$
对于计算有理数取模的方法，请参考[模板题](https://www.luogu.com.cn/problem/P2613)。


title: 洞察（Insight）

background:
看待万物毫无偏见的新视角 —— 洞察。

****
「洞察之光」凯伊·雅思·德·布拉德，是减法盗贼，也是背负黑暗命运的混沌骑士。

凯伊的右手内隐藏着混沌之剑，为了使其发挥出足够的力量又不至于失控，需要满足特定的内部结构。她想知道有多少种符合条件的结构，为了方便你的计算，她把问题转化为如下形式：

description:
赛时更新：题面中的笔误已修改为：相邻点对颜色**互不相同**。
****
在一个**无向连通图** $G$ 中，有黑色和白色的点各 $n$ 个，红色的点 $1$ 个。
所有点之间互不相同，图中有 $2n$ 条边，且所有相邻点对（也就是有边直接相连的点对）的颜色也互不相同。

对于 $\text{type}$ 等于 $0$ 或 $1$，分别在不同条件下计算符合条件的图 $G$ 有多少个：

- $\text{type}=0$：无附加条件。
- $\text{type}=1$：对于每个**不包含**红色点的极大连通子图，都要对**恰好一个**点做特殊标记（每个标记也都是不同的）。

答案对 $998244353$ 取模。

inputFormat: 输入一行两个整数 $n$ 和 $\text{type}$。

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

hint:
【样例 $1$ 解释】
此时 $\text{type}=1$，所有 $5$ 种合法的图包括：

1. $R-W'-B$
2. $R-W-B'$
3. $R-B'-W$
4. $R-B-W'$
5. $B'-R-W'$

由于 $n=1$，可以仅用 $B$ 和 $W$ 来区分白点和黑点，$R$ 表示红点。中间的横杠表示连边，$B'$ 和 $W'$ 分别表示有标记的白点和黑点。

注意，由于第 $5$ 个图中，单个的 $B$ 和 $W$ 就是不包含 $R$ 的极大连通子图，必须各有一个标记在这唯一的位置上。

【样例 $2,3$ 解释】

见附件图片，其中展示了 $\text{type}=0$ 时全部的 $45$ 种可能的图 $G$。

对于 $\text{type}=1$ 的情况，只需要对每个图的基础上做标记，就可以数出答案为 $149$。

【样例 $4,5$ 解释】

取模前的答案分别为 $116758263583336861101$ 和 $4159784334433940020473603987503242886367209494283213841$。

【数据范围】

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

Subtask 1（8 pts）：$n \le4$；
Subtask 2（10 pts）：$n \le 10^3$，$\text{type}=0$；
Subtask 3（11 pts）：$\text{type}=0$；
Subtask 4（13 pts）：$n \le 100$，$\text{type}=1$；
Subtask 5（14 pts）：$n \le 10^3$，$\text{type}=1$；
Subtask 6（21 pts）：$n\le 10^5$，$\text{type}=1$；
Subtask 7（23 pts）：$\text{type}=1$。

对于全部的数据，$1\le n \le 10^7$，$\text{type}\in \{ 0,1\}$。

【提示】
对于这类题目，你或许会想从 [OEIS](https://oeis.org/) 上寻找答案。但我要提醒你的是，直接搜索答案数列不会找到任何结果。然而，对于小数据范围，仍然可以提前处理出答案数列。

图片链接似乎已损坏（？），原链接地址：https://i.niupic.com/images/2024/04/05/huyP.png


title: 『STA - R5』Remove and Decrease Game

description:
给定 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个，**保证 $\bm{a_i}$ 互不相同**。

Alice 和 Bob 轮流执行以下两种操作中的一种，Alice 先手，不能执行操作的人判负。

- 对于每堆石子均取走一个石子。
- 移除石子数量最小的一堆石子。

在两人均采取最优策略的情况下，问谁可以获胜。你需要回答 $T$ 次询问。

inputFormat:
**本题单个测试点内含有多组询问。**

第一行一个正整数 $T$，代表询问次数。

对于每组询问：第一行一个正整数 $n$，代表石子堆数。第二行 $n$ 个正整数，第 $i$ 个正整数代表 $a_i$。

outputFormat: 对于每组询问，输出一行 `Alice` 或 `Bob`，表示谁会获胜。


title: [USACO18OPEN] Family Tree B

description: Farmer John 拥有一个传承数代的家族经营的农场，其中的奶牛的根源同样也可以在这个农场中追溯数代。通过检索古老的记录，Farmer John 好奇于现在的这群奶牛互相之间是什么关系。请帮帮他！

inputFormat:
输入的第一行包含 $N$（$1\le N\le 100$），之后是两头奶牛的名字。每头奶牛的名字都是由至多 $10$ 个大写字母（`A-Z`）组成的字符串。Farmer John 好奇于这行输入中这两头奶牛之间的关系。

接下来的 $N$ 行，每行包含两头奶牛的名字 $X$ 和 $Y$，表示 $X$ 是 $Y$ 的母亲。

outputFormat:
输出包含一行，表示输入第一行指定的两头奶牛之间的关系（简单起见，在下面的例子中，将这两头奶牛称为 BESSIE 和 ELSIE）。下面是可能出现的不同种类的关系：

- 如果BESSIE和ELSIE的母亲是同一头奶牛，输出 `SIBLINGS`。
- BESSIE 可能是 ELSIE 的直系后代，也就是说 ELSIE 是BESSIE 的母亲（`mother`），外祖母（`grand-mother`），外曾外祖母（`great-grand-mother`），外曾外曾外祖母（`great-great-grand-mother`），等等。如果是这种情况，输出 `ELSIE is the (relation) of BESSIE`，其中 `(relation)` 是适当的关系，比如 `great-great-grand-mother`。
- 如果 ELSIE 不是 BESSIE 的某个祖先或姐妹，但是是 BESSIE 的某个祖先的孩子，那么 ELSIE 就是 BESSIE 的姨母（`aunt`）。（译者注：英语原题在这里表述有误，供题人已作出声明。）如果 ELSIE 是 BESSIE 的外祖母的孩子，输出 `ELSIE is the aunt of BESSIE`；如果 ELSIE 是 BESSIE 的外曾外祖母的孩子，输出 `ELSIE is the great-aunt of BESSIE`；如果 ELSIE 是 BESSIE 的外曾外曾外祖母的孩子，输出 `ELSIE is the great-great-aunt of BESSIE`；以此类推。
- 如果 BESSIE 和 ELSIE 有任何其他的亲戚关系（也就是说，她们有共同的祖先），她们就是表姐妹，输出 `COUSINS`。
- 如果 BESSIE 和 ELSIE 既没有共同的祖先，其中任何一头也不是另一头的直系后代，输出 `NOT RELATED`。

下图描述了上述关系，你只需考虑这些关系。观察到有一些像是“甥女（`niece`）”（姊妹的女儿）的关系是不必要的，这是由于如果 BESSIE 是 ELSIE 的甥女，那么 ELSIE 就是 BESSIE 的姨母。

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

samples:
7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER


title: 水影若深蓝

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

帆帆爱明日方舟，更爱水月和深蓝之树。但在龙年，他想构建一棵独属于他的深蓝之树。

description:
在梦里，在朦胧的水影中，帆帆看见了这棵只属于他的深蓝之树。

当一切梦沉寂，他却遗忘了所有，只记得树上有 $n$ 个结点。

真的吗？似乎并没有，有 $m$ 件事情他一直牢记着，第 $i$ 件事情是：节点 $u_i$ 和 $v_i$ 在这棵深蓝之树上唯一的不重复经过某个点的路径恰好有两条边。

那么，你能否帮助帆帆想起来这棵深蓝之树的样子呢，如果有多个可能的，你只需要输出任意一种。

当然，帆帆也是会磨损的，因此当你发现无论如何都找不到满足帆帆这 $m$ 件事情的深蓝之树时，你需要报告无解。

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

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

对于每组数据：

第一行两个非负整数 $n,m$ 表示树上的点数和帆帆记忆中事件个数。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$ 表示一个事件。

outputFormat:
对于每组数据：

- 若不存在符合条件的树，输出 `No`。
- 否则，第一行输出 `Yes`，接下来 $n-1$ 行输出 $n-1$ 对正整数 $(u,v)$，表示你给出的树上的 $n-1$ 条边。

本题采用 `special judge` 评测，也就是说，如果有多种可能的答案，你可以输出任意一种。

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

对于第一组数据，不难验证给出的树符合条件。

对于第二组数据，可以证明不存在符合条件的树。

### 测试点约束

对于 $100\%$ 的数据，$1\le T\le 10^5$，$n\ge 1$，$m\ge 0$，$1\le \sum n\le 3\times 10^5$，$0\le \sum m\le 3\times 10^5$，$1\le u_i,v_i\le n$，$u_i\neq v_i$。

本题采用捆绑测试。

| 子任务编号 | 特殊限制 | 分值 |
| :--------: | :-------------: | :--: |
| Subtask #1 |     $\sum n,\sum m\le 9$     | $10$ |
| Subtask #2 |    $\sum n,\sum m\le 50$     | $10$ |
| Subtask #3 |    $\sum n,\sum m\le 5000$    | $10$ |
| Subtask #4 |   $v_i=u_i+1$    | $10$ |
| Subtask #5 |   $u_i=1$    | $10$ |
| Subtask #6 |   $u_i\neq 1,v_i\neq 1$    | $10$ |
| Subtask #7 |   $T=1$    | $10$ |
| Subtask #8 |   无    | $30$ |


title: 勇气（Courage）

background:
数学家渴求真理的美德，永不停歇的力量的源泉 —— 勇气。
****
「勇气之光」乔伊，是杜沃夫族的接任族长，也是拥有古代战神之力的战士。

description:
乔伊有一项技能，可以将 $x$ 的攻击力强化为 $x^2$。但这个技能并不完美，除了第一次之外，每一次**使用该技能前**，攻击力都会衰减到之前的一半。

比如最初的攻击力为 $\color{red}6$，强化后变成 $6^2=\color{red}{36}$。而在下一次强化前，会先衰减到 $36/2=18$，然后再强化为 $18^2=\color{red}{324}$。

乔伊想知道，如果最初的攻击力为 $x$，至少需要多少次强化，可以使其**不小于** $2^n$？
如果无论强化多少次，都不可能达到要求，请输出 `inf`。

inputFormat: 输入一行两个正整数 $x,n$。分别表示初始攻击力为 $x$，以及要达到 $2^n$ 的攻击力。

outputFormat: 输出一行一个整数或字符串 `inf`，表示答案。

hint:
【样例 $1$ 解释】
初始攻击力 $x=2$ 就已经达到了 $2^n=2$，不需要使用技能就满足了要求，故答案为 $0$。

【样例 $2$ 解释】
初始攻击力为 $3$，需要达到 $2^6=64$。第一次用技能后变为 $9$，第二次后变为 $(9/2)^2=81/4$，第三次变为 $((81/4)/2)^2=6561/64$，已经达到了要求，故答案为 $3$。

【数据范围】
**本题采用捆绑测试。**

Subtask 1（15 pts）：$n\le 60$；
Subtask 2（20 pts）：$x=4$；
Subtask 3（25 pts）：$n\le 10^5$；
Subtask 4（40 pts）：无特殊限制。

对于全部的数据，$2\le x\le 10^9$，$1\le n \le 10^9$。


title: 『STA - R5』5k.sync.closer

description:
给定一条 [`std::freopen`](https://zh.cppreference.com/w/cpp/io/c/freopen) 语句，输出其操作的文件名称。

形式化地，[`std::freopen`](https://zh.cppreference.com/w/cpp/io/c/freopen) 语句都应该恰好是

```cpp
std::freopen("<title>","<mode>",<stream>);
```

其中 `<title>` 为其操作的文件名称。其至少包含一个字符，并且只可能包含下列几种字符：
- 大写英文字符；
- 小写英文字符；
- 阿拉伯数字；
- 英文半角句点 `.`。

`<mode>` 为文件访问标记，其只可能为 `r`、`w`、`a` 中的一种。`<stream>` 为文件流，其只可能为 `stdin`、`stdout`、`stderr` 中的一种。

你需要回答 $T$ 次询问。

inputFormat:
**本题单个测试点内含有多组询问。**

第一行一个正整数 $T$，代表询问次数。

对于每组询问：一行一个字符串，代表一条 [`std::freopen`](https://zh.cppreference.com/w/cpp/io/c/freopen) 语句。

outputFormat: 对于每组询问，输出一行一个字符串，代表其操作的文件名称。

samples:
5k.sync.closer
5k.sync.closer
5k.sync.closer
5k.sync.closer
5k.sync.closer
5k.sync.closer
5k.sync.closer
5k.sync.closer
5k.sync.closer

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

对于 $100\%$ 的数据：

- $1 \le T \le 1000$。
- 每条语句的长度均不超过 $1000$。

具体部分分分配如下：

- Subtask 1 (30pts)：保证文件名为 `5k.sync.closer`。
- Subtask 2 (30pts)：保证文件名长度为 $1$。
- Subtask 3 (40pts)：无特殊限制。


title: 奉献（Dedication）

background:
不断鞭策自己的数学精神 —— 奉献。
****
「奉献之光」丽莎，既是「秩序之神」派拉的神官，亦为「无秩序之神」迪奥尼斯的信徒。

丽莎最近学习了[高精度除法](https://www.luogu.com.cn/problem/P5432)，她能以 $\Theta(n \log n)$ 的时间复杂度计算 $n$ 位整数除法了。

description:
丽莎想要制作一张 $n$ 以内正整数的除法表。具体来说，是一张记录了 $\lfloor a/b \rfloor$（$1\leq b \leq a \leq n$，$a,b$ 均为整数）的表格。她使用如下方法来制作：

>以 $a$ 为第一关键字从小到大，以 $b$ 为第二关键字从小到大的顺序枚举位置 $(a,b)$。若 $(a,b)$ 位置**未被填写**，则：
>
>计算 $\lfloor a/b \rfloor$，这需要消耗的**魔力**为 $d_a \log_2 d_a$（其中 $d_a$ 表示 $a$ 在十进制下的位数，即 $d_a=\lfloor 1+ \log_{10}a\rfloor$）。然后枚举正整数 $i$，找到所有**未被填写**的 $(ai,bi)$（$ai\leq n$）位置都填写入 $\lfloor a/b \rfloor$。每次填写需要消耗的魔力为 $d_i$。

由于美娜已经做过一张乘法表，丽莎无需魔力就可以直接计算乘法。现在丽莎想要知道，制作整个除法表需要消耗多少魔力。

为了防止精度问题，只要你的输出与标准输出的**相对误差**不超过 $10^{-6}$ 则视为正确。保证标准输出与实际答案的相对误差不超过 $10^{-10}$。

inputFormat: 输入一行一个正整数 $n$，表示要制作大小为 $n$ 的除法表。

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

hint:
【样例 $1$ 解释】

由于 $a \leq 6$，$d_a=1$，从而 $d_a \log_2 d_a=0$。也就是说在此范围下只有填写数字会消耗魔力。而每次 $i$ 也不超过 $6$，满足 $d_i=1$，每次填写都消耗固定 $1$ 点魔力，要填写全部 $1+2+3+4+5+6=21$ 个数消耗的魔力就是 $21$。

故答案为 $21$。

【数据范围】

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

Subtask 1（15 pts）：$n\le 5000$；
Subtask 2（15 pts）：$n\le 10^5$；
Subtask 3（30 pts）：$n\le 2 \times 10^6$；
Subtask 4（40 pts）：无特殊限制。

对于全部的数据，$1\le n \le 2 \times 10^7$。

【提示】

$\log_2 n$ 读作「以 $2$ 为底的 $n$ 的对数」。设 $x=\log_2n$，它表示 $2^x=n$。


title: 超越（Transcendent）

background:
越过领域和现实的终极存在 —— 超越。

****
「超越之光」美娜，是亚特兰蒂斯最强的魔法师，亦是无人能及的贤者。即便如此，她也一刻都没有停下对数学的探索。

「最高次系数为 $1$ 的整系数多项式方程的解不一定是整数，」美娜自言自语道，「但是其所有根组成的对称多项式的值必然是整数。」

「这很容易证明，却也很有趣呢。」想到这里，美娜突然有了开发新魔法的思路。

description:
美娜的魔法需要 $m+1$ 个阶段来构建。第 $i \ (1 \leq i \leq m)$ 个阶段每次尝试的成功概率为 $a_i/b_i$，如果失败**只需要重试当前阶段**即可，如果成功就能进入下一个阶段。

最后的第 $m+1$ 个阶段需要选一个魔力基数 $c$。不过这个魔法现在并不稳定，设 $r$ 是一个不大于 $2n$ 的范围内**均匀随机**生成的正整数，则
$$c=\cos \frac{r\pi}{n}$$
最后，若美娜在前 $m$ 个阶段中总共尝试了 $k$ 次（每次无论失败或成功，都算多一次尝试），她的魔法会产生 $c^k$ 的能量。

美娜想知道这个魔法所产生能量的期望值是多少，当然她很容易就算出了答案，你能帮她验算一下吗？

你只用输出答案对 $998244353$ 取模的结果即可。显然，答案一定是有理数，所以你可以简单地计算其对 $998244353$ 取模的值。

inputFormat:
第一行两个正整数 $n,m$。
接下来 $m$ 行，每行两个正整数 $a_i,b_i$，意义如题目描述。

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

hint:
【样例 $1$ 解释】

此时 $m=3$，前 $m$ 个阶段中，第一阶段的成功概率为 $1/2$，之后两个阶段的成功概率都为 $2/3$。由此可以算出，恰好尝试 $k \ (k \geq m)$ 次完成前 $m$ 个阶段的概率为（我有一个巧妙的方法给出证明，可惜这里空间太小，写不下）：

$$p_k=2^{4-k}-4(k+1)3^{1-k}$$
例如 $p_3=2/9$，这是每个阶段都一次成功的概率 $1/2 \times 2/3 \times 2/3$。
又如 $p_4=7/27$，这要求在某一阶段尝试恰好两次，其它阶段都一次成功，即：
$$p_4=\left( \frac 12\right)^2   \frac 23 \cdot \frac 23+\frac 12\left( \frac 29\right)\frac 23+\frac 12\cdot \frac 23\left( \frac 29\right)$$
样例中 $n=2$，可知 $c=1$ 的概率为 $1/4$，$c=-1$ 的概率为 $1/4$，还有 $1/2$ 的概率 $c=0$。故答案为

$$\frac 14\sum_{k\geq 3}p_k (1+(-1)^k)=\frac{11}{48}$$
对 $998244353$ 取模后为 $103983787$。

【样例 $2$ 解释】

取模前的答案为 $\dfrac{24284321}{191028915}$。

【数据范围】

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

Subtask 1（7 pts）：$n\le 6$，$m=1$；
Subtask 2（9 pts）：$n\le 6$，$m\le 10$；
Subtask 3（13 pts）：$n\le 500$，$m\le 500$；
Subtask 4（13 pts）：$n=2^{19}$；
Subtask 5（15 pts）：$n \le 10^5$，$m\le 500$；
Subtask 6（15 pts）：不同的 $a_i/b_i$ 最多有两组；
Subtask 7（28 pts）：无特殊限制。

对于全部数据，$1\le n \le 10^8$，$1\le m \le 60000$，$1\le a_i<b_i\leq 10^8$。且保证

$$U_n\left( \frac{b_i}{b_i-a_i}\right)\not \equiv 0 \pmod{998244353}$$
其中 $U_n(x)$ 表示 $n$ 次的[第二类 Chebyshev 多项式](https://mathworld.wolfram.com/ChebyshevPolynomialoftheSecondKind.html)。

【提示】
你在找什么呢？或许可以再看看题目背景，会有帮助的。


title: [WC2024] 代码堵塞

description:
小 $\beth$ 为了纪念停办的 codejam，准备了一场“代码堵塞纪念赛”。小 $\beth$ 的朋友小 $\mho$ 也来围观，于是小 $\beth$ 想预测小 $\mho$ 的成绩。

比赛共 $T$ 秒，有 $n$ 道题。第 $i(1 \le i \le n)$ 题分数为 $a_i$，小 $\beth$ 预测小 $\mho$ 需要 $t_i$ 秒完成。

题目有两种类型：结果可见和结果不可见。结果不可见的题在比赛结束后才能知道评测结果，而结果可见的题在提交后立即得到评测结果。小 $\beth$ 还没确定每道题的类型。

小 $\mho$ 由于从不写对拍，所以会先按编号从小到大完成所有结果可见的题，再按编号从小到大完成所有结果不可见的题。小 $\mho$ 会花 $t_i$ 秒完成第 $i$ 题，当小 $\mho$ 花费在第 $i$ 题和在第 $i$ 题之前完成的所有题的时间总和**不超过** $T$，就会在第 $i$ 题**产生提交**。

由于小 $\mho$ 提交即 AC，所以小 $\beth$ 想知道对于所有 $2^n$ 种确定 $n$ 道题类型的方案，小 $\mho$ 所能得到的分数总和的和。由于答案很大，你需要将答案对 $998244353$ 取模。

inputFormat:
输入的第一行包含三个整数 $c, n, T$，表示测试点编号，题数和比赛时间。样例中的 $c$ 表示其满足的限制条件与第 $c$ 个测试点一致。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \cdots , a_n$，分别表示每道题的分数。

输入的第三行包含 $n$ 个整数 $t_1, t_2, \cdots , t_n$，分别表示小 $\mho$ 做每道题的时间。

outputFormat: 输出一行包含一个整数，表示对于所有确定 $n$ 道题类型的方案，小 $\mho$ 所能得到的分数总和的和，对 $998244353$ 取模。


title: [WC2024] 水镜

description:
**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

A 城是一座多雨的城市，山溪泉水众多。出于对水的喜爱，市民们在城市中央修建了一座大喷泉。

喷泉的水池中有一排 $n$ 个石柱，从左到右编号为 $1, 2, \cdots , n$，第 $i$ 个石柱的高度为 $h_i$。水池中有储水，水位 $L$ 为一个**正实数**。第 $i$ 个石柱会产生一个高度为 $h'_i = 2L - h_i$ 的像。若石柱在水面上方，像在水面下方；若石柱在水面下方，像在水面上方；若石柱顶端与水面重合，则像也与水面重合。

传说水中栖息着泉水精灵，每到满月之夜，它们就会在石柱上起舞，行动规则如下：

- 泉水精灵只能栖息在石柱顶端，或者石柱的像的顶端。即如果泉水精灵在石柱 $u$ 上，它的高度 $r_u$ 便只有 $h_u, h'_u$ 两种可能取值。
- 泉水精灵每次只能前往右侧相邻的石柱（或石柱的像）。
- 在移动过程中，泉水精灵的高度必须**严格单调递增**。

泉水精灵会选择一个石柱（或石柱的像）为起点，进行若干次移动后停止。这样的过程称为一次**舞蹈**。

A 城的雨季漫长，由于不规律的降雨，喷泉的水位可能会多次变化，舞蹈路径的可能性也随之改变。作为远道而来的旅人，你很想知道有多少种舞蹈是可能实现的。具体地，你需要计算有多少对 $(u, v)$（$1 ≤ u < v ≤ n$），满足存在一种水位 $L$，使得泉水精灵在一次舞蹈中，能从第 $u$ 个石柱（或它的像）出发，到达第 $v$ 个石柱（或它的像）。

**形式化的**：给定一个长度为 $n$ 的正整数序列 $h_1, h_2,\cdots , h_n$，求满足以下所有条件的
二元组 $(u, v)$ 的数量：
- $1 \le u < v \le n$，且 $u, v$ 为整数；
- 存在一个**正实数** $L$ 以及一个长度为 $(v - u + 1)$ 的序列 $r_u, r_{u+1},\cdots , r_v$ 满足以下
所有条件：
- $\forall u \le i \le v$，记 $h'_i = 2L - h_i$，则 $r_i \in \{h_i,h'_i\}$，特别地，当 $h_i = h'_i$ 时，$r_i = h_i$；
- $\forall u \le i < v, r_i < r_{i+1}$。

inputFormat:
输入的第一行包含一个正整数 $n$，表示石柱的个数。

输入的第二行包含 $n$ 个正整数 $h_1, h_2, \cdots , h_n$，表示石柱的高度。

outputFormat: 输出一行一个整数，表示符合题目描述的 $(u, v)$ 对数。


title: [WC2024] 线段树

description:
小 Y 最近学会了如何用线段树维护序列，并支持区间求和的操作。

**以下给出本题中线段树的定义。 该定义可能和你熟知的线段树有区别。**

- 线段树是一种有根的二叉树，其每个节点对应了序列上的一个区间 $[l, r)$，其中根节点对应 $[0, n)$。
- 对于每个节点，若其代表的序列区间 $[l, r)$ 满足 $r - l = 1$，则其为叶节点；否则存在整数 $m(l < m < r)$，满足其左儿子代表区间 $[l, m)$，右儿子代表区间 $[m, r)$。
- 线段树的形态取决于每个非叶结点的划分点 $m$ 的选择。
- 在区间求和的问题上，对于序列 $a_0, a_1, \dots , a_{n-1}$，线段树的每个结点 $[l, r)$ 维护了
$(a_l + a_{l+1} + \cdots + a_{r-1})$ 的值。

小 J 有一个长度为 $N$ 的数组 $A_0, A_1, \dots , A_{N-1}$，他并不知道 $A$ 中的任何一个数，但是他有一棵线段树维护了 $A$ 的区间和。线段树由 $X_1, X_2, \dots , X_{N-1}$ 给出，其中 $X_i$ 是线段树先序遍历的第 $i$ 个非叶结点的划分点。

例如，如果 $N = 5, X = [2, 1, 4, 3]$，则线段树包含的结点的先序遍历为 $[0, 5), [0, 2), [0, 1), [1, 2), [2, 5), [2, 4), [2, 3), [3, 4), [4, 5)$。

小 J 有 $M$ 个区间 $[L_1, R_1), [L_2, R_2), \dots , [L_M, R_M)$，他想知道，在所有 $2^{2N-1}$ 个线段树结点的子集中，有多少个子集 $S$ 满足以下条件：

- 如果已知 $S$ 中所有结点维护的值，则每个 $[L_i
, R_i)$ 区间的和都能被唯一确定。

例如，如果已知 $[0, 1), [1, 2)$，就能确定 $[0, 2)$ 的和；反过来，如果已知 $[0, 1), [0, 2)$，也能确定 $[1, 2)$ 的和。但如果仅已知 $[0, 2), [2, 4)$ 则不能确定 $[0, 3)$ 或 $[1, 2)$ 的和。

由于答案很大，你需要输出答案对 $998244353$ 取模后的值。

inputFormat:
输入的第一行包含两个整数 $N, M$，分别表示数组长度和区间个数。

输入的第二行包含 $N - 1$ 个整数 $X_1, X_2, \dots , X_{N-1}$。

接下来 $M$ 行，每行包含两个整数 $L_i, R_i$，表示一个区间。

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

hint:
**样例 1 解释**

只有当直接知道 $[0, 2)$ 的总和或同时知道 $[0, 1)$ 和 $[1, 2)$ 的总和时才能知道 $[0, 2)$ 的总和，因此总的方案数为 $2^2 + 1 = 5$。

### 数据范围

对于所有测试数据：
- $2 \le N \le 2 \times 10^5$，
- $1 \le M \le \min \{\frac{N(N+1)}{2}, 2 \times 10^5\}$，
- $\forall 1 \le i \le N - 1, 1 \le X_i \le N - 1$，
- 保证 $X_i$ 正确描述了一棵线段树，
- $\forall 1 \le i \le M, 0 \le L_i < R_i \le N$，
- $\forall i \ne j,(L_i, R_i) \ne (L_j, R_j )$。

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


title: 似巨龙高歌

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

拜谢 whk 神犇帆巨/bx

尽管帆帆文化课很强，但在新年他不想给同龄蒟蒻带来太大压力，于是他准备对一年的考试成绩做一些手脚……

description:
面对着自己向巨龙一样腾飞的成绩，新年到来时帆帆忍不住唱起了《爱你》。

他今年一共有 $n$ 次考试，第 $i$ 次考试的排名是 $a_i$。

这在无形之中给别的同学造成了压力，于是他希望把自己的 $n$ 次排名进行重排，使得进步最大的一次考试进步的名次最少，这样他就可以隐藏自己的实力。

对于第 $i$ 次和第 $i+1$ 次考试（$1\le i < n$），他的进步名次即为 $a_i-a_{i+1}$，如果该值为负则代表他退步了。

请你帮帮他。

inputFormat:
输入两行。

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

第二行，输入 $n$ 个整数，每两个整数之间用空格隔开。第 $i$ 个整数表示 $a_i$。

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

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

帆帆不改变原本的考试序列，那么从第一次到第二次考试进步了 $0$ 名（排名没变化）。

### 【样例 2 解释】

帆帆可以把自己的考试排名重排为 $1,2,3,4$，那么他每次考试都进步了 $-1$，所以答案是 $-1$。

本题采用捆绑测试

### 【数据范围】

- 对于 $30\%$ 的数据，保证 $n\le 10$。

- 对于 $50\%$ 的数据，保证 $n\le 5000$。

- 对于另外 $20\%$ 的数据，保证 $a_i\le 2$。

- 对于 $100\%$ 的数据，保证 $2\le n\le 10^6$，$1\le a_i\le 10^9$。


title: 陌路寻诗礼

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

作为 luogu 网红的帆巨，有非常多狂热的粉丝，而我们的帆巨也很喜欢面基，寻找遍布大江南北的粉丝们。

description:
帆巨所在的家乡的地图是一张有 $n$ 个节点 $m$ 条有向道路的有向图，每个节点都是一个城市，而帆巨所在的城市是 $1$ 号城市，并且 $1$ 号城市总是可以通过若干道路到达其他任何城市。

第 $i$ 条道路从 $x_i$ 号城市出发到达 $y_i$ 号城市，长度为 $z_i$。

帆帆现在要从他的 $1$ 号城市前往各个城市面基。

精通 spfa 算法的帆帆在面基的过程中自然会按照长度和最短的路径去其他城市。

但是帆帆有选择困难症，他希望从 $1$ 号城市到达每一座城市的最短路径都是唯一的，所以他决定施加魔法，改变所有道路的长度，具体地：

帆巨施加魔法后，对于每一条道路的长度，都可以 **独立地** 将其变成一个 $[1,k]$ 范围内的整数，其中 $k$ 是帆巨的魔法等级。

但帆巨所在的世界的地图和他的魔法等级一直在变，总共会变 $T$ 次，所以他希望你对 $T$ 次询问都给出一种构造方法使得帆巨不会纠结或者报告无解。

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

接下来 $T$ 组，每组先是三个整数 $n,m,k$，接着 $m$ 行描述有向道路 $(x_i,y_i)$。

**不保证无自环无重边。**

outputFormat:
对于每组数据，如果有解，第一行输出 `Yes`，第二行 $m$ 个数依次输出每条边的权值；如果没有解，一行输出 `No`。

本题采用 `special judge` 评测，也就是说，如果有多种可能的答案，你可以输出任意一种。

hint:
### 【样例解释】

对于第一组数据，$1$ 号点到达每个点的路径都是唯一，自然无论怎么设置边权，最短路都是唯一的。

对于第二组数据，因为 $k=1$，所以两条边的边权都只能设置为 $1$。$1$ 号点到 $2$ 号点的最短路长度为 $1$，走两条边都可以，所以不是唯一的。

### 【数据范围】

本题采用捆绑测试。

对于 $20\%$ 的数据，$n,m\leq 5$。

对于另外 $20\%$ 的数据，$k=1$。

对于另外 $20\%$ 的数据，$m=n-1$。

对于另外 $20\%$ 的数据，$k=10^9$。

对于 $100\%$ 的数据，$n\ge 1$，$m\ge 0$，$1\le \sum n,\sum m\leq 3\times 10^5$，$1\leq k \leq 10^9$，$1\le x_i,y_i\le n$。


title: [yLCPC2024] C. 舞萌基本练习

description:
扶苏在游玩舞萌 dx 的过程中，发现一首歌可以分成不超过 $k$ 段分别进行练习。

具体来说，这首歌共有 $n$ 个音符，每个音符有一个难度值。第 $i$ 个音符的难度值为 $a_i$。扶苏觉得一段歌曲的音符的难度应该是尽可能变难的。因此对于音符序列的一个区间 $[l, r]$，她认为这段区间的『不优美度』是这段区间的**逆序对**数。

一个区间 $[l, r]$ 的**逆序对数**被定义为满足 $l \leq i < j \leq r$ 且 $a_i > a_j$ 的数对 $(i, j)$ 个数。

扶苏希望把这首歌划分成不超过 $k$ 个子段，满足每个音符都至少属于一个子段，使得不优美度最大的段的不优美度尽可能小。

形式化的，你需要划分出 $t \leq k$ 个区间 $[l_1, r_1], [l_2, r_2], \dots [l_t, r_t]$，满足：

- $l_1 = 1$，$r_t = n$。
- 对 $1 \leq i < t$，$r_i + 1= l_{i + 1}$。
- 对 $1 \leq i \leq t$，$l_i \leq r_i$。

定义 $f(l, r)$ 表示区间 $[l, r]$ 的不优美度，最小化 $\max\limits_{i = 1}^t f(l_i, r_i)$

inputFormat:
**本题单个测试点内有多组测试数据**。第一行是一个正整数 $T$，表示数据组数。对每组数据：

第一行是两个整数 $n,k$（$1 \leq k \leq n \leq 10^5$），表示歌曲的音符数和最多的划分段数。
第二行有 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示每个音符的难度。

数据保证单个测试点内的 $n$ 之和不超过 $10^5$。

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


title: [yLCPC2024] D. 排卡

background:
经过千辛万苦，扶苏终于到达了机厅。但是她很快发现机厅排起了大 b 队 ~~（不是省选的 B 队）~~。

舞萌玩家们在人多的时候经常采取排卡的方式决定谁下一个上机。因为人实在是太多了，他们在排卡的时候，便注意到了卡上的编号。

他们向扶苏提了一个问题，你能解决吗？

description:
扶苏有一个双端队列 $a$。这个队列与计算机科学中队列的概念类似，不同的是，这个队列既可以从队列头读取和弹出元素，也可以在队列尾部读取和弹出元素，因此被称为『双端队列』。

这个队列中有 $n$ 个数。扶苏将通过 $n$ 次操作构造一个长度为 $n$ 的序列 $b$，第 $i$（$1 \leq i \leq n$）次操作会可以进行如下两个过程之一：

1. 令 $b_i$ 为 $a$ 的队列头，并在 $a$ 的头部弹出一个元素。
2. 令 $b_i$ 为 $a$ 的队列尾，并在 $a$ 的尾部弹出一个元素。

我们定义一个数对 $(i, j)$ 的得分为：

$$\mathrm{score}(i,j) = i^j \bmod 998244353$$

即 $i$ 的 $j$ 次幂对 $998244353$ 取余数的结果。特别的，在本题中我们规定 $0^0 = 0$。

现在，扶苏想用最优的策略构造 $b$ 序列，最大化如下式子的值：

$$\sum_{i = 1}^{n - 1} \mathrm{score}(b_i, b_{i + 1})$$

即 $b$ 所有相邻两项按原顺序计算的得分之和。

注意，我们仅在计算一个数对的时候将得分对 $998,244,353$ 取模，在计算求和时不再将这个和取余。

inputFormat:
**本题单个测试点内有多组测试数据**。第一行是一个正整数，表示数据组数 $T$。对每组数据：

第一行是一个整数 $n$（$2 \leq n \leq 10^3$），表示序列的长度。
第二行有 $n$ 个整数 $a_1, a_2, \dots a_n$（$0 \leq a_i < 998,244,353$），按从头到尾的顺序表示队列 $a$ 里每个数字的值。

数据保证单个测试点内 $n$ 的和不超过 $10^3$。

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


title: [yLCPC2024] F. PANDORA PARADOXXX

background:
扶苏所在的城市的机厅联合举办了 KING of PerforPandora！

但是因为大雪封路，有些机厅不能到达。她想知道在能互相到达的机厅中距离最远为多少。

description:
给定一棵 $n$ 个结点的树。一棵树被定义为一个有 $n$ 个点和 $n-1$ 条边的无向连通图。这棵树的边有边权。两点 $u,v$ 间的距离 $\mathrm{dist}(u,v)$ 定义为从 $u$ 到 $v$ 的简单路径边权和。可以证明树上两点间的简单路径是唯一的。特别的，我们规定 $\mathrm{dist}(u, u) = 0$。

现在有 $q$ 次操作，每次会删除这棵树上的一条边。显然在做出至少一次操作后，这棵树会被分成若干个连通块。你需要在每次操作后都求出每个连通块内距离最远的两个点的距离的最大值。

形式化的，每次操作后，你要求出

$$\max\limits_{c \in C}\{\max\limits_{u, v \in c} \mathrm{dist}(u,v)\}$$

其中 $C$ 表示当前所有连通块构成的集合。

inputFormat:
**本题单个测试点内有多组测试数据**。第一行是一个正整数 $T$，表示数据组数。对每组数据：

输入第一行是两个整数 $n, q$（$1 \leq q < n \leq 10^5$），依次表示树的结点数和操作数。
接下来 $n - 1$ 行，每行三个整数 $u,v,w$（$1 \leq u, v \leq n$，$1 \leq w \leq 10^5$）表示树上有一条连接 $u$ 和 $v$ 的权值为 $w$ 的边。
接下来 $q$ 行，每行一个整数 $e_i$（$1 \leq e_i < n$），表示这次操作删除了输入的第 $e_i$ 条边。数据保证每条边只会被删除一次。

数据保证单个测试点内的 $n$ 之和不超过 $3 \times 10^5$。

outputFormat: 对每组数据，输出 $q$ 行，每行一个整数，依次表示每次操作后所求的答案。

hint:
#### 提示

请注意大量的数据读入和输出对程序效率造成的影响，选择合适的读入输出方式，不要频繁刷新输出缓冲区，避免超时。


title: 【MX-X3-T2】「RiOI-4」消えた夏の夢

background:
> いつまでも二人語り合おう\
終わった夏を	\
探してた夢をそっと\
終わらせよう戻らないように\
お別れだね\
君へ届けと願った声が\
風になって心の隙間を\
通り抜けた\
——《消えた夏の夢》

小 T 不会出题。

description:
小 T 手中有一个数 $x$，初始时为 $p$。而小 ⊥ 手中有一个长为 $n$ 的序列 $a$。一次操作中，小 T 需要依次进行如下的修改：

- 选中 $a$ 中的一个数 $a_i$。
- 将 $x$ 加上 $a_i$。
- 让 $a_i$ 变为自身的相反数，即 $-a_i$。

小 T 想知道，在若干次操作（可以不进行操作，同一个位置可以选中多次）之后，小 T 手中的数 $x$ 最大是多少。

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

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

outputFormat: 输出一行仅一个整数，表示 $x$ 最大是多少。


title: [语言月赛 202402] 三位数

description:
bj12z_jiasiyuan  想要你输出满足以下几个条件的三位数，设百位为 $a$，十位为 $b$，个位为 $c$。

- $a$ 为 $1 \sim 9$ 之间的数字，$b$ 为 $0 \sim 9$ 之间的数字，$c$ 为 $0 \sim 9$ 之间的数字。
- $a \times 10 + b$ 为 $k$ 的倍数，$b \times 10 + c$ 为 $k$ 的倍数。
- $a \times 100 + b \times 10 + c$ 为 $k$ 的倍数。

你需要**由小到大**输出所有满足以上几个条件的三位数，每行输出一个。

如果没有三位数满足上述要求，输出一行 ```None!```。

inputFormat: 输入一行一个整数 $k$。

outputFormat:
**由小到大**输出所有满足条件的三位数，每行一个。

如果没有三位数满足上述要求，输出一行 ```None!```。

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

- 对于 $50\%$ 的数据，$1 \leq k \leq 10$；
- 对于 $100\%$ 的数据，$1 \leq k \leq 20$。


title: [yLCPC2024] G. 系ぎて

background:
> 与其说不甘心吧，这谱面到底是什么东西…
> ——ReMiRiA
> 虽然获得了冠军非常开心，但是这个谱面到底是什么？真的会收录吗？？
> ——yoshiki

description:
扶苏很喜欢拆分自然数。

对给定的正整数 $n$，若 $n = i \times j \times k$，其中 $i,j,k$ 是正整数，则称三元组 $(i,j,k)$ 是 $n$ 的一组优秀的拆分。

三元组 $(i,j,k)$ 是有序的。例如，对于 $2 = 1 \times 1 \times 2 = 1 \times 2 \times 1 = 2 \times 1 \times 1$，我们称 $(1,1,2)$、$(1,2,1)$、$(2,1,1)$ 是三组不同的优秀的拆分。

现在，扶苏想问你，对于 $n = 1,2,3\dots N$，$n$ 的所有的优秀的拆分之和是多少。

形式化的，记 $f(n)$ 表示 $n$ 的优秀的拆分数量，你需要求出 $\sum_{i = 1}^N f(i)$。

inputFormat: 输入只有一行一个整数，表示 $N$（$1 \leq N \leq 10^{10}$）。

outputFormat: 输出一行一个整数表示答案。因为答案可能过大，你只需要输出这个值除以 $2^{64}$ 的余数。


title: [语言月赛 202402] 小朋友的身高

background: 卷王十分喜欢和朋友们一起玩！

description:
卷王有 $n$ 个朋友，最初，第 $i$ 位朋友的身高为 $a_i$。

时光飞逝，一转眼就过去了 $m$ 年。在第 $i$ 年第 $j$ 位朋友的身高增长了 $b_{i,j}$。

卷王有 $q$ 次询问，每一次询问包含 $3$ 个数 $x,y,z$，表示询问**过了 $x$ 年后**第 $y$ 位朋友和第 $z$ 位朋友的**身高差**（即第 $y$ 位朋友 $x$ 年后的身高减第 $z$ 位朋友 $x$ 年后的身高）。特别的，若 $x=0$，表示询问最初时第 $y$ 位朋友和第 $z$ 位朋友的**身高差**。

inputFormat:
读入数据共 $m+q+2$ 行。

第一行三个正整数 $n,m,q$，含义见题意。
接下来一行 $n$ 个正整数 $a_i$，表示小朋友们最初的身高。
接下来 $m$ 行，每行 $n$ 个正整数，表示 $b_{i,j}$。
最后 $q$ 行，每行 $3$ 个正整数 $x,y,z$，表示询问过了 $x$ 年后第 $y$ 个小朋友和第 $z$ 个小朋友的**身高差**。

outputFormat: 输出共 $q$ 行。对于每组询问，输出对应的身高差。

hint:
### 样例 1 解释

$1$ 年后，第 $1$ 位朋友身高为 $3$，第 $3$ 位朋友身高为 $5$，身高差为 $3-5=-2$；\
$2$ 年后，第 $2$ 位朋友身高为 $7$，第 $3$ 位朋友身高为 $6$，身高差为 $7-6=1$；

### 数据规模与约定

- 对于 $20\%$ 的数据，满足所有 $b_{i,j}$ 都相等；
- 对于 $50\%$ 的数据，满足 $1\leq n,m,q\leq 300$，$1\leq a_i\leq 10^5$，$1\leq b_{i,j}\leq 10^5$；
- 对于 $100\%$ 的数据，满足 $1\leq n,m,q\leq 10^3$，$0\leq x\leq m$，$1\leq y,z\leq n$，$1\leq a_i\leq 10^9$，$1\leq b_{i,j}\leq 10^9$。


title: [DTCPC 2024] The last permutation

background:
**本题题目背景不均为虚构，不影射任何人**。

小 L 是小 L 初中时的白月光。

有一天，小 L 在朋友圈说要玩农，小 L 火速研究怎么下载王者。

第二天，小 L 在朋友圈说要玩吃鸡，小 L 火速研究怎么下载 pubg。

但小 L 很快就和小 L 分手了，小 L 最后的情思化作一个排列。遗憾的是，小 L 并不情愿告诉大家。

不过在你的不断追问下，小 L 还是同意回答几个关于排列的问题。

description:
现存在一个长度为 $n$ 的隐藏排列 $p$。你可以进行如下询问若干次：选择三元组 $(l,r,k)$，满足 $1\leq l\leq r\leq n$，$1\leq k\leq r - l + 1$，交互库会返回下标在 $[l,r]$ 内的第 $k$ 大值。

对于一次询问操作，其代价为 $\frac{1}{r-l+1}$，你需要在不超过 $11.8$ 的代价内得出排列。

交互库不自适应，也就是说，你所需得到的排列在交互开始前就已经确定。

inputFormat:
输入第一行是一个正整数 $t$ ($1 \le t \le 5$) 表示测试组数。

对于每组数据，输入一行 $n$ ($1 \le n \le 1000$) 表示排列 $p$ 的长度。

当你已经得到排列，你应当输出形如 `! p1 p2 ... pn` 表示你得出的排列。

本题使用 IO 交互模式。

### 交互格式
- `? l r k`，询问下标在 $[l,r]$ 内的第 $k$ 大值。

- `! p1 p2 p3 ... pn`，输出答案。

请注意：在每组数据中，请保证询问操作的代价总和不超过 $11.8$。

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

- 对于 C/C++：`fflush(stdout);`
- 对于 C++：`std::cout << std::flush;`
- 对于 Java：`System.out.flush();`
- 对于 Python：`stdout.flush();`
- 对于 Pascal：`flush(output);`

对于其他语言，请自行查阅对应语言的帮助文档。

outputFormat: 见「交互格式」。


title: [DTCPC 2024] 小方学乘法

background: 小方上数学课，开始学乘法，但是他在课上睡着了。

description:
他梦见了一个数学公式，只包含数字和乘号，梦境是迷糊的，所以他可能会把乘号看成字母 $x$。

他冥冥之中记得这个 $x$ 的值，并且他认为字母可以看成数字，因此他在将字母 $x$ 都替换为了数字的情况下算出了这个表达式的值。

然后他被教练抓到睡觉了。

在被 gank 之前，他想回忆起梦中算出的值。

但是小方太困了，所以他决定求出所有情况下的值，也就是将每个**乘号**都替换或者不替换为字母 $x$ 所代表的值后，对所有可能情况求和。

然而小方连 $x$ 都忘记了，只记得它在某个范围 $[L,R]$ 内，所以他要对每个 $x$ 求出上面那个和的和。

小方刚学乘法，算不清太大的数字，所以他想让你求出答案 $\bmod {10^9+7}$ 的结果。

**形式化题意**

给你一个只含有数字 $1 \sim 9$ 和 `?` 的字符串 $s$，保证没有两个相邻的 `?`，且字符串的第一个字符和最后一个字符都不是 `?`。

现在每个 `?` 可以换成 $x$ 或者 $\times$，其中 $x$ 是一个给定的字符串拼接变量。

比如 `12x45` 当 $x=33$ 时替换结果为 `123345`。

记 $x=k$ 时所有 `?` 替换方案下表达式的权值和为 $f(k)$。

求 $\sum_{i=L}^R{f(i)} \bmod {10^9 + 7}$。

inputFormat:
第一行一个长度为 $n$（$1 \le n \le 2000$） 字符串 $S$，表示算式。

第二行两个正整数 $L,R$（$1 \le L \le R < 10^{18}$）。

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


title: [DTCPC 2024] 小方的疑惑 10

background: 小方一直有很多疑惑。

description:
小 C 在几年前的生日那天收到了一个礼物：一个长度为 $n$ 的只包含 $\text{(}$ 和 $\text{)}$ 的字符串，其中恰好有 $k$ 个子串为合法的括号序列。

由于小方很疑惑这个礼物长什么样，所以你要构造一个这样的字符串，或者输出 $-1$ 表示无解。

合法的括号序列满足以下条件：

- $\text{()}$ 是合法的括号序列。
- 若 $\text{A}$ 和 $\text{B}$ 是合法的括号序列，则 $\text{(A)}$ 和 $\text{AB}$ 是合法的括号序列。
- 其它序列均不是合法的括号序列。

小方有很多疑惑，所以他会询问你 $T$ 次。

inputFormat:
第一行一个整数 $T$ 表示询问次数。

接下来 $T$ 行，每行两个整数 $n$ 和 $k$（$1\le n,k \le 10^5$，$\sum n\le 10^6$）。

**本题输入输出量较大，请使用较为快速的输入输出方式。**

outputFormat: 对于每次询问，如果有解，输出一行一个长度为 $n$ 的字符串，否则输出 $-1$。


title: [DTCPC 2024] 0=1=0

description:
给你一个只含 $0$ 和 $1$ 的字符串 $s$。

每次你可以选择 $i\in [1,n)$，并将 $s_i$ 和 $s_{i+1}$ 分别取反。

定义 $1$ 取反结果为 $0$，$0$ 取反结果为 $1$。

要求使得顺序对数量最大，即使得 $i\lt j$ 且 $s_i\lt s_j$ 的 $(i,j)$ 个数最大。

输出方案。

inputFormat: 一行一个字符串 $S$（$\lvert S\rvert\leq 2\times 10^5$）。

outputFormat:
第一行输出一个数字，表示最大的顺序对个数。

第二行输出一个数字 $x$，表示操作步数。

接下来输出一行 $x$ 个数字，第 $i$ 个数字 $a_i$ 表示第 $i$ 步操作的是 $s_{a_i}$ 和 $s_{a_i+1}$ 。

**你要保证操作步数不超过 $2\times 10^5$ 步，但不必最小化操作步数。**


title: [DTCPC 2024] mex,min,max

description:
给定序列 $\{a_n\}$ 和 $k$，求有多少子区间 $[l,r]$ 满足 $\operatorname{mex}\{a_l,a_{l+1},\dots,a_{r-1},a_r\}+\min\{a_l,a_{l+1},\dots,a_{r-1},a_r\}+k\geq \max\{a_l,a_{l+1},\dots,a_{r-1},a_r\}$。

$\operatorname{mex}$ 定义为集合内没有出现过的最小的**非负整数**。

inputFormat:
第一行两个整数 $n,k$（$1\leq n\leq 5\times 10^5,0\leq k\leq n$）。

第二行 $n$ 个非负整数，第 $i$ 个表示 $a_i$（$0\leq a_i\leq n$）。

outputFormat: 一行一个数，表示满足条件的子区间个数。

tags: 珂朵莉树,颜色段均摊,ODT


title: [DTCPC 2024] Ultra

background:
Tony2 喜欢玩某二字游戏，这一天他在小 C 面前展示他的 $\text{Ultra}$。

但是小 C 不会 $\text{Ultra}$，所以他跑去图图酱一去了。

~~然后图图失败了~~

于是小 C 趁 Tony2 不在的时候偷偷地把他的跳跃键和下冲键交换了（

description:
Tony2 的操作可以看作下冲和跳跃的组合。

称一个 $\text{Ultra}$ 为一段连续的操作，以下冲开头，然后跳跃和下冲交替，并以下冲结束。由于是 $\text{Ultra}$，所以至少要有一次跳跃。

小 C 每次可以将一个 $\text{Ultra}$ 变成 $\text{uLTRA}$，也就是将这个 $\text{Ultra}$ 的每个下冲变成跳跃，将每个跳跃变成下冲。

小 C 不喜欢 $\text{Ultra}$，所以想要使得下冲次数尽量少。

**形式化题意**

给你一个 $01$ 序列，你可以进行如下操作若干次（或零次）:

- 将序列中形如 $101\cdots01$ 的一个子串（即 $1(01)^k$，$k\ge 1$）替换成**等长**的 $010\cdots10$（即 $0(10)^k$）。

你要操作使得 $1$ 的个数尽可能少，输出最少的 $1$ 的个数。

inputFormat: 一行一个长度为 $n$（$n\le 10^6$） 的字符串表示这个 $01$ 序列。

outputFormat: 输出一个数表示最少的 $1$ 的个数。

hint: 样例 $1$ 解释：选中该串的前三个字符 $101$，对其操作后该串变为 $0100011$，仅包含 $3$ 个 $1$。容易证明这是最优的。


title: [DTCPC 2024] 人赢的跳棋

background:
小 C 是人赢。

每周三晚上，小 T 晚上在吃猪脚饭，小 C 晚上和妹子在食堂共进晚餐。

每周五晚上，小 T 启动废墟图书馆，小 C 在和妹子聊天。

今天小 T 在睡觉，而小 C 在和妹子玩人赢的跳棋。

description:
给一棵 $n$ 个点的树，边有边权，边权为三元组。第 $i$ 条边的三元组 $e$ 为 $(e_{i,1},e_{i,2},e_{i,3})$。

设函数 $\operatorname{win}(x,y)$：
- 若 $x_2<y_2$ 且 $x_3<y_3$ 则 $\operatorname{win}(x,y)=x_1$。
- 若 $x_2>y_2$ 且 $x_3>y_3$ 则  $\operatorname{win}(x,y)=y_1$
- 否则 $\operatorname{win}(x,y)=0$。

其中 $x=(x_1,x_2,x_3),y=(y_1,y_2,y_3)$。

显然 $\operatorname{win}$ 函数满足交换律。

设一个三元组序列 $\{a_n\}$ 的权值为 $\max_{i=1}^{n-1} \operatorname{win}(a_i,a_{i+1})$，特别的，$n=1$ 时权值为 $0$。

设一条路径的权值为经过的所有边的权值按顺序组成的序列的权值。

求树的所有无向路径的权值和。

inputFormat:
第一行一个正整数 $n$（$1 \le n\leq 3\times 10^5$） 表示树的节点数。

之后 $n-1$ 行每行四个整数表示 $u,v,e_{i,1},e_{i,2}$，其中有 $e_{i,3}=i$。

保证 $\{e_{i,1}\}$ 和 $\{e_{i,2}\}$ 是一个 $1\sim n-1$ 的**排列**。

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


title: [DTCPC 2024] 平方树

description:
给你一个森林，每条边有一个方向。

你可以进行两种操作：

- 新增一个点。

- 将两个点之间连一条有向边。

你要使得最后将所有有向边看成无向边后，图形成一棵树，且每个点的出度都是平方数。

给出一种新增点数最少的方案。

inputFormat:
第一行两个整数 $n,m$（$1\le m \lt n \le 10^5$）表示这个森林的点数和边数。

接下来 $m$ 行，每行两个数 $u,v$（$1\le u,v\le n$）表示一条 $u$ 连向 $v$ 的有向边。

保证将每条边看作无向边后，这张图是森林。

outputFormat:
第一行两个整数 $x,y$ 表示你的新增点数和连边数。

接下来 $y$ 行，每行两个数 $u,v$ 表示新增一条 $u$ 连向 $v$ 的有向边，你要保证 $1\le u,v\le n+x$。


title: [DTCPC 2024] 序列

description:
定义一个长度为 $n$ 的序列 $\{p_n\}$ 的权值 $f(\{p_n\})$ 为 $\max\limits_{i=1}^n\{p_i-\max\{p_{i-1},p_{i+1}\}\}$，特别的，定义 $p_0=p_{n+1}=-\inf$。

求 $\sum\limits_{l=1}^n \sum\limits_{r=l+1}^n f(\{a_l,a_{l+1},\dots,a_r\})$。

答案对 $2^{32}$ 取模。

inputFormat:
第一行一个正整数 $n$（$1 \le n \le 10^6$）。

第二行 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）。

outputFormat:
一行一个数表示答案。

答案对 $2^{32}$ 取模。


title: [DTCPC 2024] 小方和小立方

background: 小方不想变成小立方。

description: 给你一个小写字符组成的字符串，求有多少个区间 $[l,r]$，满足这个区间所表示的串是回文的，且每个字符的出现次数不超过 $2$。

inputFormat: 一行一个字符串 $S$（$\lvert S\rvert\leq 5\times 10^4$）。

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


title: [DTCPC 2024] 取模

description: 给定序列 $\{a_n\}$ 和 $[L,R]$，问有多少个 $k\in [L,R]$ 满足 $a_i\bmod k$ 互不相同。

inputFormat:
第一行三个正整数 $n,L,R$（$n\leq 5\times 10^4,1\leq L\leq R\leq 10^9$）。

第二行 $n$ 个正整数，表示 $\{a_n\}$（$0 < a_i\leq 4\times10^5$）。


title: [DTCPC 2024] 环

background: 环

description: 给定无重边无自环的有向图 $G$ 和序列 $\{a_n\}$，每次可以花费 $a_i+a_j$ 的代价加上一条 $i\to j$ 的边，试花费最小代价使得可以找到 $k\geq 2$ 个不同的点 $p_1,p_2,\dots,p_k$，满足 $\forall i\in [1,k]$，都有一条 $p_i\to p_{i\bmod k+1}$ 的边。

inputFormat:
第一行两个整数 $n,m$（$2\le n\le 5 \times 10^5$，$n-1 \le m \le 10^6$），表示图的点数和边数。

第二行输入 $n$ 个整数，表示序列 $\{a_n\}$（$1\le a_i\le 10^9$）。

接下来 $m$ 行，每行两个整数 $u,v$（$1\le u,v\le n$），表示存在一条有向边 $u\to v$。

outputFormat: 一行一个整数表示最小代价。


title: [DTCPC 2024] 戈布

description:
对于 $01$ 序列 $\{a_n\}$，找到最小的 $k$ 满足存在一组 $\{(l_k,r_k)\}$使得以下条件成立。

- $\forall i\in[1,n]$，$a_i=1$ 当且仅当 $\exist  j\in[1,k]$，$i\in[l_j,r_j]$。

可以证明满足条件的 $\{(l_k,r_k)\}$ 仅有一个。

一个 $01$ 序列 $\{a_n\}$ 是好的当且仅当 $\forall i\in[1,k)$，$r_i-l_i<r_{i+1}-l_{i+1}$。

简单来说，一个 $01$ 序列是好的当且仅当从左到右形成的极长 $1$ 段长度严格递增。

给定序列 $\{a_n\}$，你可以进行如下操作若干次（或不进行操作）：

- 选择 $i,j$$(i\ne j)$，交换 $a_i,a_j$。

试求最小的操作次数使得 $\{a_n\}$ 变成一个好的序列。

inputFormat: 一行一个长为 $n$（$n\leq 800$） 的 $01$ 序列 $\{a_n\}$。

outputFormat: 一行一个数字，表示答案。


title: [ICPC2016 WF] Oil

description:
A large part of the world economy depends on oil, which is why research into new methods for finding
and extracting oil is still active. Profits of oil companies depend in part on how efficiently they can
drill for oil. The International Crude Petroleum Consortium (ICPC) hopes that extensive computer
simulations will make it easier to determine how to drill oil wells in the best possible way.

Drilling oil wells optimally is getting harder each day – the newly discovered oil deposits often do
not form a single body, but are split into many parts. The ICPC is currently concerned with stratified deposits, as illustrated in Figure G.1.

To simplify its analysis, the ICPC considers only the 2-dimensional case, where oil deposits are modeled
as horizontal line segments parallel to the earth’s surface. The ICPC wants to know how to place a single
oil well to extract the maximum amount of oil. The oil well is drilled from the surface along a straight
line and can extract oil from all deposits that it intersects on its way down, even if the intersection is at
an endpoint of a deposit. One such well is shown as a dashed line in Figure G.1, hitting three deposits.
In this simple model the amount of oil contained in a deposit is equal to the width of the deposit. Can
you help the ICPC determine the maximum amount of oil that can be extracted by a single well?

inputFormat:
The first line of input contains a single integer n ($1 ≤ n ≤ 2 000$), which is the number of oil deposits.

This is followed by $n$ lines, each describing a single deposit. These lines contain three integers $x_0$,
$x_1$, and y giving the deposit’s position as the line segment with endpoints $(x_0, y)$ and $(x_1, y)$. These
numbers satisfy $|x_0|, |x_1| ≤ 10^6$
and $1 ≤ y ≤ 10^6$
. No two deposits will intersect, not even at a point.

outputFormat: Display the maximum amount of oil that can be extracted by a single oil well.

translation:
### 题目描述
世界经济的很大一部分依赖于石油，这就是为什么对发现和开采石油的新方法的研究仍然活跃。石油公司的利润在一定程度上取决于他们能够多么有效地钻探石油。国际原油石油联盟（ICPC）希望通过广泛的计算机模拟来更容易地确定如何以最佳方式钻探油井。

每天钻探油井变得越来越困难，因为新发现的油藏通常不是一个整体，而是分裂成许多部分。ICPC目前关注的是分层沉积物。

为了简化其分析，ICPC只考虑二维情况，其中油藏被建模为与地球表面平行的水平线段。ICPC想知道如何放置一个单独的油井以提取最大量的石油。油井沿着一条直线从地面钻井，并可以从其下降的路径上相交的所有沉积物中提取石油，即使相交点位于沉积物的端点处。图G.1中显示了一个这样的井，击中三个沉积物。在这个简单的模型中，一个沉积物中含有的石油量等于该沉积物的宽度。你能帮助ICPC确定通过一个单井可以提取的最大石油量吗？

### 输入格式
输入的第一行包含一个整数 $n (1\le n\le 2000)$，表示油田的数量。

接下来的 $n$ 行，每行描述一个沉积物。这些行包含三个整数 $x_0、x_1$ 和 $y$，表示沉积物的位置为线段，其端点为 $(x_0,y)$ 和 $(x_1,y)$。这些数字满足 $|x_0|,|x_1|≤10^6$。没有两个沉积物会相交，甚至不会在一点相交。

### 输出格式
输出一个整数，表示单个油井可以提取的最大石油量。


title: 「Daily OI Round 4」Snow

description:
下雪了，小 Y 堆了 $n$ 个雪柱排成一排，调皮的小 X 打算推倒这 $n$ 个雪柱，他想在最少的时间内推倒所有雪柱，于是他请你来为他出谋划策。

小 Y 堆的每个雪柱高 $a_i$ 单位，推倒一个雪柱的时间为该雪柱的高度。小 X 只能从这一排雪柱的两端推雪柱 \*，次数不限，小 X 移动的时间可以忽略不计。这样就可以使一个雪柱倒向其他雪柱，从而击倒另一个雪柱（击倒的时间忽略不计），然后发生连锁反应，更加节省时间 \*\*。

设初始的势能为当前手动推倒的雪柱 $k$ 的高度 $p=a_k$，则此轮连锁反应中第 $i$ 个雪柱倒向第 $j$ 个雪柱时：

- 若 $p\ge a_j$，则使第 $j$ 个雪柱也被击倒，并令 $p \gets a_j$。
- 若 $p< a_j$，则第 $j$ 个雪柱的高度减少（不被击倒），终止整个连锁反应，令 $a_j \gets a_j-p$。

请你求出推倒所有雪柱的最短时间。

\*：每一次要么从左边推最左边的雪柱，要么从右边推最右边的雪柱。

\*\*：雪柱的倒塌方向取决于推雪柱的方向，如果从左边推，雪柱就会向右依次倒塌（第 $i$ 个雪柱倒塌向第 $i+1$ 个雪柱），反之同理。

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

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

对于每组数据：

第一行一个整数 $n$，表示雪柱的数量。

第二行 $n$ 个整数，分别表示每个雪柱的高度。

outputFormat: 对于每组数据：输出一行一个整数，表示推倒所有雪柱的最短时间。


title: 【MX-X5-T7】「GFOI Round 1」Der Richter

background: > [Der Richter - Ωμεγα](https://www.bilibili.com/video/BV11SpberEjC/)

description:
我们首先给出关于本题的一些定义。

定义一个 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$ 是**好的**，当且仅当 $\exists k \in [1, n - 1], \max\limits_{i = 1}^k p_i = k$。

定义一个序列 $x_1, x_2, \ldots, x_k$ 是一个排列 $p_1, p_2, \ldots, p_n$ 的**交换方案**，当且仅当：

- $\forall 1 \le i \le k$，$1 \le x_i \le n - 1$ 且 $x_i$ 是整数；
- 对所有 $i = 1 \sim k$ **依次**执行交换 $p$ 中 $x_i$ 和 $x_i + 1$ 位置上的数的操作之后，$p$ 是**好的**。

特别地，序列 $x$ 可以为空，代表不进行任何交换操作。

定义一个序列 $x_1, x_2, \ldots, x_k$ 是一个排列 $p_1, p_2, \ldots, p_n$ 的**关键交换方案**，当且仅当：

- $x$ 是 $p$ 的一个**交换方案**；
- $x$ 是 $p$ 的所有**交换方案**中长度最小的。

定义 $f(p)$ 为排列 $p$ 的不同的**关键交换方案**的个数。

定义一个排列 $q$ 是另一个排列 $p$ 的一个**终态**，当且仅当：

- $p$ 的长度与 $q$ 相等；
- $q$ 是**好的**；
- 存在一个 $p$ 的**关键交换方案** $x_1, x_2, \ldots, x_k$，使得对所有 $i = 1 \sim k$ **依次**执行交换 $p$ 中 $x_i$ 和 $x_i + 1$ 位置上的数的操作之后，$p$ 与 $q$ 相同（即 $\forall 1 \le i \le |p|, p_i = q_i$）。

定义一个排列 $p$ 是**极好的**，当且仅当只存在**一个**排列 $q$，使得 $q$ 是 $p$ 的**终态**。

给定一个**质数** $P$ 和 $q$ 次询问，每次询问给定两个整数 $n, m$，你需要构造任意一个**极好的**长度为 $n$ 且 $f(p) \equiv m \pmod P$ 的 $1 \sim n$ 的排列 $p$，或报告无解。

本题将使用**自定义校验器**检查你构造的排列是否正确，即若有解输出任意一个满足要求的排列都会被认为通过。

inputFormat:
第一行输入两个正整数 $q, P$，表示询问次数和模数。

接下来 $q$ 行，每行包含两个整数 $n, m$。

outputFormat:
对于每次询问：

- 若无解输出一行一个整数 $-1$；
- 否则输出一行 $n$ 个整数，表示任意一个符合要求的 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$。

本题将使用**自定义校验器**检查你构造的排列是否正确，即若有解输出任意一个满足要求的排列都会被认为通过。


title: [语言月赛 202402] 数字串

description:
bj12z_jiasiyuan 有 $n + 1$ 个长度为无穷大的序列，其中这些序列有如下的规律：

- 第 $1$ 个序列为 $\texttt{11111111111111\dots}$，即开头为 $1$，相邻的 $1$ 间隔的距离为 $0$。
- 第 $2$ 个序列为 $\texttt{10101010101010\dots}$，即开头为 $1$，相邻的 $1$ 间隔的距离为 $1$。
- 第 $3$ 个序列为 $\texttt{10010010010010\dots}$，即开头为 $1$，相邻的 $1$ 间隔的距离为 $2$。
- $\cdots$
- 第 $n + 1$ 个序列开头为 $1$，相邻的 $1$ 间隔的距离为 $n$。

同时，bj12z_jiasiyuan 给予你一个长度为 $m$ 的 $01$ 数字串 $s$，请你判断这个数字串是否可能是从以上 $n + 1$ 个序列中的某一个序列中截取出来的。

bj12z_jiasiyuan 会询问你很多次，每一次都会给予你一组新的 $n, m, s$。请你帮助回答这些询问。

inputFormat:
**本题单个测试点内有多组测试数据。**

第一行一个整数 $t$，代表测试数据组数。
第 $2 \sim t + 1$ 行，每行两个整数 $n, m$ 和一个长度为 $m$ 的 $01$ 数字串 $s$。

outputFormat: 输出 $t$ 行，每行输出一个字符串 ```Yes``` 或 ```No```，表示每次询问的答案。如果有可能，输出 ```Yes```，否则输出 ```No```。


title: 『STA - R5』ReLyna

description:
你手中有一个数字 $x$。走到位置 $i$ 时你可以将手中的数字变为 $x+a_i$ 或 $x\times b_i$。

有 $m$ 次操作。

- `1 x y z`，执行 $a_x\gets y$，$b_x\gets z$。

- `2 l r`，查询若你从 $[l,r]$ 的所有子区间中等概率选择一个子区间 $[l',r']$，则你从 $l'$ 走到 $r'$ 后手中的数的最大值的期望是多少？答案对 $10^9+7$ 取模。每次行动开始前你手中的数字都会归零。

如果你不知道有理数如何取模，可以参考 [P2613 有理数取余](https://www.luogu.com.cn/problem/P2613)。

可参考样例解释理解题意。

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

第二行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。

第三行 $n$ 个整数，第 $i$ 个整数代表 $b_i$。

后 $m$ 行每行描述一次操作，格式见题目描述。

outputFormat: 对于每个询问，输出对应的期望。答案对 $10^9+7$ 取模。


title: 【MX-X6-T4】夢重力

background:
> _空を仰げば$\\$
青さが僕を$\\$
飲み込んでしまう気がしてて$\\$
無重力なら楽だろうか$\\$
宇宙まで行けたら_
>
> _—— [夢重力 - Nanatsukaze](https://music.163.com/#/song?id=2155399298)_

在天体的随机运转中，如何找到一个没有重力的点呢？

description:
给定一个 $n\times n$ 的网格，其中有 $n$ 个关键点，保证每行每列各有一个关键点。保证 $n$ 是偶数。

我们定义网格中的一个无重力区域为网格的连续的 $\dfrac{n}{2}$ 行和连续的 $\dfrac{n}{2}$ 列构成的大小为 $\dfrac{n}{2}\times \dfrac{n}{2}$ 的子正方形，使得其中不包含任意关键点。

定义 $f(i,j)$ 为交换网格的第 $i$ 行和第 $j$ 行后，不同的无重力区域个数。请对于所有可能的交换求 $f(i,j)$ 的和，即你需要求：

$$\sum_{1\leq i<j\leq n}f(i,j)$$

注意求 $f$ 并不会真正在网格中执行交换，整个过程中不会对网格进行任何修改。

inputFormat:
第一行一个整数表示 $n$。保证 $n$ 是偶数。

接下来一行 $n$ 个空格分隔的整数 $p_1,p_2,\dots,p_n$，表示 $n$ 个关键点的位置分别是 $(1,p_1),(2,p_2),\dots,(n,p_n)$。保证 $p$ 是一个排列。

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

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

上图中，左上角对应原网格。灰色的部分表示关键点。

下面的 $6$ 个网格分别对应所有可能的交换产生的网格（依次为交换 $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$），并使用红色和蓝色标出存在的无重力区域（紫色的位置表示两个无重力区域的交）。不难看出答案为 $2+2+0+0+2+2=8$。

**【数据范围】**

对于所有数据，保证 $2\leq n\leq 2\times 10^5$ 且 $n$ 是偶数，保证 $p$ 是一个排列。

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

- Subtask 1（12 pts）：$n\leq 10$；
- Subtask 2（19 pts）：$n\leq 200$；
- Subtask 3（34 pts）：$n\leq 2000$；
- Subtask 4（35 pts）：无特殊限制。


title: 「LAOI-4」石头

description:
有一个长度为 $n$ 的排列 $a$，初始可以任意染白一个数，然后接下来每一步可以染白最小的一个与已经被染白的数相邻的数，显然 $n$ 步之后所有数都会被染白。

现在我们称满足以下要求的数对 $(i,j)$ 是好的数对：

- $1\leq i\leq j\leq n$。
- 存在一个 $k$，满足若从 $a_i$ 开始染白，$a_j$ 会在第 $k$ 步被染白；若从 $a_j$ 开始染白，$a_i$ 也会在第 $k$ 步被染白。

求好的数对的数量。

outputFormat: 共一行一个正整数，表示好的数对的数量。


title: [USACO24FEB] Palindrome Game B

description:
Bessie 和 Elsie 正在使用一堆初始时共 $S$ 个石子（$1\le S<10^{10^5}$）进行一个游戏。两头奶牛依次行动，Bessie 先行动。当轮到一头奶牛行动时，她必须从堆中取走 $x$ 个石子，其中 $x$ 是该奶牛选定的任意正整数回文数。如果当一头奶牛的回合开始时石子堆是空的，那么这头奶牛就输了。

**定义**：一个正整数如果从前向后和从后向前读相同，则该数为回文数；回文数的例子有 $1$，$121$ 和 $9009$。数不允许有前导零；例如，$990$ **不是**回文数。

有 $T$（$1\le T\le 10$）个独立的测试用例。对于每一个测试用例，输出如果两头奶牛都采取最优策略，谁会赢得游戏。

inputFormat:
输入的第一行包含 $T$，为测试用例的数量。以下 $T$ 行为测试用例，每个测试用例一行。

每个测试用例均由一个整数 $S$ 指定。

outputFormat: 对于每一个测试用例输出一行，如果 Bessie 在最优策略下可以从一堆 $S$ 个石子的石子堆开始赢得游戏，则输出 `B`，否则输出 `E`。

hint:
### 样例解释

对于第一个测试用例，Bessie 可以在第一次行动中取走所有石子，因为 $8$ 是回文数，使她获胜。

对于第二个测试用例，$10$ 不是回文数，因此 Bessie 无法在第一次行动中取走所有石子。无论 Bessie 第一回合取走多少石子，Elsie 总能在第二回合取走所有余下的石子，使她获胜。

对于第三个测试用例，可以证明在最优策略下 Bessie 可以获胜。

### 测试点性质

- 测试点 $2-4$：$S<100$。
- 测试点 $5-7$：$S<10^6$。
- 测试点 $8-10$：$S<10^9$。
- 测试点 $11-13$：没有额外限制。


title: [USACO24FEB] Milk Exchange B

description:
Farmer John 的 $N$（$1\le N\le 2\cdot 10^5$）头奶牛排成一圈，使得对于 $1,2,\ldots,N−1$ 中的每个 $i$，奶牛 $i$ 右边的奶牛是奶牛 $i+1$，而奶牛 $N$ 右边的奶牛是奶牛 $1$。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\le a_i\le 10^9$）升的桶。所有桶初始时都是满的。

每一分钟，奶牛都会根据一个字符串 $s_1s_2\ldots s_N$
传递牛奶，该字符串仅由字符 `L` 和 `R` 组成。当第 $i$ 头奶牛至少有 $1$ 升牛奶时，如果 $s_i=\texttt{L}$，她会将 $1$ 升牛奶传递给她左边的奶牛，如果 $s_i=\texttt R$ 则传递给右边的奶牛。所有交换同时发生（即，如果一头奶牛的桶是满的，送出一升牛奶，但也收到一升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。

FJ 想要知道：经过 $M$ 分钟（$1\le M\le 10^9$）后，所有奶牛总共还余下多少牛奶？

inputFormat:
输入的第一行包含 $N$ 和 $M$。

第二行包含一个字符串 $s_1s_2\ldots s_N$，仅由字符 `L` 或 `R` 组成，表示每头奶牛传递牛奶的方向。

第三行包含整数 $a_1,a_2,\ldots,a_N$，为每个桶的容量。

outputFormat:
输出一个整数，为 $M$ 分钟后所有奶牛总共余下的牛奶量。

**注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 `long long`）。**

hint:
### 样例解释 1

奶牛 $2$ 和 $3$ 互相传递一升牛奶，因此她们的牛奶得以保留。当奶牛 $1$ 将牛奶传递给奶牛 $2$ 时，奶牛 $2$ 的桶会溢出，从而一分钟后损失了一升牛奶。

### 样例解释 2

 每头奶牛都将一升牛奶传递给左边的奶牛，并从右边的奶牛那里获得一升牛奶，因此无论经过多长时间所有牛奶都会被保留下来。

### 样例解释 3

初始时，共有 $51$ 升牛奶。$5$ 分钟后，奶牛 $3$，$6$ 和 $7$ 将分别损失 $5$，$3$ 和 $5$ 升牛奶。因此，总共还剩下 $38$ 升牛奶。

### 测试点性质

- 测试点 $4-8$：$N,M\le 1000$。
- 测试点 $9-16$：没有额外限制。


title: [USACO24FEB] Maximizing Productivity B

description:
Farmer John 有 $N$（$1\le N\le 2\cdot 10^5$）个农场，编号为 $1$ 到 $N$。已知 FJ 会在时刻 $c_i$ 关闭农场 $i$。Bessie 在时刻 $S$ 起床，她希望在农场关闭前访问尽可能多的农场，从而最大限度地提高她这一天的生产力。她计划在时刻 $t_i+S$ 访问农场 $i$。Bessie 必须于严格早于 Farmer John 关闭农场的时刻抵达农场才能成功进行访问。

Bessie 有 $Q$（$1\le Q\le 2\cdot 10^5$）个询问。对于每个询问，她会给你两个整数 $S$ 和 $V$。对于每个询问，输出当 Bessie 在时刻 $S$ 起床是否可以访问至少 $V$ 个农场。

inputFormat:
输入的第一行包含 $N$ 和 $Q$。

第二行包含 $c_1,c_2,c_3\ldots c_N$（$1\le c_i\le 10^6$）。

第三行包含 $t_1,t_2,t_3\ldots t_N$（$1\le t_i\le 10^6$）。

以下 $Q$ 行，每行包含两个整数 $V$（$1\le V\le N$）和 $S$（$1\le S\le 10^6$）。

outputFormat: 对 $Q$ 个询问的每一个输出一行，输出 `YES`（是）或 `NO`（否）。

hint:
### 样例解释

对于第一个询问，Bessie 将在时间 $t=[9,7,8,8,13]$ 访问农场， 因此她在 FJ 关闭农场之前能准时访问到的只有农场 $4$。

对于第二个询问，Bessie 将无法准时访问到任何农场。

对于第三个询问，Bessie 将可以准时访问到农场 $3,4,5$。

对于第四个和第五个询问，Bessie 将能够准时访问除第一个农场之外的所有农场。

### 测试点性质

- 测试点 $2-4$：$N,Q\le 10^3$。
- 测试点 $5-9$：$c_i,t_i\le 20$。
- 测试点 $10-17$：没有额外限制。


title: [USACO24FEB] Target Practice II S

background:
**注意：本题的时间限制为 2.5 秒，通常限制的 1.25 倍。**

**注意：这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 `long long`）。**

description:
巴黎哞运会即将来临，Farmer John 正在对他的奶牛队进行射箭训练！他在二维坐标平面上设置了以下练习。

有 $N$（$1\le N\le 4\cdot 10^4$）个四边与坐标轴平行的矩形箭靶和 $4N$ 头奶牛。每头牛都必须被分配一个不同的箭靶顶点。对于 $1\le i\le N$，在时刻 $i$：

1. 箭靶 $i$ 出现。
2. 分配其顶点的 $4$ 头奶牛向它们射箭。
3. 如果奶牛的箭在击中所分配的顶点之前穿过箭靶内部，或未命中，则奶牛们的练习失败。
4. 箭靶消失，为下一个箭靶腾出空间。

每头牛都位于 $y$ 轴（$x=0$）上，每个箭靶都是一个矩形，其中箭靶 $i$ 的左下顶点坐标为 $(X_1,y^{(i)}_1)$，右上顶点坐标为 $(x^{(i)}_2,y^{(i)}_2)$。所有坐标满足 $1\le X_1<x^{(i)}_2\le 10^9$ 以及 $1\le y^{(i)}_1<y^{(i)}_2\le 10^9$（注意：$X_1$ 对于每个箭靶都是相同的）。

此外，每头奶牛都有一个正在钻研的「瞄准」角度。因此她们在射箭时会转向特定的角度。考虑到她们的箭从她们的位置沿直线射向指定的顶点，奶牛 $i$ 的箭的轨迹可以用轨迹的斜率 $s_i$（$0<|s_i|<10^9$）来表示。

为了能够仔细检查奶牛们的技术，Farmer John 希望尽量缩短最远的奶牛之间的距离。如果 Farmer John 以最佳方式给每头奶牛分配箭靶顶点并将她们放置在 $y$ 轴上，你能否帮助他求出最远奶牛之间的最小距离是多少，或者奶牛是否总是会练习失败？

每个测试点包含 $T$（$1\le T\le 10$）个独立的测试用例。输入保证所有测试用例的 $N$ 之和不超过 $4\cdot 10^4$。

inputFormat:
输入的第一行包含 $T$（$1\le T\le 10$），为测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含两个整数 $N$ 和 $X_1$，分别为箭靶的数量以及所有箭靶的左端的 $x$ 坐标。

以下 $N$ 行，第 $i$ 行包含三个整数 $y^{(i)}_1$，$y^{(i)}_2$ 和 $x^{(i)}_2$，分别为第 $i$ 个箭靶的下端 $y$ 坐标，上端 $y$ 坐标和右端 $x$ 坐标。

最后一行包含 $4N$ 个整数 $s_1,s_2,\ldots,s_{4N}$，其中 $s_i$ 表示奶牛 $i$ 的射箭轨迹的斜率。

outputFormat: 输出最远奶牛之间的最小可能距离，或如果奶牛总是练习失败时输出 $−1$。

hint:
### 样例解释

对于测试用例 $1$，一个最佳分配方案是分别为奶牛 $1-8$ 分配以下目标顶点：

$$(6,1),(6,3),(3,4),(3,6),(1,4),(1,3),(1,6),(1,1)$$

这得出了奶牛 $1-8$ 的 $y$ 坐标如下：

$$−5,9,−2,12,1,6,2,5$$

这给出了最小距离 $12−(−5)=17$。

第二个测试用例的答案是不可能的原因之一是，如果箭不穿过箭靶 $1$ 的内部，不可能射中 $(6,3)$ 处的顶点（箭靶 $1$ 的右上顶点）。

### 测试点性质

- 测试点 $2$：对于所有的 $1\le i\le 4N$，$|S_i|$ 均相同。
- 测试点 $3-9$：所有测试用例的 $N$ 之和不超过 $1000$。
- 测试点 $10-15$：没有额外限制。


title: [USACO24FEB] Minimum Sum of Maximums P

description:
Bessie 有一行 $N$（$2\le N\le 300$）块瓷砖，依次具有丑陋度 $a_1,a_2,\ldots,a_N$（$1\le a_i\le 10^6$）。其中 $K$（$0\le K\le \min(N,6)$）块瓷砖卡住了；具体地，索引为 $x_1,\ldots,x_K$（$1\le x_1<x_2<\cdots<x_K\le N$）的瓷砖。

Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum\limits^{N−1}_{i=1}\max(a_i,a_{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。

求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。

inputFormat:
输入的第一行包含 $N$ 和 $K$。

第二行包含 $a_1,\ldots,a_N$。

第三行包含 $K$ 个索引 $x_1,\ldots,x_K$。

outputFormat: 输出最小可能的总丑陋度。

hint:
### 样例解释 1

Bessie 可以交换第二块和第三块瓷砖，使得 $a=[1,10,100]$，达到总丑陋度 $\max(1,10)+\max(10,100)=110$。或者，她也可以交换第一块和第二块瓷砖，使得 $a=[100,1,10]$，同样达到总丑陋度 $\max(100,1)+\max(1,10)=110$。

### 样例解释 2

瓷砖的初始总丑陋度为 $\max(1,100)+\max(100,10)=200$。Bessie 只允许交换第一块和第三块瓷砖，这并不能使她能够减少总丑陋度。

### 测试点性质

- 测试点 $5$：$K=0$。
- 测试点 $6-7$：$K=1$。
- 测试点 $8-12$：$N\le 50$。
- 测试点 $13-24$：没有额外限制。


title: [USACO24FEB] Moorbles S

description:
Bessie 和 Elsie 正在玩弹珠游戏。游戏的玩法如下：Bessie 和 Elsie 开始时各有一定数量的弹珠。Bessie 取出 $A$ 个弹珠放在蹄子下，Elsie 猜测 $A$ 是偶数还是奇数。如果 Elsie 猜对了，她从 Bessie 那里赢得 $A$ 个弹珠，如果她猜错了，她输给 Bessie $A$ 个弹珠（如果 Elsie 有少于 $A$ 个弹珠，她就会输掉所有弹珠）。一名玩家失去所有弹珠时即失败。

游戏进行了一定回合后，Elsie 拥有 $N$（$1\le N\le 10^9$）个弹珠。她感觉获胜很难，但她只是想不要输。在与 Bessie 玩得足够久之后，Elsie 对 Bessie 的习惯有了很好的了解，她发现在回合 $i$，Bessie 只可能会取出 $K$（$1\le K\le 4$）种不同数量的弹珠。距离 Bessie 感到无聊退出游戏只有 $M$（$1\le M\le 3\cdot 10^5$）个回合了。你能求出一个字典序最小的行动序列，使得无论 Bessie 如何选择，Elsie 都不会输吗？

inputFormat:
输入的第一行包含一个整数 $T$（$1\le T\le 10$），为测试用例的数量。每个测试用例的描述如下：

- 第一行包含三个整数 $N$，$M$ 和 $K$，分别表示 Elsie 拥有的弹珠数量，回合数及 Bessie 可能进行的选择数。
- 以下 $M$ 行，第 $i$ 行包含 $K$ 个不同的空格分隔的整数 $a_{i,1}a_{i,2}\ldots a_{i,K}$（$1\le a_{i,j}\le10^3$），表示 Bessie 在回合 $i$ 可能取出的弹珠数量。

输入保证所有测试用例的 $M$ 之和不超过 $3\cdot 10^5$。

outputFormat:
对于每一个测试用例，输出 Elsie 保证不输的字典序最小的行动序列，或者如果她会输则输出 $−1$。行动序列输出在一行中，包含 $M$ 个空格分隔的单词，每个单词为 `Even`（偶）或 `Odd`（奇）。

注意：`Even` 的字典序小于 `Odd`。

hint:
### 样例解释 1

在第一个测试用例中，唯一字典序更小的行动序列是 `Even Even Even`，但 Bessie 可以使 Elsie 输，通过先出 $5$，将 Elsie 的弹珠数量从 $10$ 减少到 $5$，然后再出 $3$，将 Elsie 的弹珠数量从 $5$ 减少到 $2$，然后出 $3$，这会输光她所有的弹珠。

如果 Elsie 采用正确的行动序列 `Even Even Odd`，那么如果 Bessie 以同样的方式进行游戏，最后当她出 $3$ 时，Elsie 将获得那 $3$ 个弹珠，将她的弹珠数量增加到 $5$。可以进一步证明，只要 Elsie 操作是 `Even Even Odd`，Bessie 无法以其他的方式赢走 Elsie 的所有弹珠。

在第二个测试用例中，可以证明，对于 Elsie 可以选择的任何行动顺序，Bessie 都存在一种方式可以赢走 Elsie 的所有弹珠。

### 测试点性质

- 测试点 $3$：$M\le 16$。
- 测试点 $4-6$：$M\le 1000$。
- 测试点 $7-12$：没有额外限制。


title: String Minimization

description:
你有四个长 $n$ 的字符串 $a,b,c,d$。你可以执行任意多次如下操作：

- 选择一个 $i$，交换 $a_i,c_i$，然后交换 $b_i,d_i$。

求在 $a$ 的字典序尽量小的前提下，$b$ 字典序最小是什么。

---

如果你不知道什么是字典序，看这里：

对于两个字符串 $p,q$，称 $p$ 的字典序小于 $q$（记为 $p<q$），当且仅当存在**自然数** $k$ 使 $p,q$ 的前 $k$ 个字符相同且 $p_{k+1}$ 的 ASCII 码小于 $q_{k+1}$ 的 ASCII 码。

例如：
- $\texttt{abc}<\texttt{baa}$（当 $k=0$）
- $\texttt{bae}<\texttt{bbb}$（当 $k=1$）

inputFormat:
输入的第一行有一个正整数 $n$，表示字符串 $a,b,c,d$ 长度。

之后四行，每行一个字符串，分别表示 $a,b,c,d$。

outputFormat: 输出一行一个字符串，表示题目要求的字符串 $b$。

hint:
【样例解释】

选择 $i$ 为 $1,3,4$ 可以让 $a$ 取到最小的字典序 $\texttt{weablake}$，此时字符串 $b$ 也得到满足题意最小的字典序 $\texttt{auazyqaq}$。

事实上如果 $i=1$ 时不操作 $a$ 的字典序也是最小的，但是此时字符串 $b$ 就是 $\texttt{yuazyqaq}$，不够小。

【数据范围】

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

|测试点编号|$n\le$|特殊性质|
|:-:|:-:|:-:|
|$1\sim 2$|$15$||
|$3$|$10^5$|$a_i>c_i$|
|$4\sim 5$|$10^5$|$a_i\ne c_i$|
|$6\sim 7$|$10^5$|$b_i\ge d_i$|
|$8\sim 10$|$10^5$||

对于全体数据，保证 $1\le n\le 10^5$，字符串所有字符都是小写字母。


title: 【模板】Pfaffian

background:
称一个长度为 $2n$ 的排列 $\pi$ 是完美匹配，当且仅当其满足
- $\forall 1\le i\le n,\pi_{2i-1}<\pi_{2i}$
- $\forall 1\le i< n,\pi_{2i-1}<\pi_{2i+1}$

记 $\textup{inv }\pi$ 表示 $\pi$ 的逆序对数，$\textup{sgn }\pi=(-1)^{\textup{inv }\pi}$，$\mathfrak{M}_{2n}$ 表示全体长度为 $2n$ 的完美匹配构成的集合。

令 $\mathbf{A}=(a_{i,j})_{1\le i<j\le 2n}$ 是一个反对称矩阵，定义 $\mathbf{A}$ 的 $\text{Pfaffian}$ 为
$$\textup{Pf}(\mathbf{A})=\sum\limits_{\pi\in\mathfrak{M}_{2n}}(\textup{sgn }\pi)\prod\limits_{i=1}^{n}a_{\pi(2i-1),\pi(2i)}$$

description: 给定偶数 $n$ 与反对称矩阵 $\mathbf{A}=(a_{i,j})_{1\le i<j\le n}$，求 $\textup{Pf}(\mathbf{A})$ 对 $10^9+7$ 取模的结果。

inputFormat:
第一行一个正整数 $n$，保证 $n$ 是偶数。

接下来 $n-1$ 行，第 $i$ 行有 $n-i$ 个非负整数，其中第 $j$ 个整数表示 $a_{i,i+j}$。

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


title: 一首诗

background: 题目描述最后有形式化题意。

description:
文学大师 ZHY 创作了一首诗。

这首诗由 $n$ 个单词组成，为了方便表述，ZHY 将这首诗记录为一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。创作完后，ZHY 立刻将自己的作品分享给了 YHZ。YHZ 在感受到了诗歌之美后，希望借此提高一下自己的文学素养，于是准备对这首诗中的诗句进行摘抄。

YHZ 认为一个“诗句”，应该是 $a_1,a_2,\dots,a_n$ 的一个**连续**子序列，诗句的长度即为子序列的长度。当然，他不会摘抄所有的诗句，而是只选择“优美的诗句”进行摘抄。由于不懂文法，YHZ 简单地认为一个诗句是“优美的”，当且仅当这个诗句中不存在两个**相邻**的重复单词。形式化的说，一个连续子序列 $a_l,a_{l+1},\dots,a_r$（$l\leq r$）组成的诗句是“优美的”，当且仅当对于所有的 $l\leq i<r$，有 $a_i\neq a_{i+1}$。

YHZ 发现文学大师 ZHY 写的诗里优美的诗句太多了，所以他需要进行归类。不过还是由于他不懂文法，他希望直接按照句子的长度归类。记 $b_i$ 为长度为 $i$ 的优美的诗句的个数，YHZ 希望知道 $b_1,b_2,\dots,b_n$。但即使是所有的 $b$ 数量也太多了，所以他只需要知道 $b_1\oplus b_2\oplus\dots\oplus b_n$。

还没等 YHZ 摘抄结束，文学大师 ZHY 告诉 YHZ 他要进行 $Q$ 次润色。具体地，每次润色，ZHY 会选择一个诗句 $[l_i,r_i]$ 和一个整数 $x_i$，并对所有的 $l_i\leq j\leq r_i$，将单词 $a_j$ 修改为 $a_j+x_i$。好学的 YHZ 希望对每次润色后的诗歌进行摘抄，即对于每次修改后的 $a_1,a_2\dots,a_n$，知道 $b_1\oplus b_2\oplus\dots\oplus b_n$。

不过文学大师 ZHY 太卷了，他进行的润色次数太多了，YHZ 还是承受不了这么大的工作量，所以他希望你帮帮他。

**形式化题面：**

给定一个序列 $a_{1\sim n}$，定义 $b_i$ 表示 $a$ 中有多少个长度为 $i$ 的区间使得任意两个相邻的数都不同。有 $q$ 次操作，每次操作给定 $l,r,x$，表示将 $a_{l\sim r}$ 都加上 $x$。请在第一次操作之前和每次操作之后求出 $b_1\oplus b_2\oplus \cdots \oplus b_n$。其中 $\oplus$ 表示按位异或。

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

第二行 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$。

接下来 $q$ 行，每行三个整数 $l_{i},r_{i},x_{i}$，表示一次操作。

outputFormat: 输出 $q+1$ 行，表示第一次操作前和每次操作后的答案。


title: [yLCPC2024] E. Latent Kindom

background:
扶苏和 10circle 老师正在拼机游玩最新最热歌曲 Latent Kindom（LK）！

LK 这首歌共有 $n$ 个难度的谱面，第 $i$ 个难度的谱面有 $l_i$ 个音符，分别是 $a_{i, 1}, a_{i, 2}, \dots a_{i, l_i}$，构成了一个序列。

扶苏想知道，如果她开难度为 $i$ 的谱面，10circle 老师开难度为 $j$ 的谱面，那么两个谱面的音符序列合并起来的中位数是多少。

description:
给定 $n$ 个序列 $a_1, a_2, \dots a_n$。你要回答 $q$ 次询问，每次询问会给出 $i, j$，你要求出序列 $a_i$ 和 $a_j$ 拼接后的中位数是多少。

拼接两个序列 $x, y$ 指的是把 $y$ 序列中的数依次写在 $x$ 序列后面。如果得到的序列长度为 $t$，中位数指的是序列中第 $\left\lceil\frac t 2 \right\rceil$ 小的数字。其中 $\left\lceil x \right\rceil$ 表示不小于 $x$ 的最小整数。

需要注意的是，本题的询问是独立的。也就是说，虽然你要回答假设 $a_i$ 和 $a_j$ 拼接后的中位数，但是不会真的进行对数列拼接的操作。

inputFormat:
**本题单个测试点内有多组测试数据**。输入的第一行是一个正整数 $T$，表示数据组数。对每组数据：

第一行是两个整数 $n,q$（$2 \leq n, q \leq 10^6$），表示序列的个数和询问的次数。
接下来 $n$ 行，每行表示一个序列。第 $i$ 行首先有一个整数 $l_i$（$1 \leq l_i \leq 10^6$），表示序列 $a_i$ 的长度。接下来 $l_i$ 个整数，表示序列 $a_i$。保证序列里的数都是不大于 $10^{18}$ 的正整数。
接下来 $q$ 行，每行两个整数 $i,j$（$1 \leq i,j \leq n$，$i \neq j$）表示一组询问。

数据保证单个测试点内的 $n,q,l_i$ 之和均不超过 $10^6$。

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

hint:
#### 提示

请注意大量的数据读入输出对程序效率造成的影响，使用合适的读入输出方式，不要频繁刷新输出缓冲区，避免超时。


title: [语言月赛 202403] 2014

background: 迷茫的 ScaredQiu 总是会想起 2014 年，如果你问他现在的年份，他可能也会告诉你是 2014 年。

description:
定义 2014 串为一个由若干个 `2014` 首尾相接连成的字符串，例如 `20142014` 和 `201420142014`是 2014 串，而 `2014201` 和 `572364` 不是 2014 串。

给定一个仅包含从 $0$ 到 $9$ 的数字的字符串 $S$，你每次操作可以交换 $S$ 中任意两个字符。判断是否能通过执行任意多次（可以为 $0$ 次）操作将 $S$ 变为 2014 串。

inputFormat:
第一行输入一个整数 $n$ 表示字符串 $S$ 的长度。
第二行输入一个长度为 $n$ 的字符串 $S$，保证 $S$ 仅包含从 $0$ 到 $9$ 的数字。

outputFormat: 如果可以将 $S$ 变为 2014 串，输出 `Yes`；否则输出 `No`。

hint:
对于 $20\%$ 的数据，$1 \leq n\leq 8$。
对于 $40\%$ 的数据，$1\leq n \leq 18$。
对于另外 $20\%$ 的数据，保证 $S$ 仅包含 $0,1,2,4$ 四种数字。
对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，字符串 $S$ 仅包含从 $0$ 到 $9$ 的数字。


title: [语言月赛 202403] Qiu

description:
有 $n$ 个球，其中有 $k$ 个橙色的，剩下的是绿的，求至少需要增加几个绿球才能让橙球的占比小于等于 $\dfrac{p}{q}$。

如果总共有 $a$ 个球，$b$ 个橙球，那么橙球的占比是 $\dfrac{b}{a}$。

inputFormat: 输入一行四个整数 $n,k,p,q$。

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

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

对于 $30\%$ 的数据，$q=1$。
对于另外 $30\%$ 的数据，$k=0$。
对于 $100\%$ 的数据，$1 \leq n,q \leq 1000$，$0 \leq k \leq 1000$，$0 \leq p \leq q$。


title: [语言月赛 202403] 雀？雀！

description:
可爱的 szm 妹妹迷上了雀魂麻将。在雀魂麻将中，点数的计算规则为：

* 满贯为 $5$ 番，庄家满贯获得 $12000$ 点，其他玩家满贯获得 $8000$ 点。
* 跳满为 $6$ 到 $7$ 番，可以获得满贯点数（即满贯所获得的点数，下同）的 $1.5$ 倍。
* 倍满为 $8$ 到 $10$ 番，可以获得满贯点数的 $2$ 倍。
* 三倍满为 $11$ 到 $12$ 番，可以获得满贯点数的 $3$ 倍。
* 番数为 $13x\sim 13x+12$（$x$ 是正整数）时，称为 $x$ 倍役满，可获得满贯点数的 $4x$ 倍。

按照游戏规则，如果 szm 获得 $x$ 点，第一名就减少 $x$ 点。例如，第一名当前的点数为 $35000$, szm 当前的点数为 $22000$，szm 获得 $8000$ 点后，第一名将减少 $8000$ 点，变为 $27000$，szm 将增加 $8000$ 点，变为 $30000$。

现在是 All Last（最后一局），szm 妹妹是庄家，她的点数是第二名，你需要找到最小的能使她变为第一名（点数不低于第一名的点数）的番数。

**题目描述的雀魂麻将和真实的雀魂麻将有所不同，请以题目描述为准。**

inputFormat: 输入一行两个整数 $x,y$，分别表示 szm 妹妹的点数和第一名的点数。

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

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

对于 $30\%$ 的数据，$1 \leq y-x \leq 24000$。
对于 $60\%$ 的数据，$1 \leq y-x \leq 10^7$。
对于 $100\%$ 的数据，$1 \leq x < y \leq 2\times 10^9$，$1 \leq y-x \leq 10^9$。


title: [语言月赛 202403] 传染病

background: 新型病毒正在肆虐洛谷。

description:
91-DIVOC 正在广泛传播，珂学家 RyanLi 想要探究 91-DIVOC 的传染系数。

第一天有 $a$ 个人被 91-DIVOC 感染，从第二天起，每个感染者都会向 $q$ 个没有感染的人传播 91-DIVOC，使他们变为感染者。

举个例子，如果第一天有 $3$ 人被感染，每个感染者每天向 $2$ 个人传播病毒，那么第二天会有 $3 \times 2$ 个人被感染。第三天会有 $3\times 2\times 2$ 个人被感染 $\cdots$ 以此类推。

定义传染系数为每天被感染 91-DIVOC 的人数的乘积，RyanLi 需要你求出 $k$ 天内的传染系数。由于这个数很大，你只需要输出它对 $722733748$ 取模的结果。

inputFormat: 输入一行三个整数 $k,a,q$。

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


title: [语言月赛 202403] 大西洋船王

background: 大西洋船王 Arthur von Montgomery 是 ScaredQiu 的童年男神。

description:
亚瑟目前有 $n$ 个任务需要完成，对于一个任务，他需要派遣 $1$ 到 $m$ 条船（不能不派遣）。派遣一条船出一次任务的花费为 $k$ 元，第 $i$ 次任务派出 $j$ 条船可以获得 $a_{i,j}$ 元。

请计算最优情况下亚瑟的收入，请注意这个值可能是负数。

inputFormat:
第一行输入三个整数 $n,m,k$。
接下来 $n$ 行每行输入 $m$ 个整数，第 $i$ 行的第 $j$ 个数为 $a_{i,j}$。

outputFormat: 输出一行一个整数，表示最优情况下亚瑟的收入。

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

对于 $20\%$ 的数据，$1 \leq n,m\leq 8$。
对于 $50\%$ 的数据，$1 \leq n,m\leq 100$。
对于 $100\%$ 的数据，$1 \leq n,m\leq 1000$，输入的所有数字都为整数，且都不超过 C++ 中 $32$ 位有符号整数可表示的范围。


title: [语言月赛 202403] szmgo

background:
本题请参考文字题解。

shinzanmono 想要学习 szm 语，但是 szm 语太难了。

description:
现代 szm 语采用罗马字表示，其划分音节的规则如下：

- 规定元音是字符 `a`、`e`、`i`、`o`、`u` 之一。
- 一般地，一个音节仅包含一个元音，并且以元音结尾。
- 特别地，当且仅当 `n` 后第一个字符不是元音时，`n` 单独作一个音节。
- 一个音节至多包含 $3$ 个字符。

举个例子，`shinzanmono` 的音节依次为 `shi` `n` `za` `n` `mo` `no`；`naku` 的音节依次为 `na` `ku`。

如果一个字符串是空串或者不能按照以上规则划分，则这个字符串不合法。**题目描述中给出的字符串和测试数据中输入的字符串全部合法，你无需进行合法性检验。**

将字符串 $S$ 的 $k$ 个音节依次表示为 $S'_1 \sim S'_k$，将另一个字符串 $T$ 的 $m$ 个音节依次表示为 $T'_1 \sim T'_m$。

如果存在一个正整数 $p$，满足 $p+m-1 \leq k$ 且对于从 $p$ 到 $p+m-1$ 的每个正整数 $i$ 都有 $S'_i=T'_{i - p + 1}$，那么称 $S$「包含」$T$。

在 szm 语中有一些习语，一种习语对应有一些固定的字符串。如果一个字符串「包含」且仅「包含」一种习语的一个固定子串，那么这个字符串是这种习语，否则这个字符串不是这种习语。

例如，当一种习语对应的子串只有 `ao` 时，字符串 `nao` 不是这种习语，因为 `nao` 的音节依次为 `na` `o`，而 `ao` 的音节依次为 `a` `o`。另一个例子是，如果敬语对应的子串为 `desu` 和 `suma`，那么 `kyuusaidesu` 是敬语，而 `kyuusaidesuma` 和 `kyuusaidema` 不是敬语。

某种习语对应 $n$ 个长度不超过 $10$ 的不同子串，给定 $q$ 个字符串，判断每个字符串是否是这种习语。

inputFormat:
第一行输入两个整数 $n,q$，含义如题面所述。
接下来 $n$ 行，第 $i$ 行输入一个字符串 $c_i$，表示习语对应的第 $i$ 个子串。
接下来 $q$ 行，第 $i$ 行输入一个字符串 $s_i$，询问字符串 $s_i$ 是否是给定习语。

outputFormat:
输出 $q$ 行，如果字符串 $s_i$ 是给定习语，在第 $i$ 行输出 `
Yes, Commander`；否则在第 $i$ 行输出 `No, Commander`。

samples:
2 4
desu
suma
kyuusaidesu
kyuusaidesuma
kyuusaidema
desudesu

samples:
Yes, Commander
No, Commander
No, Commander
Yes, Commander

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

对于 $30\%$ 的数据，保证习语对应的所有字符串都没有由单个元音组成的音节。
对于另外 $30\%$ 的数据，保证习语对应的所有字符串均只包含一个音节。
对于 $100\%$ 的数据，$1 \leq n \leq 10$，$1 \leq q \leq 10^5$，习语对应的每个子串的长度不超过 $10$ 且两两不同，询问的 $q$ 个字符串的字符个数之和不超过 $5 \times 10^5$，输入的所有字符串均只包含小写字符。


title: [语言月赛 202403] 数数，数数，数数

background: 请读出题目名称。

description:
我们的 szm 喜欢大数，她有一个数组 $a$，她还要你进行 $q$ 次操作。

对于第 $i$ 次操作，你需要将数组 $a$ 中的第 $x_i$ 个数修改为 $y_i$。

完成所有操作后，她需要你输出数组中大于等于 $V$ 的数的个数。

inputFormat:
第一行输入两个整数 $n,q$。
第二行输入一个整数 $V$。
第三行输入 $n$ 个整数，第 $i$ 个整数为 $a_i$。
接下来 $q$ 行，第 $i$ 行输入两个整数 $x_i,y_i$。

outputFormat: 输出一行一个整数，表示完成所有操作后数组中大于等于 $V$ 的数的个数。

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

对于 $30\%$ 的数据，$q=0$。
对于另外 $30\%$ 的数据，$V=0$。
对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq q \leq 10^5$，$1\leq x_i \leq n$，输入的所有数字都为整数，且都不超过 C++ 中 $64$ 位有符号整数可表示的范围。


title: 【MX-J3-T2】Substring

description:
你有一个数列 $a$，**其中 $1\sim n$ 各出现了一次**。

当你任意选一对 $1\le l\le r\le n$，并将 $a_l,a_{l+1},\ldots,a_r$ 排成一行，你就得到了 $a$ 的一个子串，记为 $a_{l\sim r}$，称 $l$ 为左端点，$r$ 为右端点。

你需要把 $a$ 所有子串按字典序从小到大排序。但是为了避免输出量过大，我会给出 $q$ 个问题，每次给出一个 $k$，求字典序第 $k$ 小的子串左右端点。

---

如果你不知道什么是字典序，看这里：

对于两个数列 $p,q$，称 $p$ 的字典序小于 $q$（记为 $p<q$），当且仅当存在**自然数** $k$ 使 $p,q$ 的前 $k$ 个数相同且 $p_{k+1}<q_{k+1}$。

特别地，若 $p$ 是 $q$ 的前缀且 $p\ne q$，也认为 $p$ 的字典序小于 $q$。

例如：
- $[1,2]<[3,2]$（当 $k=0$）
- $[3,1,100]<[3,2,1]$（当 $k=1$）
- $[3,4]<[3,4,6]$（$p$ 是 $q$ 前缀）

inputFormat:
输入的第一行有两个正整数 $n,q$ 表示序列长度和询问个数。

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

之后有 $q$ 行，每行有一个正整数 $k$，表示要求的子串的排名。

outputFormat: 对于每个问题，输出一行两个整数 $l,r$，表示字典序第 $k$ 小的子串是 $a_{l\sim r}$。


title: [语言月赛 202403] 土块

background: ScaredQiu 有一个形影不离的好朋友小 F，因为小 F 非常讨厌做题，考试的时候只能开赌。

description:
小 F 的考试中有 $n$ 道多选题，题号分别是从 $0$ 到 $n-1$ 的整数，每道题有 $4$ 个选项。一个选项要么是对的，要么是错的。一道题目的评分标准如下：

- 选择了至少一个错误选项或未选择任何选项，得 $0$ 分。

- 选择了全部的正确选项且没有选择任何错误选项，得 $6$ 分。

- 选择了一部分正确选项且没有选择任何错误选项，得 $3$ 分。

每道题目每个选项是否正确将由一个 $n$ 行 $4$ 列的 $01$ 矩阵 $a$ 描述，矩阵第 $i$ 行第 $j$ 列的元素为 $1$ 说明题号为 $i-1$ 的题目的第 $j$ 个选项是正确的，否则说明该选项是错误的。

小 F 按顺序作答了所有题目，他会给出一个 $n$ 行 $4$ 列的 $01$ 矩阵 $b$，矩阵第 $i$ 行第 $j$ 列的元素为 $1$ 说明他选择了他作答的第 $i$ 道题的第 $j$ 个选项，否则说明他没有选择该选项。

由于时间太紧，小 F 好像把答题卡涂错了。假设他作答的第 $1$ 道题的题号为 $x$，他会依次作答题号为 $x,(x+1) \bmod n,(x+2) \bmod n, \cdots ,(x+n-1) \bmod n$ 的题目。其中 $\bmod$ 为取模运算。

请计算：对于从 $0$ 到 $n-1$ 的每个整数 $i$，在作答的第 $1$ 道题的题号为 $i$ 的情况下，小 F 获得的总分数。

inputFormat:
第一行输入一个整数 $n$ 表示题目总数。
接下来 $n$ 行，每行输入四个整数，第 $i$ 行输入的第 $j$ 个数为 $a_{i,j}$。
接下来 $n$ 行，每行输入四个整数，第 $i$ 行输入的第 $j$ 个数为 $b_{i,j}$。

outputFormat: 输出一行 $n$ 个整数，第 $i$ 个整数表示小 F 作答的第一题的题号为 $i-1$ 时的答案。


title: 「MYOI-R3」消消乐

background:
**upd 2024/5/12 18:14：增加了两组 Hack 数据，位于 Subtask 1，分值为 $0$ 分。**

**upd 2024/5/12 21:27：增加了一组 Hack 数据，位于 Subtask 1，分值为 $0$ 分。**

description:
给定一个长度为 $n$ 的数列 $a$。

定义一次操作为选择三个整数 $x,y,z\in[1,n]$，满足 $\gcd(a_x,a_y)=a_z$ 且 $x,y,z$ 两两不同，接着消除 $a_z$（即之后的操作中不能再选择 $a_z$ 了）。

问经过若干次操作后可否消除数列 $a_1\sim a_n$ 中的 $n-2$ 个数？

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

对于每组数据，

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

第二行 $n$ 个正整数 $a_i$。

outputFormat: 对于每组数据，一行一个字符串 `Yes` 或 `No`。

hint:
### 样例解释：

- 对于第一组数据，可以通过 $(2,3)$ 消除 $1$。
- 对于第二组数据，可以证明无解。

### 数据范围：

本题共有 $20$ 个测试点，每个测试点的分值均为 $5$ 分。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$2\leq n \leq 10^6$，$2 \le \sum n\le 10^6$，$1\le a_i\le 10^9$。


title: Exciting Days

background:
网上流传一种说法，称 $10$ 月 $24$ 日是“程序员节”，因为 $1024$ 恰好是 $2^{10}$，而计算机和二进制有密切联系。

如果某个不使用地球历法的外星文明，也不一定用传统的二进制计算机，会不会也有类似的传统呢？

description:
某个星球的历法和地球虽然数值上和地球不同，但是其结构和地球人的历法大体相似。具体地，他们的一年有 $n$ 个月，其中第 $i$ 个月有 $a_i$ 天。

定义 $m$ 月 $d$ 日的**特征值**为将 $m,d$ 的十进制写出（不含前导 $0$）后，直接拼接的结果。例如 $3$ 月 $7$ 日特征值是 $37$，$12$ 月 $20$ 日特征值是 $1220$。

如果一个日期的特征值是 $k$ 的自然数次幂，则称这个日期是**广义程序员节**。你可以求出这个星球的所有广义程序员节吗？

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

每组测试数据输入两行。第一行有两个正整数 $n,k$，含义和题目描述一致；第二行有 $n$ 个正整数 $a_1,\ldots,a_n$ 表示每个月的天数。

outputFormat:
对于每组测试数据，先输出一行一个自然数表示广义程序员节个数；再输出若干行，每行一对用空格隔开的正整数 $m,d$ 表示 $m$ 月 $d$ 日表示一个程序员节。

在同一组测试数据中，输出的日期应按照一年当中的顺序输出。


title: 『FLA - I』歌静河

background:
**[English statement.](/problem/U458237) You must submit your code at the Chinese version of the statement.**

> You can cry
>
> Drinking your eyes
>
> Do you miss the sadness when it's gone
>
> And you let the river run wild
>
> And you let the river run wild

— _The River_ by _AURORA_

description:
秋有两个长度为 $n$ 且仅包含 `#` 和小写字母的字符串 $a,b$。

这两个字符串总共包含 $m$ 个 `#`，秋打算执行 $m$ 次操作，用小写字母把两个字符串中所有的 `#` 都替换掉。对于第 $i$ 次操作，他要在 $a,b$ 中选择一个字符串，将这个字符串中从左向右数第一个 `#` 替换为第 $(i-1) \bmod 26 +1$ 个小写字母。**他不能选择不包含 `#` 的字符串。**

秋有一位热爱艺术的好友，他想最小化执行完 $m$ 次操作后的字符串 $a$ 的字典序。秋想，编程也是一种艺术，这样的话，他们的心也会更近一些。

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

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

第三行输入一个长度为 $n$ 的字符串 $b$。

outputFormat: 输出一行一个字符串，表示执行 $m$ 次操作后能够得到的字典序最小的 $a$。

hint:
**「样例解释 #1」**

第一次操作选择字符串 $a$，将 $a$ 中的 `#` 替换为第 $(1-1) \bmod 26+1=1$ 个小写字母，即 `a`；第二次操作选择字符串 $b$，将 $b$ 中的 `#` 替换为第 $(2-1) \bmod 26+1=2$ 个小写字母，即 `b`。最终的字符串 $a$ 即为 `thankyou`，可以证明这是执行 $m$ 次操作后能得到的字典序最小的 $a$。

**「数据范围」**

|测试点编号|$n \leq$|特殊性质|
|:-:|:-:|:-:|
|$1 \sim 3$|$10$|无|
|$4 \sim 6$|$10^5$|有|
|$7 \sim 10$|$10^5$|无|

- 特殊性质：保证 $a,b$ 中存在一个不包含 `#` 的字符串。

对于所有测试数据，$1 \leq n \leq 10^5$，$1 \leq m \leq 2n$，字符串 $a,b$ 仅包含字符 `#` 和小写字母。

2024 年 8 月 4 日：添加了 1 组 hack 数据置于 Subtask #1。