title: [USACO21OPEN] Acowdemia III B

description:
Bessie 是一位忙碌的计算机科学研究生。然而，即使是研究生也需要交友。因此，Farmer John 开设了一片草地，目的是为了帮助 Bessie 与其他奶牛建立持久的友谊。

Farmer John 的草地可以被看做是由正方形方格组成的巨大二维方阵（想象一个巨大的棋盘）。每个方格用如下字符标记：

 - `C`，如果这个方格中有一头奶牛。
 - `G`，如果这个方格中有草。
 - `.`，如果这个方格既没有奶牛也没有草。

对于两头想要成为朋友的奶牛，她们必须选择在一个与她们均水平或竖直方向上相邻的有草方格见面。在这个过程中，她们会在这个有草方格中吃草，所以之后的奶牛不能再使用这个方格作为见面地点。一头奶牛可以与多头其他奶牛成为朋友，但是同一对奶牛不能见面并成为朋友多于一次。

Farmer John 希望有许多奶牛可以见面并成为朋友。请求出当这一活动结束时在奶牛之间可以建立的朋友关系的最大数量。

inputFormat:
输入的第一行包含 $N$ 和 $M$（$1\le N,M\le 1000$）。

以下 $N$ 行每行包含一个由 $M$ 个字符组成的字符串，表示这个草地。

outputFormat: 输出在这一活动结束时在奶牛之间可以建立的朋友关系的最大数量


title: [USACO21JAN] Uddered but not Herd B

type: P

description:
一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。牛文由 $26$ 个字母 `a` 到 `z` 组成，但是当奶牛说牛文时，可能与我们所熟悉的 `abcdefghijklmnopqrstuvwxyz` 不同，她会按某种特定的顺序排列字母。

为了打发时间，奶牛 Bessie 在反复哼唱牛文字母歌，而 Farmer John 好奇她唱了多少遍。

给定一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母，计算 Bessie 至少唱了几遍完整的牛文字母歌，使得 Farmer John 能够听到给定的字符串。Farmer John 并不始终注意 Bessie 所唱的内容，所以他可能会漏听 Bessie 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。

inputFormat: 输入的第一行包含 $26$ 个小写字母 `a` 到 `z` 的牛文字母表顺序。下一行包含一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母。字符串的长度不小于 $1$ 且不大于 $1000$。

outputFormat: 输出 Bessie 所唱的完整的牛文字母歌的最小次数。

hint:
### 样例解释 1

在这个样例中，牛文字母表与日常的字母表的排列一致。

Bessie 至少唱了三遍牛文字母歌。有可能 Bessie 只唱了三遍牛文字母歌，而 Farmer John 听到了以下被标记为大写的字母。

`abcdefghijklMnOpqrstuvwxyz`
`abcdefghijklmnOpqrstuvwxyz`
`abcDefghijklmnopqrstuvwxyz`

### 测试点性质

- 测试点 $2-5$ 中，牛文字母表与日常的字母表相同。
- 测试点 $6-10$ 没有额外限制。


title: [USACO21JAN] Even More Odd Photos B

description:
Farmer John 正再一次尝试给他的 $N$ 头奶牛拍照（$2\le N\le 1000$）。

每头奶牛有一个范围在 $1\ldots 100$ 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。

Farmer John 可以分成的最大组数是多少？

inputFormat: 输入的第一行包含 $N$。下一行包含 $N$ 个空格分隔的整数，为 $N$ 头奶牛的品种编号。

outputFormat: 输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。

hint:
### 样例解释 1

在这个样例中，以下是一种分成最大组数三组的方案。将 1 和 3 分在第一组，5、7 和 9 分在第二组，11 和 13 分在第三组。

### 样例解释 2

在这个样例中，以下是一种分成最大组数五组的方案。将 2 分在第一组，11 分在第二组，13 和 1 分在第三组，15 分在第四组，17 和 3 分在第五组。


title: [USACO21JAN] Just Stalling B

description: Farmer John 有 $N$ 头奶牛（$1\le N\le 20$），高度为 $a_1\ldots a_N$。他的牛栏有 $N$ 个牛棚，高度限制分别为 $b_1\ldots b_N$（例如，如果 $b_5=17$，那么一头高度不超过 $17$ 的奶牛可以住在牛棚 $5$ 里）。Farmer John 有多少种不同的方式安排他的奶牛，使得每头奶牛均住在不同的牛棚里，并且使得每个牛棚的高度限制均得到满足？

inputFormat: 输入的第一行包含 $N$。第二行包含 $N$ 个空格分隔的整数 $a_1,a_2,\ldots,a_N$。第三行包含 $N$ 个空格分隔的整数 $b_1,b_2,\ldots,b_N$。所有的高度和高度限制均在范围 $[1,10^9]$ 内。

outputFormat: 输出 Farmer John 可以将每头奶牛安排到不同的牛棚里，使得每个牛棚的高度限制均得到满足的方法数。注意输出的数量可能需要使用 64 位整数型，例如 C++ 中的 long long。

hint:
### 样例解释 1

在这个例子中，我们不能将第三头奶牛安排到第一个牛棚里，因为 $3=a_3>b_1=2$。类似地，我们不能将第四头奶牛安排到第一或第三个牛棚里。一种符合高度限制的安排方式为将奶牛 1 安排到牛棚 1，奶牛 2 安排到牛棚 2，奶牛 3 安排到牛棚 3，奶牛 4 安排到牛棚 4。

### 测试点性质

- 测试点 $1-5$ 满足 $N\le 8$。
- 测试点 $6-12$ 没有额外限制。


title: [USACO21FEB] Year of the Cow B

description:
Farmer John 的奶牛们得知最近正在庆祝牛年的到来时十分兴奋。牛年总是奶牛们的最爱。

我们知道，中国历法中每一年所对应的生肖遵循 $12$ 年的周期：Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat（牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠），然后回到牛。

奶牛 Bessie 自豪地说她是在许多年前的一个牛年出生的。她的朋友 Elsie 想要知道她与 Bessie 出生相差多少年，并且希望你能够通过查看农场上若干奶牛出生年份之间的关系来帮助她推算。

inputFormat:
输入的第一行包含一个整数 $N$（$1\le N\le 100$）。以下 $N$ 行每行包含一个 $8$ 个单词的短语，指定了两头奶牛的出生年份之间的关系，格式为

`Mildred born in previous Dragon year from Bessie`（Mildred 在 Bessie 出生的前一个龙年出生），

或

`Mildred born in next Dragon year from Bessie`（Mildred 在 Bessie 出生的后一个龙年出生）。

最后一个单词是农场上某一头奶牛的名字，为 `Bessie` 或一头已经在之前的输入中出现过的奶牛。

第一个单词是农场上某一头奶牛的名字，不为 `Bessie` 且未在之前的输入中出现过。所有的奶牛名字不超过 $10$ 个字符，且仅包含字符 `a..z` 或 `A..Z`。

第 $5$ 个单词是上述十二生肖之一。

第 $4$ 个单词是 `previous`（之前）或 `next`（之后）之一。例如，如果短语为 `Mildred born in previous Dragon year from Bessie`，则 Mildred 的出生年份为最为接近且严格处于 Bessie 的出生年份之前（不等于）的龙年。

outputFormat: 输出 Bessie 和 Elsie 的出生年份之间相差的年数。输入保证可以通过给定的信息求出结果。

samples:
4
Mildred born in previous Dragon year from Bessie
Gretta born in previous Monkey year from Mildred
Elsie born in next Ox year from Gretta
Paulina born in next Dog year from Bessie

hint:
### 样例解释 1

在以上的输入中，

- Elsie 在 Bessie 之前 $12$ 年出生。
- Mildred 在 Bessie 之前 $9$ 年出生。
- Gretta 在 Bessie 之前 $17$ 年出生。
- Paulina 在 Bessie 之前 $9$ 年出生。


title: [USACO21FEB] Comfortable Cows B

description:
Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。

Farmer John 将会逐一地将 $N$（$1\le N\le 10^5$）头奶牛加入到草地上。第 $i$ 头奶牛将会占据方格 $(x_i,y_i)$，不同于所有已经被其他奶牛占据的方格（$0\le x_i,y_i\le 1000$）。

一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。Farmer John 对他的农场上舒适的奶牛数量感兴趣。对 $1\ldots N$ 中的每一个 $i$，输出第 $i$ 头奶牛加入到草地上之后舒适的奶牛的数量。

inputFormat: 输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数，表示一头奶牛所在的方格坐标 $(x,y)$。输入保证所有方格的坐标是不同的。

outputFormat: 输出的第 $i$ 行包含前 $i$ 头奶牛加入到草地上之后舒适的奶牛的数量。

hint:
### 样例解释 1

在前四头奶牛加入之后，位于 $(1,1)$ 的奶牛是舒适的。

在前七头奶牛加入之后，位于 $(2,1)$ 的奶牛是舒适的。

在前八头奶牛加入之后，位于 $(2,1)$ 和 $(2,2)$ 的奶牛是舒适的。

### 测试点性质

- 测试点 $1-4$ 满足 $N\le 400$。
- 测试点 $5-12$ 没有额外限制。


title: [USACO21FEB] Clockwise Fence B

description:
围绕 Farmer John 最大的草地的栅栏已经损坏了，如今他终于决定要换一个新的栅栏。

不幸的是，当 Farmer John 在铺设新栅栏时，一只巨大的蜜蜂突然出现，在他的草地上追着他跑，导致最后栅栏被沿着一条相当不规则的路径铺设。栅栏可以用一个字符串表示，每个字符为 `N`（north，北）、`E`（east，东）、`S`（south，南）、`W`（west，西）之一。每个字符表示一米长的一段栅栏。举例来说，如果字符串为 `NESW`，这表示栅栏从起点开始向北延伸 $1$ 米，然后向东延伸 $1$ 米，然后向南延伸 $1$ 米，然后向西延伸 $1$ 米，回到栅栏的起点。

栅栏的结束位置与开始位置相同，而这是栅栏的路径上唯一会被到达多次的位置（从而起始位置是唯一会被再次到达的位置，在栅栏结束之时）。结果，栅栏确实围起了一个草地上连通的区域，尽管这个区域可能形状十分奇特。

Farmer John 想要知道他铺设栅栏的路径是顺时针（当按字符串表示的顺序沿着栅栏的路径行走时被围起的区域位于右侧）还是逆时针（被围起的区域位于左侧）。

inputFormat: 输入的第一行包含一个整数 $N$（$1\le N\le 20$）。以下 $N$ 行每行包含一个长度不小于 $4$ 且不超过 $100$ 的字符串，表示一个栅栏的路径。

outputFormat: 对 $N$ 条输入的栅栏路径的每一条，输出一行，为 `CW`（clockwise，顺时针）或 `CCW`（counterclockwise，逆时针）。


title: [USACO20JAN] Word Processor B

description:
奶牛 Bessie 正在完成她的写作课的一篇作文。由于她写字很难看，她决定用一个文字处理器来输入这篇作文。

这篇作文共有 $N$ 个单词（$1\le N\le 100$），用空格分隔。每个单词的长度在 $1$ 到 $15$ 之间，仅由大写和小写字母组成。根据作业的要求，这篇作文需要用一种特别的方式排版：每一行包含的字符不超过 $K$ 个（$1\le K\le 80$），空格不计。幸好 Bessie 的文字处理器能够处理这样的要求，它会按照如下的方式：

 - 如果 Bessie 输入了一个单词，这个单词能够放进当前行，就放在当前行。
 - 否则，将这个单词放到下一行，然后继续向下一行添加单词。

当然，同一行中的单词之间仍然用一个空格分隔。每一行的结尾都不应当有空格。

很不幸，Bessie 的文字处理器刚好坏了。请帮助她正确地排版她的作文！

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

下一行包含 $N$ 个单词，单词之间用单个空格分隔。所有单词的长度都不超过一行中的字符上限数 $K$。

outputFormat: 输出正确排版的 Bessie 的作文。

samples:
10 7
hello my name is Bessie and this is my essay

hint:
### 样例解释 1

第一行包含 $7$ 个非空格字符，包括 `hello` 以及 `my`。再加入 `name` 会使得第一行包含 $11>7$ 个非空格字符，所以这个单词会被放到下一行。


title: [USACO20JAN] Photoshoot B

description:
Farmer John 在给他编号为 $1\ldots N$ 的 $N$ 头奶牛排队拍照（$2\le N\le 10^3$）。FJ 一开始计划从左向右数第 $i$ 个位置排编号为 $a_i$ 的奶牛，他在一张纸上写下了排列 $a_1,a_2,\ldots,a_N$。不幸的是，这张纸刚刚被 Farmer Nhoj 偷走了！

幸好 FJ 仍然有机会恢复他之前写下的排列。在这张纸被偷走之前，Bessie 记录了序列 $b_1,b_2,\ldots,b_{N−1}$，对于每一个 $1\le i<N$ 满足 $b_i=a_i+a_{i+1}$。

基于 Bessie 的信息，帮助 FJ 恢复可以产生序列 $b$
的“字典序最小”的排列 $a$。排列 $x$ 字典序小于排列 $y$，如果对于某个 $j$，对于所有 $i<j$ 均有 $x_i=y_i$，且有 $x_j<y_j$（换句话说，这两个排列到某个位置之前都相同，在这个位置上 $x$ 小于 $y$）。保证存在至少一个满足条件的 $a$。

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

第二行包含 $N−1$ 个空格分隔的整数 $b_1,b_2,\ldots,b_{N−1}$。

outputFormat: 输出一行，包含 $N$ 个空格分隔的整数 $a_1,a_2,\ldots,a_N$。


title: [USACO20JAN] Race B

description:
Bessie 正在参加一场 $K$（$1\le K\le 10^9$）米的跑步比赛。她从 $0$ 米每秒的速度开始比赛。在每一秒中，她可以选择将她的速度增加 $1$ 米每秒，保持速度不变，或者将她的速度减少 $1$ 米每秒。例如，在第一秒中，她可以将她的速度增加到 $1$ 米每秒，跑 $1$ 米，或者保持她的速度 $0$ 米每秒不变，跑 $0$ 米。Bessie 的速度不会降低到小于零。

Bessie 始终朝着终点线的方向跑，她想要花费整数秒的时间完成比赛。此外，她不想在终点时跑得太快：在 Bessie 跑完 $K$ 米的时刻，她希望她的速度不超过 $X$（$1\le X\le 10^5$）米每秒。Bessie 想要对于 $N$（$1\le N\le 1000$）个不同的 $X$ 值知道她多快可以完成比赛。

inputFormat:
输入的第一行包含两个整数 $K$ 和 $N$。

以下 $N$ 行每行包含一个整数 $X$。

outputFormat: 输出 $N$ 行，每行包含一个整数，表示 Bessie 完成比赛时的速度小于或等于 $X$ 的情况下跑完 $K$ 米需要的最小时间。

hint:
### 样例解释 1

当 $X=1$ 时，一种最优方案为：

1. 将速度增加到 $1$ 米/秒，跑 $1$ 米
2. 将速度增加到 $2$ 米/秒，跑 $2$ 米，总计跑 $3$ 米
3. 将速度保持在 $2$ 米/秒，总计跑 $5$ 米
4. 将速度保持在 $2$ 米/秒，总计跑 $7$ 米
5. 将速度保持在 $2$ 米/秒，总计跑 $9$ 米
6. 将速度降低到 $1$ 米/秒，总计跑 $10$ 米

当 $X=3$ 时，一种最优方案为：

1. 将速度增加到 $1$ 米/秒，跑 $1$ 米
2. 将速度增加到 $2$ 米/秒，总计跑 $3$ 米
3. 将速度增加到 $3$ 米/秒，总计跑 $6$ 米
4. 将速度保持在 $3$ 米/秒，总计跑 $9$ 米
5. 将速度保持在 $3$ 米/秒，总计跑 $12$ 米

注意当 $X=3$ 时，以下方案是不合法的：

1. 将速度增加到 $1$ 米/秒，跑 $1$ 米
2. 将速度增加到 $2$ 米/秒，总计跑 $3$ 米
3. 将速度增加到 $3$ 米/秒，总计跑 $6$ 米
4. 将速度增加到 $4$ 米/秒，总计跑 $10$ 米

这是因为在 Bessie 跑完 $10$ 米的时刻，她的速度是 $4$ 米/秒。


title: 「Cfz Round 2」Binary

description:
给定 $n + 1$ 个整数 $a_0\dots a_n$。

对于整数 $u$，设它在二进制下为 $1$ 的位分别为 $k_1, k_2\dots k_m$，那么它的权值 $f(u) = a_{k_1} \oplus a_{k_2} \oplus \dots \oplus a_{k_m}$。此处的二进制位的编号从右到左，依次为 $0,1,2\dots$。其中 $\oplus$ 表示 [按位异或](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fromModule=search-result_lemma-recommend) 符号。

你想要知道有多少个 $0 \leq u \leq 2^n - 1$ 使得 $f(u) = f(u + 1)$。为了方便，请你用 **二进制形式** 输出答案（不取模）。

请注意：输出不能包含前导 $0$，除非答案为 $0$。

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

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

接下来依次输入每组测试数据。对于每组测试数据：

- 第一行输入一个正整数 $n$。
- 第二行输入 $n + 1$ 个整数 $a_0 \dots a_n$。

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

再次提示：输出不能包含前导 $0$，除非答案为 $0$。


title: [Ynoi2000] pmpkmp

description:
给定一棵树，树上的每条边上有一个字符。给定一个常数 $X$。

有两种操作，每次操作输入三个整数与一个字符串：

`1 x y S`：对于 $x$ 到 $y$ 的有向简单路径上的边，将路径上的第 $i$ 条边上的字符替换为 $S$ 上的对应字符 $S_i$，保证这条 $x$ 到 $y$ 之间路径的边数为 $X$。

`2 x y S`：查询 $x$ 到 $y$ 构成的有向简单路径所形成的字符串上，$S$ 匹配的次数（这里的匹配即：将 $S$ 当做模式串，在这条路径构成的字符串上逐位置匹配。）例如：$S=121$ ，路径上的字符串为 $1212122$，则匹配了2次，分别在第 $[1,3]$ 处和$[3,5]$ 处。

上述所有字符串 $S$ 的下标从 $1$ 开始，保证每个输入的字符串长度均为 $X$。

inputFormat:
第一行三个以空格分隔的整数 $n,m,X$。

之后一行包含 $n-1$ 个数，第 $i$ 个数表示第 $i+1$ 个点的父亲 $f_{i+1}$，保证每个点父亲的编号比这个点的编号小。

之后一行包含 $n-1$ 个字符，第 $i$ 个字符表示第 $i+1$ 个点到父亲的边上的字符 $a_{i+1}$。

之后 $m$ 行，每行输入以空格隔开的三个整数 $opt,x,y$ 与一个长为 $X$ 的字符串 $S$，表示一次操作。

outputFormat: 共 $m$ 行，每行一个整数，表示每次 $2$ 操作的答案。

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

对于 $10\%$ 的数据，满足 $1\le n,m\le 250$。

对于另外 $10\%$ 的数据，不存在 1 操作。

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

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

对于另外 $10\%$ 的数据，满足 $X\ge 20000$。

对于另外 $10\%$ 的数据，满足 $f_i=i-1$。

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

对于另外 $10\%$ 的数据，满足 $1\le n,m\le 2.5\times 10^4$，$mX\le 2.5\times 10^4$。

对于另外 $10\%$ 的数据，满足 $1\le n,m\le 2.5\times 10^5$，$mX\le 2.5\times 10^5$。

对于 $100\%$ 的数据，满足 $1\le n,m,X\le 5\times 10^5$，字符集为 $[1,9]$ 以内的整数，$mX\le 5\times 10^5$。


title: [Ynoi1999] TS-54

description:
给定整数序列 $a_1,\dots,a_n$ ，满足不存在 $1\le i<j<k<l\le n$ 使得 $a_i=a_j=a_k=a_l$ ；

共 $m$ 次操作，每次操作给出 $x$ ，首先进行修改，将 $a_1,a_2,\dots,a_x$ 翻转为 $a_x,\dots,a_2,a_1$ ，然后查询有多少个不同的 $k$ ，满足存在 $1\le i\le x<j\le n$ 使得 $a_i=a_j=k$ 。

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

第二行 $n$ 个整数依次表示 $a_1,\dots,a_n$ ；

接下来 $m$ 行，每行一个整数 $x$ ，表示一次操作。

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

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足所有数值为整数，$1\le a_i\le n$，$1\le x\le n$，$n,m\le 5\times 10^5$。


title: [Ynoi Easy Round 2023] TEST_69

description:
给定一个长为 $n$ 的序列 $a$，有 $m$ 次操作。

每次有两种操作：

``1 l r x``：对于区间 $[l,r]$ 内所有 $i$，将 $a_i$ 变成 $\gcd(a_i,x)$。

``2 l r``：查询区间 $[l,r]$ 的和，答案对 $2^{32}$ 取模后输出。

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

第二行 $n$ 个数表示 $a_i$。

之后 $m$ 行，每行三个或四个数，表示一次操作。

outputFormat: 对每个 $2$ 操作，输出一行一个数表示这次查询的答案。

hint:
Idea：nzhtl1477，Solution：nhtl1477，Code：ccz181078，Data：ccz181078

对于 $20\%$ 的数据，满足 $1 \le n,m,a_i,x \le 10^3$。

对于 $50\%$ 的数据，满足  $1 \le n,m \le 10^5$，且 $a$ 中的元素与每次操作的 $x$ 均随机生成。

对于另外 $20\%$ 的数据，满足所有的查询均在修改后发生。

对于 $100\%$ 的数据，满足 $1\le n\le 2\cdot 10^5,1\le m\le 5 \cdot 10^5$，所有数值为 $[1,10^{18}]$ 内的整数。


title: [Ynoi1999] M47升级型“钢铁阿诺”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


title: [Ynoi Easy Round 2023] TEST_90

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

共有 $m$ 次询问，每次询问给定 $l,r$，求区间 $[l,r]$ 中有多少 子区间 $[i,j]$ 满足 $l\le i\le j\le r$，且在区间 $[i,j]$ 内出现过的数的个数为奇数。

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

接下来一行 $n$ 个整数表示序列 $a_1,\dots,a_n$

接下来一行一个整数 $m$。

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

outputFormat: 对每个询问，输出一行，包含一个整数，表示答案。

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

对于 $25\%$ 的数据，满足 $1\le n,m\le 10^2$。

对于 $50\%$ 的数据，满足 $1\le n,m\le 10^4$。

对于另外 $25\%$ 的数据，满足序列中出现过的数个数不超过 $100$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le m\le 10^6$，$1\le a_i\le n。$

对每个询问满足 $1\le l\le r\le n$。

以上所有数值为整数。


title: [Ynoi2000] rfrqwq

description:
给定一个长为 $n$ 的序列 $a$，每个位置是一个 $[1,n]$ 内的整数。

定义 $f(i,j)$ 表示有多少 $x$ 满足 $i\le x<j$ 且 $a_x\neq a_{x+1}$。

有 $m$ 次操作：

`1 l r x`：表示将区间 $[l,r]$ 中所有元素都修改为 $x$。

`2 l r x`：表示查询区间 $[l,r]$ 中，对任意 $l\le i<j\le r$，且 $a_i=a_j=x$，$f(i,j)$ 的和。

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

第二行 $n$ 个用空格隔开的数表示序列 $a$。

之后 $m$ 行，每行四个用空格隔开的数 $opt,l,r,x$ 表示一次操作。

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

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

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

对于另外 $20\%$ 的数据，没有 $1$ 操作。

对于另外 $10\%$ 的数据，数据中的操作类型在 $[1,2]$ 内， $a_i,x$ 在 $[1,100]$ 内均匀随机生成，区间 $[l,r]$ 两个端点为 $[1,n]$ 中均匀随机生成的整数，如果生成后 $l>r$，则将二者交换。

对于另外 $30\%$ 的数据，满足 $1\le n,m\le 10^5$。

对于 $100\%$ 的数据，满足 $1\le n,m \le 5\times10^5$，$1\le l\le r\le n$，$1\le a_i,x\le n$，所有输入均为整数。


title: [Ynoi1999] 56TP

description:
给包含 $n$ 个顶点的有根树，每个顶点 $i$ 在时刻 $t$ 有权重 $v(t,i)$。

对每个顶点给出 $v(0,i)$，保证对非叶节点 $i$ 有 $v(0,i)=0$，对叶子 $i$ 有 $0\le v(0,i)\le n$。

共 $m$ 次询问，每次询问给出 $x,y,t$，问 $x$ 到 $y$ 路径上在时刻 $t$ 的权重的最小值、最大值、和。

对叶子 $i$，有 $v(t,i)=v(0,i)$；

对非叶节点 $i$，$t>0$，$v(t,i)$ 是 $i$ 的每个孩子 $j$ 的 $v(t-1,j)$ 的最大值。

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

接下来 $n-1$ 行每行一个整数依次表示 $f_2,\dots,f_n$，其中 $f_i$ 表示节点 $i$ 的父亲，根为 $1$。

接下来 $n$ 行每行一个整数依次表示 $v(0,1),v(0,2),\dots,v(0,n)$。

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

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

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

对于 $100\%$ 的数据，满足  $1\le n,m\le 10^6$，$1\le f_i\le i-1$，$0\le v(0,i)\le n$，$1\le x,y,t\le n$。


title: [Ynoi2000] tmostnrq

description:
给定 $n$ 个顶点的树，顶点编号为 $1,\dots,n$，给定长度 $n_0$ 的序列 $a_1,\dots,a_{n_0}$，共 $m$ 次查询，每次查询给定 $l,r,x$，问树的顶点 $x$，依次向 $a_l,\dots,a_r$ 移动一步，到达的顶点。

若 $x=y$，则从顶点 $x$ 向 $y$ 移动一步到达 $x$，否则到达与 $x$ 在树上相邻且距离 $y$ 最近的位置。

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

接下来一行 $n-1$ 个整数依次表示 $f_2,\dots,f_n$，其中 $f_i$ 是顶点 $i$ 的父亲，$1$ 为根；

接下来一行 $n_0$ 个整数，依次表示 $a_1,\dots,a_{n_0}$；

接下来 $m$ 行，每行三个整数 $l,r,x$ 表示一次查询。

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

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

对于 $100\%$ 的数据，满足 $1\le n,n_0,m\le 10^6$；


title: [Ynoi Easy Round 2024] TEST_132

description:
给定平面上 $n$ 个互不相同的点 $(x_i,y_i)_{i=1}^n$，每个点有点权，初始为 $v_i$；

共 $m$ 次操作：

修改操作：给定 $X$，将满足 $x_i=X$ 的点的点权 $v_i$ 修改为 $v_i^2$；

查询操作：给定 $Y$，求满足 $y_i=Y$ 的点的点权 $v_i$ 的和；

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

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

接下来 $n$ 行，每行三个整数 $x_i,y_i,v_i$；

接下来 $m$ 行，每行两个整数，修改操作表示为 $1,X$，查询操作表示为 $2,Y$；

outputFormat: 对每个查询操作，输出一行，表示答案。

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le x_i,y_i\le n$，$0\le v_i\le 10^9+6$，$1\le X,Y\le n$。

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

对于另外 $25\%$ 的数据，没有修改操作；

对于另外 $25\%$ 的数据，满足 $x_i,y_i,X,Y$ 在 $1,2,\dots,n$ 中独立地均匀随机选取；

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


title: [Ynoi2000] hpi

description: 给定 $n$ 个互不相同的点 $(x_i,y_i)$，共 $m$ 次询问，每次询问给出 $A,B,C$，问满足 $x_i<x_j,\;y_i<y_j,\;Ax_i+By_i+C>0,\;Ax_j+By_j+C>0$ 的二元组 $(i,j)$ 的个数。

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

接下来 $n$ 行每行两个数 $x_i,y_i$，$i=1,\dots,n$。

接下来 $m$ 行每行一个三个数表示一个询问 $A,B,C$。

outputFormat: 对每个询问，输出一行，包含一个整数，表示这个询问的答案。

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

对于 $100\%$ 的数据，满足 $A^2+B^2>0$，$|A|,|B|,|C|\le 10^8$，$1\le n,m\le 2\times 10^5$，$|x_i|,|y_i|\le 10^4$，$x_i,y_i$ 均匀随机选取，但保证没有重复的点。

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

对于另外 $25\%$ 的数据，满足 $A=0$。

对于另外 $25\%$ 的数据，满足 $C=0$。

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


title: 「Cfz Round 2」Max of Distance

description:
给定一棵包含 $n$ 个结点的树 $G$ 和一个整数 $E$。

你需要构造树 $G$ 中每条边的整数边权 $w_i$，满足：

- $1 \le w_i \le 10^9$；
- 均匀随机选择一个结点 $u$，$\max\limits_{v=1}^n\operatorname{dis}(u,v)$ 的期望对 $998244353$ 取模的值等于 $E$；

或报告无解。

其中，$\operatorname{dis}(u,v)$ 表示结点 $u,v$ 之间简单路径上的边权和。

如果你不知道如何计算期望对 $998244353$ 取模的结果，请移步 [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。

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

接下来 $n-1$ 行，每行输入两个正整数 $u_i,v_i$，表示树 $G$ 中结点 $u_i,v_i$ 之间存在一条边 $(u_i,v_i)$。

接下来一行，输入一个整数 $E$。

outputFormat:
输出一行或 $n-1$ 行：

- 若有解，则输出 $n-1$ 行，每行输出一个整数 $w_i$，表示你构造的树 $G$ 中边 $(u_i,v_i)$ 的边权；
- 若无解，则输出一行，包含一个整数 $-1$。

**所有满足要求的输出均可通过。**

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

所有 $\operatorname{dis}$ 的值如下表，其中标红的是行首结点的 $\operatorname{dis}$ 的最大值。

|$\operatorname{dis}$|$1$|$2$|$3$|
|:-:|:-:|:-:|:-:|
|$1$|$0$|$1$|$\color{red}3$|
|$2$|$1$|$0$|$\color{red}2$|
|$3$|$\color{red}3$|$2$|$0$|

可以验证，$E=\dfrac{3+2+3}{3}=\dfrac{8}{3}\equiv 665496238\pmod {998244353} $。

#### 「数据范围」

对于所有数据，$2\le n\le 10^5$，$1 \le u_i,v_i \le n$，$0\le E < 998244353$，保证输入数据形成一棵树。

**只有你通过本题的所有测试点，你才能获得本题的分数。**


title: [Ynoi2000] pri

description:
给定 $1,\dots,n$ 的排列 $a_1,\dots,a_n$ ；

共 $m$ 次操作，每次操作给出 $x$ ，首先进行修改，将 $a_1,a_2,\dots,a_x$ 翻转为 $a_x,\dots,a_2,a_1$ ，然后查询有多少组不同的 $(i,j)$ ，满足 $1\le i<j\le x$ 使得 $a_i<a_j$ 。

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

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

所有数值为整数。

对于 $100\%$ 的数据，满足 $1\le a_i\le n$，$1\le x\le n$，$1\le n\le 2\times 10^5,\;1\le m\le 5\times 10^4$。


title: [Ynoi2000] rspcn

description:
给定整数序列 $a_1,\dots,a_n$ ，共 $m$ 次操作；

每次操作给出 $l,r,x$ ，首先进行修改，然后查询 $a_1,\dots,a_x$ 中有多少种不同的值。

若 $l\le r$ ，则进行的修改是将 $a_l,\dots,a_r$ 从小到大排序；否则进行的修改是将 $a_r,\dots,a_l$ 从大到小排序。

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

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

接下来 $m$ 行，每行三个整数 $l\oplus c,r\oplus c,x\oplus c$ ，依次表示每次操作，其中 $\oplus$ 是按位异或，$c$ 是上次操作的查询的答案（特别地，对于第一次操作，$c=0$）。

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

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

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

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

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

对于另外 $20\%$ 的数据，满足 $n,m\le 10^5$。

对于 $100\%$ 的数据，满足 $1\le a_i\le n$，$1\le l,r,x\le n$，$1\le n,m\le 10^6$。


title: 「Cfz Round 2」Osmanthus

description:
给定一个长度为 $n$ 的序列 $a$。

我们定义一次操作为，**同时**将序列 $a$ 中的**每个**元素 $a_i$ 替换为 $\bigoplus\limits_{j=1}^i a_j$（即 $a_1$ 至 $a_i$ 的异或和），其中 $\bigoplus$ 表示**按位异或**，即 C++ 中的 `^`。

现有 $q$ 次有序的修改，每次修改会给定两个整数 $x_i,p_i$，表示将 $a_{x_i}$ 的值修改为 $p_i$。**修改之间并不独立，每次修改会对后续的修改产生影响**。

你需要在每次修改后，找到**最小**的正整数 $t$，满足进行 $t$ 次操作后的序列 $a$ 与操作前的序列 $a$ 相同。可以证明一定存在满足要求的正整数 $t$。

由于答案可能很大，所以你只需要输出答案对 $(10^9+7)$ 取模的结果。

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

第二行输入 $n$ 个整数，表示给定的序列 $a$。

接下来 $q$ 行，每行输入两个整数 $x_i,p_i$，表示一次修改。

outputFormat: 共 $q$ 行，每行输出一个整数，其中第 $i$ 行的整数表示第 $i$ 次修改后，最小的满足要求的正整数 $t$ 对 $(10^9+7)$ 取模的结果。

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

第 $1$ 次修改后的序列 $a$ 为 $\{3,2,0\}$，此时进行 $1$ 次操作后的序列 $a$ 为 $\{3,1,1\}$，进行 $2$ 次操作后的序列 $a$ 为 $\{3,2,3\}$，进行 $3$ 次操作后的序列 $a$ 为 $\{3,1,2\}$，进行 $4$ 次操作后的序列 $a$ 为 $\{3,2,0\}$，所以最小的满足要求的正整数 $t$ 为 $4$。

#### 「数据范围」

对于所有数据，$1 \le n,q \le 3\times10^5$，$0 \le a_i,p_i \le 10^9$，$1 \le x_i \le n$。

**只有你通过本题的所有测试点，你才能获得本题的分数。**


title: [Ynoi1999] XM66F

description: 给定序列 $a_1,\dots,a_n$ ，$m$ 次询问，每次询问给出 $l,r$ ，问有多少组 $(i,j,k)$ 满足 $l\le i<j<k\le r,\;a_i=a_k>a_j$ 。

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

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

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

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

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

所有数值为整数。

对于 $100\%$ 的数据，满足 $1\le a_i\le n$，$1\le l\le r\le n$，$n,m\le 5\times 10^5$。


title: [USACO20FEB] Triangles B

description:
Farmer John 想要给他的奶牛们建造一个三角形牧场。

有 $N$（$3\le N\le 100$）个栅栏柱子分别位于农场的二维平面上不同的点 $(X_1,Y_1)\ldots(X_N,Y_N)$。他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 $x$ 轴平行，且有另一条边与 $y$ 轴平行。

Farmer John 可以围成的牧场的最大面积是多少？保证存在至少一个合法的三角形牧场。

inputFormat: 输入的第一行包含整数 $N$。以下 $N$ 行每行包含两个整数 $X_i$ 和 $Y_i$，均在范围 $−10^4\ldots 10^4$ 之内，描述一个栅栏柱子的位置。

outputFormat: 由于面积不一定为整数，输出栅栏柱子可以围成的合法三角形的最大面积的**两倍**。

hint:
### 样例解释 1

位于点 $(0,0)$、$(1,0)$ 和 $(1,2)$ 的木桩组成了一个面积为 $1$ 的三角形。所以，答案为 $2\cdot 1=2$。只有一个其他的三角形，面积为 $0.5$。


title: [USACO20FEB] Mad Scientist B

description:
Farmer John 的远房亲戚 Ben 是一个疯狂的科学家。通常这会在家庭聚会时造成不小的摩擦，但这偶尔也会带来些好处，尤其是当 Farmer John 发现他正面对一些有关他的奶牛们的独特而不寻常的问题时。

Farmer John 当前正面对一个有关她的奶牛们的独特而不寻常的问题。他最近订购了 $N$ 头奶牛（$1\le N\le 1000$），包含两种不同品种：荷斯坦牛和更赛牛。他在订单中用一个长为 $N$ 的字符串来指定奶牛，其中的字符为 `H`（表示荷斯坦牛）或 `G`（表示更赛牛）。不幸的是，当这些奶牛到达他的农场，他给她们排队时，她们的品种组成的字符串与原先的不同。

我们将这两个字符串称为 $A$ 和 $B$，其中 $A$ 是 Farmer John 原先想要的品种字符组成的字符串，$B$ 是他的奶牛们到达时组成的字符串。Farmer John 并没有简单地检查重新排列 $B$ 中的奶牛是否能得到 $A$，而是请他的远房亲戚 Ben 利用他的科学才华来解决这一问题。

经过数月的研究，Ben 发明了一台不同寻常的机器：奶牛品种转换机 3000，能够选择任意奶牛组成的子串并反转她们的品种：在这个子串中的所有 `H` 变为 `G`，所有 `G` 变为 `H`。Farmer John 想要求出将他当前的序列 $B$ 变为他本来订购时想要的 $A$ 需要使用这台机器的最小次数。然而，Ben 的疯狂的科学家技能并不会处理开发奇异机器以外的事，所以你需要帮助 Farmer John 解决这个计算难题。

inputFormat: 输入的第一行包含 $N$，以下两行包含字符串 $A$ 和 $B$。每个字符串均包含 $N$ 个字符，字符均为 `H` 和 `G` 之一。

outputFormat: 输出将 $B$ 变为 $A$ 需要使用机器的最小次数。

hint:
### 样例解释 1

首先，FJ 可以仅改变第一个字符组成的子串，将 $B$ 变为 `GHGGGHH`。然后，他可以改变由第三和第四个字符组成的子串，得到 $A$。当然，还存在其他有效的执行两次操作的方案。


title: [USACO20FEB] Swapity Swap B

description:
Farmer John 的 $N$ 头奶牛（$1\le N\le 100$）站成一排。对于每一个 $1\le i\le N$，从左往右数第 $i$ 头奶牛的编号为 $i$。

Farmer John 想到了一个新的奶牛晨练方案。他让她们重复以下包含两个步骤的过程 $K$（$1\le K\le 10^9$）次：

1. 当前从左往右数在位置 $A_1\ldots A_2$ 的奶牛序列反转她们的顺序（$1\le A1<A2\le N$）。
2. 然后，在当前从左往右数在位置 $B_1\ldots B_2$的奶牛序列反转她们的顺序（$1\le B_1<B_2\le N$）。

当奶牛们重复这一过程 $K$ 次后，请对每一个 $1\le i\le N$ 输出从左往右数第 $i$ 头奶牛的编号。

inputFormat: 输入的第一行包含 $N$ 和 $K$。第二行包含 $A_1$ 和 $A_2$，第三行包含 $B_1$ 和 $B_2$。

outputFormat: 在第 $i$ 行输出晨练结束时从左往右数第 $i$ 头奶牛的编号。

hint:
### 样例解释 1

初始时，奶牛们的顺序从左往右为 $[1,2,3,4,5,6,7]$。在这一过程的第一步过后，顺序变为 $[1,5,4,3,2,6,7]$。在这一过程的第二步过后，顺序变为 $[1,5,7,6,2,3,4]$。再重复这两个步骤各一次可以得到样例的输出。

### 测试点性质

- 测试点 $2-3$ 满足 $K\le 100$。
- 测试点 $4-13$ 没有额外限制。


title: [USACO20OPEN] Social Distancing I B

description:
一种新型疾病，COWVID-19，开始在全世界的奶牛之间传播。Farmer John 正在采取尽可能多的预防措施来防止他的牛群被感染。

Farmer John 的牛棚是一个狭长的建筑物，有一排共 $N$ 个牛栏（$2\le N\le 10^5$）。有些牛栏里目前有奶牛，有些目前空着。得知“社交距离”的重要性，Farmer John 希望使得 $D$ 尽可能大，其中 $D$ 为最近的两个有奶牛的牛栏的距离。例如，如果牛栏 $3$ 和 $8$ 是最近的有奶牛的牛栏，那么 $D=5$。

最近两头奶牛新来到 Farmer John 的牛群，他需要决定将她们分配到哪两个之前空着的牛栏。请求出他如何放置这两头新来的奶牛，使得 $D$ 仍然尽可能大。Farmer John 不能移动任何已有的奶牛；他只想要给新来的奶牛分配牛栏。

inputFormat: 输入的第一行包含 $N$。下一行包含一个长为 $N$ 的字符串，由 $0$ 和 $1$ 组成，描述牛棚里的牛栏。$0$ 表示空着的牛栏，$1$ 表示有奶牛的牛栏。字符串中包含至少两个 $0$，所以有至少有足够的空间安置两头新来的奶牛。

outputFormat: 输出 Farmer John 以最优方案在加入两头新来的奶牛后可以达到的最大 $D$ 值（最近的有奶牛的牛栏之间的距离）。

hint:
### 样例解释 1

在这个例子中，Farmer John 可以以这样的方式加入奶牛，使得牛栏分配变为 `10x010010x0010`，其中 `x` 表示新来的奶牛。此时 $D=2$。不可能在加入奶牛之后取到更大的 $D$ 值。

### 测试点性质

- 测试点 $2-6$ 满足 $N\le 10$。
- 测试点 $7-8$ 满足 $N\le 100$。
- 测试点 $9-11$ 满足 $N\le 5000$。
- 测试点 $12-15$ 没有额外限制。


title: [USACO20OPEN] Social Distancing II B

description:
由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。

尽管他尽了最大努力使他的 $N$ 头奶牛们（$1\le N\le 1000$）践行“社交距离”，还是有许多奶牛不幸染上了疾病。编号为 $1\ldots N$ 的奶牛们分别位于一条长直道路上的不同位置（相当于一维数轴），奶牛 $i$ 位于位置 $x_i$。Farmer John 知道存在一个半径 $R$，任何与一头被感染的奶牛距离不超过 $R$ 单位的奶牛也会被感染（然后会传染给与其距离 $R$ 单位内的奶牛，以此类推）。

不幸的是，Farmer John 并不确切知道 $R$ 的值。他只知道他的哪些奶牛被感染了。给定这个数据，求出起初感染疾病的奶牛的最小数量。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行每行用两个整数 $x$ 和 $s$ 描述一头奶牛，其中 $x$ 为位置（$0\le x\le 10^6$），$s$ 为 $0$ 表示健康的奶牛，$1$ 表示染病的奶牛，并且所有可能因传播而染病的奶牛均已染病。

outputFormat: 输出在疾病开始传播之前已经得病的奶牛的最小数量。

hint:
### 样例解释 1

在这个例子中，我们知道 $R<3$，否则位于位置 $7$ 的奶牛会传染给位于位置 $10$ 的奶牛。所以，至少 $3$ 头奶牛初始时已被感染：位于位置 $1$ 和 $3$ 的两头奶牛中的一头，位于位置 $6$ 和 $7$ 的两头奶牛中的一头，以及位于位置 $15$ 的奶牛。


title: [USACO20OPEN] Cowntact Tracing B

description:
由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们（编号为 $1\ldots N$）的健康。

最近，Farmer John 对他的所有奶牛进行了检测，发现有一部分奶牛对该疾病的检测结果呈阳性。利用牛棚内的视频监控，他得以查看最近的奶牛之间的互动行为，结果发现奶牛们互相打招呼时，她们会握蹄，不幸的是这是一种会将疾病从一头奶牛传播给另一头奶牛的行为。Farmer John 汇总了一个添加了时间戳的清单，每条数据的形式为 $(t,x,y)$，表示在时间 $t$，奶牛 $x$ 与奶牛 $y$ 握了蹄。Farmer John 同时还知道以下信息：

（一）他的农场上恰有一头奶牛最初带有携带疾病（我们将这头奶牛称为“零号病人”）。

（二）一旦一头奶牛被感染，她会在接下来的 $K$ 次握蹄中传染疾病（可能会与同一头奶牛握蹄多次）。握蹄 $K$ 次后，她不再在此后的握蹄中传染疾病（因为此时她意识到了她会传染疾病，于是会仔细地洗蹄）。

（三）一旦一头奶牛被感染，她会持续处于被感染状态。

不幸的是，Farmer John 不知道他的 $N$ 头奶牛中的哪一头是零号病人，也不知道 $K$ 的值！基于他的数据，请帮助他缩小这些未知量的范围。保证至少有一种可能的情况。

inputFormat: 输入的第一行包含 $N$（$2\le N\le 100$）和 $T$（$1\le T\le 250$）。下一行包含一个长为 $N$ 的字符串，每个字符均为 $0$ 或 $1$，表述目前 Farmer John 的 $N$ 头奶牛的状态——$0$ 表示一头健康的奶牛，$1$ 表示一头染病的奶牛。以下 $T$ 行每行包含 Farmer John 的互动清单中的一条记录，由三个整数 $t$、$x$ 和 $y$ 组成，其中 $t$ 为一次互动发生的正整数时间（$t\le 250$），$x$ 和 $y$ 为范围 $1\ldots N$ 内的不同整数，表示时间 $t$ 握蹄的两头奶牛。在每一时刻至多只有一次互动发生。

outputFormat: 输出一行，包含三个整数 $x$、$y$ 和 $z$，其中 $x$ 为可能为零号病人的奶牛数量，$y$ 为与数据一致的最小可能 $K$ 值，$z$ 为与数据一致的最大可能 $K$ 值（如果通过数据无法推断 $K$ 的上界，$z$ 输出 `Infinity`）。注意可能有 $K=0$。

hint:
### 样例解释 1

唯一可能是零号病人的是奶牛 $1$。对于所有的 $K>0$，奶牛 $1$ 在时刻 $7$ 感染奶牛 $2$，而奶牛 $3$ 和奶牛 $4$ 均不会被感染。


title: [USACO20DEC] Do You Know Your ABCs? B

description:
Farmer John 的奶牛正在 "mooZ" 视频会议平台上举行每日集会。她们发明了一个简单的数字游戏，为会议增添一些乐趣。

Elsie 有三个正整数 $A$、$B$ 和 $C$（$A\le B\le C$）。这些数字是保密的，她不会直接透露给她的姐妹 Bessie。她告诉 Bessie 七个范围在 $1\ldots 10^9$ 之间的整数（不一定各不相同），并宣称这是 $A$、$B$、$C$、$A+B$、$B+C$、$C+A$ 和 $A+B+C$ 的某种排列。

给定这七个整数，请帮助 Bessie 求出 $A$、$B$ 和 $C$。可以证明，答案是唯一的。

inputFormat: 输入一行，包含七个空格分隔的整数。

outputFormat: 输出 $A$、$B$ 和 $C$，用空格分隔。

hint:
### 测试点性质

- 测试点 $2-3$ 满足 $C\le 50$。
- 测试点 $4-10$ 没有额外限制。


title: [USACO20DEC] Daisy Chains B

description:
每天，作为她绕农场行走的一部分，奶牛 Bessie 会经过她最喜爱的草地，其中种有 $N$ 朵花（五颜六色的雏菊），编号为 $1\ldots N$（$1\le N\le 100$），排列成一行。花 $i$ 有 $p_i$ 朵花瓣（$1\le p_i\le 1000$）。

作为一名崭露头角的摄影家，Bessie 决定给这些花拍些照片。具体地说，对于每一对满足 $1\le i\le j\le N$ 的花 $(i,j)$，Bessie 会给从花 $i$ 到花 $j$ 之间的所有花（包括 $i$ 和 $j$）拍一张照。

后来 Bessie 查看这些照片时注意到有些照片里存在「平均」的花——一朵恰好有 $P$ 朵花瓣的花，其中 $P$ 等于照片中所有花的花瓣数量的平均值。

Bessie 的照片中有几张存在平均的花？

inputFormat: 输入的第一行包含 $N$。第二行包含 $N$ 个空格分隔的整数 $p_1\ldots p_N$。

outputFormat: 输出存在平均的花的照片数量。

hint:
### 样例解释 1

每张仅包含一朵花的照片均会被计入答案（在这个样例中有 $4$ 张）。另外，在这个样例中 $(i,j)$ 为 $(1,2)$ 和 $(2,4)$ 所对应的照片也存在平均的花。


title: [USACO20DEC] Stuck in a Rut B

description:
Farmer John 最近扩大了他的农场，从奶牛们的角度看来这个农场相当于是无限大了！奶牛们将农场上放牧的区域想作是一个由正方形方格组成的无限大二维方阵，每个方格中均有美味的草（将每个方格看作是棋盘上的一个方格）。Farmer John 的 $N$ 头奶牛（$1\le N\le 50$）初始时位于不同的方格中，一部分朝向北面，一部分朝向东面。

每一小时，每头奶牛会执行以下二者之一：

 - 如果她当前所在的方格里的草已经被其他奶牛吃掉了，则她会停下。
 - 吃完她当前所在的方格中的所有草，并向她朝向的方向移动一个方格。

经过一段时间，每头奶牛的身后会留下一条被啃秃了的轨迹。

如果两头奶牛在一次移动中移动到了同一个有草的方格，她们会分享这个方格中的草，并在下一个小时继续沿她们朝向的方向移动。

请求出每头奶牛吃到的草的数量。有些奶牛永远不会停下，从而吃到无限多的草。

inputFormat:
输入的第一行包含 $N$。以下 $N$ 行，每行描述一头奶牛的起始位置，包含一个字符 `N`（表示朝向北面） 或 `E`（表示朝向东面），以及两个非负整数 $x$ 和 $y$（$0\le x\le 10^9$，$0\le y\le 10^9$）表示方格的坐标。所有 $x$ 坐标各不相同，所有 $y$ 坐标各不相同。

为了使方向和坐标尽可能明确，如果一头奶牛位于方格 $(x,y)$ 并向北移动，她会到达方格 $(x,y+1)$。如果她向东移动，她会到达方格 $(x+1,y)$。

outputFormat: 输出 $N$ 行。输出的第 $i$ 行包含输入中的第 $i$ 头奶牛吃到草的方格的数量。如果一头奶牛可以吃到无限多的草，为这头奶牛输出 `Infinity`。

hint:
### 测试点性质

 - 测试点 $2-5$ 中，所有坐标不超过 $100$。
 - 测试点 $6-10$ 没有额外限制。


title: [USACO19JAN] Shell Game B

description:
为了消磨时光，奶牛 Bessie 和她的朋友 Elsie 喜欢玩一种她们在农业展览会上看到的游戏。

游戏准备阶段，Bessie 在桌子上放置三个倒置的坚果壳，并在其中一个坚果壳下面藏了一块小的鹅卵石（至少她希望这是一块鹅卵石——她在一块牧场的地上找到的）。随后 Bessie 会两两调换坚果壳，同时 Elsie 试着去猜鹅卵石的位置。

奶牛们在农业展览会上看到的这个游戏的标准形式是玩家可以看到鹅卵石初始的位置，然后要求玩家猜所有交换完成之后鹅卵石最终的位置。

然而，现在奶牛们想要去进行这样一种玩法，Elsie 不知道鹅卵石的初始位置，同时她可以在每一次交换之后猜一下鹅卵石的位置。Bessie 知道正确答案，在游戏结束后会给 Elsie 一个分数，等于她猜对的次数。

给定所有的交换和 Elsie 的猜测，但是不给出鹅卵石的初始位置，请求出 Elsie 最高可能获得的分数。

inputFormat: 输入的第一行包含一个整数 $N$，为交换的次数（$1\le N\le 100$）。以下 $N$ 行每行描述了游戏的一个回合，包含三个整数 $a$、$b$ 和 $g$，表示 Bessie 交换了坚果壳 $a$ 和 $b$，然后 Elsie 猜的是坚果壳 $g$。所有这三个数均为 $1$、$2$、$3$ 之一，并且 $a\neq b$。

outputFormat: 输出 Elsie 可以得到的最高分数。

hint:
### 样例解释 1

在这个例子中，Elsie 最多可以获得 $2$ 分。如果鹅卵石开始时位于坚果壳 $1$ 下面，那么她猜中了一次（最后一次）。如果鹅卵石开始时位于坚果壳 $2$ 下面，那么她猜中了两次（开始两次）。如果鹅卵石开始时位于坚果壳 $3$ 下面，那么她没有猜对任何一次。


title: [USACO19JAN] Sleepy Cow Sorting B

description:
Farmer John正在尝试将他的 $N$ 头奶牛（$1\le N\le 100$），方便起见编号为 $1\ldots N$，在她们前往牧草地吃早餐之前排好顺序。

当前，这些奶牛以 $p_1,p_2,p_3,\ldots,p_N$ 的顺序排成一行，Farmer John 站在奶牛 $p_1$ 前面。他想要重新排列这些奶牛，使得她们的顺序变为 $1,2,3,\ldots,N$，奶牛 $1$ 在 Farmer John 旁边。

今天奶牛们有些困倦，所以任何时刻都只有直接面向 Farmer John 的奶牛会注意听 Farmer John 的指令。每一次他可以命令这头奶牛沿着队伍向后移动 $k$ 步，$k$ 可以是范围 $1\ldots N−1$ 中的任意数。她经过的 $k$ 头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。

例如，假设 $N=4$，奶牛们开始时是这样的顺序：

> FJ: $4, 3, 2, 1$

唯一注意 FJ 指令的奶牛是奶牛 $4$。当他命令她向队伍后移动 $2$ 步之后，队伍的顺序会变成：

> FJ: $3, 2, 4, 1$

现在唯一注意 FJ 指令的奶牛是奶牛 $3$，所以第二次他可以给奶牛 $3$ 下命令，如此进行直到奶牛们排好了顺序。

Farmer John 急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。请帮助他求出将奶牛们排好顺序所需要的最小操作次数。

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

第二行包含 $N$ 个空格分隔的整数，$p_1,p_2,p_3,\ldots,p_N$，表示奶牛们的起始顺序。

outputFormat: 输出一个整数，为 Farmer John 采用最佳策略可以将这 $N$ 头奶牛排好顺序所需要的操作次数。


title: [USACO19JAN] Guess the Animal B

description:
奶牛 Bessie 和她的朋友 Elsie 厌倦了她们的坚果壳游戏，她们想要玩另一个叫做“猜动物”的常见游戏。

游戏开始时，Bessie 会想好一种动物（大部分时候，她想的都是奶牛，这使得游戏相当无聊，但是偶尔 Bessie 也能有些新意，想一些别的）。随后 Elsie 会通过问一些问题来猜出 Bessie 选择的动物。每个问题都是询问这种动物是否具有某个特定的特征，Bessie 对于每个问题回答“是”或“不是”。例如：

Elsie：“这种动物是能飞的吗？”
Bessie：“不是。”
Elsie：“这种动物是吃草的吗？”
Bessie：“是。”
Elsie：“这种动物是能产奶的吗？”
Bessie：“是。”
Elsie：“这种动物是会哞哞叫的吗？”
Bessie：“是。”
Elsie：“这样的话我想这种动物是奶牛。”
Bessie：“猜对了！”

如果我们将所有具备符合 Elsie 到目前为止所提出的问题的特征的动物的集合称为“可行集”，那么 Elsie 会持续进行提问直到可行集仅包含一种动物，然后她会把这种动物作为她的答案。对于每个问题，Elsie 会选择某种动物的一个特征进行询问（即使这个特征并不能进一步帮助她缩小可行集）。她不会关于同一个特征询问两次。

给定 Bessie 和 Elsie 知道的所有动物以及它们的特征，请求出 Elsie 在猜出正确的动物之前能够得到的“是”的回答的最大数量。

inputFormat: 输入的第一行包含动物的数量 $N$（$2\le N\le 100$）。以下 $N$ 行每行描述了一种动物。每一行开始是这种动物的名称，接下来是一个整数 $K$（$1\le K\le 100$），接下来是这种动物的K个特征。动物的名称和特征是至多 $20$ 个小写字母（`a..z`）组成的字符串。没有两种动物具有完全相同的特征。

outputFormat: 输出游戏结束之前 Elsie 可能得到的“是”的回答的最大数量。

samples:
4
bird 2 flies eatsworms
cow 4 eatsgrass isawesome makesmilk goesmoo
sheep 1 eatsgrass
goat 2 makesmilk eatsgrass

hint:
### 样例解释 1

在这个例子中，Elsie 可能在对话中获得 $3$ 个“是”的回答（题目中的例子），并且不可能进行包含超过 $3$ 个“是”的回答的对话。


title: [USACO19FEB] Sleepy Cow Herding B

description:
Farmer John 的三头获奖奶牛 Bessie、Elsie 和 Mildred，总是会迷路走到农场上遥远的地方去！他需要你帮助将她们一起赶回来。

农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。这 $3$ 头奶牛现在正位于不同的整数位置，Farmer John 想要移动她们，使得她们占据三个相邻的位置（例如，位置 $6$、$7$、$8$）。

不幸的是，奶牛们现在很困，Farmer John 要让她们集中精力听从命令移动并不容易。任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。

inputFormat: 输入包含一行，包括三个空格分隔的整数，为 Bessie、Elsie 和 Mildred 的位置。每个位置均为一个范围 $1\ldots 10^9$ 内的整数。

outputFormat: 输出的第一行包含 Farmer John 需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。

hint:
### 样例解释 1

最小移动次数为 $1$——如果 Farmer John 将位置 $4$ 的奶牛移动到位置 $8$，那么奶牛们就处在连续的位置 $7$、$8$、$9$。最大移动次数为 $2$。例如，位置 $9$ 的奶牛可以被移动到位置 $6$，然后位置 $7$ 的奶牛可以被移动到位置 $5$。


title: [USACO19FEB] The Great Revegetation B

description:
长时间的干旱使得 Farmer John 的 $N$ 块草地上牧草匮乏。随着雨季即将到来，现在应当是重新种植的时候了。

在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。他的 $M$ 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以有两种草可供选择。Farmer John 知道没有一块草地受到多于 $3$ 头奶牛的喜爱。

请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。

inputFormat: 输入的第一行包含 $2 \leq N \leq 100$ 和 $1 \leq M \leq 150$。以下 $M$ 行，每行包含两个范围为 $1 \dots N$ 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。

outputFormat: 输出一个 $N$ 位数，每一位均为 $1\ldots 4$ 之一，表示每一块草地上所种的草的种类。第一位对应草地 $1$ 的草的种类，第二位对应草地 $2$，以此类推。如果有多种可行的解，只需输出所有解中最小的 $N$ 位数。


title: 【深基1.例2】简单的分苹果

type: B

background: **本题来自洛谷编写教材《深入浅出程序设计竞赛 - 基础篇》**，并带有详细的教程和讲解，点击下列链接了解本书详情。[【官方网店绝赞热卖中！】>>>](https://item.taobao.com/item.htm?id=637730514783)

description:
这里有 $10$ 个苹果，小 A 拿走了 $2$ 个，Uim 拿走了 $4$ 个，八尾勇拿走剩下的所有的苹果。我们想知道：

1. 小A 和 Uim 两个人一共拿走多少苹果？
2. 八尾勇能拿走多少苹果？

现在需要编写一个程序，输出两个数字作为答案，中间使用空格分开。

inputFormat: 不需要输入。

outputFormat: 输出两个数字作为答案，中间使用空格分开。


title: 【深基1.例3】简单的分苹果 2

description:
现在有 $14$ 个苹果。要均分给 $4$ 名同学，分不掉的苹果放回冰箱。请问：

1. 每位同学能分得几个苹果？
2. 一共分出去多少苹果？
3. 把几个苹果放回冰箱？

现在需要编写一个程序，输出三个数字作为答案，每个数字一行。

outputFormat: 输出三个数字作为答案，每个数字一行。


title: 【深基1.例9】圆的计算

description: 当半径为 $r=5$，请输出圆的周长、面积和球体积。取 $\pi=3.141593$。请直接使用 `cout` 输出答案，每行一个数字。

outputFormat: 请直接使用 `cout` 输出答案，每行一个数字。一共三个数字。


title: 【深基1.例10】简单的猴子吃桃

description: 一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半，又贪嘴多吃了一个；第二天他也刚好吃了剩余桃子的一半，贪嘴多吃了一个；第三天他又刚好吃了剩下的桃子的一半，并贪嘴多吃了一个。第四天起来一看，发现桃子只剩下一个了。请问小猴买了几个桃子？

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


title: 【深基1.例11】评测机队列

description: 洛谷的评测任务是单位时间内均匀增加的。$8$ 台评测机 $30$ 分钟可以刚好把评测队列中的程序评测完毕，$10$ 台评测机 $6$ 分钟可以刚好把评测队列中的程序评测完毕，请问几台评测机可以在 $10$ 分钟时刚好把评测队列中的程序评测完毕？

outputFormat: 请输出一个数字表示答案。这个数字是一个整数。


title: 【深基1.习1】清扫教室

description: $3$ 名同学 $3$ 小时可以扫干净 $3$ 间教室，那么 $9$ 名同学 $9$ 小时可以扫干净几间教室？

outputFormat: 请输出一个数字表示答案。这个数字是一个整数。


title: 【深基1.习2】面积计算

description: 一个长方形的长和宽的和是 $24$ 厘米，长比宽多 $4$ 厘米，请问这个长方形的面积是多少？

outputFormat: 请输出一个数字表示答案。这个数字是一个整数。


title: 【深基1.习3】竞赛得分

description: 小A 和 UIM 程序设计竞赛中得分之和是 $480$，UIM 的得分是小A 的 $1.4$ 倍，请问他们分别得了多少分？

outputFormat: 请输出两个数字表示答案，均为整数，中间用空格隔开。


title: 【深基1.习4】简单的分苹果 3

description: 给同学分苹果，若每人分 $3$ 个就剩下 $11$ 个；如果每人分 $4$ 个则少一个，请问有多少同学，有多少个苹果？

outputFormat: 请输出两个整数表示答案，使用空格隔开。


title: 【深基1.习5】打字速度

description: 小A 每分钟输入 $120$ 个字符，UIM 每分钟输入 $80$ 个字符，UIM 比小A 先开始打字 $12$ 分钟，请问小A 开始打字多少时间后能赶上 UIM 的进度？

outputFormat: 请输出一个数字表示答案。这个数字是一个整数。


title: 【深基1.习6】鸡兔共笼

description: 兔子有 $4$ 只脚，鸡有 $2$ 只。一个笼子里面有若干只兔子和鸡，有 $35$ 个头，$94$ 只脚，请问兔子和鸡分别有几只？

outputFormat: 请输出两个整数表示答案，使用空格隔开。


title: 【深基1.习7】定期存款

description: 银行定期存款年利率是一年定存 3.5% ，五年定存 4%。小 A 和 UIM 手上各有 $10000$ 元。小A 决定每次存一年期，到期后将连本带利再存一年，直到存满 $5$ 年。UIM 直接存五年定期。请问 $5$ 年后小 A 和 UIM 分别有多少钱？

outputFormat: 请输出两个浮点数表示答案。直接使用 cout 输出答案即可，中间用空格隔开。


title: 【深基2.例1】跑步

description: 小 A 跑步速度 $5 \text{ m/s}$，八尾勇跑步速度 $8 \text{ m/s}$，八尾勇在小 A 后面 $100 \text{ m}$，他们同时起跑，请问需要多长时间八尾勇可以追上小 A？输出一个数字表示答案，使用 `cout` 直接输出。

outputFormat: 请输出一个数字表示答案，使用 `cout` 直接输出。


title: 【深基2.例2】英文字母

description:
大家都知道有 $26$ 个英文字母，其中 A 是第一个字母。现在请编程求出：

1. M 是字母表中的第几个字母？
2. 第 $18$ 个大写字母是什么？

输出一个数字和一个字母，使用换行隔开。

outputFormat: 输出一个数字和一个字母，使用换行隔开。


title: 【深基2.例3】玩橡皮泥

description: 小 A 有两块球形橡皮泥，一个半径是 $4$，一个半径是 $10$。他想把这两块橡皮泥揉在一起，然后塑造成一个正方体，请问这个正方体的棱长是多少？如果结果不是整数，则舍去小数点之后的数字。取 $\pi = 3.141593$。

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


title: 【深基2.例4】销量预测

description: 根据咕咕网校的预测，当课程定价为 $110$ 元时，会有 $10$ 人报名。如果课程价格每降低 $1$ 元，就会多 $1$ 名报名者（反之亦然）。如果希望总共能收到 $3500$ 元学费的话，那么应该定价多少呢？已知本题有两个答案符合要求，则取较小的那一个。如果这个答案不是整数，则需四舍五入精确到整数。

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


title: 【深基3.例1】数字比较

description:
输入两个整数 $a$ 和 $b$（其绝对值不超过 $10000$），想知道：

1. $a$ 是否大于 $b$？
2. $a$ 是否小于或等于 $b$？
3. $a$ 是否不等于 $b$？

inputFormat: 输入两个整数 a 和 b。

outputFormat: 输出 3 个整数，用空格隔开。对于每一个询问，如果成立（条件为真）输出 1，否则输出 0。


title: [USACO19FEB] Measuring Traffic B

description:
Farmer John 的农场边上的高速公路最近出现了引人注目的流量上升，或者至少 Farmer John 看起来是这样的。为了证实这件事，他打算用一组传感器测量公路上的车流量，每个传感器被用来测量一小段路面上的车流量的数值。

不幸的是，某一天经过牛棚的时候，Farmer John 被绊倒了，装有传感器的盒子掉进了一个巨大的奶缸，之后它们就不能正常工作了。比起之前可以产生一个精确的车流量读数，现在每个传感器只能输出一个可能结果的范围。例如，一个传感器可能会给出范围 $[7,13]$，表示在这段路面上的车流量不小于 $7$，并且不大于 $13$。

高速公路经过农场的这一段长 $N$ 英里，车辆仅从一个方向通过公路，从第 $1$ 英里驶向第 $N$ 英里。Farmer John 想要安装 $N$ 个传感器——每一个监测高速公路上 $1$ 英里长的路段。在其中某些路段上，有能够使得车辆进入高速公路的上匝道；在所有这样的路段上，Farmer John 会将传感器装在上匝道上，测量流入的（近似）车流量。在某些路段上有能够使得车辆离开高速公路的下匝道；在所有这样的路段上，Farmer John 会将传感器装在下匝道上。每一个路段包含至多一个匝道。如果在公路的一个路段上没有上匝道或下匝道，Farmer John就将传感器装在高速公路的主路上。

给定 Farmer John 的 $N$ 个传感器的读数，请求出在高速公路第 $1$ 英里之前和第 $N$ 英里之后车流量的最为准确的可能范围。这些范围应当与所有 $N$ 个传感器的读数相一致。

inputFormat: 输入的第一行包含 $N$（$1\le N\le 100$）。余下 $N$ 行每行按从第 $1$ 英里至第 $N$ 英里的顺序描述一段 $1$ 英里长的路段。每行包含一个字符串，为 `on`（如果这段路上有一个上匝道），`off`（如果这段路上有一个下匝道），或者是 `none`（如果这段路上没有匝道），然后是两个范围为 $0\ldots 1000$ 的整数，表示这段路上的传感器的读数所给出的下界、上界。如果这段路上包含匝道，传感器读数来自于匝道，否则来自于主路。至少一个高速公路路段的描述会是 `none`。

outputFormat: 输出的第一行包含两个整数，为第 $1$ 英里之前的车流量的最准确的可能范围。第二行包含两个整数，为第 $N$ 英里之后的车流量的最准确的可能范围。输入保证存在符合要求的解。

hint:
### 样例解释 1

在这个例子中，路段 $2$ 和路段 $3$ 的读数组合在一起告诉我们通过这两个路段的车流量为范围 $[11,14]$ 之间的某个值，因为只有这个范围与两个读数 $[10,14]$ 和 $[11,15]$ 均一致。在第 $1$ 英里，恰有 $1$ 单位的车辆通过上匝道进入，所以在第 $1$ 英里之前，车流量一定在范围 $[10,13]$ 之内。在第 $4$ 英里，$2$ 单位到 $3$ 单位之间的车辆通过下匝道离开，所以这段路之后可能的车流量范围为 $[8,12]$。


title: [THUPC 2024 初赛] 排序大师

description:
由于你是排序大师，你经常被路过的游客刁难，要求用一些奇怪的操作给序列排序。

由于你是远近闻名的排序大师，邻国的排序萌新小 I 慕名前来拜访，留下了一个长度为 $n$ 的排列 $a_1, a_2 \cdots, a_n$，并要求你用以下操作将排列升序排序：

- 定义 $a_{i \sim j} = \{a_i,a_{i+1},\cdots, a_j\}$。选定 $1 \le i \le j < k \le l \le n$，交换 $a_{i \sim j}$ 和 $a_{k \sim l}$，即交换过后序列变为 $a_{1 \sim i-1}, a_{k \sim l}, a_{j+1 \sim k-1}, a_{i \sim j}, a_{l+1 \sim n}$。

由于你是因精益求精而远近闻名的排序大师，你需要给出一个排序方案**最小化**操作次数。

inputFormat: 输入的第一行一个整数 $n(1 \le n \le 2000)$ 表示序列长度，第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n (1 \le a_i \le n)$ 描述排列。

outputFormat: 输出的第一行一个整数 $s$ 表示你给出的方案的步数，接下来 $s$ 行每行四个整数 $i,j,k,l$ 表示一次操作。若有多个方案，输出任意一个即可。

hint:
### 样例 \#1 解释
选定 $i = 2, j = 3, k = 5, l = 5$，$\colorbox{white}{\color{black}{1}\color{blue}{45}\color{black}{3}\color{red}{2}\color{black}{6}}$ 变为 $\colorbox{white}{\color{black}{1}\color{red}{2}\color{black}{3}\color{blue}{45}\color{black}{6}}$。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 一棵树

description:
这里有一棵树，具体的，这是一张有 $n$ 个节点和 $n-1$ 条边组成的无向联通图。

每个节点初始颜色为白色，你需要恰好将其中 $k$ 个节点染成黑色，定义一条边的权值是，断开这条边之后，两个连通块的黑色节点个数之差，定义一棵树的权值为所有边的权值求和，你需要最小化整棵树的权值。

inputFormat:
第一行两个正整数 $n,k$（$1\leq k\leq n\leq 5\times10^5$）。

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

outputFormat: 输出共 $1$ 行，表示最优的染色方案下，这棵树的权值的最小值。

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

下图展示了一种满足条件的染色方案，边上的数字表示边权。

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

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 前缀和

description:
小兰很喜欢随机数。

TA 首先选定了一个实数 $0 < p < 1$，然后生成了 $n$ 个随机数 $x_1,\dots,x_n$，每个数是独立按照如下方式生成的：

- $x_i$ 有 $p$ 的概率是 $1$，有 $(1-p)p$ 的概率是 $2$，有 $(1-p)^2p$ 的概率是 $3$，以此类推。

生成完这些随机数之后，小艾对这个数列求了前缀和，得到了数列 $y_1,\dots,y_n$。

给定 $1\leq l\leq r\leq n$，小兰想知道，期望有多少 $y_i$ 落在 $[l, r]$ 内？

inputFormat: 一行输入四个数 $n, p, l, r$。保证 $1\leq l\leq r\leq n\leq 10^9$，$p$ 的位数不超过 $6$。

outputFormat: 输出一个实数，表示答案。你需要保证答案的绝对或相对误差不超过 $10^{-6}$。

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

有 $1/4$ 的概率，$x_1=1$ 而 $x_2>1$，此时只有 $y_1$ 落在 $[1, 2]$ 内。

有 $1/4$ 的概率，$x_1=1$ 且 $x_2=1$，此时 $y_1,y_2$ 落在 $[1, 2]$ 内。

有 $1/4$ 的概率，$x_1=2$，此时只有 $y_1$ 落在 $[1, 2]$ 内。

所以期望是 $1/4\cdot (1 + 2 + 1) = 1$。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [USACO23DEC] Candy Cane Feast B

description:
Farmer John 的奶牛对甜食情有独钟，它们尤其喜欢吃糖果棒。FJ 共有 $N$ 头奶牛，每头奶牛都有一个特定的初始高度。他想要喂它们 $M$ 根糖果棒，每根糖果棒的高度也各不相同（$1 \le N,M \le 2\cdot 10^5$）。

FJ 计划按照输入给出的顺序，逐一喂给奶牛们糖果棒。然后，奶牛们会按照输入给出的顺序一个接一个地排队，走向糖果棒，每头奶牛最多吃到与它高度相同的部分（因为它们够不到更高的地方）。即使奶牛吃掉了糖果棒的底部，糖果棒也在最初悬挂的地方保持不动，并不会被降低到地面。如果糖果棒的底部已经高于某头奶牛的高度，那么这头奶牛在它的回合中可能什么也吃不到。每头奶牛轮流吃过后，它们的身高会增加它们吃掉的糖果棒的单位数量，然后农夫约翰挂上下一根糖果棒，奶牛们再次重复这个过程（第一头奶牛再次成为第一个开始吃下一根糖果棒的）。

inputFormat:
第一行包含 $N$ 和 $M$。

接下来的一行包含 $N$ 头奶牛的初始高度，每头奶牛的高度都在 $[1,10^9]$ 的范围内。

接下来的一行包含 $M$ 根糖果棒的长度，每根糖果棒的长度都在 $[1,10^9]$ 的范围内。

outputFormat:
输出 $N$ 行，表示每头奶牛最终的高度。

请注意，由于这个问题涉及的整数大小较大，可能需要使用 64 位整数数据类型（例如，在 C/C++ 中使用 `long long` 类型）。

hint:
### 样例解释 1

第一根糖果棒高度为 $6$ 单位。

- 第一头奶牛吃掉了第一根糖果棒直至高度 $3$ 的部分，之后第一根糖果棒剩余高度 $[3,6]$ 的部分。
- 第二头奶牛不够高，无法吃掉第一根糖果棒的任何剩余部分。
- 第三头奶牛额外吃掉了第一根糖果棒的两个单位。第一根糖果棒的剩余高度 $[5,6]$ 的部分未被吃掉。

接下来，每头奶牛根据它吃掉的数量增长，所以奶牛的高度变为 $[3+3, 2+0, 5+2]=[6, 2, 7]$。

第二根糖果棒高度为 $1$ 单位，被第一头奶牛全部吃掉。

### 测试点性质

- 测试点 $2-10$ 满足 $N,M \le 10^3$。
- 测试点 $11-14$ 没有额外限制。


title: [THUPC 2024 初赛] 多折较差验证

description:
临海听潮意，入林闻籁鸣。这是一座依山傍水、宁静祥和的小镇，在这里人们很少担心自己家里的物品故障损坏，因为 Kanan 总能帮大家修好。Kanan 是这片地区首屈一指的机械师；虽然她还年轻，但是娴熟的技艺加上慷慨的性格使得她平时总会收到人们的修理委托，据说就连那位遗世独立的魔王遇到了问题都得求助她。在帮人修理时， Kanan 会接触到千奇百怪的使用说明书。其中一些说明书有着不可思议的折叠结构，Kanan 为了理解机械的构造会在修理之前展开说明书，可在修好之后按照原来的折痕折回原状却比修理本身更费劲。

对于所有折痕互相平行的说明书，可以按照说明书上文字的阅读顺序从上到下给每条折痕分别编号 $1, 2, \cdots, N$，这 $N$ 条折痕将说明书分成了 $(N+1)$ 条纸带。每条折痕可能为两种形态之一：一种是垂直纸面向内凸出，对应将纸的上下两半向前对折；一种是垂直纸面向外凸出，对应将上下两半向后对折。根据折痕截面的形状，分别使用小写字母 `v` 表示向内凸出的折痕，`^` （ASCII 码为 $94$）表示向外凸出的折痕。假设所有纸带的宽度都是一样的，并且折纸的过程中说明书不发生形变，那么沿着一条折痕对折后两侧的纸能够重合，当且仅当两侧的折痕是相反的；即，如果沿着第 $k$ 条折痕折叠，那么对于所有满足 $1\le k-m<k+m\le N$ 的正整数 $m$，第 $(k-m)$ 条折痕和第 $(k+m)$ 条折痕的形态是相反的。例如，对于折痕依次为 `v^v^^^^v` 的说明书，可以沿其第 $7$ 条折痕进行折叠。根据定义可知，一张说明书总能沿着第一条或最后一条折痕进行折叠。折叠之后的说明书可以用被折叠的折痕两侧中，剩余折痕数量较多一侧的折痕表示，如 `v^v^^^^v` 沿着第 $7$ 条折痕折叠后得到 `v^v^^^`。如果被折叠的折痕两侧折痕数量相等，那么用哪一侧的折痕表示折叠后的纸都可以，因为折痕在三维空间中是旋转对称的。特别地，对只剩下一条折痕的说明书，即 `v` 或 `^` 进行折叠后，所有 $(N+1)$ 条纸带都重叠在一起，此时称这张说明书被折叠整齐。

虽然按顺序依次折叠每一条折痕，总能将说明书折叠整齐，但 Kanan 觉得这样并不美观。一种美观的折法应该尽量少折，并且每次折的时候折痕两侧应该尽可能的对称。定义一种折法的不对称程度为每次折叠时，被折叠的折痕两侧的折痕数量之差的总和。给出一张说明书的折痕，Kanan 想知道最少需要折多少次才能将这张说明书折叠整齐，以及所有折叠次数最少的折法中，不对称程度的最小值。

inputFormat:
输入的第一行包含一个正整数 $N$，表示折痕的条数。保证 $1\le N\le 5000$。

输入的第二行包含一个字符串 $s$，按顺序表示每条折痕。保证 $|s|=N$，且 $s$ 仅由 `v` 和 `^` 组成。

outputFormat: 输出仅一行，包括两个非负整数，分别表示最少的折叠次数和最小化折叠次数的前提下的最小不对称程度，两个数之间用一个空格隔开。

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

如果先沿着中间的折痕对折，那么两侧的纸恰好重合，此时再对折一次即可将说明书折叠整齐。

### 子任务

对于所有数据，保证 $1\le N\le 5000$，$|s|=N$ 且 $s$ 仅由 `v` 和 `^` 组成。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [USACO23DEC] Cowntact Tracing 2 B

description:
Farmer John 有 $N$ 头奶牛排成一列（$1 \leq N \leq 3\cdot 10^5$）。不幸的是，有一种疾病正在传播。

最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它左右两边的奶牛（如果这些奶牛存在的话）。一旦奶牛被感染，她就会持续处于感染状态。

经过一些晚上，Farmer John 意识到情况已经失控，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。请找出最少有多少头奶牛最初可能感染了这种疾病。

inputFormat:
第一行为一个整数 $N$，即 Farmer John 拥有的奶牛数量。

接下来一行，包含长度为 $N$ 的由 $1$ 和 $0$ 组成的位串。其中 $1$ 表示一头被感染的奶牛，$0$ 表示一头在经过若干晚之后仍未被感染的奶牛。

outputFormat: 输出一个整数，表示最少有多少头奶牛可能最初感染了这种疾病。

hint:
### 样例解释 1

假设只有中间的奶牛最初被感染。那么，奶牛们将按以下顺序被感染：

- 第 $0$ 晚：$00100$（第三只奶牛一开始被感染）
- 第 $1$ 晚：$01110$（第二和第四只奶牛现在被感染了）
- 第 $2$ 晚：$11111$（第一和第五只奶牛现在被感染了）
- 第 $3$ 晚：$11111$（所有的奶牛都已经被感染了，没有新的奶牛被感染）
- ……

经过两个或更多的晚上，奶牛们的状态即与输入的状态相符。还有许多其他的初始状态和夜晚数量可能导致了输入的状态，例如：

- 第 $0$ 晚：$10001$
- 第 $1$ 晚：$11011$
- 第 $2$ 晚：$11111$

或者：

- 第 $0$ 晚：$01001$
- 第 $1$ 晚：$11111$

或者：

- 第 $0$ 晚：$01000$
- 第 $1$ 晚：$11100$
- 第 $2$ 晚：$11110$
- 第 $3$ 晚：$11111$

所有这些初始状态中至少有一头奶牛被感染。

### 样例解释 2

唯一可能导致这个最终状态的初始状态和夜晚数是：没有经过任何夜晚，输入中的四头感染的奶牛都是从最开始就感染了这种疾病。

### 测试点性质

- 测试点 $3-7$ 满足 $N \le 1000$。
- 测试点 $8-12$ 没有额外限制。


title: [THUPC 2024 初赛] 转化

background: 小 E 在玩 Somzig 游戏的时候因为操作时间不够绷不住了，于是就有了这个题。

description: 小 E 有 $n$ 种颜色的球，其中第 $i$ 种有 $a_i$ 个。有两类工具，第一类可以把一个指定颜色的球变成一个**任意**颜色的球；第二类可以把一个指定颜色的球变成两个**这种**颜色的球。一个变化之后的球也可以通过工具产生新的变化。关于第 $i$ 种颜色的第一类工具有 $b_i$ 个，第二类工具有 $c_i$ 个。小 E 想知道，如果每一**个**工具最多只能使用一次，那么对于每种颜色 $i$，第 $i$ 种颜色的球最后最多能有多少个。以及，小 E 最后最多能有多少个球。

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

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

第三行 $n$ 个整数，其中第 $i$ 个表示 $b_i$。

第四行 $n$ 个整数，其中第 $i$ 个表示 $c_i$。

outputFormat:
第一行 $n$ 个整数，其中第 $i$ 个表示如果每个工具最多使用一次，那么小 E 最后第 $i$ 种颜色的球最多有多少个。

第二行一个整数，表示如果每个工具最多使用一次，那么小 E 最后最多能有多少个球。

hint:
### 子任务

保证 $1\le n \le 351493$。

保证 $0\le a_i,b_i,c_i\le 10^9$。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 机器人

description:
有 $n$ 个机器人围成一圈，编号按照逆时针顺序分别为 $0\sim n-1$。

每个机器人有两只手。编号为 $i$ 的机器人初始「左手」指向编号 $l_i$ 的机器人，「右手」指向编号 $r_i$ 的机器人。

所有的机器人内部都写有 $m$ 行「指令」，「指令」有以下这些形式：

### 指令

「指令」分为「基础指令」和「高级指令」两种。「高级指令」的功能会更复杂一些，但它们本质上没有多大区别。下面介绍这些「指令」的格式以及它们被「执行」时的效果。文中的“自己”一词均指拥有这条「指令」的机器人。

#### 基础指令

- `SLACKOFF`：**「摸鱼」**，即什么也不做。
- `MOVE h z`：将第 $h$ 只手向逆时针方向 **「移动」** $z$ 个机器人的位置。当 $h=0$ 时表示「左手」，当 $h=1$ 时表示「右手」，下同。
- `SWAP h x y`：将第 $h$ 只手指向的机器人的第 $x$ 行「指令」与自己的第 $y$ 行「指令」 **「对调」**。
- `MIRROR h x`：将第 $h$ 只手指向的机器人的第 $x$ 行「指令」**「镜像」** 取反，即将「指令」中的 $h$ 取反（$0$ 变成 $1$，$1$ 变成 $0$）。特殊地，它对 `SLACKOFF` 指令没有效果；而对 `TRIGGER` 指令，会直接修改「触发」时「执行」的「指令」中的 $h$。
- `REPLACE h x <COMMAND>`：将第 $h$ 只手指向的机器人的第 $x$ 行「指令」**「替换」** 为 `<COMMAND>`。其中 `<COMMAND>` 为一条完整的「指令」。

#### 高级指令

- `ACTIVATE h`：**「激活」** 第 $h$ 只手指向的机器人，即按顺序「执行」那个机器人的所有「指令」。前一行「指令」「执行」完毕之后才会「执行」后一行。注意在「执行」前面的「指令」时后面的「指令」可能会发生更改，这时需要「执行」更改后的「指令」。当那个机器人的所有「指令」「执行」完毕后，该「指令」才算「执行」完毕。

- `TRIGGER <COMMANDNAME>: <COMMAND>`：其中 `<COMMANDNAME>` 表示「指令」的名称，即一条「指令」中的第一个全大写单词；`<COMMAND>` 表示一条完整的「基础指令」。`TRIGGER` 指令不会被「执行」，即按顺序「执行」时会跳过该「指令」。但是，当一个 **其他** 机器人「执行」完一条「指令」之后，且「右手」指向自己的时候，自己最靠前的满足如下条件的 `TRIGGER` 指令（如果有）就会被 **「触发」**——「执行」一次对应的 `<COMMAND>`：

  - `<COMMANDNAME>` 不为 `TRIGGER` 时，刚刚「执行」完毕的「指令」为 `<COMMANDNAME>` 指令；
  - `<COMMANDNAME>` 为 `TRIGGER` 时，刚刚「执行」完毕的「指令」是 `TRIGGER` 指令被「触发」时「执行」的「指令」。

  「执行」完毕后会回到原来的「执行」顺序中。

你需要从 $0$ 号机器人开始按照编号顺序一圈又一圈地「激活」这些机器人，并输出「执行」的前 $k$ 条指令的有关信息。

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

接下来按照编号从小到大的顺序表示 $n$ 个机器人的信息。

对于每个机器人，第一行两个非负整数 $l_i,r_i$ 表示「左手」指向的机器人编号和「右手」指向的机器人编号。

接下来 $m$ 行，按顺序表示机器人的「指令」，「指令」的格式见题目描述。

outputFormat:
输出 $k$ 行，按顺序描述前 $k$ 条开始「执行」的指令的相关信息，在开始「执行」前输出，每条一行，格式如下：

- 「摸鱼」时输出 `Robot <id> slacks off.`。其中 `<id>` 为一个整数，表示「执行」当前「指令」的机器人编号，下同。
- 「移动」时输出 `Robot <id> moves its <side> hand towards Robot <id2>.`。其中 `<side>` 为 `left` 或 `right`，表示移动了哪只手（`left` 表示「左手」，`right` 表示「右手」）；`<id2>` 为一个整数，表示移动之后这只手指向的机器人的编号。
- 「对调」时输出 `Robot <id> swaps a line of command with Robot <id2>.`。其中 `<id2>` 为一个整数，表示与之「对调」「指令」的机器人编号。
- 「镜像」取反时输出 `Robot <id> modifies a line of command of Robot <id2>.`。其中 `<id2>` 为一个整数，表示被「镜像」取反「指令」的机器人编号。
- 「替换」时输出 `Robot <id> replaces a line of command of Robot <id2>.`。其中 `<id2>` 为一个整数，表示被「替换」「指令」的机器人编号。
- 「执行」 `ACTIVATE` 指令「激活」（区别于你的一圈又一圈的「激活」）时输出 `Robot <id> activates Robot <id2>.`。其中  `<id2>` 为一个整数，表示被「激活」的机器人编号。
- `TRIGGER` 指令由于不会被「执行」就不需要输出，但当它们被「触发」时，仍然需要按照上面的格式输出对应的「基础指令」被「执行」的信息。

samples:
2 2 5
0 0
MOVE 1 1
MOVE 0 1
0 1
TRIGGER MOVE: MOVE 0 1
SLACKOFF

samples:
Robot 0 moves its right hand towards Robot 1.
Robot 1 moves its left hand towards Robot 1.
Robot 0 moves its left hand towards Robot 1.
Robot 1 moves its left hand towards Robot 0.
Robot 1 slacks off.

samples:
2 2 4
0 1
ACTIVATE 1
SLACKOFF
0 1
SWAP 0 2 2
MIRROR 0 1

samples:
Robot 0 activates Robot 1.
Robot 1 swaps a line of command with Robot 0.
Robot 1 slacks off.
Robot 0 modifies a line of command of Robot 0.

samples:
3 2 6
1 2
ACTIVATE 0
ACTIVATE 0
2 1
SWAP 0 2 2
TRIGGER ACTIVATE: REPLACE 0 2 SLACKOFF
0 1
TRIGGER MIRROR: SLACKOFF
SLACKOFF

samples:
Robot 0 activates Robot 1.
Robot 1 swaps a line of command with Robot 2.
Robot 1 slacks off.
Robot 2 replaces a line of command of Robot 0.
Robot 0 slacks off.
Robot 1 swaps a line of command with Robot 2.

samples:
3 2 8
0 1
SLACKOFF
TRIGGER MOVE: SLACKOFF
1 2
TRIGGER TRIGGER: SLACKOFF
TRIGGER SLACKOFF: MOVE 0 1
2 0
TRIGGER SLACKOFF: MOVE 1 2
TRIGGER TRIGGER: MOVE 1 1

samples:
Robot 0 slacks off.
Robot 1 moves its left hand towards Robot 2.
Robot 2 moves its right hand towards Robot 1.
Robot 1 slacks off.
Robot 2 moves its right hand towards Robot 0.
Robot 0 slacks off.
Robot 1 slacks off.
Robot 2 moves its right hand towards Robot 2.

samples:
见附加文件的 5.in。
见附加文件的 5.ans。

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

`TRIGGER` 指令的「触发」时机是「执行」完毕之后。注意不能「触发」自己的 `TRIGGER` 指令。

### 样例 \#2 解释

注意在「执行」前面的「指令」时后面的「指令」可能会发生更改，这时需要「执行」更改后的「指令」。

### 样例 \#3 解释

`ACTIVATE` 指令「激活」另一个机器人时，当那个机器人的所有「指令」「执行」完毕后，该「指令」才算「执行」完毕。

### 样例 \#4 解释

只有自己最靠前的满足条件的 `TRIGGER` 指令才会被 **「触发」**。

### 样例 \#5 解释

无私的馈赠？有力的援助？

### 子任务

保证所有的指令的格式均正确。

保证输入文件的长度不超过 $5\mathtt{MB}$。

保证能够「执行」至少 $k$ 条「指令」。

保证 $2\le n\le 100$，$1\le m \le 10$，$1\le k \le 3\times 10^5$。

保证 $0\le l_i,r_i<n$。

保证 $0\le h \le 1$，$1\le x,y \le m$，$1\le z<n$。所有输入的数都是整数。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 采矿

background:
_“我已经买不起第二个机器人了。”_

_“那就雇点人来凑数吧。注意别给死里头。”_

description:
你是一个矿坑老板。

你的矿坑是二叉树形结构，有 $n$ 个节点。$1$ 号点为地面，对于所有的 $2\le i\le n$，$i$ 号节点与更浅层的 $f_i$ 号节点通过通道相连，其中 $f_i<i$，且相同的 $f_i$ 最多出现两次。矿坑的不同节点的产量和开采难度均不相同。对于 $i$ 号节点 $(2\le i\le n)$，如果派一个机器人开采，一单位时间内能有 $r_i$ 的产出；如果派一个人类开采，一单位时间内能有 $p_i$ 的产出。地面没有产出。

你有一个机器人，初始位于 $s$ 号节点。你的矿坑里初始没有人类工人。

所有通道与节点都十分狭窄，每个节点都只能容下一名工人（工人包括人类和机器人），每个通道也只能恰好容一名工人通过。在移动的任何时刻，只能有最多一名工人在通道中，其余工人都必须在节点上。

你现在有 $q$ 条计划需要按顺序执行。每个计划分为准备、执行、调整、开采四个阶段。

在准备阶段，人类可以在满足上述移动规则的前提下任意移动，但不能进入或离开矿坑（矿坑内的工人到达 $1$ 号节点不算离开矿坑），因为你在看着他们；移动的顺序和次数均没有限制。机器人不能移动。

在执行阶段，不同计划需要做的事情可能不同，共分为 $4$ 种：

1. 机器人只能沿通道向**更浅**的方向移动，且至少需要经过一条通道。人类不能移动。
2. 机器人只能沿通道向**更深**的方向移动，且至少需要经过一条通道。人类不能移动。
3. 使一名人类从 $1$ 号节点进入矿坑（这意味着该阶段开始时 $1$ 号节点上必须没有工人）。除此之外所有工人都不能移动。
4. 使一名人类从 $1$ 号节点移出矿坑（这意味着该阶段开始时 $1$ 号节点上必须有一名人类）。除此之外所有工人都不能移动。

在调整阶段，限制与准备阶段相同。人类可以在满足上述移动规则的前提下任意移动，但不能进入或离开矿坑；移动的顺序和次数均没有限制。机器人不能移动。

在开采阶段，所有的工人会采一单位时间的矿。所有有工人的非地面节点会根据位于该节点的工人种类计算产出。没有工人的节点没有产出。该计划的产出为所有节点的产出之和。

问按顺序执行完所有计划之后，你所有计划的产出之和最多可以达到多少。

inputFormat:
第一行三个正整数 $n,q,s$。

第二行 $n-1$ 个整数，其中第 $i$（$1\le i<n$，下同）个表示 $f_{i+1}$。

第三行 $n-1$ 个整数，其中第 $i$ 个表示 $r_{i+1}$。

第四行 $n-1$ 个整数，其中第 $i$ 个表示 $p_{i+1}$。

接下来 $q$ 行，每行一个整数表示计划的种类，其中第 $i$ 个整数表示第 $i$ 条计划：

- `1` 表示第一种计划：将机器人向更浅的方向移动；
- `2` 表示第二种计划：将机器人向更深的方向移动；
- `3` 表示第三种计划：将一名人类从 $1$ 号节点送入矿坑；
- `4` 表示第四种计划：将一名人类从 $1$ 号节点移出矿坑。

outputFormat: 如果无论如何你都无法完成你的计划，输出一行 `No solution.`。否则输出一行一个整数，表示你的产出之和的最大值。

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

一个最优解如下：（一些没有移动的阶段略过不提）

第一个计划的调整阶段：将刚送入 $1$ 号点的人类移动两次到 $5$ 号点。

第一个计划的开采阶段：机器人产出为 $7$，人类产出为 $6$。

第二个计划的调整阶段：将刚送入 $1$ 号点的人类移动到 $2$ 号点。

第二个计划的开采阶段：机器人产出为 $7$，人类产出为 $4+6=10$。

第三个计划的执行阶段：将机器人移动至 $1$ 号点。

第三个计划的调整阶段：将一名人类从 $5$ 号点移动至 $4$ 号点。

第三个计划的开采阶段：机器人产出为 $0$，人类产出为 $4+8=12$。

第四个计划的准备阶段：将一名人类从 $4$ 号点移动至 $5$ 号点。

第四个计划的执行阶段：将机器人移动至 $3$ 号点。

第四个计划的开采阶段：机器人产出为 $9$，人类产出为 $4+6=10$。

第五个计划的执行阶段：将机器人移动至 $4$ 号点。

第五个计划的开采阶段：机器人产出为 $7$，人类产出为 $4+6=10$。

第六个计划的准备阶段：将一名人类从 $2$ 号点移动至 $1$ 号点。

第六个计划的开采阶段：机器人产出为 $7$，人类产出为 $6$。

总的产出为 $7+6+7+10+0+12+9+10+7+10+7+6=91$。

### 子任务

保证 $2\le n\le 301$，$1\le q \le 600$，$1\le s\le n$。

保证 $1\le f_i < i$，$0\le r_i,p_i \le 10^9$。

保证相同的 $f_i$ 最多出现两次。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 二进制

description:
今天也是喜欢二进制串的一天，小 F 开始玩二进制串的游戏。

小 F 给出了一个这里有一个长为 $n$ 的二进制串 $s$，下标从 $1$ 到 $n$，且 $\forall i\in[1,n],s_i\in \{0,1\}$，他想要删除若干二进制子串。

具体的，小 F 做出了 $n$ 次尝试。

在第 $i\in[1,n]$ 次尝试中，他会先写出正整数 $i$ 的二进制串表示 $t$（无前导零，左侧为高位，例如 $10$ 可以写为 $1010$）。

随后找到这个二进制表示 $t$ 在 $s$ 中从左到右 **第一次** 出现的位置，并删除这个串。

注意，删除后左右部分的串会拼接在一起 **形成一个新的串**，请注意新串下标的改变。

若当前 $t$ 不在 $s$ 中存在，则小 F 对串 $s$ 不作出改变。

你需要回答每一次尝试中，$t$ 在 $s$ 中第一次出现的位置的左端点以及 $t$ 在 $s$ 中出现了多少次。

定义两次出现不同当且仅当出现的位置的左端点不同。

请注意输入输出效率。

inputFormat:
第一行一个正整数 $n$（$1\leq n\leq 1000000$）。

第二行一个长度为 $n$ 的字符串 $s$。保证 $\forall i\in[1,n], s_i \in \{0, 1\}$。

outputFormat:
输出共 $n$ 行，每行两个整数，第 $i$ 行表示小 F 进行第 $i$ 次尝试时开头端点的位置以及相应的字符串出现的次数。

若这次尝试失败，则当前行输出 $-1\ 0$。

hint:
### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 分治乘法

description:
小艾想要挑战分治乘法。TA 将策略抽象成了如下问题：

现在给定一个目标集合 $T$，该集合是 $\{1,\dots,n\}$ 的一个子集（$1\leq n\leq 5\times 10^5$）。你需要通过一系列操作构造一些集合最后得到 $T$，具体来说有以下三种操作：

- 创造一个大小为一的集合 $|S|=1$。
- 将已经被构造出的两个不交集合 $A, B$ 并起来，得到 $A\cup B$。
- 将已经被构造出的一个集合 $A$ 进行平移，也即 $A+x = \{ a+x : a\in A \}$。

一个已经被构造出的集合可以在之后被使用多次。同时你需要保证操作过程中出现的所有集合都是 $\{1,\dots,n\}$ 的子集。

你的代价是构造出的所有集合的大小之和，你不需要最小化代价，只需要让代价控制不超过 $5\times 10^6$ 即可。你用的操作数量也不应超过 $10^6$。

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

接下来一行输入一个 `01` 串，长度为 $n$，第 $x$ 位为 `1` 表示 $x\in T$，否则 $x\notin T$，保证 $T$ 非空。

outputFormat:
第一行输出一个正整数 $m$ 表示你使用的操作数量。

接下来 $m$ 行，每行描述一个操作，设第 $i$ 次操作得到的集合为 $T_i$：

- `1 x` 表示创造一个大小为一的集合 $\{x\}$。
- `2 x y` 表示将不交集合 $T_x, T_y$ 并起来。
- `3 x y` 表示将已经被构造出的一个集合进行平移，也即 $T_x+y$。

你需要保证所有操作满足题目要求，并且最后一次操作产生的集合是 $T$。

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

- 第一次操作：创造集合 $T_1=\{1\}$。
- 第二次操作：创造集合 $T_2=\{4\}$。
- 第三次操作：将 $T_1, T_2$ 并起来，得到 $T_3=\{1,4\}$。
- 第四次操作：将 $T_3$ 平移 $1$，得到 $T_4=\{2,5\}$。
- 第五次操作：将 $T_3, T_4$ 并起来，得到 $T_5=\{1,2,4,5\}$。这就得到了 $T$。

这个方案的总代价是 $1 + 1 + 2 + 2 + 4 = 10$。

### 提示

如果你的复杂度是好的，请相信常数。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 套娃

description:
我们定义一个集合的 $\operatorname{mex}$ 是最小的不在 $S$ 中的非负整数。

给定一个序列 $a_1,\dots,a_n$，对于每个 $1\leq k\leq n$，我们按照如下方式定义 $b_k$：

- 对于 $a$ 的所有长为 $k$ 的子区间，求出这个子区间构成的数集的 $\operatorname{mex}$。
- 对于求出的所有 $\operatorname{mex}$，求出这个数集自己的 $\operatorname{mex}$，记为 $b_k$。

请你求出序列 $b$。

inputFormat:
第一行输入一个正整数 $n$（$1\leq n\leq 10^5$）。

第二行输入 $n$ 个整数 $a_1,\dots,a_n$（$0\leq a_i\leq n$）。

outputFormat: 一行输出 $n$ 个整数 $b_1,\dots,b_n$。


title: [THUPC 2024 初赛] 三步棋

background:
昼短夜长冬至近。江冽漆黑，但见东云粉。窗外惺忪鸥鹭阵，室中香漫晨炊奋。

朝肄暮劳催彼盹。宵寂观书，灯烬方安寝。请替君劳分重任，逍遥共舞生辰顺。

description:
K 家里有一条不成文的规矩。如果家里只有 K 和 H 两个人，那么两个人会通过一种叫作“三步棋”的游戏来决定谁做饭。三步棋的规则与五子棋有一些相似之处。众所周知，五子棋是一种先连出五枚己方棋子者获胜的游戏。与五子棋相同的是，三步棋中双方也轮流在网格状的棋盘上摆放棋子，并根据是否连成指定的图案决定胜负。与五子棋不同的是：

1. 三步棋不区分双方的棋子，即可以认为双方执同色棋子进行游戏；

2. 在判定时，指定的图案不能旋转；

3. 如果连成指定的图案时，棋盘上的棋子数量恰好为 $3$ 的倍数，则连成指定的图案的一方获胜，否则判定该方负（即对方获胜）。

例如，如果指定的图案为

```
.o
oo
```

且当前盘面为

```
o..o.
o.o..
oo...
o.o..
o..o.
```

时，认为没有连成给定的折线形图案，其中 `o` 表示棋子，`.` 表示空格；但若接下来在第二行第二列放一枚棋子，则连成了给定的图案，对应的棋子使用 `@` 表示：

```
o..o.
o@o..
@@...
o.o..
o..o.
```

此时盘面上恰有 $11$ 枚棋子，而 $11$ 不是 $3$ 的倍数，所以判定放这枚棋子的玩家，也即先手输掉本局。

在 K 家，为了节约时间，通常使用 $5\times 5$ 的初始为空的棋盘进行三步棋。同时，每次也只会随机选择一个由不超过 $4$ 枚棋子组成的四连通图案。显然三步棋不存在平局，所以 K 和 H 约定由输的一方负责做饭。K 想知道，如果自己和 H 都足够聪明，那么以选中的图案进行的三步棋游戏是否为**先手必胜**；因为如果她更容易赢，她就要偷偷地给自己的妹妹放水。

inputFormat:
输入文件包含多组数据。

输入的第一行包含一个正整数 $T$，表示数据组数。保证 $1\le T\le 200$。

对于每组数据，输入包含 $5$ 行，每行包括一个长度为 $5$ 且仅含 `.` 及 `o` 的字符串，表示指定的图案。保证每组数据中 `o` 至少出现一次，且所有 `o` 组成一个大小不超过 $4$ 的四连通块。

outputFormat: 对于每组数据输出一行。如果输入的图案为**先手必胜**，则输出 `Far`，否则输出 `Away`。

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

该样例包含三组数据。

第一组数据输入的图案为 $1$ 行 $2$ 列的 `oo`。显然，无论先手将棋子放在棋盘上的哪个位置，后手都只有两种策略：

- 和先手的棋子连成 `oo`，此时棋盘上只有 $2$ 枚棋子，故后手立即输掉游戏；

- 不和先手的棋子连成 `oo`，但是接下来轮到先手时，先手可以任意连成 `oo`，此时棋盘上恰有 $3$ 枚棋子，故先手取胜。

无论是哪种策略，后手都无法取胜，故对于 `oo` 而言**先手必胜**。

第二组数据输入的图案为 $2$ 行 $1$ 列的图案，与 `oo` 同理，可知为**先手必胜**。

第三组数据输入的图案为 $1$ 行 $3$ 列的 `ooo`，可以证明为先手必败。

### 子任务

保证 $1\le T\le 200$。对于每组数据，保证输入的 $5\times 5$ 的由 `.` 和 `o` 组成的字符矩阵中至少含有一个 `o`，且所有 `o` 组成一个大小不超过 $4$ 的四连通块。

### 题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。


title: [THUPC 2024 初赛] 勇闯末日塔

background:
安宁顷刻今将逝，末日黑云伺隙来。宿命无情何所惧？越其止境冀花开。

为了执行毁灭世界的疯狂计划，一位占用了已死之人躯壳的神秘男子在这颗蓝色的星球上创造出了无数末日塔。这些末日塔会散发出浓密的以太射线，对末日塔附近的几乎所有生物进行精神控制，只有受到特殊加护的人才能免受以太射线控制。

一些受到加护的义勇队对这些末日塔进行了调查，其结果显示：这些末日塔组成了复杂的以太传输网络，持续不断地从大地中吸收以太，并将以太传输到位于帝国的中枢塔。

一队持有特殊加护的英雄决定闯入其中一些末日塔，以期彻底调查并尝试破坏这些末日塔。英雄们破坏掉进入的末日塔后，以太传输网络就会受到影响，因此大家希望选择一些末日塔，将其破坏后能使得网络的最大传输容量降到最低。

作为勇闯末日塔小队的先锋，你再次阅读了小队目前所掌握的所有信息。这次大胆的行动计划最终能否拯救这个世界，眼下恐怕谁都无法事先料定。但为了这颗星球的未来，我们只能放手一搏。

description:
星球的表面是一个中心位于 $(0, 0, 0)$，半径为 $R$ 的完美球面。星球表面上共有 $N$ 座末日塔，这些令人毛骨悚然的塔构成了以太传输网络的所有节点。

- 末日塔的高度远小于星球半径，因此我们认为第 $i (1 \le i \le N)$ 座塔是球面上的一个点 $\left(x_i, y_i, z_i\right)$。第 $i$ 座塔的以太传输效率为 $q_i$。
- 保证 $N$ 座末日塔的位置两两不同。在这 $N$ 座末日塔中，$s$ 号塔是以太吸收点，$t$ 号塔是位于帝国的中枢塔；这两座塔的以太浓度显著高于其它的末日塔，因此只能闯入这两座塔之外的末日塔。

$N$ 座末日塔之间共有 $M$ 条传输通道。第 $j (1 \le j \le M)$ 条传输通道连接 $u_j, v_j$ 两座末日塔，让它们可以互相传输以太。

- 传输通道是双向的，但单位时间内以太的流向必须是单向的。
- 为了节省不必要的成本，传输通道的两端不会连接相同的塔，也不会有两条传输通道连接相同的末日塔对。
- 为了降低传输距离，第 $i$ 条传输通道沿着 $u_j$ 和 $v_j$ 所在的大圆的劣弧铺设，故其**长度** $r_j$ 为两座末日塔在星球表面的球面距离。为了避免传输通道的互相干扰，**对于任意一条传输通道所对应的劣弧，其他传输通道所对应的劣弧只会在该劣弧的两端点上与该劣弧相交**。保证由同一条传输通道相连的两座末日塔的位置不是对跖点关系。
  - 如果不知道大圆、劣弧、球面距离和对跖点是什么，可以参考题面最后的提示部分。

受到传输效率和通道长度的影响，每条传输通道有各自传输以太的容量上限。

- 具体而言，每个单位时间内，第 $j$ 条传输通道的**容量上限**为 $\frac{Kq_{u_j} q_{v_j}}{r_j^2}$，其中 $K$ 是给定的常数，$q_{u_j}, q_{v_j}$ 为该传输通道两端的塔的传输效率，$r_j$ 为这条传输通道的长度。

整张以太传输网络需要将 $s$ 号塔吸收的以太沿着传输通道传输到 $t$ 号塔，并使得单位时间内的以太传输量最大。为此，传输网络会自动确定一个以太传输方案，在满足所有传输通道容量上限的前提下，最大化这一传输量。

- 换句话说，如果将末日塔看作图上的点，传输通道看作边，而传输通道的容量上限对应每条边的容量，那么以太的传输方案应该恰好为 $s$ 到 $t$ 的最大流。

虽然没有任何人能保证闯入末日塔之后就一定能将其破坏，但作为勇闯末日塔小队的先锋，你还是想在出发之前计算一下，如果成功破坏了所有将要闯入的末日塔，传输网络单位时间的最大传输量将会降至多少。

- 如果成功破坏了选择的末日塔，与其相连的所有传输通道的容量都将降至 $0$，其余传输通道容量不发生变化；此时传输网络会自动调节至一个在新的网络中传输量最大的新方案。
- 在最理想的情况下，小队将有机会调查并破坏 $L$ 座末日塔。因此，需要事先选择 $L$ 座末日塔（均不能是 $s$ 或 $t$），使得当这 $L$ 座末日塔都被成功破坏时，传输网络的新的传输方案的以太传输量尽可能地小。

inputFormat:
输入的第一行包括五个正整数 $N, M, L, s, t$（$3\le N\le 500$，$2\le M\le \frac{N(N-1)}{2}$，$1\le L\le \min\{8,N-2\}$，$1\le s, t\le N$），分别表示该传输网络包含的末日塔数量，传输通道数量，有机会闯入的末日塔数量，最主要的以太吸收塔的编号和中枢塔的编号。

输入的第二行包括两个实数 $R, K$（$1\le R\le 10^3$，$1\le K\le 10^3$），分别表示星球的半径和计算以太容量时用到的常数。

接下来 $N$ 行，每行三个实数 $a_i, b_i, q_i$（$0\le a_i\le 1$，$0\le b_i< 2$，$1\le q_i \le 10^3$），描述第 $i$ 座末日塔的信息，其中 $q_i$ 表示第 $i$ 座末日塔的传输能力， $a_i$ 和 $b_i$ 共同描述末日塔的位置：令 $\theta_i = \pi a_i$，$\varphi_i = \pi b_i$（如果你习惯使用角度制而不是弧度制，可以将 $\pi$ 改为 $180^\circ$），则 $\left(x_i, y_i, z_i\right) = \left(R \sin\theta_i \cos\varphi_i, R\sin\theta_i \sin\varphi_i, R\cos\theta_i\right)$。保证末日塔的位置各不相同。

最后 $M$ 行，每行两个正整数 $u_i, v_i$（$1\le u_i, v_i\le N$），表示一条传输通道连接的两座末日塔的编号。保证同一条传输通道连接的两座末日塔不相同且不互为对跖点，没有两条传输通道连接的是相同的末日塔对，且传输网络是连通的。

保证输入的所有实数保留到小数点后第 $4$ 位。

outputFormat: 输出一个实数，表示如果成功破坏了将要闯入的末日塔，新的传输网络单位时间的最大传输量。当你的输出与标准输出的相对误差或绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。

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

以太传输网络如下图所示。图中蓝色球面即为星球表面；紫色点为各末日塔，其中 $P_i$ 对应输入的第 $i$ 座末日塔；黄色的线表示各传输通道。

![样例 1 示意图](https://cdn.luogu.com.cn/upload/image_hosting/4bynt5dl.png)

原来的传输网络单位时间最大传输量为 $188/\pi^2$。破坏第 $2$ 个末日塔或第 $5$ 个末日塔都能使新的传输网络单位时间的最大传输量降至 $80/\pi^2$，而破坏第 $3$ 个末日塔或第 $4$ 个末日塔只能使新的传输网络单位时间的最大传输量降至 $94/\pi^2$，所以应该选择第 $2$ 个或第 $5$ 个末日塔尝试破坏。


title: [THUPC 2024 初赛] 你说得对，但是 AIGC

background: 你说得对，但是**本题不接受提供 hack 数据。**

description:
你说得对，但是众所周知 AIGC 是当下计算机领域最热门的方向之一，算协的几名成员也对此很有兴趣，经过长时间的奋战，终于研发出了一款全新的语言大模型——ChatSAA。

你说得对，但是当模型即将发布之时，开发团队忽然发现模型存在重大问题——由于开发团队的某名成员沉迷于一款**中文二字英文七字的游戏（见样例）**，导致训练模型时使用的语料库被莫名其妙地污染了，这使得模型生成的句子全都带有一个相同的前缀。

你说得对，但是紧急更换语料库重新训练显然已经来不及了，无奈开发团队只能在文档中注明：本模型的最大**特性（而非 bug）**在于生成文本的**前 19 个字符**，这既是模型独特的防伪标记，也充分彰显了算协团队的人文情怀和文化素养。

你说得对，但是一个微不足道的问题在于：这会让人们一眼就能分辨出哪些句子是由 AI 生成的，这会对那些打算用 AI 来写作业的同学很不友好。

你说得对，但是现在你手里有一些句子，这些句子有的是由 ChatSAA 生成的，有的是人类写的（假设人类没有刻意模仿 ChatSAA 的生成特性），你需要写一个程序来辨别二者。

inputFormat: 你说得对，但是你的程序应当输入一行，一个字符串 $s$ 表示需要判断的句子，满足 $|s| \le 200$，且 $s$ 由包括空格在内的 ASCII 可见字符（即 ASCII 码在 $32\sim 126$ 的字符）组成。

outputFormat: 你说得对，但是你的程序应当输出一行，一个字符串表示判断结果，如果这句话是 AI 生成的，输出 `AI`，否则输出 `Human`。

samples: You are right, but "Sao Lei (Winmine)" is a game whose Chinese name contains two characters while English name contains seven.

samples: Ni shuo de dui, dan shi zhe ju hua bu shi yi "You are right, but " kai tou de.

samples: You are wrong. Here is why. The English name of game "G****** I*****" contains 14 characters (including a space), not 7.

hint:
### 样例 \#1 解释
你说得对，但是扫雷（Winmine）是一款中文二字英文七字的游戏。

### 提示

你说得对，但是如果我说这道题的题面是 AI 生成的，阁下又该如何应对？


title: [USACO23DEC] Farmer John Actually Farms B

description:
Farmer John 在他的农场上种植了 $N$（$1 \leq N \leq 2\cdot 10^5$） 株芦笋！然而，其中有一些植物存在基因差异，长得比其他植物快。第 $i$ 株植物的初始高度为 $h_i$ 英寸，之后每天，第 $i$ 株植物长高 $a_i$ 英寸。

FJ 更加钟爱其中的一些植物。他将给你一组由不同整数组成的数组 $t_1,\dots,t_N$，这个数组包含 $0$ 到 $N-1$ 的全部整数。他希望恰好有 $t_i$ 株植物比第 $i$ 株植物高。找到最少要经过多少天，才能满足 FJ 的要求，或者报告这个要求是不可能满足的。

inputFormat:
**每个测试点中包含多组测试数据。**

第一行为一个整数 $T$，代表测试数据组数（$1 \leq T \leq 10$）。

对于每一组测试数据，第一行一个整数 $N$（$1 \leq N \leq 2\cdot 10^5$），表示植物数量。

第二行包含 $N$ 个整数 $h_i$（$1 \leq h_i \leq 10^9$），表示第 $i$ 株植物的初始高度。

第三行包含 $N$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$），表示第 $i$ 株植物每天增长的高度。

第四行包含 $N$ 个不同的整数 $t_i$，表示 FJ 给你的数组。

保证所有测试数据的 $N$ 的和不超过 $2\cdot 10^5$。

outputFormat:
输出 $T$ 行，每行表示一组测试数据的答案。如果要求不可能满足，输出 $-1$。

请注意，由于这个问题涉及的整数大小较大，可能需要使用 64 位整数数据类型（例如，在 C/C++ 中使用 `long long` 类型）。

hint:
### 样例解释 1

在第一组样例中，有 $6$ 组测试数据。

在第一组测试数据中，只有一株植物，所以要求在第 $0$ 天就已经满足。

在第二组测试数据中，需要让第一株植物比第二株植物矮。第   $1$ 天后，它们的高度为 $15,13$；第 $2$ 天后，它们的高度均为 $23$；第 $3$ 天后，它们的高度为 $31,33$，这是满足要求的第一天。

第三组和第四组测试数据与第二组类似。

在第五组测试数据中，两株植物的初始高度均为 $7$ 英寸，且每天均增长 $8$ 英寸，所以它们的高度永远相同。因此，条件永远无法满足。

在第六组测试数据中，初始高度不满足要求且增长速度均相同，所以条件永远无法满足。

### 样例解释 2

在第二组样例中，有 $2$ 组测试数据。

在第一组测试数据中，第 $4$ 天后的最终高度为 $19, 20, 21, 18, 16$。

在第二组测试数据中，第 $7$ 天后的最终高度为 $25, 17, 19, 35, 36$。

### 测试点性质

- 测试点 $3$ 满足 $N \le 2$。
- 测试点 $4-5$ 满足 $N \le 50$，$a_i, h_i \le 10^3$。
- 测试点 $6-8$ 满足 $N \le 10^3$。
- 测试点 $9-13$ 没有额外限制。


title: [USACO23DEC] Bovine Acrobatics S

description:
Farmer John 决定让他的奶牛表演杂技！首先，FJ 为他的奶牛称重，发现她们有 $N$（$1\le N\le 2\times 10^5$）个不同的体重。具体来说，对于全部的 $i\in [1,N]$，有 $a_i$ 只奶牛的体重为 $w_i$ 单位（$1\le a_i\le 10^9, 1\le w_i\le 10^9$）。

他最出名的节目需要奶牛叠成**平衡的奶牛塔**。一座**奶牛塔**是一些奶牛，每只奶牛站在下一只奶牛身上。一座奶牛塔是**平衡的**，当且仅当每一只被踩着的奶牛，都比**直接**踩在它身上的那只奶牛重至少 $K$（$1\le K\le 10^9$）单位。每只奶牛都可以成为奶牛塔的一部分。

如果 FJ 想要创造最多 $M$（$1 \le M \le 10^9$）座奶牛塔，最多有多少只奶牛可以成为奶牛塔的一部分？

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

接下来 $N$ 行，每行包含两个空格分隔的整数 $w_i$ 和 $a_i$。保证所有的 $w_i$ 是不同的。

outputFormat: 输出当 FJ 采用最佳方案时，奶牛塔中奶牛的最大数目。

hint:
### 样例解释 1

FJ 可以用体重为 $5,7,9$ 的奶牛创造四座平衡的奶牛塔，再用体重为 $5,7$ 的奶牛创造另一座。

### 样例解释 2

FJ 可以用体重为 $5,9$ 的奶牛创造四座平衡的奶牛塔，再用体重为 $7$ 的一只奶牛创造另一座。或者，他可以用体重为 $5,9$ 的奶牛创造四座平衡的奶牛塔，再用体重为 $5$ 的一只奶牛创造另一座。

### 测试点性质

- 测试点 $3-5$ 满足 $M \le 5000$ 且奶牛的总数不超过 $5000$。
- 测试点 $6-11$ 满足奶牛的总数不超过 $2\cdot 10^5$。
- 测试点 $12-17$ 没有额外限制。


title: [USACO23DEC] Cycle Correspondence S

description:
Farmer John 有 $N$（$3 \le N \le 5\cdot 10^5$）座谷仓，其中 $K$ 对不同的谷仓连接在一起。

一开始，Annabelle 为每座谷仓分配了一个 $[1,N]$ 范围内的整数编号，并发现编号为 $a_1,\dots,a_K$ 的谷仓按照顺序形成了一个环形连接。换句话说，对于所有的 $1 \le i < K$，谷仓 $a_i$ 和 $a_{i+1}$ 相连，谷仓 $a_K$ 与 $a_1$ 亦相连。所有的 $a_i$ 不相同。

然后，Bessie 也为每个谷仓分配了一个 $[1,N]$ 范围内的整数编号，并发现编号为 $b_1,\dots,b_K$ 也按照顺序形成了一个环形链接。所有的 $b_i$ 不相同。

一些（可能没有或全部）谷仓被 Annabelle 和 Bessie 分配了相同的编号。计算最多有多少个这样的谷仓。

inputFormat:
第一行包含 $N$ 和 $K$。

接下来一行包含 $a_1,\dots,a_K$。

接下来一行包含 $b_1,\dots,b_K$。

outputFormat: 分配了相同编号谷仓的最大数量。

hint:
### 样例解释 1

Annabelle 和 Bessie 可以为每个谷仓分配相同的编号。

### 样例解释 2

Annabelle 和 Bessie 无法为任何谷仓分配相同的编号。

### 样例解释 3

Annabelle 和 Bessie 可以分配编号 $2,3,4,6$ 给相同的谷仓。

### 测试点性质

- 测试点 $4-5$ 满足 $N \le 8$。
- 测试点 $6-8$ 满足 $N \le 5000$。
- 测试点 $9-15$ 没有额外限制。


title: [USACO23DEC] Target Practice S

description:
Bessie 是一只仿生牛。在一条数轴上，她正尝试命中 $T$（$1 \leq T \leq 10^5$）个位于不同位置的靶子。Bessie 在位置 $0$ 开始行动，并遵循一个长度为 $C$（$1 \leq C \leq 10^5$）的命令序列，序列由 `L`、`F` 和 `R` 组成：

- `L`：Bessie 向左移动一个单位距离。
- `R`：Bessie 向右移动一个单位距离。
- `F`：Bessie 开枪。如果有一个靶子在 Bessies 当前的位置，这个靶子将被命中并摧毁。它不可以再次被命中。

如果在 Bessie 开始前，你被允许修改序列中的至多一条命令，Bessie 最多可以命中多少靶子？

inputFormat:
第一行包含 $T$ 和 $C$。

下一行包含 $T$ 个靶子的位置，均为 $[-C,C]$ 范围内的不同整数。

下一行包含长度为 $C$ 的命令序列，仅包含字符 `F`、`L` 和 `R`.

outputFormat: 输出修改至多一个命令后，Bessie 可以命中的靶子的最大数量。


title: [USACO23DEC] Flight Routes G

description:
Bessie 最近发现她最喜欢的摇滚艺术家 Elsie Swift 正在表演她最新的“时代之旅”音乐会！不幸的是，票卖光的太快了，所以 Bessie 考虑飞往另一个城市参加音乐会。“时代之旅”将在编号为 $1\dots N$ 的 $N$（$2 \le N \le 750$）座城市上演，每对满足 $i<j$ 的城市对 $(i,j)$ 都可能存在从 $i$ 到 $j$ 的一条**单向直飞航班**。

从城市 $a$ 到城市 $b$ 的一条**航线**是一个包含 $k\ge 2$ 座城市的序列 $a=c_1<c_2<\cdots<c_k=b$，使得对于所有的 $1\le i< k$，城市 $c_{i}$ 到城市 $c_{i+1}$ 有**单向直飞航班**。对于所有满足 $i<j$ 的城市对 $(i,j)$，你将被告知它们之间航线数目的奇偶性（$0$ 代表偶数，$1$ 代表奇数）。

在计划她的旅行行程时，Bessie 分心了。现在她想知道，有多少对城市间有**单向直飞航班**。可以证明答案是唯一的。

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

接下来 $N-1$ 行，第 $i$ 行包含 $N-i$ 个整数。第 $i$ 行的第 $j$ 个整数表示从城市 $i$ 到城市 $i+j$ 的航线数目的奇偶性。

outputFormat: 输出有单向直飞航班的城市对数。

hint:
### 样例解释 1

有两条单向直飞航班：$1\rightarrow 2$ 和 $2\rightarrow 3$。有城市 $1,2$ 之间、$2,3$ 之间，仅包含一条单向直飞航班的航线各一条。还有城市 $1,3$ 之间的航线一条（$1\rightarrow 2\rightarrow 3$）。

### 样例解释 2

有六条单向直飞航班：$1\rightarrow 2$，$1 \rightarrow 4$，$1\rightarrow 5$，$2\rightarrow 3$，$3\rightarrow 5$，$4\rightarrow 5$。这导致的航线数如下表所示：

| 出发地\目的地 | 1 | 2 | 3 | 4 | 5 |
| :-: | :-: | :-: | :-: | :-:|:-:|
| 1 | 0 | 1 | 1 | 1 | 3 |
| 2 | 0 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 |

这与输入是相符的。

### 测试点性质

- 测试点 $3-4$ 满足 $N \le 6$。
- 测试点 $5-12$ 满足 $N \le 100$。
- 测试点 $13-22$ 没有额外限制。


title: [USACO23DEC] Minimum Longest Trip G

description:
Bessie 正在奶牛大陆上旅行。奶牛大陆由从 $1$ 到 $N$ 编号的 $N$（$2 \le N \le 2\cdot 10^5$）座城市和 $M$（$1 \le M \le 4\cdot 10^5$）条单向道路组成。第 $i$ 条路从城市 $a_i$ 通向城市 $b_i$，标签为 $l_i$。

由城市 $x_0$ 开始的长度为 $k$ 的旅程被定义为一个城市序列 $x_0,x_1,\ldots,x_k$，对于所有的 $0 \le i < k$，存在由城市 $x_i$ 到 $x_{i+1}$ 的路。保证在奶牛大路上不存在长度无限的旅程，不存在两条路连接一对相同的城市。

对于每座城市，Bessie 想知道从它开始的最长旅程。对于一些城市，从它们开始的最长旅程不唯一，Bessie 将选择其中道路标签序列字典序更小的旅程。一个序列比等长的另一个序列字典序更小，当且仅当在它们不同的第一个位置，前者比后者的元素更小。

输出 Bessie 在每座城市选择的旅途的长度和道路标签之和。

inputFormat:
第一行包含 $N$ 和 $M$。

接下来 $M$ 行，每行三个整数 $a_i,b_i,l_i$，代表一条由 $a_i$ 到 $b_i$，标签为 $l_i$ 的单向道路。

outputFormat: 输出 $N$ 行，第 $i$ 行包含由空格分隔的两个整数，表示 Bessie 选择的从城市 $i$ 开始的旅程的长度和道路标签之和。

hint:
### 样例解释 2

在下面的解释中，我们用 $a_i\xrightarrow{l_i} b_i$ 表示由城市 $a_i$ 通往 $b_i$，标签为 $l_i$ 的单向道路。

从城市 $4$ 出发有多条旅程，包含 $4\xrightarrow{4} 3\xrightarrow 5 1$，$4\xrightarrow 1 1$ 和 $4\xrightarrow 2 2\xrightarrow{10} 1$。在这些旅程中，$4\xrightarrow{4} 3\xrightarrow 5 1$ 和 $4\xrightarrow 2 2\xrightarrow{10} 1$ 是最长的。它们的长度均为 $2$，道路标签序列分别为 $[4,5]$ 和 $[2,10]$。$[2,10]$ 是字典序更小的那一个，它的和为 $12$。

### 测试点性质

- 测试点 $5-6$ 满足所有道路的标签相同。
- 测试点 $7-8$ 满足所有道路的标签不相同。
- 测试点 $9-10$ 满足 $N,M \le 5000$。
- 测试点 $11-20$ 没有额外限制。


title: [集训队互测 2022] 线段树

background: 请注意：**本题不是线段树模板题**。

description:
给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots a_n$。你需要进行共 $q$ 次下面两种操作：

- `1 l r`：将 $a_{l\sim r}$ 替换为它的异或差分。形式化地说，令 $b_i := a_i \text{ xor } a_{i-1}$（$l<i\leq r$），然后对于每个 $l<i\leq r$，将 $a_i$ 替换为 $b_i$。

- `2 pos`：查询 $a_{pos}$ 的值。

操作执行完后，你还需要回答最终的 $a$ 序列。

inputFormat:
第一行包含一个整数 $T$，表示该数据满足第 $T$ 个子任务的限制。

第二行包含两个整数 $n,q$，分别表示序列的长度和操作的个数。

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

接下来 $q$ 行，每行若干个数，表示一个操作。若操作为第一种操作，则此行包含三个数 `1 l r` 。若操作为第二种操作，则此行包含两个数 `2 pos`。

outputFormat:
设共有 $q_2$ 个第二种操作，则输出共包含 $q_2+n$ 行。

前 $q_2$ 行，每行输出一个整数，表示该操作的答案。

接下来 $n$ 行，每行输出一个整数，表示最终的 $a$
 序列。


title: [USACO23DEC] Haybale Distribution G

description:
Farmer John 正在农场上分发干草堆。

Farmer John 的农场上有 $N$（$1 \le N \le 2\cdot 10^5$）座谷仓，分别位于数轴上的整点 $x_1,\ldots,x_N$（$0 \le x_i \le 10^6$）。Farmer John 正计划将 $N$ 车干草堆运输到整点 $y$（$0 \le y \le 10^6$），然后为每一座谷仓运输一车干草堆。

不幸的是，Farmer John 的运输系统浪费了很多干草堆。具体来说，给出一些 $a_i,b_i$（$1 \le a_i,b_i \le 10^6$），每车干草堆每向左移动一单位距离，$a_i$ 堆干草堆会被浪费；每车干草堆每向右移动一单位距离，$b_i$ 堆干草堆会被浪费。形式化地，一车干草堆从整点 $y$ 运动到位于 $x$ 的谷仓，被浪费的干草堆堆数如下：

$$\begin{cases}a_i\cdot (y-x) & \text{if} \ y>x \\ b_i\cdot(x-y)&\text{if}\ x>y\end{cases}$$

给出 $Q$（$1 \le Q \le 2 \cdot 10^5$）组相互独立的询问，每组询问给出一组 $(a_i,b_i)$ 的值，帮助 Farmer John 计算当按照最佳方案选择 $y$，最少有多少堆干草堆被浪费。

inputFormat:
第一行包含 $N$。

接下来一行包含 $x_1\dots x_N$。

接下来一行包含 $Q$。

接下来 $Q$ 行，每行包含两个整数 $a_i,b_i$。

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


title: [USACO23DEC] Cowntact Tracing P

description:
Farmer John 有依次编号为 $1\dots N$ 的 $N$（$2\le N \le 10^5$）头奶牛，奶牛间的关系可以用树结构描述。不幸的是，有一种疾病正在传播。

最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它的邻居。一旦奶牛被感染，她就会持续处于感染状态。经过一些晚上，Farmer John 意识到这样的情况，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。

你将得到 $Q$（$1\le Q \le 20$）个不同的夜晚数，每个都是 $[0,N]$ 范围内的整数。对于每个夜晚数，请找出最少有多少头奶牛最初可能感染了这种疾病，或者报告夜晚数与给出的信息不符。

inputFormat:
第一行为一个整数 $N$。

接下来一行，包含长度为 $N$ 的由 $1$ 和 $0$ 组成的位串。其中 $1$ 表示一头被感染的奶牛，$0$ 表示一头在经过若干晚之后仍未被感染的奶牛。

接下来 $N-1$ 行描述了树的边。

接着输入 $Q$ 和 $Q$ 个夜晚数。

outputFormat: 输出 $Q$ 行，表示每个夜晚数的答案。若无解，输出 $-1$。

hint:
### 样例解释 1

对于前四个询问，一种可能是只有 $3$ 号奶牛一开始被感染。对于第五组询问（$1$ 晚），一种可能是 $2,4$ 号奶牛一开始被感染。对于第六组询问（$0$ 晚），一种可能是所有的五只奶牛在一开始都被感染。

### 样例解释 2

对于第一组询问（$0$ 晚），一种可能是所有的十只奶牛一开始都被感染。对于第二组询问（$1$ 晚），一种可能是 $2,7,9$ 号奶牛一开始被感染。对于第三组询问（$2$ 晚），一种可能是 $2,9$ 号奶牛一开始被感染。对于第四至第十一组询问，一种可能是只有 $7$ 号奶牛一开始被感染。

### 样例解释 3

对于第一组询问（$0$ 晚），一种可能是 $1,2,3$ 号奶牛一开始被感染。对于第二组询问（$1$ 晚），一种可能是只有 $2$ 号奶牛一开始被感染。对于第三组询问（$2$ 晚），一种可能是只有 $1$ 号奶牛一开始被感染。对于第四至第六组询问，不可能满足题给条件。

### 测试点性质

- 测试点 $4-5$ 满足 $N \le 10$。
- 测试点 $6-8$ 满足所有奶牛都被感染。
- 测试点 $9-11$ 满足 $N \le 400$。
- 测试点 $12-23$ 没有额外限制。


title: [USACO23DEC] A Graph Problem P

description:
为了丰富自己的数学知识，Bessie 选修了一门图论课程，她发现她被下面的问题困住了，请帮帮她！

给出一张连通的无向图，包含编号为 $1\dots N$ 的节点和编号为 $1\dots M$（$2 \le N \le 2\cdot 10^5$，$N - 1 \le M \le 4 \cdot 10^5$）的边，下边的操作将被实施：

1. 假设集合 $S=\{v\}$，变量 $h=0$。
2. 当 $|S|<N$，重复执行：
	1. 仅有一个顶点在集合 $S$ 中的边中，找到编号最小的那条，编号记为 $e$。
    2. 将 $e$ 不在 $S$ 中的那个顶点加入集合 $S$。
    3. 将 $h$ 修改为 $10h+e$。
3. 返回 $h$ 对 $10^9+7$ 取模的值。

输出这个过程的全部返回值。

inputFormat: 第一行包含 $N$ 和 $M$。接下来 $M$ 行，每行包含第 $e$ 条边的顶点 $(a_e,b_e)$，保证图连通，没有重边。

outputFormat: 输出 $N$ 行，第 $i$ 行包含在节点 $i$ 开始过程的返回值。


title: [USACO23DEC] Train Scheduling P

background: **Note: The memory limit for this problem is 512MB, twice the default.**

description:
Bessie 找到了一份行车调度的新工作。现在有两座火车站 $A$ 和 $B$，由于预算限制，只有一条单线铁道连接起车站 $A$ 和 $B$。如果一列列车在 $t$ 时刻离开其中一座火车站，它将在 $t+T$（$1 \le T \le 10^{12}$）时刻到达另一座火车站。

现在有 $N$（$1 \le N \le 5000$）列火车的出发时间需要安排。第 $i$ 列火车必须在 $t_i$ 时刻后从车站 $s_i$ 出发（$s_i\in \{A,B\}$，$0 \le t_i \le 10^{12}$）。在同一时刻不允许铁道上有相反方向的列车，否则它们会相撞。但是，假设火车有可以忽略的尺寸，在同一时刻，铁道上可以有许多相同方向的列车。

帮助 Bessie 安排每辆列车的出发时间，在不会相撞的前提下最小化总延误时间。假设第 $i$ 辆列车被安排在 $a_i$ 时刻出发，总延误为 $\sum\limits_{i=1}^n{a_i-t_i}$。

inputFormat:
第一行包含 $N$ 和 $T$。

接下来 $N$ 行，第 $i$ 行包含用于描述第 $i$ 辆列车的 $s_i,t_i$。

outputFormat: 输出合法安排中最小总延误时间。

hint:
### 样例解释 1

唯一的一辆列车准点出发。

### 样例解释 2

有两种最佳方案。第一种是让列车 $2,3,4$ 准点出发，列车 $1$ 延误一分钟后出发。第二种是让列车 $1,2,3$ 准点出发，列车 $4$ 延误一分钟后出发。

### 样例解释 3

最佳方案是让列车 $1,3$ 准点出发，列车 $2$ 在时刻 $13$ 出发，列车 $4$ 在时刻 $23$ 出发。总延误为 $0+11+0+2=13$。

### 测试点性质

- 测试点 $5-6$ 满足 $N \le 15$。
- 测试点 $7-10$ 满足 $N \le 100$。
- 测试点 $11-14$ 满足 $N \le 500$。
- 测试点 $15-18$ 满足 $N \le 2000$。
- 测试点 $19-24$ 没有额外限制。


title: 「Daily OI Round 3」Simple

background: 这是一道简单题。

description:
Acoipp 的某个软件的账号叫做 Svpoll，并且这款软件的账号与洛谷账号均不区分大小写，例如 $\texttt{SVPOLl}$ 和 $\texttt{svPOLL}$ 等价，$\texttt{aCoIPp}$ 和 $\texttt{Acoipp}$ 等价。

现在你想要知道某个账号名称是与 $\texttt{Acoipp}$ 等价，还是与 $\texttt{Svpoll}$ 等价，或者是与前两者都不等价。

inputFormat: 一行一个字符串，表示账号名称。

outputFormat: 一行一个字符串，如果输入的字符串与 $\texttt{Acoipp}$ 等价，那么输出 $\texttt{Luogu}$；如果输入的字符串与 $\texttt{Svpoll}$ 等价，那么输出 $\texttt{Genshin}$；如果输入的字符串与前两者都不等价，输出 $\texttt{Boring}$。

samples: SVPOLL Genshin

samples: ACoiPP Luogu

samples: RECOLL Boring

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

因为不区分大小写，所以 $\texttt{SVPOLL}$ 中的 $\texttt{V}$，$\texttt{P}$，$\texttt{O}$，$\texttt{L}$ 分别与 $\texttt{v}$，$\texttt{p}$，$\texttt{o}$，$\texttt{l}$ 等价，所以 $\texttt{SVPOLL}$ 与 $\texttt{Svpoll}$ 等价。

#### 【数据范围】

设 $|S|$ 为字符串长度，对于全部数据保证：$|S|=6$ 并且输入的字符串只包含大小写英文字母。


title: 「Daily OI Round 3」City Planning

background: 只要不失去你的崇高，整个世界都会为你敞开。

description:
Provence-Alpes-Côte d'Azur 的管理者们遇上大麻烦了！他们邀请你来解决城市规划的问题。

这群管理者一共有 $t$ 人，并且这个地区一共有 $n$ 个城镇，第 $i$ 个城镇内部又有 $k_i$ 个村庄，通过 $p_i$ 条道路连接，第 $j$ 条道路双向连接第 $i$ 个城镇中的第 $u_{i,j}$ 和 $v_{i,j}$ 两个村庄，管理道路的人是第 $w_{i,j}$ 个，客流量是 $z_{i,j}$。

为了管理组内部的团结，保证每个人在同一个城镇最多管理 $1$ 条道路。

现在这些城镇中的村庄和村庄之间的道路都遭到了损坏，管理者们急于恢复这些城镇内的交通。这些城镇互相之间有 $m$ 条高铁，每条高铁连接了 $u,v$ 两个城镇，并且当初为了设计的优美，这 $n$ 个城镇和 $m$ 条高铁构成了一个**二分图**。

对于每个城镇 $i$，你都需要帮助管理组选择一个参数 $c_i(1 \le c_i \le k_i)$，修复一些村庄，编号在 $1 \sim c_i$ 之间的村庄都会被修复，如果道路的两端的村庄都修复了，那么这条道路就会自动修复。因此第 $i$ 个城镇中会产生 $b_{i,c_i}$ 的花费。

对于管理者 $i$ 来说，如果存在两条他在不同城镇管理的道路都没有被修复，并且这两条道路所属的城镇有高铁**直接连接**，你需要支付这两条道路的人流量的乘积来弥补损失，这样管理者 $i$ 才会高兴。（对于**任意**两条满足上述条件的道路你都需要弥补损失，而不是对于每个管理者只需要弥补一对道路的损失）

为了让管理组的成员都高兴并且给出的方案符合题目的要求（即 $1 \le c_i \le k_i$），你需要提前计算好自己至少需要支付多少钱以应对这一群管理者们的刁难。

inputFormat:
第一行三个整数 $n,m,t$ 表示城镇的数量，城镇间的高铁的数量和管理组人员的数量。

接下来 $m$ 行每行两个整数 $x,y$ 表示这条高铁连接的两个城镇的编号。

接下来 $n$ 组输入，对于第 $i$ 组输入，格式如下：

第一行两个整数 $k_i,p_i$ 表示第 $i$ 个城镇有 $k_i$ 个村庄，$p_i$ 条道路。

第二行 $k_i$ 个整数，第 $j$ 个整数表示当 $c=j$ 时的花费 $b_{i,j}$。

接下来 $p_i$ 行，每行四个整数 $u_{i,j},v_{i,j},w_{i,j},z_{i,j}$，表示有一条边连接 $i$ 号城镇的第 $u_{i,j}$ 个村庄和第 $v_{i,j}$ 个村庄，并且管理道路的人是第 $w_{i,j}$ 个，客流量为 $z_{i,j}$。

outputFormat: 一行一个整数表示让所有管理者都高兴的最小花费是多少。

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

我们可以选择 $c_1=1,c_2=2$，那么花费就是 $b_{1,c_1}+b_{2,c_2}=3+6=9$，而没有一个管理员你需要讨好。

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

我们可以选择 $c_1=1,c_2=1,c_3=2$，那么花费就是 $b_{1,c_1}+b_{2,c_2}+b_{3,c_3}=1+1=2$，但是管理员 $2$ 在城镇 $1$ 中管理的道路 $2 \to 3$ 不可能被修复，在城镇 $2$ 中管理的道路 $1 \to 2$ 不可能被修复，你就需要花费 $2 \times 1 = 2$ 的代价讨好管理员 $2$，总的代价就是 $4$。

你并不需要讨好管理员 $1$，哪怕他在城镇 $1$ 和 $3$ 中分别有一条道路不可能被修复，因为城镇 $1$ 和 $3$ 没有高铁相连，所以你不需要为此支付额外的资金。

#### 【数据范围】

对于全部数据保证：$1 \le n \le 50$，$1 \le k_i \le 100$，$0 \le p_i \le t$，$0 \le m \le 500$，$1 \le t \le 50$，$1 \le x,y \le n$，$x \ne y$，$0 \le b_{i,j} \le 10^9$，$1 \le u_{i,j},v_{i,j} \le k_i$，$1 \le w_{i,j} \le t$，$1 \le z_{i,j} \le 10^4$。

$n$ 个城镇和 $m$ 条高铁构成的图是一个二分图，每个管理员在同一个村庄管理的道路数量不超过 $1$。

**可能有连接同一对城镇的不同的高铁，不会出现自己连向自己的高铁。但城镇中的村庄可能会有自己连向自己的道路，也可能出现连接同一对村庄的不同的道路。**


title: 「Cfz Round 2」How to Prove

description:
给定一个正整数 $n$。

我们定义，对于一个集合 $S$，$\Omega(S)$ 为集合 $S$ 的所有的 **非空子集的元素和** 所组成的集合。

形式化地，$\Omega(S)=\{x\mid x=\sum\limits_{i\in T}i,T\subseteq S,T\neq \varnothing\}$。

例如，当 $S=\{2,0,-3,5\}$ 时，$\Omega(S)=\{-3,-1,0,2,4,5,7\}$。

你需要构造一个大小为 $n$ 的集合 $S$，满足：

- 集合 $S$ 中的所有元素均为不大于 $10^9$ 且不小于 $-10^9$ 的整数；
- $|\Omega(S)|$ 最小，即 $\Omega(S)$ 所包含的元素个数最少。

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

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

接下来依次输入每组测试数据。对于每组测试数据，输入一行一个正整数 $n$。

outputFormat:
对于每组测试数据，输出一行 $n$ 个整数，表示你构造的集合 $S$ 中的所有元素。

**所有满足要求的输出均可通过。**

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

对于第 $1$ 组数据，$S=\{3\}$，$\Omega(S)=\{3\}$。当然，$\{0\}$、$\{-2\}$ 等也为满足条件的集合 $S$。

对于第 $2$ 组数据，$S=\{0,5\}$，$\Omega(S)=\{0,5\}$。

对于第 $3$ 组数据，$S=\{2,0,-2,4\}$，$\Omega(S)=\{-2,0,2,4,6\}$。

可以证明以上构造均满足条件。

#### 「数据范围」

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有数据，$1 \le T \le 100$，$1 \le n \le 10^6$，$\sum n \le 10^6$。

**只有你通过本题的所有测试点，你才能获得本题的分数。**


title: [USACO19OPEN] Bucket Brigade B

description:
农场上起火了，奶牛们正在紧急赶去灭火！

农场可以用一个像这样的 $10×10$ 的字符方阵来描述：

```plain
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
```

字符 `B` 表示正着火的牛棚。字符 `L` 表示一个湖，而字符 `R` 表示农场上的一块巨大岩石。

奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。这对于湖边的奶牛也是对的——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。

请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的 `.` 格子的最小数量。

奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。

inputFormat: 输入包含 $10$ 行，每行 $10$ 个字符，描述这个农场的布局。输入保证图案中恰有一个字符 `B`、一个字符 `L` 以及一个字符 `R`。

outputFormat: 输出一个整数，为组成一条可行的水桶传递队列所需要的奶牛的最小数量。


title: [USACO19OPEN] Milk Factory B

description:
牛奶生意正红红火火！Farmer John 的牛奶加工厂内有 $N$ 个加工站，编号为 $1\dots N$（$1\le N\le 100$），以及 $N−1$ 条通道，每条连接某两个加工站。（通道建设很昂贵，所以 Farmer John 选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。

为了创新和提升效率，Farmer John 在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。

然而，Farmer John 认为事情可能还不算完全失败，只要至少还存在一个加工站 $i$ 满足从其他每个加工站出发都可以到达加工站 $i$。注意从其他任意一个加工站 $j$ 前往加工站 $i$ 可能会经过 $i$ 和 $j$ 之间的一些中间站点。请帮助 Farmer John 求出是否存在这样的加工站 $i$。

inputFormat: 输入的第一行包含一个整数 $N$，为加工站的数量。以下 $N−1$ 行每行包含两个空格分隔的整数 $a_i$ 和 $b_i$，满足 $1\le a_i,b_i\le N$ 以及 $a_i\neq b_i$。这表示有一条从加工站 $a_i$ 向加工站 $b_i$ 移动的传送带，仅允许沿从 $a_i$ 到 $b_i$ 的方向移动。

outputFormat: 如果存在加工站 $i$ 满足可以从任意其他加工站出发都可以到达加工站 $i$，输出最小的满足条件的 $i$。否则，输出 $−1$。


title: [USACO19OPEN] Cow Evolution B

description:
现在是 3019 年，在过去的一千年里发生了不计其数的牛类进化，产生了具有各种有趣特性的奶牛。

牛类进化的记录可以用一棵树来表示，起源是位于树根位置的没有特殊特性的奶牛。树上每一个产生后代的结点，有可能所有的奶牛都进化出了一种新的特性（比如说喷火（fire breathing），如下图所示，其中所有斑点（spots）奶牛最后都能喷火），或者是奶牛种群产生了分支进化，其中有些进化出了新的特性（比如，飞（flying）），有的没有。

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

树底部的叶结点表示 3019 年所有产生的奶牛的子种群。没有不同的叶结点（子种群）具有完全相同的一组特性。例如，子种群 #1 是没有特殊特性的奶牛，子种群 #3 是能够心灵感应的（telepathic）会飞的奶牛。相比之下，子种群 #2 是会飞但不能心灵感应的奶牛。子种群 #3 是唯一既会飞又会心灵感应的。

像上图这样每一种进化出的新特性都恰好在树中的一条边上产生（也就是说，在整个进化历史中仅在一个时间点产生），这样的进化树被称为是“合法的”。例如，如果斑点这一特性在两个不同分支中均进化产生，这棵进化树就不是合法的。给定 3019 年奶牛子种群的描述，请判断是否这可以由一棵合法的进化树所解释。

inputFormat: 输入的第一行包含子种群的数量 $N$（$2\le N\le 25$）。以下 $N$ 行每行描述一个子种群。每行包含一个整数 $K$（$0\le K\le 25$），之后是 $K$ 个该子种群奶牛所拥有的特性。特性是由至多 $20$ 个小写字母（`a..z`）组成的字符串。没有两个子种群拥有完全相同的特性。

outputFormat: 如果可能构造一棵可以解释所有子种群产生途径的进化树，输出 `yes`，否则输出 `no`。

samples:
4
2 spots firebreathing
0
1 flying
2 telepathic flying

hint:
### 样例解释 1

这个输入样例与上图所示的合法进化树一致。


title: [USACO18JAN] Blocked Billboard II B

description:
Bessie the cow used to have such a nice view from her barn, looking across road at a set of two billboards advertising delicious looking cow feed. Unfortunately, one of these billboards has recently been updated so it now advertises "Farmer Larry's Lawnmowers". Bessie is not a fan of lawnmowers since their only purpose, as far as she can tell, is cutting back the grass in her field that she finds so tasty (if you haven't noticed, much of Bessie's thought process revolves around food).

Fortunately, the remaining cow feed billboard is situated in front of the lawnmower billboard, potentially obscuring it.

Bessie, determined to remove the offensive lawnmower billboard completely from her view, hatches a risky plan. She plans to steal a large rectangular tarp from the barn and sneak out late at night to cover the remaining portion of the lawnmower billboard, so that she can no longer see any part of it.

Given the locations of the two billboards, please help Bessie compute the minimum area of the tarp she will need. Since the only tarps available in the barn are rectangular in size, Bessie observes that she may conceivably need a tarp whose area is slightly larger than the exposed area of the lawnmower billboard, as illustrated in the example below. The tarp may only be placed such that its sides are parallel to those of the other billboards (i.e., it cannot be "tilted").

inputFormat: The first line of input contains four space-separated integers: $x_1,y_1,x_2,y_2$, where $(x_1,y_1)$ and $(x_2,y_2)$ are the coordinates of the lower-left and upper-right corners of the lawnmower billboard in Bessie's 2D field of view. The next line contains four more integers, similarly specifying the lower-left and upper-right corners of the cow feed billboard. The cow feed billboard may obscure all, some, or none of the lawnmower billboard. All coordinates are in the range $-1000$ to $+1000$.

outputFormat: Please output the minimum area of the tarp Bessie needs to use to cover part of the lawnmower billboard so that it becomes completely obscured.

translation:
奶⽜ Bessie 曾在谷仓中享受着这么漂亮的景色 —— 看着公路旁的两个矩形广告牌，上⾯播放着美味的牛饲料广告。不幸的是，其中有一个广告牌最近更新并刊登着广告 “农夫 Larry 的割草机” 。Bessie 不喜欢割草机，因为据她所知，割草机的唯一作用是割掉田地里美味的草。

幸运的是，另⼀个播放牛饲料广告的广告牌位于割草机广告牌的前面，并有可能将其遮挡住。

Bessie 决定从她的视线中完全移除掉冒犯的割草机广告牌，因此制定了一个冒险的计划。她计划从谷仓中偷窃一个矩形大布，并在深夜里偷偷地把这块大布覆盖在割草机广告牌的其余部分，这样她就不用看到割草机广告牌的任
何一部分了。

给定两个广告牌的位置，请帮助 Bessie 计算大布的最小面积。由于谷仓中只有矩形大布， Bessie 意识到可能需要一个面积略大于割草机广告牌未被遮挡部分的面积的大布，如样例所示。矩形大布的边必须与广告牌的边平行（即不能倾斜放置大布）。

hint:
### Sample Explanation 1

Here, the cow feed billboard obscures the lower right corner of the lawnmower billboard, but this doesn't really help, since Bessie still needs to use a tarp whose size is as large as the entire lawnmower billboard.


title: [USACO18JAN] Lifeguards B

description:
Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires $N$ cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time $t=0$ until time $t=1000$ on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time $t=4$ and ending at time $t=7$ covers three units of time (note that the endpoints are "points" in time).

Unfortunately, Farmer John hired 1 more lifeguard than he has the funds to support. Given that he must fire exactly one lifeguard, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.

inputFormat: The first line of input contains $N (1\le N\le 100)$. Each of the next N lines describes a lifeguard in terms of two integers in the range $0\dots 1000$, giving the starting and ending point of a lifeguard's shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

outputFormat: Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires 1 lifeguard.

translation: 给定 $n$ 个左闭右开区间，问在去掉任意一个区间的情况下，区间的覆盖长度最大是多少。


title: [USACO18JAN] Out of Place B

description:
Feeling ambitious, Farmer John plans to attempt something that never seems to go quite right: he wants to take a photograph of his entire herd of cows.

To make the photograph look nice, he wants the cows to line up in a single row from shortest to tallest. Unfortunately, right after he has the cows line up this way, Bessie the cow, always the troublemaker, steps out of line and re-inserts herself at some other location in the lineup!

Farmer John would like to swap pairs of cows so the entire herd is again lined up properly. Please help him determine the minimum number of swaps he needs to make between pairs of cows in order to achieve this goal.

inputFormat: The first line of input contains $N (2\le N\le 100)$. The next $N$ lines describe the heights of the cows as they are lined up after Bessie makes her move. Each cow height is an integer in the range $1\dots 1,000,000$. Cows may have the same height.

outputFormat: Please output the minimum number of times Farmer John needs to swap pairs of cows in order to achieve a proper ordering. Swaps do not necessarily need to involve adjacent cows in the ordering.

translation:
给定一个长度为 $n$ 的序列 $a$，序列原本单调递增，但有一数 $a_k$，或插入到了序列头部，或插入到了序列尾部，或插入到了两数字 $a_i$ 和 $a_{i+1}$ 之间，且序列中原本的 $a_k$ 会被删除。

问最少交换多少对数，才能使得该序列再次单调递增？

hint:
### Sample Explanation

In this example, Bessie is clearly the cow of height 3. FJ return the cows to sorted order using three swaps as described below:

2 4 7 7 9 3 - Original Lineup
2 4 7 7 3 9 - Swap the last two cows
2 4 3 7 7 9 - Swap the first 7 and 3
2 3 4 7 7 9 - Swap 4 and 3


title: [集训队互测 2023] Permutation Counting 2

description:
给定 $n$，对于每组 $x,y\in [0,n)$ 求出有多少个 $1\sim n$ 的排列 $p$ 满足以下条件：

- $\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x$。

- $\sum\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+1}]=y$。

其中 $p^{-1}$ 表示 $p$ 的逆排列，满足 $p^{-1}_{p_i}=i$。

答案对给定的质数 $MOD$ 取模。

inputFormat: 共一行，两个整数，表示 $n,MOD$。

outputFormat: 共 $n$ 行，每行共 $n$ 个整数，第 $i$ 行第 $j$ 列的数表示 $x=i-1,y=j-1$ 时的答案。

hint:
对于 $100\%$ 数据，$1\le n\le 500$，$10^9\le MOD\le 1.01\times 10^9$，保证 $MOD$ 为质数。

$\operatorname{Subtask} 1(10\%):n\le 8$。

$\operatorname{Subtask} 2(15\%):n\le 16$。

$\operatorname{Subtask} 3(25\%):n\le 40$。

$\operatorname{Subtask} 4(25\%):n\le 100$。

$\operatorname{Subtask} 5(25\%):$ 无特殊限制。


title: [集训队互测 2023] 优惠购物

description:
小 C 要购买 $n$ 个物品，这些物品有前置关系，必须**依次**购买（即在购买了第 $i$ 个后才能购买第 $i+1$ 个）。

他初始有 $m$ 张优惠劵和无穷多个金币。每个物品有两个属性，价格 $a_i$ 和优惠劵的使用上限 $b_i(0\le b_i\le a_i)$。

购买一个物品的流程如下：

- 选择使用 $x(0\le x\le b_i)$ 张优惠券，付出 $a_i-x$ 个金币和 $x$ 张优惠券。
- 购买完后可得到 $\lfloor \frac{a_i-x}{c} \rfloor$ 张优惠券（即一次购买中，每付出 $c$ 个金币可以得到一张优惠券，$c$ 为给定常数）

小 C 想求出最少花费多少个金币能购买全部物品。

inputFormat:
本题包含多组数据，第一行包含一个整数 $T$，表示数据组数。

对于每组数据：

- 第一行包含三个整数 $n,m,c$。
- 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$ 表示每个物品的价格。
- 第三行包含 $n$ 个整数 $b_1,b_2,...,b_n$ 表示优惠劵的使用上限。

outputFormat:
对于每组数据输出一行：

- 第一行输出一个整数，表示最少需要的金币数量。

samples:
见附件 ex_shop2.in。
见附件 ex_shop2.out。

hint:
对于所有数据，$1\le \sum n\le 10^6,0\le m,a_i,b_i\le 10^9,2\le c\le 10^9$。

- Subtask 1 (5 pts)：$1\le T\le 5,1\le n\le 10,1\le m,\sum a_i,\sum b_i\le 10$
- Subtask 2 (10 pts)：$a_i=b_i$
- Subtask 3 (10 pts)：$1\le \sum n\le 500,1\le \sum m,\sum a_i,\sum b_i\le 500$
- Subtask 4 (10 pts)：$1\le \sum n\le 6000,1\le \sum m,\sum a_i,\sum b_i\le 6000$
- Subtask 5 (10 pts)：$1\le \sum n\le 6000$
- Subtask 6 (15 pts)：$1\le \sum n\le 2\times 10^5,2\le c\le 20$
- Subtask 7 (10 pts)：$1\le \sum n\le 1\times 10^6,2\le c\le 20$
- Subtask 8 (15 pts)：$1\le \sum n\le 2\times 10^5$
- Subtask 9 (15 pts)：$1\le \sum n\le 1\times 10^6$

时间限制：$\texttt{1s}$

空间限制：$\texttt{2048MB}$


title: [集训队互测 2022] Range Minimum Element

description: 有一个长度为 $n$，值域为 $[1,c]$ 的正整数序列 $a$。给定 $m$ 个区间 $[l_i,r_i]$，设长度为 $m$ 的序列 $b$ 满足 $\forall i\in [1,m],b_i=\min\limits_{j=l_i}^{r_i}\{a_j\}$。求出 $a$ 在范围内任意取的情况下共能得到多少种不同的 $b$。答案对 $998244353$ 取模。

inputFormat:
第一行，三个数，依次表示 $n,m,c$。

接下来 $m$ 行，每行两个数 $l_i,r_i$ 表示一个给定的区间。

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


title: [集训队互测 2023] 网格图最大流计数

description:
给定 $n,m,k$，和两个正整数序列 $a_{1...n},b_{1...m}$，以及一个 $k\times k$ 的 $01$ 矩阵 $s_{1...k,1...k}$。

考虑一张有向图 $G=(V,E)$，其中 $V=\{S,T\}\cup(\{0,1\}\times ([1,k]\cap\mathbb{Z})^2)$，而 $E=E_1\cup E_2\cup E_3$ 由三部分组成：

- $E_1=\{(S,(0,1,a_i)) \mid 1\le i\le n\}\cup\{((1,k,b_i),T)\mid 1\le i\le m\}$
- $E_2=\{((1,i,j),(0,i+1,j))\mid1\le i<k,1\le j\le k\}\cup \{(1,i,j),(0,i,j+1))\mid1\le i\le k,1\le j<k\}$
- $E_3=\{((0,i,j),(1,i,j))\mid 1\le i,j\le k,s_{i,j}=1\}$

简单来说，你可以看成每个格子 $(i,j),1\le i,j\le k$ 被拆成了一个入点 $(0,i,j)$ 和一个出点 $(1,i,j)$。$E_1$ 描述了 $S,T$ 与这些点之间的边，由 $a,b$ 决定；$E_2$ 描述了每个格子的出点连向它上方和右方格子的入点的边；$E_3$ 描述了每个格子的入点连向出点的边，由 $s$ 决定。

现在我们将 $G$ 看成一个网络，每条边的容量是 $1$。你需要求出以 $S$ 为源点，以 $T$ 为汇点的最大流，以及最大流的数量（两个流被认为是不同的，当且仅当存在一条边在两个流中的流量不同）。

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

第二行 $n$ 个正整数 $1\le a_1<a_2<...<a_n\le k$。

第三行 $m$ 个正整数 $1\le b_1<b_2<...<b_m\le k$。

接下来 $k$ 行，每行一个长度为 $k$ 的 01 字符串，表示矩阵 $s$。

outputFormat: 输出一行两个非负整数，分别表示最大流和最大流的数量，后者对 $10^9+7$ 取模。


title: [集训队互测 2023] 落日珊瑚

description:
给一个长度为 $n$、包含方括号和圆括号的括号串，定义一个串 $S$ 合法，当且仅当以下几种情况之一：

1.  $S$ 为空串；
1.  $S= [T]$ 且 $T$ 合法；
1.  $S= (T)$ 且 $T$ 合法；
1.  $S=TU$ 且 $T, U$ 合法。

比如 ```()```，```[()]``` 都是一个合法的括号串，但 ```[()]())``` 不是。

定义一个操作叫选择一个区间 $[l, r]$，并把所有在区间里的字符从方括号变圆括号，从圆括号变方括号。

定义一个括号串的权值 $val(S)$ 为：如果这个括号串能通过操作变成合法，就是最小的操作次数；否则是 $0$。

给出 $q$ 次修改查询，有以下两种可能。

1.  修改，给出一个区间 $[l, r]$ 把所有在区间里的字符从方括号变圆括号，从圆括号变方括号。
2.  查询，给出一个区间 $[l, r]$，求 $\sum_{[l', r'] \in [l, r]} val(s[l', r'])$。

inputFormat:
第一行四个整数 $n, q, T, subtaskid$，分别表示字符串长度，操作次数，强制在线的参数，子任务编号。

接下来一行一个长度为 $n$ 的字符串。

接下来 $q$ 行，每行三个数 $opt, L, R$，表示一次操作。

强制在线，真实的 $l = \min((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$，$r = \max((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$ 其中 $lastans$ 是上一次询问的答案，如果没有上次询问则为 $0$。

**请注意，即使是离线的部分分，也有可能 $L \neq l$，$R \neq r$**。

outputFormat: 若干行，每次询问输出一个答案。


title: [集训队互测 2023] Tree Topological Order Counting

description:
给定一颗 $n$ 个点的有根树，$1$ 是根，记 $u$ 的父亲是 $fa_u$。另给出一长度为 $n$ 的权值序列 $b$。

称一个长度为 $n$ 的排列 $a$ 为这颗树的合法拓扑序，当且仅当 $\forall 2 \le u \le n,a_u > a_{fa_u}$。

对每个点 $u$，定义 $f(u)$ 为，在所有这颗树的合法拓扑序中，$b_{a_u}$ 之和。

现在对 $1 \le u \le n$，求 $f(u) \bmod 10^9+7$。

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

第二行 $n-1$ 个整数，第 $i$ 个表示 $fa_{i+1}$，描述树的结构。

第三行 $n$ 个整数，第 $i$ 个表示 $b_i$，描述权值序列。

outputFormat: 一行 $n$ 个整数，第 $i$ 个表示 $f(i) \bmod 10^9+7$。


title: [集训队互测 2023] 茧

description:
Lily 是一个有趣的女孩子。她经常和 Kaguya 玩一些奇怪的游戏。

今天她们在玩一个名为 nim 的游戏。具体地，nim 游戏的规则如下：

- 有若干排数目已知的棋子，两人轮流从任意一排移除任意正整数枚棋子。
- Lily 先手，无法操作者负，即移除最后一枚棋子者获胜。

因为其最优策略非常简单，所以几局过后，她们就开始感到无趣了。于是，她们在原有规则的基础上增加了一条规则：

- 在一排 $x$ 枚棋子中可以移除 $y$ 枚，当且仅当 $y^k \le x$。

这下游戏变得有趣了。不过，由于策略比较复杂，Lily 在计算的时候常常感到力不从心。

可以证明，这个游戏的任意一个局面都满足：要么 Lily 有必胜策略，要么 Kaguya 有必胜策略。

于是，Lily 想请你编写一个程序来计算某个局面下谁有必胜策略（Lily 总是先手），以便复盘时分析哪次操作失误了。

由于求知欲旺盛的 Lily 可能会对局面进行比较细致的分析，所以你需要回答她的多次询问。

由于所有局面都是复盘同一局游戏时衍生出来的，所以所有询问的参数 $k$ 都相同。

**本题询问的局面形式比较特殊，详见输入格式。**

inputFormat:
输入的第一行包含两个整数 $t, k$，分别表示询问次数和操作中的参数。

接下来依次输入每次询问，对于每次询问：

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

输入的第二行包含 $n$ 个整数 $a_1, \dots, a_n$。

$(n, a_{1 \dots n})$ 表示有 $\sum a_i$ 排棋子，各排所含棋子数分别为 $1 \dots a_1, 1 \dots a_2, \dots, 1 \dots a_n$。

如果你对博弈论比较熟悉的话，不难发现题意可以转化为：

- 记一排 $x$ 个棋子的 [Grundy value](https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem) 为 $g(x)$，设 $h(x)$ 为 $g(x)$ 的前缀异或和，求 $h(a_1) \dots h(a_n)$ 的异或和是否为 $0$。

outputFormat:
对于每次询问输出一行一个字符串。

- 若 Lily 有必胜策略，输出 `Lily`；
- 若 Kaguya 有必胜策略，输出 `Kaguya`。


title: [集训队互测 2023] 左蓝右红

background:
小 S 是一个喜欢音游的女孩子。

2077 年 7 月 7 日，某三维立体音乐游戏的 20.7.7 版本更新了一个塞满直角蛇的谱面 Tnemitnep [Beyond 18+]。但是当小 S 开始游玩这个谱面之后发现，由于游戏 bug，所有的蛇的色彩指示都没了……

但是小 S 作为 ptt 20.77 的 18 星高端玩家，首个理论值这首曲目的位置她势在必得，因此她不想等游戏开发者修复 bug。她决定：通过这个游戏的机制自行计算出所有蛇原本的颜色！

不幸的是，小 S 经过一些简单的推理，发现这个游戏的机制并不足以唯一确定所有蛇的颜色。因此小 S 首先希望通过这个游戏的“左蓝右红”规则计算出一种反手尽量少的染色可能性；同时计算出不同的染色方案数，以获知自己在最坏情况下需要尝试多少次才能正确地接住所有蛇。

小 S 将这个问题抽象成了一个 OI 问题，可是小 S 并不是很会 OI，于是她找到了即将参加 IOI 2024 的你。你能帮助小 S 在别人都还在莫名其妙红蛇 Track Lost 的时候拿下 Tnemitnep BYD 的首杀吗？

description:
在平面直角坐标系上给定 $n$ 个矩形，形成若干个交点，每个矩形的所有边都平行于坐标轴。**保证没有两个矩形的两条边共线。**

矩形之间会形成若干个交点，每一个矩形都被它上面的交点分成若干段。定义属于一个矩形上的**一段**是该矩形上相邻的两个交点之间的部分。也就是说一个矩形上如果有 $n$ 个交点，就会被划分成 $n$ 段。

现在将每一个矩形上的每一段染色为蓝色或红色。要求：

- 与同一个交点相邻的**同属于一个矩形的**两段不同色；
- 所有红线形成若干互不相交的封闭曲线；
- 所有蓝线形成若干互不相交的封闭曲线。

定义两个图形 $R,B$：

- $R$ 为删去所有蓝线后，所有被**奇数个**红色封闭曲线包含的点组成的集合；
- $B$ 为删去所有红线后，所有被**奇数个**蓝色封闭曲线包含的点组成的集合。

一个方案合法当且仅当它满足上述所有条件，并且**使得 $R\cap B$ 里面只有有限个点**。

**如果无法理解上述定义，可以参考样例解释。**

你需要分别求出：

- 字典序最小的合法染色方案（字典序在输出格式里面有定义）。
- 合法染色方案数，对 $20,051,131$（质数）取模。两个染色方案不同当且仅当存在一段，在一种方案中被染成红色，在另一种方案中被染成蓝色。

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

接下来 $n$ 行，第 $i$ 行 4 个整数 $x_{1,i},y_{1,i},x_{2,i},y_{2,i}$，前两个表示左下角坐标，后两个表示右上角坐标。

outputFormat:
第一行输出字典序最小的合法方案：如果无解，输出一行 `-1`；否则输出一个长度为 $n$ 的 0/1 串。如果在你的方案中，按输入顺序给出的第 $i$ 个矩形的左下角是红色，则你输出的第 $i$ 个整数应该是 $0$；否则应该是 $1$。可以证明给定这些数之后能够唯一确定整个染色方案。如果有多解，你输出的解必须使得**上面描述的 01 序列字典序最小**。

第二行输出合法染色方案数，对 $20,051,131$ 取模。无解时应输出 $0$。

hint:
样例 5、6、7 见附件。

---

样例 1 解释：

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

如图是给定的矩形在平面直角坐标系上的形态。

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

如图，标出颜色的地方是属于第 1 个矩形的两段。

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

如图，标出颜色的地方是属于第 2 个矩形的两段。按照上述图片给出的颜色进行染色可以得到样例输出中给出的合法方案：

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

如下图，左侧方案是不合法的，因为与用圈标出的交点相邻的同属于一个矩形的两段同色；右侧方案也是不合法的，因为 $R$ 与 $B$ 交在图中的紫色正方形内，$R\cap B$ 包含无限多个点。

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

如下方案是合法的，但是对应字符串 `10` 不是字典序最小的。

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

---

样例 2 解释：

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

左侧的图为给定的所有矩形。

中间的图表示对应的染色方案。每一个矩形都包含 $6$ 段，并且满足与任何一个交点相邻的同属于一个矩形的两段不同色。

右侧的图中，用红色区域标出 $R$ 的范围，蓝色区域标出 $B$ 的范围。两图形的交只包含 $12$ 个点。

---

样例 3 解释：

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

如图，该样例中，因为环内部的部分被 $2$ 条红色封闭曲线包含，$2$ 是偶数，所以环内部不属于 $R$，$R$ 形成一个环。

---

数据范围：

对于 $100\%$ 的数据，保证 $1\leq n\leq 2\times 10^5$，$x_{1,i}<x_{2,i}$，$y_{1,i}<y_{2,i}$，$\{x_{i,j}|1\leq i\leq 2,1\leq j\leq n\}=\{y_{i,j}|1\leq i\leq 2,1\leq j\leq n\}=\{1,2,3,\cdots,2n\}$。

- Subtask 1（5 pts）：矩形之间互不相交。
- Subtask 2（20 pts）：$n\leq 13$。
- Subtask 3（20 pts）：$n\leq 200$。
- Subtask 4（25 pts）：$n\leq 2000$。
- Subtask 5（30 pts）：无特殊限制。


title: [集训队互测 2023] 虹

description:
给定一棵 $n$ 个点的树。

- 称点集 $S$ **连通**，当且仅当 $\forall u,v \in S$，所有 $u$ 到 $v$ 的简单路径上的点均在 $S$ 中。
- 称点集 $S$ 是 $[l,r]$ 的**虹**，当且仅当 $S$ **连通**，且 $S$ 包含 $[l,r]$ 中的所有点。
- 称点集 $S_0$ 是 $[l,r]$ 的**最小虹**，当且仅当 $S_0$ 是 $[l,r]$ 的所有**虹**中大小最小的。可以证明，$S_0$ 是唯一的。

点带权，点 $u$ 的权值为 $w_u$，初始所有点权均为 $0$。同时，给定序列 $\{z_1,z_2,\cdots,z_n\}$。

给定 $q$ 次命令，每次命令形如以下两类之一：

- `1 l r`：令 $S_0$ 为 $[l,r]$ 的**最小虹**，$\forall u \in S_0$，将 $w_u$ 加 $1$。
- `2 l r u`：求 $\left(\sum_{i=l}^r 19901991^{z_{\gcd(i,u)} w_i} \right) \bmod {20242024}$ 的值。

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

第二行 $n$ 个非负整数，依次表示 $z_1,z_2,\cdots,z_n$。

接下来 $n-1$ 行，每行两个正整数 $u,v$，描述一条树上从 $u$ 到 $v$ 的边。

最后 $q$ 行，每行 $3$ 或 $4$ 个正整数，描述一次命令。

**注意：本题输入文件行末有 `\r`，请选手自行过滤。**

outputFormat: 对于每次询问（即第二类命令）输出答案。


title: [集训队互测 2023] 树哈希

description:
这是一道 [模板题](https://uoj.ac/problem/763)。

给定正整数 $n,q,mod$。保证 $mod$ 是质数。

对于一棵以点 $1$ 为根的有根树 $T$，设 $s(T)$ 为这棵树中最多能选出多少个互不同构的子树（也就是这颗树本质不同的子树个数），那么这个树的权值 $w(T) = q^{s(T)}$。

对于所有 $1 \le m \le n$，输出所有大小为 $m$，根为 $1$ 的有标号树的权值之和对 $mod$ 取模后的值。

两棵有根树 $T_1$、$T_2$ 同构当且仅当他们的大小相等，且存在一个顶点排列 $\sigma$ 使得在 $T_1$ 中 $i$ 是 $j$ 的祖先当且仅当在 $T_2$ 中 $\sigma(i)$ 是 $\sigma(j)$ 的祖先。

inputFormat: 一行两个整数，表示 $n,q,mod$。

outputFormat: 输出 $n$ 行，第 $m$ 行表示 $m$ 个点的答案。

hint:
#### 样例解释 1

$n=3,q=2,mod=998244353$ 时，有三颗不同三个点的根为 $1$ 的有标号树，其中两颗满足 $w(T)=2^3$，另一颗满足 $w(T)=2^2$。因此答案为 $(2 \times 2^3+2^2) \bmod 998244353 = 20$。

#### 限制与约定

对于所有测试数据，保证 $n = 100, 10^8 \le mod \le 1.01 \times 10^9, 1 \le q < mod$，且 $mod$ 是质数。

本题共 $1$ 个子任务，每个子任务 $100$ 分。你在每个子任务中的得分为该子任务所有测试点的得分的最小值。

**你必须按照输出格式输出 $n$ 个数，但是你可以输出错误的答案**。如果你输出了 $c$ 个正确的答案，那么你获得的分数按照如下方式计算：

- 对于 $0 \le c \le 20$，你的得分为 $2c$ 分；
- 对于 $21 \le c \le 60$，你的得分为 $c + 20 $ 分。
- 对于 $61 \le c \le 100$，你的得分为 $\lfloor \frac{c}{2}\rfloor + 50$ 分。

时间限制：$\texttt{4s}$。
空间限制：$\texttt{2048MB}$。

你可以使用下面的代码来加速你的取模。

```cpp
struct fastmod {
  typedef unsigned long long u64;
  typedef __uint128_t u128;

  int m;
  u64 b;

  fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
  int reduce(u64 a) {
    u64 q = ((u128)a * b) >> 64;
    int r = a - q * m;
    return r < m ? r : r - m;
  }
} z(2);
void solve() {
	long long mod = 998244353, qwq = 1e9;
	z = fastmod(mod);
	cout << z.reduce(qwq) << ' ' << qwq % mod << '\n';
}
```


title: [GESP202312 一级] 小杨的考试

description: 今天是星期 $X$，小杨还有 $N$ 天就要考试了，你能推算出小杨考试那天是星期几吗？（本题中使用 $7$ 表示星期日）

inputFormat: 输入 $2$ 行，第一行一个整数 $X(1\le X \le 7)$；第二行一个整数 $N(1≤N≤364)$。

outputFormat: 输出一个整数，表示小杨考试那天是星期几。

hint:
**样例解释1**

今天是星期 1，那么 6 天后就是星期日，星期日在本题中用 $7$ 表示。

**样例解释2**

今天是星期 5，那么 3 天后就是星期 1。


title: [GESP202312 一级] 小杨报数

description:
小杨需要从 $1$ 到 $N$ 报数。在报数过程中，小杨希望跳过 $M$ 的倍数。例如，如果 $N=5$， $M=2$ ，那么小杨就需要依次报出 $1$、$3$、$5$。

现在，请你依次输出小杨报的数。

inputFormat: 输入 $2$ 行，第一行一个整数 $N（1 \le N \le 1,000）$；第二行一个整数 $M（2 \le M \le 100）$。

outputFormat: 输出若干行，依次表示小杨报的数。


title: [GESP202312 二级] 小杨做题

description:
为了准备考试，小杨每天都要做题。第 $1$ 天，小杨做了 $a$ 道题；第 $2$ 天，小杨做了 $b$ 道题；从第 $3$ 天起，小杨每天做的题目数量是前两天的总和。

此外，小杨还规定，当自己某一天做了大于或等于 $m$ 题时，接下来的所有日子里，他就再也不做题了。

请问，到了第 $N$ 天，小杨总共做了多少题呢？

inputFormat:
总共 $4$ 行。第一行一个整数 $a$，第二行一个整数 $b$，第三行一个整数 $m$，第四行一个整数 $N$。

保证 $0 \le a,b \le 10$；$a,b<M<1,000,000$；$3 \le N \le 364$。

outputFormat: 一行一个整数，表示小杨 $N$ 天里总共做了多少题目。

hint:
**样例解释 1**

小杨第一天做 $1$ 题，第二天做 $2$ 题，第三天做 $1+2=3$ 题，第四天做 $2+3=5$ 题，第五天做 $3+5=8$ 题。因此他总共做了 $1+2+3+5+8=19$ 题。

**样例解释 2**

小杨前 $5$ 天分别做了 $1,1,2,3,5$ 题，由于第 $5$ 天小杨做了 $5$ 题，而 $m=5$，于是小杨从此以后不再做题。因此小杨总共做了 $1+1+2+3+5=12$ 题。


title: [GESP202312 二级] 小杨的H字矩阵

background: 感谢 @[Present_Coming_Time](/user/793625) 提供的数据。

description:
小杨想要构造一个 $N \times N$ 的 H 字矩阵（$N$ 为奇数），具体来说，这个矩阵共有 $N$ 行，每行 $N$ 个字符，其中最左列、最右列都是 `|` ，而中间一行（即第$\frac{N+1}{2}$行）的第 $2 \sim N-1$ 个字符都是 `-` ，其余所有字符都是半角小写字母 `a`。例如，一个 $N=5$ 的 H 字矩阵如下：
```
|aaa|
|aaa|
|---|
|aaa|
|aaa|
```
请你帮小杨根据给定的 $N$ 打印出对应的“H 字矩阵”。

inputFormat: 一行一个整数 $N$（$5\le N \le 49$ ，保证 $N$ 为奇数）。

outputFormat:
输出对应的“H 字矩阵”。

请严格按格式要求输出，不要擅自添加任何空格、标点、空行等任何符号。你应该恰好输出 $N$ 行，每行除了换行符外恰好包含 $N$ 个字符，这些字符要么是 - ，要么是 | ，要么是 a 。**你的输出必须和标准答案完全一致才能得分，请在提交前仔细检查。**

samples:
|aaaaa|
|aaaaa|
|aaaaa|
|-----|
|aaaaa|
|aaaaa|
|aaaaa|


title: [GESP202312 三级] 小猫分鱼

description:
海滩上有一堆鱼，$N$ 只小猫来分。第一只小猫把这堆鱼平均分为 $N$ 份，多了 $i<N$ 个，这只小猫把多的 $i$ 个扔入海中，拿走了一份。第二只小猫接着把剩下的鱼平均分成 $N$ 份，又多了 $i$ 个，小猫同样把多的 $i$ 个扔入海中，拿走了一份。第三、第四、……，第 $N$ 只小猫仍是最终剩下的鱼分成 $N$ 份，扔掉多了的 $i$ 个，并拿走一份。

编写程序，输入小猫的数量 $N$ 以及每次扔到海里的鱼的数量 $i$，输出海滩上最少的鱼数，使得每只小猫都可吃到鱼。

例如：两只小猫来分鱼 $N=2$，每次扔掉鱼的数量为 $i=1$，为了每只小猫都可吃到鱼，可令第二只小猫需要拿走 $1$ 条鱼，则此时待分配的有 $3$ 条鱼。第一只小猫待分配的鱼有  $3\times 2+1=7$ 条。

inputFormat:
总共 $2$ 行。第一行一个整数 $N$，第二行一个整数 $i$。

保证 $0<N<10$；$i<N$ 。

outputFormat: 一行一个整数，表示满足要求的海滩上最少的鱼数。

hint:
**样例解释 2**

三只小猫来分鱼 $N=3$，每次扔掉鱼的数量为 $i=1$，为了每只小猫都可吃到鱼，可令第三只小猫需要拿走 $3$ 条鱼（拿走 $1$ 条和 $2$ 条不满足要求），则此时待分配的有 $10$ 条鱼。第二只小猫待分配的鱼有 $10×3/2+1 = 16$ 条。第一只小猫待分配的鱼有 $16×3/2+1 = 25$ 条。


title: [GESP202312 三级] 单位转换

description:
小杨这周的数学作业是做单位转换，喜欢编程的小杨决定编程帮他解决这些问题。

小杨只学了长度单位和重量单位，具体来说：

- 长度单位包括千米（`km`）、米（`m`）、毫米（`mm`），它们之间的关系是：$1\text{km} = 1000\text{m} = 1000000\text{mm}$。

- 重量单位包括千克（`kg`）、克（`g`）、毫克（`mg`），它们之间的关系是：$1\text{kg} = 1000\text{g} = 1000000\text{mg}$。

小杨的作业只涉及将更大的单位转换为更小的单位，也就是说，小杨的作业只会包含如下题型：米转换为毫米，千米转换为毫米，千米转换为米，克转换为毫克，千克转换为毫克，千克转换为克。

现在，请你帮忙完成单位转换的程序。

inputFormat:
输入的第一行为一个整数，表示题目数量。

接下来 $N$ 行，每行一个字符串，表示转换单位的题目，格式为 $x$ 单位 $1 = ?$ 单位 $2$。其中，$x$ 为一个不超过 $1000$ 的非负整数， 单位 $1$ 和 单位 $2$ 分别为两个单位的英文缩写，保证它们都是长度单位或都是重量单位，且 **单位 1** 比 **单位 2** 更大。

例如，如果题目需要你将 $1\text{km}$ 转换为 $\text{mm}$，则输入为 `1 km = ? mm`。

保证 $1\le N \le 1000$。

outputFormat:
输出 $N$ 行，依次输出所有题目的答案，输出时，只需要将输入中的 $?$ 代入答案，其余部分一字不差地输出即可。由于小杨的题目只涉及将更大的单位转换为更小的单位，并且输入的 $x$ 是整数，因此答案一定也是整数。

例如，如果题目需要你将 $1\text{km}$ 转换为 $\text{mm}$，则输入为 `1 km = ? mm`。则你需要输出 `1 km = 1000000 mm`。


title: [GESP202312 四级] 小杨的字典

description:
在遥远的星球，有两个国家 A 国和 B 国，他们使用着不同的语言：A 语言和 B 语言。小杨是 B 国的翻译官，他的工作是将 A 语言的文章翻译成 B 语言的文章。

为了顺利完成工作，小杨制作了一本字典，里面记录了 $N$ 个 A 语言单词对应的 B 语言单词，巧合的是，这些单词都
由地球上的 26 个小写英文字母组成。

小杨希望你写一个程序，帮助他根据这本字典翻译一段 A 语言文章。这段文章由标点符号 `!()-.[].{}\|;:'",./?<>` 和一些 A 语言单词构成，每个单词之间必定由至少一个标点符号分割，你的程序需要把这段话中的所有 A 语言单词替换成它的 B 语言翻译。特别地，如果遇到不在字典中的单词，请使用大写 UNK 来替换它。

例如，小杨的字典中包含 $2$ 个 A 语言单词 `abc` 和 `d`，它们的 B 语言翻译分别为 `a` 和 `def`，那么我们可以把 A 语言文章 `abc.d.d.abc.abcd.` 翻译成 B 语言文章 `a.def.def.a.UNK.` 其中，单词 `abcd` 不在词典内，因此我们需要使用 UNK 来替换它。

inputFormat:
第一行一个整数 $N$，表示词典中的条目数。保证  $N \le 100$。

接下来  $N$ 行，每行两个用单个空格隔开的字符串  $A$， $B$ ,分别表示字典中的一个 A 语言单词以及它对应的 B 语言翻译。保证所有 $A$ 不重复；保证 $A$ 和 $B$ 的长度不超过 $10$。

最后一行一个字符串 $S$ ，表示需要翻译的 A 语言文章。保证字符串 $S$ 的长度不超过 $1000$，保证字符串 $S$ 只包含小写字母以及标点符号 `!()-.[].{}\|;:'",./?<>` 。

outputFormat: 输出一行，表示翻译后的结果。

samples:
3
abc a
d def
abcd xxxx
abc,(d)d!-abc?abcd

samples:
1
abcdefghij klmnopqrst
!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz


title: [GESP202312 四级] 田忌赛马

description:
你要和田忌赛马。你们各自有 $N$ 匹马，并且要进行 $N$ 轮比赛，每轮比赛，你们都要各派出一匹马决出胜负。

你的马匹的速度分别为 $u_1,u_2,\cdots，u_n$，田忌的马匹的速度分别为 $v_1,v_2,\cdots,v_n$。田忌会按顺序派出他的马匹，请问你要如何排兵布阵，才能赢得最多轮次的比赛？巧合的是，你和田忌的所有马匹的速度两两不同，因此不可能出现平局。

inputFormat:
第一行一个整数 $N$。保证 $1\le N \le 5\times 10^4$

接下来一行 $N$ 个用空格隔开的整数，依次为 $u_1,u_2,\cdots,u_n$，表示你的马匹们的速度。保证 $1\le u_i\le 2N$。

接下来一行 $N$ 个用空格隔开的整数，依次为 $v_1,v_2,\cdots,v_n$，表示田忌的马匹们的速度。保证 $1\le v_i\le 2N$。

outputFormat: 输出一行，表示你最多能获胜几轮。

hint:
**样例解释 1**

第 1 轮，田忌派出速度为 2 的马匹，你可以派出速度为 3 的马匹迎战，本轮你获胜。

第 2 轮，田忌派出速度为 4 的马匹，你可以派出速度为 5 的马匹迎战，本轮你获胜。

第 3 轮，田忌派出速度为 6 的马匹，你可以派出速度为 1 的马匹迎战，本轮田忌获胜。

如此，你可以赢得 2 轮比赛。


title: [GESP202312 五级] 小杨的幸运数

description:
小杨认为，所有大于等于 $a$ 的完全平方数都是他的超级幸运数。

小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数，小杨规定，可以将它一直 $+1$，直到它变成一个幸运数。我们把这个过程叫做幸运化。例如，如果$a=4$，那么 $4$ 是最小的幸运数，而 $1$ 不是，但我们可以连续对 $1$ 做 $3$ 次 $+1$ 操作，使其变为 $4$，所以我们可以说， $1$幸运化后的结果是 $4$。

现在，小杨给出 $N$ 个数，请你首先判断它们是不是幸运数；接着，对于非幸运数，请你将它们幸运化。

inputFormat:
第一行 $2$ 个正整数 $a, N$。

接下来 $N$ 行，每行一个正整数 $x$ ，表示需要判断（幸运化）的数。

outputFormat: 输出 $N$ 行，对于每个给定的 $x$ ，如果它是幸运数，请输出 `lucky`，否则请输出将其幸运化后的结果。

samples:
16
16
16
16
lucky
lucky
lucky
lucky
lucky
lucky
lucky

hint:
**样例解释 1**

虽然是完全平方数，但它小于 $a$，因此它并不是超级幸运数，也不是幸运数。将其进行 $3$ 次 $+1$ 操作后，最终得到幸运数 $4$。4是幸运数，因此直接输出 `lucky` 。

$5$ 不是幸运数，将其进行 $3$ 次 $+1$ 操作后，最终得到幸运数 $8$。

$9$ 是幸运数，因此直接输出 `lucky` 。

**数据规模**

对于 $30\%$ 的测试点，保证 $a,x \le 100,N \le 100$。

对于 $60\%$ 的测试点，保证 $a,x \le 10^6$。

对于所有测试点，保证 $a \le 1,000,000$；保证 $N \le 2 \times 10^5$；保证 $1 \le x \le 1,000,001$。


title: [GESP202312 五级] 烹饪问题

description:
有 $N$ 种食材，编号从 $0$ 至 $N-1$，其中第 $i$ 种食材的美味度为 $a_i$。

不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为 $x$ 和 $y$ ，那么它们的契合度为 $x\ \text{and}\ y $。

其中，$\text{and}$ 运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足 ，再逐位进行与运算。例如，$12$ 与 $6$ 的二进制表示分别为 $1100$ 和 $0110$ ，将它们逐位进行与运算，得到 $0100$ ，转换为十进制得到 4，因此 $12 \text{and} 6 = 4$。**在 C++ 或 Python 中，可以直接使用 `&` 运算符表示与运算。**

现在，请你找到契合度最高的两种食材，并输出它们的契合度。

inputFormat:
第一行一个整数 $N$，表示食材的种数。

接下来一行 $N$ 个用空格隔开的整数，依次为 $a_1,\cdots,a_N$，表示各种食材的美味度。

outputFormat: 输出一行一个整数，表示最高的契合度。

hint:
**样例解释 1**

可以编号为 $1,2$ 的食材之间的契合度为 $2\ \text{and} \ 3=2$，是所有食材两两之间最高的契合度。

**样例解释 2**

可以编号为 $3,4$ 的食材之间的契合度为 $10\ \text{and}\ 13=8$，是所有食材两两之间最高的契合度。

**数据范围**

对于 $40\%$ 的测试点，保证 $N \le 1,000$；

对于所有测试点，保证 $N \le 10^6$，$0\le a_i \le 2,147,483,647$。


title: [GESP202312 六级] 闯关游戏

description:
你来到了一个闯关游戏。

这个游戏总共有 $N$ 关，每关都有 $M$ 个通道，你需要选择一个通道并通往后续关卡。其中，第 $i$ 个通道可以让你前进 $a_i$ 关，也就是说，如果你现在在第 $x$ 关，那么选择第 $i$ 个通道后，你将直接来到第 $x+a_i$ 关（特别地，如果 $x + a_i \geq N$，那么你就通关了）。此外，当你顺利离开第 $s$ 关时，你还将获得 $b_s$ 分。

游戏开始时，你在第 $0$ 关。请问，你通关时最多能获得多少总分。

inputFormat:
第一行两个整数 $N$，$M$，分别表示关卡数量和每关的通道数量。

接下来一行 $M$ 个用单个空格隔开的整数 $a_0,a_1\cdots,a_{M-1}$。保证 $1\le a_i \le N$。

接下来一行 $N$ 个用单个空格隔开的整数 $b_0,b_1\cdots,b_{N-1}$。保证 $|b_i|\le 10^5$。

outputFormat: 一行一个整数，表示你通关时最多能够获得的分数。

hint:
**样例解释 1**

你可以在第 $0$ 关选择第 $1$ 个通道，获得 $1$ 分并来到第 $3$ 关；随后再选择第 $0$ 个通道，获得 $100$ 分并来到第 $5$ 关；最后任选一个通道，都可以获得 $30$ 分并通关。如此，总得分为 $1+100+30=131$。

**样例解释 2**

请注意，一些关卡的得分可能是负数。

**数据范围**

对于 $20\%$ 的测试点，保证 $M=1$。

对于 $40\%$ 的测试点，保证 $N \le 20$；保证 $M\le 2$。

对于所有测试点，保证 $1 \le N \le 10^4$；保证 $1 \le M\le 100$。