title: [USACO16JAN] Angry Cows G

background:
【题目描述】

奶牛Bessie设计了一个游戏：“愤怒的奶牛”。游戏的原型是：有一些可爆炸的草堆分布在一条数轴的某些坐标上，玩家用弹弓把一头奶牛发射到数轴上。奶牛砸到数轴上的冲击波会引发附近的草堆爆炸，而被引爆的草堆可能会引爆其他草堆。游戏的目标是玩家用一只奶牛炸掉所有的草堆。

有N个草堆在数轴的不同位置，坐标为x1,x2,….,xn。如果玩家以能量R把奶牛发射到坐标x，就会引爆半径R及以内的的草堆，即坐标范围[x−R,x+R]的草堆都会燃爆，每个被奶牛引爆的草堆又会2次引爆半径R-1及以内的的草堆，2次引爆的草堆又会3次引爆半径R-2及以内的的草堆...直到一次引爆后没有其他草堆被波及或半径为0。

现在只有1头奶牛，能量为R，请计算如果要引爆所有的草堆，最小的R是多少？

【输入格式】

第一行：1个整数N(2≤N≤50,000)。

下面有N行,每行一个整数：x1,x2,…,xn，范围在[0…1,000,000,000]。

【输出格式】

输出最小的能量R，保留1位小数。

感谢wenyu0909和世界第一弱的翻译。

description:
Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows".  The premise,  which she believes is completely original, is that the player shoots a cow with a slingshot  into a one-dimensional scene consisting of a set of hay bales located at various points on a number line; the cow lands with sufficient force to detonate the hay bales in close proximity to her landing site, which in turn might set of a chain reaction that causes additional hay bales to explode.  The goal is to use a single cow to start a chain reaction that detonates all the hay bales.

There are $N$ hay bales located at distinct integer positions $x_1, x_2, \ldots, x_N$ on the number line.  If a cow is launched with power $R$ landing at position $x$, this will causes a blast of "radius $R$", engulfing all hay bales within the range $x-R \ldo s x+R$.  These hay bales then themselves explode (all simultaneously), each with a blast radius of $R-1$.  Any not-yet-exploded bales caught in these blasts then all explode (all simultaneously) with blast radius $R-2$, and so on.

Please determine the minimum amount of power $R$ with which a single cow may be launched so that, if it lands at an appropriate location, it will cause subsequent detonation of every single hay bale in the scene.

inputFormat:
The first line of input contains $N$ ($2 \leq N \leq 50,000$).  The remaining

$N$ lines all  contain integers $x_1 \ldots x_N$ (each in the range

$0 \ldots 1,000,000,000$).

outputFormat:
Please output the minimum power $R$ with which a cow must be launched in order

to detonate all the hay bales.  Answers should be rounded and printed to exactly

1 decimal point.

hint:
In this example, a cow launched with power 3 at, say, location 5, will cause

immediate detonation of  hay bales at positions 3 and 8.  These then explode

(simultaneously) each with blast radius 2, engulfing bales at positions 1 and

10, which next explode (simultaneously) with blast radius 1, engulfing the final

bale at position 11, which finally explodes with blast radius 0.


title: [USACO16JAN] Radio Contact G

type: P

description:
Farmer John has lost his favorite cow bell, and Bessie the cow has agreed to help him find it!  They both fan out and search the farm along different paths, but stay in contact via radio so they can keep in touch with each-other. Unfortunately, the batteries in their radios are running low, so they want to plan their movements so as to conserve power, by trying to stay always within a short distance apart.

Farmer John starts at location ($f_x, f_y$) and plans to follow a path consisting of  $N$ steps, each of which is either 'N' (north), 'E' (east), 'S' (south), or 'W' west.  Bessie starts at location ($b_x, b_y$) and follows a similar path consisting of $M$ steps.  Both paths may share points in common.  At each time step, Farmer John can either stay put at his current location, or take one step forward along his path, in whichever direction happens to be next (assuming he has not yet reached the final location in his path). Bessie can make a similar choice.  At each time step (excluding the first step where they start at their initial locations), their radios consume energy equal to the square of the distance between them.

Please help FJ and Bessie plan a joint movement strategy  that will minimize the total amount of energy consumed up to and including the final step where both of them first reach the final locations on their respective paths.

inputFormat:
The first line of input contains $N$ and $M$ ($1 \leq N, M \leq 1000$).   The

second line contains integers $f_x$ and $f_y$, and the third line contains $b_x$

and $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). The next line contains  a

string of length $N$ describing FJ's path, and the final line contains a string

of  length $M$ describing Bessie's path.

It is guranteed that Farmer John and Bessie's coordinates are always in the

range ($0 \leq x,y \leq 1000$) throughout their journey.  Note that East points in the positive x direction and North points in the positive y direction.

outputFormat:
Output a single integer specifying the minimum energy FJ and Bessie can use

during their travels.

translation:
FJ 失去了他最喜欢的牛铃，而 Bessie 已经同意帮助他找到它！他们用不同的路径搜索农场，通过无线电保持联系。

不幸的是，无线电中的电池电量不足，所以他们设法尽可能保持两者位置的距离最小，以节省电量。

FJ 从位置$(f_x,f_y)$ 开始，并计划遵循由 $N$ 步组成的路径.Bessie 从位置 $(b_x,b_y)$ 开始，并遵循由 $M$ 步组成的路径。每个步骤都是 `N`（北），`E`（东），`S`（南），或`W`（西）。其中，东方向为 $x$ 轴正方向，北方向为 $y$ 轴正方向。两个路径可以经过相同的点。

在每个时间段，FJ 可以不移动，也可以沿着他的道路前进一步。无论哪个方向恰好在下一个（假设他还没有到达他的路径的最后位置）。Bessie 可以做出类似的选择。

在每个时间点（不包括从初始位置开始的第一步），他们的无线电消耗的能量等于它们之间距离的平方。

请帮助 FJ 和 Bessie 计划行动策略，使双方达到各自终点时，最大限度地减少消耗的能量总量。输出所消耗的最小的能量。

### 输入格式

第一行两个整数 $N$ 和 $M$ $(1\le N,M\le 1000)$。

第二行两个整数 $f_x$ 和 $f_y$。

第三行两个整数 $b_x$ 和 $b_y$ $(0\le f_x,f_y,b_x,b_y\le 1000)$。

下一行为一个长度为 $N$ 的字符串，描述 FJ 的路径。

最后一行为一个长度 $M$ 的字符串，描述 Bessie 的路径。

### 输出格式

共一行一个整数，表示最小能量。


title: [USACO16JAN] Lights Out G

description:
Farmer John has installed a fancy new milking machine in his barn, but it draws so much power that it occasionally causes the power to go out! This happens so often that Bessie has memorized a map of the barn, making it easier for her to find the exit of the barn in the dark. She is curious though about the impact of power loss on her ability to exit the barn quickly. For example, she wonders how much farther she might need to walk find the exit in the dark.

The barn is described by a simple (non self-intersecting) polygon with integer  vertices $(x_1, y_1) \ldots (x_n, y_n)$ listed in clockwise order.  Its edges alternate between horizontal (parallel to the x-axis) and vertical (parallel to the y-axis); the first edge can be of either type. The exit is located at

$(x_1, y_1)$.  Bessie starts inside the barn located at some vertex  $(x_i, y_i)$ for $i > 1$.  She can walk only around the perimeter of the barn, either clockwise or counterclockwise, Her goal is to travel a minimum distance to reach the exit. This is relatively easy to do with the lights on, of course, since she will travel either  clockwise or counterclockwise from her current location to the  exit -- whichever direction is shorter.

One day, the lights go out, causing Bessie to panic and forget which vertex she is standing at.  Fortunately, she still remembers the exact map of the barn, so she can possibly figure out her position by walking around and using her sense of touch.  Whenever she is standing at a vertex (including at her initial vertex), she can feel the exact interior angle at that vertex, and she can tell if that vertex is the exit.  When she walks along an edge of the barn, she can determine the exact length of the edge after walking along the entire edge.  Bessie decides on the following strategy: she will move clockwise around the perimeter of the barn until she has felt enough angles and edges to deduce the vertex at which she is currently located.  At that point, she can easily figure out how to get to the exit by traveling a minimum amount of remaining distance, either by continuing to move clockwise or by switching direction and moving counter-clockwise.

Please help Bessie determine the largest amount by which her travel distance will increase in the worst case (over all possibilities for her starting vertex) for travel in the dark versus in a lit barn.

inputFormat:
The first line of the input contains $N$ ($4 \leq N \leq 200$).  Each of the

next $N$ lines contains two integers, describing the points $(x_i, y_i)$ in

clockwise order around the barn.  These integers are in the range

$-100,000 \ldots 100,000$.

outputFormat:
Output the largest amount that Bessie's travel distance will increase in the

worst case starting position using the strategy in the problem statement.

translation:
### 题目描述

Farmer John 在他的谷仓里安装了一个非常不错的新挤奶机，但是这台挤奶机耗电太多了，有时候会让谷仓直接停电！这种事发生的太频繁了，以至于 Bessie 直接把谷仓的地图背过了，以便于可以在黑暗中找到谷仓的出口。她对于停电对于她快速离开谷仓的能力的影响非常好奇。比如说，她想知道她在黑暗中需要走多远来找到谷仓的出口。

谷仓里的路可以被描述为是一个简单的用几个顶点来表示的多边形，这些顶点可以按照顺时针被表示为 $(x_1, y_1) \cdots (x_n, y_n)$（保证这些顶点连成的线没有交叉的情况）。这些点构成的边在水平轴（平行于 $x$ 轴）和竖直轴（平行于 $y$ 轴）之间交替出现。第一条边可以是任意一种类型。谷仓出口在坐标 $(x_1, y_1)$ 。Bessie 从谷仓内任意一个点 $(x_i, y_i)$ 开始走。她只可以沿着这些边走，要不然是顺时针，要不然就是逆时针，她的目标就是以最短距离抵达出口。当然，如果灯亮着的话这个事还算相对简单，因为她要不然顺时针要不然逆时针走，无所谓哪个方向的路程更短一点。

一天，谷仓突然停电了，导致 Bessie 受到惊吓、忘记了她站在哪个顶点。幸亏她还记得谷仓的准确地图，所以她可以四处走走，用她的触觉来弄清楚她的位置。不管什么时候，只要她站在一个顶点，那么她就可以感受到她在这个点的朝向角度，弄清楚这个点是不是出口。当她沿着谷仓的一个边走完的时候，她可以算出精确的边长。Bessie 决定用这么一个策略：她会顺时针沿着谷仓周围的边走，直到她知道了足够的角度和边、可以推断出她目前在的是哪个顶点。在那个顶点，她就可以轻易地弄清楚怎样以最短距离到达出口（要不然继续沿着顺时针走，要不然倒回去沿着逆时针走）。

请帮助 Bessie 算出在起点可以是任何一个顶点情况下，在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

### 输入格式

第一行包括一个数字 $N (4 \leqslant N \leqslant 200)$ ，接下来 $N$ 行，每行包括两个数字，沿着顺时针表示顶点 $(x_i, y_i)$   $x_i, y_i \in [-10^5, 10^5]$ 。

### 输出格式

输出 Bessie 在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

### 说明/提示

在这个样例中，Bessie 开始可以感觉到她沿着 $90 \degree$ 角站着，但是她辨别不出来她是在 $2, 3, 4$ 中的哪一个顶点。

在走了一条边以后，Bessie 要不然到了出口要不然就可以根据她走过的距离推断出她的位置。情况如下：

如果她从 $2$ 号点开始走，她需要在黑暗中走 $12$ 个单位，包括一个单位到达第三个点、十一个单位离开谷仓。同时，如果亮着灯，她可以只走 $10$ 个单位就离开谷仓。差值是 $2$ 。

如果从 $3$ 号点开始，她两种情况都要走 $11$ 个单位。

如果从 $4$ 号点开始，她两种情况都要走 $1$ 个单位。

所以最坏情况差值是 $2$ 。

hint:
In this example, Bessie can feel that she is initially standing at a 90-degree

angle, but she cannot tell if she is initially standing at vertex 2, 3, or 4.

After taking a step along one edge in the clockwise direction, Bessie either

reaches the exit or can uniquely determine her location based on the length of

this edge.  The distances she obtains are:

If starting at vertex 2: she travels 12 units in the dark (1 unit to reach

vertex 3, then 11 units to continue to the exit).  She only needs to travel 10

units in a lit barn.  This is an extra distance of 2 for this vertex.

If starting at vertex 3: she travels 11 units in both cases.

If starting at vertex 4: she travels 1 unit in both cases.

The worst-case difference over all starting points is therefore 12 - 10 = 2.  That

is, Bessie can guarantee that using her strategy, no matter where she starts,

she will travel at most 2 extra units of distance farther in the dark than in the light.


title: [USACO16JAN] Fort Moo P

description:
Bessie is building a fort with her friend Elsie. Like any good fort, this one needs to start with a sturdy frame. Bessie wants to build a frame in the shape of a one-meter-wide rectangular outline, atop which she will build the fort.

Bessie has already chosen a site on which to build the fort -- a piece of land measuring $N$ meters by $M$ meters ($1 \leq N, M \leq 200$). Unfortunately, the  site has some swampy areas that cannot be used to support the frame.  Please help Bessie determine the largest area she can cover with her fort (the area of

the rectangle supported by the frame), such that the frame avoids sitting on any of the swampy areas.

奶牛 Bessie 和 Elsie 正在建她们的城堡。这个城堡有一个框架，框架为长方形。现在输入一个 $n \times m$ 的地图，标注 `.` 为平地，标注 `X` 为沼泽地。框架的任何一点都不能出现在沼泽地上，求最大框架面积。

inputFormat:
Line 1 contains integers $N$ and $M$.

The next $N$ lines each contain $M$ characters, forming a grid describing the

site.  A character of '.' represents normal grass, while 'X' represents a swampy

spot.

outputFormat:
A single integer representing the maximum area that Bessie can cover with her

fort.

hint:
In the example, the placement of the optimal frame is indicated by 'f's below:

```cpp
.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...
```


title: [USACO16JAN] Mowing the Field P

description:
Farmer John is quite reliable in all aspects of managing his farm, except one: he is terrible at mowing the grass in a timely fashion.   He only manages to move the mowing machine once per day, in fact. On day 1, he starts at position $(x_1, y_1)$ and on day $d$ he mows along a straight segment to the position $(x_d, y_d)$, moving either horizontally or vertically on the 2D map of his farm; that is, either  $x_d = x_{d-1}$, or $y_d = y_{d-1}$.  FJ alternates between horizontal and vertical moves on successive days.

So slow is FJ's progress that some of the grass he mows might grow back before he is finished with all his mowing. Any section of grass that is cut in day $d$ will reappear on day $d + T$, so if FJ's mowing path crosses a path he cut at least $T$ days earlier, he will end up cutting grass at the same point again.  In an effort to try and reform his poor mowing strategy, FJ would like to count the number of times this happens.

Please count the number of times FJ's mowing path crosses over an earlier segment on which grass has already grown back.  You should only count "perpendicular" crossings, defined as a point in common between a horizontal and a vertical segment that is an endpoint of neither.

inputFormat:
The first line of input contains $N$ ($2 \leq N \leq 100,000$) and $T$

($1 \leq T \leq N$, $T$ even).

The next $N$ lines describe the position of the mower on days $1 \ldots N$.  The

$i$th of these lines contains integers $x_i$ and $y_i$ (nonnegative integers

each at most 1,000,000,000).

outputFormat:
Please output a count of the number of crossing points described above, where FJ

re-cuts a point of grass that had grown back after being cut earlier.

translation:
FJ 在给农场除草。

FJ 第一天位于坐标 $(x_1,y_1)$，此后的每一天，FJ 都会水平或竖直地移动到另一个坐标并除去其上的草。具体而言：我们认为 $(x,y)\rightarrow (x+k,y)$ 视为一次水平移动，$(x,y)\rightarrow (x,y+k)$ 视为一次竖直移动。

FJ 在连续的两天内不会使用同一种移动方式进行移动，即 FJ 使用水平移动以及竖直移动是**交替**的。

FJ 在第 $d$ 天除去的草会在 $d+T$ 天再次生长出来，其中 $T$ 是一个**偶数**。

如果某次移动与先前的另外一次移动垂直交叉（即其中一个是水平移动，另外一个是竖直移动）且满足先前一次除去的草已经再次生长，那么就产生一次计数。

FJ 想知道，按照当前计划进行除草会产生多少次计数。

### 形式化题意

现给出 $n$ 个点，其中，第 $i$ 个点和第 $i+1$ 个点相连必定构成一条水平或竖直的线段，记为线段 $i$。显然线段 $i$ 必定与线段 $i+1$ 共用一个端点。

额外保证线段 $i$ 必定与线段 $i+1$ 垂直。

对于某条线段 $d$，你需要统计出线段 $1\cdots d-T$ 中有多少条与线段 $d$ 相交且垂直，记为 $f_d$。

输出 $ans$，其中 $ans=\sum_{i=1}^{n-1} f_i$。

hint:
Here, FJ crosses on day 7 a segment of grass he cut on day 2, which counts. The

other intersections do not count.

Note: This problem has expanded limits: 5 seconds per test case (10 for Python and Java), and 512 MB of memory.


title: [USACO16FEB] Circular Barn S

background: *本题与 [金组同名题目](/problem/P6170) 在题意上一致，唯一的差别是数据范围。*

description:
作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部 $n$ 个房间排成环形（$3 \leq n \leq 1000$），按顺时针顺序编号为 $1\ldots n$，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。

现在 FJ 有 $n$ 头奶牛，他的目标是让每个房间恰好有一头奶牛。然而不幸的是，现在奶牛们随意呆在某个房间里，第 $i$ 个房间里有 $c_i$ 头奶牛。保证 $\sum c_i =n$。

FJ 决定采用这样的方法来解决这个问题：让某些奶牛**顺时针**穿过某些房间到达指定的位置。如果一头奶牛穿过了 $d$ 扇门，他消耗的能量为 $d^2$。你需要帮 FJ 算出所有奶牛消耗的能量和最小值是多少。

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

outputFormat: 输出所有奶牛最小消耗能量和。


title: [USACO16FEB] Load Balancing S

background: *本题与 [白金组同名题目](/problem/P6172) 在题意上一致，唯一的差别是数据范围。*

description:
Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 1000$）散布在整个农场上。整个农场是一个无限大的二维平面，第 $i$ 头奶牛的坐标是 $(x_i,y_i)$（保证 $x_i,y_i$ 均为正奇数，且 $x_i,y_i \leq 10^6$），且没有任意两头奶牛在同一位置上。

FJ 希望修建一条竖直方向的栅栏，它的方程是 $x=a$，他还希望修建一条水平方向的栅栏，它的方程是 $y=b$。为了防止栅栏经过奶牛，$a,b$ 均要求是偶数。容易发现，这两个栅栏会在 $(a,b)$ 处相交，将整个农场分割为四个区域。

FJ 希望这四个区域内的奶牛数量较为均衡，尽量避免一个区域奶牛多而另一个区域奶牛少的情况。令 $M$ 为四个区域里奶牛最多区域的奶牛数量，请帮 FJ 求出 $M$ 的最小值。

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

接下来 $N$ 行，每行两个整数 $x_i,y_i$，描述第 $i$ 头奶牛的位置。

outputFormat: 输出 $M$ 的最小值。


title: [USACO16FEB] Milk Pails S

description:
Farmer John has received an order for exactly $M$ units of milk ($1 \leq M \leq 200$) that he needs to fill right away.  Unfortunately, his fancy milking machine has just become broken, and all he has are two milk pails of integer sizes $X$ and $Y$ ($1 \leq X, Y \leq 100$) with which he can measure milk.  Both pails are initially empty.  Using these two pails, he can perform up to $K$ of the following types of operations ($1 \leq K \leq 100$):

- He can fill either pail completely to the top.

- He can empty either pail.

- He can pour the contents of one pail into the other, stopping when the former becomes empty or the latter becomes full (whichever of these happens first).

Although FJ realizes he may not be able to end up with exactly $M$ total units of milk in the two pails, please help him compute the minimum amount of error between $M$ and the total amount of milk in the two pails.  That is, please compute the minimum value of $|M-M'|$ such that FJ can construct $M'$ units of milk collectively between the two  pails.

FJ 最近刚收到了解决 $M$（$1 \leq m \leq 200$）个单位牛奶的指令。他有两个桶，大小分别为 $X, Y$（$1 \leq X, Y \leq 100$）。

他可以选择执行如下操作 $k$（$1 \leq k \leq 100$）次：

他可以在任意一个桶中装满牛奶；他可以倒空任意一个桶；他可以将一个桶里的奶倒入另一个桶中，直到倒空或另一个桶被倒满

尽管 FJ 意识到他可能不能在两个桶中刚好装下 $M$ 个单位的牛奶，但请你算出他经过操作后，两桶牛奶的和同 $M$ 的差值最小是多少。

inputFormat: The first, and only line of input, contains $X$, $Y$, $K$, and $M$.

outputFormat: Output the smallest distance from $M$ to an amount of milk FJ can produce.

hint:
In two steps FJ can be left with the following quanities in his pails

```cpp
(0, 0) = 0 units
(14, 0) = 14 units
(0, 50) = 50 units
(0, 14) = 14 units
(14, 36) = 50 units
(14, 50) = 64 units
```

The closest we can come to 32 units is 14 for a difference of 18.  Note that it

would require an extra step to pour out the first pail to end up with (0, 36).


title: [USACO16FEB] Circular Barn Revisited G

description:
After the last debacle involving Farmer John's circular barn, one would think he had learned his lesson about non-traditional architecture.  However, he thinks he can still make his circular barn (from the preceding problem) function properly by allowing multiple cows into each room.  To recap, the barn consists of a ring of $n$ rooms,  numbered clockwise from $1 \ldots n$ around the perimeter of the barn ($3 \leq n \leq 100$).  Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.

Farmer John wants exactly $r_i$ cows to end up in room $i$ ($1 \leq r_i \leq 1,000,000$). To herd the cows into the barn in an orderly fashion, he plans to unlock $k$ exterior doors ($1 \leq k \leq 7$), allowing the cows to enter through only those doors. Each cow then walks clockwise through the rooms until she reaches a suitable destination.  Farmer John wants to unlock the exterior doors that will cause his cows to collectively walk a minimum total amount of distance after entering the barn (they can initially line up however they like outside the $k$ unlocked doors; this does not contribute to the total distance in question).  Please determine the minimum total distance his cows will need to walk, if he chooses the best $k$ such doors to unlock.

还是这个谷仓，有n(3<=n<=100)个房间。当然，奶牛可能不止n头了。奶牛都在谷仓外面。现在约翰想要让第i个房间关ri（1<=ri<=1000000）头奶牛按顺时针方向走，直到到达合适的房间。这k(1<=k<=7)个门开在哪里，才能使得奶牛们走的路程最少。奶牛在谷仓外可以随意移动，可以随意选择k个门中的任意一个排队，这不计入最终的路程。

inputFormat:
The first line of input contains $n$ and $k$.  Each of the remaining $n$ lines

contain $r_1 \ldots r_n$.

outputFormat: Please write out the minimum amount of distance the cows need to travel.

hint:
Farmer John can unlock doors 2 and 5.  11 cows enter at door 2 and walk a total

distance of 8 to get to rooms 2, 3, and 4.  10 cows enter at door 5 and walk a

total distance of 6 to get to rooms 5, 6 and 1.


title: [USACO16FEB] Fenced In P

background: *本题和 [金组同名题目](/problem/P6171) 在题意上一致，唯一的不同是数据范围。*

description:
Farmer John 意识到他的奶牛最近患上了一种恐惧症（害怕过于开阔的空间）。为了减少放牧的恐惧，FJ 决定在牧场中建一些水平和竖直方向的栅栏来将牧场分成若干个小区域。

整个牧场是一个矩形，两个角的坐标分别为 $(0,0)$ 和 $(A,B)$。FJ 在 $a_1,\ldots ,a_n$ 这 $n$ 个两两不同的位置建造了竖直方向的栅栏，每个栅栏从 $(a_i,0)$ 到 $(a_i,B)$；FJ 在 $b_1,\ldots ,b_m$ 这 $m$ 个两两不同的位置建造了水平方向的栅栏，每个栅栏从 $(0,b_i)$ 到 $(A,b_i)$。竖直方向的栅栏和水平方向的栅栏两两相交，将整个牧场分割成 $(n+1)(m+1)$ 个区域。

不幸的是，FJ 忘记了在栅栏上开门，奶牛都只能被困在一个个的小区域里！他想通过去掉一些栅栏来解决这个问题。他一次可以选择两个相邻的区域，将隔离这两个区域的栅栏去掉。FJ 的目标是让奶牛能够抵达牧场的任意一个地方。

这是一个例子：

```plain
+---+--+
|   |  |
+---+--+
|   |  |
|   |  |
+---+--+
```

去掉一些栅栏后的效果是这样的：

```plain
+---+--+
|      |
+---+  +
|      |
|      |
+---+--+
```

为了降低工程量，FJ 当然希望拆除的栅栏长度最短。

inputFormat:
第一行四个整数 $A,B,n,m$，保证 $1 \leq n,m \leq 2.5 \times 10^5$，$1 \leq A,B \leq 10^9$。

接下来 $n$ 行，第 $i$ 行一个整数 $a_i$，保证 $0 \lt a_i \lt A$。

接下来 $m$ 行，第 $i$ 行一个整数 $b_i$，保证 $0 \lt b_i \lt B$。

outputFormat: 输出拆除栅栏的最小长度。**答案需要用 64 位带符号整数存储。**


title: [USACO16OPEN] Field Reduction S

description:
Farmer John's $N$ cows ($5 \leq N \leq 50,000$) are all located at distinct positions in his two-dimensional field.  FJ wants to enclose all of the cows with a rectangular fence whose sides are parallel to the x and y axes, and he wants this fence to be as small as possible so that it contains every cow (cows on the boundary are allowed).

FJ is unfortunately on a tight budget due to low milk production last quarter. He would therefore like to build an even smaller fenced enclosure if possible, and he is willing to sell up to three cows from his herd to make this possible.

Please help FJ compute the smallest possible area he can enclose with his fence after removing up to three cows from his herd (and thereafter building the tightest  enclosing fence for the remaining cows).

For this problem, please treat cows as points and the fence as a collection of four line segments (i.e., don't think of the cows as "unit squares").  Note that the answer can be zero, for example if all remaining cows end up standing  in a common vertical or horizontal line.

农夫约翰的N(5<=N<=50000)头牛被定在了平面内的不同的位置。他想用栅栏(平行于x和y轴)围住所有的牛。他想这个栅栏尽可能小(牛在边界上也被视作围住)。

他因为牛奶产量低而感到经费紧张，所以他想卖掉三头牛再围起剩下的牛。请算出栅栏围出的最小面积。

inputFormat:
The first line of input contains $N$.  The next $N$ lines each contain two

integers specifying the location of a cow.  Cow locations are positive integers

in the range $1 \ldots 40,000$.

outputFormat:
Write a single integer specifying the minimum area FJ can enclose with his fence

after removing up to three carefully-chosen cows from his herd.


title: [USACO16OPEN] Diamond Collector S

description:
Bessie the cow, always a fan of shiny objects, has taken up a hobby of mining diamonds in her spare time!  She has collected $N$ diamonds ($N \leq 50,000$) of varying sizes, and she wants to arrange some of them in a pair of  display cases in the barn.

Since Bessie wants the diamonds in each of the two cases to be relatively similar in  size, she decides that she will not include two diamonds in the same case if their sizes differ by more than $K$ (two diamonds can be displayed together in the same case if their sizes differ by exactly $K$).  Given $K$, please help Bessie determine the maximum number of diamonds she can display in both cases together.

奶牛Bessie很喜欢闪亮亮的东西（Baling~Baling~），所以她喜欢在她的空余时间开采钻石！她现在已经收集了N颗不同大小的钻石（N<=50,000），现在她想在谷仓的两个陈列架上摆放一些钻石。

Bessie想让这些陈列架上的钻石保持相似的大小，所以她不会把两个大小相差K以上的钻石同时放在一个陈列架上（如果两颗钻石的大小差值不大于K，那么它们可以同时放在一个陈列架上）。现在给出K，请你帮Bessie确定她最多一共可以放多少颗钻石在这两个陈列架上。

inputFormat:
The first line of the input file contains $N$ and $K$ ($0 \leq K \leq 1,000,000,000$).

The next $N$ lines each contain an integer giving the size of one of the

diamonds.  All sizes will be positive and will not exceed $1,000,000,000$.

outputFormat:
Output a single positive integer, telling the maximum number of diamonds that

Bessie can showcase in total in both the cases.


title: [USACO16OPEN] Closing the Farm S

background: *本题和 [金组同名题目](/problem/P6121) 在题意上一致，唯一的不同是数据范围。*

description:
FJ 和他的奶牛们正在计划离开小镇做一次长的旅行，同时 FJ 想临时地关掉他的农场以节省一些金钱。

这个农场一共有被用 $M$ 条双向道路连接的 $N$ 个谷仓（$1 \leq N,M \leq 3000$）。为了关闭整个农场，FJ 计划每一次关闭掉一个谷仓。当一个谷仓被关闭了，所有的连接到这个谷仓的道路都会被关闭，而且再也不能够被使用。

FJ 现在正感兴趣于知道在每一个时间（这里的“时间”指在每一次关闭谷仓之前的时间）时他的农场是否是“全连通的”——也就是说从任意的一个开着的谷仓开始，能够到达另外的一个谷仓。注意自从某一个时间之后，可能整个农场都开始不会是“全连通的”。

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

接下来 $M$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条连接 $u,v$ 两个农场的路。

最后 $N$ 行每行一个整数，表示第 $i$ 个被关闭的农场编号。

outputFormat:
输出 $N$ 行，每行包含 `YES` 或 `NO`，表示某个时刻农场是否是全连通的。

第一行输出最初的状态，第 $i$ 行（$2 \leq i \leq N$）输出第 $i-1$ 个农场被关闭后的状态。


title: [USACO16OPEN] Splitting the Field G

description:
Farmer John's $N$ cows ($3 \leq N \leq 50,000$) are all located at distinct positions in his two-dimensional field.  FJ wants to enclose all of the cows with a rectangular fence whose sides are parallel to the x and y axes, and hewants this fence to be as small as possible so that it contains every cow (cowson the boundary are allowed).

FJ is unfortunately on a tight budget due to low milk production last quarter.He would therefore like to enclose a smaller area to reduce maintenance costs,and the only way he can see to do this is by building two enclosures instead of one.  Please help him compute how much less area he needs to enclose, in total,by using two enclosures instead of one.  Like the original enclosure, the two enclosures must collectively contain all the cows (with cows on boundaries allowed), and they must have sides parallel to the x and y axes.  The two enclosures are not allowed to overlap -- not even on their boundaries. Note that enclosures of zero area are legal, for example if an enclosure has zero width and/or zero height.在一个二维的牧场中，Farmer John的N（3<=N<=50000）头牛都各占一席。他想用边平行于x轴和y轴的矩形围栏围住所有牛，并且要让围栏尽可能小（牛可以在边界线上）。

不幸地，由于Farmer John的奶牛产量惨淡，导致最后一个季度预算紧张。因此，他希望封闭一个较小的地区来减少维修的费用，他能看到的唯一方法就是修建两个围栏而不是建一个。请编程告诉他用两个围栏比用一个围栏总共能够节省多少需要围住的面积。同样地，用两个围栏的时候必须围住所有的牛（牛同样可以在边界上），边也要平行于x轴和y轴。两个围栏不允许重叠（边界也不能）。注意面积为零是合法的，例如一个围栏有着长度为零的宽或长度为零的长（一条线）。

inputFormat:
The first line of input contains $N$.  The next $N$ lines each contain two

integers specifying the location of a cow.  Cow locations are positive integers

in the range $1 \ldots 1,000,000,000$.

outputFormat:
Write a single integer specifying amount of total area FJ can save by using two

enclosures instead of one.


title: [USACO16OPEN] 248 G

description:
Bessie likes downloading games to play on her cell phone, even though she  doesfind the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing.The game starts with a sequence of $N$ positive integers ($2 \leq N\leq 248$), each in the range $1 \ldots 40$.  In one move, Bessie cantake two adjacent numbers with equal values and replace them a singlenumber of value one greater (e.g., she might replace two adjacent 7swith an 8).  The goal is to maximize the value of the largest numberpresent in the sequence at the end of the game.  Please help Bessiescore as highly as possible!

inputFormat:
The first line of input contains $N$, and the next $N$ lines give the sequence

of $N$ numbers at the start of the game.

outputFormat: Please output the largest integer Bessie can generate.

translation: 给定一个 $1\times n\,(2\le n\le248)$ 的地图，在里面玩 2048，每次可以合并两个相邻且相同的数（数值范围 $1\sim 40$），问序列中出现的最大数字的值最大是多少。注意合并后的数值并非加倍而是 $+1$，例如 $2$ 与 $2$ 合并后的数值为 $3$。

hint:
In this example shown here, Bessie first merges the second and third 1s to

obtain the sequence 1 2 2, and then she merges the 2s into a 3.  Note that it is

not optimal  to join the first two 1s.


title: [USACO16OPEN] 262144 P

description:
Bessie likes downloading games to play on her cell phone, even though she  doesfind the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing.The game starts with a sequence of $N$ positive integers ($2 \leq N\leq 262,144$), each in the range $1 \ldots 40$.  In one move, Bessiecan take two adjacent numbers with equal values and replace them asingle number of value one greater (e.g., she might replace twoadjacent 7s with an 8). The goal is to maximize the value of thelargest number present in the sequence at the end of the game.  Pleasehelp Bessie score as highly as possible!

Bessie 喜欢在手机上下游戏玩，然而她蹄子太大，很难在小小的手机屏幕上面操作。

她被她最近玩的一款游戏迷住了，游戏一开始有 $n$ 个正整数（$2 \leq n \leq 262144$），范围在 $1 \sim 40$。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个 $7$ 合并成一个 $8$)，目标是使得最大的数最大，请帮助 Bessie 来求最大值。

hint:
In this example shown here, Bessie first merges the second and third 1s to

obtain the sequence 1 2 2, and then she merges the 2s into a 3.  Note that it is

not optimal to join the first two 1s.


title: [USACO16OPEN] Bull in a China Shop P

description:
Farmer John has decided his home needs more decoration.  Visiting the local china shop, he finds a delicate glass cow figurine that he decides to purchase, knowing that it will fit perfectly on the mantel above his fireplace.

The shape of the cow figurine is described by an $N \times M$ grid of haracters

like the one below ($3 \leq N, M \leq 500$), where lowercase letter characters are each part of the figurine (indicating different colors) and '.' characters are not.

```cpp
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
```

Unfortunately, right before FJ can make his purchase, a bull runs through the shop  and breaks not only FJ's figurine, but many of the other glass objects on the shelves as well!  FJ's figurine breaks into 3 pieces, which quickly becomelost  among $K$ total pieces lying on the ground ($4 \leq K \leq 100$).  Each ofthe $K$ pieces is described by a grid of characters, just like the originalfigurine.

Please help FJ determine how many sets of 3 pieces (out of the $K$ on the floor)could be glued back together to mend his broken figurine.

The pieces on the ground might have been flipped vertically or horizontally, orrotated by some multiple of 90 degrees. Therefore, given the original grid aswell as $K$ grids describing pieces, you want to find sets of 3 pieces that canbe joined together to form the original picture, allowing the pieces to betranslated, flipped, or rotated multiples of 90 degrees.  When thensuperimposed, the 3 pieces should exactly form the original picture, with eachcolored square in the original picture represented in exactly one of the pieces.

FJ想买点饰品摆在家里，逛了陶瓷商店后，看上了一个玻璃牛摆件，“放在俺家的壁炉架上太合适了”

牛摆件的形状用N\*M的字符矩阵来描述，.代表空区域，其他不同的小写字母代表不同的颜色。

不幸的是，就在FJ决定购买的时候，一头公牛冲过商店（出题人是西班牙的吗），打碎了好多商品，FJ的雕像碎成了3块，地板（4<=k<=100）上散落了一地碎片 ,碎片也用一个矩阵描述，碎片的方向可能垂直、水平，或者90倍数的旋转。

请从这些碎片中找出，有多少组（i，j，k）可以组成原来的牛。

例如结样例输出中的3，可以是（0,1,2）（0,2,4）（1,3,4） 组

inputFormat:
The first line contains a single integer $K$. Following that will be $K + 1$ piece descriptions.  The first description will describe the original glass cow,the following $K$ descriptions will be of the broken pieces.

Each description begins with a line containing two integers $R$ and $C$ ($1 \le R, C \le 100$).  The following $R$ lines contain $C$ lowercase alphabet characters describing the color of each cell.  Each piece will be horizontally/vertically connected and have at least one non-empty cell.

outputFormat: Output the number of triples $i, j, k$ ($i < j < k$) such that pieces $i$, $j$, and $k$ can be arranged to form the original glass cow.

samples:
5
5 5
aaaaa
..a..
bbabb
..a..
aaaaa
3 5
..abb
..a..
aaaaa
5 2
a.
a.
aa
a.
a.
1 2
bb
1 5
bbabb
2 5
aaaaa
..a..

hint:
The three solutions use pieces $(0, 1, 2)$, $(0, 2, 4)$, $(1, 3, 4)$.

Note that this problem has a time limit of 6 seconds per test case (and twice that  for Java and Python submissions).

感谢@wflengxuenong提供翻译


title: 海底高铁

description:
该铁路经过 $N$ 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第 $i$ 段铁路连接了城市 $i$ 和城市 $i+1(1\leq i<N)$。如果搭乘的比较远，需要购买多张车票。第 $i$ 段铁路购买纸质单程票需要 $A_i$ 博艾元。

虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第 $i$ 段铁路，需要花 $C_i$ 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣 $B_i(B_i<A_i)$ 元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第 $i$ 段铁路的 IC 卡，无法乘坐别的铁路的车。

Uim 现在需要出差，要去 $M$ 个城市，从城市 $P_1$ 出发分别按照 $P_1,P_2,P_3,\cdots,P_M$ 的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。

现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。

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

接下来一行，$M$ 个数字，表示 $P_i$。

接下来 $N-1$ 行，表示第 $i$ 段铁路的 $A_i,B_i,C_i$。

outputFormat: 一个整数，表示最少花费


title: [NOIP2017 提高组] 宝藏

background: NOIP2017 D2T2

description:
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋， 也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是 $\mathrm{L} \times \mathrm{K}$。其中 $L$ 代表这条道路的长度，$K$ 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

inputFormat:
第一行两个用空格分离的正整数 $n,m$，代表宝藏屋的个数和道路数。

接下来 $m$ 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 $1-n$），和这条道路的长度 $v$。

outputFormat: 一个正整数，表示最小的总代价。

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

【样例解释 $1$】

小明选定让赞助商打通了 $1$ 号宝藏屋。小明开发了道路 $1 \to 2$，挖掘了 $2$ 号宝藏。开发了道路 $1 \to 4$，挖掘了 $4$ 号宝藏。还开发了道路 $4 \to 3$，挖掘了 $3$ 号宝藏。

工程总代价为 $1 \times 1 + 1 \times 1 + 1 \times 2  = 4 $。

【样例解释 $2$】

小明选定让赞助商打通了 $1$ 号宝藏屋。小明开发了道路 $1 \to 2$，挖掘了 $2$ 号宝藏。开发了道路 $1 \to 3$，挖掘了 $3$ 号宝藏。还开发了道路 $1 \to 4$，挖掘了 $4$ 号宝藏。

工程总代价为 $1 \times 1 + 3 \times 1 + 1 \times 1  = 5$。

【数据规模与约定】

对于 $ 20\%$ 的数据： 保证输入是一棵树，$1 \le n \le 8$，$v \le 5\times 10^3$ 且所有的 $v$ 都相等。

对于 $40\%$ 的数据： $1 \le n \le 8$，$0 \le m \le 10^3$，$v \le 5\times 10^3$ 且所有的 $v$ 都相等。

对于 $ 70\%$ 的数据： $1 \le n \le 8$，$0 \le m \le 10^3$，$v \le  5\times 10^3$。

对于 $ 100\%$ 的数据： $1 \le n \le 12$，$0 \le m \le 10^3$，$v \le  5\times 10^5$。

---

$\text{upd 2022.7.27}$：新增加 $50$ 组 Hack 数据。


title: 可持久化并查集

description:
给定 $n$ 个集合，第 $i$ 个集合内初始状态下只有一个数，为 $i$。

有 $m$ 次操作。操作分为 $3$ 种：

 - `1 a b` 合并 $a,b$ 所在集合；

 - `2 k` 回到第 $k$ 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；

 - `3 a b` 询问 $a,b$ 是否属于同一集合，如果是则输出 $1$，否则输出 $0$。

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

接下来 $m$ 行，每行先输入一个数 $opt$。若 $opt=2$ 则再输入一个整数 $k$，否则再输入两个整数 $a,b$，描述一次操作。

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


title: 跳楼机

background: DJL 为了避免成为一只咸鱼，来找 srwudi 学习压代码的技巧。

description:
Srwudi 的家是一幢 $h$ 层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi 改造了一个跳楼机，使得访客可以更方便的上楼。

经过改造，srwudi 的跳楼机可以采用以下四种方式移动：

1. 向上移动 $x$ 层；
2. 向上移动 $y$ 层；
3. 向上移动 $z$ 层；
4. 回到第一层。

一个月黑风高的大中午，DJL 来到了 srwudi 的家，现在他在 srwudi 家的第一层，碰巧跳楼机也在第一层。DJL 想知道，他可以乘坐跳楼机前往的楼层数。

inputFormat:
第一行一个整数 $h$，表示摩天大楼的层数。

第二行三个正整数，分别表示题目中的 $x, y, z$。

outputFormat: 一行一个整数，表示 DJL 可以到达的楼层数。


title: 正整数序列

description:
kkk制造了一个序列，这个序列里的数全是由正整数构成的。你别认为她的数列很神奇——其实就是1, 2, …, n而已。当然，n是给定的。kkk的同学lzn认为0是一个好数字（看上去很饱满有木有），所以他机智的趁kkk不在把这个序列全变成了0（其实只是准备窝）~

可是kkk突然回来了！于是lzn的计划破灭了。但是他并不甘心，就和kkk说：我可以每次从这个序列中选取一些数，然后一起减去一个相同的数（当然也是正整数）。然后经过有(wu)限(qiong)次这样的操作后，这个序列就可以全变成0。

kkk当然不信咯，于是lzn就求出了他最少要做几次这样的操作，才能使这个序列全部变成0。

inputFormat: 一个正整数n

outputFormat:
最少操作次数

如果无解输出-1


title: 排序

description:
有 $n$ 个人依次站在小 A 面前。小 A 会依次对这 $n$ 个人进行 $m$ 次操作。

每次操作选择一个位置 $k$，将这 $n$ 个人中的所有身高小于等于当前 $k$ 位置的人的身高的人从队伍里拎出，然后按照身高从矮到高的顺序从左到右依次插入到 这些人原本的位置当中。

小 A 对这 $n$ 个人身高构成的序列的逆序对很感兴趣。现在小 A 想要知道每一次操作后这个序列的逆序对数。

----

Update（2021-01-17）：$a$ 序列中的逆序对的定义是满足 $i < j$ 且 $a_i > a_j$ 的数对 $(i, j)$。

inputFormat:
第一行两个整数 $n$ 和 $m$，表示人数和操作数。

接下来一行 $n$ 个整数 $a_i$，表示初始状态从左到右每个人的身高。

接下来 $m$ 行每行一个数，表示这次操作的 $k$。

outputFormat:
输出共 $m + 1$ 行，第一行表示未操作时的逆序对数量。

除第一行外第 $i$ 行表示第 $i - 1$ 次操作后序列的逆序对数。


title: pb的游戏（1）

background: 有一天 pb 和 zs 玩游戏  你需要帮 zs 求出每局的胜败情况。

description:
游戏规则是这样的：

- 先手对给出的数进行分割，分割成两个正整数，之后接着后手选择留下两个数中的其中一个。两人轮流操作，直到一方无法操作，另一方胜利。

现在要你求出 $N$ 次游戏的胜败。

我们认为双方绝顶聪明。每局由 pb 先进行分割。如果 pb 存在必胜策略，输出 `pb wins`；否则输出 `zs wins`。

inputFormat:
第一行一个数 $N$，表示数据组数。

之后 $N$ 行，每行一个数 $M$，表示每局初始的数。

outputFormat: 共 $N$ 行，每行一串字符，表示游戏结果。


title: [NOIP2017 提高组] 列队

background: NOIP2017 D2T3

description:
`Sylvia` 是一个热爱学习的女孩子。

前段时间，`Sylvia` 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有 $n \times m$ 名学生，方阵的行数为 $n$，列数为 $m$。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中 的学生从 $1$ 到 $n \times m$ 编上了号码（参见后面的样例）。即：初始时，第 $i$ 行第 $j$ 列 的学生的编号是 $(i-1)\times m + j$。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了 $q$ 件这样的离队事件。每一次离队事件可以用数对 $(x,y) (1 \le x \le n, 1 \le y \le m)$ 描述，表示第 $x$ 行第 $y$ 列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：

1. 向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条 指令之后，空位在第 $x$ 行第 $m$ 列。
2. 向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条 指令之后，空位在第 $n$ 行第 $m$ 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 $n$ 行 第 $m$ 列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 `Sylvia` 想要计算每一次离队事件中，离队的同学 的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。

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

第一行包含 $3$ 个用空格分隔的正整数 $n, m, q$，表示方阵大小是 $n$ 行 $m$ 列，一共发 生了 $q$ 次事件。

接下来 $q$ 行按照事件发生顺序描述了 $q$ 件事件。每一行是两个整数 $x, y$，用一个空 格分隔，表示这个离队事件中离队的学生当时排在第 $x$ 行第 $y$ 列。

outputFormat: 按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。

hint:
【输入输出样例 $1$ 说明】

$$\begin{matrix}
\begin{bmatrix}
1 & 2 \\
3 & 4 \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
 & 2 \\
3 & 4 \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 &  \\
3 & 4 \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 4 \\
3 &  \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 4 \\
3 & 1 \\
\end{bmatrix} \\[1em]
\begin{bmatrix}
2 & 4 \\
3 & 1 \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 4 \\
3 &  \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 4 \\
3 &  \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 4 \\
3 &  \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 4 \\
3 & 1 \\
\end{bmatrix}\\[1em]
\begin{bmatrix}
2 & 4 \\
3 & 1 \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 &  \\
3 & 1 \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 &  \\
3 & 1 \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 1 \\
3 &  \\
\end{bmatrix} & \Rightarrow &
\begin{bmatrix}
2 & 1 \\
3 & 4 \\
\end{bmatrix}
\end{matrix}$$

列队的过程如上图所示，每一行描述了一个事件。 在第一个事件中，编号为 $1$ 的同学离队，这时空位在第一行第一列。接着所有同学 向左标齐，这时编号为 $2$ 的同学向左移动一步，空位移动到第一行第二列。然后所有同 学向上标齐，这时编号为 $4$ 的同学向上一步，这时空位移动到第二行第二列。最后编号为 $1$ 的同学返回填补到空位中。

【数据规模与约定】

| 测试点编号 | $n$ | $m$ | $q$ | 其他约定 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1\sim 6$ | $\le 10^3$ | $\le 10^3$ | $\le 500$ | 无 |
| $7\sim 10$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | $\le 500$ | 无 |
| $11\sim 12$ | $=1$ | $\le 10^5$ | $\le 10^5$ | 所有事件 $x=1$ |
| $13\sim 14$ | $=1$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | 所有事件 $x=1$ |
| $15\sim 16$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | 所有事件 $x=1$ |
| $17\sim 18$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 无 |
| $19\sim 20$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | 无 |

数据保证每一个事件满足 $1 \le x \le n,1 \le y \le m$。


title: 丝绸之路

background: 张骞于公元前 138 年曾历尽艰险出使过西域。加强了汉朝与西域各国的友好往来。从那以后，一队队骆驼商队在这漫长的商贸大道上行进，他们越过崇山峻岭，将中国的先进技术带向中亚、西亚和欧洲，将那里的香料、良马传进了我国。每当人们凝望荒凉的大漠孤烟，无不引起对往日商贸、文化繁荣的遐想……

description:
小仓鼠带着货物，从中国送到安息，丝绸之路包括起点和终点一共有 $N+1$ 个城市，$0$ 号城市是起点长安，$N$ 号城市是终点巴格达。要求不超过 $M$ 天内必须到达终点。一天的时间可以从一个城市到连续的下一个城市。从 $i-1$ 城市到 $i$ 城市距离是 $D_i$。

大家都知道，连续赶路是很辛苦的，所以小仓鼠可以在一个城市时，可以有以下选择：

- 移动：向下一个城市进发

- 休息：呆在原来的城市不动

沙漠天气变化无常，在天气很不好时，前进会遇到很多困难。我们把 $M$ 天的第 $j(1<=j<=M)$ 天的气候恶劣值记为 $C_j$。从 $i-1$ 城市移动到 $i$ 城市在第 $j$ 天进发时，需要耗费 $D_i\times C_j$ 的疲劳度。

不过小仓鼠还是有选择权的，可以避开比较恶劣的天气，休息是不会消耗疲劳值的。现在他想知道整个行程最少要消耗多少疲劳值。

inputFormat:
第一行 $2$ 个整数 $N$，$M$。

接下来，连续 $N$ 行每行一个整数 $D_j$。

连续 $M$ 行每行一个整数 $C_j$。

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


title: [IOI2005] Riv 河流

description:
几乎整个 Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫 Bytetown。

在 Byteland 国，有 $n$ 个伐木的村庄，这些村庄都座落在河边。目前在 Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到 Bytetown 的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造 $k$ 个伐木场。这 $k$ 个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到 Bytetown 了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。

注：所有的河流都不会分叉，形成一棵树，根结点是 Bytetown。

国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米 $1$ 分钱。

inputFormat:
第一行包括两个整数 $n,k$。$n$ 为村庄数，$k$ 为要建的伐木场的数目。除了 Bytetown 外，每个村子依次被命名为 $1,2,3\ldots n$，Bytetown 被命名为 $0$。

第 $2$ 到第 $(n + 1)$ 行，每行 $3$ 个整数，第 $(i + 1)$ 行的整数分别代表，分别表示每年 $i$ 村子产的木料的块数 $w_i$，离 $i$ 村子下游最近的村子 $v_i$（即 $i$ 村子的父结点），$v_i$ 到 $i$ 的距离 $d_i$（千米）。

outputFormat: 输出最小花费，单位为分。

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

- 对于 $50\%$ 的数据，保证 $n\le 20$。
- 对于 $100\%$ 的数据，保证 $2\le n\le 100$，$1\le k\le \min(n,50)$，$0\le v_i\le n$，$0\le w_i\le 10^4$，$1\le d_i\le 10^4$。
- 保证每年所有的木料流到 bytetown 的运费不超过 $2\times 10^9$ 分。


title: 路障

description:
B 君站在一个 $n\times n$ 的棋盘上。最开始，B君站在 $(1,1)$ 这个点，他要走到 $(n,n)$ 这个点。

B 君每秒可以向上下左右的某个方向移动一格，但是很不妙，C 君打算阻止 B 君的计划。

**每秒结束的时刻**，C 君 会在 $(x,y)$ 上摆一个路障。B 君不能走在路障上。

B 君拿到了 C 君准备在哪些点放置路障。所以现在你需要判断，B 君能否成功走到 $(n,n)$。

**保证数据足够弱：也就是说，无需考虑“走到某处然后被一个路障砸死”的情况，因为答案不会出现此类情况。**

inputFormat:
首先是一个正整数 $T$，表示数据组数。

对于每一组数据：

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

接下来 $2n-2$ 行，每行两个正整数 $x$ 和 $y$，意义是在那一秒结束后，$(x,y)$ 将被摆上路障。

outputFormat: 对于每一组数据，输出 `Yes` 或 `No`，回答 B 君能否走到 $(n,n)$。


title: 仓鼠窝

description:
萌萌哒的 Created equal 是一只小仓鼠，小仓鼠自然有仓鼠窝啦。

仓鼠窝是一个由 $n\times m$ 个格子组成的行数为 $n$、列数为 $m$ 的矩阵。小仓鼠现在想要知道，这个矩阵中有多少个子矩阵。

比如说有一个 $2\times 3$ 的矩阵，那么 $1\times 1$ 的子矩阵有 $6$ 个，$1\times 2$ 的子矩阵有 $4$ 个，$1\times 3$ 的子矩阵有 $2$ 个，$2\times 1$ 的子矩阵有 $3$ 个，$2\times 2$ 的子矩阵有 $2$ 个，$2\times 3$ 的子矩阵有 $1$ 个，所以子矩阵共有 $6+4+2+3+2+1=18$ 个。

可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道，有多少个内部不含被破坏的格子的子矩阵。

inputFormat:
第一行两个正整数 $n$ 和 $m$，分别表示仓鼠窝的行数 $n$，列数 $m$。

接下来 $n$ 行，每行 $m$ 个数，每个数代表对应的格子，非 $0$ 即 $1$。若为 $0$，表示这个格子被破坏；反之代表这个格子是完好无损的。

outputFormat: 仅一个正整数，表示未被破坏的子矩阵的个数。


title: 洛谷树

background:
萌哒的 Created_equal 小仓鼠种了一棵洛谷树！

（题目背景是辣鸡小仓鼠乱写的 QAQ）。

description:
树是一个无环、连通的无向图，由 $n$ 个点和 $n-1$ 条边构成。树上两个点之间的路径被定义为他们之间的唯一一条简单路径——显然这是一条最短路径。

现在引入一个概念——子路径。假设树上两个点 $p_1$ 和 $p_n$ 之间的路径是 $P = \langle p_1,p_2,p_3, \ldots, p_n \rangle $，那么它的子路径被定义为某一条路径 $P'$，满足 $P'= \langle p_i,p_{i+1},p_{i+2},\ldots,p_j \rangle $，其中 $1\le i \le j \le n$。显然，原路径是一条子路径，任意一个点也可以作为子路径。

我们给每条边赋予一个边权。萌萌哒的 Sugar 问小仓鼠：对于任意两个点 $u$ 和 $v$，你能快速求出，$u$ 到 $v$ 的路径上所有子路径经过的边的边权的 $\text{xor}$ 值的和是多少。具体地说就是，你把 $u$ 到 $v$ 的路径上所有子路径全部提出来，然后分别把每个子路径上经过的边的边权 $\text{xor}$ 在一起，最后求出得到的所有 $\text{xor}$ 值的和。

什么？你不知道 $\text{xor}$？那就去百度啊！

这时候，fjzzq2002 大爷冒了粗来：窝还要你滋磁修改某条边边权的操作！

小仓鼠那么辣鸡，当然不会做这道题啦。于是他就来向你求救！

inputFormat:
第一行两个正整数 $n$ 和 $q$，表示点的个数，查询和询问的总次数。

接下来 $n-1$ 行，每行两个正整数 $u,v$ 和一个非负整数 $w$，表示 $u$ 和 $v$ 两个点之间有一条边权为 $w$ 的边。

接下来 $q$ 行，格式为 `1 u v` 或 `2 u v w`。
如果为 `1 u v` 操作，你需要输出 $u$ 到 $v$ 的路径上所有子路径经过的边的边权的 $\text{xor}$ 值的和是多少。
如果为 `2 u v w` 操作，你需要把 $u$ 到 $v$ 这条边的边权改为 $w$，保证这条边存在。

outputFormat: 对于每个 $1$ 操作，输出答案。


title: 哈希冲突

background: 众所周知，模数的 hash 会产生冲突。例如，如果模的数 $p=7$，那么 $4$ 和 $11$ 便冲突了。

description:
B 君对 hash 冲突很感兴趣。他会给出一个正整数序列 $\text{value}$。

自然，B 君会把这些数据存进 hash 池。第 $\text{value}_k$ 会被存进 $(k \bmod p)$ 这个池。这样就能造成很多冲突。

B 君会给定许多个 $p$ 和 $x$，询问在模 $p$ 时，$x$ 这个池内 **数的总和**。

另外，B 君会随时更改 $\text{value}_k$。每次更改立即生效。

保证 ${1\leq p<n}$。

inputFormat:
第一行，两个正整数 $n$, $m$，其中 $n$ 代表序列长度，$m$ 代表 B 君的操作次数。

第一行，$n$ 个正整数，代表初始序列。

接下来 $m$ 行，首先是一个字符 $\text{cmd}$，然后是两个整数 $x,y$。

- 若 $\text{cmd}=\text{A}$，则询问在模 $x$ 时，$y$ 池内 **数的总和**。

- 若 $\text{cmd}=\text{C}$，则将 $\text{value}_x$ 修改为 $y$。

outputFormat: 对于每个询问输出一个正整数，进行回答。


title: [CQOI2009] 跳舞

description:
一次舞会有 $n$ 个男孩和 $n$ 个女孩。

每首曲子开始时，所有男孩和女孩恰好配成 $n$ 对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。

有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和 $k$ 个不喜欢的女孩跳舞，而每个女孩也最多只愿意和 $k$ 个不喜欢的男孩跳舞。

给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

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

以下 $n$ 行每行包含 $n$ 个字符，每个字符只可能是 `Y` 或 `N`。第 $(i + 1)$ 行的第 $j$ 个字符为 `Y` 当且仅当男孩 $i$ 和女孩 $j$ 相互喜欢。

outputFormat: 一行一个整数代表舞曲数目的最大值。

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

- 对于 $100\%$ 的数据，保证 $1\leq n\leq 50$，$0\leq k\leq 30$。


title: [CQOI2009] 循环赛

description:
$n$ 支队伍比赛，每两支队伍比赛一次，平 $1$ 胜 $3$ 负 $0$。

给出队伍的最终得分，求有多少种可能的分数表。

```平1胜3负0```指：

- 若两支队伍打平，则各得到 $1$ 分；
- 否则，胜利的队伍得到 $3$ 分，被打败的队伍得到 $0$ 分。

inputFormat: 第一行包含一个正整数 $n$，表示队伍的个数。第二行包含 $n$ 个非负整数，即每支队伍的得分。

outputFormat: 输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。

hint: 所有数据满足 $n\le 8$。


title: [CQOI2009] 叶子的染色

description:
给一棵 $m$ 个结点的无根树，你可以选择一个度数大于 $1$ 的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。

你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。

对于每个叶结点 $u$，定义 $c_u$ 为从根结点到 $u$ 的简单路径上最后一个有色结点的颜色。给出每个 $c_u$ 的值，设计着色方案，使得着色结点的个数尽量少。

inputFormat:
第一行包含两个整数 $m,n$，其中 $n$ 是叶子的个数，$m$ 是结点总数。结点编号为 $1,2,\ldots,m$，其中编号 $1,2,\ldots ,n$ 是叶子。

以下 $n$ 行每行一个 $0$ 或 $1$ 的整数（$0$ 表示黑色，$1$ 表示白色），依次为 $c_1,c_2,\ldots,c_n$。

以下 $m-1$ 行每行两个整数 $a,b$，表示结点 $a$ 和 $b$ 有边相连。

outputFormat: 仅一个数，即着色结点数的最小值。

hint:
#### 数据规模与约定
对于全部的测试点，保证 $1\le m\le 10^4$，$1\le n\le 5021$，$1\le a < b \le m$。


title: [CQOI2011] 动态逆序对

description:
对于序列 $a$，它的逆序对数定义为集合
$$\{(i,j)| i<j \wedge a_i > a_j \}$$
中的元素个数。

现在给出 $1\sim n$ 的一个排列，按照某种顺序依次删除 $m$ 个元素，你的任务是在每次删除一个元素**之前**统计整个序列的逆序对数。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，即初始元素的个数和删除的元素个数。
以下 $n$ 行，每行包含一个 $1 \sim n$ 之间的正整数，即初始排列。
接下来 $m$ 行，每行一个正整数，依次为每次删除的元素。

outputFormat: 输出包含 $m$ 行，依次为删除每个元素之前，逆序对的个数。


title: [CQOI2011] 放棋子

description:
在一个 $m$ 行 $n$ 列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列，有多少种方法？

例如，$n=m=3$，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。

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

inputFormat:
输入第一行为两个整数 $n,m,c$，即行数、列数和棋子的颜色数。

第二行包含 $c$ 个正整数，即每个颜色的棋子数。

outputFormat: 输出仅一行，即方案总数除以 $10^9+9$ 的余数。

hint: $1\le n,m\le 30$，$1\le c\le 10$，总棋子数 $\le \max (250,n\times m)$。


title: [CQOI2012] 交换棋子

description: 有一个 $n$ 行 $m$ 列的黑白棋盘，你每次可以交换两个相邻格子（**相邻是指有公共边或公共顶点**）中的棋子，最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m_{i,j}$ 次交换。

inputFormat: 第一行包含两个整数 $n,m$。以下 $n$ 行为初始状态，每行为一个包含 $m$ 个字符的 $01$ 串，其中 $0$ 表示黑色棋子，$1$ 表示白色棋子。以下 $n$ 行为目标状态，格式同初始状态。以下 $n$ 行每行为一个包含 $m$ 个 $0\sim9$ 数字的字符串，表示每个格子参与交换的次数上限。

outputFormat: 输出仅一行，为最小交换总次数。如果无解，输出 $-1$。

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

对于 $100\%$ 的数据，$1\leq n,m\leq20$。


title: [CQOI2012] 局部极小值

description:
有一个 $n$ 行 $m$ 列的整数矩阵，其中 $1$ 到 $n\times m$ 之间的每个整数恰好出现一次。

如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。

答案对 $12{,}345{,}678$ 取模。

inputFormat:
输入第一行包含两个整数 $n$ 和 $m$，即行数和列数。

以下 $n$ 行每行 $m$ 个字符，第 $(i + 1)$ 行的第 $j$ 个字符代表第 $i$ 列的第 $j$ 个格子是否是局部极小值，该字符只可能是 `X` 或 `.`，其中 `X` 表示局部极小值，`.` 表示非局部极小值。

outputFormat: 输出仅一行，为可能的矩阵总数除以 $12345678$ 的余数。

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

- 对于 $100\%$ 的数据，保证 $1\le n\le4$，$1\le m\le7$。


title: [CQOI2012] 模拟工厂

description:
有一个称为“模拟工厂”的游戏是这样的：在时刻 $0$，工厂的生产力等于 $1$。在每个时刻，你可以提高生产力或者生产商品。如果选择提高生产力，在下一个时刻时工厂的生产力加 $1$；如果选择生产商品，则下一个时刻你所拥有的商品数量增加 $p$，其中 $p$ 是本时刻工厂的生产力。

有 $n$ 个订单，可以选择接受或者不接受。第 $i$ 个订单 $(t_i, g_i, m_i)$ 要求在时刻 $t_i$ 给买家提供 $g_i$ 个商品，事成之后商品数量减少 $g_i$，而收入增加 $m_i$ 元。如果接受订单 $i$，则必须恰好在时刻 $t_i$ 交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。

例如，如果一共有两个订单 $(5,1,8)$ 和 $(7,15,3)$，用如下策略是最优的：时刻 $0$, $1$, $2$ 提高生产力（时刻 $3$ 的生产力为 $4$），然后在时刻 $3$，$4$ 生产商品，则在时刻 $5$ 时将拥有 $8$ 个商品。此时接受第 $1$ 个订单（还会剩下 $7$ 个商品），并且在时刻 $5$，$6$ 继续生产商品，则在时刻 $7$ 时拥有 $7+4+4=15$ 个商品，正好满足订单 $2$。

inputFormat: 输入第一行包含一个整数 $n$，即订单数目。以下 $n$ 行每行三个整数 $t_i, g_i, m_i$。

outputFormat: 输出仅一行，为最大总收入。输出保证在 $32$ 位带符号整数范围内。


title: [CQOI2012] 组装

description: 数轴上有 $m$ 个生产车间可以生产零件。一共有 $n$ 种零件，编号为 $1\sim n$。第 $i$ 个车间的坐标为 $x_i$ ，生产第 $p_i$ 种零件（$1\le p_i\le n$）。你需要在数轴上的某个位置修建一个组装车间，把这些零件组装起来。为了节约运输成本，你需要最小化 $cost_1+cost_2+\ldots+cost_n$，其中 $cost_x$ 表示生产第 $x$ 种零件的车间中，到组装车间距离的平方的最小值。

inputFormat: 输入第一行为两个整数 $n$, $m$ ，即零件的种类数和生产车间的个数。以下 $m$ 行每行两个整数 $x_i$ 和 $p_i$（$1\le p_i\le n$）。输入按照生产车间从左到右的顺序排列（即 $x_i\le x_{i+1}$ 。注意车间位置可以重复）。输入保证每种零件都有车间生产。

outputFormat: 输出仅一行，即组装车间的最优位置（可以和某个生产车间重合），四舍五入保留四位小数。输入保证最优位置惟一。


title: [CQOI2014] 危桥

description:
Alice 和 Bob 居住在一个由 $N$ 座岛屿组成的国家，岛屿被编号为 $0$ 到 $N-1$。某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。

Alice 希望在岛屿 $a_1$ 和 $a_2$ 之间往返 $a_n$ 次（从 $a1$ 到 $a2$ 再从 $a2$ 到 $a1$ 算一次往返）。同时，Bob 希望在岛屿 $b_1$ 和 $b_2$ 之间往返 $b_n$ 次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问 Alice 和 Bob 能完成他们的愿望吗？

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

每组数据第一行包含七个空格隔开的整数，分别为$N$、$a_1$、$a_2$、$a_n$、$b_1$、$b_2$、$b_n$。
接下来是一个 $N$ 行 $N$ 列的对称矩阵，由大写字母组成。矩阵的 $i$ 行 $j$ 列描述编号 $i-1$ 和 $j-1$ 的岛屿间的连接情况，若为 “`O`” 则表示有危桥相连：为 “`N`” 表示有普通的桥相连：为 “`X`” 表示没有桥相连。

outputFormat: 对于每组测试数据输出一行，如果他们都能完成愿望输出 “Yes”，否则输出 “No”（不含引号）。

samples:
4 0 1 1 2 3 1
XOXX
OXOX
XOXO
XXOX
4 0 2 1 1 3 2
XNXO
NXOX
XOXO
OXOX

hint: 对于所有数据，$4 \leq N\leq 50,\ 0 \leq a_1, a_2, b_1, b_2 \leq N-1,\ 1 \leq a_n, b_n \leq 50$。


title: [CQOI2014] 和谐矩阵

description: 我们称一个由 $0$ 和 $1$ 组成的矩阵是和谐的，当且仅当每个元素都有偶数个相邻的 $1$。一个元素相邻的元素包括它本身，及他上下左右的 $4$ 个元素（如果存在）。给定矩阵的行数和列数，请计算并输出一个和谐的矩阵。注意：所有元素为 $0$ 的矩阵是不允许的。

inputFormat: 输入一行，包含两个空格分隔的整数 $m$ 和 $n$，分别表示矩阵的行数和列数。

outputFormat: 输出包含 $m$ 行，每行 $n$ 个空格分隔整数（$0$ 或 $1$），为所求矩阵。测试数据保证有解。

hint:
数据范围

$1\le n,m\le 40$。

感谢@miaomiao 提供spj。


title: [CQOI2014] 排序机械臂

description:
为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到高度最低的物品的位置 $P_1$ ，并把左起第一个物品至 $P_1$  间的物品 (即区间 $[1,P_1]$  间的物品) 反序；第二次找到第二低的物品的位置 $P_2$ ，并把左起第二个至 $P_2$  间的物品 (即区间 $[2,P_2]$  间的物品) 反序……最终所有的物品都会被排好序。

![样例说明](https://cdn.luogu.com.cn/upload/pic/15642.png)

上图给出有六个物品的示例，第一次操作前，高度最低的物品在位置 $4$ ，于是把第一至第四的物品反序；第二次操作前，第二低的物品在位罝六，于是把第二至六的物品反序……

你的任务便是编写一个程序，确定一个操作序列，即每次操作前第 $i$ 低的物品所在位置 $P_i$ ，以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后它们的相对位置关系与初始时相同。

inputFormat:
第一行包含正整数n,表示需要排序的物品数星。

第二行包含n个空格分隔的整数$P_i$,表示每个物品的高度。

outputFormat: 输出一行包含n个空格分隔的整数Pi。


title: [CQOI2014] 数三角形

description: 给定一个 $N\times M$ 的网格，请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。

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

outputFormat: 输出一个正整数，为所求三角形数量。

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

对于全部的测试点，保证 $1\le N,M\le1000$。


title: [CQOI2014] 通配符匹配

description: 几乎所有操作系统的命令行界面（CLI）中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号（```*```），可以匹配 0 个及以上的任意字符：另一个是问号（```?```），可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

inputFormat: 第一行是一个由小写字母和上述通配符组成的字符串。第二行包含一个整数 $n$，表示文件个数。接下来 $n$ 行，每行为一个仅包含小写字母字符串，表示文件名列表。

outputFormat: 输出 $n$ 行，每行为 ``YES`` 或 ``NO``，表示对应文件能否被通配符匹配。

samples:
*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct


title: [CQOI2015] 任务查询系统

description:
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。

超级计算机中的任务用三元组 $(s_i, e_i, p_i)$ 描述，$(s_i, e_i, p_i)$ 表示任务从第 $s_i$ 秒开始，在第 $e_i$ 秒后结束（第 $s_i$ 秒和 $e_i$ 秒任务也在运行），其优先级为 $p_i$。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。

调度系统会经常向查询系统询问，第 $x_i$ 秒正在运行的任务中，优先级最小的 $k_i$ 个任务（即将任务按照优先级从小到大排序后取前 $k_i$ 个）的优先级之和是多少。

特别的，如果 $k_i$ 大于第 $x_i$ 秒正在运行的任务总数，则直接回答第 $x_i$ 秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在 $[1, n]$ 之间。

inputFormat:
输入文件第一行包含两个空格分开的正整数 $m$ 和 $n$，分别表示任务总数和时间范围。

接下来 $m$ 行，每行包含三个空格分开的正整数 $s_i,e_i,p_i$（$s_i \le e_i$），描述一个任务。

接下来 $n$ 行，每行包含四个空格分开的整数 $x_i,a_i,b_i,c_i$，描述一次查询。

**本题强制在线**。查询的参数 $k_i$ 需要由公式 $k_i = 1 +(a_i \times \text{pre}+b_i) \bmod c_i$ 计算得到。其中 $\text{pre}$ 表示上一次查询的结果，定义初始 $\text{pre} = 1$ 。

outputFormat: 输出共 $n$ 行，每行一个整数，表示查询结果。


title: [CQOI2015] 多项式

description:
在学习完二项式定理后，数学老师给出了一道题目：已知整数 $n,t$ 和 $a_k$（$0\le k\le n$），求 $b_k$（$0\le k\le n$）的表达式使得:

$$
\sum_{k=0}^n a_kx^k=\sum_{k=0}^nb_k(x-t)^k
$$

同学们很快算出了答案。见大家这么快就搞定了，老师便布置了一个更 BT 的作业：计算某个 $b_k$ 的具体数值！接着便在黑板上写下了 $n,t$ 的数值，由于 $a_k$ 实在太多，不能全写在黑板上，老师只给出了一个 $a_k$ 的递推式，让学生自行计算:

$$
a_k=
\begin{cases}
(1234\cdot a_{k-1}+5678)\bmod 3389 & k\gt 0 \\
1 & k=0 \\
\end{cases}
$$

正在学习信息竞赛的你觉得这个作业实在不适合手工完成，便敲起了代码……

inputFormat: 输入文件共三行，第一行为一个正整数 $n$，第二行为一个非负整数 $t$，第三行为一个非负整数 $m$。

outputFormat: 输出一行，为 $b_m$ 的值。


title: [CQOI2015] 标识设计

description:
一家名字缩写为 LLL 的公司正在设计 logo，他们的初步方案是在一张方格上放置 $3$ 个 L 形的图案以及一些额外的装饰性图形，例如：![](https://cdn.luogu.com.cn/upload/pic/15558.png)  （灰色区域表示装饰性图形）。

$3$ 个 L 图案和装饰性图形均放置在方格之中，且必须占满方格。L 的横竖笔画长短均可，但长度必须大于 $0$（即不能退化为一条线段）。另外，为了使 L 图案醒目且容易辨别，设计师规定 $3$ 个 L 形图案之间不能有重叠或交叉的部分。当然，L 形图案也不能穿过装饰图形或与之重叠。

现在设计师已经确定了所有装饰性图形的位置，希望你计算一下放置不同的 L 形图案总共可以设计出多少个 logo。

inputFormat:
第一行包含两个空格分开的正整数 $n$ 和 $m$，分别表示方格的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，第 $(i + 1)$ 行第 $j$ 个字符代表第 $i$ 行第 $j$ 列的图形，该字符只可能为 `.` 或 `#`。`#` 表示该方格为装饰性图形，`.` 表示可以放置 L 图案的空白区域。

outputFormat: 输出一个整数，为可能的logo总数。

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

对于 $100\%$ 的数据，保证 $2\le n,m\leq 30$。


title: [CQOI2015] 网络吞吐量

background: 路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法 OSPF (开放式最短路径优先) 中，路由器会使用经典的 Dijkstra 算法计算最短路径，然后尽量沿最短路径转发数据包。

description: 现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），网络中的路由器使用 $1$ 到 $n$ 编号，假设所有数据包一定沿最短路径转发，试计算从路由器 $1$ 到路由器 $n$ 的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器 $1$ 到路由器 $n$ 作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将 $1$ 和 $n$ 直接相连的链路。

inputFormat:
输入的第一行是用空格隔开的两个整数，分别代表路由器的数量 $n$ 和链路的数量 $m$。

第 $2$ 到第 $(m + 1)$  行，每行三个整数 $u, v, w$，代表存在一条连结路由器 $u$ 和路由器 $v$  的距离为 $w$ 的双向链路。

第 $(m + 2)$ 到第 $(n + m + 1)$  行，每行一个整数，第 $(i + m + 1)$ 行的整数代表路由器 $i$ 的吞吐量 $c_i$。

outputFormat: 输出一行一个整数，代表网络的最大吞吐量。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 500$，$1 \leq m \leq 10^5$，$1 \leq w, c_i \leq 10^9$。


title: [CQOI2015] 选数

description:
我们知道，从区间 $[L,H]$（$L$ 和 $H$ 为整数）中选取 $N$ 个整数，总共有 $(H-L+1)^N$ 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 $N$ 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 $K$，你需要回答他最大公约数刚好为 $K$ 的选取方案有多少个。

由于方案数较大，你只需要输出其除以 $10^9+7$ 的余数即可。

inputFormat: 输入一行，包含四个空格分开的正整数，依次为 $N,K,L,H$。

outputFormat: 输出一个整数，为所求方案数除以 $10^9 + 7$ 的余数。


title: [HAOI2009] 巧克力

description:
有一块 $n \times m$ 的矩形巧克力，准备将它切成 $n \times m$ 块。巧克力上共有 $n-1$ 条横线和 $m-1$ 条竖线，你每次可以沿着其中的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为 $y_1,y_2,\cdots,y_{n-1}$，而沿竖线切割的代价依次为 $x_1,x_2,\cdots,x_{m-1}$。

例如，对于下图 $6 \times 4$ 的巧克力，我们先沿着三条横线切割，需要 $3$ 刀，得到 $4$ 条巧克力，然后再将这 $4$ 条巧克力沿竖线切割，每条都需要 $5$ 刀，则最终所花费的代价为 $y_1+y_2+y_3+4 \times (x_1+x_2+x_3+x_4+x_5)$。

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

当然，上述简单切法不见得是最优切法，那么怎样切割该块巧克力，花费的代价最少呢？

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

接下来 $n-1$ 行，每行一个整数，分别代表 $x_1,x_2,\cdots,x_{n-1}$；

接下来 $m-1$ 行，每行一个整数，分别代表 $y_1,y_2,\cdots,y_{m-1}$。

outputFormat: 输出一整数，为切割巧克力的最小代价。


title: [HAOI2009] 毛毛虫

background: 感谢由@ScanfN 提供的两组 hack 数据。

description:
对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫，点数越多，毛毛虫就越大。例如下图左边的树（图 $1$）抽出一部分就变成了右边的一个毛毛虫了（图 $2$）。

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

inputFormat:
输入中第一行两个整数 $N, M$，分别表示树中结点个数和树的边数。

接下来 $M$ 行，每行两个整数 $a, b$ 表示点 $a$ 和点 $b$ 有边连接（$a, b \le N$）。你可以假定没有一对相同的 $(a, b)$ 会出现一次以上。

outputFormat: 输出一行一个整数 , 表示最大的毛毛虫的大小。


title: [HAOI2015] 按位或

description: 刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行或（C++,C 的 `|`，pascal 的 `or`）操作。选择数字 $i$ 的概率是 $p_i$。保证 $0\leq p_i \leq 1$，$\sum p_i=1$ 。问期望多少秒后，你手上的数字变成 $2^n-1$。

inputFormat: 第一行输入 $n$ 表示 $n$ 个元素，第二行输入 $2^n$ 个数，第 $i$ 个数表示选到 $i-1$ 的概率。

outputFormat: 仅输出一个数表示答案，绝对误差或相对误差不超过 $10^{-6}$ 即可算通过。如果无解则要输出 `INF`。

hint:
对于 $100\%$ 的数据，$n\leq 20$。

以下为 spj 源代码。

```cpp
//liuchenrui
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define AC {fclose(fstd),fclose(fuser);return 0;}
#define WA {fclose(fstd),fclose(fuser);return 1;}
#define PE {fclose(fstd),fclose(fuser);return 5;}
#define eps 1e-6
int main(int const argc, char*const argv[]){
    FILE *fstd,*fuser;
    fstd=fopen(argv[2],"r");
    fuser=fopen(argv[3],"r");
    //fstd=fopen("x1.in","r");
    //fuser=fopen("x2.in","r");
    char s[30],t[30];
    if(fscanf(fuser,"%s",s+1)==-1)WA;
    fscanf(fstd,"%s",t+1);
    if(s[1]=='I' && t[1]=='I')AC;
    if(s[1]=='I' || t[1]=='I')WA;
    double p,q;
    sscanf(s+1,"%lf",&p);
    sscanf(t+1,"%lf",&q);
    if(fabs(p-q)<eps)AC
    else{
        if(fabs(p-q)/q<eps)AC;
        if(fabs(q-p)/q<eps)AC;
        if(fabs(p-q)/p<eps)AC;
        if(fabs(q-p)/p<eps)AC;
    }
    WA;
}

```


title: [HAOI2015] 数字串拆分

description:
你有一个长度为 $n$ 的数字串 $s_0$。

定义 $f(s)$ 为将 $s$ 拆分成若干个 $1 \sim m$ 的数的和的方案数，比如 $m=2$ 时，$f(4)=5$，分别为 $4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2$。

定义 $g(s)$ 为将 $s$ 这个数字串分割成若干个数字（允许前导 $0$），设他们的和为 $x$，则 $g(s)$ 为所有情况下 $f(x)$ 之和。比如 $g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。

给定 $s_0$ 和 $m$，求 $g(s)$。

答案对 $998,244,353$ 取模。

inputFormat:
第一行有一个字符串。代表 $s_0$。

第二行有一个整数，代表 $m$。

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

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

- 对于 $100\%$ 的数据，保证 $1\le|s_0|\le 500$， $1\le m\le 5$，$s_0$ 中只有数字字符。


title: [HAOI2015] 树上染色

description: 有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $k$ ，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他的 $n-k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。

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

第二到 $n$ 行每行三个正整数 $u, v, w$，表示该树中存在一条长度为 $w$ 的边 $(u, v)$。输入保证所有点之间是联通的。

outputFormat: 输出一个正整数，表示收益的最大值。


title: [HAOI2015] 树上操作

description:
有一棵点数为 $N$ 的树，以点 $1$ 为根，且树有点权。然后有 $M$ 个操作，分为三种：
- 操作 $1$：把某个节点 $x$ 的点权增加 $a$。
- 操作 $2$：把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$。
- 操作 $3$：询问某个节点 $x$ 到根的路径中所有点的点权和。

inputFormat:
第一行包含两个整数 $N,M$。表示点数和操作数。
接下来一行 $N$ 个整数，表示树中节点的初始权值。
接下来 $N-1$ 行每行两个正整数 $\mathit{from},\mathit{to}$， 表示该树中存在一条边 $(\mathit{from},\mathit{to})$。
再接下来 $M$ 行，每行分别表示一次操作。其中第一个数表示该操作的种类，之后接这个操作的参数。

outputFormat: 对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

hint: 对于 $100\%$ 的数据，$1\le N,M\le10^5$，且所有输入数据的绝对值都不会超过 $10^6$。


title: [HAOI2015] 数组游戏

description:
有一个长度为 $n$ 的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。

每次操作选择一个白色的格子，假设它的下标为 $x$。接着，选择一个大小在 $1\ldots \dfrac{n}{x}$ 之间的整数 $k$，然后将下标为 $x,2\times x,\ldots ,k\times x$ 的格子都进行颜色翻转。不能操作的人输。

现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。

inputFormat:
第一行包含一个整数 $n$，表示数组的长度。

第二行包含一个整数 $k$，表示询问的个数。

接下来 $2\times k$ 行，每两行表示一次询问。

在这两行中，第一行一个正整数 $w$，表示数组中有多少个格子是白色的，第二行则有 $w$ 个 $1$ 到 $n$ 之间的正整数，表示白色格子的对应下标。

outputFormat: 对于每个询问，输出一行一个字符串，若先手必胜输出 `Yes`，否则输出 `No`。

hint:
#### 样例输入输出 1 解释

在第一个询问中，甲选择点 $1$，然后将格子 $1\times 1$ 和 $2\times 1$ 翻过来即可。

第二个询问中，无论甲选择哪个点，都只能翻掉一个格子。乙只需翻掉另一个格子就行了。

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^9$， $1\leq k, w \leq 100$ ，不会有格子在同一次询问中多次出现。


title: [HAOI2016] 地图

description:
一天 rin 来到了一个遥远的都市。这个都市有 $n$ 个建筑，编号从 $1$ 到 $n$，其中市中心编号为 $1$，这个都市有 $m$ 条双向通行的街道，每条街道连接着两个建筑，其中某些街道首尾相连连接成了一个环。

rin 通过长时间的走访，已经清楚了这个都市的两个特点：
1. 从市中心出发可以到达所有的建筑物。
2. 任意一条街道最多存在与一个简单环中。令 rin 心花怒放的是，每个建筑物都会有拉面售卖。拉面有很多不同的种类，但对于 rin 而言只有油腻程度的不同，因此我们把油腻程度相同的拉面看做同一种拉面。

由于不同建筑物的拉面的油腻程度可能不同，我们用一个正整数来表示拉面的油腻程度。

要知道，拉面可是 rin 的最爱，但是现在到了下班高峰期，都市的交通变得非常的堵塞。 rin 只能通过没有被堵死的街道通行，去品尝所在建筑物的拉面。

现在 rin 想知道，如果她正在编号为 $x$ 的建筑物，那么在从市中心到 $x$ 的所有简单路径经过的街道都被堵死的情况下，rin 可以品尝到的拉面中（注意没有出现的拉面是不能算在里面的）：

1. 油腻程度 $\leq y$ 且品尝次数为奇数次的拉面有多少种？
2. 油腻程度 $\leq y$ 且品尝次数为偶数次的拉面有多少种？

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

第二行一共 $N$ 个正整数，第 $i$ 个数 $A_i$ 表示第 $i$ 个建筑物出售的拉面的油腻程度。

接下来 $M$ 行，每行两个正整数 $x, y$，表示在建筑物 $x, y$ 之间有一条双向通行的街道。数据保证 $1 \leq x < y \leq N$。

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

接下来 $Q$ 行每行三个非负整数 $ty, x, y$，$ty=0$ 时表示询问偶数，$ty=1$ 表示询问奇数。

$N \leq 100000, M \leq 150000, Q \leq 100000, A_i \leq 10^6$。

提示：请注意数据范围中的 $\leq$，特殊条件中提到的??均为询问中的 $y$，对于所有的数据，有 $y \leq 10^6$。

outputFormat: 一共 $Q$ 行，对于每个询问输出一个答案。


title: [HAOI2016] 找相同字符

description: 给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

inputFormat: 两行，两个字符串 $s_1,s_2$，长度分别为 $n_1,n_2$。

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

hint: $1\le n_1,n_2\le 2\times 10^5$，字符串中只有小写字母。


title: [HAOI2016] 放棋子

description: 给你一个 $N\times N$ 的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放 $N$ 枚棋子（障碍的位置不能放棋子），要求你放 $N$ 个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。

inputFormat: 第一行一个 $N$，接下来一个 $N \times N$ 的矩阵。$N\leq 200$，0 表示没有障碍，1 表示有障碍。

outputFormat: 一个整数，即合法的方案数。


title: [HAOI2016] 食物链

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

如图所示为某生态系统的食物网示意图，据图回答第 1 小题
现在给你 $n$ 个物种和 $m$ 条能量流动关系，求其中的食物链条数。物种的名称为从 $1$ 到 $n$ 编号 $M$ 条能量流动关系形如 $a_1,b_1,a_2,b_2,a_3,b_3,\ldots,a_{m-1},b_{m-1},a_m,b_m$。其中 $a_i$ 和 $b_i$ 表示能量从物种 $a_i$ 流向物种 $b_i$，注意单独的一种孤立生物不算一条食物链。

inputFormat: 第一行两个整数 $n, m$，接下来 $m$ 行每行两个整数 $a_i$ 和 $b_i$ 描述 $m$ 条能量流动关系。

outputFormat: 一个整数即食物网中的食物链条数。

hint:
数据保证输入数据符合生物学特点，且不会有重复的能量流动关系出现，题目保证答案不会爆 `int`。

对于 $100 \%$ 的数据，$1 \leq N \leq 100000$，$0 \leq m \leq 200000$。


title: [USACO16DEC] Counting Haybales S

description:
Farmer John has just arranged his $N$ haybales ($1 \leq N \leq 100,000$) at various points along the one-dimensional road running across his farm.  To make sure they are spaced out appropriately, please help him answer $Q$ queries ($1 \leq Q \leq 100,000$), each asking for the number of haybales within a specific interval along the road.

农夫John在一条穿过他的农场的路上（直线）放了N个干草垛（1<=N<=100,000），每个干草垛都在不同的点上。为了让每个干草垛之间都隔着一定的距离，请你回答农夫John的Q个问题（1<=Q<=100,000），每个问题都会给出一个范围，询问在这个范围内有多少个干草垛。

（其实就是有一条数轴上有N个不重复的点，再问Q个问题，每个问题是给出一个范围，问此范围内有多少个点？）

（在给出范围的边界上也算）

inputFormat:
The first line contains $N$ and $Q$.

The next line contains $N$ distinct integers, each in the range $0 \ldots 1,000,000,000$, indicating that there is a haybale at each of those locations.

Each of the next $Q$ lines contains two integers $A$ and $B$($0 \leq A \leq B \leq 1,000,000,000$) giving a query for the number of haybales between $A$ and $B$, inclusive.

第一行包括N和Q

第二行有N个数字，每个数字的范围在0~1,000,000,000，表示此位置有一个干草垛。

接下来的Q行，每行包括两个数字，A和B（0<=A<=B<=1,000,000,000）表示每个询问的范围

outputFormat:
You should write $Q$ lines of output.  For each query, output the number of haybales in its respective interval.

总共Q行，每行输出此范围内的干草垛数量

hint: 感谢@2014nhc 提供翻译


title: [HNOI2007] 分裂游戏

description:
聪聪和睿睿最近迷上了一款叫做分裂的游戏。

该游戏的规则是： 共有 $n$ 个瓶子， 标号为 $0, 1, \ldots, n-1$，第 $i$ 个瓶子中装有 $p_i$ 颗巧克力豆，两个人轮流取豆子，每一轮每人选择 $3$ 个瓶子，标号为 $i,j,k$, 并要保证 $i \lt j, j \leq k$，且第 $i$ 个瓶子中至少要有 $1$ 颗巧克力豆，随后这个人从第 $i$ 个瓶子中拿走一颗豆子并在 $j,k$ 中各放入一粒豆子（$j$ 可能等于 $k$） 。如果轮到某人而他无法按规则取豆子，那么他将输掉比赛。胜利者可以拿走所有的巧克力豆！

两人最后决定由聪聪先取豆子，为了能够得到最终的巧克力豆，聪聪自然希望赢得比赛。他思考了一下，发现在有的情况下，先拿的人一定有办法取胜，但是他不知道对于其他情况是否有必胜策略，更不知道第一步该如何取。他决定偷偷请教聪明的你，希望你能告诉他，在给定每个瓶子中的最初豆子数后是否能让自己得到所有巧克力豆，他还希望你告诉他第一步该如何取，并且为了必胜，第一步有多少种取法？

inputFormat:
输入文件第一行是一个整数 $t$，表示测试数据的组数。

每组测试数据的第一行是瓶子的个数 $n$，接下来的一行有 $n$ 个由空格隔开的非负整数，表示每个瓶子中的豆子数。

outputFormat:
对于每组测试数据，输出包括两行，第一行为用一个空格两两隔开的三个整数，表示要想赢得游戏，第一步应该选取的 $3$ 个瓶子的编号 $i,j,k$，如果有多组符合要求的解，那么输出字典序最小的一组。如果无论如何都无法赢得游戏，那么输出用一个空格两两隔开的三个 $-1$。

第二行表示要想确保赢得比赛，第一步有多少种不同的取法。

hint: $1 \leq t \leq 10$，$2 \leq n \leq 21$，$0 \leq p_i \leq 10^4$，


title: [HNOI2007] 所罗门的咒语

description:
所罗门的宝藏被一个强大的咒语封印着，只有用特殊的咒语才能打开。为了给后来人留下一线开启的希望，所罗门将开启宝藏的咒语隐藏在巨大的所罗门广场。

所罗门广场由边长为1米的正方形大理石板铺成，据说由于所罗门魔法的作用，在每个雷电交加的黎明，广场上的每块大理石板会发出不同的微弱的光芒，而那些亮度大于某个值的大理石板作为一个整体来看，就是开启所罗门宝藏的咒语，但由于年久失修，有的大理石板可能产生错误的亮度。

图1为在一个雷电交加的黎明从太空看所罗门广场的一个实例。通过所罗门的藏书可以知道，开启所罗门宝藏的咒语是由15种字符0,1,2,3,4,5,6,7,8,9,A,D,E,L,X中的若干个组成的长度小于10的符号串，这些符号按照从左到右的顺序大致排成一行，如图1所示。

现已在一个雷电交加的黎明搜集到所罗门广场上各块大理石板的亮度，亮度值用0到255的整数来度量，你能破译出开启所罗门宝藏的咒语么？

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

inputFormat:
第一行包含用一个空格隔开的2个整数L和H，其中L表示所罗门广场包含的大理石板的列数，5<=L<=100，H表示所罗门广场包含的大理石板的行数, 5<=H<=100。

接下来的H行，每行有L个由一个空格隔开的整数，不妨记接下来的第i行，第J列的整数为Vij，则有0<=Vij<=255。

outputFormat: 第一行为正整数t，表示咒语的长度。第2行为一个长度为t的字符串，表示识别出的咒语。


title: [HNOI2007] 最小矩形覆盖

description: 给定一些点的坐标，求能够覆盖所有点的最小面积的矩形，输出所求矩形的面积和四个顶点坐标。

inputFormat: 第一行为一个整数 $n$，从第 $2$ 至第 $n+1$ 行每行有两个浮点数（精确到至多五位小数，不使用科学计数法），表示一个顶点的 $x$ 和 $y$ 坐标。

outputFormat: 第一行为一个浮点数，表示所求矩形的面积，接下来 $4$ 行每行表示一个顶点坐标，**按逆时针**输出顶点坐标。

hint:
$3 \le n \le 50000$，坐标范围 $\in [0,10]$。保证覆盖所有点所需要的最小矩形面积至少是 $0.1$。

如果你的矩形面积为 $S'$，正确答案为 $S$，那么当 $\frac{|S'-S|}{\max\{1,S\}}<10^{-4}$，且所有点满足在矩形内或者到矩形的距离 $<10^{-4}$ 时，你的答案会被判定为正确（你可以忽略这段话，简而言之你的答案只要不是有特别大的精度误差就可以通过）。

感谢 @intruder 提供题目简述


title: [HNOI2007] 梦幻岛宝珠

description: 给你 $n$ 颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过 $W$，且总价值最大，并输出最大的总价值。

inputFormat:
输入文件中包含多组数据。每组数据的格式如下：

第一行是两个正整数 $n$ 和 $W$，分别表示宝石的数目和最多能带走的宝石重量。

接下来的 $n$ 行，每行有两个正整数 $w_i,v_i$，分别表示第 $i$ 颗宝石的重量和价值。

最后一组数据的后面有两个 $-1$，表示文件的结束。这两个 $-1$ 并不代表一组数据，你不需对这组数据输出结果。

输入文件中数据的组数不超过 $20$。

outputFormat:
对于输入的每组数据，输出一个整数 $c$，表示小 P 最多能带走的宝石的总价值。
每个结果整数 $c$ 单独占一行。

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

对于 $100\%$ 的数据，$1\le n \le 100$，$1\le W,w_i,v_i \le 2^{30}$。
保证每个 $w_i$ 能写成 $a \times 2^b\space (a,b \in \mathbb N)$ 的形式，$a \leq 10$ , $b \leq 30$，且答案不超过 $2^{30}$。


title: [HNOI2007] 海盗分宝

description:
据说，加勒比海盗每次抢劫完，如果有金银珠宝等贵重物品，都会以特殊的仪式分宝。

他们首先将珠宝装在一个个边长为 $1$ 的土陶立方体中，并在盖子上标记出珠宝的价值 $v$。然后将这些盒子排列成一个长为 $l$，宽为 $w$ 的矩形（如果珠宝不够，可能会用空的土陶盒占据空位，并在盖子上标记价值为 $0$），第 $i$ 行第 $j$ 列的土陶盒上标记的价值为 $v_{i,j}$（其中 $0<i\leq w$，$0<j\leq l$，**左下角的土陶盒所在位置为第一行第一列**）。

海盗们按照功劳的大小，决定分宝的顺序，被轮到选取珠宝的海盗将被发给一个底面为 $m\times n$ 的矩形，高为 $h$ 的木箱子，并要求用这个木箱子来装所选土陶盒，最后盖上木箱盖子。

土陶盒的选取需要分批选取，要求每批土陶盒为一个等同于木箱底面的紧挨着的矩形区域，且木箱长为 $m$ 的边必须与土陶盒摆成矩形时长为 $w$ 的边平行。被选走的土陶盒所在位置在被选走后马上由空土陶盒填充。海盗从土陶盒摆成的矩形底部正中出发，即从第一行的第  $\lfloor \frac{w}{2} \rfloor$ 列的土陶盒的右下角出发，向上沿着据土陶盒摆成的矩形区域的最左边 $\lfloor \frac{w}{2} \rfloor$ 的直线前进。

如图中粗线箭头所示。设第 $k$ 批被选取的区域的最小角为第 $i_k$ 行第 $j_k$ 列的土陶盒，$j_k$ 必须满足 $\lfloor \frac{m}{2}+j_k-\frac{w}{2}\rfloor \leq a$，其中 $k\geq 1$，且当 $j_k=j_{k-1}$ 的时候，$i_k$ 必须满足 $i_k-i_{k-1}\geq d_1$，当 $j_k\neq j_{k-1}$ 时，$i_k$ 必须满足 $i_k-i_{k-1}\geq d_2$，其中 $k\geq 2$。

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

inputFormat:
第一行包括八个正整数，这些正整数之间用一个空格隔开，这八个正整数依次为 $l,w,m,n,h,a,d_1,d_2$。从第二行到第 $l+1$ 行，每行有 $w$ 个整数，不妨将输入中第 $i+1$ 行，第 $j$ 列的整数记做 $v_{i,j}$（$1\leq j\leq w$，$1\leq i\leq l$），分别表示土陶盒上标记的珠宝价值，同一行的整数之间用一个空格隔开。

需注意的是：**输入时 $v_{i,j}$ 是从左上角的土陶盒开始，但在求解时左下角的那个土陶盒为第 $1$ 行第 $1$ 列的土陶盒。**

outputFormat: 输出文件中的第一行为一个整数，是最多能得到的珠宝总价值 $T$。


title: [HNOI2007] 神奇游乐园

description:
经历了一段艰辛的旅程后，主人公小 P 乘坐飞艇返回。在返回的途中，小 P 发现在漫无边际的沙漠中，有一块狭长的绿地特别显眼。往下仔细一看，才发现这是一个游乐场，专为旅途中疲惫的人设计。

娱乐场可以看成是一块大小为 $n\times m$ 的区域，且这个 $n\times m$ 的区域被分成 $n\times m$ 个小格子，每个小格子中就有一个娱乐项目。

然而，小 P 并不喜欢其中的所有娱乐项目，于是，他给每个项目一个满意度。满意度为正时表示小 P 喜欢这个项目，值越大表示越喜欢。为负时表示他不喜欢，这个负数的绝对值越大表示他越不喜欢。为 $0$ 时表示他对这个项目没有喜恶。

小 P 决定将飞艇停在某个小格中，然后每步他可以移动到相邻的上下左右四个格子的某个格子中。

小 P 希望找一条路径，从飞艇所在格出发，最后又回到这个格子。

小 P 有一个习惯，从不喜欢浪费时间。因此，他希望经过每个格子都是有意义的：他到一个地方后，就一定要感受以下那里的惊险和刺激，不管自己是不是喜欢那里的娱乐项目。而且，除了飞艇所在格，其他的格子他不愿意经过两次。小 P 希望自己至少要经过四个格子。

在满足这些条件的情况下，小 P 希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗？

inputFormat:
第一行为两个正整数 $n$ 和 $m$，表示游乐场的大小为 $n\times m$。

接下来的 $n$ 行，每行有 $m$ 个整数，第 $(i + 1)$ 行的第 $j$ 个数表示游乐场的第 $i$ 行第 $j$ 列的小格子中的娱乐项目的满意度 $a_{i,j}$。同一行的两个整数之间用空格隔开。

outputFormat: 仅一行为一个整数，表示最高的满意度之和。


title: [HNOI2007] 紧急疏散EVACUATE

description: 发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

inputFormat: 输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D'，且字符间无空格。

outputFormat: 只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出'impossible'（不包括引号）。


title: [HNOI2007] 胜负一子

description:
五子棋是一种流传很广的棋类游戏，在一个 $15\times 15$ 的棋盘上，对弈双方执黑白棋子（类似于围棋），执黑子者先下，凡落下的棋子不能被提起，即不存在挪子和吃子的情况。

为了简化问题，假设黑方不存在“禁手”，“禁手”是五子棋术语，指禁止走棋子的地方。当某选手的棋子在横、竖、$45$ 度斜线方向、$135$ 度斜线方向之一先出现相连的 $5$ 个棋子时，该选手获胜。

先考虑轮到黑棋走的一盘残局，请给出黑棋获胜的最少步数和在该步数下能获胜的所有不同的下一步走法。

inputFormat: 共有 $15$ 行，每行有 $15$ 个由一个空格隔开的整数。第 $i$ 行，第 $j$ 列的整数记做 $v_{i,j}$，用 $v_{i,j}=0,1,2$ 表示第 $i$ 行，第 $j$ 列的位置为空、为黑子、为白子，从左上角开始，按从左至右，自上而下的顺序输入，即输入的第 $1$ 行第 $1$ 列整数 $v_{1,1}$ 表示第 $1$ 行第 $1$ 列位置的状态，输入的第 $15$ 行第 $15$ 列整数 $v_{15,15}$ 表示第 $15$ 行第 $15$ 列位置的状态。

outputFormat:
第一行为两个整数 $a$ 和 $b$，其中：$a$ 表示黑棋获胜的最少步数，$b$ 表示黑棋在 $a$ 步获胜的所有不同的下一步走法的种数。

从第二行到第 $b+1$ 行，每行有两个整数，分别表示黑棋在 $a$ 步获胜的一种下一步走法落子位置的行数 $i$ 和列数 $j$，要求这些走法按照 $15\times i+j$ 的大小从小到大排列。


title: [HNOI2008] GT考试

description:
阿申准备报名参加 GT 考试，准考证号为 $N$ 位数$X_1,X_2…X_n\ (0\le X_i\le 9)$，他不希望准考证号上出现不吉利的数字。
他的不吉利数字$A_1,A_2,\cdots, A_m\ (0\le A_i\le 9)$ 有 $M$ 位，不出现是指 $X_1,X_2\cdots X_n$ 中没有一段恰好等于 $A_1,A_2,\cdots ,A_m$，$A_1$ 和 $X_1$ 可以为 $0$。

inputFormat: 第一行输入 $N,M,K$ 接下来一行输入 $M$ 位的数。

outputFormat: 阿申想知道不出现不吉利数字的号码有多少种，输出模 $K$ 取余的结果。

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

对于全部数据，$N\leq10^9$，$M\leq 20$，$K\leq1000$。


title: [HNOI2008] 水平可见直线

description:
在 $x-y$ 直角坐标平面上有 $n$ 条直线 $L_1,L_2,…L_n$，若在 $y$ 值为正无穷大处往下看，能见到 $L_i$ 的某个子线段，则称 $L_i$ 为可见的，否则 $L_i$ 为被覆盖的。
例如，对于直线:
$L_1:y=x$;
$L_2:y=-x$;
$L_3:y=0$;
则 $L_1$ 和 $L_2$ 是可见的，$L_3$ 是被覆盖的。给出 $n$ 条直线，表示成 $y=Ax+B$ 的形式($|A|,|B| \le 500000$)，且 $n$ 条直线两两不重合，求出所有可见的直线。

outputFormat: 从小到大输出可见直线的编号，两两中间用空格隔开，最后一个数字后面也必须有个空格。


title: [HNOI2008] 玩具装箱

description:
P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。

P 教授有编号为 $1 \cdots n$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。

为了方便整理，P教授要求：

- 在一个一维容器中的玩具编号是连续的。

- 同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $x=j-i+\sum\limits_{k=i}^{j}C_k$。

制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$。其中 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望所有容器的总费用最小。

inputFormat:
第一行有两个整数，用一个空格隔开，分别代表 $n$ 和 $L$。

第 $2$ 到 第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 件玩具的长度 $C_i$。

outputFormat: 输出一行一个整数，代表所有容器的总费用最小是多少。

hint: 对于全部的测试点，$1 \leq n \leq 5 \times 10^4$，$1 \leq L \leq 10^7$，$1 \leq C_i \leq 10^7$。


title: [HNOI2008] 神奇的国度

description:
K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.

所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

inputFormat: 第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋友

outputFormat: 输出一个整数，最少可以分多少队


title: [HNOI2008] 越狱

description:
监狱有 $n$ 个房间，每个房间关押一个犯人，有 $m$ 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对 $100,003$ 取模。

inputFormat: 输入只有一行两个整数，分别代表宗教数 $m$ 和房间数 $n$。

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


title: [HNOI2008] 遥远的行星

description:
直线上 $N$ 颗行星，$X=i$ 处有行星 $i$，行星 $J$ 受到行星 $I$ 的作用力，当且仅当 $i \le A J$，此时 $J$ 受到作用力的大小为$F_{i->j}=\frac{M_i \times M_j}{j-i}$。

其中 $A$ 为很小的常量，故直观上说每颗行星都只受到距离遥远的行星的作用。
请计算每颗行星的受力，只要结果的相对误差不超过 5% 即可.

inputFormat:
第一行两个整数 $N$ 和 $A$。
接下来 $N$ 行输入 $N$ 个行星的质量 $M_i$

outputFormat: $N$ 行，依次输出各行星的受力情况


title: [HNOI2009] 最小圈

description:
考虑带权有向图 $G=(V,E)$ 以及 $w:E\rightarrow \R$，每条边 $e=(i,j)$（$i\neq j$，$i, j\in V$）的权值定义为 $w_{i,j}$。设 $n=|V|$。

$c=(c_1,c_2,\cdots,c_k)$（$c_i\in V$）是 $G$ 中的一个圈当且仅当 $(c_i,c_{i+1})$（$1\le i<k$）和 $(c_k,c_1)$ 都在 $E$ 中。称 $k$ 为圈 $c$ 的长度，同时记 $c_{k+1}=c_1$，并定义圈 $c=(c_1,c_2,\cdots,c_k)$ 的平均值为
$$
\mu(c)= \frac 1 k \sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}
$$
即 $c$ 上所有边的权值的平均值。设 $\mu'(G)=\min_c\mu(c)$ 为 $G$ 中所有圈 $c$ 的平均值的最小值。

给定图 $G=(V,E)$ 以及 $w:E\rightarrow \R$，求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\mu'(G)$。

inputFormat:
第一行两个正整数，分别为 $n$ 和 $m$，并用一个空格隔开。其中 $n=|V|$，$m=|E|$ 分别表示图中有 $n$ 个点 和 $m$ 条边。

接下来 $m$ 行，每行三个数 $i,j,w_{i,j}$，表示有一条边 $(i,j)$ 且该边的权值为 $w_{i,j}$，注意边权可以是实数。输入数据保证图 $G=(V,E)$ 连通，存在圈且有一个点能到达其他所有点。

outputFormat: 一个实数 $\mu'(G)$，要求精确到小数点后 $8$ 位。

hint:
对于 $100\%$ 的数据，$2\leq n\le 3000$，$1\leq m\le 10000$，$|w_{i,j}| \le 10^7$，$1\leq i, j\leq n$ 且 $i\neq j$。

------------
提示：本题存在 $O(nm)$ 的做法，但是 $O(nm\log n)$ 的做法也可以通过。


title: [HNOI2009] 有趣的数列

description:
我们称一个长度为 $2n$ 的数列是有趣的，当且仅当该数列满足以下三个条件：

- 它是从 $1 \sim 2n$ 共 $2n$ 个整数的一个排列 $\{a_n\}_{n=1}^{2n}$；

- 所有的奇数项满足 $a_1<a_3< \dots < a_{2n-1}$，所有的偶数项满足 $a_2<a_4< \dots <a_{2n}$；

- 任意相邻的两项 $a_{2i-1}$ 与 $a_{2i}$ 满足：$a_{2i-1}<a_{2i}$。

对于给定的 $n$，请求出有多少个不同的长度为 $2n$ 的有趣的数列。
因为最后的答案可能很大，所以只要求输出答案对 $p$ 取模。

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

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


title: [HNOI2009] 梦幻布丁

description:
$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。

例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.

inputFormat:
第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。
接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型：
- 若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。
- 若 $op = 2$，则表示一次询问。

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

hint:
### 样例 1 解释
初始时布丁颜色依次为 $1, 2, 2, 1$，三段颜色分别为 $[1, 1], [2, 3], [4, 4]$。
一次操作后，布丁的颜色变为 $1, 1, 1, 1$，只有 $[1, 4]$ 一段颜色。

### 数据规模与约定

对于全部的测试点，保证 $1 \leq n, m \leq 10^5$，$1 \leq a_i ,x, y \leq 10^6$。

### 提示

请注意，**不保证**颜色的编号不大于 $n$，也**不保证** $x \neq y$，$m$ **不是**颜色的编号上限。


title: [HNOI2009] 通往城堡之路

description:
听说公主被关押在城堡里，彭大侠下定决心：不管一路上有多少坎坷，不管城堡中的看守有多少厉害，不管救了公主之后公主会不会再被抓走，不管公主是否漂亮、是否会钟情于自己，他将义无反顾地朝着城堡前进。

可是，通往城堡的路上出现了一些情况。抽象地说，假象地图在二维平面的第一象限。在每个横轴的x位置上有一个高为hx的支撑点，如果彭大侠没有跳到支撑点上，那么他就会掉下去，牺牲在路途。

开始时彭大侠在起点（1，h1）处，而城堡的入口在（n，hn）处。彭大侠每次可以从支撑点（x，hx）跳到支撑点（x+1，hx+1）。但是彭大侠每次的跳跃能量只有d，也就是说，每次跳跃必须满足条件|hx+1-hn|<=d。换句话说，如果两个相邻支撑点的纵向落差大于d，那么彭大侠就无法跳跃了！幸运的是，彭大侠还有一个杀手锏。
在起点处，他可以花一个金币，把某个支撑点升高1个单位，或者降低1个单位。但是，起点处和城堡入口处的支撑点高度不能改变，并且一旦离开起点彭大侠就无法使用该杀手锏。

彭大侠被告知100个金币可兑换一单位生命。于是他希望通过少花金币来保存更多单位的生命。

他终于找到了你这位热心的高手，请你帮他规划一下以便耗费尽量少的金币来到达城堡。

inputFormat: 文件第一行包含一个整数m(m<=5)，表示问题求解次数。接下来的2m行依次表示每次求解的输入数据块。每个输入数据块占2行，其中第一行包含两个整数n和d，分别表示从起点到城堡入口处必须经过的支撑点数和每次跳跃允许的最大纵向落差，n和d之间用空格隔开，输入数据保证2<=n<=5000，0<=d<=109；第二行包含用空格隔开的n个非负整数h1、h2、...、hn，其中hi(1<=i<=n)表示第i个支撑点的高度，特别地，h1表示彭大侠出发时所在支撑点的高度，hn表示城堡入口所在支撑点的高度，输入数据保证对所有1<=i<=n有0<=hi<=109。

outputFormat: 有m行，第I(1<=I<=m)行表示第I次求解时彭大侠到达城堡必须耗费的最少金币数量。若无论怎样使用杀手锏他都无法到达城堡，则输出impossible。输入数据保证答案在int64范围之内。

hint:
对样例中的第一个输入数据块，d=2，把第三个支撑点降低3个单位，把第六个支撑点降低1个单位，把第七个支撑点升高2个单位，原序列变成：4 5 7 6 6 8 6 7 9 8，这时任意相邻支撑点的纵向落差没有超过2，彭大侠可以到达城堡！

对样例中的第二个输入数据块，d=1，这时不管怎样调节第二个支撑点的高度，都无法使任意相邻支撑点的纵向落差不超过1。

对样例中的第三个输入数据块，d=2，这时，把第二个支撑点升高1个单位，把第三个支撑点降低3个单位就满足条件了。

【数据规模】

     20%     n<=100

     40%     n<=1000

100%    n<=5000


title: [HNOI2010] 弹飞绵羊

description:
某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。

游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$ 个装置，则绵羊被弹飞。

绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

inputFormat:
第一行包含一个整数 $n$，表示地上有 $n$ 个装置，装置的编号从 $0 \sim n-1$。

接下来一行有 $n$ 个正整数，依次为那 $n$ 个装置的初始弹力系数。

第三行有一个正整数 $m$，表示操作次数。接下来 $m$ 行每行至少有两个数 $i,j$。

- 若 $i=1$，你要输出从编号为 $j$ 的装置出发被弹几次后被弹飞

- 若 $i=2$，则还会再输入一个正整数 $k$，表示编号为 $j$ 的弹力装置的系数被修改成 $k$。

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


title: [HNOI2010] 公交线路

description:
小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。 作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路：

1. 设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。
2. 每个车站必须被一辆且仅一辆公交车经过（始发站和终点站也算被经过）。
3. 公交车只能从编号较小的站台驶往编号较大的站台。
4. 一辆公交车经过的相邻两个站台间距离不得超过Pkm。

在最终设计线路之前，小Z想知道有多少种满足要求的方案。由于答案可能很大，你只需求出答案对30031取模的结果。

inputFormat: 仅一行包含三个正整数N K P，分别表示公交车站数，公交车数，相邻站台的距离限制。N<=10^9，1<P<=10，K<N，1<K<=P

outputFormat: 仅包含一个整数，表示满足要求的方案数对30031取模的结果。


title: [HNOI2010] 合唱队

description:
为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 $n$ 个人，第 $i$ 个人的身高为 $h_i$ 米（$1000 \le h_i \le 2000$），并已知任何两个人的身高都不同。假定最终排出的队形是 $A$ 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：

- 第一个人直接插入空的当前队形中。

- 对从第二个人开始的每个人，如果他比前面那个人高（$h$ 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（$h$ 较小），那么将他插入当前队形的最左边。

当 $n$ 个人全部插入当前队形后便获得最终排出的队形。

例如，有 $6$ 个人站成一个初始队形，身高依次为 $1850, 1900, 1700, 1650, 1800, 1750$，
那么小 A 会按以下步骤获得最终排出的队形：

- $1850$。

- $1850, 1900$，因为 $1900 > 1850$。

- $1700, 1850, 1900$，因为 $1700 < 1900$。

- $1650, 1700, 1850, 1900$，因为 $1650 < 1700$。

- $1650, 1700, 1850, 1900, 1800$，因为 $1800 > 1650$。

- $1750, 1650, 1700, 1850, 1900, 1800$，因为 $1750 < 1800$。

因此，最终排出的队形是 $1750, 1650, 1700, 1850, 1900, 1800$。

小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。

请求出答案对 $19650827$ 取模的值。

inputFormat:
第一行一个整数 $n$。
第二行 $n$ 个整数，表示小 A 心中的理想队形。

outputFormat: 输出一行一个整数，表示答案 $\bmod 19650827$ 的值。


title: [HNOI2010] 城市建设

description:
PS 国是一个拥有诸多城市的大国。国王 Louis 为城市的交通建设可谓绞尽脑汁。Louis 可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。

Louis 希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变。Louis 会不断得到某道路的修建代价改变的消息。他希望每得到一条消息后能立即知道使城市连通的最小花费总和。Louis 决定求助于你来完成这个任务。

inputFormat:
第一行包含三个整数 $n,m,q$，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。

接下来 $m$ 行，第 $i+1$ 行有三个用空格隔开的整数 $x_i,y_i,z_i$，表示在城市 $x_i$ 与城市 $y_i$ 之间修建道路的代价为 $z_i$。接下来 $q$ 行，每行包含两个数 $k,d$，表示输入的第 $k$ 个道路的修建代价修改为 $d$（即将 $z_k$ 修改为 $d$）。

outputFormat: 输出包含 $q$ 行，第 $i$ 行输出得知前 $i$ 条消息后使城市连通的最小花费总和。

hint:
### 数据规模与约定
- 对于 $20\%$ 的数据，$n\le 10^3$，$m,q\le 6\times 10^3$。
- 对于另外 $20\%$ 的数据，$n\le 10^3$，$m\le 5\times 10^4$，$q\le 8\times 10^3$。修改后的代价不会比之前的代价低。
- 对于 $100\%$ 的数据，$1\le n\le 2\times 10^4$，$1\le m,q\le 5\times 10^4$，$1\le x_i,y_i\le n$，$0\le z_i\le 5\times 10^7$。


title: [HNOI2010] 物品调度

description:
现在找工作不容易，Lostmonkey 费了好大劲才得到 fsk 公司基层流水线操作员的职位。流水线上有 $n$ 个位置，从 $0$ 到 $n - 1$ 依次编号，一开始 $0$ 号位置是空的，其它的位置 $i$ 上有编号为 $i$ 的盒子。Lostmonkey 要按照以下规则重新排列这些盒子。

规则由五个数描述，$q, p, m, d, s$，$s$ 表示空位的最终位置。

首先生成一个序列 $c$，$c_0=0$，$c_{i+1}=(c_i\times q+p)\bmod m$。

接下来从第一个盒子开始依次生成每个盒子的最终位置 $pos_i$，$pos_i=(c_i+d\times x_i+y_i)\bmod n$，$x_i,y_i$ 是为了让第 $i$ 个盒子不与之前的盒子位置相同的由你设定的非负整数，且 $pos_i$ 还不能为 $s$。

如果有多个序列 $x,y$ 满足要求，你需要选择 $y$ 的字典序最小的，当 $y$ 相同时选择 $x$ 字典序最小的。这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。

问把所有的盒子移动到最终位置所需的最少步数。

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

接下来 $t$ 行，每行六个数，$n, s, q, p, m, d$ 意义如上所述。

outputFormat: 对于每组数据输出一个数占一行，表示最少移动步数。

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

第 $1$ 个到第 $7$ 个盒子的最终位置依次是：$[2, 5, 6, 4, 1, 0, 7]$。

**【数据范围】**

对于 $30 \%$ 的数据，$n \le 100$，
对于 $100 \%$ 的数据，$1 \le t \le 20$，$1 \le n \le 100000$，$0 \le s < n$。

其余所有数字均为不超过 $100000$ 的正整数。

**【提示】**

计算过程可能超过整型范围。


title: [HNOI2010] 矩阵

description:
小 Z 近日闲来无事，便研究起矩阵来。他先写了一个 $N\times M$ 的矩阵，每个格子里填入了一个小于 $P$ 的非负整数，然后他对于每个 $2\times 2$ 的子矩阵，算出了其中数的和。

譬如 $N=3, M=3, P=3$，小 Z 写的矩阵如下：

$$ A = \begin{pmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{pmatrix} $$

共有 $4$ 个 $2\times 2$ 的子矩阵，容易算出它们的和如下：

$$ A = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 4 & 5 \\ 0 & 5 & 3 \end{pmatrix} $$

(第一行和第一列的 $0$ 是为了格式美观而添加进去的)

现在小 Z 想试一试能不能根据这些和推算出原矩阵。由于小 Z 的数学并不好，因此这个任务就交给你了。

当然，小 Z 早就发现了，解很可能不唯一，譬如下面的矩阵算出的和与 $A$ 相同：

$$ A = \begin{pmatrix} 0 & 2 & 1 \\ 0 & 2 & 0 \\ 2 & 1 & 0 \end{pmatrix} $$

示意图在有多个矩阵满足要求的情况下请你输出字典序最小的那一个。

字典序的比较方式如下：对于两个解矩阵 $X$ 和 $Y$，找到 $X$ 和 $Y$ 不同的位置中行数最小的那一个格子，若有多个则取列数最小的那个格子，该位置较小的矩阵字典序较小。

譬如上述的矩阵 $A$ 和 $B$，第一个不同的格子应是第一行第二个格子，而 $A[1][2] < B[1][2]$，故矩阵 $A$ 的字典序比 $B$ 小。

另外，小 Z 的数学还没有差到加法都做错，因此保证输入数据都是有解的。

inputFormat: 第一行包含三个正整数 $N, M, P$ 表示矩阵的行数列数以及每个数的范围，接下来 $N$ 行每行包含 $M$ 个非负整数，其中第 $i$ 行第 $j$ 个数表示以格子 $(i,j)$ 为右下角的 $2 \times 2$ 子矩阵中的数的和。保证第一行与第一列的数均为 $0$，且每个和都不超过 $4 (P-1)$。

outputFormat: 包含 $N$ 行，每行 $M$ 个整数，描述你求出的矩阵，相邻的整数用空格分开。（行末不要有多余空格）


title: [HNOI2010] 平面图判定

description: 若能将无向图 $G=(V, E)$ 画在平面上使得任意两条无重合顶点的边不相交，则称 $G$ 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。

inputFormat: 输入文件的第一行是一个正整数 $T$，表示数据组数 (每组数据描述一个需要判定的图)。接下来从输入文件第二行开始有 $T$ 组数据，每组数据的第一行是用空格隔开的两个正整数 $N$ 和 $M$，分别表示对应图的顶点数和边数。紧接着的 $M$ 行，每行是用空格隔开的两个正整数 $u$ 和 $v$ $\left(1\leq u,v\leq N\right)$，表示对应图的一条边 $\left(u,v\right)$, 输入的数据保证所有边仅出现一次。每组数据的最后一行是用空格隔开的 $N$ 个正整数，从左到右表示对应图中的一个哈密顿回路：$V_1,V_2,…,V_N$，即对任意 $i\not=j$ 有 $V_i\not=V_j$ 且对任意 $1\leq i\leq N-1$ 有 $\left(V_i,V_{i+1}\right)\in E$ 及 $\left(V_1,V_N\right)\in E$。输入的数据保证 $100\%$ 的数据满足 $T\leq100,3\leq N\leq200,M\leq10000$。

outputFormat: 包含 $T$ 行，若输入文件的第 $i$ 组数据所对应图是平面图，则在第 $i$ 行输出 $\text{YES}$，否则在第 $i$ 行输出 $\text{NO}$，注意均为大写字母

hint:
感谢@hibiki 对题目进行修正

感谢@@Anguei  提供latex题面


title: [HNOI2010] 取石头游戏

description:
A 公司正在举办一个智力双人游戏比赛 - 取石子游戏，游戏的获胜者将会获得 A 公司提供的丰厚奖金，因此吸引了来自全国各地的许多聪明的选手前来参加比赛。

与经典的取石子游戏相比，A 公司举办的这次比赛的取石子游戏规则复杂了很多：

* 总共有 $N$ 堆石子依次排成一行，第 $i$ 堆石子有 $a_i$ 个石子。

* 开始若干堆石子已被 A 公司故意拿走。

* 然后两个玩家轮流来取石子，每次每个玩家可以取走一堆中的所有石子，但有一个限制条件：一个玩家若要取走一堆石子，则与这堆石子相邻的某堆石子已被取走(之前被某个玩家取走或开始被 A 公司故意拿走)。注意：第 $1$ 堆石子只与第 $2$ 堆石子相邻，第 $N$ 堆石子只与第 $N-1$ 堆石子相邻，其余的第 $i$ 堆石子与第 $i-1$ 堆和第 $i+1$ 堆石子相邻。

* 所有石子都被取走时，游戏结束。谁最后取得的总石子数最多，谁就获得了这场游戏的胜利。

作为这次比赛的参赛者之一，绝顶聪明的你，想知道对于任何一场比赛，如果先手者和后手者都使用最优的策略，最后先手者和后手者分别能够取得的总石子数分别是多少。

inputFormat: 第一行是一个正整数 $N$，表示有多少堆石子。输入文件第二行是用空格隔开的 $N$ 个非负整数 $a_1, a_2,\ldots, a_N$，其中 $a_i$ 表示第 $i$ 堆石子有多少个石子，$a_i  = 0$ 表示第 $i$ 堆石子开始被 A 公司故意拿走。输入的数据保证 $0\leq a_i\leq 10^8$，并且至少有一个 $i$ 使得 $a_i = 0$。

outputFormat: 仅包含一行，为两个整数，分别表示都使用最优策略时，最后先手者和后手者各自能够取得的总石子数，并且两个整数间用一个空格隔开。

hint:
样例解释：两个玩家都使用最优策略时取走石子的顺序依次为 $9, 2, 1, 4, 7, 3$，因此先手者取得 $9 + 1 + 7 = 17$ 个石子，后手者取得 $2 + 4 + 3 = 9$ 个石子。

$30\%$ 的数据满足 $2\leq N\leq 100$。

$100\%$ 的数据满足 $2\leq N\leq 10^6$。


title: [HNOI2011] XOR和路径

description:
给定一个无向连通图，其节点编号为 $1$ 到 $N$，其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算“XOR 和”时也要被重复计算相应多的次数。

直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 $1$ 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 $N$ 号节点为止，便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

inputFormat: 输入文件的第一行是用空格隔开的两个正整数 $N$ 和 $M$，分别表示该图的节点数和边数。紧接着的 $M$ 行，每行是用空格隔开的三个非负整数 $u,v$ 和 $w$。$(1\le u,v\le N$，$0\le w\le 10^9)$，表示该图的一条边 $(u,v)$，其权值为 $w$。输入的数据保证图连通。

outputFormat: 输出文件仅包含一个实数，表示上述算法得到的路径的“XOR 和”的期望值，要求保留三位小数。（建议使用精度较高的数据类型进行计算）

hint:
### 样例解释

有 $\dfrac{1}{2}$ 的概率直接从 $1$ 号节点走到 $2$ 号节点，该路径的“XOR和”为 $3$；有 $\dfrac{1}{4}$ 的概率从 $1$ 号节点走一次 $1$ 号节点的自环后走到 $2$ 号节点，该路径的“XOR和”为 $1$；有 $\dfrac{1}{8}$ 的概率从 $1$ 号节点走两次 $1$ 号节点的自环后走到 $2$ 号节点，该路径的“XOR和”为 $3$…依此类推，可知“XOR和”的期望值为：$\dfrac{3}{2}+\dfrac{1}{4}+\dfrac{3}{8}+\dfrac{1}{16}+\dfrac{3}{32}+\cdots=\dfrac{7}{3}$，约等于 $2.333$。

### 数据范围

- $30\%$ 的数据满足 $N\le 30$。
- $100\%$ 的数据满足 $2\le N\le 100$，$M\le 10000$，但是图中可能有重边或自环。


title: [HNOI2011] 任务调度

description:
有 $n$ 个任务和两台机器 A 与 B。每个任务都需要既在机器 A 上执行，又在机器 B 上执行，

第 $i$ 个任务需要在机器 A 上执行时间 $a_i$，且需要在机器 B 上执行时间 $b_i$。最终的目标是所有任务在 A 和 B 上都执行完，且希望执行完所有任务的总时间尽量少。当然问题没有这么简单，有些任务对于先在机器 A 上执行还是先在机器 B 上执行有一定的限制。据此可将所有任务分为三类：

1. 任务必须先在机器 A 上执行完然后再在机器 B 上执行。
2. 任务必须先在机器 B 上执行完然后再在机器 A 上执行。
3. 任务没有限制，既可先在机器 A 上执行，也可先在机器 B 上执行。

现在给定每个任务的类别和需要在机器 A 和机器 B 上分别执行的时间，问使所有任务都能按规定完成所需要的最少总时间是多少。

inputFormat:
输入的第一行只有一个正整数 $n$，表示任务的个数。

接下来的 $n$ 行，每行是用空格隔开的三个正整数 $t_i,a_i,b_i$，分别表示第 $i$ 个任务的类别（类别 $1$，$2$，$3$ 的定义如上）以及第 $i$ 个任务需要在机器 A 和机器 B 上分别执行的时间。

outputFormat: 输出仅包含一个正整数，表示所有任务都执行完所需要的最少总时间。

hint:
#### 样例 1 解释

一种最优任务调度方案为：

机器 A 上执行的各任务依次安排如下：

任务 $1\ (0\to 5)$，任务 $2\ (5\to 11)$, 任务 $3\ (11\to 13)$；

机器 B 上执行的各任务依次安排如下：

任务 $3\ (0 \to 6)$, 任务 $1\ (6 \to 13)$, 任务 $2\ (13 \to14)$，

这样，所有任务都执行完所需要的总时间为 $14$。

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 20$，$1\le a_i\le 10^3$，$1\le t_i\le 3$，并保证 $t_i=3$ 的 $i$ 不超过 $10$ 个。


title: [HNOI2011] 勾股定理

description:
沫沫最近在研究勾股定理。对于两个正整数 A 与 B，若存在正整数 C 使得 A2+B2=C2，且 A 与 B 互质，则称(A,B)为一个互质勾股数对。

有一天，沫沫得到了 N 根木棍，其长度都是正整数，她准备从中挑选出若干根木棍来玩拼图游戏，为了使拼出的图案有凌乱美，她希望挑选出的木棍中任意两根的长度均不是互质勾股数对。现在，沫沫想知道有多少种满足要求的挑选木棍的方案。由于答案可能很大，你只要输出答案对 $10^9+7$ 取模的结果。

inputFormat:
从文件input.txt中读入数据，输入文件第一行是一个正整数N，表示共有多少根木棍。

输入文件第二行是用空格隔开的N个正整数h1, h2, …, hN，其中对1≤i≤N，hi表示第i根木棍的长度。

输入的数据保证30%的数据满足对$1≤i≤N$有$1≤h_i≤3000$，

另外30%的数据满足对$1≤i≤N$有$1≤hi≤200000$，

剩下的40%的数据满足对$1≤i≤N$有$20000≤h_i≤1000000$，

100%的数据满足$N≤1000000$。

outputFormat: 输出文件 output.txt 仅包含一个非负整数，表示满足要求的挑选木棍的方案数对 109+7 取模的结果。


title: [HNOI2011] 卡农

description:
众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。

他将声音分成 $n$ 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 $1$ 到 $n$ 个音阶构成的和声，即从 $n$ 个音阶中挑选若干个音阶同时演奏出来。

为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段音乐中每个音阶被奏响的次数为偶数。

现在的问题是：小余想知道包含 $m$ 个片段的音乐一共有多少种。
两段音乐 $a$ 和 $b$ 同种当且仅当将 $a$ 的片段重新排列后可以得到 $b$。例如：假设 $a$ 为 $\{\{1,2\},\{2,3\}\}$，$b$ 为 $\{\{2,3\},\{1,2\}\}$，那么 $a$ 与 $b$ 就是同种音乐。

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

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

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


title: [HNOI2011] 括号修复 /  [JSOI2011]括号序列

description:
一个合法的括号序列是这样定义的：

1.    空串是合法的。
2.    如果字符串 `S` 是合法的，则`(S)`也是合法的。
3.    如果字符串 `A` 和 `B` 是合法的，则 `AB` 也是合法的。

现在给你一个长度为 $n$ 的由`(`和`)`组成的字符串，位置标号从 $1$ 到 $n$。对这个字符串有下列四种操作：

-  `Replace a b c`：将 $[a,b]$ 之间的所有括号改成 $c$。假设原来的字符串为：`))())())(`，那么执行操作 `Replace 2 7 (`  后原来的字符串变为：`)(((((()(`。

-  `Swap a b`：将 $[a,b]$ 之间的字符串翻转。假设原来的字符串为：`))())())(`，那么执行操作 `Swap 3 5` 后原来的字符串变为：`))))(())(`。

-  `Invert a b`：将 $[a,b]$ 之间的 `(` 变成 `)` ，`)` 变成 `(`。假设原来的字符串为：`))())())(`，那么执行操作 `Invert 4 8` 后原来的字符串变为：`))((()(((`。

-  `Query a b`：询问 $[a,b]$ 之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的 `(` 变成 `)` 或 `)` 变成 `(`。注意执行操作 `Query` 并不改变当前的括号序列。假设原来的字符串为：`))())())(`，那么执行操作 `Query 3 6` 的结果为 $2$，因为要将位置 $5$ 的`)`变成`(`并将位置 $6$ 的`(`变成`)`。

inputFormat:
输入文件的第一行是用空格隔开的两个正整数 $n,q$，分别表示字符串的长度和将执行的操作个数。

第二行是长度为 $n$ 的初始字符串 $S$。接下来的 $q$ 行是将依次执行的$q$个操作，其中操作名与操作数之间以及相邻操作数之间均用空格隔开。

outputFormat: 对于每个 `Query` 操作，输出一行一个整数表示答案。输入数据保证有解。

samples:
4 5
((((
Replace 1 2 )
Query 1 2
Swap 2 3
Invert 3 4
Query 1 4

hint:
### 样例解释

输入中有 $2$ 个 `Query` 操作，所以输出有 $2$ 行。
执行第一个 `Query` 操作时的括号序列为 `))((`，因改变第 $1$ 位可使 $[1,2]$ 之间的字符串变成合法的括号序列，故输出的第一行为 `1`。

执行第二个 `Query` 操作时的括号序列为 `)(()`，因要改变第 $1$ 位和第 $2$ 位才能使 $[1,4]$ 之间的字符串变成合法的括号序列，故输出的第二行为 `2`。

### 数据范围

对于 $30\%$ 的数据，$1\le n,q \le 3000$；
对于 $100\%$ 的数据，$1\le n,q \le 10^5$。


title: [HNOI2011] 数学作业

description:
小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：

给定正整数 $n,m$，要求计算 $\text{Concatenate}(n) \bmod \ m$  的值，其中 $\text{Concatenate}(n)$ 是将 $1 \sim n$ 所有正整数 顺序连接起来得到的数。

例如，$n = 13$，$\text{Concatenate}(n) = 12345678910111213$。小 C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

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

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


title: [HNOI2011] 数矩形

description:
最近某歌手在研究自己的全球巡回演出计划，他将所有心仪的城市都用平面上的一个点来表示，并打算从中挑选出 4 个城市作为这次巡回演出的地点。

为了显示自己与众不同，他要求存在一个矩形使得挑选出的 4 个点恰好是这个矩形的 4 个顶点，并且希望这个矩形的面积最大。

这可急坏了其经纪人，于是他向全球歌迷征集方案，当然你这位歌迷一定不会错过这个机会。

inputFormat: 从文件input.txt中读入数据，输入文件的第一行是一个正整数$N$，表示平面上点的个数(即某歌手心仪的城市数)。接下来的$N$行，每行是由空格隔开的两个整数$X_i$和$Y_i$,表示其对应点的坐标。20%的数据满足$N\leq 500$，100%的数据满足$N\leq 1500$，$-10^8\leq X_i,Y_i\leq 10^8$，且输入数据保证答案存在。

outputFormat: 输出文件 output.txt 仅包含一个非负整数，表示最大的矩形面积。


title: [HNOI2011] 赛车游戏

description:
名歌手LAALA最近迷上了一款赛车游戏，游戏中开车的玩家在不同的路段需要选择不同的速度，使得自己在最短的时间内到达终点。开始游戏时，车内的初始油量为f，所以游戏的关键是如何在速度和耗油量之间实现平衡。

LAALA 经过一段时间的研究后，发现这款游戏可以用一个简单的数学模型来描述，具体来说：从起点到终点的路线可以被简化成折线段，每条线段代表一个上坡或者下坡，若在一段斜率为 s(s>0 代表上坡，s=0 代表平地，s<0 代表下坡)的道路上以速度 v km/h 行驶，则每公里的耗油量为 max(0,av+bs)，其中 a 和 b 为游戏的内置参数，分别表示在平地行驶时的耗油率及斜坡对耗油量的影响(b 恒为正)。这里假设，加速和减速不耗油，且看成是瞬间完成的，所以即使在同一条线段上也可采取以不同的速度行驶的策略来缩短耗费的时间。

由于 LAALA 在以前的游戏中表现不佳，现在使用的车型依然是系统初始分配的，所以它的速度不能超过 vmax km/h。在获得这些参数后，LAALA 想知道在初始油量受限的情况下（中途不许加油）自己能得到的最佳成绩是多少。作为 LAALA 的歌迷，你能帮帮他吗?

inputFormat: 从文件input.txt中读入数据，输入文件的第一行是一个正整数T，表示数据组数。对每组数据，第一行是用空格隔开的4个浮点数a、b、vmax和f，其中a、b和vmax的意义如前所述，f表示初始油量，其单位也与前面的描述保持一致。第二行是一个正整数r，表示线段的数目。接下来的r行，每行是用空格隔开的2个浮点数xi和yi，分别表示在标准笛卡耳坐标系下该线段在水平方向和垂直方向的改变量(单位为米)。

outputFormat: 输出文件 output.txt 包含 T 行，依次对应输入中的 T 组数据。对某组数据，若基于初始油量无法到达终点，则对应行输出 IMPOSSIBLE，否则输出最少需要的时间(单位为小时)。

hint:
【数据范围】

100%的数据满足 T≤100,0.1≤a≤100,0.1≤b≤100,10≤vmax≤200,0≤f≤50,r≤10000,1≤xi≤1000,-1000≤yi≤1000，且如果问题有解，那么答案不超过 24。

你所输出的答案需要恰好保留到小数点后 5 位,当且仅当你的输出与标准答案完全一致时你的输出才被视作正确。


title: [HNOI2012] 三角形覆盖问题

description:
二维平面中，给定   N个等腰直角三角形（每个三角形的两条直角边分别平行于坐标轴，斜边从左上到右下）。我们用三个非负整数( x, y, d)来描述这样一个三角形，三角形三个顶点的坐标 分别为(x, y), (x + d, y)和(x, y +     d)。要求计算这   N个三角形所覆盖的总面积。例如，下图有 3 个三角形，覆盖的总面积为 11.0。

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

inputFormat:
输入文件第一行为一个正整数N，表示三角形的个数。

接下来的 N行每行有用空格隔开的三个非负整数，x, y, d，描述一个三角形的顶点坐标，分别为(x, y), (x + d, y), ( x, y+d)，其中 x, y, d 满足0<= x, y, d<=1000000。

outputFormat: 仅包含一行，为一个实数  S，表示所有三角形所覆盖的总面积，输出恰好保留一位小数。输入数据保证  S<=2^31 。


title: [HNOI2012] 与非

background: 如果你能提供题面或者题意简述，请直接在讨论区发帖，感谢你的贡献。

description:
NAND（与非）是一种二元逻辑运算，其运算结果为真当且仅当两个输入的布尔值不全为真。NAND运算的真值表如下（1表示真，0表示假）:

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

两个非负整数的NAND是指将它们表示成二进制数，再在对应的二进制位进行NAND运算。由于两个二进制数的长度可能不等，因此一般约定一个最高位K，使得两个数的二进制表示都不 超过K位，不足K位的在高位补零。给定N个非负整数A1,A2......AN和约定位数K，利用NAND运算与括号，每个数可以使用任意次，请你求出范围[L,R]内可以被计算出的数有多少个。

inputFormat: 输入文件第一行是用空格隔开的四个正整数N，K，L和R，接下来的一行是N个非负整数A1,A2......AN，其含义如上所述。 100%的数据满足K<=60且N<=1000,0<=Ai<=2^k-1,0<=L<=R<=10^18

outputFormat: 仅包含一个整数，表示[L,R]内可以被计算出的数的个数

hint: 样例1中，(3 NAND 4) NAND (3 NAND 5) = 1，5 NAND 5 = 2，3和4直接可得。


title: [HNOI2012] 双十字

description:
在 C 部落，双十字是非常重要的一个部落标志。所谓双十字，如下面两个例子，由两条水平的和一条竖直的 `1` 线段组成：

```
..........
....1.....      ..1..
..11111...      .111.
....1.....      ..1..
.1111111..      11111
....1.....      ..1..
....1.....
..........
```

合法的双十字要求满足以下几个限制：
- 两条水平的线段不能在相邻的两行。
- 竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。
- 竖直线段必须将两条水平线段严格划分成相等的两半。
- 上方的水平线段必须严格短于下方的水平线段。

所以上面右边的例子是满足要求的最小的双十字。

现在给定一个 $R\times C$ 的 `01` 矩阵，要求计算出这个 `01` 矩阵中有多少个双十字。例如下面这个例子，`01` 矩阵如下：

```
10001011
10111111
10001101
11111110
11111111
11101011
```

我们可以找到 $5$ 个满足条件的双十字，分别如下：

```
....1...  ....1...  ....1...
...111..  ...111..  ...111..
....1...  ....1...  ....1...
..11111.  ..11111.  ....1...
....1...  ....1...  ..11111.
........  ....1...  ....1...

....1...  ....1...
...111..  ..11111.
....1...  ....1...
....1...  ....1...
.1111111  .1111111
....1...  ....1...
```

注意最终的结果可能很大，只要求输出双十字的个数 $\bmod\ 10^9+9$ 的值。

inputFormat:
第一行为用空格隔开的两个正整数 $R$ 和 $C$，分别表示 `01` 矩阵的行数和列数。

第二行是一个非负整数 $N$，表示 `01` 矩阵中 `0` 的个数。

接下来的 $N$ 行，每行为用空格隔开的两个正整数 $x$ 和 $y$（$1\le x\le R,1\le y\le C$），表示 $(x,y)$ 是 `0`。数据保证 $N$ 个 `0` 的坐标两两不同。

outputFormat: 一行一个整数，为双十字的个数 $\bmod\ 10^9+9$ 的值。


title: [HNOI2012] 射箭

description:
沫沫最近在玩一个二维的射箭游戏，如下图 $1$ 所示，这个游戏中的 $x$ 轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。

沫沫控制一个位于 $(0,0)$ 的弓箭手，可以朝 $0$ 至 $90$ 中的任意角度（不包括 $0$ 度和 $90$ 度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些只有端点被射中的靶子。

这个游戏有多种模式，其中沫沫最喜欢的是闯关模式。

在闯关模式中，第一关只有一个靶子，射中这个靶子即可进入第二关，这时在第一关的基础上会出现另外一个靶子，若能够一箭双雕射中这两个靶子便可进入第三关，这时会出现第三个靶子。依此类推，每过一关都会新出现一个靶子，在第 $K$ 关必须一箭射中前 $K$ 关出现的所有 $K$ 个靶子才能进入第 $K+1$ 关，否则游戏结束。

沫沫花了很多时间在这个游戏上，却最多只能玩到第七关“七星连珠”，这让她非常困惑。于是她设法获得了每一关出现的靶子的位置，想让你告诉她，最多能通过多少关？

inputFormat:
输入文件第一行是一个正整数 $N$，表示一共有 $N$ 关。

接下来有 $N$ 行，第 $i+1$ 行是用空格隔开的三个正整数 $x_i,y_{i1},y_{i2}\ (y_{i1}<y_{i2})$，表示第 $i$ 关出现的靶子的横坐标是 $x_i$，纵坐标的范围是从 $y_{i1}$ 到 $y_{i2}$。

outputFormat: 仅包含一个整数，表示最多的通关数。

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

### 数据范围及约定

- $30\%$ 的数据满足 $N \le 100$；
- $50\%$ 的数据满足 $N \le 5000$；
- $100\%$ 的数据满足 $N \le 100000$ 且给出的所有坐标不超过 $10^9$。


title: [HNOI2012] 排队

description: 某中学有 $n$ 名男同学，$m$ 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）

inputFormat: 只有一行且为用空格隔开的两个非负整数 $n$ 和 $m$，其含义如上所述。

outputFormat: 仅一个非负整数，表示不同的排法个数。注意答案可能很大。


title: [HNOI2012] 永无乡

description:
永无乡包含 $n$ 座岛，编号从 $1$ 到 $n$ ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 $n$ 座岛排名，名次用 $1$  到 $n$ 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干座（含 $0$ 座）桥可以 到达岛 $b$ ，则称岛 $a$ 和岛 $b$ 是连通的。

现在有两种操作：

`B x y` 表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。

`Q x k` 表示询问当前与岛 $x$ 连通的所有岛中第 $k$ 重要的是哪座岛，即所有与岛 $x$ 连通的岛中重要度排名第 $k$ 小的岛是哪座，请你输出那个岛的编号。

inputFormat:
第一行是用空格隔开的两个整数，分别表示岛的个数 $n$ 以及一开始存在的桥数 $m$。

第二行有 $n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的岛屿的排名 $p_i$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一开始存在一座连接编号为 $u$ 的岛屿和编号为 $v$ 的岛屿的桥。

接下来一行有一个整数，表示操作个数 $q$。

接下来 $q$ 行，每行描述一个操作。每行首先有一个字符 $op$，表示操作类型，然后有两个整数 $x, y$。
- 若 $op$ 为 `Q`，则表示询问所有与岛 $x$ 连通的岛中重要度排名第 $y$ 小的岛是哪座，请你输出那个岛的编号。
- 若 $op$ 为 `B`，则表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。

outputFormat: 对于每个询问操作都要依次输出一行一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 $-1$ 。

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

- 对于 $20\%$ 的数据，保证 $n \leq 10^3$, $q \leq 10^3$。
- 对于 $100\%$ 的数据，保证 $1 \leq m \leq n \leq 10^5$, $1 \leq q \leq 3 \times 10^5$，$p$ 为一个 $1 \sim n$ 的排列，$op \in \{\texttt Q, \texttt B\}$，$1 \leq u, v, x, y \leq n$。


title: [HNOI2012] 矿场搭建

description:
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

inputFormat:
输入文件有若干组数据。

每组数据的第一行是一个正整数 $N\ (N \le 500)$，表示工地的隧道数。

接下来的 $N$ 行每行是用空格隔开的两个整数 $S$ 和 $T$，表示挖煤点 $S$ 与挖煤点 $T$ 由隧道直接连接。

输入数据以 $0$ 结尾。

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

第 $i$ 行组数据以 $\verb!Case i: !$ 开始（注意大小写，$\verb!Case!$ 与 $\verb!i!$ 之间有空格，$\verb!i!$ 与 $\verb!:!$ 之间无空格，$\verb!:!$ 之后有空格）。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 $2^{64}$。输出格式参照以下输入输出样例。

hint:
### 样例解释

- Case 1 的四组解分别是 $(2,4)$，$(3,4)$，$(4,5)$，$(4,6)$；
- Case 2 的一组解为 $(4,5,6,7)$。

### 数据范围及约定

对于每组数据，设 $m$ 为各组 $S, T$ 中最大值，则有：

- $1 \le m \le 10^3$；
- 各组 $S, T$ 构成的集合 $V = [1, m] \cap \mathbb Z$。
- $V$ 中任意两点连通。


title: [HNOI2012] 集合选数

description:
《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{ 1, 2, 3, 4, 5 \}$ 的所有满足以下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。

同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 $n \le 10^5$，如何求出 $\{1,2,\ldots ,n\}$ 的满足上述约束条件的子集的个数（只需输出对 $10^9+1$ 取模的结果），现在这个问题就交给你了。

inputFormat: 只有一行，其中有一个正整数 $n$。$30 \%$ 的数据满足 $n \le 20$。

outputFormat: 仅包含一个正整数，表示 $\{1,2,\ldots ,n\}$ 有多少个满足上述约束条件的子集。


title: [HNOI2013] 切糕

description:
经过千辛万苦小 A 得到了一块切糕，切糕的形状是长方体，小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑，小 A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。

出于简便考虑，我们将切糕视作一个长 $P$、宽 $Q$、高 $R$ 的长方体点阵。我们将位于第 $z$ 层中第 $x$ 行、第 $y$ 列上的点称 $(x,y,z)$，它有一个非负的不和谐值 $v(x,y,z)$。一个合法的切面满足以下两个条件：

 - 与每个纵轴（一共有 $P\times Q$ 个纵轴）有且仅有一个交点。即切面是一个函数 $f(x,y)$，对于所有 $(x,y)(x\in [1,P],y\in[1,Q])$，我们需指定一个切割点 $f(x,y)$，且 $1\le f(x,y)\le R$。

 - 切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的 $1\le x,x'\le P$ 和 $1\le y,y'\le Q$，若 $|x-x'|+|y-y'|=1$，则 $|f(x,y)-f(x',y')| \le D$，其中 $D$ 是给定的一个非负整数。

可能有许多切面 $f$ 满足上面的条件，小 A 希望找出总的切割点上的不和谐值最小的那个。

inputFormat:
第一行是三个正整数 $P,Q,R$，表示切糕的长宽高。

第二行有一个非负整数 $D$，表示光滑性要求。

接下来是 $R$ 个 $P$ 行 $Q$ 列的矩阵，第 $z$ 个矩阵的第 $x$ 行第 $y$ 列是 $v(x,y,z)(1\le x\le P,1\le y\le Q,1\le z\le R)$。

outputFormat: 仅包含一个整数，表示在合法基础上最小的总不和谐值。


title: [HNOI2013] 数列

description: 小T最近在学着买股票，他得到内部消息：F公司的股票将会疯涨。股票每天的价格已知是正整数，并且由于客观上的原因，最多只能为N。在疯涨的K天中小T观察到：除第一天外每天的股价都比前一天高，且高出的价格（即当天的股价与前一天的股价之差）不会超过M，M为正整数。并且这些参数满足M(K-1)<N。小T忘记了这K天每天的具体股价了，他现在想知道这K天的股价有多少种可能

inputFormat: 只有一行用空格隔开的四个数：N、K、M、P。对P的说明参见后面”输出格式“中对P的解释。输入保证20%的数据M,N,K,P<=20000，保证100%的数据$ M,K,P<=10^9 $ ，$ N<=10^{18} $ 。

outputFormat: 仅包含一个数，表示这K天的股价的可能种数对于P的模值。【输入输出样例】


title: [HNOI2013] 旅行

description:
在遥远的 HX 国，住着一个旅行家小 L，他希望骑着他的自行车游遍全国。在这个国家中，每个城市都有一个编号，共有 $n$ 个城市，编号从 $1$ 到 $n$。

有的城市没有小 L 想去的景点，而有的城市有且仅有一个小 L 想去的景点，所有的城市都是这两种情况之一，小 L 非常热爱信息学，他编写程序给他的旅行安排了一条最短路线以到达所有他想去的景点（所有的通知旅行线路上城市编号是乱序的）：他第 $1$ 个到达的城市编号为 $a_1$，第 $i$ 个到达的城市编号为 $a_i$，最后到达城市 $a_n$ 结束这次旅行。小L希望用恰好的 $m$ 个月（$m<n$）的时间完成这次旅行，所以他需要制定一个理性的旅游计划。

当他抵达一个城市时，如果这个城市有他想要去的景点，他会因此获得 $1$ 点快乐值；但是若到达的城市没有他想去的景点，他会因旅途的疲惫得到 $1$ 点的疲劳值：一个月的时间足够他游玩任意多个城市，但他也希望拿出一点时间来休息。他每个月总是在本月所到达的最后一个城市休息（但如果这个城市有景点，那么小 L 总会游玩这个景点再休息）。当然，小 L 希望每个月都能有一定的旅行任务。即便这个月他所到达的城市中并没有他想去的的景点，换句话说，每个月他都会至少到达一个新的城市。

小 L 无法自己安排旅行计划，所以求助于你。你需要告诉他一个序列：$x_1,x_2,\ldots,x_m$，其中 $x_i$ 表示小 L 第 $i$ 个月休息时。他所在的城市编号：由于他最后一个月必须完成他的旅行，所以 $x_m$ 肯定等于 $a_n$，例如，设 $n=5$，$m=3$，$(a_1,a_2,a_3,a_4,a_5)=(3,2,4,1,5)$，$(x_1,x_2,x_3)=(2,1,5)$，这意味着：第 $1$ 个月先后到达 $3$ 号和 $2$ 号城市，并在 $2$ 号城市休息：第 $2$ 个月先后到达 $4$ 号和 $1$ 号城市，并在 $1$ 号城市休息：第 $3$ 个月到达 $5$ 号城市，并在 $5$ 号城市休息。

这样的方案序列有很多种，设每种方案序列中第 $i$ 个月旅行中当月获得的快乐值与疲劳值的差绝对值为 $d_i$，设第 $k$ 种方案序列中求出的 $d_1,d_2,\ldots,d_m$ 这个 $m$ 值的最大值为 $c_k$，小 L 希望所选择的方案序列的 $c_k$ 在所有方案序列中是最小的。

事实上，可能有多个方案序列的 $c_k$ 达到并列最小值。由于小 L 喜爱编程，他患上了一定的强迫症（虽然他自己认为他的强迫症让他炫的发黄），他希望给他的序列是这多个方案中字典序最小的。

Tips：比较两个序列字典序即比较第一个不相同数字的大小，如 $(1,2,3,4)<(1,2,4,3)$。

inputFormat:
第一行为两个空格隔开的正整数 $n, m$，表示旅行的城市数与旅行所花的月数。

接下来 $n$ 行，其中第 $i$ 行包含两个空格隔开的整数 $A_i$ 和 $B_i$，$A_i$ 表示他第 $i$ 个去的城市编号，$B_i$ 为 $0$ 或 $1$。如果 $B_i=0$ 则表示城市 $A_i$ 没有小 L 想去的景点，如果 $B_i=1$ 则表示城市 $A_i$ 有小 L 想去的景点，$A_i$ 两两不同且有 $1\leq  A_i\leq N$，即 $\{A_i\}$ 为 $1,2,\ldots,N$ 的一个排列。

outputFormat: 输出仅包含一行，包含 $m$ 个空格隔开的正整数 $X_1,X_2,\ldots,X_m$，即给小 L 安排的旅行计划对应的路线。

hint:
第 $1$ 个月得到 $2$ 点快乐值与 $2$ 点疲劳值，第 $2$ 个月得到 $1$ 点快乐值与 $1$ 点疲劳值，第 $3$ 个月得到 $1$ 点快乐值与 $1$ 点疲劳值。$3$ 个月中疲劳值与快乐值差的最大值为 $0$，达到所有方案最小值。

可行方案有：

- 1 6 8
- 3 6 8
- 3 1 8

其中 1 6 8 字典序最小。

$N \leq 5 \times 10^5$，$M \leq 2 \times 10^5$。


title: [HNOI2013] 比赛

description:
沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联赛共 $N$ 支球队参加，比赛规则如下：

1. 每两支球队之间踢一场比赛；

2. 若平局，两支球队各得 $1$ 分；

3. 否则胜利的球队得 $3$ 分，败者不得分。 尽管非常遗憾没有观赏到精彩的比赛，但沫沫通过新闻知道了每只球队的最后总得分， 然后聪明的她想计算出有多少种可能的比赛过程。

譬如有 $3$ 支球队，每支球队最后均积 $3$ 分，那么有两种可能的情况：

可能性 $1$ and 可能性 $2$

| 球队 | $A$ | $B$ | $C$ | 得分 | 球队 | $A$ | $B$ | $C$ | 得分 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $A$ | - | $3$ | $0$ | $3$ | $A$ | - | $0$ | $3$ | $3$ |
| $B$ | $0$ | - | $3$ | $3$ | $B$ | $3$ | - | $0$ | $3$ |
| $C$ | $3$ | $0$ | - | $3$ | $C$ | $0$ | $3$ | - | $3$ |

但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果。

inputFormat: 第一行是一个正整数 $N$，表示一共有 $N$ 支球队。 接下来一行 $N$ 个非负整数，依次表示各队的最后总得分。 输入保证 $20\%$ 的数据满足 $N\leq4$，$40\%$ 的数据满足 $N\leq6$，$60\%$ 的数据满足 $N\leq8$，$100\%$ 的数据满足 $3\leq N\leq10$ 且至少存在一组解。

outputFormat: 仅包含一个整数，表示答案对 $10^9+7$ 取模的结果。


title: [HNOI2013] 消毒

description:
最近在生物实验室工作的小 T 遇到了大麻烦。 由于实验室最近升级的缘故，他的分格实验皿是一个长方体，其尺寸为 $a\times b\times c$。为了实验的方便，它被划分为 $a\times b\times c$ 个单位立方体区域，每个单位立方体尺寸为 $1\times 1\times 1$，并用 $(i,j,k)$ 标识一个单位立方体。这个实验皿已经很久没有人用了。现在，小 T 被导师要求将其中一些单位立方体区域进行消毒操作（每个区域可以被重复消毒）。

而由于严格的实验要求，他被要求使用一种特定的 F 试剂来进行消毒。 这种 F 试剂特别奇怪，每次对尺寸为 $x\times y\times z$ 的长方体区域（它由 $x\times y\times z$ 个单位立方体组成）进行消毒时，只需要使用 $\min(x,y,z)$ 单位的 F 试剂。F 试剂的价格不菲，这可难倒了小 T。

现在请你告诉他，最少要用多少单位的 F 试剂。

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

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

接下来是 $D$ 组数据，每组数据第一行是三个正整数 $a,b,c$ 表示实验皿的尺寸。

接下来会出现 $a$ 个 $b$ 行 $c$ 列的用空格隔开的 `01` 矩阵，`0` 表示对应的单位立方体不要求消毒，`1` 表示对应的单位立方体需要消毒：如，如果第 $1$ 个 `01` 矩阵的第 $2$ 行第 $3$ 列为 `1`，则表示单位立方体 $(1,2,3)$ 需要被消毒。

outputFormat: $D$ 行，每行一个整数，表示对应实验皿最少要用多少单位的 F 试剂。


title: [HNOI2013] 游走

description:
给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。

小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。

inputFormat:
第一行是两个整数，分别表示该图的顶点数 $n$ 和边数 $m$。

接下来 $m$ 行每行两个整数 $u,v$，表示顶点 $u$ 与顶点 $v$ 之间存在一条边。

outputFormat: 输出一行一个实数表示答案，保留三位小数。

hint:
#### 样例输入输出 1 解释

边 $(1,2)$ 编号为 $1$，边 $(1,3)$ 编号 $2$，边 $(2,3)$ 编号为 $3$。

---

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n\leq 10$。
- 对于 $100\%$ 的数据，保证 $2\leq n \leq 500$， $1 \leq m \leq 125000$，$1 \leq u, v \leq n$，给出的图无重边和自环，且从 $1$ 出发可以到达所有的节点。


title: [HNOI2014] 世界树

description:
世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。

世界树的形态可以用一个数学模型来描述：世界树中有 $n$ 个种族，种族的编号分别从 $1$ 到 $n$，分别生活在编号为 $1$ 到 $n$ 的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为 $1$。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地 $a$ 和 $b$ 之间有道路，$b$ 和 $c$ 之间有道路，因为每条道路长度为 $1$ 而且又不可能出现环，所以 $a$ 与 $c$ 之间的距离为 $2$。

出于对公平的考虑，第 $i$ 年，世界树的国王需要授权 $m_i$ 个种族的聚居地为临时议事处。对于某个种族 $x$（$x$ 为种族的编号），如果距离该种族最近的临时议事处为 $y$（$y$ 为议事处所在聚居地的编号），则种族 $x$ 将接受 $y$ 议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则 $y$ 为其中编号最小的临时议事处）。

现在国王想知道，在 $q$ 年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。

inputFormat: 第一行为一个正整数 $n$，表示世界树中种族的个数。接下来 $n-1$ 行，每行两个正整数 $x，y$，表示 $x$ 聚居地与 $y$ 聚居地之间有一条长度为 $1$ 的双向道路。接下来一行为一个正整数 $q$，表示国王询问的年数。接下来 $q$ 块，每块两行：第 $i$ 块的第一行为 $1$ 个正整数 $m_i$，表示第 $i$ 年授权的临时议事处的个数。第 $i$ 块的第二行为 $m_i$ 个正整数 $h_1, h_2,\ldots,h_{m_i}$，表示被授权为临时议事处的聚居地编号（保证互不相同）。

outputFormat: 输出包含 $q$ 行，第 $i$ 行为 $m_i$ 个整数，该行的第 $j$ ($j=1, 2,\ldots, m_i$) 个数表示第 $i$ 年被授权的聚居地 $h_j$ 的临时议事处管理的种族个数。


title: [HNOI2014] 抄卡组

description:
一天闲着无聊的小L找来了当前正火爆的游戏《炉石传说》来玩，但是怎么打怎么输，于是他大喊一声”我要抄卡组！“就找来了游戏传说组第一名的游戏高手小H的直播来看。

但是小L家的网络技术还停留在拨号，看着直播画面又是卡顿又是花屏，他不给力的网络让他完全无法记录小H展示的给力的卡组。小L周围都是学霸没有人玩游戏想去帮他这个忙，但是学霸们热衷于讨论各种信息学问题。

于是他想到了一个方法：由于每次花屏的屏幕位置不一样，于是小H每次总能记录下卡组的一些部分，如果这样记录多次，不就有可能还原出小L想要的一个卡组么？

但是存在的一个问题是，小H每次展示的卡组有可能不一样，所以他想知道他每次看直播抄下来几次的卡组碎片是否一致。

这样一来小H将他遇到的游戏问题抽象成这样一个学术问题让学霸（你）解决：'\*'可以匹配任意长度个的字符 （包含0个），问所有字符串是否两两匹配。

inputFormat: 第一行包含一个正整数T，表示了数据组数。    接下来包含T组数据：    每组数据的第一行是一个正整数N，表示该组数据酌字符串个数。    接下来N行，每行一个字符串，字符串仅包含小写字母、数字、通配符术。注意:数据为UNIX格式，中间包含空行,你可以采用逐字符读入的方式

outputFormat: 输出包含T行，每行一个字母Y或者N，Y表示这组数据中所有字符串两两匹配，N表示这组数据中至少有一对字符串不匹配。

hint:
对于100%的数据，满足N<= 100000，T= 10，输入文件不超过10M，N\*最长字符串长度不超过2x10^8

目前有且仅有 hack 数据中 $T = 1$。


title: [HNOI2014] 江南乐

description:
小A是一个名副其实的狂热的回合制游戏玩家。在获得了许多回合制游戏的世界级奖项之后，小A有一天突然想起了他小时候在江南玩过的一个回合制游戏。

游戏的规则是这样的，首先给定一个数F，然后游戏系统会产生T组游戏。每一组游戏包含N堆石子，小A和他的对手轮流操作。每次操作时，操作者先选定一个不小于2的正整数M (M是操作者自行选定的，而且每次操作时可不一样)，然后将任意一堆数量不小于F的石子分成M堆，并且满足这M堆石子中石子数最多的一堆至多比石子数最少的一堆多1（即分的尽量平均，事实上按照这样的分石子万法，选定M和一堆石子后，它分出来的状态是固定的）。当一个玩家不能操作的时候，也就是当每一堆石子的数量都严格小于F时，他就输掉。(补充：先手从N堆石子中选择一堆数量不小于F的石子分成M堆后，此时共有N+M-1)堆石子，接下来小A从这N+M-1堆石子中选择一堆数量不小于F的石子，依此类推。

小A从小就是个有风度的男生，他邀请他的对手作为先手。小A现在想要知道，面对给定的一组游戏，而且他的对手也和他一样聪明绝顶的话，究竟谁能够获得胜利？

inputFormat: 输入第一行包含两个正整数T和F，分别表示游戏组数与给定的数。    接下来T行，每行第一个数N表示该组游戏初始状态下有多少堆石子。之后N个正整数，表示这N堆石子分别有多少个。

outputFormat: 输出一行，包含T个用空格隔开的0或1的数，其中0代表此时小A（后手）会胜利，而1代表小A的对手（先手）会胜利。

hint:
对于100%的数据，T<100，N<100，F<100000，每堆石子数量<100000。

以上所有数均为正整数。


title: [HNOI2014] 画框

description:
小 T 准备在家里摆放几幅画，为此他买来了 $N$ 幅画和 $N$ 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。

对于第 $i$ 幅画与第 $j$ 个画框的配对，小 T 都给出了这个配对的平凡度 $A_{i, j}$ 与违和度 $B_{i, j}$ 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第 $i$ 幅画与第 $P_i$ 个画框配对，则总体不和谐度为

$$\mathrm{disharmony}=\sum_{i=1}^{N}A_{i,p_i}\times \sum_{i=1}^{N}B_{i,p_i}$$
小 T 希望知道通过搭配能得到的最小的总体不和谐度是多少。

inputFormat: 输入文件第 $1$ 行是一个正整数 $T$，表示数据组数，接下来是 $T$ 组数据。对于每组数据，第 $1$ 行是一个正整数 $N$，表示有 $N$ 对画和画框。第 $2$ 到第 $N+1$ 行，每行有 $N$ 个非负整数，第 $i+1$ 行第 $j$ 个数表示 $A_{i,  j}$。第 $N+2$ 到第 $2N+1$ 行，每行有 $N$ 个非负整数，第 $i+N+1$ 行第 $j$ 个数表示 $B_{i, j}$ 。

outputFormat: 包含 $T$ 行，每行一个整数，表示最小的总体不和谐度。

hint:
第 $1$ 幅画搭配第 $3$ 个画框，第 $2$ 幅画搭配第 $1$ 个画框，第 $3$ 幅画搭配第 $2$ 个画框，则总体不和谐度为 $30$。

对于 $100\%$ 的数据，$N\leq 70$，$T\leq 3$，$A_{i, j}\leq 200$，$B_{i, j}\leq 200$。