title: [入门赛 #10] Hack Problem P

background:
这是一道 **hack 题**。在此类型的题目中，你将得到若干个问题和若干个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于每个问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

---
**提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言**

description:
以下给出三个问题的题目描述：

#### 问题 1

给出两个正整数 $x, y$，保证它们的最小公倍数（$\mathrm{lcm}$）不大于 $10^9$。求它们的最小公倍数。

#### 问题 2

**多组数据**，给定一个长度为 $n$ 的数组 $[a_1, a_2, \dots a_n]$，保证数组单调递增。有 $q$ 次询问，每次给出一个整数 $x$，求数组中有多少数小于等于 $x$。

#### 问题 3

**多组数据**，给定一个长度为 $n$ 的数组 $[a_1, a_2, \dots a_n]$，有 $q$ 次询问，每次给出一个整数 $x$，求数组中有多少数小于等于 $x$。

注：问题 $2$ 和问题 $3$ 除了在是否保证数组递增上有差异外，在数据范围上也有区别，见下。

inputFormat:
#### 问题 1

输入只有一行两个整数，依次表示 $x$ 和 $y$。

#### 问题 2

第一行是一个整数 $T$，表示测试数据组数。
接下来按顺序给出每组数据的输入。
每组数据第一行是两个整数，依次表示数组 $a$ 的长度 $n$ 和询问次数 $q$。
每组数据第二行有 $n$ 个整数，依次表示 $a_1, a_2, \dots a_n$。
每组数据第三行有 $q$ 个整数，依次表示 $q$ 次询问给出的 $x$。

#### 问题 3

第一行是一个整数 $T$，表示测试数据组数。
接下来按顺序给出每组数据的输入。
每组数据第一行是两个整数，依次表示数组 $a$ 的长度 $n$ 和询问次数 $q$。
每组数据第二行有 $n$ 个整数，依次表示 $a_1, a_2, \dots a_n$。
每组数据第三行有 $q$ 个整数，依次表示 $q$ 次询问给出的 $x$。

outputFormat:
#### 问题 1

输出只有一行一个整数，表示两数的最小公倍数。

#### 问题 2

对每组数据，输出一行 $q$ 个整数，依次表示每次询问的答案。

#### 问题 3

对每组数据，输出一行 $q$ 个整数，依次表示每次询问的答案。

hint:
### 样例组与实际输入的说明

三个样例分别对应三个问题的样例输入输出。

如果你直接采用『提交答案』的方式，请分别将三个输入数据命名为 `1.in`、`2.in`、`3.in`，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器可以从标准输入读入一个整数 $x$，满足 $1 \leq x \leq 3$，表示该测试点对应的问题编号，然后**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对三个问题的样例说明。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有行末空格和文末回车。
2. 数据中所有的数字都应为整数。
3. 对于问题 1，$1 \leq x, y \leq 10^9$，且你**必须保证**两数的最小公倍数也不超过 $10^9$。
4. 对于问题 2，$1 \leq T \leq 3$，$1 \leq n,q \leq 10^5$，$1 \leq a_i, x \leq 10^9$。
5. 对于问题 3，$1 \leq T \leq 3$，$1 \leq n, q, a_i, x \leq 10^6$。

### 目标代码

你需要 hack 如下的代码：

#### 问题 1

```cpp
#include <iostream>
#include <algorithm>

int main() {
  int x, y;
  std::cin >> x >> y;
  int ans = x * y / std::__gcd(x, y);
  std::cout << ans << std::endl;
}
```

#### 问题 2

```cpp
#include <iostream>
#include <algorithm>

const int maxn = 1000003;

int T;
int n, q;
int a[maxn], b[maxn];

int find(int x) {
  int l = 1, r = n;
  int ans = 0;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (a[mid] <= x) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return ans;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (std::cin >> T; T; --T) {
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
      std::cin >> a[i];
    }
    for (int x; q; --q) {
      std::cin >> x;
      std::cout << find(x) << " ";
    }
    std::cout << std::endl;
  }
}
```

#### 问题 3

```cpp
#include <iostream>

const int maxn = 1000003;

int T;
int n, q;
int a[maxn], b[maxn];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (std::cin >> T; T; --T) {
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
      std::cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
      b[a[i]]++;
    }
    for (int i = 1; i < maxn; ++i) b[i] += b[i - 1];
    for (int x; q; --q) {
      std::cin >> x;
      std::cout << b[x] << " \n"[q == 1];
    }
  }
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

### 判分说明

本题共三个测试点，分别对应三个问题，每个问题 hack 成功则对应测试点返回 accepted。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 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: [Ynoi2001] 冷たい部屋、一人

type: P

background:
 冷たい部屋の隅に 射し込んできた夕陽だったら
 冰冷房间的角落 洒满夕阳的光辉
 近づいてみても感情は無くて 裏切りも無い
 再怎么接近也没有感情 没有变化

 今日も明日も一人で きっとそれが普通のことで
 就算今后都是一个人 也只是很平常的事
 交わす言葉も無く 一日を終える時
 交谈也无法改变 这一天的终结

 例えば 優しさはどれくらいの
 例如 温柔究竟是怎样的
 ぬくもりかも知らないで
 连获取温暖都不知道
 そんなにそんなに簡単じゃない
 那么那样不是很简单吗
 心の距離
 心的距离

 冷たい部屋の隅に 小さくなったまま
 冰冷房间的角落 就这样变小吧
![](https://cdn.luogu.com.cn/upload/image_hosting/6uukzjeq.png)

description:
给定 $n,m$，以及序列 $a_1,a_2,\dots,a_n$ 和 $1,2,\dots,n$ 的排列 $y_1,y_2,\dots,y_n$，你需要回答 $m$ 个询问。

对每个询问，给定 $l,r$，查询：

$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n [a_i=a_j]\cdot\prod_{k=i}^j [l\le y_k\le r]$；

其中 $[\mathrm{cond}]$ 在条件 $\mathrm{cond}$ 为真时值为 $1$，否则值为 $0$。

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

第二行 $n$ 个整数 $a_1,\dots,a_n$；

第三行 $n$ 个整数 $y_1,\dots,y_n$；

接下来 $m$ 行，每行两个数 $l,r$ 表示一个询问。

outputFormat: $m$ 行，每行一个整数，表示相应的答案。

hint:
Idea：Ynoi&nzhtl1477，Solution：Ynoi&ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n,m\le 5\times 10^5$；$1\le a_i\le n$；$1\le y_i\le n$，$y_i$ 互不相同；对每个询问，$1\le l\le r\le n$。

对于 $20\%$ 的数据，满足 $n,m\le 100$。

对于 $40\%$ 的数据，$n,m\le 5000$

对于 $60\%$ 的数据，$n,m\le 2\times 10^5$


title: [Ynoi2079] r2pspc

description: 给定序列 $a_1,\dots,a_n$，共 $m$ 次查询，每次查询问 $\sum\limits_{i=l}^r 2^{a_i}$ 的二进制表示中 $1$ 的个数。

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

第二行 $n$ 个数表示 $a_1,\dots,a_n$。

接下来 $m$ 行每行 $l,r$ 表示一次查询。

outputFormat: 共 $m$ 行，依次为每次查询的答案。

hint:
Idea：rushcheyo，Solution：djq_cpp&ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n\le {10}^5$，$1\le m\le {10}^6$，$1\le a_i\le 10^9$，$1\le l\le r\le n$。

对于 $25\%$ 的数据，满足 $n,m\le 1000$。

对于另外 $25\%$ 的数据，满足 $a_i\le100$。

对于另外 $25\%$ 的数据，满足 $m\le 10^5$

对于另外 $25\%$ 的数据，无特殊限制。


title: 『STA - R2』机场修建

background: 智利在修机场。

description:
有 $n$ 个城市排成一列，最开始是互不连通的。
每个城市初始都没有人口。
会出现以下操作 / 查询共 $m$ 个：

1. `1 x y` 开通城市 $x$ 和城市 $y$ 之间的双向航班。
2. `2 l r a` 城市 $[l, r]$ 的人口数都 $+a$。
3. `3 x` **如果**所有能够到达城市 $x$ 的人都来到城市 $x$，城市 $x$ 有多少人。

inputFormat:
第一行两个数 $n, m$。
接下来 $m$ 行，每行一个操作。

outputFormat: 对于所有的操作 $3$ ，输出答案。

hint:
**本题捆绑测试。**
- Easy（5pts）：$1 \le n, m \le 2 \times 10^5$，且不存在操作 $1$。
- Normal（10pts）：$1 \le n, m \le 1000$。
- Hard（20pts）：$1 \le n, m \le 10^5$，且操作 $3$ 之后不存在操作 $2$。
- Lunatic（30pts）：$1 \le n, m \le 5 \times 10^4$。
- Overdrive（35pts）：$1 \le n, m \le 2 \times 10^5$。

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$0 \le a \le 10^9$。保证答案在 64 位有符号整形表示的范围内。

![](https://cdn.luogu.com.cn/upload/image_hosting/dgqoqa8d.png)
出于某些原因，给了较多的部分分。


title: [语言月赛202303] Hack Problem P

type: B

description:
下面程序想要实现的功能为：

> 给出两个正整数 $x, y$，保证它们的最小公倍数（$\mathrm{lcm}$）不大于 $10^9$。求它们的最小公倍数。

```cpp
#include <iostream>
#include <algorithm>

int main() {
  int x, y;
  std::cin >> x >> y;
  int ans = x * y / std::__gcd(x, y);
  std::cout << ans << std::endl;
}
```

但是这个程序存在一些问题，请你提交一个程序，你提交的程序**应当输出一组这道题的输入数据，使得上面的程序输出错误的结果**。

提示：
1. `__gcd(x, y)` 可以求出 $x$ 和 $y$ 的最大公因数。
2. $\mathrm{lcm}(x,y)
\times\mathrm{gcd}(x,y)=x
\times y$

inputFormat: 无

outputFormat:
你提交的程序输出的输入数据应当符合下面的格式：

> $x \quad y$

你给出的数据需要满足 $1 \leq x, y \leq 10^9$，且你**必须保证**两数的最小公倍数也不超过 $10^9$。


title: [JRKSJ R8] 暴风雪

background:
那边就是最上层了吗……

那里会有什么呢？

description:
给你一棵带点权 $v_i$ 的树，树以 $1$ 为根。初始点权 $v_i$ 均为 $0$。

定义 $\text{dis}(x,y)$ 为树上 $x,y$ 之间的距离，即 $x\to y$ 的简单路径上的边数。

设 $\text{subtree}(x)$ 为树上以 $x$ 为根的子树，定义 $f(x)=\max_{d\ge 0} \sum_{y\in\text{subtree}(x)} v_y[\text{dis}(x,y)=d]$。

现在给出 $m$ 次操作，每次操作中给出 $x,w,y$，先令 $v_x\gets v_x+w$，然后求 $\sum_{i\in \text{subtree}(y)} f(i)$。

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

第二行 $n-1$ 个整数 $f_{2\dots n}$，依次表示结点 $2,3,\dots ,n$ 的父亲。

接下来 $m$ 行，每行三个整数 $x,w,y$。

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


title: 【MX-X1-T1】「KDOI-05」简单的无限网格问题

description:
小 X 正在参加 KDOI 机器人锦标赛。

比赛场地是一个**无限大**的网格，小 X 的机器人初始时位于 $(1,1)$，他需要进行若干次操作，使得机器人移动到 $(n,m)$（$n,m\ge 2$）。

第 $i$ 次操作时，小 X 可以指定上、下、左、右中的一个方向和一个正整数 $x_i$，然后让机器人向该方向移动 $x_i$ 步。

不幸的是，小 X 的机器人出现了一些 bug，因此，他的操作必须满足一些限制，否则机器人就会立即爆炸：

+ 对于第 $i$ 次操作，若 $i$ 是奇数，则 $x_i$ 也是奇数；若 $i$ 是偶数，则 $x_i$ 也是偶数。

请帮助小 X 计算出使他的机器人到达 $(n,m)$ 的最小操作次数。

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

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

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

outputFormat: 对于每组测试数据，输出一行一个整数，表示答案。可以证明，小 X 的机器人一定能在有限步内到达 $(n,m)$。


title: [POI2010] Monotonicity

description:
**译自 POI 2010 Stage 3. Day 0「[Monotonicity](https://szkopul.edu.pl/problemset/problem/HVVwfLd9uyYNOW6hUZ_Zcnqe/site/?key=statement)」**

对于一个整数序列 $a_1, a_2, \cdots, a_n$，我们定义其“单调序列"为一个由 $<$，$>$ 和 $=$ 组成的符号序列 $s_1, s_2, \cdots,s_{n-1}$，其中符号 $s_i$ 表示 $a_i$ 和 $a_{i+1}$ 之间的关系。例如，数列 $2, 4, 3, 3, 5, 3$ 的单调序列为 $<, >, =, <, >$。

对于整数序列 $b_1, b_2, \cdots, b_{n+1}$ 以及其单调序列 $s_1, s_2, \cdots, s_n$，如果符号序列 $s_1', s_2', \cdots, s_k'$ 满足对所有 $1 \le i \le n$ 有 $s_i = s_{((i - 1) \bmod n) + 1}'$，我们就说序列 $s_1, s_2, \cdots, s_n$ 「实现」了序列 $s_1', s_2', \cdots, s_k'$。也就是说，序列 $s_1, s_2, \cdots, s_n$ 可以通过重复多次 $s_1', s_2', \cdots, s_k'$ 序列并删除一个后缀得到。例如，整数数列 $2, 4, 3, 3, 5, 3$ 至少实现了以下符号序列：

* $<, >, =$
* $<, >, =, <, >$
* $<, >, =, <, >, <, <, =$
* $<, >, =, <, >, =, >, >$

给定一个整数序列 $a_1, a_2, \cdots, a_n$ 以及一个单调序列 $s_1, s_2, \cdots, s_k$，求出原整数序列最长的子序列 $a_{i_1}, a_{i_2}, \cdots, a_{i_m} (1 \le i_1 \lt i_2 \lt \cdots \lt i_m \le n)$ 使得前者的单调序列实现后者的符号序列。

inputFormat:
第一行包含用空格分隔的两个整数 $n,k$，分别表示整数序列 $a_i$ 的长度和单调序列 $s_j$ 的长度。

第二行包含用空格分隔的 $n$ 个整数，表示序列 $a_i$。

第三行包含用空格分隔的 $k$ 个符号，表示符号序列 $s_j$。

outputFormat:
第一行输出一个整数 $m$，表示序列 $a_1, a_2, \cdots, a_n$ 的最长的「实现」了单调序列 $s_1, s_2, \cdots, s_n$ 的子序列。

第二行输出任意一个这样的子序列 $a_{i_1}, a_{i_2}, \cdots, a_{i_n}$，元素之间用空格分隔。


title: [KMOI R1] 军事行动

background:
$$\blue{他们来了。}$$

$$\purple{集结军队，干掉他们，一个不留。}$$

$$\blue{是！}$$

description:
喵星边境局势愈发紧张，导致发生边境冲突。喵星军队总司令小袁立即对 $Y$ 星采取军事行动。

整个宇宙可以看作一个平面直角坐标系，城市 $1,2,\dots,n$ 的坐标分别为 $(x_1,y_1),(x_2,y_2),\dots(x_n,y_n)$。

现在小袁率领的**若干支**舰队（可以理解为小袁的军事力量是无限的）驻扎在边境要塞，城市 $1$ 处。他的舰队会进行以下移动：

- 如果舰队的坐标为 $(x,y)$，那么一天之后它可以移动到 $(x-1,y+2)$ 或 $(x+1,y+2)$ 或 $(x+2,y+1)$ 或 $(x-2,y+1)$ 或 $(x-1,y-2)$ 或 $(x+1,y-2)$ 或 $(x+2,y-1)$ 或 $(x-2,y-1)$ 处。

其中环绕在外的还有一条小行星带，当舰队的坐标  $(x,y)$ 且 $x\le 0$ 或 $y\le 0$ 或 $m < x$ 或 $m < y$ 时，舰队就会撞到小行星带。这是小袁所不想看到的。

现在小袁要攻打城市 $2,3,\dots,n$，每一次他都会从一个**已经占领**的城市（城市 $1$ 也算），派出舰队前往城市 $i$ 并攻打它，舰队**到达之后的第二天**城市 $i$ 就被攻占了。

特别的，小袁在一个舰队**前往攻打或攻打一个城市**的时候不会派出另外一支舰队，在**攻占一座城市后当天**可以立即派出另外一支舰队。

小袁想问，最少要花多少时间才能攻占所有的城市。

**攻打顺序可以不按照 $2,3\dots n$ 的顺序。**

inputFormat:
第一行一个整数 $n,m$，表示城市个数和小行星带的范围。

接下来 $n$ 行，每一行两个正整数 $(x_i,y_i)$，表示城市 $i$ 的坐标。**保证 $1\le x_i,y_i \le m$**。

outputFormat: 一个整数 $ans$，表示最少要花的时间。

samples:
查看附件的 example4.in
查看附件的 example4.out


title: 纸币问题 1

description: 某国有 $n$ 种纸币，每种纸币面额为 $a_i$ 并且有无限张，现在要凑出 $w$ 的金额，试问最少用多少张纸币可以凑出来？

inputFormat:
第一行两个整数 $n,w$，分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的整数 $a_1, a_2, a_3, \dots a_n$ 依次表示这 $n$ 种纸币的面额。

outputFormat: 一行一个整数，表示最少使用的纸币张数。


title: 纸币问题 2

background: 你是一个非常有钱的小朋友。

description:
你有 $n$ 种面额互不相同的纸币，第 $i$ 种纸币的面额为 $a_i$ 并且有无限张，现在你需要支付 $w$ 的金额，求问有多少种方式可以支付面额 $w$，答案对 $10^9+7$ 取模。
注意在这里，同样的纸币组合如果支付顺序不同，会被视作不同的方式。例如支付 $3$ 元，使用一张面值 $1$ 的纸币和一张面值 $2$ 的纸币会产生两种方式（$1+2$ 和 $2+1$）。

inputFormat:
第一行两个正整数 $n,w$，分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的正整数 $a_1, a_2, \dots a_n $ 依次表示这 $n$ 种纸币的面额。

outputFormat: 一行一个整数，表示支付方式的数量。

hint:
对于 $40\%$ 的数据，满足 $n\le 10$，$w\le 100$；
对于 $100\%$ 的数据，满足 $1\le n\le 10^3$，$1\le a_i \le  w\le 10^4$。

其实小朋友并不有钱。


title: 纸币问题 3

background:
你是一个非常有钱的小朋友。

**注意：**本题和《进阶篇》的对应题目，输入格式略有差异。

description: 你有 $n$ 种面额互不相同的纸币，第 $i$ 种纸币的面额为 $a_i$ 并且有无限张，现在你需要支付 $w$ 的金额，请问有多少种纸币组合能恰好支付金额 $w$，答案对 $10^9+7$ 取模。

inputFormat:
第一行两个正整数 $n,w$，分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的正整数 $a_1, a_2, \dots a_n$ 依次表示这 $n$ 种纸币的面额。

outputFormat: 一行一个整数，表示能恰好凑齐面额 $w$ 的纸币组合数量。

hint:
对于 $40\%$ 的数据，满足 $n\le 10$，$w\le 100$；
对于 $100\%$ 的数据，满足 $1\le n\le 10^3$，$1\le a_i \le w\le 10^4$。

其实小朋友并不有钱。


title: 转圈

description:
小 $\delta$ 喜欢转圈圈。

他有一个圈，被均匀分成了 $n$ 个格子，神奇的是，$n$ 是一个质数。第 $i$ 个格子上写着一个数 $i \times m$，他现在站在第一个格子上。

接下来他会看看脚下踩着的数是多少，然后向前走这么多格。他会一直反复这么做。

求最终被小 $\delta$ 踩到过的格子的数量。由于小 $\delta$ 有很多圈圈，所以他会问你很多次。

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

对于每组询问，输入一行两个正整数 $n,m$。

outputFormat: 对于每次询问，输出一行一个正整数，代表被踩到的格子的数量。

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

以第一次询问为例，小 $\delta$ 依次经过的格子编号为 $1 \to 3 \to 4 \to 2 \to 1 \to \cdots$，因此被踩到过的格子个数为 $4$。

**【数据范围】**

- 对于 $20\%$ 的数据，$n \le 10^3$，$T \le 2 \times 10^3$。
- 对于另外 $40\%$ 的数据，$T \le 3 \times 10^3$。
- 对于另外 $40\%$ 的数据，无特殊性质。

对于所有数据，$1 \le m < n \le 10^7$，$1 \le T \le 4 \times 10^5$。保证 $n$ 是质数。


title: 青蛙寻青。

background:
数次失败后，小青蛙的思想开始发生变化。

他开始寻找自己为青蛙之本。

他开始寻找其他青蛙帮忙。

他在发生蜕变。

他在升华。

他，将变成光！

他给自己取了新名字 —— 青蛙青（qwq），因为名字很可爱。

description:
白色光可以被分解成青色光还有很多其他颜色的光。

$\{a\}$ 是一个长度为 $n$，有 $k$ 种不同颜色的序列，第 $i$ 个元素颜色为 $a_i$（保证颜色 $1\sim k$ 都在 $a$ 中出现过）。

$\{b\}$ 是一个长度为 $m$ 的序列，第 $i$ 个元素颜色为 $b_i$（保证每个 $b_i$ 都是 $k$ 种颜色中的一种，但不保证 $k$ 种颜色都在 $b$ 中出现过）。我们可以修改 $b$ 中若干个位置的颜色，得到一个长度仍为 $m$ 的序列 $b'$。

我们对 $b'$ 与 $a$ 中颜色相同的点连这种颜色的一条线段。

如 $n=3,m=4,k=3,a=\{1,2,3\},b'=\{1,3,2,2\}$，它们之间的连线是这样的：

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

要求**不同颜色的线段两两不交**，**且 $k$ 种颜色都要在 $b$ 中出现**，请问最少修改次数是多少？

形式化的，设你修改后的符合要求的序列为 $b'$，那么你需要最小化：

$$
\sum_{i=1}^{m}[b_i\ne b'_i]
$$

对于上述 $a=\{1,2,3\},b'=\{1,3,2,2\}$ 的情况，它们之间的连线（红色的 $2$ 与紫色 $3$ 之间）出现了相交。

但如果我们把 $b$ 修改成 $\{1,2,3,3\}$，它们之间的连线没有相交，满足上述条件：

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

注意：

- $b' = \{1,1,4,5\}$ 的情况连线也没有相交，但是 $b'$ 包含了 $k$ 种颜色之外的颜色（有 $4$ 和 $5$），因此这个 $b'$ 不合法。
- $b' = \{1,1,1,1\}$ 的情况连线也没有相交，但是 $b'$ 中没有包含 $1\sim k$ 中所有的颜色（没有 $2$ 和 $3$），因此这个 $b'$ 也不合法。

特别的，如果无论怎样修改都无法满足要求，请输出 `-1`。

inputFormat:
第一行共两个整数 $n,m$，分别表示序列 $a,b$ 的元素个数。

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

第三行共 $m$ 个整数，第 $i$ 个整数表示 $b_i$。

outputFormat:
一行，一个整数，表示满足要求的最小修改次数。

如果无论怎样修改都无法满足要求，请输出 `-1`。


title: [NICA #1] 自动取款机

description: 小 A 要购买一件价值为 $a$ 元的商品，而他的手上有 $b$ 元现金。由于现金可能不够，他可能需要去银行提款。自动取款机可以提供无限张 $100$ 元纸币。现在小 A 告诉了你 $a$ 和 $b$，他希望知道他至少要取多少张 $100$ 元纸币，才能买下这个商品。

inputFormat: 输入两个正整数 $a$ 和 $b$，以空格隔开。

outputFormat: 输出一行，一个整数，表示他至少要取多少张 $100$ 元纸币，才能买下这个商品。

hint: 对于所有数据，$1 \leq b\leq a \leq 10^{12}$。


title: [NICA #1] 成绩

description:
小 A 的期末考试考完了，他迫不及待想要知道自己的期末总评成绩。

他的考试科目只有语文、数学、英语三个科目。由于学校的教务制度，小 A 的学校一共有两种考核指标：

- 传统型：不超过一门低于 $60$ 分，就属于及格；
- 特色型：给每个科目附上权重，让科目期末得分等于考试分数乘以权重，再将三门科目的期末得分相加除以权重总和。如果不低于 $60$ 分就属于及格。

例如小 A 语文考了 $70$ 分，权重是 $2$，数学考了 $50$ 分，权重是 $4$，英语考了 $60$ 分，权重是 $3$。在传统型的考核指标中他期末是及格的。但是如果使用了特色型考核指标，那么他的期末总评是 $\dfrac{70\times 2+50 \times 4+60 \times 3}{2+4+3} \approx 57.78$，未及格。

小 A 告诉了你他每一门考试的分数和每一门科目的权重，他希望知道他是否在两个考核指标中都及格了。

inputFormat:
输入一行。

首先输入三个正整数 $a,b,c$，分别表示小 A 语文、数学、英语的分数。

之后输入三个正整数 $d,e,f$，分别表示语文的权重、数学的权重和英语的权重。

outputFormat:
输出两行。第一行表示小 A 在传统型考核指标中的及格情况；第二行表示小 A 在特色型考核指标中的及格情况。

如果及格，则输出 `PASS`，否则输出 `FAIL`。

hint: 对于所有数据保证，$1 \leq a,b,c \leq 100$，$1 \leq d,e,f \leq 10$。


title: [NICA #1] 年龄问题

description:
小 A 的爸爸今年 $a$ 岁，他比小 A 年长 $b$ 岁，又比小 A 的奶奶年轻 $c$ 岁。

请问小 A 和他的奶奶今年年龄多少？

inputFormat: 第一行输入三个正整数 $a,b,c$，以空格隔开。

outputFormat: 输出一行，两个正整数，用一个空格隔开。分别表示小 A 和他的奶奶今年的年龄是多少岁。

hint: 对于所有数据，保证 $1 \leq b<a\leq 100$，$1 \leq c \leq 100$。

tags: 语言入门（请选择[入门与面试]题库）


title: [NICA #1] 图形

description:
小 A 在做模型。他希望知道，制作下图中的模型一共需要多少平方米的材料？图中的 $a,b,c$ 由输入给出，且 $a,b,c$ 的单位为**厘米**。圆周率 $\pi=3.1415926535$。

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

inputFormat: 输入三个正整数 $a,b,c$，以空格隔开。

outputFormat: 输出一行，一个保留到小数点后三位的浮点数，表示一共需要多少平方米的材料。

hint: 数据保证，$1 \leq a,b,c \leq 100$。


title: [NICA #1] 交换

description:
给定长度为 $n$ 的排列 $a$。排列的含义是，数字 $1,2,3,\cdots n$ 在 $a$ 中**恰好**出现了一次。现在有 $m$ 次操作，

- 第 $1$ 次操作将会交换第 $1$ 大（即最大）的元素和第 $2$ 大的元素。
- 第 $2$ 次操作将会交换第 $2$ 大的元素和第 $3$ 大的元素。
- 第 $3$ 次操作将会交换第 $3$ 大的元素和第 $4$ 大的元素。
- ……
- 第 $n-1$ 次操作将会交换第 $n-1$ 大的元素和第 $n$ 大的元素。
- 第 $n$ 次操作将会交换第 $1$ 大的元素和第 $2$ 大的元素。
- 第 $n+1$ 次操作将会交换第 $2$ 大的元素和第 $3$ 大的元素。
- 第 $n+2$ 次操作将会交换第 $3$ 大的元素和第 $4$ 大的元素。
- ……
- 第 $2n-2$ 次操作将会交换第 $n-1$ 大的元素和第 $n$ 大的元素。
- ……

形式化地讲，第 $i$ 次操作将会交换第 $(i-1)\bmod (n-1)+1$ 大和第 $(i-1)\bmod (n-1)+2$ 大的数字。

你需要求出排列最后的情况。

inputFormat:
第一行有两个整数 $n,m$，含义如题面所示。

第二行有 $n$ 个整数 $a_1,a_2,\cdots,a_n$，描述初始时的序列 $a$。

outputFormat: 输出共一行 $n$ 个整数，表示最终的 $a$ 序列。


title: [NICA #1] 弹幕

description:
某款弹幕游戏的 BOSS 会放出弹幕攻击玩家（自机）。由于这些弹幕的行动轨迹十分诡异，因此现在希望找到一个「安定点」（只要呆在这个位置就不会被任何弹幕打到的地方）

假定空中有 $n$ 道弹幕。我们用三元组 $(a_i,b_i,c_i)$ 描述每一个弹幕的参数。我们认为自机在一条标着 $0,1,2,\cdots,10^6$ 的数轴上，且只能处于**整点**处。

假定自机位于坐标为 $x$ 的位置。那么自机会被第 $i$ 枚弹幕打到，当且仅当 $x^3+a_ix^2+b_ix+c_i=0$。

现在你需要求出**任意**一个 $x$，使得自机不会被任何一个弹幕打中。你需要保证求出来的 $x$ 在 $[0,10^6]$ 之内。

inputFormat:
第一行有一个正整数 $n$，表示弹幕的数量。

接下来 $n$ 行，每行有三个整数 $a_i,b_i,c_i$，描述一条弹幕的参数。

outputFormat: 输出共一行一个整数 $x$，表示**任意一个**不会被弹幕打中的地方。

hint:
### 样例解释

- 第一枚弹幕只会打到位于 $0$ 位置的自机；
- 第二枚弹幕只会打到位于 $1$ 位置的自机；
- 第三枚弹幕只会打到位于 $1,2,3$ 位置的自机。

因此如果在 $4$ 位置，自机就不会被打中。事实上，只要不是 $0,1,2,3$ 位置均可，答案不唯一。

### 数据范围及约定

对于全部数据，保证 $1\le n\le 2\times 10^5$，$|a_i|\le 10^6$，$|b_i|\le 10^{12}$，$|c_i|\le 10^{18}$。


title: [NICA #1] 百货商场

description:
小 A 在百货商场购物，他携带了 $m$ 元钱。

一路上他一共看到了 $n$ 家店面排成一列，他会一家一家地走过这些店铺。第 $i$ 家店面的商品需要花费 $a_i$ 元购买。如果他支付不起这一家店的商品他会直接进入下一家店，否则会支付钱并购买商品后再进入下一家店购物。

当他购物完成后，由于他是商场的大会员，他可以获得一些返现。他实际只需支付他购买的所有商品的总价的八八折（向下取整），因此他多支付的那一部分差价将会退还给小 A。

请你计算一下小 A 这一次购物能够获得多少的差价退还？

inputFormat:
第一行输入两个正整数 $n,m$，表示店面数和钱数。

第二行输入 $n$ 个正整数 $a_i$，表示第 $i$ 家店面的商品价格。

outputFormat: 输出一个正整数，表示退还的差价。

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

小 A 购买了第一、第二、第三家店的商品后，手上只有 $40$ 元，买不起第四家店的商品，因此直接进入第五家店买下了 $40$ 元的商品。此时他总共消费了 $100$ 元。最后按照八八折计算，实际只应当支付 $88$ 元，因此退还 $12$ 元差价。

数据保证，对于所有数据，$1 \leq n,m,a_i \leq 10000$。


title: [NICA #1] 年金现值系数表

description:
小 A 最近在研究财务事项。

在财务计算中，年金现值系数是一个常用概念。它定义，$\mathrm{PVIFA}(i,n)=\dfrac{[1-(1+i)^{-n}]}{i}$，其中 $i$ 表示每期利率，$n$ 表示年金支付天数。例如，$\mathrm{PVIFA}(5\%,10)=\dfrac{[1-(1+5\%)^{-10}]}{5\%}=7.7217$。你不必在意 $\mathrm{PVIFA}$ 的具体含义。

小 A 希望你能把年金现值系数以表格的形式打印出来，方便他快速查阅。具体而言，你应该输出一张表格，纵轴表示期数，横轴表示每期利率。如下图：

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

inputFormat: 输入一行，两个正整数 $n$ 和 $i$，表示表格中需要绘制的行数和列数。

outputFormat:
输出 $n+1$ 行 $i+1$ 列的图表。规定如下：
- 第一行第一列为 `\t`；
- 第一行第二列起往后一共 $i$ 个位置，依次输出 $1\%,2\%,\dots,i\%$，以 `\t` 作为分隔符；
- 第二行第一列起往下每行的第一列，依次输出 $1,2,\dots n$，与后面的内容以 `\t` 作为分隔符。
- 第二行第二列开始，设当前为第 $a$ 行第 $b$ 列，则只需输出 $\mathrm{PVIFA}((b-1)\%,a - 1)$ 保留四位小数的值，以 `\t` 作为分隔符。
- 每行行末以 `\n` 作为换行符，不应出现多余的 `\t`。

hint: 数据保证，$1 \leq n,i \leq 50$。


title: [NICA #1] 序列

description:
小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\dots a_n$。他希望支持两种操作：

- `1 k`，给序列中的每一个元素加上一个整数 $k$；
- `2`，查询序列中的最大子序列和。

子序列指的是从原序列中去除某些元素（也可以不去除），但不破坏余下元素的相对位置形成的新的序列。例如，对于序列 $\{2,3,4,5,6\}$，那么 $\{2,3,4\},\{2,4,6\}$ 都是它的子序列，而 $\{6,5,4\}$ 不是。子序列可以为空，此时子序列和为 $0$。

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

第二行输入 $n$ 个正整数 $a_i$，表示序列的元素。

第三行开始，往下 $m$ 行，每一行分别为 `1 k` 或者 `2` 的形式，含义如题意所述。

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

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

- 第一次操作求序列中的最大子序列和，则为 $12+2+8=22$；
- 第二次操作让序列中每一个元素加上了 $3$。此时序列变为 $-2,15,-4,5,11$；
- 第三次操作求序列中的最大子序列和，则为 $15+5+11=31$；
- 第四次操作让序列中每一个元素加上了 $4$。此时序列变为 $2,19,0,9,15$；
- 第五次操作求序列中的最大子序列和，则为 $2+19+9+15=45$。

数据保证，$1 \leq n,m \leq 5\times 10^5$，$-5\times 10^5 \leq a_i,k \leq 5\times 10^5$，操作仅为 $1$ 或 $2$ 操作。


title: [NICA #1] 梦熊培养计划

description:
梦熊信奥一直致力于培养高质量的信奥人才，这意味着需要有对学员学习状态充足的关照，特别是成绩起伏不定的学员。

现在某个班级一共有 $n$ 个学员，他们参与了 $m$ 次考试。为了衡量一个学员的成绩的波动情况，我们采用标准差这一概念。标准差的计算公式如下：

$$\sigma=\sqrt{\dfrac{\sum(X-\mu)^2}{N}}$$

其中，$X$ 指的是这个人每一次考试的成绩，$\mu$ 指的是这个人所有考试成绩的平均值，$N$ 指的是这个人参与的考试次数，$\sum$ 符号表示将所有的结果累加求和。标准差越小，说明成绩越稳定。

例如说如果一个学员的三次考试分数分别为 $40,50,60$，那么其成绩的标准差为 $\sqrt{\dfrac{(40-50)^2+(50-50)^2+(60-50)^2}{3}}=\dfrac{10\sqrt{6}}{3} \approx 8.16$。

现在你已知每个学员的名字和他们每一次考试的成绩，请你将他们根据成绩的波动情况从大到小进行排序。**你只需输出成绩波动最不稳的前 $20$ 人（不满 $20$ 人则全部输出）。**

inputFormat:
第一行输入两个正整数 $n,m$，表示学员人数和参与考试次数。

第二行开始，往下 $n$ 行。对于第 $i$ 行：

- 每行第一个为字符串，表示第 $i$ 个学员的姓名；
- 接着读入 $m$ 个整数，以空格隔开，表示第 $i$ 个学员每次考试的成绩 $a_{i,j}$。

outputFormat: 输出 $\min(n,20)$ 行，按照他们成绩的波动情况由大到小输出每个学员的姓名。如果有多个人成绩波动情况相同，则根据他们姓名的字典序从小到大输出。

samples:
pinkrabbit
chenzhe
kkksc03
xht37
yakumoran

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

xht37 与 yakumoran 的成绩的标准差为 $0$，kkksc03 与 chenzhe 的成绩的标准差约为 $8.16497$，而 pinkrabbit 的成绩的标准差约为 $15.3695$。

数据保证，$1 \leq n \leq 100000$，$1 \leq m \leq 20$，学员姓名长度不超过 $10$ 且只由大小写字母和数字构成。$0 \leq a_{i,j} \leq 100$。

**【提示】**

您不必过多关心浮点误差。


title: 「INOH」Round 1 - 纽结

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

上图是两个结的平面投影图。

我们发现一个结可以由基本的重叠点描述，并且每一个重叠点都是二重点。

也就是说我们可以用**一个点表示重叠点，重叠点之间用不同属性的边来连接**。

可以发现**一个点有四个出口，出口与出口相连**，这四条中有**两条在上，两条在下**。

我们用一个二元组 $(u,d)$ 表示这样一个出口。

其中 $u$ 为这个点，$d \in [ 0, 3 ] $，同时**钦定 $0$ 和 $1$ 为两条上边，$2$ 和 $3$ 为两条下边**。

又发现一个结有两端，这两端一定可以与外界相连，为了方便，用 **$(-1,0)$ 和 $(-2,0)$ 表示这两端**。

现在给您一个这样的结，您需要回答，当我们手捏两端，然后用力拉，这是个活结还是死结？

如果是活结请输出 `Yes`，如果是死结请输出 `No`。

inputFormat:
第一行为数据组数 $T$。

每组数据第一行 $n$，表示结点数。

之后 $n$ 行，第 $i$ 行有 $ u_0, d_0, u_1, d_1, u_2, d_2, u_3, d_3 $ 共八个数分别为第 $i$ 个点的 $0$ 到 $3$ 号出口连向的对应出口。

第 $i$ 行的第 0 组 $(u_0,d_0)$ 指第 $i$ 个点的 $0$ 号出口与第 $u_0$ 个点的 $d_0$ 号出口相连，以此类推。

outputFormat: 一共 $T$ 行，每行为 `Yes` 或 `No`。

hint:
### 数据范围
**本题采用捆绑测试**。
- Subtask 0（20pts）：$T = 3$，$1 \le n \le 10$。
- Subtask 1（20pts）：$T = 10^3$，$1 \le n \le 10$。
- Subtask 2（10pts）：$T = 10$，$1 \le n \le 10^5$，且保证数据随机生成。
- Subtask 3（50pts）：$T = 10$，$1 \le n \le 10^5$。

### 样例解释：

样例一为左图，它是死结。

样例二为右图，它是活结。

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


title: 「INOH」Round 1 - 狂气

description:
有一个无限长的序列 $\{a\}$，**数组下标从 $1$ 开始**，初始 $a_1=1$，其余位置均为 $0$。

$m$ 次操作：
1. 对于所有**奇数** $i$，令 $a_{i+1}\gets a_{i+1}+a_i$。
2. 对于所有**偶数** $i$，令 $a_{i+1}\gets a_{i+1}+a_i$。

你需要求出所有操作进行完之后的序列。

为了方便输出，你只需要输出 $( \displaystyle\prod_{i = 1}^{m} (a_i + 1))\bmod 998244353$ 的值即可。

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

第二行一个长度为 $m$ 的字符串，表示操作序列。

outputFormat: 一行，表示 $( \displaystyle\prod_{i = 1}^{m} (a_i + 1)) \bmod 998244353$ 的值。

hint:
**样例 1 解释**

经过 5 次操作之后，序列前五项：
$a_1 = 1$，$a_2 = 3$，$a_3 = 4$，$a_4 = 4$，$a_5 = 0$。

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

- Subtask 0（10pts）：$1 \le m \le 1000$。
- Subtask 1（20pts）：操作序列形如 $\tt121212\dots$。
- Subtask 2（20pts）：操作序列随机生成。
- Subtask 3（50pts）：无特殊限制。

对于 $100\%$ 的数据，有 $1 \le m \le 2 \times 10^5$。

**请选手注意常数因子对运行效率的影响**


title: [NICA #1] 上大分

background: 小 T 喜欢打 CF。

description:
小 T 获得了预知能力，能预知自己后面 $n$ 场比赛的表现分。

下面是表现分的定义：

- 记小 T 在参加这场比赛前账号的分数是 $i$，他这场的表现分为 $j$，那么打完这场之后他的账号分数是 $i+\lfloor\frac{j-i}{4}\rfloor$ 。
- 其中 $\lfloor x\rfloor$ 表示对 $x$ 下取整，如 $\lfloor 1.9\rfloor=1,\lfloor -1.3\rfloor=-2$。

但是小 T 只有一个账号，初始分数是 $x$。他决定从未来的 $n$ 次比赛中选择**不超过** $k$ 次参加，同时，这些比赛的类型不同，具体分为两类，这些类型会给出：

- division 1：不管小 T **当前的分数**是多少，都可以参加。
- division 2：只有小 T **当前的分数** $< 1900$，他才能参加。
- 注意，**当前的分数**为这次比赛前的分数，而不是初始分数。**当前的分数**会随着小 T 之前选择参加比赛的策略变动而变动。

他希望自己在所有比赛结束后得分最高，请你来帮他规划一下，在最优决策下，参加完选出的比赛后能获得的最高分数是多少。

inputFormat:
第一行三个正整数 $n,k,x$，同题意。

接下来 $n$ 行每行两个整数 $\mathrm{type},a_i$，分别表示比赛的类型和小 C 这场比赛的表现分，其中 $\mathrm{type}=2$ 表示是 division 2 的比赛，$\mathrm{type}=1$ 表示是 division 1 的比赛。

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

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

两场都打。

#### 【数据范围】

对于 $100\%$ 的数据，满足 $0\leq x,a_i\leq 4000$，$n,k\leq 5000$，$1\leq k\leq n$。


title: [Ynoi2001] 梦想歌

background:
 子供の頃の夢は
 孩童时期的梦想
 色褪せない落書きで
 是永不褪色的涂鸦
 いつまでも描き続けられた
 无论何时都不停描绘着
 願う未来へとつながる
 与理想中的未来紧紧相连
 鐘が鳴る音
 钟声鸣响
 遠くから聞こえてくる
 即使在远方也听得见
 素直な心に
 传达到坦率的内心之中
 届いては響いてる
 随之回响
 光りは
 化作七彩的
 七色に変わって
 光芒
![](https://tuchuangs.com/imgs/2023/03/19/e23d3bd048e193de.jpg)

description:
给定树上 $n$ 个点，每个点有一个点权 $v_i$。

在此题面中，启发式合并指，递归地进行从底往上的集合合并，每一次以集合的点权和为键值，将权值和更小的集合中的点加入更大的权值和的集合中，初始时每个点集合为该点本身。

同时我们钦定如下的枚举顺序：假设已经递归进行了所有子树的合并，合并当前层节点时从子树的根开始，将儿子们按编号大小从小到大排序，每一次合并两两集合得到子树的集合。

同时，若两个集合的权值和相同，以集合中最小节点深度为第二关键字进行比较（深度大的向深度小的合并）。

钦定该树的根为 $1$。给出以下查询和修改操作：

```1 x``` 表示查询当前以 $x$ 为根的子树进行启发式合并后，没有进行「合并入另外一个集合」操作的节点权值。

```2 x d```将第 $x$ 个点的节点权值加 $d$。

inputFormat:
第一行两个整数 $n,q$，分别表示树的大小和操作次数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，其中 $a_i$ 表示结点 $i$ 的初始权值。

第三行 $n-1$ 个整数 $p_2,p_3,\cdots,p_n$，其中 $p_i$ 表示以结点 $1$ 为根时，结点 $i$ 的父亲。

接下来 $q$ 行，每行格式形如 `1 x` 或 `2 x d`，分别对应题目描述中的两种操作。

outputFormat: 对于每个类型为 $1$ 的操作，输出一行一个整数，表示所求答案。

hint:
Idea：FutaRimeWoawaSete，Solution：zhoukangyang，Code：Rainybunny，Data：FutaRimeWoawaSete/Rainybunny

对于 $100\%$ 的数据，$1\le n,q\le2\times10^5$，$1\le p_i<i$；操作给出的 $x\in[1,n]$，$d\in[-10^{18},10^{18}]$；在任意时刻 $a_x\ge 1$ 且 $\sum_{x=1}^na_x\le10^{18}$。


title: [NICA #1] 乘只因

background: 咯咯咯（只因叫）。

description:
给定 $n,k$，请统计有多少个长度为 $k$ 的序列 $[a_1,a_2,\dots,a_k]$ 满足：

- $a_1\times a_2\times a_3\times \dots\times a_k=n$。
- $1<a_1\leq a_2\leq a_3\leq \dots\leq a_k$。
- 这 $k$ 个数的最小公倍数等于 $n$。

inputFormat:
本题多测，共 $T$ 组数据。

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

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

outputFormat:
共 $T$ 行。

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

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

- 只能拆分为 $2\times 5$。
- $2$ 和 $5$ 的最小公倍数为 $10$。

#### 【数据范围】

对于 $100\%$ 的数据，满足 $n,k\leq 10^7$，$T\leq 10^5$。


title: 「GMOI R2-T2」猫耳小

background:
**本题与 [加强版](https://www.luogu.com.cn/problem/P9202) 的区别在于数据范围和输出格式。在这一版本中，$n\le 5\times 10^3$，值域为 $5\times 10^3$，你不需要给出构造。**

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

description:
小 R 是一个可爱的猫耳女孩子，她喜欢研究数列的 $\operatorname{mex}\text{*}$。

现在她有一个长度为 $n$ 的数列 $a$。她讨厌整数 $k$，因此她希望修改数列 $a$ 的若干个元素为任意**自然数**，使得 $a$ 的任意**连续非空子串**的 $\operatorname{mex}$ 都不等于 $k$。

请你求出最少需要修改多少个元素。

$\text{*}$ 本题中，数列的 $\operatorname{mex}$ 被定义为数列中最小未出现的**自然数**，例如：

- $\operatorname{mex}\{1,2,3\}=0$，因为 $0$ 是自然数。
- $\operatorname{mex}\{0,1,3\}=2$。
- $\operatorname{mex}\{0,1,2\}=3$。

inputFormat:
第一行两个整数 $n,k$，表示数列长度和小 R 讨厌的数。

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$，表示这个数列的第 $i$ 项。

outputFormat: 一行一个整数，表示最少需要修改的元素个数。


title: 「INOH」Round 1 - 意外

background:
**这是一道通信题。**

**由于一些原因，本题有特殊的时空限制，且只有三个测试点。**

**您的得分是三个测试点得分的最小值。**

**请选手注意不要用 `C++14 (GCC 9)` 提交。**

description:
通信中的意外是不可避免的。

A 程序从交互程序获得一个长度为 $10^2$ 的数组，其元素值域为 $ \lbrack 0, 998244353 ) $，A 程序对其进行编码，即 `Encode` 操作，生成一个长度任意，元素值域为 $\lbrack 0, 998244353 )$ 的数组，然后将其返回给交互程序。

交互程序会对编码生成的数组进行如下操作：

- 对于每一个元素，有 $50\%$ 概率，将其赋成在 $ \lbrack 0, 998244353 ) $ 内的一个随机的数，有 $50\%$ 概率不变。

之后 B 程序会从交互程序获得操作后的数组，B 程序需要对其进行解码，即 `Decode` 操作，根据数组信息还原出最初 A 程序从交互程序获得的数组。

### 实现细节

由于无法实现通信，本题以交互的形式运行。

你不需要，也不应该实现主函数，你只需要实现下面两个函数

1. `vector <int> Encode ( vector <int> vec );`
- 该函数传入一个长度为 $10^2$ 的 `vector`，返回一个任意长度的 `vector`。
2. `vector <int> Decode ( vector <int> vec );`
- 该函数传入一个任意长度的 `vector`，返回一个长度为 $10^2$ 的 `vector`。

**交互库会调用 `Encode` 不超过 $3 \times 10^4$ 次，调用 `Decode` 不超过 $1 \times 10^4$ 次。**

**下发的交互库**的实现是固定的测试数据组数，随机一个数组，并立即对其 `Encode` 和 `Decode`，即仅用于简单检验程序。

使用时，你可以**直接将实现好的 `Encode` 和 `Decode` 函数放到交互库代码里**，编译运行即可。

如果交互库输出 `Illegaled operation`，你将获得 $0$ 分。可能的原因包括未还原原数组、返回的数组不合法。

否则交互库会输出一个整数，表示你的分数。

**评测交互库**不一定在 `Encode` 后立即 `Decode`，即可能会先对若干个数组进行编码，再逐一解码。

所有的数应均在 $ \lbrack 0, 998244353 ) $ 范围内。

### 评分方式

设您 `Encode` 返回的最大长度为 $Len$，则得分为 $ \min( 100, \lfloor \frac{1500}{ \lceil \frac{Len}{50} \rceil } \rfloor ) $。

inputFormat: 无

outputFormat: 无


title: [KMOI R1] 音波武器

background: 在 [对 $Y$ 星的军事行动](/problem/P9709) 中，舰队在攻占城市 $p$ 时遇到了一些困难。

description:
小袁的舰队采用使用音波武器攻击的方式，但是对方的城墙使用了一种特殊材料——普林，导致音波攻击效果不是很好。

我们定义**削弱系数 $m$** 为：收到强度为 $n$ 的音波时，音波在穿透普林后会被削弱为 $n\bmod m$ 强度的音波。

现在小袁发射了强度为 $l!,(l+1)!,(l+2)!\dots (r-1)!,r!$ 的 $r-l+1$ 个音波，对方使用了削弱系数为 $k$ 的普林。现在小袁想知道，经过削弱后强度最大的音波的强度是多少。

符号 $!$ 在这里表示阶乘，$x!=1\times 2\times\dots\times x$。例如 $4!=1\times2\times3\times4$。特别地， $0!=1$。

inputFormat: 三个正整数 $l,r,k$，意义如上。

outputFormat: 一个整数 $ans$，表示最大的强度。


title: 不死「火鸟　−凤翼天翔−」

background:
拥有了「不死」的能力的藤原妹红，同时获得了操纵火焰的力量，是不死鸟的化身。

不死鸟，和凤凰是同一种生物吗？

description:
妹红可以操纵火鸟。火鸟可以看作在边长**无限大**的棋盘上放置着的一枚棋子 $A$，$A$ 位于 $(x_1,y_1)$ 处。$A$ 以如下规则移动：

- 在奇数次移动时，$A$ 只能向右上或者左下移动一格，如下图红色箭头；
- 在偶数次移动时，$A$ 只能向右下或者左上移动一格，如下图蓝色箭头。

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

由于棋盘无限大，因此 $x,y$ 的取值可以为负数。

每一步行动时 $A$ 不能待在原地不移动。现在需要把 $A$ 移动到坐标为 $(x_2,y_2)$ 的 $B$ 位置，最少要多少步？特别地，若不存在这样的方案，输出 $-1$。

如下图所示是 $A=(2,7)$，$B=(5,2)$ 的情况。一种移动次数最小的方案已在图上标出，需要 $9$ 步。红色线段表示奇数次的移动，蓝色线段表示偶数次的移动。

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

inputFormat: 输入共一行四个整数 $x_1,y_1,x_2,y_2$，描述 $A,B$ 的坐标。

outputFormat: 输出共一行一个整数。如果存在一条从 $A$ 到 $B$ 的移动方案，输出移动的最小步数；否则输出 $-1$。

hint:
### 数据范围及约定

对于全部数据，保证 $0\le x_1,y_1,x_2,y_2\le 10^9$。


title: 『XYGOI round1』三个数

description: MX 有一个有 $(w-2)$ 个数的集合 $S=\{3,4,5,\cdots ,w\}$。要求构造一个只包含非负整数的集合（无重复元素），使得 $S$ 里面的任何一个数都能被这个集合里面大于等于 $3$ 个不同的数相加得到，求这个集合中至少包含多少个元素。

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

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

接下来 $T$ 行每行输入一个整数 $w$。

outputFormat: 共 $T$ 行，每行输出一个整数 $n$，表示集合至少应该含有的元素个数。


title: [ZSHOI-R1] 河外塔（加强版）

background:
河内塔（又称汉诺塔）问题，就是在一块木板上有三个立柱，在柱 1 上放着三个圆盘，小的在上面，大的在下面（初始状态）。让被试将在柱 1 上的三个圆盘移到柱 3 上面（目标状态）。条件是：每次只能移动任何一个柱子上面的一个圆盘，但大的圆盘不能放在小的圆盘上。

通用问题解决者的解决过程即是手段——目的分析的策略。

description:
但是，你可能没有听过河外塔问题。虽然但是，好像并没有河外塔问题。于是，伟大的 X_Xy 决定创造一个河外塔问题。

既然是河内塔问题的延申，就得有些一样的东西：有三个柱子
$A$，$B$ 和 $C$ ，以及 $n$ 个圆盘，其中编号为 $i$ 的圆盘的半径长为 $i$，这些圆盘最开始都在 $A$ 上，最终都要顺序（即从上往下从小到大）地移到 $C$ 上。

既然是河内塔问题的延伸，就得有些不同的东西：最开始在 $A$ 上面的圆盘并不是顺序的，由于这个限制，我们也不在意移动过程中的顺序，也就意味着你可以将一个大的圆盘放在小的圆盘上。

但是 X_Xy 很懒，他只想让你操作至多 $10^6$ 次。

inputFormat:
输入共两行。

第一行有一个数 $n$，表示圆盘的数量。

第二行有 $n$ 个数，表示 $A$ 上所有的圆盘**从上往下**的标号，保证圆盘构成一个 $1\sim n$ 的排列。

outputFormat:
共若干行。

第一行有一个数 $tot$，表示你的操作数。

接下来的第 $2$ 到第 $tot$ 行，每行两个用空格隔开的大写字母，第 $i+1$ 行表示你的第 $i$ 次操作是从某立柱移到了另一个上。


title: [COCI2022-2023#5] Kalendar

description:
Magdalena 喜欢日历，她为每个月制作自己的日历。

每月的每一天都正好用三个字符表示：

- 如果天数是一位数，则表示为 `..X`。例如：数字 $7$ 被表示为 `..7`。
- 如果天数是两位数，那么它表示为 `.XY`。例如：数字 $17$ 被表示为 `.17`。

日历的每一行代表一个星期，每个星期由 $7$ 天组成。如果
一周没有所有的 $7$ 天（因为有可能这个月不是从星期一开始的，或者不是在星期日结束的），那么缺失的日子就用 `...` 表示。

Magdalena 也希望她的日历是漂亮的。她将用以下方式来装饰它：
她将在上下两边填上 `-`（ASCII 45），左右两边填上 `|`（ASCII 124），而四个角落用 `+`（ASCII 43）。

你的任务是确定 Magdalena 日历的格式，如果它有 $n$ 天，并且每月的第一天是一周的第 $x$ 天。例如，如果 $x=1$，这个月就从星期一开始，如果 $x=5$，就从星期五开始。

我们假设一周的第一天是星期一。

inputFormat: 一行，包含整数 $n$ 和 $x(1\leq n\leq 99,1\leq x\leq 7)$，表示该月的天数，以及该月的起始日。

outputFormat: 输出 Magdalena 日历的样子。


title: [COCI2022-2023#5] Diskurs

description:
给你 $n$ 个非负整数 $a_1, a_2, \cdots a
_n$，任何一个都小于 $2^m$。

对于其中的每一个数，你都要找出它与数组中其他元素之间的最大哈明距离。

两个非负整数的哈明距离被定义为在这些数字的二进制表示中，它们之间有多少个不同的位置（如果有必要，加上前导零）。

形式上，对于每个 $i$ 求：

$$\max\limits_{1\leq j\leq n} hamming(a_i,a_j)$$

inputFormat:
第一行包含两个整数 $n$ 和 $m(1\leq n\leq 2^
m，1\leq m\leq 20)$。
第二行包含 $n$ 个数字 $a_i(0 \leq ai < 2^
m)$。

outputFormat: 一行 $n$ 个数，第 $i$ 个数表示 $a_i$ 与数组中其他元素之间的最大哈明距离。


title: [COCI2022-2023#5] Logaritam

description:
定义对数序列为一个长为 $n$ 的对数序列 $(a_1,a_2,\ldots,a_n)$，满足对于所有正整数 $x,y$ 且 $xy\le n$，有 $a_{xy}=a_x+a_y$。一个长为 $6$ 的对数序列例子为 $0,1,\pi,2,0.7,1+\pi$。

有 $q$ 个长度为 $n$ 的对数序列，但是现在每个序列都恰好有一个元素被改掉了。给你序列个数 $q$，序列长度 $n$ 和每个序列被改动的元素位置 $x_i$，对于每个序列，输出在不改动已经更改的元素的情况下，至少要修改序列中多少个位置的元素才能使这个序列仍然是对数序列。

注：可以证明对于任意的初始对数序列，改动同一位置后，在不改动这个位置的情况下将序列变为对数序列的最小改动数都是相等的。

inputFormat:
第一行两个正整数 $n,q\ (1\le n\le 10^8,1\le q\le 10^4)$，分别表示序列长度和序列个数。

接下来 $q$ 行，第 $i$ 行一个正整数 $x_i\ (1\le x_i\le n)$，表示第 $i$ 个序列中修改的元素下标。

outputFormat: 如果第 $i$ 个序列无法在不改动已经更改的元素的情况下，将原序列变为对数序列，则输出 `-1`，否则输出最少更改元素个数。


title: [COCI2022-2023#5] Slastičarnica

description: 有一列数 $a_1,\ldots,a_n$ 和 $q$ 次操作，每次操作形如「删掉长为 $d_i$ 的前缀或后缀，且需要保证这个前缀和后缀中所有元素都大于等于 $s_i$。」每次操作前，你可以选择一个长度任意的前缀或后缀（可以为空），并删除它。如果某次操作无法进行，则停止这次和之后的所有操作。问最多可以进行多少次操作。

inputFormat:
第一行两个正整数 $n,q\ (1\le n\le 5\ 000,1\le q\le 2\cdot 10^5)$，表示序列长度和操作次数。

第二行 $n$ 个正整数 $a_i\ (1\le a_i\le 10^9)$，表示这个数列。

接下来 $q$ 行，每行两个整数 $d_i,s_i\ (1\le d_i\le n,1\le s_i\le 10^9)$，表示一次操作。

outputFormat: 输出一行一个整数，表示最多能进行多少次操作。

hint:
样例 $3$ 解释：

首先删除前缀 $(1)$，之后进行第一次操作，删除前缀 $(3,2,5)$。此时序列变为 $(1,4,6,2,1)$。

然后删除前缀 $(1)$，之后进行第二次操作，删除前缀 $(4,6)$，此时序列变为 $(2,1)$。

然后不删除任何前缀或后缀，之后进行第三次操作，删除后缀 $(1)$，此时序列变为 $(2)$。

然后不删除任何前缀或后缀，之后进行第四次操作，删除唯一剩余的 $(2)$，此时序列变为空序列。

最后一次操作由于序列为空无法完成，操作停止。

因此一共进行了四次操作。

|子任务编号|	附加限制|	分值|
|:-:|:-:|:-:|
|$0$|	是样例|	$0$|
|$1$|	$n,q\le 100$|	$19$|
|$2$|	$d_1=d_2=\ldots=d_q=1$|	$28$|
|$3$|	无附加限制|	$53$|


title: [COCI2022-2023#5] Zastave

description: 有 $n$ 个直角三角形，第 $i$ 个直角三角形的斜边长度为 $r_i$，这些直角三角形的高度和不超过 $S$。求这 $n$ 个直角三角形的最大面积和。

inputFormat:
第一行两个整数 $n,S\ (1\le n\le 10^5,1\le S\le 10^{10})$，表示三角形个数和这些三角形的高度之和的最大值。

第二行 $n$ 个整数 $r_i\ (1\le r_i\le 10^5)$。

outputFormat: 输出这 $n$ 个直角三角形的最大面积和（保留 $10$ 位小数）。如果你的输出与答案的绝对误差或相对误差不超过 $10^{-6}$ 则认为你的输出正确。


title: 不死「徐福时空」

background:
徐福是秦朝齐地方士。

奉秦皇之命，徐福率三千童男童女踏上了寻找传说中的「蓬莱之药」的征途。但最后再也没有回来。

徐福最终去了哪里？有没有找到蓬莱之药？这些问题已经无关紧要了。

description:
时间的流逝可以抽象成对数字序列进行排序所花费的时间。不同排序策略花费的时间是不同的。这里介绍一种人类探索排序过程中具有里程碑意义的一种排序算法：希尔排序。

希尔排序可以被视为一种对插入排序的优化。为了研究希尔排序的运行效率，我们希望你实现一个简单的希尔排序的过程。在这之前，我们会规范插入排序的具体流程以及评价一个插入排序的过程的「代价」。

### 插入排序

对于一个长度为 $n$ 的数组 $a=[a_1,a_2,\cdots,a_n]$，插入排序的思想是，从前到后枚举每一个元素，将其插入到正确的位置上去：

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

如图所示是一个典型的插入排序的过程。在第 $i$ 轮中我们把下标为 $i$ 的元素插入到了**排好序的部分中第一个比 $\bm{a_i}$ 大的元素之前**。假设 $a_i$ 最终被插入到了 $b_i$ 位置，那么我们称这一轮的代价为 $|a_i-b_i|+1$，整个插入排序的过程的代价就是每一轮的代价之和。

### 希尔排序

为了减小插入排序的代价，我们引入了希尔排序。希尔排序将整个排序过程分成了若干轮，每一轮会按照一定的间隔把元素分组，对每一组内的元素分别进行排序。在最后一轮，希尔排序会对整个数组进行一次最终的插入排序。

具体的分组方式是，选定一个整数 $d$，划分为如下组别：

- 下标为 $1,1+d,1+2d,\cdots$ 的元素；
- 下标为 $2,2+d,2+2d,\cdots$ 的元素；
- 下标为 $3,3+d,3+2d,\cdots$ 的元素；
- ……
- 下标为 $d,2d,3d,\cdots$ 的元素。

下面是**一轮**希尔排序的过程。我们选定 $d=3$。

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

希尔排序每一轮分别选取 $d$，并且在最后一轮取 $d=1$，每一轮都进行这样的排序，最终得到一个有序的数组。

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

虽然看上去进行了很多轮插入排序，但是最终每一轮插入排序的代价之和可能会远小于对整个数组进行单次插入排序的代价（上述例子中体现得并不明显，可以参考样例 $2,3$ 给出的例子）。

事实上，希尔排序是人类发现的第一个最坏复杂度低于 $\Theta (n^2)$ 的排序算法。例如，当取 $d=2^k-1,\ k=\lfloor\log_2 n\rfloor,\lfloor\log_2 n\rfloor-1,\lfloor\log_2 n\rfloor-2,\cdots,1$ 时，整个过程的最坏时间复杂度为 $\mathcal \Theta(n^{3/2})$。

inputFormat:
第一行有两个整数 $n,m$，分别表示待排序的数组的长度以及希尔排序进行的轮数。

第二行有 $n$ 个整数 $a_1,a_2,\cdots,a_n$，描述数组里的元素。

第三行有 $m$ 个整数 $d_1,d_2,\cdots,d_m$，描述每一轮选取的 $d$ 的值。数据保证 $d_m=1$。

outputFormat:
第一行输出一个整数 $\mathrm{cost}$，表示整个希尔排序过程中插入排序产生的代价之和。

第二行输出 $n$ 个整数，表示数组 $a$ 排序后的结果。

hint:
### 数据范围及约定

对于全部数据，保证 $1\le n\le 10^5$，$1\le m\le 100$，$\mathrm{cost}\le 5\times 10^7$，$1\le a_i\le 10^9$，$1\le d_i\le n$，$d_m=1$。


title: [JOI Open 2016] 摩天大楼

background: **译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T3 「高層ビル街 / Skyscraper」**

description:
将互不相同的 $N$ 个整数 $A_1, A_2, \cdots, A_N$ 按照一定顺序排列。

假设排列为 $f_1, f_2, \cdots, f_N$，要求：$| f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N| \leq L$。

求满足题意的排列的方案数对 $10^9+7$ 取模后的结果。

inputFormat:
输入共两行。

第一行有两个整数 $N, L$。
第二行有 $N$ 个整数 $A_1, A_2, \cdots, A_N$。

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


title: [JOI Open 2016] 销售基因链

background:
**译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T2 「RNA 鎖の販売 / Selling RNA Strands」**

本题由于测试数据过多，仅在此提供部分测试数据，剩余数据请[于此测试](https://www.luogu.com.cn/problem/U288877)。

description:
基因库中有 $N$ 个字符串，这些字符串仅由 `A`，`G`，`U`，`C` 组成（保证每个字符串都包含四种字母）。

有 $M$ 组查询，每组查询包含两个字符串 $P,Q$，试求：基因库中有多少个字符串同时存在前缀 $P$ 和后缀 $Q$。

举个例子，`GAC` 存在前缀 `G`、`GA`、`GAC`，存在后缀 `C`、`AC`、`GAC`，那么我们可以说：`GAC` 同时存在前缀 `GA` 和后缀 `AC`。

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

第一行有两个整数 $N, M$。
在接下来的 $N$ 行中，每行一个字符串 $S_i$，表示基因库中的一个字符串。
在接下来的 $M$ 行中，每行有两个用空格分隔的字符串，表示一组查询。

outputFormat: 输出共 $M$ 行，每行一个整数，表示符合查询条件的字符串的数量。

samples:
8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA

hint:
### 样例 1 解释

第一组查询：无法找到；
第二组查询：`AUGC` 满足条件；
第三组查询：`AUGC` 和 `AGC` 满足条件。

### 样例 2 解释

注意基因库中的字符串可以重复。

### 数据规模与约定

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

对于所有数据，$1\le N, M \leq 10 ^ 5$，$1 \leq |S_i|, |P_j|, |Q_j| \le 10^5$，$1\le\sum |S_i|, \sum |P_j|, \sum |Q_j| \le 2\times 10^6$。

- Subtask 1（10 points）：$N, M, |S_i|, |P_j|, |Q_j| \le 100$。
- Subtask 2（25 points）：$N, M\le 5000$。
- Subtask 3（25 points）：$\sum |S_i|, \sum|P_j|, \sum |Q_j| \le 10^5$。
- Subtask 4（40 points）：没有额外限制。


title: [JOI Open 2016] JOIRIS

background: **译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T1 「JOIRIS」**

description:
JOIRIS 的游戏区域名叫「井」，是一个宽度为 $N$，高度足够大的矩形网格。位于左数第 $i$ 列，从下往上数第 $j$ 列的格子记作 $(i,j)$。游戏过程中，每个格子要不有一个方块，要不没有方块。

开始时，在第 $i$ 列有且仅有 $(i,1), (i,2),\cdots, (i, A_i)$ 有方块。

接下来，$10^4$ 个 $1 \times K$ 的骨牌一个个下落，玩家要依次放置骨牌。每次放置骨牌按照如下方式进行：

玩家先选择骨牌是横向放置还是纵向放置。
- 若选择纵向，玩家还需再选择一个整数 $x$（$1 \le x \le N$）。一个骨牌会下落到第 $x$ 列最上方方块的上面一行。若第 $x$ 列没有方块，骨牌会下落到井底。
- 若选择横向，玩家还需再选择一个整数 $x$（$1 \le x \le N-K+1$）。一个骨牌会下落到第 $x$ 列至第 $x+K-1$ 列最上方方块的上面一行。若第 $x$ 列至第 $x+K-1$ 列没有方块，骨牌会下落到井底。

每个骨牌停止下落后，系统将从井底往上逐行检查，如果有一行格子被方块填满，该行的所有方块都会消失，且上方的所有方块向下移动 $1$ 格。

此时检查井中是否有方块，如果井中没有方块，游戏结束，玩家胜利，否则玩家开始放置下一个骨牌。

保证开始时最底下一行没有被方块填满。请判断玩家能否胜利，如果可能，则输出一种方案。

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

第一行含有两个整数 $N,K$。
在接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）有一个整数 $A_i$。

outputFormat:
如果玩家无法胜利，请输出一行一个 $-1$。

否则请输出 $X+1$ 行，其中 $X$ 表示消去所有棋子所需要的步数：

第一行包含一个整数 $X$。接下来第 $i$ 行（$1 \le i \le X$）表示你的方案。

- 如果第 $i$ 个下落的骨牌纵向放置，输出两个整数，第一个整数为 $1$，第二个整数 $x$ 表示玩家放置零件的位置（如题目描述中所述）。
- 如果第 $i$ 个下落的骨牌横向放置，输出两个整数，第一个整数为 $2$，第二个整数 $x$ 表示玩家放置零件的位置（如题目描述中所述）。

hint:
### 样例 1 解释

![](https://www.z4a.net/images/2018/08/05/JOI-Open-16-T1.png)

### 数据规模与约定

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

对于所有数据，$2\le N\le 50$，$1\le K\le N$，$0\le A_i \le 50$。

- Subtask 1（15 points）：$K=2$ 且 $N$ 为奇数。
- Subtask 2（15 points）：$K=2$ 且 $N$ 为偶数。
- Subtask 3（15 points）：$K$ 能够整除 $N$。
- Subtask 4（55 points）：没有额外限制。


title: 时效「月岩笠的诅咒」

background:
蓬莱之药，被诅咒的不死之药。

奉命将蓬莱之药投入富士山中销毁的月岩笠，最终打算把蓬莱之药改投入八岳销毁。在下山途中妹红将其踹下山，抢到了蓬莱之药。

那已经是千年前的事情了。

description:
时间节点上发生过的两件事情的时间可被看作两实数 $a,b$。我们称两个事件满足「周年」关系，当且仅当可以通过执行以下两种操作（可以 $0$ 次）使其相等：

- 将 $a$ 加上 $1$，即 $a\gets a+1$；
- 将 $b$ 加上 $1$，即 $b\gets b+1$。

现在给定实数 $a,b$，询问它们是否满足「周年」。

inputFormat: 输入共一行两个实数 $a,b$。输入保留到小数点后 $12$ 位。

outputFormat: 输出共一行。如果存在合法方案，输出 $\verb!YES!$，否则输出 $\verb!NO!$。

hint: 对于全部数据，保证 $0<a,b\le 10^9$。


title: 「RiOI-03」Just a Q. (Easy ver.)

background:
「Yes, I am Q.」

面前的小 R 莞尔一笑。

+ 保证本题的任何合理的部分分或正解的 std + spj 均可以在当前数据下，$400$ ms 的时间限制、$32$ MB 的空间限制内正确运行并获得 AC 状态。
+ 本题不添加仅为无意义地卡满 spj 运行时间的 hack 数据。

**请注意，本题只有约束范围与困难版不同，且两个版本的约束范围并不完全重叠。**

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

小 R 有一个变量 $Q$。$Q$ 初始为 $0$。

小 R 有 $n$ 个隐藏的整数 $q_1 \dots q_n$，满足 $1 \leq \lvert q_i \rvert \leq V$，且有且仅有一个 $i$ 满足 $q_i \lt 0$，而面前的你，需要得出这个满足 $q_i \lt 0$ 的下标 $i$。

小 R 承诺不会让你以仅仅 $\frac{1}{n}$ 的几率盲猜，所以她可以允许你进行最多 $k$ 次询问。每次询问，你可以向小 R 给出**可重**正整数集合 $S$ 满足 $0 \leq \lvert S \rvert \leq S_{\max}$ 且 $\forall i \in S, i \leq n$，她会计算 $M = \prod\limits_{i\in S}q_i$，然后让 $Q \leftarrow Q + M$。特殊地，若 $S$ 为空集，则 $M = 1$。

一次询问后，小 R 会向你给出此时的 $\text{sgn}(Q)$（为 `+`，`-` 或 `0`），表示 $Q$ 的符号。具体地，若 $Q \gt 0$，小 R 返回 `+`；若 $Q \lt 0$，小 R 返回 `-`；否则返回 `0`。

请你在不超过 $k$ 次询问后，找到那个满足 $q_i \lt 0$ 的下标 $i$。

**保证对于所有数据，满足 $q_i \lt 0$ 的下标 $i$ 是在 $[1, n]$ 内均匀随机选取的。请注意报告下标属于一次询问。**

inputFormat:
### 交互格式

第一行，输入三个正整数 $n, k, S_{\max}$。

在此之后，你应当进行若干次询问。

对于你的每组询问，输出 $?\ m\ s_1\ s_2 \dots s_m$，表示给出一个**可重**正整数集合 $S$，其大小为 $m$，你需要保证 $0 \leq m \leq S_{\max}$。此外，同时应有 $1 \leq s_i \leq n$，描述这个集合里的元素编号。

如果你已经得到答案，请输出 $!\ i$，满足 $1 \leq i \leq n$，代表你得到 $q_i \lt 0$，在这之后你应当立即退出本轮交互。

每次你输出之后，请**刷新缓冲区**。

你可以使用如下语句来清空缓冲区：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

每次询问并刷新缓冲区后，你将从标准输入中输入一个字符，字符为 `+`，`-` 或 `0`，表示当前 $Q$ 的符号 $\text{sgn}(Q)$。

### 输入格式

本题有多组数据。

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

对于每一组数据，请按照 **【交互格式】** 进行交互。当你报告下标后：

+ 如果你给出的下标正确：
	+ 如果这是最后一组数据，交互库退出并返回 Accepted；
	+ 如果这不是最后一组数据，你应当接着读入 $n, k, S_{\max}$ 以进行下一组数据的交互。
+ 否则，下标错误，交互库会立刻终止，返回 Unaccepted。

outputFormat: 见 **【输入格式】**。

hint:
### 样例解释 1

$q = \{-1, 1, 4, 5, 1, 4\}$。

### 数据规模与约定

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

+ Subtask 0（5 pts）：$q_i \neq 1$ 且 $q_i \neq -1$。
+ Subtask 1（10 pts）：$q_i \neq -1$，$k = 2n$。
+ Subtask 2（10 pts）：$q_i \neq 1$，$k = 2n$。
+ Subtask 3（9 pts）：$n = 13$，$k = 5000$。
+ Subtask 4（11 pts）：$n = 13$，$k = 2500$。
+ Subtask 5（20 pts）：$k = 2n$。
+ Subtask 6（35 pts）：无特殊限制。

对于每组数据，$1 \leq n \leq 200$，$1 \leq V \leq 10^6$，$n \leq k \leq 5\times 10^3$，$S_{\max} = n$。

对于每个测试点，$1 \leq T \leq 500$，$\sum n^2 \leq 2\times 10^5$，$\sum k \leq 2\times 10^5$。


title: 「RiOI-03」A Journey to the Moonlight

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

（图片来自 phigros 曲绘，侵删。）

[加强版链接](/problem/P10286)

KDOI 的业务发展到月亮上了。但是月亮上网速很慢，他们需要解决网速问题。

KDOI 的工作人员研发了一种新型无线局域网模块 Wife（WIreless Fidelity Extend），每个模块最多连接两个用户，并且可以选择为其中一位客户提供 $1$ 单位带宽。不过，无论有多少个模块同时为一位客户提供带宽，他的总带宽永远是 $1$。

公司的员工都很懒，经常 ppt 一鸽就是一个月。因此，他们也懒得为 Wife 贴上标签，也就是所有模块间不做区分。另外，为了节省电费，不能有两个模块的工作客户范围完全相同。

现在有 $n$ 个用户购买了服务。当 Wife 系统正式启动时，鹿由器发现了一个问题：可能有些用户没有宽带可以使用！快斗现在手里没有 Wife，只能抢来一个，牺牲一个用户的利益，按一定顺序给所有包括有宽带的用户使用。然而，没有宽带的用户们要求很苛刻，只要没有给他们按注册顺序连续地提供宽带，他们就会威胁鹿由器退钱。

快斗已经忘了他们的注册时间了，只能随机选一个 $1\sim n$ 的排列来决定提供宽带的顺序。为了让尝试的次数尽量小，他会调整 Wife 连接的用户。他想知道，要让这些顾客平息愤怒，需要尝试的最小期望次数是多少。

特别的，Wife 有两种型号。型号 $1$ 可以选择只连接一位，型号 $2$ 则只能连接两个不同客户。你需要分别计算出这两种型号的答案。

快斗自己肯定~~不~~会做，所以他要让你求出所有 $i\in[0,n]$ 的结果 $ans_i$。考虑到你如果一个一个汇报会累死的，仁慈的鹿由器会给你数组 $a$，让你输出 $\sum a_i\times ans_i$。

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

对于一个右部点为 $m$ 个的二分图 $G$，定义它的权值 $w(G)$ 如下：

- 选择一种匹配方案，标记第一个已匹配的右部点。如果不存在这样的点，那么标记第一个未匹配的右部点。
- 每次随机选择一个 $1,2,\cdots,m$ 的排列，当未匹配的右部点与被标记的点 **按标号顺序作为一个子段出现在排列中时** 停止操作。
- $w(G)$ 为在所有匹配方案中操作次数期望的 **最小值**。

将这个二分图 $G$ 定义为 **$k$ 合法** 的，当且仅当：

- 所有左部点的度数在 $k\sim 2$ 之间。
- 没有任意两个左部点，与其相邻的点组成的集合相同。

定义 $f(k,x)$ 为所有右部点 $x$ 个，左部点不进行区分的 $k$ 合法二分图 $G$ 的 $w(G)$ 之和。

给定 $n,k,a_{0\sim n}$，求 $\sum\limits^n_ia_if(k,i) \bmod998244353$。

inputFormat:
一行两个正整数，分别表示 $n$ 与 Wife 的型号 $k$。

第二行 $n+1$ 个非负整数，分别表示 $a_{0\sim n}$。

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


title: 原神

background:
## 提示：题目背景与题目无关。

你说的对，但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界，在这里，被神选中的人将被授予「神之眼」，导引元素之力。你将扮演一位名为「旅行者」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘「原神」的真相。

因为你的素养很差，我现在每天玩原神都能赚 150 原石，每个月差不多 5000 原石的收入， 也就是现实生活中每个月 5000 美元的收入水平，换算过来最少也 30000 人民币，虽然我 只有 14 岁，但是已经超越了中国绝大多数人（包括你）的水平，这便是原神给我的骄傲的资本。

毫不夸张地说，《原神》是 miHoYo 迄今为止规模最为宏大，也是最具野心的一部作品。即便在经历了 8700 个小时的艰苦战斗后，游戏还有许多尚未发现的秘密，错过的武器与装备，以及从未使用过的法术和技能。

尽管游戏中的战斗体验和我们之前在烧机系列游戏所见到的没有多大差别，但游戏中各类精心设计的敌人以及 Boss 战已然将战斗抬高到了一个全新的水平。就和几年前的《塞尔达传说》一样，《原神》也是一款能够推动同类游戏向前发展的优秀作品。

description:
原神中有一个魔法师，她可以打出 $ n $ 次火元素攻击魔法和 $ m $ 次冰元素攻击魔法，每次攻击的伤害分别为 $ a_1,a_2,\cdots, a_n $ 和 $ b_1,b_2,\cdots, b_m $。

元素攻击之间存在如下反应规则：

- 每次元素攻击可以给**没有元素附着**的怪物附着相应的元素，初始时怪物没有元素附着；

- 如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 $ \times 2 $，**并清空元素附着**；

- 如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 $ +k $，**并清空元素附着**。

现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以从自己没有使用过的魔法中任意挑选一种使用。她希望最大化总伤害，请问**最大总伤害**是多少。

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

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

第三行 $ m $ 个整数 $ b_1,b_2,\cdots, b_m $。

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

samples:
见附件中的 samples/genshin4.in
见附件中的 samples/genshin4.ans

samples:
见附件中的 samples/genshin5.in
见附件中的 samples/genshin5.ans


title: [省选联考 2023] 火车站

description:
有 $n$ 个火车站排成一条直线，从 $1$ 到 $n$ 编号。一共有 $m$ 条火车轨道，每条轨道覆盖一段火车站区间 $[l_i, r_i]$。

对于一个被多条火车轨道覆盖的火车站，火车在经过这里的时候，可以在此处改变轨道。但是火车无法掉头，只能朝着一个方向运行（即只能一直往 $1$ 的方向开或者一直往 $n$ 的方向开）。

小 A 从火车站 $x$ 出发，即搭上了经过 $x$ 的任意一列火车（这列火车也可能是从车站 $x$ 出发）。这列火车可能行驶在火车站 $x$ 所处的任一条轨道上，其运行方向既可能是往 $1$ 的方向开，也可能是往 $n$ 的方向开。小 A 上车后就开始昏睡，直到乘坐的火车到达某条线路的终点站停下，他才醒过来。问小 A 最后可能到达的车站。

注意：火车应运行至少一个车站，且火车切换轨道后不会立刻停下来，而是会继续沿着当前轨道前进。

inputFormat:
输入的第一行包含三个正整数 $n, m, x$，分别表示火车站的数量，火车轨道的数量以及小 A 初始的起点。

接下来 $m$ 行，每行包含两个正整数 $l_i, r_i$，表示一条火车轨道运行的区间。

outputFormat: 输出一行，包含若干个用单个空格分隔的正整数，表示小 A 最后可能到达的车站，按照车站编号升序排序输出。


title: [省选联考 2023] 城市建造

description:
在这个国度里面有 $n$ 座城市，一开始城市之间修有若干条双向道路，导致这些城市形成了 $t \ge 2$ 个连通块，特别的，这些连通块之间两两大小差的绝对值不超过 $0 \le k \le 1$。为了方便城市建设与发展，$n$ 座城市中的某 $t$ 座城市**在这 $t$ 座城市之间**额外修建了至少一条双向道路，使得所有城市连通。

现在已经知道额外修建后的所有道路，你需要算出有哪些双向道路集合 $E'$，满足这些道路有可能是后来额外修建的，请输出答案对 $998,244,353$ 取模的结果。

即给定一张 $n$ 个点 $m$ 条边的**无向连通**图 $G = (V, E)$，询问有多少该图的子图 $G' = (V', E')$，满足 $E' \ne \varnothing$ 且 $G - E'$ 中恰好有 $|V'|$ 个连通块，且任意两个连通块大小之差不超过 $k$，保证 $0 \le k \le 1$，请输出答案对 $998,244,353$ 取模的结果。

inputFormat:
输入的第一行包含三个正整数 $n, m, k$，分别表示城市数、修建后的道路数以及任意两个连通块大小之差的上限。

接下来 $m$ 行每行包含两个正整数 $u, v$，表示城市 $u$ 和 $v$ 之间存在一条双向道路，保证 $u \ne v$。

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

samples:
见附件中的 cities/cities2.in
见附件中的 cities/cities2.ans

samples:
见附件中的 cities/cities3.in
见附件中的 cities/cities3.ans

samples:
见附件中的 cities/cities4.in
见附件中的 cities/cities4.ans


title: [省选联考 2023] 人员调度

background: **滥用本题评测将封号**。

description:
众所周知，一个公司的 $n$ 个部门可以组织成一个树形结构。形式化地，假设这些部门依次编号为 $1, \ldots, n$，那么除了 $1$ 号部门以外，第 $i \in [2, n]$ 个部门**有且仅有**一个上级部门 $p_i \in [1, i - 1]$。这样，这家公司的 $n$ 个部门可以视为一个以 $1$ 为根的树。如果 $i$ 是 $j$ 子树中的点，那么称部门 $i$ 是部门 $j$ 的子部门。

该公司初始时有 $k$ 名优秀员工，编号依次为 $1 \ldots k$。第 $i$ 名优秀员工初始时在第 $x_i$ 个部门工作，并且其有一个能力值 $v_i > 0$。

为了最大化公司的运作效率，公司老板 0/\\/\G 决定进行一些人员调动。具体来说，可以将编号为 $i$ 的优秀员工调动到 $x_i$ 的一个子部门，或者不调度（此时该员工在 $x_i$ 部门）。随后，优秀员工们会在其所在的部门竞选部门领导——能力值最高者将担任这一职位，并给公司带来等同于其能力值的贡献。如果一个部门一个优秀员工也没有，那么就无法选出部门领导，从而对公司的贡献将是 $0$。此时，公司的业绩被定义为公司各部门的贡献之和。

公司老板 0/\\/\G 自然想知道，该如何进行人员调动，使公司的业绩最大？

这当然难不倒他，然而，公司优秀员工的数量也会发生变化；具体来说，会依次发生 $m$ 个事件，每个事件形如：

- `1 x v`：先令 $k = k + 1$，然后新增一位编号为 $k$、初始部门为 $x$、能力值为 $v$ 的优秀员工；
- `2 id`：编号为 $\mathit{id}$ 的优秀员工将被辞退。

公司老板 0/\\/\G 希望你能在最开始和每个事件发生后，告诉他公司的业绩最大可能是多少？

注意，每次人员调动都是独立的，也就是每次计算公司的最大可能业绩时，每个优秀员工都会回到其所在的初始部门。

inputFormat:
输入的第一行包含一个正整数 $\mathit{sid}$，表示该测试点对应的数据范围以及特殊性质，详见后表；

输入的第二行包含三个整数 $n, k, m$，分别表示部门数，初始优秀员工数和事件数。

输入的第三行包含 $n - 1$ 个正整数 $p_2, \ldots, p_n$，表示每个部门的上级部门。

接下来 $k$ 行，每行包含两个正整数 $x_i, v_i$，表示优秀员工的初始部门和能力值。

接下来 $m$ 行，每行形如 `1 x v` 或 `2 id` 表示一次事件。

outputFormat: 输出一行包含 $m + 1$ 个由单个空格隔开的非负整数，依次表示最开始和每个事件发生后，公司的业绩可能的最大值。

samples:
见附件中的 transfer/transfer2.in
见附件中的 transfer/transfer2.ans

samples:
见附件中的 transfer/transfer3.in
见附件中的 transfer/transfer3.ans

samples:
见附件中的 transfer/transfer4.in
见附件中的 transfer/transfer4.ans

samples:
见附件中的 transfer/transfer5.in
见附件中的 transfer/transfer5.ans

samples:
见附件中的 transfer/transfer6.in
见附件中的 transfer/transfer6.ans

samples:
见附件中的 transfer/transfer7.in
见附件中的 transfer/transfer7.ans

samples:
见附件中的 transfer/transfer8.in
见附件中的 transfer/transfer8.ans

samples:
见附件中的 transfer/transfer9.in
见附件中的 transfer/transfer9.ans

samples:
见附件中的 transfer/transfer10.in
见附件中的 transfer/transfer10.ans

samples:
见附件中的 transfer/transfer11.in
见附件中的 transfer/transfer11.ans

samples:
见附件中的 transfer/transfer12.in
见附件中的 transfer/transfer12.ans

samples:
见附件中的 transfer/transfer13.in
见附件中的 transfer/transfer13.ans

samples:
见附件中的 transfer/transfer14.in
见附件中的 transfer/transfer14.ans

samples:
见附件中的 transfer/transfer15.in
见附件中的 transfer/transfer15.ans


title: 金盏花

description:
有一个十二位十进制数 $X$，你只知道它的后六位构成的数是 $Y$。

另外再给出一个整数 $Z$，你需要求出所有可能的 $X$ 中，$X$ 与 $Z$ 的差，即 $\lvert X - Z \rvert$ 的最小值。

注意，$X,Y,Z$ 都没有前导零（即最高位不是 $0$），$X,Y$ 分别要有恰好十二位和六位。

inputFormat: 第一行：两个整数 $Y,Z$。

outputFormat: 第一行：一个整数表示 $\lvert X - Z \rvert$ 的最小值。


title: 红草莓

description:
有一个由 $n$ 颗珍珠串成的项链，项链是一个环，首尾相连。其中有一颗珍珠上有特殊的记号，我们称它为**起始珍珠**。

有个外星人很会发射宇宙射线，他依次发射了 $m$ 轮宇宙射线，第 $i$ 轮有一个参数 $a_i$，表示：

- 外星人从起始珍珠开始数，起始珍珠是 $0$ 号，起始珍珠的下一个珍珠是 $1$ 号，以此类推（数完一圈后还会继续，例如 $n$ 号珍珠仍然是起始珍珠，$n+1$ 号珍珠是起始珍珠的下一个珍珠）。外星人会对编号为 $0,a_i,2a_i,\dots$ 这些 $a_i$ 倍数位置上的珍珠都发射一次宇宙射线。

一开始所有珍珠都是红色的，而当一个珍珠被发射宇宙射线后就会被从红色染成蓝色。

你需要输出：对于每轮操作，有多少个操作前为红色的珍珠被这轮操作变成了蓝色。

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

第二行：$m$ 个整数 $a_1,\dots,a_m$。

outputFormat: 第一行：$m$ 个整数，分别表示每轮操作中有多少个操作前为红色的珍珠被变为蓝色。


title: 黄玫瑰

description:
给定一张包含 $n$ 个点的简单有向无环图 $G$，点 $i$ 的点权设为 $w_i$，但**点权不是给定的**。

你需要构造一个包含至多 $2\times n$ 个点和恰好 $n$ 条边的有向无环图 $G'$，你需要为 $G'$ 的每条边钦定某个 $w_i$ 作为它的边权，使得 $G'$ 和 $G$ 的**最长路**长度相等。

在 $G$ 中一条路径的长度定义为其中所有点权和，$G'$ 中则为所有边权和。

然而，所有 $w_i$ 都不是给定的，所以你构造的 $G'$ 需要满足：对于任何一种可能的**正数**序列 $[w_1,\ldots,w_n]$，$G$ 和 $G'$ 的最长路长度都要相等。

请构造 $G'$，或说明它不存在。

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

接下来 $m$ 行：每行两个整数 $x,y$，表示存在一条点 $x$ 到点 $y$ 的有向边。

outputFormat:
如果不存在满足题意的 $G'$，则输出一行一个 $-1$。

否则，输出 $n+1$ 行：

第一行：一个整数 $N$，表示你构造的 $G'$ 的点数。

接下来 $n$ 行：每行三个整数 $x,y,z$，表示 $G'$ 中存在一条点 $x$ 到点 $y$ 的边，边权等于 $w_z$。

你需要保证 $0\leq N\leq 2\times n$，$1\leq x,y\leq N$，$1\leq z\leq n$。

若有多种可能的解，任意输出一个即可。

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

如下图，左为 $G$，右为 $G'$，颜色相同的点/边表示权值相同：

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

注意这只是一种可能的答案，其他正确的答案也可通过。

---

**【样例 #2 解释】**

下图为 $G$，不存在合法的 $G'$：

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

---

**【数据范围】**

对于全部数据：$1\leq n\leq 20000$，$1\leq m\leq 3\times 10^5$，$1\leq x,y\leq n$，保证给定的图无环且无重边。

|     子任务编号     | $n\leq$ |    $m\leq$     |           特殊性质            | 分值 |
| :----------------: | :-----: | :------------: | :---------------------------: | :--: |
| $\text{Subtask 1}$ | $5000$  |     $4999$     | $m=n-1$，每个点入度不超过 $1$ | $18$ |
| $\text{Subtask 2}$ | $5000$  |     $4999$     | $m=n-1$，每个点出度不超过 $1$ | $19$ |
| $\text{Subtask 3}$ |  $20$   |      $50$      |              无               | $20$ |
| $\text{Subtask 4}$ | $5000$  |    $10000$     |              无               | $21$ |
| $\text{Subtask 5}$ | $20000$ | $3\times 10^5$ |              无               | $22$ |

---

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


title: 紫丁香

description:
对于一个字符串 $A$，记 $A_i$ 表示它的第 $i$ 个字符。

设 $S$ 是任意长度为 $m$ 的 $01$ 串。我们有 $n$ 个操作，第 $i$ 个操作可以表示成一个定义域和值域都是长度为 $m$ 的 $01$ 串集合的函数 $f_i$，表示经过这次操作后 $S$ 会变成 $f_i(S)$。而函数 $f_i$ 可以由一个长度为 $m$ 的串 $T_i$ 表示，$T_i$ 由 $\texttt{0,1,-}$ 三种字符组成，其中：

- $T_{i,j}=\texttt{0}$ 表示 $[f_i(S)]_j=\texttt{0}$。

- $T_{i,j}=\texttt{1}$ 表示 $[f_i(S)]_j=\texttt{1}$。

- $T_{i,j}=\texttt{-}$ 表示 $[f_i(S)]_j=S_j$。

也就是说，每个操作会将 $S$ 的一些位赋值为 $0$，一些位赋值为 $1$，还有一些位不变。

现在有 $q$ 次操作，每次操作给定一个长度为 $m$ 的 $01$ 串 $S$，你可以对它做任意多次操作，操作的顺序任意，一个操作可以做多次。得到的串 $S'$ 可以被看做一个二进制数，求对应二进制数最大的 $S'$。

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

接下来 $n$ 行：每行一个长度为 $m$ 的串 $T$，表示一种操作。

接下来 $q$ 行：每行一个长度为 $m$ 的串 $S$，表示一个询问。

outputFormat: 输出 $q$ 行：每行一个长度为 $m$ 的串，依次表示每个询问的答案。


title: 白鹭兰

description:
有很多有关火星人的传说，比如他们的 DNA 非常复杂，他们有成千上万根手指等等，但这些都没有得到证实。同样没有得到证实的一个传说是火星人很会做 OI 题。

为了验证最后这个传说，地球人们给来自火星的外星旅人出了一道 OI 题：

> 给定一张 $n$ 个点 $m$ 条边的无向连通图 $G=(V,E)$，请找出最小的 $k$ 使得存在一个对点集的划分 $V_1,\ldots,V_t$ 使得：
>
> - $\forall 1\leq x\leq t$，$\bigcup_{i=1}^x V_i$ 的导出子图连通；
>
> - $\forall 1\leq x\leq t$，$\bigcup_{i=x}^t V_i$ 的导出子图连通；
>
> - $\forall 1\leq x\leq t$，$|V_x|\leq k$。
>
> 注意，作为划分，还需要满足 $\bigcup_{i=1}^t V_i=V$，$ V_i\cap V_j=\varnothing\ (\forall i\neq j)$，且所有 $V_i$ 非空。
>
> 请给出最小的 $k$ 以及对应的划分。

再见，You're 火星人。现在你需要完成这道题，证明火星人的智慧。

inputFormat:
第一行：两个整数 $n,m$，分别表示图 $G$ 的结点数和边数。

接下来 $m$ 行：每行两个整数 $x,y$，表示一条连接结点 $x,y$ 的无向边。

outputFormat:
第一行：两个整数 $k_{min},t$，分别表示最小的 $k$ 以及对应的划分大小。

接下来 $t$ 行：第 $i$ 行首先一个整数 $s_i$，表示 $V_i$ 的大小，然后 $s_i$ 个整数表示 $V_i$ 的元素。

如有多种划分方案，可以任意输出一种，注意你并不需要最小化 $t$。

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

如下图，$V_1,\ldots,V_5$ 分别是红色/橙色/绿色/蓝色/紫色点集，可以验证这满足题目条件。

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

---

**【评分方式】**

如果你的输出格式错误，将有可能不得分，也可能导致不可预知的错误。

如果你的输出格式正确，若你的 $k_{min}$ 正确，你将获得测试点 $50\%$ 的分数，若在此基础上你的构造方案正确，你将获得测试点 $100\%$ 的分数。

---

**【数据范围】**

对于全部数据：$2\leq n\leq 2\times 10^5$，$1\leq m\leq 2.3\times 10^5$，$1\leq x,y\leq n$，保证给出的 $m$ 条边中没有重边和自环，保证给出的图连通。

|     子任务编号     | $m\leq$ |        特殊限制        | 分值 |
| :----------------: | :-------------: | :--------------------: | :--: |
| $\text{Subtask 1}$ |     $2\times 10^5$     | $G$ 是链 | $10$ |
| $\text{Subtask 2}$ |      $10$       |         无          | $10$ |
| $\text{Subtask 3}$ |     $2000$      |         $G$ 是树          | $15$ |
| $\text{Subtask 4}$ |     $2000$      |         无          | $20$ |
| $\text{Subtask 5}$ |      $10^5$      |           $G$ 是树           | $15$ |
| $\text{Subtask 6}$ |     $2.3\times 10^5$     |           无           | $30$ |

---

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


title: 橙垒球

description:
垒球很喜欢一个叫迷你某·萨菲克斯的题，并且很崇拜这题的出题人，所以出了个差不多的题。

给定一个长度为 $n$ 的序列 $a_1,\ldots,a_n$，请构造一个**字典序最大**的长度为 $n$ 的字符串 $w$，使得：

- $w$ 的每个字符是 $1$ 到 $n$ 的整数，字符的大小顺序为 $1$ 最小 $n$ 最大；

- $w$ 的长度为 $i$ 的前缀的**字典序最大的后缀**长度恰为 $a_i$。

请输出这样的 $w$，或报告无解。

本题单个测试点包含多组数据。

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

接下来依次输入 $T$ 组数据，对于每组数据：

第一行：一个整数 $n$。

第二行：$n$ 个整数 $a_1,\ldots,a_n$。

outputFormat:
对于每组数据：

若无解，只输出一行一个 $-1$。

若有解，则输出一行 $n$ 个整数，表示你给出的 $w$。

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

字符串 $1,2,3$ 的每个前缀的最大后缀长度恰好为 $1,1,1$，且是满足这个条件的字典序最大的字符串。

字符串 $2,3,3$ 的每个前缀的最大后缀长度恰好为 $1,1,2$，且是满足这个条件的字典序最大的字符串。

不存在一个字符串，每个前缀的最大后缀长度恰好为 $1,1,3$。

字符串 $2,2,3$ 的每个前缀的最大后缀长度恰好为 $1,2,1$，且是满足这个条件的字典序最大的字符串。

不存在一个字符串，每个前缀的最大后缀长度恰好为 $1,2,2$。

字符串 $3,3,3$ 的每个前缀的最大后缀长度恰好为 $1,2,3$，且是满足这个条件的字典序最大的字符串。

---

**【评分方式】**

每个测试点的分数等于其中所有测试数据分数的最小值。一个测试数据的分数由以下方式确定：

如果你的输出格式错误（即不符合输出格式的要求），则不能得分。

否则，如果你正确判定了是否有解（即在无解的数据输出 $-1$，有解的数据输出了 $n$ 个 $[1,n]$ 中的数），则可以获得 $20\%$ 的分数。

在此基础上，如果该测试点无解，或者有解且你输出的是一组合法解（未必是字典序最大的），则可以再获得 $30\%$ 的分数。

在此基础上，如果该测试点无解，或者有解且你输出的是字典序最大的解，则可以再获得 $50\%$ 的分数。

---

**【数据范围】**

对于全部数据：$1\leq T\leq 10000$，$1 \le n \le 4 \times 10 ^ 6$，$\sum n\leq 4\times 10^6$，$1\leq a_i\leq i$。

|     子任务编号     |  $\sum n\leq$  | 特殊性质 | 分值 |
| :----------------: | :------------: | :------: | :--: |
| $\text{Subtask 1}$ | $4\times 10^6$ | 保证无解 | $1$  |
| $\text{Subtask 2}$ | $4\times 10^5$ | 保证有解 | $29$ |
| $\text{Subtask 3}$ | $4\times 10^6$ |    无    | $70$ |

---

**【提示】**

请使用较快速的输入输出方式。

---

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


title: [省选联考 2023] 过河卒

background: 棋盘上有一个过河卒，需要走到底线。卒行走的规则是可以向左移动一格，向右移动一格或者向前移动一格。同时在棋盘上有两个另一方的棋子，需要拦截这个卒走到底线。这两个棋子的走法和帅一致，可以走到前后左右四个方向上相邻的格子。因此本题可以称为“帅拦过河卒”。

description:
有一个 $n$ 行 $m$ 列的棋盘。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置。棋盘上有一些 障碍，还有一个黑棋子和两个红棋子。

游戏的规则是这样的: 红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 $(i,j)$，那么它可以走到 $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ 中的一个，只要这个目的地在棋盘内且没有障碍且没有红方的另一个棋子。

黑方每次可以将自己的棋子向三个方向之一移动一格。具体地，假设这个黑棋子位置在 $(i,j)$，那么它可以走到 $(i-1,j),(i,j-1),(i,j+1)$ 这三个格子中的一个，只要这个目的地在棋盘内且没有障碍。

在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断胜负（列在前面的优先）：

- 黑棋子位于第一行。此时黑方胜。

- 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。

- 当前玩家不能进行任何合法操作。此时对方胜。

现在假设双方采用最优策略，不会进行不利于自己的移动。也就是说:

- 若存在必胜策略，则会选择所有必胜策略中，不论对方如何操作，本方后续获胜所需步数最大值最少的操作。
- 若不存在必胜策略，但存在不论对方如何行动，自己都不会落败的策略，则会选择任意一种不败策略。
- 若不存在不败策略，则会选择在所有策略中，不论对方如何操作，对方后续获胜所需步数最小值最大的操作。

如果在 $100^{100^{100}}$ 个回合之后仍不能分出胜负，则认为游戏平局。请求出游戏结束时双方一共移动了多少步，或者判断游戏平局。

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

输入的第一行包含两个整数 $\text{id},T$，分别表示测试点编号和数据组数。特别地，样例的 $\text{id}$ 为 $0$。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含两个正整数 $n,m$，表示棋盘的行数和列数。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，其中第 $i$ 行的第 $j$ 个字符表示棋盘上 $(i,j)$ 这个位置的状态。

在这些字符中：$\texttt{'.'}$ 表示空位；$\texttt{'\#'}$ 表示障碍物；$\texttt{'X'}$ 表示黑棋；$\texttt{'O'}$ 表示红棋。

保证黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一行。

outputFormat:
对于每组数据，输出一行字符串。

如果游戏平局，请输出一行 $\texttt{"Tie"}$。

如果红方胜，请输出一行 $\texttt{"Red t"}$。其中 $\texttt{t}$ 为游戏结束时双方移动的步数之和。显然这应该是一个奇数。

如果黑方胜，请输出一行 $\texttt{"Black t"}$。其中 $\texttt{t}$ 为游戏结束时双方移动的步数之和。显然这应该是一个偶数。

注意，请输出双引号内的字符串，不包含双引号。

samples:
见附件中的 zu/zu2.in
见附件中的 zu/zu2.ans

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

第一组数据，红方第一步没有可行的移动，所以黑方胜。

第二组数据，无论第一步红方怎么移动，黑方都可以在下一步让黑棋子与红棋子在同一个位置。

第三组数据，无论第一步红方怎么移动，黑方都可以将自己的棋子往上移动一枚来达成胜利。

第四组数据，有一个红棋子不能动。另一个红棋子可以在第三行移动来防止黑棋子进入第一行。黑棋子也可以一直在第五行移动。如果红棋子到达第五行，黑棋子可以选择从另一边逃走。

第五组数据，在最后一行的那个红棋子可以从左边绕一圈抓住黑棋子。注意另一个红棋子可以移动。

**【样例 2 解释】**

这个样例中的每一组数据都满足测试点 $5$ 到 $13$ 中某一个测试点的限制。

**【子任务】**

对于所有的数据，保证：$1 \leq T \leq 10$，$2 \leq n \leq 10$，$1 \leq m \leq 10$，$\text{id}$ 等于测试点编号。

对于每组数据保证：棋盘上的黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一 行。

- 测试点 $1 \sim 4$：保证要么平局，要么红方在开始时无法移动。

- 测试点 $5 \sim 6$：保证 $n \geq 4$ 。保证棋盘上第 $n-1$ 行的每一个格子都是障碍物，且 棋盘上其他行没有障碍物。保证黑棋在前 $n-2$ 行，有一个红棋在前 $n-2$ 行，另一个红棋在第 $n$ 行。

- 测试点 $7 \sim 9$：保证 $m=1$。

- 测试点 $10 \sim 13$：保证要么平局，要么存在策略可以在 $9$ 步之内结束游戏。

- 测试点 $14 \sim 20$：无特殊限制。


title: [省选联考 2023] 填数游戏

description:
众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。

一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 $n$ 个 $[1,m]$ 范围内的正整数。等 Alice 写完，Bob **在看到 Alice 写的纸条之后开始写他的纸条**。

Alice 需要保证她写下的第 $i$ 个数在集合 $S_{i}$ 中，Bob 需要保证他写下的第 $i$ 个数在集合 $T_{i}$ 中。**题目保证** $1 \leq\left|S_{i}\right|,\left|T_{i}\right| \leq 2$ 。

Alice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 $n$ 个数 $b_{1}, \ldots, b_{n}$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。

即设 Alice 写下的数为 $a_{1}, \ldots, a_{n}$，Bob 写下的数为 $b_{1}, \ldots, b_{n}$，记 $X$ 为满足 $1 \leq i \leq n, a_{i}=b_{i}$ 的下标 $i$ 的个数，则

- Alice 希望最大化 $X,$
- Bob 在**保证 $b_{1}, \ldots, b_{n}$ 互不相同的前提下**希望最小化 $X$。

你首先想知道 Bob 能否保证他写下的 $n$ 个数互不相同。如果 Bob 能够做到，你想知道**在双方均采取最优策略的前提下** $X$ 的值会是多少。

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

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

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含两个正整数 $n,m$，表示纸条上需要写的数的个数和数的值域。

接下来 $n$ 行，每行输入的第一个整数为 $\left|S_{i}\right|$ 表示集合 $S_{i}$ 的元素个数，接下来输入 $\left|S_{i}\right|$ 个正整数描述 $S_{i}$ 中的元素。

接下来 $n$ 行，每行输入的第一个整数为 $\left|T_{i}\right|$ 表示集合 $T_{i}$ 的元素个数，接下来输入 $\left|T_{i}\right|$ 个正整数描述 $T_{i}$ 中的元素。

outputFormat: 对于每组测试数据输出一行：若 Bob 无法做到他写下的 $n$ 个数互不相同，输出 `-1`；否则输出在双方均予取最优策略的前提下 $X$ 的值。

samples:
见附件中的 game/game2.in
见附件中的 game/game2.ans

samples:
见附件中的 game/game3.in
见附件中的 game/game3.ans

samples:
见附件中的 game/game4.in
见附件中的 game/game4.ans

samples:
见附件中的 game/game5.in
见附件中的 game/game5.ans

samples:
见附件中的 game/game6.in
见附件中的 game/game6.ans

samples:
见附件中的 game/game7.in
见附件中的 game/game7.ans

samples:
见附件中的 game/game8.in
见附件中的 game/game8.ans

samples:
见附件中的 game/game9.in
见附件中的 game/game9.ans

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

在这组样例中，$S_{1}=\{3\}, S_{2}=T_{1}=\{1,2\}, S_{3}=T_{3}=\{3,4\}, T_{2}=\{2,3\}$。Alice 的填法有 $4$ 种，列举如下：

第一种：$a_{1}=3,a_{2}=1,a_{3}=3$。

第二种：$a_{1}=3,a_{2}=1,a_{3}=4$。

第三种：$a_{1}=3,a_{2}=2,a_{3}=3$。

第四种：$a_{1}=3,a_{2}=2,a_{3}=4$。

由于 Bob 必须保证他所填的数互不相同，所以他有以下填法:

第一种：$b_{1}=1,b_{2}=2,b_{3}=3$。

第二种：$b_{1}=2,b_{3}=3,b_{3}=4$。

第三种：$b_{1}=1,b_{2}=2,b_{3}=4$。

第四种：$b_{1}=1,b_{2}=3,b_{3}=4$。

若 Alice 选择第一种填法，则 Bob 为最小化 $X$，选择第二种填法，得到 $X=0$。

若 Alice 选择第二种填法，则 Bob 为最小化 $X$，选择第一种填法，得到 $X=0$。

若 Alice 选择第三种填法，则 Bob 为最小化 $X$，选择第一种填法，得到 $X=0$。

若 Alice 选择第四种填法，则 Bob 无论选择哪种填法，$X$ 均不小于 $1$。

因此，Alice 为最大化 $X$ 的值，她会选择第四种填法。

**【子任务】**

表格中 $\sum n,\sum m$ 分别表示同个测试点内所有测试数据的 $n$ 总和和 $m$ 总和。 $\sum n^{2}, \sum m^{2}, \sum n^{3}, \sum m^{3}$ 的含义类似。

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

特殊性质 A：对于任何 $1 \leq i \leq n,S_i$ 和 $T_i$ 互不相交，即 $S_i \cap T_i=\emptyset$。

特殊性质 B：$n \geq 3$，且对于任何 $1 \leq i<n, T_{1} =\{i,i+1\}$，且 $T_{n}=\{n,1\}$。

特殊性质 C：对于任何 $1 \leq i \leq n,|S_i|=1$。

特殊性质 D：对于任何 $1 \leq i \leq n,S_{i}=T_{i}$。

**【提示】**

本题部分测试点读入规模较大，我们建议你采取效率较高的读入方式。


title: [省选联考 2023] 染色数组

description:
给定一个长度为 $n$ 的正整数数组 $A$，其中每个数都在 $1$ 到 $m$ 之间，从左到右排成一排。现在要将每个数字染成红色或者绿色，我们定义一个染色方案为优秀的染色方案，当且仅当它满足：

1. 每个数 $A_{i}$ 要么被染成红色，要么被染成绿色。
2. 红色的数从左到右依次严格递增，绿色的数从左到右依次严格递减。

例如：$1\;9\;3\;4\;7\;6$ 中，将 $1\;3\;4\;7$ 染成红色，$9\;6$ 染成绿色是优秀的染色方案（$\color{red}1\color{green}9\color{red}347\color{green}6$）；$1\;3\;4\;6$ 染成红色，$9\;7$ 染成绿色也是优秀的染色方案（$\color{red}1\color{green}9\color{red}34\color{green}7\color{red}6$）。但是将 $1\;4\;7\;6$ 染成红色，$9\;3$ 染成绿色则**不是**优秀的染色方案，因为 $1\;4\;7\;6$ 不是递增的。$1\;9\;5\;5$ 中，将 $1$ 和任意一个 $5$ 染色红色，$9$ 和另一个 $5$ 染成绿色，也是优秀的染色方案（其中一种是 $\color{red}1\color{green}95\color{red}5$）。

如果一个数组**至少存在两个不同的**优秀的染色方案，那么称这个数组是**完美**的。（两个染色方案不同当且仅当至少存在一个位置上的数字被染成不同的颜色）。

例如，$1\;9\;3\;4\;7\;6$ 和 $1\;9\;5\;5$ 都是完美的，因为上面已经分别给出了 $2$ 种优秀的染色方案。而 $2\;3\;3\;3$ 则不是完美的，因为找不到任何一种优秀的染色方案。同时 $1\;5\;3\;6\;4$ 也不是完美的，因为仅存在一种优秀的染色方案（$\color{red}1\color{green}5\color{red}36\color{green}4$）。

补充说明：如果红色的数只有 $0$ 个或者 $1$ 个，我们也认为它严格递增；同理如果绿色的数只有 $0$ 个或者 $1$ 个，我们也认为它严格递减。例如 $\color{red}123$，$\color{red}1\color{green}2\color{red}3$ 都是优秀的的染色方案，因此 $1\;2\;3$ 是完美的数组。

我们定义一种给染色方案打分的方式。

对于每个的有序元素对 $A_{i}, A_{j}(i<j)$ :

1. 如果 $A_{j}$ 染成红色，且 $A_{j}<A_{i}$，则该元素对得 $m-A_{j}+1$ 分;
2. 如果 $A_{j}$ 染成绿色，且 $A_{j}>A_{i}$，则该元素对得 $A_{j}$ 分;
3. 不满足 1 或 2 ，则该元素对得 $0$ 分。

则一个染色方案的得分为所有有序元素对的得分和。

一个完美的数组的得分为它所有优秀的染色方案的得分的最大值。

现在确定数组 $A$ 的前 $t$ 个数 $A_{1}, A_{2}, \ldots, A_{t}$, 你需要回答以下两个问题:

- 第一问：有多少种确定 $A$ 中后 $n-t$ 个数的方案使得 $A$ 是一个完美数组？
- 第二问：所有可能的完美数组的得分和是多少？

由于答案太大，你只需要输出答案在模 $998244353$ 下的结果即可。

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

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

接下来包含 $C$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n, m, t$，分别表示数组长度，数组内数字的最大值和确定的前缀长度。

第二行包含 $t$ 个正整数 $A_{1} \ldots A_{t}$，表示已经确定的前缀。

outputFormat:
对于每组测试数据输出一行包含两个用单个空格隔开的整数。

- 第一个整数表示优秀数组的数量模 $998244353$ 的值；

- 第二个整数表示优秀数组的得分之和模 $998244353$ 的值。

samples:
见附件中的 color/color2.in
见附件中的 color/color2.ans

hint:
**【评分方式】**

每个测试点 $5$ 分。

每一行应按顺序输出两问的答案，不符合输出格式的输出得 $0$ 分。

程序仅回答对第一问得 $1$ 分，仅回答对第二问得 $4$ 分，两问都答对得 $5$ 分。

如果你不回答第一问或第二问，也需要在对应位置上输出任意一个整数以满足输出格式。

**【子任务】**

对于所有的数据，保证： $1 \leq C \leq 5$；$2 \leq n \leq 50$；$1 \leq t \leq n$；$1 \leq m \leq 200$；$1 \leq A_{i} \leq m$ 。

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


title: [USACO23OPEN] FEB B

description:
Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out
over $N$ text messages. Their conversation can be
represented by a string $S$ of length $N$ where $S_i$ is either `B` or `E`,
meaning the $i$ th message was sent by Bessie or Elsie, respectively.

However, Farmer John hears of the plan and attempts to intercept their
conversation. Thus, some letters of $S$ are `F`, meaning Farmer John obfuscated
the message and the sender is unknown.

The  **excitement level** of a non-obfuscated conversation is the number of
times a cow double-sends - that is, the number of occurrences of substring `BB`
or `EE` in $S$. You want to find the excitement level of the original message,
but you don’t know which of Farmer John’s messages were actually Bessie’s
/ Elsie’s. Over all possibilities, output all possible excitement levels of
$S$.

inputFormat:
The first line will consist of one integer $N$.

The next line contains $S$.

outputFormat:
First output $K$, the number of distinct excitement levels possible. On the next
$K$ lines, output the excitement levels, in increasing order.

translation:
### 题目描述
贝西和埃尔希正在密谋最终推翻他们的主人——农夫约翰！他们通过 $N$ 条短信进行计划。他们的对话可以用一个长度为 $N$ 的字符串 $S$ 来表示。
其中 $S_i$ 是字母 ```B``` 或 ```E```，这意味着第 $i$ 条消息分别由贝西或埃尔希发送的。

然而，农夫约翰听说了这个消息，并试图拦截他们的谈话。因此，字符串 $S$ 的一些字母是 ```F```，这意味着农夫约翰混淆了信息，发件人未知（贝西、埃尔希都有可能）。
**注：约翰没有发送信息！他只是在干扰奶牛间的通话！**

未混淆对话的兴奋程度是**一只奶牛重复发送信息的次数**。也就是说，子串 ```BB``` 或 ```EE``` 在 $S$ 中出现的次数。你想找到原始信息的兴奋程度，但你不知道约翰的信息中哪一条实际上是贝西或埃尔希的。在所有可能的情况下，**从小到大输出**所有可能的兴奋程度。

### 输入格式
第一行：一个整数 $N$（通话长度）。
第二行：一个字符串 $S$（通话内容）。

### 输出格式
第一行：输出一个整数 $K$，为**不同**兴奋程度的可能数量。
随后 $K$ 行：每行一个整数，为每种兴奋程度。**注意按照从小到大的顺序输出。**

### 数据范围
$1 \le N \le 2 \times 10^5$。
- 测试点 4~8：$N \le 10$
- 测试点 9~20：无额外限制。

hint:
$1\le N\le 2\cdot 10^5$.

- Inputs 4-8: $N\le 10$.
- Inputs 9-20: No additional constraints.


title: [USACO23OPEN] Moo Language B

background:
Farmer John is interested in better interacting with his fellow cows, so he
decided he will learn the moo language!

description:
Moo language is actually quite similar to English, but more minimalistic. There
are only four types of words: nouns, transitive verbs, intransitive verbs, and
conjunctions. Every two consecutive words must be separated by a space.  There
are also only two types of punctuation: periods and commas.  When a period or
comma appears after a word, it appears directly after the word, and is then
followed  by a space if another word appears next.

A sentence needs to follow one of the following formats:
- Type 1: noun + intransitive verb.
- Type 2: noun + transitive verb + noun(s). Specifically, at least one noun
must follow the transitive verb, and there must be a comma in front of every
following noun besides the first following noun.

Two sentences may be joined into a compound sentence if a conjunction is placed
in between them.  The resulting compound sentence cannot be further joined with
other sentences or other compound sentences.  Every sentence (or compound
sentence, if two sentences are joined) must end with a period.

Farmer John has a word bank of $N$ words, $C$ commas, and $P$ periods. He may only use a word or punctuation mark as
many times as it appears in the word bank. Help him output a sequence of
sentences containing the maximum possible number of words.

Each input file contains $T$ independent instances of this
problem.

inputFormat:
The first line contains $T$, the number of instances. Each instance is specified
as follows:

The first line consists of three integers $N, C$ and $P$.

The $N$ following lines will consist of two strings. The first string will be
the word itself that FJ can use (a string of at least $1$ and at most $10$ lowercase
letters), and the second string will be either one of the following: noun,
transitive-verb, intransitive-verb, or conjunction, denoting the type of the
word. It is possible the same word occurs more than once in FJ's word bank, but
it will always have the same type each time it appears.

outputFormat:
In the first line, output the maximum possible number of words.

In the second line, output any sequence of sentences with the maximum possible
number of words. Any valid sequence will be accepted.

**The grader is sensitive to whitespace, so make sure not to output any
extraneous spaces, particularly at the end of each line.**

translation:
### 题目背景

FJ 对与奶牛更好地互动感兴趣，所以他决定学习 moo 语言！

### 题目描述

moo 语言与英语相似，但更为简单。单词只有四种类型：名词、及物动词、不及物动词和连词，每两个单词之间必须用空格隔开。标点符号仅包含逗号和句号，它会跟在单词后面，若该标点符号后面存在单词，则需要隔一个空格再放单词。

对于每个句子，都需要遵循以下格式中的一条：

1. 名词+不及物动词。
2. 名词+及物动词+名词（可以有多个）。及物动词后面必须有至少一个名词。除及物动词后面的第一个名词外，后面的每个名词前面都必须加一个逗号。

也可以在两个句子之间加一个连词，形成复合句，复合句不能与其他句子用连词连接。每一个句子（包括复合句）都必须以句号结尾。

FJ 的词库中有 $N$ 个单词、$C$ 个逗号和 $P$ 个句号。每个单词的使用次数不能超过这个单词在词库中出现的次数。现在，你要帮他输出几个符合以上要求的句子，使总单词数尽量多。

每个输入文件中共包含 $T$ 组样例。

### 输入格式

第一行输入 $T$，表示样例组数。对于每组样例，格式如下：

第一行输入三个正整数 $N$、$C$ 和 $P$。

在接下来的 $N$ 行，每行输入两个字符串。第一个字符串输入一个 FJ 可以用的单词（全为小写字母，长度为 $1$ 至 $10$），第二个字符串为以下字符串中的任意一个，表示该单词的类型：

- `noun`（名词）；
- `transitive-verb`（及物动词）；
- `intransitive-verb`（不及物动词）；
- `conjunction`（连词）。

同一个单词可能在词库中出现多次，但是每次出现时它们的类型都相同。

### 输出格式

第一行输出组成符合以上要求的句子序列的最大单词数。

在第二行中，输出句子序列，使单词数最多。本题开启 SPJ，任何符合以上要求的句子序列均可通过。

**请不要输出多余的空格，尤其是在每行末尾。**

translated by [liyuanchen2021](https://www.luogu.com.cn/user/557680)

samples:
3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

samples:
0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.

hint:
$1\le T\le 100$，$1 \leq P,C\le N \leq 10^3$.

- Inputs 2-6: $N\le 10$.
- Inputs 7-11: $N\le 100$.
- Inputs 12-16: $N\le 1000$.
- Inputs with remainder 2 when divided by 5: There are no transitive
verbs.
- Inputs with remainder 3 when divided by 5: There are no intransitive
verbs.
- Inputs with remainder 4 when divided by 5: There are no conjunctions.


title: [USACO23OPEN] Rotate and Shift B

description:
**Note: The time limit for this problem is 4s, 2x the default.**

To celebrate the start of spring, Farmer John's $N$ cows have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way.

Specifically, there are $N$ positions around the circle, numbered sequentially from $0$ to $N-1$, with position $0$ following position $N-1$.  A cow resides at each position.  The cows are also numbered sequentially from $0$ to $N-1$.  Initially, cow $i$ starts in position $i$.  You are told a set of $K$ positions $0=A_1<A_2<\dots<A_K<N$ that are "active", meaning the cows in these positions are the next to move.

In each minute of the dance, two things happen.  First, the cows in the active positions rotate: the cow at position $A_1$ moves to position $A_2$, the cow at position $A_2$ moves to position $A_3$, and so on, with the cow at position $A_K$ moving to position $A_1$.  All of these $K$ moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow.  Next, the active positions themselves shift:
$A_1$ becomes $A_1+1$, $A_2$ becomes $A_2+1$, and so on (if $A_i = N-1$ for some active position, then $A_i$ circles back around to $0$).

Please calculate the order of the cows after $T$ minutes of the dance.

inputFormat:
The first line contains three integers $N, K$ and $T$.

The second line contains $K$ integers representing the initial set of active positions
$A_1,A_2, \dots, A_K$.  Recall that $A_1 = 0$ and that these are given in increasing order.

outputFormat:
Output the order of the cows after $T$ minutes, starting with the cow in position $0$, separated by
spaces.

translation:
为了庆祝春天的开始，FJ 的 $N$ 头奶牛发明了一个有趣的新舞蹈。在这个舞蹈中，他们站成一个圆圈，并以一种给定的方式移动。

具体地，圆圈上有 $N$ 个位置，按顺序分别编号为 $0$ 至 $N - 1$，其中位置 $N - 1$ 之后是位置 $0$。每个位置都有恰好一头奶牛。奶牛也按顺序分别编号为 $0$ 至 $N - 1$。初始状态中，编号为 $i$ 的奶牛位于编号为 $i$ 的位置。在圆圈上，有 $K$ 个活跃位置 $0 = A_1 < A_2 < \dots < A_K < N$，在活跃位置上的奶牛将会移动。

在舞蹈的每一分钟里，都会发生两件事。首先，在活跃位置上的奶牛会发生轮换：在 $A_1$ 位置的奶牛移到 $A_2$ 位置，在 $A_2$ 位置的奶牛移到 $A_3$ 位置……在 $A_K$ 位置的奶牛移到 $A_1$ 位置。所有 $K$ 个移动同时发生，因此，在轮换结束后，每个活跃位置上仍有恰好一头奶牛。接下来，活跃位置会发生变换：$A_1$ 变为 $A_1 + 1$，$A_2$ 变为 $A_2 + 1$，以此类推（若某个活跃位置满足 $A_i = N - 1$，则 $A_i$ 变为 $0$）。

请求出舞蹈持续 $T$ 分钟后奶牛的顺序。

hint:
For the example above, here are the cow orders and $A$ for the first four timesteps:
```
Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3]
T = 1: order = [3 1 0 2 4]
T = 1: A = [1 3 4]
T = 2: order = [3 4 0 1 2]
T = 2: A = [2 4 0]
T = 3: order = [2 4 3 1 0]
T = 3: A = [3 0 1]
T = 4: order = [1 2 3 4 0]
```

$1 \leq K \leq N \leq 2 \cdot 10^5$, $1\le T\le 10^9$.

- Inputs 2-7: $N \leq 1000, T \leq 10000$.
- Inputs 8-13: No additional constraints.


title: [USACO23OPEN] Milk Sum S

description:
**Note: The time limit for this problem is 4s, 2x the default.**

Farmer John's $N$ cows have integer milk production
values $a_1,\dots,a_N$.  That is, the $i$ th cow produces $a_i$ units of milk per
minute.

Each morning, Farmer John starts with all $N$ cows hooked up to his milking
machine in the barn.  He is required to unhook them one by one, sending them out
for their daily exercise routine.  The first cow he sends out is unhooked after
just 1 minute of milking, the second cow he sends out is unhooked after another
minute of milking, and so on.  Since the first cow (say, cow $x$) only spends
one minute on the milking machine, she contributes only $a_x$ units of total
milk.  The second cow (say, cow $y$) spends two total minutes on the milking
machine, and therefore contributes $2a_y$ units of total milk.  The third cow
(say, cow $z$) contributes $3a_z$ total units, and so on.  Let $T$ represent the
maximum possible amount of milk, in total, that Farmer John can collect, if he
unhooks his cows in an optimal order.

Farmer John is curious how $T$ would be affected if some of the milk production
values in his herd were different.  For each of $Q$ queries,
each specified by two integers $i$ and $j$, please calculate what would be the
new value of $T$ if $a_i$ were set to $j$.  Note that
each query is considering a temporary potential change independent of all other
queries; that is, $a_i$ reverts back to its original value before the next query
is considered.

inputFormat:
The first line contains $N$.

The second line contains $a_1\dots a_N$.

The third line contains $Q$.

The next $Q$ lines each contain two space-separated integers $i$ and $j$.

outputFormat: Please print the value of $T$ for each of the $Q$ queries on separate lines.

translation: 给定数组 $a_1,...,a_N$ 在数组中依次选出一个元素构成排列 $b_1,...,b_N$ 。定义 $T = \sum _{i=1} ^N i \times b_i $ 。现在给出 $Q$ 个操作，每个操作有两个数 $x$ 和 $y$ 表示将 $a_x$ 替换成 $y$ ，对于每一个操作求出操作后的 $T$ 的最大值，每次操作后数组还原成原样。

hint:
For the first query, $a$ would become $[1,1,4,2,6]$, and
$T =
1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 4 + 5 \cdot 6 = 55$.

For the second query, $a$ would become $[1,8,4,2,6]$, and
$T =
1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 6 + 5 \cdot 8 = 81$.

For the third query, $a$ would become $[1,10,4,5,6]$, and
$T =
1 \cdot 1 + 2 \cdot 4 + 3 \cdot 5 + 4 \cdot 6 + 5 \cdot 10 = 98$.

$1\le N\le 1.5\cdot 10^5$, $0 \leq a_i \leq 10^8$,$1\le Q\le 1.5\cdot 10^5$，$0 \leq j \leq 10^8$.

- Inputs 2-4: $N,Q\le 1000$.
- Inputs 5-11: No additional
constraints.


title: [USACO23OPEN] Field Day S

description:
**Note: The time limit for this problem in Python is 15s.  Other languages have the default time limit of 2s.**

Each of Farmer John's $N$ barns has selected a team of $C$
cows to participate in field day. The breed of every cow is
either a Guernsey or a Holstein.

The difference between two teams is defined to be the number of positions $i$
($1 \leq i \leq C$) at which the breeds of the cows in the $i$ th positions
differ. For every team $t$ from $1 \ldots N$, please compute the maximum
difference between team $t$ and any other team.

inputFormat:
The first line contains $C$ and $N$.

The next $N$ lines each contain a string of length $C$ of `G`s and `H`s.  Each line
corresponds to a team.

outputFormat: For each team, print the maximum difference.

translation:
### 题目描述

**提示：本题的 Python 时限为 15s。其它语言默认 2s。**

Farmer John 的 $N$ 个牛棚都会选出包含 $C$ 只奶牛的队伍去参加户外聚会。所有奶牛的品种都只可能是根西牛（`G`）或荷斯坦奶牛（`H`）。

我们将两个奶牛队伍中，同一位置对应的两头奶牛品种不同的所有位置 $i(1 \leq i \leq C)$ 的个数，定义为的两个奶牛队伍的差异。对于编号 $1...N$ 的每个奶牛队伍 $t$，请计算出 $t$ 和其它所有队伍的差异的最大值。

### 输入格式

第一行包含两个整数 $C$ 与 $N$。

接下来 $N$ 行，每行有一个长度为 $C$ 的，仅包含字母 `G` 和 `H` 的字符串，每行对应一支奶牛队伍。

### 输出格式

对于每个队伍，输出差异最大值。

### 说明/提示

第一个和第三个队伍的差异为 $5$。第二个和第三个队伍的差异为 $3$。

$2 \leq N \leq 10^5,1 \leq C \leq 18$。

- 对于测试点 2-5：$C = 10$。
- 对于测试点 6-9：所有答案最少为 $C - 3$。
- 对于测试点 10-20：没有额外条件。

hint:
The first and third teams differ by $5$. The second and third teams differ by
$3$.

$2\le N\le 10^5$, $1\le C\le 18$.

- Inputs 2-5: $C = 10$.
- Inputs 6-9: All answers are at least $C-3$.
- Inputs 10-20: No additional constraints.


title: [USACO23OPEN] Pareidolia S

background:
**Note: The time limit for this problem is 4s, 2x the default.**

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in
images where none really exist -- for example seeing a face in a cloud.  As you
might imagine, with Farmer John's constant proximity to cows, he often sees
cow-related patterns in everyday objects.  For example, if he looks at the
string "bqessiyexbesszieb", Farmer John's  eyes ignore some of the letters and
all he sees is "bessiebessie".

description:
Given a string $s$, let $B(s)$ represent the maximum number of repeated copies
of "bessie" one can form by deleting zero or more of the characters from $s$.
In the example above, $B(\text{``bqessiyexbesszieb"}) = 2$.

Computing $B(s)$ is an interesting challenge, but Farmer John is interested in
solving a challenge that is even more interesting: Given a string $t$ of length
at most $3\cdot 10^5$ consisting only of characters a-z, compute the sum of
$B(s)$ over all contiguous substrings $s$ of $t$.

inputFormat:
The input consists of a nonempty string of length at most $3\cdot 10^5$ whose
characters are all lowercase English letters.

outputFormat:
Output a single number, the total number of bessies that can be made across all
substrings of the input string.

translation: Farmer John有的时候看东西会忽略一些字母，如把 `bqessiyexbesszieb` 看成 `bessiebessie`。定义 $B(s)$ 表示把 $s$ 中的若干个字母删去后，形成尽量多个 `bessie` 相连的形式 (`bessiebessiebessieb...`)，返回 `bessie` 的最大数量。如 $B(\text{"bqessiyexbesszieb"})=2$。对字符串 $s$ 计算 $B(s)$ 是一个有趣的挑战，但FJ想到了一个更有趣的挑战：对 $s$ 的所有子串进行计算B函数，并求和。$s$ 的长度不超过 $3\times 10^5$。

hint:
For the first sample, twelve substrings contain exactly $1$ "bessie", and $1$ string contains exactly $2$ "bessie"s, so the total is $12\cdot 1+1\cdot 2=14$.

- Inputs 3-5: The string has length at most $5000$.
- Inputs 6-12: No additional constraints.


title: [USACO23OPEN] Custodial Cleanup G

description:
Due to the disorganized structure of his mootels (much like motels but with
bovine rather than human guests), Farmer John has decided to take up the role of
the mootel custodian to restore order to the stalls.

Each mootel has $N$ stalls labeled $1$ through $N$ and $M$ corridors that connect pairs of stalls to each other
bidirectionally. The $i$ th stall is painted with color $C_i$ and initially has a
single key of color $S_i$ in it. FJ will have to rearrange the keys to appease
the cows and restore order to the stalls.

FJ starts out in stall $1$ without holding any keys and is allowed to repeatedly
do one of the following moves:
- Pick up a key in the stall he is currently in. FJ can hold multiple keys at
a time.
- Place down a key he is holding into the stall he is currently
in. A stall may hold multiple keys at a time.
- Enter stall $1$ by
moving through a corridor.
- Enter a stall other than stall $1$ by
moving through a corridor. He can only do this if he currently holds a key that
is the same color as the stall he is entering.

Unfortunately, it seems that the keys are not in their intended locations. To
restore order to FJ's mootel, the $i$th stall requires that a single key of
color $F_i$ is in it. It is guaranteed that $S$ is a permutation of $F$.

For $T$ different mootels, FJ starts in stall $1$ and needs
to place every key in its appropriate location, ending back in stall $1$. For
each of the $T$ mootels, please answer if it is possible to do this.

inputFormat:
The first line contains $T$, the number of mootels (test cases).

Each test case will be preceded by a blank line. Then, the first line
of each test case contains two integers $N$ and $M$.

The second line of each test case contains $N$ integers. The $i$-th integer on
this line $C_i$ means that stall $i$ has color $C_i$.

The third line of each test case contains $N$ integers. The $i$-th integer on
this line $S_i$ means that stall $i$ initially holds a key of color $S_i$.

The fourth line of each test case contains $N$ integers. The $i$-th integer on
this line $F_i$ means that stall $i$ needs to have a key of color $F_i$ in it.

The next $M$ lines of each test case follow. The $i$-th of these lines contains
two distinct integers $u_i$ and $v_i$. This represents
that a corridor exists between stalls $u_i$ and $v_i$. No corridors are
repeated.

outputFormat:
For each mootel, output `YES` on a new line if there exists a way for FJ to return
a key of color $F_i$ to each stall $i$ and end back in stall $1$. Otherwise,
output `NO` on a new line.

translation:
奶牛旅馆可以被看作一个 $N$ 个节点 $M$ 条边的无向简单图，其中每个房间有一个颜色 $C_i$，以及一个钥匙，颜色为 $S_i$， FJ 最初在 $1$ 号节点，手上一把钥匙都没有。

FJ 可以进行无数次以下操作：

- 捡起当前房间的钥匙。（FJ 可以同时手持多个钥匙）

- 将部分或全部手上的钥匙放在当前房间。 (房间内可以同时放多把钥匙)

- 通过一条边，移到一个相邻的房间，前提是目标房间是房间 $1$, 或者 FJ 拥有至少一个目标房间颜色的钥匙。

已知 $F$ 是 $S$ 的排列， FJ 想要让每个房间里面都恰好有一个 $F_i$ 颜色的钥匙，并且最后回到 $1$ 号点。求是否可能。

有 $T$ 组数据，每组数据由一个空行开始，接着先给定 $3$ 行每行 $N$ 个整数，分别表示 $C$,$S$,$F$，最后给定 $M$ 行，每行两个整数表示一条边。

by [Error_Eric](/user/217300).

hint:
For the first test case of the first sample, here is a possible sequence of moves:

```
Current stall: 1. Keys held: []. Keys in stalls: [3, 4, 3, 4, 2]
(pick up key of color 3)
Current stall: 1. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(move from stall 1 to 2, allowed since we have a key of color C_2=3)
Current stall: 2. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(pick up key of color 4)
Current stall: 2. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(move from stall 2 to 1 to 4 to 5, allowed since we have keys of colors C_4=4 and C_5=3)
Current stall: 5. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(pick up key of color 2 and place key of color 3)
Current stall: 5. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(move from stall 5 to 4 to 1 to 3, allowed since we have keys of colors C_4=4 and C_3=2)
Current stall: 3. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(pick up key of color 3 and place key of color 4)
Current stall: 3. Keys held: [2, 3]. Keys in stalls: [x, x, 4, 4, 3]
(move from stall 3 to stall 2 and place key of color 3)
Current stall: 2. Keys held: [2]. Keys in stalls: [x, 3, 4, 4, 3]
(move from stall 2 to stall 1 and place key of color 2)
Current stall: 1. Keys held: []. Keys in stalls: [2, 3, 4, 4, 3]
```

For the second test case of the first sample, there exists no way for FJ to return a key of color
$F_i$ to each stall $i$ and end back at stall $1$.

$0 \le M \le 10^5$, $1 \le C_i, S_i, F_i, u_i, v_i \le N \le 10^5$.
$1 \le T \le 100$, $1 \le \sum N \le 10^5$, $1 \le \sum M \le 2\cdot 10^5$.

- Test cases 3-6 satisfy $N,M\le 8$.
- Test cases 7-10 satisfy $C_i=F_i$.
- Test cases 11-18 satisfy no additional constraints.


title: [USACO23OPEN] Pareidolia P

description:
Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string `bqessiyexbesszieb`, Farmer John's eyes ignore some of the letters and all he sees is `bessiebessie`.

Given a string $s$, let $B(s)$ represent the maximum number of repeated copies of `bessie` one can form by deleting zero or more of the characters from $s$. In the example above, $B(bqessiyexbesszieb)=2$. Furthermore, given a string $t$, let $A(t)$ represent the sum of $B(s)$ over all contiguous substrings $s$ of $t$.

Farmer John has a string t of length at most $2\times10^5$ consisting only of characters a-z. Please compute A(t), and how A(t) would change after $U (1\le U\le2\times10^5)$ updates, each changing a character of t. Updates are cumulative.

inputFormat:
The first line of input contains $t$.

The next line contains $U$, followed by $U$ lines each containing a position $p$ $(1\le p\le N)$ and a character $c$ in the range a-z, meaning that the pth character of $t$ is changed to $c$.

outputFormat: Output $U+1$ lines, the total number of bessies that can be made across all substrings of $t$ before any updates and after each update.

translation:
给定一个字符串 $t$。

定义 $B(s)$ 表示 $s$ 这个字符串中删除一些字符后最多能找出多少个 ```bessie```。

定义 $A(t)$ 表示对于 $t$ 中的每个子串 $s$，求 $B(s)$ 的和。

先输出一开始的 $A(t)$。接下来有 $q$ 次修改，每次把 $t$ 中第 $p$ 个字符改成 $c$，要求输出每次修改完的 $A(t)$。

hint:
Before any updates, twelve substrings contain exactly $1$ `bessie` and $1$ string contains exactly $2$ `bessie`s, so the total number of bessies is $12⋅1+1⋅2=14$.

After one update, $t$ is `belsiebessie`. Seven substrings contain exactly one `bessie`.

After two updates, $t$ is `belsiesessie`. Only the entire string contains `bessie`.

Input $2$: $|t|,U\le300$;

Inputs $3-5$: $U\le10$;

Inputs $6-13$: $|t|,U\le10^5$;

Inputs $14-21$: No additional constraints.


title: [USACO23OPEN] Pareidolia G

background:
Pareidolia is the phenomenon where your eyes tend to see familiar patterns in
images where none really exist -- for example seeing a face in a cloud.  As you
might imagine, with Farmer John's constant proximity to cows, he often sees
cow-related patterns in everyday objects.  For example, if he looks at the
string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and
all he sees is "bessiexbessieb" -- a string that has contains two contiguous
substrings equal to "bessie".

description:
Given a string of length at most $2\cdot 10^5$ consisting only of characters
a-z, where each character has an associated deletion cost, compute the maximum
number of contiguous substrings that equal "bessie" you can form by deleting
zero or more characters from it, and the minimum total cost of the characters you need to
delete in order to do this.

inputFormat:
The first line contains the string. The second line contains the deletion cost
associated with each character (an integer in the range $\left[1,1000\right]$).

outputFormat:
The maximum number of occurrences, and the minimum cost to produce this number
of occurrences.

translation:
一个字符串 $s$。

第一问：求出 $s$ 删去若干字符后最多能出现多少个 ```bessie```。

给出删除每一位的代价 $c_1,c_2,...,c_{|s|}$。

第二问：求满足 ```bessie``` 出现次数最多的前提下最小的删除代价和。

samples:
besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

hint:
For the first sample, by deleting the 's' at position 4 we can make the whole string "bessie". The
character at position 4 has a cost of $4$, so our answer is cost $4$ for $1$
instance of "bessie", which is the best we can do.

For the second sample, by deleting the "con" at positions 5-7, we can make the string "bebessiete"
which has "bessie" in the middle. Characters 5-7 have costs $5 + 7 + 9 = 21$, so
our answer is cost $21$ for $1$ instance of "bessie", which is the best we can
do.

For the third sample, by deleting the "giraffe" at positions 4-10, we can make the string
"bessiebessibessie", which has "bessie" at the beginning and the end. "giraffe"
has 7 characters and all characters have cost $1$, so our answer is cost $7$ for
$2$ instances of "bessie", which is the best we can do. This sample satisfies the constraints for the second subtask.

- Inputs 4-5: $N\le 2000$.
- Inputs 6-8: All costs are $1$.
- Inputs 9-17: No additional constraints.


title: [USACO23OPEN] Good Bitstrings P

description:
For any two positive integers $a$ and $b$, define the function `gen_string(a,b)` by the following Python code:

```
def gen_string(a: int, b: int):
	res = ""
	ia, ib = 0, 0
	while ia + ib < a + b:
		if ia * b <= ib * a:
			res += '0'
			ia += 1
		else:
			res += '1'
			ib += 1
	return res
```

Equivalent C++ code:

```
string gen_string(int64_t a, int64_t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b <= (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}
```

$ia$ will equal $a$ and $ib$ will equal $b$ when the loop terminates, so this function returns a bitstring of length $a+b$ with exactly $a$ zeroes and $b$ ones. For example, `gen_string(4,10)=01110110111011`.

Call $a$ bitstring $s$ **good** if there exist positive integers $x$ and $y$ such that s=`gen_string(x,y)`. Given two positive integers $A$ and $B$ $(1\le A,B\le10^{18})$, your job is to compute the number of good prefixes of `gen_string(A,B)`. For example, there are $6$ good prefixes of `gen_string(4,10)`:

```
x = 1 | y = 1 | gen_string(x, y) = 01
x = 1 | y = 2 | gen_string(x, y) = 011
x = 1 | y = 3 | gen_string(x, y) = 0111
x = 2 | y = 5 | gen_string(x, y) = 0111011
x = 3 | y = 7 | gen_string(x, y) = 0111011011
x = 4 | y = 10 | gen_string(x, y) = 01110110111011
```

inputFormat:
The first line contains $T$ $(1\le T\le10)$, the number of independent test cases.

Each of the next $T$ lines contains two integers $A$ and $B$.

outputFormat: The answer for each test case on a new line.

translation:
定义函数 ```gen_string(a,b)```：

Python:
```python
def gen_string(a: int, b: int):
	res = ""
	ia, ib = 0, 0
	while ia + ib < a + b:
		if ia * b <= ib * a:
			res += '0'
			ia += 1
		else:
			res += '1'
			ib += 1
	return res
```
C++:
```cpp
string gen_string(int64_t a, int64_t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b <= (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}
```
如果一个字符串 $s$，存在 $a,b$ 使得 ```gen_string(a,b)``` 为 $s$，则称 $s$ 是好的。

共 $T$ 组数据，每次给出 $a,b$，求 ```gen_string(a,b)``` 有多少个前缀是好的。注意，前缀可以是整个字符串。

hint:
Input $2$: $A,B\le100$;\
Input $3$: $A,B\le1000$;\
Inputs $4-7$: $A,B\le10^6$;\
Inputs $8-13$: All answers are at most $10^5$.\
Inputs $14-21$: No additional constraints.


title: [USACO23OPEN] Tree Merging G

description:
Having just completed a course in graph algorithms, Bessie the cow has begun
coding her very own graph visualizer! Currently, her graph visualizer is only
capable of visualizing rooted trees with nodes of distinct values, and it can
only perform one kind of operation: merging.

In particular, a merging operation takes any two distinct nodes in a tree with
the same parent and merges them into one node, with value equal to the maximum
of the values of the two nodes merged, and children a union of all the children
of the nodes merged (if any).

Unfortunately, after Bessie performed some merging operations on a tree, her
program crashed, losing the history of the merging operations she performed. All
Bessie remembers is the tree she started with and the tree she ended with after
she performed all her merging operations.

Given her initial and final trees, please determine a sequence of merging
operations Bessie could have performed. It is guaranteed that a sequence exists.

Each input consists of $T$ independent test cases. It is
guaranteed that the sum of $N$  over all test cases does not exceed $1000$.

inputFormat:
The first line contains $T$, the number of independent test cases. Each test
case is formatted as follows.

The first line of each test case contains the number of nodes $N$ in Bessie's initial tree, which have values $1\dots N$.

Each of the next $N-1$ lines contains two space-separated node values $v_i$ and
$p_i$ indicating that the node with value $v_i$ is a
child node of the node with value $p_i$ in Bessie's initial tree.

The next line contains the number of nodes $M$ in Bessie's
final tree.

Each of the next $M-1$ lines contains two space-separated node values $v_i$ and
$p_i$ indicating that the node with value $v_i$ is a
child node of the node with value $p_i$ in Bessie's final tree.

outputFormat:
For each test case, output the number of merging operations, followed by an
ordered sequence of merging operations of that length, one per line.

Each merging operation should be formatted as two distinct space-separated
integers: the values of the two nodes to merge in any order.

If there are multiple solutions, output any.

translation:
定义一棵有根树的一次合并操作为：选择两个具有相同父亲的结点，将其合并成一个节点，新节点的编号为原来的两个节点编号的较大值，新节点的子节点集合为原来的两个节点子节点集合的并集。

Bessie 对一棵具有 $n$ 个节点的有根树进行了若干次合并操作，使这棵树变成了一棵具有 $m$ 个节点的树。但不幸的是，她忘记了她进行了哪些合并操作！

你需要构造出**任意**一组满足上述条件的合并操作序列。输入数据保证有解（即原状态一定可以通过若干次合并操作变为目标状态）。

注意事项：

- 本题单个测试点内有 $T$ 组测试数据；

- 对于 $100\%$ 的数据，$1\le T\le 100$， $2 \leq M\leq N \leq 1000$，$1 \leq v_i, p_i \leq N$；

- 部分分设置：

  - 对于测试点 $2-6$，满足执行操作前的树和执行操作后的树叶子节点数量相同；
  - 对于测试点 $7-16$，无特殊限制。

翻译自 @[zyc212303](https://www.luogu.com.cn/user/556366)。

hint:
$1\le T\le 100$, $2 \leq N \leq 1000$, $1 \leq v_i, p_i \leq N$,$2 \leq M \leq N$.

- Inputs 2-6: The initial and final trees have the same number of leaves.
- Inputs 7-16: No additional constraints.


title: [USACO23OPEN] Triples of Cows P

description:
There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\dots N$, forming a tree. The cows are
leaving the farm for vacation one by one. On day $i$, the $i$ th cow leaves the
farm, and then all pairs of the $i$ th cow's friends still present on the farm
become friends.

For each $i$ from $1$ to $N$, just before the $i$ th cow leaves,  how many
ordered triples of distinct cows $(a,b,c)$ are there such that none of $a,b,c$
are on vacation, $a$ is friends with $b$, and $b$ is friends with $c$?

inputFormat:
The first line contains $N$.

The next $N-1$ lines contain two integers $u_i$ and $v_i$ denoting that cows
$u_i$ and $v_i$ are initially friends.

outputFormat: The answers for $i$ from $1$ to $N$ on separate lines.

translation:
给定一棵初始有 $n$ 个点的树。

在第 $i$ 天，这棵树的第 $i$ 个点会被删除，所有与点 $i$ **直接相连**的点之间都会**两两**连上一条边。你需要在每次删点**发生前**，求出满足 $(a,b)$ 之间有边，$(b,c)$ 之间有边且 $a\not=c$的**有序**三元组 $(a,b,c)$ 对数。

hint:
For the first sample:
$(1,2,3)$ and $(3,2,1)$ are the triples just before cow $1$ leaves.
After cow
$1$ leaves, there are less than $3$ cows left, so no triples are possible.

For the second sample:
At the beginning, cow $1$ is friends with all other cows, and no other pairs of
cows are friends, so the triples are $(a, 1, c)$ where $a, c$ are different cows
from $\{2, 3, 4\}$, which gives $3 \cdot 2 = 6$ triples.
After cow $1$ leaves, the remaining three cows are all friends, so the triples
are just those three cows in any of the $3! = 6$ possible orders.
After cow $2$ leaves, there are less than $3$ cows left, so no triples are
possible.

$2\le N\le 2\cdot 10^5$, $1\le u_i,v_i\le N$.

- Inputs 4-5: $N\le 500$.
- Inputs 6-10: $N\le 5000$.
- Inputs 11-20: No additional constraints.


title: [ROI 2018] Extraction of radium

background: 译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T1. [Добыча радия](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Extraction of radium](http://codeforces.com/gym/102147/problem/A))。

description:
给一个 $n\times m$ 的矩阵 $a$，矩阵中的数互不相同。
接下来有 $q$ 次修改，每次修改会将某个值修改为一个更大的值。保证修改后矩阵中的数仍互不相同。
每次修改后，请求出：矩阵中有多少个数，既是它所在行的最大值，又是它所在列的最大值。

inputFormat:
第一行三个整数 $n$，$m$，$q$ ，表示矩阵的大小与修改操作的次数。
接下来 $n$ 行，每行 $m$ 个整数，表示该矩阵。
接下来 $q$ 行，每行三个整数 $x$，$y$，$t$，表示将该矩阵第 $x$ 行，第 $y$ 列的元素改为 $t$。

outputFormat: $q$ 行，每行一个整数，表示每次修改后，矩阵中有多少个数满足条件。


title: 「RiOI-03」water problem

description:
给定一个正整数 $n$，问一个正方形能否被分割为 $n$ 个小正方形（**不要求大小相等**），输出 `Yes` 或 `No`。多组数据。

分割的不严格定义可以理解为切一刀。但是切出的这一刀必须是线段，且其端点必须在正方形的边界上或先前切出的线段上。

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

对于每组数据，一行一个正整数 $n$。

outputFormat: 对于每组数据，分别一行一个字符串，`Yes` 或 `No` 表示方案的存在与否。

hint:
### 样例解释 1

显然，正方形无法分割为 $3$ 个小正方形；\
由于 $4 = 2^2$，$256 = 16^2$，则它们均能被分割成若干个全等的小正方形。

### 数据规模与约定

+ Subtask 0（10 pts）：$n$ 是偶数。
+ Subtask 1（35 pts）：$n \leq 8$。
+ Subtask 2（55 pts）：无特殊限制。

对于所有数据，$1 \leq T \leq 10^5$，$1 \leq n \leq 10^9$。


title: [ROI 2018] Innophone

background: 译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T3. [Иннофон](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Innophone](http://codeforces.com/gym/102147/problem/B))。

description:
有一个二元函数 $f(x,y)$，它是这么定义的：

 $f(x,y)=\left\{
\begin{array}{rcl}
a, & & {\text{if} \quad \quad \ \ \ a \leq x}\\
b, & & {\text{else if} \quad b \leq y}\\
0, & & {\text{else}}
\end{array} \right.$

其中 $a,b$ 为常数。现在给定 $n$ 组 $x,y$，你需要选择合适的 $a,b$，使得 $\sum_{i=1}^{n} f(x_i,y_i)$ 最大。

inputFormat:
第一行一个整数 $n$，表示 $x$，$y$ 的组数。

后面 $n$ 行，每行两个数 $x_i$，$y_i$。


title: [POI2020] Cukiernia / 糕点店

background: **题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Cukiernia](https://sio2.mimuw.edu.pl/c/oi28-1/p/cuk/)。**

description:
Bajtuś 面包店售卖蛋糕，甜甜圈和羊角面包三种食物。在面包店中，有 $n$ 个橱窗，在正常情况下，每个货架上只应该放置一种食物。但一天早上，面包店老板 Bajtazara 的儿子 Bajtuś 偷偷进入了面包店，将所有的食物摆放得乱七八糟。

面包店马上就要开门了，Bajtazara 急切地想要重新摆放食物，使得每个货架上只有一种食物（特别地，一个货架上没有食物也是允许的）。请你帮助他求出，至少需要移动多少次食物才能达成目标。

inputFormat:
第一行一个整数 $n$，代表面包店中货架的数量。

接下来 $n$ 行，第 $i$ 行三个整数 $d_i,p_i,r_i$，分别代表该货架上现有的蛋糕数，甜甜圈数和羊角面包数。数据保证面包店中至少有一份食物。

outputFormat: 输出一个整数，表示需要移动食物的最小次数。

hint:
【样例解释#1】：

一种合法的移动方案如下：

1. 将一个甜甜圈从货架 $1$ 移动至货架 $3$，将一个羊角面包从货架 $1$ 移动至货架 $2$；
2. 将三个甜甜圈从货架 $2$ 移动至货架 $3$；
3. 将一个蛋糕从货架 $3$ 移动至货架 $1$，将三个羊角面包从货架 $3$ 移动至货架 $2$；

在此之后，货架 $1$ 只有蛋糕，货架 $2$ 只有羊角面包，货架 $3$ 只有甜甜圈，货架 $4$ 只有蛋糕，货架 $5$ 是空的。

【数据范围】：

所有测试点均满足：$3 \leq n \leq 3 \times 10^5$，$0 \leq d_i,p_i,r_i \leq 10^9$。

| 子任务编号 | $n \leq$        | 分值 |
| :----------: | :---------------: | :----: |
| $1$        | $10$            | $15$ |
| $2$        | $5 \times 10^3$ | $35$ |
| $3$        | $3 \times 10^5$ | $50$ |


title: [POI2020] Licznik długu / 债务计数器

background: **题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Licznik długu](https://sio2.mimuw.edu.pl/c/oi28-1/p/lic/)。**

description:
Bajterowicza 教授指出，Bajtocji 的经济形势现在不容乐观。为了警示民众，他让 Bajtazara 公司在 Bajtocji 首都的市中心安装一块大型显示屏，用来显示 Bajtocji 现在的公共债务是多少。

Bajtocji 的公共债务由两部分组成：国内债务和国际债务。国内债务和国际债务最多可由 $n-1$ 个十进制数组成。而在显示屏上显示的是两部分债务的总和。

随着时间推移，Bajtocji 的债务状况也在不断变化。你现在需要帮助 Bajtazara 公司完成显示软件的编辑工作。

这个软件需要执行如下三种操作：

- 更改国内债务数值在某一位上的值。
- 更改国际债务数值在某一位上的值。
- 输出总公共债务在某一位上的值。

inputFormat:
输入第一行两个整数 $n,z$，分别代表显示器能显示的数字位数和操作次数。

第二行包含一个长度 $n-1$ 的数字，代表 Bajtocji 最初的国内债务的值，这个数字可能有前导零。

第三行包含一个长度 $n-1$ 的数字，代表 Bajtocji 最初的国际债务的值，这个数字可能有前导零。

接下来 $z$ 行，每行描述一个询问操作：

- $\texttt{W}\ i \ c$ 表示将国内债务的第 $i$ 位的值更改为 $c$（$1 \leq i \leq n-1$，$0 \leq c \leq 9$）。
- $\texttt{Z}\ i \ c$ 表示将国际债务的第 $i$ 位的值更改为 $c$（$1 \leq i \leq n-1$，$0 \leq c \leq 9$）。
- $\texttt{S}\ i$ 表示输出总公共债务第 $i$ 位的值（$1 \leq i \leq n-1$）。

outputFormat: 对于每个 $\texttt{S}$ 操作，输出一行一个整数表示结果。

hint:
【样例解释#1】：

最初公共债务总额为 $7341+150=7491$，因此第三位上的值为 $4$。

在操作 $2$ 后，公共债务总额为 $7041+150=7191$，因此第三位上的值为 $1$。

在操作 $4$ 后，公共债务总额为 $7041+159=7200$，因此第一位上的值为 $0$，第三位上的值为 $2$。

【数据范围】：

所有测试点均满足：$2 \leq n \leq 10^5$，$1 \leq z \leq 10^5$。

|子任务编号|约束|分值|
|:-:|:-:|:-:|
|$1$|$n,z\leq5\times10^3$|$30$|
| $2$|任何时刻，国内债务和国际债务的每个位上的数字都是 $0$ 或 $5$|$20$|
| $3$|无附加约束|$50$|


title: [POI2020] Tablica binarna / 01 矩阵

background: **题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Tablica binarna](https://sio2.mimuw.edu.pl/c/oi28-1/p/tab/)。**

description:
矩阵 $A$ 有 $n$ 行 $m$ 列，行自上到下编号为 $1$ 至 $n$，列自左到右编号为 $1$ 到 $m$，因此可以用 $(i,j)$ 表示矩阵的第 $i$ 行第 $j$ 列的元素。且矩阵 $A$ 中每个元素的值为 $0$ 或 $1$。

最初，矩阵内的所有元素的值均为 $0$。接下来可以对该矩阵执行 $q$ 次修改操作。每次操作将给出四个参数 $i_1,j_1,i_2,j_2$，表示将以 $(i_1,j_1)$ 为左上角，$(i_2,j_2)$ 为右下角的矩形内的所有元素的值翻转（从 $0$ 变成 $1$，或从 $1$ 变为 $0$）。

如果一次操作中，矩形的左上角与矩阵的左上角重合（即 $i_1=j_1=1$），则称这次修改操作是**简单的**。

现在你想要知道，在每次对矩阵执行修改操作后，需要执行至少多少次**简单的**修改操作，使得矩阵内所有元素的值全部变为 $0$。

inputFormat:
输入第一行三个整数 $n,m,q$，分别代表矩阵的行数，列数，操作的次数。

接下来 $q$ 行，每行四个整数 $i_1,j_1,i_2,j_2$，描述一次修改操作。保证 $1 \leq i_1 \leq i_2 \leq n$，$1 \leq j_1 \leq j_2 \leq m$。

outputFormat: 输出 $q$ 行。第 $i$ 行输出一个整数，表示在第 $i$ 次修改过后，需要执行至少多少次**简单的**修改操作，使得矩阵内所有元素的值全部变为 $0$。


title: [ROI 2018] Viruses

background: 译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T2. [Вирусы](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Viruses](https://codeforces.com/gym/102147/problem/D))。

description:
现在有 $n$ 只细胞与 $n$ 个病毒，$i$ 号细胞的初始病毒的序号也为 $i$，每个细胞心中对每位病毒都有一定的易感染度。

细胞之间可以互相攻击，如果细胞甲攻击了细胞乙，且乙「对甲现在的病毒的易感染度」比「对自家病毒的易感染度」高，那么乙就会被甲的病毒感染（成为甲的病毒的细胞）。

细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时，游戏宣告结束。

如果存在一种攻击顺序，使得病毒 $i$ 最终拥有一只或以上的细胞，那么我们则称病毒 $i$ 为「可行的病毒」。
如果对于任意一种攻击顺序，都使得病毒 $i$ 最终拥有一只或以上的细胞，那么我们则称病毒 $i$ 为「稳定的病毒」。

现在病毒们想知道，有多少个可行的病毒与稳定的病毒。

inputFormat:
第一行一个正整数 $n$，表示细胞与病毒的数量。

下面 $n$ 行，每行 $n$ 个正整数，表示每名病毒按当前细胞心中的易感染度降序排列后的病毒编号序列。

比如输入了 `2 1 3`，则表示该细胞对 $2$ 号病毒的易感染度最高，对 $1$ 号病毒的易感染度第二高，对 $3$ 号病毒的易感染度最差。

最后一行一个整数 $p$。

outputFormat:
第一行，一个整数 $x$。如果 $p=1$，输出稳定的病毒数量；如果 $p=2$，输出可行的病毒的数量。

接下来一行， $x$ 个整数，表示这 $x$ 个病毒的编号，按升序排列。


title: [ROI 2018]  Decryption

background: 译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T1. [Расшифровка](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf) ([Decryption](https://codeforces.com/gym/102154/problem/B))。

description:
研究表明，汉字的顺序并不一定能影响阅读。科学家们对数列进行了类似的研究。

给一个正整数数列，若数列首项为数列中所有数的最小值，末项为数列中的最大值，则我们称这是个正确的数列。例如，序列 $[1, 3, 2, 4]$ 和 $[1, 2, 1, 2]$ 是正确的，但序列
$[1, 3, 2]$ 不是。

给出长度为 n 的序列 $[a_1, a_2, \ldots, a_n]$。对于该序列的某个片段 $[a_l, a_{l+1}, \ldots, a_r]$, 若该片段的首项为该片段中的最小值，末项为该片段中的最大值，则我们称这是个正确的片段。

对于给定的序列，请求出该序列至少需要被分成多少段，才能使得每个片段均为正确的片段。序列 $[2, 3, 1, 1, 5, 1]$ 可以分为三个正确的段：$[2, 3]$ 和 $[1, 1, 5]$ 和 $[1]$。

需要编写一个程序，该程序按给定的顺序确定可以划分的最小正确段数。

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

接下来一行 $n$ 个数，分别为 $a_1,a_2,\ldots,a_n$。

outputFormat: 输出可以划分的最小正确段数。

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

对于 $60\%$ 的数据，$1 \leq n \leq 5000$。

对于所有数据，$1 \leq n \leq3 \times 10^5$，$1\leq a_i \leq 10^9$。


title: [ROI 2018] Quantum teleportation

background: 译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html)  T4. [Квантовая телепортация ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf)([Quantum teleportation](https://codeforces.com/gym/102147/problem/C))。

description:
在一个平面直角坐标系上有编号为 $1\dots k$ 的 $k$ 块 CPU。

每块 CPU 的位置可以用平面上的坐标来表示。$1$ 号 CPU 位于 $(1,1)$，$k$ 号 CPU 位于 $(n,m)$。保证所有 CPU 均位于整点上，且对于每块 CPU 的坐标 $(x_i, y_i)$，保证 $1 \le x_i \le n, 1 \le y_i \le m$。

$i$ 号 CPU 通过总线将一笔数据传输到 $j$ 号 CPU 的耗时为 ${2^{\max(|x_{{i}}-x_{{j}}|,|y_{{i}}-y_{{j}}|)}}$ 个单位时间。

试求：要将数据从 $1$ 号 CPU 传送到 $k$ 号 CPU，至少需要多久，并给出一组方案。

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

以下 $k$ 行，每行两个整数 $x_i,y_i$。

outputFormat:
第一行一个整数 $L$，表示最快的方案中要经过多少块 CPU。

第二行 $L$ 个整数，表示依次经过的 CPU。

如果存在多组路径使耗时最少，输出任意一种即可。