title: [COCI2022-2023#1] Berilij（暂无spj）

background: 小羊 Berilij 被外星人绑架了。她需要帮助外星人解决一个问题。

description:
就在 COCI 比赛当天，外星人计划乘 $n$ 艘宇宙飞船访问地球，授予参赛者丰厚的奖励。他们的宇宙飞船都是完美的圆形。

出于安全考虑，他们选择了 $m$ 对在着陆时外部必须相接触的飞船。外星人已经确定了每艘飞船的着陆点坐标，而 Berilij 的任务是确定每艘飞船的半径，以确保所有飞船都能安全着陆。

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

如图，左右两对飞船均不满足外部接触的条件。只有中间的一对飞船满足外部接触的条件。换句话说，“外部接触”定义为当且仅当两艘飞船对应的圆形**外切**时，这两艘飞船的外部相接触。

宇宙飞船造价昂贵，它们的成本等于它们的面积，所以外星人希望宇宙飞船成本尽可能小。由于外星人科技非常先进，因此外星人的宇宙飞船可以重叠，直径也可以为 $0$。

如果 Berilij 不能解决这个问题，外星人将会吃掉她！请你帮帮小羊 Berilij。

inputFormat:
第一行包含两个整数 $n,m$，分别表示外星人的飞船数量以及需要接触的飞船的对数。

接下来 $n$ 行每行两个实数 $x_i,y_i$，表示第 $i$ 艘飞船着陆点的坐标。给出的坐标均精确到小数点后十位。

下面的 $m$ 行包含两个整数 $a_i$ 和 $b_i$，表示第 $a_i$ 号和第 $b_i$ 号飞船在着陆后必须外部接触。数据保证无序对 $(a_i,b_i)$ 不重复。

outputFormat:
如果无解，输出一行```NE```。

否则第一行输出```DA```，接下来 $n$ 行输出成本最小的方案下每艘飞船的半径。

hint:
当你的答案与正确答案误差不大于 $10^{-4}$ 时，答案被视为正确的。

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $15$ | $n$ 为奇数且所有飞船都恰好与两艘飞船接触 |
| $2$ | $25$ | 数据保证有解 |
| $3$ | $30$ | 对于任何一对飞船 $(a,b)$ 都有且仅有一个飞船序列满足其起始于 $a$ 结束于 $b$ 且此序列内任意相邻的两艘飞船都彼此接触 |
| $4$ | $40$ | 无特殊性质 |

对于 $100\%$ 的数据，$1\leq n,m \leq 10^5,-10^4\leq x_i,y_i \leq 10^4,1\leq a_i,b_i \leq n$ 且 $a_i \neq b_i$。

本题满分 $110$ 分。


title: [COCI2022-2023#1] Neboderi

type: P

background: Domagoj 来到了伦敦这个大城市！现在有一排高摩天大楼在他面前，他想拍张照片来纪念这一时刻。

description:
这排摩天大楼共有 $n$ 座，它们可以被视作序列 $h_1,h_2,...h_n$，其中 $h_i$ 为第 $i$ 栋楼的高度。Domagoj 将会拍下这排大楼的一个子区间。为了更好地捕捉城市之美，他想拍摄至少 $k$ 座摩天大楼。

Domagoj 有着奇怪的审美：他认为照片中有高大的摩天大楼是美的；但如果照片中所有的摩天大楼的高度有着很大的公因数，他会认为更美。

如果一张照片拍下的大楼区间为 $[l,r]$，且这段区间内所有大楼高度的 $\gcd$ 为 $g$，则 Domagoj 定义这张照片的“美丽度”为 $g \times \sum_{i=l}^r h_i$。

帮助 Domagoj 算出他能拍到的最美照片的美丽度吧！

inputFormat:
第一行包含两个整数 $n,k$，分别表示大楼总数和 Domagoj 至少拍到的大楼数。

第二行包含 $n$ 个整数 $h_i$，依次表示每座大楼的高度。

outputFormat: 一行一个整数，即最大美丽值。


title: [语言月赛202212] 旋转排列

type: B

background:
我们称一个数列 $p$ 是一个长度为 $n$ 的排列，当且仅当 $p$ 满足如下条件：

1. $p$ 的长度为 $n$；
2. $1, 2, 3, \dots n$ 这 $n$ 个数在 $p$ 中均**恰好**出现一次。

description:
对于一个排列 $p$，定义一次“shift”操作是指：将 $p$ 里的每一个数字都依次向后移动一位，并把 $p$ 的最后一个数字移动到开头去。

例如，若排列 $p$ 初始时为 $[1,4,2,3]$，则“shift”一次以后将变为 $[3,1,4,2]$。

现在，给定一个长度为 $n$ 的排列 $p$，请你按照如下规定循环操作：
1. 对当前的排列 $p$ 做一次“shift”操作；
2. 输出本次“shift”以后的排列 $p$；
3. 判断排列 $p$ 的最后一个数字是否是 $n$，如果是，则结束循环操作；否则回到 $1$ 继续操作。

提示：**请严格按照题目给出的顺序进行循环操作。**

inputFormat:
第一行是一个整数，表示排列 $p$ 的长度 $n$。
第二行有 $n$ 个整数表示排列 $p$，第 $i$ 个整数表示 $p_i$。

outputFormat: 对于每次操作的第二条“输出”操作，请你输出一行 $n$ 个整数，按顺序表示当前排列的每个数，一行中相邻两个数之间用一个空格隔开。

hint:
### 样例 2 解释

对 $p = [1, 2, 3]$，按如下顺序进行循环操作：

1. 进行一次“shift”操作，$p$ 变为 $[3,1,2]$；
2. 输出当前的排列 $p$，故输出第一行为 `3 1 2`；
3. 判断 $p_3 = 2 \neq 3$，故继续循环操作；
4. 进行一次“shift”操作，$p$ 变为 $[2,3,1]$；
5. 输出当前的排列 $p$，故输出第二行为 `2 3 1`；
6. 输出判断 $p_3 = 1 \neq 3$，故继续循环操作；
7. 进行一次“shift”操作，$p$ 变为 $[1,2,3]$；
8. 输出当前的排列 $p$，故输出第二行为 `1 2 3`；
9. 输出判断 $p_3 = 3 =3$，故停止循环；

### 数据规模与约定

各测试点的信息如下表：
| 测试点编号 | $n = $ | 特殊约定 |
| :-: | :-: | :-: |
| $1$ | $1$ | 无|
| $2$ | $2$ | 无 |
| $3$ | $3$ | 无 |
| $4 \sim 6$ | $2000$ | $p_{n - 1} = n$ |
| $7 \sim 10$ | $2000$ | 无 |

对全部的测试点，保证 $1 \leq p_i \leq n \leq 2000$，$p$ 是长度为 $n$ 的排列。

By 一扶苏一


title: 「KDOI-04」Pont des souvenirs

background:
虽然这是一个 C，但是

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

description:
给定正整数 $n,k$，求有多少个长度为 $n$ 的正整数序列 $a$ 满足：

* $0<a_1\le a_2\le a_3\le\cdots\le a_n\le k$；
* $\forall\ i\not=j$，$a_i+a_j\le k+1$。

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

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

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

对于每组测试数据，输入包含一行两个正整数 $n,k$。

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


title: 「KDOI-04」挑战 NPC Ⅲ

description:
小 S 有一个伟大的梦想：证明 $\text{P}=\text{NP}$。

有一天，他得知一般图最大独立集是 NPC 问题后，决定解决他。

当然小 S 太菜了，解决不了，于是求助于你：

> 给出一个含有 $n$ 个顶点，$m$ 条边的无向图 $G$，求 $G$ 中大小恰好为 $n-k$ 的独立集的数量。由于答案可能很大，请将其对 $998~244~353$ 取模。

小 S 不喜欢多测，因为他在 NOIp 中因为多测挂分，所以本题包含多组测试数据。

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

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

对于每组测试数据，第一行三个正整数 $n,m,k$。

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

保证图中不存在自环，但**可能存在重边**。

outputFormat: 对于每组测试数据，输出一行一个正整数，表示符合要求的独立集数量。答案对 $998~244~353$ 取模。

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

对于第 $1,2$ 组测试数据，图是完全图，容易发现，完全图的最大独立集为 $1$，并且每一个顶点都单独构成一个独立集。因此第 $1$ 组测试数据的答案为 $0$，第 $2$ 组测试数据的答案为 $4$。

对于第 $3$ 组测试数据，该组数据中给出的无向图如下：

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

其中，所有大小为 $3$ 的独立集为：

+ $\{2,4,8\}$；
+ $\{2,3,7\}$；
+ $\{3,4,6\}$；
+ $\{2,4,6\}$；
+ $\{1,4,6\}$；
+ $\{2,3,6\}$；
+ $\{1,4,5\}$；
+ $\{2,3,4\}$。

**【数据范围】**

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

![数据范围](https://cdn.luogu.com.cn/upload/image_hosting/p3jwdqp3.png)

对于 $100\%$ 的数据，保证 $1\leq n\leq10^5$，$0\le m\le 10^5$，$0\leq k\leq \min(n-1,18)$，$1\leq T\leq 10^{4}$，$\sum n,\sum m\leq10^6$。

并且对于每个测试点保证：

设 $K=\max k$，即该测试点中所有 $k$ 的最大值，

+ 若 $K\ge 17$，则 $T=1$；
+ 若 $K\ge 15$，则 $T\le 3$；
+ 若 $K\ge 10$，则 $T\le 5$；
+ 若 $K\ge 5$，则 $T\le 300$。


title: 「CGOI-3」招魂术

background:
墓园的骷髅海！

要塞的禁魔球！

塔楼的三后排！

据点的破甲比蒙！

地下城的满魔抗黑龙！

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

###### 塔楼↑

-----
燊队来打英雄无敌 3 了。

description:
招魂术是墓园阵营的核心法术。

拥有招魂术的英雄，在每场战争结束后，能根据消灭的敌军数目来获得一定数量的骷髅。我们可以用整数 $A,B$ 来描述招魂术。设 $F_{A,B}(i)$ 表示消灭 $i$ 个敌人所能获得的骷髅数量，有：

$$F_{A,B}(1)=A,F_{A,B}(2)=B,F_{A,B}(x)=\lfloor \sqrt{F_{A,B}(x-2)F_{A,B}(x-1)}\rfloor+1\;(x \ge 3)$$

现在燊队要在酒馆招募一个英雄，英雄甲招魂术的属性为 $A,B$，英雄乙招魂术的属性为 $X,Y$。为了比较两个英雄招魂术的强弱，请你计算以下式子的值：

$$\prod_{i=1}^nF_{X,Y}(i)-F_{A,B}(i)$$

燊队当然知道怎么做，但他想考考你。

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

接下来 $T$ 行，每行五个整数 $n,A,B,X,Y$。

outputFormat:
输出为 $T$ 行，即每组询问答案对 $998244353$ 取模的结果。

建议使用 `sqrtl` 和 `long double` 进行开平方。


title: 「DPOI-1」道路规划

background: 不可以，总司令。

description:
战场上有 $n$ 个据点，从 $1\sim n$ 编号。**每两个据点**之间**都**有一条双向道路。

一天，总司令来战区巡视，走着走着迷路了，于是愤怒地下达命令，让你把每一条双向道路变成单向的，使得这些道路**不包含环**（否则总司令会迷路）。但由于每个据点的规模互不相同，总司令从第 $i$ 个据点出发沿着单向道路能**直接到达**的据点数量需要在 $[l_i,r_i]$ 之间。换言之，第 $i$ 个点的出度需要在 $[l_i,r_i]$ 之间。你需要告诉总司令有没有可能满足他的需求。

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

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

对于每组数据：

第一行，一个整数 $n$，表示据点数量；

第二行，$n$ 个整数 $l_1, l_2, \dots, l_n$；

第三行，$n$ 个整数 $r_1, r_2, \dots, r_n$。

outputFormat:
对于每组数据：

一行，一个字符串。若可以满足总司令的需求，一行 `YES`；否则，一行 `NO`。

samples:
见下发文件 road2.in
见下发文件 road2.out


title: [入门赛 #7] 狠狠地切割 (Hard Version)

background: **本题与 H1 的题意完全一致，区别仅在数据范围。在语言月赛中不存在 H2 题目，本题仅用于增加公开赛的区分度，并不严格遵循比赛考察范围，请酌情完成。**

description:
现给你一个长度为 $n$ 的序列 $a _ 1, \cdots, a _ n$ 和 $m$ 个互不相同的整数 $b _ 1, \cdots, b _ m$。你需要按照这 $m$ 个数对序列 $a$ 进行**狠狠地切割**。

具体的，对于一个数字 $i \in [1, n]$，如果存在一个整数 $j \in [1, m]$，使得 $a _ i = b _ j$，则将位置 $i$ 称为一个**切割点**。对序列 $a$ 中的每一个切割点，我们在这个位置进行一次**狠狠地切割**。方法是，将该位置的数字去除，然后在这个位置将其左右的**序列/片段**一分两半。

如果对**狠狠地切割**的定义有疑问，可以参照「样例 #1」及「样例解释 #1」进行理解。

你需要计算，在进行了所有可能的**狠狠地切割**后，序列被切割为了多少**片段**。

特别的，如果在切割后，某一段内没有数组，那这一段不可被叫做**片段**。同样的，如果 $1$ 或 $n$ 为切割点，其与开头和结尾之间也不存在片段。

如果对**片段**的概念有疑问，可以参照「样例 #2」及「样例解释 #2」进行理解。

inputFormat:
第一行为两个整数，依次表示序列 $a$ 的长度 $n$ 和序列 $b$ 的长度 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。
第三行有 $m$ 个整数，第 $i$ 个整数表示 $b_i$。

outputFormat: 输出一个整数，代表**狠狠地切割**后的**片段**的个数。

hint:
### 样例 1 解释

在**狠狠地切割**前，序列 $a$ 如下所示：

$$\begin{matrix} 3 & 4 & 3 & 5 & 2 & 6 \end{matrix}$$

容易知道，第二个位置和第四个位置为切割点，我们使用 `|` 对其进行替换，代表去除工作：

$$\begin{matrix} 3 & | & 3 & | & 2 & 6 \end{matrix}$$

我们将片段进行简单的标记：

$$\begin{matrix} \overbrace{3} ^ \text{片段 1} & | & \overbrace{3} ^ \text{片段 2} & | & \overbrace{2 \quad 6} ^ \text{片段 3} \end{matrix}$$

共计 $3$ 个片段。

### 样例 2 解释

以下我们展示去除之后的序列：

$$\begin{matrix} | & 4 & | & | & 2 & | \end{matrix}$$

我们将片段进行简单的标记：

$$\begin{matrix} \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} | & \overbrace{4} ^ \text{片段 1} & | & \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} & | & \overbrace{2} ^ \text{片段 2} & | \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段}\end{matrix}$$

共计 $2$ 个片段。

### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $a$ 序列中没有任何元素在 $b$ 中出现过。形式化的，$\forall i \in [1, n], \forall j \in [1, m], a _ i \neq b _ j$。
- 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 5 \times 10 ^ 5$，$- 10 ^ {18} \leq a _ i, b_i \leq 10 ^ {18}$，序列 $b$ 中的元素两两不同。

### 提示
本题输入规模较大，建议考虑使用较快的读入读出方式。


title: [语言月赛202301] 就要 62

description: 给你一个整数 $x$，你需要判断，这个整数中是否出现过数字 $62$ **或者**能够被 $62$ 整除。如果是，输出 `Yes`，否则输出 `No` 即可。

inputFormat: 输入共一行，为一个整数 $x$。

outputFormat:
输出共一行。

如果 $x$ 中出现过数字 $62$ 或者能够被 $62$ 整除，输出一行 `Yes`，否则输出一行 `No`。

hint:
### 样例 1 解释

显然，$11624$ 中出现了 $62$。

### 样例 2 解释

容易知道，$12214 = 62 \times 197$，所以 $12214$ 可以被 $62$ 整除。

### 样例 3 解释

虽然 $16124$ 中出现了 $6$ 和 $2$，但是没有出现一个完整的 $62$。这种情况不被叫做【出现 $62$】。

### 样例 4 解释

显然，$62$ 中出现了 $62$，也是 $62$ 的倍数。

### 数据规模与约定

对于 $20\%$ 的测试数据，保证 $x \leq 10$；
对于 $40\%$ 的测试数据，保证 $x < 100$；
对于 $100\%$ 的测试数据，保证 $1 \leq x \leq 10 ^ {18}$。


title: [DMOI-R2] 回到过去

background:
 > 想回到过去\
试着抱你在怀里\
羞怯的脸带有一点稚气\
想看你看的世界\
想在你梦的画面\
只要靠在一起就能感觉甜蜜\
想回到过去\
试着让故事继续\
至少不再让你离我而去\
分散时间的注意\
这次会抱得更紧\
这样挽留不知还来不来得及\
想回到过去\
沉默支撑跃过陌生\
静静看着凌晨黄昏\
你的身影 失去平衡\
慢慢下沉\
想回到过去\
—— 周杰伦《[回到过去](https://www.bilibili.com/video/BV1fx411N7bU?p=32&vd_source=2f4592e5507d6452d7d44dc098844d6b)》
>

什么阻碍着两颗心的碰面？什么阻碍着两个人的相见？

或许是令人捉摸不透的时间吧。

description: 给出 $n,m,t$ 以及 $t$ 个障碍物坐标，求在 $n$ 行 $m$ 列的矩阵中的非障碍位置上放置 $k$ 个两两之间没有公共边的方格的方案有多少种，答案对 $10^9+7$ 取模。

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

第一行一个整数 $T$，表示测试点数量。

接下来 $T$ 个测试点，每个测试点的第一行四个整数 $n,m,k,t$。接下来 $t$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个障碍物的坐标（保证不重叠）。

outputFormat: 共 $T$ 行，每行一个整数表示当前询问的答案。


title: [YsOI2023] CF1764B

background:
Ysuperman 模板测试的博弈论题。

都什么年代了，还在玩传统对称博弈，快来玩玩非传统非对称博弈。

猜猜题目名称啥意思，没错就是要你快去做 CF1764B！！！另外这题融合了 CF1495、CF1707、CF1764 的梗（）

description:
今天 Ysuperman 发现了一款非对称博弈游戏，名字叫做 Bugaboo，具体规则如下：

> 在游戏的一开始，Qingshan 手中有一个正整数集 $S$，Daniel 手中有一个正整数集 $T$。
>
> Qingshan 和 Daniel 依次如下操作（Qingshan 先手）：选择在自己数集中的任意两个**不同的**数字 $x,y$，并且还需要满足 $|x-y|$ 不属于**对方的数集**，然后将 $|x-y|$ 加入**对方的数集**。最终无法操作的人失败。
>
> 可以注意到在游戏的进行过程中一个人手中的数集是会不断变化的，他在选择数字 $x,y$ 时既可以选择初始自己拥有的数字，也可以选择后面新增的数字。

现在 Ysuperman 给了你一个正整数集 $R$，Ysuperman 想要知道如果 Qingshan 一开始拥有的集合 $S$ 是 $R$ 的 $2^{|R|}$ 个子集中的任意一个，而 Daniel 一开始拥有的集合 $T$ 也是 $R$ 的 $2^{|R|}$ 个子集中的任意一个，那么在多少种情况下 Qingshan 会赢。

由于答案可能很大， Ysuperman 不想为难你，于是只要你求出答案对 $998,244,353$ 取模后的结果。

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

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$ 表示集合 $R$ 中的所有数。

outputFormat: 输出一行一个数表示答案对 $998,244,353$ 取模后的结果。


title: 「UOI-R1」询问

background: ZSS 有一个序列，但他实在不太聪明，以至于一个操作问题都要来问你了。

description:
给定 $n$ 个数的整数序列 $a_1, a_2, \cdots, a_n$，有 $m$ 次操作，每次操作给定 $x, y$，你需要找到所有 $i$，满足 $i \oplus x = 0$，然后 $a_i \gets a_i - y$。如果没有任何一个这样的 $i$，则序列什么也不会更改。这里的 $\oplus$ 为按位异或操作。

操作结束后，你需要输出这个序列。

inputFormat:
第一行，两个正整数 $n,m$，表示序列长度和操作次数。

接下来一行，表示初始序列。

接下来 $m$ 行，每行两个数 $x,y$，意思如题面所示。

outputFormat: 输出一行，$n$ 个数，表示操作结束后的序列。

samples:
见文件附件的 queries3.in
见文件附件的 queries3.ans

samples:
见文件附件的 queries4.in
见文件附件的 queries4.ans

hint:
对于 $20\%$ 的数据，保证 $1 \leq n, m \leq 10^3$。

对于另外 $20\%$ 的数据，保证 $x=0$。

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^6$，$-10^8 \leq y, a_i \leq 10^{8}$，$0 \leq x \leq n$。


title: [YsOI2022] NOIp 和省选

background: Ysuperman 为了检验他的教学水平，决定给幼儿园的小朋友们来两场摸底考试！

description:
其中一场考试有四道题目，满分 $400$；另一场考试有六道题目，满分 $600$。每个人每场考试得分都是一个 $0$ 到满分间的一个**非负整数**（可以为 $0$ 或者满分）。

有 $n$ 名同学参加了这两场考试，其中第 $i$ 名同学第一场得分 $a_i$，第二场得分 $b_i$，Ysuperman 通过以下规则计算第 $i$ 名同学的**标准得分** $c_i$：

1. 分别统计两场比赛的最高分 $A,B$，有 $A\ne 0$，$B\ne 0$。
2. 令 $c_i=1000(\frac{a_i}{A}+\frac{b_i}{B})$，其中 $c_i$ **四舍五入保留到整数**。

在算出了每位同学的标准得分后，Ysuperman 粗心地弄丢了每位同学的原始分，你能帮 TA 找到任意一组可能的原始分吗？

简单来说，已知 $n$ 和每位同学的**标准得分** $c_{1\sim n}$，Ysuperman 希望你找到一组合法的 $a_{1\sim n}$，$b_{1\sim n}$ 满足上述要求。

特别的，有个十分强的小朋友 Qiu 在两场考试中都拿到了**最高分**，也就是保证 $c_1=2000$。另外其他小朋友水平都差不多，所以保证有 $\forall i>1,c_i\in [10,1990]$。

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

接下来 $n$ 行，第 $i$ 行一个正整数 $c_i$。

outputFormat: 输出共 $n$ 行，第 $i$ 行两个非负整数 $a_i,b_i$，由题意可知你需要保证 $a_i\in [0,400]$，$b_i\in [0,600]$ 并且 $\max a_i>0$，$\max b_i>0$。


title: [YsOI2022] 淀粉树

background: Ysuperman 教大家淀粉质和淀粉树。

description:
Ysuperman 定义一棵**有根树** $S$ 是树 $T$ 的一棵淀粉树当且仅当 $S$ 满足如下两个条件（记 $s_i$ 表示 $S$ 中以 $i$ 为根的子树中所有点构成的点集）：

1. $S$ 与 $T$ 点数相同（不妨设为 $n$）且编号为 $1\sim n$。
1. 对于 $S$ 中任意一个有儿子的点 $i$，对于其任意一个儿子 $j$，满足在 $T$ 中 $i$ 与 $s_j$ 中至少一个点有直接连边。

容易发现一棵树 $T$ 的淀粉树可能有很多棵。

Ysuperman 现在给定 $n$ 以及两棵点编号 $1\sim n$ 的树 $T$ 和树 $S$，设树 $S$ 中度数最大的点的度数为 $d$，TA 需要你进行至少一次且不超过 $d$ 次操作，每次操作把 $T$ 替换成它的任意一棵淀粉树，使得最终 $T$ 变成 $S$。

请注意，这里给定的 $S$ 是没有给定根的，你只需要满足最后 $T$ 的连边情况和 $S$ 相同我们就认为 $T$ 变成了 $S$。

输入保证存在至少一组解。

inputFormat:
第一行两个数 $n,d$，保证 $d$ 等于 $S$ 中度数最大的点的度数。

接下来 $n-1$ 行每行两个数 $u,v$ 表示 $T$ 中 $u,v$ 有连边。保证形成一棵树。

接下来 $n-1$ 行每行两个数 $u,v$ 表示 $S$ 中 $u,v$ 有连边。保证形成一棵树。

outputFormat:
为了方便检验，Ysuperman 需要你按照有根树的形式输出答案。

答案第一行一个正整数 $k(1\le k\le d)$ 表示你进行的操作数。

接下来 $k$ 行第 $i$ 行 $n$ 个整数表示你进行第 $i$ 次操作后 $T$ 变成的有根树中 $1\sim n$ 各个点的父亲编号，根的父亲编号规定为 $0$，**请保证你输出树的根是淀粉树的根**。

hint:
#### 样例 1 解释

这是 $T$：

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

这是 $S$：

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

该输出仅对 $T$ 进行了一次操作，即将 $T$ 变成了下面这棵有根树：

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

这棵有根树是 $T$ 的一棵淀粉树，理由如下：

1. 对于 $2$ 的儿子 $1$，在 $T$ 中 $2$ 与 $s_1=\{1\}$ 中的 $1$ 有直接连边。
2. 对于 $3$ 的儿子 $2$，在 $T$ 中 $3$ 与 $s_2=\{1,2\}$ 中的 $1$ 有直接连边。
3. 对于 $3$ 的儿子 $4$，在 $T$ 中 $3$ 与 $s_4=\{4\}$ 中的 $4$ 有直接连边。
4. 对于 $3$ 的儿子 $5$，在 $T$ 中 $3$ 与 $s_5=\{5\}$ 中的 $5$ 有直接连边。

最终得到的有根树和 $S$ 的连边情况相同，所以这份输出将被判定为正确。

#### 数据范围

子任务 $1$（$20$ 分），满足 $n\le 6$。

子任务 $2$（$20$ 分），满足 $d=2$。

子任务 $3$（$20$ 分），满足 $T$ 可以只进行一次操作即可变成 $S$ 且 $n\le 447$。

子任务 $4$（$20$ 分），满足 $n\le 2000$。

子任务 $5$（$20$ 分），无特殊限制。

对于所有数据，满足 $2\le n\le 10^5$，$d\times n\le 2\times 10^5$。

#### 提示

附件下发了本题 checker。


title: 「UOI-R1」磁铁

description:
有两串磁铁 $a,b$，均可以看作由一些小写或大写字符或数字组成的。

你可以对磁铁 $a$ 进行**无限次**操作，每次操作可以是以下两个中的一个：

1. 将前若干个字符删除，例如删除 $\texttt{91987}$ 的前 $3$ 个字符后字符串将会变成 $\texttt{87}$。
2. 将后若干个字符移至前面去，例如将 $\texttt{91987}$ 的后 $3$ 个字符移至前面去后字符串会变成 $\texttt{98791}$。

问经过操作后，能否使磁铁 $a$ 和 $b$ 相等，$a$ 和 $b$ 相等当且仅当 $a$ 和 $b$ 长度相等且每个字符都相同。

为了防止 ````不可以，总司令```` 的情况发生，你需要回答多次。

inputFormat:
第一行，数据组数 $t$。

接下来 $t$ 组数据，每组两行字符串，表示磁铁串 $a, b$。

outputFormat: 输出 $t$ 行，每行输出 `Y` 或 `N` 表示操作后可以或不可以使得 $a$ 和 $b$ 相等。

samples:
见文件附件的 magnets4.in
见文件附件的 magnets4.ans


title: [语言月赛202212] 计算

description:
给定一个 $3$ 位整数 $n$，计算：
1. $n$ 的各位数字之和；
2. $n$ 的各位数字之和的平方；
3. $n$ 的各位数字之和的立方；

例如，当这个三位数是 $123$ 时：

1. 各位数字之和为：$1+2+3=6$；
2. 各位数字之和的平方为：$(1+2+3)^2=(1+2+3)\times (1+2+3)=36$；
3. 各位数字之和的立方为：$(1+2+3)^3=(1+2+3)\times (1+2+3)\times (1+2+3)=216$。

inputFormat: 输入只有一行一个三位整数 $n$。

outputFormat: 输出共**三行**，第一行为各位数字之和，第二行为各位数字之和的平方，第三行为各位数字之和的立方。

hint:
### 样例 1 解释

各位数字之和为：$8+1+7=16$；
各位数字之和的平方为：$16^2=16\times 16 = 256$；
各位数字之和的立方为：$16^3 =16\times 16\times 16 = 4096$。

### 数据规模与约定

对于全部的测试点，保证 $100 \leq n \leq 999$。


title: 「TERRA-OI R1」你不是神，但你的灵魂依然是我的盛宴

background: 踏在这木质的平台上，嘎吱嘎吱作响，你从包里掏出了各式各样的药水，逐一饮下后一股暖意从心底升腾起来，你拿出了精心准备的诱饵，那是用三位仆从的精华凝聚而成，你将其高举头顶，想要引出那位噬神者。天空开始弥漫着蓝紫色的迷雾，这种氛围压得你喘不过气，恍惚间，你面前的空间开始撕裂出一条裂缝，一条身披紫色外壳的巨蟒从中钻出，你拿起了手上的巨剑，听着一声又一声的嘶吼，你知道这将是一场恶战......

description:
请求出：

$\sum_{i=1}^{n} \sum_{j=1}^{m}(i\times j \bmod p)$

的值，其中 $n,m,p$ 为给定的值。

inputFormat: 一行三个用空格分隔的正整数 $n,m,p$，含义见题目描述。

outputFormat: 一行一个整数表示答案，由于这个结果可能很大，请输出其对 $10^9+7$ 取模的结果。


title: 「TERRA-OI R1」别得意，小子

background: 战至中途，蓝紫色天空瞬间变为黑压压一片，噬神者身上一些紫色外壳开始脱落，化为更小的蟒蛇，这些小家伙从出现开始便不要命的向你冲过来，刚清理掉这些小家伙，迷雾中忽然涌现出一张血盆大口，噬神者正向你冲击而来......

description: 现给定一个有 $n$ 段的分段函数，每一段可能是一个一次函数或者一个二次函数，并有 $q$ 次询问，每次询问 $x=k$ 时 $y$ 的取值或是 $y=k$ 与函数有多少个交点。

inputFormat:
第一行两个用空格分隔的整数 $n,q$，表示函数段数与询问次数。

从第 $2$ 行到 $n+1$ 行，先给出 $l_i$ $r_i$，表示这个分段函数对应的取值范围为 $(l_i,r_i]$（保证 $l_1=0$，$\forall i\in [1,n-1],r_i=l_{i+1}$）。然后读入有以下两种情况：

- $1$ $k$ $b$，表示这个区间内是 $y=kx+b$ 的一个一次函数（保证 $k\ne 0$）。
- $2$ $a$ $b$ $c$，表示这个区间内是 $y=ax^2+bx+c$ 的二次函数（保证 $a\ne 0$）。

从第 $n+2$ 行到第 $n+q+1$ 行，每行两个用空格分隔的整数 $op,k$：

- 若 $op=1$ ，表示求出当 $x=k$ 时 $y$ 的值（保证 $k\in (0,r_n]$）。
- 若 $op=2$ ，表示求出直线 $y=k$ 在 $(0,r_n]$ 范围内与整个分段函数有几个交点。

outputFormat: 一共 $q$ 行，每行一个整数表示对于每个询问的答案。

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

三段函数分别为 $y=x+2$，$y=x^2-2x+1$，$y=x$。

对于当 $x=4$ 时套入第二段函数可以得到结果为 $9$。

而直线 $y=5$ 只与第一段与第二段函数相交，并且各只有一个交点，所以结果为 $2$。

显而易见，第三个询问对应的直线不与函数相交。

第四个询问虽然与第一段函数交于 $x=0$ 的位置，但 $0$ 不在该函数区间内，故舍去。

------------

#### 【数据范围】

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

| Subtask | Score | $n,q\le$ | limit |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10$ | $100$ | 无 |
| $2$ | $15$ | $10^3$ | $r_n\le 5\times 10^3$ |
| $3$ | $20$ | $2\times 10^5$ | 不存在询问 $2$ |
| $4$ | $25$ | $2\times 10^5$ | 不存在二次函数 |
| $5$ | $30$ | $2\times 10^5$ | 无 |

对于 $100\%$ 的数据，$1\le n,q\le 2\times 10^5$，$0\le l_i,r_i\le10^9$，$\forall i\in [1,n],r_i>l_i$ 。

所有的函数系数均在 **$64$ 位有符号整型变量**存储范围内，并且运算结果与每个函数式中任何一项的最大值与最小值不会超过 **$64$ 位有符号整型变量**存储范围。所有询问参数均在 **$32$ 位有符号整型变量**范围内。

（即 $-4\times 10^{18}\le k,a,b,c\le 4\times 10^{18}$，$-10^9\le x\le 10^9$）

------------
#### 【提示】

采用浮点数据时建议使用 long double，避免产生精度问题。

upd：添加一组 hack 数据，未通过会显示为“Unaccepted 100pts”。


title: [语言月赛202212] 数字口袋

description:
小 A 有一个口袋，里面可以装整数。他从 $1$ 开始，按从小到大的顺序，依次将每个整数装入口袋。

但是口袋是有限的，大小为 $n$，这就是说，口袋里所有的数字的和不能够超过 $n$。

inputFormat: 输入只有一行一个整数，表示整数 $n$。

outputFormat: 输出若干行，每行一个整数，按从小到大的顺序输出口袋里的数字。


title: [JRKSJ R7] TSM eerT

description:
对于一个 $n$ 个结点的带边权的树 $T$，定义 $dis(x,y)$ 为 $T$ 中 $x\to y$ 路径上的边权和。再定义一个 $n$ 个结点的无向完全图 $p(T)=G$，其中 $\forall x,y\in [1,n]$，$G$ 中边 $(x,y)$ 的边权为 $dis(x,y)$。

定义 $f(T)$ 为 $p(T)$ 的最大生成树。特别的，若 $p(T)$ 的最大生成树不唯一，请立刻判断出并报告。

给定树 $T_0$ 和整数 $k$，求 $f^k(T_0)$。其定义将在下文给出。

inputFormat:
第一行两个整数 $n,k$。\
下面第 $2\sim n$ 行，第 $i$ 行两个整数 $i-f_i,v_i$ 表示 $T_0$ 的一条边 $(i,f_i)$，边权为 $v_i$。**也就是说，这一行输入了两个整数 $f'_i,v_i$，真实的 $f_i=i-f'_i$。**

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

若 $\exists x\in[0,k-1]$ 使得 $p(f^x(T_0))$ 的最大生成树不唯一，输出 $-1$。否则，输出 $f^k(T_0)$ 的所有边权和对 $2^{32}$ 取模的结果。


title: [语言月赛202212]  洛谷三角洲

description:
在平行的洛谷世界，有 A，B，C 三座城市，它们构成了洛谷三角洲。

两两城市之间各有一条双向道路。也就是说，一共有三条道路，A 市与 B 市之间有一条道路，A 市与 C 市之间有一条道路，B 市与 C 市之间有一条道路。

由于每条道路的拥堵程度不同，因此通过一条路需要的时间也不同。对于每一条路，双向的拥挤程度相同（即经过 A 市与 B 市之间的一条道路，由 A 市到 B 市和由 B 市到 A 市所需的时间相同）。

通过 A 市与 B 市之间的道路需要 $x$ 分钟，通过 B 市与 C 市之间的道路需要 $y$ 分钟，通过 C 市与 A 市之间的道路需要 $z$ 分钟。

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

由于业务需要，洛谷站长需要在三个市之间频繁往返。如果能够知道任意两个市之间通行的最短时间，那么他能够极大地提高工作效率。

所以他现在想知道：从 A 市到 B 市，从 B 市到 C 市，从 A 市到 C 市分别**至少**需要多少时间（单位：分钟）。但是他认为这个问题太难了，所以他把这个问题交给了聪明的你。

inputFormat: 输入共一行，共三个整数，分别表示 $x,y,z$。

outputFormat:
输出共三行：
第一行为从 A 市到 B 市至少需要的时间。
第二行为从 B 市到 C 市至少需要的时间。
第三行为从 A 市到 C 市至少需要的时间。

hint:
### 样例 1 解释

从 A 市到 B 市需要 $1$ 分钟，从 B 市到 C 市需要 $2$ 分钟。
从 A 市到 C 市可以先从 A 市到 B 市，再从 B 市到 C 市，这样只需要花费 $1+2=3$ 分钟。

### 数据规模与约定

- 对于 $20\%$ 的数据，满足 $x=y=z$；
- 对于另外 $20\%$ 的数据，满足 $x+y\ge z$，$x+z\ge y$，$y+z\ge x$；
- 对于 $100\%$ 的数据，满足 $1 \leq x,y,z\le 10^9$。


title: 「GMOI R1-T1」Perfect Math Class

description:
Index 给了你一个函数如下：

$$f(x)=a_kx^k+a_{k-1}x^{k-1}+\cdots+a_1x^1+a_0$$

画出它的函数图像（`*` 表示经过该点，`.` 表示不经过该点），大小为 $n\times m$，其中 $x$ 的范围是 $[0,n-1]$，$f(x)$ 的范围是 $[0,m-1]$。

具体的，你需要输出一个 $n\times m$ 的字符矩阵，若该函数经过整点 $(x,y)$，则**从左往右**第 $x+1$ 列，**从下往上**第 $y+1$ 行输出 `*`，否则为 `.`。

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

第二行 $k+1$ 个整数，其中第 $i$ 个整数表示 $a_{i-1}$。

outputFormat: 输出共 $m$ 行，每行 $n$ 个字符，即输出该函数的函数图像。具体的，仅当函数经过 $(x,y)$ 时，**从左往右**第 $x+1$ 列，**从下往上**第 $y+1$ 行输出 `*`，否则为 `.`。


title: [语言月赛202301] Hello, 2023

background:
Goodbye, 2022

Hello, 2023

description:
某 E 在 2022 年的幸运数字是 $x$，这个数可能是正的，也可能是负的。

某 E 想要知道 $x \bmod 2023$ 的值。其中，$\bmod$ 是取模操作。也就是说，你需要求出 $x$ 除以 $2023$ 的余数，**这个余数必须是非负整数**。

例如，$2022 \bmod 2023 = 2022$，$2025 \bmod 2023 = 2$，$-2 \bmod 2023 = 2021$，$-2026 \bmod 2023 = 2020$。

具体来说，$x = k \times 2023 + r$，其中 $0 \le r < 2023$，$k,r$ 都是整数。你需要求出这个 $r$。

**请注意：如果你使用 C/C++ 语言中的取模运算符（$\texttt{\%}$）对负数取模，你将会得到一个负数作为结果。在这个负数结果上加上模数，得到的才是正确的取模结果。**

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

outputFormat: 输出 $x \bmod 2023$ 的值。


title: [语言月赛 202212] 宇宙密码

description:
经历十九年的探索，人们终于找到了宇宙中的那份瑰宝。

这份瑰宝被装在一个密码箱里，按照情报，密码应为一串长度为 $n$ 的数字 $a$。

人们满怀希望地输入了密码，但是密码箱没有任何反应。

这时人们意识到，在十九年中，由于宇宙射线的侵蚀，密码箱的密码发生了改变。

现在人们知道，能够打开密码箱的新密码是由原密码 $a$ 变化而来。具体的，新密码相比原密码变化了 $t$ 位数字，其中 $t$ 满足 $0 \leq t \leq k$，且对于变化的数字位，变化后的数字是在该位置原数字的基础上增加或减小 $1$ 得到的数字。特别的，如果原数字是 $0$，在原数字基础上减少 $1$ 得到的数字是 $9$；如果原数字是 $9$，在原数字基础上增加 $1$ 得到的数字是 $0$。

现在人们知道了 $n, a, k$，想知道经过宇宙射线侵蚀后，所有可能打开密码箱的密码。

人类将重任交到了你身上，请你帮助人类解决这个问题。你需要由小到大输出所有可能的密码，每个一行。

特别的，有一些密码可能存在前导 $0$。为了方便操作，这时你**不必也不应**将这些前导 $0$ 一并输出。

人类感谢你。

inputFormat: 输入只有一行三个整数，依次代表原密码位数 $n$，去掉前导零后的原密码 $a$，和变化位数的最大值 $k$。

outputFormat: 输出若干行，每一行包含一个整数，代表由小到大的所有可能的密码。

hint:
### 样例 1 解释

原密码为 $014$，允许至多 $1$ 位有变化。

所有密码情况如下：

| 变化位数和位置 | 可能的结果 |
| :-: | :-: |
| $0$ 位 | $014$ |
| $1$ 位，从左向右第 $1$ 位 | $114, 914$ |
| $1$ 位，从左向右第 $2$ 位 | $024, 004$ |
| $1$ 位，从左向右第 $3$ 位 | $013, 015$ |

共 $7$ 个可能的密码，按从小到大排序输出即可。

### 数据规模与约定

- 对于前 $10\%$ 的数据，保证 $n = k = 1$。
- 对于前 $40\%$ 的数据，保证 $k \leq 1$。
- 对于另外 $10\%$ 的数据，保证 $k = n$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 6$，$0 \leq a < 10 ^ n$，$0 \leq k \leq n$，保证输入数据无前导 $0$。

请注意，输出数据中**不应**存在前导 $0$。


title: [语言月赛202212] 盒武器

description:
Aya 在网校共有两名助教，她们的网名分别为某 E 和 L 队。

Aya 热衷于开盒。他对两名助教使用了盒武器，得知某 E 的真实姓名为一个字符串 $s$，L 队的真实姓名为一个字符串 $t$。两个人的名字均只包含英文小写字母。

Aya 确信实力和姓名的字典序有关，姓名字典序越靠前，实力越强。

但是事实上，L 队的实力严格强于某 E。所以，你需要重新确定 $26$ 个英文小写字母的大小顺序，以保证 Aya 得到的结果与事实相符。

也就是说，请你重新定义 $26$ 个字母之间的大小关系，使得按照你新定义的大小关系比较 $s,t$ 两字符串的字典序时，满足 $t < s$。

字符串 $t$ 的字典序小于 $s$ 的字典序当且仅当满足如下两个条件之一：
1. $t$ 是 $s$ 的一个前缀；
2. 存在一个位置 $j \leq \min(|s|, |t|)$，使得对 $1 \leq i < j$ 都有 $s_i = t_i$ 且 $t_j < s_j$。其中两字符相比较的小于号是你重新定义的小于关系。

inputFormat:
输入的第一行为一个字符串 $s$。
输入的第二行为一个字符串 $t$。

outputFormat:
输出一行一个字符串，长度为 $26$，$\texttt{a} \sim \texttt {z}$ 这些字符在你的输出中均应恰好出现一次，以表示字母之间新定义的大小关系。

在输出中靠前位置的字母小于在输出中靠后位置的字母。

答案可能有多种，你只需要给出任意一组。

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

- 对于 $30\%$ 的数据，$|s|=|t|=1$；
- 对于 $60\%$ 的数据，$|s|=|t|$；
- 对于 $100\%$ 的数据，$1 \le |s|,|t| \le 10^6$，且 $s \neq t$。

数据保证存在一种方式，使得字典序上 $t<s$。


title: [DMOI-R2] 暗号

background:
> 有太多人太多事 夹在我们之间咆哮
> 杂讯太多讯号弱 就连风吹都要干扰
> 可是你不想 一直走在黑暗地下道
> 想吹风想自由 想要一起手牵手 去看海绕世界流浪
> ——《[暗号](https://www.bilibili.com/video/BV1p24y1f7zM)》

书接上回，每个军队都拿到了补给。但是要上战场，准备还不是很充分。JF 只有军队组成了一个集团军。才有可能形成一股强大的战斗力，才可以在军阀混战中取得胜利。

description:
已知 JF 有 $n$ 支军队，他们分别由 $n-1$ 条边连接。$1$ 号军队为根。每支军队有自己的或黑或白的 **“暗号”**，方便相互联系，以及他的战力值和士气值。**初始的时候，军队的士气值等于战力值**。我们从深度最深的军队开始改变士气值，对于当前的军队 $u$ 来说，在与他直接相连的军队且深度比 $u$ 深的军队中，如果有军队 $v$ 和他的暗号相同，$u$ 就可以联系上 $v$，然后 $u$ 的士气值 **就必须全部加上**  $v$ 的子树内和 $v$ 颜色相同的点的战力值。（可以理解为，在 $u$ 的士气更新完毕时，$u$ 的子树的士气也更新完毕了。）

现在，你可以任意修改这些军队的暗号。要你求出所有**军队士气值的和的最大值**是多少。

inputFormat:
第一行一个整数 $n$，如题所示。

第二行至第 $n$ 行每行有两个数，表示 $u$ 和 $v$ 之间有连边。

第 $n+1$ 行有 $n$ 个数，第 $i$ 个数表示第 $i$ 支军队一开始的战力值 $w_i$。

outputFormat: 一行一个整数，表示士气值之和的最大值。


title: [语言月赛202212] 打 ACM 最快乐的就是滚榜读队名了(Easy Version)

background:
**本题与 [I2](https://www.luogu.com.cn/problem/P8890) 的题意完全一致，区别仅在 $m$ 和 $K$ 的范围**。

在刚刚结束的 ICPC 杭州赛站上，某 E 经历了刺激的滚榜。她发现打 ACM 最快乐的就是滚榜读队名了。

description:
一场 ICPC 正式赛共 $5$ 小时。

队伍的排名由通过题数与罚时决定。通过题数更多的队伍排名更靠前，若通过题数相同，则罚时更小的队伍排名更靠前。通过题数与罚时均相同的队伍排名相同。本题中可能出现队伍排名相同的情况，此时，认为先出现在提交记录中的队伍排名靠前。

罚时是由通过题目的时间和未通过提交的次数决定的。罚时为每一道题通过时比赛开始的分钟数之和，加上该题之前未通过提交的次数乘 $20$ 分钟得到的。例如，某队在比赛进行 $1:28:35$ 时通过了 G 题，在此之前共有 $3$ 次未通过的提交，则 G 题对罚时的总贡献为 $88+3 \times 20=148$ 分钟。

**需要注意的是，仅有通过的试题的未通过提交会被计算罚时**。例如，某队在 I 题共有 $14$ 次未通过的提交，但到比赛结束，该队都没有通过 I 题，则这 $14$ 次未通过的提交不会被计算罚时。**在某一题通过后，该队对这一题的任何提交（无论是否能够通过）都不会影响本题通过的结果和本题的罚时。**

选手在比赛过程中可以随时提交某一道试题的代码，代码将被立即评测并返回结果（$\texttt{Accepted}$，$\texttt{Time Limit Exceeded}$，$\texttt{Memory Limit Exceeded}$，$\texttt{Presentation Error}$，$\texttt{Wrong Answer}$，$\texttt{Runtime Error}$）。其中，评测结果 $\texttt{Accepted}$ 为通过，其他评测结果均为不通过。

在比赛进行的前四小时（$0:00:00 \sim 4:00:00$），每支队伍的提交均会在排行榜上反映出来。比赛的最后一小时（$4:00:01 \sim 5:00:00$），排行榜将被冻结（封榜），所有的提交在排行榜对应队伍对应试题上均显示为待判题（提交的队伍知道评测结果）。

在比赛结束后，会进行紧张刺激的滚榜环节。滚榜嘉宾将按照封榜时的排行榜，依照从最后一名到第一名，**先读出队伍队名**，再按照从 A 题依次到最后一题的顺序，公布排行榜上该队“待判题”状态试题最终是否通过。

如果通过，所有队伍的排名将立即重新计算，显然，已经滚榜完成（被滚榜嘉宾念过队名，且所有待判题状态的结果都已经揭晓）的队伍排名不会有影响。若该队伍排名上升，则滚榜嘉宾立即开始下一支队伍的滚榜。因此，一支队伍的队名可能被滚榜嘉宾多次读出。

例如，某队队名为“囤题”，在前四小时没有通过任何一题，封榜时排在最后一名。在封榜后，该队连续通过全部十三道题目。那么滚榜嘉宾有可能读到该队队名七八次。当然，当该队上升到第一名后，其排名不会再发生变化，即使揭晓的判题结果为通过，但其排名没有发生变化，滚榜嘉宾不会再次读出其队名。

现在给出某场 ICPC 完整的提交记录，请你依次输出滚榜嘉宾念出的队名。

**一次提交记录都没有的队伍不会在排行榜上出现，也不会在滚榜中被念到队名。**

inputFormat:
输入的第一行为三个整数 $n,m,K$，依次为该场 ICPC 试题数、该场 ICPC 队伍数、该场 ICPC 提交记录数。

接下来 $K$ 行，每行为四个空格分隔的字符串，表达一条提交记录。第一个形如 $x:yy:zz$，代表该记录在比赛开始 $x$ 小时 $yy$ 分钟 $zz$ 秒时提交。第二个字符串为一个大写英文字母，代表试题的编号（$\texttt{A,B,} \cdots$）。第三个字符串为队名，保证队名不含空格。第四个字符串（可能含有空格，但为仅出现「题目描述」中的六种评测结果）为该评测记录的评测结果，具体字符串的含义见试题描述部分。

outputFormat: 输出若干行，为该滚榜嘉宾依次读到的队名。

samples:
2 2 4
0:00:01 A abc Wrong Answer
0:00:02 A abc Accepted
0:19:38 A bcd Accepted
4:18:22 B abc Accepted

hint:
### 样例解释

在封榜前，队伍 $\texttt{abc}$ 仅通过 $\texttt{A}$ 题，且在第二秒的第一次正确提交之前有一次错误提交，因此罚时为 $20$ 分钟；队伍 $\texttt{bcd}$ 同样仅通过 $\texttt{A}$ 题，且在 $0:19:38$ 的第一次正确提交之前没有错误提交，因此罚时为 $19$ 分钟。

在封榜后，队伍 $\texttt{abc}$ 通过了 $\texttt{B}$ 题。

在滚榜环节开始，由于封榜后的提交未被揭晓，因此暂时认为队伍 $\texttt{abc}$ 与 $\texttt{bcd}$ 均只通过一题，且前者罚时较大，排名靠后。

依照从最后一名到第一名的原则，队伍 $\texttt{abc}$ 的名字先被念到，并揭晓其在封榜后的提交的结果。其通过了 $\texttt{B}$ 题，因此其通过题数被更新为 $2$，罚时同样被更新。同时，所有队伍的排名立即被重新计算。由于此时 $\texttt{abc}$ 通过题目数量大于 $\texttt{bcd}$，因此其排名重新计算为第一名，而 $\texttt{bcd}$ 成为最后一名第二名。

这之后，队伍 $\texttt{bcd}$ 的名字被念到，由于其在封榜后没有提交，因此这时所有队伍的排名没有变化，滚榜嘉宾会进行其上一名队伍的滚榜。

最后，队伍 $\texttt{abc}$ 的名字被念到，滚榜结束。

需要注意的是，在滚榜过程中是逐题揭晓提交。也就是说，如果一支队伍封榜后通过了多道题，在其进行滚榜过程中，只要按照从 $\texttt{A}$ 题依次到最后一题的顺序，该队第一个“待判题”状态试题通过，后面的“待判题”同样暂时不会揭晓，而是立刻进行排名更新过程以及可能存在的更换另一支队伍进行滚榜的过程。

### 数据规模与约定

- 对于 $30\%$ 的数据，$n = 1$；
- 对于另外 $10\%$ 的数据，$m = 1$；
- 对于 $100\%$ 的数据，$1 \le n \le 20$，$1 \le m \le 1000$，$1 \le K \le 10^4$，$0 \leq x \leq 5$，$00 \leq yy < 60$，$00 \leq zz < 60$，且当 $x = 5$ 时保证 $yy = zz = 00$。

保证提交记录按照提交时间不降序给出，即先给出的提交记录提交时间不会晚于后给出的提交记录的提交时间，试题名称为大写字母 $\texttt{A} \sim \texttt{Z}$，队名均为长度不超过 $50$ 的由小写字母组成的字符串，评测状态为试题中所给的 $6$ 种之一。


title: [DTOI 2023] C. 不见故人

background: 虽然 luanmenglei 已经是成熟的高中生了，但每次提起 luanmenglei 八年级的女朋友时，luanmenglei 都会沉浸在美好的回忆中，不可自拔。

description:
给定 $n, k$ 和序列 $\{a_n\}$，你同时有一个临时变量 $x$，你可以进行以下操作若干次（也可以是 $0$ 次），一次操作的流程是：
1. 选定一个区间 $[l,r]$，$\forall i\in[l,r]$，$x\leftarrow \gcd(a_l,a_{l+1},\cdots,a_r)$。
2. $\forall i\in[l,r]$，$a_i\leftarrow x$。

简而言之，你每次可以选定一个区间并将其中每个数变成这个区间的 $\gcd$。

一次操作的代价是 $r-l+1+k$，现在你希望把这个序列的每个数都变成相等的，求最小代价和。

----
如果您不了解 $\gcd$ 或者多元 $\gcd$ 的含义，可以参照如下定义：
- $\gcd(a_1,a_2,\dots, a_k)$ 表示 $a_1,a_2,\dots, a_k$ 的最大公约数，即最大的能同时整除 $a_1,a_2,\dots, a_k$ 的正整数。

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

第二行 $n$ 个数，表示 $\{a_n\}$。

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

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

操作一次，选择区间 $[1,10]$。

#### 【样例 4】

见附加文件中的 `old/old4.in` 与 `old/old4.out`。

该样例满足测试点 $9\sim 12$ 的限制。

#### 【样例 5】

见附加文件中的 `old/old5.in` 与 `old/old5.out`。

该样例满足测试点 $13\sim 16$ 的限制。

#### 【数据范围与提示】

对于所有数据，保证 $1\leq n\leq 4\times 10^6$，$0\leq k\leq 10^9$，$1\leq a_i\leq 10^9$。

每个测试点的具体限制见下表：

| 测试点编号 | $n\leq$ | $k,a_i\leq$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10^6$ | $10^9$ | 所有数都相等 |
| $2\sim 4$ | $4$ | $10^9$ | 无 |
| $5\sim 8$ | $100$ | $10^9$ | 无 |
| $9\sim 12$ | $1000$ | $10^9$ | 无 |
| $13\sim 16$ | $10^6$ | $10^9$ | 无 |
| $17\sim 20$ | $4\times 10^6$ | $10^9$ | 无 |

本题的读入量较大，请选择较快的读入方式，下面提供一种读入策略：

请在代码的开头加入此行：`std::ios::sync_with_stdio(false);std::cin.tie(0);`。

请注意，加入本行后 `cin/cout` 的效率将大幅提高，保证其能在 `250 ms` 内读入所有数据，**但使用后你仅能使用 `cin/cout` 流读入数据。**


title: [DTOI 2023] D. Goodbye 2022

background: > 我用烟花宣告，用挥手告别，用鞠躬感谢，过去的都已经过去，接下来的路我要悠闲地走，愉悦地走，脚步如同时间不会停止，下一年，我们还会再会。

description:
这次的题目背景和 luanmenglei 没有一点关系。

给定 $n,k,p$，求有多少有序 $p$ 元组 $(a_1,a_2,\cdots,a_p)$ 满足

- $\forall i \in [1,p]$，$a_i\in [1,n]$。

- $\forall i\in [1,p)$，$\operatorname{popcount}(a_i\oplus a_{i+1})=k$。

- $\forall i,j\in[1,p],i\neq j$，$a_i\neq a_j$。

答案对 $998244353$ 取模。

---

- 其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制表达下 $1$ 的个数。
- $\oplus$ 表示按位异或操作。
- 两个有序 $p$ 元组 $(a_1,a_2,\dots,a_p)$，$(b_1,b_2,\dots,b_p)$ 不同当且仅当存在 $i\in[1,p]$ 使得 $a_i\neq b_i$。

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


title: 虚人「无」

background:
一点也不美丽的不死鸟。

那双锐爪，沾染了无辜的鲜血。

description:
给定二元序列 $\{(v_i,c_i)\}$ 和一棵以 $1$ 为根的有根树。第 $i$ 个点的点权是 $(v_i,c_i)$。

- 定义一个非根节点的权值为其子树内的 $c$ 的积乘上其子树补的 $v$ 的积。
- 定义一个根节点的权值为其子树内的 $c$ 的积。

形式化的讲，若 $u$ 不为根节点，则 $u$ 的权值 $f_u$ 为：

$$f_u=\prod\limits_{v\in \operatorname{substree}(u)} c_v\times \prod\limits_{v\notin \operatorname{substree}(u)} v_v$$

否则，其权值 $f_u$ 为：

$$f_u=\prod\limits_{v=1}^n c_v$$

试求整棵树**所有节点的权值之和**，答案对 $m$ 取模。请注意：**保证 $\bm m$ 是质数**。

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

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

接下来一行 $n$ 个数，表示 $c_{1, 2, \dots, n}$。

接下来一行 $n$ 个数，表示 $v_{1, 2, \dots, n}$。

outputFormat: 输出一个数，表示答案对 $m$ 取模后的结果。

hint:
### 样例解释

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

（图片有误，应该交换 $v,c$ 的权值。）

### 数据范围及约定

对于 $100\%$ 的数据，满足 $1\le n\leq 3\times 10^5$，$1\leq v_i,c_i,m\leq 10^9$。


title: [入门赛 #7] 打 ACM 最快乐的就是滚榜读队名了 (Hard Version)

background:
**本题的题意与 [I1](https://www.luogu.com.cn/problem/B3692) 完全相同，区别仅在 $m$ 和 $K$ 的范围。**

在刚刚结束的 ICPC 杭州赛站上，某 E 经历了刺激的滚榜。她发现打 ACM 最快乐的就是滚榜读队名了。

outputFormat: 输出若干行，为该滚榜嘉宾依次读到的队名。

hint:
### 样例解释

在封榜前，队伍 $\texttt{abc}$ 仅通过 $\texttt{A}$ 题，且在第二秒的第一次正确提交之前有一次错误提交，因此罚时为 $20$ 分钟；队伍 $\texttt{bcd}$ 同样仅通过 $\texttt{A}$ 题，且在 $0:19:38$ 的第一次正确提交之前没有错误提交，因此罚时为 $19$ 分钟。

在封榜后，队伍 $\texttt{abc}$ 通过了 $\texttt{B}$ 题。

在滚榜环节开始，由于封榜后的提交未被揭晓，因此暂时认为队伍 $\texttt{abc}$ 与 $\texttt{bcd}$ 均只通过一题，且前者罚时较大，排名靠后。

依照从最后一名到第一名的原则，队伍 $\texttt{abc}$ 的名字先被念到，并揭晓其在封榜后的提交的结果。其通过了 $\texttt{B}$ 题，因此其通过题数被更新为 $2$，罚时同样被更新。同时，所有队伍的排名立即被重新计算。由于此时 $\texttt{abc}$ 通过题目数量大于 $\texttt{bcd}$，因此其排名重新计算为第一名，而 $\texttt{bcd}$ 成为最后一名第二名。

这之后，队伍 $\texttt{bcd}$ 的名字被念到，由于其在封榜后没有提交，因此这时所有队伍的排名没有变化，滚榜嘉宾会进行其上一名队伍的滚榜。

最后，队伍 $\texttt{abc}$ 的名字被念到，滚榜结束。

需要注意的是，在滚榜过程中是逐题揭晓提交。也就是说，如果一支队伍封榜后通过了多道题，在其进行滚榜过程中，只要按照从 $\texttt{A}$ 题依次到最后一题的顺序，该队第一个“待判题”状态试题通过，后面的“待判题”同样暂时不会揭晓，而是立刻进行排名更新过程以及可能存在的更换另一支队伍进行滚榜的过程。

### 数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 20$，$1 \le m \le 2 \times 10^5$，$1 \le K \le 2 \times 10^6$，$0 \leq x \leq 5$，$00 \leq yy < 60$，$00 \leq zz < 60$，且当 $x = 5$ 时保证 $yy = zz = 00$。

保证提交记录按照提交时间不降序给出，即先给出的提交记录提交时间不会晚于后给出的提交记录的提交时间，试题名称为大写字母 $\texttt{A} \sim \texttt{Z}$，队名均为长度不超过 $50$ 的由小写字母组成的字符串，评测状态为试题中所给的 $6$ 种之一。


title: 「DBOI」Round 1 人生如树

background:
> _永远这么酷 永远永远这么酷_\
_像个冒险家一样 不断探着山顶的路_\
——《Hustle》

张均好望着窗外，朱芝心走过来坐在他旁边，折了一架纸飞机飞出去。他对张均好说，要带着对未来的期待，往前走，别回头。

正如 [命运](https://www.luogu.com.cn/problem/P6773) 所述，每个人的人生都是一棵树。它总在无限的随机与缘分中伸展，有的枝丫茂盛了，有些却也不可避免地枯萎。

description:
朱芝心用魔法得到了张均好的人生树。

这是一棵 $n$ 个节点的树，节点 $i$ 上有权值 $w_i$。

朱芝心想要观测 $m$ 次张均好的人生：

设**当前**张均好人生树上的节点数量为 $s$。

1. 输入四个整数 $u_1,v_1,u_2,v_2$。令 $u_1\to v_1$ 的简单路径上**顺次组成**的数组为 $a$，$u_2\to v_2$ 的简单路径上**顺次组成**的数组为 $b$。朱芝心认为张均好这两段人生的相似度是 $LRP(a,b)$，希望你求出它。保证 $1\leq u_1,v_1,u_2,v_2 \leq s$。

2. 输入两个整数 $u,w'$。朱芝心观测到了张均好的另外一种可能，因此你需要新建一个点权为 $w'$ 的节点，编号为 $s+1$，建立一条 $(s+1,u)$ 的无向边，其中 $u\leq s$。显然，此后 $s\leftarrow s+1$。

对于两个数组 $a,b$，设它们的相似度 $LRP(a,b)$ 表示最大的 $i$ 满足 $i\leq \min\{|a|, |b|\}$ 且**对于所有** $1\leq j\leq i$，都有 $b_j=a_j+j$。其中 $|a|$ 表示数组 $a$ 的长度。特殊地，若不存在这样的 $i$，则 $LRP(a,b) = 0$。

inputFormat:
第一行三个正整数 $n,m,idx$，分别表示树的节点数量，操作数量和该测试点所在 Subtask 编号。对于样例，有 $idx = 0$。

接下来一行 $n$ 个整数，第 $i$ 个整数表示 $w_i$，即点 $i$ 上的权值。

接下来 $n - 1$ 行，每行两个正整数 $u_i,v_i$，表示有一条 $(u_i,v_i)$ 的无向边。

接下来 $m$ 行，每行一个操作。每行第一个整数是 $opt$，后面的若干整数表示操作的具体内容。$opt=1$ 时表示是操作 $1$，$opt=2$ 时表示是操作 $2$。

outputFormat: 对于每个操作 $1$，输出一行，表示当前询问的 $LRP(a, b)$。


title: [DTOI 2023] A. 小狗哥哥

background:
luanmenglei 有一个辉煌的现在：他们班的女同学都叫他易酱。

但谁能想到 luanmenglei 有一个悲伤的过去，他五岁的弟弟叫他小狗哥哥。

description:
下文的所有参数均默认为整数。

作为一位（7k7k 小游戏的）游戏开发者，你设计了如下（简陋的不如小狗哥哥幼儿园大班的毕业设计的）游戏，存在两个要素：
1. 一个敌对生物，其血量为 $m$。
2. 主角的武器，分为 $n$ 级，第 $i$ 级的伤害是 $i\times p$。

游戏的平衡性需要提前规划，所以你还有一个序列 $\{a_n\}$，其含义如下：

- $a_i$ 表示敌对生物被第 $i$ 级武器恰好攻击 $a_i$ 下会死。

可惜你忘记了 $p$ 具体是多少，所以你需要求出所有可能的 $p$ 的个数。

如果可能有无数个 $p$，那么请输出 `xiaogougege`。

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

第二行 $n$ 个正整数，表示序列 $\{a_n\}$。

outputFormat: 一行一个整数，表示可能的 $p$ 的个数，或字符串 `xiaogougege`，其具体含义见题目描述。

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

当武器为 $1$ 级时，分析可以发现 $p$ 要满足 $1 \leq p < \frac{3}{2}$。
当武器为 $2$ 级时，分析可以发现 $p$ 要满足 $\frac{3}{4} \leq p < \frac{3}{2}$。
当武器为 $3$ 级时，分析可以发现 $p$ 要满足 $1 \leq p$。

又 $p$ 是整数。综上，只有当 $p = 1$ 时满足题目所述条件。

#### 【样例 2】

见附加文件中的 `game/game2.in` 与 `game/game2.out`。

该样例满足测试点 $13\sim 20$ 的限制。

#### 【数据范围与提示】

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

每个测试点的具体限制见下表：

|  测试点编号  |      $n\leq$ | $m,a_i\leq $ | 特殊性质 |
| :-: | :-: |:-:|:-:|
| $1\sim 9$ | $10^5$ | $10^9$ | 数据纯随机 |
|  $10 \sim 12$  |       $3$       |$5$| 无 |
| $13 \sim 20$ | $10^5$ |$10^9$| 无 |

你需要注意，上文纯随机数据的具体生成程序代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, m, w;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  assert(l <= r);
  return uniform_int_distribution<>(l, r)(rng);
}

int main() {
  scanf("%d%d%d", &n, &m, &w);
  printf("%d %d\n", n, m);
  for (int i = 1; i <= n; i ++) printf("%d%c", rand(1, w), " \n"[i == n]);
  return 0;
}
```

通俗的说，就是对于给定的 $n,m,w(w\le 10^9)$，数据生成器会随机生成 $n$ 个值域在 $[1,w]$ 内的数，作为 $\{a_n\}$。


title: 「LAOI-1」小熊游景点

description:
小熊的地图上有 $n$ 个景点，每个景点有分数 $s_i$。

$n-1$ 个点对之间有双向直达的公交线路，每条线路有收费 $w_i$。

现在小熊在 $a$ 景点，总司令在 $b$ 景点，他们要在 $a\to b$ 路径上的 $p$ 景点汇合，然后一起去 $q$ 景点。（$q$ 为任意点，每个人不会游览两次 $p$ 景点）

$m$ 次询问，给定 $a,b$，求 $p,q$，使得小熊和总司令花费之和最小的前提下他们经过的景点分数之和最大，输出他们经过的景点分数之和。（指小熊经过的景点分数之和 $+$ 总司令经过的景点分数之和）

**重复经过的线路收费重复计算，重复经过的景点分数重复计算。**

inputFormat:
第一行两个整数 $n,m$。分别表示景点个数和询问次数。

接下来一行 $n$ 个整数 第 $i$ 个整数 $s_i$ 表示第 $i$ 个景点的权值。

接下来 $n-1$ 行，每行 $3$ 个整数 $u,v,w$，表示 $u$ 节点和 $v$ 节点之间有一条收费 $w$ 的双向公交路线。

接下来 $m$ 行，每行两个整数 $a$ 和 $b$，表示小熊和总司令所在的景点位置。

outputFormat: 对于每组询问，每行输出一个整数表示结果。


title: [语言月赛202212] 狠狠地切割(Easy Version)

description:
现给你一个长度为 $n$ 的序列 $a _ 1, \cdots, a _ n$ 和 $m$ 个互不相同的整数 $b _ 1, \cdots, b _ m$。你需要按照这 $m$ 个数对序列 $a$ 进行**狠狠地切割**。

具体的，对于一个数字 $i \in [1, n]$，如果存在一个整数 $j \in [1, m]$，使得 $a _ i = b _ j$，则将位置 $i$ 称为一个**切割点**。对序列 $a$ 中的每一个切割点，我们在这个位置进行一次**狠狠地切割**。方法是，将该位置的数字去除，然后在这个位置将其左右的**序列/片段**一分两半。

如果对**狠狠地切割**的定义有疑问，可以参照「样例 #1」及「样例解释 #1」进行理解。

你需要计算，在进行了所有可能的**狠狠地切割**后，序列被切割为了多少**片段**。

特别的，如果在切割后，某一段内没有数组，那这一段不可被叫做**片段**。同样的，如果 $1$ 或 $n$ 为切割点，其与开头和结尾之间也不存在片段。

如果对**片段**的概念有疑问，可以参照「样例 #2」及「样例解释 #2」进行理解。

inputFormat:
第一行为两个整数，依次表示序列 $a$ 的长度 $n$ 和序列 $b$ 的长度 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。
第三行有 $m$ 个整数，第 $i$ 个整数表示 $b_i$。

outputFormat: 输出一个整数，代表**狠狠地切割**后的**片段**的个数。

hint:
### 样例 1 解释

在**狠狠地切割**前，序列 $a$ 如下所示：

$$\begin{matrix} 3 & 4 & 3 & 5 & 2 & 6 \end{matrix}$$

容易知道，第二个位置和第四个位置为切割点，我们使用 `|` 对其进行替换，代表去除工作：

$$\begin{matrix} 3 & | & 3 & | & 2 & 6 \end{matrix}$$

我们将片段进行简单的标记：

$$\begin{matrix} \overbrace{3} ^ \text{片段 1} & | & \overbrace{3} ^ \text{片段 2} & | & \overbrace{2 \quad 6} ^ \text{片段 3} \end{matrix}$$

共计 $3$ 个片段。

### 样例 2 解释

以下我们展示去除之后的序列：

$$\begin{matrix} | & 4 & | & | & 2 & | \end{matrix}$$

我们将片段进行简单的标记：

$$\begin{matrix} \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} | & \overbrace{4} ^ \text{片段 1} & | & \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} & | & \overbrace{2} ^ \text{片段 2} & | \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段}\end{matrix}$$

共计 $2$ 个片段。

### 数据规模与约定

- 对于 $20\%$ 的数据，保证 $n, m \leq 10$。
- 对于 $70\%$ 的数据，保证 $n, m \leq 5 \times 10 ^ 3$。
- 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 5 \times 10 ^ 5$，$1 \leq a_i,b_i \leq 5 \times 10^{6}$。

### 提示
本题输入规模较大，建议考虑使用较快的读入读出方式。


title: 「TERRA-OI R1」神，不惧死亡

background: 战斗已经到了白热化阶段，你已经精疲力竭，手臂因承受不住手中巨剑重量不住地发抖，噬神者的紫色外壳已经脱落大半，似乎再承受几次重击就会碎落一地。天空中紫色的迷雾开始变得暗淡，空间由于被不断撕裂而逐渐扭曲。在你的身前，噬神者最后一次撕开裂缝，用最原始的方式向你发起最后一击。你握紧手中的巨剑，准备迎接这最后一击，即使你清楚这是神明吞噬者最后的倔强，可你依然不敢放松一分一毫。最后一击过后，远处响起了钟声，战斗终将落下帷幕......

description:
李子要在一个长度为 $n$ 的序列 $a$ 上玩游戏，他每次会把下标在 $[l,r]$ 范围内，且取值在 $[p,q]$ 范围内的所有数全部找出来，每次他可以选择其中两个相同的值，并进行**抵消**操作，将这两个数从数列中删除。当且仅当一个原本存在的值被消除掉后，所有值小于这个数的每个值全部要被删除一次（例如数列中原本有三个 $2$，进行一次删除后将会仅剩两个 $2$），并且这个游戏将会立即停止。

李子会不止一次的玩这个游戏，并且每次取的区间都不相同，而且，为了加大游戏难度，李子会时不时的修改序列中某个数的值。

现在李子想让剩下的数列中的最小值尽可能大，需要请你针对每次游戏，输出这个最大的最小值。特别地，如果这个游戏无法停止或者存在一种方案可以消除整个数列，输出 $-1$。

inputFormat:
第一行两个用空格分隔的正整数 $n,m$，含义见题目描述。

第二行 $n$ 个用空格分隔的正整数，表示对应 $a$ 序列。

第三行到第 $m+2$ 行，每行有以下两种情况：

- $1$ $p$ $x$ 表示给 $a_p$ 的值加上 $x$。
- $2$ $l$ $r$ $p$ $q$ 表示询问将下标属于 $[l,r]$，取值属于 $[p,q]$ 的数列取出进行游戏的结果。

outputFormat: 针对每个询问 $2$，输出一行一个整数表示答案。

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

第一个询问对应的数列为 $[1,1,4,5,1,4]$，我们将两个 $1$ 先抵消，再抵消两个 $4$，此时比 $4$ 小的 $1$ 将会删除一次，整个序列只剩一个 $5$。

第二个询问针对前 $4$ 个数，且由于 $5$ 不属于 $[1,4]$ 值域范围，所以数列为 $[1,1,4]$，将两个 $1$ 抵消后游戏直接结束，答案为 $4$。

第三次修改将 $a_1$ 加 $1$，修改后数列为 $[2,1,4,5,1,4]$。

第四次询问对应的数列为 $[2,1,4]$，所有数据都只出现一次，没办法进行抵消操作，游戏无法停止所以输出 $-1$。

第五次询问的数列为 $[1,4,5,1,4]$，我们选择将两个 $1$ 抵消，由于数列中不再有 $1$，游戏结束，最小为 $4$。你也可以抵消两个 $4$，但这样答案为 $1$，比 $4$ 要小。

------------

#### 【数据范围】

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

| Subtask | Score | $n,m\le$ | limit |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10$ | $10^3$ | 无 |
| $2$ | $20$ | $10^5$ | 保证不存在操作 $1$ |
| $3$ | $30$ | $10^5$ | 保证对于每个操作 $2$ ，$p=1,q=n$ |
| $4$ | $40$ | $10^5$ | 无 |

对于 $100\%$ 的数据，$1\le n,m\le10^5$，对于任何时刻 $\forall i,a_i\in[1,n]$。

对于每个操作 $1$，$1\le p\le n$，$-n+1\le x\le n-1$ 并且 $-a_p<x\le n-a_p$。

对于每个询问 $2$，$1\le l \le r \le n$，$1\le p \le q \le n$。


title: [集训队互测 2022] 心跳排列图

background: 下发文件见附件。

description:
注：本题中所有序列下标均从 1 开始。

机器人心脏的跳动，排列成图是什么样的？

你有一个算法竞赛机器人，每分钟心跳 $n$ 次，第 $i$ 次心跳的强度为 $a_i$。这里，$a_1\sim a_n$ 恰为 $1\sim n$ 的一个排列。

设 $A_i$ 为序列 $a$ 删除第 $i$ 个元素后得到的序列，即 $A_i=[a_1,\dots,a_{i-1},a_{i+1},\dots,a_n]$。

对于元素互不相同的序列 $p$，设 $G(p)$ 为一个无向图，有 $|p|$ 个点，编号为 $1\sim |p|$。对于每对正整数 $1\le i\lt j\le |p|$，若 $\forall k\in [i,j]\cap \mathbb{Z}$，都有 $p_k\in [\min(p_i,p_j),\max(p_i,p_j)]$，则 $G(p)$ 中 $i$ 号点和 $j$ 号点有一条边。设 $F(p)$ 为 $G(p)$ 中 $1$ 号点到 $|p|$ 号点的最短路长度，这里一条路径长度定义为其边数。

设 $f(a)=[F(A_1),F(A_2),\dots,F(A_n)]$。

给定长度为 $n$ 的序列 $[b_1,\dots,b_n]$，请你求出任意一个 $1\sim n$ 的排列 $a$，使得 $f(a)=b$。**保证有解。**

在某些子任务中，算法竞赛机器人小 G 会给你一些“提示”：设 $G_0=G(a)$，设 $path_0$ 为 $G_0$ 中某条 $1$ 到 $n$ 的最短路经过的点构成的集合，设 $path_j$ 为 $G(A_j)$ 中某条起始点到结束点的最短路经过的点构成的集合（注意，为了方便，这里给出的 $path_j$ 中点的编号仍然沿用原图中点的编号，参见样例 2）。则小 G 有可能会额外告诉你所有 $path_j$（包括 $path_0$），也有可能只告诉你 $path_0$，也有可能不给你提示，详见输入格式。

保证给出的提示是正确的，也即一定存在一个满足所有提示的排列。

下发文件中有 `checker.cpp`，你可以用它来检查自己的输出是否正确。用法是 `./checker input output output`，`input` 和 `output` 分别为输入文件和你的输出。同时还下发了 `testlib.h`，请将其和 checker 置于同一目录下来编译 checker。

inputFormat:
第一行两个正整数，为子任务编号 $S$ 以及数据组数 $T$。

接下来 $T$ 组数据，每组数据格式为：第一行一个正整数 $n$，第二行 $n$ 个正整数 $b_1,\dots,b_n$。

**特别地，**

1. 若 $S=5$，每组数据还会输入 $n+1$ 行，这 $n+1$ 行里第 $i$ 行是一个长度为 $n$ 的 01 串 $c_i$，$c_{i,j}=[j\in path_{i-1}]$。
2. 若 $S=6$，每组数据还会输入第三行，包含一个长度为 $n$ 的 01 串 $c$，$c_i=[i\in path_0]$。

注意：

1. 即使你的程序不需要用到提示，在 $S=5$ 或 $S=6$ 时你仍然需要读入数组 $c$。
2. 对于一种输入的 $b$，符合条件的 $a$ 可能不唯一，进而 $c$ 可能也不唯一。**不要求**你的输出符合我们给出的 $c$ 的限制，只要符合 $b$ 的限制即视为正确。

同一行输入的不同变量用一个空格隔开。

outputFormat: 对于每组数据输出一行 $n$ 个正整数，为你求出的排列 $a$。

hint:
**样例 1 解释**

考虑样例中的第一组数据。一组解是 $a=[1,2,4,3]$。$A_1,A_2,A_3,A_4$ 分别为 $[2,4,3],[1,4,3],[1,2,3],[1,2,4]$。$G(A_1),G(A_2),G(A_3),G(A_4)$ 四个图中的边分别为：

- $G(A_1)$：$(1,2),(2,3)$。因此 $F(A_1)=2$。
- $G(A_2)$：$(1,2),(2,3)$。因此 $F(A_2)=2$。
- $G(A_3)$：$(1,2),(1,3),(2,3)$。因此 $F(A_3)=1$。
- $G(A_4)$：$(1,2),(1,3),(2,3)$。因此 $F(A_4)=1$。

所以 $f(a)=[2,2,1,1]$，符合输入。

符合输入的 $a$ 不唯一，比如 $a=[4,3,1,2]$ 也是正确的。

**样例 2 解释**

该样例的排列和第一个样例中第一组数据是相同的，但本样例存在子任务 5 的提示。注意在给出 $path_j$ 时仍然沿用原编号，例如删去 $1$ 后，新的最短路经过的点编号为 $2\to 3\to 4$。

**样例 3 解释**

该样例的排列和第一个样例中第一组数据是相同的，但本样例存在子任务 6 的提示。

**数据范围**

对于所有数据：$1\le T\le 4\times 10^4,4\le n\le 10^5,\sum n\le 5\times 10^5$。

- 子任务 1（$7$ 分）$T\le 250,n\le 7$。
- 子任务 2（$5$ 分）$b_i=1$。
- 子任务 3（$10$ 分）$n\ge 90000$，保证存在一组解满足 $a_1=1,a_n=n$。
- 子任务 4（$7$ 分）$n\ge 90000$，保证存在一组解满足 $a_2=1,a_{n-1}=n$。
- 子任务 5（$15$ 分）$n\le 100,\sum n^3\le 3\times 10^6$，存在所有 $path_j$ 的提示。
- 子任务 6（$15$ 分）$n\le 100,\sum n^3\le 3\times 10^6$，存在 $path_0$ 的提示。
- 子任务 7（$15$ 分）$n=100,T=3$，共 5 个测试点，输入生成方式是随机一个 $a$ 再求出 $f(a)$ 作为输入。
- 子任务 8（$25$ 分）$n\le 100,\sum n^3\le 3\times 10^6$。
- 子任务 9（$1$ 分）无特殊限制。


title: [集训队互测 2021] 数列重排

background: dottle bot。

description:
定义一个数列区间的 $\textrm{mex}$ 为区间中最小的没有出现过的自然数，定义一个数列的价值为其中 $\textrm{mex}\geq k$ 的区间数量。

给定 $n$ 个小于 $m$ 的自然数和一个区间 $[l,r]$，令 $f(k)$ 表示 $n$ 个数构成的数列所有重排列中数列价值的最大值，对于每一个 $k\in [l,r]$，求出 $f(k)$。

令 $a_i$ 表示数字 $i$ 出现的次数，保证存在正整数 $X$，使得  $\forall i\le m-1,a_i\in \{X,X+1\}$。

inputFormat:
由于 $n$ 可能很大，将采取如下方式减少读入量：

第一行四个整数 $m,l,r,X$。

第二行一个长度为 $m$ 的 $01$ 串，若其中第 $i$ 个位置为 $1$ 则数字 $i-1$ 的出现次数为 $X+1$，否则出现次数为 $X$。

根据输入可以推出 $n=mX+S$，其中 $S$ 为 $01$ 串中 $1$ 的数量。

outputFormat: 为了减少输出量，令 $ans=\displaystyle{\bigoplus_{i=l}^r}$$  (233^if(i)\bmod 998244353)$，其中 $\displaystyle\bigoplus$ 表示二进制下的按位异或，输出一行一个整数 $ans$。

hint:
#### 样例 1 解释

在样例给出的数列中，有 $3$ 个 $0$ 和 $2$ 个 $1$，任意排列 $f(0)$ 均为 $15$，排列为 $\textrm{01010}$ 时 $f(1)$ 有最大值 $13$，答案为：
$$
\displaystyle (233^0\times 15\bmod 998244353)\oplus(233^1\times 13\bmod 998244353)=3034
$$

#### 数据范围

- Subtask 1（5 points）：$n,m\leq 9$。
- Subtask 2（15 points）：$n,m\leq 200$。
- Subtask 3（15 points）：$n,m\leq 5\times 10^3$。
- Subtask 4（5 points）：$m\leq 2$，$l=0$，$r=1$。
- Subtask 5（10 points）：$m\leq 10^6$，$l=m$，$r=m$。
- Subtask 6（10 points）：$m\leq 10^6$，$X=1$，$s_i=0$。
- Subtask 7（15 points）：$m\leq 10^6$，$r-l+1\leq 10^4$。
- Subtask 8（15 points）：$m\leq 2\times 10^6$。
- Subtask 9（10 points）：无特殊限制。

对于所有数据，满足 $n\leq 10^9$，$m\leq 10^7$，$0\leq l\leq r\leq m$，$X\geq 1$。


title: [集训队互测 2022] 在路上

background:
滥用本题评测者封号。

dottle bot。

description:
**这是一道交互题，仅支持 C++ 提交**。

有一棵未知的树，**保证树的大小为奇数，你需要找到这棵树重心的编号**。

你可以进行询问，每次询问你可以询问三个点 $(x,y,z)$，若不存在一条简单路径同时经过三个点，则交互器会返回 $0$，否则若存在，那么交互器会返回三个点在路径上相对顺序中间的一个点。

令 $dis(a,b)$ 表示 $a,b$ 两点在树上最短路径经过的边数，你也可以理解为:

若 $dis(x,y)+dis(x,z)=dis(y,z)$，则交互器会返回 $x$。

否则若 $dis(y,x)+dis(y,z)=dis(x,z)$，交互器会返回 $y$。

否则若 $dis(z,x)+dis(z,y)=dis(x,y)$，交互器会返回 $z$。

否则交互器会返回 $0$。

在最终的测试中，每个测试点会包含 $T$ 组测试数据，和一个常数 $M$，表示你在所有测试数据中询问次数总和的上限，具体细则见 输入格式 以及 数据范围。

#### 实现细节

~~你需要引用 `path.h` 头文件。~~ 本题中你只需要把 `path.h` 头文件的内容粘贴到程序开头即可，不要引用 `path.h` 头文件。

你需要实现下面的函数：

```
int centroid(int id,int N,int M);
```

其中 $id$ 为当前子任务的编号，$N$ 为当前询问树的大小，$M$ 为当前测试点剩余的询问次数，函数的返回值为当前树的重心编号。

具体的，在第一次调用时 $M$ 为当前测试点的询问次数上限，每次调用结束之后 $M$ 会减去当前测试点使用的询问次数。

你可以调用下面的函数：

```
int ask(int x,int y,int z);
```

表示你进行了一次询问，交互器会返回当前询问的答案，特别的，若询问次数已经超过了上限，交互器会返回 $-1$。

注意同一个测试点中 `centroid` 函数可能会被多次调用，请注意数组清空等情况。

**下发文件中有样例交互库，该交互库的实现与评测时的交互库几乎一致，如果对交互方式有不理解可以参照交互库的代码理解**。

inputFormat:
样例评测库将读入如下格式的输入数据：

第一行三个整数 $id,T,M$，表示当前的子任务编号以及测试数据的数量，以及询问次数的上界。

对于每一组测试数据，第一行一个正整数 $n$，表示当前测试数据中树的大小。

之后一行 $n-1$ 个正整数，第 $i$ 个数表示 $i+1$ 在以 $1$ 为根意义下的父亲节点。

数据的答案将在交互库内部计算。

outputFormat: 具体信息见交互库。

hint:
#### 数据范围

![](https://cdn.luogu.com.cn/upload/image_hosting/f3d6b2zv.png?x-oss-process=image/resize,m_lfit,h_1700,w_2250)

特殊性质 $A$：保证树的形态为一条链，即每个点的度数均不超过 $2$。

保证每个 Subtask 里的测试数据数量均不超过 $20$。**请仔细阅读每一档子任务及其限制**。

#### 时空限制

Subtask 5 时限为 3s。

Subtask 7,8 时限为 4s。

其余 Subtask 时限为 1s。

空间限制：512MB。

保证最终交互库的时间使用不超过  2s，空间使用不超过 64MB。

#### 下发文件

下发文件中有一个样例交互库，提供的交互头文件，一份示例代码，以及一个满足子任务 $4$ 性质的样例，选手也可以按照题目的输入格式构造其他样例。

另外也有一份洛谷样式的交互库。

保证下发的交互库和最终使用的交互库除反作弊之外没有区别，你可以使用这个交互库输出调试信息。


title: 无可奈何花落去

background: 天上下起了蒙蒙小雨，回家已是傍晚，推开院门，一地花瓣映入眼帘，随着最近几天花瓣的凋落，树上的花瓣已所剩无几。从地上捡起一片花瓣，干涩的双眼立刻充满了泪水，它顺着脸颊滑下。落到花上的，不知是雨还是泪......

description:
望向树上的花朵：一朵花有 $n$ 瓣花瓣，花瓣之间有 $n-1$ 条边连接，所有的花瓣都是连通的。

树上的花瓣随着春天的离开而凋落。具体地，每一天，都会在未断开的边中均匀随机地选择一条边断开。

当每个花瓣的度数均不超过 $2$ 时，我们称这朵花凋零了。

一朵花期望会在几天后凋零呢？

inputFormat:
第一行一个正整数 $n$，表示花瓣的数量。

第二行 $n-1$ 个正整数 $f_2,\dots,f_n$，表示花瓣 $f_i$ 与花瓣 $i$ 之间有一条边。

outputFormat:
一行，一个正整数，表示一朵花的期望凋零时间，对 $985661441$（是个质数捏）取模。

如果你不会分数取模，请参考[此题](https://www.luogu.com.cn/problem/P2613)。

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

可以发现第一次不管断开哪条边，均会使这朵花凋零，故期望凋零时间为 $1$。

**【样例 2 解释】**

第一次断开 $(1,2)$ 或 $(2,4)$ 或 $(2,5)$，凋零时间为 $1$；第一次断开 $(1,3)$，凋零时间为 $2$。故期望凋零时间为 $\frac{3}{4}\times 1+\frac{1}{4}\times 2=\frac{5}{4}$。

**【数据规模与约定】**

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

-  Subtask 1（1 point）：$f_i=i-1$。
-  Subtask 2（12 points）：$n\leq 8$。
-  Subtask 3（12 points）：$n\leq 18$。
-  Subtask 4（8 points）：$f_i=1$。
-  Subtask 5（16 points）：有且仅有 $1$ 号点度数大于 $2$。
-  Subtask 6（13 points）：$n\leq 50$。
-  Subtask 7（13 points）：$n\leq 100$。
-  Subtask 8（13 points）：$n\leq 500$。
-  Subtask 9（12 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\leq 5\times 10^3$，$f_i<i$。


title: 【MX-X6-T5】再生

background:
> _このまま$\\$
らったった$\\$
音に乗って$\\$
今きっと世界で僕だけだ$\\$
後ろ向きな歌を聴いて$\\$
少しだけ$\\$
前向きに生きていく_
>
>_—— [再生 - Nanatsukaze](https://music.163.com/#/song?id=2133659925)_

破碎的点依照破碎的规则进行重组，如此再生的一个结构将会是什么样的呢？

description:
现有一棵 $n$ 个点的有标号有根树，给定其长链剖分得到的 top 数组，请你输出有多少种不同的树可以在长链剖分之后得到该 top 数组。答案对 $20051131$（质数）取模。

具体来说，对于一棵树 $T$，对所有点 $u$ 定义其树高 $h_u$：

- 如果 $u$ 是叶子，则 $h_u=1$。
- 否则设 $u$ 的孩子集合为 $S_u$，则 $h_u=\max\limits_{v\in S_u}h_v + 1$。

给定数组 $t_{1\cdots n}$，你需要计算有多少种树满足：

- 对于根节点 $r$，满足 $t_r=r$。
- 对于每一个不是叶子的节点 $u$，存在恰好一个孩子 $v$ 满足 $h_v+1=h_u$ 并且 $t_v=t_u$，其他孩子满足 $t_v=v$。

模 $20051131$（质数）。

两棵树不同当且仅当它们的根不同或它们的边集不同。

**保证答案不为 $\bf 0$，但是不保证答案在模意义下不为 $\bf 0$。**

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

接下来一行，$n$ 个空格分隔的正整数 $t_{1\cdots n}$，表示 top 数组。

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

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

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

仅有图中的两种树满足条件。

**【数据范围】**

对于所有数据，保证 $1\leq n\leq 5\times 10^5$，$1\leq t_i\leq i$，保证取模前答案不为 $0$。

**捆绑测试**，共 5 个 Subtask，具体限制如下所示：

- Subtask 1（11 pts）：$t_i=1$。
- Subtask 2（24 pts）：$n\leq 5$。
- Subtask 3（17 pts）：$n\leq 16$。
- Subtask 4（22 pts）：$n\leq 2\times 10^3$。
- Subtask 5（26 pts）：无特殊限制。


title: [语言月赛202301] 九九乘方表

description:
九九乘法表是数学学习中必须记忆的内容之一。

九九乘法表的前三行为：

`1 * 1 = 1`
`2 * 1 = 2 2 * 2 = 4`
`3 * 1 = 3 3 * 2 = 6 3 * 3 = 9`

类似的，我们可以定义出九九乘方表，其前三行为：

`1 ^ 1 = 1`
`2 ^ 1 = 2 2 ^ 2 = 4`
`3 ^ 1 = 3 3 ^ 2 = 9 3 ^ 3 = 27`

`a ^ b` 的含义为 $a^b$，也就是 $b$ 个 $a$ 相乘。

例如：$3^4=3\times3\times 3\times 3 = 81$

请你输出九九乘方表的前 $n$ 行，每两项之间由**一个**空格隔开。

inputFormat: 输入一行一个整数 $n$。

outputFormat:
输出 $n$ 行，为九九乘方表的前 $n$ 行。

请注意：符号 ^ 和 = 前后均由一个空格分隔，每两项之间由**一个**空格隔开。

hint: 对于 $100\%$ 的测试数据，$1 \le n \le 9$。


title: 接连不断！

background:
小青蛙被关进了监狱的小黑屋里，他遭受了接连不断的折磨，无论是肉体上还是精神上。

他的精神萎靡不振，他的身体行动迟缓。

有些东西被暂时的压制了，但这些东西越是被压制，它反弹时威力就越大。

他需要一个契机。

description:
青蛙有 $m+1$ 个无向图，编号为 $0\sim m$。每个图的点集都是 $V$，点集 $V$ 包含 $n$ 个点，编号为 $0\sim n-1$。起初所有的图都没有边存在。

接下来，在编号为 $x$ 的图中，对于所有在 $[0, n - 1]$ 中的编号 $i$，青蛙会将编号为 $i$ 的点与编号为 $(i\cdot x)\bmod n$ 的点连一条无向边。

他想知道这 $m+1$ 个图中有多少个图是**连通的**，这个问题交给你来回答。

注：
1. $\bmod$ 表示取模，$a\bmod b$ 表示 $a$ 除以 $b$ 得到的余数。
2. 在一张图中，若在点集内任意两个不同的点 $x, y$ 之间存在至少一条路径，则我们称这个图是**连通的**。

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

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

接下来 $T$ 行，每行两个整数 $n,m$，含义同上。

outputFormat: 共 $T$ 行，每行一个整数表示答案。


title: Digital Fortress

background:
布林克霍夫大声喊道：“这当然是密码！这不是密码，还能是什么？还有什么原因能让友加送掉这枚戒指？到底是谁在戒指上刻一大串杂乱无章的字母？”

方丹愤怒地等了布林克霍夫一眼，使他安静了下来。

“啊……伙计们？”贝克插了一句话，似乎很不情愿卷进来一样，“你们一直说这些是杂乱无章的字母。我想我应该让你们知道……这枚戒指上刻的字母并不是杂乱无章。如果你近距离看一下，就会明白，实际上，这些字母……这个……这个是拉丁文。”

指挥台上的所有人都看向了那枚戒指。上面写道：

> Quis custodiet ipsos custiodies.
谁来监视这些监视者……

description:
致命的变异串已经穿过了 X-11 过滤器，深入了国安局数据库。苏珊与贝克需要即时破解出密码，以关闭蠕虫病毒。

在蠕虫的文件中，他们找到了密码的一个特点：

- 共有 $n$ 位，每个数都在 $[1,m]$ 之间，并且单调不减。
- 如算出前缀异或和，那么前缀异或和也单调不减。
- 如算出后缀异或和，那么后缀异或和仍然单调不减。

除此之外，他们也找到了 $n,m$ 的值。现在，他们需要构造出一组密码，以满足所有特征。
***

#### 【形式化题意】

求是否存在长度为 $n$，所有元素都在 $[1,m]$ 范围内的单调不减正整数序列 $a$，满足：

- $\forall1<i\le n,a_1\ \text{xor}\ a_2\ \text{xor}\ \cdots\ \text{xor}\ a_{i-1}\le a_1\ \text{xor}\ a_2\ \text{xor}\ \cdots\ \text{xor}\ a_{i}$
- $\forall1\le i<n,a_n\ \text{xor}\ a_{n-1}\ \text{xor}\ \cdots\ \text{xor}\ a_{i+1}\le a_n\ \text{xor}\ a_{n-1}\ \text{xor}\ \cdots\ \text{xor}\ a_{i}$

如存在，输出一组合法解。多组数据。

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

对于每组数据，输入两个正整数 $n,m$。

outputFormat: 对于每组数据，如不存在满足要求的密码，输出 `No`。否则，输出 `Yes`，并在下一行输出一种合法方案。


title: Deception Point

background:
“防空火网已启用。”三角洲二号喊道，他坐在“基奥瓦”武装直升机舱门边的武器控制椅里，竖起了大拇指，“火力网
、调制噪声、掩护脉冲全都激活并锁定。”

三角洲一号心领神会，驾驶着飞机猛地向右一个侧弯飞机又驶上了一条前往“戈雅”的直线路径。这一招能躲过“戈雅”的雷达监控。

“锡箔包确定！”三角洲二号喊道。

> 绝对的孤立，

三角洲一号想。

> 他们毫无抵抗力。

他们的目标幸运且狡猾地从米尔恩冰架上逃脱了，但这回他们不会再得逞了。雷切尔 · 塞克斯顿和迈克尔 · 托兰选择弃岸上船，真是糟糕的选择。不过，这将是他们所做的最后一个坏决定了。

description:
雷切尔与迈克尔被困在了“戈雅”号上，而三角洲二号正在顺着雷达追杀二人。幸运的是，雷切尔也有一副雷达，因此双方都能知道对方的位置。

船舱内部共有 $n$ 个舱室，其中有 $n$ 条走廊连接这些舱室。$n$ 个舱室是互相连通的。由于船上空间拥挤，船舱内不会出现小于等于四条走廊组成的环。每过一分钟，雷切尔与三角洲二号都会同时从一个舱室跑到另一个舱室。

如果雷切尔在舱室内或者过道上碰到了三角洲，那么就意味着大限将至。雷切尔总共有 $q$ 个问题：当她在舱室 $x$，且三角洲二号在舱室 $y$ 时，她是否可以存活下来？

---

#### **【形式化题意】**

给定一张 $n$ 个点 $n$ 条边的无向连通图，图内不存在四元（及以下）环。$q$ 次询问 $x,y$，分别在图上 $x,y$ 点上放上棋子 $\rm A, B$。

每次两人同时操作棋子沿图边移动一步，若两棋子同时走到了同一个点上或者同时走过了相同的边，则 $\rm B$ 胜利。如果在 $10^{10^{9961}}$ 次操作后 $\rm B$ 还未胜利，则 $\rm A$ 胜利。

$\rm A,B$ 都是绝顶聪明的，他们不会做出对自己不利的决策。请你求出每次游戏的游戏结果。若 $\rm A$ 获胜，输出 `Survive`；否则输出 `Deception`。

**若对题意有疑问，请移步样例解释与数据范围部分。**

inputFormat:
第一行两个整数 $n,q$。
接下来 $n$ 行，每行两个整数 $u_i,v_i$，表示舱室 $u_i$ 与 $v_i$ 之间有一条过道。
之后 $q$ 行，每行两个整数 $x_i,y_i$，表示一次询问。

outputFormat: 共 $q$ 行。对于每个询问，如果雷切尔可以存活，那么输出 `Survive`，否则输出 `Deception`。


title: The Lost Symbol

description:
设二元运算符 $k\operatorname A n$ 为排列数 ${\rm A}_n^k$，$k \operatorname C n$ 为组合数 ${\rm C}_n^k$，定义 $k>n$ 时两者的值都为 $0$。

给定 $n,m$ 和一个长度为 $n-1$ 的仅包含 $\textrm A,\textrm C$ 的序列 ${\rm opt}_{[1,n-1]}$，对所有长度为 $n$，且每一个数都是 $[1,m]$ 中的整数的序列 $a_{[1,n]}$ 求 $(\cdots(((a_1\operatorname{opt}_1 a_2)\operatorname{opt}_2 a_3)\operatorname{opt}_3 a_4)\cdots\operatorname{opt}_{n-2}a_{n-1})\operatorname{opt}_{n-1}a_n$ 的和。

答案对质数 $11417603$ 取模。

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

接下来一行一个长度为 $n-1$ 的字符串表示 $\text{opt}$。

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


title: Inferno

background:
> 我是幽灵。
> 穿过悲惨之城，我落荒而逃。
> 穿过永世凄苦，我远走高飞。

沿着阿尔诺河的堤岸，我夺路狂奔，气喘吁吁……左转上了卡斯特拉尼大街，一直朝北而行，始终隐蔽在乌菲兹美术馆的阴影之下。

但他们还是穷追不舍。

他们的脚步声越来越响，这些追捕者冷酷无情，不达目的绝不善罢甘休。

这么多年来，他们一直尾随着我。他们锲而不舍，是的我只能活在地下……被迫呆在炼狱之中……就像冥府的恶魔，时刻忍受地狱的煎熬。

> 我是幽灵。

如今浮生尘世，我举目北望，却看不到通往救赎的捷径——那高耸的亚平宁山脉挡住了黎明的第一缕阳光。

description:
罗伯特 · 兰登在洗下但丁死亡面具上的丙烯石膏后，在背面发现了一行字：

> 哦，有着稳固智慧的人啊，
> 请注意这里的含义
> 就藏在晦涩的序列面纱之下。

下面有一行由 $1,-1$ 组成的长度为 $n$ 的序列。面具经受了岁月的侵蚀，序列中有一些数已经模糊不清。幸运的是，面具下面有给出两条线索：

> 你只得往空缺的位置填 $k$ 个 $1$，其余填入 $-1$，需要最大化这个序列的最大子段和。

 > > **一个序列的最大子段和定义为，其在一段连续长度的区间内的最大和。形式化地，一个序列 $a$ 的最大子段和即为 $\max\limits_{l=1}^n\max\limits_{r=l}^n\left(\sum\limits_{i=l}^r a_i\right)$。**

罗伯特 · 兰登希望在瘟疫扩散之前找到有关的线索。于是他找到了你。

- - -

#### 【形式化题意】

给定一个只包含 $-1,0,1$ 的序列，求出往 $0$ 的位置上填 $k$ 个 $1$，其余填 $-1$ 后最大子段和的最大值。

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

接下来一行 $n$ 个整数 $a_i\in\{-1,0,1\}$，其中 $0$ 表示数字模糊不清。

outputFormat: 一行一个正整数，表示可能的最大子段和。


title: Angels & Demons

background:
教皇内侍已经感觉到了身体上的疼痛。疼痛迅速传遍了全身，让他想抓想挠。

>不要忘记耶稣所遭受的痛苦。

他感觉喉咙中有种火烧火燎般的疼痛，就连吗啡都无法将之化解。

>我在这里的事情已经做完了。

他激起了人们的敬畏之心，人们又有了希望。

在帕利恩凹室里的时候，教皇内侍遵从上帝的教诲，举行了涂油仪式。他的身体上，发须上，面颊上，麻布长袍上，全身都涂满了灯油。他这会儿像是浸泡在神圣的绿色灯油中一样，气味芬芳，如母亲的体香，可却易燃烧。他将会幸运地升天。那是个充满奇迹而又迅速的过程。他留给世人的不再是丑闻……而是一股新的力量和奇迹。

他的手滑入长袍的口袋，摸出从帕利恩凹室里拿来的小小的金色打火机。

他低声说出了上帝在最后审判时说过的一句话。

>熊熊烈焰直冲云霄，上帝的天使也会在火焰中升天。

他的大拇指按在了打火机上。

人们还在圣彼得广场上唱着颂歌……

description:
给定 $n$ 个由小写字母组成的模板串 $S_{1...n}$，$q$ 组询问，询问分为以下两种类型：

1. `1 T`：给定一个由小写字母组成的询问串 $T$。
2. `2 p l r`：设 $num(p,l,r)$ 表示 $S_p$ 的 $[l,r]$ 子串是多少个询问串的子串，求 $\max\limits_{i=1}^{l}(num(p,i,r))$。

inputFormat:
第一行，两个数 $n,q,w_0$，其中 $w_0$ 表示数据类型。

* $w_0=0$：

  第 $2\sim n+1$ 行，每行一个字符串，第 $i+1$ 行表示 $S_i$。

  接下来 $q$ 行，每行一组询问，格式如题。
* $w_0=1$：

  第二行，输入三个整数 $A,B,C$。

  接下来 $n$ 行，每行一个字符串，表示一个模板串。

  接下来，询问按照如下代码生成（代码中的 ```lst``` 表示上一次询问 $2$ 的答案，初始时为 $0$，```le[i]``` 表示模板串 $i$ 的长度，```s``` 是 char 数组）：

```cpp
while (q--) {
	int op;
	scanf("%d", &op);
	if (op == 1) {
		scanf("%s", s + 1);
		int x((1ll * A * lst + B) % C), l(strlen(s + 1));
		for (int i(1); i <= l; ++i) {
			swap(s[i], s[x % l + 1]);
			x = (1ll * A * x + B) % C;
		}
	} else {
		int p, l, r;
		scanf("%d%d%d", &p, &l, &r);
		int x((1ll * A * lst + B) % C);
		p = (p + x) % n + 1;
		x = (1ll * A * x + B) % C;
		l = (l + x) % le[p] + 1;
		x = (1ll * A * x + B) % C;
		r = (r + x) % le[p] + 1;
		if (l > r) swap(l, r);
		// 此处更新 lst
	}
}
```

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


title: 去年天气旧亭台

background: 依旧是过往的天气，过往的楼台烟雨。时间悄悄流逝着，山河仍在，人却已不是过去的人……

description:
登上楼台，旧时满面沉灰的地板映入眼帘。

共有 $n$ 块地板，地板分为两类，第 $i$ 块地板的类别用 $c_i$ 表示，积灰程度用 $a_i$ 表示。**注意 $c_i$ 为 $0$ 或 $1$。**

现在要清理这些地板上的灰尘。每次操作中，你可以：

+ 选择两个下标 $i,j$，满足 $1\leq i\leq j\leq n$， $c_i=c_j$，**且第 $i$ 块和第 $j$ 块地板上的灰尘均未被清理过**；
+ 花费 $a_i+a_j$ 的能量清理**第 $i$ 块到第 $j$ 块所有地板**上的灰尘。

求清理完所有地板上的灰尘至少要多少能量。

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

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

对于每组测试数据：

- 第一行一个整数 $n$。
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。
- 第三行 $n$ 个整数 $c_1,c_2,\dots,c_n$。

outputFormat: 对于每组测试数据，一行一个整数表示最小能量。

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

- 对于第一组数据，直接花费 $a_1+a_6=5$ 的能量清理所有灰尘。
- 对于第二组数据，先花费 $a_1+a_1=6$ 的能量清理第一个地板上的灰尘，再花费 $a_2+a_8=7$ 的能量清理剩余灰尘。

**【数据规模与约定】**

对于 $10\%$ 的数据，保证 $T\le 10$，$n\le 10$；

对于 $40\%$ 的数据，保证 $T\le 20$，$n\le 10^3$；

另有 $10\%$ 的数据，保证 $c_i=1$；

对于 $100\%$ 的数据，保证 $1 \le T \le 10^5$，$1 \le n,\sum n\le 2 \times 10^6$，$c_i \in \{0,1\}$，$1 \le a_i \le 10^9$。


title: 小园香径独徘徊

background:
徘徊在一条幽深的小径上，拾起记忆的碎片，将它们放入两个长长的口袋中。

将它们收集完倒出来后，会拼成什么样的故事呢？

description:
有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串：

1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头；
1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾；
1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。

a3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。

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

第一行一个整数 $Q$，表示测试数据组数。

对于每组测试数据，一行一个字符串 $S$。

outputFormat: 对于每组测试数据，一行一个字符串，表示可以构成的字典序最小的 $T$。

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

- 对于 $\texttt{ababdca}$，依次进行第 $1,2,1,2,2,2,1$ 种操作，即可得到 $\texttt{aaabbdc}$。
- 对于 $\texttt{dcbcadb}$，依次进行第 $1,1,1,2,3,1,2$ 种操作，即可得到 $\texttt{abbcdcd}$。

**【数据规模与约定】**

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

-  Subtask 1（5 points）：$S$ 由至多两种字符构成。
-  Subtask 2（10 points）：$\sum |S|\le 12$。
-  Subtask 3（15 points）：$\sum |S|\le 100$。
-  Subtask 4（25 points）：$\sum |S|\le 3\times 10^3$。
-  Subtask 5（20 points）：$\sum |S|\le 2\times 10^5$。
-  Subtask 6（25 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le Q\le 3\times 10^5$，$1\le |S|\le 10^6$，$1\le \sum |S|\le 2\times 10^6$，$S$ 仅由小写字母构成。


title: The Da Vinci Code

background:
> 圣杯在罗斯琳教堂下静待。
> 大师杰作掩映中相拥入眠。
> 剑刃圣杯守护着她的门宅。
> 星空下她可安息无碍。

好的题目不需要花里胡哨的背景。

description:
给定一个长度为 $n$ 的数列 $a$，初始情况下 $a_i=i$。

另有一个取值在 $[1,n]$ 内的随机的整数 $x$，它取 $i$ 的概率为 $b_i$。

接下来进行 $k$ 次操作，每次**均匀随机**地选两个 $[1,n]$ 中的整数 $i,j$（允许 $i=j$），交换 $a_i,a_j$ 的值（如果 $i=j$ 则什么也不干）。问最后 $x$ 在位置 $i$ 上的概率，你需要对所有 $1\leq i\leq n$ 求出答案。你需要输出答案模 $3221225473$ 的值。

我们定义 $x$ 在位置 $i$ 上指 $a_i=x$。

inputFormat:
一行三个整数 $n,k,seed$。接下来使用如下代码生成 $b_i$：

```cpp
#include <cstdio>

typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;

const uint mod = 3221225473u;
const int N = 20000010;

ull seed;

ull getnext() {
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

uint rd(uint l, uint r) {
	return getnext() % (r - l + 1) + l;
}

int n;
ull k;
uint b[N];

int main() {
	scanf("%d%llu%llu", &n, &k, &seed);
	ull sum = 0;
	for (int i = 1; i < n; ++ i) b[i] = rd(2u, mod - 1), (sum += b[i]) %= mod;
	b[n] = mod + 1 - sum;
}
```

outputFormat: 设 $ans_i$ 表示 $x$ 在位置 $i$ 上的概率模 $3221225473$，则输出 $ans_i\times i$ 的异或和。


title: 待黑白分明

description:
[Shiro](https://www.bilibili.com/video/BV1jb411k7wa) 所在的城市可以看成数轴上 $n$ 个坐标连续的点，其中 $i$  号点的高度为 $p_i$，保证 $p$ 是一个 $\{1,2,\ldots,n\}$ 的排列。

3202 年的科技非常发达，发展出了虫洞列车技术。共有 $n$ 种列车，第 $i$ 种列车会经过所有高度大于等于 $i$ 的位置，每种列车线路都是双向的，也就是说可以乘列车从左到右，也可以从右到左。

Shiro 想在城市里转转，她定义一个位置集合 $S$ 合法，当且仅当我们将 $S$ 中的位置**按照高度排序**后，相邻的城市可以通过乘坐**一种**列车在中途不停靠的情况下直达。

她会给你 $q$ 次询问，每次给定 $l,r$，你需要告诉 Shiro 所有位置的**高度**均在 $[l,r]$ 内的合法集合 $T$ 的数量对 $998244353$ 取模的结果。

inputFormat:
第一行，两个正整数 $n,q$。

第二行，$n$ 个正整数，表示 $p_{1,2,\ldots,n}$。

接下来 $q$ 行，第 $i$ 行两个正整数 $l_i, r_i$，表示第 $i$ 次询问的高度区间。

outputFormat: 输出 $q$ 行，每行一个非负整数，表示答案。


title: 计数题

background:
[Easy Counting Problem](https://atcoder.jp/contests/agc022/tasks/agc022_e)

> 身のうさを思ひしらでややみなまし そむくならひのなき世なりせば

description:
给定长度为 $N$ 的 $01$ 串 $S$，你可以做若干个操作，形如将长度为 $3$ 的子串变成它们的中位数（注意是变成一个数字），问可以得到多少个不同的串。

答案对 $998244353$ 取模。

inputFormat:
本题有多组数据。第一行输入数据组数 $T$。

对于每组数据，仅输入一个字符串 $S$ 表示给定的 $01$ 串。

outputFormat: 对每组数据输出一行一个整数，表示答案对 $998244353$ 取模的结果。


title: 「DTOI-4」行走

background: 小 L 感到无聊，于是希望在树上行走。

description:
小 L 有一棵 $n$ 个点的树，树上点有点权，其中第 $i$ 个点权值为 $a_i$。

他不喜欢奇奇怪怪的权值，于是他保证 $a_i$ 一定是 $-1, 0, 1$ 之一。

他认为在树上行走是有趣的，于是他想要在这棵树上走出一条路径 $P$，其需要满足以下条件：

- $P$ 是一条**可以为空**的**简单有向路径**。
- 设 $P$ 中依次经过的点为 $P_1, P_2, \cdots, P_{|P|}$，则你求出的 $P$ 需要满足 $P_1 = 1$。
- 设 $f(P) = \displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$，则你求出的 $P$ 需要满足 $f(P)$ 最大。
- 在 $f(P)$ 最大的前提下，你求出的 $P$ 还需要满足 $P$ 的字典序最小。

请你求出符合上述条件的路径 $P$。

------------

关于本题中字典序的定义：

设有两条待比较的路径 $P \neq Q$。

- 若存在 $1 \leq i \leq \min(|P|, |Q|)$，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i < Q_i$，则我们称 $P$ 的字典序小于 $Q$。
- 若存在 $1 \leq i \leq \min(|P|, |Q|)$，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i > Q_i$，则我们称 $P$ 的字典序大于 $Q$。
- 若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $|P| < |Q|$，则我们称 $P$ 的字典序小于 $Q$。
- 若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $|P| > |Q|$，则我们称 $P$ 的字典序大于 $Q$。

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

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$；

接下来 $n - 1$ 行，每行两个整数 $u, v$，表示树上的一条边。

outputFormat:
一行，$|P|$ 个整数，表示你求出的路径 $P$ 中依次经过的点。

**特别的，若 $P$ 为空路径，请不要进行任何输出操作。**


title: 「KDOI-04」XOR Sum

background:
凯文一眼秒了这题。

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

description:
给定一个正整数 $n$，请构造一个长度为 $n$ 的**非负整数**序列 $a_1,a_2,\dots,a_n$，满足：

+ 对于所有 $1\le i\le n$，都有 $0\le a_i\le m$。
+ $a_1\oplus a_2\oplus\dots\oplus a_n=k$。其中 $\oplus$ 表示[按位异或](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677)运算。

或者判断不存在这样的序列。

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

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

对于每组测试数据，输入包含一行三个非负整数 $n,k,m$。

outputFormat:
对于每组测试数据，输出一行一个 $-1$ 表示没有这样的序列存在。

否则，输出 $n$ 个用空格分隔的**非负整数**，表示你所构造的序列。如果有多个合法的答案，你只需要输出其中任意一种。

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

对于第 $1$ 组测试数据，有且仅有一个序列满足条件。

对于第 $2$ 组测试数据，由于 $4\oplus 7=3$ 且 $4,7\le10$，所以这是一个合法的答案。同样地，序列 $(2,1)$ 也是一个合法的答案。

对于第 $4$ 组测试数据，可以证明不存在满足要求的序列。

**【数据范围】**

记 $\sum n$ 为单个测试点中所有 $n$ 的值之和。

对于所有测试数据，保证 $1\le T\le 1~000$，$1\le n\le 2\cdot10^5$，$0\le m,k\le 10^8$，$\sum n\le 2\cdot10^5$。

**【子任务】**

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

+ Subtask 1 (18 pts)：$k\le m$。
+ Subtask 2 (82 pts)：没有额外的约束条件。


title: [DTOI 2023] B. 去年 11 月卵梦蕾简易钨丝

background:
# 大样例已修复

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

description:
给定序列 $\{a_n\}$，支持两种形如 `opt x` 操作：

1. `1 x`：删除一个数 $x$，若序列中没有 $x$，则输出 $-1$ 并跳过本次操作，**若有多个 $x$，则仅删除一个**。

2. `2 x`：向序列中插入一个数 $x$。

**对于每个未被跳过的操作**，试求出 $a$ 的一个排列 $p$，最小化 $\sum \limits_{i=1}^{n} \lvert p_{i+1}-p_i\rvert$ 的值，即最小化 $\lvert p_2-p_1\rvert+\lvert p_3-p_2\rvert+\dots+\lvert p_{n+1}-p_n\rvert$ 的值，其中 $p_{n+1}=p_1$。

**保证任意时刻序列内至少有 $1$ 个数。**

---
$p$ 是 $a$ 的排列当且仅当对于 $\forall x$，$\sum [p_i=x]=\sum [a_i=x]$。

简而言之，$p$ 是 $a$ 经过某种方式重排后的结果。

例如 $\{1,1,4,5,1,4\}$ 是 $\{1,5,4,1,4,1\}$ 的一个排列，但是 $\{1,5,4,1,4,7\}$ 不是。

inputFormat:
输入共 $q + 2$ 行。

第 $1$ 行两个正整数 $n, q$。

第 $2$ 行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，代表初始的序列。

第 $3 \sim q + 2$ 行，每行两个数 $opt, x$ ， 代表一个询问。

outputFormat:
输出有多行。

每行输出 $1$ 个数，代表一个未被忽略的询问的答案，否则输出 `-1`。

hint:
#### 【样例 1 解释】
对于第一个询问，删除了序列中的数 $4$，则当前序列为$ 1, 2, 3, 10 $， 可以证明 $18$ 为当前序列的最小答案。

对于第二个询问，删除了序列中的数 $10$，则当前序列为$ 1, 2, 3 $， 可以证明 $4$ 为当前序列的最小答案。

对于第三个询问，向序列中添加了一个数 $9$，则当前序列为$ 1, 2, 3, 9 $， 可以证明 $16$ 为当前序列的最小答案。

#### 【样例 2】

见附加文件中的 `abs/abs2.in` 与 `abs/abs2.out`。

该样例满足测试点 $1\sim 4$ 的限制。

#### 【样例 3】

见附加文件中的 `abs/abs3.in` 与 `abs/abs3.out`。

该样例满足测试点 $7\sim 10$ 的限制。

#### 【数据范围与提示】
记 $w$ 为值域大小，对于所有测试数据，保证 $n,q\leq 10^6$，$0\leq w\leq 10^6$。

每个测试点的具体限制见下表：

| 测试点编号 | $n,q\leq$ | $w$ |
| :----------: | :----------: | :----------: |
| $1\sim 4$ | $100$ | $10$ |
| $5\sim 6$ | $10^3$ | $10^3$ |
| $7\sim 10$ | $10^6$ | $10^6$ |


title: [RC-07] Abnormal Permutation Tuples

description:
给出三个正整数 $n,m$ 和 $mod$。

有多少个 $1\sim n$ 的排列构成的有序 $m$ 元组，$(p_1,p_2,\dots,p_m)$，满足：

- 字典序：$p_1\lt p_2\lt \dots\lt p_m$
- 逆序对数：$p_1\gt p_2\gt \dots\gt p_m$

设 $f(n,m)$ 为答案模 $mod$ 的值。对于所有 $1\le i\le n,1\le j\le m$，请你输出 $f(i,j)$。

inputFormat: 输入包含一行三个正整数 $n,m,mod$。

outputFormat: 输出一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列为 $f(i,j)$。


title: [RC-07] 超超立方体

description:
有一个 $n$ 维 $(a_1-1)\times (a_2-1)\times \dots \times (a_n-1)$ 超立方体。左下角坐标为 $(1,1,\dots,1)$，右上角坐标为 $(a_1,a_2,\dots,a_n)$。

考虑一个无向图，有 $a_1\times a_2\times \dots \times a_n$ 个有标号的结点。结点的标号分别为 $(x_1,\dots,x_n)\ (1\le x_i\le a_i)$，每个节点对应超立方体内部或者边界上一个整点。对于一对图上的顶点 $(U,V)\ (U=(x_1,\dots,x_n),V=(y_1,\dots,y_n))$，它们之间有边相连当且仅当 $UV$ 平行于超立方体的一条棱。换句话说，也就是 $\sum_{1\le i\le n}[x_i=y_i]=n-1$。

计算该图生成树个数对 $998244353$ 取模的结果。

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

接下来一行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

outputFormat: 输出答案对 $998244353$ 取模的结果。

hint:
所有数据均满足：$1\le n\le 100$，$2\le a_i\le 5000$。

- 子任务 $1$（$5$ 分）：$n=1$。
- 子任务 $2$（$5$ 分）：$n\le 3,\prod a_i\le 500$。
- 子任务 $3$（$10$ 分）：$n=2$。
- 子任务 $4$（$80$ 分）：无特殊限制。


title: [RC-07] 心跳

description:
对正整数 $x$，设 $f(x,B)$ 表示 $x$ 在 $B$ 进制下的数位和。说一个正整数 $p$ 是 $B$-好的，当且仅当对于任意正整数 $q<p$ 都有 $f(p,B)\ge f(q,B)$。

给定正整数 $n$ 和 $B$，计算有多少个 $\le n$ 的正整数是 $B$-好的。

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

第一行是数据组数 $T$。

接下来 $T$ 行，每行两个正整数 $n,B$。

outputFormat: 输出 $T$ 行，每行一个非负整数，为答案。


title: [语言月赛202301] 一次函数

description:
在二维平面坐标系 $xOy$ 中，一个点的位置可以由横坐标 $x$ 和纵坐标 $y$ 两个参数描述，其坐标记为 $(x,y)$。

一次函数 $y=kx+b$ 是满足纵坐标 $y$ 等于 $k$ 乘以横坐标 $x$ 加 $b$ 的点的集合，即满足该条件的点都在该一次函数的直线上。

现在有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$。

现在请你求出，分别有多少点，在给定的一次函数图像上。

**形式化地，给出 $n$ 对整数 $(x,y)$，请你求出有多少对数满足 $y=k\times x+b$。**

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

输入的第一行为三个整数 $n,k,b$。

接下来 $n$ 行，每行两个数 $x_i,y_i$，代表第 $i$ 个点的坐标。

outputFormat: 输出一行一个整数，代表有多少点在给出的一次函数上（即满足 $y_i = kx_i+b$）。


title: [语言月赛202301] 华小科的旅行开始了

description:
[华中科技大学](https://www.hust.edu.cn/)（Huazhong University of Science and Technology, HUST）面积辽阔。其地图可以被划分为 $n$ 行 $m$ 列。用 $(i,j)$ 来表示第 $i$ 行第 $j$ 列的位置。

华小科的旅行开始了，她将从 $(S_x,S_y)$ 出发。在每一个 $(i,j)$ 位置有着任务指引，告诉华小科她下一步应该前往的位置，或者是结束旅行。

请你依次输出华小科的旅行到达的位置信息，数据保证旅行能够在有限步内结束。

inputFormat:
输入的第一行为四个整数 $m,n,S_x,S_y$，分别代表列数、行数和开始的坐标。

接下来 $n$ 行，每行 $2m$ 个整数。第 $i$ 行的第 $2\cdot j-1$ 和第 $2 \cdot j$ 个数为第 $i$ 行第 $j$ 列的“任务指引”，表示到达位置 $(i,j)$ 后下一步将要前往的位置。若两个数均为 $0$，则代表结束旅行。这些数均为 $0 \sim \max \{n, m\}$ 范围内的整数。

outputFormat: 输出若干行，每行两个数 $x,y$，由空格分开，代表华小科的旅行路径经过了 $(x,y)$。


title: [语言月赛202301] 避雷针

description:
$n$ 个避雷针从左至右排成一排，我们将它们从左至右依次标号为 $1 \sim  n$。

现在有 $m$ 道雷依次劈下。你得知了一串序列 $a _ 1, \cdots, a _ m$。对于第 $i$ 道雷，其劈中了 $a _ i - 2$（如果存在）、$a _ i - 1$（如果存在）、$a _ i$、$a _ i + 1$（如果存在）、$a _ i + 2$（如果存在）号避雷针。

在 $m$ 道雷劈完后，你想要知道，被劈过**至少一次**的避雷针有几个。

inputFormat:
输入共两行。

第一行为两个整数 $n, m$，代表避雷针数量和雷的数量。

第二行为 $m$ 个整数 $a _ 1, \cdots, a _ m$，代表题面中的序列。

outputFormat:
输出共一行。

输出一行一个整数，被劈过**至少一次**的避雷针的数量。

hint:
### 样例 1 解释

被劈中的避雷针是 $2, 3, 4, 5, 6$ 号，共 $5$ 个。

### 样例 2 解释

被劈中的避雷针是 $1, 2, 3, 4$ 号，共 $4$ 个。请注意 $a _ 1 - 2 = 0$ 号避雷针不存在，也不应被劈中。

### 样例 3 解释

被劈中的避雷针是 $1, 2, 3, 4, 5, 6, 7, 8, 9$ 号，共 $9$ 个。

请注意尽管部分避雷针被劈了两次甚至三次，对这些避雷针我们仍然只计数一次。

### 数据规模与约定

- 对于前 $10\%$ 的数据，保证 $n = 1$。
- 对于前 $30\%$ 的数据，保证 $m = 1$。
- 对于另外 $20\%$ 的数据，保证 $m \leq n - 2$ 且 $\forall i \in [1, m], a _ i = i$。
- 对于 $100\%$ 的数据，保证 $1 \leq n,m \leq 10 ^ 6$，$1 \leq a _ i \leq n$。


title: [Ynoi2004] rpfrdtzls

description:
给定 $n,m,A$，维护由序列构成的序列 $a_1,\dots,a_n$，初始 $a_i$ 包含一个元素 $A+1$；

共 $m$ 次操作：

修改操作：给定 $l,r,x$，对 $l\le i\le r$，在序列 $a_i$ 前面插入元素 $x$

查询操作：给定 $l,r$，查询 $\sum\limits_{i=l}^r F(a_i,A)$

其中 $F((x_1,\dots,x_n),0)=0$

对 $k>0$，$F((x_1,\dots,x_n),k)=F((x_2,\dots,x_n),\lfloor \frac{k}{x_1} \rfloor)+1$

###

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

接下来 $m$ 行，每行 $1,l,r,x$ 表示一个修改操作，或 $2,l,r$ 表示一个查询操作；

outputFormat: 对每个查询操作，输出一行，表示答案。

hint:
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n,m\le 5\times 10^5$，$1\le A,x\le 10^9$，$1\le l\le r\le n$。

对于 $25\%$ 的数据，满足 $n,m\le 100$。

对于 $50\%$ 的数据，满足 $n,m\le 10^5$。

对于另外 $25\%$ 的数据，满足 $x\ne 1$。

对于另外 $25\%$ 的数据，无特殊限制。


title: 数列前缀和 4

background: 这次不是数列的问题了。

description:
给定一个 $n$ 行 $m$ 列的矩阵 $a$，有 $q$ 次询问，每次给定 $(u, v)$ 和 $(x, y)$，请你求出：

$$(\sum_{i = u}^x \sum_{j = v}^y a_{i,j}) \bmod 2^{64}$$

也就是求出以 $(u, v)$ 为左上角、$(x,y)$ 为右下角的矩形元素和对 $2^{64}$ 取余数的结果。

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

输入的第一行是一个整数 $T$，表示数据组数。接下来依次给出每组数据的输入信息：

第一行三个整数，依次表示矩阵的行数 $n$ 和列数 $m$ 以及询问数 $q$。
接下来 $n$ 行，每行 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。
接下来 $q$ 行，每行四个整数，依次为 $u,v,x, y$，表示一组询问。

outputFormat: 为了避免输出过大，对于每组数据，请输出一行一个整数，表示本组数据的所有询问的答案的按位异或和。

hint:
### 样例 1 解释

对第一组数据，三次询问的答案依次为 $45,9,16$。其按位异或和为 $52$。

### 数据规模与约定

对全部的测试点，保证 $1 \leq T \leq 10$，$1 \leq n, m \leq 10^3$，$1 \leq q \leq 10^6$，$0 \leq a_i < 2^{64}$，$1 \leq u \leq x \leq n$，$1 \leq v \leq y \leq m$。

数据保证 $\sum(n \times m) \leq 10^6$，$\sum q \leq 10^6$。即输入矩阵的总大小和询问总数均不超过 $10^6$。

### 提示
如果你不知道什么是按位异或和，可以在你的代码里添加如下的函数：

```cpp
template <class T>
T getXorSum(T *begin, T *end) {
  T ret = 0;
  for (T *it = begin; it != end; ++it) ret ^= *it;
  return ret;
}
```
这一函数的作用是计算传入数组（包括 `std::vector`）某一左闭右开区间的按位异或和，返回值类型与传入数组的类型相同，调用方法与 `std::sort` 类似，例如，要求数组 $a$ 的 $a_1 \sim a_n$ 的按位异或和，则调用 `getXorSum(a + 1, a + 1 + n)`，求 $a_0 \sim a_{n - 1}$ 的按位异或和，则调用 `getXorSum(a, a + n)`。如果 $a$ 是 `std::vector`，则将上述调用代码里的 `a` 均改为 `a.begin()` 即可。


title: 数列离散化

description:
给定一个长度为 $n$ 的数列 $a$。定义 $\mathrm{rank}(i)$ 表示数列 $a$ 中比 $a_i$ 小的不同数字个数再加一。

对 $1 \leq i \leq n$，现在请你求出所有的 $\mathrm{rank}(i)$。

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

输入的第一行是一个整数，表示数据组数 $T$。接下来依次给出每组数据的信息：

第一行是一个整数，表示数列长度 $n$。
第二行有 $n$ 个整数表示数列 $a$，第 $i$ 个整数表示 $a_i$。

outputFormat: 对每组数据，输出一行 $n$ 个整数，用空格隔开，依次表示 $\mathrm{rank}(1)$ 到 $\mathrm{rank}(n)$。

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

对全部的测试点，保证 $1 \leq T \leq 5$，$1 \leq n \leq 10^5$，$-10^9 \leq a_i \leq 10^9$。


title: 「LAOI-6」Yet Another Graph Coloration Problem

background: [English statement](https://www.luogu.com.cn/problem/U477166). You must submit your code at the Chinese version of the statement.

description:
小 R 有一张 $n$ 个节点和 $m$ 条的边简单无向图，节点的编号依次为 $1 \sim n$。她想要为图中的每个节点分配黑色或白色的颜色，使得：

- 有至少 $1$ 个黑色节点；
- 有至少 $1$ 个白色节点；
- 对于任何一对点对 $(u, v)$，只要 $u$ 和 $v$ 的颜色不同，就存在至少 $2$ 条从 $u$ 到 $v$ 的不同的简单路径。
	- 简单路径是图上指不重复经过同一点的路径。
	- 若两条简单路径不同，要么其长度不同，要么至少存在一个正整数 $i$ 使两条路径经过的第 $i$ 个点不同。

或者，报告解不存在。

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

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

- 第一行，两个整数 $n, m$，表示图的节点数和边数。
- 接下来 $m$ 行，每行两个整数 $u, v$，表示有一条 $u, v$ 之间的边。

保证给出的图无重边、无自环。

outputFormat:
对于每组数据：

- 若有解，输出一行长为 $n$ 的字符串，第 $i$ 个字符为 `B` 表示 $i$ 号节点为黑色，为 `W` 表示 $i$ 号节点为白色；
- 若无解，仅输出一行一个整数 $-1$。

如果有多种合法的解，你只需要输出任意一种即可。

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

- Subtask 0（15 pts）：$\sum 2^n \leq 2^{16}$。
- Subtask 1（25 pts）：$n \leq 3\times 10^3$，$m \leq 3\times 10^3$，$\sum n \leq 10^4$，$\sum m \leq 2\times 10^4$。
- Subtask 2（5 pts）：保证图不连通。
- Subtask 3（10 pts）：保证每个点的度数均为 $2$。
- Subtask 4（20 pts）：保证 $n = m$。
- Subtask 5（25 pts）：无特殊限制。

对于所有数据，保证 $1 \leq T \leq 10^5$，$2 \leq n \leq 2 \times 10^5$，$0 \leq m \leq 2 \times 10^5$，$\sum n \leq 2\times 10^6$，$\sum m \leq 2\times 10^6$，保证给出的图无重边、无自环。


title: 「DROI」Round 1 游戏

background: 人生，又何尝不是一场游戏呢？

description:
你将和一名小朋友进行 $T$ 次游戏，每一次游戏的规则如下：

1. 首先，你需要在 $[1,n]$ 中选择一个正整数 $x$。

2. 接下来，小朋友会有 $Q$ 次询问，对于每次询问，他会给出一个 $a_i$（保证 $a_i \in [1,n]$），你需要回答他 $\gcd(x,a_i)$ 的值。

3. 当某一轮小朋友得到答案后，如果他能唯一确定你选择的数，那么本次游戏结束。

现在**你提前知道了**小朋友每次询问的 $a_i$，你需要找到一个 $x$，使得游戏持续的轮数最长。

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

第一行一个整数 $T$，表示进行游戏的次数。

对于每次游戏：

第一行两个整数，分别为 $n$ 和 $Q$。

第二行 $Q$ 个整数，其中第 $i$ 个整数表示 $a_i$。

outputFormat: 对于每次游戏，请输出游戏能持续的最长轮数，如果存在一个 $x$ 使得小朋友在 $Q$ 轮之后也无法唯一确定其值，则输出`game won't stop`。

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

选取 $11$ 作为 $x$，显然小朋友到游戏结束也无法唯一确定。

------------

#### 样例解释#2

对于第一组数据：选取 $1$ 作为 $x$，小朋友在第五轮结束后可以唯一确定 $x$，可以证明不存在更优的 $x$。

对于第二组数据：同理，选取 $1$ 作为 $x$ 即可。

------------

#### 数据范围

**「本题采用捆绑测试」**

- $\operatorname{Subtask} 1(20\%)$：$n,Q\leq 500$。

- $\operatorname{Subtask} 2(20\%)$：$n,Q \leq 5 \times 10^4$。

- $\operatorname{Subtask} 3(30\%)$：$Q \leq 10^5$。

- $\operatorname{Subtask} 4(30\%)$：无特殊限制。

对于 $100\%$ 的数据：$T \leq 10$，$1 \leq a_i \leq n \leq 10^{18}$，$1 \leq Q \leq 2\times 10^{6}$，$\sum Q \leq 6\times 10^{6}$。

**本题输入量较大，请用较快的输入方法。**


title: 「KDOI-06-S」消除序列

description:
小 M 有一个长度为 $n$ 的序列 $v_1,v_2,\ldots,v_n$，初始时，所有元素的值均为 $1$。

你有 $3$ 种作用在这个序列上的操作：

1. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_1,v_2,\ldots,v_i$ 的值全部设为 $0$，这种操作的代价是 $a_i$；
2. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_i$ 的值设为 $0$，这种操作的代价是 $b_i$；
3. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_i$ 的值设为 $1$，这种操作的代价是 $c_i$。

现在有 $q$ 次询问，每次询问中给定一个集合 $P$，你希望进行若干次操作（可能为 $0$），使得：序列 $v$ 中下标位于该集合的元素的值为 $1$，其余位置的值为 $0$。**形式化地说，对于任意 $\bm{1\le i\le n}$，若 $\bm{i\in P}$，则 $\bm{v_i=1}$，否则 $\bm{v_i=0}$。** 并且，你需要最小化这次询问中所有操作的总代价。

注意，询问是相互独立的，也就是说，每次询问结束后，序列 $v$ 将会回到初始状态，即所有元素的值全都变为 $1$。

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

输入的第一行包含一个正整数 $n$，表示序列 $v$ 的长度。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，表示第一种操作的代价。

第三行包含 $n$ 个非负整数 $b_1,b_2,\ldots,b_n$，表示第二种操作的代价。

第四行包含 $n$ 个非负整数 $c_1,c_2,\ldots,c_n$，表示第三种操作的代价。

第五行包含一个正整数 $q$，表示询问次数。

接下来的 $q$ 行中，第 $i$ 行包含以下内容：

+ 开头一个非负整数 $m$，表示第 $i$ 次询问中集合 $P$ 的大小；
+ 接下来有 $m$ 个正整数 $p_1,p_2,\ldots,p_m$，依次表示集合 $P$ 中每个元素的值，保证对于任意 $1\le i<m$，都有 $p_i<p_{i+1}$。

outputFormat:
输出到标准输出。

输出共 $q$ 行，第 $i$ 行包含一个非负整数，表示第 $i$ 次询问中操作总代价的最小值。

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

对于第一次询问，可以按顺序执行如下操作：

+ 在 $i=4$ 处执行操作 $1$，在这之后，序列 $v$ 变为 $[0,0,0,0,1]$，代价为 $0$；
+ 在 $i=4$ 处执行操作 $3$，在这之后，序列 $v$ 变为 $[0,0,0,1,1]$，代价为 $2$；
+ 在 $i=5$ 处执行操作 $2$，在这之后，序列 $v$ 变为 $[0,0,0,1,0]$，代价为 $5$。

所以总代价为 $0+2+5=7$，可以证明，不存在更小的总代价。

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

对于这个样例中的唯一一次询问，可以选择在 $i=10$ 处执行操作 $1$，总代价为 $a_{10}=7$。

**【样例 #4】**

见选手目录下的 `reserve/reserve4.in` 与 `reserve/reserve4.ans`。

**【样例 #5】**

见选手目录下的 `reserve/reserve5.in` 与 `reserve/reserve5.ans`。

这个样例满足测试点 $8\sim 11$ 的条件限制。

**【样例 #6】**

见选手目录下的 `reserve/reserve6.in` 与 `reserve/reserve6.ans`。

这个样例满足测试点 $14\sim 15$ 的条件限制。

**【样例 #7】**

见选手目录下的 `reserve/reserve7.in` 与 `reserve/reserve7.ans`。

这个样例满足测试点 $16$ 的条件限制。

**【样例 #8】**

见选手目录下的 `reserve/reserve8.in` 与 `reserve/reserve8.ans`。

这个样例满足测试点 $17\sim 20$ 的条件限制。

***

**【数据范围】**

记 $\sum m$ 为单测试点内所有询问 $m$ 的值之和。

对于所有数据保证：$1 \leq n \leq 5\times 10^5$，$0\le m \le n$，$0 \leq \sum m \leq 5 \times 10^5$，$1\le q\le \max(n,\sum m)$，$0 \le a_i, b_i, c_i \le 10^9$，$1\le p_i \le n$。

| 测试点编号 | $n \le$ | $m \le$ | $\sum m \le$| 是否有特殊性质 |
|:--:|:--:|:--:|:--:|:--:|
| $1 \sim 2$ | $5 \times 10^5$ | $0$ | $0$ | 否 |
| $3 \sim 4$ | $7$ | $7$ | $15$ | 否 |
| $5 \sim 6$ | $2 \times 10^3$ | $1$ | $2 \times 10^3$ | 否 |
| $7$ | $2 \times 10^3$ | $2 \times 10^3$ | $2 \times 10^3$ | 是 |
| $8 \sim 11$ | $2 \times 10^3$ | $2\times 10^3$ | $2 \times 10^3$ | 否 |
| $12 \sim 13$ | $5 \times 10^4$ | $5 \times 10^4$ | $5 \times 10^4$ | 否 |
| $14 \sim 15$ | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | 否 |
| $16$ | $5 \times 10^5$ | $5 \times 10^5$ | $5 \times 10^5$ | 是 |
| $17 \sim 20$ | $5 \times 10^5$ | $5 \times 10^5$ | $5 \times 10^5$ | 否 |

特殊性质：对于任意 $1\le i\le n$，保证 $c_i = 0$。

**【提示】**

本题输入输出量较大，请使用适当的 I/O 方式。


title: [语言月赛202301] 铺地毯

background: 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域铺上一些**正方形**地毯。

description:
这片矩形区域长 $a$ 米，宽 $b$ 米。地毯为边长为 $c$ 米的正方形。

他想要知道，在地毯不进行裁切且两两不重叠的前提下，能否使用若干张这种地毯铺满**整个**矩形，如果可以铺满，那么铺满**整个**矩形需要多少张地毯。

inputFormat: 输入共一行，为三个正整数 $a, b, c$，分别表示矩形区域的长、宽和地毯的边长。

outputFormat:
输出共一行。

如果无法使用若干张这种地毯铺满**整个**矩形，输出一行一个 `-1`。

如果可以使用若干张这种地毯铺满**整个**矩形，输出一行一个正整数，代表铺满**整个**矩形需要的地毯的数量。


title: 「RiOI-2」likely

background:
小 E 喜欢把东西排成环状，而不是一条链。

近些天，她在学校学到了正负号。她把它们放在了环上，作为密码。

然而，她现在已然忘却了，只看到草稿纸上的一个数字。那是什么？

description:
对于一个长度为 $n$ 的仅包含 $\pm1$ 的序列 $a_0\dots a_{n-1}$，我们定义 $S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n}$。

给定 $n, m, k$，求在 $2^n$ 个不同的序列 $a$ 里，试求出有多少不同的 $a$ 满足 $S(a, m) = k$。

答案对 $998,\!244,\!353$ 取模。

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

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

接下来 $T$ 行，每行三个整数，依次表示 $n, m, k$。

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


title: [语言月赛202301] 新年快乐

background: 要过春节了，扶苏收到了她的新年礼物：一个崭新的字符串。

description:
扶苏收到的字符串是一个只含小写字母的字符串 $s$。

对于一个长度为 $x$ 的只含小写字母的字符串 $t$，我们定义 $t$ 的『上一个字符串』是：将所有的长度为 $x$ 且仅含小写字母的字符串按字典序排列后，恰好排在 $t$ 之前一个的字符串。

例如，字符串 $\texttt{bcd}$ 的『上一个字符串』是 $\texttt{bcc}$，而 $\texttt{aaa}$ 的『上一个字符串』不存在。

现在，扶苏有 $q$ 次询问，每次询问给出一个区间 $[l, r]$，查询：$s$ 的第 $l$ 个到第 $r$ 个字符组成的字符串的『上一个字符串』是否在 $s$ 中出现？

如果查询区间对应的字符串不存在『上一个字符串』，也算作『上一个字符串』没有在 $s$ 中出现。

inputFormat:
第一行是一个字符串，表示扶苏收到的字符串 $s$。
第二行有一个整数，表示询问的次数 $q$。
接下来 $q$ 行，每行两个整数，表示一次询问的 $l, r$。

outputFormat:
对于每次询问，输出两行，每行一个字符串。
对于每次询问的第一行输出，请输出对应字符串的『上一个字符串』。如果『上一个字符串』不存在，则输出 `NULL`。
对于每次询问的第二行输出，如果对应字符串的『上一个字符串』在 $s$ 中出现了，请输出 `Happy New Year!`，否则请输出 `Happy Chinese New Year!`。

samples:
bcc
Happy New Year!
cbzz
Happy New Year!
a
Happy New Year!
zy
Happy Chinese New Year!
NULL
Happy Chinese New Year!


title: 蓬莱「凯风快晴　−富士火山−」

background:
富士山，被当地人称为「神山」。这是一座休眠火山，最近一次喷发在 $300$ 年前。

向这样的山中投入不死之药，想必会直接喷发吧。如此便理解为什么月岩笠最终抗命。

description:
所谓的山，是一种上细下粗的结构。能不能在「树」里也找到这样的结构呢？

给定一个以 $1$ 为根的大小为 $n$ 的有根树 $T$。你需要找到满足宽度单调不减的**导出子树**中最大的一棵：

- 记该导出子树为 $T_0$，共有 $k$ 层。
- 记 $T_0$ 的根节点的深度为 $1$，计算出 $T_0$ 中每个结点的深度 $d_i$。由此定义 $T_0$ 第 $i$ 层的宽度 $w_i$ 为「所有深度为 $i$ 的节点的个数」。
- 你需要使得 $w_i$ 单调不减。即，$w_1\le w_2\le \cdots \le w_k$。

记原树的点集和边集分别为 $V,E$。导出子树是原树的一个**连通块**，它的点集 $V_0\subseteq V$，边集 $E_0$ 是 $E$ 当中所有端点均在 $V_0$ 内的边。导出子树的根，是组成它的所有节点中**在原树内深度最浅的那一个**。$T$ 也可以被认为是自身的一棵导出子树。

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

如图所示，绿色的区域和橙色的区域分别是原树的导出子树。它们的根分别为 $2$ 和 $13$。

**注意**：导出子树的定义略微不同于子树的定义。请不要将两者混淆。

请找到最大的符合条件的导出子树的大小。

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

接下来 $n-1$ 行，每行两个整数 $u,v$，描述树上的一条边。

outputFormat: 输出共一行一个整数，表示最大的符合条件的导出子树的大小。

hint:
### 样例解释

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

如图所示，标灰的节点是两个样例中选出来的导出子树。

- 样例 $1$ 找到的导出子树，每一层的宽度分别为 $\{1,2,3,3\}$。
- 样例 $2$ 找到的导出子树，每一层的宽度分别为 $\{1,2,4,4,5\}$。
### 数据范围及约定

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


title: 「VUSC」Math Game

background:
**upd 2023.1.22**：新增一组 Hack 数据 by @[MCRS_lizi](https://www.luogu.com.cn/user/585805)。

远在哞利坚的 Bessie 也要在新春之际走亲访友！为了打发时间，她常和 Farmer John 玩一个有趣的数字游戏。

description:
Farmer John 有一个集合 $S$，集合初始为 $\{2,3,4,...,N\}$。

对于两个**在集合 $S$ 内的**正整数 $p,q$，我们称它们为「一对好数」当且仅当 $p^k=q(k\ge 2\land k\in\N)$。

我们将每个 $S$ 中的数看成一张**无向图**中的节点，对于每一对「好数」，我们在这两个数间连一条无向边。

Farmer John 会进行 $Q$ 次操作，操作有以下两种：

1. 给出 $x$，询问结点 $x$ 所在的连通块大小。
2. 给出 $x$，从 $S$ 中移除 $x$。**与此同时，无向图中的结点 $x$ 也被移除。**

由于 Bessie 的速度太慢了，她想要你来帮忙。

inputFormat:
第 $1$ 行 $2$ 个正整数，$N,Q$。

接下来 $Q$ 行，每行一个正整数，$op_i,x_i$。
其中，$op_i$ 表示操作的序号。

**数据保证 $x_i$ 在集合 $S$ 中**。

outputFormat: 对于操作 $1$，每行输出一个正整数，表示询问的答案。

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

这是原始无向图（上面一排都是孤点）：
![](https://cdn.luogu.com.cn/upload/image_hosting/utsz04dt.png)

这是进行第一次操作 $2$ 后的无向图（删除了结点 $9$）：
![](https://cdn.luogu.com.cn/upload/image_hosting/wmexc9ks.png)

这是进行第二次操作 $2$ 后的无向图（删除了结点 $2$）：
![](https://cdn.luogu.com.cn/upload/image_hosting/9mi0l18p.png)

---

#### 【数据范围】

全部数据满足：
- $2\le N \le 10^{18}$
- $1\le Q \le 10^6$
- $x_i\in S$
- $op_i \in \{1,2\}$

测试点 $1\sim2$ 另外满足 $2\le N \le 10^5$，$1\le Q \le 10^4$。

测试点 $3\sim4$ 另外满足所有 $x_i=m^{p_i}$，其中 $m$ 为一满足 $m\ge 2 \land m\in \N$ 的**常数**。

测试点 $5\sim10$ 没有额外限制。


title: 「GMOI R2-T1」轴对称

description:
你有一个 $n$ 行 $m$ 列的图片（矩阵），该图片的像素为 $n\times m$。

初始时，所有像素块均为黑色，RGB 是 $(0,0,0)$。每一次操作可以将一个像素块的 RGB 中的一个数字改变。

在每次操作过后，请你输出图片是否左右对称？

左右对称：即对于任何的 $i,j$，总满足第 $i$ 行第 $j$ 列的像素与第 $i$ 行第 $m-j+1$ 列的像素的 RGB 值相等。

inputFormat:
第一行三个整数 $n,m,q$，$q$ 代表操作次数。

接下来 $q$ 行，每行输入四个整数 $i,j,t,c$，表示将第 $i$ 行第 $j$ 列的格子的 RGB 值的第 $t$ 个数增加 $c$，任何一个 RGB 值的任何一个数如果超出 $255$ 则自动对 $256$ 取模。

outputFormat: 每次操作过后，如果图片左右对称，输出 `Yes`，否则输出 `No`。每组询问的输出之间用换行隔开。


title: [语言月赛202302] 听见下雨的声音

background:
>还记得，那个下午，窗外下起了细雨。
>正在初赛考试的我，听到了街上嬉戏的孩童，听到了飞驰而过的汽车。
>我想，我听见了下雨的声音。

---

这是一道**笔试**题，你需要完成下面的几道试题，并提交答案。

你的程序需要读入一个整数 $T(1 \le T \le 5)$ 代表试题题号，并输出对应试题的答案。

description:
### 试题 1

二进制数 $00101100$ 和 $00010101$ 的和为

A. $00101000$
B. $01000001$
C. $01000100$
D. $00111000$

### 试题 2

下列四组字符串中都可以用作 C++ 语言的变量名的是

A. `print`  `_3d`  `db8`  `aBc`
B. `I\am`  `one_half`  `start$it`  `3pai`
C. `atr_1`  `Cpp`  `pow`  `while`
D. `Pxq`  `My->book`  `line#`  `His.age`

### 试题 3

有 $7$ 个一模一样的七海，放到 $3$ 个一样的包裹中（允许有空包裹），一共有______种放法。

### 试题 4

周末七海和向日创、黑白熊三个人一起想动手做三道菜。七海负责洗菜、向日创负责切菜、黑白熊负责炒菜。假设做每道菜的顺序都是：先洗菜 $10$ 分钟，然后切菜 $10$ 分钟，最后炒菜 $10$ 分钟。那么做一道菜需要 $30$ 分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要______分钟。

### 试题 5

阅读下面的 C++ 程序，写出它的输出结果。

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

inputFormat: 输入一个整数，代表题号。

outputFormat: 输出你的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of problem 1", // 双引号中替换为 试题 1 的答案
        "The answer of problem 2", // 双引号中替换为 试题 2 的答案
        "The answer of problem 3", // 双引号中替换为 试题 3 的答案
        "The answer of problem 4", // 双引号中替换为 试题 4 的答案
        "The answer of problem 5", // 双引号中替换为 试题 5 的答案
    };
    int T;
    cin >> T;
    cout << ans[T - 1] << endl;
    return 0;
}
```


title: [语言月赛202302] 晚秋绝诗

background:
> 在这贫困的年代，诗人何为？
> 可是，你却说，诗人是酒神神圣的祭司，
> 在神圣的黑夜中，他走遍大地。
——荷尔德林

description:
诗人有两个仓库。甲仓库有 $x$ 升啤酒，乙仓库有若干升啤酒，如果甲仓库给予乙仓库 $z$ 升啤酒，那么甲乙两仓库的啤酒体积相等。

现有一辆最多可以运输 $c$ 升啤酒的卡车来运送**乙仓库**的所有啤酒，请问至少要运多少次？

inputFormat:
输入共两行。

输入的第一行，两个正整数 $x, z$。

输入的第二行，一个浮点数 $c$。

outputFormat: 输出一行一个整数，输出要运多少次。

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

对于 $20\%$ 的测试数据，保证 $z = 0$；
对于 $30\%$ 的测试数据，保证 $c$ 是整数；
对于 $100\%$ 的测试数据，满足 $0 \leq z \leq 10^{12}$，$2z < x \leq 10^{18}$，$1 \leq c \leq 10^{18}$。


title: [语言月赛202302] 风神瞳

description:
你正在帮助他们设计一款象棋软件。现在，你想要设计一个逻辑功能。以下是对这个功能的介绍。

想象一个无限大的棋盘，我们用 $(x, y)$ 表示棋盘的第 $x$ 行第 $y$ 列。具体的，如果说一个棋子在 $(x, y)$ 位置，那么这个棋子则在棋盘的第 $x$ 行第 $y$ 列。

现在有四种棋子**车、炮、马、象**。它们对应的**编号**及它们的**吃棋子规则**如下表所示。以下规则均假设当前棋子在 $(x, y)$ 位置。

**请注意，以下规则可能与真实的中国象棋规则略有不同。**

| 名称 | 编号 | 走法规则 |
| :----------: | :----------: | :----------: |
| 车 | $1$ | 可沿横线或者竖线移动，即一次操作可以吃掉 $(x + k, y), (x - k, y), (x, y + k), (x, y - k)$ 中的任意一个位置的棋子（$k$ 为任意正整数）。 |
| 炮 | $2$ | 想象一条直线，炮与对方棋子都在这条直线上。那么只有在这条直线上的炮与对方棋子的中间**有一个另外的棋子**时，炮才能吃掉对方。 |
| 马 | $3$ | 马走日，即一次操作可以吃掉 $(x + 2, y + 1), (x + 2, y - 1), (x - 2, y + 1), (x - 2, y - 1), (x + 1, y + 2), (x + 1, y - 2), (x - 1, y + 2), (x - 1, y - 2)$ 中的任意一个位置的棋子。 |
| 象 | $4$ | 象走田，即一次操作可以吃掉 $(x + 2, y + 2), (x + 2, y - 2), (x - 2, y + 2), (x - 2, y - 2)$ 中的任何一个位置的棋子。 |

现在你得到了一组询问，包含 $p, x _ 0, y _ 0, x _ 1, y _ 1$ 五个整数，代表现在棋盘上**只有**两个棋子，第一个棋子编号为 $p$，在第 $x _ 0$ 行，第 $y _ 0$ 列。第二个棋子编号未知且不需要了解，在第 $x _ 1$ 行，第 $y _ 1$ 列。

你需要考虑，如果你现在可以且仅可以操作第一个棋子**一次**，第一个棋子能否吃掉第二个棋子。

inputFormat:
输入共一行。

第一行为五个整数 $p, x _ 0, y _ 0, x _ 1, y _ 1$，两两之间以一个空格隔开，同题面中的含义。

outputFormat: 输出一行，如果第一个棋子可以吃掉第二个棋子，输出 `Yes`，否则输出 `No`。

hint:
### 样例解释

样例组 #1 与 #2 代表了车能够与不能够吃掉对方棋子的情况。

样例组 #3 代表了炮不能够吃掉对方棋子的情况。

样例组 #4 代表了马能够吃掉对方棋子的情况。

<https://www.luogu.com.cn/paste/et767k4o> 中含有所有样例的棋子摆放情况，可以按需查阅。

### 数据规模与约定

对于 $20\%$ 的数据，保证 $p = 2$；
对于 $100\%$ 的数据，保证 $p \in \{1, 2, 3, 4\}$，$1 \leq x _ 0, y _ 0, x _ 1, y _ 1 \leq 10 ^ 9$，且保证不存在 $x _ 0$ 与 $x _ 1$、$y _ 0$ 与 $y _ 1$ 同时相等的情况，即两个棋子不会重合。


title: [语言月赛202302] 神树大人挥动魔杖

description:
神树大人挥动魔杖，召唤出了 $9 \times 10^{n-1}$（即 $9 ~ \underbrace{000 \cdots 0000} _ \text{n - 1 个 0}$）只家养小精灵。每只家养小精灵都有一个互不相同的 $n$ 位数编号 $a_i$，编号依次为 $1\underbrace{000 \cdots 0000} _ \text{n - 1 个 0} \sim \underbrace{9999 \cdots 9999} _ \text{n 个 9}$。

例如，一位数为 $1 \sim 9$，三位数为 $100 \sim 999$。

神树大人希望将这些家养小精灵分为 $k$ 组。第 $p$ 组的所有家养小精灵满足编号 **$a_i$ 除以 $k$ 的余数为 $p-1$**。例如，$a_i = 101, k = 4$，那么 $a_i$ 对 $k$ 取模的值为 $1$，应当被分入第 $2$ 组。

神树大人想要知道，每一组小精灵分别有多少只。

inputFormat: 输入共一行两个整数，依次为 $n,k$。

outputFormat: 输出一行 $k$ 个整数，由空格分隔。第 $i$ 个整数代表第 $i$ 组小精灵的个数。

hint:
### 样例解释

给定的小精灵编号依次为 $100 \sim 999$。

不难发现，每个编号除以 $10$ 的余数就是这个编号的个位数。

所以按照个位数是 $0 \sim 9$ 对编号进行分类，每种个位数对应的编号各有 $90$ 个。

### 数据规模与约定

对于 $20\%$ 的数据，$n = 1$；
对于 $100\%$ 的数据，$1 \le n \le 8$，$1 \le k \le 10$。


title: [语言月赛202302] 破碎的历史

description:
某 E 设计了一款抽卡模拟器，她希望能够抽到最好的卡片 CARD。

这款抽卡模拟器将在第 $5$ 次抽取保底。也就是说，如果前 $4$ 次抽取都没有抽中卡片 CARD，第 $5$ 次一定能够抽中卡片 CARD。

某 E 希望你设定第 $1$ 次至第 $4$ 次抽取抽中的概率 $p_1,p_2,p_3,p_4$，使得最后保底的概率为 $S$。

$p_1,p_2,p_3,p_4$ 应当在 $[0,1]$ 范围内，且精确到小数点后两位，如 $0.12$。

容易发现，$S = (1-p_1)\cdot(1-p_2)\cdot(1-p_3)\cdot(1-p_4)$。

某 E 想要知道一共有多少设置的方案。

inputFormat: 输入一行一个浮点数 $S$，$S$ 精确到小数点后 $8$ 位。

outputFormat: 输出一行一个整数，代表方案数。


title: 「DROI」Round 1 下坠

background: 下坠是有终点的吗？

description:
$f$ 是定义在 $\mathbb{N^+}$ 上的函数。

我们令 $a_i$ 表示 $x$ 从低到高第 $i$ 位，那么 $f(x)= \prod_{i=1}^{len} (a_i+1)$（$len$ 表示 $x$ 的位数）。

如果对于一个数 $x$，存在 $y$ 使得 $f(y)=x$，那我们称 $x$ 是下坠数。

现在有 $Q$ 次询问，每次询问会给出一个正整数 $k$。

令 $x$ 表示所有下坠数中第 $k$ 小的下坠数，那么请你找到一个**最小的** $y$，使得 $f(y)=x$。若不存在一个 $y \in [1,10^{18}]$ 满足条件，则输出 $-1$。

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

接下输入一行 $Q$ 个数，第 $i$ 个数表示第 $i$ 次询问的 $k$。

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

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

注意到 $f$ 的定义域是 $\mathbb{N^+}$，所以 $1$ 不是下坠数。则前三个下坠数分别为 $2,3,4$，对应的 $y$ 值则为 $1,2,3$。

------------

#### 样例解释 #2

第 $9$ 和 $14$ 个下坠数分别为 $10$ 和 $18$，其对应的 $y$ 值则为 $9$ 和 $18$。可以证明，第 $46666666$ 个下坠数对应的 $y > 10^{18}$。

------------

#### 数据范围

对于 $100\%$ 的数据满足：$Q \leq 10^5$，$k \leq 5 \times 10^7$。

其中对于 $10\%$ 的数据满足：$k \leq 100$。

对于 $30\%$ 的数据满足：$k \leq 5 \times 10^3$。

对于另外 $20\%$ 的数据满足：对于所有被询问到的下坠数 $x$，都有 $\vert x-y \vert \leq 100$ 或者 $y > 10^{18}$。

**请注意不同寻常的时间限制。**


title: [语言月赛202302] 对了，还有花，少女，银河

background:
扶苏是洛谷网校的一名讲师，她负责了一场[基础-提高衔接计划](https://class.luogu.com.cn/course/yugu23xja)全真模拟赛。

在全真模拟赛里，需要选手在本地完成代码后按照真实比赛的要求放入以题目名命名的子目录（子文件夹）中，子文件夹的上级文件必须是用考号命名的文件夹。再把用考号命名的文件夹打成 zip。

例如，如果一道题目的名字叫做 `ovo`，那么源程序必须命名为 `ovo.cpp`。如果选手考号为 `SD-114`，那么从 zip 起本题的目录结构必须为：

```SD-114.zip/SD-114/ovo/ovo.cpp```

这里 `/` 符号表示的是两级目录之间的间隔。

如果该选手的目录结构变成了 ```SD-114.zip/SD-114/SD-114/ovo/ovo.cpp```（也就是套了两层用考号名命名的文件夹），将无法正常评测。

description:
但是，扶苏生气地发现，即使在前一天晚上已经在群里强调了多次如何打包，并且通过测试赛指出了提交文件目录有问题的选手，但在全真模拟赛时仍有大量同学的目录结构出现问题。

一共有 $n$ 名选手参加全真模拟赛，模拟赛共 $m$ 道题。给出每道题的名字和每个选手每份源程序的目录结构，请你对于每个选手的每份源程序，判定 ta 的源程序目录是否正确。

选手的错误五花八门，包括但不限于：源程序名写错、考号写错、文件夹套多等等问题。为了方便起见，我们约定对于考号为 `X` 的选手的题目 `Y`，`X.zip/X/Y/Y.cpp` 是**唯一正确**的目录结构，其余**结构均为错误结构**。

注意：同一选手不同题目的上级目录可能是不同的，也可能一个正确一个错误。

inputFormat:
第一行是两个整数，依次表示参赛选手数 $n$ 和题目数 $m$。
接下来 $m$ 行，每行一个字符串 $s_i$，表示一道题目的名字。
接下来 $(m+1) \times n$ 行，每 $(m+1)$ 行一组表示一名选手的所有题目的目录结构：
每组第一行是一个字符串 $t_i$，表示该选手的考号。
接下来 $m$ 行，每行一个字符串 $r_i$，按题目顺序给出该选手每道题目的目录结构。

outputFormat: 按输入顺序，对每个选手的每个目录结构，输出一行一个字符串，如果该选手的目录结构正确，输出 `Fusu is happy!`，否则输出 `Fusu is angry!`。

samples:
4 2
ovo
vov
SD-114
SD-114.zip/SD-114/ovo/ovo.cpp
SD-114.zip/SD114/vov/vov.cpp
LG-514
LG-514.zip/lg-514/ovo/ovo.cpp
LG-514.zip/LG-514/vov/ovo.cpp
PJ-998
PJ-998.zip/PJ-998/PJ-998/ovo/ovo.cpp
PJ-998/PJ-998/vov/vov.cpp
fusu
fusu.zip/fusu/ovo/ovo.cpp
fusu.zip/fusu/ovo/vov.cpp

samples:
Fusu is happy!
Fusu is angry!
Fusu is angry!
Fusu is angry!
Fusu is angry!
Fusu is angry!
Fusu is happy!
Fusu is angry!

hint:
### 样例 1 解释

共有 $4$ 位选手，$2$ 道题目。两道题目分别是 `ovo` 和 `vov`。

- 第一位选手的准考证号是 `SD-114`。
- + 他的第一题目录完全正确。
- + 他第二题的第二级目录（SD114 文件夹）没有加中间的 `-` 符号，与准考证号不一致，故错误。
- 第二位选手的准考证号是 `LG-514`。
- + 他第一题的第二级目录使用了小写字母，错误。
- + 他第二题的源程序名写成了 `ovo.cpp`，应该是 `vov.cpp`，错误
- 第三位选手的准考证号是 `PJ-998`。
- + 他第一题的的准考证号目录套了两层（即有两个 `PJ-998`），故错误。
- + 他第二题没有打 zip 包（第一级目录没有 `.zip` 后缀），故错误
- 第四位选手的准考证号是 `fusu`。
- + 她第一题的目录完全正确。
- + 她第二题的子目录（第三级目录）写成了 `ovo`，因该是 `vov`，故错误。

### 数据规模与约定

- 对 $30\%$ 的数据，$n = 1$。
- 另有 $30\%$ 的数据，$m = 1$。
- 对 $100\%$ 的数据，$1 \leq n,m\leq 10$，$s_i$ 和 $t_i$ 的长度均不超过 $20$，$r_i$ 的长度不超过 $500$。字符串均只含大小写字母、数字和 `-`，`.` 与 `/` 符号。保证题目名和准考证号不含 `/` 符号。


title: [入门赛 #9] 牵连的世界 (Hard Version)

background:
这是一道 **hack 题**。在此类型的题目中，你将得到若干个问题和若干个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于每个问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

---
**提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言**

description:
以下给出三个问题的题目描述：

#### 问题 1

给出 $n$ 个整数，求其中奇数的个数。

#### 问题 2

判定 $p$ 是否为质数。

#### 问题 3

给出 $n$ 个整数，第 $i$ 个为 $a_i$。找到最大的数 $p$，使得满足 $a_i \ge p$ 的 $i$ 个数不小于 $\lfloor \dfrac{n}{2} \rfloor$。

inputFormat:
#### 问题 1

输入包含两行。
第一行是一个整数，表示数列长度 $n$。
第二行有 $n$ 个以单个空格隔开的整数，依次表示 $a_1, a_2, \dots a_n$。

#### 问题 2

输入包含一行一个整数 $p$。

#### 问题 3

输入包含两行。
第一行是一个整数，表示数列长度 $n$。
第二行有 $n$ 个以单个空格隔开的整数，依次表示 $a_1, a_2, \dots a_n$。

outputFormat:
#### 问题 1

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

#### 问题 2

输出一行，若 $p$ 为质数，输出 `Yes`；否则输出 `No`。

#### 问题 3

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

hint:
### 样例组与实际输入的说明

三个样例分别对应三个问题的样例输入输出。

如果你直接采用『提交答案』的方式，请分别将三个输入数据命名为 `1.in`、`2.in`、`3.in`，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器可以从标准输入读入一个整数 $x$，满足 $1 \leq x \leq 3$，表示该测试点对应的问题编号，然后**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对三个问题的样例说明。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有行末空格和文末回车。
2. 数据中所有的数字都应为整数。
3. 对于问题 1，$1 \leq n \leq 1000, -2 \times 10^9 \le a_i \le 2 \times 10^9$。
4. 对于问题 2，$1 \le p \le 10^{12}$。
5. 对于问题 3，$2 \leq n \leq 100$，$1 \leq a_i \leq 2 \times 10^9$。

### 目标代码

你需要 hack 如下的代码：

#### 问题 1

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, ans = 0;
  cin >> n;
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    if(x % 2 == 1) ++ans;
  }
  cout << ans << endl;
}
```

#### 问题 2

```cpp
#include<bits/stdc++.h>
using namespace std;

bool isprime(long long x) {
    if(x == 1) return false;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    long long p;
    cin >> p;
    if(isprime(p)) cout << "Yes" << endl;
    else cout << "No";
    return 0;
}
```

#### 问题 3

```cpp
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000 + 7;

int n, a[MAXN];

bool check(int x) {
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] >= x) ++tot;
    }
    return (tot >= (n / 2));
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int L = 1, R = 2000000000, ans;
    while(L <= R) {
        int mid = (L + R) / 2;
        if(check(mid)) ans = mid, L = mid + 1;
        else R = mid - 1;
    }
    cout << ans << endl;
    return 0;
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

### 判分说明

本题共三个测试点，分别对应三个问题，测试点分值依次为 $30$分、$30$ 分、$40$ 分。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 Unaccepted 的结果。

#### 超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

#### 结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和**完全正确的输出**，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

#### 未定义行为判定

我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

### 样例程序

这是一份可以帮你理解你需要输出的内容的样例程序，**但它不能给出正确的 hack 数据**。直接提交此程序不会得分。

```cpp
#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "" <<endl;
  } else if (taskId == 2) {
    cout << "" << endl;
  } else if (taskId == 3) {
    cout << "" << endl;
  } else { // 这个 else 不会被执行
    cout << "QiHai Nanami" << endl;
  }
}
```

如果你使用『提交答案』功能，请务必保证打开压缩包后能且仅能**直接**看到三个 `.in` 文件。这就是说，文件结构必须是：

```plain
ans.zip
 |---1.in
 |---2.in
 |---3.in
```

三个文件不应该被额外的文件夹包含，即文件结构不能是：

```plain
ans.zip
 |---ans(folder)
      |---1.in
      |---2.in
      |---3.in
```

### 关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。


title: [语言月赛202301] HACK IT!

background:
这是一道 **hack 题**。在此类型的题目中，你将得到若干个问题和若干个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于每个问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

description:
以下给出三个问题的题目描述：

#### 问题 1

给定两个整数 $a, b$，请求出 $a + b$ 的值。

#### 问题 2

给定一个仅包含小写字母的字符串 $s$，求 $s$ 中有多少个小写 `a` 字母。

#### 问题 3

给定一个长度为 $n$ 的数组 $a$（下标从 $0$ 开始），对所有的 $i$ 满足 $0 \leq i < n$，设 $b_i = a_{i + 1 \bmod n} - a_i$，这里 $i + 1 \bmod n$ 表示 $i + 1$ 对 $n$ 取模的结果。请求出 $b$ 数组。

inputFormat:
#### 问题 1

输入包含一行两个整数，用单个空格隔开，依次表示 $a$ 和 $b$。

#### 问题 2

输入包含一行一个字符串 $s$。

#### 问题 3

输入包含两行。
第一行是一个整数，表示数列长度 $n$。
第二行有 $n$ 个以单个空格隔开的整数，依次表示 $a_1, a_2, \dots a_n$。

outputFormat:
#### 问题 1

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

#### 问题 2

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

#### 问题 3

输出一行 $n$ 个整数，依次表示 $b_0, b_1, \dots b_{n - 1}$。整数之间用单个空格隔开。

hint:
### 样例组与实际输入的说明

三个样例分别对应三个问题的样例输入输出。

如果你直接采用『提交答案』的方式，请分别将三个输入数据命名为 `1.in`、`2.in`、`3.in`，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器可以从标准输入读入一个整数 $x$，满足 $1 \leq x \leq 3$，表示该测试点对应的问题编号，然后**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『输出格式』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对三个问题的样例说明。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有行末空格和文末回车。
2. 对于问题 1，$1 \leq a, b \leq 2 \times 10^9$。
3. 对于问题 2，$s$ 只含小写英文字母，其对应的 ASCII 值应在 $[97, 122]$ 范围内，$s$ 的长度应 $\geq 1$ 且不超过 $10 ^ 6$。
4. 对于问题 3，$1 \leq n \leq 100$，$-10^9 \leq a_i \leq 10^9$。

### 目标代码

你需要 hack 如下的代码：

#### 问题 1

```cpp
#include <iostream>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  cout << a + b << endl;
}
```

#### 问题 2

```cpp
#include <cstring>
#include <iostream>

using namespace std;

char s[1000005];

int main() {
    cin >> s;
    int ans = 0;
    for (int i = 0; i < strlen(s); ++i) {
        if (s[i] == 'a')
            ++ans;
    }
    cout << ans << endl;
    return 0;
}
```

#### 问题 3

```cpp
#include <iostream>

using namespace std;

const int maxn = 100;

int a[maxn], b[maxn];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) {
    b[i] = a[i + 1] - a[i];
    if (i + 1 == n)
      b[i] = a[0] - a[i];
  }
  for (int i = 0; i < n; ++i) {
    cout << b[i] << " \n"[i == (n - 1)];
  }
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

### 判分说明

本题共三个测试点，分别对应三个问题，每个测试点 10 分。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 unaccepted 的结果。

#### 超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

#### 结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和**完全正确的输出**，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

#### 未定义行为判定

我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

### 样例程序

这是一份可以帮你理解你需要输出的内容的样例程序，**但它不能给出正确的 hack 数据**。直接提交此程序不会得分。

```cpp
#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "1 1" <<endl;
  } else if (taskId == 2) {
    cout << "aba" << endl;
  } else if (taskId == 3) {
    cout << "2\n1 1" << endl;
  } else { // 这个 else 不会被执行
    cout << "OvoOvoovOovO" << endl;
  }
}
```

如果你使用『提交答案』功能，请务必保证打开压缩包后能且仅能**直接**看到三个 `.in` 文件。这就是说，文件结构必须是：

```plain
ans.zip
 |---1.in
 |---2.in
 |---3.in
```

三个文件不应该被额外的文件夹包含，即文件结构不能是：

```plain
ans.zip
 |---ans(folder)
      |---1.in
      |---2.in
      |---3.in
```

### 关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。

### 关于本题的特殊说明

本题是第一道 hack 题，也是试机题。此类型题目的初衷是使得选手可以有针对性地练习代码里的易错点。在『洛谷入门赛 #8』结束后的一周内，你可以任意地尝试攻击 special judge 而不会受到处罚（恶意卡评测、重复提交除外）。被允许的攻击行为包括但不限于尝试提交各种输入数据以期让 special judge 返回错误的结果。如果攻击产生了成果，请在讨论区发帖并 at 一扶苏一。

**特别提醒：恶意卡评测的行为包括多次提交导致给出程序运行超时的且无本质区别的数据**。

需要说明的是，在乐多赛制下，多次尝试提交会造成本题得分降低。


title: 「VUSC」Card Tricks

background:
**upd 2023.1.17 数据已加强。**

**upd 2023.10.18 空间限制调整为 100 MiB。**

Bessie 正在玩一场卡牌游戏！

这个游戏有一些~~神秘的~~规则。Bessie 需要用一些编程技巧，加快计算。

description:
牌堆可以看成一个长度为 $N$ 的数列，下标为 $i$ 的位置值为 $a_i$。$(1\le i\le N)$

有 $Q$ 次操作，每次操作给定 $l_i,r_i,v_i$，$\forall l_i\le j \le r_i,a_j\gets a_j \lor v_i$。

其中 $\lor$ 表示按位或操作，即 C++ 中的 `|`。

对于 $i=1,2,\dots,N$，求出在哪一次操作后，$a_i$ **首次严格大于** $P$，其中 $P$ 为一给定常数。

数据保证在初始情况下，$P\ge\max\{a_i\}$。

inputFormat:
第一行三个整数 $N,Q,P$。

第二行 $N$ 个整数，第 $i$ 个数为 $a_i$ 的初始值。

接下来 $Q$ 行，每行三个整数，$l_i,r_i,v_i$。

outputFormat:
输出 $N$ 个数 $id_1,id_2,\dots,id_N$，第 $i$ 个数表示在第 $id_i$ 次操作后，$a_i$ 首次严格大于 $P$。

**如果 $a_i$ 始终小于等于 $P$，请在这一位输出 $-1$。**

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

第一次操作后的数列为 $1,2,3,4,5$。

第二次操作后的数列为 $11,2,3,4,5$。

第三次操作后的数列为 $11,6,7,4,5$。

……

最终的数列为 $11,14,15,4,23$。

---

#### 数据范围
全部数据满足：$1\le N,Q \le 10^6$，$1\le l_i\le r_i \le N$，$1\le a_i,v_i,P\le 10^9$。

测试点 $1\sim2$ 另满足 $1\le N,Q\le 10^3$。

测试点 $3$ 另满足 $l_i=r_i$。

测试点 $4$ 另满足 $l_i=1,r_i=N$。

测试点 $5\sim10$ 无额外限制。

**本题数据规模较大，请注意常数优化。**


title: 「WHOI-4」加减法构造

description:
小 W 给了你一个长度为 $n$ 的**整数**数组 $x$。你需要构造一个长度也为 $n$ 的**整数**数组 $y$，并满足：

1. $\forall 1\le i,j,i+j\le n,y_{i+j}=y_i+y_j+k$，$k$ 是一个你需要钦定的整数。
3. $d(x,y)=\sum\limits_{i=1}^n|x_i-y_i|$ 最小。
3. $-V\le y_i\le V$，$V$ 是输入中给定的数。

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

接下来一行 $n$ 个整数，第 $i$ 个代表 $x_i$。

outputFormat:
第一行两个整数 $k,d$，代表你钦定的值和你的答案。

接下来一行 $n$ 个整数，第 $i$ 个代表 $y_i$。

题目保证 $d$ 的最小值在 `long long` 范围内。

hint:
**数据范围**

- Subtask 1（$20$ pts）：$n\le10$，$ V\le10$，$ |x_i|\le10$；
- Subtask 2（$20$ pts）：$n\le100$，$ |x_i|\le100$，$V\le1000$；
- Subtask 3（$20$ pts）：$n\le10^6$，$ |x_i|\le10^6$，$V=10^{12}$；
- Subtask 4（$20$ pts）：$n\le10^7$，$|x_i|\le10^7$，$V\le10^7$;
- Subtask 5（$20$ pts）：$n\le10^7$，$|x_i|\le10^7$，$V\le 10^{12}$。

对于所有数据，保证 $1\le n\le 10^7$，$|x_i|\le10^7$，$1\le V\le10^{12}$。

**关于 Special Judge 的说明**

对于每个测试点：

如果你输出的格式不正确，你将会获得 $0$ 分。

如果你输出的数中有不在 $[-V,V]$ 范围的数，你将会获得 $0$ 分。

如果你的数列 $y$ 不符合你输出的 $k$，你将会获得 $0$ 分。

如果你的数列 $y$ 不符合你输出的 $d$，你将会获得 $0$ 分。

否则你将会获得的分数为该测试点总分的百分之 $\max\{0,\min\{100,10100-\frac{10000d}{d'}\}\}$，$d'$ 是答案的 $d$ 值。


title: 『GROI-R1』 虹色的彼岸花

background:
少年身着春季校服的深灰色外套与黑色短裤，外套内是白净的衬衫。

他的右手不知为何缠着绷带，右眼用头发挡得严严实实，扑面而来的是一种神秘感。

一瓣鲜红的彼岸花，在教室上空无人在意之处打旋。

玘的身世，总是一个谜题吧。

「所以你到底是什么人，又为什么要来这里！」

可是彼岸花显然不想让你知道这些。

description:
玘给了寒一棵编号为 $1\sim n$ 的树，这棵树上每个点都有一个点权，同时有些边有边权，有些边没有边权。可是玘把每一个点的点权删除了。寒只知道****点权都是整数，而且在 $l$ 和 $r$ 之间（包含端点）****。而且，点权和边权有着下面的特殊关系：

- 对于****有边权****的边，要求****连接的两个点的点权和为边权****。

- 对于****没有边权的边****，****无限制****。

玘问寒这棵树****有多少种不同的点权填写方式****。两种填写方式不同，当且仅当至少存在一个点的点权不同。可是寒不会做这个题。

寒请你解决这个问题。

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

第一行一个整数 $T$，代表测试数据组数。

对于每一组测试数据：

第一行三个整数 $n,l,r$，代表树上点的个数是 $n$，点权的范围是 $[l,r]$。

接下来 $n-1$ 行，每行先输入一个整数 $op$，$op=0$ 表示这条边没有边权，$op=1$ 表示这条边有边权。

+ 如果 $op=0$，再输入两个整数 $u,v$，表示这条边连接 $u,v$ 两个点。

+ 如果 $op=1$，再输入三个整数 $u,v,w$，表示有一条权值为 $w$ 的边连接 $u,v$ 两个点。

outputFormat: 对于每个测试点，输出一行一个整数，代表点权填写方式的个数。答案对 $10^9+7$ 取模。


title: 『GROI-R1』 一切都已过去

background:
悦关上窗，拉上帘布。

果然还是想不起来啊。

隐约记得曾和什么人一起做过这样的事。

仰面躺下，手执一只木笺。

「究竟如何，才能拥有“过去”啊……」

她闭上双眼。

「6 岁前的记忆……究竟如何才能寻回？」

description:
悦正在寻找她的记忆。忽然，她来到了有 $n$ 个节点的一棵树上。树上每一条边都有各自边权，每一个点都有各自的点权。

「把经历都聚拢起来，能完整地复原吗……」

悦从树上的一个点，慢慢地走到了另一个点，可是她什么也没找到。但是，她不知道，玘一直在远处望着她走过的道路。

玘发现，悦全程****没有走回头路****。他想把悦****走过的每一条边的边权乘起来****，可惜他发现他遇到了一个这一生未曾见到过的数字。

「为什么会这样呢？」

玘想到悦是突然出现在树上的，最初的点一定有蹊跷！他****把最初那个点的点权乘上****……

突然，一束彼岸花的红光亮起！世界重新安静了下来。

悦看到了玘留下的字样，可惜她不能从中看出任何过去的记忆。现在，你要帮她判断：把经历都聚拢起来，****能完整地复原过去吗****？我们称悦的一条路径能“复原过去”，当且仅当玘****留下的乘积是一个整数****。

**形式化题面**

给定一棵 $n$ 个节点的树和 $q$ 次询问。每次询问给出两个整数 $x,y$，表示询问树上以 $x$ 和 $y$ 为端点的简单路径上边权乘积与点 $x$ 的点权相乘是否为整数。

inputFormat:
第一行两个正整数 $n$ 和 $q$，表示树上有 $n$ 个节点编号为 $1\sim n$，悦在树上走了 $q$ 条路径。

接下来一行 $n$ 个非负整数表示每个点的点权 $a_i$。

接下来 $n-1$ 行每行两个正整数 $u,v$ 和一个非负实数 $w$ 表示 $u,v$ 间有一条边权为 $w$ 的边。

接下来 $q$ 行，每行两个正整数 $x,y$，表示悦从点 $x$ 开始走到了点 $y$。

outputFormat: 对于悦的每一次询问，你需要输出一行一个字符串。如果悦能够成功复原她的过去，请输出 `Yes`，否则请输出 `No`。


title: 『GROI-R1』 湖底之城

background:
那年你我仍是无瑕的少年

在夜晚安逸的后院无所顾忌地笑谈人生

——怀念这样毫无猜忌的时光

description:
悦，玲和荧三个人在湖底之城闲游。湖底之城的道路错综复杂，形成了一棵有 $n$ 个节点的树。

她们三人的手上都有一个计数器，初始都为 $0$。她们每走到一个点的时候，**悦和荧**手上的计数器会自动加上刚刚经过的**这条边的边权**，同时**玲**的计数器会恰好**增加 $1$**。同时，她们整个过程中**没有经过某个点超过一次**。

由于她们的计数器不能存储很大的值，所以，当**玲**的计数器上的值是「湖之数」$p$ 的**倍数**时，**悦可以**将她的计数器上的值减去**荧**的计数器上的值，接下来，**玲和荧**的计数器都会立刻**归零**。

玘现在不知道她们闲游的起点和终点，所以天生计算能力很好的玘对于每一对起点和终点，计算出了悦手上计数器在终点时可能出现的最小值。玘把这个值记作 $f(u,v)$，意思是她们从点 $u$ 走到了点 $v$。可是，玘认为，没有红色彼岸花的寒，一定是算不出来这些答案的。所以，他让寒做一道更简单的题。玘给寒一个长度为 $m$ 的序列 $s$，让寒对于每一个点为 $u$ 时计算 $\min\limits_{i=1}^m\{f(s_i,u)\}$。

**形式化题面**

给定一个 $n$ 个点的树 $(V,E)$ 和一个正整数 $p$，每一条边有一个整数边权 $w_i$。

我们定义 $f(s,v)$ 表示为对 $u,a,b,c$ 进行若干次**拓展**后可以得到的当 $u=v$ 时的 $a$ 的最小值，其中最开始 $u\gets s$ 同时 $a,b,c\gets0$。

**拓展**的定义为依次进行如下操作：

- 选择任意一条边 $(u',v,w)\in E$ 满足 $u=u'$，令 $u\gets v,a\gets a+w,b\gets b+1,c\gets c+w$；

- 如果 $p\mid b$，你****可以****令 $a\gets a-c,b\gets 0,c\gets0$。

特别地，对于每一次**拓展**，你**不能**取一个之前取过的点。

给定序列 $\{s_m\}$，对于每个点 $u$ 求 $\min\limits_{i=1}^m\{f(s_i,u)\}$。

inputFormat:
第一行三个整数 $n,m,p$，表示树的节点数为 $n$，编号分别为 $1\sim n$，「湖之数」为 $p$，序列 $s$ 的长度为 $m$。

接下来 $n-1$ 行每行三个整数 $u,v,w$ 表示存在一条连接 $u,v$ 两个点，边权为 $w$ 的边。

接下来一行 $m$ 个整数表示 $s_{1\sim m}$ 即 $m$ 个起点。

outputFormat: 设 $ans_u=\min\limits_{i=1}^m\{f(s_i,u)\}$，那么你需要输出 $\text{xor}_{i=1}^n |ans_i|$。其中 $|a|$ 表示 $a$ 的绝对值。


title: 『GROI-R1』 古朴而优雅

background:
会馆内忽地安静了下来。

「敝姓言，名杉。」

他的声音沉稳而凝重，略带沙哑，却不失力度，极具穿透力。每个字都重重地打在耳畔，渗进头脑里，让人想不认真听都难。

「这所学院的院长。」

description:
杉虽然年事已高，但是还是保持与时俱进。他学习了深度优先遍历算法，觉得这种新潮的东西在一所古朴而优雅的学院里会很受欢迎。所以，他找到了在走廊里晃荡的寒，向他提出了一个问题：

「我们知道，对一棵树进行深度优先遍历可以用下面的伪代码很好地解决。」

$$
\begin{array}{l}
\text{DFS-TREE}(u)\\
\begin{array}{ll}
1 & p\gets p+1\\
2 & t_p\gets u\\
3 & vis_u\gets 1\\
4 & \textbf{for }\text{each edge }(u,v)\in E \\
5 & \qquad \textbf{if }vis_v=0\\
6 & \qquad \qquad \text{DFS-TREE}(v)\\
7 & p\gets p+1\\
8 & t_p\gets u\\
\end{array}
\end{array}
$$

起初，所有变量或数组的值均为 $0$。

「我们把调用 $\text{DFS-TREE}(1)$ 在遍历过程中得到的数组 $t$ 称为这棵树的**遍历顺序**。」

「你看这段代码的第 $4$ 行，这句话**遍历每一条边的顺序是不固定的**。」

寒素来最讨厌不确定的东西，可是碍于院长的颜面，还是继续听下去。

「你能数出这段代码**会生成多少种不同的遍历顺序**吗？」

寒发现他曾经做过这个题，很快地报出了解法。本以为就结束了，可是杉继续说：

「如果我**在树上增加一条边**，你还会做吗？」

寒发现他的那点水平完全不够了，于是他去请教玘。玘却认为这道题目依然很简单，他告诉了寒这道题的做法。可是寒找不到杉了。

这个世界到底怎么了呢？

inputFormat:
第一行，两个整数 $n$ 和 $q$，表示树上有 $n$ 个结点，编号为 $1\sim n$，有 $q$ 次询问。

接下来 $n-1$ 行，每行两个整数 $u,v$，描述这棵树上的一条边。

接下来 $q$ 行，每行两个整数 $x,y$，表示在树上添加连接 $x$ 和 $y$ 的一条边，询问有多少种可能的遍历顺序。注意：每次询问是**互相独立的**，也就是说，上一次询问添加的边不会保留到下一次询问。

outputFormat: 共 $q$ 行，每行一个整数表示这次询问的答案对 $10^9+7$ 取模后得到的值。


title: 『GROI-R1』 继续深潜，为了同一个梦想

background:
玘正在折叠床脚几件刚洗净的白衬衫，他注意到身后的声响，向右后转头看去。

以为是“外面的家伙”的他并没有刻意去遮掩自己的右眼——毕竟学院里的人不可能进来。

他看见了那个紫眸的少年；当然寒也看见了那一瞬间的鲜红。

「你什么都没看见。」

玘装作欣赏窗外的晚霞。

description:
「世上没有无价的情报，」玘露出一丝满意的微笑。

「你懂我的意思吧？」

寒收回手。

玘给出了他留给寒的题。

> 既然紫堇和彼岸花给予了我们异色的瞳孔，我们理所应当是连接在一起的。我称**一棵树上的一个点集是“连接的”**，当且仅当**树上存在一条链能够覆盖这个点集并且这个集合大小不小于 $2$**。我们是独一无二的，可是你知道，一棵树，总是连起来的啊。

「然后呢？」

「现在，你需要告诉我每个点被多少个这样的点集所包含。」

玘飘然而去。

湖底之城那封存已久的记忆，被彼岸花和紫堇的力量，揭开了封印的一角。

inputFormat:
第一行一个正整数 $n$ 表示这棵树有 $n$ 个点编号为 $1\sim n$。

接下来 $n-1$ 行，每行两个正整数 $u,v$ 描述一条边。

outputFormat:
为了防止输出量过大，本题采用以下的输出方式。

设 $ans_i$ 为包含 $i$ 号节点的连接的集合的个数对 $10^9+7$ 取模得到的值，你需要输出 $\operatorname{xor}_{i=1}^n ans_i\times i$ 的值。注意这里没有取模运算。


title: 「DROI」Round 1 失控

background: 失控的，或许反而是理智的。

description:
给定一个 $n \times m$ 的矩阵 $G$ 和两个长度为 $m$ 的排列 $p,q$。

我们称元素 $G_{i,j}$ 是**失控的**，当且仅当 $\vert G_{i,j} - G_{i-1,p_j} \vert > C$ **且** $\vert G_{i,j} - G_{i+1,q_j} \vert > C$，其中 $C$ 是给定的常数。特殊地，我们规定无论如何第 $1$ 行和第 $n$ 行的元素都不是失控的。

此时再给定两个长度为 $k$ 的序列 $A$ 和 $B$。

你将有 $k$ 种操作：其中第 $i$ 种操作是将某一行所有元素增加 $A_i$，这将会花费 $B_i$ 的代价。**每种操作可以使用的次数不限，但对于每一行，你只可以进行这些操作中的一种或不操作。并且，你必须保证任意相邻两行最多有一行进行操作。**

请问要使得矩阵 $G$ 中所有元素均不失控，至少要花费的代价是多少（数据保证有解）？

inputFormat:
第一行四个整数，分别为 $n,m,k,C$。

接下来 $n+4$ 行，前 $n$ 行每行 $m$ 个数，表示矩阵 $G$，第 $n+1$ 和 $n+2$ 行每行 $m$ 个数，分别表示排列 $p$ 和 $q$，最后两行每行 $k$ 个数，分别表示序列 $A$ 和 $B$。

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

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

显然对于样例一，不用进行任何操作就能保证所有元素均不失控。

------------

#### 样例解释 #2

对第三行使用 $3$ 操作，对第七行使用 $4$ 操作即可。可以证明不存在更优的方案。

------------

#### 数据范围

**「本题采用捆绑测试」**

- $\operatorname{Subtask} 1(10\%)$：$n,m,k \leq 8$。

- $\operatorname{Subtask} 2(30\%)$：$m\leq 50,k\leq 100$。

- $\operatorname{Subtask} 3(20\%)$：$m\leq 50,k\leq 1000$。

- $\operatorname{Subtask} 4(40\%)$：无特殊限制。

对于 $100\%$ 的数据满足：$3 \leq n\leq 50$，$1 \leq m \leq 300$，$0 \leq k \leq 2000$，$C,G_{i,j},A_i,B_i \leq 10^6$。

**本题输入量较大，请用较快的输入方法。**

------------

#### 提示

- 本题不卡常，如果你认为自己的算法差一点就能跑过下一个 Subtask 却没有跑过，那么请不要纠结于无意义的卡常，因为差的这一点可能需要更优秀的算法来弥补。


title: 集合运算 3

background:
关于集合、交集、并集的定义请参考 https://www.luogu.com.cn/problem/B3633。

以下给出对称差的定义：

对两个集合 $A, B$，规定 $A$ 和 $B$ 的对称差 $A \Delta B$ 为在 $A$ 中出现但不在 $B$ 中出现，或在 $B$ 中出现但不在 $A$ 中出现的元素。
例如，$A = \{1, 2, 3\}$，$B = \{2, 3, 5\}$，则 $A \Delta B = \{1, 5\}$

description:
给定 $n$ 个集合 $s_1, s_2, \dots s_n$，每个集合都含有 $[1, m]$ 之间的若干个整数。

现在，有 $q$ 次操作，每次操作如下：
- `1 x y`：将 $s_x$ 中的每个元素都加上 $y$，再删去其中大于 $m$ 的；
- `2 x y`：将 $s_x$ 中的每个元素都减去 $y$，再删去其中小于 $1$ 的；
- `3 x y`：查询 $s_x$ 和 $s_y$ 的**交集**的元素个数；
- `4 x y`：查询 $s_x$ 和 $s_y$ 的**并集**的元素个数；
- `5 x y`：查询 $s_x$ 和 $s_y$ 的**对称差**的元素个数；

inputFormat:
第一行有三个数，依次表示集合的个数 $n$，集合元素的最大值 $m$ 和操作次数 $q$。

第 $2$ 到第 $(n + 1)$ 行，每行有若干个整数，第 $(i + 1)$ 行的整数描述集合 $i$ 的元素：
每行首先有一个整数 $c_i$ 表示 $s_i$ 的元素个数，接下来有 $c$ 个互不相同的整数 $s_{i,1}, s_{i,2}, \dots s_{i, c_i}$ 表示集合 $s_i$ 里的元素。

接下来 $q$ 行，每行三个整数 $o, x, y$，表示一次操作。具体见『题目描述』。

outputFormat: 对于每个查询操作，请输出一行一个整数表示答案。

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

对于全部的测试点，保证 $1 \leq n,m,q \leq 3 \times 10^4$，$1 \leq \sum_{i = 1}^n c_i \leq 10^6$，$1 \leq x, y \leq n$，$1 \leq o \leq 5$。集合里的元素都是不超过 $m$ 的正整数。

感谢 @[Zyingyzzz](/user/434929) 提供 hack 数据一组。


title: 『GROI-R2』 记忆碎片

description:
记忆的碎片散落在各个角落，而爱丽丝想把它们拼合在一起。

碎片的顺序是给定的，因为记忆显然不能反过来进行。但是，碎片各自的形状和内容是可以打磨和修正的——毕竟所有人的记忆都会歪曲和遗忘。

每个碎片上的记忆都可以用一个**非负整数**来表示。而相邻的两个碎片能够完整地拼合起来，当且仅当它们记忆的和是一个**完全平方数**。

现在，爱丽丝可以打磨若干块碎片，使得每一对相邻的碎片都能够完整地拼合起来。对于每一次打磨，爱丽丝可以选择一块碎片，将这块碎片上的记忆修改为任意一个**非负整数**。爱丽丝想知道，她至少要打磨多少块碎片，才能实现她的目标。同时，她还希望你给出打磨之后，每块碎片上留有的记忆是多少。

**形式化题面**

给定一个**非负整数**序列 $\{a_n\}$，我们定义一次操作是任意选择一个 $i\in [1,n]$ 并将 $a_i$ 改为任意一个**非负整数** $x$。

问至少进行几次操作才可以满足 $\forall i\in [1,n-1]$ 有 $a_i+a_{i+1}$ 为**完全平方数**，并给出修改方案。

inputFormat:
第一行输入一个整数 $n$，表示记忆碎片的个数。

第二行输入一个长度为 $n$ 的非负整数序列 $a$，表示每个记忆碎片上的记忆。

outputFormat:
第一行输出一个整数，表示最少打磨次数。

第二行输出一个长度为 $n$ 的整数序列，表示所有打磨过后的记忆碎片上的记忆。

你必须保证你打磨后的记忆满足题目条件，且与你给出的最少打磨次数相符，并满足每个碎片上的记忆都在 $[0,10^{18}]$ 的范围内。


title: 「DROI」Round 1 距离

background: 没有什么距离是无法跨越的。

description:
定义一棵树 $G$ 上两点 $u,v$ 之间的距离 $\operatorname{dis}(u,v)$ 为两点之间点的数量。

若对于树上两点 $u,v$，满足 $\forall x \in G,\operatorname{dis}(u,x) \leq \operatorname{dis}(u,v)$ **且** $\operatorname{dis}(v,x) \leq \operatorname{dis}(u,v)$，那么我们称无序点对 $(u,v)$ 为**极远点对**。

同时，树 $G$ 上一点 $x$ 的权值 $v_x$ 定义为：满足两点间最短路径经过 $x$ 的极远点对的数量。

现给定树 $G$，求 $\sum\limits_{x \in G}{v_x^k}$ 对 $998244353$ 取模的值，其中 $k$ 是给定的常数，且 $k \in [1,2]$。

inputFormat:
第一行两个数 $n,k$，分别表示树 $G$ 的点数以及给定的常数。

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

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