title: [IOI2007] flood 洪水

description:
1964年的一场灾难性的洪水冲毁了萨格勒布城。洪水袭来时许多建筑的墙被彻底冲毁。在这个题目中，给定了城市在洪水来袭前的简化模型，你的任务是确定洪水过后哪些墙没有被冲毁。

简化模型由平面上的$N$个点和$W$堵墙构成。每堵墙连接两个点，没有任何一堵墙通过其它点。模型具有如下性质：

- 不存在两堵墙相交或者重合的情况，但是两堵墙可以在端点相连；
- 每堵墙或者平行于坐标系的横轴，或者平行于坐标系的纵轴。

最开始，整个坐标平面都是干的。在零时刻，洪水将城市的外围淹没（城市的外围是指没有被墙围起来的区域）。一个小时之后，所有一边是水，一边是空气的墙在水的压力下都会倒塌。于是洪水又会吞没那些没有被完好的墙围住的区域。接下来又有一些墙面临一边是水一边是空气，将要被洪水冲毁的局面。又过了一个小时，这些墙也被冲毁了。这样的过程不断重复，直到洪水淹没整个城市。

下图给出了洪水侵袭过程的一个例子。

![](https://cdn.luogu.com.cn/upload/pic/20664.png )

给定$N$个点的坐标和连接这些点的$W$堵墙的描述，编程确定洪水过后，哪些墙会被留下来。

inputFormat: 输入的第一行包含一个整数$N(2 \leq N \leq 100 000)$, 表示平面上的点的个数。 接下来的$N$行每行包含两个整数$X$和$Y$（都是$0$到$1 000 000$之间（包括$0$和$1 000 000$）的整数），表示点的坐标。所有点按照它们被给出的顺序编号为$1$到$N$。没有两个点在同一位置上。 接下来一行包含一个整数$W(1 \leq W \leq 2N)$，表示墙的数目。 接下来$W$行每行包含两个不同的整数$A$和$B(1 \leq A \leq N, 1 \leq B \leq N)$，表示在洪水到来前，有一堵墙连接$A$和$B$。这些墙按照它们被给出的顺序编号为$1$到$W$。

outputFormat:
输出的第一行包含一个整数$K$，表示洪水过后留下的墙的数目。

接下来的$K$行包含留下的墙的序号，每行一个，序号可以以任意顺序输出。

hint:
这个样例对应前页图中的例子。

有40分的测试点，所有坐标小于等于$500$。

在上面的测试点和另外15分的测试点中，点的个数不超过$500$个。


title: [IOI2007] sails 船帆

type: P

description:
让我们来建造一艘新的海盗船。船上有 N个旗杆，每根旗杆被分成单位长度的小节。旗杆的长度等于它被分成的小节的数目。每根旗杆上会挂一些帆，每张帆正好占据旗杆上的一个小节。在一根旗杆上的帆可以任意排布在不同的小节中，但是每个小节上至多能挂一张帆。

在风中，帆的不同排布方式会产生不同的推动力。靠近船头的帆比它后面的相同高度上的帆获得的推动力少，换句话说，靠近船头的帆的推动力由于受它后面相同高度的帆的影响而打了折扣。对于任意一张帆，它的推动力折扣等于在它后面并且和它在同一高度的帆的数目。

所有帆的任意一种位置组合的推动力折扣总和等于在该位置下所有帆的推动力折扣的总和。

![](https://cdn.luogu.com.cn/upload/pic/20670.png )

这条船上有6个旗杆，从前（图上的左边）到后的高度分别是3，5，4，2，4和3。图中所示的帆的位置组合的总推动力折扣是10。上图给出了每张帆自己的推动力折扣。

给定N个旗杆的高度和每个旗杆上挂的帆的数目，写一个程序求出所有位置组合中的可能达到的最小的总推动力折扣。

inputFormat: 第一行包含一个整数$N(2 \leq N \leq 100 000)$，表示旗杆的数目。 接下来的N行每行包含两个整数$H$和$K(1 \leq H \leq 100 000, 1 \leq K \leq H)$，分别表示对应旗杆的高度及其上的帆的数目。旗杆按照从船头到船尾的顺序给出。

outputFormat:
输出包含一个整数，表示可以达到的最小的总推动力折扣。

注意：计算和输出结果时使用64位整数类型（在C/C++中用```long long```, 在Pascal中用```int64```）。

hint:
这个样例数据和上页中图示的样例相同。

在 25 分的测试数据中，帆的不同位置组合的总数目不超过 $1,000,000$ 。


title: [IOI2007] pairs 动物对数

description:
Mirko 和 Slavko 正在玩动物玩具的游戏。 首先，他们要在下图给出的三种玩具模板中选择一种。三种模板分别由一维、二维和三维的网格点（在图中用圆圈表示）组成。

![](https://cdn.luogu.com.cn/upload/pic/20672.png )

接下来Mirko 把 $N$ 个小动物玩具放到选中的模板的网格点上。

动物玩具可以走一步到达与它相邻的网格点上（在图中相邻的点之间有一条小短线相连）。两个网格点之间的距离定义为**从一个网格点到另一个网格点所需要移动的最小步数**。

如果两个动物之间的距离小于等于$D$，则它们之间可以互相听见。Slavko 的任务是计算在模板上有多少对动物可以互相听得见。

给定模板的类型、所有动物的位置以及数字$D$，写一个程序计算有多少对动物可以互相听得见。

inputFormat:
输入的第一行按顺序给出四个整数：
- 模板类型 $B (1 \leq B \leq 3)$;
- 玩具动物的数目 $N (1 \leq N \leq 100 000)$;
- 动物之间可以互相听得见的最大距离$D (1 \leq D \leq 100 000 000)$;
- 模板的大小 $M$ ( 即在输入中允许的最大的坐标值):  当 $B=1$ 时, $M$ 最大是 $75 000 000$. 当 $B=2$时, $M$ 最大是 $75 000$. 当 $B=3$时, $M$ 最大是 $75$.

接下来的$N$ 行每行包含$B$ 个整数，整数之间用空格隔开，表示一个动物玩具的坐标。坐标的取值范围是$1$ 到 $M$ ( 包括$M$ )。

每个网格点可以同时包含多个动物玩具。

outputFormat:
输出应该包括一个整数，表示可以互相听得见的玩具动物的对数。

注意：使用64 位整数类型计算和输出结果 (在 C/C++ 中用```long long```, 在Pascal 中用```int64``` ) 。

hint:
在30分的测试数据中, 动物数目 $N$ 最多是 $1 000$。

如果成功通过了某一种模板（一维、二维或者三维）的全部测试数据，将会得到至少30分。

对于input 1的解释： 假设动物按给出的顺序编号为$1$到$6$。$4$对互相能够听得到的动物分别是:
- 1-5 ( 距离是5)
- 1-6 ( 距离是2)
- 2-3 ( 距离是0)
- 5-6 ( 距离是3)

对于input 2 的解释：$8$对动物分别是:
- 1-2 ( 距离是2)
- 1-4 ( 距离是4)
- 1-5 ( 距离是3)
- 2-3 ( 距离是3)
- 2-4 ( 距离是4)
- 3-4 ( 距离是3)
- 3-5 ( 距离是4)
- 4-5 ( 距离是3)


title: [IOI2007] training 训练路径

description:
马克(Mirko)和斯拉夫克(Slavko)正在为克罗地亚举办的每年一次的双人骑车马拉松赛而紧张训练。他们需要选择一条训练路径。

他们国家有$N$个城市和$M$条道路。每条道路连接两个城市。这些道路中恰好有$N-1$条是铺设好的道路，其余道路是未经铺设的土路。幸运的是，每两个城市之间都存在一条由铺设好的道路组成的通路。换句话说，这$N$个城市和$N-1$条铺设好的道路构成一个树状结构。

此外，每个城市最多是$10$条道路的端点。

一条训练路径由某个城市开始，途经一些道路后在原来起始的城市结束。因为马克和斯拉夫克喜欢去看新城市，所以他们制定了一条规则：绝不中途穿越已经去过的城市，并且绝不在相同的道路上骑行两次（不管方向是否相同）。训练路径可以从任何一个城市开始，并且不需要访问所有城市。

显然，坐在后座的骑行者更为轻松，因为坐在前面的可以为他挡风。为此，马克和斯拉夫克在每个城市都要调换位置。为了保证他们的训练强度相同，他们要选择一条具有偶数条道路的路径。

马克和斯拉夫克的竞争者决定在某些未经铺设的土路上设置路障，使得他们两人不可能找到满足上述要求的训练路径。已知在每条土路上设置路障都有一个费用值（一个正整数），并且竞争者不能在铺设好的道路上设置路障。

给定城市和道路网的描述，写一个程序计算出为了使得满足上述要求的训练路径不存在，而需要的设置路障的最小总费用。

inputFormat: 输入的第一行包含两个整数$N$和$M$，（$2\leq N\leq 1000$，$N-1\leq M\leq5000$），分别表示城市和道路的个数。 接下来的$M$行每行包含$3$个整数$A, B$和$C$（$1\leq A\leq N, 1\leq B\leq N, 0\leq C\leq10 000$）, 用来描述一条道路。$A$和$B$是不同的整数，表示由这条道路直接相连的两个城市。对于铺设好的道路$C$是$0$；对于土路，$C$是在该条路上设置路障所需的费用值。 每个城市最多是$10$条道路的端点。任意两个城市都不会有多于一条直接相连的道路。

outputFormat: 输出包含一个整数，表示求出的最小总费用。

hint:
![](https://cdn.luogu.com.cn/upload/pic/20676.png )

第一个样例中道路与城市的布置。已被铺设好的道路以粗边显示。

![](https://cdn.luogu.com.cn/upload/pic/20677.png )

共有5种可能的路线。如果边1-3、3-5和2-5被封锁，则两人将会不能使用5种路线的任何一种。封锁这三条边的代价是5。

只封锁两条边，像是2-4和2-5，也是可以的，但这样会导致较高的代价，6。

在前30分的测试数据中，铺设好的道路会形成一条链。


title: 帕秋莉的魔导书

background: 帕秋莉有一个巨大的图书馆，里面有数以万计的书，其中大部分为魔导书。

description:
魔导书是一种需要钥匙才能看得懂的书，然而只有和书写者同等或更高熟练度的人才能看得见钥匙。因此，每本魔导书都有它自己的等级 $a_i$，同时它也有自己的知识程度为 $w_i$，现在我们想要知道，一个等级为 $b_i$ 的生物(...)，可以从这些魔导书中得到多少知识。

然而不幸的是，每个生物并不知道自己确切的等级，只有一个等级的大致范围，你需要计算出这个生物获得知识程度的期望值。

inputFormat:
第一行两个正整数 $n,m$ 代表起始书的个数，以及操作的个数。

以下 $n$ 行，每行两个正整数 $a_i$ 和 $w_i$，代表每本书的等级以及知识程度。

接下来的 $m$ 行，每行 $2$ 或 $3$ 个正整数。

操作 1：格式：`1 x y`。含义：求等级为 $[x, y]$ 的生物能获得的期望知识程度。

操作 2：格式：`2 x y`。含义：图书馆又收入了一本等级为 $x$，知识程度为 $y$ 的魔导书。

outputFormat: 输出包含若干行实数，即为所有操作 1 的结果，答案保留四位小数。

hint:
对于 $30\%$ 的数据，保证 $1\le $ 所有输入的数字 $\le 10^3$。

对于 $100\%$ 的数据，保证 $1\le n,m\le 10^5$，对于其他数字，保证在 $32$ 位带符号整数范围内（保证运算中所有的数均在 $-2^{63}\sim 2^{63}-1$ 内）。


title: 帕秋莉的魔法

background: 帕秋莉是一个有哮喘病的魔法使。

description:
众所周知，不同的魔法会需要念不同长度咒语$a_i$但也会产生不同的威力$b_i$。同时，在发动过一个魔法后也会对接下来发动的一个魔法产生影响$w_{i,j}$（即在用完第$i$种魔法后第$j$种魔法的威力会变为$b_j + w_{i.j}$，而且只会影响到下一个魔法）。
（当然也可能有魔法会减少咒语长度或者产生治愈的效果的魔法，魔法不可重复使用）

帕秋莉现在知道使用每种魔法后对接下来一种魔法的影响，以及每种魔法需要念的咒语长度和产生的威力，同时，由于编号大的魔法比编号小的魔法高级，所以一个魔法只有在编号不大于自己的魔法后使用才能保证魔法的连续性），现在她想知道念出长度为$m$的咒语最大能产生多少威力。(以免下次在战斗中又因为哮喘病发作而惨败)

(编号顺序即给出的顺序)

inputFormat:
第一行：两个正整数$n,m$，表示一共有$n$种魔法，念出长度为$m$咒语。

接下来的$n$行：每行两个正整数$a_i,b_i $，表示咒语的长度以及魔法的威力。

接下来的$n$行 ： 每行$n$个整数，第$i$行，第$j$列，代表第$i$种魔法在第$j$种魔法后使用产生的附加值$w_{i,j}$。

outputFormat:
一个整数，表示最大能产生的威力。
（如果无论如何都无法组成长度为$m$的咒语，则输出-1）

hint:
对于20%的数据，保证$a_i$ = 1

对于另外20%的数据，保证所有数字均为正整数。

对于100%的数据，$1 \le n \le 50,  |a_i|,|b_i|, |w_{i,j}|\le 50, |m| \le 2500$，保证运算过程中的数字大小均在int范围内(废话...)。


title: [BalticOI 2005] Maze

description: 给出一个平行四边形的长与高. 给出入口与出口,对于四边形的每条边都有一种Color,非黑即白. 你要找出一条路径,走过的边黑白交替,且长度最短

inputFormat: 第一行给出平行四边形的长与高.且值在[1,500] 第二行给出入口,出口坐标. 下面的字符矩阵代表这个平行四边形每条边的Color

outputFormat: 输出路径的最少长度

samples:
5 4
0 2 5 2
nnbnn
nnnwwbwnnnn
nbbbn
nnwbwwbwwnn
bwwww
nnbwbbwwbnn
nwwwn
nnnnbwbbnnn
nnwnn


title: [BalticOI 2005] Bus Trip

description:
这里有 $N$ 座城镇, 和城镇之间的 $M$ 巴士单行线(没有中间停靠站)。 城镇从$1$到 $N$ 标号。 一个旅行者在 $0$ 时刻位于 $1$ 号城镇想要到达 $P$ 号城镇。他将乘坐巴士在 $T$ 时刻到达 $P$ 号城镇。如果他早到了，他必须等待。

对于任意一个巴士路线 $i$ , 我们知道其中的起点城镇 $si$ 和目标城镇$ti$ 。我们也同样知道路线的出发时间和到达时间,但仅仅是近似值：我们知道巴士离开起点城镇 $si$ 在时间范围$[ai, bi]$内，且到达目标城镇 $ti$ 在时间范围$[ci, di]$内(端点值包括在内)。

旅行者不喜欢等待, 因此他要寻找一个旅行计划使得最大等待时间尽量小，同时保证绝对不会错过计划中的任何一辆巴士(意思是, 每次他换乘巴士, 他需要下车的巴士的最晚到达时间不会迟于他需要搭乘的下一辆巴士的最早出发时间)。

当计算等待时间时，我们必须假设最早可能到达的时间和最晚可能出发的时间。

编写一个程序，寻找一个最为合理的搭车计划。

inputFormat:
输入文件名为TRIP.IN。第一行包含整数$N(1 \leq N \leq 50000),M(1 \leq M \leq 100000),P(1 \leq P \leq N),T(0 \leq T \leq 1000000000)$。

下面的M线描述了公交线路。每一行包含整数$si, ti, ai, bi, ci, di$，其中$si$和$ti$是公交线路$i$的始发地和目的地，$ai,bi,ci,di$描述了出发和到达时间，如上文所解释的$(1 \leq si \leq N, 1 \leq ti \leq N, 0 \leq ai \leq bi < ci \leq di \leq 1,000,000,000)$。

outputFormat: 只需要包含一个数——最合理搭车方案的最长可能等待时间。如果不可能保证在 $T$ 时刻到达城市$P$，那么输出-1。

hint: 翻译来自BZOJ P1354


title: [BalticOI 2016 day1] Bosses

description:
A company of $n$ employees is due for a restructuring. In the resulting hierarchy,represented as a rooted tree, every node will be the boss of its children.

Each employee has a list of bosses they will accept. In addition, all employees mustbe assigned a salary. The salary must be a positive integer, and the salary of eachboss must be larger than the sum of salaries of their immediate subordinates.

Your task is to structure the company so that all above conditions hold, and the sumof all the salaries is as small as possible.

inputFormat:
The first input line contains an integer $n$ : the number of employees. The employees are numbered $1,2,...,n$

.After this, the input contains $n$ lines that describe the preferences of the employees.The $i$th such line contains an integer $k_i$ , followed by a list of $k_i$ integers. The list consists of all employees that the $i$th employee accepts as their boss.

outputFormat: You should output the lowest total salary among all valid restructurings. You can assume that at least one solution exists.

translation:
[BalticOI 2016 Day1]上司们

## 题目描述

某公司有 $n$ 个职员，其职员之间的阶级关系可以用一棵有根树表示，每个结点都是其所有儿子的上司。
每个职员应当分配一个工资。工资是一个正整数，且每个上司的工资必须大于它所有直系下属的工资之和。
你的任务是找到一种工资分配方案，使得以上所有条件满足且工资之和尽量小。

## 输入格式

第一行包含一个整数 $n$，表示职员的个数，职员依次编号为 $1,2,\dots,n$。
接下来 $n$ 行，第 $i$ 行包含一个整数 $k_i$，以及一个包含 $k_i$ 个数的数列。这个数列表示第 $i$ 个员工的愿意接受的上司。

## 输出格式

输出所有方案中最小的工资之和，数据保证有解。

由 @I_love_him52 提供翻译


title: [BalticOI 2016 day1] Park

description:
In the capital of Byteland, there is a fenced park whose area is a rectangle. The trees and the visitors in the park are represented as circles.

There are four entrances in the park, one in each corner (1 = bottom-left, 2 =bottom-right, 3 = top-right, 4 = top-left). The visitors can enter and exit the park only through the entrances.

Visitors can enter and exit the park when they touch both sides of a corner of the corresponding entrance. Visitors can move freely in the park, but they cannot overlap any of the trees or the fence.

Your task is to calculate for each visitor, given the entrance they will enter the park,through which entrances they can exit the park.

inputFormat:
The first input line contains two integers $w$ and $h$ : the number of trees in the park and the number of visitors.

The second input line contains two integers $w$ and $h$ : the width and the height of the park area. The bottom-left corner is $(0,0)$, and the top-right corner is $(w,h)$.

After this, there are  lines that describe the trees. Each line contains three integers, $x,y$ and $r$ : the center of the tree is $(x,y)$ and its radius is $r$. The trees do not overlap each other or the fence.

Finally, there are $m$ lines that describe the visitors. Each line contains two integers $r$ and $e$ : the radius of the visitor and the entrance they will enter the park.

In addition, no tree overlaps a square area of $2k\times2k$ in each corner, where $k$ is the radius of the largest visitor.

outputFormat: You should output for each visitor a single line containing the entrances through which they can exit the park, in sorted order without spaces in between.

translation:
## 题目描述

在 Byteland 的首都，有一个以围墙包裹的矩形公园，其中以圆形表示游客和树。
公园里有四个入口，分别在四个角落（$1, 2, 3, 4$ 分别对应左下、右下、右上、左上）。游客只能从入口进出。
游客可以在他们与公园的两邻边相切的时候进出对应的入口。游客可以在公园里自由活动但不允许与树重叠。
你的任务是为每个游客计算，给定他们进入公园的入口，他们可以从哪个入口离开公园。

## 输入格式

第一行包含两个整数 $n$ 和 $m$，分别为树的个数和游客的个数。
第二行包含两个整数 $w$ 和 $h$，公园的左下角在 $(0,0)$，右上角在 $(w,h)$。
接下来 $n$ 行，每行三个整数 $x,y$ 和 $r$，表示有一棵圆心在 $(x,y)$ 且半径为 $r$ 的树。保证树与树之间不会互相重叠。
接下来 $m$ 行，每行两个整数 $r$ 和 $e$，表示有一个半径为 $r$ 的游客从入口 $e$ 进入。
此外，保证没有树会与每个角落的一个大小为 $2k^2$ 的方形区域重叠，$k$ 表示最大的游客半径。

## 输出格式

对于每个游客，输出没有空格的一行，表示该游客可以从这几个入口离开，按照升序排列。

## 限制与提示

两个物体有重叠定义为它们不止一个公共点。

下图展示了每个游客的入口和可能的路线：

![](https://i.loli.net/2018/08/11/5b6e30c4b5a35.png)

对于每个子任务，$4k \leq w,h \leq 10^9$，$k$表示最大的游客半径。

|子任务|分数|数据范围|
|:-:|:-:|-|
|1|27|$1 \leq n \leq 2000,m=1$|
|2|31|$1 \leq n \leq 200,1 \leq m \leq 10^5$|
|3|42|$1 \leq n \leq 2000,1 \leq m \leq 10^5$|

由 @I_love_him52 提供翻译

hint:
Two objects touch if they have one common point. Two objects overlap if they have more than one common point.

## 样例解释

The following figure shows the entrance areas and possible routes for each visitor:

![](https://cdn.luogu.com.cn/upload/pic/20869.png)

## Subtasks

In all subtasks $4k\leq w,h\leq10^9$ where $k$ is the radius of the largest visitor.

### Subtask 1 (27 points)

- $1\leq n\leq2000$

- $m=1$

### Subtask 2 (31 points)

- $1\leq n\leq200$

- $1\leq m\leq10^5$

### Subtask 3 (42 points)

- $1\leq n\leq2000$

- $1\leq m\leq10^5$


title: [BalticOI 2016 day1] Spiral

description:
A grid of size $(2n+1)\times(2n+1)$ has been constructed as follows. Number $1$ has been placed in the center square, number $2$ has been placed to the right of it, and the following numbers have been placed along the spiral counterclockwise.

Your task is to calculate answers for $q$ queries where the sum of numbers in an rectangular region in the grid is requested (modulo $10^9+7$). For example, in the following grid $n=2$ and the sum of numbers in the gray region is $74$ :

![](https://cdn.luogu.com.cn/upload/pic/20871.png)

inputFormat:
The first input line contains two integers $n$ and $q$ : the size of the grid and the number of queries.

After this, there are $q$ lines, each containing four integers $x_1, y_1, x_2$  and $y_2$ ($-n\leq x_1\leq x_2\leq n, -n\leq y_1\leq y_2\leq n$). This means that you should calculate the sum of numbers in a rectangular region with corners $(x_1,y_1)$ and $(x_2,y_2)$.

outputFormat: You should output the answer for each query (modulo $10^9+7$).

translation:
[BalticOI 2016 Day1]螺旋

## 题目描述

一个矩阵的大小为 $(2n+1)\times (2n+1)$，我们们通过下述方法填数：数字 $1$ 在中心，数字 $2$ 在其右，其他数字依次按照逆时针螺旋摆放。

你的任务是对于 $q$ 个询问，计算出一个给定子矩阵所有数字的和对 $(10^9+7)$ 取余的结果。比如以下 $n=2$ 的矩阵，灰色区域的数字之和为 $74$：

![](https://i.loli.net/2018/08/11/5b6e3ead24175.png)

## 输入格式

第一行，两个整数 $n$ 和 $q$，分别表示矩阵的大小和询问的个数。

接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2$ 和 $y_2$ $(-n \leq x_1 \leq x_2 \leq n,$ $-n \leq y_1 \leq y_2 \leq n)$。这表示你需要计算一个对角为 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的子矩阵的数字之和。

## 输出格式

对于每个询问，输出一行表示答案（对 $10^9+7$ 取余）。

由 @I_love_him52 提供翻译

hint:
## Subtasks

In all subtasks $1\leq q\leq100$.

### Subtask 1 (12 points)

- $1\leq n\leq1000$

### Subtask 2 (15 points)

- $1\leq n\leq10^9$

- $x_1=x_2$ and $y_1=y_2$

### Subtask 3 (17 points)

- $1\leq n\leq10^5$

### Subtask 4 (31 points)

- $1\leq n\leq10^9$

- $x_1=y_1=1$

### Subtask 5 (25 points)

- $1\leq n\leq10^9$


title: [IOI2008] Type Printer

description:
你需要利用一台可移动的打印机打印出 $n$ 个单词。这种可移动式打印机是一种老式打印机，它需要你将一些小的金属块（每个包含一个字母）放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作：

- 在打印机当前词的末端（尾部）添加一个字母；
- 在打印机当前词的尾部删去一个字母（将打印机当前词的最后一个字母删去）。仅当打印机当前至少有一个字母时才允许进行该操作；
- 将打印机上的当前词打印出来。

初始时打印机为空，或者说它不含任何带字母的金属块。打印结束时，允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。

由于每一个操作都需要一定时间，所以需要你尽可能减少所需操作的总数目（将操作的总数最小化）。

你需要编写一个程序，给定所要打印的 $n$ 个单词，找出以任意次序打印所有单词所需操作的最小数目，并输出一种这样的操作序列。

inputFormat:
- 第 $1$ 行包含一个整数 $n$, 表示你需要打印的单词数。
- 随后的 $n$ 行中，每一行都包含一个单词。每个词仅由小写字母组成，而且单词的长度为 $1$ 到 $20$ 个字母（包含 $1$ 和 $20$ 在内）。所有单词都不相同。

outputFormat:
第一行包含一个整数 $m$，表示打印这 $n$ 个单词所需操作的最小数目。

接下来的 $m$ 行，每行一个字符，表示你的操作序列，序列的描述方法如下：
- 添加一个字母，用这个小写字母的自身来表示。
- 删去一个字母，用 `-` 表示。
- 打印单词，用 `P` 表示。

samples:
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P


title: [IOI2008] Fish

description:
据Scheherazade说，在很远的沙漠中有一个湖。湖中起初有$F$条鱼。选择最值钱的$K$种宝石，对$F$条鱼的每一条只喂给它一块宝石。注意，因为$K$可能小于$F$，两条或更多的鱼可能会吞下同一种宝石。

随着时间的流逝，有些鱼吃掉了别的鱼。一条鱼能够吃掉另一条鱼，当且仅当它的长度至少是被吃掉的鱼的两倍($A$ 能吃掉$B$ 当且仅当$L_A \geq 2L_B$)。没有规则说明一条鱼何时会吃掉另一条鱼。有的鱼可能会一条接一条地吃掉几条小鱼，而有的鱼可能不吃别的鱼，即使它们有能力吃。当一条鱼吃掉一条小鱼时，它的身长并不改变，但是小鱼腹中的宝石会完好无损地进到大鱼腹中。

据Scheherazade说，如果你能够找到那个湖，你会被准许捕捉一条鱼，并且得到鱼腹中的宝石。你很想试试运气，但是在出发前很想知道捉到一条鱼可能会有多少种不同的宝石组合。

写一个程序，给定每条鱼的长度以及其最初吞食的宝石的种类，找出鱼腹中宝石不同组合的数量对给定整数$M$取模的值。组合由每种宝石的数量定义，与宝石的排列顺序无关。同一类宝石中任意两块是没有区别的。

inputFormat:
你的程序需要从标准输入上读入下列数据：
- 第一行是整数$F$, 即湖中最初鱼的数量。
- 第二行是整数$K$, 即宝石的种类数。不同类型的宝石分别用从 $1$ 到 $K$的整数表示。
- 第三行是整数$M$。
- 以后 $F$ 行中的每一行用由一个空格分隔的两个整数描述一条鱼：按顺序分别是鱼的长度以及鱼腹中的宝石的类型。

注意: 在所有的测试用例中，$K$ 种宝石中的每一种都会至少有一块。

outputFormat: 你的程序需要在标准输出上输出一个介于$0$和$M-1$(包含)的整数，即宝石所有可能的不同组合数量模$M$，占一行。注意，在问题求解中，数值$M$除了简化计算外没有其他的作用。

hint:
### 限制

有总计70分的测试数据，其中$K$不超过$7,000$。在这些测试数据中，有总计25分的测试数据的$K$不超过$20$。

对于所有的测试数据，$1 \leq F \leq 500,000$，$1 \leq K \leq F$，$2 \leq M \leq 30,000$，$1 \leq L_X \leq 1,000,000,000$。

### 样例说明

有 $11$ 种可能的组合，所以你需要输出$4$，也就是$11$ 模 $7$。这些可能的组合是: $[1] [1,2] [1,2,3] [1,2,3,3] [1,3] [1,3,3] [2] [2,3] [2,3,3] [3]$ 和 $[3,3]$。(对每一种组合, 我们列出其所包含的宝石。 例如，$[2,3,3]$ 包含一块$2$型宝石和两块$3$型宝石)

这些组合可以由下述方式获得:

$[1]$: 如果你在第二条鱼 (或第四条) 吃掉任何其它鱼之前捕捉到它。

$[1,2]$: 如果第二条鱼吃掉第一条鱼, 它就会有一块 $1$ 型宝石(它在初始时刻吞下的) 和一块2型宝石 (从第一条鱼腹中得到的)。

$[1,2,3]$: 一种可能的途径是: 第四条鱼吃掉第一条鱼，然后第三条鱼又吃掉它。如果你此时捉到了第三条鱼，那它腹中就有这三种宝石一样一块

$[1,2,3,3]$: 第四条鱼吃掉第一条鱼，第三条鱼吃掉第四条鱼，第三条鱼吃掉第五条鱼，你捉到了第三条鱼。

$[1,3]$: 第三条鱼吃掉第四条鱼，你捉到了第三条鱼。

$[1,3,3]$: 第三条鱼吃掉第五条鱼，第三条鱼吃掉第四条鱼，你捉到了第三条鱼。

$[2]$: 你捉到了第一条鱼。

$[2,3]$: 第三条鱼吃掉第一条鱼，你捉到了第三条鱼

$[2,3,3]$: 第三条鱼吃掉第一条鱼，第三条鱼吃掉第五条鱼，你捉到了第三条鱼。

$[3]$: 你捉到了第三条鱼。

$[3,3]$: 第三条鱼吃掉第五条鱼，你捉到了第三条鱼。


title: [IOI2008] Linear Garden

description:
拉美西斯二世刚刚获胜归来。为了纪念这一胜利，他决定建造一座壮观的花园。这个花园里的植物排成一行，从他在卢克索的宫殿直达卡纳克神庙。所种植的植物只有莲花和纸莎草，因为它们分别代表上埃及和下埃及。

这个花园中必须有$N$棵植物，并且必须保持平衡，即在花园中任取一段，其中莲花和纸莎草的棵数之差不能超过$2$。

花园可以被表示为由字母```L```（莲花）和```P```（纸莎草）组成的字符串。例如，当$N=5$时，有$14$种可能的平衡花园，按照字母排序如下：```LLPLP```，```LLPPL```，```LPLLP```，```LPLPL```，```LPLPP```， ```LPPLL```，```LPPLP```，```PLLPL```，```PLLPP```，```PLPLL```，```PLPLP```，```PLPPL```，```PPLLP``` 和 ```PPLPL```。

给定长度的所有可能的平衡花园可按字母顺序排序，并从$1$开始编号。例如，当$N=5$时，第$12$号花园是```PLPPL```。

写一个程序，给定植物棵数$N$和一个表示平衡花园的字符串，计算该花园的序号模$M$的结果，其中$M$是一个给定的整数。 注意，在问题求解中，数值 $M$ 除了简化计算外没有其他的作用。

inputFormat: 第一行是整数$N$，说明花园中植物的数量。第二行是整数$M$。第三行是长度为$N$的由字符```L```或```P```组成的字符串，表示一个平衡的花园。

outputFormat: 你的程序需要向标准输出上输出一个介于$0$和$M-1$（含）的整数，占一行，表示该花园的序号模$M$。

hint:
有总分40分的测试点的$N$不超过$40$。

对于所有测试点，$1 \leq N \leq 1,000,000$，$7 \leq M \leq 10,000,000$。

### 样例说明

第一个样例中，实际的序号是12。因此输出的是12模7，即5。


title: [IOI2008] Teleporters

description:
你正在参加一项沿着直线路线自西向东横穿埃及的比赛。开始时你位于这条直线路线的最西端。根据比赛规则，你必须要沿着这条直线路线始终向东行进。

在这条直线路线上有 $N$ 个传送器。每个传送器都有两个端点。每当你到达某个传送器的两个端点之一时，传送器都会立即将你传送到该传送器的另一个端点（注意，根据你所在的端点位置，传送器能够将你从当前位置向东或者向西传送）。当你被传送到另一个端点之后，你必须继续沿这条直线路线向东行进；你无法避开你前进路上的任何传送器端点。绝不会出现两个端点在同一位置的情形。所有端点都严格位于这条直线路线的起点和终点之间。

每当你被传送一次，你就会获得 $1$ 分。比赛的目标就是获取尽可能多的分数。为使获得的分数最多，允许你在比赛开始前在这条路线上增设 $M$ 个新的传送器。使用这些新的传送器你也同样可以获得分数。

你可以将这些新传送器的端点设在任何位置上（甚至是非整数坐标点也可以），只要这些坐标点并不出现在已经被另一个端点占用的位置上即可。换句话说，所有传送器的端点位置必须是唯一的。同样，新传送器的端点都必须严格位于这条直线路线的起点和终点之间。

题目可以保证，不管你如何增设这些传送器，你一定可以到达比赛路线的终点。

试编写一个程序，对于给定的 $N$ 个传送器的端点位置和你可以增设的新传送器的数目 $M$，计算你能获得的最高分数。

inputFormat:
你的程序必须从标准输入中读入下列数据：
- 第 $1$行包含一个整数 $N$，表示开始时在路线上的传送器数目；
- 第 $2$行包含一个整数 $M$，表示你可以增设的新传送器的最大数目；
- 随后的 $N$ 行每行描述一个传送器。第 $i$ 行描述第 $i$ 个传送器。每行有两个整数 $W_i$ 和 $E_i$，这两个整数分别描述从路线起点到该传送器的两个端点的距离。

对于给定的这些传送器，没有任何两个端点在同一位置上。比赛路线的起点为位置 $0$，而终点则在位置 $2\,000\,001$ 上。

outputFormat: 你的程序必须向标准输出写一行数据，这行数据只包含一个整数，表示你找到的能获得的最高分数。

hint:
### 样例 1 说明

![](https://cdn.luogu.com.cn/upload/pic/20908.png )

上面左图表示一条初始有 $3$ 个传送器的比赛路线的情形。右图表示在增设一个端点分别为 $0.5$ 和 $1.5$ 的新传送器之后的同一比赛路线。

在增设上图所示的新的传送器之后，你的比赛路途如下：
- 你从位置 $0$ 出发，向东行进。
- 你到达位于 $0.5$ 的传送器端点，并且被传送到另一端点 $1.5$（你获得 $1$ 分）。
- 你继续向东行进，并且到达位于 $2$ 的传送器端点；你被传送到位于 $3$ 的另一端点（这时你共获得 $2$ 分）。
- 你到达位于 $4$ 的传送器端点，并且被传送到位于 $1$ 的另一端点（这时你共获得 $3$ 分）。
- 你到达位于 $1.5$ 的传送器端点，并且被传送到位于 $0.5$ 的另一端点（这时你共获得 $4$ 分）。
- 你到达位于 $1$ 的传送器端点，并且被传送到位于 $4$ 的另一端点（这时你共获得 $5$ 分）。
- 你到达位于 $10$ 的传送器端点，并且被传送到位于 $11$ 的另一端点（这时你共获得 $6$ 分）。
- 你继续行进直到到达比赛的终点，以获得总分为 $6$ 分结束。

### 数据范围

- 对于 $30\%$ 的数据，$N \leq 500$ 并且 $M \leq 500$。
- 对于所有数据，$1 \leq N \leq 1,000,000$，$1 \leq M \leq 1,000,000$，$1 \leq W_X < E_X \leq 2,000,000$。


title: [IOI2008] Pyramid Base

description:
你要在自己财力许可的范围内寻找一个尽可能大的地方，以便兴建一个新的金字塔。为帮助你作出决定，为你提供了土地测绘图。为方便起见，该地块被划分为由$M\times N$个小正方形构成的网格。金字塔的地基部份必须是正方形，而且各边要与这些方格平行。

测绘图中标出了$P$个有可能重叠的障碍物，这些障碍物是上述网格上的长方形，其各边与方格平行。为了建造金字塔，任何塔基所占方格中的障碍物必须被移走。移除障碍物$i$需要付出成本$C_i$。当移除一个障碍物时，需要将障碍物整个地移除，即不能只移除障碍物的一部份。同时，移除一个障碍物对与其重叠的其他障碍物无任何影响。

已知测绘图中$M$和$N$的大小，对$P$个障碍物的描述，移走每个障碍物的成本以及你的预算$B$。编写程序，找出在移走障碍物总成本不超过$B$的前提下金字塔地基的最大边长。

inputFormat:
你的程序需要从标准输入上读入以下数据：
- 第一行包含两个以单个空格分隔的整数，分别表示$M$及$N$。
- 第二行包含整数$B$，是你可付出的最大成本（即你的预算）。
- 第三行包含整数$P$，是测绘图中标出的障碍物数量。
- 以下$P$行的每一行表示一个障碍物。其中第$i$ 行表示第$i$个障碍物。每一行包含$5$个以单个空格分隔的整数$X_{i1}, Y_{i1}, X_{i2}, Y_{i2}$和$C_i$，分别表示障碍物左下角小正方形的座标，右上角小正方形的座标，以及移除这个障碍物的成本。网格左下角的小正方形座标为$(1,1)$，而其右上角小正方形为$(M, N)$。

outputFormat: 你的程序必须向标准输出写出一行，该行只含一个整数，即金字塔基可能的最大边长。如果无法建造任何金字塔，程序应输出0。

hint:
### 样例说明

样例1：

![](https://cdn.luogu.com.cn/upload/pic/20909.png )

样例2：

![](https://cdn.luogu.com.cn/upload/pic/20910.png )

### 数据范围

程序用三组不相交的数据进行评测。以下限制适用于所有的测试数据： $1 \leq M, N \leq 1,000,000$ 网格的尺寸。 $1 \leq Ci \leq 7,000$ 移除障碍物i的成本。 对每个障碍物$i$均有 $1 \leq X_{i1} \leq X_{i2} \leq M$ 并且 $1 \leq Y_{i1} \leq Y_{i2}\leq N$。

第一组测试总分值35分：

- $B = 0$ ——可以付出的最大成本。（不可移除任何障碍物）
- $1\leq P \leq 1,000$ ——网格中障碍物的数目。

第二组测试总分值35分：

- $0 < B \leq 2,000,000,000$ ——你的预算。

- $1\leq P \leq 30,000$ ——网格中障碍物的数目。

第三组测试值30分：

- $B = 0$ ——你的预算。（不可以移除任何障碍物）

- $1\leq P \leq 400,000$ ——网格中障碍物的数目。


title: [Wind Festival] Iron Man

background:
[Midnight - 23:59]

在风筝节上交到了老铁(并不是 Nishikino)，接触了 OI，gyx 全身的热情都被点燃啦！！为了更好地参与到下一届风筝节的工作中去，gyx 准备开始为期一年的学习。

description:
gyx 想用全部的时间学(tui)OI(fei)!!!

gyx 为了合理的利用所有时间学 OI，他开始规划自己的学习计划。

首先，gyx 的眼里每年有 $n$ 天，因为 gyx 实在是太想学习啦，所以他并没有留下玩耍的时间（每天都全部用来学 OI 或者文化课），gyx 划分天数的原则是，在每一天中，gyx 对 OI 的感兴趣程度相同。但是，未免 gyx 也会因生活琐事而没法静心学习，所以某些天 gyx 对 OI 的兴趣程度有可能是负的。

然后，gyx 开始安排学习 OI 的时间，gyx 统计出他要学习的OI 知识有 $k$ 种。因为 gyx 是一个追求完美的人，他认为对于每一种 OI 知识，知识体系的完整性是必要的，某一个部分的 OI 知识学习过程中一旦停下来会影响自己的学习效果，所以他会用连续的一些天来学习一个部分的知识，期间不能停下来学习文化课，也不会穿插着进行几种知识的学习。

但是注意，gyx 在进行每部分 OI 知识的学习之间可以留出一些时间段用来学文化课。并且，gyx 并不介意各个部分 OI 知识间学习的顺序，因为他对每一部分的 OI 知识兴趣程度是相同的。

现在，gyx 想知道他总共用于学 OI 的日子兴趣值之和是多少，因为 gyx 还没有学习过高级的规划算法，所以 gyx 将他学习计划的规划交给你，你可以选择任意一个小于等于 $n$ 的一个正整数 $i$，使他从第 $i$ 天开始，进行长 $n$ 天的学习（不一定一开始就必须学 OI），但在这一年中他一定要把清单中所有的知识都学完，gyx 相信你一定能给出兴趣值之和最高的方法。

inputFormat:
两个正整数 $n,k$，分别代表 gyx 眼中一年有 $n$ 天，gyx 要学习的知识有 $k$ 种。

接下来一行有 $n$ 个整数，第 $i$ 个数 $a_i$ 代表 gyx 第 $i$ 天对 OI 的兴趣程度。

outputFormat: 输出一个整数，代表他总共学 OI 的所有日子兴趣值之和最大是多少。

hint:
### 样例解释

从第 $3$ 个时间段开始学习，那么他学 OI 的这一年兴趣程度的序列便为：

- $[3,-1,2,3,2,-4]$。

用于学习两个知识的时间段分别是新序列的第 $1$ 个和第 $3,4,5$ 个，于是 $ans=3+(2+3+2)=10$。

### 数据范围

- 对于 $10\%$ 的数据，满足 $k=1$；
- 对于另 $30\%$ 的数据，满足 $k=2$；
- 对于$100\%$ 的数据，满足：$1\le k\le50$，$k\le n\le10^5$，$|a_i|\le 10^4$。


title: [ZJOI2011] 道馆之战

description:
口袋妖怪（又名神奇宝贝或宠物小精灵）红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。

三个冰地分别如下：

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

当走出第三个冰地之后，就可以与馆主进行道馆战了。馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了$n$个房间，任意两个房间之间均有且仅有一条路径相连，即这$n$个房间构成一个树状结构。每个房间分成了$A$和$B$两个区域，每一区域都是一个薄冰块或者障碍物。每次只能移动到相邻房间的同一类区域（即若你现在在这个房间的$A$区域，那么你只能移动到相邻房间的$A$区域）或这个房间的另一区域。现在挑战者从房间$u$出发，馆主在房间$v$，那么挑战者只能朝接近馆主所在房间的方向过去。一开始挑战者可以在房间$u$的任意一个冰块区域内。如果挑战者踩过的冰块数达到了最大值（即没有一种方案踩过的冰块数更多了），那么当挑战者走到最后一个冰块上时，他会被瞬间传送到馆主面前与馆主进行道馆战。自从馆主修改规则后已经经过了$m$天，每天要么是有一个挑战者来进行挑战，要么就是馆主将某个房间进行了修改。对于每个来的挑战者，你需要计算出他若要和馆主进行战斗需要经过的冰块数。

inputFormat:
第一行包含两个正整数$n$和$m$。

第$2$行到第$n$行，每行包含两个正整数$x$和$y$，表示一条连接房间$x$和房间$y$的边。房间编号为$1\cdots n$。

接下来$n$行，每行包含两个字符。第$n+k$行表示房间$k$的两个区域，第一个字符为$A$区域，第二个字符为$B$区域。其中“.”（ASCII码为46）表示是薄冰块，“#”（ASCII码为35）表示是障碍物。

最后的$m$行，每行一个操作：

$C$ $u$ $s$：将房间$u$里的两个区域修改为$s$。

$Q$ $u$ $v$：询问挑战者在房间$u$，馆主在房间$v$时，挑战者能与馆主进行挑战需要踩的冰块数。如果房间$u$的两个区域都是障碍物，那么输出$0$。

outputFormat: 包含若干行，每行一个整数。即对于输入中的每个询问，依次输出一个答案。


title: [Wind Festival] Energy Center

background:
$[Noon - 12:13$ $P.M.]$

$Curtis$ $Nishikino$看到大家为晚会准备地如此认真，~~可爱的~~她也做起了志愿者！

description:
$Curtis$ $Nishikino$来到了风筝节的能源中心，大家正在为晚会做准备. 这里共有 $N$ 台设备. 当然，由于计划的调整，可能会随时发生增删设备的操作. 但设备的总数不会超过$10^4$. 随时记录设备的数量也是志愿者的工作之一.

每台设备都有一些属性，比如设备$i$, 对于她拥有的每个属性, 比如属性$j$, 都会有一个给定的值, 记为$value_{ij}$.但属性是共有的, 这意味着即便一台设备没有某个属性, 也只会使她这个属性的值为$0$. 属性的数量是$M$. 注意属性的编号是从$0$到$M-1$.

现在志愿者们正尝试将一部分相邻设备联系在一起，效果如下：

- 对于从$j$到$k$的设备, 最终效果$i$的值为 $\sum_{p=j}^{k}value_{pi}$.

志愿者需要$Curtis$帮忙，但做计算太麻烦了，$Curtis$ $Nishikino$也希望你能帮帮她.

inputFormat:
第一行两个整数 $n$ 和 $m$.

接下来 $n$ 行, 第一个整数 $k_i$,这意味着设备 $i$ 有 $k_i$ 个属性. 后面是 $2\times k$ 个整数, $x_j$ 和 $y_j$, 这意味着 $value_{ix_j}=y_j$.

下面是一个整数 $q$, 即 $q$ 个操作. 每项操作都是如下之一:

$I$ $x$ :在设备 $x$ 后插入一台设备, 下面有一行描述信息，像初始化一样.

$D$ $x$:丢弃第 $x$ 台设备.

$QA$ :询问设备总数.

$QS$ $l$ $r$: 询问连接设备 $l$ 到 $r$ 的效果.

输入数据保证合法.

outputFormat:
对于每个 $QA$, 输出一行一个整数.

对于每个 $QS$, 输出一行 $m$ 个整数, 如果属性 $i$ 的值是 $0$, 在那个位置输出 $0$ 即可.

###### 注意！

请在完成所有操作后输出一行额外的 "end" (不包含双引号).


title: [FJWC2018] 全排列

description:
定义两个长为 $n$ 的排列 $A$ 与 $B$ 相似：若 $\forall i$，满足 $C(A, A_i) = C(B, B_i)$。其中 $C(P, x)$ 为满足 $P_j < x$ $(1 \leqslant j \leqslant n)$ 的 $j$ 的数目。

对于两个长为 $n$ 的排列 $P_1, P_2$，定义函数 $F(P_1, P_2)$ 等于满足 $P_1[l \ldots r]$ 相似于 $P_2[l \ldots r]$ $(1 \leqslant l \leqslant r \leqslant n)$ 并且 $P_1[l \ldots r]$ 包含不超过 $E$ 个逆序对的数对 $(l, r)$ 的数目。

现在请你求出：对 $P_1, P_2$ 分别取遍所有 $1 \sim n$ 的排列后所有 $F(P_1, P_2)$ 的和。

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

接下来 $T$ 行，每行包含两个非负整数 $n, E$。

outputFormat: 对于每组数据，输出一行一个整数表示答案模 $10^9 + 7$。

hint:
对于 $50\%$ 的数据，$T \leqslant 10^4, n \leqslant 10, E \leqslant 50$。

对于 $80\%$ 的数据，$T \leqslant 10^4, n \leqslant 50, E \leqslant 10^6$。

对于 $100\%$ 的数据，$T \leqslant 10^4, n \leqslant 500, E \leqslant 10^6$。


title: 【模板】三维凸包

description: 给出空间中 $n$ 个点，求凸包表面积。

inputFormat:
第一行一个整数 $n$，表示点数。

接下来 $n$ 行，每行三个实数 $x, y, z$ 描述坐标。

outputFormat: 输出凸包表面积，保留 $3$ 位小数。


title: [Ynoi2016] 掉进兔子洞

background:
5.632

我（或者是在读这篇文字的你）不属于这个世界

这是世界的界限

6.41

世界的意义必定存在于世界之外

世界中的一切事物如其所存在般而存在，如其所发生般而发生

世界之中不存在价值

——《逻辑哲学论》

我们的情人，不过是随便借个名字，用幻想吹出来的肥皂泡

把信拿去吧，你可以使假戏成真

我本来是无病呻吟，漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了，你可以从信里看出来

拿去吧---由于不是出自真心，话就说得格外动听，拿去吧，就这么办吧...

![](https://cdn.luogu.com.cn/upload/pic/21091.png)

果然……好女人要有的是，烟、楼顶……还有轻飘飘的衣服呀……

某一天，水上由岐看见天上掉下了个布制玩偶

为了被天空接受而投掷出的她的布偶，不知在天空飞舞了多少次，已经遍体鳞伤

“被天空接受”——那是为了寻找不知何时开始在这个城市流传的“回归天空之路”的行为

![](https://cdn.luogu.com.cn/upload/pic/21102.png)

为了被天空接受而被扔出去的木偶，在空中飞舞并最终坠落

那是为了将其本身即为世界的少女送予天空的少女的行为

![](https://cdn.luogu.com.cn/upload/pic/21093.png)

横跨银河，被称作Vega与Altair，或是织女星与牛郎星的两颗星星，再加上北十字星之顶的天鹅座构成了夏之大三角

它被称作譬如三位一体的神圣的图形

只有神圣的图形在天空闪耀之时，世界才与天空相遇

![](https://cdn.luogu.com.cn/upload/pic/21094.png)

我想试一试，第一次，也是最后一次的恶作剧

![](https://cdn.luogu.com.cn/upload/pic/21095.png)

那是...什么？

什么事也没有哦，只是，间宫君他自己主动跳下去了而已哦~

怎么回事？

什么事也没有哦，只是，间宫君他自己主动跳下去了而已哦~

但是我看到了，是那个杀死了大家吗？

什么事也没有哦，只是，间宫君他自己主动跳下去了而已哦~

不，那个东西，什么都没有做，只是...

什么事也没有哦，只是，间宫君他自己主动跳下去了而已哦~

只是...怎么回事...

什么事也没有哦，只是，间宫君他自己主动跳下去了而已哦~

我确实听到了头盖骨破碎的声音

但是那个，并非是外面的世界

而是总自己的里面传来的

![](https://cdn.luogu.com.cn/upload/pic/21096.png)

水上同学...我偶尔会思考这种事情...

世界的极限到底在哪里呢...

世界的...世界的尽头的更尽头...

要是能有那种地方...

要是假如我能够站在那个地方的话...我还是能跟平时一样看着那个尽头的风景吗？我有这种想法....

我理所当然的想着这种事...然后决定似乎是有些奇怪啊

因为那里是世界的尽头哦

是世界的极限哦

如果我能够看到那个的话...世界的极限...是否就等同于我的极限呢？

因为，从那里看到的世界...我所看见的...不就是我的世界吗？

世界的极限...就会变成我的极限吧~

世界就是我看到的摸到的，并且感受到的东西

那样的话，世界到底是什么呢

世界和我到底有什么不同呢...我有这种想法

有吗？

世界和我的差别

是一样的

但是，或许其他人也有相同的感觉...

就连你，或许也认为世界就是你自己吧

并且，我觉得那个大概是正确的...

虽然我不太清楚...大概是你也站在世界的尽头，跟我一样在看着它吧

所以，你也和世界一样

但是啊，那样果然很奇怪啊...

如果世界就是我的话...为什么我会看不到你看到的世界呢？

明明我的世界里有你存在...却看不到你看到的世界

我从来没有看到过你看到的世界

那个，简直就像是两者不会交集的平行宇宙一样...

即使有现象暗示着那个东西存在...却是绝对的无法触碰...

我...看不到你所在的世界...

但是...

那个也是真的是真的吗？

我真的没有看到过你的世界吗...

既然所有的人都平等的拥有她们自己的世界的话

那么为什么世界会变成一个呢？

为什么那么多的世界会存在于这里呢？

世界变成一个的理由

...我偶尔会思考这种事情

所以...我才能够喜欢上你

description:
您正在打 galgame，然后突然发现您今天太颓了，于是想写个数据结构题练练手：

一个长为 $n$ 的序列 $a$。

有 $m$ 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。

注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，比如三个区间是  $[1,2,2,3,3,3,3]$，$[1,2,2,3,3,3,3]$ 与 $[1,1,2,3,3]$，就一起扔掉了 $1$ 个 $1$，$1$ 个 $2$，$2$ 个 $3$。

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

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

之后 $m$ 行，每行 $6$ 个整数 $l_1,r_1,l_2,r_2,l_3,r_3$ 表示这三个区间。

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

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

$1\leq n , m \leq 10^5$，$1 \leq a_i\leq 10^9$，$1\leq l_1,r_1,l_2,r_2,l_3,r_3\leq n$，$l_1\leq r_1$，$l_2\leq r_2$，$l_3\leq r_3$。


title: [Ynoi2016] 这是我自己的发明

background:
一切伟大的世界历史事件与人物，可以说都会出现两次

第一次是作为悲剧出现

第二次，则是作为笑剧出现

——《路易.波拿巴的雾月十八日》

感动、

痛苦、

以及快乐、

都只是遥不可及的宝石

即便如此，人们啊，

获得幸福吧！

![](https://cdn.luogu.com.cn/upload/pic/21098.png)

世界将在7月20日终结

世界回归天空的日子

万物被天空侵染的日子

回归天空的日子

世界必须回归

世界的极限

世界的尽头

世界的终结

![](https://cdn.luogu.com.cn/upload/pic/21099.png)

你看…那就是极限…最尽头的天空

如今，已无应该之事了如今，已无忘却之物了

不需要的话语

![](https://cdn.luogu.com.cn/upload/pic/21100.png)

告别了永不相交的平行，我被吸进了…

垂直下落的世界

![](https://cdn.luogu.com.cn/upload/pic/21101.png)

虽哭亦喜

虽悲亦喜

各种感情混在一起...

比起其他所有，想必还是高兴占多吧

她高兴地抱着我

紧紧地抱着

再也不会松开了...

想永远这样...

她的思绪，以比语言更快的速度，传达给了我

有些东西，比语言更快

她的思绪，以比语言更快的速度，传达给了我

有些东西，比语音更准确

世界上无论多么短暂的瞬间，都有意义

有意义

块临近终结了

最后的瞬间

啊啊...

远方的警笛声

黑色的天空

月正笑

地正润潮

星正舞

风正凉

在我怀中，温暖的，

橘希实香

![](https://cdn.luogu.com.cn/upload/pic/21103.png)

她在我的怀中...静静地合上了双眼

然后我也...

静静地合上了双眼

description:
您正在打 galgame，然后突然家长进来了，于是您假装在写数据结构题：

给一个树，$n$ 个点，有点权，初始根是 1。

$m$ 个操作，种类如下：

`1 x` 将树根换为 $x$。

`2 x y` 给出两个点 $x,y$，从 $x$ 的子树中选每一个点，$y$ 的子树中选每一个点，求点权相等的情况数。

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

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

之后 $n-1$ 行 , 每行两个数 $x,y$ , 表示一条边。

之后 $m$ 行，每行表示一个操作。

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

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

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^5$，$1 \le m \le 5\times 10^5$ , $1 \le a_i \le 10^9$。


title: [Ynoi2016] 镜中的昆虫

background:
镜子的世界里会有美丽的东西吗？

镜子的世界里会有快乐的事情吗？

镜子世界的我，像我一样摆着一副无聊的表情

——出自《镜之国的爱丽丝》

![](https://cdn.luogu.com.cn/upload/pic/21104.png)

两个少女的战斗故事

文学代表强烈的意志，化学是对抗物理世界的力量

她们只有这两样对抗现实的武器

![](https://cdn.luogu.com.cn/upload/pic/21105.png)

啊，勒布雷！

我今天要登上乳白色的月球了！

不需要发明是机器，真是如此，我要一跃而出！

没错朋友！那个月亮的世界！

才是为我们创造的世界！

不止一个我所爱的人，大概都被放逐到那里...然后在等着我...

苏格拉底！伽利略！

物质的基本要素的灵魂就是...

这是...不，这有问题...哥白尼说过！

没错朋友们，究竟为何，会中了魔障？

究竟为何，会中了魔障，他到底去双桅战船上干什么呢？

作为哲学家！

物理学家！

诗人！

剑客！

音乐家！

空中旅行家！

针尖对麦芒的辩士！

他无所不能

作为至高...但是...

却又一事无成...

...没错，你们这些家伙，想夺走我的一切！

...来，夺走吧，夺走就是了...

但是...无论你们再怎么叫嚷，在去往新世界的路上，我还是会带走一个！

让我看看你坚强的心吧！

没错，你帽子上的羽饰！

象征你内心的勇气的纹章...毛子上的羽饰！

对不起，我该走了，我不能让人久等！

你们看...月亮来迎接我了！

Mon panache！

![](https://cdn.luogu.com.cn/upload/pic/21106.png)

我往空中踏出一步

两人拼命地想要拉住我

但是我往空中踏出一步

没错

我要为了崭新的世界，从天而降

为了获得新的力量

为了新的真实

我踏出了这一步

从手上，感到了两人的颤抖

没关系...

我在你们身边！

Sora！

![](https://cdn.luogu.com.cn/upload/pic/21109.png)

我完全投身于空中

我的身体瞬间从空中向地面落去

我紧紧地握住两人手腕，拉着两人

看见两人的表情...

她们边哭边笑...

似乎很害怕...

却又似很高兴的表情...

啊...

什么嘛，飞翔好舒服啊

宛如变成了天使一般...

好快的速度...

好快的风...

但是却听不见声音...

世界在静静地回转

已经，马上就要到地面了...

空气力学的先驱者...

我知道一切都在回转的天空，

还有包容着我的大地

还差一点，就抵达世界了...

还差一点，就抵达地面了...

接近着的影子

地面映出我的身影

description:
您正在欣赏 galgame 的 HS，然后游戏崩溃了，于是您只能做数据结构题了：

维护一个长为 $n$ 的序列 $a_i$，有 $m$ 次操作。

1. 将区间 $[l,r]$ 的值修改为 $x$。

2. 询问区间 $[l,r]$ 出现了多少种不同的数，也就是说同一个数出现多次只算一个。

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

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

后面 $m$ 行每行为 $1\ l\ r\ x$ 或者 $2\ l\ r$ ，分别表示修改和询问。

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

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

$1\leq n , m \leq 10^5$，$1\leq a_i\leq 10^9$。


title: Nagisa loves Tomoya

description:
可爱的古河渚得到了一个序列。她定义一次操作为 将所有的 $a_i$ 变为 $a_i+a_{(i\ mod \ n+1)}$
然后她会向你进行 $Q$ 次询问，每次问你 $x,y$ ,意义为在第 $x$ 次操作后位置 $y $ 的元素是多少。

这个问题太简单了，我们的 Nagisa 轻易地就解决了这个问题。请问您能解决这个问题吗？

inputFormat:
一个整数 $n$，表示序列的长度。

接下来一行 $n$ 个整数，表示这个序列。

接下来一行一个整数 $Q$，表示询问次数

接下来 $Q$ 行，每行两个整数 $x,y$，意义如题所示。

outputFormat: 共 $Q$ 行，每行一个整数表示询问的答案，请注意对 $998244353$ 取模。


title: [QkOI#R1] Quark and Flying Pigs

description:
给定一个 $n$ 个点 $m$ 条边的边带权简单连通无向图，在 $0$ 时刻你在点 $1$ 上。

假设当前是 $t$ 时刻，你在点 $v$ 上，你可以选择两种操作：

- 仍停留在点 $v$ 上，操作后到 $t+1$ 时刻。
- 选择一条边 $(a,b,w)$ 满足 $a=v$ 或 $b=v$，则你到这条边连接的另一个点上，操作后到 $t+w$ 时刻。

有 $k$ 条信息，每一条信息形如 $(t_i,v_i)$ 表示在 $t_i$ 时刻，点 $v_i$ 上会出现一只飞猪，其编号为 $i$，若该时刻你在 $v_i$ 上，则你捕获到了 $i$ 号飞猪。

现在你需要求出你能捕获到的飞猪数量的最大值。

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

接下来 $m$ 行每行三个正整数 $a_i,b_i,w_i$。

接下来 $k$ 行每行两个正整数 $t_i,v_i$。

outputFormat: 一行一个整数，为你能捕获到的飞猪数量的最大值。

hint:
### 样例解释

最优方案如下：

$0$ 时刻，选择移动到节点 $2$，时间来到 $2$ 时刻。
$2$ 时刻，捕获到第 $2$ 只飞猪，选择停留在节点 $2$，时间来到 $3$ 时刻。
$3$ 时刻，捕获到第 $3$ 只飞猪，选择移动到节点 $1$，时间来到 $5$ 时刻。
$5$ 时刻，捕获到第 $4$ 只飞猪，选择移动到节点 $2$，时间来到 $7$ 时刻。
$7$ 时刻，捕获到第 $5$ 只飞猪。

### 数据范围

对于 $20\%$ 的数据，$n,m,k\le 7$。
对于 $100\%$ 的数据，$2\le n\le 200$，$1\le m\le \frac{n(n-1)}{2}$，$1\le k\le 5000$，$1\le a_i,b_i,v_i\le n$，$1\le w_i\le 1000$，$1\le t_i\le 10^9$。


title: [Ynoi2016] 谁的梦

background:
6.373

世界是独立于我的意志的。

6.374

就算我们所期望的全部的事情都发生了

这果然也只能说是命运的恩惠吧。

要问为什么，那是因为意志和世界之间

能够保证这件事的逻辑性的关联并不存在

Ludwig Josef Johann Wittgenstein [逻辑哲学论]

自从双胞胎的哥哥过世起，已经过了多久了呢…

从那时起，我一直保存着那个布偶。

在那以后的我只是个影子…而这个布偶才是我…

这样也并没有什么不好。

我觉得只要现在的我消失掉就行了…

那两个人却救了这样的我。

一个是由歧姐…

她又来到了我的身边…

带着皆守哥…回到了我们的身边…

水上由岐姐姐…温柔的姐姐

曾经非常喜欢皆守哥的人……

![](https://cdn.luogu.com.cn/upload/pic/21195.png)

回去的路上…

平时不会经过的坡道…

在登上那个坡道的途中…

我看到了夜晚的太阳。

明明就在附近，却一直不知道的巨大的向日葵。

夜露使它的绒毛泛出了白光。

碧蓝的月光和黄色的向日葵…

就好像太阳和月亮的立场反过来一样…

原本是那么耀眼的的太阳在地上，只能在其背后下发光的月亮在天上…

黄色的向日葵被染成了碧蓝色。

那副样子虽然很美丽…

努力绽放的向日葵，看起来反而是柔弱的存在。

在夜里向天空伸展的向日葵…

我在车内一直追寻着它的身影…

被夜晚的月光映照着的太阳。

被染成碧蓝色的太阳…

它的身影…我一直追寻着……

![](https://cdn.luogu.com.cn/upload/pic/21196.png)

被月光照亮的天台上…

一个人影…

明明只是一个人影…却好像…在和什么东西对峙着一样…

皆守哥…

月下的立像，一个人影。

胸口在风中闪烁。

放在胸前的手里的是…那时的小刀。

和七年前同样的姿势。

唯一不同的是，那里的人影只有一个。

那把小刀，好像是被他自己刺入体内。

![](https://cdn.luogu.com.cn/upload/pic/21197.png)

是诅咒…

这是理所当然的事…

那并不是什么精神病…

那是诅咒…

下在幸存的我们身上的…诅咒…

说不定，不仅仅是卓司哥…连由岐姐也在诅咒我们…

所以变成这种结果…

哥哥刺向了自己的胸口…

破坏了我的半身…

然后…还要把很多人送回到天空…

回归天空的日子。

交还灵魂的日子。

那一天，卓司哥对我做的事情。

杀了由岐姐的…那个行为…

他想要再一次实行…

这次…和很多人一起…

![](https://cdn.luogu.com.cn/upload/pic/21198.png)

不是…

那是…我啊…

是那个…坡道的事情啊…

两个人一起看到向日葵的…那个坡道…

…我说要爬上那个坡道…要去寻找爸爸的灵魂…

我想，如果到了那个坡道的前方，就能取回爸爸的灵魂…爸爸就会复生的…

如果越过向日葵之路…向着向日葵所朝向的天空延伸的…那个大大的坡道的话…
大概，就会有爸爸的灵魂…

爸爸的故乡的…大大的坡道…

![](https://cdn.luogu.com.cn/upload/pic/21199.png)

哥哥的身体浮在空中…

我无言地跳了出去。

啊啊…是这样啊…

由岐姐也是这种心情啊…

并没有什么道理可言…

只是因为喜欢的人向着天空跳下去了…

我想要抓住那个身体…

我——

description:
您正在打 galgame，突然断电了，于是您跑去物管处问，结果发现是由于一个光头踢了变压器一脚导致的，可能还要修很久，于是您决定想一个之前见过的数据结构题：

定义一个序列的权值为不同数字的个数，例如 $[1,2,3,3]$  权值为 $3$。

现在有 $n$ 个序列，我们在每个序列里面选一个连续非空子串，拼接起来，求所有选法得到的序列的权值之和。

如果一个序列能通过多种方法被选择出来，那么计算多次。

本题带修改操作，格式请参考输入格式。

由于结果可能过大，请输出答案 $\bmod 19260817$ 的结果。

inputFormat:
第一行两个整数 $n,m$，表示有 $n$ 个序列，$m$ 次修改。

第二行 $n$ 个整数，第 $i$ 个数是 $len_i$，表示第 $i$ 个序列的长度。

之后 $n$ 行，每行 $len_i$ 个整数，表示第 $i$ 个序列。

之后 $m$ 行，每行三个整数 $x,y,z$ 表示将第 $x$ 个序列的第 $y$ 个元素改为 $z$。

outputFormat: 输出 $m + 1$ 行，每行一个整数，依次表示初始局面以及每次修改后的答案。

hint:
Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477( partially uploaded )

$1 \leq n,m,len_i \leq 10^5$，序列中的元素均为 $32$ 位整型数，$\sum len_i \leq 10^5$。

共 $50$ 组数据。


title: [Ynoi2016] 炸脖龙 II

background:
瞬间…

真要说的话，比瞬间还要短暂。

羽咲往悬崖的方向飞去。

瘦小的羽咲，比想象中更轻易地飞侠了悬崖。

我急忙跑向悬崖边。

然而，飞奔而出之后，方向并不是那么容易改变。

我失去了平衡，就这么摔倒在地。

只能一直用目光追寻着羽咲的身影。

飞出悬崖的羽咲。

身体浮在半空中。

在下一瞬间，便听任自由落体定律…径直坠下陡峭的悬崖

![](https://cdn.luogu.com.cn/upload/pic/21200.png)

细长的双眼…注视着我的眼睛。

这是幻觉吗…还是现实…

卓司的指尖捅破了头盖骨…

这根本不可能的吧…人的手劲如何能够捏破头盖骨…

这毫无疑问是幻觉…不可能存在于现实中…

这种事，习武的我是最清楚不过的…

这种根本不可能的事…

尽管如此…

我的意识仍朦胧起来…

已经无法与这个世界保持联系了…

“我…收下皆守哥哥的身体了哦…”

![](https://cdn.luogu.com.cn/upload/pic/21201.png)

司空见惯的风景。

比之前看到的风景更让人眼熟。

我所熟悉的风景…

![](https://cdn.luogu.com.cn/upload/pic/21202.png)

“我会把他带走的…所以你走吧…”

“卓司…那个电波小子，就让我把他带走…”

“所以你就前进吧…”

“在无法登上的坡道的尽头”

“你不能停滞不前，必须前去迎接小羽”

“好啦，打起精神来…皆守”

“在这里告别吧…”

![](https://cdn.luogu.com.cn/upload/pic/21203.png)

轻飘飘的感觉。

瞬间，感觉到了周围空气的急速变冷。

扬起的灰尘伴随月光的照耀，在空中废物。

告别了永不相交的平行，我和羽咲被吸进了…

垂直下落的世界。

月光映照出羽咲身体的轮廓。

地面没有影子。

宛如高空飞翔一般…

远方传来警笛声。

在苍穹之下反复回想。

我仰望无限的天空，笔直坠下。

一刻也不远看丢，在我上方的羽咲…

月在笑。

神在笑。

笑这滑稽的姿势。

笑这喜剧般的悲剧。

群星旋转。

如舞如蹈。

夜空上的神，正嘲弄着我们。

就想把空瓶子扔在地上的天真的孩子一样…

世界变得一片空虚。

![](https://cdn.luogu.com.cn/upload/pic/21204.png)

望不到尽头的坡道…

遥远而模糊的坡道…

宛如…我们就漫步在这样的世界中一般…

就算在意坡道的前方也毫无用处。

我们就在这坡道上快乐地走着。

![](https://cdn.luogu.com.cn/upload/pic/21205.png)

description:
您在打galgame，突然听说苏联解体了，于是您发现您永远看不到一个活着的苏联人了，很郁闷，于是开始写一道数据结构题：

这是一道模(du)拟(liu)题。

你需要维护一棵包含 $n$ 个结点有根有序树（也就是说每个点的孩子是有“从左到右”的顺序的），初始根为 $1$，支持以下几个操作：

`A(x,y)`：对 $x$ 进行路径压缩，即将 $x$ 到根路径上除了根之外的点的父亲设为根，这些点在根的孩子中的顺序保持原先路径上从浅到深的顺序。

`B(x,y)`：将根的孩子 $x,y$（$x$ 在 $y$ 左边）以及之间的点按顺序展开成一条路径，$x$ 仍与根相连，涉及到的点原先的孩子都移至路径右侧。

`C(x,y)`：将树的根设为 $x$，此时原先在根到 $x$ 路径左侧的点仍在左侧且先相对顺序不变，右侧同理，$x$ 的孩子在 $x$ 成为根后在 $x$ 到原先的根的路径的右侧。

`D(x,y)`：给 $x$ 到根的路径上每个点的点权同时加一个数，并在这之后求 $x$ 到根的路径上的点权和。

`E(x,y)`：保证 $x$ 和 $y$ 父亲相同且 $x$ 在 $y$ 左侧，对在 $x$ 的父亲的孩子中，$x$ 到 $y$ 之间（含 $x,y$）的每个点的点权加上 $x+y$，并在这之后求这些点的点权和。

`F(x,y)`：给 $x$ 添加一个孩子 $y$，在最右边，这个操作在其它所有操作之前进行，用于描述树的初始形态。

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

接下来 $q$ 行，每行表示一个操作。

outputFormat: 对每个 `D` 或 `E` 操作，输出一行，表示答案对 $2^{32}$ 取模的结果。

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

$2\leq n\leq 10^5$，$n\leq q\leq 2\times 10^5$，$0\leq x,y \leq n$。

保证操作合法。

为了对称，所有操作都有两个参数 $x,y$，但实际上 `A`，`C` 操作中不需用到 $y$，数据保证此时 $y=0$。

前 $n-1$ 个操作一定是 `F` 操作，保证 $n-1$ 次操作后得到一棵以 $1$ 为根的树，且以后不会再出现 `F` 操作。

注意到 `A`，`B`，`C`，`F` 操作都有关于孩子顺序的规定，可以参照样例解释进行直观的理解。

共 $10$ 组数据。


title: [PA2013] Raper

description:
你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。

你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间，每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。

求生产出 $k$ 张光盘的最小花费。

inputFormat:
第一行包含两个整数 $n, k$，表示有 $n$ 天，要生产 $k$ 张光盘。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天送到 A 工厂加工光盘的花费。

第三行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天送到 B 工厂加工光盘的花费。

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

hint:
保证 $1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ $1 \leqslant  a_i, b_i \leqslant 10^9$。

注：添加了 2 组 Hack 数据，如未通过将扣除 3 分。


title: [CEOI2011] Matching

description:
对于整数序列 $(a_1,a_2,\cdots,a_n)$ 和 $1\sim n$ 的排列 $(p_1,p_2,\cdots,p_n)$，称 $(a_1,a_2,\cdots,a_n)$ 符合 $(p_1,p_2,\cdots,p_n)$，当且仅当：

-    $\{a\}$ 中任意两个数字互不相同；

-    将 $(a_1,a_2,\cdots,a_n)$ 从小到大排序后，将会得到 $(a_{p_1},a_{p_2},\cdots,a_{p_n})$。

现在给出 $1\sim n$ 的排列 $\{p\}$ 和序列 $h_1,h_2,\cdots,h_m$，请你求出哪些 $\{h\}$ 的子串符合排列 $\{p\}$。

inputFormat:
第一行两个空格隔开的正整数 $n,m$。

第二行 $n$ 个空格隔开的正整数，表示排列 $p$。

第三行 $m$ 个空格隔开的正整数，表示序列 $h$。

outputFormat:
第一行一个整数 $k$，表示符合 $\{p\}$ 的子串个数。

第二行 $k$ 个空格隔开的正整数，表示这些子串的起始位置（编号从 $1$ 开始）。请将这些位置按照从小到大的顺序输出。特别地，若 $k=0$，那么你也应当输出一个空行。

hint: 对于 $100\%$ 的数据，有 $2\le n\le m\le 1\ 000\ 000;1\le h_i\le 10^9;1\le p_i\le n$，保证 $\{h\}$ 中的元素互不相同，且 $\{p\}$ 是一个排列。


title: [CEOI2011] Balloons

description:
有 $n$ 个气球，他们一开始都是空的。

接下来，它们会按照从 $1$ 到 $n$ 的顺序依次充气，其中第 $i$ 个气球与地面在 $x_i$ 位置接触。

当气球碰到碰到前面的某个气球，或者达到半径最大限制时，就会停止充气。其中第 $i$ 个气球的半径最大限制为 $r_i$。

现在请你求出，每个气球最终半径是多少。

inputFormat:
第一行一个正整数 $n$，表示气球个数。

接下来 $n$ 行，每行两个空格隔开的整数 $x_i,r_i$。

outputFormat:
输出 $n$ 行，每行一个浮点数，第 $i$ 行的浮点数表示最终第 $i$ 个气球的半径。

你的答案会被判为正确，当且仅当与答案的绝对误差不超过 $10^{-3}$。


title: [CEOI2011] Hotel

description:
你经营着一家旅馆，这家旅馆有 $n$ 个房间，每个房间有维护费用和容量。其中第 $i$ 个房间的维护费用为 $c_i$，容量为 $p_i$ 人。

现在有 $m$ 个订单，每个订单有两个参数：$v_i,d_i$ ，其中 $v_i$ 表示这个订单支付的租金，$d_i$ 表示人数。

你现在得要合理选择一些订单，并放弃其他订单，使得每个选择的订单被安排在同一间房间内，且人数不超过这个房间的容量限制。当然，两个不同的订单也不能被安排在同一间房间内。

现在你想要知道，在最多选出 $o$ 个订单时的最大收益。一个方案的收益的定义为，选出的订单的租金和，减去选出的房间的维护费用和。

inputFormat:
第一行三个空格隔开的整数 $n,m,o$ 。

接下来 $n$ 行，每行两个空格隔开的整数 $c_i,p_i$。

接下来 $m$ 行，每行两个空格隔开的整数 $v_i,d_i$。

outputFormat: 一行一个整数表示最大收益。注意答案可能很大。

hint:
**样例 $1$ 解释**

可以将第一个订单安排至第三个房间，将第二个订单安排至第二个房间。

**数据范围**

对于 $100\%$ 的数据，有 $1\le n,m\le 500\ 000;1\le o\le \min(n,m);1\le c_i,p_i,v_i,d_i\le 10^9$，保证 $\forall 1\le i,j\le n$，若 $p_i\lt p_j$，则 $c_i\le c_j$。


title: [CEOI2011] Teams

description:
有 $n$ 个小朋友要进行比赛，他们要被分为若干队伍。每一个小朋友都有一个要求，其中第 $i$ 个小朋友要求他所在的队伍最少要有 $a_i$ 个人（包括自己）。

现在请你求出一种划分方案，在满足所有小朋友的要求的情况下，最大化队伍的数量。同时在此基础上，请你最小化人数最多的队伍的人数。

inputFormat:
第一行一个数 $n$ 表示小朋友的个数。

接下来 $n$ 行，每行一个数，其中第 $i$ 行的数字为 $a_i$ 。

outputFormat:
第一行一个数 $t$ ，表示在你的方案中的队伍数量。

接下来 $t$ 行，每行若干个空格隔开的数字，表示一只队伍。每一行首先输出一个数 $k_i$ 表示第 $i$ 只队伍的人数，接下来 $k_i$ 个数依次描述该队伍内的小朋友的编号（从 $1$ 开始）。

若有多解（在满足题目要求的情况下），输出任意一个即可。

hint: 对于 $100\%$ 的数据，有 $1\le n\le 1\ 000\ 000;1\le a_i\le n$，输入保证有解。


title: [CEOI2011] Traffic

description:
在平面直角坐标系上有 $n$ 个点，其中第 $i$ 个点的坐标是 $(x_i,y_i)$ ，所有点在一个以 $(0,0)$ 和 $(A,B)$ 为相对顶点的矩形内。

如果 $x_i=0$ ，那么我们称这个点在西侧。如果 $x_i=A$ ，那么我们称这个点在东侧。

这些点之间有 $m$ 条边，每条边可能是有向边也可能是无向边，保证边在交点以外的任何地方不相交。

现在请你求出，对于每一个西侧的点，能够沿着边到达多少东侧的点。

inputFormat:
第一行四个空格隔开的数 $n,m,A,B$ 。

接下来 $n$ 行，每行两个空格隔开的数 $x_i,y_i$ 。

接下来 $m$ 行，每行三个空格隔开的数 $c_i,d_i,k_i$ ，表示一条 $c_i$ 和 $d_i$ 之间的边。如果 $k_i=1$ ，那么表示这条边是有向边，方向为 $c_i$ 指向 $d_i$ ，否则这条边是无向边。

outputFormat: 输出有若干行，每行一个数表示答案。请按照 $y$ 从大到小的顺序输出所有点对应的答案。


title: 好编号

description:
给定参数 $ N $、$ K $。一个编号 $ A $ 被称为好编号，当且仅当对于任意的 $ i \in \{ 1, 2, \cdots, N-1 \} $，均满足：$ \dfrac{A}{K^i} - \left\lfloor \dfrac{A}{K^i} \right\rfloor > \dfrac{A}{K^N} $。

求好编号的个数模 $ 10^9+7 $ 的值。

inputFormat: 一行两个正整数 $N,K$。

outputFormat: 一行，好编号个数模 $10 ^ 9 + 7$ 的值。


title: 【模板】最小树形图

background: 这是一道模板题。

description: 给定包含 $n$ 个结点， $m$ 条有向边的一个图。试求一棵以结点 $r$ 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 $r$ 为根的最小树形图，输出 $-1$。

inputFormat:
第一行包含三个整数 $n,m,r$，意义同题目所述。

接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示图中存在一条从 $u$ 指向 $v$ 的权值为 $w$ 的有向边。

outputFormat: 如果原图中存在以 $r$ 为根的最小树形图，就输出最小树形图每条边的权值之和，否则输出 $-1$。

hint:
**样例 $1$ 解释**

最小树形图中包含第 $2$， $5$， $6$ 三条边，总权值为 $1 + 1 + 1 = 3$

**样例 $2$ 解释**

最小树形图中包含第 $3$， $5$， $6$ 三条边，总权值为 $2 + 1 + 1 = 4$

**样例 $3$ 解释**

无法构成最小树形图，故输出 $-1$ 。

**数据范围**

对于所有数据，$1 \leq u, v \leq n \leq 100$, $1 \leq m \leq 10^4$, $1 \leq w \leq 10^6$。


title: [Cnoi2019] 数学课

description:
聪明的 Cirno 开始学习计算，于是她很开心的算出了从 $1$ 一直加到 $n$。

得到了一个 $n$ 项的数列 : $ \{ a_n$ = $1 + 2 + 3 + 4 + ... + n \} $

为了验证自己算是否算错，她需要以某种规律从数列里取出两个元素 $v_1, v_2$（元素可以相同），并等概率的选出整数 $a \in [ 1,v_1 ]$，$b \in [ 1,v_2 ]$ 判断哪个比较大.

所以她需要你来计算 $a>b$ 的概率。

某种规律：
选到数列第 $i$ 个元素的概率是：

$$\frac{a_i}{\sum\limits_{n=1}^n a_n}=\frac{3i\times(i+1)}{n(n+1)(n+2)}$$

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

outputFormat: 输出在模 $998244353$ 意义下的概率。


title: 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

description:
给定长度为 $2^n$ 两个序列 $A,B$，设

$$C_i=\sum_{j\oplus k = i}A_j \times B_k$$

分别当 $\oplus$ 是 or, and, xor 时求出 $C$。

inputFormat:
第一行，一个整数 $n$。
第二行，$2^n$ 个数 $A_0, A_1, \ldots, A_{2^n-1}$。
第三行，$2^n$ 个数 $B_0, B_1, \ldots, B_{2^n-1}$。

outputFormat: 三行，每行 $2^n$ 个数，分别代表 $\oplus$ 是 or, and, xor 时 $C_0, C_1, \ldots, C_{2^n-1}$ 的值 $\bmod\ 998244353$。

tags: 快速莫比乌斯变换 FMT


title: Added Sequence

description:
小$L$发明了一种新的数据结构，并将其命名为$L$数组。$L$数组的作用是可以在$O(1)$时间内将整个数组加上或减去一个数。现在给你一个长度为$N$的数组$a$，他想用$L$数组来挑战你的计算能力。

定义$f(i,j)=|\sum_{p=i}^{j} a_p|$其中$|x|$表示$x$的绝对值。

定义一个数组的美丽度为$\max_{1 \le i \le j \le N} f(i,j)$，每当他将整个数组加上$x$ ，请你回答此时的美丽度。

注意，你的算法必须为在线的。

inputFormat:
第一行输入两个整数$N,M$，分别表示数组长度和询问数量。

第二行输入$N$个整数，表示起始的数组$a$。

接下来$M$行，每行一个整数$x_i$，设前面一次回答的答案为$pre$，那么表示第$i$次询问时在起始数组的基础上整个数组加上$[(x_i+pre)\%(4n+1)-2n]$。其中$\%$表示求余运算，第一次回答时$pre=0$。

outputFormat: 输出$M$行，第$i$行为在起始数组的基础上整个数组加上$x_i$时的美丽度。


title: 【模板】Pollard-Rho

description:
Miller Rabin 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。

Pollard rho 是一个非常玄学的方式，用于在 $O(n^{1/4})$ 的期望时间复杂度内计算合数 $n$ 的某个非平凡因子。事实上算法导论给出的是 $O(\sqrt p)$，$p$ 是 $n$ 的某个最小因子，满足 $p$ 与 $n/p$ 互质。但是这些都是期望，未必符合实际。但事实上 Pollard rho 算法在实际环境中运行的相当不错。

这里我们要写一个程序，对于每个数字检验是否是质数，是质数就输出 `Prime`；如果不是质数，输出它最大的质因子是哪个。

inputFormat:
第一行，$T$ 代表数据组数（不大于 $350$）

以下 $T$ 行，每行一个整数 $n$，保证 $2 \le n \le {10}^{18}$。

outputFormat:
输出 $T$ 行。

对于每组测试数据输出结果。

hint:
2018.8.14 新加数据两组，时限加大到 2s，感谢 @whzzt

2022.12.22 加入新的数据，感谢 @ftt2333 和 Library Checker

by @will7101


title: 最大异或和

description:
给定一个非负整数序列 $\{a\}$，初始长度为 $N$。

有 $M$ 个操作，有以下两种操作类型：

1. `A x`：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $N$ 加 $1$。
2. `Q l r x`：询问操作，你需要找到一个位置 $p$，满足 $l \le p \le r$，使得：$a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x$ 最大，输出最大值。

inputFormat:
第一行包含两个整数 $N, M$，含义如问题描述所示。
第二行包含 $N$ 个非负整数，表示初始的序列 $A$。
接下来 $M$ 行，每行描述一个操作，格式如题面所述。

outputFormat: 假设询问操作有 $T$ 个，则输出应该有 $T$ 行，每行一个整数表示询问的答案。

hint: - 对于所有测试点，$1\le N,M \le 3\times 10 ^ 5$，$0\leq a_i\leq 10 ^ 7$。


title: [中山市选] 杀人游戏

description:
一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在$N$个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。

问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

inputFormat:
第一行有两个整数 $N,M$。
接下来有 $M$ 行，每行两个整数 $x,y$，表示 $x$ 认识 $y$（$y$ 不一定认识 $x$ ,例如President同志） 。

注：原文zz敏感内容已替换

outputFormat: 仅包含一行一个实数，保留小数点后面 $6$ 位，表示最大概率。

hint:
警察只需要查证$1$。假如$1$是杀手，警察就会被杀。假如$1$不是杀手，他会告诉警察$2,3,4,5$谁是杀手。而$1$是杀手的概率是$0.2$，所以能知道谁是杀手但没被杀的概率是$0.8$。

对于$100\%$的数据有$1≤N≤100000,0≤M≤300000$。


title: [USACO22DEC] Bribing Friends G

description:
Bessie 想要观看纪录片：奶牛基因组学，但她不想一个人去。不幸的是，她的朋友们没有足够的热情和她一起去！于是，Bessie 需要贿赂她的朋友们陪她去电影院。她的贿赂武器库中有两种工具：**哞尼**和**冰激凌甜筒**。

Bessie 有 $N(1 \le N \le 2000)$ 个朋友。然而，并非所有的朋友都是生而平等的！朋友 $i$ 有受欢迎度 $P_i(1 \le P_i \le 2000)$，Bessie 想最大化陪她的朋友们的受欢迎度之和。朋友 $i$ 只有当 Bessie 给了她 $C_i(1 \le C_i \le 2000)$ 哞尼才愿意陪她。如果 Bessie 给她 $X_i(1 \le X_i \le 2000)$ 个冰激凌甜筒，她还可以给 Bessie $1$ 哞尼的折扣。Bessie 可以从朋友那里得到任意整数数量的折扣，只要这些折扣不会使得朋友倒给她哞尼。

Bessie 有 $A$ 哞尼和 $B$ 个冰激凌甜筒可供使用（$0 \le A,B \le 2000$）。请帮助她求出如果她以最优方案花费她的哞尼和冰激凌甜筒，她可以达到的最大受欢迎度之和。

inputFormat:
输入的第 1 行包含三个整数 $N$，$A$ 和 $B$，分别表示 Bessie 拥有的朋友的数量，哞尼的数量和冰激凌甜筒的数量。

以下 $N$ 行每行包含三个整数 $P_i$，$C_i$ 和 $X_i$，表示受欢迎度（$P_i$），贿赂朋友 $i$ 陪 Bessie 所需要的哞尼（$C_i$），以及从朋友 $i$ 处获得 $1$ 哞尼的折扣所需要的冰激凌甜筒的数量（$X_i$）。

outputFormat: 输出陪 Bessie 的朋友们的最大受欢迎度之和，假设她以最优方案花费她的哞尼和冰激凌甜筒。

hint:
### 样例 1 解释

Bessie 可以将 $4$ 哞尼和 $4$ 个冰激凌甜筒给奶牛 $1$，将 $6$ 哞尼和 $3$ 个冰激凌甜筒给奶牛 $3$，这样奶牛 $1$ 和 $3$ 就可以陪她，得到 $5+10=15$ 的受欢迎度。

### 测试点性质

 - 测试点 $2-4$ 满足 $N \le 5$ 以及 $C_i=1$。
 - 测试点 $5-7$ 满足 $B=0$。
 - 测试点 $8-10$ 满足 $N,A,B,P_i,C_i,X_i \le 50$。
 - 测试点 $11-15$ 满足 $N,A,B,P_i,C_i,X_i \le 200$。
 - 测试点 $16-20$ 没有额外限制。


title: [USACO22DEC] Mountains G

description: 沿着 Farmer John 的农场边缘有 $N(1 \le N \le 2000)$ 座排成一行等间隔分布的山。这些山可以用一个高度数组 $h_1,h_2, \cdots ,h_N$ 表示。对于山 $i$，如果没有一座山严格高于连接山 $j$ 和 $i$ 山顶的视线，则可以看到山 $j$。形式化地说，对于两座山 $i<j$，如果不存在 $k$ 使得 $i<k<j$ 并且 $(k,h_k)$ 高于连接 $(i,h_i)$ 和 $(j,h_j)$ 的线段，则这两座山之间互相可以看到对方。给定 $Q(1 \le Q \le 2000)$ 次更新操作，每次更新增加一座山的高度。求每次更新后可以互相看到的山的无序对数。

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

第 $2$ 行包含 $N$ 个高度 $h_1,h_2,\cdots,h_N$（对每一个 $i$，有 $0 \le h_i \le 10^9$）。

第 $3$ 行包含 $Q$。

第 $4$ 到 $3+Q$ 行每行包含 $x,y(1 \le x \le N,1 \le y)$，其中 $x$ 为山的编号，$y$ 是山增加的高度。输入保证这座山更新后的高度不超过 $10^9$。

outputFormat: 输出 $Q$ 行，包含每次更新后可以互相看到的山的无序对数。

hint:
### 样例 1 解释

初始时，以下的山之间可以互相看到：$(1,2)$，$(2,3)$，$(2,5)$，$(3,4)$，$(3,5)$，$(4,5)$，共 $6$ 对。

第一次更新后，山 $4$ 的高度为 $4$，这不会阻挡现有的可见性，但使得山 $4$ 现在可以看到山 $2$，从而使得答案变为 $7$。

第二次更新后，山 $1$ 的高度为 $5$，这不会阻挡现有的可见性，但使得山 $1$ 现在可以看到山 $3$，$4$ 和 $5$，从而使得答案变为 $10$。

第三次更新后，山 $3$ 的高度为 $5$，阻挡了山 $1$ 看到山 $4$，阻挡了山 $2$ 看到山 $4$ 和 $5$，同时由于该山本就可以看到其他所有山，所以并没有使得该山看到更多的山，从而使得答案变为 $7$。

### 测试点性质

 - 测试点 $2-5$ 满足 $N,Q \le 100$。
 - 测试点 $6-11$ 满足 $Q \le 10$。
 - 测试点 $12-21$ 没有额外性质。


title: [USACO22DEC] Strongest Friendship Group G

description:
Farmer John 有 $N$ 头奶牛（$2 \le N \le 10^5$），编号为 $1\cdots N$。这些奶牛中有 $M(1 \le M \le 2\times 10^5)$ 对朋友。

一组奶牛被称为是「小团体」，如果该组中的每头奶牛都可以从该组中的每头其他奶牛出发通过完全位于该组内的一系列朋友关系到达（连接到组外奶牛的朋友关系无效）。小团体的「强度」是组内奶牛的最小组内朋友数乘以组内奶牛的数量（同样，注意连接到组外奶牛的朋友关系不计入此定义）。

求所有小团体的最大强度。

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

以下 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 和 $v_i$ 是朋友（$1 \le u_i,v_i \le N,u_i\neq v_i$）。每个奶牛无序对至多出现一次。

outputFormat: 输出一行，包含所有小团体的最大强度。

hint:
### 样例 1 解释

可以观察到最大强度来自编号为 $1,2,3,4$ 的奶牛组。该组内奶牛的最小朋友数为 $3$，故答案为 $4 \times 3=12$。

### 测试点性质

 - 对于 $1 \le T \le 3$，测试点 $T$ 满足 $N \le 16$。
 - 对于 $4 \le T \le 9$，测试点 $T$ 满足 $N \le 1000$。
- 对于 $10 \le T \le 20$，测试点 $T$ 没有额外限制。


title: 【模板】分治 FFT

background: 也可用多项式求逆解决。

description:
给定序列 $g_{1\dots n - 1}$，求序列 $f_{0\dots n - 1}$。

其中 $f_i=\sum_{j=1}^if_{i-j}g_j$，边界为 $f_0=1$。

答案对 $998244353$ 取模。

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

第二行 $n-1$ 个整数 $g_{1\dots n - 1}$。

outputFormat: 一行 $n$ 个整数，表示 $f_{0\dots n - 1}$ 对 $998244353$ 取模后的值。


title: 【模板】最大流 加强版 / 预流推进

description: 给定 $n$ 个点，$m$ 条有向边，给定每条边的容量，求从点 $s$ 到点 $t$ 的最大流。

inputFormat:
第一行包含四个正整数 $n$、$m$、$s$、$t$，用空格分隔，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来 $m$ 行每行包含三个正整数 $u_i$、$v_i$、$c_i$，用空格分隔，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，容量为 $c_i$。

outputFormat: 一个整数，表示 $s$ 到 $t$ 的最大流。

hint:
$1\leqslant n \leqslant 1200, 1\leqslant m \leqslant 120000, 1\leqslant c \leqslant 2^{31}-1$。

保证答案不超过 $2^{31}-1$。

常用网络流算法的复杂度为 $O(n^2 m)$，请尽量优化算法。

数据提供者：@negiizhao

（如果有人用 dinic 算法过掉了此题，请私信上传者）


title: [USACO22DEC] Breakdown P

description:
Farmer John 的农场可以用一个带权有向图表示，道路（边）连接不同的结点，每条边的权值是通过道路所需的时间。每天，Bessie 喜欢从牛棚（位于结点 $1$）经过恰好 $K$ 条道路前往草地（位于结点 $N$），并希望在此限制下尽快到达草地。然而，在某些时候，道路停止维护，一条一条地开始破损，变得无法通行。帮助 Bessie 求出每一时刻从牛棚到草地的最短路径！

形式化地说，我们从一个 $N$ 个结点（$1 \le N \le 300$）和 $N^2$ 条边的带权有向完全图开始：对于 $1 \le i,j \le N$ 的每一对 $(i,j)$ 存在一条边（注意存在 $N$ 个自环）。每次移除一条边后，输出从 $1$ 到 $N$ 的所有路径中经过恰好 $K$ 条边（不一定各不相同）的路径的最小权值（$2 \le K \le 8$）。注意在第 $i$ 次移除后，该图还剩下 $N^2-i$ 条边。

路径的权值定义为路径上所有边的权值之和。注意一条路径可以包含同一条边多次或同一个结点多次，包括结点 $1$
和 $N$。

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

以下 $N$ 行每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数为 $w_{ij}(1 \le w_{ij} \le 10^8)$。

以下 $N^2$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i,j \le N$）。每对整数出现恰好一次。

outputFormat: 输出 $N^2$ 行，为每一次移除后经过 $K$ 条边的路径的最小权值。如果不存在经过 $K$ 条边的路径则输出 $-1$。

hint:
### 样例 1 解释

第一次移除后，最短的经过 $4$ 条边的路径为：

$$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3$$

第二次移除后，最短的经过 $4$ 条边的路径为：

$$1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3$$

第三次移除后，最短的经过 $4$ 条边的路径为：

$$1 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3$$

六次移除后，不再存在经过 $4$ 条边的路径。

### 测试点性质

 - 对于 $2 \le T \le 14$，测试点 $T$ 满足 $K=\lfloor \dfrac{T+3}{2} \rfloor$。


title: 10 进制转 x 进制

type: B

description: 给定一个十进制整数 $n$ 和一个小整数 $x$。将整数 $n$ 转为 $x$ 进制。对于超过十进制的数码，用 `A`，`B` ... 表示。

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

第二行一个整数 $x$。

outputFormat: 输出仅包含一个整数，表示答案。

hint:
【数据规模和约定】
保证 $n$ 不超过 $10^9$，$x$ 不超过 $36$。


title: 【模板】常系数齐次线性递推

description:
求一个满足 $k$ 阶齐次线性递推数列 ${a_i}$ 的第 $n$ 项，即：

$$a_n=\sum\limits_{i=1}^{k}f_i \times a_{n-i}$$

inputFormat:
第一行两个数 $n$,$k$，如题面所述。

第二行 $k$ 个数，表示 $f_1 \ f_2 \ \cdots \ f_k$

第三行 $k$ 个数，表示 $a_0 \ a_1 \ \cdots \ a_{k-1}$

outputFormat: 一个数，表示 $a_n \bmod 998244353$ 的值


title: 【模板】多项式对数函数（多项式 ln）

description:
给出 $n-1$ 次多项式 $A(x)$，求一个 $\bmod{\:x^n}$ 下的多项式 $B(x)$，满足 $B(x) \equiv \ln A(x)$.

在  $\text{mod } 998244353$  下进行，且 $a_i \in [0, 998244353) \cap \mathbb{Z}$

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

下一行有 $n$ 个整数，依次表示多项式的系数 $a_0, a_1, \cdots, a_{n-1}$.

保证 $a_0 = 1$.

outputFormat: 输出 $n$ 个整数，表示答案多项式中的系数 $a_0, a_1, \cdots, a_{n-1}$.


title: 【模板】多项式指数函数（多项式 exp）

description: 给出 $n-1$ 次多项式 $A(x)$，求一个 $\bmod{\:x^n}$ 下的多项式 $B(x)$，满足 $B(x) \equiv \text e^{A(x)}$。系数对 $998244353$ 取模。

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

下一行有 $n$ 个整数，依次表示多项式的系数 $a_0, a_1, \cdots, a_{n-1}$.

保证 $a_0 = 0$.


title: [ZJOI2007] 粒子运动

description:
阿Q博士正在观察一个圆形器皿中的粒子运动。不妨建立一个平面直角坐标系，圆形器皿的圆心坐标为$(x_0, y_0)$，半径为$R$。器皿中有若干个粒子，假设第$i$个粒子在时刻$0$的位置为$(x_i, y_i)$，速度为$(v_{x_i},v_{y_i})$（注：这是一个速度向量，若没有发生碰撞，$t$时刻的位置应该是$(x_i + t * v_{x_i}, y_i + t * v_{y_i})$ ）。假设所有粒子的运动**互不干扰**；若某个粒子在某个时刻碰到了器皿壁，将发生完全弹性碰撞，即速度方向按照碰撞点的切线镜面反射，且速度大小不变（如图）。认为碰撞是瞬间完成的。

![particle](https://cdn.luogu.com.cn/upload/pic/22046.png)

尽管碰撞不会影响粒子的速率，但是粒子却会受到一定的伤害，所以若某一个粒子碰撞了$k$次器皿壁，那么在第$k$次碰撞时它便会消亡。

出于研究的需要，阿Q博士希望知道从时刻$0$到所有粒子都消亡这段时间内，所有粒子之间的最近距离是什么。你能帮助他么？

inputFormat: 输入文件particle.in第一行包含三个实数，分别为$x_0, y_0, R$，即圆形器皿的圆心坐标及半径。第二行包含两个正整数$N, k$，分别表示粒子的总数与消亡碰撞次数。接下来$N$行每行四个实数，分别为$x_i, y_i, v_{x_i} , v_{y_i}$，保证$(x_i, y_i)$都在圆内且$(v_{x_i}, v_{y_i})$非零。

outputFormat: 输出文件particle.out仅包含一个实数，即所有粒子的历史最近距离，精确到小数点后三位。

hint:
对于所有的数据，$2 \leq N \leq 100$。$1 \leq k \leq 100$。

请注意实数精度问题。


title: [HNOI2009] 图的同构计数

background:
当学生们遇到某个难题时经常会说“这怎么做，这不是NP问题吗？”、“这个只有搜了，这己经被证明是NP问题了”。但是，你应该淸楚，大多数人此时所说的NP问题其实都是指NPC问题。很多人没有真正掌握NP问题和NPC问题这两个基本概念。其实NP问题并不是那种“只有搜才行”的问题，NPC问题才是。

很久以前就有一个古老的传说：有―个著名的问题，即P是否等于NP的问题，传说中谁要是证明或者证伪了这个命题，他将获得幸福。这里P是指能在多项式时间里求解的问题的集合。而NP是指可在多项式时间里验证的问题的集合。显然P是NP的子集，因为能在多项式时间里求解的问题，必定可在多项式时间里验证。

到目前为止还没有人因这个命题得到幸福。但是，有一个总的趋势，也就是人们普遍认为，$P=NP$不成立，即，多数人相信，至少存在一个不可能有多项式时间复杂度的求解算法的NP问题。人们如此坚信$P \neq NP$是有原因的，因为在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也就是所谓的NPC问题。正是因为存在NPC问题，才使人们相信$P \neq NP$。

在提出NPC的概念之后，绝大多数“自然”的难题最后都被证明是NPC问题，只有三个例外，它们分别是：

- 线形规划问题；
- 图同构问题；
- 素数判定问题与大数分解问题。

description:
小雪在了解到以上情况后，自认为直接挑战终极难题还有不少困难，于是决定先从简单的问题做起，具体来说，他对图同构问题产生了浓厚的兴趣。$A$图与$B$图被认为是同构的是指：$A$图的顶点经过一定的重新标号以后，$A$图的顶点集和边集要完全与$B$图一一对应。

小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含$N$个点的图有多少种。众所周知含$N$个点的简单图最多有$N*(N-1)/2$条边，这样含$N$个点的图有$2^{N*(N-1)/2}$种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你，在他想出来之前快点解决吧！

inputFormat: 从文件input.txt中读入数据，文件中只有一个非负整数$N$，表示图的顶点数，且$0 \leq N \leq 60$。

outputFormat: 输出文件output.txt中仅包含一个整数，表示含$N$个点的图在同构意义下不同构的图的数目。因为答案可能很大，所以输出的最终答案是$\bmod 997$的结果（$997$是一个素数）。


title: [HNOI2009] 双递增序列

description:
考虑一个长度为偶数 $n$ 的序列 $a_1, a_2, \dots, a_n$，我们称这个序列为好的，当且仅当存在 $a_1, a_2, \dots, a_n$ 的一个划分 $U=\{ a_{i_1}, a_{i_2}, \dots, a_{i_{n/2}} \}, V=\{ a_{j_1}, a_{j_2}, \dots, a_{j_{n/2}} \}=\{ a_1, a_2, \dots, a_n \}-U$，且 $i_1<i_2< \dots <i_{n/2}, a_{i_1}<a_{i_2}< \dots <a_{i_{n/2}}, j_1<j_2< \dots <j_{n/2}, a_{j_1}<a_{j_2}< \dots <a_{j_{n/2}}$。

比如序列 $3, 1, 4, 5, 8, 7$ 就是一个好的序列。因为它可以分成 $U=\{3, 4, 8\}, V=\{1, 5, 7\}$。而序列 $3, 2, 1, 6, 5, 4$ 则不是一个好的序列。

现在的问题是，针对给出的若干序列，请你判断它们是否是好的序列。

inputFormat:
第一行仅包含一个整数 $m$，表示需要判断 $m$ 个序列。
接下来的 $m$ 行分别给出这些序列。每个序列的输入为一行，每行的第一个数为一个偶数 $n$，表示序列的长度，随后的 $n$ 个整数表示序列本身的元素 $a_1, a_2, \dots, a_n$。同一行的各数之间用一个空格隔开。

outputFormat: 输出 $m$ 行，如果第 $i$ 个序列为好的序列，那么第 $i$ 行输出`Yes!`，否则输出 `No!`。


title: [HNOI2009] 积木游戏

description:
丹丹是一位狂热的俄罗斯方块爱好者，但在把积分刷爆之后她终于开始感到厌倦了。于是她着手思考这样一个俄罗斯方块的简化版游戏：在初始状态地面上是空的。假设所有的积木都是长方形，且积木不能旋转或翻转。丹丹在每个时刻会选择一个位置将一块积木落下，当积木在落下的过程中碰到地面或另一块积木时，它会停留在地面上或那块积木上。落到另—块积木上意味着：上面的积木的下边界与下面的积木的上边界至少有一条线段重合(―个点不算)，如图 1 所示。

![图1](https://cdn.luogu.com.cn/upload/pic/22107.png)

在俄罗斯方块中，如果某个时刻积木之间形成了一个洞，那么看上去就很不优美。于是丹丹想知道，每落下一块积木之后，会形成几个新的洞。一个洞是指由积木的边界或地面组成的一块面积大于 $0$ 的封闭的区域，如图 2（a）和图 2（b）所示。

要注意的是：当出现图 3 所示的情况时，因为积木 1 和积木 2 紧紧地挨在一起，所以当积木 3 落下的时候，不会形成新的洞。

现在丹丹告诉你她依次落下的积木的髙度 $H_i$ 以及落下的位置的左右边界 $L_i$ 与 $R_i$，$1 \leq i \leq n$，而她想知道毎次积木落下时会形成几个新的洞？

![图23](https://cdn.luogu.com.cn/upload/pic/22108.png)

inputFormat: 第一行包含一个正整数 $n$，表示落下的积木的总数。接下来有$n$行，每行有用一个空格隔开的三个整数，分别表示 $L_i$、$R_i$ 和 $H_i$，即积木落下的左右边界和积木的高度。

outputFormat: 包含 $n$ 行，每行只有一个数，第 $i$ 行表示第 $i$ 个积木落下后形成的新的洞的数目。

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

输入数据保证 $0 \leq L_i < R_i \leq 100000, H_i \leq 1000$。

$30\%$ 的数据保证 $n \leq 100$。

$100\%$ 的数据保证$n \leq 100000$。

**【样例说明】**

样例执行后的结果如图 4 所示，其中依次落下的积木按顺序编号为从 $1$ 到 $6$ 的一个整数。

![图4](https://cdn.luogu.com.cn/upload/pic/22110.png)


title: 孤舟蓑笠翁

background:
![Background](https://i.loli.net/2018/07/04/5b3cc42f57e64.png)

出于保护鱼类的目的，最优秀的渔翁才能在洞庭湖继续捕鱼。经过层层选拔，洞庭湖上只剩下孤舟蓑笠翁。以前跟其他渔翁一起钓鱼、打牌、切磋武艺，而如今只剩孤单一人，蓑笠翁不禁黯然神伤。选拔被淘汰，如今他们都去哪里了呢？大概回家种田养猪了吧。

description:
![Description](https://i.loli.net/2018/07/04/5b3cc3f0cd5f5.png)

蓑笠翁现在闲暇时在练的武术名为"左右互搏术"，相传是周伯通首创的武功。

练功时，蓑笠翁的双手在某竖直平面内运动，以该平面上某点作为坐标原点，向右为 $x$ 轴正方向，向上为 $y$ 轴正方向建立直角坐标系。那么该平面内的一个点就可以用坐标 $(x, y)$ 来表示。

该武功有 $n$ 个可停顿点，分别为 $p_1 = (x_1, y_1), p_2 = (x_2, y_2), \ldots, p_n = (x_n, y_n)$。我们可以将蓑笠翁练功的过程分成一秒一秒来看，第 $i$ 秒时，双手都处于可停顿点上。而第 $i$ 秒末双手进行移动，移动到其它可停顿点上。（当然也可以不移动）

左右互搏术中，有 $k$ 种绝招。第 $i$ 种绝招为：左手处于 $v_i$ 号可停顿点，右手处于 $u_i$ 号可停顿点，则可以发动绝招。

练武功也有禁忌，在两只手停顿的时候，如果两只手的曼哈顿距离小于 $d_{min}$，则容易走火入魔。如果两只手的曼哈顿距离大于 $d_{max}$，则蓑笠翁的胳膊显然快被扯断了。所以假设左手在 $l$ 号停顿点，右手在 $r$ 号停顿点，则需要满足 $d_{min} \leq |x_l - x_r| + |y_l - y_r| \leq d_{max}$。

从一个停顿点移动到另一个停顿点也有讲究，而且对于左右手还不一样。有 $m$ 个移动条件，每个移动条件形如：左手在 $a$ 号停顿点时能移动到 $b$ 号停顿点且在 $b$ 号停顿点时也能移动到 $a$ 号停顿点，或右手在 $a$ 号停顿点时能移动到 $b$ 号停顿点且在 $b$ 号停顿点时也能移动到 $a$ 号停顿点。对于某一秒末，蓑笠翁的手没那么快，所以每只手至多只能进行移动一次。上面未提到的移动方式均为非法。

蓑笠翁希望能发动连击。即先发动第 $i$ 种绝招，经过 $t$ 秒的移动后，又发动了第 $j$ 种绝招，且 $i \neq j$。

给出 $p_1, \ldots , p_n$，$v_1, \ldots v_k$，$u_1, \ldots , u_k$，$d_{min}$，$d_{max}$，和 $m$ 个移动条件，现在蓑笠翁想知道，发动第 $i$ 种绝招之后，最少经过多少秒的移动后能发动某个编号不为 $i$ 的绝招，即发动连击的最短耗时。请对于每个 $1 \leq i \leq k$ 输出答案。

inputFormat:
![Input](https://i.loli.net/2018/07/04/5b3ce144d752b.png)

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

第二行两个非负整数 $d_{min}, d_{max}$。保证 $d_{min} \leq d_{max}$。

接下来 $n$ 行，这 $n$ 行中的第 $i$ 行每行两个正整数 $x, y$ 表示 $i$ 号停顿点的坐标。

接下来的一行一个正整数 $k$ 。

接下来 $k$ 行，这 $k$ 行中的第 $i$ 行每行两个正整数 $v, u$ 表示 $i$ 号绝招。左手处于 $v$ 号可停顿点，右手处于 $u$ 号可停顿点时能发动该绝招。保证 $1 \leq v, u \leq n$，不会有两个绝招完全相同，保证 $v, u$ 的曼哈顿距离不小于 $d_{min}$ 不大于 $d_{max}$。

接下来 $m$ 行，每行三个正整数 $a, b, type$，若 $type = 0$ 则表示左手在 $a$ 号停顿点时能移动到 $b$ 号停顿点且在 $b$ 号停顿点时也能移动到 $a$ 号停顿点，若 $type = 1$ 则表示右手在 $a$ 号停顿点时能移动到 $b$ 号停顿点且在 $b$ 号停顿点时也能移动到 $a$ 号停顿点。保证 $1 \leq a, b \leq n$，$type \in \{0, 1\}$。

outputFormat:
![Output](https://i.loli.net/2018/07/04/5b3cc520d9fa0.png)

$k$ 行，第 $i$ 行表示第 $i$ 个绝招发动一次连击的最短耗时。

如果无论如何都无法连击，请输出 $-1$。

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

![Explain](https://i.loli.net/2018/07/04/5b3cc62a913ae.png)

**对于样例一的解释**　对于绝招 $1$，可以先同时将左手移动到 $2$ 号可停顿点，右手移动到 $3$ 号可停顿点，这样耗时 $1 \textrm{ s}$，再将左手移动到 $1$ 号可停顿点，右手不动，这样可以发动绝招 $2$，共用时 $2 \textrm{ s}$。对于绝招 $2$ 可以把刚才的过程反过来，发动绝招 $1$。对于绝招 $3$，无论如何右手都无法移动，不能发动任何绝招，故输出 $-1$。

**对于样例二的解释**　不解释。

**【数据范围】**

![Constraint](https://i.loli.net/2018/07/04/5b3cc6528795b.png)

其中 $20 \%$ 的数据，$n \leq 50$，$m \leq 100$，$k \leq 100$。
另有 $30 \%$ 的数据，$n \leq 500$，$m \leq 2000$，$k \leq 10000$，$d_{min} = 0$，$d_{max} = 10000$。
对于 $100 \%$ 的数据，$n \leq 1000$，$m \leq 4000$，$1 \leq x_i, y_i \leq 1000$，$0 \leq d_{min} \leq d_{max} \leq {10}^9$。


title: [BalticOI 2015] Bowling

description:
Byteasar is a fan of both bowling and statistics. He has written down the results of a few past bowling games.

Unfortunately, some characters in the notes are blurry, and thus unreadable. Byteasar asks you to write a
program to calculate the number of distinct games which are consistent with his notes.

## Rules of Bowling

A bowling game consists of $n$ frames: $n-1$ simple frames and one final frame. In a typical game $n = 10$. At the beginning of each frame $10$ pins are put standing upright at the end of a lane and a player gets no more than two (or three for the final frame) attempts (shots) to throw a bowling ball down the lane to try to knock down as many pins as possible. Each frame is denoted by two (for a simple frame) or three (for the final frame)
characters.

For each shot the player receives as basic points the total number of pins knocked down in this shot. The player’s basic points in each frame are the sum of basic points of all the shots in this frame. If all $10$ pins are knocked down in a simple frame (and therefore $10$ basic points are earned), the player gets additional bonus points.

For a simple frame the rules are the following:

   - If a player knocks down all $10$ pins in the first shot of a frame, she gets a strike and the frame ends. As bonus points she gets the sum of basic points of her next two shots. A strike is denoted as “``x-``”.

   - If a player knocks down all $10$ pins using both shots of a frame, she gets a spare. As bonus points she gets the basic points of her next shot. A spare is denoted as “``A/``”, where $A$ is a digit describing the number of pins knocked down in the first shot of the frame.

   - If $9$ or fewer pins are knocked down after both shots, the player gets just basic points and such a frame is denoted as “``AB``”, where $A$ is the one-digit number of pins knocked down in the first shot, and $B$ is the one-digit number of pins knocked down in the second shot $(A + B < 10)$.

Note that bonus points are included to the score of a frame in which the strike or the spare was obtained,regardless of the fact that the exact number of bonus points depends on future shots in next frames.

For the final frame the rules are the following:

   - Initially the player receives two shots in this frame. If $9$ or fewer pins are knocked down in the two shots,the frame ends. Otherwise (if the first two shots are a spare or the first shot is a strike), the player receives a third shot in the frame. Whenever the player knocks down all the pins in any of the three shots, the pins are reset to the initial configuration for the next shot. The score of the final frame is the total number of pins knocked down (note that no bonus points are earned due to strikes and spares).

   - Overall there are seven possible configurations of the final frame with the following outcomes ($A$ and $B$ stand for one-digit numbers):

![0](https://s1.ax1x.com/2018/07/05/PVwA8U.png)

Each game is described as a sequence of $2n + 1$ characters. At the end of the game the total number of points after each frame may be calculated. For example, for a game of $n = 10$ frames described as “``08x-7/2/x-x-23441/0/x``”, the player’s points after respective frames were as follows:

![1](https://s1.ax1x.com/2018/07/05/PVwE2F.png)

inputFormat:
The first line of input contains one integer $q(1 \le q \le 25)$, specifying the number of test cases to consider. The following $3q$ lines of input contain descriptions of test cases. Each test case is described by three lines of input.
The first line of a test case description contains one integer $n(2 \le n \le 10)$, specifying the number of frames. The second line contains a sequence of $2n + 1$ characters which denotes the game description from Byteasar’s notes. Blurry characters are replaced by “``?``” characters. The third line contains $n$ integers, the total number of points after each frame, separated by spaces. In each number either all digits are readable, or all digits are blurry. Numbers in which all digits are blurry are replaced by “``-1``”.

outputFormat:
Your program should output $q$ lines, one line per each test case in the same order as in the input.

For each test case your program should write one integer: the number of possible distinct games corre-sponding to the test case. Two games are considered different if and only if they differ in at least one shot,that is, their $(2n+1)$-character game descriptions are different. You can assume that there is at least one game consistent with each test case in the input. You can assume that the result fits into 64-bit signed integer type.

hint:
**Explanation to the examples:** In the first case, in frame $5$ after the character “``x``” the only possible character is “``-``”. In frame $8$ the player got $8$ points in total. Thus there are $9$ possibilities how this sum could have been obtained: $0 + 8,1 + 7,...,8 + 0$. There were no bonus points in frame $9$. Therefore, there were no points on the first shot of the final frame. To obtain $20$ points in the last two shots, the only possibility is a spare with a following strike in the last shot of the frame. Therefore there are $9$ different valid games which correspond to this input data.

In the second case, any character from $0$ to $9$ is consistent with the input data.

以下子任务和评测无关，仅供参考。

![3](https://s1.ax1x.com/2018/07/05/PVwmr9.png)

（但是我开不了 5 个 Subtask，所以就放在一起测了）


title: [BalticOI 2015] Editor

description:
Byteasar is a programmer who works on a revolutionary text editor. In the editor there are two types of operations: one type allows to edit text in the editor, and the other type allows to undo previously performed operations. One of the innovative features of this editor is a multilevel undo operation. It works as follows.

We say that a text editing operation is an operation of level $0$. An undo operation of level $i(for \ i = 1,2,...)$ undoes the last operation of level at most $i-1$ which is not undone. For instance, an undo operation of level $1$ can undo only editing operations, and an undo operation of level $2$ can undo editing operations as well as undo operations of level $1$ (but no undo operations of greater levels).

More formally, each of the already performed operations can be in two states: active or undone. Let $X$ be one of the operations. Just after performing the operation $X$, it is in the state active. If $X$ is an undo operation of level $i$, we find the most recent operation in state active of level at most $i-1$ (denote it by $X_1$) and change the state of the operation X1 to undone. If X1 is also an undo operation, we must change to active the state of the operation which $X_1$ had undone (say $X_2$). We continue in the same manner: whenever
the state of an undo operation $X_j$ which had previously undone some operation $X_{j+1}$ changes, we must also change the state of the operation $X_{j+1}$(which, of course, may result in changing states of further operations).

The whole chain of state modifications finishes when an editing operation is reached.

For simplicity, the current contents of text in the editor will be specified by a single integer s, called the editor state (equal to $0$ at the beginning). Each editing operation specifies the editor state that it produces.

The editor state depends on the last editing operation in the state active. Help Byteasar and write a program which keeps track of the editor state.

Let us see this in action: the following table shows some operations performed by Byteasar and the editor state after performing each of them. The symbol $E_s$ denotes an editing operation which changes the editor state to $s$, whereas the symbol $U_i$ denotes an undo operation of level $i$.

![0](https://s1.ax1x.com/2018/07/05/PV0kdI.png)

First, Byteasar performed three editing operations. The editor state changed from $0$ to $1$, then to $2$, and finally to $5$. Next, he performed two undo operations of level $1$, which undid the operations $E_5$ and $E_2$(changing
their state to undone). Thus the editor state was restored to $1$. The following undo operation of level $3$ undid the last operation $U_1$(changing its state to undone), consequently restoring the operation $E_2$(changing its state
back to active). As a result the editor state changed once again to $2$. Operation $U_2$ undid the operation $E_4$,operation $U_1$ once again undid the restored operation $E_2$, the last operation $U_1$ undid the operation $E_1$, and the final operation is $E_1$.

inputFormat: The first line of the input contains a positive integer $n$, specifying the number of operations performed by Byteasar. The next $n$ lines contain descriptions of operations, one per line, each being an integer $a_i(-n \le a_i \le n, a_i ≠ 0)$. If $a_i> 0$, then it specifies an editing operation which modifies the editor state to $a_i$. If $a_i< 0$,then it specifies an undo operation of level $-a_i$. You can assume that for every undo operation there will be some operation in the state active of smaller level to undo.

outputFormat: Your program should output $n$ lines. The $i-th$ line should contain one integer specifying the editor state after performing the first $i$ operations from the input.

hint:
以下子任务和评测无关，仅供参考。

![0](https://s1.ax1x.com/2018/07/05/PV0nSS.png)

（但是我开不了 4 个 Subtask，所以就放在一起测了）


title: [BalticOI 2015] Tug of War

description:
拔河（*Tug of War*）在 Byteland 是十分受欢迎的运动。规则十分简单：两队以相反方向拉绳子。一年一度的 Byteland 拔河比赛将要进行，并且许多选手都报名参加了。作为公平竞赛专员，你的工作是把选手们划分为两个队伍，使得这个比赛能够进行很长时间。

由于一共 $2n$ 名选手报名参赛，所以一个队有 $n$ 名队员。一根绳上左右两边各有 $n$ 个点。Byteland 的拔河精英们都很挑剔，每个参赛选手在左右两边都有一个他们想要站的位置。此外，你知道每一个参赛选手的力量值。

组织者现在问你如下的问题：给定一个整数 $k$，能否分出两个队，这两个队各有 $n$ 名选手，并且他们站在他们想站的位置（当然不能有两名或以上选手站在同一位置），双方力量和之差不超过 $k$？

inputFormat:
输入的第一行有两个正整数 $n,k$，分别表示绳子每一侧的位置数和两队的最大力量差。为了简单，我们把参赛者编号为 $1$ 到 $2n$。

接下来 $2n$ 行，每行描述一个参赛者，这些行中的第 $i$ 行包含三个正整数 $l_i,r_i,s_i$，分别表示 $i$ 号选手有力量 $s_i$，并且想站在左边的 $l_i$ 位置或是右边的 $r_i$ 位置。

outputFormat: 你的程序应在第一行输出一个单词 `YES` 或 `NO`，表示是否有可能建立两支符合上述条件的队伍。

hint:
### 样例解释 1

第一个样例中我们可以安排 $1,3,6,7$ 号选手站在左边（这个队伍力量值为 $1+8+2+1=12$），并安排 $2,4,5,8$ 号选手站在右边（这个队伍力量值为 $2+2+5+2=11$）。力量值的差为 $1$。

### 样例解释 2

第二个样例中两位力量值为 $4$ 的选手不得不在一个队中，因此两队最小的力量值之差为 $6$。

### 子任务

以下子任务与评测无关，仅供参考。

本题采用子任务式测评，只有一个子任务内所有测试点均正确才可获得此子任务的分数。

对于全部子任务，$k\le 20n,1\le l_i,r_i\le n,1\le s_i\le 20$。

对于每个子任务满足的条件如下：

| 子任务 |           条件            | 分数 |
| :----: | :-----------------------: | :--: |
|  $1$   |         $n\le 10$         | $18$ |
|  $2$   |    $n\le 2\times 10^3$    | $30$ |
|  $3$   | $n\le 3\times 10^4,s_i=1$ | $23$ |
|  $4$   |    $n\le 3\times 10^4$    | $29$ |

~~注：实际上，拔河并不取决于力量而取决于双方体重。原题的选手力量值应正比于选手体重值。~~

### 附注

本题翻译搬运自 [LibreOJ](https://loj.ac/problem/2707)，译者为 HeRaNO，在此对原翻译者表示感谢。


title: [BalticOI 2015] Hacker

description:
Byteasar the hacker has qualified for this year’s IHO, the International Hacking Olympiad. One of the tasks in the Olympiad involves competing against a system operator. There are $n$ computers numbered from $1$ to $n$,connected in a ring topology, i.e. computers $i$ and $i+1$ are connected $(for \ i = 1,...,n-1)$, and also computers $n$ and $1$ are connected.
The competition is performed as a game between the hacker and the system operator:
   - Byteasar moves first. Afterwards, the operator and Byteasar move alternately.
   - In his first move, Byteasar chooses any computer and hacks it (for instance,by exploiting some operating system vulnerabilities).
   - In his first move, the operator chooses any non-hacked computer and protects it (for instance, by installing latest security upgrades).
   - In all his following moves, Byteasar either (a) does nothing or (b) chooses any computer that is neither hacked nor protected and is directly linked to any hacked computer, and hacks it.
   - In all his following moves, the operator either (a) does nothing or (b) chooses any computer that is neither hacked nor protected and is directly linked to any protected computer, and protects it.
   - The game ends as soon as both have done nothing in two subsequent moves.

At the beginning of the game none of the computers are hacked or protected.
Every computer $i$ has a certain value viwhich specifies the value of the data which is stored on it. For each hacked computer $i$, Byteasar scores its value $v_i$. Byteasar is quite a good hacker, but has no idea of algorithms.
That is why he asks you to write a program that computes his maximum possible score, assuming that the operator plays optimally.

inputFormat:
The first line of input contains a positive integer $n(n \ge 2)$, specifying the number of computers. The second line contains a sequence of $n$ integers $v_1,v_2,...,v_n(1 \le v_i \le 2000)$; number vispecifies the value of the data
stored on computer $i$.

outputFormat: In the first and only line of output your program should write one integer: Byteasar’s maximum possible score against an optimally playing operator.

hint:
**Explanation to the examples:** In the first example, Byteasar in his first move should hack computer $2$(scoring $6$). The operator’s response will be protecting computer $3$. In the next move Byteasar can hack computer $1$ (scoring $7$). Finally, the operator will protect computer $4$.

以下子任务与评测无关，仅供参考。

![PVIZHx.png](https://s1.ax1x.com/2018/07/05/PVIZHx.png)


title: Beautiful Pair

description: 小 D 有个数列 $\{a\}$，当一个数对 $(i,j)$（$i \le j$）满足 $a_i$ 和 $a_j$ 的积不大于 $a_i, a_{i+1}, \ldots, a_j$ 中的最大值时，小 D 认为这个数对是美丽的。请你求出美丽的数对的数量。

inputFormat:
第一行输入一个整数 $n$，表示元素个数。
第二行输入 $n$ 个整数 $a_1,a_2,a_3,\ldots,a_n$，为所给的数列。

outputFormat: 输出一个整数，为美丽的数字对数。


title: 【模板】扩展卢卡斯定理/exLucas

background: 这是一道模板题。

description:
求

$${\mathrm{C}}_n^m \bmod{p}$$

其中 $\mathrm{C}$ 为组合数。

inputFormat: 一行三个整数 $n,m,p$ ，含义由题所述。

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


title: [CERC2017] Assignment Algorithm

description:
A low-budget airline is designing a sophisticated algorithm that will assign more desirable seats to passengers who buy tickets earlier. Their airplane has $r$ rows of seats, where $r$ is an even integer. There are also $3$ exit rows in the airplane; those rows do not contain any seats but only provide access to the emergency exits. One exit row is in the very front of the airplane (before the first row of seats), one in the very back (behind the last row of seats) and one right in the middle. The rows are numbered with integers $1$ through $r + 3$ with row numbers increasing from the front to the back of the airplane. Rows
numbered $1$, $r/2 + 2$ and $r + 3$ are exit rows while all the other rows are seat rows.
The seating configuration is “3–3–3” — each seat row contains three groups of three seats with the passenger aisles between the groups. Seats in the same row are denoted with consecutive letters left to right corresponding to the pattern “``ABC.DEF.GHI``”.
When a passenger purchases a ticket, she is assigned a seat according to the following rules:
   1.    If there is an empty seat in a row directly after an exit row, all other rows are ignored in the following step (but they are not ignored when balancing the airplane in the last step).
   2.    First, we select a seat row with the largest number of empty seats. If there are multiple such rows,we select the one closest to an exit row (distance between rows $a$ and $b$ is simply $|a − b|$). If there are still multiple such rows, we select the one with the lowest number.
   3.    Now, we consider empty seats in the selected row and select one with the highest priority. Seat priorities, from highest to lowest are as follows:
   - (a) Aisle seats in the middle group (``D`` or ``F``).
   - (b) Aisle seats in the first and third group (``C`` or ``G``).
   - (c) Window seats (``A`` or ``I``).
   - (d) Middle seat in the middle group (``E``).
   - (e) Other middle seats (``B`` or ``H``).

If there are two empty seats with the same highest priority, we consider the balance of the entire airplane. The airplane’s left side contains all seats with letters ``A``, ``B``, ``C`` or ``D``, while the right side contains all seats with letters ``F``, ``G``, ``H`` or ``I``. We select an empty seat in the side with more empty seats. If both sides have the same number of empty seats, we select the seat in the left side of the airplane.

Some of the airplane’s seats are already reserved (possibly using a completely different procedure from the one described above). Determine the seats assigned to the next $n$ passengers purchasing a ticket.

inputFormat: The first line contains two integers $r$ and $n(2 \le r \le 50, 1 \le n \le 26)$ — the number of seat rows in the airplane (always an even integer) and the number of new passengers purchasing tickets. The following $r + 3$ lines contain the current layout of the airplane. The $j-th$ line contains exactly $11$ characters — the layout of the row $j$ of the airplane. Exit rows and aisles are denoted with the “``.``” characters. The “``#``” character denotes a reserved seat, while the “``-``” character denotes a seat that is currently empty. You may assume there will be at least $n$ empty seats in the airplane.

outputFormat: Output $r + 3$ lines containing the final layout of the airplane. The layout should be exactly the same as in input with the following exception: the seat assigned to the $j-th$ passenger purchasing a ticket should be denoted with the $j-th$ lowercase letter of the English alphabet.

translation:
## 题目描述

一家航空公司正在设计一种复杂的算法，将为提前购票的乘客分配更理想的座位。他们的飞机有 $r$ 排座位，其中 $r$ 是一个偶数。飞机上有 $3$ 行出口行，这些排没有座位，只提供通往紧急出口的通道。一个出口排在飞机的最前面（在第一排座椅之前），一个在最后面（在最后一排座椅之后），另一个在中间的位置。这些行用整数 $1$ 到 $r+3$ 进行编号，行号从飞机前部到后部递增。

编号为 $1$、$r/2+2$ 和 $r+3$ 的行是出口行，而所有其他行都是座位行。
座位配置为 “$3–3–3$” 每排座位包含三个组三个座位，每组座位之间有乘客通道。同一排座位用从左到右的连续字母表示，对应于“``ABC.DEF.GHI``”模式。
当乘客购买机票时，会根据以下规则为其分配座位：

1.如果在出口排的正后方有一排空座位，则在接下来的步骤中忽略所有其他排（但在最后一步中平衡飞机时不忽略）。

2.首先，我们选择空座位数最多的一排座位。如果有多个这样的行，则选择最靠近出口行的行（行 $a$ 和 $b$ 之间的距离仅为 $|a− b|$）。如果仍有多个这样的行，则选择编号最低的行。

3.现在，我们考虑所选行中的空座位，并选择一个优先级最高的座位。座位优先级从高到低排序按照如下规则：\
-（a）中间组的过道座位（即`D`或`F`）。\
-（b）第一组和第三组的过道座位（即``C``或``G``）。\
-（c）靠窗座位（即``A``或``I``）。\
-（d）中间组中的中间座位（即`E`）。\
-（e）第一组和第三组的中间座位（即``B``或``H``）。\
如果有两个空座位具有相同的最高优先级，我们会考虑整个飞机的平衡。飞机左侧包含字母``A``、``B``、`C`或`D`的所有座位，而右侧包含字母`F` 、`G`、`H`或 `I` 的所有座位。我们在空座位较多的一侧选择一个空座位。如果两边有相同数量的空座位，则优先选择飞机左侧的座位。\
飞机的一些座位已经预定好了（即输入中的 `#`）。现在请你确定分配给第 $i$ 个购票的乘客的座位。

## 输入格式

第一行包含两个整数 $r$ 和 $n$ （$2\le r \le50，1\le n \le26$）表示飞机中的座位排数（保证为偶数）和购买机票的乘客数。第 $2$ 到 $r+3$ 行包含飞机的当前布局。第 $j$ 行正好包含 $11$ 个字符，即飞机第 $j$ 行的布局。出口行和通道用 “``.``” 字符表示。“``#``” 字符表示已经预定好的座位，而“``-``”表示当前空座位。保证飞机上至少有 $n$ 个空座位。

## 输出格式

输出包含飞机最终布局的 $r+3$ 行。整体布局应与输入中的布局相同，分配给第 $j$ 个购票乘客的座位应使用英文字母，依次从小写字母 $a$ 到 $z$ 表示。

### 样例输入 #1.

```
2 17
...........
---.#--.---
...........
---.---.---
...........
```

### 样例输出 #1

```
...........
hnd.#lb.fpj
...........
kqg.cma.eoi
...........
```

### 样例输入 #2

```
6 26
...........
---.---.###
#-#.---.---
---.###.---
...........
---.###.---
#--.#-#.--#
#--.--#.#-#
...........
```

### 样例输出 #2

```
...........
gke.aic.###
#-#.mzo.r-v
x-p.###.n-t
...........
fjb.###.dlh
#-s.#-#.w-#
#-u.qy#.#-#
...........
```


title: [CERC2017] Buffalo Barricades

description:
A pasture in the wild west can be represented as a rectangular grid embedded in the upper-right quadrant of a standard coordinate system. A herd of $n$ buffalos is scattered throughout the grid, each occupying a unit square. Buffalos are numbered $1$ through $n$; buffalo $j$ is located in the unit square whose upper-right corner is the point with integer coordinates $(x_j,y_j)$. The coordinate axes represent two rivers meeting at the origin, restricting buffalo movement downwards and leftwards.

A total of $m$ settlers arrive, one by one, and each claims a piece of land using the following procedure:
   1.    The settler picks a point with integer coordinates and installs a single fence post at that point.The point he picks is guaranteed to be free of any previously installed fence posts or fences.Moreover, no two fence posts will have the same $x$-coordinate and no two fence posts will have the same $y$-coordinates.
   2.    Starting from the fence post, the settler builds horizontal and vertical fence segments leftwards and downwards, respectively. Each segment is built to be as long as possible — i. e. until it reaches the river or another fence.
   3.    The settler claims all the land in the connected area bounded with fences and rivers whose upper-right corner is his fence post. Of course, he claims all the buffalos inside as well. Note that settlers arriving later may claim pieces of land already claimed by earlier settlers.

For each settler, find the total number of buffalos he claimed when he arrived.

inputFormat:
The first line contains an integer $n(1 \le n \le 300 000)$ — the number of buffalos. The $j-th$ of the following $n$ lines contains two integers $x_j$ and $y_j(1 \le x_j,y_j \le 10^9)$ — the location of the $j-th$ buffalo.No two buffalos will share the same location.
The following line contains an integer $m(1 \le m \le 300 000)$ — the number of settlers. The $j-th$ of the following $m$ lines contains two integers $x^{'}_{j}$ and $y^{'}_{j}(1 \le x^{'}_{j},y^{'}_{j} \le 10^9)$ — the coordinates of the fence postinstalled by the $j-th$ settler. All $x^{'}_{j}$ are different and all $y^{'}_{j}$ are different.

outputFormat: Output $m$ lines. The $j-th$ line should contain the number of buffalos claimed by the $j-th$ settler upon arrival.

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

（西进运动时期）美国西部的一块牧场可以被表示为坐标系第一象限中的一块矩形网格。有 $n$ 头水牛在其中分布着，每一头都占据着一个单位正方形。水牛们从 $1$ 到 $n$ 编号；$j$ 号水牛位于右上角坐标为 $(x_j, y_j)$ 的单位正方形中。坐标轴表示了两条交汇于原点处的河流，阻止水牛向左下方移动。

一共有 $m$ 个殖民者接连到达，每个人都要宣称一块土地的所有权，其过程遵循以下规则：

1. 殖民者选定一个整数坐标点，并在此处安装一个栅栏柱。他选定的点必须没有被此前安装的栅栏或栅栏柱占据。并且，不存在两个栅栏柱会拥有相同的 $x$ 坐标，也不存在两个栅栏柱会拥有相同的 $y$ 坐标。
2. 从栅栏柱开始，殖民者分别朝着左侧或下侧修建水平或竖直的栅栏片段。每段栅栏都修建得尽可能长：即直到碰到了河流或另一段栅栏才停下。
3. 殖民者宣称以他的栅栏柱为右上角的，被栅栏和河流包围住的连通区域的所有权。当然，他也宣称了其中的所有水牛的所有权。注意后到来的殖民者也有可能宣称了已被先到来的殖民者宣称过的土地。

对于每个殖民者，请求出当他刚到来时，被他宣称了所有权的水牛的数量。

**【输入格式】**

第一行一个正整数 $n$，表示水牛的个数。

接下来 $n$ 行，第 $j$ 行两个正整数 $x_j, y_j$，表示第 $j$ 头水牛的位置，不存在两头水牛的位置重合。

接下来一行一个正整数 $m$，表示殖民者的个数。

接下来 $m$ 行，第 $j$ 行两个正整数 $x'_j, y'_j$，表示第 $j$ 个殖民者安装的栅栏柱的位置，所有 $x'_j$ 互不相同，所有 $y'_j$ 互不相同。

**【输出格式】**

输出 $m$ 行，第 $j$ 行一个整数，表示第 $j$ 个殖民者刚到来时，被他宣称了所有权的水牛的数量。

**【数据范围】**

对于全部数据，$1 \le n, m \le 3 \times {10}^5$，$1 \le x_j, y_j, x'_j, y'_j \le {10}^9$，所有有序数对 $(x_j, y_j)$ 互不相同，所有 $x'_j$ 互不相同，所有 $y'_j$ 互不相同。

**翻译来源**：IOI 2021 集训队第一部分作业，PinkRabbit。


title: [CERC2017] Cumulative Code

description:
As you probably know, a tree is a graph consisting of $n$ nodes and $n - 1$ undirected edges in which any two nodes are connected by exactly one path. In a labeled tree each node is labeled with a different integer between $1$ and $n$.
The Prüfer code of a labeled tree is a unique sequence associated with the tree, generated by repeatedly removing nodes from the tree until only two nodes remain. More precisely, in each step we remove the leaf with the smallest label and append the label of its neighbour to the end of the code. Recall, a leaf is
a node with exactly one neighbour. Therefore, the Prüfer code of a labeled tree is an integer sequence of length $n - 2$. It can be shown that the original tree can be easily reconstructed from its Prüfer code.
The complete binary tree of depth $k$, denoted with $C_k$, is a labeled tree with $2^k - 1$ nodes where node $j$ is connected to nodes $2j$ and $2j + 1$ for all $j < 2^{k-1}$. Denote the Prüfer code of $C_k$ with $p_1,p_2,..., p_{2^k-3}$.
Since the Prüfer code of $C_k$ can be quite long, you do not have to print it out. Instead, you need to answer $n$ questions about the sums of certain elements on the code. Each question consists of three integers: $a, d$ and $m$. The answer is the sum of the of the $C_k'$ s Prüfer code elements $p_a, p_{a+d},p_{a+2d},...,p_{a+(m-1)d}$.

inputFormat: The first line contains two integers $k$ and $q(2 \le k \le 30,1 \le q \le 300)$ — the depth of the complete binary tree and the number of questions. The $j-th$ of the following $q$ lines contains the $j-th$ question:three positive integers $a_j,d_j$ and $m_j$ such that $a_j,d_j$ and $a_j + (m_j - 1)d_j$ are all at most $2^k - 3$.

outputFormat: Output 1 lines. The $j-th$ line should contain a single integer — the answer to the $j-th$ question.

translation:
给一棵深度为 $k$，点数为 $2^k-1$ 的完全二叉树，其中根节点编号为 $1$，节点 $x$ 的儿子为 $2x$ 和 $2x+1$。

记它的 prufer 序列为 $p$，下标从 $1$ 开始。给定 $q$ 次询问，每次给出三个参数 $a$、$d$、$m$，求 $\sum\limits_{i=0}^{m-1}p_{a+id}$。

hint: In the first example above, when constructing the Prüfer code for $C_3$ the nodes are removed in the following order: $4, 5, 2, 1, 6$. Therefore, the Prüfer code of $C_3$ is $2, 2, 1, 3, 3$.


title: [CERC2017] Donut Drone

description:
You are building a simulation in which a drone explores a volatile torus-shaped planet. Technically,the drone is moving across a toroidal grid — a rectangular grid that wraps around circularly in both dimensions. The grid consists of cells organized into $r$ rows numbered $1$ through $r$ top to bottom and $c$
columns numbered $1$ through $c$ left to right. Each grid cell has a certain elevation — a positive integer.

![PZ6NxP.png](https://s1.ax1x.com/2018/07/06/PZ6NxP.png)

The drone is initially located in the cell in the first row and first column. In each step the drone considers three cells: the cell directly to the right, the cell diagonally right-down and the cell diagonally right-up (wrapping around if necessary). The drone flies to the cell with the largest elevation of the three.

Two types of events may happen during the simulation:
   - “``move k``” — The drone makes $k$ steps.
   - “``change a b e``” — The elevation of the cell in row $a$ column $b$ changes to $e$.

Find the drone’s position immediately after each ``move`` event. You may assume that at each point in time, no sequence of three circularly consecutive cells in the same column will have the same elevation.
Hence, each drone step is well defined.

inputFormat:
The first line contains two integers $r$ and $c(3 \le r,c \le 2 000)$ — the number of rows and the number of columns of the toroidal grid. The $i-th$ of the following $r$ lines contains a sequence of $c$ integers $e_{i,1},e_{i,2},...,e_{i,c}(1 \le e_{i,j} \le 10^9)$ — the initial elevations of cells in row $i$.

The following line contains an integer $m(1 \le m \le 5 000)$ — the number of events. The $j-th$ of the following $m$ lines contains the $j-th$ event and is either of the form “``move k``” where $k$ is an integer such that $1 \le k \le 10^9$ or “``change a b e``” where $a,b$ and $e$ are integers such that $1 \le a \le r, 1 \le b \le c$ and $1 \le e \le 10^9$.

outputFormat: Output $w$ lines where $w$ is the number of ``move`` events in the input — the $j-th$ line should contain the drone’s position (row and column numbers) after the $j-th$ ``move`` event in the input.

translation:
输入一个循环矩阵（即第一行的上一行是最后一行，最后一行的下一行是第一行，最后一列的下一列是第一列）。你的初始位置在 $(1,1)$，每一步会走向右上、右、右下三个格子中权值最大的一个格子。

支持两种操作：

- 修改一个格子的权值
- 从当前位置走 $k$ 步，并输出目标位置


title: [CERC2017] Embedding Enumeration

description:
As you probably know, a tree is a graph consisting of $n$ nodes and $n - 1$ undirected edges in which any two nodes are connected by exactly one path. In a labeled tree each node is labeled with a different integer between $1$ and $n$. In general, it may be hard to visualize trees nicely, but some trees can be
neatly embedded in rectangular grids.

Given a labeled tree $G$ with $n$ nodes, a $2$ by $n$ embedding of $G$ is a mapping of nodes of $G$ to the cells of a rectangular grid consisting of $2$ rows and $n$ columns such that:
   - Node $1$ is mapped to the cell in the upper-left corner.
   - Nodes connected with an edge are mapped to neighboring grid cells (up, down, left or right).
   - No two nodes are mapped to the same cell.

Find the number of $2$ by $n$ embeddings of a given tree, modulo $10^9 + 7$.

inputFormat: The first line contains an integer $n(1 \le n \le 300 000)$ — the number of nodes in $G$. The $j-th$ of the following $n - 1$ lines contains two different integers $a_j$ and $b_j(1 \le a_j,b_j \le n)$ — the endpoints of the $j-th$ edge.

outputFormat: Output the number of $2$ by $n$ embeddings of the given tree, modulo $10^9 + 7$.

translation:
输入一棵树，求把这棵树放入  $2*n$ 的网格图中的方案数，对  $10^9+7$ 取模。

要求： $1$ 必须放在  $(1,1)$，有边连接的节点必须相邻，两个节点不能放在同一个格子。

hint:
![PZgNB8.png](https://s1.ax1x.com/2018/07/06/PZgNB8.png)

All $4$ embeddings of the tree in the example input are given in the figure above.


title: albus就是要第一个出场

description:
已知一个长度为 $n$ 的正整数序列 $A$（下标从 $1$ 开始），令 $S = \{ x | 1 \le x \le n \}$，$S$ 的幂集 $2^S$ 定义为 $S$ 所有子集构成的集合。定义映射 $f : 2^S \to Z,f(\emptyset) = 0,f(T) = \mathrm{XOR}\{A_t\}, (t \in T)$。

现在 albus 把 $2^S$ 中每个集合的 $f$ 值计算出来，从小到大排成一行，记为序列 $B$（下标从 $1$ 开始）。

给定一个数，那么这个数在序列 $B$ 中第 $1$ 次出现时的下标是多少呢？

inputFormat: 第一行一个数 $n$, 为序列 $A$ 的长度。接下来一行 $n$ 个数，为序列 $A$，用空格隔开。最后一个数 $Q$，为给定的数.

outputFormat: 共一行，一个整数，为 $Q$ 在序列 $B$ 中第一次出现时的下标模 $10086$ 的值.


title: Gty的妹子序列

description:
Autumn 和 Bakser 又在研究 Gty 的妹子序列了！但他们遇到了一个难题。

对于一段妹子们，他们想让你帮忙求出这之内美丽度 $\in[a,b]$ 的妹子的美丽度的种类数。

为了方便，我们规定妹子们的美丽度全都在 $[1,n]$ 中。

给定一个长度为 $n(1\le n\leq 10^5)$ 的正整数序列 $s(1\le s_i\le n)$，对于 $m(1\le m\le 10^6)$ 次询问 $l,r,a,b$，每次输出 $s_l\cdots s_r$ 中，权值 $\in[a,b]$ 的权值的种类数。

inputFormat:
第一行包括两个整数 $n,m(1 \le n \le 100000,1 \le m \le 1000000)$，表示数列 $s$ 中的元素数和询问数。

第二行包括 $n$ 个整数 $s_1\cdots s_n(1 \le s_i\le n)$。

接下来 $m$ 行,每行包括 $4$ 个整数 $l,r,a,b(1 \le l \le r \le n,1 \le a \le b \le n)$，意义见题目描述。

保证涉及的所有数在 C++ 的 int 内。保证输入合法。

outputFormat: 对每个询问，单独输出一行，表示 $s_l \cdots s_r$ 中权值 $\in [a,b]$ 的权值的种类数。

hint:
【样例的部分解释】

`5 9 1 2 `
子序列为`4 1 5 1 2`
在[1,2]里的权值有1,1,2，有2种，因此答案为2。

`3 4 7 9`
子序列为`5 1 `
在[7,9]里的权值有5，有1种，因此答案为1。

`4 4 2 5`
子序列为`1`
没有权值在[2,5]中的，因此答案为0。

`2 3 4 7`
子序列为`4 5`
权值在[4,7]中的有4,5，因此答案为2。

建议使用输入/输出优化。


title: 【模板】拉格朗日插值

background: 这是一道模板题

description:
~~由小学知识可知~~ $n$ 个点 $(x_i,y_i)$ 可以唯一地确定一个多项式 $y = f(x)$。

现在，给定这 $n$ 个点，请你确定这个多项式，并求出 $f(k) \bmod 998244353$ 的值。

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

接下来 $n$ 行，第 $i$ 行两个整数 $x_i,y_i$。

outputFormat: 一行一个整数，表示 $f(k) \bmod 998244353$ 的值。


title: Preprefix sum

description:
前缀和（prefix sum）$S_i=\sum_{k=1}^i a_k$。

前前缀和（preprefix sum）则把 $S_i$ 作为原序列再进行前缀和。记再次求得前缀和第 $i$ 个是 $SS_i$。

给一个长度 $n$ 的序列 $a_1, a_2, \cdots, a_n$，有两种操作：

1. `Modify i x`：把 $a_i$ 改成 $x$。
2. `Query i`：查询 $SS_i$。

inputFormat:
第一行给出两个整数 $N,M$。分别表示序列长度和操作个数。
接下来一行有 $N$ 个数，即给定的序列 $a_1,a_2,\cdots,a_n$。
接下来 $M$ 行，每行对应一个操作，格式见题目描述。

outputFormat: 对于每个询问操作，输出一行，表示所询问的 $SS_i$ 的值。

samples:
5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

hint: $1\le N,M\le 10^5$，且在任意时刻 $0\le A_i\le 10^5$。


title: 清理雪道

description:
滑雪场坐落在 FJ 省西北部的若干座山上。

从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。

由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

inputFormat:
第一行一个整数 $n$ 代表滑雪场的地点的数量。

接下来的 $n$ 行，描述 $1$ 到 $n$ 号地点出发的斜坡。第 $i$ 行的第一个数为 $m_i$，后面共有 $m_i$ 个整数，由空格隔开，每个整数 $a_{i,j}$ 互不相同，代表从地点 $i$ 下降到地点 $a_{i,j}$ 的斜坡。

outputFormat: 一行一个整数，表示直升飞机的最少飞行次数。

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

对于 $100\%$ 的数据，$2 \le  n \le 100$，$1\le m_i < n$ 且每个地点至少有一个斜坡与之相连。


title: 城市旅行

description:
W 国地大物博，由 $n$ 座城市组成，共 $n-1$ 条双向道路连接其中的两座城市，且任意两座城市都可相互到达。

风景秀美的 W 国吸引了无数慕名而来的游客，根据游客对每座城市的打分，我们定义第 $i$ 座城市的美丽度为 $a_i$。一次从城市 $x$ 到城市 $y$ 的旅行，所获得的的愉悦指数为从城市 $x$ 到城市 $y$ 所有城市的美丽度之和（包括 $x$ 和 $y$）。我们定义这个值为 $H(x,y)$。

现在小 A 在城市 $X$，Sharon 在城市 $Y$，他们想知道如果在城市 $X$ 到城市 $Y$ 之间的所有城市中任选两座城市 $x$ 和 $y$（$x$ 可以等于 $y$），那么 $H(x,y)$ 的期望值是多少，我们记这个期望值为 $E(x,y)$。

当然，城市之间的交通状况飘忽不定，因此我们不能排除某些时刻某些道路将无法通行。某些时刻会突然添加新的道路。以及游客们审美观的改变，某些城市的美丽度也会发生变化。作为 W 国负责旅游行业的 T 君，他要求你来写一个程序来模拟上面的所有过程。

inputFormat:
第一行两个整数，$n,m$ 表示城市个数和操作个数。

接下来一行 $n$ 个整数，第 $i$ 个表示 $a_i$。
接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $u$ 和 $v$ 之间有一条路。
接下来 $m$ 行，是进行下面的操作：

- `1 u v` 如果城市 $u$ 和城市 $v$ 已经无直接连接的道路，则忽略这个操作，否则删除 $u,v$ 之间的道路。
- `2 u v` 如果城市 $u$ 和城市 $v$ 联通那么忽略。否则在 $u,v$ 之间添加一条道路。
- `3 u v d` 如果城市 $u$ 和城市 $v$ 不连通，那么忽略。否则将城市 $u$ 到城市 $v$ 的路径中所有城市（包括 $u$ 和 $v$）的美丽度都增加 $d$。
- `4 u v` 询问 $E(u,v)$ 的值。

outputFormat: 对于操作 4，输出答案，一个经过化简的分数 $\frac{p}{q}$。如果 $u$ 和 $v$ 不连通输出 `-1`。


title: [集训队作业2013] 城市规划

description:
刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了。

刚才说过，阿狸的国家有 $n$ 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。

为了省钱, 每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。

好了，这就是困扰阿狸的问题。换句话说，你需要求出 $n$ 个点的简单 (无重边无自环) 有标号无向连通图数目。

由于这个数字可能非常大, 你只需要输出方案数对 $1004535809$ ( $479 \times 2 ^{21} + 1$ ) 取模即可。

inputFormat: 仅一行一个整数 $n$

outputFormat: 仅一行一个整数，为方案数 $\bmod \space 1004535809$。


title: [国家集训队] 书堆

description:
蚂蚁是勤劳的动物，他们喜欢挑战极限?现在他们迎来了一个难题！蚂蚁居住在图书馆里，图书馆里有大量的书籍。书是形状大小质量都一样的矩形。蚂蚁要把这些书摆在水平桌子的边緣。蚂蚁喜欢整洁的布置，所以蚂蚁规定书本必须水平摆放，宽必须平行于桌緣（如图），而且不允许同一高度摆多本书。

![](https://cdn.luogu.com.cn/upload/pic/30575.png)

蚂蚁想要让书本伸出桌子边缘尽量远，同时不让书因为重力垮下来。它们己经用不知道什么方法测出了书的长度M(如图)。如果总共有N本书，请你帮忙计算如何摆放使得最多水平伸出桌缘多远。你不用考虑蚂蚁用什么方法搭建这堆书。

如果某本书以上的所有书的重心的竖直射影不在这本书上，或者正好落在在这本书的边界上，那么这堆书是不稳定的，会因为重力而垮下来。

考虑以下的假设：

- 不考虑地球自转，重力系数也不因高度改变；
- 书是质量均匀，质地坚硬的理想二维物体；
- 在不会垮的前提下，每本书的位置坐标可以是任意实数。

inputFormat: 第一行正整数 N M

outputFormat: 一行（有换行符），L，表示水平延伸最远的整数距离 (不大于答案的最大整数)


title: [中山市选] 生成树

description:
有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。

![https://cdn.luogu.com.cn/upload/pic/22665.png](https://cdn.luogu.com.cn/upload/pic/22665.png)

现在给定一个n五角形圈，你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗？一个图的生成树是保留原图的所有顶点以及顶点的数目减去一这么多条边,从而生成的一棵树。
注意：在给定的n五角形圈中所有顶点均视为不同的顶点。

inputFormat: 输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组测试数据包含一个整数n( 2<=N<=100)，代表你需要求解的五角形圈中心的边数。

outputFormat: 对每一组测试数据，输出一行包含一个整数x，表示n五角形圈的生成树数目模2007之后的结果。


title: [BJWC2012] 冻结

background:
“我要成为魔法少女！”

“那么，以灵魂为代价，你希望得到什么？”

“我要将有关魔法和奇迹的一切，封印于卡片之中„„”

在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。

现在，不需要立下契约也可以使用魔法了！你还不来试一试？

比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。

例如，我们熟知的 Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。当然，更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小巫见大巫了。

这说明之前的世界中有很多魔法少女曾许下控制时间的愿望，比如 Akemi Homura、Sakuya Izayoi、……

当然，在本题中我们并不是要来研究历史的，而是研究魔法的应用。

description:
我们考虑最简单的旅行问题吧： 现在这个大陆上有 $N$ 个城市，$M$ 条双向的道路。城市编号为 $1$ ~ $N$，我们在 $1$ 号城市，需要到 $N$ 号城市，怎样才能最快地到达呢？

这不就是最短路问题吗？我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。

现在，我们一共有 $K$ 张可以使时间变慢 50%的 SpellCard，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是：

1. 在一条道路上最多只能使用一张 SpellCard。
2. 使用一张SpellCard 只在一条道路上起作用。
3. 你不必使用完所有的 SpellCard。

给定以上的信息，你的任务是：求出在可以使用这不超过 $K$ 张时间减速的 SpellCard 之情形下，从城市 $1$ 到城市 $N$ 最少需要多长时间。

inputFormat:
第一行包含三个整数：$N$、$M$、$K$。

接下来 $M$ 行，每行包含三个整数：$A_i$、$B_i$、$Time_i$，表示存在一条  $A_i$ 与 $B_i$ 之间的双向道路，在不使用 SpellCard 之前提下，通过它需要 $Time_i$ 的时间。

outputFormat: 输出一个整数，表示从 $1$ 号城市到 $N$ 号城市的最小用时。

hint:
#### 样例 1 解释

在不使用 SpellCard 时，最短路为 $1 \to 2 \to 4$，总时间为 10。现在我们可以使用 1 次 SpellCard，那么我们将通过 $2 \to 4$ 这条道路的时间减半，此时总时间为7。

#### 数据规模与约定

对于 $100\%$ 的数据，保证：

- $1 \leq K \leq N \leq 50$，$M \leq 10^3$。
- $1 \leq A_i,B_i \leq N$，$2 \leq Time_i \leq 2 \times 10^3$。
- 为保证答案为整数，保证所有的 $Time_i$ 均为偶数。
- 所有数据中的无向图保证无自环、重边，且是连通的。


title: 已经没有什么好害怕的了

description:
已经使 Madoka 有签订契约，和自己一起战斗的想法后，Mami 忽然感到自己不再是孤单一人了呢。

于是，之前的谨慎的战斗作风也消失了，在对 Charlotte 的傀儡使用终曲——Tiro Finale 后，Mami 面临着即将被 Charlotte 的本体吃掉的局面。

这时，已经多次面对过 Charlotte 的 Homura 告诉了学 OI 的你这样一个性质：Charlotte 的结界中有两种具有能量的元素，一种是“糖果”，另一种是“药片”，各有 $n$ 个。在 Charlotte 发动进攻前，“糖果”和“药片”会两两配对，若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多 $k$ 组，则在这种局面下，Charlotte 的攻击会丟失，从而 Mami 仍有消灭 Charlotte 的可能。

你必须根据 Homura 告诉你的“糖果”和“药片”的能量的信息迅速告诉 Homura 这种情况的个数.

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

接下来一行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个糖果的能量。

接下来 $n$ 个整数，第 $j$ 个数表示第 $j$ 个药片的能量。

保证上面两行不会有重复的数字。

outputFormat: 一个答案，表示消灭 Charlotte 的情况个数，需要对 $10^9+9$ 取模。


title: [TJOI2013] 拯救小矮人

description:
一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，直到最顶端的小矮人伸直胳膊可以碰到陷阱口。

对于每一个小矮人，我们知道他从脚到肩膀的高度 $A_i$，并且他的胳膊长度为 $B_i$。陷阱深度为 $H$。

如果我们利用矮人 $1$，矮人 $2$，矮人 $3$，……，矮人 $k$ 搭一个梯子，满足 $A_1+A_2+A_3+\dots+A_k+B_k \geq H$，那么矮人 $k$ 就可以离开陷阱逃跑了，一旦一个矮人逃跑了，他就不能再搭人梯了。

我们希望尽可能多的小矮人逃跑，问最多可以使多少个小矮人逃跑。

inputFormat: 第一行一个整数 $N$，表示矮人的个数，接下来 $N$ 行每一行两个整数 $A_i$ 和 $B_i$，最后一行是 $H$。

outputFormat: 一个整数表示最多可以逃跑多少小矮人。


title: [CERC2017] Gambling Guide

description:
A railroad network in a nearby country consists of $n$ cities numbered $1$ through $n$, and $m$ two-way railroad tracks each connecting two different cities. Tickets can only be purchased at automated machines installed at every city. Unfortunately, hackers have tampered with the ticket machines and now they all work as follows: when a single coin is inserted in the machine installed at city $a$, the machine dispenses a single one-way ticket from $a$ to a random neighboring city. More precisely, the destination city is chosen uniformly at random among all cities directly connected to a with a railroad track. Destinations on different tickets originating in the same city are independent.

A computer science student needs to travel from city $1$ (where she lives) to city $n$ (where a regional programming contest has already started). She knows how the machines work (but of course cannot predict the random choices) and has a map of the railway network. In each city, when she purchases a ticket, she can either immediately use it and travel to the destination city on the ticket, or discard the ticket and purchase a new one. She can keep purchasing tickets indefinitely. The trip is finished as soon as she reaches city $n$.

After doing some calculations, she has devised a traveling strategy with the following properties:
  - The probability that the trip will eventually finish is $1$.
  - The expected number of coins spent on the trip is the smallest possible.

Find the expected number of coins she will spend on the trip.

inputFormat:
The first line contains two integers $n$ and $m(1 \le n,m \le 300 000)$ — the number of cities and the number of railroad tracks. Each of the following $m$ lines contains two different integers $a$ and $b(1 \le a, b \le n)$ which describe a railroad track connecting cities $a$ and $b$.

There will be at most one railroad track between each pair of cities. It will be possible to reach city $n$ starting from city $1$.

outputFormat: Output a single number — the expected number of coins spent. The solution will be accepted if the absolute or the relative difference from the judges solution is less than $10^{-6}$.

translation:
一个铁路系统由 $n$ 个城市和 $m$ 条双向铁路组成。铁路票只能在安装在每个城市的自动售票机购买。不幸的是，黑客们已经篡改了这些售票机，现在它们有下面的规则：

当 $a$ 市的售票机有一个硬币投入时，机器会发一张从 $a$ 市到随机一个邻市的单程票。

你需要从城市 $1$ 到城市 $n$。你知道机器是怎么工作的并且有一份铁路系统的地图。在每一个城市，当你买了一张票时，你可以选择立即使用它后到达目的地，或者是丢掉它并买一张新票。你可以无限制的购买的票。当你到达城市 $n$，旅行就会结束。

你需要确定一个满足以下条件的策略：

- 旅行最终到达终点的概率为 $1$。

- 花在旅行上的硬币的期望值越少越好。

输出这个期望值。

**【输入格式】**

第一行包含两个整数 $n$ 和 $m(1 \le n,m \le 300000)$。

接下来 $m$ 行每行包含了两个不同的整数 $a$ 和 $b(1 \le a,b \le n)$，描述了一条连接 $a$ 市和 $b$ 市的双向铁路。

两个城市之间最多只会有一条铁路，输入保证有一条从城市 $1$ 到 $n$ 的路径。

**【输出格式】**

输出一个数，为期望值。此输出只要与正解的相对差或绝对差小于 $10^{−6}$ 就可以通过。


title: 八百标兵奔北坡

background: baingbaboom正在往北边跑！！！

description:
现在在一张N*M的地图上有K只babingbaboom！！！对于一张地图上的点都有一个 $ h_{i,j} $ 来表示这个地方的高度。现在这些babingbaboom都想要跑到北边的一个山坡上。求出离每一个babingbaboom最近的靠北的山。

补充定义：

山：

山的周围没有比它更高的地方。(四联通)

在北边：

令Babingbaboom的坐标为$A(a,b)$，山的坐标为$B(x,y)$，山在Babingbaboom的北边当且仅当$dis_{A,B}==a-x$

切比雪夫距离:

$ A(x_1,y_1) \qquad B(x_2,y_2) : \qquad dis_{A,B}=max(|x_1 - x_2|, |y_1 - y_2|)$

inputFormat:
第1行三个正整数N,M,K。
第2-N+1行每行有M个正整数 $ h_{i,j} $ 。
第N+2-N+K+1行每行有两个正整数X_i,Y_i表示每一个babingbaboom的坐标。

outputFormat: K行。如果对于每一个babingbaboom存在这样的最近的山(切比雪夫距离)，就输出这个babingbaboom到山的切比雪夫距离；否则输出“Pool Babingbaboom!”(不要引号！(我知道可怜的是Poor，但是我就爱写Pool))

samples:
Pool Babingbaboom!
Pool Babingbaboom!
1
2
0

hint:
$$ 1 \leqslant  N,M \leqslant 1e3 $$
$$ 1 \leqslant  K \leqslant 1e5 $$
$$ 1 \leqslant  h_{i,j} \leqslant 1e9 $$
数据有梯度！

样例图片(星代表一个Babingbaboom，红色代表一个山)：
![](https://cdn.luogu.com.cn/upload/pic/22827.png)
(竖的是x，横的是y。画的时候没注意，很抱歉。)


title: 红鲤鱼与绿鲤鱼

background: JerryC家里除了有驴之外，还有一个有着红鲤鱼和绿鲤鱼的鱼缸。

description:
在JerryC家里的鱼缸里，有一些红鲤鱼和绿鲤鱼(鱼缸里没有驴！)这天晚上23:05的时候，JerryC闲的无聊，于是打开了某神秘OJ开始爆肝。。作为一名膜法师，JerryC可以通过预言术得知下一次自己的提交是对是错。当然，预言术使用的工具就是眼前的鱼缸了。每当JerryC的预言术指示一只红鲤鱼的时候，就说明这次提交会WA，同时会增加5min的罚时；如果是绿鲤鱼就会AC。(当然，由于JerryC的膜法，JerryC是不会番薯田扛把子的。JerryC第一次提交会在第5min，而且不幸的是JerryC的膜法有5min的冷却时间)并且JerryC在每一次预言后就会把预言到的那一只鲤鱼取出来，以便比赛完毕后给鱼缸换水~~(给自己换换口味)~~现在JerryC告诉你他家里有多少条红鲤鱼和绿鲤鱼，请你告诉他他这场比赛的罚时期望是多少。当然，JerryC会按顺序做题，并且罚时只会记录AC的题目，算罚时的时候需要加上AC的时间，并且所有的鲤鱼用完后还会提交一次，而且这一次JerryC并不会预测并且必定AC。）
由于JerryC脾气比较犟，所以他不会因为WA掉一道题而换一道题去做，除非AC。

inputFormat: 一行，两个正整数A，B，分别表示有多少条红鲤鱼和绿鲤鱼。

outputFormat: 一行，一个正整数，表示罚时的期望模998244853的结果。如果结果除不尽时，若结果可以表示为 $ \frac{P}{Q} $ ，则需要输出 $ P * Q^{mod-2} \% mod $  。

hint:
$$ 10 pts: 1 \leqslant A + B \leqslant 5 $$
$$ 30 pts: 1 \leqslant A + B \leqslant 20 $$
$$ 70 pts: 1 \leqslant A + B \leqslant 3000 $$
$$ 100 pts: 1 \leqslant A \leqslant 1e18, 1 \leqslant B \leqslant 1e7 $$

最后六个点时限2400ms！！！
其他点时限400ms！！！

$$ \color{white}{\text{温馨提示:注意模数}}$$

样例1:
有两种可能：
1. AC WA AC
2. WA AC AC

第一个情况的罚时是5(第5分钟AC)+5(WA一次罚时5分钟)+15(第15分钟AC)=25

第二个情况的罚时是5(WA一次罚时5分钟)+10(第10分钟AC)+15(第15分钟AC)=30

所以期望罚时为$ \frac{25+30}{2} = \frac{55}{2} $ 需要对分数取模，所以最后答案为499122454。


title: 灰化肥，会挥发

background: Farmer Justin 有一大堆会发黑和挥发的灰化肥呢！！！

description: 在 Farmer Justin 的农场中有许多灰化肥，它们都堆积在A仓库里。为了方便施肥，Farmer Justin 需要修一些公路使得他能用拖拉机把这些灰化肥拉到其他仓库里。由于 Farmer Justin 及其懒惰，所以他只想一次拉完所有的灰化肥送到其他仓库里。但是灰化肥见光易挥发，所以 Farmer Justin 需要尽快把这些灰化肥拉完。现在告诉你Farmer Justin农场的构成地图，请你帮帮他计划一条**从 A 仓库出发**走完所有仓库的方案吧！由于Farmer Justin 非常的讨厌浪费时间，所以你只需要告诉他最短的距离和走过所有农场的顺序。（注意：拖拉机走的时候是四联通的。）

inputFormat:
第一行三个正整数 $R,C,N$ 分别表示地图大小和仓库数量。
下面给出一个 $R$ 行 $C$ 列的地图，其中 `.` 表示空地，可以修建公路；`*` 表示是 Farmer Justin 的农业区，不可以修建公路；用大写字母表示仓库编号。

outputFormat:
第一行一个正整数表示最短的距离。

第二行表示拖拉机走过仓库的方案（由仓库编号组成的字符串）。若有多种方案，输出字典序最小的方案。

数据保证有解。

hint: 对于全部数据，$ 1 \leqslant R,C \leqslant 500 $，$ 1 \leqslant N \leqslant 16 $。