title: 『FLA - I』云音泛

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

“……这些年来，过得可好？”

“……无所谓好或不好，人生一场空虚大梦，韶华白首，不过转瞬。惟有天道恒在，往复循环，不曾更改...”

description:
在梦中，秋种下了 $n$ 朵凋零玫瑰。他记得，第 $i$ 朵玫瑰是在时刻 $t_i$ 种植的。

凋零玫瑰在被种下的那个时刻就立即开放，但每一株玫瑰只会开放 $m$ 个时刻（在时刻 $T$ 种植的玫瑰会且仅会在从时刻 $T$ 到时刻 $T+m-1$ 的 $m$ 个时刻开放），在 $m$ 个时刻后便化作再也无法挽留的灰尘，飘散在凛冽的寒风中。

他问你，假如他可以改变不超过一朵玫瑰的种植时间（选定一个 $t_i$ 并将其修改为任意正整数），那么最多有多少个时刻有且仅有一株凋零玫瑰开放？

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

第二行输入 $n$ 个正整数，第 $i$ 个正整数为 $t_i$。

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

hint:
**「样例解释 #1」**

如图，使用金色标记有且仅有一株凋零玫瑰开放的时刻，使用黑色和红色标记每朵凋零玫瑰开放的时刻。

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

将使用红色标记的玫瑰的种植时刻改为 $17$（将 $t_1$ 的值修改为 $17$，如下图）后有 $14$ 个时刻有且仅有一株凋零玫瑰开放。可以证明不存在能够使有且仅有一株凋零玫瑰开放的时刻数量大于 $14$ 的修改方案。

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

**「数据范围」**

|测试点编号|$n \leq$|$m \leq$|$t_i \leq$|
|:-:|:-:|:-:|:-:|
|$1 \sim 6$|$5000$|$5000$|$5000$|
|$7 \sim 12$|$2 \times 10^5$|$2 \times 10^5$|$2 \times 10^5$|
|$13 \sim 14$|$2 \times 10^5$|$1$|$10^9$|
|$15 \sim 20$|$2 \times10^5$|$10^9$|$10^9$|

对于所有测试数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m,t_i \leq 10^9$。


title: 「CMOI R1」mex2

type: P

background:
小 U 对于从一个集合映射到一个数的函数很感兴趣，而 $\text{mex}$ 是一个很好的例子。

$\text{mex}(S)$ 指的是在集合 $S$ 中没有出现过的最小非负整数。

description:
多组数据。

每组数据，给定 $c$，要求构造序列 $a_1,a_2,...,a_n\in [0,2\times 10^9]$ 满足

$$\sum\limits_{1\le l\le r\le n}\text{mex}(a_l,a_{l+1},...,a_r)=c$$

其中要求 $1\le n\le3000$。可以证明在该题的数据范围内如果存在解，则在 $1\le n\le 3000$ 时一定存在解。

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

之后 $T$ 行每行一个非负整数 $c$。

outputFormat:
对于每组数据：

如果无解，则仅输出一行一个整数 $-1$。

否则，第一行输出一个正整数 $n$。

第二行输出 $n$ 个非负整数 $a_1,a_2,...,a_n$。


title: 「HOI R1」杂造选构

background: 小 $\iiint$ 跟这个烦人的构造没有任何关系。

description:
若一个序列 $a$ 满足以下要求：

- $a_i=-1$ 或 $a_i\in [1,n]$。
- 对于每个 $a_i\not=-1$，将 $a_i\to i$ 连边而形成的图不存在环。

则称这个序列是合法的。

现给定整数 $x$ 与序列 $a$，满足序列 $a$ 所有元素是 $[-1,n]$ 范围内的整数。请你将所有 $a_i=0$ 的位置替换成其他整数，使得 $\sum\limits ^{n} _{i=1} a_i = x$ 且 $a$ 是合法的。若不存在这样一种方案，则报告无解。

inputFormat:
第一行两个整数 $n$ 和 $x$。

第二行 $n$ 个整数，表示 $a$ 序列。保证 $\forall a_i \in [-1,n]$。

outputFormat: 若无解，则说明你被骗了，因此输出一个字符串 `Rick`。否则输出 $n$ 个整数，表示替换完所有为 $0$ 的元素后的 $a$ 序列。

hint:
**本题开启捆绑测试。**

| Subtask | 分值 | $n \le$ | $x \le$ |特殊性质 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| #0 | $13$ | $15$ | $225$|无|
| #1 | $24$ | $10^3$ | $10^9$|无|
| #2 | $27$ | $10^5$ | $10^{18}$|有|
| #3 | $36$ | $10^5$ | $10^{18}$|无|

*特殊性质：保证 $\forall a_i =0$。

对于所有数据，满足 $1 \le n \le 10^5,-10^{18} \le x \le 10^{18}$。

***

**Special Judge 返回值对应表**

- `Accepted.` 答案正确。
- `Oops, your answer is wrong. 1` 答案为无解，选手代码输出有解。
- `Oops, your answer is wrong. 2` 选手输出的 $\sum a_i \not = x$。
- `Oops, your answer is wrong. 3` 选手输出中含有 $0$。
- `Oops, your answer is wrong. 4` 选手输出中含有环。
- `Oops, your answer is wrong. 5` 选手输出在填空的同时将输入的 $a_i \not=0$ 的位置改动了。


title: [USACO24FEB] Bessla Motors G

background: **注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。本题的内存限制为 512MB，通常限制的 2 倍。**

description:
为了推广他的贝斯拉（Bessla）电动拖拉机系列，Farmer John 希望展示贝斯拉的充电网络。他已标记了地图上 $N$（$2\le N\le 5\cdot 10^4$）个编号为 $1\ldots N$ 的兴趣点，其中前 $C$（$1\le C<N$）个是充电站，其余为旅游目的地。这些兴趣点之间由 $M$（$1 \le M \le 10^5$）条双向道路连接，其中第 $i$ 条连接不同的点 $u_i$ 和 $v_i$（$1\le u_i,v_i\le N$）且长度为 $l_i$ 英里（$1\le l_i\le 10^9$）。

贝斯拉一次充电最多可行驶 $2R$英里（$1\le R\le 10^9$），使之可以到达一个充电站 $R$ 英里范围内的任何目的地。一个目的地被称之为交通便利的，如果可以从至少 $K$（$1\le K\le 10$）个不同的充电站到达目的地。你的任务是帮助 Farmer John 确定交通便利的旅游目的地的集合。

inputFormat:
输入的第一行包含五个空格分隔的整数 $N$，$M$，$C$，$R$ 和 $K$。以下 $M$ 行，每行包含三个空格分隔的整数 $u_i$，$v_i$ 和 $l_i$，其中 $u_i\neq v_i$。

充电站的编号为 $1,2,\ldots,C$。其余兴趣点均为旅游目的地。

outputFormat: 首先输出一行，包含交通便利的旅游目的地的数量。然后升序输出所有交通便利的旅游目的地，每个一行。

hint:
### 样例解释 1

我们在 $1$ 有一个充电站。从这个充电站出发，我们可以到达 $2$（因为它与 $1$ 的距离为 $3$），但不能到达 $3$（因为它与 $1$ 的距离为 $5$）。因此，只有点 $2$ 是交通便利的。

### 样例解释 2

我们在 $1$ 和 $2$ 有充电站，点 $3$ 和 $4$ 均位于 $1$ 和 $2$ 的 $101$ 距离内。因此，点 $3$ 和 $4$ 都是交通便利的。

### 测试点性质

- 测试点 $4-5$：$K=2$，$N\le 500$ 且 $M\le 1000$。
- 测试点 $6-7$：$K=2$。
- 测试点 $8-15$：没有额外限制。


title: [USACO24FEB] Milk Exchange G

description:
Farmer John 的 $N$（$1\le N \le 5\cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\le a_i\le 10^9$）升的桶。所有桶初始时都是满的。

每一分钟，对于 $1\le i<N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满的，送出 $x$ 升牛奶同时收到 $x$ 升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。

在 $1,2,\ldots,N$ 的每一分钟后，所有奶牛总共还余下多少牛奶？

inputFormat:
输入的第一行包含 $N$。

第二行包含 $a_1,a_2,\ldots,a_N$。

outputFormat: 输出 $N$ 行，其中第 $i$ 行包含 $i$ 分钟后所有奶牛总共余下的牛奶量。


title: [USACO24FEB] Quantum Moochanics G

description:
在空闲时间，Bessie 喜欢涉猎实验物理。她最近发现了一对新的亚原子粒子，命名为**哞微子**和**反哞微子**。如同标准的[物质-反物质对](https://baike.baidu.com/item/%E5%8F%8D%E7%89%A9%E8%B4%A8/115035)，哞微子和反哞微子相遇时会相互湮灭并消失。但这些粒子的独特之处在于，每当 Bessie 看向它们时它们就会改变运动方向（同时保持相同的速率）。

在她最新的实验中，Bessie 将**偶数** $N$（$2\le N\le 2\cdot 10^5$）个这些粒子排成一行。这一行的左端以哞微子开始，然后在两种类型的粒子之间交替，第 $i$ 个粒子位于位置 $p_i$（$0\le p_1<\cdots <p_N\le 10^{18}$）。哞微子初始时**向右**运动而反哞微子初始时**向左**运动，其中第 $i$ 个粒子以每秒 $s_i$ 单位的恒定速率运动（$1\le s_i\le 10^9$）。

Bessie 在以下时刻进行观察：

- 首先是实验开始后 $1$ 秒。
- 然后是第一次观察后 $2$ 秒。
- 然后是第二次观察后 $3$ 秒。
- $\ldots \ldots$
- 然后是第 $n$ 次观察后 $n+1$ 秒。

在每次观察中，Bessie 都会记下哪些粒子消失了。

这个实验可能需要非常长的时间才能完成，所以 Bessie 想要首先模拟一下它的结果。根据实验设置，请帮助 Bessie 求出她何时（即**观察次数**）会观察到各个粒子消失！可以证明，所有粒子最终都会消失。

inputFormat:
每个测试点包含 $T$（$1\le T\le 10$）个独立的测试用例。

每个测试用例包含三行。第一行包含 $N$，第二行包含 $p_1,\ldots,p_N$，第三行包含 $s_1,\ldots,s_N$。

输入保证所有 $N$ 之和不超过 $2\cdot 10^5$。

outputFormat: 对于每一个测试用例，输出每个粒子消失时的观察次数，用空格分隔。

hint:
### 样例解释 1

对于第一个测试用例，Bessie 在前 $8$ 次观察中观察到以下情况：

- 哞微子（初始时向右运动）出现在位置 $2\to 0\to 3\to −1\to 4\to −2\to 5\to −3$。
- 反哞微子（初始时向左运动）出现在位置 $10\to 12\to 9\to 13\to 8\to 14\to 7\to 15$。

然后恰好在观察 $9$ 时，两个粒子在位置 $6$ 相遇并相互湮灭。

对于第二个测试用例，反哞微子的初始位置更靠右 $1$
单位，从而两个粒子在观察 $11$ 之前半秒在位置 $6.5$ 相遇。

注意我们只关心观察次数，不关心时刻或位置。

### 样例解释 2

对于第一个测试用例：

- 最左边的两个粒子恰好在观察 $1$ 时在位置 $2$ 相遇。
- 最右边的两个粒子在观察 $3$ 之前半秒在位置 $6.5$ 相遇。

### 测试点性质

- 测试点 $3$：$N=2$。
- 测试点 $4$：$N\le 2000$，且对于所有粒子，$p_i\le 10^4$。
- 测试点 $5-7$：$N\le 2000$。
- 测试点 $8-12$：没有额外限制。


title: [USACO24FEB] Lazy Cow P

description:
Bessie 正在努力为美国件算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 $a$，花费 $3^{a−1}$ 能量准备 $a$ 个测试用例。

Farmer John 有 $D$（$1\le D\le 2\cdot 10^5$）个需求。对于第 $i$ 个需求，他告诉 Bessie，在前 $m_i$ 分钟内她总共需要准备至少 $b_i$ 个测试用例（$1\le m_i\le 10^6,1\le b_i\le 10^{12}$）。

令 $e_i$ 为满足前 $i$ 个需求 Bessie 最小需要花费的能量。输出 $e_1,\ldots,e_D$ 模 $10^9+7$ 的余数。

inputFormat: 输入的第一行包含 $D$。以下 $D$ 行，第 $i$ 行包含两个空格分隔的整数 $m_i$ 和 $b_i$。

outputFormat: 输出 $D$ 行，第 $i$ 行包含 $e_i \bmod 10^9+7$。

hint:
### 样例解释 1

对于第一个测试用例，

- $i=1$：如果 Bessie 在前 $5$ 天分别制作 $[2,3,2,2,2]$ 个测试用例，她将花费 $3^1+3^2+3^1+3^1+3^1=21$ 单位能量，并在第 $5$ 天结束时制作了 $11$ 个测试用例。
- $i=2$：Bessie 可以遵循上面的策略，确保在第 $5$ 天结束时制作了 $11$ 个测试用例，而这将自动满足第二个需求。
- $i=3$：如果 Bessie 在前 $10$ 天分别制作 $[2,3,2,2,2,0,1,1,1,1]$ 个测试用例，她将花费 $25$ 单位能量并满足所有需求。可以证明她无法花费更少的能量。
- $i=4$：如果 Bessie 在前 $10$ 天每一天制作 $3$ 个测试用例，她将花费 $3^2\cdot 10=90$ 单位能量并满足所有需求。

对于每一个 $i$，可以证明 Bessie 无法花费更少的能量满足前 $i$ 个需求。

### 测试点性质

- 测试点 $4-5$：$D\le 100$，且对于所有 $i$，$m_i\le 100$。
- 测试点 $6-8$：$D\le 3000$。
- 测试点 $9-20$：没有额外限制。


title: [USACO24FEB] Test Tubes S

description:
Bessie 最近开始对化学感兴趣。目前，她有两种不同颜色 $1$ 和 $2$ 的液体，彼此之间无法混合。她有两个无限容量的试管，各装有 $N$（$1\le N\le 10^5$）单位的这两种颜色的液体混合物。由于液体无法混合，一旦沉淀，它们就会分成不同颜色的层。因此，两个试管可以被视为两个字符串 $f_1f_2\ldots f_N$ 和 $s_1s_2\ldots s_N$，其中 $f_i$ 表示距离第一个试管底部 $i$ 单位处的液体的颜色，$s_i$ 表示距离第二个试管底部 $i$ 单位处的液体的颜色。输入保证两种颜色的液体至少各有一个单位。

Bessie 想要分离这些液体，以使得每个试管包含一种颜色的液体的所有单位。她有第三个无限容量的空烧杯来帮助她完成这一任务。当 Bessie 进行一次「倾倒」时，她将一个试管或烧杯顶部的所有颜色为 $i$ 的液体移至另一个的顶部。

求出将所有液体分离到两个试管中所需的最小的倾倒次数，以及所需的移动操作。两个试管最终包含的液体颜色不影响正确性，但烧杯必须是空的。

有 $T$（$1\le T\le 10$）个测试用例，每个测试用例有一个参数 $P$。

设将液体分离至试管中的最小倾倒次数为 $M$。

- 若 $P=1$，当你仅输出 $M$ 时可以得到分数。
- 若 $P=2$，当你输出 $A$，其中 $M\le A\le M+5$，并在以下 $A$ 行输出以该操作次数构造的一个方案时，可以得到分数。每一行包含来源试管和目标试管（$1$，$2$，或用 $3$ 表示烧杯）。操作之前，来源试管必须是非空的，并且不得将一个试管向其自身倾倒。
- 若 $P=3$，当你输出 $M$，并输出以该操作次数构造的一个方案时，可以得到分数。

inputFormat:
输入的第一行包含 $T$，为测试用例的数量。对于每一个测试用例，第一行包含 $N$ 和 $P$，为每个试管最初装有液体的数量以及询问类型。下一行包含 $f_1f_2f_3\ldots f_N$，表示第一个试管。$f_i\in \{1,2\}$，$f_1$ 表示试管的底部。下一行包含 $s_1s_2s_3\ldots s_N$，表示第二个试管。$s_i\in \{1,2\}$，$s_1$ 表示试管的底部。

输入保证两个字符串均包含至少一个 $1$ 和一个 $2$。

outputFormat: 对于每一个测试用例，输出一个整数，表示分离试管中液体的最少倾倒次数。根据询问类型，你可能还需要提供合法的构造方案。

hint:
### 样例解释

在前三个测试用例中，分离试管的最小倾倒次数为 $4$。我们可以看到以下操作是如何分离试管的：

初始状态：

```plain
1: 1221
2: 2211
3:
```

在操作 `1 2` 后：

```plain
1: 122
2: 22111
3:
```

在操作 `1 3` 后：

```plain
1: 1
2: 22111
3: 22
```

在操作 `2 1` 后：

```plain
1: 1111
2: 22
3: 22
```

在操作 `3 2` 后：

```plain
1: 1111
2: 2222
3:
```

在最后一个测试用例中，最小倾倒次数为 $5$。然而，由于 $P=2$，给出的 $6$ 次操作的构造也是合法的，因为它与最优解的差在 $5$ 次倾倒之内。

### 测试点性质

- 测试点 $2-6$：$P=1$。
- 测试点 $7-11$：$P=2$。
- 测试点 $12-21$：没有额外限制。

除此之外，输入保证除样例外的所有测试点均有 $T=10$。


title: [USACO24FEB] Infinite Adventure P

background: **注意：本题的内存限制为 512MB，通常限制的 2 倍。**

description:
Bessie 正在计划一次在 $N$（$1\le N\le 10^5$）个城市的大陆上的无尽冒险。每个城市 $i$ 都有一个传送门以及循环周期 $T_i$。所有 $T_i$ 均为 $2$ 的幂，且 $T_1+\cdots+T_N\le 10^5$。如果你在日期 $t$ 进入城市 $i$ 的传送门，那么你会立即从城市 $c_{i,t\bmod T_i}$ 的传送门出来。

Bessie 的旅行有 $Q$（$1\le Q\le 5\cdot 10^4$）个计划，每个计划由一个元组 $(v,t,\Delta)$ 组成。在每个计划中，她将于日期 $t$ 从城市 $v$ 出发。然后，她将执行以下操作 $\Delta$ 次：她将进入当前城市的传送门，然后等待一天。对于她的每一个计划，她想要知道她最终会在哪个城市。

inputFormat:
输入的第一行包含两个空格分隔的整数：结点的数量 $N$，以及询问的数量 $Q$。

第二行包含 $N$ 个空格分隔的整数：$T_1,T_2,\ldots,T_N$（$1\le T_i$，$T_i$ 是 $2$ 的幂，且 $T_1+\cdots+T_N\le 10^5$）。

对于 $i=1,2,\ldots,N$，第 $i+2$ 行包含 $T_i$ 个空格分隔的正整数，为 $c_{i,0},\ldots,c_{i,T_{i−1}}$（$1\le c_i,t\le N$）。

对于 $j=1,2,…,Q$，第 $j+N+2$ 行包含三个空格分隔的正整数 $v_j,t_j,\Delta_j$（$1\le v_j\le N$，$1\le t_j\le 10^{18}$，且 $1\le \Delta_j\le 10^{18}$），表示第 $j$ 个询问。

outputFormat: 输出 $Q$ 行。第 $j$ 行包含第 $j$ 个询问的答案。

hint:
### 样例解释 1

Bessie 的前三次冒险会如下进行：

- 在第一次冒险中，她于时刻 $4$ 从城市 $2$ 出发，于时刻 $5$ 到达城市 $3$，于时刻 $6$ 到达城市 $4$，于时刻 $7$ 到达城市 $2$。
- 在第二次冒险中，她于时刻 $3$ 从城市 $3$ 出发，于时刻 $4$ 到达城市 $4$，于时刻 $5$ 到达城市 $2$，于时刻 $6$ 到达城市 $4$，于时刻 $7$ 到达城市 $2$，于时刻 $8$ 到达城市 $4$，于时刻 $9$ 到达城市 $2$。
- 在第三次冒险中，她于时刻 $3$ 从城市 $5$ 出发，于时刻 $4$ 到达城市 $5$，于时刻 $5$ 到达城市 $5$。

### 测试点性质

- 测试点 $3$：$\Delta_j\le 2\cdot 10^2$。
- 测试点 $4-5$：$N,\sum T_j\le 2\cdot 10^3$。
- 测试点 $6-8$：$N,\sum T_j\le 10^4$。
- 测试点 $9-18$：没有额外限制。


title: [CTS2024] 水镜

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: [CTS2024] 线段树

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 )$。

子任务 1（6 分）：$N≤10$。

子任务 2（18 分）：$N≤100$。

子任务 3（9 分）：$N≤500$。

子任务 4（17 分）：$N≤5000$。

子任务 5（10 分）：$M=1$。

子任务 6（13 分）：$M≤5$。

子任务 7（7 分）：$M=N,L_i=0,R_i=i$。

子任务 8（20 分）：无额外限制。


title: [CTS2024] 众生之门

background: [原题面存档。](https://www.luogu.com.cn/paste/pd4a89g5)

description:
给定 $n$、一棵 $n$ 个点的无向树和树上的两个不相同的节点 $s,t$，其中每条边的长度均为 $1$。节点由 $1$ 至 $n$ 的整数编号。记 $\mathrm{dist}(u,v)$ 表示 $u$ 和 $v$ 的距离（即简单路径经过的边数）。你需要给出一个 $1$ 到 $n$ 的排列 $p_1,p_2,\cdots,p_n$ 满足以下两个条件：

- $p_1=s$，$p_n=t$；
- 设 $d_i=\mathrm{dist}(p_i,p_{i+1})(1\leq i\leq n-1)$，那么你给出的排列需要满足以上条件的前提下，最小化 $\oplus_{i = 1} ^ {n - 1}d_i$，其中 $\oplus$ 表示按位异或。

如果有多种满足条件的排列，输出任意一种均可。

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

本题有多组测试数据。第一行输入一个正整数 $T$ 表示测试数据组数。

对于每组数据，第一行输入三个正整数 $n,s,t$，接下来 $n-1$ 行每行两个正整数 $u,v$，表示地点 $u$ 和 $v$ 有直接无向道路连接（即树上的一条边）。

outputFormat:
输出到标准输出。

对于每组数据，输出一行 $n$ 个正整数 $p_1,p_2,\cdots,p_n$，你需要保证其为 $1$ 到 $n$ 的一个排列且 $p_1=s$，$p_n=t$，且 $\oplus_{i = 1} ^ {n - 1} d_i$ 最小。

samples: 见题目目录下的 2.in 与 2.ans。

hint:
**样例 1 解释**

该样例共有三组测试数据。

- 对于第一组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $0$，样例输出为 $1,2,3$，其中 $d_1=d_2=1$。
- 对于第二组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $2$，样例输出为 $3,2,1,4$，其中 $d_1=d_2=1$，$d_3=2$；另一种合法输出为 $3,1,2,4$。
- 对于第三组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $1$，样例输出为 $1,5,3,4,2$，其中 $d_1=2$，$d_2=1$，$d_3=3$，$d_4=1$。

**样例 2 解释**

值得注意的是，该输入数据由所有满足 $n\leq 10$ 的，且所有不同 $s$ 和 $t$ 的相对位置的可能的树形态构成。

这个样例，无疑是善良的出题人无私的馈赠。中间忘了。出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。

### 数据范围

设 $\sum n$ 表示单个测试点内所有数据的 $n$ 的和。对于所有测试数据，

- $T≥1$；
- $2\leq n\leq 5\times 10 ^4$，$\sum n\leq 5\times 10 ^ 5$；
- $1\leq s,t\leq n$，$s\neq t$；
- $1\le u,v\le n$，$u\neq v$；
- 输入的 $n-1$ 个 $(u,v)$ 构成一棵树。

| 子任务编号 | $n$                   | $\sum n$              | 特殊性质 | 分数 |
|-------|-----------------------|-----------------------|------|----|
| 1     | $\le 8$               | $\le 10^{3}$          | 无    | 5  |
| 2     | $\le 12$              | $\le 10^{3}$          | 无    | 8  |
| 3     | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | A    | 17 |
| 4     | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | B    | 20 |
| 5     | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | C    | 17 |
| 6     | $\le 10^{3}$          | $\le 10^{4}$          | D    | 10 |
| 7     | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | 无    | 23 |

特殊性质 A：保证每个点度数小于等于 $2$。

特殊性质 B：保证对于任意 $x$ 有 $\mathrm{dist}(s,x)+\mathrm{dist}(x,t)\le \mathrm{dist}(s,t)+2$。

特殊性质 C：保证 $\mathrm{dist}(s,t)=1$。

特殊性质 D：该子任务共有五个测试点，对于每一个测试点，保证 $T=10$ 且 $n=1000$，并且每个测试数据中，$s$ 在 $1\sim n$ 中等概率随机生成，$t$ 从 $1\sim n$ 除去 $s$ 中等概率随机生成，树从所有 $n$ 个点的有标号树中等概率随机生成。


title: [CTS2024] 多方计算

background:
## 滥用本题评测将被封号

**特别注意**：为了能够正常评测，请删去代码开头的 `#include "mpc.h"` 并加入以下代码段：

```cpp
#include <array>
struct player{
    bool last_message;
    std::array<int, 4096> memory;
};
int precalc(int n, int m);
bool transmit(player &player, int round, int position);
```

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

有 $n+1$ 个人，由 $0$ 至 $n$ 编号。第 $i(0 \le i \le n-1)$ 个人有一个 $[0,2^m-1]$ 之间的整数 $a_i$。

编号为 $n$ 的人希望知道 $a_0+a_1+\cdots+a_{n-1}$ 的值。为此，他们可以进行如下通讯：

1. 首先，选定通讯的秒数 $N$。
2. 接下来的 $N$ 秒中的每一秒，所有 $i(0 \le i \le n-1)$ **同时**向 $(i+1)$ 发送一个比特的信息。

  - 该消息会在下一秒开始前收到。特别地，最后一秒发出的信息不会被收到。
  - 除此之外，不允许任何其他形式的通讯。

你需要用尽可能少的通讯秒数完成这个任务。

## 实现细节

请确保你的程序开头有 `#include "mpc.h"`。

你不需要也不应该实现主函数。你需要实现以下两个函数：

```cpp
int precalc(int n, int m);
```

- `n` 表示人数，`m` 表示整数的值域。
- 你需要返回通讯的秒数 $N$。

```cpp
bool transmit(player &player, int round, int position);
```

- `round` 表示目前通讯的秒数，其取值为 $[1,N]$ 中的整数；
- `position` 表示当前传递信息的人的编号，其取值为 $[0,n]$ 中的整数；
- `player` 为一个结构体类型，描述了当前传递信息的人。该结构体实现在 `mpc.h` 中。其包含以下两个成员变量：
  - 布尔类型变量 `last_message`，表示上一秒上一个人传递的信息。若 `position` 为 $0$ 或 `round` 为 $1$，则 `last_message` 的值一定为 $0$；
  - 长度为 $4096$ 的整型数组 `memory`，描述当前传递信息的人的“记忆”。
    - 在 `transmit` 函数中，这个数组可以被任意修改。
    - `player.memory` 只可能在 `transmit` 函数中被修改。若 `transmit` 函数中不对 `player.memory` 进行修改，则同一个人多次传递信息时，`player.memory` 都存储相同的值。
    - `player.memory` 的初始值按照以下规则设定：
      - `position` 不为 $n$ 时，`memory` 的 $0$ 到 $m-1$ 位取值为 $\{0,1\}$，从低位到高位描述 $a_{\text{position}}$ 的二进制表示（即第 $i$ 位对应位权 $2^i$ 的位），而其余位置为 $0$；
      - 否则，该数组的所有位置均为 $0$。
- 你需要返回这个人在这一秒传递给下一个人的信息。
  - 当 `position` 为 $n$ 时或 `round` 为 $N$ 时，该返回值不会产生任何影响。

在所有 `transmit` 调用结束后，你需要保证编号为 $n$ 的人的 `player.memory` 中前 $2200$ 位取值均属于 $\{0,1\}$，且对应的二进制数是所有 $a_i$ 的和。

在满足题目条件和数据范围的情况下，交互库至多消耗 $0.15$ 秒的时间以及 $128\text{MiB}$ 的空间。

**在程序中使用其他形式的通讯，包括但不限于使用全局变量，会被视为攻击交互库。**

## 测试程序方式

试题目录下提供了一个交互库的参考实现 `grader.cpp`。最终测试时所用的交互库实现与该实现有不同，因此选手的解法不应依赖交互库的具体实现。

你需要在本题目录下使用以下编译命令得到可执行程序：

`g++ mpc.cpp grader.cpp -o mpc -O2 -std=c++17 -lm`

可执行文件将从标准输入读入以下格式的数据：

- 第一行两个整数 $n, m$，
- 接下来 $n$ 行每行 $m$ 个 `01` 整数，从低到高表示每个人的整数的二进制表示，每行的两个整数之间用一个空格分隔。

读入完成后，交互库会先调用一次 `init(n,m)` 函数得到 $N$，然后进行 $\max(0,N)$ 轮调用，第 $k(1 \le k \le \max(0,N))$ 轮调用会调用所有 $\text{round}=k$ 的 `transmit` 函数，并在调用完之后更新相应的 `player.last_message` 的值。

- 若 $N \le 0$，则不会进行任何调用，所有 `player.memory` 为其初始值。

若你的程序正确运行，可执行文件会输出以下格式的数据：

- 第一行一个长度为 $2200$ 的字符串，表示所有 $a_i$ 的和，按二进制从低位到高位输出。
- 第二行一个字符串，依次输出所有交互完毕后编号为 $n$ 的人的 `player.memory` 中前 $2200$ 个位置表示的数，**相邻两个数之间没有空格**。
- 第三行，如果上述两个字符串不同，那么会告知你答案错误；不然，会输出你在这组数据上的得分。

本题目录中同时下发了样例 `1.in`，`1.ans` 以及一个样例程序 `mpc.cpp`。该样例程序可以通过下发的样例。


title: [CTS2024] 投票游戏

description:
有 $n$ 个人，由 $1$ 至 $n$ 编号。第 $i (2 \le i \le n)$ 个人有一个讨厌的人 $f_i (1 \leq f_i < i)$，第 $1$ 个人没有讨厌的人。

这一天，$n$ 个人进行了一场关于投票的游戏。一次游戏会进行 $n$ 轮。游戏开始时，所有人都没有被票出。游戏的每一轮中，会进行以下过程：

1. 对于每一个没有被票出的人 $i$，TA 初始有 $a_i$ 票。
2. 随后，对于每一个没有被票出的人 $i$，如果 TA 有讨厌的人且 TA 讨厌的人 $f_i$ 没有被票出，则 TA 会给 $f_i$ 投 $b_i$ 票。
3. 最后，票出当前没有被票出的人的票数最高的，如果有多个票数最高的人，票出其中编号最大的人。

一次游戏的 $n$ 轮之间独立计票。

在游戏开始前，发生了 $q$ 次事件，事件有以下两种：

1. 给定 $p, x, y$，将 $(a_p, b_p)$ 修改为 $(x,y)$；
2. 小明想知道，给定两个人 $c,d$，如果此刻进行一次游戏，两个人中谁先被票出。

作为小明的朋友，你可以帮帮小明吗？

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

第一行两个正整数 $n, q$，表示人数与发生的事件数。

第二行 $(n-1)$ 个整数 $f_2, f_3, \cdots, f_n$。

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

第四行 $n$ 个整数 $b_1, b_2, \cdots, b_n$。

接下来 $q$ 行，每行三个或四个整数描述一个事件。第一个正整数 $op$ 表示发生事件的类型。

- 若 $op=1$，则接下来三个整数 $p, x, y$，表示将 $(a_p, b_p)$ 修改为 $(x, y)$。
- 若 $op=2$，则接下来两个正整数 $c, d$，你需要判断如果此时进行了一次游戏，$c$ 和 $d$ 谁先被票出。

outputFormat:
输出到标准输出。

对于每个 $op=2$ 的事件输出一行一个 `01` 字符，若 $c$ 先被票出输出 `0`，否则输出 `1`。


title: [CTS2024] 字符串游戏

description:
小 P 和小 B 喜欢玩游戏，他们找到了 skip。skip 告诉了他们这样一个游戏：

- 有一个包含小写字母的字符串 $S$，游戏开始时其为 skip 给定的一个字符串 $S_0$。游戏对小 P 和小 B 计算分数，初始他们的分数都为 $0$。
- 小 P 和小 B 轮流在这个串上操作，小 P 先手。每次操作方可以进行以下操作：
  - 选择 $S$ 的一个非空前缀（可以是 $S$ 本身），获得等同于这个前缀在 $S$ 中的出现次数的分数，并将这个前缀从 $S$ 中删掉。
- 如果进行了某次操作后 $S$ 变为空，游戏就结束了。

为了让你更好的理解游戏规则，考虑如下例子：

- 初始时，$S_0 = ababa$；
- 小 P 选择 $ababa$ 的前缀 $a$，获得 3 分，$S$ 变为 $baba$；
- 小 B 选择 $baba$ 的前缀 $ba$，获得 2 分，$S$ 变为 $ba$；
- 小 P 选择 $ba$，获得 1 分，字符串变为空，游戏结束。最终小 P 获得 4 分，小 B 获得 2 分。

小 P 希望最大化小 P 的得分减去小 B 的得分，而小 B 希望最小化这个值。他们想知道在双方都绝顶聪明的情况下，最终小 P 的得分减去小 B 的得分会是多少。

inputFormat:
标准输入读入数据。

输入仅一行一个小写字母构成的字符串 $S_0$。

outputFormat:
输出到标准输出。

一个整数，表示双方绝顶聪明的前提下，游戏结束时小 P 的得分减去小 B 的得分的值。


title: [JOI 2024 Final] 室温

description:
K 董事长负责调节高管们的房间的室温，他希望高管们能尽可能舒适地工作。

现在房间里有 $N$ 位高管。每位高管都有一个从 $1$ 到 $N$ 的编号。不穿外套时，高管 $i\ (1 \leq i \leq N)$ 的舒适温度是 $A_{i}$ 度。另外，每位高管每穿一件外套，舒适温度就会降低 $T$ 度。也就是说，高管 $i$ 如果穿了 $k$ 件外套，那么高管 $i$ 的舒适温度就是 $A_{i}-k T$ 度。

如果房间的温度是 $x$ 度，某位高管的舒适温度是 $y$ 度，那么这位高管的不舒适度就是 $|x-y|$。其中，$|t|$ 表示 $t$ 的绝对值。每位高管会根据房间的温度，穿上大于等于 $0$ 件合适的外套，使得不舒适度最小。

K 董事长把高管们的不舒适度的最大值称为房间的不舒适度，并决定要把房间的温度设定为使得房间的不舒适度最小的值。但是，设定的温度必须是整数。

给定高管和舒适温度的信息。编写一个程序，求出房间的不舒适度可能的最小值。

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

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

outputFormat: 输出一行一个整数，表示房间的不舒适度可能的最小值。


title: [JOI 2024 Final] 建设工程 2

description:
JOI 国有 $N$ 个火车站，编号从 $1$ 到 $N$。另外，JOI 国有 $M$ 条双向铁路线，编号从 $1$ 到 $M$。铁路线 $i\ (1 \leq i \leq M)$ 连接了火车站 $A_{i}$ 和火车站 $B_{i}$，从一个站到另一个站需要花费 $C_i$ 分钟。

你是 JOI 国的部长，决定按照以下方式新建一条铁路线：

选择两个整数 $u, v\ (1 \leq u<v \leq N)$，在火车站 $u$ 和火车站 $v$ 之间建设一条双向铁路线，从一个站到另一个站需要花费 $L$ 分钟。注意，即使已经有一条连接火车站 $u$ 和火车站 $v$ 的铁路线也可以建设。

如果你建设这条铁路线后，可以花费不超过 $K$ 分钟从火车站 $S$ 到火车站 $T$，国王就会高兴。我们不考虑换乘时间和等待时间。

你有 $\frac{N(N-1)}{2}$ 种选择两个整数 $u, v$ 的方法，你想知道其中有多少种方法会让国王高兴。

给定火车站和铁路线以及国王的要求的信息，编写一个程序，求出其中有多少种选择整数的方法会让国王高兴。

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

第一行包含两个整数 $S,T,L,K$。

接下来 $M$ 行，每行包含三个整数 $A_i, B_i, C_i$，表示第 $i$ 条双向铁路线。

outputFormat: 输出一行一个整数，表示让国王高兴的两个整数的选择方法有多少种。


title: [JOI 2024 Final] 马拉松比赛 2

description:
JOI 大道是一条东西向的长度为 $L$ 米的道路，地点 $l$ 位于从道路的西端走 $l\ (0 \leq l \leq L)$ 米的地方。

今年 JOI 大道上第一次举办了马拉松大会。这个马拉松大会的规则和一般的不同，是按照以下的方式进行的：

- 道路上放了 $N$ 个球，第 $i\ (1 \leq i \leq N)$ 个球放在地点 $X_{i}$。有些地方可能有多个球放在一起。
- 参加者从规定的起点出发，拿到所有 $N$ 个球后，如果在规定的时间内到达规定的终点，就算是完赛。但是，如果把拿到的球放在地上就会被取消资格。

这个大会的起点，终点和时间限制还没有公布，但是已经公布了 $Q$ 个可能的方案。第 $j\ (1 \leq j \leq Q)$ 个方案的起点是地点 $S_{j}$，终点是地点 $G_{j}$，时间限制是 $T_{j}$ 秒。

理恵是马拉松大会的其中一名运动员。她拿起一个球要花 $1$ 秒，拿着 $x$ 个球在道路上跑 $1$ 米要花 $x+1$ 秒。

给出 JOI 大道，球，方案的信息。编写一个程序，对于每个方案判断理恵能不能完赛。

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

第二行包含用空格分隔的 $N$ 个整数 $X_1, X_2, \ldots ,X_N$。

第三行包含一个整数 $Q$。

接下来 $Q$ 行，每行包含三个整数 $S_j, G_j, T_j$，表示第 $j$ 个方案。

outputFormat: 输出 $Q$ 行。第 $j\ (1 \leq j \leq Q)$ 行，如果第 $j$ 个方案理恵能完赛输出 Yes，否则输出 No。


title: [JOI 2024 Final] 礼物交换

description:
JOI 学园有 $N$ 名学生，每个学生都有一个从 $1$ 到 $N$ 的编号。

JOI 学园计划近期举办一个礼物交换会。每个学生都要准备一份礼物带到会场，学生 $i\ (1 \leq i \leq N)$ 带来的礼物的价值是 $A_{i}$ 。学生们都不喜欢收到比自己带来的礼物价值低很多的礼物，具体来说，学生 $i$ 如果收到价值低于 $B_{i}$ 的礼物，就会感到不满。保证 $B_{i}<A_{i}$。

不过，并不是所有 $N$ 名学生都会真的参加礼物交换会。JOI 学园的校长 K 正在考虑 $Q$ 种可能参加礼物交换会的学生组合，第 $j\ (1 \leq j \leq Q)$ 种组合由 $R_{j}-L_{j}+1$ 名学生 $L_{j}, L_{j}+1, \ldots, R_{j}$ 组成。

对于一个由 $2$ 人以上的学生组成的组合，如果他们可以在组内互换礼物，而不会有人收到自己带来的礼物或者不满意的礼物，那么这个组合就是可行的。准确地说，由 $m$ 名 $(m \geq 2)$ 学生 $p_{1}, p_{2}, \ldots, p_{m}$ 组成的组合是可行的，当且仅当存在一个由 $p_{1}, p_{2}, \ldots, p_{m}$ 重新排列得到的数列 $q_{1}, q_{2}, \ldots, q_{m}$，这里 $q_{k}\ (1 \leq k \leq m)$ 表示给学生 $p_{k}$ 送礼物的学生的编号，满足以下的条件：

- 对于所有的 $k\ (1 \leq k \leq m)$ ，$p_{k} \neq q_{k}$。
- 对于所有的 $k\ (1 \leq k \leq m)$ ，$A_{q_{k}} \geq B_{p_{k}}$。

校长 K 想要让礼物交换会成功的，所以他想要知道这 $Q$ 个组合中，哪些是可行的。

给定学生的信息和组合的信息，对于每个组合，判断它是否是可行的，并编写一个程序来输出结果。

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

第二行包含 $N$ 个用空格分隔的整数 $A_1,A_2,\ldots ,A_N$。

第三行包含 $N$ 个用空格分隔的整数 $B_1,B_2,\ldots ,B_N$。

第四行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含两个整数 $L_i,R_i$。

outputFormat: 输出 $Q$ 行，第 $j\ (1 \leq j \leq Q)$ 行如果第 $j$ 个组合是可行的输出 Yes，否则输出 No。

hint:
**样例解释**

第一个组合是由 2 名学生 3,4 组成的。如果学生 3 收到学生 4 的礼物，学生 4 收到学生 3 的礼物，那么由于 $A_{3} \geq B_{4} 且 A_{4} \geq B_{3}$ ，所以两个学生都不会不满。因此，这个组合是可行的，所以在第一行输出 Yes。

第二个组合是由 3 名学生 1,2,3 组成的。由于 $A_{1}<B_{2}$ 且 $A_{3}<B_{2}$ ，所以学生 2 不管收到学生 1 还是学生 3 的礼物，都会感到不满。因此，这个组合不是可行的，所以在第二行输出 No。

第三个组合是由 4 名学生 1,2,3,4 组成的。例如，如果学生 1 收到学生 2 的礼物，学生 2 收到学生 4 的礼物，学生 3 收到学生 1 的礼物，学生 4 收到学生 3 的礼物，那么没有人会不满。因此，这个组合是可行的，所以在第三行输出 Yes。

这个样例满足子任务 1,2,4,7,8 的限制。

**数据范围**

对于所有输入数据，满足：

- $2 \leq N \leq 5\times 10^5$
- $1 \leq B_{i}<A_{i} \leq 2N\ (1 \leq i \leq N)$
- $A_{1}, B_{1}, A_{2}, B_{2}, \ldots, A_{N}, B_{N}$ 各不相同
- $1 \leq Q \leq 2\times 10^5$
- $1 \leq L_{j}<R_{j} \leq N\ (1 \leq j \leq Q)$

详细子任务附加限制及分值如下表所示。

|子任务|	附加限制|	分值|
|:-:|:-:|:-:|
|1|	$N \leq 10, Q \leq 10$|	4
|2|	$N \leq 18, Q \leq 10$|	5
|3|	$N \leq 10^5, A_{1} \geq 2 N-2, B_{1}=1, Q=1, L_{1}=1, R_{1}=N$|	10
|4|	$N \leq 10^5, Q \leq 10$|	31
|5|	$N \leq 10^5, A_{i}<A_{i+1}, B_{i}<B_{i+1}\ (1 \leq i \leq N-1)$|	8
|6|	$N \leq 10^5, A_{i}<A_{i+1}\ (1 \leq i \leq N-1)$|	12
|7|	$N \leq 10^5$|	18
|8|	无附加限制	|12


title: [JOI 2024 Final] 路网服务 2

description:
JOI 市有一个由 $H$ 条东西向的无限长道路和 $W$ 条南北向的道路组成的网格状道路网。从北边数第 $i\ (1 \leq i \leq H)$ 条的东西向的道路和从西边数第 $j\ (1 \leq j \leq W)$ 条的南北向的道路相交的地方称作交叉点 $(i, j)$。

现在，由于道路年久失修，一部分道路被封锁了。具体的封锁情况如下：

- 如果 $A_{i, j}=0\ (1 \leq i \leq H,1 \leq j \leq W-1)$，则从北边数第 $i$ 条的东西向的道路的，交叉点 $(i, j)$ 和交叉点 $(i, j+1)$ 之间的部分就是封锁的；如果 $A_{i, j}=1$ 则是可以通行的。
- 如果 $B_{i, j}=0\ (1 \leq j \leq W,1 \leq i \leq H-1)$ 从西边数第 $j$ 条的南北向的道路的，交叉点 $(i, j)$ 和交叉点 $(i+1, j)$ 之间的部分就是封锁的；如果 $B_{i, j}=1$ 就是可以通行的。
- 道路的其他部分，即 $H \times W$ 个交叉点外面的部分都是封锁的。

JOI 市的市长 K 理事长决定制定一个道路维修计划。维修计划由大于等于 $0$ 次维修构成。一次维修时选择一个满足的整数 $i\ (1 \leq i \leq H)$，然后进行以下的操作：

对于**所有**满足 $1 \leq j \leq W-1$ 的整数 $j$，如果从北边数第 $i$ 条的东西向的道路的，交叉点 $(i, j)$ 和交叉点 $(i, j+1)$ 之间的部分是封锁的话，将其变成可以通行的。这个过程总共需要 $C_{i}$ 天。其中，$C_{i}$ 为 $1$ 或 $2$。

维修计划里包含的多次维修不能同时进行。因此，维修计划的执行所需要的天数是维修计划里包含的所有维修所需要的天数的总和。

为了让市里的重要设施之间能够互相通行，K 理事长向你提出了 $Q$ 个问题。第 $k\ (1 \leq k \leq Q)$ 个问题是这样的：

是否存在一个维修计划，能够让 $T_{k}$ 个交叉点 $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ 之间，只通过可以通行的道路互相通行。如果存在的话，执行这样的维修计划最少需要多少天。

给定道路网的封锁情况，各条道路的维修所需要的天数，K 理事长的问题的内容，编写一个程序来回答 K 理事长的所有问题。

inputFormat:
第一行包含三个整数 $H,W,Q$。

接下来 $H$ 行，每行包含一个长度为 $W-1$ 的字符串，表示 $A_{i,1},A_{i,2},\ldots ,A_{i,W-1}$。

接下来 $H-1$ 行，每行包含一个长度为 $W$ 的字符串，表示 $B_{i,1},B_{i,2},\ldots ,B_{i,W}$。

接下来一行包含 $H$ 个用空格分隔的整数 $C_1,C_2,\ldots ,C_H$。

接下来有 $Q$ 个询问，每个询问用以下形式给出：

第一行包含一个整数 $T_k$。
接下来 $T_k$ 行每行包含两个整数 $X_{k,i},Y_{k,i}$。

outputFormat: 输出 $Q$ 行，第 $k$ 行 $(1 \leq k \leq Q)$ 里，如果存在一个维修计划，能够让 $T_{k}$ 个交叉点 $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ 之间互相通行，就输出执行这样的维修计划最少需要多少天。否则输出 $-1$。


title: 自由（Freedom）

background:
完全抽象的，只在数学中被允许的**无限**的「自由」。

****

「自由之光」，未知数的骑士 —— 知修。哪怕面对的是无限的绝望，他也能将其转变为无限的自由。

description:
给定一个 $n$ 个节点、$m$ 条边的**有向图**，节点和边都有权值，保证对于任意两个节点 $u,v$，从 $u$ 指向 $v$ 的边最多只有一条。

**路径** $P$ 是一个节点序列 $u_1,\cdots,u_k$，其中对于任意 $1\leq i < k$，$u_i$ 有指向 $u_{i+1}$ 的边（这条边记为 $e_i$）。则定义 $P$ 的**边权**是所有 $e_i$ 的权值的乘积，其**点权**是所有 $u_i$ 权值的和，其**长度**为 $k$。特别地，如果 $k=1$，则定义其**边权**为 $1$。

对于两条路径 $P_1,P_2$，长度分别为 $L_1,L_2$，包含的节点序列记为 $u_1,\cdots,u_{L_1}$ 和 $v_1,\cdots,v_{L_2}$。定义它们是**相同**的，当且仅当 $L_1=L_2$，且对于所有 $1\le i \le L_1$ 有 $u_i=v_i$。

给定正整数 $V$，请求出所有不相同的「**点权**为 $V$ 的路径」的**边权**之和。答案可能很大，请对 $998244353$ 取模后输出。

**题目的输入数据下载链接：[Link1](https://pan.baidu.com/s/1Gn0T5DNQBwC41oR-0hsh4A)，提取码：`92ih`；**
备用下载路径与操作方法：[Link2](https://www.luogu.com.cn/paste/xkqpnptw)。

inputFormat:
第一行一个正整数 $T$，表示测试点编号。

第二行三个正整数 $n,m,V$，意义如题目描述。
第三行 $n$ 个正整数 $a_1,\cdots,a_n$，$a_i$ 表示了编号为 $i$ 的节点的权值。
接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，表示编号为 $u_i$ 的点有一条权值为 $w_i$ 的边指向 $v_i$。

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


title: [语言月赛 202403] 星云

type: B

background: 你看，那一抹云，衬着星星，多美啊！

description: 定义星云数为位数不大于 $n$ 且各数位之和不超过 $k$ 的正整数，给定 $n,k$，求星云数的个数。

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

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

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

对于 $30\%$ 的数据，$n=1$。
对于 $100\%$ 的数据，$1 \leq n \leq 7$，$1 \leq k \leq 100$。


title: [省选联考 2024] 季风

background: 生活在二维平面的小 X 准备拜访小 Y，但由于气候的变化，平面上刮起了季风。小 X 想知道季风的影响下，TA 至少要多少天能够到达小 Y 的家，但小 X 也是第一次遇见这种怪事，所以请精通算法的你来帮忙。

description:
给定 $n,k,x,y$ 和 $2n$ 个整数 $x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}$。

找到最小的**非负整数** $m$，使得存在 $2m$ 个实数 $x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}'$ 满足以下条件，或报告不存在这样的 $m$：
- $\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})=x$；
- $\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})=y$；
- $\forall 0\leq i\leq m-1,|x_i'|+|y_i'|\leq k$。

特别地，$m=0$ 时，认为 $\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})$ 和 $\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})$ 均为 $0$。

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

对于每组测试数据，
- 第一行四个整数 $n,k,x,y$；
- 接下来 $n$ 行，第 $i$ 行两个整数 $x_{i-1},y_{i-1}$。

outputFormat: 对于每组测试数据输出一行一个整数，如果存在满足题意的 $m$，输出其最小可能值，否则输出 $-1$。

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

该组样例共有四组测试数据。
- 对于第一组测试数据，取 $m=1$，$(x_0',y_0')=(1,1)$ 满足条件，可以证明不存在更小的 $m$ 满足条件；
- 对于第二组测试数据，可以证明不存在任何非负整数 $m$ 满足条件；
- 对于第三组测试数据，取 $m=0$ 满足条件，可以证明不存在更小的 $m$ 满足条件。

**【样例 2】**

见附件中的 `wind2.in/ans`。

该组样例共有八十组测试数据，所有测试数据均满足 $n=1$，其中测试数据 $1\sim 20$ 满足特殊性质 A，$21\sim 40$ 满足特殊性质 B，$41\sim 60$ 满足特殊性质 C。

**【样例 3】**

见附件中的 `wind3.in/ans`。

该组样例共有六十组测试数据，所有测试数据均满足 $n=200$，其中测试数据 $1\sim 20$ 满足特殊性质 A，$21\sim 40$ 满足特殊性质 B。

**【子任务】**

设 $\sum n$ 为单个测试点内所有测试数据 $n$ 的和。对于所有测试数据：

- $1\leq T\leq 5\times 10^4$；
- $1\leq n\leq 10^5$，$1\leq \sum n \leq 10^6$；
- $0\leq |x|,|y|,|x_i|,|y_i|,k\leq 10^8$。

| 测试点编号 | $n\leq$ | $\sum n\leq$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $1$ | $300$ | A |
| $2$ | $1$ | $300$ | B |
| $3$ | $1$ | $300$ | C |
| $4$ | $1$ | $300$ | 无 |
| $5$ | $200$ | $5000$ | A |
| $6$ | $200$ | $5000$ | B |
| $7$ | $200$ | $5000$ | 无 |
| $8$ | $10^4$ | $10^5$ | A |
| $9$ | $10^4$ | $10^5$ | B |
| $10$ | $10^5$ | $10^6$ | 无 |

- 特殊性质 A：$\forall 0\leq i \leq n-1$，$|x_i|+|y_i| \leq k$；
- 特殊性质 B：$k=0$；
- 特殊性质 C：$x_0=y_0=0$。

**【提示】**

本题输入文件较大，请使用较为快速的输入方式。


title: [省选联考 2024] 魔法手杖

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

C 城是一座魔力之都，以最高的魔法师水平闻名。对于一名魔法师而言，最重要的固然是魔法手杖和镶嵌在手杖上的魔法水晶。

每个魔法手杖和魔法水晶都可以用**魔力值**来衡量其能力大小，一个魔法手杖的魔力值是镶嵌在其上的所有魔法水晶中魔力值的最小值。

小 $\omega$ 是 C 城的一名见习魔法师，他想加强他的魔法手杖。在加强之前，小 $\omega$ 的魔法手杖镶嵌着 $n$ 颗魔法水晶，它们的魔力值分别为 $a_1,a_2,\dots,a_n$。

小 $\omega$ 准备使用一次强力的秘术来加强他的手杖。这一次秘术中，他可以任意选择 $x$，然后将所有魔法水晶的魔力值由 $a_i$ 变为 $(a_i \oplus x)$，其中 $\oplus$ 表示按位异或。由于小 $\omega$ 能力有限，$a_1,a_2,\dots,a_n$ 和 $x$ 都是 $[0,2^k-1]$ 中的整数。

小 $\omega$ 还发现这个秘术可以定向加强。具体地，他可以花费 $b_i$ 的体力值对第 $i$ 个魔法水晶进行定向加强，将原本应变为 $(a_i \oplus x)$ 的魔力值变为 $(a_i+x)$。小 $\omega$ 能力有限，因此他定向加强所花费的体力值总和不能超过 $m$，且每个水晶只能被定向加强至多一次。

小 $\omega$ 想知道他在加强魔法手杖后，魔法手杖的魔力值最大能为多少，但他并不会算，所以请你来帮他计算。

**形式化的：** 给定 $a_1,a_2,\dots,a_n$ 以及 $b_1,b_2,\dots,b_n$，满足 $a_i \in [0,2^k-1]$ 以及 $b_i\geq 0$，你需要给出 $S \subseteq \{1,2,\dots,n\}$ 以及 $x \in [0,2^k-1]$ 满足以下条件：

- $\sum \limits_{i\in S} b_i\leq m$；
- 满足以上条件的前提下，最大化 $val(S,x)=\min(\min \limits_{i \in S}(a_i+x),\min \limits_{i \in U \backslash S}(a_i \oplus x))$ 的值。

你只需要给出最大的 $val(S,x)$ 的值即可。

inputFormat:
**本题有多组测试数据。** 输入的第一行包含两个整数 $c,T$，表示测试点编号与测试数据组数。样例中的 $c$ 表示该样例的数据范围与第 $c$ 个测试点的数据范围相同。

接下来依次给出每组输入数据，对于每组数据：
- 第一行三个整数 $n,m,k$；
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，分别表示每个魔法水晶的初始魔力值；
- 第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$，分别表示每个魔法水晶定向加强需要的体力值。

outputFormat: 对于每组测试数据输出一行一个整数表示小 $\omega$ 能获得魔法手杖魔力值的最大值。


title: [省选联考 2024] 虫洞

description:
E 国有 $n$ 个城市，编号为 $1$ 至 $n$。为了让城市之间的来往更加便利，E 国的交通部想在 $n$ 个城市间建造一些虫洞。每条虫洞是一条**单向**的从某个城市到另一个城市的通道。允许通道的起点和终点是同一个城市，也允许两个城市之间有多个虫洞连接。

为了区分虫洞的建造时间，交通部给每一条虫洞一个正整数的编号。

我们称一种虫洞的建造方案是**好的**，若它满足如下四个条件：

1. 存在一个非负整数 $d$ 使得每个城市恰好是 $d$ 条虫洞的起点，也恰好是 $d$ 条虫洞的终点。
2. 对于每个城市而言，在以它为起点的虫洞的编号中，$1$ 到 $d$ **恰好**各出现一次。
3. 对于每个城市而言，在以它为终点的虫洞的编号中，$1$ 到 $d$ **恰好**各出现一次。
4. 任意选取一个城市 $u$ 和正整数 $1\le j_1, j_2 \le d$。设从 $u$ 出发，先经过一次编号为 $j_1$ 的虫洞，再经过一次编号为 $j_2$ 的虫洞，到达城市 $v_1$。设从 $u$ 出发，先经过一次编号为 $j_2$ 的虫洞，再经过一次编号为 $j_1$ 的虫洞，到达城市 $v_2$。则条件 $v_1=v_2$ 必定满足。

特别地，不建造任何虫洞的方案也是好的。

现在，建造师已建造了 $mn$ 条虫洞，且给了它们 $1\sim m$ 的编号，**此时这样的建造方案是好的**。他想要新建造 $kn$ 条虫洞，并给它们 $(m+1)\sim (m+k)$ 的编号。他必须保证这 $(m + k)n$ 条虫洞形成的建造方案仍然是好的。他想知道有多少种新建造 $kn$ 条虫洞的方法，使得这 $(m + k)n$ 条虫洞形成的建造方案是好的。

由于答案很大，你只需要求出方案数除以 $998244353$ 的余数。

inputFormat:
输入的第一行四个非负整数 $c, n, m, k$，其中 $c$ 表示测试点编号。样例中的 $c$ 表示该样例的数据范围与第 $c$ 个测试点的数据范围相同。

接下来 $nm$ 行，每行三个正整数 $u,v,w$，表示一条编号为 $w$ 的，起点为 $u$ 号城市，终点为 $v$ 号城市的虫洞。

outputFormat: 输出一行整数，表示方案数除以 $998244353$ 的余数。

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

在该组样例中，已经建造的编号为 $1$ 的虫洞为 $1\to 2,2\to 1,3\to 4,4\to 3$。为了使 $8$ 条虫洞形成的建造方案是好的，新建造的编号为 $2$ 的虫洞可能有 $8$ 种情形：

1. $1\to 1, 2\to 2, 3\to 3, 4\to 4$
2. $1\to 1, 2\to 2, 3\to 4, 4\to 3$
3. $1\to 2, 2\to 1, 3\to 3, 4\to 4$
4. $1\to 2, 2\to 1, 3\to 4, 4\to 3$
5. $1\to 3, 2\to 4, 3\to 1, 4\to 2$
6. $1\to 3, 2\to 4, 3\to 2, 4\to 1$
7. $1\to 4, 2\to 3, 3\to 1, 4\to 2$
8. $1\to 4, 2\to 3, 3\to 2, 4\to 1$

**【样例 2】**

见附件中的 `wormhole2.in/ans`。

该样例的 $c = 2$，它满足第 2 个测试点的限制条件。

**【样例 3】**

见附件中的 `wormhole3.in/ans`。

该样例的 $c = 5$，它满足第 5 个测试点的限制条件。

**【样例 4】**

见附件中的 `wormhole4.in/ans`。

该样例的 $c = 7$，它满足第 7 个测试点的限制条件。

**【样例 5】**

见附件中的 `wormhole5.in/ans`。

该样例的 $c = 9$，它满足第 9 个测试点的限制条件。

**【样例 6】**

见附件中的 `wormhole6.in/ans`。

该样例的 $c = 11$，它满足第 11 个测试点的限制条件。

**【样例 7】**

见附件中的 `wormhole7.in/ans`。

该样例的 $c = 15$，它满足第 15 个测试点的限制条件。

**【样例 8】**

见附件中的 `wormhole8.in/ans`。

该样例的 $c = 17$，它满足第 17 个测试点的限制条件。

**【样例 9】**

见附件中的 `wormhole9.in/ans`。

该样例的 $c = 20$，它满足第 20 个测试点的限制条件。

**【样例 10】**

见附件中的 `wormhole10.in/ans`。

该样例的 $c = 22$，它满足第 22 个测试点的限制条件。

**【子任务】**

对于所有测试点，

- $1\le n \le 2\cdot 10^3$，$0 \le m \le 10^3$，$1 \le k \le 10^{15}$；
- $1 \le u,v \le n$，$1 \le w \le m$；
- 保证初始建造的 $mn$ 条虫洞构成一个号的建造方案。

| 测试点编号 | $n$ | $m$ | $k$ |
| :--: | :--: | :--: | :--: |
| $1\sim 4$ | $\le 5$ | $\le 3$ |$ \le 3$ |
| $5\sim 6$ | $\le 2\cdot 10^3$| $=0$ | $=1$|
| $7\sim 8$ | $\le 10^2$ | $=1$| $=1$ |
| $9\sim 10$ | $\le 10^2$ | $\le 10$ | $=1$|
| $11\sim 14$ | $\le 10^2$ | $\le 10$ | $\le 10^3$|
| $15\sim 16$ | $\le 10^2$ | $=0$ | $\le 10^{15}$ |
| $17\sim 19$ | $\le 10^2$ | $\le 10$ | $\le 10^{15}$ |
| $20\sim 21$ | $\le 2\cdot 10^3$ | $\le 10^3$ | $\le 10^2$ |
| $22\sim 25$ | $\le 2\cdot 10^3$ | $\le 10^3$ | $\le 10^{15}$ |

**【提示】**

本题部分测试点输入规模较大，我们推荐你使用较为快速的读入方式。


title: [省选联考 2024] 迷宫守卫

description:
Alice 拥有一座迷宫，这座迷宫可以抽象成一棵拥有 $2^n$ 个叶节点的满二叉树，总节点数目为 $(2^{n+1} - 1)$，依次编号为 $1 \sim (2^{n+1} - 1)$。其中编号为 $2^n \sim (2^{n+1} - 1)$ 的是叶节点，编号为 $1 \sim (2^n - 1)$ 的是非叶节点，且非叶节点 $1 \le u \le (2^n - 1)$ 的左儿子编号为 $2u$，右儿子编号为 $(2u + 1)$。

每个非叶节点都有一个石像守卫，初始时，所有石像守卫均在沉睡。唤醒 $u$ 点的石像守卫需要 $w_u$ 的魔力值。

每个叶节点都有一个符文，$v$ 点的符文记作 $q_v$。**保证 $q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}-1}$ 构成 $1 \sim 2^n$ 的排列**。

探险者初始时持有空序列 $Q$，从节点 $1$ 出发，按照如下规则行动：

- 到达叶节点 $v$ 时，将 $v$ 点的符文 $q_v$ 添加到序列 $Q$ 的末尾，然后返回父节点。
- 到达非叶节点 $u$ 时：
  - 若该点的石像守卫已被唤醒，则只能先前往左儿子，（从左儿子返回后）再前往右儿子，（从右儿子返回后）最后返回父节点。
  - 若该点的石像守卫在沉睡，可以在以下二者中任选其一：
    - 先前往左儿子，再前往右儿子，最后返回父节点。
    - 先前往右儿子，再前往左儿子，最后返回父节点。

返回节点 $1$ 时，探险结束。可以证明，探险者一定访问每个叶节点各一次，故此时 $Q$ 的长度为 $2^n$。

探险者 Bob 准备进入迷宫，他希望探险结束时的 $Q$ 的字典序越小越好，与之相对，Alice 希望 $Q$ 的字典序越大越好。

在 Bob 出发之前，Alice 可以选择一些魔力值花费之和不超过 $K$ 的石像守卫，并唤醒它们。Bob 出发时，他能够知道 Alice 唤醒了哪些神像。若**双方都采取最优策略**，求序列 $Q$ 的最终取值。

对于两个长度为 $2^n$ 的序列 $Q_1,Q_2$，称 $Q_1$ 字典序小于 $Q_2$ 当且仅当以下条件成立：

- $\exist i \in [1, 2^n]$ 满足以下两个条件：
  - $\forall 1 \le j < i，Q_{1,j} = Q_{2,j}$；
  - $Q_{1,i} < Q_{2,i}$。

inputFormat:
**本题有多组测试数据**。输入的第一行包含一个正整数 $T$，表示测试数据组数。

接下来依次 $T$ 组测试数据。对于每组测试数据：

- 第一行两个整数 $n,K$ 表示迷宫规模和 Alice 可用于唤醒石像守卫的魔力值上限。
- 第二行 $(2^n - 1)$ 个整数 $w_1,w_2,\cdots,w_{2^n-1}$ 表示唤醒各个石像守卫耗费的魔力值。
- 第三行 $2^n$ 个整数 $q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}-1}$ 表示各个叶节点上的符文。

outputFormat: 对于每组数据，输出一行 $2^n$ 个整数 $Q_1,Q_2,\cdots,Q_{2^n}$，表示双方都采取最优策略的情况下，序列 $Q$ 的最终取值。


title: [省选联考 2024] 重塑时光

description:
小 T 正在研究某段时间中所发生的事件。经观测，有 $n$ 个编号为 $1\sim n$ 的事件在这段时间内按顺序依次发生，第 $i$ 个发生的是事件 $p_i$。这个描述事件发生顺序的排列 $p$ 可称为这段时间的**时间线**。

突然，邪恶生物小 S 攻击了这条时间线，将这 $n$ 个事件的发生顺序 $p$ 变为了在所有长为 $n$ 的排列中等概率随机选取的一个排列。不仅如此，小 S 还用剪刀把时间线剪断，通过进行 $k$ 次操作，将排列 $p$ 分割成了 $(k + 1)$ 段。

具体而言，在小 S 进行第 $i$ 次操作时，排列 $p$ 和之前所有插入的剪断点构成了一个长度为 $(n + i - 1)$ 的序列。该序列包括所有相邻元素之间和序列开头、末尾处共有 $(n + i)$ 个插入位置。小 S 将从这些插入位置中等概率随机选取一个位置，插入一个新的剪断点。最后，小 S 从最终被插入的 $k$ 个剪断点处把序列剪开，将排列 $p$ 分割成了 $(k + 1)$ 段序列。这 $(k + 1)$ 段序列中可能有空序列。

为了拯救这条即将毁灭的时间线，小 T 决定把这 $(k + 1)$ 段序列按某种顺序重新拼接成一个长度为 $n$ 的排列，形成一条新的时间线。不过，由于事件之间存在一定的逻辑关系，事件的发生时间之间也存在一些先后顺序要求。经研究，共存在 $m$ 条先后顺序要求 $(u, v)$，要求事件 $u$ 的发生时间必须在事件 $v$ 之前。也就是说，$u$ 在时间线中的出现位置必须在 $v$ 之前。

请你设计程序，计算有多大的概率，存在至少一种重新排列这 $(k + 1)$ 段序列，并将其重新拼接为一条新的时间线的方案，能够使所有的 $m$ 条事件发生时间之间的先后顺序要求都得到满足。

为了避免精度误差，请你输出答案对 $10^9 +7$ 取模的结果。形式化地，可以证明答案可被表示为一最简分数 $\frac{p}{q}$，请你输出一个 $x$ 满足 $0 \le x < 10^9+7$ 且 $qx \equiv p \pmod {10^9+7}$。可以证明在题目条件下这样的 $x$ 总是存在。

inputFormat:
第一行三个整数 $n, m, k$，分别描述事件的个数，事件之间先后顺序的条数以及小 S 进行的剪断操作次数。

接下来 $m$ 行，每行两个整数 $u, v$，表示一条事件发生时间的先后顺序要求。

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


title: [省选联考 2024] 最长待机

description:
精灵程序员小 $\omega$ 和 小 $\aleph$ 拥有无限的寿命，因此在写代码之余，它们经常玩一些对抗游戏来打发时间。尽管如此，时间还是太多，于是它们发明了一款专用于消磨时间的游戏：最长待机。

为了了解最长待机的规则，首先要了解精灵们使用的编程语言 Sleep++ 的规则：

- 程序由 $n$ 个函数组成，第 $i(1 \le i\le n)$ 个函数具有种类 $e_i$ 和子函数编号序列 $Q_i = (Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i})$。$Q_i$ 可以为空，此时 $l_i$ 为 $0$。

- $n$ 以及所有的 $e_i$ 和 $Q_i$ 可以由程序员任意给出，但它们需要满足以下所有条件：
  - $n\ge 1$；
  - $\forall 1 \le i \le n$，$e_i \in \{0, 1\}$；
  - $\forall 1 \le i \le n$，$Q_i$ 中元素两两不同且均为 $[i + 1, n]$ 中的整数；
  - $\forall 2 \le j \le n$，**恰好有一个 $Q_i(1 \le i \le n)$ 包含了 $j$**。

- **调用**函数 $i(1 \le i \le n)$ 时，按顺序执行如下操作：
  - 若 $e_i = 0$，令变量 $r_i$ 为 $1$；否则程序员需要立即为 $r_i$ 输入一个**正整数值**。
  - 若 $Q_i$ 为空，程序等待 $r_i$ 秒；否则重复以下操作 $r_i$ 次：
    * 按顺序**调用**编号为 $Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i}$ 的函数。

- 若一个种类为 $1$ 的函数 $j$ 被调用多次，则其每次调用都需要输入 $r_j$。

- 我们认为，在函数调用中，除了“等待 $r$ 秒”之外的操作不消耗任何时间，即函数调用、运行和输入都在瞬间完成。因此，一个时刻内程序员可能输入多个数。

可以证明，调用任意一个 Sleep++ 程序的任意一个函数，无论如何设定输入，消耗的时间总是有限的。

“最长待机”的游戏规则如下：

- 小 $\omega$ 和 小 $\aleph$ 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。

- 在时刻 $0$，小 $\omega$ 和 小 $\aleph$ 同时调用自己选择的函数，游戏开始。

- 在时刻 $t$（$t \ge 0$），双方可以看到对方在时刻 $0$ 至 $(t - 1)$ 输入的所有数字，并相应调整自己在时刻 $t$ 输入的数字，但双方无法得知对方在时刻 $t$ 输入的数字。

- 函数调用先结束的一方输掉游戏，另一方胜利。两个调用同时结束算作平局。

小 $\omega$ 和 小 $\aleph$ 都是绝顶聪明的，在它们眼中，如果有一方存在必胜策略，那么这局游戏是不公平的。换言之，双方都不存在必胜策略的游戏是公平的。

小 $\omega$ 写了一个 $n$ 个函数的 Sleep++ 程序并进行了 $m$ 次操作，操作有以下两种：

- 操作一：给出 $k$，将 $e_k$ 修改为 $(1 - e_k)$；
- 操作二：给出 $k$，与小 $\aleph$ 玩一局“最长待机”，开始时小 $\omega$ 会调用自己的函数 $k$。

小 $\aleph$ 信奉极简主义，它希望对于每一局游戏设计出函数个数最少的程序，使得选择其中某个函数能让这局游戏是公平的。你能帮它求出最少所需的函数个数吗？

可以证明，小 $\aleph$ 总是能设计一个程序并选择其中一个函数，使得游戏是公平的。

inputFormat:
输入的第一行包含两个正整数 $n,m$，表示小 $\omega$ 的程序中函数的个数以及操作次数。

接下来 $n$ 行，第 $i$ 行若干个整数，描述小 $\omega$ 程序中的函数 $i$：

- 前两个整数 $e_i, l_i$ 表示函数种类和子函数编号序列长度；
- 接下来 $l_i$ 个整数 $Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i}$ 描述子函数编号序列。

接下来 $m$ 行，第 $j$ 行两个整数 $o_j, k_j$ 描述一次操作，其中 $o_j = 1$ 表示操作一，$o_j = 2$ 表示操作二。

outputFormat: 对于每个操作二输出一行一个整数，表示小 $\aleph$ 的程序中最少所需的函数个数。

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

- 对于前两次游戏，小 $\aleph$ 可以给出与小 $\omega$ 完全一致的程序并在游戏开始时调用函数 $1$。可以证明不存在函数个数更少的方案。

- 对于第三次游戏，小 $\aleph$ 可以给出一个仅包含一个种类为 $1$ 的函数的程序，并在游戏开始时调用函数 $1$。
  - 在时刻 $0$，小 $\omega$ 输入其程序中的 $r_2$，小 $\aleph$ 输入其程序中的 $r_1$。
    * 注意：$r$ 变量在小 $\omega$ 和小 $\aleph$ 的程序之间是独立的，不会互相影响。
  - 输入完成后，小 $\omega$ 的程序在时刻 $(r_2 +1)$ 结束，小 $\aleph$ 的程序在时刻 $r_1$ 结束。
  - 由于两人在时刻 $0$ 互不知道对方的决策，不能保证 $(r_2 + 1)$ 和 $r_1$ 的大小关系，故双方均不存在必胜策略，这局游戏是公平的。

**【样例 2】**

见附件中的 `sleep2.in/ans`。

该组数据满足特殊性质 AD。

**【样例 3】**

见附件中的 `sleep3.in/ans`。

该组数据满足特殊性质 BD。

**【样例 4】**

见附件中的 `sleep4.in/ans`。

该组数据满足特殊性质 D。

**【样例 5】**

见附件中的 `sleep5.in/ans`。

该组数据满足特殊性质 C。

**【子任务】**

对于所有测试数据，

- $1 \le n \le 5\times 10^5$，$1 \le m \le 2\times 10^5$；
- $\forall 1 \le i \le n$，$e_i\in \{0, 1\}$，$0 \le l_i <n$；
- $\forall 1 \le i \le n,1 \le j \le l_i$，$i < Q_{i,j} \le n$；
- $\forall 1 \le i \le n, 1 \le p < q \le l_i$，$Q_{i,p}\neq Q_{i,q}$；
- $\forall 2 \le j \le n$，恰好有一个 $Q_i(1 \le i \le n)$ 包含了 $j$；
- $\forall 1 \le j \le m$，$1 \le o_j \le 2$，$1 \le k_j \le n$。

| 测试点编号 | $n \le $ | $m\le $| 特殊性质 |
|:--:|:--:|:--:|:--:|
| $1\sim 2$ | $3$ | $24$ | 无 |
| $3$ | $80$ | $400$ | AD |
| $4$ | $80$ | $400$ | BD |
| $5\sim 6$ | $80$ | $400$ | D |
| $7$ | $3\times 10^5$ | $10^5$ | AD |
| $8$ | $3\times 10^5$ | $10^5$ | BD |
| $9\sim 10$ | $3\times 10^5$ | $10^5$ | D |
| $11$ | $3\times 10^5$ | $10^5$ | A |
| $12$ | $3\times 10^5$ | $10^5$ | BC |
| $13$ | $3\times 10^5$ | $10^5$ | B |
| $14\sim 15$ | $3\times 10^5$ | $10^5$ | C |
| $16\sim 17$ | $3\times 10^5$ | $10^5$ | 无 |
| $18\sim 19$ | $5\times 10^5$ | $2\times 10^5$ | A |
| $20$ | $5\times 10^5$ | $2\times 10^5$ | BC |
| $21$ | $5\times 10^5$ | $2\times 10^5$ | B |
| $22\sim 23$ | $5\times 10^5$ | $2\times 10^5$ | C |
| $24\sim 25$ | $5\times 10^5$ | $2\times 10^5$ | 无 |

特殊性质 A：保证

- 任意时刻 $e_1$ 均为 $0$；
- $\forall 2\le i \le n$，$l_i \le 1$；
- 操作二的 $k$ 均为 $1$。

特殊性质 B：保证

- 操作二的 $k$ 满足当时的 $e_k$ 为 $1$。

特殊性质 C：保证

- $\forall 2\le i \le n$，$i \in Q_{\lfloor \frac{i}{2}\rfloor}$；
- $\forall 1 \le i \le n$，序列 $Q_i$ 单调递增。

特殊性质 D：保证

- 操作二不超过 $10$ 个；
- 操作二的 $k$ 均为 $1$。


title: [GESP样题 四级] 绝对素数

description: 如果一个两位数是素数，且它的数字位置经过对换后仍为素数，则称为绝对素数，例如 $13$。给定两个正整数 $A, B$，请求出大于等于 $A$、小于等于 $B$ 的所有绝对素数。

inputFormat: 输入 $1$ 行，包含两个正整数 $A$ 和 $B$。保证 $10<A<B<100$。

outputFormat: 若干行，每行一个绝对素数，从小到大输出。


title: [GESP样题 四级] 填幻方

description:
在一个 $N\times N$ 的正方形网格中，每个格子分别填上从 1 到 $N×N$ 的正整数，使得正方形中任一行、任一列及对角线的几个数之和都相等，则这种正方形图案就称为“幻方”（输出样例中展示了一个 $3×3$ 的幻方）。我国古代称为“河图”、“洛书”，又叫“纵横图”。

幻方看似神奇，但当 $N$ 为奇数时有很方便的填法：
1. 一开始正方形中没有填任何数字。首先，在第一行的正中央填上 $1$。
2. 从上次填数字的位置向上移动一格，如果已经在第一行，则移到同一列的最后一行；再向右移动一格，如果已经在最右一列，则移动至同一行的第一列。如果移动后的位置没有填数字，则把上次填写的数字的下一个数字填到这个位置。
3. 如果第 2 步填写失败，则从上次填数字的位置向下移动一格，如果已经在最下一行，则移到同一列的第一行。这个位置一定是空的（这可太神奇了！）。把上次填写的数字的下一个数字填到这个位置。
4. 重复 2、3 步骤，直到所有格子都被填满，幻方就完成了！

快来编写一个程序，按上述规则，制作一个 $N\times N$ 的幻方吧。

inputFormat: 输入为一个正奇数 $N$，保证 $3 \leq N \leq 21$。

outputFormat: 输出 $N$ 行，每行 $N$ 个空格分隔的正整数，内容为 $N×N$ 的幻方。


title: [COCI 2023/2024 #3] Eurokod

background: **译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T1「[Eurokod](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

description:
Eurokod，全球美丽与高可读性代码竞赛，今年第一次举行！

共有 $n$ 名参赛者参加了竞赛，他们被依次编号为 $1\sim n$。每名参赛者已经编写了一份代码。

他们的代码将由一组计算机科学家进行评估。这组计算机科学家分为组长与其他成员，组长将用一种方法给出评分，其他成员则用另一种方法给出评分。

**组长评分：**

组长按照他的想法，将代码按照美丽程度从大到小排序。最美丽的代码将获得 $n$ 分，其他代码依次比上一名少一分。

**其他成员评分：**

每名其他成员将投票选出自己认为最美丽的代码。在所有其他成员投票后，所有代码按照投票人数从高到低排序。得票数最多的代码将获得 $n$ 分，其他代码依次比上一名少一分。

**总分：**

一份代码的总分由组长评分与其他成员评分加和得到。

你的任务是按照得分降序输出代码的编号。如果两份代码得分相同，其他成员评分高者列前。

inputFormat:
第一行包含一个整数 $n$（$1 \le n \le 50$），表示参赛者的数目。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le n$），第 $i$ 个整数表示组长评为第 $i$ 名代码的编号。按照美丽程度从高到低给出。保证 $1\sim n$ 恰好出现一次。

第三行包含 $n$ 个整数 $b_i$（$0 \le b_i \le 200$），第 $i$ 个整数表示第 $i$ 份代码收获的其他成员票数。保证没有两份代码获得了同样的票数。

outputFormat:
输出 $n$ 行，按照分数降序输出代码编号。

每一行的输出应当符合 `[rank]. Kod[label] ([number of points])` 的格式。其中，`[rank]` 表示代码的排名，`[label]` 是用含前导零的两位十位数表示的代码编号，`[number of points]` 是代码获得的总分。

例如，$3$ 号代码以 $12$ 分总分获得第一名，那么你应该在第一行输出 `1. Kod03 (12)`。

hint:
### 样例解释 1

Kod03 和 Kod02 得分相同，但 Kod03 从其他成员处获得了更高的分数，所以 Kod03 排名列前。

### 样例解释 2

组长给予 Kod05 最高的排名，它因此获得 $n=5$ 分。

### 子任务

| Subtask | Points | Constraints |
|:--:|:--:|:--:|
| 1|17|对于每一份代码，其他成员投的票数与其他成员评分在数值上相同。同时，没有两份代码总分相同。|
|2|19|没有两份代码总分相同。|
|3|14|无特殊限制。|


title: [COCI 2023/2024 #3] Vrsar

background: **译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T2「[Vrsar](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

description:
Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。

Iva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsar 停留的每一天都以溜冰度过。在第 $i$ 天的开始，他们距离海岸 $a_i$ 米。当滑雪场开放的同时，他们开始他们的溜冰之旅。他们需要走去滑雪场，走路的速度为每分钟 $1$ 米。

他们的身体非常好，因此他们不需要额外时间来爬山。一旦他们到达山顶的滑雪场，他们可以滑任意长的时间，直到滑雪场关闭。然而，下山并不像上山一样容易，因为下雨，山路非常湿滑，他们需要消耗 $s_i$ 的时间走下第 $i$ 座山。从一座山上下来后，他们可以前往另一座山。

Iva 和 Mia 想知道每天他们最长可以滑多久的雪。每天他们可以访问任意多座滑雪场。因为他们想用尽可能多的时间滑雪，用尽可能少的时间计算，所以他们向你寻求帮助。帮助他们解决这个问题。

请注意：如果 Iva 和 Mia 早晨出发的位置就有一座山，他们在山脚。

inputFormat:
第一行包含两个整数 $n,m$（$1 \le n,m \le 10^5$），表示山的数量和天数。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,t_i,s_i$（$0 \le x_i,t_i,s_i \le 10^9$），分别表示第 $i$ 座山到海岸的距离、滑雪场的关闭时间和下山所需的时间。

第三行包含 $m$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示 Iva 和 Mia 第 $i$ 天出发时到海岸的距离。

outputFormat: 输出一行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 天 Iva 和 Mia 可以滑雪的最长时间。

hint:
### 样例解释 1

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

Iva 和 Mia 在位置 $1$ 出发，走 $2$ 分钟到位置 $3$ 的山，并滑雪 $5$ 分钟。接着花费 $0$ 分钟时间下山，继续走 $3$ 分钟时间到位置 $6$ 山上的滑雪场，滑雪 $1$ 分钟。

他们一共滑雪 $6$ 分钟。

### 子任务

| Subtask | Points | Constraints |
| :--: | :--: | :--: |
| 1 | 8 | $n,m \le 10$ |
| 2 | 17 | $m=1,a_1=0$ |
| 3 | 19 | $n,m \le 1000$ |
| 4 |  26 | 无特殊限制。|


title: [COCI 2023/2024 #3] Milano C.le

background: **译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T3「[Milano C.le](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

description:
Silvia 目前在米兰中央车站，她注意到车站有很多站台。她觉得站台数量太多了，所以她打算统计有多少真正需要的站台。

Silvia 同样注意到这个车站的一个有趣的事实：出发和到达时刻表每两天就会重复一次，并且时刻表满足所有 $n$ 列火车在一天到达车站，并且在另一天离开。注意按这种方式，没有火车会在所有火车都到达之前离开。

车站的站台足够长，可以满足所有 $n$ 列火车都能在同一站台停成一列。然而，如果火车 $x$ 先进入站台，然后 $y$ 进入同一站台，则火车 $x$ 不可以在火车 $y$ 离开站台之前离开。

Silvia 想知道在不存在由于排在某列火车前面的火车还没离开导致这列火车无法离开的情况下，最少需要多少站台可以使所有火车都停下。

inputFormat:
第一行一个整数 $n\ (1\le n\le 2\cdot 10^5)$，表示火车的数量。

第二行包含 $n$ 个整数 $a_i\ (1\le a_i\le n,\forall i\neq j,a_i\neq a_j)$，表示第 $i$ 列火车在第一天第 $a_i$ 个到达车站。序列 $(a_i)$ 是一个排列。

第三行包含 $n$ 个整数 $b_i\ (1\le b_i\le n,\forall i\neq j,b_i\neq b_j)$，表示第 $i$ 列火车在第二天第 $b_i$ 个离开车站。序列 $(b_i)$ 是一个排列。

outputFormat: 输出一行一个整数，表示最少需要多少个站台。

hint:
### 样例解释 2

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

上图展示了一个样例二中站台上可能的列车调度情况。列车上 $(i:a_i/b_i)$ 的标签表示第 $i$ 列火车在第一天第 $a_i$ 个到达车站，然后在第二天第 $b_i$ 个离开车站。火车 $(2:1/2)$ 不能比火车 $(4:5/1)$ 更早离开车站。

### 样例解释 3

所有火车均可在同一站台排成一列，没有任何问题。

### 子任务

| 子任务 |               附加限制               | 分值 |
| :--------: | :----------------------------------: | :--: |
|    $1$     |              $n\le 10$               | $21$ |
|    $2$     | 最小所需站台数要么是 $1$，要么是 $2$ | $18$ |
|    $3$     |            $n\le 1\ 000$             | $31$ |
|    $4$     |              无附加限制              | $40$ |


title: [COCI 2023/2024 #3] Restorani

background: **译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T4「[Restorani](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

description:
来到塞格德，Malnar 先生像通常一样，必须了解当地文化，品尝所有传统餐点、特色美食和当地饮料。

我们可以把塞格德想象成由 $n - 1$ 条双向道路连接的 $n$ 个景点，这些景点的编号从 $1$ 到 $n$。这样，每一对景点之间都有一条路径。令人惊奇的是，Malnar 先生走过每条道路正好需要一分钟。在景点行走的时间可以忽略不计。

Malnar 先生有一份他想去的 $m$ 家餐厅的清单。它由 $m$ 个正整数组成，其中第 $i$ 个数表示第 $i$ 个餐厅在哪个景点附近。

一个问题是 Malnar 先生在餐厅用餐后，必须马上去甜品店吃冰淇淋。另一个问题是，他拒绝两次光顾同一家甜品店。

幸运的是他有备而来，因为他知道 $m$ 家甜品店，这些甜品店的位置是由 $m$ 个正整数组成的列表，其中第 $i$ 个数字代表第 $i$ 家甜品店在这个景点附近。

Malnar 先生旅途劳累，不想走更多的路，因此他请你计算一下他需要走多少路，并提供去餐厅和甜品店的顺序，这样他就可以在没有帮助的情况下穿梭于餐厅和甜品店之间了。

Malnar 先生目前在景点 $1$，并且必须在最后回到景点 $1$。

inputFormat:
第一行包含整数 $n$ 和 $m\ (1\le m\le n\le 3\cdot 10^5)$，分别表示景点个数和餐厅/甜品店个数。

第二行包含 $m$ 个整数 $a_i\ (1\le a_i\le n,\forall i\neq j,a_i\neq a_j)$，表示餐厅清单。

第二行包含 $m$ 个整数 $b_i\ (1\le b_i\le n,\forall i\neq j,b_i\neq b_j)$，表示甜品店清单。

接下来 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i\ (1\le x_i,y_i\le n)$，表示景点 $x_i$ 和 $y_i$ 之间有一条道路。

outputFormat:
第一行输出 $t$，表示 Malnar 先生为了去所有餐厅和甜品店，并最后返回景点 $1$ 的最短用时。

第二行输出 $2m$ 个整数 $v_i$，表示去餐厅和甜品店的顺序。

在奇数位置的数表示餐馆，这些数必须组成前 $m$ 个正整数的排列。在偶数位置的数表示甜品店，这些数也必须组成前 $m$ 个正整数的排列。

按上述顺序去景点并返回开始位置所经历的时间必须为最短时间 $t$。

如果有多个最优顺序，输出任意一个均可。

hint:
### 样例解释 1

Malnar 先生首先走一分钟前往唯一在景点 $2$ 的餐厅，然后走两分钟到唯一在景点 $3$ 的甜品店，然后花一分钟走回景点 $1$。Malnar 先生总共会花 $1+2+1=4$ 分钟。

### 样例解释 2

Malnar 先生按如下顺序去餐厅和甜品店：在景点 $4$ 的餐厅（$2$ 分钟），在景点 $4$ 的甜品店（$0$ 分钟），在景点 $6$ 的餐厅（$3$ 分钟），在景点 $5$ 的甜品店（$1$ 分钟），在景点 $3$ 的餐厅（$1$ 分钟），在景点 $9$ 的甜品店（$3$ 分钟），在景点 $2$ 的餐厅（$3$ 分钟），在景点 $8$ 的甜品店（$3$ 分钟）。在景点 $8$ 处的甜品店吃完冰淇淋后，他返回景点 $1$（$2$ 分钟）。Malnar 先生一共走了 $2+0+3+1+1+3+3+3+2=18$ 分钟。

### 样例解释 3

Malnar 先生按如下顺序去餐厅和甜品店：在景点 $7$ 的餐厅（$6$ 分钟），在景点 $9$ 的甜品店（$2$ 分钟），在景点 $8$ 的餐厅（$1$ 分钟），在景点 $10$ 的甜品店（$2$ 分钟），在景点 $6$ 的餐厅（$4$ 分钟），在景点 $4$ 的甜品店（$2$ 分钟），在景点 $5$ 的餐厅（$1$ 分钟），在景点 $2$ 的甜品店（$3$ 分钟），在景点 $3$ 的餐厅（$1$ 分钟），在景点 $1$ 的甜品店（$2$ 分钟）。在吃完最后的冰淇淋后，他已经在景点 $1$ 所以他不会移动。Malnar 先生一共走了 $24$ 分钟。

### 子任务

| 子任务编号 |                附加限制                | 分值 |
| :--------: | :------------------------------------: | :--: |
|    $1$     |         $n\le 5\ 000,m\le 10$          | $18$ |
|    $2$     | $\forall i=1,\ldots,n-1,x_i=i,y_i=i+1$ | $18$ |
|    $3$     |             $n\le 5\ 000$              | $27$ |
|    $4$     |               无附加限制               | $37$ |


title: [COCI 2023/2024 #3] Slučajna Cesta

background: **译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T5「[Slučajna Cesta](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

description:
Vito 住在一个有 $n$ 个公园的城市，这些公园编号为 $1$ 到 $n$。这些公园被 $n-1$ 条道路相连，满足任意两公园之间都存在一条路径。每个公园均有一个美丽值，第 $i$ 个公园的美丽值为 $v_i$。

昨晚 Vito 决定在城市中走走，在他游览完一个公园后，他会等概率随机选择一条路，并游览这条路通往的公园。但在出发前，他透过摩天大楼的窗户看到，每条路上都有一条蓝蛇或红蛇。蓝蛇会攻击所有从编号较小的公园前往编号较大的公园的人，红蛇会攻击所有从编号较大的公园前往编号较小的公园的人。由于 Vito 不想被蛇攻击，他决定改变计划，在随机选择道路时只考虑不会被蛇攻击的道路。因为他喜欢长距离行走，所以在至少有一条路他可以安全通过之前，他不会停下脚步。

当 Vito 下楼时，他完全忘记了哪条路上有红蛇或蓝蛇，于是他想知道：「如果每条路上有蓝蛇或红蛇的概率相同，那么我从第 $i$ 个公园开始的路线的美感的期望是多少？」

一条路线的美感是在这条路线上经过的公园的美丽值的和。路线美感的期望定义为对于所有可能的路线，路线的美感乘以 Vito 按这条路线走的概率的乘积之和。

inputFormat:
第一行一个整数 $n\ (2\le n\le 10^6)$，表示公园数量。

第二行有 $n-1$ 个整数 $p_i\ (1\le p_i<i)$，表示第 $i+1$ 个公园和第 $p_i$ 个公园之间有一条道路。

第三行 $n$ 个整数 $v_i\ (0\le v_i\le 10^6)$，表示第 $i$ 个公园的美丽值。

outputFormat: 第 $i$ 行输出 Vito 从第 $i$ 个公园开始的路线的美感的期望。如果这个值为 $\frac{a}{b}$（$a,b$ 为整数），则输出 $ab^{-1} \pmod{10^9+7}$，其中 $b^{-1}$ 是 $b$ 在模 $10^9+7$ 意义下的逆元。


title: 『STA - R7』Divide and Merge Game

description:
给定两个正整数 $n, k(2 \le k \le n)$，Alice 和 Bob 将进行如下游戏：

- Alice 需要给出一个长度为 $k$ 的**正整数**序列 $a$，满足 $\sum\limits_{i = 1}^{k} a_i = n$。

- Bob 需要尝试给出一个不小于 $2$ 的正整数 $m$，满足可以将 Alice 给出的正整数序列 $a$ 划分为 $m$ 个**非空可重**集合，且其元素之和均相同。若 Bob 可以给出一个符合条件的正整数则 Bob 胜利，反之 Alice 胜利。

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

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

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

对于每组询问：一行两个正整数 $n, k$，含义见【题目描述】。

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

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

对于第一组测试数据，Alice 只能给出正整数序列 $\left\{1,1,1,1\right\}$，那么此时 Bob 给出 $m = 4$，并将这个正整数序列划分为 $\left\{\left\{1\right\},\left\{1\right\},\left\{1\right\},\left\{1\right\}\right\}$。Bob 也可以给出 $m = 2$，并将正整数序列划分为 $\left\{\left\{1, 1\right\}, \left\{1, 1\right\}\right\}$ 进而得到两个元素之和均为 $2$ 的集合， 同样满足要求。

对于第二组测试数据，Alice 可以给出正整数序列 $\left\{3, 2, 3\right\}$，可以证明此时 Bob 不存在符合要求的划分方案，因此 Alice 胜利。

**【数据范围】**

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

对于 $100\%$ 的数据：

- $1 \le T \le 2 \times 10^5$；
- $2 \le k \le n \le 10^8$。

具体部分分分配如下：

|Subtask 编号|数据范围|分值|
|:--------:|:--------:|:--------:|
|1|$n \le 10$|$16$|
|2|$k^2 \le n$|$27$|
|3|$2 \nmid n$|$27$|
|4|无特殊限制|$30$|


title: [Opoi 2024] 二十六点

background:
二十六点：

> 。 。 。 。 。 。 。 。 。 。 。 。 。
>
> 。 。 。 。 。 。 。 。 。 。 。 。 。

凑二十六点真好玩，而为了凑四道题，就有了这道权值只有 $26$ 种的凑数题。

description:
给你一棵有 $n$ 个结点的以 $1$ 为根的树 $T$，第 $i$ 个结点有一个颜色 $c_i$，${\tt a} \le c_i \le {\tt z}$，和一个值 $P_i$。

对于每一个点 $x$，**从它到它子树中每一个点**（注意顺序是从它本身到子树中的点）都有一条路径，一共有子树的大小条路径。

现在忽略掉这些路径中的第 $2$ 到第 $P_x$ 个的点，特别地，若 $P_x = 1$ 则不忽略任何点。将忽略后的路径当作一个序列，序列中每个点的权值为路径上点的 $c_i$，求**每一个点的所有序列最长不下降子序列长度的最大值**。

注: 若有路径 $j$ 上的节点数 $len_j < P_x$，则相当于忽略这条路径上除第一个点外的所有点。

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

第二行 $n$ 个整数 $P_i$。

第三行 $n$ 个小写字母 $c_i$，**字符与字符间没有空格**。

接下来 $n - 1$ 行，描述树 $T$，每行两个整数 $u,v$，表示 $u,v$ 存在一条边。

行末可能有多余空格（慎用 `getchar()`）。

outputFormat: 输出 $n$ 行，表示每一个点的答案，按照编号从小到大输出。


title: [Opoi 2024] 热核武器

background:
跳蚤国与蛐蛐国正在激战！

![level](https://tse3-mm.cn.bing.net/th/id/OIP-C.ewEm2cQO23KvtiSwFQMFGQHaE8?w=293&h=195&c=7&r=0&o=5&pid=1.7)

上面是战术核显卡，与题目没有关联。

description:
跳蚤国的国土可以看作平面直角坐标系。

跳蚤国有 $N+1$ 座城市，有 $1$ 座是首都，位于 $(0,0)$，另 $N$ 座是普通城市，在这里假设首都为 $0$ 号城市，其他城市编号为 $1$ 至 $N$，对于每一座普通城市，位于 $(x_i,y_i)$。

由于跳蚤国财力有限，对于每一个不是首都的城市 $i$，它会选择一个城市 $j$ 修建一条双向公路。令 $dis(x,y)$ 为 $x$，$y$ 城市的欧几里得距离，**则对于每一个不是首都的城市 $i$，它所对应的 $j$ 则是满足 $dis(j,0) \le dis(i,0)$ ，$j \ne i$ 的所有点中 $dis(i,j)$ 最小的点，如有多个合法 $j$，取其中编号最小的一个。**

定义一座城市的 $\gamma$ 值为这个城市走到首都所需要的最小道路数 $+1$，**如果走不到首都，设 $\gamma$ 值为 $0$。**

蛐蛐国要对跳蚤国进行战术核显卡打击，这次行动分为两个组：洛伦兹组和安培组。每个组都要对跳蚤国的部分城市进行打击，其中两个组需要恰好把跳蚤国每个城市打击一遍。

对于这两个组来说，名利是最重要的，而蛐蛐国的评功标准是按照本次行动所打击城市的 $\gamma$ 值和。所以你需要求出：有没有一种划分方式使得洛伦兹组和安培组分别的打击城市的 $\gamma$ 值和相等，可以，输出 ```Yes```，否则输出 ```No``` 。

inputFormat:
第 $1$ 行输入一个整数 $N$，表示跳蚤国普通城市的数目。

接下来第 $2 \sim N+1$ 行，第 $i+1$ 行输入两个整数，表示第 $i$ 座城市的横纵坐标 $(x_i,y_i)$。

outputFormat: 一行一个字符串，```Yes``` 或者 ```No```。表示是否会有一种方法使得洛伦兹组和安培组分别的打击城市的 $\gamma$ 值和相等。

hint:
### 样例解释

这幅图是长这样的：

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

对于 $C1$，$C0$ 和 $C2$ 满足 $dis(j,0) \le dis(C1,0)$，但是 $C0$ 离 $C1$ 距离更近，添加边 $(C1,C0)$。

对于 $C2$，只有 $C0$ 满足 $dis(j,0) \le dis(C2,0)$，添加边 $(C2,C0)$。

对于 $C3$，$C0$，$C1$ 和 $C2$ 满足 $dis(j,0) \le dis(C3,0)$，但是 $C2$ 离 $C3$ 距离最近，因此添加边 $(C3,C2)$。**注意这里是因为在 $C3$ 处考虑时，最优点为 $C2$，所以 $C3$ 才向 $C2$ 修建了一条公路，和公路 $(C2,C0)$ 完全独立。**

对于 $C4$，其他所有点都满足 $dis(j,0) \le dis(C4,0)$，但是 $C0$ 离 $C4$ 距离最近，添加边 $(C4,C0)$。

得到下面的表：

| 城市编号 | $\gamma$ 值 |
| :-----------: | :-----------: |
| 0 | 1 |
| 1 | 2 |
| 2 | 2 |
| 3 | 3 |
| 4 | 2 |

所以把 $0,1,2$ 分给洛伦兹组，$3,4$ 分给安培组即可。

### 数据范围

$1 \le N \le 500$，$-10^6 \le x_i,y_i \le 10^6$。

### 特殊说明

由于本题输出只有 ```Yes``` 和 ```No```，所以本题采用最小分值评测法，即取所有测试点的得分最小值作为结果。


title: [COCI 2023/2024 #4] Bingo

background: **译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T1「[Bingo](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**

description:
现在是游玩 Bingo 的时间！

想要玩 Bingo 游戏，你需要一名游戏主持人和一个装有 90 个球的滚轮。滚轮中的球被编号为 $1\sim 90$，每个数字编号写在恰好一个球上。

在游戏开始前，主持人向 $n$ 名玩家每人发放一块 $5\times 5$ 的格板，每格包含一个 $1$ 到 $90$ 范围内的整数。一块格板上的数字互不相同，每名玩家的格板互不相同。

所有的玩家都拿到格板后，游戏开始。

主持人开始从滚轮中取出球。取出编号为 $x_i$ 的球后，主持人向所有玩家宣布编号，并将球放到一边。所有玩家会检查自己的格板，如果格板上有取出的球的编号，他们会将这个数从格板上划去。

当一名玩家划去了行、列、主对角线或从对角线上全部的 5 个数字，这名玩家将喊出 `Bingo!`。此时，游戏结束，这名玩家赢得游戏。

为了让游戏更加有趣，主持人决定引入一条额外规则。在任何人被允许喊出 `Bingo!` 前，主持人将先取出 $m$ 个球。（即使玩家已经划去了连续的 5 个数，也必须等到 $m$ 个球取出后才能喊出 `Bingo!`）

但是，当主持人取出第 $m$ 个球的瞬间，场上发生了一阵骚动！所有的玩家都喊出了 `Bingo!`。

主持人不知道该相信谁。为了解决这个状况，他向你寻求帮助。请计算出 $m$ 个球被取出后，有多少玩家可以喊出 `Bingo!`。

inputFormat:
输入的第一行为一个整数 $n$（$1 \le n \le 50$），表示玩家的数目。

接下来 $n\times 6$ 行：

- 第一行包含一个长度不超过 $20$ 的字符串，仅由英文小写字母组成，表示玩家的姓名。没有两个玩家姓名相同。
- 接下来 $5$ 行，每行包含 $5$ 个 $1\sim90$ 的整数，描述了这名玩家的格板。每块格板上数字不同。

接下来一行包含一个整数 $m$（$1 \le m \le 90$），表示主持人将取出的球的数目。

接下来一行包含 $m$ 个 $1\sim 90$ 范围内的整数，表示主持人从滚轮中取出的球的编号。每个数字最多出现一次。

outputFormat:
第一行输出一个整数 $k$，表示可以喊出 `Bingo!` 的玩家数目。

接下来 $k$ 行，输出他们的名字。按照输入的顺序输出。

hint:
### 样例解释 1

`babylasagna` 在第一行实现了 `Bingo!`。

`nataliebalmix` 在第一列实现了 `Bingo!`。

`lettri` 在左下角到右上角的从对角线实现了 `Bingo!`。

### 样例解释 2

只取出了 4 个球，没有人能划去 5 个数。

### 子任务

| Subtask | Points | Constraints |
| :--: | :--: | :--: |
| 1 | 12 | 只有一个玩家，也就是说，$n=1$ |
| 2 | 22 | 最多只有一个玩家喊出 `Bingo!` |
| 3 | 16 | 无额外限制 |


title: [COCI 2023/2024 #4] Knjige

background: **译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T2「[Knjige](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**

description:
Marko 正在 Interliber 图书集市，他一共购买了 $n$ 本书，第 $i$ 本书的吸引力为 $k_i$。Marko 按照吸引力从左到右单调不减的方式，将所有的书放在了书架上。

距离 Interliber 已经过去了很久，但 Marko 最近才找到时间阅读这些书。他一共花费了 $t$ 分钟阅读。

对于每一本书，他可以花费 $a$ 分钟完整阅读，也可以花费 $b$ 分钟，只通过封面了解内容。

他将从最左侧的书籍开始阅读，当他读完当前的书后（完整阅读或通过目录了解内容），他开始阅读紧靠右侧的下一本书。Marko 的灵感值与他完整阅读的书的吸引力之和相等。$t$ 分钟后，Marko 的灵感值最大是多少？

注意：如果 Marko 开始阅读一本书，但是没有在第 $t$ 分钟结束前读完，这本书将不会对 Marko 的灵感值产生贡献。

inputFormat:
输入的第一行包含四个整数 $n,t,a,b$（$1 \le n \le 2\cdot 10^5$，$1 \le t \le 10^9$，$1\le b < a \le 10^9$），分别表示书的数目，Marko 阅读的时间，完整阅读和阅读封面所需要的时间。

输入的第二行包含 $n$ 个整数 $k_i$（$1 \le k_i \le 10^9$，$k_i \le k_{i+1}$），表示书的吸引力。

outputFormat: 输出一行一个整数，表示 $t$ 分钟后 Marko 灵感最大值。

hint:
### 样例解释 1

例如，Marko 完整阅读第 $1,3$ 本书，阅读第 $2$ 本书的封面，可以达到灵感最大值。

### 子任务

| Subtask | Points | Constraints |
| :--: | :--: | :--: |
| 1 | 7 | 对于 $i=1,\ldots,n-1$，$k_i=k_{i+1}$ |
| 2 | 27 | $n \le 1000$ |
| 3 | 36 | 无额外限制 |


title: [COCI 2023/2024 #4] Lepeze

background: **译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T3「[Lepeze](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**

description:
小 Fran 收到了一个礼物——一个正多边形木制框架。由于多边形有 $n$ 个顶点，他还收到了 $\frac{n(n-3)}{2}$ 根与每条对角线相匹配的木棍。多边形的顶点按逆时针顺序标记为 $1$ 到 $n$。一开始，弗兰将 $n-3$ 根木棍放在框架内，以使每根木棍接触框架的两个不相邻顶点，并且没有两根木棍相交。换句话说，他做了一个三角剖分。由于这对他来说不够有趣，他决定进行特定的操作来改变这种放置方法，该操作由两个步骤组成：

1. 移除一根木棍。
2. 添加一根新的木棍，使得我们得到一个新的三角剖分。

我们用一个由无序对组成的有序对 $((a, b),(c, d))$ 来描述这个操作，表示小 Fran 移除了接触顶点 $a$ 和 $b$ 的木棍，并添加了接触顶点 $c$ 和 $d$ 的木棍。

弗兰喜欢扇子，所以在进行这些操作时，他有时会问自己：「将这个三角剖分转换为以顶点 $x$ 为『扇形』三角剖分需要多少次操作，并且有多少种方式可以实现？」

由于他忙于操作和娱乐，他请求你的帮助！

以顶点 $x$ 为中心的「扇形」三角剖分是一种三角剖分，其中所有的对角线都有一个共同的端点，即顶点 $x$。

设所需操作的数量为 $m$。设 $f_1,f_2,\ldots ,f_m$ 是一个操作序列，满足按这一顺序操作可以实现满足条件的三角剖分。设 $s_1,s_2,\ldots ,s_m$ 是另一种这样的序列。如果存在一个下标 $i$ 使得 $f_i\neq s_i$，则两个序列是不同的。

由于这样的序列数量可能非常大，小 Fran 只关心它对 $10^9 + 7$ 取模后的值。

inputFormat:
第一行两个整数 $n$ 和 $q\ (4\le n\le 2\cdot 10^5,1\le q\le 2\cdot 10^5)$，表示顶点数和事件数。

接下来 $n-3$ 行，每行两个整数 $x_i,y_i\ (1\le x_i,y_i\le n)$，表示第 $i$ 根木棍接触的两个顶点。

接下来 $q$ 行，每行描述一个事件。第一个整数为 $t_i\ (1\le t_i\le 2)$，表示事件类别。

如果 $t_i=1$，则接下来还有四个整数 $a_i,b_i,c_i,d_i\ (1\le a_i,b_i,c_i,d_i\le n)$，表示一次 $((a_i,b_i),(c_i,d_i))$ 操作。保证给出的操作可以实现。

如果 $t_i=2$，则接下来一个整数 $x_i\ (1\le x_i\le n)$，表示小 Fran 对与目前顶点 $x_i$ 处的「扇形」三角剖分的数据感兴趣。

outputFormat: 对于每个类型为 $2$ 的事件，按照它们在输入中的顺序，输出两个整数：所需的最小操作数和使用最小操作数达到目标三角剖分的方式数量。


title: [COCI 2023/2024 #4] Putovanje

background: **译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T4「[Putovanje](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**

description:
Malnar 先生终于迎来了他的年假。他决定要去的国家可以表示为 $n$ 个城市和 $m$ 条双向连接它们的道路。每条道路的长度相同，并且可以通过这些道路从任何一个城市到达另一个城市。从城市 $a$ 到城市 $b$ 的路径被定义为一系列道路，满足从城市 $a$ 开始，按照该序列依次遍历道路，最终到达城市 $b$。路径的长度定义为该路径上的道路数量。

Malnar 先生像以往一样预订了其中一个城市最贵的酒店，然后开始规划他的旅程。为了方便规划，他记录了从酒店到每个城市的最短路径长度。

由于对他期待已久的假期感到兴奋，Malnar 先生完全忘记了酒店位于哪个城市。他当然不想错过这次旅行，所以他请你确定酒店可能位于哪些城市。

inputFormat:
第一行两个整数 $n$ 和 $m\ (1\le n\le 5\cdot 10^4,n-1\le m\le 10^5)$，分别表示城市和道路的数量。

接下来 $m$ 行，每行两个整数 $u_i,v_i\ (1\le u_i,v_i\le n,u_i\neq v_i)$，表示城市 $u_i$ 和 $v_i$ 之间有一条道路。任意两城市之间最多只有一条道路。

最后一行有 $n$ 个整数，第 $i$ 个整数 $d_i\ (-1\le d_i<n)$ 表示从城市 $i$ 到酒店所在城市的路径长度，如果 Malnar 先生没有记录这个值，则为 $-1$。

outputFormat:
第一行输出酒店可能位于多少个城市。

第二行输出酒店可能位于的城市编号，**按升序输出**。


title: [COCI 2023/2024 #4] Roboti

background: **译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T5「[Roboti](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**

description:
Kile 是一个桌游爱好者，他最近发现了一个叫做 Robots 的游戏。这个游戏由一个 $n$ 行 $m$ 列的网格和一个机器人组成。位置 $(1, 1)$ 是棋盘的左上角，位置 $(n, m)$ 是右下角。

开始时，机器人位于某个位置 $(x, y)$（第 $x$ 行，第 $y$ 列），玩家可以将其朝上下左右之一的方向进行移动。根据选择的方向，它将沿着该方向移动，直到到达目标格或网格中的特殊格。如果在任何时候机器人想要离开棋盘，它将翻折到另一侧。例如，如果它位于位置 $(n, 3)$ 并希望向下移动，它将到达位置 $(1, 3)$。

棋盘上有三种类型的位置：

- 空格：机器人朝相同的方向继续移动；
- 左转格：当机器人进入此格时，它会左转 $90$ 度并继续移动；
- 右转格：当机器人进入此格时，它会右转 $90$ 度并继续移动。

网格中大部分位置都是空格，只有 $k$ 个位置是左转或右转格。

游戏由 $q$ 轮组成。在第 $i$ 轮中，机器人将被放置在位置 $(a_i, b_i)$。目标是使用最少的转弯次数到达位置 $(c_i, d_i)$，或判定这是不可能的。

在多次玩这个游戏后，Kile 意识到它比起初看起来要更具挑战性。这就是为什么他现在需要你的帮助。帮助他确定每一轮游戏所需的最小转弯次数！

**注意**：如果机器人路径的起点或终点位于左转或右转格上，则该格不起作用。

inputFormat:
第一行包含三个整数 $n,m,k\ (1\le n,m\le 10^6,0\le k\le 10^5)$，分别表示行数，列数和网格中非空格的个数。

接下来 $k$ 行，每行两个整数 $x_i,y_i\ (1\le x_i\le n,1\le y_i\le m)$ 和一个字符 $s_i\ (s_i\in \{\texttt{L},\texttt{R}\})$，分别表示第 $i$ 个特殊格的位置和类别。如果 $s_i$ 是 `L`，则表示这是一个左转格。如果是 `R`，则表示这是一个右转格。

接下来一行一个整数 $q\ (1\le q\le 3\cdot 10^5)$，表示游戏轮数。

接下来 $q$ 行，每行四个整数 $a_i,b_i,c_i,d_i\ (1\le a_i,c_i\le n,1\le b_i,d_i\le m)$，分别表示起始和目标位置。

outputFormat: 输出 $q$ 行，第 $i$ 行输出第 $i$ 轮所需的最小转弯次数，如果无法到达目标，则输出 $-1$。

hint:
### 样例解释 2

第一轮：从 $(1, 1)$ 开始。如果初始机器人向左移动，它将在下一步到达 $(1, 3)$，因为它想要离开棋盘，所以会从另一侧进入。位置 $(1, 3)$ 是一个左转格，所以机器人将朝下方向移动。再经过两步，它将到达目标位置 $(3, 3)$。

第二轮：从 $(3, 3)$ 开始。如果初始机器人向上移动，它将在两步后到达 $(1, 3)$，在那里由于左转格而向左转。再经过两步，它将到达位置 $(1, 1)$，这也是一个左转格，所以它将向下移动。在下一步中，它将到达目标位置 $(2, 1)$。

### 子任务

| 子任务编号 |       附加限制       | 分值 |
| :--------: | :------------------: | :--: |
|    $1$     |        $k=0$         | $10$  |
|    $2$     | $n,m\le 300,q\le 10$ | $13$ |
|    $3$     |     $n,m\le 300$     | $49$ |
|    $4$     |      无附加限制      | $38$ |


title: 「HOI R1」杂交选种

background:
$\clubsuit$ 星球盛产“代马”，其优越的速度与耗能使得它风靡整个银河系。可小 $\iiint$ 并不满足于此，他想培育出更好的“代马”，并取代掉还在用传统能源的落后四足兽。于是，他开始研究基因技术……

**本题仅支持 C++ 语言提交。**

**由于技术限制，请勿使用 C++14 (GCC 9) 语言提交，否则将会得到 Compile Error 的结果。**

你的代码中需如下进行 `query` 和 `cross` 函数的声明：

```cpp
char query(int k);
void cross(int i, int j);
```

调用 $10^6$ 次 `query` 与 `cross` 函数的时间不超过 50 毫秒，除这两个函数所占用的时间外，交互库运行所占用的时间不超过 100 毫秒。

description:
#### 【形式化题意】

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

定义 **基因** 为一个字符，其内容为 $\verb!A!$ 或 $\verb!a!$。定义 **基因型** 为由两个基因组成，且大写字母在小写字母之前的字符串。也即 $\{\verb!aa!,\verb!Aa!,\verb!AA!\}$ 中的一种。一个基因型的 **表现** 如下：

- 若基因型中含有 $\verb!A!$，则表现为 $\verb!A!$。
- 否则，表现为 $\verb!a!$。

两个基因型可以相互 **杂交**，其定义如下：

- 在两个基因型中各均匀随机取一个基因，并将两个基因组合成基因型作为结果输出。

小 $\iiint$ 有 $n$ 个基因型，编号为 $1,2,\cdots,n$。每次询问可以给交互库两个不同的编号 $i,j$。若当前是第 $k$ 次杂交，交互库会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。

你可以在时限范围内任意次查询编号为 $x$ 的种子的表现。你需要在 $4.5\times10^5$ 次杂交内，求出初始给定的 $n$ 个基因型。

### 实现细节

**你不需要，也不应该实现主函数。** 你需要实现下面的函数：

```cpp
vector<string> guess(int n)
```

- $n$ 表示初始基因型个数。
- 该函数应当返回一个长度恰好为 $n$ 的数组，数组中的每一个元素是一个长度为二的字符串，表示你所求出的基因型。**你需要保证大写字母在小写字母的前面**。
- 对于每个测试点，该函数被恰好调用一次。

该函数可调用以下函数：

```cpp
char query(int k)
```

- $k$ 表示你要查询的基因型的编号。**你需要保证这个编号对应的基因型存在**。
- 该函数将返回该基因型的表现。
- 该函数可以在时限内被调用任意次。

```cpp
void cross(int i, int j)
```

- $i,j$ 代表你要杂交的两个基因的编号。**你需要保证 $i\not=j$ 且对应的基因型存在**。
- 若是第 $k$ 次调用该函数，该函数会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。保证杂交过程为均匀随机。
- 你最多可以调用该函数 $4.5\times10^5$ 次。
- 评测程序不是适应性的。也就是说，所有初始元素的基因型在 `guess` 函数被调用前已经确定。

hint:
#### 【交互示例】

以下为 $n=2$，基因型为 $\{\verb!Aa!,\verb!AA!\}$ 时一种可能的交互过程。

|选手程序|交互库|
|:-:|:-:|
||`guess(2)`|
|`cross(1,2)`||
||$\{\verb!Aa!,\verb!AA!,\verb!Aa!\}$|
|`cross(1,3)`||
||$\{\verb!Aa!,\verb!AA!,\verb!Aa!,\verb!aa!\}$|
|`query(4)`||
||$\verb!a!$|
|$\{\verb!Aa!,\verb!AA!\}$||
||`Ok,accepted.`|

#### 【约束条件】

+ $2\le n\le 2\times10^4$，$n$ 为偶数。
+ 每次程序运行时将恰好调用一次 `guess()` 函数。
+ 保证交互库是非自适应性的，即所有初始元素的基因型不在交互过程中发生改变。

#### 【子任务】

|Subtask|分值|$n\le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$0$|$0$|$2$|无|
|$1$|$5$|$2\times10^4$|保证不存在 $\verb!Aa!$|
|$2$|$15$|$500$|无|
|$3$|$20$|$2\times10^4$|保证至少存在一个 $\verb!aa!$|
|$4$|$25$|$5\times10^3$|无|
|$5$|$35$|$2\times10^4$|无|

对于所有数据，$2\le n\le 2\times10^4$，保证 $n$ 为偶数。

由于本题涉及概率与期望，如果你确定你的算法无误，可以尝试多交几发。


title: [入门赛 #21] 星云 hard ver.

background:
本题与 easy ver. 的区别在于本题**有**多组测试数据。

你看，那一抹云，衬着星星，多美啊！

description: 定义星云数为位数不大于 $n$ 且各数位之和不超过 $k$ 的正整数，给定 $n,k$，求星云数的个数。

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

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

对于每组测试数据：
第一行输入两个整数 $n,k$。

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

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

对于 $50\%$ 的数据，$1 \leq n \leq 2$。
对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$1 \leq n \leq 7$，$1 \leq k \leq 100$。


title: 符卡对决

background:
灵梦正在和魔理沙进行符卡对决。

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

> 永夜の报い，Pixiv76062895，作者是 minusT，侵删。

description:
灵梦一共有 $n$ 张符卡，每张卡都有一个能力值，对于第 $i$ 张卡，它的能力值为 $a_i$，现在她想从中选出两张符卡并使用它们，灵梦发现，如果她同时打出了两张符卡 $i, j$，这两张符卡造成的伤害将会是 $a_i\times a_j$。

这些符卡之间有能力的冲突，灵梦会告诉你这些符卡的兼容性，具体而言这些符卡之间有 $m$ 条关系，这些关系表明某两张符卡之间是兼容的，**注意**，如果符卡 $i, j$ 兼容且符卡 $j, k$ 兼容，那么符卡 $i, k$ 也是兼容的，如果打出的两张符卡之间不是兼容的，那么它们造成的伤害为 $0$。

她很好奇符卡之间的兼容性会造成什么样的影响，所以她会询问你 $q$ 次，每次告诉你一对正整数 $l, r$，意味着只有编号在区间 $[l, r]$ 内的关系才会生效。

灵梦不想把魔理沙虐得太惨，所以她会随机从所有符卡中选出两张**不同**的符卡来打出，她想知道每次询问造成的伤害的期望值对 $10^9 + 7$ 取模后是多少。

inputFormat:
第一行三个整数 $n, m, q$ 分别表示符卡总数，符卡间的关系总数，灵梦的询问次数。

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

接下来 $m$ 行，每行两个正整数 $u_i, v_i$，表示第 $u_i$ 张符卡与第 $v_i$ 张符卡是兼容的。

接下来 $q$ 行，每行两个正整数 $l_i, r_i$，表示灵梦询问的编号区间 $[l_i, r_i]$。

outputFormat: 一共 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问中，随机选择两张**不同**的符卡，造成伤害的期望值对 $10^9 + 7$ 取模后的结果。


title: [CCC 2024 J1] Conveyor Belt Sushi

description:
小镇里新开了一家传送带寿司店。一盘盘寿司在高高架起的传送带上旋转，顾客可以直接通过取走盘子来选择吃什么。

每一个红色盘子的寿司需要 $3$ 美元，每一个绿色盘子的寿司需要 $4$ 美元，每一个蓝色盘子的寿司需要 $5$ 美元。

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

你的任务是根据顾客选择的每种颜色的盘子数量，确定一顿饭的价钱。

inputFormat: 输入的第一行包含一个非负整数 $R$ 表示顾客选择的红色盘子数量。第二行包含一个非负整数 $G$ 表示顾客选择的绿色盘子数量。第三行包含一个非负整数 $B$ 表示顾客选择的蓝色盘子数量。

outputFormat: 输出一个非负整数 $C$ 表示这顿饭花费的美元。

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

这个顾客选择了 $0$ 个红色盘子，$2$ 个绿色盘子，$4$ 个蓝色盘子。所以这顿饭的价钱为 $0 \times 3 + 2 \times 4 + 4 \times 5 = 28$ 美元。

**【数据范围】**

对于所有数据，保证 $0\leq R,G,B\leq 500$。


title: [CCC 2024 J2] Dusa And The Yobis

description:
Dusa 吃 Yobi，但是只吃大小在某个范围里的 Yobi。

如果 Dusa 遇到了一个大小比它小的 Yobi，它会吃掉这个 Yobi 并把它的大小吞并。（即令自己的大小加上这个 Yobi 的大小。）

例如，如果 Dusa 的大小是 $10$，并且遇到了一个大小是 $6$ 的 Yobi，Dusa 会吃掉这个 Yobi 并且大小变大为 $10 + 6 = 16$。

如果 Dusa 遇到了一个和它一样大或者甚至比它更大的 Yobi，Dusa 会选择逃跑并且不吃掉 Yobi。

Dusa 现在遇到了一列 Yobi 并且按照顺序遇到它们。保证 Dusa 必定会遇到一个 Yobi 导致它逃跑。你需要确定 Dusa 逃跑时的大小。

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

inputFormat:
输入的第一行包含一个正整数 $D$ 表示 Dusa 的初始大小。

剩下的每一行包含一个正整数按顺序表示遇到的 Yobi 的大小。

outputFormat: 输出一个正整数 $R$ 表示 Dusa 逃跑时的大小。

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

Dusa 可以吃掉大小为 $3$ 的 Yobi 并使得 Dusa 的大小变为 $8$。Dusa 可以吃掉大小为 $2$ 的 Yobi 并使得 Dusa 的大小变为 $10$。Dusa 可以吃掉大小为 $9$ 的 Yobi 并使得 Dusa 的大小变为 $19$。大小为 $20$ 的 Yobi 导致了 Dusa 逃跑。

**【样例 2 解释】**

大小为 $10$ 的 Yobi 导致了 Dusa 逃跑，它的大小没有改变。

**【数据范围】**

对于所有数据，保证输入的所有数不超过 $5 \times 10^5$，输入的总行数不超过 $2 \times 10^5$。


title: [CCC 2024 J3] Bronze Count

description:
一次比赛结束后，您可能迫切地想知道有多少参赛者获得了铜牌？

金牌会授予所有获得最高分的参赛者。银牌会授予获得第二高分的所有参赛者。铜牌会授予获得第三高分的所有参赛者。

给定一份参赛选手的成绩列表，请求出获得铜牌所需的分数以及有多少人正好得到这一分数。

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

inputFormat:
输入的第一行包含一个正整数 $N$ 表示参赛者的数量。

接下来 $N$ 行包含一个整数表示一个参赛者的分数。

保证每个分数都在 $0$ 到 $75$ 之间（包含）并且至少存在三个不同的分数。

outputFormat: 输出一个非负整数 $S$ 和一个正整数 $P$ 用空格隔开。其中 $S$ 是得到铜牌所需要的分数，$P$ 是正好得到这个分数的参赛者数量。

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

得到铜牌需要 $62$ 分并且有一个参赛者正好得到这一分数。

**【样例 2 解释】**

得到铜牌需要 $60$ 分并且有两个参赛者正好得到这一分数。

**【数据范围】**

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

对于所有数据，保证 $1\leq N\leq 2.5\times 10^5$，分数 $s$ 满足 $0\leq s\leq 75$，至少存在三个不同的分数。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | 描述 | 范围 |
| :-: | :- | :-: |
| $6$ | 分数互不相同并且参赛者数量很少。 | $N \leq 50$ |
| $7$ | 分数可能存在相同并且参赛者数量很少。 | $N \leq 50$ |
| $2$ | 分数可能存在相同并且参赛者数量可以很大。 | $N \leq 2.5 \times 10^5$ |


title: [CCC 2024 J4] Troublesome Keys

description:
Alex 的键盘很奇怪。有两个字母按键出现了问题：

- 键盘上有一个按键，每次按下它的时候总是显示另一个错误的字母。Alex 把这个按键称为愚蠢的按键。奇怪的是，Alex 从来没有尝试过输入这个错误的字母。
- 键盘上还有一个按键，按下它的时候则不会显示任何内容。Alex 把这个按键称为安静的按键。

Alex 至少按下了一次愚蠢的按键，但不一定按下了安静的按键。

你需要确定出现问题的按键和按下它时显示的错误的字母。幸运的是，这是可能的，因为 Alex 从来没有在按下愚蠢的按键之后立即按下安静的按键，也没有再按下安静的按键之后立即按下愚蠢的按键。

inputFormat: 输入共两行。输入的第一行包含 Alex 按下的 $N$ 个按键。第二行包含屏幕上显示的字母。

outputFormat:
输出共两行。

第一行输出用空格分开的两个字母表示愚蠢的按键和按下时显示的错误字母。

第二行输出一个字符，如果安静的按键被按下，输出安静的按键，否则输出一个短横线（`-`）。

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

与愚蠢的按键对应的字母是 `o`，每次按下会显示错误的字母 `x`。安静的按键没有被按下过。

**【样例 2 解释】**

与愚蠢的按键对应的字母是 `o`，每次按下会显示错误的字母 `x`。没有显示的安静的按键对应的字母是 `s`。

**【样例 3 解释】**

与愚蠢的按键对应的字母是 `s`，每次按下会显示错误的字母 `z`。没有显示的安静的按键对应的字母是 `o`。

**【数据范围】**

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

对于所有数据，保证输入中每行都只包含小写字母，$1\leq N\leq 5\times 10^5$。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | 描述 | 范围 |
| :-: | :- | :-: |
| $3$ | 安静的按键没有被按下过，按键次数很少。 | $N \leq 50$ |
| $3$ | 按下的第一个有问题的按键是愚蠢的按键，按键次数很少。 | $N \leq 50$ |
| $5$ | 按下的第一个有问题的按键可能是愚蠢的按键或者安静的按键，按键次数很少。 | $N \leq 50$ |
| $4$ | 按下的第一个有问题的按键可能是愚蠢的按键或者安静的按键，按键次数可能很多。 | $N \leq 5 \times 10^5$ |


title: [CCC 2024 J5] Harvest Waterloo

description:
有一款新出现的广受欢迎的收割模拟游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行，南瓜地里有成捆的干草和不同大小的南瓜。游戏开始时，一个农民在其中一个南瓜的位置上。

农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动，不能穿过干草，也不能离开田地。

你的工作是确定农民收获的南瓜的总价值。其中一个小南瓜值 $1$ 美元，一个中等大小的南瓜值 $5$ 美元，而一个大南瓜值 $10$ 美元。

inputFormat:
输入的第一行是一个整数 $R > 0$ 表示南瓜地的行数。

第二行是一个整数 $C > 0$ 表示南瓜地的列数。

接下来 $R$ 行描述了整个南瓜地。每行包含 $C$ 个字符并且每个字符要么表示一个南瓜，要么表示干草：`S` 表示小南瓜，`M` 表示中等大小的南瓜，`L` 表示一个大南瓜，`*` 表示干草。

下一行包含一个整数 $A$ 满足 $0 \leq A < R$，最后一行是一个整数 $B$ 满足 $0 \leq B < C$。表示农民一开始在第 $A$ 行第 $B$ 列的位置。南瓜地的左上角称为第 $0$ 行第 $0$ 列。

outputFormat: 输出一个整数 $V$ 表示农民能够收割的南瓜的总价值。

samples:
6
6
**LMLS
S*LMMS
S*SMSM
******
LLM*MS
SSL*SS
5
1

samples:
6
6
**LMLS
S*LMMS
S*SMSM
***SLL
LLM*MS
SSL*SS
2
4

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

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

农民在第 $5$ 行第 $1$ 列开始可以收割 $6$ 个南瓜。可以收割到 $2$ 个小南瓜，$1$ 个中等大小的南瓜和 $3$ 个大南瓜。收割的南瓜的总价值是 $2 \times 1 + 1 \times 5 + 3 \times 10 = 37$。

**【样例 2 解释】**

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

农民在第 $2$ 行第 $4$ 列开始可以收割 $19$ 个南瓜。可以收割到 $8$ 个小南瓜，$6$ 个中等大小的南瓜和 $5$ 个大南瓜。收割的南瓜的总价值是 $8 \times 1 + 6 \times 5 + 5 \times 10 = 88$。

**【数据范围】**

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

对于所有数据，保证 $1\leq R,C\leq 10^5$，$1\leq R\times C\leq 10^5$。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | 描述 | 范围 |
| :-: | :- | :-: |
| $1$ | 南瓜地很小并且不存在干草。 | $R \times C \leq 100$ |
| $4$ | 南瓜地很小并且干草把南瓜地分割为一些矩形区域。 | $R \times C \leq 100$ |
| $5$ | 南瓜地很小并且干草可以在任意位置。 | $R \times C \leq 100$ |
| $5$ | 南瓜地可能很大并且干草可以在任意位置。 | $R \times C \leq 10^5$ |


title: [CCC 2024 S1] Hat Circle

description:
在最近的一次聚会上，$N$ 个人围坐在一张圆桌旁，其中 $N$ 是偶数。座椅按顺时针方向编号为 $1\sim N$。每个人都戴着一顶写有数字的帽子。具体来说，座位 $i$ 上的人戴着一个写有数字 $H_i$ 的帽子。

每个人都看着圆圈中与自己正对面的人。

请你求出看到戴着与自己相同号码的帽子的人的数量。

inputFormat:
输入的第一行包含一个正偶数 $N$ 表示聚会的人数。

接下来 $N$ 行分别包含一个非负整数 $H_i$，表示第 $i$ 个人的帽子上写的数字。

outputFormat: 输出一个整数，表示看到戴着与自己相同号码的帽子的人的数量。

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

桌子周围的四个座位排布如下图所示。圆圈里的数字表示这个人的帽子上写的数字，圆圈旁边的数字表示这个人的编号。注意每个人看到的数都与自己的帽子上的数相等。坐在位置 $1$ 和 $3$ 上的人都看到了数字 $0$，坐在位置 $2$ 和 $4$ 上的人都看到了数字 $1$。

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

**【样例 2 解释】**

桌子周围的四个座位排布如下图所示。圆圈里的数字表示这个人的帽子上写的数字，圆圈旁边的数字表示这个人的编号。注意每个人看到的数都不与自己的帽子上的数相等。坐在位置 $1$ 和 $4$ 上的人都看到了数字 $0$，坐在位置 $2$ 和 $3$ 上的人都看到了数字 $1$。

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

**【数据范围】**

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

对于所有数据，保证 $1\leq N\leq 10^6$，$0\leq H_i\leq 2\times 10^6$。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | 描述 | $N$ 的范围 | $H_i$ 的范围 |
| :-: | :- | :-: | :-: |
| $2$ | 人数很少；只有两种可能的帽子上的数 | $N \leq 4$ | $H_i \leq 1$ |
| $1$ | 只有一种可能的帽子上的数 | $N \leq 100$ | $H_i = 1$ |
| $2$ | 坐在奇数位置上的人的帽子上数为 $1$，坐在偶数位置上的人的帽子上数为 $0$ | $N \leq 100$ | $H_i \leq 1$ |
| $5$ | 中等多少的人数 | $N \leq 2 \times 10^3$ | $H_i \leq 4 \times 10^3$ |
| $5$ | 很多人和可能的帽子上的数 | $N \leq 10^6$ | $H_i \leq 2 \times 10^6$ |


title: [CCC 2024 S2] Heavy-Light Composition

description:
在一个只包含小写字母的字符串中，称一个字母是重的当且仅当它在字符串中出现了超过一次，否则称它是轻的。

给定一些字符串，对于每个字符串，请判断其中重的字母和轻的字母是否满足交替出现。（即要么每个奇数位的字母都是重的，每个偶数位的字母都是轻的，要么每个奇数位的字母都是轻的，每个偶数位的字母都是重的。）

inputFormat:
输入的第一行包含两个正整数 $T$ 和 $N$ 表示字符串数量和每个字符串的长度。

接下来 $T$ 行每行包含一个长度为 $N$ 的小写字母组成的字符串。

outputFormat: 输出 $T$ 行，每行包含一个字符 `T` 或者 `F`。如果第 $i$ 个输入的字符串的轻的字母和重的字母交替出现，在第 $i$ 行输出 `T`，否则在第 $i$ 行输出 `F`。

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

第一个字符串由轻字母、重字母、轻字母、重字母组成。

第二个字符串以两个连续的重字母结尾。

第三个字符串由重字母、轻字母、重字母、轻字母组成。

**【样例 2 解释】**

第一个字符串全部是轻字母。

第二个字符串由重字母、轻字母、重字母组成。

**【数据范围】**

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

对于所有数据，保证字符串中只包含小写字母，$2\leq T\leq 10^4$，$2\leq N\leq 100$。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | $T$ 的范围 | $N$ 的范围 | 其他限制 |
| :-: | :-: | :-: | :- |
| $5$ | $2 \leq T \leq 4$ | $2 \leq N \leq 4$ | 字符串只包含 `a` 和 `b` |
| $5$ | $2 \leq T \leq 10$ | $2 \leq N \leq 30$ | 无 |
| $2$ | $2 \leq T \leq 100$ | $2 \leq N \leq 100$ | 只有字母 `a` 是重的；其他字母是轻的 |
| $3$ | $2 \leq T \leq 10^4$ | $2 \leq N \leq 100$ | 无 |


title: [CCC 2024 S3] Swipe

description:
Swipe 是一款新的手机游戏，最近大受欢迎。在 Swipe 游戏的每一个关卡中，您都会得到两个长度为 $N$ 的数列 $A$ 和 $B$。Swipe 游戏的每个关卡的目标是把数组 $A$ 变成数组 $B$。

现在有两种可以对 $A$ 进行的滑动操作。

- 向右滑动：选择一个区间 $[l, r]$，对任意 $l \leq i \leq r$ 令 $A_i = A_l$。
- 向左滑动：选择一个区间 $[l, r]$，对任意 $l \leq i \leq r$ 令 $A_i = A_r$。

例如，一开始 $A = [0, 1, 2, 3, 4, 5]$，如果我们对区间 $[2, 4]$ 做向右滑动的操作，序列变为 $[0, 1, 2, 2, 2, 5]$。如果我们对区间 $[3, 5]$ 做向左滑动的操作，序列变为 $[0, 1, 2, 5, 5, 5]$。注意序列从 $0$ 开始编号。

不幸的是，游戏存在一些问题，可能会包含无法通过的关卡。请问是否可以将数组 $A$ 转换为数组 $B$。如果可以，请给出任意一种将数组 $A$ 转换为数组 $B$ 的滑动操作方案。

inputFormat:
输入的第一行包含一个正整数 $N$ 表示两个数列的长度。

第二行包含 $N$ 个空格隔开的 $A$ 中的整数。

第三行包含 $N$ 个空格隔开的 $B$ 中的整数。

outputFormat:
如果存在一种操作方案可以把 $A$ 变为 $B$，在第一行输出 `YES`，否则输出 `NO`。

如果在第一行输出了 `YES`，则下一行包含一个非负整数 $K$（$K \leq N$）表示滑动次数。

接下来 $K$ 行每行包含三个空格隔开的数 $D_j,l_j$ 和 $r_j$。$D_j$ 是 `R` 或者 `L` 表示第 $j$ 次操作是向右滑动还是向左滑动。

$l_j$ 和 $r_j$ 表示这次滑动操作的左端和右端，必须满足 $0 \leq l_j \leq r_j < N$。

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

对于所有数据，保证 $1 \leq N \leq 3 \times 10^5$，$1 \leq A_i, B_i \leq 3 \times 10^5$。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | $N$ 的范围 | $A_i$ 和 $B_i$ 的范围 |
| :-: | :-: | :-: |
| $2$ | $N = 2$ | $1 \leq A_i, B_i \leq 3$ |
| $4$ | $1 \leq N \leq 8$ | $1 \leq A_i, B_i \leq 8$ |
| $4$ | $1 \leq N \leq 500$ | $1 \leq A_i, B_i \leq 3000$ |
| $5$ | $1 \leq N \leq 3 \times 10^5$ | $1 \leq A_i, B_i \leq 3 \times 10^5$ |

注意对于一个分值为 $M$ 的子任务，如果只答对了第一行的内容，你可以得到 $\left\lfloor\dfrac M2\right\rfloor$ 分。


title: [CCC 2024 S4] Painting Roads

description:
Kitchener 市的市长 Alanna 成功地改进了该市的道路规划。然而，来自 RedBlue 市的一位售货员仍然抱怨道路的颜色不够丰富。Alanna 的下一个任务就是粉刷一些道路。

Kitchener 市的道路规划可以表示为 $N$ 个十字路口和 $M$ 条道路，第 $i$ 条道路连接第 $u_i$ 个十字路口和第 $v_i$ 个十字路口。一开始所有道路都是灰色的。Alanna 想要把一些道路染成红色或者蓝色，满足以下条件：

- 对于每一条灰色道路，假设其连接十字路口 $u_i$ 和十字路口 $v_i$，一定存在一条从十字路口 $u_i$ 到十字路口 $v_i$ 的路径，满足路径上的道路颜色红色和蓝色交替出现，任何道路都不是灰色的。

为了降低城市的支出，Alanna 希望尽可能少地对道路进行染色。请帮助 Alanna 设计一个符合要求的染色方案。

inputFormat:
输入的第一行包含两个整数 $N$ 和 $M$（$1\leq N, M \leq 2 \times 10^5$）。

接下来 $M$ 行中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ 表示存在一条连接十字路口 $u_i$ 和十字路口 $v_i$ 的道路（$1 \leq u_i, v_i \leq N$，$u_i \neq v_i$）。

任意两个十字路口之间至多存在一条道路。

outputFormat:
输出一个长度为 $M$ 的字符串，表示染色的方案。第 $i$ 个字符表示第 $i$ 条道路的颜色，`R` 表示红色，`B` 表示蓝色，`G` 表示灰色（未染色）。

注意你必须在满足条件的情况下最小化染色的道路数目。如果存在多个这样的染色方案，输出任意一个。

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

十字路口以及有效的道路的示意图如下所示，该方案最小化了染色道路的数量。请注意，每条道路上的颜色显示为 R（红色）、B（蓝色）或 G（灰色）。

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

所有为染色的道路都满足条件：

- 第二条路标记为 $G_2$ 连接了十字路口 $2$ 和 $4$，路径 $2, 1, 4$ 上的道路被染上红色、蓝色。
- 第三条路标记为 $G_3$ 连接了十字路口 $5$ 和 $2$，路径 $5, 4, 1, 2$ 上的道路被染上红色、蓝色、红色。
- 第五条路标记为 $G_5$ 连接了十字路口 $4$ 和 $3$，路径 $4, 1, 3$ 上的道路被染上蓝色、红色。

**【样例 2 解释】**

请注意 Kitchener 的道路可能不是连通的。

**【数据范围】**

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

对于所有数据，保证 $1\leq N, M \leq 2 \times 10^5$，$1 \leq u_i, v_i \leq N$，$u_i \neq v_i$。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | 附加条件 |
| :-: | :- |
| $2$ | 对任意 $1 \leq i < N$ 存在一条连接 $i$ 和 $i + 1$ 的道路（还可能存在其他道路） |
| $3$ | 图连通并且 $N = M$ |
| $3$ | 任何道路都不同时属于至少两个简单环（见下文定义） |
| $7$ | 无 |

定义：若用 $u \leftrightarrow v$ 表示一条连接 $u$ 和 $v$ 的道路，则称 $k \geq 3$ 且所有 $w_i$ 互不相同是序列 $w_1 \leftrightarrow w_2 \leftrightarrow \cdots \leftrightarrow w_k \leftrightarrow w_1$ 为简单环。


title: [CCC 2024 S5] Chocolate Bar Partition

description:
Maxwell 有一块巧克力想和他的朋友们分享。巧克力可以看作 $2\times N$ 个小方块组成的，每个小方块的美味度可以表示为 $2 \times N$ 的整数数组 $T_{i,j}$。Maxwell 想把整个巧克力分成若干个连通块，每个连通块的巧克力小方格的平均美味程度都是一样的。Maxwell 想知道根据如上所述，他可以将巧克力棒分成的最大连通块数量是多少。

如果可以通过向上、向下、向左或向右移动的方式访问到每个小方块，则该部分被视为一个连通块。

inputFormat:
输入的第一行包含一个正整数 $N$ 表示巧克力的长度。

第二行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第一行第 $j$ 个小方块的美味度 $T_{1,j}$。

类似地，第三行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第二行第 $j$ 个小方块的美味度 $T_{2,j}$。

outputFormat: 输出一个整数，表示 Maxwell 最多能把巧克力切分出的连通块数。

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

把巧克力分割成 $2$ 块是最优的，一种方案是把右下角的一个小方块作为一个连通块，其余三个小方块作为第二个连通块，如下图所示。

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

每一个连通块的平均美味度都为 $5$。

**【样例 2 解释】**

一种获得平均分割巧克力的方案如下图所示：

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

注意每一块的平均美味度都为 $1$。

**【数据范围】**

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

对于所有数据，保证 $1 \leq N \leq 2 \times 10^5$，$0 \leq T_{i,j} \leq 10^8$。

下面的表格显示了 $15$ 分的分配方案：

| 分值 | $N$ 的范围 | $T_{i,j}$ 的范围 |
| :-: | :-: | :-: |
| $2$ | $N = 2$ | $0 \leq T_{i,j} \leq 5$ |
| $2$ | $1 \leq N \leq 8$ | $0 \leq T_{i,j} \leq 20$ |
| $1$ | $1 \leq N \leq 20$ | $0 \leq T_{i,j} \leq 20$ |
| $2$ | $1 \leq N \leq 100$ | $0 \leq T_{i,j} \leq 20$ |
| $2$ | $1 \leq N \leq 1000$ | $0 \leq T_{i,j} \leq 100$ |
| $3$ | $1 \leq N \leq 2000$ | $0 \leq T_{i,j} \leq 10^5$ |
| $3$ | $1 \leq N \leq 2 \times 10^5$ | $0 \leq T_{i,j} \leq 10^8$ |


title: [THUSC 2021] 搬东西

description:
有 $n$ 件物品，编号为 $1$ 到 $n$，编号为 $i$ 的物品重量记为 $a_i$，是一个正整数。

只有一个可用的箱子，它最大可容纳的重量是一个正整数 $m$。物品被分批搬运，每批搬走其中一部分，直至所有物品都被搬走。每个批次被搬走的物品是当时剩下物品的一个子集，按如下策略选择：

选择重量之和不超过 $m$ 且包含物品数量最多的方案，如果有多种数量最多的方案，则将被选择的物品编号从小到大排列成一个序列，选择使这个序列字典序最大的方案。

请计算出依此策略会分成多少批次来搬运。

inputFormat: 输入共有两行，第一行包含两个空格分隔的正整数 $n, m$，第二行包含 $n$ 个空格隔开的正整数，依次为 $n$ 个物品的重量 $a_i$。

outputFormat: 输出一个正整数，表示完成搬运所需的批次数。

samples:
见附件中的 2.in。
见附件中的 2.ans。

samples:
见附件中的 3.in。
见附件中的 3.ans。

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

第一次最多可以搬运 $6$ 件物品，编号序列为 $6, 7, 8, 9, 10, 11$。

第二次最多可以搬运 $3$ 件物品，这时有 $4$ 种数量最大的方案：

+ 编号序列 $1, 2, 3$。
+ 编号序列 $1, 2, 5$。
+ 编号序列 $1, 3, 5$。
+ 编号序列 $2, 3, 5$。

选择字典序最大的 $2, 3, 5$。

第三次最多可以搬运 $1$ 件物品，编号序列为 $4$。

第四次最多可以搬运 $1$ 件物品，编号序列为 $1$。

**【子任务】**

|子任务|分值|$n$|$m$|
|:----:|:----:|:----:|:----:|
|$1$|$5$|$n \leq 20$|$m \leq 100$|
|$2$|$25$|$n \leq 500$|$m \leq 10^9$|
|$3$|$20$|$n \leq 3000$|$m \leq 10^9$|
|$4$|$10$|$n \leq 50000$|$m \leq 10$|
|$5$|$40$|$n \leq 50000$|$m \leq 10^9$|

全部数据满足：

+ $1 \leq n \leq 50000$，$1 \leq m \leq 10^9$；
+ 所有物品的重量满足 $1 \leq a_i \leq m, \ i=1 \dots n$。

**【提示】**

对于两个等长且不相同的序列 $a$ 和 $b$，如果序列中的元素可以比较大小，那么 $a$ 与 $b$ 的字典序大小关系如下定义：从前向后找到第一个位置 $i$ 使 $a_i \neq b_i$，若 $a_i < b_i$ 则 $a<b$，否则 $a_i>b_i$ 时 $a>b$。

在本题中，$a$ 和 $b$ 是两个搬运方案中涉及的物品编号序列，元素之间的大小关系指的就是编号之间的整数比较。

### 题目使用协议

来自 清华大学 2021 年全国优秀中学生信息学体验营 (THUSC 2021)。

以下『本仓库』皆指 THUSC 2021 官方仓库（[https://gitlink.org.cn/thusaa/thusc2021](https://gitlink.org.cn/thusaa/thusc2021)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址。
4. 清华大学计算机系保留一切权利。


title: [THUSC 2021] 白兰地厅的西瓜

background:
> 在地底的洞府中住着一个霍比特人。这不是那种让人恶心的洞，脏兮兮湿乎乎的，长满虫子，透着一股子泥腥味儿；也不是那种满是泥沙的洞，干巴巴光秃秃的，没地方好坐，也没好东西好吃。这是一个霍比特人的洞，而霍比特人的洞就意味着舒适。
>
> ——《霍比特人》开篇

description:
白兰地厅是最大的霍比特洞之一，位于雄鹿山内部，是白兰地鹿家族的祖宅，数百年来白兰地鹿家族的霍比特人不断扩张白兰地厅的规模，直至其占满了整个山丘。白兰地鹿家族是弗罗多·巴金斯的母族，他十二岁那年，双亲在划船时不幸溺亡，弗罗多便被交由白兰地厅抚养。

白兰地厅有 $n$ 个房间，房间之间以双向圆形通道相连。从任意一个房间出发都可以到达任意另一个房间，但为了避免人们迷失在交错纵横的通道里，白兰地厅经过了精心设计，以保证任意两个房间之间仅有一条路径可达。在炎炎的夏日，白兰地鹿家有贮藏甘甜可口的西瓜的习俗，但由于西瓜个头太大，白兰地鹿家会在每个房间里贮藏恰好一个西瓜。对一个西瓜而言最重要的是它的甜度，$i$ 号房间里的西瓜的甜度为 $a_i$。

弗罗多算是客居于此，因而可以在白兰地厅自由走动，也可以在任意一个他想过夜的房间里过夜。弗罗多每天会从一个房间前往另一个房间，但他生性懒惰，总是会沿着最短的路径来走。经过每个房间时弗罗多都可以品尝那个房间里的西瓜，当然他也可以只是经过而选择忽略西瓜——这也包括了他出发和最终落脚的房间。

弗罗多喜欢吃甜的西瓜，然而众所周知，味蕾感受到的甜度是相对甜度，也就是说，如果弗罗多先吃了一个甜度为 $x$ 的西瓜，紧接着又吃了一个甜度为 $y$ 的西瓜，当 $y > x$ 时，味蕾才会觉得后者是甜的，当 $y \le x$ 时，弗罗多并不会感觉到后者的甜。所以，弗罗多给自己定了一个规矩：**除了每天的第一个西瓜外，他吃的每一个西瓜的甜度都要大于前一个**。

一天清晨，弗罗多突然对白兰地厅里百无聊赖的生活心生倦意，或许只有西瓜才能让他解忧，他想吃很多个西瓜，并且不想违背他的规矩。弗罗多不禁陷入思考……他的一天里总是面临很多选择，从哪一个房间出发、最终抵达哪一个房间、在经过的房间中选择吃哪一些房间的西瓜、并忽略另一些房间里的西瓜……弗罗多想知道，在如此多的选择下，弗罗多的一天最多能吃到多少个西瓜呢？

inputFormat:
第一行包含一个正整数 $n$，表示白兰地厅的房间数量。保证 $2 \le n \le 10^{5}$。

第二行包含 $n$ 个正整数，第 $i$ 个整数为 $a_i$，表示 $i$ 号房间里的西瓜的甜度。保证 $1 \le a_i \le 10^{9}$。

接下来 $n - 1$ 行描述了白兰地厅的形态，第 $i$ 行为两个正整数 $u_i$ 和 $v_i$，表示 $u_i$ 号房间和 $v_i$ 号房间之间有一条双向通道。保证 $1 \le u_i, v_i \le n$。

outputFormat: 输出共一行，包含一个正整数，即 **弗罗多一天里最多能吃到多少个西瓜**。

samples:
见附件中的 2.in。
见附件中的 2.ans。

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

下图为本样例中的白兰地厅的示意图。黑色直线表示房间之间的通道；左侧墙壁上的数字为房间编号；西瓜内部的数字为其甜度。

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

弗罗多一天最多能吃到 5 个西瓜，有三种选择可以让他吃到 5 个西瓜。

选择一：

 - 从 8 号房间出发，并吃掉房间里的西瓜（甜度为 1）；
 - 经过 6 号房间，忽略房间里的西瓜；
 - 经过 1 号房间，并吃掉房间里的西瓜（甜度为 2）；
 - 经过 2 号房间，并吃掉房间里的西瓜（甜度为 4）；
 - 经过 4 号房间，并吃掉房间里的西瓜（甜度为 6）；
 - 抵达 5 号房间，并吃掉房间里的西瓜（甜度为 7）。

选择二：

 + 从 8 号房间出发，并吃掉房间里的西瓜（甜度为 1）；
 + 经过 6 号房间，并吃掉房间里的西瓜（甜度为 3）；
 + 经过 1 号房间，忽略房间里的西瓜；
 + 经过 2 号房间，并吃掉房间里的西瓜（甜度为 4）；
 + 经过 4 号房间，并吃掉房间里的西瓜（甜度为 6）；
 + 抵达 5 号房间，并吃掉房间里的西瓜（甜度为 7）。

选择三：

 * 从 9 号房间出发，并吃掉房间里的西瓜（甜度为 2）；
 * 经过 6 号房间，并吃掉房间里的西瓜（甜度为 3）；
 * 经过 1 号房间，忽略房间里的西瓜；
 * 经过 2 号房间，并吃掉房间里的西瓜（甜度为 4）；
 * 经过 4 号房间，并吃掉房间里的西瓜（甜度为 6）；
 * 抵达 5 号房间，并吃掉房间里的西瓜（甜度为 7）。

 **【子任务】**

 本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。

每个子任务的测试点满足一些特殊的限制，具体如下表：

|子任务编号|$n \le$|特殊性质|占分|
|:----:|:----:|:----:|:----:|
|$1$|$100$|无|$10$|
|$2$|$1000$|无|$10$|
|$3$|$5000$|$a_i \le 4$|$10$|
|$4$|$10 ^ 5$|$a_i \le 2$|$10$|
|$5$|$10 ^ 5$|树中仅有一个节点度数大于 $1$|$10$|
|$6$|$10 ^ 5$|树中所有节点度数不超过 $2$|$10$|
|$7$|$10 ^ 5$|无|$40$|

对于所有测试点，保证 $1 \le a_i \le 10^{9}$，$2 \le n \le 10^{5}$。

### 题目使用协议

来自 清华大学 2021 年全国优秀中学生信息学体验营 (THUSC 2021)。

以下『本仓库』皆指 THUSC 2021 官方仓库（[https://gitlink.org.cn/thusaa/thusc2021](https://gitlink.org.cn/thusaa/thusc2021)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址。
4. 清华大学计算机系保留一切权利。


title: [THUSC 2021] Emiya 家明天的饭

background: 由于本题的测试数据规模较大，本题只评测一部分测试数据，其余的测试数据可以在 [U412486](https://www.luogu.com.cn/problem/U412486) 中提交测试。

description:
Emiya 是个擅长做菜的高中生，他会做 $m$ 道不同的菜品。某天，Yaz、Zid 和他们的 $n$ 个朋友们到他家做客，Emiya 需要做一些菜来招待他们。

Yaz 和 Zid 什么都吃，但他们的朋友们有些挑食。具体来说，我们用整数 $a_{i,j}\geq -1$ 来表示第 $i$ 个朋友对第 $j$ 道菜品的态度：

* 若 $a_{i,j}\geq 0$，则第 $i$ 位朋友不讨厌这道菜品，如果饭桌上有这道菜，且没有其他让这位朋友讨厌的菜品，那么他会给 Emiya 留下 $a_{i,j}$ 元红包以表赞许和感谢。

* 若 $a_{i,j} = -1$，则第 $i$ 为朋友讨厌这道菜品，如果饭桌上有这道菜，那么这位朋友会非常生气，并直接离席而去。这意味着他将不会因为任何菜品留下红包。

Emiya 擅长做菜，却不擅长计算，请你帮助 Emiya 挑选若干道菜品，使得他收到的红包数额总和最大。方便起见，你只需要输出这个最大的总和即可。

inputFormat:
第一行包含两个整数 $n,m$，意义见题目描述。

第 $2$ 到第 $n+1$ 行，每行包含 $m$ 个整数：其中第 $i+1$ 行的第 $j$ 个整数为 $a_{i,j}$，意义见题目描述。

保证 $n,m\geq 1$，保证 $a_{i,j} \geq -1$。

outputFormat: 一行一个整数，表示红包金额的最大总和。

samples:
见附件中的 2.in。
见附件中的 2.ans。

samples:
见附件中的 3.in。
见附件中的 3.ans。

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

最优方案是制作第 $1$ 和第 $2$ 道菜。若如此做，虽然第 $2$ 位客人会生气地离席而去，但另两位客人留下的红包总金额是最大的。

**【子任务】**

本题设置 4 个子任务：

* 第 1 个子任务（20 分）的特殊限制：$n\leq 10, m\leq 2000$；
* 第 2 个子任务（20 分）的特殊限制：$n\leq 14$；
* 第 3 个子任务（20 分）的特殊限制：每位朋友不喜欢的菜品编号范围为一个区间，即对于每位客人 $i$，存在整数 $l,r$（$l\leq r$），满足 $a_{i,j} = -1$ 当且仅当 $j\in \left[l,r\right]$；
* 第 4 个子任务（40 分）没有特殊限制。

对于所有测试点，保证 $n\leq 20$，$m\leq 10^6$，$a_{i,j}\leq 10^9$。

**【提示】**

一些测试点的输入规模较大，请注意程序的 IO 效率。

### 题目使用协议

来自 清华大学 2021 年全国优秀中学生信息学体验营 (THUSC 2021)。

以下『本仓库』皆指 THUSC 2021 官方仓库（[https://gitlink.org.cn/thusaa/thusc2021](https://gitlink.org.cn/thusaa/thusc2021)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址。
4. 清华大学计算机系保留一切权利。


title: [GESP样题 五级] 小杨的锻炼

description: 小杨的班级里共有 $n$ 名同学，每位同学都有各自的锻炼习惯。具体来说，第 $i$ 位同学每隔 $a_i$ 天就会进行一次锻炼（也就是说，每次锻炼会在上一次锻炼的 $a_i$ 天后进行）。某一天，班上的 $n$ 名同学恰好都来进行了锻炼。他们对此兴奋不已，想要计算出下一次所有同学都来锻炼，至少要过多少天。但他们不会计算，你能帮帮他们吗？

inputFormat:
第一行一个整数 $n$，表示同学的数量。
第二行 $n$ 个用空格隔开的正整数，依次为 $a_0, a_1, …, a_{n-1}$。

outputFormat: 输出一个整数，表示下一次所有同学都来锻炼，至少要过多少天。

hint:
### 样例 1 解释

第一位同学每天都锻炼；第二位同学每 $2$ 天锻炼一次；第三位同学每 $3$ 天锻炼一次。因此，$6$ 天之后，三位同学都会进行锻炼。在此之前，第二位同学只会在第 $2, 4$ 天进行锻炼，第三位同学只会在第 $3$ 天进行锻炼，他们都无法相遇。

### 样例 2 解释

第四位同学每 $16$ 天锻炼一次，而 $16$ 天后也恰好是前三位同学锻炼的日子。

### 数据规模与约定

- 对 $20\%$ 的数据，$n = 2$。
- 对 $50\%$ 的数据，$n = 4$。
- 对 $100\%$ 的数据，$2 \leq n \leq 10$，$1 \leq a_i \leq 50$。


title: [USACO24OPEN] Logical Moos B

description:
Farmer John 有一个布尔语句，包含 $N$ 个关键字（$1\le N<2\cdot 10^5$，$N$ 为奇数）。奇数位置仅出现 $\texttt{true}$ 或 $\texttt{false}$，偶数位置上仅出现 $\texttt{and}$ 或 $\texttt{or}$。

一个 $x \operatorname{OPERATOR} y$ 形式的短语，其中 $x$ 和 $y$ 为 $\texttt{true}$ 或 $\texttt{false}$，而 $\operatorname{OPERATOR}$ 为 $\texttt{and}$ 或 $\texttt{or}$ ，按如下规则求值：

- $x \operatorname{and} y$：如果 $x$ 和 $y$ 均为 $\texttt{true}$，则求值结果为 $\texttt{true}$，否则为 $\texttt{false}$。
- $x \operatorname{or} y$：如果 $x$ 或 $y$ 为 $\texttt{true}$，则求值结果为 $\texttt{true}$，否则为 $\texttt{false}$。

在求值该语句时，FJ 必须考虑 Moo 语言中的运算符优先级。与 C++ 类似，$\operatorname{and}$ 优先级高于 $\operatorname{or}$。更具体地说，在求值该语句时，重复以下步骤直至该语句仅包含一个关键字。

1. 如果语句中包含 $\operatorname{and}$，选择其中任意一个，并将其周围的短语替换为其求值结果。
2. 否则，该语句包含 $\operatorname{or}$。选择其中任意一个，并将其周围的短语替换为其求值结果。

可以证明，如果在指定的一个步骤中可以求值多个短语，那么选择哪一个求值并不重要；该语句最终的求值结果将始终相同。

FJ 有 $Q$（$1\le Q\le 2\cdot 10^5$）个询问。在每个询问中，他给你两个整数 $l$ 和 $r$（$1\le l\le r\le N$，$l$ 和 $r$ 均为奇数），并删除关键字 $l$ 到关键字 $r$ 之间的段。反过来，他希望用一个简单的 $\texttt{true}$ 或 $\texttt{false}$ 替换他刚刚删除的段，以使整个语句的求值结果为某个指定的布尔值。帮助 FJ 判断是否可行！

inputFormat:
输入的第一行包含 $N$ 和 $Q$。

下一行包含 $N$ 个字符串，为一个合法的布尔语句。

以下 $Q$ 行，每行包含两个整数 $l$ 和 $r$，以及一个字符串 $\texttt{true}$ 或 $\texttt{false}$，表示他希望整个语句的求值结果为 $\texttt{true}$ 还是 $\texttt{false}$。

outputFormat: 输出一个长度为 $Q$ 的字符串，其中如果第 $i$ 个询问的结果为可能，则第 $i$ 个字符为 `Y`，否则为 `N`。

samples:
5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

samples:
13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

hint:
### 样例解释 1

我们来分析第一个询问：

如果我们删除段 $[1,1]$ 并替换为 $\texttt{true}$，那么整个语句将变为：

$\texttt{true and true or true}$

我们对位置 $2$ 处的 $\texttt{and}$

关键字求值，得到

$\texttt{true or true}$

由于我们没有剩下的 $\texttt{and}$ 关键字，我们必须求值 $\texttt{or}$ 关键字。求值结束后，余下的是

$\texttt{true}$

可以证明，如果我们用 $\texttt{false}$ 替换该段，该语句仍将求值为 $\texttt{true}$，因此我们输出 `N`，因为该语句不可能求值为 false。

对于第二个询问，我们可以将段 $[1,3]$
替换为 true，整个语句将求值为 $\texttt{true}$，因此我们输出 `Y`。

对于第三个询问，由于 $[1,5]$ 是整个语句，我们可以将其替换为任意内容，因此我们输出 `Y`。

### 测试点性质

- 测试点 $3-5$：$N,Q\le 10^2$。
- 测试点 $6-8$：$N,Q\le 10^3$。
- 测试点 $9-26$：没有额外限制。


title: [USACO24OPEN] Walking Along a Fence B

description:
Farmer John 的 $N$ 头奶牛（$1\le N\le 10^5$）每头都喜欢日常沿围着牧场的栅栏散步。

栅栏由 $P$ 根柱子组成（$4\le P\le 2\cdot 10^5$，$P$ 为偶数），每根柱子的位置是 FJ 农场地图上的一个不同的二维坐标点 $(x,y)$（$0\le x,y\le 1000$）。每根柱子通过垂直或水平线段的栅栏连接到两根相邻的柱子，因此整个栅栏可以被视为各边平行于 $x$ 轴或 $y$ 轴的一个多边形（最后一根柱子连回第一根柱子，确保围栏形成一个包围牧场的闭环）。栅栏多边形是「规则的」，体现在栅栏段仅可能在其端点处重合，每根柱子恰好属于两个栅栏段，同时每两个在端点处相交的栅栏段都是垂直的。

每头奶牛的日常散步都有一个偏好的起始和结束位置，均为沿栅栏的某个点（可能在柱子处，也可能不在）。每头奶牛日常散步时沿着栅栏行走，从起始位置开始，到结束位置结束。由于栅栏形成闭环，奶牛有两条路线可以选择。由于奶牛是一种有点懒的生物，每头奶牛都会选择距离较短的方向沿栅栏行走（如果并列，奶牛可以选择任一方向）。

求每头奶牛行走的距离。

inputFormat: 输入的第一行包含 $N$ 和 $P$。以下 $P$ 行的每一行包含两个整数，以顺时针或逆时针顺序表示栅栏柱子的位置。以下 $N$ 行的每一行包含四个整数 $x_1\ y_1\ x_2\ y_2$，表示一头奶牛的起始位置 $(x_1,y_1)$ 和结束位置 $(x_2,y_2)$。

outputFormat: 输出 $N$ 个整数，为每头奶牛行走的距离。


title: [USACO24OPEN] Farmer John's Favorite Permutation B

description:
Farmer John 有一个长为 $N$（$2\le N\le 10^5$）的排列 $p$，包含从 $1$ 到 $N$ 的每个正整数恰好一次。然而，Farmer Nhoj 闯入了 FJ 的牛棚并拆散了 $p$。为了不至于太过残忍，FN 写了一些能够帮助 FJ 重建 $p$ 的提示。当 $p$ 中剩余多于一个元素时，FN 会执行以下操作：

令 $p$ 的剩余元素为 $p_1^\prime,p_2^\prime,\ldots,p_n^\prime$，

- 如果 $p_1^\prime>p_n^\prime$，他写下 $p_2^\prime$ 并从排列中删除 $p_1^\prime$。
- 否则，他写下 $p_{n−1}^\prime$ 并从排列中删除 $p_n^\prime$。

最终，Farmer Nhoj 将按顺序写下 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$。给定 $h$，Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 $p$，或者判断 Farmer Nhoj 一定犯了错误。我们知道，给定两个排列 $p$ 和 $p^\prime$，如果在第一个两者不同的位置 $i$ 处有 $p_i<p_i^\prime$，则 $p$ 的字典序小于 $p^\prime$。

inputFormat:
每个测试点包含 $T$ 个独立的测试用例（$1\le T\le 10$）。每个测试用例的描述如下：

第一行包含 $N$。

第二行包含 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$（$1\le h_i\le N$）。

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

如果存在与 $h$ 相一致的 $1\ldots N$ 的排列 $p$，输出字典顺序最小的 $p$。如果不存在这样的 $p$，输出 $-1$。


title: [USACO24OPEN] Bessie's Interview S

description:
Bessie 正在寻找新工作！幸运的是，$K$ 名农夫目前正在招聘并举行面试。由于工作竞争激烈，农夫们决定按申请的顺序对奶牛进行编号和面试。有 $N$ 头奶牛在 Bessie 之前申请，因此她的编号为 $N+1$（$1\le K\le N\le 3\cdot 10^5$）。

面试过程如下。在时刻 $0$，对于每一个 $1\le i\le K$，农夫 $i$ 将开始面试奶牛 $i$。一旦一名农夫完成面试，他将立刻开始面试队列中的下一头奶牛。如果多名农夫同时完成，下一头奶牛可以根据自己的偏好选择接受任一此时空闲的农夫的面试。

对于每一个 $1\le i\le N$，Bessie 已经知道奶牛 $i$ 的面试将恰好花费 $t_i$ 分钟（$1\le t_i\le 10^9$）。然而，她不知道每头奶牛对农夫的偏好。

由于这份工作对 Bessie 来说非常重要，所以她想要认真准备面试。为此，她需要知道她会在何时接受面试，以及哪些农夫可能会面试她。帮助她求出这些信息！

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

第二行包含 $N$ 个整数 $t_1\ldots t_N$。

outputFormat:
输出的第一行包含 Bessie 的面试将开始的时刻。

第二行包含一个长为 $K$ 的 `01` 字符串，其中如果农夫 $i$ 可能面试 Bessie 则第 $i$ 个字符为 `1`，否则为 `0`。

hint:
### 样例解释 1

除了 Bessie 之外有 $6$ 头奶牛，以及 $3$ 名农夫。面试过程将如下进行：

1. 于时刻 $t=0$，农夫 $1$ 面试奶牛 $1$，农夫 $2$ 面试奶牛 $2$，农夫 $3$ 面试奶牛 $3$。
2. 于时刻 $t=1$，农夫 $2$ 结束了对奶牛 $2$ 的面试并开始面试奶牛 $4$。
3. 于时刻 $t=3$，农夫 $1$ 和农夫 $2$ 都完成了面试，从而有两种可能：
    * 农夫 $1$ 面试奶牛 $5$，农夫 $2$ 面试奶牛 $6$。在这种情况下，农夫 $2$ 将于时刻 $t=8$ 完成面试并开始面试 Bessie。
    * 农夫 $1$ 面试奶牛 $6$，农夫 $2$ 面试奶牛 $5$。在这种情况下，农夫 $1$ 将于时刻 $t=8$ 完成面试并开始面试 Bessie。

从而，Bessie 的面试将于时刻 $t=8$ 开始，并且她可能会被农夫 $1$ 或农夫 $2$ 面试。

### 测试点性质

- 测试点 $2-3$：没有两名农夫同时完成面试。
- 测试点 $4-9$：$N\le 3\cdot 10^3$。
- 测试点 $10-21$：没有额外限制。


title: [USACO24OPEN] Painting Fence Posts S

background: **注意：本题的时间限制和内存限制为 3 秒 和 512MB，分别为通常限制的 1.5 倍和 2 倍。**

description:
Farmer John 的 $N$ 头奶牛（$1\le N\le 10^5$）每头都喜欢日常沿围着牧场的栅栏散步。不幸的是，每当一头奶牛走过栅栏柱子时，她就会碰到它，这要求 Farmer John 需要定期重新粉刷栅栏柱子。

栅栏由 $P$ 根柱子组成（$4\le P\le 2\cdot 10^5$，$P$ 为偶数），每根柱子的位置是 FJ 农场地图上的一个不同的二维坐标点 $(x,y)$（$0\le x,y\le 10^9$）。每根柱子通过垂直或水平线段的栅栏连接到两根相邻的柱子，因此整个栅栏可以被视为各边平行于 $x$ 轴或 $y$ 轴的一个多边形（最后一根柱子连回第一根柱子，确保围栏形成一个包围牧场的闭环）。栅栏多边形是「规则的」，体现在栅栏段仅可能在其端点处重合，每根柱子恰好属于两个栅栏段，同时每两个在端点处相交的栅栏段都是垂直的。

每头奶牛的日常散步都有一个偏好的起始和结束位置，均为沿栅栏的某个点（可能在柱子处，也可能不在）。每头奶牛日常散步时沿着栅栏行走，从起始位置开始，到结束位置结束。由于栅栏形成闭环，奶牛有两条路线可以选择。由于奶牛是一种有点懒的生物，每头奶牛都会选择距离较短的方向沿栅栏行走。值得注意的是，这个选择总是明确的——不存在并列的情况！

一头奶牛会触碰一根栅栏柱子，当她走过这根柱子，或者当这根栅栏柱子是她散步的起点或终点时。请帮助 FJ 计算每个栅栏柱子每天所经历的触碰次数，以便他知道接下来要重新粉刷哪根柱子。

可以证明，给定所有柱子的位置，组成的栅栏仅有唯一的可能性。

inputFormat: 输入的第一行包含 $N$ 和 $P$。以下 $P$ 行的每一行包含两个整数，表示栅栏柱子的位置，没有特定的顺序。以下 $N$ 行的每一行包含四个整数 $x_1\ y_1\ x_2\ y_2$，表示一头奶牛的起始位置 $(x_1,y_1)$ 和结束位置 $(x_2,y_2)$。

outputFormat: 输出 $P$ 个整数，包含每个栅栏柱子所经历的触碰次数。

hint:
### 样例解释 1

柱子以如下方式由栅栏段连接：

$$
(3,1)\leftrightarrow(3,5)\leftrightarrow(1,5)\leftrightarrow(1,1)\leftrightarrow(3,1)
$$

各奶牛接触的柱子如下：

1. 柱子 $2$ 和 $4$。
2. 柱子 $2$ 和 $3$。
3. 柱子 $1$ 和 $3$。
4. 无。
5. 无。

### 测试点性质

- 测试点 $4-6$：$N,P\le 1000$。
- 测试点 $7-9$：所有位置均有 $0\le x,y\le 1000$。
- 测试点 $10-15$：没有额外限制。


title: [USACO24OPEN] The 'Winning' Gene S

background: **注意：本题的内存限制为 512MB，通常限制的 2 倍。**

description:
在多年举办比赛并看着 Bessie 一次又一次地获得第一名后，Farmer John 意识到这绝非偶然。他得出结论，Bessie 一定将胜利写进了 DNA，于是他开始寻找这种「胜利」基因。

他设计了一个过程来识别这个「胜利」基因的可能候选。他获取了 Bessie 的基因组，为一个长为 $N$ 的字符串 $S$，其中 $1\le N\le 3000$。他选择某个数对 $(K,L)$，其中 $1\le L\le K\le N$，表示「胜利」基因候选的长度将为 $L$，并且将在一个较大的 $K$ 长度子串中进行寻找。为了识别这一基因，他从 $S$ 中取出所有 $K$ 长度的子串，我们将称这样的子串为一个 $K$-mer。对于一个给定的 $K$-mer，他取出其所有长度为 $L$ 的子串，将字典序最小的子串识别为胜利基因候选（如果存在并列则选择其中最左边的子串），然后将该字串在 $S$ 中的起始位置 $p_i$（从 $0$ 开始索引）写入一个集合 $P$。

由于他还没有选定 $K$ 和 $L$，他想知道每对 $(K,L)$ 将有多少个候选。

对于 $1\ldots N$ 中的每一个 $v$，帮助他求出满足 $|P|=v$ 的 $(K,L)$ 对的数量。

inputFormat: 输入的第一行包含 $N$，为字符串的长度。第二行包含 $S$，为给定的字符串。输入保证所有字符均为大写字符，其中 $s_i\in \texttt A-\texttt Z$，因为奶牛遗传学远比我们的高级。

outputFormat: 对于 $1\ldots N$ 中的每一个 $v$，输出满足 $|P|=v$ 的 $(K,L)$ 对的数量，每行输出一个数。

hint:
### 样例解释 1

在这个测试用例中，输出的第三行为 $5$ 是因为我们发现恰好有 $5$ 对 $K$ 和 $L$ 存在三个「胜利」基因候选。这些候选为（其中 $p_i$ 从 $0$ 开始索引）：

```plain
(4,2) -> P = [0,3,4]
(5,3) -> P = [0,3,4]
(6,4) -> P = [0,3,4]
(6,5) -> P = [0,1,3]
(6,6) -> P = [0,1,2]
```

为了了解 $(4,2)$ 如何得到这些结果，我们取出所有的 $4$-mer

```plain
AGTC
GTCA
TCAA
CAAC
AACG
```

对于每一个 $4$-mer，我们识别出字典序最小的长度为 $2$ 的子串

```plain
AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA
```

我们取出所有这些子串在原字符串中的位置并将它们添加到集合 $P$ 中，得到 $P=[0,3,4]$。

另一方面，如果我们关注 $(4,1)$ 对，我们会发现这只会得到总共 $2$ 个「胜利」基因候选。如果我们取出所有的 $4$-mer 并识别字典序最小的长度为 $1$ 的子串（用 A，A' 和 A* 来区分不同的 A），我们得到

```plain
AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'
```

尽管 A' 和 A* 在最后 3 种情况下字典序均为最小，但最左边的子串优先，因此仅有 A' 在所有这些情况中被视为候选。这意味着 $P=[0,4]$。

### 测试点性质

- 测试点 $2-4$：$N\le 100$。
- 测试点 $5-7$：$N\le 500$。
- 测试点 $8-16$：没有额外限制。


title: [USACO24OPEN] Cowreography G

description:
奶牛们组了一支舞蹈队，Farmer John 是她们的编舞！舞蹈队最新而最精彩的舞蹈有 $N$ 头奶牛（$2\le N\le 10^6$）排成一行。舞蹈中的每次动作都涉及两头奶牛，至多相距 $K$ 个位置（$1\le K < N$），优雅地跳起并降落在对方的位置上。

队伍中有两种奶牛——更赛牛（Guernsey）和荷斯坦牛（Holstein）。因此，Farmer John 将这一舞蹈记录为一系列**长为 $N$ 的 `01` 字符串**，其中 `0` 代表更赛牛，`1` 代表荷斯坦牛，整个字符串表示奶牛在这一行中是如何排列的。

不幸的是，Farmer Nhoj（对手团队的编舞）蓄意破坏了这一舞蹈，并清除了除第一个和最后一个 `01` 字符串之外的所有内容！由于一场大型比赛即将开始，Farmer John 必须抓紧每一秒重建这一舞蹈。

给定这两个 `01` 字符串，帮助 Farmer John 求出舞蹈中的最小动作数量！

inputFormat:
输入的第一行包含 $N$ 和 $K$。

第二行包含第一个 `01` 字符串。

第三行包含最后一个 `01` 字符串。

输入保证两个 `01` 字符串包含相同数量的 `1`。

outputFormat: 输出舞蹈中的最小动作数量。


title: [USACO24OPEN] Grass Segments G

description:
Bessie 正在数轴的正半轴上种一些草。她有 $N$（$2\le N\le 2\cdot 10^5$）个不同的栽培品种，并将把第 $i$ 个品种种植在区间 $[l_i,r_i]$（$0<l_i<r_i\le 10^9$）内。

此外，品种 $i$ 会在存在某个品种 $j$（$j\neq i$）使得品种 $j$ 与品种 $i$ 重叠至少 $k_i$（$0<k_i\le r_i-l_i$）长度时生长得更好。Bessie 想要评估她所有的品种。对于每一个 $i$，计算 $j\neq i$ 的数量，使得 $j$ 与 $i$ 重叠至少 $k_i$ 长度。

inputFormat:
输入的第一行包含 $N$。

以下 $N$ 行每行包含三个空格分隔的整数 $l_i$，$r_i$ 和 $k_i$。

outputFormat: 输出所有品种的答案，每种一行。

hint:
### 样例解释 1

两品种的重叠部分为 $[4,6]$，长度为 $2$，不小于 $2$ 但并非不小于 $3$。

### 测试点性质

- 测试点 $4-5$：$N\le 5000$。
- 测试点 $6-11$：$k$ 对于所有的区间均相同。
- 测试点 $12-20$：没有额外限制。

此外，对于测试点 $5$，$7$，……，$19$，对于所有 $i$ 有 $r_i\le 2N$。


title: [USACO24OPEN] Smaller Averages G

description:
Bessie 有两个长度为 $N$ 的数组（$1\le N\le 500$）。第一个数组的第 $i$ 个元素为 $a_i$（$1\le a_i\le 10^6$），第二个数组的第 $i$ 个元素为 $b_i$（$1\le b_i\le 10^6$）。

Bessie 希望将两个数组均划分为若干**非空**子数组，使得以下条件成立。

1. 每个元素恰属于 $1$ 个子数组。
2. 两个数组划分为相同数量的子数组。令第一个和第二个数组被划分为的子数组数量为 $k$（即，第一个数组被划分为恰好 $k$ 个子数组，第二个数组被划分为恰好 $k$ 个子数组）。
3. 对于所有 $1\le i\le k$，第一个数组左数第 $i$ 个子数组的平均值**小于或等于**第二个数组左数第 $i$ 个子数组的平均值。

计算她有多少种方式在满足限制的情况下将两个数组划分为非空子数组，对 $10^9+7$ 取模。两种划分方式被认为是不同的，如果子数组的数量不同或是某个元素属于不同的子数组。

inputFormat:
输入的第一行包含 $N$。

第二行包含 $a_1,a_2,\ldots,a_N$。

第三行包含 $b_1,b_2,\ldots,b_N$。

outputFormat: 输出在满足限制的情况下将两个数组划分为非空子数组的方法数模 $10^9+7$ 的余数。


title: [USACO24OPEN] Identity Theft P

description:
Farmer John 的 $N$（$1\le N\le 10^5$）头奶牛每头都有一个二进制字符串（由字符 `0` 和 `1` 组成的字符串）形式的农场证号。Bessie，最年长的奶牛，记住了所有奶牛的农场证号，还喜欢到处询问奶牛她们的农场证号。

当一头奶牛被询问她的农场证号时，她们会开始报正确的二进制字符串，但有可能会感到困惑并在报完之前停下来。当 Bessie 听到该二进制字符串时，如果它不等于农场上任何一头奶牛的农场证号，她就会耸耸肩走开。然而，如果它等于不同于她所询问的奶牛的另一头奶牛的农场证号，那么她就会认为发生了身份盗用并封锁整个农场。注意，这种情况即使当奶牛报出完整的农场证号时也可能发生。

Farmer John 希望防止这种情况发生，并愿意以添加更多二进制位的方式改变奶牛的农场证号。他可以在一秒钟内在任意一头牛的农场证号末尾添加一个二进制位。求出他所需要的最小时间以防止封锁发生。

inputFormat:
输入的第一行包含 $N$，为 Farmer John 的农场上的奶牛数量。

以下 $N$ 行，第 $k$ 行包含表示 Farmer John 的农场上第 $k$ 头奶牛的农场证号的二进制字符串。

所有奶牛的农场证号均不为空，且所有农场证号的总长度不超过 $10^6$。

outputFormat: 输出 Farmer John 需要花费的最小秒数以确保封锁不会发生。

hint:
### 样例解释 1

这一样例满足第一个子任务的性质。

我们可以花费 5 秒使得封锁不可能发生，通过对第一个农场证号添加 `0`，对第二个农场证号添加 `10`，对第三个农场证号添加 `11`，使农场证号变为 `10`，`110` 和 `111`。

你可以证明这不可能在 4 秒或更少的时间内完成。例如，如果你保持所有农场证号不变，则所有 3 头奶牛都具有相同的农场证号 `1`，因此当 Bessie 听到它时，它将始终等于另一头奶牛的农场证号。

作为另一个例子，如果你仅花费 2 秒对第二个农场证号添加 `0`，对第三个农场证号添加 `1`，则农场证号变为 `1`，`10` 和 `11`，因此第二头和第三头奶牛在报她们的农场证号时，可能会停在中间只报出 `1`，而这将等于第一头奶牛的农场证号。

### 样例解释 2

我们可以在 2 秒内使得封锁不可能发生，通过对前两个农场证号添加 `0`，像之前一样使农场证号变为 `10`，`110` 和 `111`。你可以证明这不可能在 1 秒内完成。

### 样例解释 3

我们可以在 4 秒内使得封锁不可能发生，通过对第一个农场证号添加 `00`，对第二个农场证号添加 `01`。你可以证明这不可能在 3 秒或更少的时间内完成。

### 样例解释 5

这一样例满足第一个子任务的性质。

### 测试点性质

- 测试点 $6-7$：所有农场证号的长度均恰好为 $1$。
- 测试点 $8-15$：$N\le 10^2$，且所有农场证号的总长度不超过 $10^3$。
- 测试点 $16-25$：没有额外限制。


title: [USACO24OPEN] Splitting Haybales P

description:
Farmer John 想要将干草堆公平地分配给他最喜欢的两头奶牛 Bessie 和 Elsie。他有 $N$（$1\le N\le 2\cdot 10^5$）个降序排序的干草堆，其中第 $i$ 个干草堆有 $a_i$ 单位干草（$2\cdot 10^5\ge a_1\ge a_2\ge \cdots \ge a_N\ge 1$）。

Farmer John 正在考虑将一个连续区间的干草堆 $a_l,\ldots,a_r$ 分配给 Bessie 和 Elsie。他决定按从 $l$ 到 $r$ 的顺序处理干草堆，当处理第 $i$ 个干草堆时他会将其交给当前干草较少的奶牛（如果并列，他会将其交给 Bessie）。

给定 $Q$（$1\le Q\le 2\cdot 10^5$）个询问，每个询问包含三个整数 $l,r,x$（$1\le l\le r\le N$，$|x|\le 10^9$）。对于每个询问，输出如果 Bessie 初始时比 Elsie 多 $x$ 单位干草，在处理干草堆 $l$ 到 $r$ 后 Bessie 将比 Elsie 多多少单位的干草。注意如果 Elsie 最终获得的干草多于 Bessie 则该值为负。

inputFormat:
输入的第一行包含 $N$。

第二行包含 $a_1\ldots a_N$。

第三行包含 $Q$。

以下 $Q$ 行包含 $l,r,x$。

outputFormat: 输出 $Q$ 行，包含每个询问的答案。

hint:
### 样例解释 1

对于第 1 个询问，Elsie 初始时比 Bessie 多 2 单位干草。然后，在处理干草堆 1 后，Bessie 将收到 3 单位干草，从而 Bessie 将比 Elsie 多 1 单位干草。

对于第 3 个询问，Elsie 和 Bessie 初始时有相同的干草数量。在处理干草堆 1 后，Bessie 将收到 3 单位干草，从而 Bessie 将比 Elsie 多 3
单位干草。

对于第 9 个询问，Bessie 初始时比 Elsie 多 1 单位干草，然后在处理第 1 个干草堆后，比 Elsie 少 2 单位干草，处理第 2 个干草堆后，比 Elsie 少 1 单位干草。

### 样例解释 2

对于第 5 个询问，有 5 个干草堆需要处理。Bessie 收到 4 单位干草，然后 Elsie 收到 4 单位干草，然后 Bessie 收到 3 单位干草，然后 Elsie 收到 1 单位干草，然后 Elsie 收到 1 单位干草。

### 测试点性质

- 测试点 $3$：$Q\le 100$。
- 测试点 $4-6$：至多存在 $100$ 个不同的 $a_i$。
- 测试点 $7-22$：没有额外限制。


title: [USACO24OPEN] Activating Robots P

description:
你和一个机器人初始时位于周长为 $L$（$1\le L\le 10^9$）的圆上的点 $0$ 处。你可以以每秒 $1$
单位的速度沿圆周顺时针或逆时针移动。本题中的所有移动都是连续的。

你的目标是放置恰好 $R-1$ 个机器人，使得最终每两个相邻的机器人彼此相距 $L/R$（$2\le R\le 20$，$R$ 整除 $L$）。有 $N$（$1\le N\le 10^5$）个激活点，其中第 $i$ 个激活点位于距点 $0$ 逆时针方向 $a_i$ 距离处（$0\le a_i<L$）处。如果你当前位于一个激活点，你可以立刻在该点放置一个机器人。所有机器人（包括初始的）均以每 $K$ 秒 $1$ 单位的速度逆时针移动（$1\le K\le 10^6$）。

计算达到目标所需要的最小时间。

inputFormat:
输入的第一行包含 $L$，$R$，$N$ 和 $K$。

第二行包含 $N$ 个空格分隔的整数 $a_1,a_2,\ldots,a_N$。

outputFormat: 输出达到目标所需要的最小时间。

hint:
### 样例解释 1

我们可以通过顺时针移动在 $4$ 秒内到达点 $6$ 的激活点。此时，初始的机器人将位于点 $2$。再等待 $18$ 秒直到初始机器人位于点 $1$。现在我们可以放置一个机器人以立即获胜。

### 样例解释 2

我们可以通过顺时针移动在 $3$ 秒内到达点 $7$ 的激活点。此时，初始的机器人将位于点 $1.5$。再等待一秒直到初始机器人位于点 $2$。现在我们可以放置一个机器人以立即获胜。

### 测试点性质

- 测试点 $5-6$：$R=2$。
- 测试点 $7-12$：$R\le 10,N\le 80$。
- 测试点 $13-20$：$R\le 16$。
- 测试点 $21-24$：没有额外限制。


title: 诈骗题

background: 这是一道诈骗题。

description:
定义 $f(n,m)$ 为下列问题的答案。

> 考虑一个 $n\times m$ 黑白网格图，初始全是白色的。每次操作如下：
> - 选择一个白格子 $(x,y)$，将其所在行全染黑，这个操作叫 $(x,y,\text{R})$。
> - 选择一个白格子 $(x,y)$，将其所在列全染黑，这个操作叫 $(x,y,\text{C})$。
>
> 假设最多能操作 $k$ 次。问：
>
> - 对于所有操作 $k$ 次的方案，有多少种本质不同的 **操作集合** 。操作集合是一个大小为 $k$ 的集合，代表操作过的 $k$ 种操作。（注意，顺序不同但操作集合相同的 $2$ 种方案只会被计算 $1$ 次）

称两个操作集合 $A, B$ 本质不同，当且仅当存在某种操作 $opt$，满足 $[opt \in A] + [opt \in B] = 1$。

现在给定 $n,m$，请你对于所有 $1\le i\le n,\ 1\le j\le m$ 求出 $f(i,j)$ 的取值。

由于答案可能有点大，因此你只需要输出其取模 $998244353$ 的结果。

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

outputFormat: 输出一个 $n$ 行 $m$ 列的矩阵，第 $i$ 行第 $j$ 个数表示 $f(i,j)\bmod 998244353$。


title: Pairing Pairs （加强版）

background: 本题是 [Pairing Pairs](https://www.luogu.com.cn/problem/P10247) 的加强版，数据范围和输入输出方式都有区别。

description:
你有一些数对 $(u_i,v_i)$（保证 $0\le u_i<v_i<n$ 且数对两两不同），对于每个 $i$ 找一个 $j$ 使得 $u_i,v_i,u_j,v_j$ 四个数两两不同，或报告不存在。

**为加速输入输出，本题采用 grader 交互。请注意本题和赛时题目的区别，本题输入和输出的下标均从 $0$ 开始。**

你需要实现一个函数 `int* find_pairs(int n,int m,int u[],int v[])`，其中 $n,m,u,v$ 如题意所示。

返回值是一个数组（设为 `ans`），则 `ans[i]` 表示你对于 $i$ 找到的 $j$。若这样的 $j$ 不存在，则 `ans[i]=-1`，**不是 $0$。**

**由于本题的返回值是一个指针，请保证返回的数组在堆空间中，具体可以参考[这篇博客](https://www.luogu.com.cn/article/sxyv0830)。**

inputFormat:
**以下输入输出格式均为 `sample_interactive_lib.cpp` 的输入输出格式。你不需要输入或输出任何数据，甚至不应该实现 `main` 函数。**

输入的第一行有两个正整数 $n,m$ 表示数对中数字的范围和数对的个数。

之后 $m$ 行，其中的第 $i$ 行有两个正整数 $u_i,v_i$ 表示第 $i$ 个数对。

outputFormat:
输出一行 $m$ 个自然数，其中第 $i$ 个数表示你对这个 $i$ 找到的 $j$。若对应的 $j$ 不存在则输出 $-1$。

若符合题意的 $j$ 有多个，任意输出一个都可以通过本题。

hint:
【样例解释】

根据该程序，样例交互库将会调用 `find_pairs(7,5,{0,2,0,2,3},{2,3,3,5,6})`，然后如果你返回的数组是 `{4,-1,3,4,0}`，就会得到样例输出。这个样例输出是合法的。

【数据范围】

对于全体数据，保证 $1\le n,m\le 10^7$。

std 用时为 $324$ 毫秒，空间为 $267.87$ MB。


title: Yet another ZP problem

description:
从左到右排列着 $n$ 个点，编号分别为 $1,2,\dots,n$。

你要在他们之间连一些边，记边集为 $E=\{(x,y)\ |\ 1\leq x<y\leq n\}$。

我们称边集 $E$ 满足限制 $[l,r]$，当且仅当存在 $(x,y)\in E$ 使得 $[x\in[l,r]]+[y\in[l,r]]=1$。

基础地，我们希望对所有 $1\leq i\leq n$ 满足限制 $[i,i]$。

在此基础上，输入还给定了额外的 $m$ 个限制 $[l_i,r_i]$（$1\leq l_i<r_i\leq n$ 并且 $[l_i,r_i]\neq [1,n]$）。

请问 $|E|$ 最小是多少，在此基础上给出一组合法构造。可以证明，合法的 $E$ 总是存在的。

对于形如 $[P]$ 的表达式，当且仅当命题 $P$ 为真时其取值为 $1$，否则取值为 $0$。

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

接下来 $m$ 行每行两个正整数 $l_i,r_i$。

outputFormat:
第一行输出一个数代表 $|E|$。

接下来 $|E|$ 行，每行两个数 $x,y$ 代表一条边，**注意你需要保证 $1\le x<y\le n$**。


title: 火大

description:
给定两个正整数 $n,m$，求一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，满足如下两个要求。

- 对于任意整数 $i$ ，其中 $1\le i\le n$，满足 $0\le a_i<m$ 且 $a_i$ 为整数。
- 对于任意整数 $i,j$，其中 $1\le i\le j\le n$，存在整数 $k$，其中 $1\le k\le j$，满足 $a_k\in [\frac{m(i-1)}{j},\frac{mi}{j})$。

若存在序列 $a$ 满足要求，请给出构造，否则请输出 `fire big`。

inputFormat:
**本题多测。**

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

随后输入 $T$ 组数据。对于每组数据，输入两个正整数 $n,m$，其意义如题目中所描述。

outputFormat: 对于每组数据，若存在序列 $a$ 满足要求，输出一行 $n$ 个数表示序列 $a$，否则输出一行 `fire big`。


title: 「LAOI-4」Mex Tower (Hard ver.)

background:
**本题与 Easy Version 的区别为本题需判断方案的合法性。**

**保证本题所有的测试点时空限制均为 std 的 $2.5$ 倍及以上**。

description:
定义 $\operatorname{mex}(x, y)$ 表示在集合 $\{x, y\}$ 中最小的未出现的 **自然数**。例如，$\operatorname{mex}(1, 5) = 0$，$\operatorname{mex}(3, 0) = 1$。

继而，我们定义对自然数序列 $a_1\dots a_n$ 的一次操作，是将序列 $a$ 替换为 **长度为 $\bm{n - 1}$ 的** 序列 $a'_1\dots a'_{n-1}$，其中 $a'_i = \operatorname{mex}(a_i, a_{i+1})$。

一个长度为 $n$ 的整数序列 $a_1\dots a_n$，满足 $0 \leq a_i \leq 10^9$；然后依次对它进行 $n - 1$ 次操作。显然最终序列 $a$ 只会剩下一个数，定义这最终一个数的值成为 **该序列的价值**，记为 $f(a)$。

请问对于给定的 $n$ 和 $a$ 序列，是否对于所有长度为 $n$ 的自然数序列 $b$，$f(a)\ge f(b)$。

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

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

对于每组数据，第一行一个正整数 $n$。

接下来 $n$ 个整数，表示序列 $a$。

outputFormat: 对于每组数据，一行一个字符串 `Yes` 或 `No`。


title: Happybob's Pencil Case (UBC001C)

background: 注：本题无 typo。

description:
假设教室是一个 $n \times n$ 的 `01` 矩阵，`0` 表示空，`1` 表示有课桌（障碍）。

现在 Cuazyoxi 拿着 Happybob's Pencil Case 在 $(x_1, y_1)$ 处，Happybob 在 $(x_2, y_2)$ 处。

我们定义一次移动为往当前格子的上下左右一格移动。形式化地，假设当前一人（Cuazyoxi 或 Happybob）在 $(x, y)$ 处，如果 $(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)$ 当中的某一个存在且不是障碍，则他可以移动到那一格。

每秒，Cuazyoxi 先移动一次或不动，然后 Happybob 移动一次或两次或者不动，每次移动后他们都知道对方的位置。

双方都很聪明。Cuazyoxi 想要让 Happybob 抓到他的时间尽量久，而 Happybob 想要尽早抓到 Cuazyoxi。

问：Cuazyoxi 还能躲避 Happybob 多少秒（Happybob 至少要多少秒后才能和 Cuazyoxi 达到同一个格子）？

inputFormat:
第一行，一个正整数 $n$，表示教室大小。

第二行，四个正整数 $x_1,y_1,x_2,y_2$，表示 Cuazyoxi 与 Happybob 的起点。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串 $S$，这 $n$ 行的字符串构成一个 `01` 矩阵。

outputFormat: 如果 Cuazyoxi 迟早会被抓到，输出他被抓到的时间，否则输出 `inf`。

hint:
**样例说明**

对于样例 $1$，Cuazyoxi 的最优策略显然是呆在原地不动，$2$ 秒后 Happybob 可以抓到他。

对于样例 $2$，无论如何 Happybob 都抓不到 Cuazyoxi。

**数据范围**

$2\le n\le 10$ 且 $1 \le x_1, x_2, y_1, y_2 \le n$。保证 $(x_1,y_1),(x_2,y_2)$ 上的数字是 `0` 且 $x_1\ne x_2$ 或 $y_1\ne y_2$。保证输入的 $n$ 个字符串长度都是 $n$ 且只含字符 `0` 与 `1`（可能只含 `1` 或只含 `0`）。


title: Happybob's Pancake (UBC001E)

description:
Happybob 想做一块煎饼，他决定在一个 $n$ 行 $n$ 列的斜正方形的锅里做一个煎饼，所以煎饼的大小不能超过斜正方形的大小。

由于原料有限，因此 Happybob 的煎饼必须是 $m$ 个长方形覆盖而成的。

Happybob 想知道，他能制作出的最大的煎饼的面积是多少。

---

**形式化题意：**

用 $m$ 个长方形覆盖大小为 $n$ 的斜正方形，最多覆盖多少个格子？

**斜正方形和覆盖的定义见说明/提示**。

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

接下来 $T$ 行，每行两个整数 $n,m$，表示一次询问。

outputFormat: $T$ 行，每一行表示一个询问的答案。

hint:
### 样例说明

三次询问的方案是：

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

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

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

（方案不唯一）

### 数据范围

$1\le T\le 50$，$1\le n\le 2\times 10^9$，$1\le m\le\lceil\dfrac{n}{2}\rceil$。

---

### 形式化定义

**斜正方形的定义：**

更形式化地，建立直角坐标系，定义一个大小为 $n$ 的**斜正方形**的**中心**为原点。

若 $n$ 为奇数，则该**斜正方形**可以描述为所有以 $\big\{(x, y) \big | |x| + |y| \le \lfloor \frac{n}{2} \rfloor \text{ and } x, y \in \Z\big\}$ 中的点为**正方形**中心的边长为 $1$ 的**正方形格子**组成的组合图形。

若 $n$ 为偶数，则该**斜正方形**可以描述为所有以 $\big\{(x, y) \big | |x| + |y| \le \frac{n}{2} \text{ and } (x + \frac{1}{2}), (y + \frac{1}{2}) \in \Z\big\}$ 中的点为**正方形**中心的边长为 $1$ 的**正方形格子**组成的组合图形。

一个 $n=5$ 的斜正方形（淡蓝色为格子中心）：

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

一个 $n=6$ 的斜正方形（淡蓝色为格子中心）：

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

**覆盖方法的定义：**

定义一个长方形 $R$ 覆盖该**斜正方形**，当且仅当 $R$ 为由若干**格子**组成的长方形。

下面是一个覆盖斜正方形的长方形：

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

下面则**不是**覆盖斜正方形的长方形：

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

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

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

定义一个**格子**被覆盖，当且仅当选择的 $m$ 个覆盖**斜正方形**的长方形中有至少一个完全包含该格子。