title: 「EZEC-4」可乐

background:
很久以前，有一个 pigstd，非常迷恋美味的可乐。为了得到美味的可乐，他几乎用尽了所有的钱，他甚至对自己的 npy 也漠不关心~~其实是因为他没有npy~~，更不爱好看戏。除非买了新可乐，才会坐上马车出门炫耀一番。每一天，每个钟头他都要喝上一瓶新可乐。

pigstd 最近又买了许多箱新可乐——当然，这些可乐只有聪明的人才能喝到。

description:
pigstd 现在有 $n$ 箱可乐，第 $i$ 箱可乐上标着一个正整数 $a_{i}$。

若 pigstd 的聪明值为一个非负整数 $x$，对于第 $i$ 箱可乐，如果 $(a_{i} \oplus x )\le k$，那么 pigstd 就能喝到这箱可乐。

现在 pigstd 告诉了你 $k$ 与序列 $a$，你可以决定 pigstd 的聪明值 $x$，使得他能喝到的可乐的箱数最大。求出这个最大值。

inputFormat:
第一行两个由空格分隔开的整数 $n,k$。

接下来 $n$ 行，每行一个整数 $a_i$，表示第 $i$ 箱可乐上标的数。

outputFormat: 一行一个正整数，表示 pigstd 最多能喝到的可乐的箱数。

hint:
### 提示

**pigstd 的聪明值 $x$ 可以为 $0$。**

### 样例解释

样例 1 解释：容易构造当 $x = 0$ 时，可以喝到所有可乐。

样例 2 解释：容易构造 $x = 913$，可以喝到所有可乐。

**样例解释未必是唯一的方法。**

### 数据范围

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

- Subtask 1（29 points）：$1 \le n,k,a_{i} \le 1000$。

- Subtask 2（1 points）：$a_{i} \le k$。

- Subtask 3（70 points）：无特殊限制。

对于所有数据，保证 $1 \le n,k,a_{i} \le 10^6$。

$\oplus$ 代表异或，如果您不知道什么是异或，请单击[这里](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin)。


title: [CCC2020]  Swapping Seats

type: P

description:
有 $N$ 个人坐在一张**圆**桌旁。

共有三个派别，每一个人属于一个派别。

现在，您想使属于同一派别的人坐到一起。

您可以每次将两个人交换位置，输出最小的交换次数。

inputFormat:
仅一行一个长度为 $N$ 的字符串 $s$，为顺时针所有人的派别。

如果 $s_i$ 为 `A`，则说明第 $i$ 个人为第一个派别的，以此类推。

outputFormat: 仅一行一个整数，表示最小的交换次数。

hint:
#### 样例解释
$\texttt{BABCBCACCA}\to\texttt{AABCBCBCCA}\to\texttt{AABBBCCCCA}$。

#### 子任务
**本题采用捆绑测试，且本题的 Subtask 分数有微调。**
- Subtask 1（$26$ 分）：$s_i\in\{$`A`$,$`B`$\}$ 且 $N\le 5\times 10^3$。
- Subtask 2（$27$ 分）：$s_i\in\{$`A`$,$`B`$\}$。
- Subtask 3（$27$ 分）：$N\le 5\times 10^3$。
- Subtask 4（$20$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $s_i\in\{$`A`$,$`B`$,$`C`$\}$，$1\le N\le 10^6$。

#### 说明
本题译自 [Canadian Computing Competition 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Senior](https://cemc.math.uwaterloo.ca/contests/computing/2020/ccc/seniorEF.pdf) T4 Swapping Seats。


title: [省选联考 2020 B 卷] 卡牌游戏

description:
轩轩某天想到了一个卡牌游戏，游戏规则如下：

1. 初始时轩轩的手中有自左向右排成一排的 $n$ 张卡牌，每张卡牌上有一个整数分值。
2. 接下来，轩轩每次可以选取卡牌序列最左边的连续若干张卡牌（至少 $2$ 张），将它们替换为一张新卡牌。新卡牌将插入到序列的最左端，它的分值为本次操作中被替换掉的卡牌的分值之和。
3. 初始时轩轩总分为 $0$，每执行一次卡牌替换操作，新卡牌的分值将加到总分中。当序列长度为 $1$ 时游戏结束，轩轩也可以在任意时刻结束游戏。

现在给出序列中各个卡牌的分值，请你来帮助轩轩计算他能够获得的最高总分是多少？

inputFormat:
第一行一个正整数 $n$，代表卡牌的数目。

接下来一行 $n$ 个以空格分隔的整数，第 $i$ 个数字 $a_i$ 代表自左向右第 $i$ 张卡牌的分值。

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

hint:
**样例解释 1**

最优策略为，首先选择最左侧的两张卡牌，总分增加 $2 + (-1) = 1$。此时轩轩选择的两张卡牌被替换为一张分值为 $1$ 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 $1$ 和 $2$。

接下来选择当前序列中所有卡牌，总分增加 $1 + 2 = 3$，总分为 $4$。此时轩轩选择的两张卡牌被替换为一张分值为 $3$ 的卡牌，且被放入序列最左侧，此时序列中只有一张分值为 $3$ 的卡牌，游戏结束。

**样例解释 2**

最优策略为，首先选择最左侧的四张卡牌，总分增加  $(-4) + 3 + 0 + 7 = 6$。此时轩轩选择的四张卡牌被替换为一张分值为6 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 $6, -3, -5, -3$。

再选择最左侧的两张卡牌，总分增加 $6 + (-3) = 3$，总分为 $9$。此时轩轩选择的两张卡牌被替换为一张分值为 $3$ 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 $3, -5, -3$。

此时无论如何操作均无法使总分继续增大，轩轩选择结束游戏。

**数据范围与约定**

测试点 $1 \sim6 $ 满足：$1\le n\le 16, |a_i| \le 100$。

测试点 $7 \sim 12$ 满足：$1\le n\le 10^3, |a_i| \le 100$。

测试点 $13 \sim 20$ 满足：$1\le n\le 10^5, |a_i| \le 10^5$。


title: [省选联考 2020 B 卷] 消息传递

description:
给定一个包含 $n$ 个人（从 $1$ 到 $n$ 编号）的树形社交网络。如果一个人在某天收到了一条消息，则下一天他会将消息传递给所有与他有直接社交关系的人。

现在有 $m$ 次询问，每次询问假定第 $0$ 天 $x$ 号人收到了一条消息，请你计算第 $k$ 天时新收到此条消息的人数（即第 $k$ 天前收到过此条消息的人不计入其中）。不同询问间互不影响。

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

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

对于每组测试数据：

第一行两个数 $n,m$ 分别表示树形社交网络的人数和询问的数量。

接下来 $n - 1$ 行，每行两个数 $a, b$，表示 $a$ 号人和 $b$ 号人之间有直接社交关系。保证输入的是树形社交网络。

接下来 $m$ 行，每行两个数 $x, k$，意义见题目描述。

outputFormat: 对于每组测试数据：输出 $m$ 行，每行一个数表示询问的答案。

hint:
**样例解释**

第一个询问，第一天新收到消息的人只有 $2$ 号。
第二个询问，第一天新收到消息的人有 $1$、$3$ 号，第二天新收到消息的人有 $4$ 号。

**数据范围与约定**

对于测试点 $1$：$1\le n, m\le 10$。
对于测试点 $2$：$1\le n, m\le 100$。
对于测试点 $3$：$1\le n, m\le 1000$。
对于测试点 $4\sim6$：$1\le n, m\le 10^5, k\le 20$。
对于测试点 $7\sim10$：$1\le n, m\le 10^5$。
对于所有测试点：$1\le T\le 5, 1\le x\le n, 0\le k < n$。


title: [省选联考 2020 B 卷] 幸运数字

description:
为庆祝疫情防治取得重大进展，某商场举行酬宾活动，给顾客一些优惠额度，规则如下：

1. 每位顾客可以任意选择一个整数作为自己的幸运数字。
2. 每位顾客的初始优惠额度为 $0$ 元。
3. 商场有 $n$ 个奖励条件，对应不同的奖励额度 $w_i$。
4. 每位顾客需要依次比对这 $n$ 个奖励条件，如果该位顾客选择的幸运数字满足第 $i$ 个条件，那么他的优惠额度就会**异或**上这个条件所对应的奖励额度。

奖励条件共有三种，假设顾客选择的幸运数字为 $x$：

1. 区间型条件，其有两个参数 $L$ 与 $R$，满足条件为 $L \le x\le R$。保证 $L < R$。
2. 相等型条件，其有一个参数 $A$，满足条件为 $x = A$。
3. 不等型条件，其有一个参数 $B$，满足条件为 $x \neq B$。

小炎同学获知了所有奖励条件的信息，他希望知道一位顾客能够得到的最大优惠额度以及对应的幸运数字是多少，请你帮他计算。

inputFormat:
第一行包含一个正整数 $n$，代表奖励条件的数量。

接下来 $n$ 行，每行三个或四个整数表示一个奖励条件。每行第一个整数 $t_i$ 代表奖励条件的类型：

1. $t_i = 1$ 则该条件是区间型条件，接下来三个整数，分别代表 $L, R, w_i$。
2. $t_i = 2$ 则该条件是相等型条件，接下来两个整数，分别代表 $A, w_i$。
3. $t_i = 3$ 则该条件是不等型条件，接下来两个整数，分别代表 $B, w_i$。

outputFormat:
输出一行两个整数，第一个数代表能够得到的最大优惠额度，第二个数代表对应的幸运数字。

如果有多个幸运数字能够得到最大优惠额度，输出绝对值最小的那个。如果还有多个，则输出值最大的。


title: [省选联考 2020 B 卷] 丁香之路

description:
春暖花开，万物复苏，随着疫情的逐渐过去，Yazid 带着他的 $n$ 个好朋友来到 T 大校园参观游览。方便起见，我们将他们从 $1$ 至 $n$ 编号。

T 大校园的版图可以抽象成一张 $n$ 个顶点的无向图（顶点编号从 $1$ 至 $n$）。且对于任意两个不同顶点，设它们的编号分别为 $i, j(i\neq j)$，则它们之间有一条需要花费 $|i - j|$ 单位时间通过的无向边。

丁香花是 T 大的校花之一。时下正值丁香花盛开之际，校园内的 $m$ 条道路上都开有丁香花。Yazid 的朋友们对丁香花十分感兴趣，因此他们都希望遍历**所有**开有丁香花的 $m$ 条道路。

Yazid 的朋友们从顶点 $s$ 出发。其中，第 $i$ 个朋友希望以顶点 $i$ 为终点终止他的参观。与此同时，如上面所述，每个朋友都必须经过开着丁香花的 $m$ 条道路各至少一次。

Yazid 的朋友不想太过疲累，因此他们希望花尽可能少的时间来完成他们的目标。

请你计算 Yazid 的朋友们分别需要花费多少单位时间完成他们的目标。

inputFormat:
第一行 $3$ 个非负整数 $n, m, s$。保证 $1\le s\le n$；保证 $m\le \frac {n(n-1)}2$。

第 $2$ 行至第 $m+1$ 行，每行 $2$ 个整数 $u, v$，描述一条开有丁香花的，连接顶点 $u, v$ 的无向边。保证 $1\le u, v\le n$ 且 $u\neq v$；保证每条无向边至多被描述一次。

对于输入的所有行，用单个空格将行内的多个整数隔开。

outputFormat: 输出一行 $n$ 个用单个空格隔开的整数，其中第 $i$ 个整数描述 Yazid 的第 $i$ 个朋友完成目标所需花费的最少时间。


title: [CCC2020] Josh's Double Bacon Deluxe

background: Josh 和 $N-1$ 个人去吃汉堡。

description:
这个汉堡店共有 $M$ 种汉堡。

第 $i$ 个人最喜欢吃的汉堡为第 $b_i$ 种汉堡。

这 $N$ 个人都会选他最喜欢吃的汉堡。

现在，这 $N$ 个人排队去取汉堡，不幸的是，第一个人忘记了他最喜欢的汉堡，于是他随便拿了一个汉堡。

接下来的 $N-2$ 个人会按如下规则拿汉堡：
- 如果有他最喜欢的汉堡，就直接拿走。
- 否则，他会随便拿一个。

您需要求出，**排在最后**的 Josh 拿到他最喜欢汉堡的概率。

inputFormat:
第一行为一个整数 $N$。

接下来 $N$ 行，一行一个整数 $b_i$。

outputFormat: 一行一个小数，表示**排在最后**的 Josh 拿到他最喜欢汉堡的概率。

hint:
#### 样例 1 解释
| 第一个人的选择 | 第二个人的选择 | Josh 的选择 | 概率 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $2$ | $3$ | $\frac{1}{3}$ |
| $2$ | $1$ | $3$ | $\frac{1}{3}\times \frac{1}{2}=\frac{1}{6}$ |
| $2$ | $3$ | $1$ | $\frac{1}{6}$ |
| $3$ | $2$ | $1$ | $\frac{1}{3}$ |

Josh 拿到他最喜欢汉堡的概率为 $\frac{1}{3}+\frac{1}{6}=\frac{1}{2}$。

#### SPJ 计分标准
设正确答案为 $C$，你的答案为 $P$，若 $\lvert P-C\rvert <10^{-6}$，则您得该测试点的满分，否则，您得零分。

#### 子任务
**本题采用捆绑测试，且本题的 Subtask 分数有微调。**
- Subtask 1（$27$ 分）：保证 $N\le 10^5$，$M\le 10^3$。
- Subtask 2（$33$ 分）：保证 $M\le 10^3$。
- Subtask 3（$40$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $3\le N\le 10^6$，$1\le b_i\le M\le 5\times 10^5$。

#### 说明
本题译自 [Canadian Computing Competition 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Senior](https://cemc.math.uwaterloo.ca/contests/computing/2020/ccc/seniorEF.pdf) T5 Josh's Double Bacon Deluxe。


title: [省选联考 2020 A/B 卷] 信号传递

description:
一条道路上从左至右排列着 $m$ 个信号站，初始时从左至右依次编号为 $1,2,\dots,m$，相邻信号站之间相隔 $1$ 单位长度。每个信号站只能往它右侧的任意信号站传输信号（称为普通传递），每单位长度距离需要消耗 $1$ 单位时间。道路的最左侧有一个控制塔，它在最左侧信号站的左侧，与其相隔 $1$ 单位长度。控制塔能与任意信号站进行双向信号传递（称为特殊传递），但每单位长度距离需要消耗 $k$ 个单位时间。对于给定的长度为 $n$ 的信号传递序列 $S$，传递规则如下：

1. 共 $n-1$ 次信号传递，第 $i$ 次信号传递将把信号从 $S_i$ 号信号站传递给 $S_{i+1}$ 号。
2. 若 $S_{i+1}$ 号信号站在 $S_i$ 号右侧，则将使用普通传递方式，从 $S_i$ 号直接传递给 $S_{i+1}$ 号。
3. 若 $S_{i+1}$ 号信号站在 $S_i$ 号左侧，则将使用特殊传递方式，信号将从 $S_i$ 号传递给控制塔，再由控制塔传递给 $S_{i+1}$ 号。
4. 若 $S_i=S_{i+1}$，则信号无须传递。

阿基作为大工程师，他能够任意多次交换任意两个信号站的位置，即他能够重排信号站的顺序，这样会使得 $S$ 消耗的传递时间改变。现在阿基想知道，在他重排信号站顺序后，$S$ 所消耗的传递时间最小能是多少。

inputFormat:
第一行三个整数 $n,m,k$，分别代表信号传递序列 $S$ 的长度，信号站个数，特殊传递单位长度距离的时间消耗。

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

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

hint:
【样例解释 $1$】

信号站顺序保持不变，两次使用普通传递方式，时间消耗为 $1+1=2$。

【样例解释 $2$】

对于排列 $1,2,3$，传递时间为 $1+1+(3\times 1+1\times 1)=6$。

对于排列 $1,3,2$，传递时间为 $2+(3\times 1+2\times 1)+(2\times 1+1\times 1)=10$。

对于排列 $2,1,3$，传递时间为 $(2\times 1+1\times 1)+2+(3\times 1+2\times 1)=10$。

对于排列 $2,3,1$，传递时间为 $(3\times 1+1\times 1)+1+1=6$。

对于排列 $3,1,2$，传递时间为 $1+(3\times 1+1\times 1)+1=6$。

对于排列 $3,2,1$，传递时间为 $(3\times 1+2\times 1)+(2\times 1+1\times 1)+2=10$。

【数据范围】

$30\%$ 的数据：$m\leq 8, n\leq 100$。

$60\%$ 的数据：$m\leq 20$。

$70\%$ 的数据：$m\leq 21$。

$80\%$ 的数据：$m\leq 22$。

$100\%$ 的数据：$2\leq m\leq 23$，$2\leq n\leq 10^5$，$1\leq k\leq 100$，$1\leq S_i\leq m$。


title: [省选联考 2020 A 卷] 树

description:
给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。

设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots,c_k$，定义 $x$ 的价值为：

$
val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))
$

其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$\oplus$ 表示异或运算。

请你求出 $\sum\limits_{i=1}^n val(i)$ 的结果。

inputFormat:
第一行一个正整数 $n$ 表示树的大小。

第二行 $n$ 个正整数表示 $v_i$。

接下来一行 $n-1$ 个正整数，依次表示 $2$ 号结点到 $n$ 号结点，每个结点的父亲编号 $p_i$。

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


title: [省选联考 2020 A 卷] 作业题

description:
小 W 刚刚在离散数学课学习了生成树的知识：一个无向图 $G=(V,E)$ 的生成树 $T$ 为边集 $E$ 的一个大小为 $|V|-1$ 的子集，且保证 $T$ 的生成子图在 $G$ 中连通。

小 W 在做今天的作业时被这样一道题目难住了：

给定一个 $n$ 个顶点 $m$ 条边（点和边都从 $1$ 开始编号）的无向图 $G$，保证图中无重边和无自环。每一条边有一个正整数边权 $w_i$，对于一棵 $G$ 的生成树 $T$，定义 $T$ 的价值为：$T$ 所包含的边的边权的最大公约数乘以边权之和，即：

$$
val(T)=\left(\sum\limits_{i=1}^{n-1} w_{e_i}\right) \times \gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}})
$$

其中 $e_1,e_2,\dots,e_{n-1}$ 为 $T$ 包含的边的编号。

小 W 需要求出 $G$ 的所有生成树 $T$ 的价值之和，他做了很久也没做出来，请你帮帮他。由于答案可能很大，你只需要给出答案对 $998244353$ 取模后的结果。

inputFormat:
第一行两个正整数 $n,m$，表示 $G$ 的点数和边数。

接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，第 $i$ 行表示一条无向边连接 $u_i$ 号点和 $v_i$ 号点，权值为 $w_i$。

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


title: 「Wdsr-2」环

description:
Kagamine Rin 有一个圆环，上面均匀分布着 $n$ 个点，这些点之间连接着 $m$ 条线段。

突然有一天，这些线段全都不见了。

Rin 想要找回这些线段，但是她不记得线段的分布。她只记得，这些线段中任意两条都不相交。

**注意：只在端点处相交不算相交；重合不算相交。** 下面的样例解释有助于理解本题中的定义。

Rin 有时还会记得一些额外的信息，她可能还会告诉你每个点上连接的线段数。

现在 Rin 想要知道，符合她的记忆的方案数有多少种。由于结果可能很大，你只需要输出答案对 $1000000007$ 取模的结果（模数是一个质数）。

inputFormat:
第一行输入三个整数 $n,m,type$。

如果 $type=1$，接下来一行输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个点上连接的线段数。数据保证 $\sum_{i=1}^na_i=2m$。

outputFormat: 输出只有一个整数，表示合法的方案数对 $1000000007$ 取模的结果。


title: [YsOI2020] 造林

background:
「承前」

Ysuperman 响应号召，决定在幼儿园外造林。

呐呐，如果这样的话，Ysuperman 便能在这炎热的夏天与小朋友们玩游戏了呢。

description:
为了落实环保工作，Ysuperman 购进了一批树，它们都长一个样。由于树还没有种下去，所以这些树还没有根，可以认为是**无根树**。

Ysuperman 觉得全都种长得一样的树太无聊了，于是 TA 请到了园艺公司帮 TA 规划。园艺公司提供给了 TA 一个方法——「嫁接」。

下面给出「嫁接」操作的定义：

定义「叶子节点」为树上度数为 $1$ 的节点。

「嫁接」操作指：在一棵**无根树**上接入一个新的「叶子节点」。

例如：
![](https://cdn.luogu.com.cn/upload/image_hosting/jfaksqwy.png)

图 2 是由图 1 的树进行一次合法的嫁接操作后得到的树，图 3 也是由图 1 的树进行一次合法的嫁接操作后得到的树。

那么，我们还知道，树有一个基本属性：「品种」。

一棵树的「品种」是指**每个点的最大子树大小所构成的可重集**。

两棵树的「品种」不同，当且仅当**每个点的最大子树大小所构成的可重集不同**。

这里的一个点的**最大子树大小**指将这个点删掉后**最大的联通块所包含的点数**。

例如：
![](https://cdn.luogu.com.cn/upload/image_hosting/zzyznfl7.png)

图 4 的树的每个点的最大子树大小所构成的可重集为：$ \{ 2,2,3,3 \} $
图 5 的树的每个点的最大子树大小所构成的可重集为：$ \{ 2,2,3,3 \} $
图 6 的树的每个点的最大子树大小所构成的可重集为：$ \{ 1,3,3,3 \} $
所以说，图 4 的树与图 5 的树「品种」相同，与图 6 的树「品种」不同。

Ysuperman 想知道，通过一次「嫁接」操作，可以构造出的树包含多少不同的「品种」，以及对于每个「品种」，有多少不同的「嫁接」方法可以构造。请**从小到大**输出每个「品种」的「嫁接」方法数。

两个「嫁接」方案不同，当且仅当在「嫁接」操作中与新接入的「叶子节点」直接相连的点不同。

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

outputFormat:
第一行一个数 $cnt$，表示可以构造出的树包含多少不同的「品种」。
第二行到第 $cnt+1$ 行，**从小到大**输出每个「品种」的「嫁接」方法数。

hint:
**本题采用捆绑测试。**
### 样例解释 1
可以构造出 1 种「品种」为 $\{2,4,4,5,5,5\}$ 的树。
可以构造出 2 种「品种」为 $\{3,3,4,5,5,5\}$ 的树。
可以构造出 2 种「品种」为 $\{3,3,4,4,5,5\}$ 的树。
### 样例解释 2
可以构造出 1 种「品种」为 $\{3,5,5,7,7,7,7,7\}$ 的树。
可以构造出 2 种「品种」为 $\{4,4,5,7,7,7,7,7\}$ 的树。
可以构造出 4 种「品种」为 $\{4,4,5,6,7,7,7,7\}$ 的树。

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

定义「链」为所有节点度数不超过 $2$ 的树。
定义「菊花」为包含 $n-1$ 个「叶子节点」的树。

特殊性质 1：保证树的形态为一条「链」。
特殊性质 2：保证树的形态为一朵「菊花」。
特殊性质 3：保证树的形态为一棵完全二叉树。

| subtask | $n$ | 特殊性质 | 分值 | 时间限制 |
| :-----------: | :-----------: | :-----------: | :--------:| :---------:|
| 1 | $\le 2\cdot 10^6$ | 2 | 2 | 4s |
| 2 | $\le 2\cdot 10^6$ | 1 | 3 | 4s |
| 3 | $\le 300$ | 无 | 5 | 1s |
| 4 | $\le 2\cdot10^6$ | 3 | 7 | 4s |
| 5 | $\le 5000$ | 无 | 23 | 1s |
| 6 | $\le 5\cdot10^4$ | 无 | 29 | 2s |
| 7 | $\le 2\cdot10^6$ | 无 | 31 | 4s |

### 提示：

如果你不知道完全二叉树是什么意思，Ysuperman 提供了一个链接：[Link](https://zh.wikipedia.org/zh/%E4%BA%8C%E5%8F%89%E6%A0%91#%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91)。

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

如果您使用了所需栈空间较大的递归算法，可以在本地（NOI linux 下）先使用 ```sudo su``` 获取权限，再使用 ```ulimit -s unlimited ``` 命令开启无限栈。

题目并不难。


title: [ZJOI2020] 字符串

description:
Bob 喜欢字符串。

Bob 觉得，重复两遍的字符串是优美的，例如，`aa`，`sese`，`abcabc`，`baabaa`，`abababab`是优
美的串，而 `ab`，`aadead`，`sesese`，`abba` 不是。更具体地说，如果一个字符串 $S$ 能够被写成两个相同的字符串前后拼接的形式，即存在字符串 $P$ 使得 $S=PP$，那么 $S$ 就是优美的。

Bob 有一个长度为 $n$ 的字符串 $T=T_1T_2 \cdots T_n$。现在他想知道，给定 $T$ 的一个子串 $Q=T[l \cdots r]$，这个子串 $Q$ 内一共包含多少种本质不同的优美的串作为子串。如果两个串相同，但是出现的位置不同，那么这两个串不是本质不同。

Bob 一共有 $q$ 组不同的询问，你需要快速计算出答案。

inputFormat:
第一行输入两个整数 $n, q$。第二行输入一个只包含小写字母 $a$ 和 $b$ 的字符串 $T$。

接下来 $q$ 行，每行输入两个整数 $l, r$，表示一组询问。

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

hint:
样例解释 $1$：

$|T|$ 有 `aa`，`aaaa`，`abaaba`，`aabaab`，`baabaa` 这些本质不同的优美的串。

样例输入输出 2 见附件。

对于前 $10\%$ 的数据，$n \leq 100$。

对于前 $20\%$ 的数据，$n \leq 500$。

对于前 $40\%$ 的数据，$n \leq 5000$。

对于另外 $20\%$ 的数据，保证 $T$ 中所有的优美的串的个数不超过 $10^6$，这里位置不同的串被视为不同的。

对于另外 $20\%$ 的数据，$q = 1$。

对于 $100\%$ 的数据，$1 \leq n, q \leq 200000,1 \leq l \leq r \leq n$，$T$ 只包含小写字母 `a` 和 `b`。


title: [ZJOI2020] 传统艺能

description:
Bob 喜欢线段树。

众所周知，ZJOI 的第二题有很多线段树。

Bob 有一棵根为 $[1, n]$ 的广义线段树。Bob 需要在这个线段树上执行 $k$ 次区间懒标记操作，每次操作会等概率地从 $[1, n]$ 的所有 $\dfrac{n(n+1)}{2}$ 个子区间中随机选择一个。对于所有在该次操作中被访问到的非叶子节点，Bob 会将这个点上的标记下推；而对于所有叶子节点（即没有继续递归的节点），Bob 会给这个点打上标记。

Bob 想知道，$k$ 次操作之后，有标记的节点的期望数量是多少。

【具体定义】

线段树：线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是 $[1, n]$。对于每个节点，若它记录的线段是 $[l, r]$ 且 $l \neq r$，取 $m = \lfloor \dfrac{l+r}{2} \rfloor$，则它的左右儿子节点记录的线段分别是 $[l, m]$ 和 $[m + 1, r]$；若 $l = r$，则它是叶子节点。

广义线段树：在广义的线段树中，$m$ 不要求恰好等于区间的中点，但是 $m$ 还是必须满足 $l \leq m < r$ 的。不难发现在广义的线段树中，树的深度可以达到 $O(n)$ 级别。

线段树的核心是懒标记，下面是一个带懒标记的广义线段树的伪代码，其中 `tag` 数组为懒标记：

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

注意，在处理叶子节点时，一旦他获得了一个标记，那么这个标记会一直存在。

你也可以这么理解题意：有一棵广义线段树，每个节点有一个 $m$ 值。一开始 `tag` 数组均为 $0$，Bob 会执行 $k$ 次操作，每次操作等概率随机选择区间 $[l, r]$ 并执行 `MODIFY(root,1,n,l,r);`。
最后所有 `Node` 中满足 `tag[Node]=1` 的期望数量就是需要求的值。

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

接下来输入一行包含 $n - 1$ 个整数 $a_i$：按照先序遍历的顺序，给出广义线段树上所有非叶子节点的划分位置 $m$。你也可以理解为从只有 $[1, n]$ 根节点开始，每次读入一个整数后，就将当前包含这个整数的节点做一次拆分，最后获得一棵有 $2n - 1$ 个节点的广义线段树。

保证给定的 $n - 1$ 个整数是一个排列，不难发现通过这些信息就能唯一确定一棵 $[1, n]$ 上的广义线段树。

outputFormat: 输出一行一个整数，代表期望数量对 $p = 998244353$ 取模后的结果。即，如果期望数量的最简分数表示为 $\dfrac{a}{b}$，你需要输出一个整数 $c$ 满足 $c \times b \equiv a \pmod p$。


title: [ZJOI2020] 序列

description:
Bob 喜欢序列。

有一个长度为 $n$ 的非负整数序列 $a_1, a_2,\cdots, a_n$。每一步你可以从以下三种操作中选择一种执行：

- 选择一个区间 $[l, r]$，将下标在这个区间里的所有数都减 $1$。

- 选择一个区间 $[l, r]$，将下标在这个区间里且下标为奇数的所有数都减 $1$。

- 选择一个区间 $[l, r]$，将下标在这个区间里且下标为偶数的所有数都减 $1$。

求最少需要多少步才能将序列中的所有数都变成 $0$。

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

对于每组数据，第一行输入一个整数 $n$，接下来一行输入 $n$ 个非负整数 $a_1, a_2,\dots, a_n$。

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

hint:
样例解释 $1$

第一组数据：$21212 \stackrel{1}{\longrightarrow} 1111 1 \stackrel{1}{\longrightarrow} 00000$

第三组数据：$1145141919810 \stackrel{1}{\longrightarrow} 0034030808700 \stackrel{8}{\longrightarrow} 0031000000700 \stackrel{10}{\longrightarrow}0000000000000$

样例输入输出 $2$ 见下发文件

对于前 $10\%$ 的数据，$n \leq 5, a_i \leq 10$。

对于前 $30\%$ 的数据，$n \leq 50, a_i \leq 50$。

对于前 $50\%$ 的数据，$n \leq 200, a_i \leq 200$。

对于前 $60\%$ 的数据，$n \leq 200, a_i \leq 10^9$。

对于前 $70\%$ 的数据，$n \leq 1000, a_i \leq 10^9$。

对于前 $90\%$ 的数据，$n \leq 10000, a_i \leq 10^9$。

对于 100% 的数据，$1 \leq n \leq 100000, 0 \leq ai \leq 10^9, 1 \leq T \leq 10$。


title: [SNOI2020] 生成树

description: 给定无向连通图 $G$，已知 $G$ 在删掉一条边后是一颗仙人掌（仙人掌：不存在两个拥有公共边的简单环的无向联通图），求 $G$ 的生成树个数。结果对 $998244353$ 取模。

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

接下来 $m$ 行，每行两个用空格分隔的正整数 $u,v(1 \le u,v  \le n)$，表示边 $(u,v)\in G$。

outputFormat: 输出一行一个整数，表示图 $G$ 的生成树个数对 $998244353$ 取模的结果。

hint:
对于所有数据，$1 \le n \le m \le2 \times 10^5$。

- 对于 $10\%$ 的数据，$1 \le n=m \le 2000$。
- 对于另外 $40\%$ 的数据，$1 \le n,m \le 10^5$ 且 $G$ 本身是仙人掌。
- 对于余下 $50\%$ 的数据，无特殊限制。


title: [SNOI2020] 取石子

description: 甲乙两个人玩取石子游戏。他们面前有一堆共 $n$ 个石子，然后由甲先手，两人轮流从中取走石子：甲第一次取走的个数不能超过 $k$，接下来每个人取走的个数不能超过上一个人刚刚取走个数的 $2$ 倍。每人每次必须至少取一个石子。取走最后一个石子的人失败，另一方获胜。现在已知 $k$，请你求出在 $1$ 到 $N$ 中有多少整数 $n$ 使得甲在 $n$ 颗石子的游戏中有必胜策略。

inputFormat:
**多组数据。**

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

接下来 $T$ 行每行两个用空格隔开的整数 $k,N$，表示一组询问。

outputFormat: 输出 $T$ 行，按照输入顺序，每行一个整数表示答案。

hint:
#### 样例说明

对于样例 $1$，当 $k=1$ 时：

- 如果 $n=1$，甲只能取走唯一一颗石子从而失败。
- 如果 $n=2$，甲取走一颗石子，乙只能取走最后一颗石子，甲获胜。
- 如果 $n=3$，甲只能取走一颗石子，乙再取走一颗石子，甲只能取走最后一颗石子从而失败。
- 如果 $n=4$，甲只能取走一颗石子，乙再取走两颗石子，甲只能取走最后一颗石子从而失败。
- 如果 $n=5$，甲只能取走一颗石子，乙只能取走一颗或两颗石子，甲总能再留给乙留下最后一颗石子从而获胜。

#### 数据说明与提示

对于所有数据，$1 \le T \le 10^5,k,N \le 10^{18}$。

- 对于 $10\%$ 的数据，$T,N \le 500$。
- 对于另外 $20\%$ 的数据，$T,N \le 10^5$。
- 对于另外 $20\%$ 的数据，$T \le 3,N \le 3 \times 10^6$。
- 对于另外 $20\%$ 的数据，$k=1$。
- 对于余下 $30\%$ 的数据，无特殊限制。


title: [SNOI2020] 区间和

description:
有一个长度为 $n$ 的整数数列 $a_1,a_2,\cdots,a_n$（可能含有负数）。现在对其进行 $q$ 次操作，每次操作是以下二者之一：

- `0 l r x` 表示对于 $[l,r]$，将 $a_i$ 赋值为 $\max(a_i,x)$；
- `1 l r` 求区间 $[l,r]$ 的最大子段和。即：$\max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))$。

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

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 表示初始的序列；

接下来 $q$ 行，每行形如 `0 l r x` 或 `1 l r` 表示一次操作。

outputFormat: 对于每个形如 `1 l r` 的操作，输出一行一个整数表示答案。

hint:
#### 样例说明

对于样例 $1$：

- 第 $1$ 次询问时序列为 $2,-4,6,-5,5$，最大子段和为 $6$；
- 第 $2$ 次询问时序列为 $2,-4,6,-4,5$，最大子段和为 $7$；
- 第 $3$ 次询问时序列为 $2,-4,6,-1,5$，最大子段和为 $10$；
- 第 $4$ 次询问时序列为 $2,-1,6,-1,5$，最大子段和为 $11$。

#### 数据规模与约定

对于所有数据，$1\le n\le10^5, 1\le q\le 2\times 10^5, |a_i|, |x|\le 10^9$。

- 对于 $10\%$ 的数据，$n,q \le 200$；
- 对于另外 $10\%$ 的数据，$n,q \le 2000$；
- 对于另外 $25\%$ 的数据，每次操作 $0$ 均满足 $l=r$（即，只有单点修改）；
- 对于另外 $20\%$ 的数据，每次操作 $1$ 均满足 $l=1,r=n$（即，只有全局询问）；
- 对于余下 $35\%$ 的数据，无特殊限制。

**有来自出题人的 3 个 hack 数据点**


title: [COCI2019-2020#2] Popcount

background: Miniature Algebraic Natural Relay 是小型可编程设备的最新技术进步。 您可以使用 MalnarScript 为此设备编写自己的程序。

description:
程序要求如下：

- 程序的输入是一个严格小于 $2^n$ 的单个非负整数。
- 程序的输出是一个严格小于 $2^n$ 的单个非负整数。
- 使用 MalnarScript 进行编程时，您只能使用一个 $n$ 位无符号整数变量 $a$。在程序的开头，此变量保存输入，并且其在程序末尾的值被视为程序的输出。
- MalnarScript 的源代码最多必须包含 $k$ 个格式为 $\texttt{a = <expr>}$ 的命令，这些命令按顺序执行，并且每个命令最多包含 $10^3$ 个字符。

符号 $\texttt{<expr>}$ 的递归定义如下：

$$\texttt{<expr> = A | <num> | (<expr><operator><expr>)}$$

换句话说，符号 $\texttt{<expr>}$ 可以是变量 $a$ ，也可以符合符号 $\texttt{<num>}$ 的定义，或者在括号内表示二元表达式，其中每个操作数均符合相同的 $\texttt{<expr>}$ 定义。

上面定义中的符号 $\texttt{<num>}$ 表示严格小于 $2^n$ 的非负十进制整数。而符号 $\texttt{<operator>}$ 可以是 $\texttt{+}$，$\texttt{-}$，$\texttt{|}$，$\texttt{\&}$，$\texttt{<<}$ 或 $\texttt{>>}$，分别表示：加，减，按位或，按位与，左移和右移的运算。

此外，字符 $a$ 在 $\texttt{<expr>}$ 符号中最多出现 $5$ 次。

在执行加减运算时出现溢出或下溢时，MalnarScript 将以 $2^n$ 为模执行这些运算。例如，当 $n = 3$ 时，在 MalnarScript 中，$7 + 3 = 2$，$2 - 5 = 5$。

每个命令中方程式的右侧求和为一个数字，然后将其存储到 $a$ 中。为了计算右侧表达式，MalnarScript 首先将每次出现的 $a$ 替换为其当前值。 然后，像在任何数学表达式中一样进行表达式的计算，即，括号优先。请注意，运算符的优先级（按照运算顺序）是不相关的，因为最终结果完全由括号的位置定义。

您的任务是编写一个程序，该程序在 MalnarScript 中输出程序，该程序以输入值的二进制表示形式计算一个数。

inputFormat: 第一行，两个正整数 $n, k$，含义见 **题目描述**。

outputFormat:
第一行中，您应该输出产生的 MalnarScript 程序的命令数。

在其余各行中，您应该输出所需程序的命令。每个命令必须在单独的行中输出，并且必须满足任务描述中所述的 MalnarScript 语法。

重要的是，输出中不要有不必要的空行或多余的空格字符。
每行（包括最后一行）必须以换行（`\n`）结尾。

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

| Subtask | 分数 | 数据范围及约定 |
| :-----------: | :-----------: | :-----------: |
| $1$ | $15$ | $2 \le n \le 100$，$k = n \ − \ 1$ |
| $2$ | $15$ | $n = 500$，$k = 128$ |
| $3$ | $35$ | $1 \le n \le 40$，$k = 7$ |
| $4$ | $45$ | $100 \le n \le 500$，$k = 10$ |

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T4 Popcount*。**

感谢 @[Sprague_Garundy](https://www.luogu.com.cn/user/764746) 提供的 SPJ，SPJ 可以在题目附件处下载。

另外，由于 `testlib` 库在洛谷环境下生成随机数在 $N=31$ 时有问题，采用固定已生成随机数。部分测试点 $N$ 较大，Special Judge 程序运行较久，如下。

| 特殊测试点编号 | 时限 |
|:-:|:-:|
| 15 | 3s |
| 39 | 2s |
| 40 | 3s |
| 48 | 3s |

上述测试点时限仅用于 Special Judge 程序使用。


title: [BJOI2020] 封印

background: 注：NOI 2020 北京队选拔赛因不可抗力因素取消，改为按前一年 CSP-S 第二轮成绩选出省队。因为出现同分，为决定最终 A 队名单，举办了加试。本题即为加试题。

description: 给出只包含小写字母 $a,b$ 的两个字符串 $s, t$，$q$ 次询问，每次询问 $s[l \dots r]$ 和 $t$ 的最长公共子串长度。

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

第一行一个字符串 $s$。

第二行一个字符串 $t$。

第三行一个整数 $q$。

接下来的 $q$ 行，每行两个整数 $l_i, r_i(1\le l_i \le r_i \le |s|)$，表示一次询问。

outputFormat:
输出共 $q$ 行。

第 $i$ 行表示 $s[l_i \dots r_i]$ 和 $t$ 的最长公共子串长度。


title: [YsOI2020] 制高

background: Ysuperman 特别喜欢玩战略游戏。

description:
游戏地图是一棵 $n$ 个点的有根树，根节点是 $1$ ，除节点 $1$ 外其他节点都有唯一的父亲节点。

每个节点有一个高度，第 $i$ 个节点的高度为 $h_i$ ，我们认为一个节点 $v$ 是“制高点”，当且仅当 $v$ 是根节点或者其父亲节点 $u$ 是“制高点”并且 $h_v\ge h_u$ 。

但是， Ysuperman 并不知道每个节点的父亲具体是哪个，只知道它的父亲编号可能在的区间，其中，节点 $i$ 的父亲可能在的编号范围为 $[l_i,r_i]$ ，保证 $1\le l_i\le r_i<i$ 。

现在， Ysuperman 想知道对于**所有可能的情况**，“制高点”的数量之和是多少。

因为这个结果可能会很大，所以你只需要输出结果 $\bmod \ {998244353}$ 的值即可。

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

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

接下来一行 $n$ 个非负整数，第 $i$ 个整数描述 $h_i$ 。

接下来 $n-1$ 行，每行两个正整数，分别描述 $l_2,r_2,\cdots,l_n,r_n$ 。

保证 $1\le l_i\le r_i<i$ 。

outputFormat: 一行一个整数，即答案。


title: 『MdOI R4』Kotori

background:
『「因为」？所以呢？』

『因为我是你的妹妹，所以你要叫我别阻止你胡来么？』

『因为我是你的妹妹，所以你要叫我看着你赴死么？』

『因为我是你的妹妹，所以你要叫我默默看着你可能被杀死么？』

『不要开玩笑了，这算什么啊！还以为好不容易和平下来了，还以为士道终于不用再受伤了。』

『我——我不希望士道死掉，不想再看到士道受伤了，已经受不了再让士道感到痛苦了啊……』

『因为我——』

『喜欢士道呀——』

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

description:
一年一度的世界最萌大会开始了。作为曾经的「萌王」，Kotori 自然无需参赛。但她希望帮助自己的哥哥  Shido 获得「燃王」的头衔。

本届 ISML 共有 $n=2^k$ 名参赛选手，编号为 $1,2\ldots n$，其中 Shido 的编号是 $1$，赛制为淘汰赛。每一轮比赛之后剩余选手中编号最小的两人为对手，编号第 $3,4$ 小的两人为对手，依次类推。每场比赛的胜负取决于粉丝的投票数，获得票数较多的一方晋级下一轮比赛，票数较少的一方淘汰。

例如共有 $4$ 名选手，则第一轮编号为 $1,2$ 的选手进行一场比赛，编号 $3,4$ 的选手进行一场比赛，然后两场比赛的胜者进行一场比赛，争夺总冠军。获得总冠军的选手将获得「燃王」头衔。

每个角色有一个厨团，$i$ 号选手的厨团人数为 $a_i$。每轮投票时，所有厨团的成员**会且仅会**为对应的选手投票。

此外，Kotori 拥有一个人数为 $m$ 人的团队，他们会永远跟随 Kotori 投票。也就是说，每场比赛 Kotori 都可以为对战双方的任意一者增加 $m$ 张得票。注意在一轮比赛中可能有多场比赛，每场比赛一定只有两名选手。

另外，Kotori 还拥有一项特权：当某场比赛双方的票数相同时，作为萌王的她可以决定这场比赛的胜者。

现在，Kotori 希望知道，她是否有能力帮助哥哥成为冠军，获得「燃王」的头衔。

inputFormat:
**本题包含多组数据。** 第一行有一个正整数 $T$ 表示数据组数。

接下来 $T$ 组数据，每组数据两行，包括：

- 第一行两个整数，表示 $k,m$。
- 第二行 $2^k$ 个整数，第 $i$ 个表示 $a_i$。

outputFormat:
$T$ 行，每行对应一组数据。

对于每组数据，如果可以做到输出 `Kotori`，否则输出 `Yoshino`。


title: [COCI2019-2020#2] Zvijezda

background: Mirko 和 Slavko 都将空闲时间花在玩多边形上和观看 _The Biggest Loser_ 上。

description: Mirko and Slavko are spending their free time playing with polygons and watching a new season of *The Biggest Loser*. Mirko recently drew a convex polygon with an even number of vertices $N$. Slavko then considered each pair of oposite sides (two sides are opposite if there are $\dfrac N2 - 1$ sides between them), drew straight lines that lie on those sides and colored them along with the part of the plane that lies between them and contains the polygon. Finally, Mirko found a set of $Q $ points and decided to challenge Slavko to answer for each point whether it lies in the colored or uncolored part of the plane. The new episode of *The Biggest Loser* is about to start and Slavko doesn’t have the time to answer Mirko’s queries. Can you help him?

inputFormat:
第一行，一个整数 $T$，它用作生成 Mirko 查询的参数。 该数字只可以是 $0$ 或 $1$。

第二行，一个正整数 $n$。

第 $3 \sim n + 2$ 行，每行 $2$ 个正整数 $x_i, y_i$ 。表示多边形的一个顶点。顶点是按逆时针顺序给出的，没有三个连续的顶点是共线的。

第 $n + 3$ 行，一个正整数 $q$。

接下来 $q$ 行，每行都有两个整数 $a_i, b_i$，它们用作在第 $i$ 个 Mirko 查询中生成点的参数。$x_i$ 等于 Mirko 查询的第 $i$ 个（含 $i$ 点）在平面彩色部分上的点数。 当然，$x_0 = 0$。然后，应将 Mirko 第 $i$ 个查询的点生成为：

$$p_i = (a_i \oplus (T \times x^{3}_{i-1}), b_i \oplus(T \times x^{3}_{i-1}))$$

其中 $\oplus$ 代表按位异或运算。

outputFormat: 如果 Mirko 查询的第 $i$ 个点位于平面的有色部分，则输出的第 $i$ 行为 $\tt DA$。 否则，第 $i$ 行为 $\tt NE$。

translation:
Mirko 最近绘制了一个具有偶数个顶点 $n$ 的凸多边形。

Slavko 选出了每组对边（如果两个边之间有 $\dfrac{n}{2}-1$ 边，则这两个边对边），画出位于这些边上的直线，并将它们与位于它们之间、包含多边形的平面部分一起涂上颜色。

最终，Mirko 选择了 $q$ 个点，并决定向 Slavko 询问，问他每个点是否位于有色或无色部分。

*The Biggest Loser* 节目即将开始，Slavko 没有时间回答 Mirko 的问题。你能帮她吗？


title: 「SWTR-7」Scores（easy version）

background:
#### 本题是 Scores 的 easy 版本。注意题目限制与 [hard](https://www.luogu.com.cn/problem/P7876) 版本不同。

#### 请注意特殊的时空限制，题目描述下方有简化题意。

description:
小 A 的班上有 $n$ 个学生。最近他们进行了一场考试，共有 $m$ 个学科。第 $i$ 个学生第 $j$ 门学科的得分为**整数** $s_{i,j}\ (0\leq s_{i,j}\leq 100)$。对于学生 $i$，如果**存在另一个**学生 $j$ 满足：学生 $i$ **每门学科的成绩都不大于**学生 $j$，学生 $i$ 就会感到失落。

中秋节快到了，善良的小 A 不想让任何一个同学感到失落，他决定 hack 学校的管理系统，修改每一位同学的成绩。在做出这样危险的举动之前，小 A 希望知道自己能否达到目标。不过，由于学生和科目实在太多，他想请你帮助他构造出一种合法的方案。

如果存在一张成绩表，满足没有任何一位同学感到失落，请先输出 $\texttt{YES}$，再**任意**输出一种符合要求的成绩表；否则输出 $\texttt{NO}$。

---

**「简化题意」**

试构造一个 $n\times m$ 的矩阵 $s$，满足所有元素为 $[0,100]$ 之间的整数，且对于任意 $i,j\ (i\neq j)$ 存在一个 $k$ 使得 $s_{i,k}>s_{j,k}$。

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

第一行一个整数 $t$，**表示该测试点编号**。
第二行一个整数 $T$，**表示数据组数**。

对于每组数据：
一行两个整数 $n,m$。

outputFormat:
对于每组数据：

如果小 A 的要求无法实现，输出一行字符串 $\texttt{NO}$。
否则先输出一行字符串 $\texttt{YES}$，再输出 $n$ 行，每行 $m$ 个由空格隔开的整数，第 $i+1$ 行第 $j$ 个数表示 $s_{i,j}$。

hint:
**「Special Judge」**

**本题使用 Special Judge。请认真阅读输出格式，输出格式有误可能导致 UKE。**

SPJ 首先会判断你的第一行输出是否与答案相同。
如果相同且答案为 $\texttt{YES}$，则 SPJ 会判断你的输出是否符合小 A 的要求：

- $0\leq s_{i,j}\leq 100$ 且 $s_{i,j}$ 为整数。
- 每个学生至少有一个科目的成绩比另一个学生高。

如果有解且你输出 $\texttt{YES}$，但给出方案错误，你将获得该测试点 $50\%$ 的分数。

**「数据范围与约定」**

本题共有 6 个测试点。

- Testcase #0（1 point）：是样例。
- Testcase #1（10 points）：$n=1$。
- Testcase #2（10 points）：$m=1$。
- Testcase #3（20 points）：$m=2$。
- Testcase #4（30 points）：$n\leq m$。
- Testcase #5（29 points）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,m\leq 100$，$T=20$（除 Testcase #0）。
对于所有测试点，**时间限制 200ms，空间限制 16MB。**

**「题目来源」**

[Sweet Round 07](https://www.luogu.com.cn/contest/51774) A1。
idea & solution & data：[Alex_Wei](https://www.luogu.com.cn/user/123294)；验题：[chenxia25](https://www.luogu.com.cn/user/138400)。


title: 「StOI-2」好多表达式

background:
本题为 [StOI](https://www.luogu.com.cn/team/24701) 第二场公开赛 [StOI Round2](https://www.luogu.com.cn/contest/32483) 之第一题.

__注意:如果这个数是一个多位数，不会将它拆开__ By LHQing ,14:09

:)

description:
给定一个仅由数字、`+`、`*` 组成的表达式，请求出它的所有子表达式运算值之和对 $998,244,353$ 取模的结果。

一个表达式的子表达式定义为 `一段连续的数字与其中的运算符构成的表达式` 。

如果您仍然无法理解，**可以参看样例解释**。

inputFormat:
第一行一个正整数 $n$ ，表示表达式中数字的个数。

接下来一行是这个由 $n$ 个正整数与 $n-1$ 个运算符组成的表达式，其中数字与运算符中间有空格隔开。

outputFormat: 输出一个数，表示最终的答案。

hint:
## 样例解释

所给定的表达式共有六个子表达式：
$1$、$2$、$3$、$1+2$、$2 \times 3$、$1+2 \times 3$ ，值分别为 $1$、$2$、$3$、$3$、$6$、$7$ ，和为 $22$ 。

---

## 数据范围

对于 $20\%$ 的数据：$1 \leq n \leq 1000$ 。
对于另 $20\%$ 的数据：不存在 `+` 。
对于另 $20\%$ 的数据：仅存在一个 `+` 。
对于另 $20\%$ 的数据：仅存在一个 `*` 。
对于 $100\%$ 的数据：$1 \leq n \leq 10^{5}$ ，所有数字均不大于 $10^{9}$ ，运算符只包含 `+` 、`*` 。


title: 「StOI-2」独立集

description:
一棵由 $n$ 个点组成的无根树，给定 $m$ 条树上的路径，请求出由这 $m$ 条路径组成的`独立集`方案总数。

由于这个答案可能很大，您只需求出它对 $998,244,353$ 取模的结果即可。

所谓`独立集`，就是一个路径集合，满足这个集合中**不存在**一对在树上有交点的路径。特殊的，空集和只包括一条路径的集合也是独立集。

inputFormat:
第一行两个正整数，$n$ 和 $m$ ，表示点数和路径数。
接下来 $n-1$ 行，每行两个正整数 $u_{i}$ 和 $v_{i}$ ，表示树的每条边。
接下来 $m$ 行，每行两个正整数 $a_{i}$ 和 $b_{i}$ ，表示给定的每条路径。

outputFormat: 输出一个正整数，表示最终的答案。


title: 「StOI-2」简单的树

description:
给定一棵以 $1$ 为根，由 $n$ 个点组成的有根树，每个点有点权 $c_{i}$ 。

定义每个点的 $val$ 值为：以它为根的子树内所有 $c_{i}$ 的最大值。

定义函数 $f(x,y)$ 表示将 $c_{x}$ 改为 $y$ 后整棵树的 $val$ 值之和。

现在请您回答 $q$ 组询问，每次询问给定 $3$ 个量 $(l,r,a)$ ，请求出 $\sum\limits_{i=l}^{r}{f(a,i)}$ 对 $998,244,353$ 取模的结果。

inputFormat:
**本题强制在线**

第一行三个正整数，$n$、$q$ 和 $opt$，分别表示树的点数、询问数和控制强制在线的量。

第二行 $n$ 个正整数，表示每个点的点权。

接下来 $n-1$ 行，每行两个正整数 $u_{i}$ 和 $v_{i}$，表示树的每一条边。

接下来 $q$ 行，每行三个正整数 $l',r',a'$ ，请计算出真实的 $l,r,a$ 后完成询问。

- $l = (( l' + opt \times lastans )\bmod n )$ $+ 1$
- $r = (( r' + opt \times lastans )\bmod n )$ $+ 1$
- $a = (( a' + opt \times lastans )\bmod n )$ $+ 1$

其中 $lastans$ 表示上一组询问的答案，初始为 $0$ 。

如果此时出现 $l > r$ 的情况，请交换 $l$ 和 $r$ 。

outputFormat: 对于每组询问，输出最终的答案。


title: 「EZEC-6」加减

description:
给你两个数 $n,m$，你要将 $m$ 分为 $n$ 个**互不相同的正整数**（即这 $n$ 个数之和为 $m$），使得在区间 $[1,m]$ 中至少有一个正整数无法通过这 $n$ 个数加减取得（加减时每个数最多用 $1$ 次）。

即，设 $n$ 个正整数中第 $i$ 个数为 $a_i$，你要使在区间 $[1,m]$ 中至少有一个正整数无法被表示为 $\sum\limits^{n}_{i=1}k_i\times a_i\ (k_i\in\{-1,0,1\})$ 的形式。

若无解，输出 `-1`。

若有解，则输出任意一组满足要求的 $n$ 个正整数，并输出在区间 $[1,m]$ 中无法被表示出的任意一个数。

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

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

对于每组数据，一行 $2$ 个正整数 $n,m$。

outputFormat:
对于每组数据：

若无解，输出一行 `-1`。

若有解，第一行输出 $n$ 个正整数，表示一组满足要求的解，第二行输出一个在区间 $[1,m]$ 中的正整数，该正整数无法被表示。

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

- Subtask 1（10 points）：$n\le2$。
- Subtask 2（20 points）：$2n^2\le m$。
- Subtask 3（20 points）：$\lceil1.5n^2\rceil\le m$。
- Subtask 4（20 points）：$n\le5$。
- Subtask 5（30 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le100$，$1\le n,m\le10^4$。


title: [SNOI2020] 字符串

description: 有两个长度为 $n$ 的由小写字母组成的字符串 $a,b$，取出他们所有长为 $k$ 的子串（各有 $n-k+1$ 个），这些子串分别组成集合 $A,B$。现在要修改 $A$ 中的串，使得 $A$ 和 $B$ 完全相同。可以任意次选择修改 $A$ 中一个串的一段后缀，花费为这段后缀的长度。总花费为每次修改花费之和，求总花费的最小值。

inputFormat:
第一行两个整数 $n,k$ 表示字符串长度和子串长度；
第二行一个小写字母字符串 $a$；
第三行一个小写字母字符串 $b$。

outputFormat: 输出一行一个整数表示总花费的最小值。

hint:
#### 样例说明

对于样例 $1$，所有子串为：$A = \{aab,aba,baa\}, B = \{aba, bab, aba\}$。可以看出有一对 $aba$ 是相同的，另外要把 $aab$ 改成 $aba$（花费 $2$），$baa$ 改成 $bab$（花费 $1$），总花费为 $3$。

#### 数据规模与约定

对于所有数据，$1\le k\le n\le 1.5\times 10^5$。

- 对于 $10\%$ 的数据，$n \le 11$；
- 对于另外 $20\%$ 的数据，$n \le 200$；
- 对于另外 $20\%$ 的数据，$n \le 2000$；
- 对于另外 $10\%$ 的数据，字符串的每一位在小写字母中均匀随机；
- 对于余下 $40\%$ 的数据，无特殊限制。


title: [SNOI2020] 水池

description:
有一个长条形的水池，可以划分成 $n$ 格。其中第 $i$ 格和 $i+1$ 格之间相邻，由一块高度为 $h_i$ 的可调节挡板隔开。第 $1$ 格左侧和第 $n$ 格右侧是无限高的池壁。初始时水池中没有水。现在进行 $q$ 次操作，操作有以下四种：

- `0 i x h` 在第 $x$ 格灌水直到该格的水面高度不低于 $h$（若当前水面高度已经达到 $h$ 则无事发生）；
- `1 i x` 打开第 $x$ 格底部的排水口直到该格的水流干，再关闭排水口；
- `2 i x h` 将第 $x$ 格右侧的挡板高度增加到 $h$（不改变现有水面，保证挡板高度不会下降）；
- `3 i x` 查询第 $x$ 格的水面高度。

其中，$i$ 表示这次操作是基于第 $i$ 次操作之后的情况，$i=0$ 表示基于初始状态。也就是说，这个问题要求对操作可持久化。

inputFormat:
第一行两个自然数 $n,q$，表示水池格数和操作次数。
接下来一行 $n - 1$ 个正整数 $h_i$ 表示挡板的初始高度。
接下来 $q$ 行每行一个正整数表示一次操作。

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

hint:
#### 样例说明

对于样例 $1$：

![](https://loj-img.upyun.menci.memset0.cn/2020/06/29/5ef98fcf44fd0.png)

#### 数据规模与约定

对于所有数据，$1\le n,q\le 2\times 10^5, 0\le h_i\le 10^9$。

- 对于 $10\%$ 的数据，$n \le 500$；
- 对于另外 $20\%$，没有操作 $1$，且 $i$ 从 $0$ 开始连续增长（不需要可持久化）；
-  对于另外 $20\%$，没有操作 $1$；
- 对于另外 $20\%$，且 $i$ 从 $0$ 开始连续增长（不需要可持久化）；
- 对于余下 $30\%$ 的数据，无特殊限制。


title: [SNOI2020] 排列

description:
有一个 $n$ 阶排列 $p$，其前 $k$ 位 $p_1,p_2,\cdots,p_k$ 已经确定了。

定义排列 $p$ 中，$[l,r]$ 是一个值域连续段当且仅当：

$$\max(p_l, p_{l+1}, \dots, p_r) - \min(p_l, p_{l+1}, \dots, p_r) = r-l$$

$p$ 中值域连续段个数即所有 $1 \le l \le r \le n$ 中值域连续段的总数。

请你求出：所有可能的排列 $p$ 中，值域连续段个数的最大值，以及任意一种方案。

inputFormat:
第一行两个整数 $n,k$，分别表示排列的阶数和以及确定的位数。
接下来一行由空格分隔的 $k$ 个正整数 $p_i$，表示排列一直的部分。（$k=0$ 则此行为空）

outputFormat:
输出第一行一个整数表示值域连续段个数的最大值。
第二行 $n$ 个正整数表示任意一种方案。


title: 【模板】Runs

description:
定义一个字符串 $|S|$ 里的一个 run，指其内部一段两侧都不能扩展的**周期子串**，且周期至少完整出现两次。

严格地说，一个 run 是一个 三元组 $(i,j,p)$，满足 $p$ 是 $S[i..j]$ 的最小周期，$j-i+1 \ge 2p$，且满足如下两个条件：

+ 要么 $i=1$，要么 $S[i-1]\ne S[i-1+p]$；
+ 要么 $j=n$，要么 $S[j+1] \ne S[j+1-p]$。

给定字符串 $S$，求他的所有 runs。

inputFormat: 一行一个字符串 $S$，保证其只由小写字母构成。

outputFormat:
第一行一个整数 $m$，表示 runs 的数量。

接下来 $m$ 行，每行三个整数描述一个 runs：

+ 这个 runs 的第一个字符的位置
+ 最后一个字符的位置
+ 这个 runs 的最小循环的长度

你应该以第一个字符的位置为第一关键词，最后一个字符的位置为第二关键词对所有的 runs 进行排序。


title: 可重集

description:
给出一个长度为 $n$ 的非负整数序列 $a_1,a_2,a_3,\ldots, a_n$，给出 $q$ 次操作，每次先给出一个参数 $op$：

- $op=0$，接下来给出 $2$ 个参数 $x,y$，把 $a_x$ 修改为 $y$。

- $op=1$，接下来给出 $4$ 个参数 $ l_1,r_1,l_2,r_2$（保证 $r_1-l_1=r_2-l_2$），你需要判断区间 $[l_1,r_1]$ 与区间 $[l_2,r_2]$ 是否本质相同，如果本质相同输出 `YES`，否则输出 `NO`。

本质相同的定义：令区间长度为 $\text{len}$ ，序列 $p_{1}\dots p_{\text{len}}$ 为 $a_{l_1}\dots a_{r_1}$ 升序排序后的结果，序列 $q_{1}\dots q_\text{len}$ 为 $a_{l_2}\dots a_{r_2}$ 升序排序后的结果，存在一个整数 $k$ 使得满足 $\forall i,p_i+k=q_i$。

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

第二行 $n$ 个非负整数表示 $a_{1},a_2,a_3,\ldots,a_n$。

接下来 $q$ 行，每行为上述操作中的一种。

outputFormat: 对于 $op=1$ 的操作，输出两个区间是否本质相同，如果是输出 `YES`，否则输出 `NO`。

hint:
- Subtask1 （$25$ pts）：$1\leq n,q \leq 1000$。

- Subtask2 （$25$ pts）：$1\leq n,q \leq 10^5$，$0\leq a_i,y\leq 100$。

- Subtask3 （$25$ pts）：$1\leq n,q \leq 10^5$。

- Subtask4 （$25$ pts）：无特殊限制。

你只有通过 subtask 中的所有测试点才能获得该 subtask 的分数。

对于所有数据满足：$1\leq n,q \leq 10^6$，$1\leq x \leq n$，$0\leq a_i,y \leq  10^6$ 。且对于所有 $l,r$ 有 $1\leq l\leq r\leq n$。


title: 混凝土数学

description:
你正在看混凝土数学，这时旁边的工地开工了，你觉得看他们施工更有意思，于是你向窗外望去，注意到了一些长度不同的木棍。具体而言，你看到了 $n$ 条木棍编号为 $1,2,3,\ldots,n$，长度为 $a_1,a_2,a_3,\ldots,a_n$。你突发奇想：有多少拿出其中 $3$ 条木棍的方案满足它们能构成等腰三角形呢？你不想要输出的数太大，所以最后的方案要对 $998244353$ 取模。

给出等腰三角形的要求：任意两边之和大于第三边且至少有两条边边长相等。

例如，如果木棍长度分别为 $\{3,3,2,2,4,5\}$，你就有 $6$ 种方法，选取的木棍编号分别为：$\{1,2,3\}$，$\{1,2,4\}$，$\{1,2,5\}$，$\{1,2,6\}$，$\{1,3,4\}$，$\{2,3,4\}$。

inputFormat:
第一行给出一个正整数 $n$ 表示木棍个数。

第二行 $n$ 个正整数表示 $a_1,a_2,a_3,\ldots, a_n$。

outputFormat: 一个数表示总方案数对 $998244353$ 取模的结果。

hint:
- Subtask1 （$30$ pts）：$1\leq n \leq 200$。
- Subtask2 （$30$ pts）：$1\leq n \leq 2000$。
- Subtask3 （$20$ pts）：木棍长度全部相等。
- Subtask4 （$20$ pts）：无特殊限制。

对于 $100\%$ 的数据满足：$1\leq n \leq 2\times 10^5$，$1\leq a_i \leq 2\times 10^5$。


title: 可持久化动态仙人掌的直径问题

background: 众所周知，一场考试需要一道签到题。

description: 给定 $n,m$，求有多少个正整数 $x$，使得 $x^m\le n$。

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

outputFormat: 一个整数表示正整数 $x$ 的个数。


title: 序列

description:
小 C 想出关于括号序列的一道题，但是他不怎么会造数据，所以他采取了随机的方式。

小 C 钦定了括号序列 $S$ 的长度 $N$。$S$ 初始时全为 `(`。

他初始设定了一个参数 $K$，并按照如下流程随机，直到 $K=0$：

1. 在 $[1,N]$ 的范围内**均匀随机**一个整数，把 $S$ 这一位上的括号取反（左括号变右括号，右括号变左括号）。
2. 如果本次操作使得 `(` 的数量减少了，使 $K$ 的值减 $1$。

现在数据造好了，题也就出完了。

小 C 想请你求出，在经过上述操作后，$S$ 中**最长合法括号子序列**（不要求连续）在模 $998244353$ 意义下期望有多长。

inputFormat: 输入第一行，为两个正整数 $N,K$，含义题面已给出。

outputFormat: 输出共一行，一个非负整数，表示你所求得的答案对 $998244353$ 取模的结果。

hint:
**样例解释1**

最终括号序列只有 $3$ 种，`))`，`()`，`)(`。其对应的概率分别为 $\frac{1}{2}$，$\frac{1}{4}$，$\frac{1}{4}$。

它们对应的最长合法括号子序列长度分别为 $0,2,0$。所以最终答案为 $\frac{1}{2}$，也即 $499122177$。

**数据规模：**

对于前 $5\%$ 的数据，$N=1$；
另有 $5\%$ 的数据，$N=2$；
另有 $5\%$ 的数据，$N\le 7$，$K\le 5$；
另有 $15\%$ 的数据，$N\le 15$，$K\le 500$；
另有 $ 15\%$ 的数据，$N\le 50$，$K\le 50$；
另有 $ 15\%$ 的数据，$N\le 500$，$K\le 100$；
对于全部的数据，保证 $1\le N,K\le 5000$。


title: 一次函数

description:
给定 $n$ 个一次函数 $f_i(x) = a_ix + b_i$，其中 $x$ 为形式幂级数的占位符。

从这 $n$ 个中选出 $k$ 个 $g_i(x)$ （$1\leq i \leq k$），定义集合 $H$ 为 $g_i$ 的若干次幂的乘积模 $x^2$ 的值所构成的集合。即：

$$H=\left\{\prod_{i=1}^k g_i(x)^j\bmod x^2\middle|0 \leq a, b < p \right\}$$

其中 $j$ 是任意非负整数且对于每个 $i$ 可以有不同的 $j$。

需要注意的是，$0\cdot x+1$ 始终在集合 $H$ 中（而非 $0 \cdot x + 0$），即使 $k = 0$ 也是如此。

给定 $A, B$，求出所有满足 $Ax+B\in H$ 的集合 $H$ 的 $k$ 的最小值。

若不存在 $H$ 使得 $Ax+B\in H$，输出 `-1`。

所有运算均在模 $p$ 意义下进行。

inputFormat:
第一行四个整数 $n, p, A, B$。

接下来 $n$ 行，每行两个整数 $a_i, b_i$。

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

若存在方案，接下来 $k$ 行，每行两个整数 $a, b$，需满足
$$\left(\prod f_a(x)^b\right)\bmod x^2=Ax + B$$

$a$ 的顺序可任意。

hint:
**另有两组大样例与 checker，下载地址见附件。**

要测试你某个测试点的答案，你需要在你本题目录下的命令行中执行：

``<checker> <input‐file> <output‐file> <answer‐file> [<report‐file>]``

其中：

* ``<checker>`` 表示校验器可执行文件；
* ``<input‐file>`` 表示该测试点的输入文件，如 ``func1.in``；
* ``<output‐file>`` 表示该测试点你的答案，如 ``func1.out``；
* ``<answer‐file>`` 表示该测试点的答案文件（只需要提供输出的第一行），如 ``func1.ans``；
* ``<report‐file>`` 为可选参数，如果没有给定该参数，校验器将输出至终端；否则将输出至该文件，如 ``report1.txt``。

对于所有数据，$2\leq p\leq 10^9$，保证 $p$ 为质数，$1\leq n \leq 5 \times 10^3$，$0\leq a_i, A < p$，$1\leq b_i, B < p$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

| 子任务编号 | 分值 | $n$ | $p$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $5$ | $=1$ | $\leq 1000$ |  |
| $2$ | $5$ | $\leq 3$ | $=7$ |  |
| $3$ | $15$ | $\leq 100$ | $=31$ |  |
| $4$ | $20$ | |  | $A=B=1$ |
| $5$ | $25$ | $\leq 20$ |  |  |
| $6$ | $15$ | $\leq 500$ |  |  |
| $7$ | $15$ | |  |  |

tags: 扩展欧几里德算法,exgcd


title: 「C.E.L.U-01」门禁

background:
abruce 有一次去机房去得**比较**早，然后……他在外面等了35分钟……于是，他想到这样一个问题：
机房的大门锁着，有 $n$ 名学生都需要进来，进来必须要门禁卡。但有些学生会一同前往。一同前往的人中只要有一个人带了门禁卡就会免于被锁在外面的窘境。现在老师终于要发门禁卡了，可是究竟要发多少张呢？

description: 我们将题目背景中的问题简化。给出 $n$ 个点，以及任意两个点 $i,j$ 之间存在一条无向边的概率 $p_{i,j}$，求图中联通块个数的期望。

inputFormat:
第一行一个数 $n$。
第二行到第 $n+1$ 行，每行 $n$ 个实数，代表 $p_{i,j}$。测试数据保证对任意 $1\le i \le n$，$p_{i,i}=0$，对任意 $1\le i,j \le n$，$p_{i,j}=p_{j,i}$，$0\le p_{i,j}\le1$ ，输入的实数小数点后位数不超过 $3$ 位。

outputFormat: 仅一行一个实数，表示连通块个数的期望。当你的答案与标准答案的**绝对**误差不超过 $10^{-4}$ 时算作正确。


title: 「Wdsr-2.5」小小的埴轮兵团

background:
杖刀偶磨弓是埴轮兵团的首长。

作为埴轮兵长，训练埴轮兵团是很平常的事情。

description:
磨弓下达命令让埴轮们站成一行。不妨认为它们站在了一个数轴上，每个埴轮的位置就是它脚下数轴的数字。磨弓会告诉你，第 $i$ 个埴轮的位置为 $a_i$ 。**不保证** $\bm {a_i}$ **升序**。

数轴的长度是有限制的，具体的范围是 $[-k,k]$ 。也就是说，如果某个埴轮移出了这个范围，它就脱离了这个队列了，并且不会再次回到队列当中。

为了训练埴轮，磨弓给埴轮们下达了 $m$ 个指令，有以下 3 种：

- 指令 1：**全体埴轮**向数轴的正方向移动 $x$ 个单位长度。
- 指令 2：**全体埴轮**往数轴的反方向移动 $x$ 个单位长度。
- 指令 3：依次报数，统计目前队列里一共有多少个埴轮。

但是磨弓发现，埴轮兵团的大小实在是太大了，以至于执行这些操作变得非常缓慢。尽管如此，磨弓仍然希望你告诉她所有指令 3 的结果。

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

第二行共有 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示每个埴轮的位置。

接下来 $m$ 行，有 $1$ 或者 $2$ 个正整数，描述一条指令。首先是一个整数 $\operatorname{op}$，表示这条指令的类型。如果 $1 \leq \operatorname{op} \leq 2$，接下来还会输入一个整数 $x$。

outputFormat: 对于每条指令 3 ，输出一个整数，表示目前还在队列中的埴轮的数目。

hint:
#### 样例 1 说明

一共有三个埴轮。初始时，它们的站位分别是 $[-1,1,2]$ 。

- 第一次操作后，所有埴轮向左移动 $3$ 格，位置变成了  $[\underline{\bm{-4}},-2,-1]$ 。第一个埴轮被移出了数轴。
- 第二次操作后，输出当前的埴轮数目，为 $2$ 个。
- 第三次操作后，所有埴轮向右移动 $5$ 格，位置变成了 $[3,\underline \bm4]$ ，第二个埴轮被移出了数轴。
- 第四次操作后，输出当前的埴轮数目，为 $1$ 个。

#### 样例 2, 3

见下发附件。

#### 数据规模与约定

- 对于 $30\%$ 的数据，$1 \leq n, m \leq 5\times 10^3$；
- 对于另外 $20\%$ 的数据，$1\le k\le 500$；
- 对于 $100\%$ 的数据，$1 \leq n, m \leq 3\times 10^5$，$1 \leq k, x \leq 2 \times 10^9$，$-k \le a_i \le k$ 。


title: [Cnoi2020] 雷雨

background:
> 令人不安的云开始笼罩天空。
巨大的建筑在强风中轧轧作响。
幻想乡中响彻着不和协音。
——「东方辉针城 ～ Double Dealing Character」

一个雷雨交加的夜晚，一束闪电击中了雾之湖畔的红魔馆和迷途竹林。

似乎有什么大事要发生，Cirno 在小屋静静地中思考着。

description:
幻想乡的纵切面可以抽象成一个 $n\times m$ 的矩形。

其中每一个 $1\times 1$ 的单元格 $(i,j)$ 都有一个**电阻计量值**(虚构的概念) $R_{i,j}$。

闪电从**雷雨云**上的 $\texttt{O}(n,a)$ 发出，击中了**地面**上的*红魔馆* $\texttt{A}(1,b)$ 与*迷途竹林* $\texttt{B}(1,c)$。

雷电是自然的造物，所以覆盖的位置电阻计量值总和最小，即从 $\texttt{O}$ 到 $\texttt{A}$ 与 $\texttt{B}$ 的**两条路径的并集**的电阻计量值的和最小。

所以在所有位置电阻计量已知的情况下，Cirno 想知道雷电的经过的路径的最小电阻计量值的和。

inputFormat:
第一行，五个整数 $n,m,a,b,c$。$(0<a,b,c\le m)$

以下 $n$ 行，每行 $m$ 个整数，表示电阻计量 $R_{i,j}$，其中第一行表示雷雨云，最后一行表示地面。

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

hint:
## 样例解释

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

如图黄色线为闪电的路径。

## 数据范围与约定

对于 $100\%$ 的数据保证：$0<n,m \le 1000$，$0 \le R_{i,j}\le 10^9$，$0< a,b,c \le m$。

#### 子任务「本题采用捆绑测试」

 - Subtask1（$10\%$）: $R_{i,j}\in\{1\}$。
 - Subtask2（$10\%$）: $R_{i,j}\in\{0,1\}$。
 - Subtask3（$10\%$）: $a=b=c$。
 - Subtask4（$10\%$）: $n,m \le 5$。
 - Subtask5（$60\%$）: 无特殊限制。


title: [Cnoi2020] 子弦

description: Cirno 有一个字符串 $\texttt{S}$，并希望你能求出 $\texttt{S}$ 出现次数最多的非空子串的出现次数，记作 $p$。

inputFormat: 一行，一个字符串 $\texttt{S}$。

outputFormat: 一行，一个整数 $p$。

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

对于 $100\%$ 的数据保证: $0< |\texttt{S}| \le 10^7$，$\texttt{S}_x\in[\texttt{a},\texttt{z}]$。

#### 子任务「本题采用捆绑测试」
 - Subtask1（$40\%$）：$|\texttt{S}| \le 100$。
 - Subtask2（$40\%$）：$|\texttt{S}| \le 10^5$。
 - Subtask3（$20\%$）：无特殊限制。

### 名词解释
 - **子串**：字符串中任意个连续的字符组成的子序列称为该串的子串。


title: 【模板】LGV 引理

description:
这是一道模板题。

有一个 $n\times n$ 的棋盘，左下角为 $(1,1)$，右上角为 $(n,n)$，若一个棋子在点 $(x,y)$，那么走一步只能走到 $(x+1,y)$ 或 $(x,y+1)$。

现在有 $m$ 个棋子，第 $i$ 个棋子一开始放在 $(a_i,1)$，最终要走到 $(b_i,n)$。问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过路径上的点互不相交。输出方案数 $\bmod\ 998244353$ 的值。

两种方案不同当且仅当存在至少一个棋子所经过的点不同。

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

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

对于每组数据：

第一行两个整数 $n,m$，分别表示棋盘的大小和起点终点的数量。

接下来 $m$ 行，每行 $2$ 个整数 $a_i,b_i$，其意义已在题目描述中说明。

outputFormat: 对于每一组数据，输出一行一个整数表示方案数 $\bmod\ 998244353$ 的值。

hint:
- 对于 $30\%$ 的数据，$n\leq 100$，$m\leq 8$。

- 对于 $100\%$ 的数据，$T\leq5$，$2\leq n\leq10^6$，$1\leq m\leq100$，$1\leq a_1\leq a_2\leq \dots\leq a_m\leq n$，$1\leq b_1\leq b_2\leq \dots\leq b_m\leq n$。


title: 「Wdsr-2」阴阳玉

background:
博丽灵梦有一块好大好大的阴阳玉，它是是博丽灵梦的主要武器之一。

但是阴阳玉的能量来源，源自主人的灵力聚集力量，因此，灵梦在平时总是需要对其进行保养。简单来说，灵梦会使用灵力，来获取阴阳玉所需的能量。

description:
灵力有阴阳之分。初始的时候，灵梦只有两个阳灵力，它们围成了一个圈。每次，灵梦可以进行以下两种操作：

- 在两个灵力直接加入一个阳灵力。

- 移走一个阳灵力。

为了保持稳定，任何时候这个圈上的灵力都**不应该少于两个**。

由于灵力的阴阳并不稳定，因此一旦某个灵力周围发生改变（多出一个灵力，或减少一个灵力），它就会从阳变成阴，或从阴变成阳。不过，如果只是周边灵力的性质改变，那么它就不会发生变化。

灵梦会不断调节灵力，直到它**最终**变成 $n$ 个（中途可能多于 $n$ 个）。然后，灵梦会从某个点**依次**按照顺时针或逆时针取下每个灵力。它会形成一条链。灵梦会用链上的能量，来加强她的阴阳玉。

做到这一点非常容易。但是灵梦非常好奇，一共可能形成多少种不同的**链**。

由于灵梦的偏好，她可能会有 $m$ 个限制条件。第 $i$ 个条件 $(p_i,c_i)$ ，规定了链上第 $p_i$ 个灵力应该为何种灵力。若 $c_i=0$ ，则应该为阴灵力；否则为阳。

由于可能结果太大，灵梦只需要得到答案对 $998244353$ 取模的结果。

两个链不同，当且仅当存在一个位置的点颜色不同。

inputFormat:
第一行为一个正整数 $n$ 和一个非负整数 $m$ 。

当 $m=0$ 时无约束条件。否则接下来会有 $m$ 行，每行两个非负整数 $p_i,c_i$ ，含义如上。

outputFormat: 一行，一个非负整数，表示所有链的可能种类总数对 $998244353$ 取模的值。

hint:
#### 样例解释

对于样例一，可能存在以下两种构造方式：

![pic3.JPG/The "2"-th of the "1"-st.](https://i.loli.net/2020/07/17/VQn8MB7fxJsA1Rr.jpg)

其中， $\tt ADD$ 表示增加一个阳灵力，$\tt RMV$ 表示移走一个阳灵力。

将得到的两个环分别拆开，一共可以得到以下五种链：

- 环一：**阳—阳—阳—阳**。

- 环二：**阳—阳—阴—阴**，**阳—阴—阴—阳**，**阴—阴—阳—阳**，**阴—阳—阳—阴**。

因此答案为 $5$ 。

对于样例二，我们限定了链上第一个灵力为阳。因此结果为 $3$ 。

#### 数据范围

$$\def{\t}{\text}\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & n\t{ 的范围} & m\t{ 的范围} & \t{分值}\cr\hline
1 & n\le 16 & m\le 16 & 15 \cr \hline
2 & n\le 10^6 &  m\le 5\times 10^3 & 40 \cr \hline
3 & n\le 10^{18} & m=0 & 15 \cr \hline
4 & n\le 10^{18} & m\le 5\times 10^3 & 30 \cr \hline
\end{array}$$

此外，对于全部数据，有 $1\le p_i\le n,c_i\in \{0,1\}, 0\le m\le n$ 且 $p_i$ 各不相同。


title: [CCO2019] Card Scoring

description:
您下载了一款卡牌游戏。

这款游戏的规则如下：
1. 共有 $n$ 张牌，每张牌有一个种类，种类共有 $n$ 种，用 $1\sim n$ 的整数表示，同时还有一个评分参数 $k$。
2. 您按顺序摸这 $n$ 张牌，每张牌有两种选择，拿走或不要。
3. 在任何情况下，您都要保证，您的手上的牌里只能有一种种类的牌。
4. 在摸完牌后，您可以选择结算您的分数。分数的计算方式为：若您有 $x$ 张牌，您会获得 $x^{\frac{1}{2}k}$ 的分数。结算完分数后，您的手牌将被清空，且您的总分会进行累加。

现在，您决定计算，这款手牌游戏可能取得的总分的最大值是多少。

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

接下来 $n$ 行，一行一个数，表示牌的种类。

outputFormat: 仅一行一个实数，表示可能取得的最高分。

hint:
#### 样例解释
#### 样例 1 解释
最优方案为不放弃每一张牌，摸完第一、三、五张牌后计分，分数为：$1^{1.5}+2^{1.5}+2^{1.5}\approx 6.656854249$。
#### 样例 2 解释
最优方案有两种，一种是弃掉种类为 $2$ 的牌，在第五张牌摸完后计分，共得 $3^2=9$ 分。

另一种同样例一，分数为：$1^{2}+2^{2}+2^{2}=9$。
#### SPJ 计分标准
设您的答案为 $p$，标准答案为 $q$，若 $\frac{|p-q|}{q}\le 10^{-6}$，您可以 AC。

#### 数据范围及限制
对于 $100\%$ 的数据，保证 $2\le k\le 4$，$1\le n\le 10^6$，牌的种类 $\in \{1,n\}$。

| 子任务 | $n\le $ | $k=$ | 分值 |
| - | - | - | - |
| 1 | $20$ | 无特殊限制 | $16$
| 2 | $300$ | $2$ | $4$
| 3 | $300$ | 无特殊限制 | $20$
| 4 | $5\times 10^3$ | 无特殊限制 | $12$
| 5 | 无特殊限制 | $4$ | $12$
| 6 | 无特殊限制 | 无特殊限制 | $36$

#### 说明
本题译自 [Canadian Computing Olympiad 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%202/day2.pdf) T1 Card Scoring。


title: [CCO2019] Marshmallow Molecules

description:
有一个有 $N$ 个点，$M$ 条边的无向图，图无重边，无自环。

如果 $a<b<c$ 且 $a$ 到 $b$ 有边，$a$ 到 $c$ 也有边，则 $b$ 到 $c$ 会连上一条边。

求最后的边数。

inputFormat:
第一行为两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行两个整数 $a_i$ 和 $b_i$，表示有一条从 $a_i$ 连到 $b_i$ 的边。

outputFormat: 仅一行一个整数，表示最后的边数。

hint:
#### 样例 1 解释
需要添加 $(2,4),(5,6)$ 两条边。

#### 数据范围及限制
对于 $100\%$ 的数据，保证 $1\le N,M\le 10^5$，$1\le a_i<b_i\le N$。

| 子任务 | $N\le $ | 特殊限制 | 分值
| :-: |:-: |:-:| :-:
| 1 | $100$ | 无 | $20$
| 2 | $5\times 10^3$ | 无 | $20$
| 3 | 无特殊限制 | 对于每个 $1\le j\le N$ 均有至少一组 $(a_i,b_i)$ 且 $b_i=j$ | $20$
| 4 | 无特殊限制 | 无 | $40$
#### 说明
本题译自 [Canadian Computing Olympiad 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%202/day2.pdf) T2 Marshmallow Molecules。


title: [CCO2019] Bad Codes

description:
有 $N$ 个长度至多为 $M$ 的字符串。

字符串之间可以随意拼接。

如果可以用不同的方法拼接出两个相同的字符串，则请输出可能存在的这种字符串的最小长度，否则，请输出 `-1`。

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

接下来 $N$ 行，一行一个长度至多为 $M$ 的字符串。

hint:
#### 样例 1 解释
拼接第二个字符串与第三个字符串可以得到第一个字符串。
#### 数据范围及限制
对于 $100\%$ 的数据，保证 $1\le N,M\le 50$，读入的字符串里无空串，读入的字符 $\in \{0,1\}$。

| 子任务 | $N=$ | $M\le$ | 特殊限制 | 分数
| :-: | :-: | :-: | :-: |:-:
| 1 | $4$ | $6$ | 无 | $16$
| 2 | 无特殊限制 | 无特殊限制 | 每一个字符串包含一个 `1`，如 `00100`。| $28$
| 3 | 无特殊限制 | 无特殊限制 | 无 | $56$
#### 说明
本题译自 [Canadian Computing Olympiad 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%202/day2.pdf) T3 Bad Codes。


title: [COCI2010-2011#7] ŠEĆER

background: Mirko 在制糖厂当送货员。

description:
Mirko 需要向某地的一家糖果店运送 $n$ 颗糖。

Mirko 可以使用两种类型的包装盒子：
- 一种是可以装 $3$ 颗糖的 $1$ 号包装；
- 另一种是可以装 $5$ 颗糖的 $2$ 号包装。

Mirko 想让包装盒尽可能少。例如，他要运送 $18$ 颗糖，则可以使用 $6$ 个 $1$ 号包装。但是，最优策略是 $3$ 个 $2$ 号包装和 $1$ 个 $1$ 号包装。这样总共有 $4$ 个包装。

请你帮助 Mirko 找到需要包装盒最少的方案。

inputFormat:
输入数据共一行。

第一行一个正整数 $n$，表示糖果颗数。

outputFormat:
输出数据共一行。

第一行，一个正整数表示需要包装盒最少的方案数的包装盒数，如果不可能用这 $2$ 种包装盒运 $n$ 颗糖，输出 `-1`。

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

对于 $100\%$ 的数据，$3 \le  n \le 5000$。

#### 说明

本题满分 $30$ 分。

译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T1 ŠEĆER


title: [COCI2010-2011#7] KOLO

description:
Mirko 最近购买了一个命运之轮。 他在每个扇形上写了一个大写英文字母，像这样（比如样例 $3$）：

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

轮中没有字母重复出现，而且轮沿顺时针方向旋转。

轮旋转时，有一个指针停留在同一位置（上图中指向 `H`）。 当我们旋转盘时，指针所指向的字母相应地发生变化。

Mirko 连续旋转了 $k$ 次，每次都记录了箭头指向的字母改变了多少次，以及旋转结束时所指的字母。

Slavko 找到了那张纸，她想知道 Mirko 在车轮的扇形上写了些什么。另外，扇形的总数是已知的。

inputFormat:
输入数据共 $k+1$ 行。

第一行，$2$ 个正整数 $n$，表示车轮上的楔子数，以及 $k$，表示旋转数。

接下来 $k$ 行表示 Mirko 为每次旋转记录的顺序描述。 每行包含一个整数 $s$ 和一个大写字母 $c$，表示该旋转期间指向的字母发生更改的次数，$c$ 表示指针停止处的大写字母。

outputFormat:
如果没有满足上述要求的盘，则输出 $\texttt !$。

否则，盘上的字母，从最后一次旋转结束时的尖头字母开始，然后顺时针方向输出。如果无法确定某些字母，则在对应的位置输出 $\texttt ?$。

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

对于 $100\%$ 的数据，$2 \le n \le 25, 1 \le k \le 100, 1 \le s \le 100$。

#### 说明

本题满分 $50$ 分。

译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T2 KOLO


title: [COCI2010-2011#7] POŠTAR

background:
Mirko 在一个山中小镇里得到了一个邮递员的差事。这个小镇可以用一个 $n \times n$ 的矩阵表示。每个区域有三种状态：用 $\texttt{K}$ 表示房屋，用 $\texttt{P}$ 表示邮局或用 $\texttt{.}$ 表示牧场。此外，每个区域被分配一个高度。

每天早晨，Mirko 都给镇上的每户人家送邮件。他从用 $\texttt{P}$ 表示的区域开始。Mirko 只能水平、垂直或斜向移动到相邻的区域。他一旦送完最后一封邮件，就必须返回邮局。

Mirko 不知道他的工作会有多无聊。令 Mirko 在投递邮件时所到的最高处和最低处的高度之差等于他的疲劳度。帮他找出疲劳度最小的方式，让 Mirko 投递所有的邮件。

description:
给定一个 $n \times n$ 的矩阵。

每个位置可能有 $\texttt{K}$ $\texttt{P}$ $\texttt{.}$ 三种可能状态，此外还有一个高度 $h_{i,j}$。

你需要从状态为 $\texttt{P}$ 的位置开始，水平、垂直或斜向移动，经过所有状态为 $\texttt{K}$ 的位置，最终回到起点。

在这路程中，你需要让经过的位置的 $max_h-min_h$ 最小化。

请你求出最小化的值。

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

下面的 $n$ 行每行 $n$ 个字符表示矩阵。

下面的 $n$ 行每行 $n$ 个正整数，表示区域高度。

outputFormat: 一个非负整数表示最小疲劳度。

hint:
#### 样例 1 解释

从邮局开始，Mirko 可以直接移动到房屋，然后再回到邮局。因为这两个区域高度相同，所以 Mirko的疲劳等于  $0$。

#### 数据规模及约定

对于矩阵，其中 $\texttt{P}$ 将正好出现一次，而 $\texttt{K}$ 将至少出现一次。

对于 $100\%$ 的数据 $2 \le n \le 50$

#### 说明

本题满分 $100$ 分。

译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T4 POŠTAR


title: [COCI2010-2011#7] GITARA

background:
Darko 有一个想象的外星朋友，他有十亿根手指。外星人快速拿起吉他，在网上找到一段简单的旋律并开始弹奏。

这个吉他像寻常一样有六根弦，令其用 $1$ 到 $6$ 表示。每根弦被分成 $P$ 段，令其用 $1$ 到 $P$ 表示。

旋律是一串的音调，每一个音调都是由按下特定的一根弦上的一段而产生的（如按第 $4$ 弦第 $8$ 段）。如果在一根弦上同时按在几段上，产生的音调是段数最大的那一段所能产生的音调。

例：对于第 $3$ 根弦，第 $5$ 段已经被按，若你要弹出第 $7$ 段对应音调，只需把按住第 $7$ 段，而不需放开第 $5$ 段，因为只有最后的一段才会影响该弦产生的音调(在这个例子中是第 $7$ 段)。类似，如果现在你要弹出第 $2$ 段对应音调，你必须把第 $5$ 段和第 $7$ 段都释放。

请你编写一个程序，计算外星人在弹出给定的旋律情况下，手指运动的最小次数。

description:
你有一个 $6 \times P$ 的矩阵 $A$，初始状态皆为 $0$。

对于所有要求 $(i,j)$

你需要满足要求：

1. 此时 $A_{i,j}$ 状态为 $1$。

2. 对于 $A_{i,j+k} (k>0)$ 状态为 $0$。

你在满足要求的情况下需要求状态转换最小次数。

inputFormat:
第一行包含两个正整数 $n$ ，$P$。它们分别指旋律中音调的数量及每根弦的段数。

下面的 $n$ 行每行两个正整数 $i$ ，$j$，分别表示能弹出对应音调的位置——弦号和段号，其为外星人弹奏的顺序。

outputFormat: 一个非负整数表示外星人手指运动次数最小值。

hint:
#### 样例 1 解释
所有的音调都是由第二根弦产生的。首先按顺序按 $8$ $10$ $12$ （$count=3$）。然后释放第 $12$ 段（$count=4$）。最后，按下第 $5$ 段，释放第 $8$ $10$ 段 （$count=7$）。

#### 样例 2 解释
对于每个操作，分别需要 $1$ $1$ $1$ $1$ $3$ $0$ $2$ 次手指运动。

#### 数据规模及约定

按下或释放一段弦各计一次手指运动。弹弦不算手指的移动，而是一个弹吉他的动作。（指你不需要管他怎么弹的，只需要按就是啦，说不定他可以用超能力呀）

对于 $100\%$ 的数据 $n \le 5 \times 10^5$ ，$2 \le P \le 3 \times 10^5$

#### 说明

本题满分 $70$ 分。

译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T3 GITARA


title: [COCI2010-2011#7] UPIT

background:
Mirko 厌倦了为了各种任务去实现各种数据结构。所以，他决定写一个终极数据结构去操纵他最喜欢的数字序列。

快来帮助他吧！

Mirko 会给你他的数列，以及一系列你必须执行的操作。每个询问要么询问关于数列的信息，要么修改现有的数列。下面列出了所有可能的操作类型。

查询种类|描述|例子|
:-:|:-:|:-:
`1 A B X`|将 $[A,B]$ 中所有元素值更改为 $X$|$(9, 8, 7, 6, 5, 4, 3, 2, 1)\to$ $1$ $3$ $5$ $0$ $\to$$(9, 8, 0, 0, 0, 4, 3, 2, 1)$
`2 A B X`|将 $[A,B]$ 中所有元素增加一数，第 $A+k$ 位增加 $(k+1) \times X$|$(9, 8, 7, 6, 5, 4, 3, 2, 1)\to$ $2$ $3$ $5$ $2$ $\to (9, 8, 9, 10, 11, 4, 3, 2, 1)$
`3 C X`|在原来的第 $C$ 位前插入一个数，数值为 $X$|$(9, 8, 7, 6, 5, 4, 3, 2, 1)$$\to$$3$ $4$ $100$ $\to$ $(9, 8, 7, 100, 6, 5, 4, 3, 2, 1)$
`4 A B`|查询 $[A,B]$ 的数值和|$(2, 18, 7, 6, 1, 4, 7, 7, 2)$$\to$ $4$ $6$ $7$ $\to$$result: 11$

description:
给定一个数列 $f$ ，有以下操作。

设数列当前长度为 $n$。

查询种类|描述|
:-:|:-:|:-:
`1 A B X`| $f_i=X(A \le i \le B)$
`2 A B X`| $f_i+=(i-A+1) \times X(A \le i \le B)$
`3 C X`| $f_{i+1}=f_i(C \le i \le n)$ $f_C=X$
`4 A B`| 求$\sum^B_{i=A}f_i$

inputFormat:
第一行两个正整数 $n$ , $Q$，分别表示数列初始长度和操作数量。

第二行 $n$ 个非负整数表示初始数列。

接下来 $Q$ 行每行各包含一个如上询问。

outputFormat: 对于每一个 $4$ 号操作，输出一行答案。

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

设当前数列长 $t$。

对于 $100\%$ 的数据 $1 \le n$ , $Q \le 1 \times 10^5$ , $f_i \le 1 \times 10^5$ , $1 \le X \le 100$ , $1 \le A \le B \le t$ , $1 \le C \le t + 1$。

#### 说明

本题满分 $130$ 分。

译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T6 UPIT。


title: [COCI2010-2011#7]  KUGLICE

background:
Mirko 和 Slavko 喜欢玩弹珠。 在一个激动人心的星期五，Mirko 发明了一个关于弹珠的游戏，他想向 Slavko 展示。

在游戏中，Mirko 构造了一个有向图，其中每个点出度不超过 $1$。然后他在其中一个点上放了一个弹珠，只要弹珠在某个顶点 $X$ 上，弹珠就会移动到由一条边连接的相邻顶点（没有就算了）。弹珠的运动一直持续到弹珠到达一个没有出度的点为止。弹珠也有可能因没有出度为 $0$ 的点而无限遍历图。为了确保 Slavko 能理解游戏规则，Mirko 会问一系列问题。

询问类型如下:

1. `1 X`：除非弹珠卡在一个循环，求弹珠被放在 $X$ 后最后的终止点序号。

2. `2 X`：删除顶点 $X$ 的出边。（保证存在）

注意：查询有序。

description:
给定一个有向图，其中每个点出度为 $0$ 或 $1$。

有如下询问：

1. `1 X`：给定弹珠起始点 $X$，求弹珠运动的终止点。

2. `2 X`：删除 $X$ 点出边。（保证存在）

弹珠运动规则：

从初始点沿着出边走直到一点出度为 $0$。

inputFormat:
第一行一个正整数 $n$，指图中顶点数。

第二行 $n$ 个正整数，其中第 $i$ 个数表示 $i$
的出边指向点序号，若 $0$ 则指不存在。

下面一行一个正整数 $Q$，指查询数目。

下面 $Q$ 行每行包含一个上述格式的查询。

outputFormat:
对于每个类型 $1$ 的查询，按照顺序，每行输出弹珠停止点序号。

如果弹珠永不停止，则输出 $\texttt{CIKLUS}$。

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

对于 $100\%$ 的数据 $1 \le n,Q \le 3 \times 10^5$。

#### 说明

本题满分 $120$ 分。

译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T5 KUGLICE。


title: 「MCOI-02」Glass 玻璃

background: 小 S 进入了一个服务器，这个服务器有一个游戏叫“树上的玻璃”。

description:
首先给定一棵树，每个点上有 $V_i$ 个玻璃，每条边上有权值 $W_i$。

每次操作小 S 可以选择两个节点 $u,v(u\ne v)$，从节点 $u$ 到节点 $v$ 的唯一路径上，**边和** 为路径上所有边的权值和，即 $\sum W_i$，**点和** 为路径上所有点（包括 $u,v$）的玻璃数和，即 $\sum V_i$。小 S 将可以获得 **边和** 和 **点和** 的乘积的分数，即 $\sum W_i\times\sum V_i$。

任意两次操作不能完全相同，$(u,v)$ 和 $(v,u)$ 被看作是两种操作。

但是有时候这颗树太过庞大，小 S 需要你的帮助。他需要你告诉他，经过 $N(N-1)$ 次操作后，总共能得到多少分。结果可能很大，你只需要输出答案对 $998244353$ 取模的结果。

inputFormat:
第一行一个整数 $N$ 表示树的节点数。
第二行 $N$ 个整数，第 $i$ 个数 $V_i$ 表示节点 $i$ 的玻璃数。
接下来 $N-1$ 行，每行三个数 $x,y,z$，表示节点 $x,y$ 之间连有一条权值为 $z$ 的树边。

outputFormat: 一个整数，即总共能得到的分对 $998244353$ 取模。


title: [POI 2019] Najmniejsza wspólna wielokrotność / 最小公倍数

background: Byteasar 正在准备他的数学考试。

description:
老师跟他说考试题目中有关于最小公倍数 $\rm lcm$ 的题目，于是他找到了一道题练练手。

给定一个整数 $M$，求一个区间 $[a,b]$ 使得 $M$ 为这个区间所有数的最小公倍数。

因为您很强，所以 Byteasar 在解出来这道题的同时也想问问您这题的答案。

因为 Byteasar 非常爱问问题，所以他要问您 $z$ 组问题。

inputFormat:
第一行一个整数 $z$ 代表询问个数。
接下来 $z$ 行每行一个整数 $M$ 代表一个询问。

outputFormat:
$z$ 行每行两个整数 $a,b$ 代表一个询问的答案。
如果有多组解：

- 输出 $a$ 最小的
- 如果还有多组解输出 $b$ 最小的

hint:
#### 样例说明

对于样例 $1$ 的第一组数据，$12$ 为区间 $[1,4]$ 的最小公倍数。

另一组附加样例见附加文件的 sample.in 和 sample.out。

#### 数据规模与约定

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

- Subtask 1（18 pts）：$z \le 10$，$M \le 1000$。
- Subtask 2（20 pts）：$z\le 100$，$M \le 10^9$。
- Subtask 3（20 pts）：$z \le 100$，$M \le 10^{18}$。
- Subtask 4（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le z\le 10^4$，$1 \le M \le 10^{18}$。

#### 说明

翻译自 [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) A [Najmniejsza wspólna wielokrotność](https://sio2.mimuw.edu.pl/c/oi27-1/p/nww/)。


title: [POI 2019] Pomniejszenie / 削减

background: Bajtek 和 Bitek 是兄弟俩（Bajtek 是哥哥），他们要玩一个游戏。

description:
游戏规则为：写下较大数的人获胜。

假设 Bajtek 写的是 $A$，Bitek 写的是 $B$。$A$ 和 $B$ 的长度相等，且可能有前导零。

但是每次比赛都是 Bajtek 赢（即总是 $A \ge B$），所以 Bajtek 想输一次。

他现在可以修改 $A$ 上的 **恰好** $k$ 位，使得 $A$ 比 $B$ 小。

求 $A$ 修改后比 $B$ 小的最大值。

如果无法使得 $A$ 比 $B$ 小，输出 `-1`。

因为兄弟俩很喜欢玩这个游戏，所以他们要玩 $t$ 局，即要进行 $t$ 次修改与判断。

inputFormat:
第一行一个整数 $t$ 代表局数。
接下来 $t$ 行每行三个整数 $A,B,k$ 代表 Bajtek 写的数，Bitek 写的数，和允许的修改次数。

outputFormat:
$t$ 行每行一个整数代表 $A$ 经过修改后比 $B$ 小的最大值。
如果 $A$ 怎样修改都不能使得 $A$ 比 $B$ 小，输出 `-1`。

hint:
#### 样例说明

前两组附加样例分别对应附加文件中的 sample1/2.in 和 sample1/2.out。

第三组附加样例为 sample3.zip。

#### 数据规模与约定

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

假设这里的 $n$ 为 $A,B$ 的长度：

- Subtask 1（18 pts）：$1 \le n \le 5$。
- Subtask 2（20 pts）：$1 \le n \le 5000$。
- Subtask 3（20 pts）：$1 \le n \le 10^5$，$k=1$。
- Subtask 4（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le t \le 100$，$1 \le k \le n \le 10^5$，$A \ge B$。

#### 说明

翻译自 [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) C [Pomniejszenie](https://sio2.mimuw.edu.pl/c/oi27-1/p/pom/)。


title: [POI 2019] Przedszkole / 幼儿园

background: 幼儿园的早上，老师们要给小孩子发玩具。

description:
有些小孩子玩玩具是自己一个人玩，有些小孩子是成对玩耍。

现在有 $n$ 个小孩子，这 $n$ 个小孩子可以分为 $m$ 对。

有 $k$ 种玩具，要发放给这些小孩子，必须保证在一对内的小孩子拿到的玩具不同。

求一共有多少种发放方案。

因为要发放的天数很多，所以给定 $z$ 组询问，这 $z$ 组询问中 $n,m$ 和对应的对是不变的，变的是 $k$。

inputFormat:
第一行三个整数 $n,m,z$ 代表小孩子数，成对数和询问数。
这 $n$ 个小朋友编号为 $1$ 到 $n$。
接下来 $m$ 行每行两个整数代表一对小朋友。
接下来 $z$ 行每行一个整数 $k$ 代表一组询问。

outputFormat:
$z$ 行每行一个整数代表发放方案数。
答案对 $10^9+7$ 取模。

hint:
#### 样例说明

两个附加样例请见附加文件中的 sample 1/2.in 和 sample 1/2.out。

#### 数据规模与约定

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

- Subtask 1（8 pts）：$n,k \le 8$，$z \le 50$。
- Subtask 2（26 pts）：$n \le 15$。
- Subtask 3（33 pts）：$m \le 24$。
- Subtask 4（33 pts）：一个小朋友恰好在两对小朋友。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le m \le \min(10^5,\dfrac{n^2-n}{2})$，$1 \le z \le 1000$，$1 \le k \le 10^9$。

对于其中 $50\%$ 的数据，$z=1$。

#### 说明

翻译自 [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) D [Przedszkole](https://sio2.mimuw.edu.pl/c/oi27-1/p/prz/)。


title: [POI 2019] Układ scalony / 集成电路

background:
Bajtel 公司专门生产集成电路板。

---

因为数据较多，所以 Subtask 1 的另一部分挪到了 [这里](https://www.luogu.com.cn/problem/U122678)。

description:
Bajtel 公司生产的集合电路板的大小为 $n \times m$，现在通电的格子为 $(1,1)$。

我们可以在两个相邻的格子连上电路让一个格子的电通向另一个格子，若干个电路组成集合电路。

现在我们要连 $n \times m-1$ 条电路，并且要求最长的集合电路 **恰好** 长度为 $k$，并且要求 **让所有格子通电**。

求一种连接电路的方式。

inputFormat: 一行三个整数 $n,m,k$ 代表电路板的大小和最长的集合电路必须满足的长度。

outputFormat:
如果没有满足题意的连接方式，输出一个字符串 `NIE` 并结束程序。
如果有满足题意的连接方式：
第一行一个字符串 `TAK`。
接下来 $n \times m-1$ 行每行四个整数 $u_1,v_1,u_2,v_2$ 代表一个电路连接 $(u_1,v_1)$，$(u_2,v_2)$。
如果有多组满足题意的解，输出一组即可。

samples:
2 3 1
NIE

hint:
#### 样例说明

对于样例 $1$，如下图

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

另一组附加样例请见附加文件中的 sample.zip。

#### 数据规模与约定

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

- Subtask 1（20 pts）：$n,m \le 6$。
- Subtask 2（20 pts）：$n \le 3$。
- Subtask 3（30 pts）：$n \times m$ 为奇数。
- Subtask 4（30 pts）：$n \times m$ 为偶数。

对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$0 \le k \le 10^6$。

如果您输出了 `TAK`（并且这个数据点的确有解），但是您在后面电路连接的描述中出错，您可以获得 $20\%$ 的分数。

#### 说明

翻译自 [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) E [Układ scalony](https://sio2.mimuw.edu.pl/c/oi27-1/p/ukl/)。


title: [POI 2019] Pisarze / 作家

background:
Bajtek 拿到了一些波兰文的句段，他想知道这个这个句段从哪本书来的。

**本题为数据分析题。**

# 请用 C++14/C++17 提交以避免不必要的 CE。

description:
他找到了 $t$ 个句段，并且确定这些句段来自以下三本书

- Adama Mickiewicza 的 Pan Tadeusz
- Henryka Sienkiewicza 的 Quo Vadis
- Bolesława Prusa 的 Lalka

求具体来自哪一本书。

inputFormat:
第一行一个整数 $t$ 代表句段数。
接下来 $t$ 行每行一个字符串 $s_i$ 代表一个句段。

outputFormat: $t$ 行每行一个字符串代表答案，输出该文章的作者 Mickiewicz，Prus 或 Sienkiewicz。

samples:
3
Petroniusz obudzil sie zaledwie kolo...
Litwo! Ojczyzno moja! ty jestes jak...
W poczatkach roku 1878, kiedy swiat...

hint:
#### 样例说明

样例只截取了一部分，真正的样例见附加文件中的 sample.in 与 sample.out。

#### 数据规模与约定

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

- Subtask 1（20 pts）：$t \le 100$，$500 \le |s_i| \le 2000$。
- Subtask 2（20 pts）：每行一定为完整的句子。
- Subtask 3（30 pts）：$30 \le |s_i| \le 80$。
- Subtask 4（30 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le t \le 1000$，$10 \le |s_i| \le 2000$，$\sum|s_i| \le 2 \times 10^6$。

**本题为数据分析题。**

**本题采用 Special Judge**，您不需要准确识别每一组数据，SPJ 机制如下：

- 假设 $t$ 为句段数，$p$ 为您答对的句段数。
- 如果 $p \ge 0.9 \times t$，那么您就会得到 $100\%$ 的分数。
- 如果 $p \le \dfrac{t}{3}$，很遗憾，您不会得到任何分数。
- 其他情况，您会得到 $100\times \dfrac{p-\frac{t}{3}}{0.9\times t-\frac{t}{3}}\%$ 的分数。

附加文件中的 Mickiewicz.txt，Prus.txt 和 Sienkiewicz.txt 代表三段句段。

数据生成器见附加文件中的 pistestgen.py，使用 `python3 pistestgen.py subtask name directory [seed]` 来生成一组数据，其中：

- grupa 代表子任务的编号，从 $1$ 到 $4$
- nazma 为数据名，将会生成在 nazma.in 与 nazma.out 中
- katalog 为这三本书的文件夹
- ziarno 用于生成同一组数据

#### 说明

翻译自 [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) B [Pisarze](https://sio2.mimuw.edu.pl/c/oi27-1/p/pis/)。


title: [PA 2015 Final] Edycja

description:
给定两个长度为 $n$ 的等长的小写字母串 A 和 B，你可以做以下两种操作：
1. 把 A 中某个位置上的字符修改成另一个字符，用时 1 秒。比如：```ababc``` 变成 ```ababa```。
2. 把 A 中某种字符全部修改成另一个种字符，用时 $c$ 秒。比如：```ababc``` 变成 ```acacc```。

同一时间只能做一个操作，求把 A 变成 B 的最小总耗时。

inputFormat:
第一行包含两个正整数 $n,c$，分别表示串长和操作 2 的代价。

第二行包含一个长度为 $n$ 的小写字母串 A。

第三行包含一个长度为 $n$ 的小写字母串 B。

outputFormat: 输出一个整数，即把 A 变成 B 的最小总耗时。

hint:
#### 样例解释
先把所有的 a 都修改成 b，然后再把第 4 个位置的 b 和第 5 个位置的 c 都修改为 a。

#### 数据范围
对于所有数据，满足 $1\le c\le n\le10^6$。


title: [POI1997] Genotype

background: Genotype 是一个独特的基因串。

description:
我们可以用大写英文字母 $A-Z$ 来描述 Genotype，每个字母就代表一个基因。

规定一种「分裂」规则，由三个大写字母 $A_1A_2A_3$ 组成，代表 $A_1$ 可以「分裂」为 $A_2A_3$。

现在给定 $n$ 个「分裂」规则和 $k$ 个 Genotype，判断这些 Genotype 是否能从一个特定的 **只包含大写字母 $S$ 的** 串通过「分裂」规则得到，如果可以的话输出特定的串的长度的最小值，如果不可以的话输出 `NIE`。

inputFormat:
第一行一个整数 $n$ 代表「分裂」规则数。
接下来 $n$ 行每行三个大写字母 $A_1,A_2,A_3$ 代表一个「分裂」规则。
接下来一行一个整数 $k$ 代表给定的 Genotype 数。
接下来 $k$ 行每行若干个大写字母表示一个 Genotype。

outputFormat:
$k$ 行：

- 如果没有特定的串通过「分裂」规则得到这个 Genotype，输出 `NIE`。
- 如果有特定的串通过「分裂」规则得到这个 Genotype，输出这个特定的串的最小长度。

samples:
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

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

对于 $100\%$ 的数据，$1 \le n,k \le 2000$，Genotype 的长度最大为 $100$。


title: [CCO2018] Flop Sorting

description:
Robert 创建了一道线段树题，题目是：

给定长为 $N$ 的排列 $a_i$，我们规定一个翻牌操作为将一个区间的最小值与最大值交换。现在给定您 $Q$ 个翻牌操作，每次对 $[l,r]$ 执行翻牌操作，求进行 $Q$ 次翻牌操作后的最终序列。

搞好了题目描述，接下来要搞数据了。

现在给定了 $N$，初始序列 $a_i$ 和最终序列，求中间要进行的翻牌操作。

inputFormat:
第一行一个整数代表序列长度 $N$。
第二行 $N$ 个整数代表初始序列 $a_i$。
第三行 $N$ 个整数代表最终序列。

outputFormat:
首先第一行一个整数 $Q$ 代表要进行的翻牌操作的次数。
接下来 $Q$ 行每行两个整数 $l,r$ 代表对 $[l,r]$ 进行翻牌操作。

hint:
#### 样例说明

对于样例 $1$，执行的 $4$ 次翻牌操作为：

- 对 $[2,3]$ 进行翻牌操作，交换 $3$ 和 $5$
- 对 $[3,6]$ 进行翻牌操作，交换 $6$ 和 $2$
- 对 $[2,5]$ 进行翻牌操作，交换 $5$ 和 $2$
- 对 $[4,5]$ 进行翻牌操作，交换 $5$ 和 $4$

#### 数据规模与约定

对于 $100\%$ 的数据，$1 \le a_i \le N \le 4096$，$1 \le Q \le 3 \times 10^5$，$1 \le l\le r \le N$。
对于其中 $20\%$ 的数据，$N \le 100$。
对于另外 $40\%$ 的数据，$N \le 2048$。

#### 说明

翻译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) Day 2 [C Flop Shorting](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day2.pdf)。


title: [CCO2018] Boring Lectures

description:
有一个长为 $N$ 的数列，第 $i$ 个数为 $a_i$。

有 $Q$ 次修改，第 $j$ 次会将第 $i_j$ 个数改成 $x_j$。

您需要求出在最初和每次修改之后连续的的 $K$ 个元素中，最大值与次大值的和最大是多少。

inputFormat:
第一行三个整数 $N,K,Q$ 见题目描述。
第二行 $N$ 个整数 $a_i$ 为这个序列。
接下来 $Q$ 行每行两个整数 $i_j,x_j$ 代表一次更改。

outputFormat: $Q+1$ 行第 $j$ 行代表第 $j-1$ 次修改后得到的答案，第一行就代表未修改前得到的答案。

hint:
#### 样例说明

对于样例 $1$

- 还未修改时，我们选定 $[1,3]$，得到的和为 $6+2=8$
- 进行第一次修改时，我们选定 $[2,4]$，得到的和为 $2+4=6$

#### 数据规模与约定

对于 $100\%$ 的数据，$2 \le N \le 10^6$，$2 \le K \le N$，$0 \le Q \le 10^5$，$0 \le a_i \le 10^9$，$1 \le i_j \le N$，$0 \le x_j \le 10^9$。
对于 $20\%$ 的数据，$Q=0$。
对于另外 $40\%$ 的数据，$N \le 10^4$。

#### 说明

翻译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) Day 2 [B Boring Lectures](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day2.pdf)。


title: [CCO2018] Gradient Descent

background: **本题为交互题。**

description:
Troy 要和您一起玩游戏，他的游戏要用一个 $R \times C$ 的棋盘。

现在给定 $N$ 个棋子（从 $1$ 编号到 $N$），第 $i$ 个棋子放置在 $(X_i,Y_i)$ 处，**同一格可能有多个棋子**。

Troy 可以在一秒内将一个棋子移动到与其垂直或水平相邻的格子中，格子的分数就被 Troy 定义为将这 $N$ 个棋子挪到这个格子的秒数的最小值，您要做的就是找棋盘中格子里的分数的最小值。

Troy 不会告诉您 $N$ 的值和每个棋子的位置，但是您可以问 Troy 最多 $K$ 个问题：格子 $(p,q)$ 的分数。

#### 交互策略

**本题为交互题。**

首先，读入三个整数 $R,C,K$ 代表整个棋盘的大小，和您最多能问多少个问题。

读入完这一行后，您的程序将会对提出关于 $(p,q)$ 的分数的问题（格式为 `? p q`），然后您就会得到一个整数 $s$ 带包这个格子的分数。

一旦您的程序确定了棋盘中的格子的分数的最小值，那么就会输出 `! Z` 并终止程序，$Z$ 就代表最终结果。

在输出每一行后，都应刷新缓冲区：

- C/C++：`fflush(stdout)` or `cout << endl `
- Java：`System.out.flush() `
- Pascal：`flush(output)`

如果您输出的格式有误，或者提出的问题超过了 $K$ 个，您的答案就是错误的。


title: [BalticOI 2005] Polygon

description: 给定一个凸包的每条边的长度，求这个凸包。

inputFormat:
第一行一个整数 $N$ 代表点数。
接下来 $N$ 行每行一个整数 $a_i$ 代表一条边的长度，其中 $a_i$ 代表第 $i$ 个点与第 $i+1$ 个点之间的边的长度，$a_n$ 代表第 $n$ 个点与第 $1$ 个点之间的边的长度。

outputFormat:
$N$ 行每行两个实数 $x_i,y_i$ 代表一个点的坐标。（需要满足 $|x_i|,|y_i| \le 10^7$）
如果有多组解任意输出一组即可。
如果无解输出 `NO SOLUTION`。

**注意请按照逆时针输出输出凸包上的点。**
虽然原题说顺时针或逆时针顺序输出皆可，但是在本题中 **请严格按照逆时针方向输出**。
不一定必须按照编号的顺序输出，比如说点 $P_1\to P_2 \to P_3$ 是逆时针顺序，那么按照 $P_2 \to P_3 \to P_1$  也可。

hint:
#### 样例说明

对于样例 $1$：

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

#### 数据规模与约定

对于 $100\%$ 的数据，$3 \le  N \le 1000$，$1 \le a_i \le 10^4$。

**本题使用 Special Judge。**

感谢 spj 作者 @[tiger2005](https://www.luogu.com.cn/user/60864)。

#### 说明

翻译自 [BalticOI 2005 Day2 C Polygon](https://boi.cses.fi/files/boi2005_day2.pdf)。


title: [BalticOI 2005] Ancient Manuscript

description:
给定 Baltic 字符串的定义为：

- 全部为小写字母
- 最多只能有 $V_C$ 个连续的元音
- 最多只能有 $C_C$ 个连续的辅音
- 最多只能有 $V_E$ 个连续的元音相等
- 最多只能有 $C_E$ 个连续的辅音相等

`aeiou` 为元音，除了这五个字母之外的 21 个字母为辅音。

现在给定一个字符串，一些字符为小写字母一些字符为 `*`，您可以把 `*` 替换成任意一个小写字母。

求通过替换能使得这个字符串得到的不同的 Baltic 字符串的种类数。

inputFormat:
第一行四个整数 $V_E,V_C,C_E,C_C$，具体含义见题面描述。
第二行一个字符串，具体含义见题目描述。

outputFormat:
一行一个整数代表通过替换能使得这个字符串得到的不同的 Baltic 字符串的种类数。

答案是 $64$ 位有符号整数。

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

对于 $100\%$ 的数据，$1 \le V_E \le V_C \le 4$，$1 \le C_E \le C_C \le 4$，$1 \le\ $字符串的长度$\ \le 15$。

#### 说明

翻译自 [BalticOI 2005 Day2 A Ancient Manuscript](https://boi.cses.fi/files/boi2005_day2.pdf)。


title: [BalticOI 2005] Magic Parenthesis

background:
合法括号串的定义：

- `()` 是合法的
- 如果 `A` 是合法的，那么 `(A)` 是合法的
- 如果 `A` 和 `B` 是合法的，那么 `AB` 是合法的

description:
给定一个长为 $N$ 的字符串 $S$，由 `(`，`)` 和 `]` 组成。

整个字符串中有 $M$ 个 `]`，其他全为左右括号。

现在得知可以用若干个 `)` 来替换 `]`，求一种通过替换 $S$ 中的 `]` 得到合法括号串的做法。

inputFormat:
第一行两个整数 $N,M$ 代表字符串的长度与 `]` 的个数。
第二行 $N$ 个字符代表字符串 $S$。

outputFormat:
如果无解，输出 `0` 并结束程序。
如果有解，首先输出一个 `1`，然后接下来 $M$ 行每行一个整数代表每一个 `]` 要替换多少成个 `)`。

hint:
#### 样例说明

对于样例 $1$，按照输入替换后得到的 $S$ 为 `((((()))))`，为合法括号串。

#### 数据规模与约定

对于 $100\%$ 的数据，$0 \le N \le 10^7$，$0 \le M \le 5 \times 10^6$，$M \le N$。

**本题使用 Special Judge。**

感谢 spj 提供者 @[tiger2005](https://www.luogu.com.cn/user/60864)。

#### 说明

翻译自 [BalticOI 2005 Day1 B Magic Parenthesis](https://boi.cses.fi/files/boi2005_day1.pdf)。


title: 「C.E.L.U-01」族谱树

background: 小 Soup 正在翻看他们家的族谱，他们家的族谱构成了一棵树。小 Soup 发现，由于年代久远，他们家族中的一些分支已经绝迹，他对此十分好奇。

description: 小 Soup 给你他们家的族谱树，想要问你在这棵树中**所有**第 $k$ 层的孩子（树中深度为 $k$ 的点，根节点的深度为 $1$ ,根节点编号为 $1$ ）的 $\text{最近公共祖先}$ 是谁。

inputFormat:
第一行两个整数 $n,m$。
第二行 $n$ 个整数，其中第 $i$ 个整数为 $f_i$，表示 $i$ 的父亲为 $f_i$，请注意，$1$ 的 $f_i$ 固定为 $0$。
接下来 $m$ 行，每行一个整数 $k$，代表小 Soup 的询问。

outputFormat: 对于每个小 Soup 的询问，输出一个整数，即**所有**深度为 $k$ 的点的 $\text{最近公共祖先}$。

hint:
样例解释1：
![](https://cdn.luogu.com.cn/upload/image_hosting/zgcgu0da.png)

样例解释2：
![](https://cdn.luogu.com.cn/upload/image_hosting/l02zvtkv.png)

#### 数据保证存在深度为 $k$ 的点

$\begin{array}{|c|c|c|}数据编号&n,m&特殊性质\\1&\le10&\diagdown\\2&\le100&\diagdown\\3\sim4&\le10^3&\diagdown\\5&\le3\times10^5&树为一条链\\6&\le3\times10^5&\diagdown\\7\sim10&\le3\times10^6&\diagdown\\11\sim12&\le5\times10^6&\diagdown\end{array}$

对于 $100\%$ 的数据，$n\le5\times10^6,m\le n$。

温馨提示：此题较卡常，请注意大常数带来的影响以及时空复杂度。如果你被卡常了，可以试试使用快速读入。


title: [BalticOI 2020 Day1] 染色

description:
Linda 喜欢时不时改变她头发的颜色，如果她的男友 Archie 注意到她头发颜色发生了改变，Linda 会十分高兴。当且仅当 Archie 发现 Linda 的头发颜色发生改变时，Archie 才会去评论 Linda 头发的新颜色。这意味着 Linda 始终可以知道 Archie 是否发现她的头发颜色有改变。

现在市场上有一个新染发剂系列，该染发剂系列有 $N$ 种颜色，从 $1$ 到 $N$ 编号。两个颜色的相近程度与它们编号的差值有关——差值越小，则越相近。

Linda 发现，对于该系列的染发剂，存在一个色差阈值 $C$（$1 \leq C \leq N$）。具体来说，假如 Linda 之前使用的染发剂颜色编号为 $color_{prew}$，Linda 接下来打算使用的染发剂颜色编号为 $color_{new}$，则 Archie 会注意到 Linda 的颜色头发差异，当且仅当 $\left | color_{new}-color_{prew}\right | \geq C$。

现在 Linda 买下了一套该系列的染发剂，准备做一个实验。她会不断地更换头发的颜色，并观察 Archie 是否注意到了头发颜色发生改变。因为染发剂有限，每种颜色的染发剂最多只能使用一次。

在实验开始之前，Linda 使用的是另外一个系列的染发剂，因此讨论第一次染发后 Archie 的反应是没有意义的。

现在 Linda 想要通过有限的时间找到阈值 $C$，请写一个程序帮助她完成这个任务。

### 交互方式

本题是一道交互题。

**与原题不同的是，为了压缩数据组数，本题单个测试点中将包含多组数据。**

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

对于每组数据，你首先将读入一个整数 $N$，代表该系列染发剂的颜色数量。

接下来，你可以按如下形式输出来进行询问：`? P`。其中 $P$ 代表 Linda 下一次要使用的染发剂的颜色编号。你输出的 $P$ 需要满足 $1 \leq P \leq N$，且任意两次询问的 $P$ 均不相同。

在询问过后，你的程序将读入一个整数，若这个整数为 $1$，代表 Archie 注意到了 Linda 头发颜色的变化；若为 $0$，则表示他没有注意到颜色的变化。

当你确认了阙值 $C$ 后，按如下格式输出答案：`= C`。

如果答案正确，将会直接进入下一组数据的交互。

如果答案错误，交互器将直接终止你的程序。

对于每组测试数据，你的程序可以最多进行 $64$ 次询问（最后输出答案不算作询问）。

请注意，一般情况下程序的输出会存放在缓冲区中，为了确保你的输出能被交互库接收，请在输出一行之后刷新缓冲区。

- 对于 C++ 语言，可以使用 `std::cout<<std::endl` 来在输出换行的同时刷新缓冲区；
- 对于 Java 语言，可以使用 `System.out.flush();` 来刷新缓冲区；
- 对于 Python 语言，可以使用 `sys.stdout.flush()` 来刷新缓冲区。

hint:
### 样例解释

为了方便各位理解交互过程，部分行之间人为添加了空行。

下面依次解释每次询问过程：

1. 这一次询问的结果无意义。
2. 此次询问后有 $C \leq 5$；
3. 此次询问后有 $3 \lt C \leq 5$，这时候可以考虑检测差值为 $4$ 时的情况。但因为 $4+4=8$ 和 $4-4=0$ 都不合法，因此不再考虑这么做。
4. 此次询问后有 $3 \lt C \leq 5$。
5. 此次询问后有 $3 \lt C \leq 4$，即 $C=4$。

### 子任务

所有数据均满足：$1 \leq T \leq 1200$，$1 < N \leq 10^{18}$。

- 子任务 1（9 分）：$N \leq 64$；
- 子任务 2（13 分）：$N \leq 125$；
- 子任务 3（21 分）：$N \leq 10^3$；
- 子任务 4（24 分）：$N \leq 10^9$；
- 子任务 5（33 分）：无特殊限制。


title: [BalticOI 2020 Day1] 混合调料

description:
著名餐厅 *Salt, Pepper & Garlic* 的主厨 Serge 准备好成为一名米其林一星厨师。他已被告知，今晚一位秘密评审员将光临他的餐厅。

虽然他并没有得知这位评审员的姓名，但他已经得知了这位评审员将要点的菜和他的口味偏好。具体来说，这位评审员希望在菜肴中加入非常精确比例的盐，胡椒粉和大蒜粉。

Serge 在厨房的一个架子上放了若干盐，胡椒粉和大蒜粉的混合调料瓶。对于每种调料瓶，Serge 都知道该调料瓶中混合的盐，胡椒粉和大蒜粉的量（单位为千克），他可以通过将任意多瓶调料混合起来（当然也可以单独使用一瓶调料），得到所需比例的调料。

事实上菜肴里放的调料量并不多，因此可以认为调料的量是足够的。但是，评审员要求的盐，胡椒粉和大蒜粉的量之比中的数字可能非常大。

现在 Serge 想要求出，是否能够利用已有的调料瓶配制出满足评审员要求比例的调料？如果能够配制，最少需用多少个瓶子？

此外，Serge 可能会拿到新的调料瓶，或者将架子上已有的调料瓶给其他厨师，这意味着架子上的瓶子种类会不断发生改变，Serge 希望在每次架子上的调料瓶发生变化后，再解决上面的问题。

举个例子，假如评审员要求的盐，胡椒粉和大蒜粉的量的比例为 $1:1:1$，架子上有以下几种调料瓶：

| 调料瓶编号 |  盐  | 胡椒粉 | 大蒜粉 |
| :--------: | :--: | :----: | :----: |
|     1      |  10  |   20   |   30   |
|     2      | 300  |  200   |  100   |
|     3      |  12  |   15   |   27   |

则只需将瓶子 $1$ 中的全部调料，和瓶子 $2$ 中的 $60$ 千克调料（其中包括盐 $30$ 千克，胡椒粉 $20$ 千克，大蒜粉 $10$ 千克）混合即可满足要求。一旦取走瓶子 $2$，则无法满足评审员的要求。

inputFormat:
输入第一行包含三个整数 $S_f,P_f,G_f$，表示评审员要求的盐，胡椒粉，大蒜粉的量之比为 $S_f:P_f:G_f$，$\forall \alpha \gt 0$，$(\alpha S_f,\alpha P_f, \alpha G_f)$ 的混合调料也满足评审员要求。

下一行一个整数 $N$，表示架子上的瓶子要进行 $N$ 次变动。最开始架子上没有瓶子。

接下来 $N$ 行，每行描述一次变动。

- 若架子上新增了瓶子，则该行包含一个大写字母 `A` 和三个整数 $S_i,P_i,G_i$，分别代表该瓶中盐，胡椒粉，大蒜粉的量。瓶子按加入的先后顺序从 $1$ 开始编号，即如果该瓶子是第 $i$ 个加入架子的，则其编号为 $i$。
- 若架子上移除了瓶子，则该行包含一个大写字母 `R` 和一个整数 $r_i$，代表移除的瓶子编号。保证该编号的瓶子在架子上。

outputFormat: 输出 $N$ 行。第 $i$ 行输出在第 $i$ 次变动后，满足评审员要求所需的最少瓶子数量。特别地，若不存在一种方案满足评审员的要求，输出 $0$。

hint:
所有数据均满足：$1 \leq N \leq 10^5$，$S_f,P_f,G_f \geq 0$，$0 \lt S_f+P_f+G_f \leq 10^6$，$S_i,P_i,G_i \geq 0$，$0 \lt S_i+P_i+G_i \leq 10^6$。

- 子任务 1（13 分）：$N \leq 50$，$0 \lt S_i+P_i+G_i \leq 10^2$；
- 子任务 2（17 分）：$N \leq 500$，$0 \lt S_i+P_i+G_i \leq 10^3$；
- 子任务 3（30 分）：$N \leq 5000$，$0 \lt S_i+P_i+G_i \leq 10^4$；
- 子任务 4（40 分）：无特殊限制。


title: [BalticOI 2020 Day1] 小丑

background: 由于官方测试数据量过大，为了避免过多资源占用，这里选取了部分官方数据作为本题测试数据。

description:
小丑回到了哥谭市，准备执行一个邪恶的计划。哥谭市有 $N$ 个路口（编号从 $1$ 到 $N$），$M$ 条道路（编号从 $1$ 到 $M$）。一条道路连接两个不同的路口，且两个路口间最多只有一条道路相连。

为了实现他的邪恶计划，小丑需要在城市中走完一个奇环。形式化地说，一个奇环为一个形如 $S,s_1,s_2,\ldots,s_k,S$ 的序列（要求 $k$ 为偶数），其中 $S$ 和 $s_1$，$s_k$ 和 $S$，以及 $\forall 1 \lt i \leq k$，$s_{i-1}$ 和 $s_i$ 之间都有道路直接相连。

然而，警察控制了城市中的部分街道。在第 $i$ 天，警察控制了编号在 $[l_i,r_i]$ 范围内的所有街道，小丑不能经过这些街道。然而小丑通过买通警察局的内鬼，了解到了警察在未来 $Q$ 天控制街道的计划，现在小丑想要知道，在哪些日子里，他的邪恶计划可以实现。

inputFormat:
输入第一行三个整数 $N,M,Q$。

接下来 $M$ 行，第 $i$ 行两个整数 $u,v$（保证 $u \neq v$），描述了编号为 $i$ 的街道。其连接了 $u$ 和 $v$ 两个路口。保证两个路口间最多只有一条街道相连。

接下来 $Q$ 行，第 $i$ 行两个整数 $l_i,r_i$，表示警察在第 $i$ 天将要控制编号在 $[l_i,r_i]$ 范围内的所有街道。

outputFormat:
输出 $Q$ 行。

在第 $i$ 行，若第 $i$ 天小丑的计划可以实现，输出 `YES`，否则输出 `NO`。

hint:
### 样例解释

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

### 子任务

所有数据均满足：$1 \leq N,M,Q \leq 2 \times 10^5$。

- 子任务 1（6 分）：$1 \leq N,M,Q \leq 200$；
- 子任务 2（8 分）：$1 \leq N,M,Q \leq 2 \times 10^3$；
- 子任务 3（25 分）：$\forall i \in [1,Q]$，$l_i =1$；
- 子任务 4（10 分）：$\forall i \in [1,Q]$，$l_i \leq 200$；
- 子任务 5（22 分）：$Q \leq 2 \times 10^3$；
- 子任务 6（29 分）：无特殊限制。


title: [CCO2018] Geese vs. Hawks

background: 本题题面来自 [LOJ](https://loj.ac/p/3514)。

description:
Troy 和 JP 是冰球迷。这个赛季每个冰球队会进行 $N$ 场比赛。每场比赛在两个队之间进行，得分更高者胜。并且不会出现平局的情况。

Troy 最喜欢的队伍是滑铁卢野鹅队，他记录了这个队每场比赛的结果。比赛结果记作一个字符串 $S$。如果野鹅队赢下了第 $i$ 场比赛，则 $S_i=\texttt{W}$，否则 $S_i=\texttt{L}$。他同时记下了在第 $i$ 场比赛，他们获得了 $A_i$ 分。

JP 最喜欢的队伍是劳里埃金鹰队，他也记录了这个队每场比赛的结果。比赛结果记作一个字符串 $T$。如果金鹰队赢下了第 $j$ 场比赛，则 $T_j=\texttt{W}$，否则 $T_j=\texttt{L}$。他同时记下了在第 $j$ 场比赛，他们获得了 $B_j$ 分。

Troy 和 JP 均按顺序记录了他们喜欢的队伍每场比赛的结果和分数。

一次同城德比是指一场滑铁卢野鹅对劳里埃金鹰的比赛（因为两队主场均在滑铁卢）。因为 Tory 和 JP 都没有记录他们最喜欢的球队在比赛中的对手，所以他们不能确定有没有同城德比，也确定不了哪些场比赛是同城德比。他们想知道，根据他们记录的信息推算，在所有同城德比中，两队取得分数总和的最大值是多少。

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

第二行包含一个长为 $N$ 的字符串 $S$，保证字符串 $S$ 中只包含 $\texttt{W}$ 和 $\texttt{L}$。

第三行包含 $N$ 个整数 $A_1,\ldots ,A_N$。

第四行包含一个长为 $N$ 的字符串 $T$，保证字符串 $T$ 中只包含 $\texttt{W}$ 和 $\texttt{L}$。

第五行包含 $N$ 个整数 $B_1,\ldots ,B_N$。

outputFormat: 输出一行一个整数，表示在所有同城德比中，两队取得分数总和的最大值。

hint:
#### 样例解释
#### 样例 1 解释
因为两队都赢了比赛，因此不会出现同城德比。
#### 样例 2 解释
两队各自进行的第四场比赛可能是同城德比，野鹅队得 $4$ 分，金鹰队得 $2$ 分。野鹅队进行的第三场比赛和金鹰队进行的第二场比赛可能是同城德比，金鹰队得 $5$ 分，野鹅队得 $3$ 分。两队得分总和为 $4 + 2 + 5 + 3 = 14$，并且是得分总和最大的情况。

注意野鹅队的第一场比赛赢了，并且得了 $1$ 分，这场比赛不可能是对金鹰的，因为金鹰队没有得 $0$ 分的比赛。同时，金鹰队的第一场比赛也不可能是同城德比，因为金鹰队第一场比赛输了，并且得了 $6$ 分，野鹅队没有打出过获得至少 $7$ 分的比赛。

#### 数据范围及限制
对于 $100\%$ 的数据，保证 $1\le N\le 10^3$，$1\le A_i,B_i\le 10^6$，$S_i,T_i\in\{$`W`，`L`$\}$。
- Subtask 1（$40$ 分）：保证 $N\le 10$。
- Subtask 2（$60$ 分）：无特殊限制。
#### 说明
本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2018/) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day1.pdf) T1 Geese vs. Hawks。


title: [CCO2018] Wrong Answer

description:
在一场比赛中，您遇到了一道题：
> 有一个含 $N$ 个点的完全图，边有边权，您可以操作两个人从第一个点去遍历每个点，仅能从编号较小的点到达编号较大的点，求最小的边权和。

您一看，这不是 SB 题吗，于是您秒了它。

但是，此时一名选手的 Python 提交记录吸引了您的注意：
```python
def Solve(N, A):
    # A[i][j] is cost of moving from level i to level j
    # N is the number of levels
    x, y, sx, sy = 1, 1, 0, 0 # Initialize x and y to 1, sx and sy to 0
    for i in range(2, N + 1): # loop from 2 to N
        if sx + A[x][i] < sy + A[y][i]:
            sx += A[x][i]
            x = i
        else:
            sy += A[y][i]
            y = i
    return sx + sy
```
您一眼就看出了这是个错解，于是您决定 Hack 它。

outputFormat:
第一行为一个整数 $N$。

接下来 $N-1$ 行，第 $i$ 行有 $N-i$ 个数，分别为 $A_{i,i+1},A_{i,i+2}\ldots A_{i,n}$，$A_{i,j}$ 表示 $i$ 到 $j$ 的边权。

hint:
#### SPJ 计分标准
您需要保证 $2\le N\le 100$，$1\le A_{i,j}\le 100$，否则，您保龄。

您需要保证输出格式正确，否则，您保龄。

如果这份错误代码返回 $X$，而正解是 $Y$，则您将会得到 $\lceil\min(25,\frac{X}{4\times Y})\rceil$ 的分数。

译者提醒：为方便计分，SPJ 计分请使用 $100$ 分作为满分。

#### 样例解释
标解为一个人去第二个点，另一个人去剩下的点，边权和为 $1+2+7+5=15$，而错误代码所返回 $18$，所以可得 $\lceil \frac{18}{4\times 15}\rceil=1$ 分。

#### 说明
本题译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day1.pdf) T2 Wrong Answer。

感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的 SPJ。


title: [CCO2018] Fun Palace

description:
有一个含 $N$ 个点的链，每个点有一个权值。

对于任何 $1\le i\le N-1$，都有一条边连接 $(i,i+1)$。

您可以在链中的任意一些节点放置一些生物。

对于第 $i$ 条边，若点 $i$ 至少有 $a_i$ 个生物或点 $i+1$ 至少有 $b_i$ 生物，则该边可以打开。

链是有出口的，如果在 $1$ 号点有 $e$ 个生物，则出口会被打开。

您要确定，至多放置多少个生物，可以使得生物不会打开出口。

**打开了不一定能走过去。**

inputFormat:
第一行为一个整数 $N$。

第二行为一个整数 $e$。

接下来 $N-1$ 行，一行两个数 $a_i,b_i$。

outputFormat: 仅一行一个数，表示至多放置多少个生物，可以使得生物不会逃出出口。

hint:
#### 样例解释
#### 样例 1 解释
如果超过 $19$ 个生物，出口就会被打开。
#### 样例 2 解释
假设我们放 $24$ 个生物在 $2$ 号点，有 $4$ 个生物就会去到 $1$ 号点，但仍然无法打开出口。
#### 样例 3 解释
$9$ 个生物放在 $2$ 号点，$14$ 个生物放在 $7$ 号点。

#### 数据范围及限制
| 子任务编号 | 分值 | 特殊限制 |
| :-: | :-: | :-: |
| 1 | $12$ | $1\le e\le 200$，$a_i=b_i=1$ |
| 2 | $20$ | $1\le e,a_i,b_i\le 2$ |
| 3 | $48$ | $1\le N,e,a_i,b_i\le 200$ |
| 4 | $20$ | 无 |

对于 $100\%$ 的数据，保证 $1\le N\le 10^3$，$1\le e,a_i,b_i\le 10^4$。

#### 说明
本题译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day1.pdf) T3 Fun Palace。


title: 「EZEC-4」月下轻花舞

background:
>月下的轻花，随轻风飘舞，勾起了你我的记忆......

![](http://p1.music.126.net/mi-oogxsSXkHwPACQRsxgw==/109951163115816964.jpg?param=557y315)

description:
在轻花林中，有从 $l$ 到 $r$ 编号的轻花树，编号为 $i$ 的树有 $i-1$ 棵，轻花林很美，所以每棵树上都有编号为 $1\sim n$ 的 $n$ 朵轻花，编号为 $i$ 的树上编号为 $j$ 的轻花落下会产生大小为 $\left\lceil\log_ij\right\rceil$ 的魅力值。

夜幕降临，所有树上的所有轻花全部落下，花痴（雾）tlx 想知道总共有多大的魅力值，但是只算一次太简单了，所以他会设置不同情境询问你 $T$ 次，不过由于答案很大，你只需要告诉他魅力值总和对 $998244353$ 取模的结果。

**一句话题意**： $T$ 组询问，每次给定三个整数 $l,r,n$，求出下式的值：

$$\sum_{i=l}^r(i-1)\sum_{j=1}^n \left\lceil\log_ij\right\rceil\;\;\bmod998244353$$

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

接下来 $T$ 行，每行三个整数 $l,r,n$，分别代表树编号的起始值，终止值，以及一棵树上轻花的朵数。

outputFormat: 共 $T$ 行，每行一个整数，代表每一个询问的结果对 $998244353$ 取模的结果。

hint:
**【数据范围与约束】**

**本题采用捆绑测试，具体约束如下：**

- Subtask 1 $(1\text{ pts})$：$T=1$，$n=1$；
- Subtask 2 $(9\text{ pts})$：$l=r=2$；
- Subtask 3 $(10\text{ pts})$：$T=1$，$n\leq 10^3$，$r\leq 10^3$；
- Subtask 4 $(10\text{ pts})$：$l=r\not=2$；
- Subtask 5 $(20\text{ pts})$：$T=1$，$n\leq 10^6$；
- Subtask 6 $(20\text{ pts})$：$T=1$，$r\leq 10^6$；
- Subtask 7 $(20\text{ pts})$：$T\leq 3000$；
- Subtask 8 $(10\text{ pts})$：无特殊限制，时间限制 $1.5\;\text{s}$。

对于所有数据，满足：

$1\leq T\leq 10^5$，$1\leq n\leq 10^{18}$，$2\leq l\leq r\leq 10^{18}$。

**注意：在具体约束中没有提到的数据范围均为极限数据范围。**

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

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

$$\left\lceil\log_21\right\rceil+\left\lceil\log_22\right\rceil+\left\lceil\log_23\right\rceil+\left\lceil\log_24\right\rceil+\left\lceil\log_25\right\rceil=8$$

$$\left\lceil\log_31\right\rceil+\left\lceil\log_32\right\rceil+\left\lceil\log_33\right\rceil+\left\lceil\log_34\right\rceil+\left\lceil\log_35\right\rceil=6$$

故：

$$ans=8×(2-1)+6×(3-1)=20$$

对于样例 #2，我相信您聪明的大脑可以分分钟得到答案的。

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

**【其他提示】**

如果你不了解对数（$\log$）运算,可以查看[这里](https://baike.baidu.com/item/对数公式/5557846?fr=aladdin)。


title: [THUPC2019] 摆家具

description:
你有 $k$ 件不同的家具，需要摆放在 $n$ 个不同的房间中。假设每个房间足够大，并且只考虑每件家具处于哪个房间（而不考虑房间内部如何摆放），那么总共有 $n^k$ 种不同的摆放方式（注意，不是 $k^n$）。

摆放家具也算一门学问了，至少不太好乱摆的吧？对于每种摆放方式，我们可以给这种方式打分。例如，某个方案把餐桌放到了卫生间，或是一个卧室放了两张床而另一个卧室没有床，就会获得比较低的分数。由于这个分数关于每件家具、每个房间不是独立的，我们会输入所有 $n^k$ 种摆放方式的分数。

你现在心血来潮，想换一换房间的布局。给出一种初始时的摆放方式，你会重复 $T$ 次下述操作：每次，你会任选一件家具，然后将这件家具移动到任意一个其他房间中。每一轮有 $k(n-1)$ 种决策（选择家具的方案数乘以选择另一个房间的方案数），所以总共有 $k^T(n-1)^T$ 种决策。你需要计算这每一种决策后的摆放方式的得分之和。

不仅如此，我们会给出 $q$ 次询问，每次输入初始时的摆放方式与 $T$，你需要**在线地**回答 $k^T(n-1)^T$ 种决策后的得分之和（取模）。详见输入与输出格式。

我们如下定义一种摆放方式的编号：

我们将家具用 0 到 $k-1$ 的不同整数编号，房间用 $0$ 到 $n-1$ 的不同整数编号。设在某种摆放方式下，第 $i$ 号家具被放在了 $p_i$ 号房间中，则定义这种摆放方式的编号为 $\sum_{i=0}^{k-1} p_i n^i$。可以发现，所有的 $n^k$ 种摆放方式的编号恰好是 $0$ 到 $n^k -1$ 的不同整数。

另外，设 $P=998244353$。

inputFormat:
第一行输入三个正整数 $n, k, q$。

接下来 $n^k$ 行，每行输入一个小于 $P$ 的正整数，依次表示编号为 $0, 1, \dots, n^k - 1$ 的摆放方式的得分。

接下来 $q$ 行，每行输入两个非负整数。设某行的输入为 $a, b$（保证 $0 \leq a < n^k, 0 \leq b < P$），则此次询问的初始摆放方式的编号为 $a$，而 $T=b \cdot r \bmod P$，其中 $r$ 是你上一个输出的数（对于第一次询问为 $1$）。

同一行内输入的相邻两个数之间以一个空格隔开。

保证 $n \geq 2$，$k \geq 1$；$n^k \leq 10^6$；$q \leq 5 \times 10^5$

outputFormat: 对于每次询问输出一行，包含一个非负整数，表示该询问的得分之和对 $P$ 取模的结果。

hint:
#### 样例解释
第一次询问中，初始摆放方式的编号为 $0$，$T=1$。

初始时，$0$ 号家具放在 $0$ 号房间，$1$ 号家具放在 $0$ 号房间，$2$ 号家具放在 $0$ 号房间。经过 $1$ 次操作后，可能的情况有：

* 将 $0$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $1$，得分为 $10$；
* 将 $1$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $2$，得分为 $100$；
* 将 $2$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $4$，得分为 $998244245$。

所以，所有情况的总得分为 $998244355$，对 $P$ 取模后为 $2$。

第二次询问中，初始摆放方式的编号为 $0$，$T=2$。

初始时，$0$ 号家具放在 $0$ 号房间，$1$ 号家具放在 $0$ 号房间，$2$ 号家具放在 $0$ 号房间。经过 $2$ 次操作后，可能的情况有：

* 将 $0$ 号家具移动到 $1$ 号房间，然后将 $0$ 号家具移动到 $0$ 号房间，此后的摆放方式编号为 $0$，得分为 $1$；
* 将 $0$ 号家具移动到 $1$ 号房间，然后将 $1$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $3$，得分为 $1000$；
* 将 $0$ 号家具移动到 $1$ 号房间，然后将 $2$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $5$，得分为 $100000$；
* 将 $1$ 号家具移动到 $1$ 号房间，然后将 $0$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $3$，得分为 $1000$；
* 将 $1$ 号家具移动到 $1$ 号房间，然后将 $1$ 号家具移动到 $0$ 号房间，此后的摆放方式编号为 $0$，得分为 $1$；
* 将 $1$ 号家具移动到 $1$ 号房间，然后将 $2$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $6$，得分为 $1000000$；
* 将 $2$ 号家具移动到 $1$ 号房间，然后将 $0$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $5$，得分为 $100000$；
* 将 $2$ 号家具移动到 $1$ 号房间，然后将 $1$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $6$，得分为 $1000000$；
* 将 $2$ 号家具移动到 $1$ 号房间，然后将 $2$ 号家具移动到 $0$ 号房间，此后的摆放方式编号为 $0$，得分为 $1$。

所以，所有情况的总得分为 $2202003$，对 $P$ 取模后为 $2202003$。

第三次询问中，初始摆放方式的编号为 $1$，$T=513066699$。初始时，$0$ 号家具放在 $1$ 号房间，$1$ 号家具放在 $0$ 号房间，$2$ 号家具放在 $0$ 号房间。

……（省略至少 $3^{513066699}$ 行）

#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。


title: 「EZEC-4」paulzrm Loves Array

background:
原题面：

$\color{gray}\text{zrmpaul}$ has an array consisting of $n$ integers: $a_1,a_2,...,a_n$. The initial value of $a_i$ is $i(1\le i\le n)$. There are $m$ operations, including four types as follows.

Type $1$: `1` sort the array.
Type $2$: `2` sort the array and reverse it.
Type $3$: `3 x y` swap $a_x,a_y$. **It is guaranteed that $x$ is not equal to $y$, and $1\leq x ,y \leq n$**.
Type $4$: `4` reverse the array.

You need to output the array after $m$ operations.

First line with two intergers $n,m(1\leq n,m\leq 10^6)$.

Next $m$ lines are the operations.

One line, $n$ numbers, the array.

description:
小 Z 有一个下标从 $1$ 开始并且长度为 $n$ 的序列，初始时下标为 $i$ 位置的数字为 $i$。有 $m$ 个操作，每个操作会是以下四种之一。

- `1` 对序列从小到大进行排序。
- `2` 对序列从小到大进行排序后将其翻转，(译者注：就是从大到小排序）。
- `3 x y` 将下标为 $x,y$ 的数交换位置。保证 $x\neq y$ 且 $1\le x,y\le n$。
- `4` 将序列翻转。

你要输出在 $m$ 次操作后的序列。

inputFormat:
第一行两个整数 $n,m$ ，表示序列的长度以及操作的数量。

接下来 $m$ 行，每行一个操作。保证操作合法。

outputFormat: 一行包含 $n$ 个整数，表示操作后的序列。


title: 【模板】一般图最大权匹配

background: 模板题，无背景。

description:
给定一张有 $n$ 个顶点的无向带权图，有 $m$ 条带权边。

求一种匹配的方案，使得最终匹配边的边权之和最大。

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

接下来 $m$ 行，每行 $3$ 个数：$u$，$v$，$w$，表示点 $u$ 与点 $v$ 之间有一条边权为 $w$ 的边。

outputFormat:
第一行一个数，最大边权和。

接下来一行 $n$ 个整数，描述一组最优方案。第 $v$ 个整数表示点 $v$ 匹配的点的编号。如果 $v$ 号点没有匹配，请输出 0。


title: 【模板】Chirp Z-Transform

description: 给定一个 $n$ 项多项式 $P(x)$ 以及 $c, m$，请计算 $P(c^0),P(c^1),\dots,P(c^{m-1})$。所有答案都对 $998244353$ 取模。

inputFormat:
第一行三个正整数 $n,c,m$。
第二行 $n$ 个非负整数 $a_0,a_1,\dots,a_{n-1}$，由低到高表示 $P(x)$ 的系数。

outputFormat: 一行 $m$ 个正整数，第 $i$ 个数表示 $P(c^{i-1})$。


title: 『MdOI R3』Number

description:
生活中我们会碰到一些特殊数字，这些数字使用一些特殊表达方式后会方便记忆和使用。比如说，$10^9+7$ 就非常常见——它相比于 $1000000007$，更方便选手看清数字而不必数 $0$，而且没有科学计数法的精度损失。

你现在有一个形如 $10^{k}+x$ 的数字，请还原成一般写法。

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

outputFormat: 一行一个整数表示 $10^k+x$。


title: 『MdOI R3』Operations

background: 这是这场比赛唯一一道没有题目背景的题，这就是本题的题目背景。

description:
给定非负整数 $a,b$，有两种操作：

1. 任意选择一个正整数 $x$，将两数都减去 $x$，执行一次该操作的代价为 $c$；
2. 任意选择一个正整数 $x$，将两数其中一个数乘以 $x$，另一个除以 $x$ 后向下取整，执行一次该操作的代价为 $d$。

在这里，向下取整指使一个数变为**不大于它的最大的整数**，比如 $3.5$ 向下取整为 $3$，$-0.07$ 向下取整为 $-1$。

选择的 $x$ 可以为任意正整数。在操作的过程中，可以把 $a,b$ 变为负数。

你可以任意多次对这两个数操作，求将 $a,b$ 都变成 $0$ 的代价最小值。

inputFormat: 一行四个整数 $a,b,c,d$，用空格隔开，分别表示 $a,b$ 的初始值和两种操作的代价。

outputFormat: 一行一个整数，表示代价的最小值。


title: [BalticOI 2020 Day2] 图

description:
你有一个无向图，每条边都有一种颜色：红或者黑。

你要做的就是为每个节点配一个实数点权，使得：

- 对于每条黑色边，两个端点的点权之和为 $1$
- 对于每条红色边，两个端点的点权之和为 $2$
- 所有点权的绝对值之和是最小的

求一种点权的分配方案。

inputFormat:
第一行两个整数 $N,M$ 代表点数和边数。
所有点的编号为 $1$ 到 $N$。
接下来 $M$ 行每行三个整数 $a,b,c$ 描述一条边端点为 $a$ 和 $b$，如果 $c$ 是 $1$ 那么这条边是黑色边，如果 $c$ 是 $2$ 那么这条边是红色边。

outputFormat:
如果有解，首先第一行输出 `YES`，然后第二行 $N$ 个整数代表可能的一组点权。
多组解输出任意一组即可。
如果无解，一行一个字符串 `NO`。

hint:
#### 评测方式

您的输出被评判为正确，当且仅当：

- 每条边所连两点的点权和与该边要求的点权间的误差不超过 $10^{-6}$。
- 所有点权的绝对值之和与标准答案误差不超过 $10^{-6}$。

#### 数据规模与约定

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

- Subtask 1（5 pts）：$N \le 5$，$M \le 14$。
- Subtask 2（12 pts）：$N \le 100$。
- Subtask 3（17 pts）：$N \le 1000$。
- Subtask 4（24 pts）：$N \le 10^4$。
- Subtask 5（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le M \le 2 \times 10^5$。

**本题使用 Special Judge。**


title: [BalkanOI2011] 2circles

description: 在平面直角坐标系上有一个含 $N$ 个点的凸多边形，现在想在里面放入两个半径为 $R$ 的圆，使两个圆不重合，求 $R$ 的最大值。

inputFormat:
第一行为一个整数 $N$。

接下来 $N$ 行，一行两个整数 $x_i,y_i$，表示该多边形第 $i$ 个点的坐标。

outputFormat: 仅一个实数 $R$。

hint:
#### 样例 1 解释
将两个圆心放在该正方形的对角线上的时候，半径最长，如图：

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

半径为 $\frac{\sqrt{2}}{2\times (1+\sqrt{2})}\approx 0.293$。
#### SPJ 计分标准
若您的答案与标准答案误差不超过 $0.001$，您就会 AC。
#### 数据范围及限制
- 对于 $10\%$ 的数据，保证 $N=3$。
- 对于 $40\%$ 的数据，保证 $N\le 250$。
- 对于 $100\%$ 的数据，保证 $3\le N\le 5\times 10^4$，$-10^7\le x_i,y_i\le 10^7$，这些点按逆时针方向给出。

#### 说明
本题译自 [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 1](http://www.boi2011.ro/boi2011/?pagina=probleme) [T1 2circles](http://www.boi2011.ro/resurse/tasks/2circles.pdf)。


title: [BalticOI 2020 Day2] 村庄

background: # 请用 C++14/C++17 提交以避免不必要的 CE

description:
村庄有 $N$ 个房子，之间有 $N-1$ 条道路连接，每条道路长度为 $1$。

在最开始，第 $i$ 个村民就在第 $i$ 号房子里，房子从 $1$ 到 $N$ 编号。

有一天，村民们突然突发奇想，想搬到别的房子中，村民们希望，在搬迁过后，不存在一位村民住在他原来居住的房子中。

求所有村民在新旧房屋之间的最小总距离值和最大总距离值。

inputFormat:
第一行一个整数 $N$ 代表房子数。
接下来 $N-1$ 行每行两个整数 $a,b$ 代表一条道路连接 $a$ 号房子和 $b$ 号房子。

outputFormat:
第一行两个整数代表所有村民在新旧房屋之间的最小总距离值和最大总距离值。
第二行 $N$ 个整数，给出一种达成最小总距离和的方案。其中第 $i$ 个整数 $v_i$ 代表第 $i$ 个村民要从 $i$ 号房子迁移到 $v_i$ 号房子。
第三行 $N$ 个整数，给出一种达成最大总距离和的方案。输出方式和上一行相同。
要保证 $v_i\ne i$。
如果有多组解，输出任意一组合法方案即可。

hint:
#### 评分方式

本题分为两个任务：

- 求解最小距离和，并给出一种相应的合法方案；
- 求解最大距离和，并给出一种相应的合法方案；

每成功完成一个任务，您就可以获得该测试点 $50\%$ 的分数。

您在一个子任务的得分，等于你在该子任务所有测试点的最低得分。

请注意，即使您不会求解某个子任务，也请按照要求的输出格式进行输出，否则 checker 将无法正确评分。

#### 数据规模与约定

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

- Subtask 1（12 pts）：$N \le 10$。
- Subtask 2（38 pts）：$N \le 1000$。
- Subtask 3（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le a,b \le N$。

**本题使用 Special Judge。**


title: [BalticOI 2020 Day2] 病毒

background: 本题数据为删减版（去掉了最后的 $6$ 组数据），完整版请去 [CF1387C](https://www.luogu.com.cn/problem/CF1387C) 提交。

description:
给定一种病毒，为了方便，我们用 $0$ 到 $G-1$ 的整数描述他的基因序列。

现在这个病毒可以进行变异，有一些变异规则，每个变异规则可以让基因序列上的某个数变成某个片段，如果用变异规则让基因序列变成了全部为 $0$ 和 $1$ 的序列，那么这个病毒就变异完成了。

病毒可以通过抗体进行检测，比如 $01011$ 就可以检测到 $0101110$，但不能检测到 $110110$。

对于从 $2$ 到 $G-1$ 中的基因，科学家想知道，是否能通过任意一组给定的抗体检测到这个基因变异形成的其他所有基因，不能的话，那么求不能检测到的基因中的最短长度。

inputFormat:
第一行三个整数 $G,N,M$ 代表基因数，变异规则数和抗体数。
接下来 $N$ 行每行首先两个整数 $a,k$，然后接着 $k$ 个整数 $b_i$，代表 $a$ 可以通过这个变异规则变为 $b_1,b_2,\cdots,b_k$ 这个片段，保证 $2$ 和 $G-1$ 都至少在每个规则中的 $a$ 中出现一次。
接下来 $M$ 行每行首先一个整数 $l$ 代表抗体长度，接下来 $l$ 个整数 $c_i$ 描述这个抗体。

outputFormat: $G-2$ 行第 $i$ 行代表 $i$ 基因以及其所有变异到的基因是否都可以被任意一组抗体检测到，如果可以，输出一个字符串 `YES`，如果不可以，首先一个字符串 `NO`，接下来一个整数代表不能检测到的基因中的最短长度。保证对于所有数据，该值小于 $2^{63}$。

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

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

- Subtask 1（11 pts）：$M=0$。
- Subtask 2（14 pts）：$N = G-2$。
- Subtask 3（25 pts）：$M=1$。
- Subtask 4（32 pts）：$\sum l \le 10$。
- Subtask 5（18 pts）：无特殊限制。

对于 $100\%$ 的数据，$G > 2$，$N \ge G-2$，$M \ge 0$。$2 \le a <G$，$k \ge 1$，$0 \le b_i<G$，$\sum k \le 100$，$l \ge 1$，$0 \le c_i \le 1$，$\sum l\le 50$。

**本题强制 $O2$ 优化。**


title: 「RdOI R1」冰淇淋游戏(play)

background: 又有新游戏可玩啦！

description:
小 T 发现最近市面上出现了一款游戏，这款游戏分为 $n$ 关，第 $i$ 关玩一次需要 $s_i$ 个体力，最多可以玩 $m_i$ 次第 $i$ 关。想玩第 $i$ 关，必须先玩第 $i-1$ 关至少一次，当然，玩第 $1$ 关不需要这个先决条件。

游戏规则是这样的（对于第 $i$ 关）：

一共有 $k_i$ 个冰淇淋排成一排，第 $j$ 个冰淇淋的美味度为 $y_{i,j}$，每次你需要选择一个冰淇淋吃掉，共吃 $k_i$ 次，在第 $j$ 次吃第 $l$ 个冰淇淋可以获得 $j\times y_{i,l}$ 分。

当然，要想吃冰淇淋可没有那么简单，你需要在第一次吃指定的第 $c_i$ 个冰淇淋，接下来每次只能吃已经吃完的段的两边的冰淇淋，比如第一次吃的是第 $2$ 个冰淇淋，第二次可以吃第 $1$ 个或第 $3$ 个（如果有的话）。

因为小 T 的脑子不太够计算这复杂的分数，所以他想求助你，在使用体力不超过 $t$ 的情况下，最多可以获得多少分数。

inputFormat:
第一行有两个整数 $n,t$，分别表示关卡数和体力数。

接下来第 $2$ 到第 $2\times n+1$ 行，第 $2\times i$ 行和第 $2\times i+1$ 行描述第 $i$ 关。

第 $2\times i$ 行四个整数 $s_i,m_i,k_i,c_i$，意义见题面。

第 $2\times i+1$ 行 $k_i$ 个整数，第 $j$ 个为 $y_{i,j}$，意义见题面。

outputFormat: 一行一个整数，为使用体力不超过 $t$ 的情况下的获得的分数的最大值。

hint:
【样例解释】

样例1：

最优解为玩一次第一关再玩一次第二关。

第一关按照第 $2,3,4,1$ 个的顺序吃冰淇淋，可以获得 $2\times 1+4\times 2+1\times 3+3\times 4=2+8+3+12=25$ 的分数。

第二关按照第 $3,4,2,1$ 个的顺序吃冰淇淋，可以获得 $2\times 1+2\times 2+3\times 3+2\times 4=2+4+9+8=23$ 的分数。

所以最多可以获得 $25\times 1+23\times 1=48$ 的分数。

样例2：

最优解为玩两次第一关，一次第二关，一次第三关。

可以获得 $10000 \times 2+1 \times 1+2 \times 1=20003$ 的分数。

---

【数据范围】

对于 $10\%$ 的数据，$1 \le n \le 10 , 1 \le k_i,m_i,s_i,y_{i,j} \le 100 , 1 \le t \le 100$。

对于另外 $40\%$ 的数据，$1 \le n \le 100 , 1 \le k_i,m_i,s_i,y_{i,j} \le 100 , 1 \le t \le 10^4$。

对于 $100\%$ 的数据，$1 \le n \le 200 , 1 \le k_i,m_i,s_i,y_{i,j} \le 500,1 \le t \le 10^5,1\le c_i\le k_i$。

---

【说明/提示】

- 尝试理解样例

---

【文件读入读出】**（模拟，提交代码时不需使用）**

- 文件名：`play.cpp`
- 读入文件名：`play.in`
- 读出文件名：`play.out`


title: [BalkanOI2011] decrypt

background: 这是一道 **IO 交互题**。

description:
我们随机了三个数 $R_0,R_1,R_2$，并按以下规则生成了整个 $R$ 序列：

$$R_n=R_{n-2}\oplus R_{n-1}$$

其中 $\oplus$ 为异或运算。

此外我们有一个函数 $M$，其是一个双射，即我们保证对于 $x\not=y$，$M(x)\not=M(y)$。

您的目标是，经过多次询问后，确定 $R_0,R_1,R_2,M(0),M(1),\ldots,M(255)$。

#### 交互方式
你的程序应从标准输入中读入，向标准输出中输出。

您可以向标准输出中输出一个整数 $A$，如果这是您的第 $N$ 次询问，您将会读入：

$$M(A\oplus R_{N-1})$$

如果您已经得到了所有答案，请输出一行字符串 `SOLUTION`，然后输出 $259$ 行，分别是 $R_0,R_1,R_2,M(0),M(1),\ldots,M(255)$。

**记得在输出每一行后清空缓冲区！**

hint:
#### 样例
（因为样例组不好表示所以放到这里）

我们人为规定 $R_0=0,R_1=1,R_2=3,M(i)=(i+1)\bmod 256$。

可得 $R_3=1$。

| 输出 | 输入 | 解释 |
| :-: | :-: | :-: |
| $10$ | $11$ | $M(10\oplus 0)=M(10)=11$ |
| $10$ | $12$ | $M(10\oplus 1)=M(11)=12$ |
| $11$ | $9$ | $M(11\oplus 3)=M(8)=9$ |
| $12$ | $14$ | $M(12\oplus 1)=M(13)=14$ |
| … |  | 省略了一部分输出 |
| ``SOLUTION`` |  | 省略了一部分输出 |

#### 数据范围及限制
对于 $100\%$ 的数据，保证输入的数、输出的数、$R$ 数组、$M(x)$ 中的 $x$ 与 $M(x)$ 均 $\ge 0$ 且 $\le 255$。

#### 计分策略
如果您输出的数并不在上述范围内，您保龄。

您的询问次数需要少于 $320$，否则，您保龄。

#### 提示
清空缓冲区的方法：

C：

```c
printf("%d\n", q);
fflush(stdout);
```

C++：
```cpp
cout<<q<< '\n';
cout.flush();
```

Pascal：
```pascal
writeln(q);
flush(output);
```

#### 说明
本题译自 [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 1](http://www.boi2011.ro/boi2011/?pagina=probleme) [T2 decrypt](http://www.boi2011.ro/resurse/tasks/decrypt.pdf)。

感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的交互库。


title: 「EZEC-4」求和

description:
给定正整数 $n$ 的值，求出下面这个式子的值：

$$\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j)^{i + j}$$

由于结果可能很大，所以你只需要求出结果对 $p$ 取模的值。

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

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

对于每组数据：

一行，两个正整数 $n, p$。

outputFormat: 对于每组数据，输出一行，一个正整数，表示所求的值。


title: 『MdOI R3』Teleport

background:
凯瑞甘从帝国的围攻下，击毁了大天使号，乘着雷诺的飞船逃了出来，到了休伯利安号上。

“吉米？”凯瑞甘着急地四处寻找着。

“很抱歉，我们没能救出他”马特·霍纳向凯瑞甘走来。

“你丢下了他？”凯瑞甘回想起曾经的自己被蒙斯克丢下，便起了杀心，用灵能将马特抓了起来。

“不是的，凯瑞甘，我们受到了帝国的伏击，现在必须，马上离开，过会可以回头来找他”马特解释道。

“这里没有我们！你走吧，我自己去找他。”凯瑞甘放下了马特，回头坐着雷诺的回到了星球上。

“警告，警告，敌军突破能量场。”帝国的舰队突破了马特舰队设下的能量场，控制着钢铁舰队折越到了这里，并对休伯利安号发起猛烈的攻击。

“立即进行折越，我们必须马上离开！”马特·霍纳下令道。

description:
马特·霍纳想要控制休伯利安号进行折越，想要进行折越，就要激活休伯利安号上的所有 $n$ 个位点。

休伯利安号上有 $n$ 个位点，每个位点有 $a_i$ 点能量，为了激活，马特·霍纳会消耗 $k\times n$ 点地嗪，这 $k\times n$ 点地嗪会平均分给 $n$ 个位点，每个位点在接受 $k$ 点地嗪后会激发，得到 $a_i \operatorname{xor} k$ 点高能，所有位点的高能总和为这次折越的消耗 $S$。

为了能够快速的进行折越，马特·霍纳决定用最多的 $k\times n$ 点地嗪，但可惜的是，如果地嗪使用太多，使得消耗 $S$ 超过限制值 $m$ ，那么休伯利安号就会不堪重负，最终爆炸。

现在，你的任务是帮助马特·霍纳找到这个最大的 $k$ ，使得休伯利安号能在安全的前提下尽可能快的折越走。如果任何情况下都不能安全的折越走，则输出 $-1$ 。

这里的 $\operatorname{xor}$ 表示的是位运算中的按位异或运算。

inputFormat:
第一行一个整数 $n$ 表示位点数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个位点拥有的能量。

第三行一个数 $q$ 表示询问次数。

接下来 $q$ 行表示 $q$ 次询问，每行一个数 $m$。

outputFormat: 对于每次询问输出一行一个非负整数，表示最大的 $k$。若无解，输出 $-1$ 。


title: [BalkanOI2011] medians

description:
设 $A$ 为 $1,2,3,\ldots,2\times N-1$ 的任意一种排列。

我们定义 $A$ 的前缀中位数为一个长度为 $N$ 的数列 $B$，$B_i$ 为 $A_1,A_2,\ldots,A_{2\times i-1}$ 的中位数。

我们将会给出 $B$ 数列，请构造一个数列 $A$，使得其前缀中位数为 $B$。

inputFormat:
第一行为一个整数 $N$。

接下来一行 $N$ 个整数，表示数列 $B$。

outputFormat:
仅一行 $2\times N+1$ 个整数，表示您构造的数列 $A$。

数据一定有解，您只需要输出其中一种。

hint:
#### 数据范围及限制
- 对于 $60\%$ 的数据，保证 $N\le 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le N\le 10^5$，$1\le A_i,B_i\le 2\times N-1$，数据一定有解。

#### 说明
本题译自 [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 1](http://www.boi2011.ro/boi2011/?pagina=probleme) [T3 medians](http://www.boi2011.ro/resurse/tasks/medians.pdf)。

感谢 @[using](https://www.luogu.com.cn/user/193198) 提供的 SPJ。


title: [COCI2007-2008#6] PARKING

description:
Luka 毕业了，他找到了驾驶卡车的工作。

一天晚上，他将 $3$ 辆卡车停在一个停车场，收费方式如下：

- 停放一辆卡车时，司机每分钟给每辆车支付 $a$ 元。
- 停放两辆卡车时，司机每分钟给每辆车支付 $b$ 元。
- 停放三辆卡车时，司机每分钟给每辆车支付 $c$ 元。

给定 $a, b, c$，以及 Luka 的三辆卡车的停车时间，请确定 Luka 要交多少钱。

inputFormat:
第一行，$a, b, c$，含义见题目描述。

接下来三行，每行 $2$ 个数，表示第 $i$ 辆车的停车开始时间 $begin_i$ 和结束时间 $end_i$，第 $end_i$ 分钟不收费。

outputFormat: 第一行，一个正整数，表示 Luka 要交的钱。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，$1 \le c \le b \le a \le 100$，$1\le begin_i\le end_i\le 100$。
#### 说明
- 本题满分 $20$ 分。
- 本题自动开启 O2 优化开关。
- 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T1 PARKING，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: [COCI2007-2008#6] SEMAFORI

description:
Luka 在开卡车，路上有 $n$ 个信号灯。

对于每个信号灯，他都知道红灯和绿灯亮的时间（循环不断重复）。

Luka 开始开车时，所有交通信号灯都呈红色，并且开始循环。

Luka 每秒移动 $1$ 个距离单位。当交通信号灯为红色时，他要停车，直到它变成绿色。

编写一个程序，确定 Luka 需要多少时间才能到达路的尽头。

道路的起点在 $0$ 处，终点在 $l$ 处。

inputFormat:
第一行两个数 $n, l$，分别表示信号灯的个数和道路的长度。

接下来，$n$ 行中的每行三个整数 $d, r, g$。 $d$ 表示信号灯到道路起点的距离， $r$ 和 $g$ 分别表示红色和绿色信号灯亮的时间。

信号灯将按 $d$ 升序排列。

没有两个交通信号灯将在同一位置。

outputFormat: 第一行，一个正整数，表示 Luka 到达路的尽头的时间。

hint:
#### 样例 #1 解释
在第一个示例中，Luka 在第一个信号灯处等待 $2$ 秒。 接着，他将到达第二个交通信号灯，该信号灯为绿色，可以立即通过。
#### 数据规模及规定
对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le l \le 10^3$，$1 \le d < l$，$1 \le r \le 100$，$1 \le g \le 100$。
#### 说明
- 本题满分 $30$ 分。
- 本题默认开启 O2 优化开关。
- 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T2 SEMAFORI，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: [COCI2007-2008#6] GRANICA

description:
Luka 首先从 $n$ 个车牌上的数字写在一张纸上。然后，他尝试找到整数 $m$，以使纸上的所有数除以 $m$ 都得到相同的余数。

Luka 想找到尽可能多的不同的 $m$。

编写一个程序，给定 Luka 的 $n$ 个整数，确定所有 $m$。

注意，你需要保证 $m$ 是正整数，即，$m> 1$。

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

接下来，$n$ 行，每行一个数 $a_i$，表示纸上的数，保证互不相同。

数据保证有一个 $m$ 符合要求。

outputFormat: 第一行，任意序输出所有符合要求的 $m$。

hint:
#### 样例 #1 解释
所有整数除以 $2$ 时都为 $0$，除以 $4$ 时为 $2$。

#### 数据规模及约定
- 对于 $60\%$ 的数据，$2 \le n \le 100$，$1 \le a_i \le 10^4$。
- 对于 $100\%$ 的数据，$2 \le n \le 100$，$1 \le a_i \le 10^9$。

#### 说明
- 本题满分 $50$ 分。
- 本题默认开启 O2 优化开关。
- 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T3 GRANICA，译者 @[tearing](https://www.luogu.com.cn/user/219791)。
- 感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的 checker，您可以在附件处下载。


title: 计数题

description:
您有一个无限大的集合，其中有所有小于等于 $n$ 的质数和其中它们的乘积。

如 $n=5$，集合中实际包含的数为 $2,3,5$（质数），$4,6,8,9,10,12.....$（质数之积），假设这个集合为 $T$。

求：

$\sum\limits_{S\subset T,S\neq\varnothing}\mu(\prod\limits_{i\in S}i)\varphi(\prod\limits_{i\in S}i)$

对 $998244353$ 取模。可以证明这个和是存在的。

为了您能更好的获得部分分，我们会给定一个 $k$，表示一些限制，**$k$ 的值可能影响答案！请认真阅读提示说明**。

$n\leq 10^6$

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

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


title: [COCI2007-2008#6] PRINCEZA

background: 对于 C 语言和 C++ 语言，请使用 `cin`，`scanf` 进行读入，否则可能会出现 $\color{purple}\mathsf{RE}$ & $\color{red}\mathsf{WA}$。

description:
Luka 把卡车停在湖边。

Barica 在湖中居住，Barica 跳过漂浮在湖面上的 $n$ 种植物。

Luka 知道许多民间故事，知道如果他亲吻 Barica，她会变成一个可爱的女孩子。但是，他需要先抓住她！

可以用一对坐标定义植物在湖面上的位置。 Barica 可以从 $(x, y)$ 植物中跳跃，$p$ 为任意正整数。

- 方向 A：$(x + p, y + p)$。
- 方向 B：$(x + p, y - p)$。
- 方向 C：$(x - p, y + p)$。
- 方向 D：$(x - p, y - p)$。

Barica 选择四个方向之一，然后沿所选方向跳到第一个植物上。

如果在选定的方向上没有植物，Barica 将留在原处。

Barica 跳下后，她从水槽上跳下的植物消失了。

知道植物的位置和 Barica 选择的方向顺序后，Luka 希望确定 Barica 最终将位于植物的坐标。 Luka 将在她的位置等她，亲吻她。

编写一个解决 Luka 问题的程序，并帮助他将 Barica 变成美丽的公主。

inputFormat:
第一行，两个正整数 $n, k$，分别表示植物数和跳跃次数。

第二行，$k$ 个字母，`A`，`B`，`C` 或 `D`，表示她跳的方向。

接下来，$n$ 行的每行都包含两个整数 $x, y$，表示一棵植物的坐标。 Barica 最初位于第一颗植物。

outputFormat: 第一行，Barica 的最终坐标。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，$1 \le n, k \le 10 ^ 5$，$0 \le x, y \le 10 ^ 9$。
#### 说明
- 本题满分 $60$ 分。
- 本题默认开启 O2 优化开关。
- 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T5 PRINCEZA，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: [COCI2007-2008#6] GEORGE

background:
T 先生来 Luka 所在的小镇玩，因为 T 先生是一个大人物，警察会对他将走过的路实行交通管制。

Luka 在镇上是一名送货的卡车司机。但是由于一些路正在进行交通管制，他无法及时交货，还因此差点丢掉了他的工作。

description:
Luka 知道 T 先生游玩的路线，并且他想要知道最短的交货时间。

该城市由若干十字路口和连接它们的道路连接，并且 Luka 知道他需要在某条路段上开多长时间（T 先生需要同样的时间以开过该路段）。

例如，如果 T 先生在第 $10$ 分钟进入一条路，并且需要 $5$ 分钟离开这条路，那么该街道将在第 $10 \sim 14$ 分钟时被封锁。Luka可以在第 $9$ 分钟或更早的时候，也可以在第 $15$ 分钟及以后进入该道路。

编写一个程序，计算 Luka 在 T 先生到达城市后 $k$ 分钟开始开车的最短时间。

inputFormat:
第一行两个正整数 $n, m$，分别表示十字路口数和街道数。 十字路口编号为 $1$ 到 $n$。

第二行四个正整数 $a, b, k, g$，分别表示：
- $a$：Luka 起点的路口。
- $b$：Luka 必须到达的十字路口。
- $k$：T 先生和 Luka 之间的出发时间差。
- $g$：T 先生路上的十字路口数。

第三行 $g$ 个整数，表示 T 先生路上依次经过的十字路口。保证存在对应的街道，每条街道只能走一次。

接下来 $m$ 行，每行三个整数 $a, b, l$，表示在坐标 $(a, b)$ 处有一条街道，开过去的时间为 $l$。

outputFormat: 一行，输出 Luka 送货需要的最短时间（单位：分）。

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

对于 $100\%$ 的数据，$2 \le n \le 10^3$，$2 \le m \le 10^4$，$1 \le a, b \le n$，$0 \le k \le 10^3$，$ 0 \le g \le 10^3$。

#### 说明
- 本题满分 $60$ 分。
- 本题默认开启 O2 优化开关。
- 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T4 GEORGE，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: 「Wdsr-2」白泽教育

background:
上白泽慧音在给雾之湖的妖精们讲课。

某天，慧音在上数学课时，提到了一种非常有趣的记号：**高德纳箭号表示法**。它可以用来描述非常巨大的数字。~~比如紫的年龄。~~

对于非负整数 $a, b$ 和正整数 $n$，高德纳箭号表示法的定义为：

$$a \uparrow^n b = \begin{cases}
1\ (b = 0) \\
a^b\ (n = 1\ \operatorname{and}\ b > 0) \\
a \uparrow^{n - 1} (a \uparrow^n (b - 1))\ (n > 1\ \operatorname{and}\ b > 0)
\end{cases}$$

一些简单的例子：

- $2 \uparrow 31 = 2^{31} = 2147483648$

- $2 \uparrow \uparrow 4 = 2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65536$

注：
1. $a \uparrow b$ 与 $a \uparrow^1 b$ 相同；

2. $a \uparrow \uparrow b$ 与 $a \uparrow^2 b$ 相同；

3. 请注意幂运算的顺序。

description:
慧音希望琪露诺解决以下关于 $x$ 的方程：

$$a \uparrow^n x \equiv b \pmod p$$

其中，$a, n, b, p$ 为已知的常数，$x$ 为未知数。

琪露诺被高德纳箭号表示法搞得云里雾里的，但是她不想被头槌。你能帮帮她吗？

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

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

对于每组数据：

一行，四个整数 $a, n, b, p$。

outputFormat: 对于每组数据，输出一行，一个整数，如果原方程有解，输出该方程的最小非负整数解；否则，输出 $-1$。


title: [BalkanOI2011] cmp

background:
这是一道 **Grader 交互题**。

本题时限 10s，空限除交互库所用内存仅 16MB。

本题分数最高 $190$，但标解所选择的方案可得 $100$ 分。

#### 测评注意事项
- 你的代码中不应包含 `cmp.h`，而应该在开头包含下面两个函数的声明：
   - `void bit_set(int);`
   - `int bit_get(int);`
- 你的代码中应该实现两个函数 ：
   - `void remember(int a);`
   - `int compare(int b);`

换句话说，您可以在如下的代码模板中编写程序：
```cpp
#include <bits/stdc++.h>
using namespace std;
do something...
extern "C" void bit_set(int);
extern "C" int bit_get(int);
extern "C" void remember(int a) {
    do something...
}
extern "C" int compare(int b) {
    do something...
}
```

description:
我们有一个第一维长度为 $4096$，第二维长度为 $10240$ 的二维 $01$ 数组 $mem$，初始时所有值为 $0$。

您需要编写在 $01$ 数组上执行的两个操作 `void remember(int a)` 和 `int compare(int b)`。

#### 实现细节

`void remember(int a)` ：

- 保证 $0\le a\le 4095$。
- 您可以调用 `void bit_set(int ad)`，其中您需要保证 $1\le ad \le 10240$。
  - 这会导致 $mem_{a,ad}=1$。

`int compare(int b)`：

- 保证 $0\le b\le 4095$。
- 您需要将 $a$ 与  $b$ 进行比较，其中 $a$ 未知：
  -  若 $b<a$，请返回 $-1$。
  - 若 $b=a$，请返回 $0$。
  - 若 $b>a$，请返回 $1$。
- 您可以调用 `int bit_get(int ad)`，其中您需要保证 $1\le ad \le 10240$。
  - 这会返回 $mem_{a,ad}$ 的值

#### 任务

您应该实现上述两个函数 `void remember(int a)` 和 `int compare(int b)` 在最大程度上减少 `void bit_set(int ad)` 和 `int bit_get(int ad)` 的调用次数。

您的得分由以下伪代码计算：

```
define AllMemory = array [0..4095][1..10240] of bits
set AllMemory to zeros
for a = 0..4095:
    define bit_set(address): AllMemory[a][address] = 1
    remember(a)
let maxA= the maximum number of bit_set() calls executed for any a
for (a,b) ∈ {0..4095}×{0..4095} in random order (i.e. all valid pairs (a,b) are considered, in some random order)
    define bit_get(address): return AllMemory[a][address]
    answer =compare(b)
    if answer for comparing a and b is incorrect : your score = 0; exit
let maxB = the maximum number of bit_get() calls executed for any (a,b) pair
T=maxA + maxB
If (T>20): your score = 0; exit
else your score = 1 + 9 * (21– T); exit
```

hint:
#### 限制

- 如果您的解决方案不遵守上面的实现细节部分，您保龄。

- 您的解决方案必须可以在 10s 内调用 $4096$ 次  `void remember(int a)`  和 $4096\times 4096$ 次 `int compare(int b)`。
#### 说明
本题译自 [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 2](http://www.boi2011.ro/boi2011/?pagina=probleme) [T1 cmp](http://www.boi2011.ro/resurse/tasks/cmp.zip)。

感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的交互库。


title: 「EZEC-6」跳一跳

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

小 A 最近迷上了 “跳一跳” 这个游戏。

description:
小 A 玩的 “跳一跳” 规则如下：

1. 设定一个计数器 $\text{cnt}$，将其初始值设置为 $2$。
2. 若跳上下一个格子但没跳到其中心，加 $1$ 分，将 $\text{cnt}$ 重置为 $2$。
3. 若跳上下一个格子且跳到了其中心，加 $\text{cnt}$ 分，将 $\text{cnt}$ 翻倍。
4. 若下一个格子为特殊格 $x_i$ 且跳到了其中心，额外加 $y_i$ 分。
5. 终止条件为没跳上下一个格子或者跳完了所有格子。

已知共有 $n$ 个格子，编号 $1$ 到 $n$（不包含起始格）。

小 A 跳上下一个格子但**没跳到**其中心的概率为 $a\%$，跳上下一个格子且**跳到了**其中心的概率为 $b\%$，剩余 $(100-a-b)\%$ 为没跳上下一个格子的概率。

求他的期望得分，并对 $10^9+7$ 取模。

inputFormat:
第一行三个整数 $n,a,b$。

第二行一个整数 $m$，表示共有 $m$ 个特殊格。

后 $m$ 行每行两个整数 $x,y$，表示每个特殊格的编号及其额外的加分，保证 $x$ 均不相同。

outputFormat: 一个整数表示期望得分。


title: [BalticOI 2000] Time Zones

description:
给定一个整数 $n$，现在将世界划分为 $n$ 个时区，分别编号为第 $0$ 时区到第 $n-1$ 时区，您在第 $0$ 时区。现在有 $n$ 个地方发来的一些时间，用 $hh$ 和 $mm$ 表示，代表小时和分钟。

保证 $0 \le hh \le n-1$，$0 \le mm \le 59$。

发来时间中间要跨时区，跨过一个时区 $hh$ 就要变化 $1$，因此最终第 $0$ 时区得到的时间信息是最后跨时区进行加减后的结果，跨时区之后不能使得 $hh$ 超出 $[0,n-1]$ 的范围。

求这 $n$ 个时间信息分别来自哪几个时区。

inputFormat:
第一行一个整数 $n$ 代表时区数和时间消息数。
接下来 $n$ 行每行两个整数 $hh$ 和 $mm$ 代表一个时间消息，注意 $hh$ 和 $mm$ 都要用两位整数的形式表示。
比如 $hh=5$，$mm=6$ 最终表示结果就是 $0506$。

outputFormat: 一行 $n$ 个整数代表每个时间消息来自哪个时区。

hint:
#### 样例说明

注意样例 $1$ 的第 $3$ 个数据，该时间消息必须来自第 $0$ 时区，因为其他时区的时间消息到第 $0$ 时区都要至少经过 $1$ 小时，$hh$ 最小值为 $5$，就超过了 $[0,n-1]$ 的范围。

#### 数据规模与约定

对于 $100\%$ 的数据，$5 \le n \le 60$，$0 \le hh \le n-1$，$0 \le mm \le 59$。

#### 说明

翻译自 [BalticOI 2000 Day1 B Time Zones](https://boi.cses.fi/files/boi2000_day1.pdf)。


title: [BalticOI 2000] Honeycomb Problem

description:
如下图，是一个边长为 $3$ 的蜂窝图，每个点有点权：

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

现在要从上面一行的某一点到最下面的一行某一点，每次只可以到达左下角的点和右下角的点，您最多可以交换选定的一行中的两个点的数值。

求通过交换，从上面一行的某一点到最下面的一行某一点的点权之和的最大值是多少。

inputFormat:
第一行一个整数 $n$ 代表蜂窝图的边长。
接下来 $2n-1$ 行每行若干个整数代表一个蜂窝图。

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

hint:
#### 样例说明

对于样例 $1$，交换第四行的 $5$ 和 $1$，然后我们就可以得到一条点权之和最大的路径：

$$3 \to 2 \to 8 \to 5 \to 4$$

最大值为 $22$。

#### 数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 99$，$0 \le $ 蜂窝图中的每个图 $\le 99$。

#### 说明

翻译自 [BalticOI 2000 Day1 A Honeycomb Problem](https://boi.cses.fi/files/boi2000_day1.pdf)。


title: [BalticOI 2000] Electronical Plate

description:
给定一个 $(n-1) \times (n-1)$ 的网格，两条直线的交点有一个节点，则这个网格有 $n \times n$ 个节点，从左往右，从上往下，这些节点依次编号为 $1$ 到 $n^2$。

这些节点中有一些节点被称为「电源」，现在要连一些电路，要求以电源为起点，连向其他节点，要求不能经过其他电源，终点为网格上下左右四个边缘上的节点。

比如说下面这个图，黑色的为电源，白色的为普通节点：

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

因为有一些电源就在边缘上，我们不需要进行连接。有一种可行解即为：

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

如果有多组解，找出其中一组即可。

inputFormat:
第一行一个整数 $n$ 代表网格的大小。
接下来 $n$ 行每行 $n$ 个整数代表每个节点，$0$ 或者 $1$。
$0$ 代表这个节点是普通节点，$1$ 代表这个节点是电源。

outputFormat:
第一行一个整数 $k$ 代表至少需要多少个电源要连电线。（有一些在边缘的电源不需要连电线）
接下来 $k$ 行，每行首先第一个整数代表要连电线的电源的编号，接下来一个字符串代表电源要把电线连向边缘的路线，向左输出 `W`，向右输出 `E`，向上输出 `N`，向下输出 `S`，电源按照编号从小到大输出。
如果有多解，输出一组即可。

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

对于 $100\%$ 的数据，$3 \le n \le 15$。

**本题使用 Special Judge。**

感谢 spj 提供者 @[tiger2005](https://www.luogu.com.cn/user/60864)。

#### 说明

翻译自 [BalticOI 2000 Day1 C Electronical Plate](https://boi.cses.fi/files/boi2000_day1.pdf)。


title: [BalticOI 2016 Day2] 迷宫

description:
您看到了一道题

> 给定一个迷宫，迷宫中有四种方块：
>
> - `.` 地板，可以走
> - `#` 墙壁，不可以走，也不可以穿过
> - `x` 基地
> - `o` 硬币
>
> 您的任务就是求从基地开始，可以向上，向下，向左，向右走，最后回到基地得到的硬币数的最大值。

您想知道，给定迷宫的大小为 $n \times m$，并且给定答案为 $k$，能构造出的一个迷宫。

因为您创造了 $t$ 道这样的题，所以您要构造 $t$ 个迷宫。

inputFormat:
第一行一个整数 $t$ 代表要构造的迷宫数。
接下来 $t$ 行每行三个整数 $n,m,k$ 代表迷宫大小和最终答案。

outputFormat:
对于每个要构造的数据，输出 $n$ 行，每行 $m$ 个字符代表这个迷宫。
两个迷宫之间要有一个空行。

hint:
#### 数据说明与评分策略

**本题为提交答案题**，输入数据请从附加文件中获取。

一共有 $1$ 组 $t=50$ 的输入输出文件，您提交答案的答案包里的文件应为 `maze.out`。

我们定义：

- 您得到的迷宫的难度 $x$ 为从基地开始获取所有金币的最短路长度。
- 官方得到的迷宫的难度 $d$ 为从基地开始获取所有金币的最短路长度。

**本题采用 Special Judge**。于每个构造出的迷宫，您可以得到

$$\max(0,100-3(d-x))$$

的分数。

感谢 spj 提供者 @[tiger2005](https://www.luogu.com.cn/user/60864)。

#### 说明

翻译自 [BalticOI 2016 Day2 B Maze](https://boi.cses.fi/files/boi2016_day2.pdf)。


title: [BalticOI 2014 Day2] Demarcation

description:
给定一个多边形，求画一条线段将这个多边形分为两个全等的多边形。

需要保证这条线段与坐标轴平行。

inputFormat:
第一行一个整数 $N$ 代表这个多边形由 $N$ 个点组成。
接下来 $N$ 行每行两个整数 $X_i,Y_i$ 代表多边形的一个点 $(X_i,Y_i)$。

outputFormat:
如果不可以分为两个全等的多边形，输出一个字符串 `NO`。
如果可以，输出四个整数 $x_1,y_1,x_2,y_2$ 代表线段 $(x_1,y_1)\to (x_2,y_2)$。

hint:
#### 样例说明

对于样例 $1$，如下图所示，可以分成两个全等的多边形：

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

同理，输出 `3 2 1 2` 也可。

对于样例 $2$，如下图所示，不可以分为两个全等的多边形：

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

#### 数据规模与约定

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

- Subtask 1（12 pts）：保证有解。
- Subtask 2（15 pts）：$N \le 200$。
- Subtask 3（23 pts）：$N \le 2000$。
- Subtask 4（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$4 \le N \le 10^5$。

**本题采用 Special Judge。**

#### 说明

翻译自 [BalticOI 2014 Day2 A Demarcation](https://boi.cses.fi/files/boi2014_day2.pdf)。


title: [BalticOI 2014 Day1] Three Friends

description:
有一个字符串 $S$，对他进行操作：

1. 将 $S$ 复制为两份，存在字符串 $T$ 中
2. 在 $T$ 的某一位置上插入一个字符，得到字符串 $U$

现在给定 $U$，求 $S$。

inputFormat:
第一行一个整数 $N$ 代表 $U$ 的长度。
第二行 $N$ 个字符代表字符串 $U$。

outputFormat:
- 如果不能通过上述的步骤从 $S$ 推到 $U$，输出 `NOT POSSIBLE`。
- 如果从 $U$ 得到的 $S$ 不是唯一的，输出 `NOT UNIQUE`。
- 否则，输出一个字符串 $S$。

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

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

- Subtask 1（35 pts）：$N \le 2001$。
- Subtask 2（65 pts）：无特殊限制。

对于 $100\%$ 的数据，$2 \le N \le 2 \times 10^6+1$，保证 $U$ 中只包含大写字母。

#### 说明

翻译自 [BalticOI 2014 Day1 B Three Friends](https://boi.cses.fi/files/boi2014_day1.pdf)。