title: [IOI2023] 最长路程

background:
IOI2023 D1T2

**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引入头文件，而需要把头文件的内容加入文件的开头。即，在程序开头加入以下几行语句：**

```
#include <vector>

std::vector<int> longest_trip(int N, int D);

bool are_connected(std::vector<int> A, std::vector<int> B);
```

description:
IOI 2023 组委会有大麻烦了！他们忘记计划即将到来的 Ópusztaszer 之旅了。然而，或许一切尚未为晚 ......

在 Ópusztaszer 有 $N$ 个地标，编号为从 $0$ 到 $N-1$。某些地标之间连有**双向**的**道路**。任意一对地标之间至多连有一条道路。组委会**不知道**哪些地标之间有道路相连。

如果对于每三个不同的地标，它们之间都至少连有 $\delta$ 条道路，我们就称 Ópusztaszer 的路网**密度**是**至少**为 $\delta$ 的。换言之，对所有满足 $0 \le u \lt v \lt w \lt N$ 的地标三元组 $(u, v, w)$，配对 $(u,v)$，$(v,w)$ 和 $(u,w)$ 中至少有 $\delta$ 个配对中的地标有道路相连。

组委会**已知**有某个正整数 $D$，满足路网密度至少为 $D$。注意， $D$ 的值不会大于 $3$。

组委会可以**询问** Ópusztaszer 的电话接线员，以获取关于某些地标之间的道路连接信息。在每次询问时，必须给出两个非空的地标数组 $[A[0], \ldots, A[P-1]]$ 和 $[B[0], \ldots, B[R-1]]$。地标之间必须是两两不同的，即，

* 对于满足 $0 \le i \lt j \lt P$ 的所有 $i$ 和 $j$，有 $A[i] \neq A[j]$；
* 对于满足 $0 \le i \lt j \lt R$ 的所有 $i$ 和 $j$，有 $B[i] \neq B[j]$；
* 对于满足 $0 \le i \lt P$ 且 $0\le j \lt R$ 的所有 $i$ 和 $j$，有 $A[i] \neq B[j]$。

对每次询问，接线员都会报告是否存在 $A$ 中的某个地标和 $B$ 中的某个地标有道路相连。更准确地说，接线员会对满足 $0 \le i \lt P$ 和 $0\le j \lt R$ 的所有配对 $i$ 和 $j$ 进行尝试。如果其中某对地标 $A[i]$ 与 $B[j]$ 之间连有道路，接线员将报告 `true`。否则，接线员将报告 `false`。

一条长度为 $l$ 的**路程**，被定义为由**不同**地标 $t[0], t[1], \ldots, t[l-1]$ 构成的序列，其中对从 $0$ 到 $l-2$（包括 $0$ 和 $l-2$）的所有 $i$，地标 $t[i]$ 和 $t[i+1]$ 之间都有道路相连。如果不存在长度至少为 $l+1$ 的路程，则长度为 $l$ 的某条路程被称为是**最长路程**。

你的任务是通过询问接线员，帮助组委会在 Ópusztaszer 找一条最长路程。

---

**【实现细节】**

你需要实现如下函数：

```
int[] longest_trip(int N, int D)
```

* $N$：Ópusztaszer 的地标数量。
* $D$：可以保证的路网密度最小值。
* 该函数需要返回一个表示某条最长路程的数组 $t = [t[0], t[1], \ldots, t[l-1]]$。
* 对于每个测试用例，该函数都可能会被调用 **多次**。

上述函数可以调用如下函数：

```
bool are_connected(int[] A, int[] B)
```

* $A$：一个非空、且元素两两不同的地标数组。
* $B$：一个非空、且元素两两不同的地标数组。
* $A$ 和 $B$ 之间应无交集。
* 如果存在连接 $A$ 中某个地标以及 $B$ 中某个地标的道路，该函数返回 `true`。否则该函数返回 `false`。
* 在每次 `longest_trip` 调用中，该函数可以被至多调用 $32\,640$ 次。该函数的累计调用总数至多为 $150\,000$ 次。
* 对历次调用该函数时传递的数组 $A$ 和 $B$ 长度进行累计，两个数组累计长度加起来不能超过 $1\,500\,000$。

评测程序是**非适应性的**。每次提交都将在同一组测试用例上进行评测。换言之，在每个测试用例中，$N$ 和 $D$ 的值，以及道路所连接的地标配对，对于每次 `longest_trip` 调用都保持不变。

hint:
**【例子】**

**样例一**

考虑某个 $N = 5$, $D = 1$ 的场景，其中道路连接情形如下图所示：

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

函数 `longest_trip` 被调用如下：

```
longest_trip(5, 1)
```

该函数可以调用 `are_connected` 如下。

|                调用                |  有道路连接的配对  | 返回值  |
| :--------------------------------: | :----------------: | :-----: |
| `are_connected([0], [1, 2, 4, 3])` | $(0,1)$ 和 $(0,2)$ | `true`  |
|     `are_connected([2], [0])`      |      $(2,0)$       | `true`  |
|     `are_connected([2], [3])`      |      $(2,3)$       | `true`  |
|  `are_connected([1, 0], [4, 3])`   |         无         | `false` |

在第四次调用后，可知 $(1,4)$，$(0,4)$，$(1,3)$ 和 $(0,3)$ 中**没有**哪个配对中的地标之间连有道路。由于路网的密度至少是 $D = 1$，我们由三元组 $(0, 3, 4)$ 可知，配对 $(3,4)$ 的地标之间必须连有道路。与此相似，地标 $0$ 和 $1$ 之间必须是相连的。

至此，可以总结出 $t = [1, 0, 2, 3, 4]$ 是一条长度为 $5$ 的路程，而且不存在长度超过 $5$ 的路程。因此，函数 `longest_trip` 可以返回 $[1, 0, 2, 3, 4]$。

考虑另一个场景， 其中 $N = 4$, $D = 1$，且地标之间的道路如下图所示：

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

函数 `longest_trip` 被调用如下：

```
longest_trip(4, 1)
```

在这个场景中，最长路程的长度为 $2$。因此，在对函数 `are_connected` 进行少量调用后，函数 `longest_trip` 可以返回 $[0, 1]$, $[1, 0]$, $[2, 3]$ 和 $[3, 2]$ 中的任意一个.

**样例 2**

子任务 0 包含另一个测试用例用作示例，其中有 $N=256$ 个地标。

**【数据范围】**

* $3 \le N \le 256$
* 对于每个测试用例，函数 `longest_trip` 的所有调用中 $N$ 的累计总和不超过 $1\,024$。
* $1 \le D \le 3$

**【子任务】**

1. （5 分）$D = 3$
1. （10 分）$D = 2$
1. （25 分）$D = 1$。令 $l^\star$ 表示最长路程的长度。函数 `longest_trip` 不必返回长度为 $l^\star$ 的某条路程，而应返回长度至少为 $\left\lceil \frac{l^\star}{2} \right\rceil$ 的某条路程。
1. （60 分）$D = 1$

在子任务 4 中，你的得分将根据 `longest_trip` 的单次调用中对函数 `are_connected` 的调用数量而定。对该子任务的所有测试用例调用 `longest_trip`，令 $q$ 为各次调用产生的函数 `are_connected` 调用次数的最大值。
你在该子任务上的得分将按照下表进行计算：

|            条件            | 得分 |
| :------------------------: | :--: |
| $2\,750 \lt q \le 32\,640$ | $20$ |
|   $550 \lt q \le 2\,750$   | $30$ |
|    $400 \lt q \le 550$     | $45$ |
|        $q \le 400$         | $60$ |

如果在某个测试用例上，对函数 `are_connected` 的调用没有遵守实现细节部分给出的限制条件，或者 `longest_trip` 返回的数组是错误的，你的解答在该子任务上的得分将为 $0$。

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

令 $C$ 为场景数量，即调用 `longest_trip` 的次数。
评测程序示例读取如下格式的输入数据：

* 第 $1$ 行：$C$

接下来是这 $C$ 个场景的描述数据。

评测程序示例读取每个场景如下格式的描述数据：

* 第 $1$ 行：$N \; D$
* 第 $1 + i$ 行（$1 \le i \lt N$）：$U_i[0] \; U_i[1] \; \ldots \; U_i[i-1]$

这里每个 $U_i$（$1 \le i \lt N$）均为长度为 $i$ 的数组，以给出那些有道路相连的地标配对。对于满足 $1 \le i \lt N$ 且 $0 \le j \lt i$ 的所有 $i$ 和 $j$：

* 如果地标 $j$ 和 $i$ 之间有道路相连，则 $U_i[j]$ 的值应为 $1$；
* 如果地标 $j$ 和 $i$ 之间没有道路相连，则 $U_i[j]$ 的值应为 $0$。

在每个场景中，在调用 `longest_trip` 之前，评测程序示例检查路网的密度是否至少为 $D$。如果不满足该条件，评测程序示例将输出信息 `Insufficient Density` 并中止。

如果检查出违反规则的行为，评测程序示例的输出为 `Protocol Violation: <MSG>`，这里 `<MSG>` 为如下错误信息之一：

* `invalid array`：在 `are_connected` 的某次调用中，数组 $A$ 和 $B$ 中至少其一
  - 为空，或
  - 有元素不是 $0$ 到 $N-1$ 之间（包含 $0$ 和 $N-1$）的整数，或
  - 有重复元素。
* `non-disjoint arrays`：在 `are_connected` 的某次调用中，数组 $A$ 和 $B$ 的交集不空。
* `too many calls`：函数 `are_connected` 在 `longest trip` 的当前调用中的被调用次数超过了 $32\,640$，或者其累计调用次数超过了 $150\,000$。
* `too many elements`：在 `are_connected` 的全部调用中，所传递的地标的累计数量超过了 $1\,500\,000$。

否则，令 `longest_trip` 函数在某个场景中的返回数组为 $t[0], t[1], \ldots, t[l - 1]$，这里 $l$ 为某个非负整数。评测程序示例将对该场景按照如下格式输出三行：

* 第 $1$ 行：$l$
* 第 $2$ 行：$t[0] \; t[1] \; \ldots \; t[l-1]$
* 第 $3$ 行：在该场景中调用 `are_connected` 的次数

最后，评测程序示例输出：

* 第 $1 + 3 \cdot C$ 行：在 `longest_trip` 的所有调用中，函数 `are_connected` 被调用的最多次数


title: [语言月赛 202309] pip install

type: B

description:
`pip install` 是 Python 安装包的重要指令。Python 的包具有依赖关系，在安装某些包之前，需要先安装这些包的依赖。

假定一共有依次编号为 $1 \sim N$ 的 $N$ 个包，第 $i$ 个包共有 $K_i$ 个依赖。现在，小 F 想要安装编号为 $1$ 的包。在完成 $1$ 号包及其全部依赖的安装，一共安装了多少个包？

inputFormat:
输入共 $N+1$ 行。

输入的第一行为一个正整数 $N$。

接下来 $N$ 行，第 $i$ 行描述了编号为 $i$ 的包的依赖：

- 第 $i$ 行共有 $K_i+1$ 个数。
- 第一个数为 $K_i$。
- 接下来 $K_i$ 个数，描述了所依赖的包的编号。

outputFormat: 输出一行一个整数，表示安装的包的数量。

hint: 对于 $100\%$ 的测试数据，$1 \le N \le 5000$，$0 \le K_i < N$，保证不会构成循环依赖。


title: [JRKSJ R8] 三七二十一

type: P

description:
给你一个由 $1\sim 9$ 的数字组成的数字串 $s$。定义一个数字串 $s$ 表示的数为将其看作十进制数得到的数。形式化地说，长为 $n$ 的数字串 $s$ 表示的数是 $\sum_{i=1}^n  10^{n-i}s_i$。

你可以对这个数字串执行若干次操作，每次操作中你可以选定一个位置 $1\le p\le n$ 并将 $s_p$ 修改为任意 $1\sim 9$ 中的数字。你需要使该数字串**不存在**任何一个非空子串满足这个子串表示的数字是 $2^k(k\in \N)$ 即 $2$ 的任意**非负整数**次幂，请你求出最少的操作次数。

inputFormat: 一行一个数字串 $s$。

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


title: [IOI2023] 超车

background:
这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

本题仅支持 C++ 语言提交。但请勿使用 C++14 (GCC 9)

description:
从布达佩斯机场到 Forrás 酒店有一条单向单车道的公路，公路的长度为 $L$ 公里。

IOI 2023 活动期间，有 $N+1$ 辆巴士在这条公路上行驶。巴士从 $0$ 到 $N$ 依次编号。巴士 $i$（$0 \le i \lt N$）计划在活动的第 $T[i]$ 秒从机场出发，行驶一公里用时 $W[i]$ 秒。巴士 $N$ 是备用巴士，行驶一公里用时 $X$ 秒。它从机场出发的时间 $Y$ 尚未确定。

巴士在这条公路上行驶时一般不允许超车，但允许在一些被称为**调度站**的地方进行超车。公路上一共有 $M$ 个调度站（$M \gt 1$），从 $0$ 到 $M - 1$ 依次编号，位于公路的不同位置。调度站 $j$（$0 \le j \lt M$）的位置在机场出发后沿公路的 $S[j]$ 公里处。调度站按照从机场开始的距离递增排列，也就是对于每个 $0 \le j \le M - 2$，有 $S[j] \lt S[j+1]$。首个调度站设在机场，最后一个设在酒店。也就是说，$S[0] = 0$，$S[M-1] = L$。

每辆巴士都以指定的最快速度行驶，除非它遇到前面有比它慢的巴士。在这种情况下，后面的快车会被前面的慢车压着，被迫以慢车的速度行驶。这种情况会持续到两车到达下一个调度站。在那里，快车会完成对慢车的超越。

形式化地说，对于满足 $0 \le i \le N$ 且 $0 \le j \lt M$ 的每组 $i$ 和 $j$，巴士 $i$ **到达**调度站 $j$ 的时间 $t_{i,j}$（以秒为单位）定义如下：对于每个 $0 \le i \lt N$，有 $t_{i,0} = T[i]$。另有 $t_{N,0} = Y$。对于满足 $0 \lt j \lt M$ 的每个 $j$：

* 定义巴士 $i$ 到达调度站 $j$ 的**期望到达时间** $e_{i,j}$（以秒为单位）为巴士 $i$ 到达调度站 $j-1$ 之后以全速行驶到达调度站 $j$ 的时间。也就是说，
  - 对于每个 $0 \le i \lt N$，有 $e_{i,j} = t_{i,j-1} + W[i] \cdot (S[j]-S[j-1])$；
  - 另有 $e_{N,j} = t_{N,j-1} + X \cdot (S[j]-S[j-1])$。
* 巴士 $i$ 到达调度站 $j$ 的时间，是巴士 $i$ 到达调度站 $j$ 的期望到达时间，以及其他比巴士 $i$ 早到调度站 $j-1$ 的巴士到达调度站 $j$ 的期望到达时间中的**最大值**。形式化地说，$t_{i,j}$ 是 $e_{i,j}$ 和所有满足 $0 \le k \le N$ 且 $t_{k,j-1} \lt t_{i,j-1}$ 的 $e_{k,j}$ 中的最大值。

IOI 组委会想要调度备用巴士（巴士 $N$）。你的任务是回答组委会的 $Q$ 个问题，问题的形式如下：给定备用巴士从机场出发的时间 $Y$（以秒为单位），它将于何时到达酒店？

outputFormat:
评测程序示例按以下格式打印你的答案：

* 第 $1 + k$ 行（$0 \le k \lt Q$）：问题 $k$ 中 `arrival_time` 的返回值


title: [集训队互测 2023] 基础寄术练习题

description:
对于长度为 $n$ 的序列 $a$，定义 $f(a)=\dfrac{1}{\prod\limits_{i=k}^ns_i}$，其中 $s_i$ 为 $\{a_n\}$ 的前缀和数组，**$k$ 是给定的常数且 $1\le k\le 2$**。

考虑所有满足以下三个条件的序列 $a$：

- $a$ 的长度为 $n$。
- $\forall i,j$，$a_i\ne a_j$。
- $1\le a_i\le m$。

求它们的 $f(a)$ 之和，答案对 $p$ 取模。保证 $p$ 是一个质数。

inputFormat: 第一行三个整数 $n,m,k,p$，分别代表序列长度，序列元素的上界和模数。

outputFormat: 一行一个整数表示答案对 $p$ 取模后的结果。

hint:
对于所有数据，保证 $2\le n\le m\le 100$，$10^8<p<1.07\times 10^9$ 且 $p$ 为质数，$1\le k\le 2$。

- Subtask 1 (10 pts)：$m\le 20$。
- Subtask 2 (25 pts)：$k=1$。
- Subtask 3 (15 pts)：$n=m\le 30$。
- Subtask 4 (10 pts)：$m\le 30$。
- Subtask 5 (15 pts)：$m\le 40$。
- Subtask 6 (10 pts)：$m\le 70$。
- Subtask 7 (15 pts)：$m\le 100$。


title: [IOI2023] 机器人比赛

background:
这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

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

---

由于某些技术原因，你可能需要在源代码的开头加入以下内容：

```cpp
#include <vector>

void program_pulibot();
void set_instruction(std::vector<int> S, int Z, char A);
```

description:
塞格德大学的人工智能研究人员正在举办一场机器人编程竞赛。
你的朋友 Hanga 决定参加比赛。由于著名的匈牙利牧羊犬品种 Puli 非常聪明，所以该比赛的目标定为编程实现顶级的 Pulibot。

Pulibot 将在由 $(H+2) \times (W+2)$ 网格组成的迷宫中进行测试。
网格的行从北到南编号为 $-1$ 到 $H$，网格的列从西到东编号为 $-1$ 到 $W$。
我们将位于网格的第 $r$ 行和第 $c$ 列的单元格（$-1 \le r \le H$, $-1 \le c \le W$）称为单元格 $(r,c)$。

考虑一个单元格 $(r,c)$ （$0 \le r \lt H$，$0 \le c \lt W$），和它**相邻**的有 $4$ 个单元格。

* 单元格 $(r,c-1)$ 被称为单元格 $(r,c)$ 的**西邻**；
* 单元格 $(r+1,c)$ 被称为单元格 $(r,c)$ 的**南邻**；
* 单元格 $(r,c+1)$ 被称为单元格 $(r,c)$ 的**东邻**；
* 单元格 $(r-1,c)$ 被称为单元格 $(r,c)$ 的**北邻**。

如果 $r=-1$ 或 $r=H$ 或 $c=-1$ 或 $c=W$ 成立，则单元格 $(r,c)$ 称为迷宫的**边界**。每个不是迷宫边界的单元格要么是**障碍**，要么是**空的**。
此外，每个空单元格都有一个**颜色**，由 $0$ 和 $Z_{\text{MAX}}$ 之间的非负整数表示，包括 $0$ 和 $Z_{\text{MAX}}$。最初，每个空单元格的颜色为 $0$。

例如，考虑一个迷宫，$H=4$， $W=5$， 包含一个障碍单元格 $(1,3)$。

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

唯一的障碍单元格用 $\times$ 表示。迷宫的边界单元格被阴影覆盖。
每个空单元格中的数字表示它的颜色。

从单元格 $(r_0, c_0)$ 到单元格 $(r_\ell, c_\ell)$ 的长度为 $\ell$（$\ell\gt 0$）的**路径**
是一个**空**单元格序列 $(r_0,c_0), (r_1, c_1), \ldots, (r_\ell, c_\ell)$，序列中的空单元格两两不同。其中对于每个 $i$（$0\le i\lt\ell$），单元格 $(r_i, c_i)$ 和 $(r_{i+1}, c_{i+1})$ 是相邻的。

注意长度为 $\ell$ 的路径正好包含 $\ell+1$ 个单元格。

在比赛中，研究人员设置了一个迷宫，其中至少有一条从单元格 $(0,0)$ 到单元格 $(H-1, W-1)$ 的路径。注意，这意味着单元格 $(0, 0)$ 和 $(H-1, W-1)$ 保证为空。

Hanga 不知道迷宫中哪些单元格是空的，哪些单元格是障碍。

你的任务是帮助 Hanga 对 Pulibot 进行编程，使其能够在研究人员设置的未知迷宫中找到从单元格 $(0,0)$ 到单元格 $(H-1, W-1)$ 的**最短路径**（即长度最小的路径）。
Pulibot 的说明和比赛规则如下所述。

注意，在题面的最后一部分描述了一个显示工具，该工具可以用于可视化 Pulibot。

### Pulibot 说明

对每个单元格 $(r,c)$（$-1 \le r \le H$ ，$-1 \le c \le W$），其**状态**定义为一个整数，具体如下：
* 如果单元格 $(r,c)$ 是边界，则其状态为 $-2$；
* 如果单元格 $(r,c)$ 是障碍，则其状态为 $-1$；
* 如果单元格 $(r,c)$ 是空的，那么它的状态就是单元格的颜色。

Pulibot 的程序是按一系列步骤执行的。在每一步中，Pulibot 都会识别附近单元格的状态，然后执行一条指令。它执行的指令由识别的状态决定。以下是更准确的描述。

假设在当前步骤开始时，Pulibot位于单元格 $(r,c)$，这是一个空单元格。该步骤执行如下：

1. 首先，Pulibot 识别当前**状态数组**，即数组 $S = [S[0], S[1], S[2], S[3], S[4]]$， 它包含单元格 $(r,c)$ 及其所有相邻单元格的状态：
    * $S[0]$ 表示单元格 $(r,c)$ 的状态。
    * $S[1]$ 表示西邻的状态。
    * $S[2]$ 表示南邻的状态。
    * $S[3]$ 表示东邻的状态。
    * $S[4]$ 表示北邻的状态。
1. 然后，Pulibot 确定与所识别的状态数组相对应的**指令** $(Z, A)$。
1. 最后，Pulibot 执行这条指令：它将单元格 $(r,c)$ 的颜色设置为 $Z$，然后它执行动作 $A$, $A$ 是以下动作之一：
    * **停留** 在单元格 $(r,c)$；
    * **移动** 到 $4$ 个邻居之一；
    * **终止程序**。

例如，考虑下图左侧显示的场景。Pulibot 当前位于单元格$(0,0)$，颜色为$0$。
Pulibot 识别出状态数组 $S=[0, -2, 2, 2, -2]$。Pulibot 可能有一个程序，该程序根据所识别的数组，将当前单元格的颜色设置为 $Z=1$，然后向东移动，如图的中间和右侧所示：

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

### 机器人比赛规则

* 在开始时，Pulibot 被放置在单元格 $(0,0)$ 并开始执行其程序。
* 不允许 Pulibot 移动到非空单元格。
* Pulibot 的程序必须在最多 $500\,000$ 步后终止。
* 在 Pulibot 的程序终止后，迷宫中的空单元格的着色满足以下要求：
  - 存在从 $(0,0)$ 到 $(H-1, W-1)$ 的最短路径，路径中包括的每个单元格的颜色为 $1$。
  - 所有其他空单元格的颜色为 $0$。
* Pulibot 可以在任何空单元格终止其程序。

例如，下图显示了一个可能的迷宫，其中$H=W=6$。左侧显示了初始配置，右侧显示了程序终止后空单元格的一种可以接受的着色：

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

inputFormat:
你要实现以下函数：

```
void program_pulibot()
```

* 这个函数应该产生 Pulibot 的程序。对于所有 $H$ 和 $W$ 的取值以及满足题目约束条件的任何迷宫，该程序应该都能正确工作。
* 对于每个测试用例，此函数只调用一次。

此函数可以调用以下函数来生成 Pulibot 的程序：

```
void set_instruction(int[] S, int Z, char A)
```

* $S$: 长度为 $5$ 的数组，用来描述状态数组
* $Z$: 表示颜色的非负整数
* $A$: 表示 Pulibot 动作的单个字符，具体如下:
    - `H`: 停留;
    - `W`: 移动到西邻;
    - `S`: 移动到南邻;
    - `E`: 移动到东邻;
    - `N`: 移动到北邻;
    - `T`: 终止程序。
* 调用此函数指示 Pulibot 在识别状态数组 $S$ 时应执行指令 $(Z, A)$。

用相同的状态数组 $S$ 多次调用该函数将导致  `Output isn't correct` 的判定结果。

不需要对每个可能的状态数组 $S$ 调用 `set_instruction`。 但是，如果 Pulibot 后来识别出未设置指令的状态数组，你将得到 `Output isn't correct` 的判定结果。

`program_pulibot` 完成后，评测程序会在一个或多个迷宫上调用 Pulibot 的程序。
这些调用**不**计入解决方案的时间限制。
评测程序**不**是自适应的，也就是说，每个测试用例的迷宫集合都是预先确定的。

如果 Pulibot 在终止程序之前违反了任何机器人比赛规则，你将得到 `Output isn't correct` 的判定结果。

outputFormat:
函数 `program_pulibot` 可以调用 `set_instruction` 如下：

调用                             | 对应状态数组 $S$ 的指令
:-------------------------------------------:|:---------------------------------------:
`set_instruction([0, -2, -1, 0, -2], 1, E)`  | 着色 $1$ 并且东移
`set_instruction([0, 1, -1, 0, -2], 1, E)`   | 着色 $1$ 并且东移
`set_instruction([0, 1, 0, -2, -2], 1, S)`   | 着色 $1$ 并且南移
`set_instruction([0, -1, -2, -2, 1], 1, T)`  | 着色 $1$ 并且终止程序

考虑一个场景，$H=2$， $W=3$，迷宫如下图所示。

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

对于这个特定的迷宫，Pulibot 的程序分四个步骤运行。 Pulibot 识别的状态数组和它执行的指令正好依次对应上述对“set_instruction”的四次调用。 这些指令的最后一条指令终止程序。

下图展示了四个步骤每一步之前的迷宫以及终止后的最终颜色。

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

但是，注意这个由 $4$ 条指令构成的程序有可能在其他合法的迷宫中找不到最短路径。
所以，如果这个程序被提交，它会收到 `Output isn't correct` 的判定结果。

hint:
## 约束条件

$Z_{\text{MAX}} = 19$。因此，Pulibot 可以使用 0 到 19 的颜色，包含 0 和 19。

对于每个用来测试Pulibot的迷宫：
* $2 \le H, W \le 15$
* 至少有一条从单元格 $(0,0)$ 到 $(H-1, W-1)$ 的路径。

## 子任务

1. （6 分）迷宫中没有障碍单元格。
1. （10 分）$H = 2$
1. （18 分）任意两个空单元格之间恰好有一条路径。
1. （20 分）从单元格 $(0,0)$ 到 $(H-1, W-1)$ 的最短路径的长度为 $H + W - 2$。
1. （46 分）无额外约束条件。

如果在任何测试用例中，对函数 `set_instruction` 的调用或 Pulibot 程序的执行不符合“实现细节”中所描述的限制条件，则该子任务的解决方案得分将为 $0$。

在每个子任务中，你可以通过生成几乎正确的着色来获得部分分数。

形式化地说：

* 如果空单元格的最终颜色满足机器人竞赛规则，则测试用例的解决方案是**完整**的。
* 如果最终着色如下所示，则测试用例的解决方案是**部分**的：
   - 存在一条从 $(0,0)$ 到 $(H-1, W-1)$ 的最短路径，路径中包含的每个单元格的颜色为 $1$。
   - 网格中没有其他颜色为 $1$ 的空单元格。
   - 网格中的某些空单元格的颜色既不是 $0$ 也不是 $1$。

如果你对某个测试用例的解决方案既不完整也不部分，则该测试用例的得分将为 $0$。

在子任务 1-4 中，对每个测试用例来说，完整解决方案的计分为该子任务分数的 100%，部分解决方案的计分为该子任务分数的 50%。

在子任务 5 中，你的分数取决于 Pulibot 程序中所使用颜色的数量。
更准确地说，用 $Z^\star$ 表示对 `set_instruction` 进行的所有调用中 $Z$ 的最大值。
测试用例上的得分按下表计算：

| 条件            | 分数 (完整)      | 分数 (部分)       |
|:-----------------------:|:---------------------:|:---------------------:|
| $11 \le Z^\star \le 19$ | $20 + (19 - Z^\star)$ | $12 + (19 - Z^\star)$ |
| $Z^\star = 10$          | $31$                  | $23$                  |
| $Z^\star = 9$           | $34$                  | $26$                  |
| $Z^\star = 8$           | $38$                  | $29$                  |
| $Z^\star = 7$           | $42$                  | $32$                  |
| $Z^\star \le 6$         | $46$                  | $36$                  |

每个子任务的得分是该子任务中所有测试用例上计分的最小值。

## 评测程序示例

评测程序示例按照以下格式读取输入：
* 第 $1$ 行: $H \; W$
* 第 $2 + r$ 行 ($0 \le r \lt H$): $m[r][0] \; m[r][1] \; \ldots \; m[r][W-1]$

其中，$m$ 是一个 $H$ 行 $W$ 列的二维整数数组，描述迷宫中非边界单元格。
如果单元格 $(r, c)$ 是空的，$m[r][c] = 0$；如果单元格 $(r, c)$ 是障碍， $m[r][c] = 1$。

评测程序示例首先调用 `program_pulibot()`。如果评测程序示例检测到违反规则的行为，则会打印 `Protocol Violation: <MSG>` 并终止，其中 `<MSG>` 是以下错误消息之一：

* `Invalid array`：$-2 \le S[i] \le Z_{\text{MAX}}$ 对某些 $i$ 不成立或者 $S$ 的长度不是 $5$。
* `Invalid color`：$0 \le Z \le Z_{\text{MAX}}$ 不成立。
* `Invalid action`：字符 $A$ 不是 `H`, `W`, `S`, `E`, `N` 或 `T`。
* `Same state array`：用相同的 $S$ 调用 `set_instruction` 两次或以上。

否则，当 `program_pulibot` 完成时，评测程序示例将在输入所描述的迷宫中执行 Pulibot 的程序。

评测程序示例产生两个输出。首先，评测程序示例将 Pulibot 动作记录写入工作目录中的文件 `robot.bin` 。
该文件用作下一节中描述的可视化工具的输入。

其次，如果 Pulibot 的程序未成功终止，评测程序示例将打印以下错误消息之一：

* `Unexpected state`：Pulibot 识别出一个无法调用“set_instruction”的状态数组。
* `Invalid move`：执行一个动作，导致 Pulibot 移动到一个非空单元格。
* `Too many steps`：Pulibot 执行了 $500\,000$ 步没有终止程序。

否则，令 $e[r][c]$ 为 Pulibot 程序终止后单元格 $(r, c)$ 的状态。
评测程序示例按以下格式打印 $H$ 行：
* 第 $1 + r$ 行 ($0 \le r \lt H$)：$e[r][0] \; e[r][1] \; \ldots \; e[r][W-1]$

## 显示工具

此任务的附件包含有一个名为 `display.py` 的文件。
调用时，此 Python 脚本会显示 Pulibot 在由评测程序示例的输入所描述的迷宫中的操作。
为此，工作目录中要有二进制文件 `robot.bin`。

要调用该脚本，请执行以下命令。

```
python3 display.py
```

一个简单的图形界面将会出现，主要特性如下：

* 你可以观察整个迷宫的状态。 Pulibot 的当前位置以矩形突出显示。
* 你可以通过单击箭头按钮或按热键来浏览 Pulibot 的步骤。 你还可以跳转到特定步骤。
* Pulibot 程序中即将进行的步骤显示在底部。
它显示当前状态数组及将要执行的指令。
在最后一步之后，它或者会显示评测程序的错误消息之一，或者在程序成功终止时显示 `Terminated`。
* 对于代表颜色的每个数字，你可以指定视觉背景颜色以及显示的文本。 显示的文本是一个短字符串，应出现在每个具有那个颜色的单元格。你可以通过以下任一方式指定背景颜色和显示的文本：
   - 单击 `Colors` 按钮后在对话框窗口中设置它们。
   - 编辑 `colors.txt` 文件的内容。
* 要重新加载 `robot.bin`，请使用 `Reload` 按钮。 这可以用来处理 `robot.bin` 的内容发生更改的情况。


title: [SNCPC2019] Digit Mode

description:
Let $m(x)$ be the $\textit{mode}$ of the digits in decimal representation of positive integer $x$. The mode is the largest value that occurs most frequently in the sequence. For example, $m(15532)=5$, $m(25252)=2$, $m(103000)=0$, $m(364364)=6$, $m(114514)=1$, $m(889464)=8$.

Given a positive integer $n$, DreamGrid would like to know the value of $(\sum\limits_{x=1}^{n} m(x)) \bmod (10^9+7)$.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains a positive integer $n$ ($1 \le n < 10^{50}$) without leading zeros.

It's guaranteed that the sum of $|n|$ of all test cases will not exceed $50$, where $|n|$ indicates the number of digits of $n$ in decimal representation.

outputFormat: For each test case output one line containing one integer, indicating the value of $(\sum\limits_{x=1}^{n} m(x)) \bmod (10^9+7)$.


title: [SNCPC2019] Grid with Arrows

description:
BaoBao has just found a grid with $n$ rows and $m$ columns in his left pocket, where the cell in the $j$-th column of the $i$-th row (indicated by $(i, j)$) contains an arrow (pointing either upwards, downwards, leftwards or rightwards) and an integer $a_{i, j}$.

BaoBao decides to play a game with the grid. He will first select a cell as the initial cell and tick it. After ticking a cell (let's say BaoBao has just ticked cell $(i, j)$), BaoBao will go on ticking another cell according to the arrow and the integer in cell $(i, j)$.

- If the arrow in cell $(i, j)$ points upwards, BaoBao will go on ticking cell $(i-a_{i, j}, j)$ if it exists.
- If the arrow in cell $(i, j)$ points downwards, BaoBao will go on ticking cell $(i+a_{i, j}, j)$ if it exists.
- If the arrow in cell $(i, j)$ points leftwards, BaoBao will go on ticking cell $(i, j-a_{i, j})$ if it exists.
- If the arrow in cell $(i, j)$ points rightwards, BaoBao will go on ticking cell $(i, j+a_{i, j})$ if it exists.

If the cell BaoBao decides to tick does not exist, or if the cell is already ticked, the game ends.

BaoBao is wondering if he can select a proper initial cell, so that he can tick every cell in the grid exactly once before the game ends. Please help him find the answer.

inputFormat:
There are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \times m \le 10^5$), indicating the number of rows and columns of the grid.

For the following $n$ lines, the $i$-th line contains a string $s_i$ consisting of lowercased English letters ($|s_i| = m$, $s_{i, j} \in \{\text{`u' (ascii: 117)}, \text{`d' (ascii: 100)}, \text{`l' (ascii: 108)}, \text{`r'(ascii: 114)}\}$), where $s_{i, j}$ indicates the direction of arrow in cell $(i, j)$.

- If $s_{i, j} = \text{`u'}$, the arrow in cell $(i, j)$ points upwards.
- If $s_{i, j} = \text{`d'}$, the arrow in cell $(i, j)$ points downwards.
- If $s_{i, j} = \text{`l'}$, the arrow in cell $(i, j)$ points leftwards.
- If $s_{i, j} = \text{`r'}$, the arrow in cell $(i, j)$ points rightwards.

For the following $n$ lines, the $i$-th line contains $m$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ ($1 \le a_{i, j} \le \max(n, m)$), where $a_{i, j}$ indicates the integer in cell $(i, j)$.

It's guaranteed that the sum of $n \times m$ of all test cases does not exceed $10^6$.

outputFormat: For each test case output one line. If BaoBao can find a proper initial cell, print ``Yes`` (without quotes), otherwise print ``No`` (without quotes).

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

宝宝刚刚在他的左口袋里发现了一个 $n$ 行 $m$ 列的网格，其中第 $i$ 行第 $j$ 列的单元格（表示为 $(i, j)$）包含一个箭头（指向上、下、左或右）和一个整数 $a_{i, j}$。

宝宝决定用这个网格玩一个游戏。他首先会选择一个单元格作为初始单元格并标记它。在标记一个单元格之后（假设宝宝刚刚标记了单元格 $(i, j)$），宝宝将根据单元格 $(i, j)$ 中的箭头和整数继续标记另一个单元格。

- 如果单元格 $(i, j)$ 中的箭头指向上方，宝宝将继续标记单元格 $(i-a_{i, j}, j)$，如果该单元格存在的话。
- 如果单元格 $(i, j)$ 中的箭头指向下方，宝宝将继续标记单元格 $(i+a_{i, j}, j)$，如果该单元格存在的话。
- 如果单元格 $(i, j)$ 中的箭头指向左方，宝宝将继续标记单元格 $(i, j-a_{i, j})$，如果该单元格存在的话。
- 如果单元格 $(i, j)$ 中的箭头指向右方，宝宝将继续标记单元格 $(i, j+a_{i, j})$，如果该单元格存在的话。
如果宝宝决定标记的单元格不存在，或者该单元格已经被标记，游戏结束。

宝宝想知道他是否可以选择一个合适的初始单元格，以便在游戏结束前恰好标记网格中的每一个单元格一次。请帮助他找到答案。

**【输入格式】**

有多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \times m \le 10^5$)，表示网格的行数和列数。

接下来的 $n$ 行中，第 $i$ 行包含一个字符串 $s_i$，由小写英文字母组成（$|s_i| = m$，$s_{i, j} \in \{\text{`u' (ascii: 117)}, \text{`d' (ascii: 100)}, \text{`l' (ascii: 108)}, \text{`r'(ascii: 114)}\}$），其中 $s_{i, j}$ 表示单元格 $(i, j)$ 中箭头的方向。

- 如果 $s_{i, j} = \text{`u'}$，单元格 $(i, j)$ 中的箭头指向上方。
- 如果 $s_{i, j} = \text{`d'}$，单元格 $(i, j)$ 中的箭头指向下方。
- 如果 $s_{i, j} = \text{`l'}$，单元格 $(i, j)$ 中的箭头指向左方。
- 如果 $s_{i, j} = \text{`r'}$，单元格 $(i, j)$ 中的箭头指向右方。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ ($1 \le a_{i, j} \le \max(n, m)$)，其中 $a_{i, j}$ 表示单元格 $(i, j)$ 中的整数。

保证所有测试用例的 $n \times m$ 之和不超过 $10^6$。

**【输出格式】**

对于每个测试用例输出一行。如果宝宝可以找到一个合适的初始单元格，输出 “Yes”（不含引号），否则输出 “No”（不含引号）。

**【样例解释】**

对于第一个示例测试用例，宝宝可以选择单元格 $(1, 2)$ 作为初始单元格，这样他可以按以下顺序恰好打勾所有单元格：$(1, 2), (2, 2), (2, 3), (2, 1), (1, 1), (1, 3)$。

对于第二个示例测试用例，无论选择哪个单元格作为初始单元格，宝宝最多只能打勾 2 个单元格。

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

hint:
For the first sample test case, BaoBao can select cell $(1, 2)$ as the initial cell, so that he can tick all the cells exactly once in the following order: $(1, 2), (2, 2), (2, 3), (2, 1), (1, 1), (1, 3)$.

For the second sample test case, BaoBao can only tick at most $2$ cells no matter which cell is selected as the initial cell.


title: [SNCPC2019] 0689

description:
We call a string as a 0689-string if this string only consists of digits `0`, `6`, `8` and `9`. Given a 0689-string $s$ of length $n$, one $\textbf{must}$ do the following operation exactly once: select a non-empty substring of $s$ and rotate it 180 degrees.

More formally, let $s_i$ be the $i$-th character in string $s$. After rotating the substring starting from $s_l$ and ending at $s_r$ 180 degrees ($1 \le l \le r \le n$), string $s$ will become string $t$ of length $n$ extracted from the following equation, where $t_i$ indicates the $i$-th character in string $t$:

$$t_i = \begin{cases}
s_i & \text{if } 1 \le i < l \text{ or } r < i \le n \\
\text{`0'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`0'} \\
\text{`6'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`9'} \\
\text{`8'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`8'} \\
\text{`9'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`6'} \\
\end{cases}$$

What's the number of different strings one can get after the operation?

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains a 0689-string $s$ ($1 \le |s| \le 10^6$).

It's guaranteed that the sum of $|s|$ of all test cases will not exceed $10^7$.

outputFormat: For each test case output one line containing one integer, indicating the number of different strings one can get after applying the operation exactly once.

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

我们称一个字符串为 0689-字符串，如果这个字符串只包含数字 0、6、8 和 9。给定一个长度为 $n$ 的 0689-字符串 $s$，必须执行以下操作一次：选择 $s$ 的一个非空子串并将其旋转 180 度。

更正式地说，设 $s_i$ 为字符串 $s$ 的第 $i$ 个字符。在将从 $s_l$ 开始到 $s_r$ 结束的子串旋转180度后 ($1 \le l \le r \le n$)，字符串 $s$ 将变成长度为 $n$ 的字符串 $t$，其通过以下公式得到，其中 $t_i$ 表示字符串 $t$ 中的第 $i$ 个字符：

$$t_i = \begin{cases}
s_i & \text{if } 1 \le i < l \text{ or } r < i \le n \\
\text{`0'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`0'} \\
\text{`6'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`9'} \\
\text{`8'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`8'} \\
\text{`9'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`6'} \\
\end{cases}$$

经过这个操作后，可以得到多少个不同的字符串？

**【输入格式】**

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：
- 第一行且唯一一行包含一个 0689-字符串 $s$ ($1 \le |s| \le 10^6$)。
保证所有测试用例的 $|s|$ 之和不超过 $10^7$。

**【输出格式】**

对于每个测试用例输出一行，包含一个整数，表示经过一次操作可以得到的不同字符串的数量。

**【样例解释】**

我们在此解释第一个样例测试用例。
$$\begin{array}{|c|c||c|c|}\hline \textbf{子串} & \textbf{结果} & \textbf{子串} & \textbf{结果} \\ \hline 0 & 0689 & 68 & 0899 \\ \hline 6 & 0989 & 89 & 0668 \\ \hline 8 & 0689 & 068 & 8909 \\ \hline 9 & 0686 & 689 & 0689 \\ \hline 06 & 9089 & 0689 & 6890 \\ \hline \end{array}$$
很容易发现，经过这个操作可以得到 8 个不同的字符串。

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

hint:
We hereby explain the first sample test case.

$$\begin{array}{|c|c||c|c|}\hline \textbf{Substring} & \textbf{Result} & \textbf{Substring} & \textbf{Result} \\ \hline 0 & 0689 & 68 & 0899 \\ \hline 6 & 0989 & 89 & 0668 \\ \hline 8 & 0689 & 068 & 8909 \\ \hline 9 & 0686 & 689 & 0689 \\ \hline 06 & 9089 & 0689 & 6890 \\ \hline \end{array}$$

It's easy to discover that we can get $8$ different strings after the operation.


title: [SNCPC2019] Pick Up

description:
Grid City is a city on an infinite two-dimensional plane, where for all $k \in \mathbb{Z}$ ($\mathbb{Z}$ is the set of all integers) lines $x = k$ and $y = k$ are the streets of the city. People can only move along the roads to go from one position to another. That's why the city is called the Grid City!

Two friends, BaoBao and DreamGrid, live happily in the city. Today BaoBao is heading from his home positioned at $(x_A, y_A)$ ($x_A, y_A \in \mathbb{Z}$) towards the shopping mall positioned at $(x_C, y_C)$ ($x_C, y_C \in \mathbb{Z}$). However, it's too far for him to walk there, so he decides to call DreamGrid whose home is positioned at $(x_B, y_B)$ ($x_B, y_B \in \mathbb{Z}$) for help.

BaoBao and DreamGrid set out separately from their homes at the same time. Different from BaoBao who walks at a speed of $a$ units per minute, DreamGrid drives a car and moves at a speed of $b$ units per minute. When DreamGrid and BaoBao meet at the same point, DreamGrid can pick up BaoBao and they can then move at a speed of $b$ units per minute together. It takes no time to turn around or pick up BaoBao.

What's the minimum time needed for BaoBao to go from his home to the shopping mall? Note that it's NOT necessary for DreamGrid to pick up BaoBao if it will be faster for BaoBao to get to the destination.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$($ 1 \le T \le 10^5$), indicating the number of test cases. For each test case:

The first line contains two integers $a$ and $b$ ($1 \le a < b \le 10^9$), indicating the walking speed of BaoBao and the driving speed of DreamGrid.

The second line contains six integers $x_A$, $y_A$, $x_B$, $y_B$, $x_C$ and $y_C$ ($-10^9 \le x_A, y_A, x_B, y_B, x_C, y_C \le 10^9$), indicating the position of BaoBao's home, DreamGrid's home and the shopping mall. It's guaranteed that these three points are different from each other.

outputFormat: For each test case output one line containing one number, indicating the shortest time for BaoBao to arrive at the shopping mall. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

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

格子城是一个位于无限二维平面上的城市，其中对于所有 $k \in \mathbb{Z}$（$\mathbb{Z}$ 是所有整数的集合），直线 $x = k$ 和 $y = k$ 是城市的街道。人们只能沿着道路从一个位置移动到另一个位置。这就是为什么这个城市被称为格子城！

两个朋友，宝宝和梦想格子，快乐地生活在这个城市里。今天宝宝正从他位于 $(x_A, y_A)$（$x_A, y_A \in \mathbb{Z}$）的家出发，前往位于 $(x_C, y_C)$（$x_C, y_C \in \mathbb{Z}$）的购物中心。然而，这段路对他来说太远了，所以他决定叫住在 $(x_B, y_B)$（$x_B, y_B \in \mathbb{Z}$）的梦想格子来帮忙。

宝宝和梦想格子同时从他们的家出发。不同于以每分钟 $a$ 个单位速度步行的宝宝，梦想格子开车并以每分钟 $b$ 个单位速度移动。当梦想格子和宝宝在同一个点相遇时，梦想格子可以接上宝宝，然后他们可以一起以每分钟 $b$ 个单位速度移动。转身或接上宝宝不需要时间。

从宝宝的家到购物中心所需的最短时间是多少？请注意，如果梦想格子接上宝宝会更慢，则不需要梦想格子接宝宝。

**【输入格式】**

有多个测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $a$ 和 $b$（$1 \le a < b \le 10^9$），表示宝宝的步行速度和梦想格子的驾驶速度。

第二行包含六个整数 $x_A$，$y_A$，$x_B$，$y_B$，$x_C$ 和 $y_C$（$-10^9 \le x_A, y_A, x_B, y_B, x_C, y_C \le 10^9$），表示宝宝的家、梦想格子的家和购物中心的位置。保证这三点互不相同。

**【输出格式】**

对于每个测试用例，输出一行，包含一个数字，表示宝宝到达购物中心的最短时间。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则将被视为正确。

**【样例解释】**

对于第一个样例测试用例，宝宝和梦想格子将在 $D(1,2)$ 相遇，然后梦想格子载着宝宝去购物中心。

对于第二个样例测试用例，宝宝和梦想格子将在 $D(1.5,1)$ 相遇，然后梦想格子载着宝宝去购物中心。

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

hint:
For the first sample test case, BaoBao and DreamGrid will meet at $D(1,2)$ and then DreamGrid drives BaoBao to the shopping mall.

For the second sample test case, BaoBao and DreamGrid will meet at $D(1.5,1)$ and then DreamGrid drives BaoBao to the shopping mall.

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


title: Judg.

description:
小 M 正在兴致勃勃地敲打着代码，他突然发现提交代码的评测机无响应了。

你查看了后台数据，请你根据这些已有数据判断他没有通过的测试点有哪些。

已知评测结果与测试点是否通过有如下关系：

|评测结果|测试点是否通过|
| :-----------: | :-----------: |
| $\texttt{AC}$ | 是 |
| $\texttt{WA}$ | 否 |
| $\texttt{TLE}$ | 否 |
| $\texttt{MLE}$ | 否 |

inputFormat:
第一行输入一个正整数 $n$，表示评测数据的个数。

第 $2 \sim n+1$ 行，每行输入一个字符串，依次表示测试点 $1\sim n$ 的评测结果，数据保证这些字符串一定为 $\{\texttt{AC},\texttt{WA},\texttt{TLE},\texttt{MLE}\}$ 中的一个。

outputFormat:
输出一行 $m$ 个正整数，其中第 $i$ 个数字 $a_i$ 表示第 $a_i$ 个测试点没有通过。

特别地，你需要保证这 $m$ 个数字递增。

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

对于所有测试数据，满足 $1 \le n \le 10^5$，输入的字符串一定在 $\{\texttt{AC},\texttt{WA},\texttt{TLE},\texttt{MLE}\}$ 之中。

**本题开启捆绑测试，所有数据范围均相同的测试点捆绑为一个 $\text{Subtask}$。**

各测试点的附加限制如下表所示。

|测试点 |$n \le$  |
| :-----------: | :-----------: |
| $1 \sim 5$ | $10$ |
| $6 \sim 12$ | $2 \times 10^3$ |
| $13 \sim 20$ | $10^5$ |


title: 挑战 NPC IV

background: 要是什么都和 NPC 问题一样简单就好了啊。

description:
小 A 想为小 B 写一首情诗。他现在想出了 $n$ 个句子，每个句子的优美度分别为 $1, 2 \dots n$。小 A 需要按照一定的顺序将他们组合起来，拼成一首完整的诗。换句话说，小 A 需要重新排列这 $n$ 个句子，形成一个 $1 \sim n$ 的排列 $p_1, p_2\dots p_n$；第 $i$ 行诗句的优美度就是原先第 $p_i$ 个句子的优美度，也就是 $p_i$。

不过，由于小 A 是位 OIer，所以他的文采并不是很稳定。他实际上会严重高估自己诗句的优美程度。若一条诗句在小 A 眼里的优美度为 $x$，那么小 B 认为它的优美度是 **$x$ 在二进制表示下最低位的 $1$ 的位置**。其中，小 B 认为最低位的位置是 $1$，次低位为 $2$，以此类推。也就是说，小 B 眼中的优美度 $f(x)$ 为 $1 + \log_2 \operatorname{lowbit}(x)$。

小 A 知道，小 B 拿到诗后，只会选取诗的一段来看，而她感受到的优美度是所有她读到的诗句之和。具体的，若诗有 $n$ 句，则小 B 会在 $[1, n]$ 的所有长度 $> 0$ 的区间中抽取一个 $[l, r]$，感受到 $\displaystyle\sum_{l \leq i \leq r}f(p_i)$ 的优美度。小 A 为了衡量一首诗的优美度，决定将一首诗的总优美度定义为 **所有情况下小 B 感受到的优美度之和**。

照理来说，总优美度最大的组合方式必然是最好的。遗憾的是，在小 A 的精密计算下，他发现，只有他选择总优美度恰好为 **第 $k$ 小** 的情诗时，他才最有可能和小 B 走到一起。于是，小 A 想要知道，对于 $n!$ 首本质不同的诗，第 $k$ 小可能的总优美度是多少。两首诗本质相同当且仅当原排列 $p_1 \dots p_n$ 相同。

小 A 发现这是一个 NPC 问题，他只好来向你求助了。由于总优美度过于巨大，你只需要帮他求出答案对 $998244353$ 取模后的结果。

特别的，小 A 写了 $q$ 组诗句，所以你需要分别回答他的 $q$ 个问题。

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

第一行一个正整数 $q$，表示诗句的组数。

对于每组数据，仅一行两个正整数 $n, k$ 描述小 A 的问题。

outputFormat:
输出到标准输出。

对于每组诗句，输出一行一个整数，表示第 $k$ 小的总优美度对 $998244353$ 取模后的结果。


title: Maps.

description:
小 Y 希望得到一幅地图，这份地图有些与众不同。

这份地图是一幅长为 $n$ 个单位，宽为一个单位的网格图，每个网格必须被涂鸦成白色（$0$）或者黑色（$1$）。

你希望满足小 Y 的愿望送给他一幅这样的地图，但是这时小 Y 又提出了两点要求：

- 对于每个不在网格图两端的白色格子，恰好有 $p$ 个满足它的左右两个格子都被涂鸦成黑色。
- 在满足上述所有条件的情况下，这幅地图从左到右的字符构成的字符串的字典序最小。

你心想，这些要求也是小菜一碟，于是开始了你的创作。

inputFormat:
本题有多组数据。

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

对于每组数据：

输入共一行两个整数 $n,p$，表示你需要构造的地图的长度和小 Y 对你的要求。

outputFormat: 对于每组数据：输出一行一个长度为 $n$ 的 01 字符串，表示你构造的地图；如果无法找到任何一幅地图满足小 Y 的要求，输出 $-1$。

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

对于第一组数据：只有位于第 $4$ 个字符上的数，满足本身是 $0$，不在地图边缘且周围两个都是 $1$，因此符合条件。可以证明这是满足条件的字典序最小的方案。

对于第三组数据：可以证明没有任何一个解满足长度为 $5$ 且有 $3$ 个数本身是 $0$，不在地图边缘且周围两个字符都是 $1$。

#### 【数据范围】

对于所有测试数据，满足 $1 \le T \le 100$，$1 \le n,p \le 10^5$。

**本题开启捆绑测试，所有数据范围均相同的测试点捆绑为一个 $\text{Subtask}$。**

各测试点的附加限制如下表所示。

| 测试点 | $n,p \le$ |
| :-----------: | :-----------: |
| $1 \sim 3$ | $10$ |
| $4 \sim 5$ | $10^3$ |
| $6\sim 10$ | $10^5$ |


title: 【MX-S2-T4】换

description:
给定 $n,V$ 和一个长为 $m$ 的序列 $(p_1,q_1),(p_2,q_2),\dots,(p_m,q_m)$。

请求出有多少长度为 $n$ 的正整数序列 $a$，其所有元素 $a_i$ 满足 $1\le a_i\le V$，将其按 $k=1,2,\dots,m$ 依次执行如下操作后，$a$ 不降：

- 若 $a_{p_k}>a_{q_k}$，则交换 $a_{p_k}$ 与 $a_{q_k}$ 的值。

答案对 $10^9+7$ 取模。

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

接下来 $m$ 行，每行两个整数 $p_k,q_k$。

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


title: 「QFOI R1」摸摸

description:
小 R 是一个可爱的女孩子，她喜欢被摸头。

但是摸头之前，必须答对她提出的一个问题。

她有一个长度为 $n$ 的数列 $a$，初始时所有元素均为 $0$。另有两个长度为 $n$ 的数列 $t,b$。

她可以进行两种操作：

1. 将 $t$ 与 $t$ 的倒序对应元素相加，得到新的 $t$。
    - 例如，$t=[1,4,2]$ 变为 $t'=[1+2,4+4,2+1]=[3,8,3]$。
2. 将 $a$ 与 $t$ 对应元素相加，得到新的 $a$。
    - 例如，$a=[1,2,3],t=[1,4,2]$ 变为 $a'=[1+1,2+4,3+2]=[2,6,5]$。

是否可能通过若干次以上操作将 $a$ 变为 $b$？

你希望摸她的头 $T$ 次，因此有 $T$ 组数据。

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

对于每组数据：

- 第一行一个整数 $n$，表示数列长度。
- 第二行 $n$ 个整数，第 $i$ 个整数为 $t_i$。
- 第三行 $n$ 个整数，第 $i$ 个整数为 $b_i$。

outputFormat:
共 $T$ 行，每行一个为 `Yes` 或 `No` 的字符串，表示每组数据是否可能将 $a$ 变为 $b$。

字符串不区分大小写，如果答案为 `Yes` 的话，`yes`、`YES`、`yEs` 等都将被判为正确。

hint:
**样例解释**

对于第一组数据：

- 初始时：$a=[0,0,0]$，$t=[1,2,2]$，$b=[5,8,7]$。
- 执行操作二：$a=[1,2,2]$，$t=[1,2,2]$，$b=[5,8,7]$。
- 执行操作二：$a=[2,4,4]$，$t=[1,2,2]$，$b=[5,8,7]$。
- 执行操作一：$a=[2,4,4]$，$t=[3,4,3]$，$b=[5,8,7]$。
- 执行操作二：$a=[5,8,7]$，$t=[3,4,3]$，$b=[5,8,7]$。

此时 $a=b$，符合要求。

对于第二组数据，可以证明不存在合法方案。

---

**数据范围**

本题共 $20$ 个测试点，每个测试点 $5$ 分。

记 $\sum n$ 表示每组数据的 $n$ 之和。

对于全部数据，保证 $1\le\sum n\le 2\times 10^3$，$n\ge 1$，$1\le t_i,b_i\le 2\times 10^3$。

- 对于测试点 $1\sim 4$：保证 $n\le 2$。
- 对于测试点 $5\sim 8$：保证所有 $t_i$ 都相等。
- 对于测试点 $9\sim 12$：保证 $b_i=b_{n-i+1}$。
- 对于测试点 $13\sim 16$：保证 $\sum n,t_i,b_i\le 200$。
- 对于测试点 $17\sim 20$：无特殊限制。

---

**Hack 数据**

本题在赛后添加了 Hack 数据，从 $21$ 开始编号。

原有测试点依然计 $5$ 分，Hack 数据计 $0$ 分，但只有通过所有数据才会被判为 Accepted。

为区分原有测试点和 Hack 数据，本题添加了子任务，但子任务的计分方式为“加和”，不会影响正常评测。


title: Bina.

description:
小 J 家门前有两棵树，一棵是二叉树，一棵是三叉树。

你被小 J 叫来修剪他的二叉树，使得他的二叉树的“美丽值”最大，所谓一棵树的美丽值 $=$ 这棵树的点的编号之和 $\div$ 这棵树的深度（结果向下取整）。

这棵二叉树有一个构建参数 $n$，构建方式如下：

```cpp
void build(int s,int t,int p){
  if(s==t) return ;
  build(s,(s+t)/2,2*p);
  build((s+t)/2+1,t,2*p+1);
  add_edge(p,2*p),add_edge(p,2*p+1);
}

int main(){
  build(1,n,1);
  return 0;
}
```

其中 `build(s,t,p)` 函数参数中的 $p$ 是当前点的编号，`add_edge(x,y)` 函数是指将编号为 $x$ 的点向编号为 $y$ 的点连接一条有向边。

容易发现这棵树的根节点是 $1$，并且我们规定节点的深度为节点到根节点路径上经过的点的个数（包括自己和根节点），这棵树的深度即为所有节点深度的最大值。

对于 $n=3$ 的情况，最后构建出来的结果如下，这棵树的深度为 $3$，你需要选择一个深度 $k$ 把深度大于 $k$ 的点都剪掉，但是 $k$ 必须**大于等于** $1$ 且**小于等于**这棵树的深度。

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

小 J 还给了你一个要求，你剪去的节点个数一定得大于等于 $m$ 他才会高兴，你需要保证让他高兴的同时树的“美丽值”最大。

现在小 J 给了你构建树的参数 $n$ 和至少剪的节点个数 $m$，要你求出来他的树在你修剪后最大的美丽值是多少，如果无论如何你也不可能让小 J 高兴，输出 $-1$。

inputFormat:
本题有多组数据。

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

对于每组数据：

输入共一行两个整数 $n,m$，表示构建二叉树的参数和你至少剪掉的节点个数。

outputFormat: 对于每组数据：输出一行一个整数，表示能够获得的最大的“美丽值”，如果无法让小 J 高兴，输出 $-1$。


title: [语言月赛 202309] 椰奶国

background: 扶苏的梦想是在椰奶国生活。这个国度的成员都是可爱的椰奶，椰奶们无需在意外面的世界，快乐地生活在椰奶国里。

description:
椰奶国的一天共有 $n$ 个小时。第 $i$ 个小时（$0 \leq i < n$）共有 $i + 1$ 分钟，第 $i$ 个小时的第 $j$ 分钟（$0 \leq j \leq i$）共有 $10j+1$ 秒。

注意，这里小时、分钟、秒数都是从 $0$ 起计数。

现在，给出起始时刻 $t_1 = A:B:C$，表示 $t_1$ 时刻是 $A$ 时 $B$ 分 $C$ 秒，和结束时刻 $t_2 = E:F:G$，表示 $t_2$ 时刻是 $E$ 时 $F$ 分 $G$ 秒。

已知时刻 $t_2$ 的时刻不早于 $t_1$ 的时刻，且二者时间间隔小于一天。

请你求出 $t_1$ 和 $t_2$ 之间经过了多少秒。

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

接下来 $T$ 行，每行七个整数，依次表示一组数据的 $n,A,B,C,E,F,G$。

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

hint:
### 样例 2 解释

椰奶国一天有 $2$ 小时，即第 $0$ 小时和第 $1$ 小时，第 $1$ 小时有 $2$ 分钟，即第 $0$ 分钟和第 $1$ 分钟。第 $1$ 分钟有 $10 \times 1 + 1 = 11$ 秒。在第 $1$ 小时第 $1$ 分钟第 $3$ 秒起，接下来经过的时刻是第 $4,5,6,7,8,9,10,0$ 秒（其中最后一秒是下一天的第一秒），共八秒。

### 数据规模与约定

- 对 $30\%$ 的数据，$t_2$ 代表的时刻在一天中不早于 $t_1$ 时刻。
- 对 $60\%$ 的数据，$n \leq 50$，**保证单个测试点内的答案之和不超过 $10^8$**。
- 对 $100\%$ 的数据，$1 \leq T \leq 5 \times 10^3$，$1 \leq n \leq 10^5$，$0 \leq B \leq A < n$，$C \leq 10B$。$0 \leq F\leq E < n$，$G \leq 10E$，**保证单个测试点内的 $n$ 之和不超过 $1.5 \times 10^8$**。


title: [语言月赛 202309] 扶苏迭代

background:
给定一个函数 $f(x)$，我们关注如何求出一个点 $x_0$ 使得当把 $x_0$ 带入函数式时，得到的函数值 $f(x_0)$ 为 $0$。即求出方程 $f(x) = 0$ 的一个根 $x_0$。

牛顿迭代法就是这样一个方法。

但是我不打算向您介绍牛顿迭代的具体方法，因为这和本题没什么关系。

description:
给定初始变量 $x_0$，请你按如下表达式迭代计算 $x_i$：

$$x_i = \left\lfloor\frac{x_{i - 1} + a}{a}\right\rfloor$$

其中 $i > 0$。

我们称这个迭代过程为扶苏迭代。可以证明，在经过若干次扶苏迭代以后，$x_i$ 的取值会稳定成为一个常数 $x_N$。也就是存在一个 $j \geq 0$，使得对于所有 $k,h \geq j$，$x_k = x_h$。

你的任务是输出 $x_i$ 稳定到这个常数前的扶苏迭代过程。即输出 $x_0, x_1, x_2, \dots x_j$。这里 $j$ 是最小的满足 $x_j = x_N$ 的数。

可以证明，在给定的数据范围下，迭代次数不会很多。

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

对每组数据，只有一行两个整数，表示 $x_0$ 和 $a$。

outputFormat: 对每组数据，输出一行若干个用空格隔开的整数，表示扶苏迭代过程变量 $x_i$ 的取值。


title: [SNCPC2019] Turn It Off

description:
It's already 21:30 now, and it's time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off.

There are $n$ lights, numbered from 1 to $n$, arranged in a row in BaoBao's bedroom. Each time BaoBao can select an integer $i$ and turn all the lights numbered from $i$ to $(i+L-1)$ (both inclusive) off, where $L$ is a predefined positive integer. Note that each time the value of $L$ must be the same.

Given the initial status of all the lights, please help BaoBao determine the smallest possible $L$ so that he can turn all the lights off within $k$ times.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \times 10^5$).

The second line contains a string $s$ ($|s| = n$, $s \in \{\text{`0'}, \text{`1'}\}$) indicating the initial status of the lights. Let $s_i$ be the $i$-th character in $s$, if $s_i = \text{`1'}$ then the $i$-th light is initially on, otherwise it's initially off. It's guaranteed that there is at least one `1· in $s$.

It's guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^6$.

outputFormat: For each test case output one line containing one integer, indicating the smallest possible $L$.

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

现在已经是 21:30 了，宝宝该上床睡觉了。为了确保他的睡眠质量，宝宝决定关掉卧室里的所有灯。

宝宝的卧室里有 $n$ 盏灯，从1到 $n$ 排成一排。每次宝宝可以选择一个整数 $i$，并将从第 $i$ 盏灯到第 $(i+L-1)$ 盏灯（包括两端）之间的所有灯关掉，其中 $L$ 是一个预定义的正整数。注意，每次操作的 $L$ 值必须相同。

给定所有灯的初始状态，请帮助宝宝确定可能的最小 $L$ 使得他能在 $k$ 次操作内关掉所有的灯。

**【输入格式】**

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \times 10^5$）。

第二行包含一个字符串 $s$（$|s| = n$, $s \in \{\text{`0'}, \text{`1'}\}$）表示灯的初始状态。设 $s_i$ 为字符串 $s$ 的第 $i$ 个字符，如果 $s_i = \text{`1'}$，则第 $i$ 盏灯初始是亮的，否则是灭的。保证 $s$ 中至少有一个 `1`。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^6$。

**【输出格式】**

对于每个测试用例输出一行，包含一个整数，表示可能的最小 $L$。

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


title: [SNCPC2019] K-hour Clock

description:
A $k$-hour clock is a day keeping method which follows the rules below:

- A day is divided into $k$ hours, where the $i$-th hour is called the $(i-1)$ o' clock;
- If it's $x$ o'clock now, it will be $(x+1)$ o'clock after $1$ hour if $0 \le x < k - 1$;
- If it's $(k - 1)$ o'clock now, it will be $0$ o'clock after $1$ hour.

We know that it's $x$ o'clock now, and after $y$ hours it will be $z$ o'clock. What's the value of $k$?

inputFormat:
There are multiple test cases. The first line of the input is an integer $T$ (about $10^5$), indicating the number of test cases. For each test case:

The first and only line contains three integers $x$, $y$ and $z$ ($0 \le x, z \le 10^9$, $1 \le y \le 10^9$).

outputFormat: For each test case output one line containing one integer, indicating the value of $k$. Note that there must be $1 \le k \le 2 \times 10^9$. If there are multiple valid answers, you can print any of them; If there is no valid answer, print ``-1`` (without quotes) instead.

translation: 给定三个数 $x,y,z$，求一个满足 $k>x,k>z$ 的数 $k$，使得 $x+y\equiv z\pmod k$。


title: [SNCPC2019] Paper-cutting

description:
Paper-cutting is one of the oldest and most popular folk arts in China. It can be geographically divided into a southern and a northern style. The southern style, represented by works from Yangzhou in Jiangsu Province and Yueqing in Zhejiang Province, features ingenious and beautiful designs, exquisite carving and interesting shapes. The northern style, mainly from Yuxian and Fengning in Hebei Province and best represented by works from northern Shaanxi, features exaggerated shapes, vigorousness, vivid depictions, and diverse patterns.

There are basic cut-outs, consisting of a single image, and symmetrical designs, that are usually created by some folding over a proportioned crease, and then cutting a shape, so that when unfolded, it forms a symmetrical design. Chinese paper cuttings are usually symmetrical. The paper cutouts are usually in an even number series of $2$, $4$, $24$, etc.

You are given a piece of paper in the shape of a matrix of size $n \times m$. It is partitioned into $n \times m$ blocks of size $1 \times 1$. The piece of paper can be folded in the following way:

- You choose a vertical line between two of its columns or a horizontal line between two of its rows. This line splits the paper into two sides.
- You use the line as the folding axis and fold the smaller side of the paper onto the larger one going over the axis. If both sides of the paper are of equal size, you may fold from either side.

You would like to make a paper-cutting masterpiece from this paper. At first, you fold the paper using the method above several times (including zero times). Then you use scissors to cut the paper. Each time you cut, you can cut out a connected component from the folded paper (even if the component is not reachable from outside) and throw it away. Note that two $1 \times 1$ blocks are connected if they share an edge.

Given the final look of the paper, which is a matrix of size $n \times m$ containing $0$s and $1$s, you would like to know the minimum number of cuts needed when using the scissors.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \times m \le 10^6$): the size of the paper.

Each of the next $n$ lines contains a binary string of length $m$, where $\texttt{0}$ means the $1 \times 1$ block is cut out and $\texttt{1}$ means the $1 \times 1$ block remains on the final paper-cutting.

It is guaranteed that the sum of $n \times m$ over all test cases does not exceed $10^6$.

outputFormat: For each test case output one line containing one integer, indicating the minimum number of cuts needed.

translation:
剪纸是中国最古老、最受欢迎的民间艺术之一。它在地理上可以分为南方风格和北方风格。以江苏扬州、浙江乐清作品为代表的南方风格，设计巧妙美观，雕刻精美，造型有趣。北方风格以河北蔚县、丰宁为主体，以陕北作品为代表，造型夸张、气势恢宏、刻画生动、图案多样。

基本的裁剪由单个图像组成，还有对称的设计，通常是通过在成比例的折痕上折叠，然后裁成一个形状，当展开时，就形成了对称的设计。中国剪纸通常是对称的。剪纸通常是 $2$、 $4$ 、 $24$ 等偶数系列。

你会得到一张大小为 $n \times m$ 的纸， 它被划分为 $n \times m$ 个大小为 $1 \times 1$ 的块在。这张纸可以按以下方式折叠：

- 可以在两列之间选择一条垂直线，也可以在两行之间选择一条水平线。这条线把纸分成两面。

- 你用这条线作为对称轴，把小的一面折到大的一面上。如果纸的两面大小相等，从两边对折。

你想用这张纸做一幅剪纸杰作。首先，使用上述方法将纸张折叠几次（包括零次）。然后你用剪刀剪纸。每次剪切时，都可以从折叠的纸上剪切出一个连接的部分（即使从外面无法接触到该部分并将其扔掉。请注意，如果两个 $ 1\times 1$ 的块共享一条边，则它们是连接的。

纸张的最终外观是一个包含 $0$ 和 $1$ 的大小为 $n \times m$ 的矩阵，你想知道需要使用剪刀时的最小裁剪次数。

## 输入格式

有多个测试数据。输入的第一行包含一个整数 $T$ ，表示测试数据的数量。对于每个测试数据：

第一行包含两个整数 $n$ 和 $m$ ( $1 \le n \times m \le 10^6$ )表示纸张的大小。

接下来的 $n$ 行中的每一行都包含一个长度为 $m$ 的01字符串，其中 $\texttt{0}$ 表示 $1\times 1$ 块被剪切掉， $\texttt{1}$ 意味着 $1 \times 1$ 块保留在最后的剪纸上。

保证所有测试数据的 $n \times m$ 之和不超过 $10^6$ 。

## 输出格式

对于每个测试数据输出一行，其中包含一个整数，表示所需的最小裁剪次数。

## 样例 #1

### 样例输入 #1

```
3
2 5
11001
11001
5 7
1001100
0110011
0101101
0010010
1000000
3 2
11
11
11
```

### 样例输出 #1

```
1
4
0
```

## 提示

对于样例一,你可以通过这种方式将唯一的 $0$ 剪出:
$$\begin{array}{ccc|cc} 1&1&0&0&1\\1&1&0&0&1\end{array} \to \begin{array}{ccc} 1&1&0\\ \hline 1&1&0\end{array} \to \begin{array}{ccc} 1&1&0\end{array}$$

对于样例二，你可以按照以下方式折叠并裁剪出 $0$ 的 $4$ 个连通块：
$$\begin{array}{cccc|ccc} 1&0&0&1&1&0&0\\0&1&1&0&0&1&1\\0&1&0&1&1&0&1\\0&0&1&0&0&1&0\\1&0&0&0&0&0&0\end{array} \to \begin{array}{cccc} 1&0&0&1\\0&1&1&0\\0&1&0&1\\0&0&1&0\\1&0&0&0\end{array}$$

hint:
For the first sample test case, you can fold in the following way and cut the only $0$ out:
$$\begin{array}{ccc|cc} 1&1&0&0&1\\1&1&0&0&1\end{array} \to \begin{array}{ccc} 1&1&0\\ \hline 1&1&0\end{array} \to \begin{array}{ccc} 1&1&0\end{array}$$

For the second sample test case, you can fold in the following way and cut the $4$ connected components of $0$s out:
$$\begin{array}{cccc|ccc} 1&0&0&1&1&0&0\\0&1&1&0&0&1&1\\0&1&0&1&1&0&1\\0&0&1&0&0&1&0\\1&0&0&0&0&0&0\end{array} \to \begin{array}{cccc} 1&0&0&1\\0&1&1&0\\0&1&0&1\\0&0&1&0\\1&0&0&0\end{array}$$


title: [语言月赛 202309] 打水赛打的

description:
在 H 学校，C 考试一直被用来衡量学生编程、数据结构和算法能力的重要标准。C 考试满分 $500$ 分，一名学生只有取得不低于 $200$ 分的成绩才能毕业，我们称这样的学生为**达到毕业要求的学生**，C 考试未取得不低于 $200$ 分成绩的学生为**达不到毕业要求的学生**。

然而，随着内卷的激烈化，R 比赛走进了同学们的视野。由于该比赛组织混乱、试题难度低、获奖比例高，被同学们戏称为一等奖点击就送，成为公认的水赛。

在 2023 年的一等奖获奖名单中，同学们惊讶的发现，大量**达不到毕业要求的学生**竟然可以在 R 比赛中获得一等奖，这无疑是非常讽刺的一件事。

现在，给出 依次编号为 $1\sim N$ 的 H 学校的 $N$ 名同学的 C 考试成绩，和 R 比赛一等奖获奖名单。获奖名单中可能有超过 $N$ 的编号，这是由于其他一些学校也参加了 R 比赛，只有 $1 \sim N$ 编号的学生属于 H 学校。

请你统计，有多少 H 学校的一等奖获得者，是**达不到毕业要求的学生**。

inputFormat:
输入共三行。

输入的第一行为两个正整数整数 $N,M$，依次代表 H 学校的学生数目和 R 比赛一等奖获奖名单的人数。

输入的第二行为 $N$ 个非负整数，第 $i$ 个数 $S_i$ 代表编号为 $i$ 的学生 C 考试成绩。

输入的第三行为 $M$ 个正整数，第 $i$ 个数 $W_i$ 代表一名获奖者。

**当且仅当 $1\le W_i\le N$ 时，获奖者 $W_i$ 属于 H 学校。**

outputFormat: 输出一行一个整数，表示 H 学校的一等奖获得者中，有多少是**未达到毕业要求的学生**。

hint:
 - 对于 $30\%$ 的测试数据，$1 \le N,M \le 5000$；
 - 对于另外 $30\%$ 的测试数据，$M \le N$；
 - 对于 $100\%$ 的测试数据，$1 \le N,M \le 10^5$，$1 \le W_i \le 2\times 10^5$，$0 \le S_i \le 500$。保证 $W_i$ 不重复。


title: [语言月赛 202309] 真的没有 idea 啦

description:
给定一个字符串 $s$ 和一个字符串 $t$，请你求出：$s$ 有多少对前缀后缀对 $(x, y)$，使得 $yx$ 等于 $t$。

形式化的，设 $n$ 是字符串 $s$ 的长度，你要求出有多少对 $(i, j)$ 满足 $1 \leq i, j \leq n$ 使得 $s_{j}s_{j+1}\dots s_ns_1s_2\dots s_i = t$。

其中 $s_i$ 表示 $s$ 的第 $i$ 个字符，字符串下标从 $1$ 开始。

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

对每组数据，按如下格式输入：
第一行是一个字符串，表示 $s$。
第二行是一个字符串，表示 $t$。

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


title: 农场

background:
加入 mc2b2t.com 谢谢喵。

upd：

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

description:
ZHY 想管理他的农场。

具体地，他有 $n$ 片农场，每一片农场都是一个矩形，其四条边都平行于坐标轴。这些农场可以有重叠的部分。

他现在想圈一块地来维护自己的农场。他希望这块地可以完全覆盖所有农场。为了方便，他还希望这块地也是一个四条边都平行于坐标轴的矩形。他想最小化矩形的面积。

由于他的农场实在是太多了，所以他向你寻求帮助。你需要输出这个矩形的面积。

outputFormat: 输出一个整数表示圈地的最小面积。

hint:
样例解释：如下图所示，绿色为第一个农场，红色为第二个农场，不难发现最小的圈地面积为 $3\times 4=12$。

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

----

对于 $40\%$ 的数据，$n,|x|,|y| \le 200$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^{5}$，$0 \le |x|,|y| \le 10^{9}$，$x_{1}\neq x_{2}$，$y_{1}\neq y_{2}$。


title: [SNCPC2019] To the Park

description:
BaoBao and his $(n-1)$ classmates are going to the park. For convenience, their teacher DreamGrid has numbered the students from 1 to $n$ and decides to form the students into some groups, where each group consists of exactly two students.

For some reason, DreamGrid requires that the indices of the two students in the same group should have a common divisor greater than 1. Note that each student can only belong to at most one group, and it's not necessary that every student belongs to a group.

Please help DreamGrid form as many groups as possible.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of students.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

outputFormat:
For each test case output one line. The line first contains an integer $k$ indicating the number of groups, then $2k$ integers $a_1, a_2, \dots, a_{2k}$ follow, indicating that student $a_1$ and $a_2$ belong to the same group, student $a_3$ and $a_4$ belong to the same group, ..., student $a_{2k-1}$ and $a_{2k}$ belong to the same group. The integers in a line are separated by a space. If there are multiple valid answers, you can print any of them.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

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

宝宝和他的 $(n-1)$ 个同学要去公园。为了方便，他们的老师梦想格子将学生从 1 到 $n$ 编号，并决定将学生分成一些小组，每组恰好由两个学生组成。

由于某种原因，梦想格子要求同组的两个学生的编号必须有一个大于 1 的公约数。注意，每个学生最多只能属于一个小组，并且不需要每个学生都属于一个小组。

请帮助梦想格子组成尽可能多的小组。

**【输入格式】**

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行且唯一一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示学生的数量。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

**【输出格式】**

对于每个测试用例，输出一行。该行首先包含一个整数 $k$，表示小组的数量，然后是 $2k$ 个整数 $a_1, a_2, \dots, a_{2k}$，表示学生 $a_1$ 和 $a_2$ 属于同一小组，学生 $a_3$ 和 $a_4$ 属于同一小组，以此类推。行内的整数由空格分隔。如果有多个有效答案，可以输出其中任何一个。

请不要在每行的末尾输出多余的空格，否则你的解决方案可能会被认为不正确！

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


title: [SNCPC2019] Unrooted Trie

description:
Recall the definition of a trie:

- A trie of size $n$ is a rooted tree with $n$ vertices and $(n-1)$ edges, where each edge is marked with a character;
- Each vertex in a trie represents a string. Let $s(x)$ be the string vertex $x$ represents;
- The root of the trie represents an empty string. Let vertex $u$ be the parent of vertex $v$, and let $c$ be the character marked on the edge connecting vertex $u$ and $v$, we have $s(v)$ = $s(u) + c$. Here $+$ indicates string concatenation, not the normal addition operation.

We say a trie is valid, if the string each vertex represents is distinct.

Given an unrooted tree with $n$ vertices and $(n-1)$ edges, where each edge is marked with a character, how many different vertices can be selected as the root of the tree so that the tree becomes a valid trie?

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the size of the tree.

For the following $(n-1)$ lines, the $i$-th line contains two integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) and a character $c_i$ separated by a space, indicating that there is an edge marked with a character $c_i$ connecting vertex $u_i$ and $v_i$. It's guaranteed that $c_i$ will only be lower-case English letters.

It's guaranteed that the given graph is a tree, and the sum of $n$ of all test cases will not exceed $10^6$.

outputFormat: For each test case output one line containing one integer, indicating the number of different vertices that can be selected as the root of the tree to make it a valid trie.

translation:
### 题目背景

trie 的定义是这样的：

- 一棵大小为 $n$ 的 trie，是一棵有着 $n$ 个节点和 $(n-1)$ 条边的有根树，每一条边上都标有一个字符；

- 在 trie 中，从根结点到树上某一结点的路径代表一个字符串，节点 $x$ 代表的字符串记为 $s(x)$，特别地，根节点代表的字符串为空串。

- 若节点 $u$ 是节点 $v$ 的父节点，且 $c$ 是连接 $u$ 与 $v$ 的边上的字符，则有 $s(v) = s(u) + c$（这里的 $+$ 表示字符串的连接，而非普通的加法运算）。

当每一个节点代表的字符串互不相同时，该 trie 是合法的。

### 题目描述

给出一个无根的 trie，求其中有多少节点可作为该 trie 的根，使得该 trie 合法。

### 输入格式

**每个测试点由多组数据组成。**

输入的第一行包含一个正整数 $T$，代表测试数据的组数。

对于每组测试数据：

数据的第一行包含一个正整数 $n$，代表 trie 的大小。

接下来的 $(n-1)$ 行中，第 $i$ 行包含两个正整数 $u_i,v_i$ 以及一个字符 $c_i$，用空格隔开，表示有一条标有 $c_i$ 的边连接着 $u_i$ 和 $v_i$。

### 输出格式

对于每组测试数据，输出一行一个正整数，表示可以成为根后可以使该 trie 合法的节点的个数。

### 说明/提示

【样例解释】

对于第一组测试数据，只能选择节点 $1$ 或节点 $2$ 作为根，否则 $s(1)$ 和 $s(2)$ 相同。

对于第二组测试数据，无论如何选择节点作为根，$s(1)$ 和 $s(2)$ 或 $s(5)$ 和 $s(6)$ 相同。

【数据范围】

对于每组数据，$1 \le n \le 2 \times 10^5$，$1 \le u_i,v_i \le n$，$c_i$ 都是小写字母。

对于每个测试点，保证给出的图是一棵树，所有的 $n$ 之和不会超过 $10^6$。

hint:
For the first sample test case, we can only select vertex 1 or vertex 2 as the root, otherwise $s(1)$ and $s(2)$ will be the same.

For the second sample test case, no matter which vertex we select as the root, $s(1)$ and $s(2)$, or $s(5)$ and $s(6)$ will be the same.


title: [SNCPC2019] Coolbits

description: Given $n$ intervals $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$, one must select an integer from each of the intervals and calculate their bitwise and value $b$. What's the maximum possible $b$ one can get?

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of intervals.

For the following $n$ lines, the $i$-th line contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^9$), indicating the $i$-th interval.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

outputFormat: For each test case output one line containing one integer, indicating the maximum possible $b$ one can get.

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

给定 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$，需要从每个区间中选择一个整数并计算它们的按位与值 $b$。能够得到的最大 $b$ 是多少？

**【输入格式】**

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示区间的数量。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($0 \le l_i \le r_i \le 10^9$)，表示第 $i$ 个区间。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

**【输出格式】**

对于每个测试用例输出一行，包含一个整数，表示能得到的最大可能 $b$。

**【样例解释】**

对于第一个样例测试用例，可以从三个区间中选择 7、6 和 7，并得到它们的按位与值 6。

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

hint: For the first sample test case, one can select 7, 6 and  7 from the three intervals and get their bitwise and value 6.


title: [SNCPC2019] Escape Plan

description:
BaoBao, one of the most famous monster hunters, wakes up in the middle of Heltion City dominated by monsters. Having troubles remembering what has happened, BaoBao decides to escape from this horrible city as soon as possible. Despite arming no weapon, he luckily puts his hand on a map in his right pocket, which contains valuable information that can possibly help him find a way out.

According to the map, Heltion City is composed of $n$ spots connected by $m$ undirected paths. Starting from spot $1$, BaoBao must head towards any of the $k$ exits of the city to escape, where the $i$-th of them is located at spot $e_i$.

However, it's not an easy task for BaoBao to escape since monsters are everywhere in the city! For all $1 \le i \le n$, $d_i$ monsters are wandering near the $i$-th spot, so right after BaoBao arrives at that spot, at most $d_i$ paths connecting the spot will be blocked by monsters and are unable for BaoBao to pass. When BaoBao leaves the $i$-th spot, the monsters will go back to their nests and the blocked paths are clear. Of course, if BaoBao comes back to the spot, at most $d_i$ paths will be again blocked by the monsters. The paths blocked each time may differ.

As BaoBao doesn't know which paths will be blocked, please help him calculate the shortest time he can escape from the city in the worst case.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ (about $100$), indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$ and $k$ ($1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le k \le n$), indicating the number of spots, the number of undirected paths and the number of exits of the city.

The second line contains $k$ distinct integers $e_1, e_2, \dots, e_k$ ($1 \le e_i \le n$), indicating $k$ exits of Heltion City.

The third line contains $n$ integers $d_1, d_2, \dots, d_n$ ($0 \le d_i \le m$), where $d_i$ indicates the number of monsters at the $i$-th spot.

For the following $m$ lines, the $i$-th line contains three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i,y_i \le n$, $x_i \neq y_i$, $1 \le w_i \le 10^4$), indicating an undirected edge of length $w_i$ connecting spot $x_i$ and $y_i$.

It's guaranteed that the total sum of $n$ will not exceed $10^6$ and the total sum of $m$ will not exceed $3 \times 10^6$.

outputFormat: For each case output one line containing one integer. If BaoBao can get to some exit in the worst case, output the shortest possible time cost; Otherwise if BaoBao cannot get to any exit in the worst case, output ``-1``  instead.

translation:
### 题目描述

宝宝被困在了 Heltion 城中。

城市可以看做由 $n$ 个点与 $m$ 条边组成的**有权无向图**，最开始宝宝在 $1$ 号节点。城市中存在 $k$ 个出口，第 $i$ 个出口位置在 $e_i$ 号点 ，而宝宝需要以最快的速度到达**这些出口中的任意一个**以逃离 Heltion 城。

不巧的是，城市中有怪物游荡，对于点 $i$，有 $d_i$ 只怪物驻守在此。当宝宝到达点 $i$ 时，怪物会**随机封锁至多** $d_i$ **条**与之相邻的道路，宝宝不能通过这些被封锁的道路。而当宝宝**离开后**，点 $i$ 的怪物会回窝，这时被封锁的**道路会解开**。

请帮帮宝宝，求出最坏情况下，他逃出 Heltion 城需要多久。

### 输入格式

第一行为一个正整数 $T$，表示有 $T$ 组测试数据。

对于每组数据，第一行包括三个正整数 $n$，$m$，$k$，分别表示城市的点数，边数和城市中出口的数量。

第二行有 $k$ 个正整数 $e_1, e_2,\dots , e_k$，表示第 $i$ 个出口在 $e_i$ 号节点。

第三行有 $n$ 个正整数 $d_1, d_2,\dots , d_n$，表示第 $i$ 个节点上有 $d_i$ 只怪物。

接下来的 $m$ 行，一行三个正整数 $x_i$，$y_i$，$w_i$，表示第 $i$ 条双向边所连接的两点与边权。

### 输出格式

共 $T$ 行，每行一个整数。第 $i$ 行的整数表示第 $i$ 组数据的答案。

对于每组数据，若宝宝不能到达任何一个出口，请输出 `-1`。否则，输出宝宝到达任意一个出口所需要的最少时间。

### 数据范围

对于 $100\%$ 的数据，$1\le n \le 10^5$，$\sum n \le 10^6$，$1\le m \le 10^6$，$\sum m \le 3\times 10^6$，$1\le k \le n$，$1\le e_i \le n$，$0\le d_i \le m$，$1\le x_i,y_i \le n$，$1\le w_i \le 10^4$。数据保证 $x_i \neq y_i$。


title: [SNCPC2019] Digit Product

description:
Define the ''digit product'' $f(x)$ of a positive integer $x$ as the product of all its digits. For example, $f(1234) = 1 \times 2 \times 3 \times 4 = 24$, and $f(100) = 1 \times 0 \times 0 = 0$.

Given two integers $l$ and $r$, please calculate the following value:
$$(\prod_{i=l}^r f(i)) \mod (10^9+7)$$
In case that you don't know what $\prod$ represents, the above expression is the same as
$$(f(l) \times f(l+1) \times \dots \times f(r)) \mod (10^9+7)$$

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ (about $10^5$), indicating the number of test cases. For each test case:

The first and only line contains two integers $l$ and $r$ ($1 \le l \le r \le 10^9$), indicating the given two integers. The integers are given without leading zeros.

outputFormat: For each test case output one line containing one integer indicating the answer.

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

定义正整数 $x$ 的 "数字乘积" $f(x)$ 为其所有数字的乘积。例如，$f(1234) = 1 \times 2 \times 3 \times 4 = 24$，$f(100) = 1 \times 0 \times 0 = 0$。

给定两个整数 $l$ 和 $r$，请计算以下值：
$$(\prod_{i=l}^r f(i)) \mod (10^9+7)$$
如果你不知道 $\prod$ 表示什么，上述表达式等同于
$$(f(l) \times f(l+1) \times \dots \times f(r)) \mod (10^9+7)$$

**【输入格式】**

有多个测试用例。输入的第一行包含一个整数 $T$（大约 $10^5$），表示测试用例的数量。对于每个测试用例：

第一行且唯一一行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le 10^9$），表示给定的两个整数。这些整数没有前导零。

**【输出格式】**

对于每个测试用例，输出一行，包含一个整数，表示答案。

**【样例解释】**

对于第一个样例测试用例，答案是 $9! \mod (10^9+7) = 362880$。

对于第二个样例测试用例，答案是 $(f(97) \times f(98) \times f(99)) \mod (10^9+7) = (9 \times 7 \times 9 \times 8 \times 9 \times 9) \mod (10^9+7) = 367416$。

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

hint:
For the first sample test case, the answer is $9! \mod (10^9+7) = 362880$.

For the second sample test case, the answer is $(f(97) \times f(98) \times f(99)) \mod (10^9+7) = (9 \times 7 \times 9 \times 8 \times 9 \times 9) \mod (10^9+7) = 367416$.


title: [CEOI2023] The Ties That Guide Us (incursion)

description:
你用销售机器人的利润雇佣了一名助手，现在你准备好去拿走装有 CEOI 奖章的保险箱了。

保险箱位于一所由 $n$ 个房间所组成的大学建筑内，这些房间由 $n-1$ 扇门连接。每个房间都可以从其他任何房间到达，且每个房间最多与 $3$ 扇门相连。
你和你的助手都有描述建筑物内房间相连情况的平面图，但是你们两个各自拥有的平面图虽然描述了相同的房间结构布局，但是房间和门的编号可能不同。

在比赛的第二天，委员会忙于处理赛时通知和选手提问。这将是接近装着奖牌的保险箱的完美机会。

你的助手会首先搜索整栋大楼。一旦他找到保险箱所在的房间，它就会给你留下前往那个房间的提示。由于手机不能带进赛场，他用了去年 BOI 留下的几乎无限供应的领带。由于这些领带完全相同无法区分，你能获得的信息就是他在任何给定房间里所留下的领带数量。由于一个房间内过多的领带非常可疑，因此任何单个房间内领带的最大数量应当尽可能少（参阅评分部分）。

之后，你计划在上厕所的时候溜出去，利用助手留下来的领带找到有保险箱的房间。保险箱藏在房间里，所以你进入带有保险箱的房间时，必须依靠领带识别这个房间；此外，由于“上厕所”时间过长会被发现，你必须尽快找到保险箱。你最多可以走过 $d+30$ 扇门，其中 $d$ 是你的初始位置到保险箱所在位置的最短路径上的门数量。若重复穿过同一扇门，则每次都计入。

因此，你需要编写一个程序，告诉助手需要在每个房间留下多少条领带，并引导你前往带有保险箱的房间。

inputFormat:
本题为函数交互题。

对于每个测试点，你的程序会运行两次。

你需要实现如下两个函数（函数原型已给出）：
```
vector<int> mark(vector<pair<int,int>> F, int safe);
```
- $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \le u,v \le n$ 并且保证 $u \neq v$，代表在助手的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。
- $\mathrm{safe}$: 表示你的助手的地图上保险箱所在的房间编号。

该函数应当返回一个长度为 $n$ 的 `vector<int>` $v$，其中每个元素 $v_i$ 代表你的助手应当在他地图上 $i+1$ 号房间留下的领带数量。你应当保证 $0 \le v_i \le 10^9$。

```
void locate(vector<pair<int,int>> F,int curr,int t);
```
- $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \le u,v \le n$ 并且保证 $u \neq v$，代表在你的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。
- $\mathrm{curr}$: 你目前所在的房间编号。
- $t$: 在你当前所处的房间中，找到的领带数量。

在如下的叙述中，房间编号采用你地图的编号方案。

在实现函数 `locate` 的过程中，你可以调用如下函数：
```
int visit(int v);
```
以此来从你目前所在的房间 $u$ 移动到一个相邻的房间 $v$。你需要保证操作合法，即 $1 \le v \le n,(u,v) \in F\:\vee (v,u) \in F$。

该函数返回一个非负整数 $k$，表示你在房间 $v$ 中找到的领带个数。

该函数调用的次数不应超过 $d+30$，其中 $d$ 是你的起点到终点的最短距离。

当函数 `locate` 终止时，你应当处于带有保险箱的房间内。

对于每个测试点，第一次运行程序时调用 `mark`，第二次调用 `locate`。

如果 `visit` 调用次数过多、调用不合法或在 `mark` 中被调用，你的程序将会被终止运行，提交将会被判**错误**。
你的程序不得写入或读取 `stdin` 或 `stdout`，否则将会被判**违反安全规定**。
但是你可以随便往 `stderr` 输出，没人管这个。

你需要在源代码文件开头加上 `#include "incursion.h"`。

你应当将程序与 `sample_grader.cpp` 链接以进行本地测试。

下面是示例评分器的说明，请参阅 `sample_grader.cpp` 以获取操作说明。

为简单起见，本评分器不会运行你的程序两次，而是在一次运行中调用两个函数各一次。附件中包含了一个 `sample_grader.cpp` 的示例实现。

注意：该实现不与评测所用的实现相同，禁止采用 Hack 评分器的方式试图通过本题！

hint:
### 评分细则

共有 4 个 subtask。对于每个测试点，$2 \le n \le 45000$。

Subtask 1 (30 points)，保证没有一个房间有三扇门相连。
Subtask 2 (30 points). 有且仅有一个房间有两扇门相连。
Subtask 3 (40 points). 没有特殊性质。

对于每个测试点，假设使用领带最多的房间用了 $T_{\max}$ 条领带，
- $T_{\max}<2$，你将会获得该测试点 $100\%$ 的分数。
- $T_{\max}=2$，你将会获得该测试点 $40\%$ 的分数。
- $2 < T_{\max} \le 10^9$，你将会获得该测试点 $30\%$ 的分数。

### 交互库使用方法
**注意洛谷提供的交互库与原版不同。**

请使用 `g++ -std=c++17 -Wall -O2 -o test interactive_lib.cpp xxx.cpp` 编译，其中 `xxx.cpp` 是你的程序名字。

示例交互库首先从标准输入读入三个正整数, $n$, $s$, $seed$，表示点数、起点的原编号、随机数种子。

然后读入 $n-1$ 行，每行两个正整数 $u,v$，表示原树的一条边。其中需保证 $1 \le u < v \le n$。
然后读入一行一个字符串，表示打乱规则。

**你不需要在意打乱序号的具体实现。该实现与最终评测所用交互库不一定相同。**

接下来交互库将会调用一次 `mark`，一次 `locate`。注意交互库可能会打乱序号。

交互库可能向终端输出以下信息：

- `Invalid input.` 输入不合法。
- `Invalid call to visit. (ALICE CALLED VISIT)` 在 `mark` 中调用 `visit`。
- `Invalid call to visit. (INDEX ERROR)` 访问了不合法的点。
- `Invalid call to visit. (NOT CONNECTED)` 访问的点和当前所在的点没有直接的边相连。
- `Invalid call to visit. (TOO MANY VISITS)` 调用 `visit` 次数过多。
- `Invalid return value of mark.` `mark` 的返回值不合法。即返回的 `vector` 长度不为 $n$ 或者有小于 $0$ 或大于 $10^9$ 的数。
- `Not correct: current position is X` 最终并不在目标点，你应该在 $X$ 点（在第二张地图上）。
- `Correct: at most X tie(s) per room.` 到达目标点，且用领带最多的房间使用了 X 条领带。

最终评测时，只会返回正确与否的信息。


title: [CEOI2023] Trade

background: 译自 CEOI2023 Day2 T1 [Trade](https://www.ceoi2023.de/wp-content/uploads/2023/09/4-trade.pdf)。

description:
有 $n$ 个机器人排成一排，第 $i$ 个机器人的购买价是 $c_i$ 欧元，卖出价是 $s_i$ 欧元。

给定 $1\le k\le n$，你需要购买一段长度至少为 $k$ 的区间中所有的机器人，然后选择其中的恰好 $k$ 个机器人来卖出。

你需要求出：
1. 你能够得到的最大收益；
2. 在收益最大化的前提下，哪些机器人可以在某种最优方案中被卖出。

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

第二行 $n$ 个正整数 $c_1,\dots,c_n$。

第三行 $n$ 个正整数 $s_1,\dots,c_n$。

outputFormat:
第一行输出一个整数表示最大收益。

第二行输出一个 $01$ 串，第 $i$ 位输出 $1$ 表示第 $i$ 个机器人可以在某种最优方案中被卖出，反之第 $i$ 位输出 $0$。

hint:
样例一中最优方案是购买第 $3\sim 5$ 个机器人然后将它们卖出，但仍然会亏损 $1$ 欧元。

样例二中最大收益为 $2$ 欧元，可以购买 $1,2,3$ 并卖出 $1,3$，也可以购买 $3,4$ 并卖出 $3,4$，也可以购买 $3,4,5$ 并卖出 $3,5$，因此 $1,3,4,5$ 都有可能在某种最优方案中被卖出，输出 `10111`。

### 数据规模与约定

对于全部数据，$1\le k\le n \le 250000$，$1\le c_i,s_i\le 10^9$。

- Subtask 1（5+5 points）：$n \le 200$。
- Subtask 2（5+5 points）：$n \le 6000$。
- Subtask 3（5+5 points）：$k=2$。
- Subtask 4（10+15 points）：$k\le 200$。
- Subtask 5（25+20 points）：无特殊限制。

在每个子任务中，如果第一行的输出正确，可以获得子任务前半部分的分数，如果第二行的输出也正确，可以获得子任务全部的分数。


title: [CEOI2023] Grading Server

background: 翻译自 CEOI2023 Day1 T2 [Grading Server](https://www.ceoi2023.de/wp-content/uploads/2023/09/2-grading-server.pdf)。

description:
竞赛委员会的主席注意到了一些可疑的网络活动 —— 有人想要攻击评测系统！

评测系统拥有特定的算力 $c_G$。黑客会尝试将 $c_G$ 降为 $0$（甚至更低）。系统被 $f_G$ 个防火墙保护着，每个防火墙都会将攻击的影响降低 $S$。

每个时刻，黑客可以进行以下两种操作之一：

- 击破一个防火墙，将 $f_G$ 降低 $1$（但不能低于 $0$），或者
- 用他所有的算力 $c_H$ 攻击系统，将 $c_G$ 降低 $\max(c_H - f_G\cdot S, 0)$。

但委员会主席可以反击：击破黑客的 $f_H$ 个防火墙之一；或者用系统的算力攻击黑客，类似地将 $c_H$ 降低 $\max(c_G - f_H \cdot S)$。委员会主席和黑客轮流行动，黑客先行动。

为了安排防御，委员会成员需要一个程序告诉他们，在 $Q$ 个不同的 $(c_H, f_H, c_G, f_G)$ 情况下，就算委员会主席采取了最优的行动，黑客是否依然能够击垮评测系统（将 $c_G$ 降低为 $0$ 或更低）。

inputFormat:
第一行两个整数 $S, Q$。

接下来 $Q$ 行，每行四个整数 $c_H, f_H, c_G, f_G$ 描述一个情况，分别为黑客的算力和防火墙数量，以及评测系统的算力和防火墙数量。

outputFormat: 你的程序应当输出 $Q$ 行，每行一个字符串 `YES` 或 `NO`。`YES` 表示无论委员会主席的行动如何，采取最优策略的黑客总能够让 $c_G$ 降为 $0$ 或更低；否则输出 `NO`。

hint:
#### 样例解释

考虑样例一的第一个情况：

- 首先，黑客攻击评测系统，将 $c_G$ 降低 $42 - 1\cdot 17 = 25$ 为 $8$；
- 接下来，委员会主席无法通过攻击降低 $c_H$，所以明智的选择是击破黑客的唯一的防火墙；
- 然而，黑客可以继续攻击评测系统，将 $c_G$ 降低 $25$ 为 $-17\leq 0$，击垮评测系统并毁掉第一天比赛日。

对于第二个情况：

- 一开始，黑客唯一能做的就是击破一个评测系统的防火墙；
- 接下来，委员会主席攻击黑客，将 $c_H$ 降低为 $26$；
- 接下来两轮，黑客同样只能攻击评测系统的防火墙。同时委员会主席每次攻击黑客，将 $c_H$ 降低为不大于 $0$ 的值，成功防御黑客的攻击。

#### 数据范围与约定

- Subtask 1（5 分）：$S, c_H, c_G, f_H, f_G\leq 75$；
- Subtask 2（5 分）：$S, c_H, c_G, f_H, f_G\leq 300$；
- Subtask 3（10 分）：$S = 1$；
- Subtask 4（25 分）：$S, c_H, c_G, f_H, f_G\leq 2000$；
- Subtask 5（20 分）：$S\leq 400$；
- Subtask 6（20 分）：$f_H, f_G\leq 125$；
- Subtask 7（15 分）：无特殊限制。

对于所有数据，$1\leq S\leq 3\times 10 ^ 4$，$1\leq c_H, c_G\leq 10 ^ {12}$，$0\leq f_H, f_G\leq 10 ^ {12}$，$1\leq Q\leq 2.5\times 10 ^ 5$。

#### 限制

时间：4s
空间：1GB


title: [语言月赛 202309] 悬线

background: 我们定义一个数字是质数，当且仅当它的因子仅有 $1$ 和自身。特别的，$1$ 不是质数。

description:
给定一个 $n \times m$ 的数字阵。约定第 $i$ 行第 $j$ 列上的数用 $(i,j)$ 表示。

我们称以第 $i$ 行第 $j$ 列的格子为底的**悬线**的长度是最大的 $k$，满足 $k \leq i$ 且 $(i,j), (i-1,j), (i-2,j),\dots(i-k+1,j)$ 这 $k$ 个数都是**质数**。特别的，如果 $(i, j)$ 本身不是质数，称以第 $i$ 行第 $j$ 列为底的悬线长度为 $0$。

对于每个格子，请你求出以它为底的悬线长度。

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

对每组数据，按如下格式输入：

每组数据第一行是两个整数，表示数字阵的行数 $n$ 和列数 $m$。
接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $(i,j)$。

outputFormat: 对每组数据，输出 $n$ 行，每行 $m$ 个用单个空格隔开的整数。第 $i$ 行第 $j$ 个数表示以第 $i$ 行第 $j$ 列的格子为底的悬线长度。


title: 出边排序 2

description:
给定一个 $n$ 个点 $m$ 条边的有向图 $G$，结点编号从 $1$ 至 $n$，每个结点有一个权值，结点 $i$ 的权值是 $w_i$。对于 $u = 1, 2, 3, \dots n$，依次完成如下要求：
对于 $u$ 的所有出边（即从 $u$ 出发的边），按照**权值从小到大**的顺序输出出边所指向的节点编号。如果两个点的权值相同，先输出编号较小的。

**依次完成**的含义是，先按顺序输出 $u = 1$ 的出边所指向的点的编号，再按顺序输出 $u = 2$ 的出边所指向的点的编号……最后按顺序输出 $u = n$ 的出边所指向的点的编号。

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

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

对于每组数据的格式如下：
第一行是两个整数，分别表示点的个数 $n$ 和边的个数 $m$。
第二行有 $n$ 个整数 $w_1,w_2,\cdots,w_n$，表示每个节点的权值。
接下来 $m$ 行，每行两个整数 $u, v$，表示一条由 $u$ 指向 $v$ 的边。

保证每组数据内不存在重边。

outputFormat:
对于每组数据：
输出 $n$ 行，每行若干个用空格隔开的整数。第 $i$ 行输出节点 $i$ 的出边所指向的节点编号。

**注意，如果一个结点不存在出边，你同样需要输出一个空行**。

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

对于全部的测试点，保证 $1 \leq T, n, m \leq 5 \times 10^5$，$1 \leq w_i \leq n$，但同时各测试点的 $n$ 与 $m$ 之和均不超过 $5 \times 10^5$，即 $\sum n, \sum m \leq 5 \times 10^5$。且 $1 \leq u, v \leq n$，每组数据内不存在重边。

### 提示

请注意大量读入输出对程序效率造成的影响。


title: 线性变换

description:
你有三个非负整数 $x,a,b$。在 $x \ge 0$ 的前提下，你可以对 $x$ 进行任意次（包括 $0$ 次）如下操作：

* 将 $x$ 变为 $ax - b$。

你需要求出你通过操作能得到的 $x$ 的最小值。

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

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

对于每组数据，输入一行三个整数 $x,a,b$。

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

hint:
样例解释：对于第一组数据，有 $x=6 \rightarrow 8 \rightarrow 12 \rightarrow \cdots$，很明显 $x=6$ 就是最小值。

对于第二组数据，有 $x=5\rightarrow -1$，$x=-1$ 为最小值。

----

对于 $30\%$ 的数据，$T \le 5$，$x,a,b \le 100$。

对于另 $20\%$ 的数据，$a \gt b$。

对于另 $20\%$ 的数据，$b=0$。

对于 $100\%$ 的数据，$1 \le T \le 1000$，$0 \le x,a,b \le 10^{9}$。


title: Colo.

description:
小 F 和小 Y 经常在一起玩耍，因为小 F 是一个画家，他喜欢在一个长度为 $n$，宽度为 $1$ 的网格图上画画，从左往右第 $i$ 个方格被涂成了一种颜色 $a_i$。

你觉得他的随意涂鸦太难看了，想要保留恰好 $k$ 种颜色（**你不能保留没在网格图上出现的颜色**），使得网格图上没被涂成任何一种你喜欢的颜色的网格都被剪掉，最后会剩下一些网格，你希望这些网格从左到右颜色的编号是单调不下降的。

此外，小 Y 使用的第 $i$ 种颜色有一个价值 $b_i$，小 Y 看到了你裁剪后的网格图很是高兴，于是决定付给你你选择的颜色的价值总和。

你需要求出你能够获得的最大的价值是多少。

inputFormat:
第一行两个整数 $n,k$，表示小 Y 画画的网格图的大小和你需要保留颜色的种类数。
第二行 $n$ 个整数 $a_i$，表示小 Y 画出来的网格图从左往右第 $i$ 个格子的颜色。
第三行 $n$ 个整数 $b_i$，表示第 $i$ 种颜色的价值。

outputFormat: 一行一个整数，表示你能够获得的最大价值；特别地，如果无法找到选择颜色的方法满足要求，输出 $-1$。

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

对于第一组样例，我们可以选择 $1$ 号和 $3$ 号颜色保留，剩下的网格图即为 $[1,1,3]$，满足单调不下降这一个限制，获得的价值即为 $b_1+b_3=5+1=6$，可以证明这是最优的办法。

#### 【数据范围】

对于所有测试数据，满足 $1 \le n \le 500$，$1 \le k \le 500$，$1 \le a_i \le n$，$1 \le b_i \le 10^9$。

**本题开启捆绑测试，所有数据范围均相同的测试点捆绑为一个 $\text{Subtask}$。**

各测试点的附加限制如下表所示。

| 测试点 | $n,k \le $ | 特殊性质 |
| :-----------: | :-----------: | :-----------: |
| $1 \sim 3$ | $10$ | 无 |
| $4 \sim 5$ | $100$ | 无 |
| $6 \sim 10$ | $500$ | 不同的颜色不超过 $10$ 种 |
| $11 \sim 15$ | $500$ | 每种颜色出现的次数不超过 $2$ 次 |
| $16 \sim 20$ | $500$ | 无 |


title: [CEOI2023] Balance

background: 翻译自 CEOI2023 Day1 T3 [Balance](https://www.ceoi2023.de/wp-content/uploads/2023/09/3-balance.pdf)。

description:
由于黑客对评测机的攻击，组委会决定重测所有提交记录。

有 $N$ 台评测机，$T$ 个题目（编号为 $1, 2, \cdots, T$）。组委会已经确定，每台评测机要评测哪些提交（数目相同，都是 $S$ 个提交，保证 $S$ 是 $2$ 的整数次幂）。在接下来的 $S$ 分钟内，每分钟每台评测机会评测一个提交。

每个提交都会提交至某个题目。由于存数据的机器太脆弱了，所以要求，对于所有题目和任意两个时刻，在这两个时刻，这个题的被评测的提交的数量之差不超过 $1$。

请构造一组方案，使得满足上面的条件。

inputFormat:
第一行输入 $N, S, T$。

接下来 $N$ 行，每行输入 $S$ 个整数，表示这个评测机被分配到的提交的题目编号。

outputFormat:
输出 $N$ 行，每行 $S$ 个数，表示这个评测机按顺序要评测的提交的题目编号。

可以证明，一定存在一组解。

hint:
保证存在正整数 $k$ 使得 $S = 2 ^ k$，$1 \le N, S, T \le 10 ^ 5$，$NS \le 5 \times 10 ^ 5$。

- Subtask 1（$10$ 分）：$S = 2$ 且 $N, T \le 20$。
- Subtask 2（$15 + 5 + 5$ 分）：$S = 2$。
- Subtask 3（$15 + 5 + 5$ 分）：$NS \le 10 ^ 4$。
- Subtask 4（$20 + 10 + 10$ 分）：没有其它限制。

对于后三个子任务，存在部分分（对应括号中的分数）：

- 第一个数表示如果能解决满足 $T \le N$ 且对于每个题目的提交数量均整除 $S$ 时的所有测试点能得到的分数。
- 第二个数表示如果能解决满足 $T \le N$ 时的所有测试点能多得到的分数。
- 第三个数表示如果解决了整个 Subtask 时能多得到的分数。

在洛谷上，本题分为 $10$ 个子任务。对于原来的后三个 Subtask，在本题中分别按顺序分为三个子任务（如原 Subtask 3 就是子任务 $5, 6, 7$），有依赖关系。


title: 口吃

background: 在题目描述末尾有形式化题意。

description:
因为练习说唱，ZHY 变成了一个口吃。

ZHY 的口吃十分特别，具体的，假设 ZHY 要读一段有 $n$ 个字的话，那么他会将第一个字读一遍，第二个字读两遍，第三个字读三遍……第 $n$ 个字读 $n$ 遍。例如，“原神启动”ZHY 会读成“原神神启启启动动动动”。

YHZ 手上有 $n$ 个字，每个字都有 YHZ 为其设定的悦耳值 $a_i$，且 $a_{1\sim n}$ 会形成一个 $1\sim n$ 的排列。现在，他要把这 $n$ 个字重新排列成一段话给 ZHY 读。因为 YHZ 喜欢玩原神，所以他要求重新排列后序列 $a$ 的逆序对个数恰好为 $k$。不过 YHZ 还没定好每个字的顺序，所以请你求出对于所有可能的排列，ZHY 按顺序将这段话读出后，YHZ 将听到的所有字的悦耳值之和的和。显然，如果 YHZ 听到了一个字多次，其悦耳值也应算进总和多次。

**形式化题意**

称一个 $1\sim n$ 的排列 $a_1,a_2,\cdots,a_n$ 是合法的，当且仅当其逆序对数**恰好**为 $k$。同时，对于一个排列 $a_1,a_2,\cdots,a_n$，其权值是 $\sum_{i=1}^n i\times a_i$。

给定 $n$ 和 $k$，请你求出所有 $1\sim n$ 的合法排列的权值之和，答案对 $998244353$ 取模。

一个排列的逆序对数定义为 $\sum_{i=1}^n\sum_{j=i+1}^n [a_i>a_j]$。

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

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


title: [ICPC2022 Jinan R] Tower

description:
Prof. Pang built $n$ block towers with different heights. The $i$-th tower has height $a_i$.

Prof. Shou doesn't like these towers because of their arbitrary heights. He decides to $\textbf{first remove exactly \textit{m} of them}$, and then perform some (or none) of the following operations:

- Choose a tower and increase its height $a_i$ by $1$.
- Choose a tower and decrease its height $a_i$ by $1$.
- Choose a tower and divide its height $a_i$ by $2$. If the new height is not an integer, it is rounded down.

Prof. Shou can never choose a removed tower. If after an operation, the height of a tower will become $0$, that operation is not allowed. Under these constraints, Prof. Shou can perform an arbitrary number of operations in arbitrary order.

Prof. Shou would like all the towers that are not removed to have the same heights. Please calculate the minimum number of operations to achieve this.

inputFormat:
The first line contains one integer $T~(1\le T \le 10)$, the number of test cases.

For each test case, the first line contains two integers $n, m~(1\le n\le 500, 0\le m <n)$, the number of towers, and the number of towers Prof. Shou should delete before performing the operations.

The next line contains $n$ integers $a_1,\ldots, a_n~(1\le a_i\le 10^9)$, the initial heights of the towers.

outputFormat: For each test case, output the minimum number of operations in one line.

translation:
### 题目描述
庞教授搭了 $n$ 座不同高度的塔。第 $i$ 座塔的高度是 $a _ {i}$。

寿教授不喜欢这些参差不齐的塔。他决定**先去掉它们中的 $m$ 座**，然后执行以下操作中的一些（或不执行）：
- 选择一座塔并增加它 $1$ 个单位高度。
- 选择一座塔并减少它 $1$ 个单位高度。
- 选择一座塔并把它的高度 $a _ {i}$ 除以 $2$，如果它不是整数的话，向下取整。

寿教授永远不会选择被拆除的塔。如果操作后，塔的高度变为 $0$，则不允许操作。在这些约束条件下，寿教授可以按任意顺序执行任意数量的运算。

寿教授希望所有没有被拆除的塔都有相同的高度 $a _ {i}$。请计算实现此目标的最小操作次数。
### 输入格式
第一行是一个整数 $T(1\leqslant$ $T$ $\leqslant$ $10)$,表示有 $T$ 组数据。

对于每组测试数据，第一行包括两个整数 $n,m (1\leqslant$ $n$ $\leqslant$ $500$$,$$0$ $\leqslant$ $m$ $\leqslant$ $n$$)$，表示塔的数量以及寿教授在执行操作之前应该删除的塔的数量。

下一行包括 $n$ 个整数 $a _ {1},\dots,a _ {n} (1\leqslant$ $a _ {i}$ $\leqslant$ $10^9)$，表示塔的最初高度。
### 输出格式
对于每组测试数据，在一行中输出最小操作数。


title: [ICPC2022 Jinan R] Torch

description:
Prof. Pang and Prof. Shou go to explore a cave together. Prof. Pang walks ahead of Prof. Shou.

Each of them has a torch for illumination. The torches need fuel to burn. Prof. Pang's torch can burn for $a_1$ seconds once it has been refilled, and it takes $b_1$ seconds to refuel the torch after it burns out. Prof. Shou's torch can burn for $a_2$ seconds once it has been refilled, and it takes $b_2$ seconds to refuel the torch after it burns out. The person who is refueling the torch cannot walk simultaneously. For safety reasons, they cannot refuel the torch until the fuel runs out.

Because Prof. Pang is too fat and the cave is too narrow, Prof. Shou cannot surpass Prof. Pang during the exploration, which means that Prof. Shou is at least 1 unit behind Prof. Pang.

Each of them can walk forward a distance of 1 unit per second when his torch is burning. Every second, Prof. Pang moves first, then Prof. Shou does. In order to get to their destination earlier, they will move as long as they can walk forward.

Now Prof. Shou has $n$ questions, and for the $i$-th question, he wants to know that at time $q_i$, how many units of the distance he has moved forward from the starting point? Prof. Shou starts 1 unit behind Prof. Pang. The initial time is 0. Both Prof. Pang and Prof. Shou refueled the torch before the initial time.

inputFormat:
The first line contains one integer $T~(1\le T \le 10^5)$, the number of test cases.

For each test case, the first line contains 5 integers $a_1, b_1, a_2, b_2, n~(1 \le a_1, b_1, a_2, b_2, n \le 10^6)$ denoting the time Prof. Pang's torch can burn, the time for Prof. Pang to refuel his torch, the time Prof. Shou's torch can burn, the time for Prof. Shou to refuel his torch, and the number of Prof. Shou's queries. Each of the next $n$ lines describes a query. Query $i$ is denoted by one integer $q_i~(1 \le q_i \le 10^{16})$.

It is guaranteed that over all test cases, each of the following numbers is no more than $10^6$:

- the sum of $a_1$,
- the sum of $a_2$,
- the sum of $b_1$,
- the sum of $b_2$,
- and the sum of $n$.

outputFormat: For each query, print one line containing the answer -- the number of units that Prof. Shou has walked forward from the starting point.

translation:
## 题目描述

胖子和瘦子在一个山洞里行走，胖子在瘦子前面。每个人都有一支火把。

胖子的火把填满燃料后可以燃烧 $a_1$ 秒，在熄灭后需要花费 $b_1$ 秒填充燃料。

瘦子的火把填满燃料后可以燃烧 $a_2$ 秒，在熄灭后需要花费 $b_2$ 秒填充燃料。

每个人只能在自己的火把燃烧时前进，速度为 $1\operatorname{m/s}$。

因为胖子太胖，所以瘦子只能跟在胖子后面而不能超过胖子。

每一秒胖子先移动，之后瘦子再移动。

初始时两个人的火把都已经填满了燃料，瘦子在胖子后面 $1 \operatorname{m}$。

给定 $n$ 个询问，每次给一个正整数 $q_i$，表示查询第 $q_i$ 秒后，瘦子的移动距离。

## 输入格式

**本题包含多组测试数据**

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

对于每组数据：

第一行五个正整数 $a_1, b_1, a_2, b_2, n$，含义见题目描述。

接下来 $n$ 行，每行一个正整数 $q_i$，表示询问。

## 输出格式

每组数据输出 $n$ 行，表示每个询问的答案，即第 $q_i$ 秒后瘦子的移动距离。

## 数据范围

下面 $\sum n$ 表示所有数据的 $n$ 之和，$\sum a_1, \sum b_1, \sum a_2, \sum b_2$ 同理。

$1 \le T \le 10^5$，$1 \le a_1, b_1, a_2, b_2 \le 10^6$，$\sum a_1, \sum b_1, \sum a_2, \sum b_2, \sum n \le 10^6$，$1 \le q_i \le 10^{16}$。


title: [ICPC2022 Jinan R] DFS Order 2

description:
Prof. Pang has a rooted tree that is rooted at vertex $1$ and has $n$ nodes. These $n$ nodes are numbered from $1$ to $n$.

Now he wants to start the depth-first search at the root. He wonders for each node $v$, how many ways it can appear in the $j$-th position of $\textbf{depth-first search order}$. The depth-first search order is the order of nodes visited during the depth-first search. A node appears in the $j$-th ($1\le j\le n$) position in this order means it is visited after $j-1$ other nodes. Because sons of a node can be iterated in arbitrary order, multiple possible depth-first orders exist.

Prof. Pang wants to know for each node $v$, how many different $\textbf{depth-first search order}$s such that $v$ appears in the $j$-th position. For each $v, j~(1 \le v, j \le n)$, compute the answer. Because the answer can be very large, output it modulo $998244353$.

Following is a pseudo-code for the depth-first search on a rooted tree. After calling $\textbf{main}$(), $\texttt{dfs\_order}$ is the depth-first search order.

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

inputFormat:
The first line contains one integer $n~(1\le n \le 500)$, the number of vertices in the tree.

Each of the next $n-1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects $(1\le u_i,v_i\le n, u_i\neq v_i)$.

It is guaranteed that the given edges form a tree.

outputFormat: For each vertex $v$ from $1$ to $n$, output one line containing $n$ integers modulo $998244353$. The $j$-th integer in the $v$-th line should be the number of different depth-first search orders such that $v$ appears in the $j$-th position.

translation:
### 题目描述

P有一棵树，根节点是$1$，总共有$n$个节点，从$1$到$n$编号。

他想从根节点开始进行深度优先搜索。他想知道对于每个节点$v$，在深度优先搜索中，它出现在第$j$个位置的方式有多少种。深度优先搜索的顺序是在搜索过程中访问节点的顺序。节点出现在第$j（1 \le j \le n $）个位置表示它在访问了$j - 1$个其他节点之后才被访问。因为节点的子节点可以以任意顺序访问，所以有多种可能的深度优先搜索顺序。

P想知道对于每个节点$v$，有多少种不同的深度优先搜索顺序，使得$v$出现在第$j$个位置。对于每个$v$和$j（i \le v,j \le n）$，计算答案。答案可能很大，所以输出时要取模$998244353$。以下是深度优先搜索的伪代码，用于处理树。在调用$main()$函数后， dfs_order将会包含深度优先搜索的顺序。

------------
#### 算法 $1$ 深度优先搜索的实现
```
1. 过程 DFS(节点 x)

2.	将x添加到dfs_order的末尾

3.	对于x的每个子节点y do               ·子节点可以以任意顺序遍历。

4.		DFS(y)

5.	结束循环

6. 结束过程

7. 过程 MAIN()

8.	将dfs_order设为全局变量

9.	dfs_order ← 空列表

10.	DFS(1)

11. 结束过程
```
------------

### 输入格式

第一行包含一个整数$n（1\le n\le 500）$，表示树中的节点数量。

接下来的n-1行描述了树的边。第i行包含两个整数$u_i$和$v_i$，表示连接的两个节点的标签$（1\le u_i,v_i\le n,u_i\not=v_i）$。

保证给定的边构成一棵树。

### 输出格式

对于每个从$1$到$n$的节点$v$，输出一行，包含$n$个整数，取模$998244353$。在第$v$行中，第$j$个整数表示不同的深度优先搜索顺序中，节点$v$出现在第$j$个位置的数量。

 	翻译由@ayf2192538031提供


title: [ICPC2022 Jinan R] Frozen Scoreboard

description:
There was an ICPC contest two thousand years ago in the Qin dynasty. There were $m$ problems and $n$ teams in the contest. We only know how many problems each team solved and how much total time they used from the historical records. These are called the $\textbf{final result}$s of the teams. We don't know which problems they solved or their submission times.

Recently, we seem to had a discovery. We found the $\textbf{frozen scoreboard}$ of the teams. From the frozen scoreboard of a team, we know their submissions during the whole contest, but we don't know the verdicts of the submissions in the last hour. And some people found that for some teams, their frozen scoreboards may contradict their final results in the historical records.

Given the final results and the frozen scoreboards of the teams, please construct a $\textbf{final scoreboard}$ for each team that is consistent with both its final result and its frozen scoreboard.

From the submissions during the contest, we can calculate the final scoreboard and the final result as follows:

For a fixed team $i$, its $\textbf{final scoreboard}$ is an array of $m$ elements where the $j$-th element shows some information about team $i$'s submissions on problem $j$.

- If team $i$ didn't submit to problem $j$, the cell should be a single character ``.`` (without quotes).

- If team $i$ submitted $x$ times to problem $j$ and none of the submissions was accepted, the cell should contain $-\ x$.

- Otherwise, consider all submissions from team $i$ to problem $j$. Each submission has a submission time. Suppose the earliest accepted submission is the $x$-th one. Then the cell should contain $+\ x/y$ where $y~(0\le y\le 299)$ is the submission time of the $x$-th submission. $y$ is an integer representing the submission time in minutes.

Note that in the final scoreboard, we don't care about submissions after the first accepted one. It is possible that two or more submissions happened in the same minute.

The $\textbf{final result}$ of a team is computed from its $\textbf{final scoreboard}$. For each team, we can calculate the number of problems it solved. This number is equal to the number of ``+`` in the team's final scoreboard.

We can also calculate its total time. If team $i$ solved problem $j$ in the $y$-th minute after $x-1$ unaccepted submissions (in other words, the $j$-th cell of its final scoreboard is $+\ x/y$), problem $j$ contributes $20(x-1)+y$ time to team $i$. If team $i$ didn't solve problem $j$, problem $j$ contributes $0$ time to team $i$, no matter team $i$ submitted to problem $j$ or not. The total time of team $i$ is the sum of contributions of each problem.

The rules for the $\textbf{frozen scoreboard}$ will be introduced in the input section. We will distinguish submissions in the final hour and other submissions. A submission was in the final hour if its submission time is between $240$ and $299$.

inputFormat:
The first line contains two integers $n, m~(1\le n\le 1000, 1\le m\le 13)$, the number of teams in the contest, and the number of problems in the contest.

Then there are $n$ blocks describing the $\textbf{final result}$ and the $\textbf{frozen scoreboard}$ of each team.

The $i$-th block represents team $i$. In the $i$-th block, the first line contains two integers $a_i, b_i~(0\le a_i\le m, 0\le b_i\le 10^5)$, the number of problems team $i$ solved $\textbf{during the whole contest}$ and the total time of team $i$ for solving the $a_i$ problems. These two numbers represent the final result of the contest. The next $m$ lines describe the status of team $i$ in the frozen scoreboard. For each $1\le j\le m$,

- If the $j$-th line is $+\ x/y$ $(1\le x\le 100, 0\le y\le 239)$, team $i$ solved problem $j$ at time $y$ and the accepted solution is their $x$-th submission on problem $j$.
- If the $j$-th line is $?\ x\ y$ $(1\leq x \leq y \leq 100)$, team $i$ didn't solve the problem $j$ in the first four hours. Team $i$ submitted problem $j$ for $y$ times in which $x$ submissions are in the last hour. Note that submissions made in the last hour after the accepted one will count in the $\textbf{frozen scoreboard}$, but not in the $\textbf{final scoreboard}$.
- If the $j$-th line is $-\ x$, team $i$ didn't solve the problem $j$ in the first four hours. Team $i$ submitted problem $j$ for $x~(1\le x\le 100)$ times before the last hour and did not submit problem $j$ in the last hour.
- If the $j$-th line is a single character ``.`` (without quotes), team $i$ didn't submit problem $j$ at all.

outputFormat:
For each team $i$, if its final result contradicts its frozen scoreboard, output $\texttt{No}$ in one line. Otherwise, output $\texttt{Yes}$ in the first line and then output $m$ lines, describing a final scoreboard that is consistent with both the final result and the frozen scoreboard of team $i$. The $j$-th line should contain

- $+\ x/y$ $(1\le x \le 100, 0\le y \le 299)$, if the $x$-th submission from team $i$ to problem $j$ is accepted and is in the $y$-th minute of the contest. All submissions from team $i$ to team $j$ before the $x$-th one was not accepted. Please don't output extra spaces before and after slash ``/``.
- $-\ x$ $(1\le x\le 100)$, if team $i$ submitted to problem $j$ for $x$ times and none of the submissions was accepted.
- $.$ if team $i$ didn't submit to problem $j$ at all.

If there are multiple solutions, output any.

$\textbf{Please note that in the input and the output, there is always a space following each ?, +, and -.}$

translation:
### 题目描述

2000 年以前的秦朝，曾举办过一次 ICPC 比赛。比赛中有 $m$ 道题，$n$ 个团队。我们知道每个队完成了多少道题以及其历史记录的总用时。这些称作该团队的结果，但是我们不知道他们每道题是否完成、用时多久。

最近，我们发现了每个队**冻结的计分板**。从该计分板上，我们可以看到每个队在比赛中的提交情况，但是不知道在最后一小时内提交的判分。一些人发现，对于一些队来说，他们冻结的计分板可能与他们在历史记录中的最终成绩相矛盾。

请根据最终得分和冻结的计分板，为各队创建一个与其最终结果和冻结的计分板一致的最终计分板。

按照以下规则来计算计分板和总分：

对于给定的队伍 $i$，它**最终的计分板**是一个 $m$ 元数组，其中第 $j$ 个元素给出队伍 $i$ 在第 $j$ 题上的提交信息。

- 如果队伍 $i$ 没有提交问题 $j$，输出 ```.```。

- 如果队伍 $i$ 对问题 $j$ 提交了 $x$ 次但均未通过，输出 $-x$。

- 否则，考虑队伍 $i$ 在问题 $j$ 的所有评测结果。每次提交都有一个提交时间，设第一个通过的评测是第 $x$ 次评测，在第 $y$ 分钟时提交。输出 $+x/y$，其中 $0\leq y\leq299$。

在最终计分板上，只考虑第一次通过的提交。同一分钟内可能有多次提交。

一个队伍的最终得分是该队伍完成了多少道题，即该队最终计分板上 ```+``` 的个数。

一个队伍总用时按如下方式计算。如果队伍 $i$ 在第 $y$ 分钟完成了第 $j$ 道题，在完成前有 $x-1$ 次失败的提交（即最终计分板上第 $j$ 个问题的数为 $+x/y$），该问题的用时记为 $20(x-1)+y$。 如果队伍 $i$ 没有完成第 $j$ 道题，该问题的用时记为 $0$，无论是否提交过。队伍 $i$ 的总时间是每道题用时的总和。

### 输入格式

第一行包括两个整数 $n,m\;(1\leq n\leq1000,1\leq m\leq13)$，为队伍个数和题目个数。

接下来 $n$ 组，描述每个队伍的最终得分和冻结的计分板。

第 $i$ 组表示队伍 $i$。每一组中，第一行包括两个整数 $a_i,b_i\;(0\leq a_i\leq m,0\leq b_i\leq10^5)$，为队伍 $i$ 在**整场比赛中**完成的题目个数和每道题的用时。这两个数字是比赛的最终结果。

接下来 $m$ 行，描述队伍 $i$ 在计分板上的内容。对于任意 $1\leq j\leq m$，

- 如果第 $j$ 行是 $+\,x/y\;(1\leq x\leq100,0\leq y\leq239)$，表示队伍 $i$ 在第 $y$ 分钟，第 $x$ 次提交时通过了题 $j$。

- 如果第 $j$ 行是 $?\,x\,y\;(1\leq x\leq y\leq100)$，表示队伍 $i$ 没有在前四个小时中作出题 $j$。这个队伍提交了 $y$ 次，其中 $x$ 次在最后一小时内。最后一小时内且通过该题的提交记录会在**冻结的计分板**上显示，但不会在**最终计分板**上显示。

- 如果第 $j$ 行是 $-x$，表示队伍 $i$ 没有在前四小时内作出题 $j$。这个队伍在最后一个小时前提交了 $x\,(1\leq x\leq100)$ 次，且没有在最后一小时内做出题 $j$。

- 如果第 $j$ 行是一个单一的字符 ```.```，表示队伍 $i$ 没有提交过题 $j$。

### 输出格式

对于每个队伍 $i$，如果最终结果和冻结的计分板相矛盾，输出一行 $\texttt{No}$。否则，第一行输出 $\texttt{Yes}$，接下来 $m$ 行，描述一种队伍 $i$ 可能的计分板，满足最终结果和冻结的计分板。其中，第 $j$ 行应该包括：

- $+\,x/y\,(1\leq x\leq100,0\leq y\leq299)$，如果队伍 $i$ 在第 $x$ 次提交，第 $y$ 分钟完成了题 $j$，在这之前没有队伍通过这道题。不要在字符 ```/``` 前后输出多余的空格。

- $-x\,(1\leq x\leq100)$，如果队伍 $i$ 提交了 $x$ 次题 $j$，且均未通过。

- ```.```，如果队伍 $i$ 没有提交题 $j$。

如果有多种可能的答案，任意输出一种即可。

**请注意，在输入和输出中，```?,+,-``` 后总有一个空格。**

hint:
Here is an example of the frozen scoreboard in the first sample.

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


title: [ICPC2022 Jinan R] Identical Parity

description:
Let the value of a sequence be the sum of all numbers in it.

Determine whether there exists a permutation of length $n$ such that the values of all subsegments of length $k$ of the permutation share the same parity. The values share the same parity means that they are all odd numbers or they are all even numbers.

A subsegment of a permutation is a contiguous subsequence of that permutation. A permutation of length $n$ is a sequence in which each integer from $1$ to $n$ appears exactly once.

inputFormat:
The first line contains one integer $T~(1\le T \le 10^5)$, the number of test cases.

For each test case, the only line contains two integers $n,k~(1 \le k \le n \le 10^9)$.

outputFormat:
For each test case, output $\texttt{Yes}$ (without quotes) if there exists a valid permutation, or $\texttt{No}$ (without quotes) otherwise.

You can output $\texttt{Yes}$ and $\texttt{No}$ in any case (for example, strings $\texttt{YES}$, $\texttt{yEs}$ and $\texttt{yes}$ will be recognized as positive responses).

translation:
### 题目描述

定义一个序列的 **权值** 等于这个序列所有的元素之和。

试判断：是否存在一个长度为 $n$ 的 **排列**，满足以下约束条件？

- 其所有长度为 $k$ 的 **子区间** 的权值具有相同的奇偶性。

### 输入格式

第一行一个整数 $T$ $(1\leqslant T\leqslant 10^5)$，表示测试数据组数。

对于每组测试数据，仅有一行两个整数 $n,k$ $(1\leqslant k\leqslant n\leqslant 10^9)$，含义见“题目描述”。

### 输出格式

对于每组测试数据，输出一行一个字符串。若存在符合题意的排列，输出 $\texttt{Yes}$；否则，输出 $\texttt{No}$。

你可以以任意的大小写输出 $\texttt{Yes}$ 和 $\texttt{No}$（例如，$\texttt{YES}$，$\texttt{yEs}$ 和 $\texttt{yes}$ 都会被视作合法的输出）。

### 样例解释

对于第一组测试数据，能够证明不存在任何符合题意的排列。

对于第二组测试数据，$[1,2,3,4]$ 是一个符合题意的排列。其所有长度为 $2$ 的子区间分别为 $[1,2],[2,3],[3,4]$，它们的权值分别为 $3,5,7$，具有相同的奇偶性。

对于第三组测试数据，$[1,2,3,5,4]$ 是一个符合题意的排列。其所有长度为 $3$ 的子区间分别为 $[1,2,3],[2,3,5],[3,5,4]$，它们的权值分别为 $6,10,12$，具有相同的奇偶性。

hint:
In the first test case, it can be shown that there does not exist any valid permutation.

In the second test case, $[1,2,3,4]$ is one of the valid permutations. Its subsegments of length $2$ are $[1,2],[2,3],[3,4]$. Their values are $3,5,7$, respectively. They share the same parity.

In the third test case, $[1,2,3,5,4]$ is one of the valid permutations. Its subsegments of length $3$ are $[1,2,3],[2,3,5],[3,5,4]$. Their values are $6,10,12$, respectively. They share the same parity.


title: [ICPC2022 Jinan R] Grid Points

description:
You are given a simple polygon in the first quadrant of the Cartesian plane. This means that the coordinate $(x, y)$ of any point in the polygon satisfies $x> 0$ and $y> 0$.

Consider all grid points in the polygon. Order them in increasing order of \textbf{slopes}. Output the $k$-th grid point in this order.

A grid point is a point $(x, y)$ such that $x$ and $y$ are integers. A point on the boundary of a polygon is considered to be in the polygon. The slope of point $(x, y)$ is $y/x$. If two points have the same slope, they are ordered lexicographically first by $x$, then by $y$. In other words, a point $(x_1, y_1)$ is lexicographically less than $(x_2, y_2)$ if $(x_1<x_2)\vee (x_1=x_2 \wedge y_1<y_2)$.

inputFormat:
The first line contains one integer $T~(1\le T \le 500)$, the number of test cases.

For each test case, the first line contains two integers $n, k~(n\ge 3, 1\le k)$. Each of the next $n$ lines describes a vertex of the polygon. Each vertex is denoted by two integers $x, y~(1\le x, y\le 10^9)$, representing its coordinate $(x, y)$. The vertices are given in counterclockwise order.

It is guaranteed that the polygon is simple, i.e.~ the vertices are distinct, two edges may overlap only when they are consecutive on the boundary, and the overlap contains exactly $1$ point. It is guaranteed that $k$ is no more than the number of grid points in the polygon.

It is guaranteed that the sum of $n$ over all test cases is no more than $2000$.

outputFormat: For each test case, output two integers $x, y$ in one line representing the coordinate $(x, y)$ of the $k$-th grid point.

translation:
## 题目描述

在笛卡尔平面的第一个象限中，您会得到一个简单的多边形。这意味着多边形中任何点的坐标$（x，y）$满足$x>0$和$y>0$。

考虑多边形中的所有网格点。按\textbf｛斜率｝的递增顺序排列。按此顺序输出第$k$个网格点。

网格点是一个点$（x，y）$，使得$x$和$y$是整数。多边形边界上的一个点被认为在多边形中。点$（x，y）$的斜率为$y/x$。如果两个点具有相同的斜率，则它们首先按字典顺序排列$x$，然后按$y$。换句话说，如果$（x_1<x_2）\vee（x_1=x_2\wedge y_1<y_2）$，则点$（x_1，y_1）$在字典上小于$（x_2，y_2）。

## 输入格式

第一行包含一个整数$T~（1\le T\le 500）$，即测试用例的数量。

对于每个测试用例，第一行包含两个整数$n，k~（n\ge 3，1\le k）$。接下来的每一条$n$线都描述了多边形的一个顶点。每个顶点由两个整数$x，y~（1\le x，y\le 10^9）$表示，表示其坐标$（x，y）$。顶点按逆时针顺序排列。

保证多边形是简单的，即顶点是不同的，两条边只有在边界上连续时才能重叠，并且重叠恰好包含$1$点。可以保证$k$不超过多边形中的网格点数。

保证所有测试用例的总金额不超过2000美元。

## 输出格式

对于每个测试用例，在一行中输出两个整数$x，y$，表示第$k$个网格点的坐标$（x，y）$。

## 输入输出样例

### 输入 #1

```
4
3 3
1 1
3 1
3 3
4 5000000000000000
1 1
1000000000 1
1000000000 1000000000
100000000
9 22
9 6
6 7
9 7
10 10
6 9
3 9
1 6
1 5
7 3
5 22447972861454999
270353376 593874603
230208698 598303091
237630296 255016434
782669452 568066304
654623868 958264153
```

### 输出 #1

```
3 2
500000000 500000000
7 8
730715389 644702744
```


title: [ICPC2022 Jinan R] Quick Sort

description:
When Prof. Pang was young, he wrote the following code for quick sort. Please calculate how many swaps are performed when calling $\textbf{quicksort}$$(A, 1, n)$. $A$ is a given permutation with length $n$.

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

inputFormat:
The first line contains one integer $T~(1\le T \le 10^5)$, the number of test cases.

For each test case, the first line contains one positive integer $n~(1\le n \le 5\times 10^5)$. The next line contains $n$ integers $a_1,\ldots, a_n~(1 \le a_i\le n)$ denoting the permutation $A$. It is guaranteed that $a_1,\ldots, a_n$ form a permutation, i.e.~$a_i\neq a_j$ for $i \neq j$.

It is guaranteed that the sum of $n$ over all test cases is no more than $5\times 10^5$.

outputFormat: For each test case, output one line containing the number of swaps performed when calling $\texttt{quicksort}(A, 1, n)$.

translation:
### 题目描述

给定一个长度为 $n$ 的排列 $A$。现使用如下伪代码对 $A$ 进行排序：

```
procedure QUICKSORT(A,lo,hi)
    if lo>=0 and hi>=0 and lo<hi then
    	p=PARTITION(A,lo,hi)
        QUICKSORT(A,lo,p)
        QUICKSORT(A,p+1,hi)
    end if
end procedure
procedure PARTITION(A,lo,hi)
    pivot=A[floor((hi+lo)/2)]
    i=lo-1
    j=hi+1
    while True do
        repeat
            i=i+1
        until A[i]>=pivot
        repeat
            j=j-1
        until A[j]<=pivot
        if i>=j then
            return j
        end if
        Swap A[i] with A[j]
    end while
end procedure
```

试计算：调用 `QUICKSORT(A,1,n)` 函数过程中，`Swap` 操作执行了多少次。

### 输入格式

第一行包含一个整数 $T$ $(1\leqslant T\leqslant 10^5)$，表示测试数据组数。

对于每组测试数据：

第一行包含一个正整数 $n$ $(1\leqslant n\leqslant 5\times 10^5)$。

第二行包含 $n$ 个整数 $a_1,\dots,a_n$ $(1\leqslant a_i\leqslant n)$，表示排列 $A$。保证 $a_1,\dots,a_n$ 构成一个排列，即：$\forall i\not= j,a_i\not=a_j$。

保证所有测试数据中 $n$ 的和不超过 $5\times 10^5$。

### 输出格式

对于每组测试数据，输出一行一个整数，表示调用 `QUICKSORT(A,1,n)` 函数过程中，`Swap` 操作执行的次数。


title: [ICPC2022 Jinan R] Set of Intervals

description:
Prof. Pang has a multi-set of intervals $S=\{[l_i,r_i]\}$($l_i<r_i$).

Prof. Pang will perform the following operation for $|S|-1$ times:

- Select two intervals $[a,b]$ and $[c,d]$ from $S$, and then choose two integers $x,y$ satisfying $x\in [a,b], y\in [c,d], x<y$. After that, delete $[a,b]$ and $[c,d]$ from $S$, and add $[x,y]$ to $S$.

It's easy to find that $S$ contains exactly one interval after the operations, and Prof. Pang will get the interval as a gift.

Now Prof. Pang wants you to calculate how many different intervals he can get.

inputFormat:
The first line contains one integer $T~$($1\le T \le 10^4$), the number of test cases.

For each test case, the first line contains one integer $n~$($1\le n\le 10^5$) --- the size of $S$. Each of the following $n$ lines contains two integers $l_i$ and $r_i~$($1\le l_i<r_i\le 10^9$), describing the $i$-th interval in $S$.

It is guaranteed that the sum of $n$ over all test cases is no more than $10^5$.

outputFormat: For each test case, output one line containing the answer to Prof. Pang's question.

translation:
蓝蓝有一个元素全为闭区间的可重集 $S=\{[l_i,r_i]\}$($l_i<r_i$)。

蓝蓝将会执行以下操作 $n-1$ 次：
- 从 $S$ 内选择两个闭区间 $[a,b]$ 和 $[c,d]$，再选择两个整数 $x,y$ 满足 $x\in [a,b], y\in [c,d], x<y$，然后从 $S$ 中删去 $[a,b]$ 和 $[c,d]$，并把 $[x,y]$ 添加进 $S$。

显然最终 $S$ 中有且仅有一个区间。现在蓝蓝想知道她可以获得多少不同的区间。


title: [ICPC2022 Jinan R] Shortest Path

description:
You are given an undirected weighted graph $G$ with vertices $1, 2, \ldots, n$. Please output the sum of the answers to the following $x$ questions:
- The $i$-th question $(1\le i\le x$): What is the minimum length of path that starts at vertex $1$, ends at vertex $n$, and contains exactly $i$ edges?

For each question, if such a path does not exist, the answer is considered to be $0$. A path may use one edge multiple times. Output the answer modulo $998244353$.

inputFormat:
The first line contains one integer $T~(1 \le T\le 2000)$, the number of test cases.

For each test case, the first line contains three integers $n, m, x~(1\le n\le 2000, 0\le m\le 5000, 1\le x\le 10^9)$. Each of the next $m$ lines describes an edge of the graph. Edge $i$ is denoted by three integers $a_i, b_i, w_i$ $(1\le a_i, b_i\le n, 1\le w_i\le 10^9)$, the labels of vertices it connects and its weight. Note that self-loops and parallel edges may exist.

It is guaranteed that the sum of $n$ over all test cases is no more than $2000$ and the sum of $m$ over all test cases is no more than $5000$.

outputFormat: For each test case, output one integer modulo $998244353$ denoting the answer.

translation:
### 题目描述

给定一张 $n$ 个点 $m$ 条边的无向图 $G$，边有边权。你要回答 $x$ 个问题，其中第 $i$ $(1\leqslant i\leqslant x)$ 个问题形如：

- 从结点 $1$ 出发，经过 **恰好** $i$ 条边，到达结点 $n$ 的最短路径长度为多少？

对于每个询问，若不存在这样的路径，答案应当为 $0$。一条路径可能 **多次** 经过一条边。

求出这 $x$ 个问题所对应的答案之和。输出答案对 $998244353$ 取模后的结果。

### 输入格式

第一行包含一个整数 $T$ $(1\leqslant T\leqslant 2000)$，表示测试数据组数。

对于每组测试数据：

第一行三个整数 $n,m,x$ $(1\leqslant n\leqslant 2000,0\leqslant m\leqslant 5000,1\leqslant x\leqslant 10^9)$。

接下来 $m$ 行，每行三个整数 $a_i,b_i,w_i$ $(1\leqslant a_i,b_i\leqslant n,1\leqslant w_i\leqslant 10^9)$，分别表示第 $i$ 条边连接的两个结点的编号和其边权。注意 **可能存在自环和重边**。

保证所有测试数据中 $n$ 的总和不超过 $2000$，且 $m$ 的总和不超过 $5000$。

### 输出格式

对于每组测试数据，输出这组测试数据对应的答案 $\bmod$ $998244353$ 后的结果。


title: 说唱

background: 在题目描述末尾有形式化题意。

description:
ZHY 在一个空旷的房间里练习说唱。

ZHY 初始时会发出一个强度为 $x$ 的声音，这个声音会与墙壁发生碰撞，产生一个强度为 $\lfloor \frac x {10} \rfloor$ 的回声。回声会继续与墙壁碰撞，产生回声的回声……直到这个回声的强度为 $0$。

房间里还有一个收音机，它会记录下来所有的声音（包括初始发出的声音和所有回声）。可惜，ZHY 一不小心把收音机弄坏了。现在，收音机只能显示出记录下的所有声音的强度之和 $y$，你能通过这个仅有的信息计算出 ZHY 初始发出的声音的强度是多少吗？由于收音机太过古老，可能会出现一些故障导致显示的数有误。对于这种情况，你需要输出 $-1$。

**形式化题意**

如下定义一个函数：

$$f(x)=\begin{cases} 0 & x = 0 \\ x+f(\lfloor\frac{x}{10}\rfloor) & x > 0 \end{cases}$$

比如 $f(123)=123+12+1=136$。

给定一个数 $y$，请求出是否存在唯一的一个数 $x$ 满足 $f(x)=y$，如果有则输出 $x$，否则输出 $-1$。

inputFormat:
本题有多组数据。

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

每一组数据包含一行一个整数 $y$。

outputFormat: 对于每组数据，若存在唯一的 $x$ 对应这个 $y$，则输出 $x$。否则，输出 `-1`。


title: [ICPC2021 Macao R] So I'll Max Out My Constructive Algorithm Skills

description:
BaoBao the Witch is stuck in a maze with $n$ rows and $n$ columns, where the height of the cell in the $i$-th row and the $j$-th column is $h_{i,j}$. To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down.

More formally, you need to find a sequence $(x_1, y_1), (x_2, y_2), \cdots, (x_{n^2}, y_{n^2})$ such that:
- For all $1 \le i \le n^2$, $ 1 \le x_i, y_i \le n$;
- For all $1 \le i, j \le n^2, i \neq j$, $ (x_i, y_i) \neq (x_j, y_j)$;
- For all $2 \le i \le n^2$, $|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$;
- $\sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}]} \le \sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]}$, where $[P]$ equals $1$ when $P$ is true, and equals $0$ when it is false.

Additionally, you discover that the heights in all cells are a permutation of $n^2$, so you just need to output the height of each cell in a valid path.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 100$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 64$) indicating the size of the maze.

For the following $n$ lines, the $i$-th line contains $n$ integers $h_{i, 1}, h_{i, 2}, \cdots, h_{i,n}$ ($1 \le h_{i, j} \le n^2$) where $h_{i,j}$ indicates the height of the cell in the $i$-th row and the $j$-th column. It's guaranteed that all integers in the input make up a permutation of $n^2$.

outputFormat:
For each test case output one line containing $n^2$ separated by a space indicating the heights of each cell in a valid path. If there are multiple valid answers you can output any of them. It's easy to prove that an answer always exists.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

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

宝宝女巫被困在一个 $n$ 行 $n$ 列的迷宫中，其中第 $i$ 行第 $j$ 列的单元格高度为 $h_{i,j}$。要走出迷宫，宝宝必须找到一条路径，该路径穿过每个单元格恰好一次。每次她只能移动到与当前单元格共享边的相邻单元格。但是众所周知，宝宝非常懒，所以每当她爬升（即从高度较低的单元格移动到高度较高的单元格）时，她的幸福值会减少。作为她的帮手，你的任务是找到一条有效的路径，使得沿着路径移动时，宝宝爬升的次数不多于她下降的次数。

更正式地说，你需要找到一个序列 $(x_1, y_1), (x_2, y_2), \cdots, (x_{n^2}, y_{n^2})$，使得：
- 对于所有的 $1 \le i \le n^2$，$ 1 \le x_i, y_i \le n$；
- 对于所有的 $1 \le i, j \le n^2, i \neq j$，$ (x_i, y_i) \neq (x_j, y_j)$；
- 对于所有的 $2 \le i \le n^2$，$|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$；
- $\sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}]} \le \sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]}$，其中 $[P]$ 当 $P$ 为真时等于 $1$，当为假时等于 $0$。

此外，你发现所有单元格的高度都是 $n^2$ 的排列，所以你只需要输出有效路径中每个单元格的高度。

**【输入格式】**

有多个测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$（$2 \le n \le 64$），表示迷宫的大小。

接下来的 $n$ 行，第 $i$ 行包含 $n$ 个整数 $h_{i, 1}, h_{i, 2}, \cdots, h_{i,n}$（$1 \le h_{i, j} \le n^2$），其中 $h_{i,j}$ 表示第 $i$ 行第 $j$ 列单元格的高度。保证输入中的所有整数构成 $n^2$ 的排列。

**【输出格式】**

对于每个测试用例，输出一行，包含 $n^2$ 个由空格分隔的整数，表示有效路径中每个单元格的高度。如果有多个有效答案，你可以输出其中任何一个。很容易证明答案总是存在。

请不要在每行的末尾输出多余的空格，否则你的答案可能会被认为不正确！

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