title: [SHOI2015] 脑洞治疗仪

description:
曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。

为了简单起见，我们将大脑视作一个 01 序列。$1$ 代表这个位置的脑组织正常工作，$0$ 代表这是一块脑洞。

```cpp
1      0      1      0      0      0      1      1      1      0
```

脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）

例如，用上面第 $8$ 号位置到第 $10$ 号位置去修补第 $1$ 号位置到第 $4$ 号位置的脑洞，我们就会得到：

```cpp
1      1      1      1      0      0      1      0      0      0
```

如果再用第 $1$ 号位置到第 $4$ 号位置去修补第 $8$ 号位置到第 $10$ 号位置：

```cpp
0      0      0      0      0      0      1      1      1      1
```

这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。

如果再用第 $7$ 号位置到第 $10$ 号位置去填补第 $1$ 号位置到第 $6$ 号位置：

```cpp
1      1      1      1      0      0      0      0      0      0
```

这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。

假定初始时 SHTSC 并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答 SHTSC 的问题：在大脑某个区间中最大的连续脑洞区域有多大。

inputFormat:
第一行两个整数 $n,m$，表示 SHTSC 的大脑可分为从 $1$ 到 $n$ 编号的 $n$ 个连续区域，有 $m$ 个操作。

以下 $m$ 行每行是下列三种格式之一：
* $0\quad l\quad r$：SHTSC 挖了一个范围为 $[l, r]$ 的脑洞。
* $1\quad l_0\quad r_0\quad l_1\quad r_1$：SHTSC 进行了一次脑洞治疗，用从 $l_0$ 到 $r_0$ 的脑组织修补 $l_1$ 到 $r_1$ 的脑洞。
* $2\quad l\quad r$：SHTSC 询问 $[l, r]$ 区间内最大的脑洞有多大。

上述区间均在 $[1, n]$ 范围内。

outputFormat: 对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。


title: [SHOI2015] 超能粒子炮·改

type: P

description:
曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明：超能粒子炮・改——一种可以发射威力更加强大的粒子流的神秘装置。

超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。它有两个参数 $n,k$ ，它会向每个编号为 $0$ 到 $k$ （包含两端）的位置 $i$ 发射威力为 $C_{n}^{i} \bmod 2333$ 的粒子流。

现在 SHTSC 给出了他的超能粒子炮・改的参数，让你求出其发射的粒子流的威力之和除以 $2333$ 所得的余数。

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

之后 $t$ 行，每行两个整数 $n,k$，含义如题面描述。

outputFormat: $t$ 行，每行一个整数，表示其粒子流的威力之和模 $2333$ 的值。


title: [CERC2015] ASCII Addition

background: Nowadays, there are smartphone applications that instantly translate text and even solve math problems if you just point your phone’s camera at them. Your job is to implement a much simpler functionality reminiscent of the past – add two integers written down as ASCII art.

description:
An ASCII art is a matrix of characters, exactly 7 rows high, with each individual character either a dot or the lowercase letter x.

An expression of the form a + b is given, where both a and b are positive integers. The expression is converted into ASCII art by writing all the expression characters (the digits of a and b as well as the + sign) as 7  5 matrices, and concatenating the matrices together with a single column of dot characters between consecutive individual matrices. The exact matrices corresponding to the digits and the + sign are as follows:

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

Given an ASCII art for an expression of the form a + b, find the result of the addition and write it out in the ASCII art form.

inputFormat:
Input consists of exactly 7 lines and contains the ASCII art for an expression of the form a + b, where
both a and b are positive integers consisting of at most 9 decimal digits and written without leading
zeros.

outputFormat: Output 7 lines containing ASCII art corresponding to the result of the addition, without leading zeros.

translation:
# 题目背景

现在，如果你只是用手机的相机对着它们，智能手机应用可以即时翻译文本，甚至解决数学问题。您的工作是实现一个更简单的功能，回忆过去——添加两个作为ASCII艺术的整数。

# 题目描述

ASCII艺术是一个字符矩阵，正好是7行高，每个字符都是点或小写字母X。

给出了A +B形式的表达式，其中A和B都是正整数。通过将所有的表达式字符（A和B的数字以及符号）作为7 5个矩阵，将这些矩阵转换成ASCII艺术，并将矩阵与单个字符的单个列串联在连续的各个矩阵之间。对应于数字和+符号的精确矩阵如下：

![](https://cdn.luogu.org/upload/pic/16222.png)

给定一个ASCII艺术来表达A+B的形式，找到加法的结果并用ASCII艺术形式写出。

# 输入输出格式

#### 输入格式：

输入由7行组成，包含用于A+B形式的表达式的ASCII技术，其中A和B都是由至多9个十进制数字组成的正整数，并且没有前导零。

#### 输出格式：

输出包含ASCII艺术的7行，对应于加法的结果，没有前导零。

感谢@剑圣夜雨声烦 提供的翻译

hint:
样例：1234567+890=1235457

Central Europe Regional Contest 2015 Problem A


title: [CERC2015] Book Borders

background:
A book is being typeset using a fixed width font and a simple greedy algorithm to fill each line. The
book contents is just a sequence of words, where each word contains one or more characters.

description:
Before typesetting, we choose a maximum line length and denote this value with m. Each line can be at most m characters long including the space characters between the words. The typesetting algorithm simply processes words one by one and prints each word with exactly one space character between two consecutive words on the same line. If printing the word on the current line would exceed the maximum line length m, a new line is started instead.

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

You are given a text to be typeset and are experimenting with different values of the maximum line length m. For a fixed m, the leading sentence is a sentence (a sequence of words separated with a single space character) formed by the first words of lines top to bottom. In the example above, when the sample text is typeset with the maximum line length 14, the leading sentence is “its to you n”.

Given a text and two integers a and b, find the length of the leading sentence for every candidate maximum line length between a and b inclusive. The length of a sentence is the total number of characters it contains including the space characters.

inputFormat:
The first line contains the text to be typeset – a sequence of words separated by exactly one space character. Each word is a string consisting of one or more lowercase letters from the English alphabet.

The second line contains two integers a and b – the edges of the interval we are interested in, as described above.

It is guaranteed that $1<=w<=a<=b<=z<=500 000$, where w is the length of the longest word in the text and z is the total number of characters in the text including the space characters.

outputFormat: Output $b - a + 1$ lines – the $k$-th of those lines should contain a single integer – the total length of the leading sentence when the maximum line length is equal to $a - 1 + k$.

translation:
现有一本书,用固定宽度的字体和简单的贪婪算法来填充每行文字。书的内容是一个单词序列，每个单词包含一个或多个字符。

排版前，我们选择一个最大的行长度，并用m表示这个值。每行最多可以有m个字符，包括单词之间的空格字符。请使用排版算法简单地逐个处理单词，并在同一行上的两个连续单词之间打印每个单词，每个单词只有一个空格字符。而且如果在当前行上打印该字超过最大行长度m，则开始新行。
![](https://cdn.luogu.org/upload/pic/16228.png)
现在你得到了一个要排版的文本，并且正在试验最大行长度m的不同值。对于固定m，前导句是一个句子(由一个空格字符分隔的一系列单词)，由行的第一个单词从上到下组成。在上例中，当样本文本以最大行长度14进行排版时，前导句是“对你来说是n”（its to you n）
给定一个文本和两个整数a和b，找出a和b之间每个候选最大行长度的前导句长度。句子的长度是它包含的字符总数，包括空格字符

**输入格式：**
第一行包含要排版的文本——由一个空格字符分隔的一系列单词。每个单词都是一个字符串，由英语字母表中的一个或多个小写字母组成。 第二行包含两个整数a和b——如上所述的区间边缘。保证1<=w <=a<=b<=z<=50000,
其中w是文本中最长单词的长度，z是文本中包括空格字符的字符总数。

**输出格式**
输出b-a+1行——这些行的第k行应该包含一个整数——最大行长度等于a-1+k时前导句的总长度。

**输入输出样例**

输入样例#1
```
its a long way to the top if you wanna rock n roll
13 16
```
输出样例#1
```
22
12
12
15
```

hint:
Central Europe Regional Contest 2015
Problem B


title: [CERC2015] Cow Confinement

description:
A near by pasture can be represented as a rectangular grid consisting of 106 rows and 106 columns. The rows are numbered with integers 1 through 106 top to bottom, the columns with integers 1 through 106 left to right.

A herd of n cows is scattered through the grid, each cow occupying a unit square. The pasture also contains m dandelion ﬂowers (which cows like), again each occupying a unit square. Finally, the pasture contains p fences, each a rectangle running along the edges of unit squares. Fences do not intersect or touch. However, a fence may contain other fences inside the enclosed area.

Due to unfavorable wind conditions, cows can only move in two directions – down or right. Cows can go through squares occupied by other cows or ﬂowers, but cannot cross fences.
For each cow, ﬁnd the total number of ﬂowers reachable from its present location.

inputFormat:
Input contains three blocks – the ﬁrst block describes fences, the second one ﬂowers and the third one cows.

The ﬁrst line of the ﬁrst block contains an integer f (0≤ f ≤200000) – the number of fences. Each of the following f lines contains four integers r1, c1, r2, c2 (1≤r1, c1, r2, c2 ≤$10^6$) describing a single fence – r1 and c1 are the coordinates (row and column) of the upper-left corner square inside the fence, while r2 and c2 are the coordinates of the lower-right corner square inside the fence. No two fences will intersect or touch.

The ﬁrst line of the second block contains an integer m (0≤m≤200000) – the number of ﬂowers. The k-th of the following m lines contains two integers r and c (1 ≤ r, c ≤ $10^6$) – the location of the k-th ﬂower. No two ﬂowers will occupy the same location.

The ﬁrst line of the third block contains an integer n (1≤n≤200000) – the number of cows. The k-th of the following n lines contains two integers r and c (1≤r, c≤$10^6$) – the location of the k-th cow. No two cows will occupy the same location, and no ﬂower and cow will occupy the same location.

outputFormat: Output should consist of n lines. The k-th line should contain a single integer – the total number of ﬂowers reachable from the location of the k-th cow.

translation:
### 题意简述

给定一个 $10^6$ 行 $10^6$ 列的网格图，上面有一些牛、花和一些不相交的矩形围栏。所有围栏在格子的边界上，同时牛和花在格子里。每头牛只能向下或向右走，同时不能穿过围栏和地图边界。

求每头牛能到达的花的数量。

### 输入格式

第一行一个数 $f$ 表示矩形围栏的数量。接下来 $f$ 行，每行四个数 $x_1,y_1,x_2,y_2$ ，表示 $(x_1,y_1)$ 在围栏内部矩形的左上角， $(x_2,y_2)$ 在右下角。

接下来一行一个数 $m$ 表示花的数量，之后 $m$ 行每行两个数 $x,y$ ，表示在 $(x,y)$ 处有一朵花。

接下来一行一个数 $n$ 表示牛的数量，之后的 $n$ 行每行两个数 $x,y$ ，表示在 $(x,y)$ 处有一头牛。

### 输出格式

总共 $n$ 行，每行一个数 $ans$，第 $i$ 个数表示第 $i$ 头牛能到 $ans$ 个花。

hint:
样例：

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

Central Europe Regional Contest 2015
Problem C


title: [CERC2015] Digit Division

description:
We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m.

Find the number of different such partitions modulo $10^9 +7$. When determining if two partitions are different, we only consider the locations of subsequence boundaries rather than the digits themselves, e.g. partitions $2|22$ and $22|2$ are considered different.

inputFormat: The ﬁrst line contains two integers n and m (1≤n≤300000, 1≤m≤1000000) – the length of the sequence and the divisor respectively. The second line contains a string consisting of exactly n digits.

outputFormat: Output a single integer – the number of different partitions modulo 109 +7.

translation:
有一个N位的数字，将其分割，保证每个区间里的数字可以被M整除

第一行输入N M

第二行输入待划分的数字

输出有多少种方法，对10^9+7取余

Translated by @chen_zhe

hint: Central Europe Regional Contest 2015 Problem D


title: [CERC2015] Export Estimate

background: Luka owns a geographic data company that maintains a detailed city map and exports the data to interested parties. Often, clients do not want the complete map. Instead, they want a simpliﬁed map containing only major streets.

description:
City map is an undirected graph consisting of n intersections denoted with integers from 1 to n and m two-way streets. Each street is assigned a priority – a non-negative integer. When requesting a map, the client selects a threshold priority p. The original map is then copied and converted to the exported map using the following procedure:

1. All streets whose priority is lower than p are deleted.

2. For each intersection i from 1,2,...,n (processed in that order):

(a) If the intersection i is not connected to any streets it is deleted.

(b) If the intersection i is connected to exactly two different streets x and y leading to intersections a and b both different from i then the intersection i is contracted using the following procedure:

i. Streets x and y are deleted.

ii. Intersection i is deleted.

iii. New street z connecting intersections a and b is added.

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

Initially, the map does not contain loops (loop is a street that connects an intersection to itself) or parallel edges (more than one street between the same pair of intersections), but the loops and parallel edges may form during the contraction procedure. Notice that, in the step 2. (b) above, neither x nor y can be a loop (both a and b have to be different from i), but the newly added street z could be a loop (it is possible that a and b are same).

Given a map and a sequence of incoming export requests, for each request ﬁnd the number of intersections and the number of streets in the exported map.

inputFormat:
The ﬁrst line contains two integers n (1 ≤ n ≤ 300000) and m (1 ≤ m ≤ 300000) – the number of intersections and the number of streets, respectively. Each of the following m lines contains three integers a, b and p (1≤ a,b≤n,0≤ p≤300000) which describe a street with priority p connecting intersections a and b. No street connects an intersection to itself. There is at most one street between every two intersections.

The following line contains an integer q (1 ≤ q ≤ 300000) – the number of export requests. The following line contains q integers. The k-th integer tk (0≤tk ≤300000) is the threshold priority of the k-th request.

outputFormat: Output should consist of q lines. The k-th line should contain two integers–the number of intersections and the number of streets, respectively, in the exported map for the k-th request.

translation:
#### 题意翻译：

Luka 拥有一个地理数据公司保持着详细的城市地图和出口相关的数据。但是通常客户不想要完整的地图。相反，他们更想要一个只包含主要街道的简单地图：

1. 所有优先级小于 $p$ 的街道被删除

1. 对于每一个路口点 $i$ 从 $1$ 到 $n$（按照这个顺序处理）：

   (a)如果这个路口没有连接到任何街道，它就会被删除。

   (b)如果路口 $i$ 正好连接到两个不同的街道 $x$ 和 $y$，导致 $a$ 和 $b$ 两个路口都与路口 $i$ 不同，那么 $i$ 就会根据下面的过程进行收缩：

   i.删除道路 $x$ 和道路 $y$；

   ii.删除路口 $i$；

   iii.加入一个连接路口 $a$ 和 $b$ 的新道路 $z$；

最初，图中没有环（即一条连接到自身的边）或者平行的边（即在同一对交点之间有一条以上的边），但在收缩的过程中可能会形成环和平行边。

请注意，在步骤2.（b）之前，$x$ 和 $y$ 都不能是环（即 $a$ 和 $b$ 必须和 $i$ 不同），但是新增的 $z$ 可以是一个环（即 $a$ 和 $b$ 可能是相同的）。

给定一个地图和一系列的出口的询问,每个询问找到路口的数量和街道地图出口的数量。

#### 输入格式：
第一行包含两个整数 $n(1 \le n\le3\times10^5)$ 和 $m(1\le m\le 3\times10^5)$ 分别是点和边的数量。

后面 $m$ 行包含三个整数分别是 $a,b$ 和 $p(1\le a,b \le n,0\le p\le 3\times10^5)$ 用来描述 $a,b$ 之间边的优先级 $p$，没有一条边只连接一个点，两个点之间最多有一条边。

第 $m+2$ 行包含一个整数 $q(1\le q\le 3\times10^5)$ 表示询问的个数，下一行有 $q$ 个整数，第 $k$ 个整数 $t_k(0\le tk\le 3\times10^5)$ 是第 $k$ 次询问的优先级。

#### 输出格式：
输出包括 $q$ 行。第 $k$ 行包含两个整数，分别是第 $k$ 次询问的点和边的个数。

hint: Central Europe Regional Contest 2015 Problem E


title: [CERC2015] Frightful Formula

description:
A frightful matrix is a square matrix of order n where the ﬁrst row and the ﬁrst column are explicitly speciﬁed, while the other elements are calculated using a frightful formula which is, actually, a simple recursive rule.

Given two integer sequences l and t,both of size n,as well as integer parameters a,b and c,the frightful matrix F is deﬁned as follows:

* The ﬁrst column of the matrix is the sequence l:

$$F[k, 1] = lk$$

* The ﬁrst row of the matrix is the sequence t:

$$F[1, k] = tk$$

* Other elements are calculated using a recursive formula:

$$F[i,j]=a*F[i,j-1]+b*F[i-1,j]+c$$

Given a frightful matrix, ﬁnd the value of the element $F[n,n]$ modulo $10^6 +3$.

inputFormat:
The ﬁrst line contains four integers n, a, b and c (2≤n≤200000, 0≤ a, b, c≤$10^6$) – the size of the matrix and the recursion parameters, as described in the problem statement.

The two following lines contain integers l1,...,ln and t1,...,tn, respectively (l1 = t1, 0≤lk, tk ≤106).

outputFormat: Output a single integer – the value of $F[n,n]$ modulo $10^6 +3$.

translation:
定义一个矩阵 $F$，其中第一行和第一列是给定的，计算矩阵方法如下：

矩阵的第一列是序列  $l$：

 $F[k,1]=$  $l _ k$

矩阵的第一行是序列  $t$：

 $F[1,k]=$  $t _ k$

其他元素使用给定的递归公式进行计算：

$F[i,j]=a \times F[i,j-1]+b \times F[i-1,j]+c$。

现在要求找求出 $F[n,n]$ 模 $10^6+3$ 的值。

输入输出格式。

输入格式：

第一行包含四个整数 $n$，$a$，$b$ 和 $c(2 \le n \le 200000,0 \le a,b$，$c \le 10^6)$ 矩阵的大小和递归参数，如问题描述中所述。

下面两行分别包含整数 $l_1, \cdots ,l_n$ 和 $t_1, \cdots ,t_n(l_1=t_1,0 \le lk,tk \le 10^6)$。

输出格式：

输出一个整数的值即 $F[n,n]$ 模 $10^6+3$。

感谢 @ 守望提供的翻译。

hint: Central Europe Regional Contest 2015 Problem F


title: [CERC2015] Greenhouse Growth

description:
You are switching from computer science to agriculture and your new job involves growing sunﬂowers in an underground greenhouse. The greenhouse contains n sunﬂower plants arranged in a straight line and numbered with integers 1 through n, from left to right. Two lamps provide the light and heat the sunﬂowers need to grow: the lamp A is positioned at the left end, while the lamp B is positioned at the right end of the line.

Every day exactly one of the lamps is on, causing all of the sunﬂowers to turn towards the light and some of them to grow. The sunﬂower will grow if and only if the sunﬂower directly in front of it (towards the light) is higher. The growth is continuous with a uniform rate of exactly 1 centimeter per day. Notice that, when a sunﬂower starts to grow, it may cause the sunﬂower directly behind it to start to grow instantaneously.

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

You are given initial heights of the sunﬂowers and the lamp schedule for the following m day period, ﬁnd the ﬁnal heights of all the sunﬂowers.

inputFormat:
The ﬁrst line contains two integers n and m (1≤n, m≤300000) – the number of sunﬂowers and the number of days in the period. The following line contains n integers h1,h2,...,hn (1≤ hk ≤$10^9$) – the initial heights (in centimeters) of the sunﬂowers, from left to right.

The following line contains a string consisting of exactly m characters A or B – the lamp schedule starting from the ﬁrst day of the period.

outputFormat: Output a single line containing n integers – the ﬁnal heights of the sunﬂowers, from left to right.

translation:
有两盏灯在最左边和最右边。有 $n$ 盏向日葵在中间。

每一天都一定会有一个灯开着。向日葵仅仅当它前面的（朝向灯的方向）向日葵比它高时它才会成长，成长速度为 $1$。注意，当一个向日葵开始成长时，它还可能使得在它后面的向日葵瞬间成长。

给你每株向日葵的高度，还有每天开灯的时间表，求出最后所有的向日葵的高度。

$n,m\le 3\times 10^5$，$h \leq 10^9$。

hint: Central Europe Regional Contest 2015 Problem G


title: [CERC2015] Hovering Hornet

description:
You have managed to trap a hornet inside a box lying on the top of your dining table. Unfortunately, your playing dice is also trapped inside – you cannot retrieve it and continue your game of Monopoly without risking the hornet’s wrath. Instead, you pass your time calculating the expected number of spots on the dice visible to the hornet.

The hornet, the dice and the box are located in the standard three-dimensional coordinate system with the x coordinate growing eastwards, the y coordinate growing northwards and the z coordinate growing upwards. The surface of the table corresponds to the x-y plane.

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

The dice is a 1×1×1 cube, resting on the table with the center of the bottom side exactly in the origin. Hence,the coordinates of its two opposite cornersare (−0.5, −0.5, 0) and (0.5, 0.5, 1). The top side of  the dice has 5 spots, the south side 1 spot, the east side 3 spots, the north side 6 spots, the west side 4 spots and the (invisible and irrelevant) bottom side 2 spots.

The box is a 5×5×5 cube also resting on the table with the dice in its interior. The box is speciﬁed by giving the coordinates of its bottom side – a 5×5 square.

Assume the hornet is hovering at a uniformly random point in the (continuous) space inside the box not occupied by the dice. Calculate the expected number of spots visible by the hornet. The dice is opaque and, hence, the hornet sees a spot only if the segment connecting the center of the spot and the location of the hornet does not intersect the interior of the dice.

inputFormat:
Input consists of 4 lines. The k-th line contains two ﬂoating-point numbers xk and yk (−5≤ xk, yk ≤5) –coordinates of the k-th corner of the bottom side of the box in the x-y plane. The coordinates are given in the counterclockwise direction and they describe a square with the side length of exactly 5.

The box fully contains the dice. The surfaces of the box and the dice do not intersect or touch except along the bottom sides.

outputFormat: Output a single ﬂoating point number – the expected number of spots visible. The solution will be accepted if the absolute or the relative difference from the judges solution is less than $10^{−6}$.

translation:
你把一只蜜蜂困在你餐桌上的一个盒子里。但是，你玩的骰子也被困在里面（你无法取回它）不过，你通过计算蜜蜂可以看到的骰子上的预期点数来消磨时间。

蜜蜂、骰子和盒子位于一个三维坐标系中，x-y轴如图

骰子是一个1×1×1的立方体，放在桌子上，底部的中心为原点。因此，其两个相对角的坐标为(−0.5, −0.5,0）和（0.5,0.5,1）。骰子顶部有5个点，南侧1个点，东侧3个点，北侧6个点，西侧4个点，底部2个点（不可见和不相关）。

盒子是一个5×5×5的立方体，也放在桌子上，里面有骰子。该框通过给出其底部的坐标（一个5×5的正方形）来指定。

假设蜜蜂在盒子内没有骰子的（连续）空间中的一个均匀随机点上盘旋。计算蜜蜂可以看到的点数的数量。骰子是不透明的，因此，只有当连接点数中心和蜜蜂位置的部分不与骰子内部相交时，蜜蜂才能看到斑点。

输入格式：
输入由4行组成。第k行包含两个浮点数xk和yk(−5<=xk，yk<=5）x-y平面中长方体底部第k个角的坐标。坐标以逆时针方向给出，它们描述了边长正好为5的正方形。
盒子和骰子的表面不相交或接触，除非放在底部。
输出格式：
输出一个数——预期可见点数
（样例如下）

hint: Central Europe Regional Contest 2015 Problem H


title: [CERC2015] Ice Igloos

description:
A ﬁshing village built on the surface of a frozen lake far north in the arctic is endangered by global warming-fractures are starting to form on the lake surface. The village consists of n igloos of spherical shape, each occupying a circular area of the surface.

An igloo can be represented as a circle in the coordinate plane: the center of the circle is a point with integer coordinates, while the radius is a positive ﬂoating-point number less than 1 with exactly one fractional digit.

Given the locations of possible ice fractures, the villagers would like to know how many igloos are affected by each. Formally, given q queries where each query is a straight line segment deﬁned by the two endpoints, ﬁnd the number of igloos each segment intersects. A segment intersects an igloo if it has at least one point in common with the interior of the circle.

inputFormat:
The ﬁrst line contains an integer n (1≤n≤100000) - the number of igloos. Each of the following n lines contains three numbers x, y and r – the coordinates of the center and the radius of one igloo. The coordinates x and y are integers such that 1≤ x, y≤500, while r is a ﬂoating-point number with exactly one fractional digit such that 0 < r < 1. No two igloos will intersect or touch.

The following line contains an integer q (1 ≤ q ≤ 100000) - the number of queries. Each of the following q linescontainsfourintegers x1, y1, x2, y2 (1≤ x1, y1, x2, y2 ≤500)-thecoordinatesofthe two endpoints of the segment. The two endpoints will be different. Endpoints may be inside igloos.

You may assume that, for every igloo i and the segment s, the square of the distance between s and the center of i is either less than r2−10−5 or greater than r2 +10−5 where r is the radius of the igloo i.

outputFormat: Output should consist of q lines. The k-th line should contain a single integer – the number of igloos that are intersected by the k-th segment.

translation:
给你$n$个圆$,m$条线段$,$求每条线段与多少圆相交

$n,m\le10^5,1\le x_i,y_i\le500,0\lt r_i\lt 1$

## 输入输出格式

### 输入格式

第一行一个整数$n$表示圆的个数

接下来$n$行每行两个整数$x,y$和一个实数$r$表示圆心坐标和半径

第$n+2$行一个整数$m$表示线段个数

接下来$m$行每行四个整数$x1,y1,x2,y2$表示线段的两个端点$(x1,y1),(x2,y2)$

### 输出格式

$m$行每行一个整数表示该条线段和多少圆相交

感谢@Kelin 提供的翻译

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

Central Europe Regional Contest 2015 Problem I


title: [CERC2015] Kernel Knights

description:
Jousting is a medieval contest that involves people on horseback trying to strike each other with wooden lances while riding at high speed. A total of 2n knights have entered a jousting tournament – n knights from each of the two great rival houses. Upon arrival, each knight has challenged a single knight from the other house to a duel.

A kernel is deﬁned as some subset S of knights with the following two properties:

• No knight in S was challenged by another knight in S.

• Every knight not in S was challenged by some knight in S.

Given the set of the challenges issued, ﬁnd one kernel. It is guaranteed that a kernel always exists.

inputFormat:
The ﬁrst line contains an integer n (1 ≤ n ≤ 100000) – the number of knights of each house. The knights from the ﬁrst house are denoted with integers 1 through n, knights from the second house with integers n+1 through 2n.

The following line contains integers $f_1$, $f_2$,..., $f_n$ – the k-th integer fk is the index of the knight challenged by knight k $(n+1≤ f_k ≤2n)$.

The following line contains integers $s_1$,$s_2$,...,$s_n$ – the k-th integer sk is the index of the knight challenged by knight n+k $(1≤s_k ≤n)$.

outputFormat:
Output the indices of the knights in the kernel on a single line. If there is more than one solution, you may output any one.

SPJ的格式校验较为严格，请在每个数字后面都输出一个空格，且在最后一个空格输出后请不要输出任何符号。

translation:
骑术是一项中世纪的比赛，人们骑在马背上，在高速骑行时，试图用木制长矛互相攻击。总共有2n个骑士参加了一个激战锦标赛——来自两个主要竞争对手的N个骑士。到达后，每一个骑士都从另一个房间挑战一个骑士进行决斗。

内核被定义为骑士的一些子集，具有以下两个属性：

•S中没有骑士受到S中另一个骑士的挑战。

每一个不在S中的骑士都会受到一些S中的骑士的挑战。

考虑到所面临的一系列挑战，确定一个内核。可以保证内核始终存在。

hint: Central Europe Regional Contest 2015 Problem K


title: [CERC2015] Looping Labyrinth

description:
A labyrinth is obtained by tiling the entire plane with a pattern – a rectangular grid consisting of n rows and m columns where every cell is either empty or blocked. The result is an inﬁnite grid of cells with the pattern repeating in all four directions.

Formally, suppose we denote both rows and columns of the inﬁnite grid with integers (including the negative integers). The row number increases as we move downwards in the grid, while the column number increases as we go to the right. The cell at coordinates (0,0) is called the origin. The labyrinth is obtained by copying the pattern (without mirroring or rotation) to every n-by-m rectangular area that, in the upper-left corner, has a cell with the row number divisible by n and the column number divisible by m. In particular, the upper-left corner of the pattern gets copied to the origin, while the lower-right corner gets copied to the cell with coordinates (n−1,m−1).

To escape the labyrinth starting from a particular cell, we need to reach the origin via a sequence of empty cells, going up, down, left or right in each step.

You are given a pattern and a sequence of possible starting cells. For each starting cell determine if it is possible to escape the labyrinth.

inputFormat:
The ﬁrst line contains two integers n and m (1≤n, m≤100)–the number of rows and columns in the pattern, respectively. Each of the following n lines contains a string of exactly m characters describing one row of the pattern. The character # denotes a blocked cell while the dot character denotes an empty cell. The following line contains an integer q (1≤q≤200,000) – the number of starting cells. The k-th of the following q lines contains two integers r and c ($−10^9$ ≤ r, c ≤ $10^9$) – the row and column of the k-th starting cell.

The origin and all starting cells will be empty.

outputFormat: Output should consist of q lines. The k-th line should contain the word yes if it is possible to exit the labyrinth from the k-th starting cell and the word no otherwise.

translation:
一个$n×m$的矩形，其中每格为路或墙，通过将图案平移来获得迷宫。迷宫是一个大小有限的坐标系，其图案在四个方向上重复。

用整数（包括负整数）表示横纵坐标。向下行数增加，向右列数增加，坐标$(0,0)$处称为原点。特别地，图案的左上角在原点，而右下角在坐标$(n-1,m-1)$。

原点是出口，为了从开始逃离迷宫，我们要从不同的起点到达原点，每一步可向上，下，左或右。对于每个起点，确定是否可以逃离迷宫。

输入格式：

第一行包含两个整数$n$和$m$（$1≤n$，$m≤100$）。

以下每一行包含$m$个字符。“#”表示墙，“.”表示路。
以下的一行包含整数$q$（$1≤q≤200000$）表示起点的数量。

以下$q$行每行包含两个整数$r$和$c$（$-10^9≤r$，$c≤10^9$），表示每个起点的坐标。

保证原点和所有起点为路。

输出格式：
输出$q$行。如果可以从当前起点逃出迷宫，则每行输出$yes$，否则输出$no$。

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

Central Europe Regional Contest 2015 Problem L


title: [CQOI2016] K 远点对

description:
已知平面内 $N$ 个点的坐标，求欧氏距离下的第 $K$ 远点对。

两个点 $P(x_1,y_1)$ 和 $Q(x_2,y_2)$ 的欧氏距离定义为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

inputFormat:
输入文件第一行为用空格隔开的两个整数 $N,K$ 。

接下来 $N$ 行，每行两个整数 $X,Y$ ，表示一个点的坐标。

outputFormat: 输出文件第一行为一个整数，表示第 $K$ 远点对的距离的平方（一定是个整数）。


title: [CQOI2016] 密钥破解

description:
一种非对称加密算法的密钥生成过程如下：

1.任选两个不同的质数$p,q$

2.计算$N=p \times q$，$r=(p-1)(q-1)$

3.选取小于$r$，且与$r$互质的整数$e$

4.计算整数$d$，使得$ed≡1(mod r)$

5.二元组$(N,e)$称为公钥，二元组$(N,d)$称为私钥。

当需要加密消息$n$时，（假设$n$是一个小于$N$的整数，因为任何格式的消息都可转为整数表示），使用公钥$(N,e)$，按照

$$n^e≡c(mod N)$$

运算，可得到密文$c$

对密文$c$解密时，用私钥$(N,d)$，按照

$$c^d≡n(mod N)$$

运算，可得到原文 $n$。算法正确性证明省略。

由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。

现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。

inputFormat: 输入文件内容只有一行，为空格分隔的三个正整数$e,N,c$。

outputFormat: 输出文件内容只有一行，为空格分隔的两个整数$d,n$。


title: 付公主的矩形

background: 付公主月考炸了，感到非常郁闷。

description:
为了排解心中的怒气，她造了大量的稻草人来发泄。每天付公主都会把一些稻草人摆成一个 $ R*C $ 的矩形，矩形的每个方格上都有一个稻草人。然后她站在这个矩形的左上角，向矩形的右下角射箭。付公主的箭术过人，她能穿透任意多的稻草人。弓箭经过的方格上的稻草人难逃厄运，报废掉了。看着被毁坏的稻草人，付公主开心了一些。

但是制造稻草人需要大量的金钱，所以付公主不希望坏掉太多的稻草人，所以她每天都选择毁坏掉 $ N $ 个稻草人。付公主还是个喜新厌旧的人，她希望每天能看到一种不同的稻草人摆放矩形。矩形是可以旋转的，即 $ R\times C $ 和 $ C\times R $ 等价。她毫不费力地算出了摆放方案数，于是她决定刁难你一下。不甘示弱的你决定写个程序计算这个数来提交付公主的答卷。

inputFormat: 输入只有一行且只有一个数 $N$（$1\le N\le 10^6$），代表每次被毁坏的稻草人数量。

outputFormat: 一个整数表示总方案数。

hint:
样例解释：
![](https://cdn.luogu.com.cn/upload/pic/16262.png)

对于 $40\%$ 的数据，$1 \le N \le 10^4$。

对于 $100\%$ 的数据，$1 \le N \le 10^6$。


title: [CQOI2016] 伪光滑数

description:
若一个大于 $1$ 的整数 $M$ 的质因数分解有 $k$ 项，其最大的质因子为 $a_k$ ，并且满足 $a_{k}^{k} \le N$，$a_k < 128$，我们就称整数 $M$ 为 $N$ - 伪光滑数。

现在给出 $N$，求所有整数中，第 $K$ 大的 $N$ - 伪光滑数。

### 题意澄清

设 $M = 36 = 2^2 \times 3^2$，则其对应的 $k = 4$，也就是说，对 $M$ 运用唯一分解定理，$M = \prod_{i=1}^n{p_i^{c_i}}$，$k = \sum_{i=1}^n{c_i}$。

第 $K$ 大为字面意思，是真的从大到小第 $K$ 个。

modified by expect2004 2020-11-25，这或许是他退役前对洛谷公共题库的最后一次贡献

inputFormat: 只有一行，为用空格隔开的整数 $N$ 和 $K$ 。

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


title: [CEOI2004] 锯木厂选址

description:
从山顶上到山底下沿着一条直线种植了$n$棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。

木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂，使得运输的费用总和最小。假定运输每公斤木材每米需要一分钱。

你的任务是编写一个程序，从输入文件中读入树的个数和他们的重量与位置，计算最小运输费用。

inputFormat:
输入的第一行为一个正整数$n$——树的个数$(2≤n≤20000)$。树从山顶到山脚按照$1,2,...,n$标号。

接下来$n$行，每行有两个正整数（用空格分开）。

第$i+1$行含有：$w_i$——第$i$棵树的重量（公斤为单位）和 $d_i$——第$i$棵树和第$i+1$棵树之间的距离，$1≤w_i≤10000,0≤d_i≤10000$。

最后一颗树的$d_n$，表示第$n$棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于$2×10^9$分。

outputFormat: 输出最小的运输费用。

hint:
样例图示

黑点为锯木厂

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

本题共有$13$个测试点，每个测试点的数据范围如下

测试点$1-5:n≤200$；

测试点$6-7:n≤1000$；

测试点$7-13:n≤20000$；


title: [SHOI2015] 激光发生器

description:
曾经发明了超能粒子炮・改的发明家 SHTSC 又公开了他的新发明：激光发生器——一种可以产生高能激光的神秘装置。

激光发生器从正上方看是一个无穷大的平面，里面由一个定向激光发射装置和若干个激光偏转装置组成。一个激光发生器的示例如图所示，细箭头表示定向激光发射装置，粗线段表示激光偏转装置。

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

由定向激光发射装置发射出的激光可以看成是一条射线，如果遇到激光偏转装置就会发生偏转。奇特的是，SHTSC 所使用的激光偏转装置并非像传统的镜子那样遵循反射定律，而是对于每个激光偏转装置，有一个固定的偏转系数 $λ$，其出射角 $β$ 与入射角 $α$ 的关系为 $β=λα$，并且能在这一过程中增强激光的能量。

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

注意：

1. 入射角是入射光线和反射平面法向量的夹角。
2. 偏转装置的两面均可偏转。
3. 如果激光平行射入偏转装置，则认为没有发生偏转。
4. 如果不平行且照射到了端点，则认为发生偏转。
5. 当 $β>\frac{1}{2}π$ 时，可能会偏转到另一面。

现在 SHTSC 希望你模拟他所设计的激光发生器的工作过程，来帮助他计算激光究竟被哪些激光偏转装置所偏转。

inputFormat:
第一行四个整数 $x,y,dx,dy$。表示定向激光发射装置的位置是 $(x,y)$，方向是 $(dx,dy)$。

第二行一个整数 $n$，表示一共有 $n$ 个激光偏转装置。
以下n行，每行六个整数 $x1,y1,x2,y2,a,b$，表示一个激光偏转装置是 $(x1,y1)$ 到 $(x2,y2)$ 的一条线段，其偏转系数 $\lambda=a/b$。

$n\leq 100$，所有坐标与 $a$ 和 $b$ 的绝对值不超过 $1000$，$a$、$b$ 均非 $0$。保证所有的偏转装置没有交点。激光发射起始点不在任何偏转装置上。方向向量不为零向量。

outputFormat: 一行由空格隔开的若干个整数，表示激光依次照射到的激光偏转装置的编号（按照输入顺序从 $1$ 到 $n$ 编号）。如果激光被偏转超过 $10$ 次，则只需输出前 $10$ 次所照射到的偏转装置的编号。特别地，如果激光没有被任何一个偏转装置所偏转，输出 `NONE`。

hint:
### 样例解释

如图所示，激光依次被 $1$ 号和 $2$ 号偏转装置偏转。

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

## 数据规模和约定

对于 $10\%$ 的数据，$n=1$；
对于 $40\%$ 的数据，$a=b=1$；
对于 $100\%$ 的数据，$n \le 100$，所有坐标与 $a$ 和 $b$ 的绝对值不超过 $1000$，$a,b$ 均非零，$dx$ 、$dy$ 不同时为零。保证所有的偏转装置没有交点，且激光发射起始点不在任何偏转装置上。


title: [Wind Festival] Running In The Sky

background:
$[Night - 20:02$ $P.M.]$

夜空真美啊……但是……快要结束了呢……

description:
一天的活动过后，所有学生都停下来欣赏夜空下点亮的风筝。$Curtis$ $Nishikino$想要以更近的视角感受一下，所以她跑到空中的风筝上去了(这对于一个妹子来说有点匪夷所思)! 每只风筝上的灯光都有一个亮度 $k_i$. 由于风的作用，一些风筝缠在了一起。但是这并不会破坏美妙的气氛，缠在一起的风筝会将灯光汇聚起来，形成更亮的光源！

$Curtis$ $Nishikino$已经知道了一些风筝间的关系，比如给出一对风筝$(a,b)$, 这意味着她可以从 $a$ 跑到 $b$ 上去，但是不能返回。

现在，请帮她找到一条路径(她可以到达一只风筝多次，但只在第一次到达时她会去感受上面的灯光), 使得她可以感受到最多的光亮。同时请告诉她这条路径上单只风筝的最大亮度，如果有多条符合条件的路径，输出能产生最大单只风筝亮度的答案。

inputFormat:
第一行两个整数 $n$ 和 $m$. $n$ 是风筝的数量, $m$ 是风筝间关系对的数量.

接下来一行 $n$ 个整数 $k_i$.

接下来 $m$ 行, 每行两个整数 $a$ 和 $b$, 即$Curtis$可以从 $a$ 跑到 $b$.

outputFormat: 一行两个整数。$Curtis$在计算出的路径上感受到的亮度和，这条路径上的单只风筝最大亮度.


title: [NOI2002] 贪吃的九头龙

background: 传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是 说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的 总数会远大于九，当然也会有旧头因衰老而自己脱落。

description:
有一天，有 $M$ 个脑袋的九头龙看到一棵长有 $N$ 个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把 $N$ 个果子分成 $M$ 组，每组至少有一个果子，让每个头吃一组。

这 $M$ 个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好 $K$ 个果子，而且 $K$ 个果子中理所当然地应该包括唯一的一个最大的果子。果子由 $N-1$ 根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。

对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。

九头龙希望它的“难受值”尽量小，你能帮它算算吗？

例如图 $1$ 所示的例子中，果树包含 $8$ 个果子，$7$ 段树枝，各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋，大头需要吃掉 $4$ 个果子，其中必须包含最大的果子。即 $N=8$，$M=2$，$K=4$：

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

图一描述了果树的形态，图二描述了最优策略。

inputFormat:
输入的第 $1$ 行包含三个整数 $N\ (1 \le N \le 300)$，$M(2 \le M \le N)$，$K(1 \le K \le N)$。$N$ 个果子依次编号 $1,2, \cdots N$，且最大的果子的编号总是 $1$。

第 $2$ 行到第 $N$ 行描述了果树的形态，每行包含三个整数 $a\ (1 \le a \le N), b\ (1 \le b \le N), c\ (0 \le c \le 10^5)$，表示存在一段难受值为 $c$ 的树枝连接果子 $a$ 和果子 $b$。

outputFormat: 输出仅有一行，包含一个整数，表示在满足“大头”的要求 的前提下，九头龙的难受值的最小值。如果无法满足要求，输出 $-1$。

hint: 该样例对应于题目描述中的例子。


title: [IOI2008] Island

description:
你准备浏览一个公园，该公园由 $N$ 个岛屿组成，当地管理部门从每个岛屿 $i$ 出发向另外一个岛屿建了一座长度为 $L_i$ 的桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制：

- 可以自行挑选一个岛开始游览。
- 任何一个岛都不能游览一次以上。
- 无论任何时间，你都可以由当前所在的岛 $S$ 去另一个从未到过的岛 $D$。从 $S$ 到 $D$ 有如下方法：
  - 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
  - 渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 $S$ 走到 $D$ (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。

注意，你不必游览所有的岛，也可能无法走完所有的桥。

请你编写一个程序，给定 $N$ 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的长度之和的最大值。

inputFormat:
第一行包含一个整数 $N$，即公园内岛屿的数目。

随后的 $N$ 行每一行用来表示一个岛。第 $i$ 行由两个以单空格分隔的整数，表示由岛 $i$ 筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 $L_i$。你可以假设对于每座桥，其端点总是位于不同的岛上。

outputFormat: 仅包含一个整数，即可能的最大步行距离。

hint:
**样例解释**：

![样例图示](https://cdn.vijos.org/fs/c82895f1d6f84d5756610176662d6ee644c3e55e)

样例 $N=7$ 座桥，分别为 $(1-3), (2-7), (3-4), (4-1), (5-1), (6-3)$ 以及 $(7-2)$。注意连接岛 $2$ 与岛 $7$ 之间有两座不同的桥。

其中一个可以取得最大的步行距离的方法如下：

- 由岛 $5$ 开始。
- 步行长度为 $9$ 的桥到岛 $1$。
- 步行长度为 $8$ 的桥到岛 $3$。
- 步行长度为 $4$ 的桥到岛 $6$。
- 搭渡船由岛 $6$ 到岛 $7$。
- 步行长度为 $3$ 的桥到岛 $2$。

最后，你到达岛 $2$，而你的总步行距离为 $9+8+4+3=24$。

只有岛 $4$ 没有去。注意，上述游览结束时，你不能再游览这个岛。更准确地说：

- 你不可以步行去游览，因为没有桥连接岛 $2$ (你现在的岛) 与岛 $4$。
- 你不可以搭渡船去游览，因为你可由当前所在的岛 $2$ 到达岛 $4$。一个方法是：走 $(2-7)$ 桥，再搭你曾搭过的渡船由岛 $7$ 去岛 $6$，然后走 $(6-3)$ 桥，最后走 $(3-4)$ 桥。

**数据范围**：

对于 $100\%$ 的数据，$2\leqslant N\leqslant 10^6,1\leqslant L_i\leqslant 10^8$。


title: [HNOI2009] 无归岛

description:
Neverland 是个神奇的地方，它由一些岛屿环形排列组成，每个岛上都生活着之中与众不同的物种。

但是这些物种都有一个共同的生活习性：对于同一个岛上的任意两个生物，他们有且仅有一个公共朋友，即对同一岛上的任意两个生物 a 和 b 有且仅有一个生物 c 既是 a 的朋友也是 b 的朋友，当然某些岛上也可能会只有一个生物孤单地生活着。

这一习性有一个明显的好处，当两个生物发生矛盾的时候，他们可以请那个唯一的公共朋友来裁决谁对谁错。 另外，岛与岛之间也有交流，具体来说，每个岛都会挑选出一个最聪明的生物做代表，然后这个生物与他相邻的两个岛的代表成为朋友。

不幸运的是，A 世界准备入侵 Neverland，作为 Neverland 的守护者，Lostmonkey 想知道在一种比较坏的情况下 Neverland 的战斗力。因为和朋友并肩作战，能力会得到提升，所以 Lostmonkey 想知道在不选出一对朋友的情况下Neverland的最大战斗力。即选出一些生物，且没有一对生物是朋友，并且要求它们的战斗力之和最大。

inputFormat:
第一行包含用空格隔开的两个整数 $n$ 和 $m$，分别表示 Neverland 的生物种数和朋友对数。

接下来的 $m$ 行描述所有朋友对，具体来说，每行包含用空格隔开的两个整数 $a$ 和 $b$，表示生物 $a$ 和生物 $b$ 是朋友（每对朋友只出现一次）。第 $m+2$ 行包含用空格隔开的 $n$ 个整数，其中第 $i$ 个整数表示生物 $i$ 的战斗力 $A_i$。

outputFormat: 仅包含一个整数，表示满足条件的最大战斗力。


title: [Code+#4] 组合数问题

description: 众所周知，小葱同学擅长计算，尤其擅长计算组合数，所以小葱给了你两个数 $x$ 和 $k$，希望你把 $x$ 分成恰好 $k$ 个不同的组合数的和。所谓不同，即对于两个组合数 $C(n_1,m_1)$ 和 $C(n_2,m_2)$，如果 $n_1\neq n_2$ 或者 $m_1\neq m_2$，我们就称这两个组合数是不同的。为了使得计算不过于复杂，你需要保证你给出的任何一个组合数 $C(n,m)$ 满足 $0\leq m\leq n\leq x$。数据保证一定有解。

inputFormat:
从标准输入读入数据。

第一行两个整数 $x,k$。

outputFormat:
输出到标准输出。

$k$ 行，每行两个整数 $n,m$ 代表一个组合数 $C(n,m)$。如果有多种可能的答案，任意输出一组即可。

hint:
对于 $20\%$ 的数据，$k=1$。

对于另外 $20\%$ 的数据，$x\leq 100$。

对于另外 $20\%$ 的数据，$k=2$。

对于 $100\%$ 的数据，$1\leq x\leq 10^9,1\leq k\leq 10^3.$

Credit: https://www.luogu.org/discuss/show/38908


title: [Code+#4] 喵呜

description:
在马路边有一排整齐的 $n$ 棵樱花树，每棵树的高度都恰好为 $h$。某天，一只可爱的小猫偶然跑到树上来玩，但是这只小猫有些对樱花过敏，所以她现在想赶快离开这些樱花树。

具体来说，现在小猫位于第 $x$ 棵樱花树上高度为 $y$ 的位置，她可以通过两种跳跃来离开樱花树：

轻轻跳：向左或向右移动 $a$ 棵樱花树的同时，所在高度下降 $b$，即一次轻轻跳可以从起点移动到第 $x+a$ 或 $x-a$ 棵树上高度为 $y-b$ 的位置，注意当小猫所在高度不大于 $b$ 时不可以使用轻轻跳。

使劲跳：向左或向右移动 $a$ 棵樱花树的同时，所在高度上升 $b$，即一次使劲跳可以从起点移动到第 $x+a$ 或 $x-a$ 棵树上高度为 $y+b$ 的位置，注意当小猫所在高度大于 $h-b$ 时不可以使用使劲跳。

为了离开这片樱花树，小猫需要移动到第 $1$ 或第 $n$ 棵树上，高度为 $h$ 或 $1$ 的位置（这样她可以呼吸新鲜空气或者直接走开樱花树）。现在小猫想知道，自己最少需要多少次跳跃才能达成目标。由于她是一只可爱的小猫，所以希望由你来告诉她。

inputFormat:
从标准输入读入数据。

输入数据第一行包含一个正整数 $T$，表示测试数据的组数，各组数据之间没有空行。

接下来 $T$ 行，依次描述每组数据：

每组数据包含一行，包含六个正整数 $n,h,x,y,a,b$，其含义见题目描述。

outputFormat:
输出到标准输出。

输出由 $T$ 组数据组成，各组数据之间没有空行。对于每一组数据：

若小猫可以成功离开樱花树，请输出她需要的最少跳跃次数。

若小猫无法通过给定的跳跃方法离开樱花树，**请输出-1**。


title: [Code+#4] 白金元首与七彩魔法

background: 小朋友 你们好吗　还能记得 我是谁吗　我就是魔法元首まどか！

description:
「和我签订契约，成为魔法元首吧！」

于是这天元首不明所以地被地外生物 Kyubey 忽悠去成为了魔法元首。不过在开始练习魔法之前，元首需要为自己的魔法选择一个代表色。

下图是一个明度最大（即，HSV 色彩空间中 $V = 100\%$）的单位圆色盘。色盘上任意一点的坐标为一个非负实数对 (α°,$r\%$) $(0 \leq \alpha < 360,0 \leq r \leq 100)$，表示色相为 α°、饱和度为 $r\%$ 的颜色。另一种理解是，α° 表示从联结圆心和纯红色点的射线顺时针到达该点所经过的角度，$\frac {r}{100}$ 是该点到单位圆圆心的距离。

![0](https://i.loli.net/2018/04/02/5ac1bb23a4d50.png)

具体而言，从这个坐标 (α°,$r\%$) 到红绿蓝颜色值 $(R,G,B)$ 的转换如下：

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

请参照样例确认你对公式的理解和实现。

按照 Kyubey 的判断，元首可以选择色盘所在的平面上一条给定直线段 (α1°,$r1\%$)-(α2°,$r2\%$) 上的任意颜色。元首可不需要犹豫，作为一名 bling bling 的帝国领导者，当然要选择最亮的颜色啦！

一个颜色 $(R,G,B)$ 的亮度定义为 $L = 0.30R + 0.59G + 0.11B$。下图给出了彩色色盘和表示亮度的灰度色盘的左右对比。

![2](https://i.loli.net/2018/04/02/5ac1bb2371a0b.png)

你需要编写程序帮助元首计算给定直线段上所有颜色的最大亮度。

inputFormat:
从标准输入读入数据。

输入的第一行包含一个正整数 $T$—— 数据的组数。接下来包含 $T$ 组数据，格式如下，数据间没有空行。

第 $1$ 行：四个空格分隔的整数 $\alpha_1$、$r_1$、$\alpha_2$、$r_2$。

outputFormat:
输出到标准输出。

对于每组数据输出一行，包含一个 $[0,1]$ 范围内的十进制小数 —— 直线段 (α1°,$r1\%$)-(α2°,$r2\%$) 上所有颜色的最大亮度，四舍五入保留恰好四位小数。数据保证若参考答案为 $A$，则 [$A-10^{-5},A+10^{-5}$] 范围内任意实数四舍五入到第四位小数后均相等。


title: [Code+#4] 组合数问题2

description: 众所周知，小葱同学擅长计算，尤其擅长计算组合数，所以小葱给了你两个数 $n$ 和 $k$，希望你找到 $k$ 个不同的组合数使得这 $k$ 个组合数的和最大。所谓不同的组合数，即对于组合数 $C_{a_1}^{b_1}$ 和 $C_{a_2}^{b_2}$，若 $a_1\neq a_2$ 或者 $b_1\neq b_2$，则我们认为这两个组合数是不同的。现在小葱希望你找到这样 $k$ 个不同的组合数，使得它们互不相同且对于其中任何一个组合数 $C_a^b$ 有 $0\leq b\leq a\leq n$。问这 $k$ 个组合数的和最大是多少？

inputFormat:
从标准输入读入数据。

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

outputFormat:
输出到标准输出。

一行一个整数，代表 $k$ 个组合数的和对 $10^9+7$ 取模之后的结果；数据保证一定有至少 $k$ 个数可以选。

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

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

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

对于 $100\%$ 的数据，$1\leq n\leq 10^6,1\leq k\leq 10^5.$

Credit: https://www.luogu.org/discuss/show/38908


title: [Code+#4] 最短路

background:
在北纬 91° ，有一个神奇的国度，叫做企鹅国。这里的企鹅也有自己发达的文明，称为企鹅文明。因为企鹅只有黑白两种颜色，所以他们的数学也是以二进制为基础发展的。

比如早在 $11101001$ 年前，他们就有了异或这样一个数学概念。如果你不知道异或是什么，请出门过墙左转到[这里](https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96)。

再比如早在 $1000010$ 年前，他们的大科学家 Penguin. Tu 就提出了[图](https://zh.wikipedia.org/wiki/%E5%9B%BE_%28%E6%95%B0%E5%AD%A6%29#%E6%9C%89/%E7%84%A1_%E5%90%91%E5%9B%BE)和[最短路径](https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98)这样一些概念。

description:
企鹅国中有 $N$ 座城市，编号从 $1$ 到 $N$ 。

对于任意的两座城市 $i$ 和 $j$ ，企鹅们可以花费 $(i~\mathrm{xor}~j) \times C$ 的时间从城市 $i$ 走到城市 $j$ ，这里 $C$ 为一个给定的常数。

当然除此之外还有 $M$ 条单向的快捷通道，第 $i$ 条快捷通道从第 $F_i$ 个城市通向第 $T_i$ 个城市，走这条通道需要消耗 $V_i$ 的时间。

现在来自 **P**enguin **K**ingdom **U**niversity 的企鹅豆豆正在考虑从城市 $A$ 前往城市 $B$ 最少需要多少时间？

inputFormat:
从标准输入读入数据。

输入第一行包含三个整数 $N,M,C$ ，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数$C$。

接下来的 $M$ 行，每行三个正整数 $F_i,T_i,V_i$ ($1 \leq F_i \leq N$,$1 \leq T_i \leq N ,1\leq V_i \leq 100$)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。

最后一行两个正整数 $A,B$ $(1 \leq C \leq 100)$，表示企鹅豆豆选择的起点城市标号和终点城市标号。

outputFormat:
输出到标准输出。

输出一行一个整数，表示从城市 $A$ 前往城市 $B$ 需要的最少时间。

hint:
**样例1解释**

直接从 $1$ 走到 $4$ 就好了。

**样例2解释**

先从 $3$ 走到 $2$ ，再从 $2$ 通过通道到达 $4$ ，再从 $4$ 走到 $6$。

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

活泼可爱的出题人给大家留下了下面这张图。

![1](https://i.loli.net/2018/04/02/5ac1bb2333c22.jpg)

Credit: https://www.luogu.org/discuss/show/38908


title: [SHOI2015] 零件组装机

description:
曾经发明了激光发生器的发明家 SHTSC 又公开了他的新发明：零件组装机——一种可以生产并组装零件的神秘装置。

一个零件是一张顶点由 $0$ 到 $n-1$ 标号的无向图，零件组装机有以下两种功能：

 1. 生产一个仅有一个顶点标号为$0$而没有边的零件。

 2. 组合两个已有的零件 $G_1$、$G_2$ ，且 $G_2$ 的顶点数 $m$ 大于等于 $G_1$ 的顶点数 $n$ ，得到新的零件 $G$ 。$G$ 的顶点集合是 $G_1,G_2$ 顶点集合的并集，并且 $G_2$ 的顶点 $i(0\leq i < m)$ 被重新标号为  $n+i$ 。$G$ 的边集是 $G_1,G_2$边集的并集再对所有标号为 $a(a \geq n)$ 的顶点添加一条连接$(a,a \mod n)$的无向边。

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

现在 SHTSC 正在思考，对于一个给定的零件，能否由零件组装机生产组装得到。注意：零件是带标号的，这意味着两个零件即使仅有标号不同也被视为不同的零件。为了帮助你理解问题，SHTSC 特地给了你顶点数 $\le 5$的所有零件的图例。

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

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

每组数据的第一行有两个整数 $n$，$m$，表示某个带标号的无向图有 $n$ 个从 $0$ 到 $n - 1$ 标号的顶点，以及 $m$ 条边。 接下来 $m$ 行，每行两个整数 $u,v$ ，表示一条从 $u$ 到 $v$ 的无向边。

outputFormat: 对于每组数据，输出一行。如果这个无向图可以被零件制造机制造，输出 YES，否则输出 NO。

hint:
对于 $5\%$ 的数据，图给定的图联通且 $m = n - 1$；
对于另 $15\%$ 的数据，$n \leq 5$；
对于 $50\%$ 的数据，$n \leq 1000$；
对于所有测试点，$t \leq 10$，$n,m \leq 100000$。


title: [Code+#4] Tommy 的结合

background:
深邃的天空仿佛要吞噬一切，一场 Codeforces 比赛刚刚结束。“怎么还不理我……”，睡眼惺忪的 Tommy 拿起盖在一旁的手机。空空荡荡的 QQ 提示框，没有一丝的温度。Tommy 叹了口气。昏黄的灯发出微弱的光芒，抚摸着呼呼作响的电脑。

桌面上堆满了写满 $\partial$ 和 $\int$ 的草稿纸，手机闪光灯自制的简易台灯发出刺眼的白光；灯火缱绻，映照一双如画倦容。十几个 DDL 就在附近，QQ 那边的人已经三天三夜没有合眼了。这是 Tommy 所不知道的事。

description:
人生大概就是这样。在这物欲横流的红尘紫陌中，芸芸众生为了生计四处奔走，交谈越来越少，感情越来越淡。但是，著名科学家 Access Globe 的最新研究成果可以解决这样的问题：通过增加同时做的事情来增加共同语言。

A 和 B 都得到了一些任务，设他们要执行的任务集合分别为 $V_A$ 和 $V_B$。对每个人来说，任务 $1$ 是必须一开始做的，而其他的每个任务 $e$ 都存在一个前置任务 $p_e$，表示任务 $e$ 必须在任务 $p_e$ 完成后才能执行。也就是说，每个人的任务的依赖关系构成了一棵**有根外向树**，一个任务 $e$ 能被执行当且仅当 $p_e,p_{p_{e}},\cdots,1$ 这些任务全部都被执行，称 $p$ **依赖**任务 $p_e,p_{p_{e}},\cdots,1$。

现在，A 和 B 希望他们能有一些任务是共同完成的，因此他们决定这样选出一些任务：A 选出 $m$ 个任务 $a_1,\cdots,a_m$，要求 $a_1=1$，并且对于任意的 $1\le i<m$，都要求 $a_{i+1}$ 依赖任务$a_i$,同时 B 也选出 $m$ 个满足同样要求的任务 $b_1,\cdots,b_m$，这样，A 就可以沿着从 $1$ 到 $A_m$ 的路径依次执行这些任务，同时 B 也可以沿着 $1$ 到 $B_m$ 的路径依次执行这些任务；并且经过安排，当 A 在执行任务 $a_i$ 的时候，B 恰好在执行任务 $b_i$，在这时 A 和 B 就能取得联系，增进感情。

模型的目标为最大化亲密度。对于一组同时执行任务的关系 $a_i$ 和 $b_i$，可以获得 $C_{a_i,b_i}$ 的得分；同时，A 和 B 一旦失去联系，就会使得亲密度降低，在每一分钟，如果一方距离上次和对方联系后已经执行任务 $i$ 分钟，就会使得亲密度降低 $2i-1$。

例如，两个人要做的任务所花费的时间分别为 $2,1,4,7$ 和 $4,8,3,6,4$，并且共同完成了第一个任务和最后一个任务，那么 A 在执行中间两个任务的 $1+4=5$ 分钟没有和 B 联系，使得亲密度降低 $1+3+...+11=25$；同时 B 在执行中间三个任务的 $8+3+6=17$ 分钟没有和 A 联系，使得亲密度降低 $1+3+...+35=289$。注意，亲密度的计算只和任务执行的时间有关；并且任意两个任务都可以作为 $a_i$ 和 $b_i$ 同时执行，不需要保证它们花费的时间相同。

现在，给出 A 和 B 的任务、依赖关系和每个任务的执行时间，请你帮我们求出能够获得的最大的亲密度。

inputFormat:
从标准输入读入数据。

第一行两个整数 $|V_A|,|V_B|$；

第二行 $|V_A|-1$ 个整数 $t^{(a)}_{2},t^{(a)}_{3},...,t^{(a)}_{|V_A|}$，表示 A 的每个任务的时间长度；

第三行 $|V_B|-1$ 个整数 $t^{(b)}_{2},t^{(b)}_{3},...,t^{(b)}_{|V_B|}$，表示 B 的每个任务的时间长度；

第四行 $|V_A|-1∣$ 个整数 $p^{(a)}_{2},p^{(a)}_{3},...,p^{(a)}_{|V_A|}$，表示 A 的每个任务的前置任务，保证 $p^{(a)}_{i}< i$；

第五行 $|V_B|-1$ 个整数 $p^{(b)}_{2},p^{(b)}_{3},...,p^{(b)}_{|V_B|}$，表示 B 的每个任务的前置任务，保证 $p^{(b)}_{i}< i$；

接下来 $|V_A|-1$ 行，每行 $|V_B|-1$ 个整数，第 $i-1$ 行第 $j-1$ 列为 $C_{i,j}$，表示 A 和 B 同时分别执行对应的任务 $i,j$ 能获得的亲密度，注意这些亲密度不一定是非负的；

注意以上输入均不包括第 1 个任务的信息，因为它和亲密度的计算没有关系。

outputFormat:
输出到标准输出。

输出能获得的最大的亲密度。

hint:
**样例解释**

A 和 B 分别选出任务 $1,3,4$ 和 $1,2,3$，同时执行的任务对 $(1,1)$、$(3,2)$ 和 $(4,3)$ 使得他们获得了 $4+5=9$ 的亲密度；A 孤独地执行任务 $2$ 的 $2$ 分钟丢失了 $1+3=4$ 的亲密度，因此最终的总亲密度为 $9-4=5$。这就是亲密度最大的方案。

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

对于所有数据，$2\le |V_A|,|V_B|\le 2,666$，$1\le t^{(a)}_i,t^{(b)}_i\le 1,206$，$0\le |C_{i,j}|\le 2,017,011,328$。

Credit: https://www.luogu.org/discuss/show/38908

Credit：idea 与命题/陈俊锟　验题/Tommy > <

Git Repo：https://git.thusaac.org/publish/CodePlus4

感谢腾讯公司对此次比赛的支持。


title: [AHOI2018初中组] 报名签到

description: $n$ 位同学（编号从 $1$ 到 $n$）同时来到体育馆报名签到，领取准考证和参赛资料。为了有序报名，这 $n$ 位同学需要按编号次序（编号为 $1$ 的同学站在最前面）从前往后排成一条直线。然而每一位同学都不喜欢拥挤，对于第 $i$ 位同学，如果有另外一位同学距离他/她的距离小于 $a_i$，那么就会发生冲突。小可可想知道如果要不发生任何冲突的情况下，这 $n$ 位同学排队的队列最短长度是多少。

inputFormat:
第一行一个整数 $n$ ，表示报名签到的同学人数。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个同学必须与其他同学保持的距离。

outputFormat:
输出一行，包括一个整数，表示这 $n$ 位同学排队队列的最小长度。

注意： $n$ 位同学要按 $1$ 到 $n$ 的次序从前往后排队。


title: [BOI2007] Sequence 序列问题

description:
对于一个给定的序列 $a _ 1, \cdots, a _ n$，我们对它进行一个操作 $\text{reduce}(i)$，该操作将数列中的元素 $a _ i$ 和 $a _ {i+1}$ 用一个元素 $\max(a _ i,a _ {i+1})$ 替代，这样得到一个比原来序列短的新序列。这一操作的代价是 $\max(a _ i,a _ {i+1})$。进行 $n-1$ 次该操作后，可以得到一个长度为 $1$ 的序列。

我们的任务是计算代价最小的 $\text{reduce}$ 操作步骤，将给定的序列变成长度为 $1$ 的序列。

inputFormat:
第一行为一个整数 $n$（$1 \leq n \leq 10 ^6$），表示给定序列的长度。

接下来的 $n$ 行，每行一个整数 $a _ i$（$0 \leq a _ i \leq 10 ^ 9$），为序列中的元素。

outputFormat: 只有一行，为一个整数，即将序列变成一个元素的最小代价。


title: [BOI2007] Sound 静音问题

description:
数字录音中，声音是用表示空气压力的数字序列描述的，序列中的每个值称为一个采样，每个采样之间间隔一定的时间。

很多声音处理任务都需要将录到的声音分成由静音隔开的几段非静音段。为了避免分成过多或者过少的非静音段，静音通常是这样定义的：$m$ 个采样的序列，该序列中采样的最大值和最小值之差不超过一个特定的阈值 $c$。

请你写一个程序，检测 $n$ 个采样中的静音。

inputFormat:
第一行有三个整数 $n,m,c$（$1\le n\le10^6$，$1\le m\le10^4$，$0\le c\le10^4$），分别表示总的采样数、静音的长度和静音中允许的最大噪音程度。

第 $2$ 行 $n$ 个整数 $a_i$（$0\le a_i\le 10^6$），表示声音的每个采样值，每两个整数之间用空格隔开。

outputFormat: 列出了所有静音的起始位置 $i$（$i$ 满足$\max\{a_i,a_{i+1}\cdots a_{i+m-1}\}-\min\{a_i,a_{i+1}\cdots a_{i+m-1}\}\le c$），每行表示一段静音的起始位置，按照出现的先后顺序输出。如果没有静音则输出 `NONE`。


title: [BOI2009] Radio Transmission 无线传输

description: 给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的（保证至少重复 $2$ 次）。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

inputFormat:
第一行一个整数 $L$，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

outputFormat: 仅一行，表示 $s_2$ 的最短长度。

hint:
#### 样例输入输出 1 解释
对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabcabc}$，读入的 $\texttt{cabcabca}$，是它的子串。

#### 规模与约定
对于全部的测试点，保证 $1 < L \le 10^6$。


title: [BalkanOI2007] Mokia 摩基亚

description:
摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如 “用户 C 的位置在哪？” 的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如 “给定区域内有多少名用户？” 的问题。

在定位系统中，世界被认为是一个 $w\times w$ 的正方形区域，由 $1\times 1$ 的方格组成。每个方格都有一个坐标 $(x, y)$，$1\leq x,y\leq w$。坐标的编号从 $1$ 开始。对于一个 $4\times 4$ 的正方形，就有 $1\leq x\leq 4$，$1\leq y\leq 4$（如图）：

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

请帮助 Mokia 公司编写一个程序来计算在某个矩形区域内有多少名用户。

inputFormat:
有三种命令，意义如下：

|命令|参数|意义|
|:-:|:-:|:-:|
|$0$|$w$|初始化一个全零矩阵。本命令仅开始时出现一次。|
|$1$|$x\ y\ a$|向方格 $(x, y)$ 中添加 $a$ 个用户。$a$ 是正整数。|
|$2$|$x_1\ y_1\ x_2\ y_2$|查询 $x_1\leq x\leq x_2$，$y_1\leq y\leq y_2$ 所规定的矩形中的用户数量。|
|$3$|无参数|结束程序。本命令仅结束时出现一次。|

输入共若干行，每行有若干个整数，表示一个命令。

outputFormat: 对所有命令 $2$，输出一个一行整数，即当前询问矩形内的用户数量。

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

对于 $100\%$ 的数据，保证：
- $1\leq w\leq 2\times 10 ^ 6$。
- $1\leq x_1\leq x_2\leq w$，$1\leq y_1\leq y_2\leq w$，$1\leq x,y\leq w$，$0<a\leq 10000$。
- 命令 $1$ 不超过 $160000$ 个。
- 命令 $2$ 不超过 $10000$ 个。


title: [JSOI2008] Blue Mary的战役地图

description:
Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。

由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。

具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。

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

以下n行，每行包含n个正整数，表示第一张战役地图的代表矩阵。

再以下n行，每行包含n个正整数，表示第二张战役地图的代表矩阵。

outputFormat: 仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。

hint:
样例解释：

子矩阵：
5 6
8 9
为两个地图的最大公共矩阵

约定：
n<=50


title: [JSOI2008] Blue Mary的职员分配

description:
由于Blue Mary呕心沥血的管理，Blue Mary的网络公司蒸蒸日上。现在一共拥有了n名职员，可惜没有任何的金钱和声誉。平均每名每天职员都可以给公司带来x单位金钱或者y单位声誉（名利不能双全）。并且可以花费z单位的金钱在人才交易市场发布广告招聘职员，每次发布广告三天以后就会招聘到一名职员，并且必须在发布广告并且招聘到职员的那一天才能发布下一次广告。

Blue Mary计划以最快的时间获得至少A单位金钱和至少B单位声誉，请你计算一下他至少需要多少时间才能达到他的目标。

inputFormat: 输入有且仅有一行，包含六个整数n,x,y,z,A和B，意义如题目描述所述。

outputFormat: 要求输出一行，包含一个整数，表示Blue Mary至少需要多少时间才能达到他的目标。


title: [JSOI2008] Blue Mary的旅行

description:
在一段时间之后，网络公司终于有了一定的知名度，也开始收到一些订单，其中最大的一宗来自 B 市。

Blue Mary 决定亲自去签下这份订单。为了节省旅行经费，他的某个金融顾问建议只购买 U 航空公司的机票。 U 航空公司的所有航班每天都只有一班，并且都是上午出发当天下午到达的，所以他们每人每天只能坐一班飞机。

经过调查，他们得到了 U 航空公司经营的所有航班的详细信息，这包括每一航班的出发地，目的地以及最多能买到的某一天出发的票数。(注意: 对于一个确定的航班，无论是哪一天，他们最多能买到的那一天出发的票数都是相同的）。

Blue Mary 注意到他们一定可以只乘坐 U 航空公司的航班就从 A 市到达 B 市，但是，由于每一航班能买到的票的数量的限制，他们所有人可能不能在同一天到达 B 市。

所以现在 Blue Mary 需要你的帮助，设计一个旅行方案使得最后到达B市的人的到达时间最早。

inputFormat:
第一行包含 $3$ 个正整数 $N$，$M$ 和 $T$。
题目中会出现的所有城市分别编号为 $1,2,\dots,N$，其中城市 A 编号一定为 $1$，城市 B 编号一定为 $N$。
U 公司一共有 $M$ 条（单向）航班。而连 Blue Mary 在内，公司一共有 $T$ 个人要从 A 市前往 B 市。

以下 $M$ 行，每行包含3个正整数 $x,y,z,$ 表示 U 公司的每一条航班的出发地，目的地以及 Blue Mary 最多能够买到的这一航班某一天出发的票数。(即：无论是哪一天，Blue Mary 最多只能买到 $z$ 张 U 航空公司的从城市 $x$ 出发到城市 $y$ 的机票)。

输入保证从一个城市到另一个城市的单向航班最多只有一个。

outputFormat: 仅有一行，包含一个正整数，表示最后到达 B 市的人的最早到达时间。假设他们第一次乘飞机的那一天是第一天。


title: [JLOI2014] 聪明的燕姿

background:
> 阴天傍晚车窗外
>
> 未来有一个人在等待
>
> 向左向右向前看
>
> 爱要拐几个弯才来
>
> 我遇见谁会有怎样的对白
>
> 我等的人他在多远的未来
>
> 我听见风来自地铁和人海
>
> 我排着队拿着爱的号码牌

description:
城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 $S$，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 $S$。

所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

inputFormat:
输入包含 $k$ 组数据。

对于每组数据，输入包含一个号码牌 $S$。

outputFormat:
对于每组数据，输出有两行，第一行包含一个整数 $m$，表示有 $m$ 个等的人。

第二行包含相应的 $m$ 个数，表示所有等的人的号码牌。

特别地，当某组数据出现 $m=0$，即不存在满足题意的号码牌时，该组数据不应输出第二行（只应输出第一行的 $0$）。

注意：你输出的号码牌必须按照升序排列。


title: [AHOI2013] 作业

description:
此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。

这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 $l$ 个数到第 $r$ 个数)，首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数。

小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。

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

接下来 $n$ 个不超过 $10^5$ 的正整数表示数列

接下来 $m$ 行，每行四个整数 $l,r,a,b$，具体含义参见题意。

outputFormat: 输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $l$ 到 $r$ 这段区间中大小在 $[a,b]$ 中的数的个数，以及大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数（具体可以参考样例）。


title: [BOI2003] Gem 气垫车

description:
给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数

唯一的限制条件是相邻的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。

inputFormat:
先给出一个数字 $N$ 代表树上有 $N$ 个点，$N \le 10000$。

下面 $N-1$ 行，代表两个点相连。

outputFormat: 最小的总权值。

hint: 本题已经添加数据，但考虑到题目年代较为久远（毕竟是 2003 年的 BOI 了）以及洛谷神速评测姬，将此题时限修改为 500ms。


title: 选举

description:
Byteland 国的居民最近一直为议会选举投票。现在，当结果公布的时候，党派不得不决定联合组建政府。

每个党派都会获得议会中的一定席位。联合政府由这些党派中的一部分组成，他们在议会中的席位数之和**严格大于**总席位数的一半。对于联合政府来说，席位越多越好。

一个**过剩**的联合政府是指联合政府中的一个党派被移出后，剩余的联合政府在国会中仍有过半数的席位。

请写一个程序能够找到一个在议会中有着**最大可能席位数**且**不过剩**的联合政府。

inputFormat:
标准输出的第一行包含一个整数 $n$，表示参加选举的党派数。党派被从 $1$ 到 $n$ 编号。

第二行包含 $n$ 个非负整数 $a_1,\dots ,a_n$，被一个空格隔开，$a_i$ 是第 $i$ 个党派获得的席位数。你可以假设国会中的中的总席位数为小于等于 $10^5$ 的正整数。

outputFormat: 包含一个整数，表示最大可能席位数。

hint:
样例解释：选择第二个政党和第四个。

对于全部数据，$1\le n\le 300$。


title: [USACO18OPEN] Multiplayer Moo S

description:
奶牛们提出了一款创新性的新游戏，惊讶的是她们给这款游戏取了个最没创意的名字：“Moo”。
Moo游戏在一个由$N \times N$个正方形格子组成的棋盘上进行，一头奶牛可以通过大叫一声“哞！”然后把她的数字编号写在这个格子里来占有这个格子。

在游戏结束的时候，每个格子中都包含一个数。在这个时刻，如果一头奶牛创建了一个由连通的格子组成的领域，大小不小于其他所有领域，那这头奶牛就获胜。一个“领域”被定义为一些具有相同数字编号的格子，其中每个在领域中的格子都直接与另一个同一领域中的格子通过上、下、左或者是右相邻（对角线不计）。

由于以单牛形式进行游戏有点无聊，奶牛们也对双牛组队进行游戏感兴趣。同一队的两头奶牛像之前一样可以创建一个领域，但是现在领域中的格子可以属于队伍中的任一头奶牛。

给定游戏棋盘的最终状态，请帮助奶牛们计算任何单头奶牛拥有的最大的领域包含的格子数量，以及任何两头奶牛组成的队伍占有的最大的领域包含的格子的数量。两头奶牛占有的领域必须要同时包含队伍中两头奶牛的编号，不能仅仅包含一头。

inputFormat: 输入的第一行包含$N$（$1 \leq N \leq 250$）。下面$N$行，每行包含$N$个整数（每个都在$0 \ldots 10^6$之间），描述棋盘的最终状态。棋盘中至少出现两种不同的数字。

outputFormat: 输出的第一行描述任何单头奶牛占有的最大领域大小，第二行描述任何两头奶牛的队伍占有的最大领域的大小。

hint:
在这个例子中，单头奶牛占有的最大领域是由五个9组成的。如果编号为1和9的奶牛组队，她们可以形成一个大小为10的领域。

供题：Brian Dean


title: [USACO18OPEN] Lemonade Line S

description:
这是农场上一个炎热的夏日，Farmer John要给他的$N$头奶牛发柠檬汽水了！所有的$N$头奶牛（方便起见，编号为$1 \dots N$）都喜欢柠檬汽水，只是有些喜欢的程度更高一些。具体地说，奶牛$i$为了获得柠檬汽水最多愿意排在$w_i$头奶牛之后。现在所有的$N$头奶牛都在田里，但是只要Farmer John敲响牛铃，这些奶牛就会立刻赶到FJ的柠檬汽水站。她们会在FJ开始分发柠檬汽水之前到达，但是没有两头奶牛会在同一时刻到达。此外，当奶牛$i$到达时，当且仅当至多有$w_i$头奶牛在排队时她会来排队。

Farmer John想要提前准备一定量的柠檬汽水，但是他不想浪费。排队的奶牛的数量可能取决于她们到达的顺序。帮助他求出最少可能的排队的奶牛数量。

inputFormat: 第一行包含$N$，第二行包含$N$个用空格分隔的整数$w_1, w_2, \dots, w_N$。输入保证$1 \leq N \leq 10^5$，此外对于每头奶牛$i$，$0 \leq w_i \leq 10^9$。

outputFormat: 输出在所有可能的奶牛到达顺序之下，最小可能的排队的奶牛数量。

hint:
在这个情况下，可能最后仅有三头奶牛在队伍中（这也是最小可能值）。假设$w = 7$和$w = 400$的奶牛先到并等在队伍中。然后$w = 1$的奶牛到达并且会离开，这是由于已经有2头奶牛在队伍中了。然后$w = 2$的两头奶牛到达，一头留下排队，一头离开。

供题：Dhruv Rohatgi


title: [USACO18OPEN] Talent Show G

description:
Farmer John 要带着他的 $n$ 头奶牛，方便起见编号为 $1\ldots n$，到农业展览会上去，参加每年的达牛秀！他的第 $i$ 头奶牛重量为 $w_i$，才艺水平为 $t_i$，两者都是整数。

在到达时，Farmer John 就被今年达牛秀的新规则吓到了：

（一）参加比赛的一组奶牛必须总重量至少为 $W$（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且。

（二）总才艺值与总重量的比值最大的一组获得胜利。

FJ 注意到他的所有奶牛的总重量不小于 $W$，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

inputFormat:
第一行是两个整数，分别表示牛的个数 $n$ 和总重量限制 $W$。

第 $2$ 到 $(n+1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数表示第 $i$ 头奶牛的重量 $w_i$ 和才艺水平 $t_i$。

outputFormat:
请求出 Farmer 用一组总重量最少为 $W$ 的奶牛最大可能达到的总才艺值与总重量的比值。

如果你的答案是 $A$，输出 $1000A$ 向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

请注意当问题的答案恰好是整数 $x$ 时，你的程序可能会由于**浮点数精度误差**问题最后得到一个 $x-\epsilon$ 的答案，向下取整后变为 $x-1$ 导致答案错误。这种情况下你可以在输出答案前给答案加上一个极小的值 $x\gets x+10^{-k}$ 来避免该问题。

hint:
#### 样例解释

在这个例子中，总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为 $11$、重量为 $10$ 的奶牛，但是由于我们需要至少 $15$ 单位的重量，最优解最终为使用这头奶牛加上才艺值为 $21$、重量为 $20$ 的奶牛。这样的话才艺与重量的比值为 $\frac{11+21}{10+20}=\frac{32}{30} = 1.0666\dots$，乘以 $1000$ 向下取整之后得到 $1066$。

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 250$，$1 \leq W \leq 1000$，$1 \leq w_i \leq 10^6$，$1 \leq t_i \leq 10^3$。


title: [USACO18OPEN] Milking Order G

description:
Farmer John的 $N$ 头奶牛（$1 \leq N \leq 10^5$），仍然编号为 $1 \ldots N$，正好闲得发慌。因此，她们发展了一个与 Farmer John 每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会阶层。

经过若干周的研究，Farmer John 对他的奶牛的社会结构总计进行了 $M$ 次观察（$1 \leq M \leq 50,000$）。每个观察结果都是他的某些奶牛的一个有序序列，表示这些奶牛应该以与她们在序列中出现的顺序相同的顺序进行挤奶。比方说，如果Farmer John 的一次观察结果是序列 2、5、1，Farmer John 应该在给奶牛 5 挤奶之前的某个时刻给奶牛 2 挤奶，在给奶牛 1 挤奶之前的某个时刻给奶牛 5 挤奶。

Farmer John 的观察结果是按优先级排列的，所以他的目标是最大化 $X$ 的值，使得他的挤奶顺序能够符合前 $X$ 个观察结果描述的状态。当多种挤奶顺序都能符合前 $X$ 个状态时，Farmer John 相信一个长期以来的传统——编号较小的奶牛的地位高于编号较大的奶牛，所以他会最先给编号最小的奶牛挤奶。更加正式地说，如果有多个挤奶顺序符合这些状态，Farmer John 会采用字典序最小的那一个。挤奶顺序 $x$ 的字典序比挤奶顺序 $y$ 要小，如果对于某个 $j$，$x_i = y_i$ 对所有 $i < j$ 成立，并且 $x_j < y_j$（也就是说，这两个挤奶顺序到某个位置之前都是完全相同的，在这个位置上$x$比$y$要小）。

请帮助 Farmer John 求出为奶牛挤奶的最佳顺序。

inputFormat: 第一行包含 $N$ 和 $M$。接下来的 $M$ 行，每行描述了一个观察结果。第 $i+1$ 行描述了观察结果 $i$，第一个数是观察结果中的奶牛数量 $m_i$，后面是一列 $m_i$ 个整数，给出这次观察中奶牛的顺序。所有 $m_i$ 的和至多为 $200,000$。

outputFormat: 输出 $N$ 个空格分隔的整数，给出一个 $1 \ldots N$ 的排列，为 Farmer John 给他的奶牛们挤奶应该采用的的顺序。

hint:
这里，Farmer John有四头奶牛，他的挤奶顺序应该是奶牛1在奶牛2之前、奶牛2在奶牛3之前（第一个观察结果），奶牛4在奶牛2之前（第二个观察结果），奶牛3在奶牛4之前、奶牛4在奶牛1之前（第三个观察结果）。前两个观察结果可以同时被满足，但是Farmer John不能同时满足所有的规则，因为这样的话会要求奶牛1在奶牛3之前，同时奶牛3在奶牛1之前。

这意味着总共有两种可能的挤奶顺序：1 4 2 3和4 1 2 3，第一种是字典序较小的。

供题：Jay Leeds


title: [USACO18OPEN] Out of Sorts G

description:
留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。

她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie最初的对长度为$N$的数组$A$进行排序的奶牛码实现。
```
sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false
```
显然，奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是，Bessie看上去执着于在她的代码中的不同位置使用这个语句。

在用若干个数组测试了她的代码之后，Bessie得到一个有趣的观察现象：大的元素很快就会被拉到数组末尾，然而小的元素需要很长时间“冒泡”到数组的开头（她怀疑这就是为什么这个算法得名的原因）。为了实验和缓解这一问题，Bessie试着修改了她的代码，使代码在每次循环中向前再向后各扫描一次，从而无论是大的元素还是小的元素在每一次循环中都有机会被拉较长的一段距离。她的代码现在是这样的：
```
sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false
```
给定一个输入数组，请预测Bessie修改后的代码会输出多少次“moo”。

inputFormat: 输入的第一行包含$N$（$1 \leq N \leq 100,000$）。接下来$N$行描述了$A[0] \ldots A[N-1]$，每个数都是一个范围为$0 \ldots 10^9$的整数。输入数据不保证各不相同。

outputFormat: 输出“moo”被输出的次数。

hint: 供题：Brian Dean


title: [USACO18OPEN] Disruption P

description:
Farmer John自豪于他所经营的交通发达的的农场。这个农场是由$N$块牧场（$2 \leq N \leq 50,000$）组成的，$N-1$条双向道路将它们连接起来，每一条道路的都为一单位长度。Farmer John注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。

尽管FJ的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这事实上会将他的农场分为两个不相交的牧场集合，奶牛们只能够在每一个集合内移动但不能在集合间移动。于是FJ又建造了$M$条额外的双向道路（$1 \leq M \leq 50,000$），每一条的长度都是一个至多为$10^9$的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断了。

如果某条原有的道路被阻断了，农场就会被分为两块不相交的区域，那么FJ就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条，从而奶牛们又可以从任何一块牧场去往另一块牧场。

对于农场上每一条原有的道路，帮助FJ选出最短的替代用的道路。

inputFormat: 输入的第一行包含$N$和$M$。接下来的$N-1$行，每行用整数$p$和$q$描述了一条原有的道路，其中$p \neq q$是这条道路连接的两块牧场（在$1 \ldots N$范围内）。剩下的$M$行，每行用三个整数$p$、$q$和$r$描述了一条额外的道路，其中$r$是这条道路的长度。任何两块牧场之间至多只有一条道路。

outputFormat: 对原有的$N-1$条道路的每一条，按照它们在输入中出现的顺序，输出如果这条道路被阻断的话，能够重新连接农场的最短的替代用道路的长度。如果不存在合适的替代用的道路，输出-1。


title: [USACO18OPEN] Train Tracking P

background:
鉴于本题存在特殊要求且大部分人**不遵守**，题解通道关闭。如确有正解，请联系管理员单独添加。

1. 你的程序不需要，也不应该包含 `grader.h` 头文件。
2. 请在程序中加入如下函数声明语句：

```cpp
int get(int);
void set(int,int);
void shoutMinimum(int);
int getTrainLength();
int getWindowLength();
int getCurrentCarIndex();
int getCurrentPassIndex();
```

description:
每天早晨特快列车会经过农场，开往大城市，每天下午它又会折回来，回到郊区。今天，Bessie 会花时间观察它，早晨和下午都会。

Bessie 提前知道，列车有 $N$ 节车厢，方便起见，将其编号为 $0\sim N-1$。车厢 $i$ 有一个 ID $c_i$。在早晨和下午，所有的数字都是可见的，所以对于每节车厢 Bessie 有两次机会观察它的 ID。也就是说，当列车早晨经过的时候，Bessie 能够观察 $c_0$，然后是 $c_1$，直到 $c_{N-1}$。当列车下午驶回的时候，她又一次能够观察 $c_0$，然后是 $c_1$，直到 $c_{N-1}$。

Bessie 挑选了一个整数 $K$，她想要求出每个连续的 $K$ 节车厢中最小的 ID。她有一本能够帮助执行计算的笔记本，但是这个笔记本相当小，并且 Bessie 的手写（蹄写？）字相当大。比方说，可能没有足够的空间记下所有 $N+1-K$ 个最小值。由于某些神秘的原因，Bessie 满足于当她算出最小数的时候向天哞出这些数，所以这个问题至少还不成问题。

列车马上就要来了！帮助 Bessie 在列车经过两次之后求出这 $N+1−K$ 个最小数，确保她有效地利用她有限的笔记本空间。她的笔记本被分为 $5500$ 个部分，方便起见编号为 $0\sim 5499$，每个部分的空间恰好能够记录一个在 $[-2^{31} , 2^{31}-1]$ 之间的整数。最初的时候，每个部分都记录着整数 $0$。

请帮助 Bessie 有效管理她有限的笔记本空间。

### 交互方式

这是一道交互式题目，你不需要使用标准（或文件）输入输出。具体地说，你需要实现下面的函数，这个函数用来帮助 Bessie 有效管理她有限的笔记本空间：

```cpp
void helpBessie(int ID);
```

每当一节列车车厢经过的时候，无论是在早晨和下午，你的函数都会被调用，函数的输入是这节车厢的 ID。

你的 `helpBessie` 函数的实现可以调用下面这些函数：

- `int get(int index)`：获取记录在 Bessie 的笔记本上的给定的索引处的整数值（_index_）。
- `void set (int index, int value)`：设置给定的索引（_index_）处的值为给定的整数值（_value_）。
- `void shoutMinimum (int output)`：通知 Bessie 向天哞一个指定的数。
- `int getTrainLength()`：返回列车的车厢数 $N$。
- `int getWindowLength()`：返回窗口的长度 $K$。
- `int getCurrentCarIndex()`：返回当前正在通过的车厢编号。
- `int getCurrentPassIndex()`：如果 Bessie 正在观察早晨的列车返回 $0$，下午的列车返回 $1$。

为了帮助你开始编码，我们为你提供了初始的 C/C++ 模板。遗憾地，这道题目不支持 Python 和 Pascal 语言的程序。

```cpp
#include "grader.h"

// If you find it necessary, you may import standard libraries here.

void helpBessie(int ID)
{
	// Put your code here.
}
```

调用 `void shoutMinimum (int output)` 函数进行输出。

各个窗口的最小数必须按顺序输出（所以车厢 $0,1,\cdots ,K−1$ 之中的最小值必须在车厢 $1,2,\cdots ,K$ 之中的最小值之前输出，等等），但是除了这个顺序的限制之外，你的函数可以在任何一次函数调用中任意多次地输出一些最小值。比如，你的函数可能在某几次调用中不产生任何输出，而在某几次调用中产生多个输出。

Bessie 拥有惊人的短时记忆能力，因此在 `helpBessie` 函数中没有任何的内存使用限制，除了要满足常规的 256MB 限制。然而，在车厢与车厢之间，Bessie 不能够「记住」任何不在笔记本中出现过的内容。所以在两次函数调用之间，你的程序除了通过 `get` 和 `set` 函数调用之外不能保存任何的状态。

这意味着：

**不允许定义任何非常量的全局或静态变量。任何如此做的提交会被取消成绩。教练会人工检查所有的提交以验证是否符合题目要求。由于这个问题无需文件输入输出，所以也不允许在代码中使用任何的文件输入输出**。

hint:
对于全部数据，$1\le N\le 10^6,0\le c_i\le 10^9,1\le K\le N$，你的程序进行的 `set` 调用和 `get` 调用的总次数被限制为 $25\times 10^6$ 次。

供题：Dhruv Rohatgi


title: [USACO18OPEN] Out of Sorts P

description:
留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。她最喜欢的两个算法是“冒泡排序”和“快速排序”，但是不幸的是Bessie轻易地把它们搞混了，最后实现了一个奇怪的混合算法！
如果数组$A$中$A[...i]$的最大值不大于$A[i+1 \ldots]$的最小值，我们就称元素$i$和$i+1$之间的位置为一个“分隔点”。Bessie还记得快速排序包含对数组的重排，产生了一个分隔点，然后要递归对两侧的$A[...i]$和$A[i+1 \ldots]$排序。然而，尽管她正确地记下了数组中所有的分隔点都可以在线性时间内被求出，她却忘记快速排序应该怎么重排来快速构造一个分隔点了！在这个可能会被证明是排序算法的历史中最糟糕的算法性失误之下，她做出了一个不幸的决定，使用冒泡排序来完成这个任务。

以下是Bessie最初的对数组$A$进行排序的实现的概要。她首先写了一个简单的函数，执行冒泡排序的一轮：

```
bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}
```
她的快速排序（相当快）函数的递归代码是按下面的样子构成的：

```
quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A)
   divide A at all partition points; recursively quickish_sort each piece
}
```
Bessie好奇于她的代码能够运行得多快。简单起见，她计算出她得主循环的每一轮都消耗线性时间，所以她相应增加一个全局变量work_counter的值，以此来跟踪整个算法总共完成的工作量。

给定一个输入数组，请预测quickish_sort函数接收这个数组之后，变量work_counter的最终值。

hint:
在这个例子中，数组开始时为20 2 3 4 9 8 7。在一轮冒泡排序之后（增加7的工作量），我们得到2 | 3 | 4 | 9 8 7 | 20，其中|表示一个分隔点。于是我们的问题被分成了递归的子问题，包括对2、3、4、20排序（每个消耗0单元的工作量）和对9 8 7排序。对于9 8 7这个子问题，主循环的一轮（3单元工作量）得到8 7 | 9，在此之后最后一轮处理8 7（2单元工作量） 就有效地完成了排序。

供题：Brian Dean


title: [USACO18OPEN] Out of Sorts S

description:
留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。

她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie的对长度为$N$的数组$A$进行排序的奶牛码实现。

```
sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false
```
显然，奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是，Bessie看上去执着于在她的代码中的不同位置使用这个语句。

给定一个输入数组，请预测Bessie的代码会输出多少次“moo”。

outputFormat: 输出“moo”被输出的次数。


title: [ZJOI2006] 皇帝的烦恼

description:
经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国土边境安置 $n$ 名将军。不幸的是这 $n$ 名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。

秦皇已经准备好了秘密处决这些无礼的边防大将。

不过为防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。将军们听说他们即将被授予勋章都很开心，他们纷纷上书表示感谢。第 $i$ 个将军要求得到 $a_i$ 枚不同颜色的勋章。但是这些将军都很傲气，如果两个相邻的将军拥有颜色相同的勋章他们就会认为皇帝不尊重他们，会立即造反（编号为 $i$ 的将军和编号为 $i+1$ 的将军相邻；因为他们驻扎的边境可以类似看成一个圆形，所以编号 $1$ 和编号 $n$ 的将军也相邻）。

皇帝不得不满足每个将军的要求，但对他们的飞扬跋扈感到很气愤。于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少种颜色的勋章？

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

接下来 $n$ 行每行一个整数 $a_i$，表示第 $i$ 个将军要求得到多少种勋章。

outputFormat: 输出一个整数，即最少需要多少种勋章。

hint: $1 \leq n \leq 2 \times 10^4$，$1 \leq a_i  \leq 10^5$。


title: [NOI2003] 逃学的小孩

description:
Chris 家的电话铃响起了，里面传出了 Chris 的老师焦急的声音：“喂，是 Chris 的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris 的父母就心急如焚，他们决定在尽量短的时间内找到 Chris。他们告诉 Chris 的老师：“根据以往的经验，Chris 现在必然躲在朋友 Shermie 或 Yashiro 家里偷玩《拳皇》游戏。现在，我们就从家出发去找 Chris，一旦找到，我们立刻给您打电话。”说完砰的一声把电话挂了。

Chris 居住的城市由 $N$ 个居住点和若干条连接居住点的双向街道组成，经过街道 $x$ 需花费 $T_{x}$ 分钟。可以保证，任意两个居住点间有且仅有一条通路。Chris 家在点 $C$，Shermie 和 Yashiro 分别住在点 $A$ 和点 $B$。Chris 的老师和 Chris 的父母都有城市地图，但 Chris 的父母知道点 $A$、$B$、$C$ 的具体位置而 Chris 的老师不知。

为了尽快找到 Chris，Chris 的父母会遵守以下两条规则：

1. 如果 $A$ 距离 $C$ 比 $B$ 距离 $C$ 近，那么 Chris 的父母先去 Shermie 家寻找 Chris，如果找不到，Chris 的父母再去 Yashiro 家；反之亦然。
2. Chris 的父母总沿着两点间唯一的通路行走。

显然，Chris 的老师知道 Chris 的父母在寻找 Chris 的过程中会遵守以上两条规则，但由于他并不知道 $A$、$B$、$C$ 的具体位置，所以现在他希望你告诉他，最坏情况下 Chris的父母要耗费多长时间才能找到 Chris？

inputFormat:
输入文件第一行是两个整数 $N$ 和 $M$，分别表示居住点总数和街道总数。

以下 $M$ 行，每行给出一条街道的信息。第 $i+1$ 行包含整数 $U_{i}$、$V_{i}$、$T_{i}$，表示街道 $i$ 连接居住点 $U_{i}$ 和 $V_{i}$，并且经过街道 $i$ 需花费 $T_{i}$ 分钟。街道信息不会重复给出。

outputFormat: 输出文件仅包含整数 $T$，即最坏情况下 Chris 的父母需要花费 $T$ 分钟才能找到 Chris。


title: [JSOI2009] 电子字典

description:
人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法，而只知道该单词的一个错误的近似拼法，这时人们可能陷入困境，为了查找一个单词而浪费大量的时间。带有模糊查询功能的电子字典能够从一定程度上解决这一问题：用户只要输入一个字符串，电子字典就返回与该单词编辑距离最小的几个单词供用户选择。

字符串 $a$ 与字符串 $b$ 的编辑距离是指：允许对 $a$ 或 $b$ 串进行下列“编辑”操作，将 $a$ 变为 $b$ 或 $b$ 变为 $a$，最少“编辑”次数即为距离。

1. 删除串中某个位置的字母；
2. 添加一个字母到串中某个位置；
3. 替换串中某一位置的一个字母为另一个字母。

JSOI 团队正在开发一款电子字典，你需要帮助团队实现一个用于模糊查询功能的计数部件：对于一个待查询字符串，如果它是单词，则返回 $-1$；如果它不是单词，则返回字典中有多少个单词与它的编辑距离为 $1$。

inputFormat:
第一行包含两个正整数 $N$ 和 $M$。

接下来的 $N$ 行，每行一个字符串，第 $i+1$ 行为单词 $W_i$，单词长度在 $1$ 至 $20$ 之间。

再接下来 $M$ 行，每行一个字符串，第 $i+N+1$ 表示一个待查字符串 $Q_i$。待查字符串长度在 $1$ 至 $20$ 之间。$W_i$ 和 $Q_i$ 均由小写字母构成，文件中不包含多余空格。

outputFormat:
输出应包括 $M$ 行，第 $i$ 行为一个整数 $X_i$：

- $X_i = -1$ 表示 $Q_i$ 为字典中的单词；

- 否则 $X_i$ 表示与 $Q_i$ 编辑距离为 $1$ 的单词的个数。

samples:
4 3
abcd
abcde
aabc
abced
abcd
abc
abcdd

hint:
### 样例解释

- `abcd` 在单词表中出现过；
- `abc` 与单词 `abcd`、`aabc` 的编辑距离都是 $1$；
- `abcdd` 与单词 `abcd`、`abcde`、`abced` 的编辑距离都是 $1$。

### 数据范围与约定

- 所有单词互不相同，但是查询字符串可能有重复；
- 对 $50\%$ 的数据范围，$N,M\le 10^3$；
- 对 $100\%$ 的数据范围，$N,M\le 10^4$。


title: [CQOI2005] 三角形面积并

description: 给出 $n$ 个三角形，求它们并的面积。

inputFormat:
第一行为 $n(n \leq 100)$， 即三角形的个数。

以下 $n$ 行，每行 $6$ 个实数 $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$，代表三角形的顶点坐标。坐标均为不超过 $10^6$ 的实数，输入数据保留 $1$ 位小数。

outputFormat: 输出并的面积 $u$, 保留两位小数。


title: [Cerc2007] robotic sort 机械排序

description:
SORT公司是一个专门为人们提供排序服务的公司，该公司的宗旨是：“顺序是最美丽的”。他们的工作是通过一系列移动，将某些物品按顺序摆好。他们的工作规定只能使用如下方法排序：

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

先找到编号最小的物品的位置P1，将区间[1，P1]反转，再找到编号第二小的物品的位置P2,将区间[2,P2]反转.........

上图是有6个物品的例子，编号最小的一个是在第4个位置。因此，最开始把前面4个物品反转，第二小的物品在最后一个位置，所以下一个操作是把2-6的物品反转，第三步操作是把3-4的物品进行反转……

在数据中可能存在有相同的编号，如果有多个相同的编号，则按输入的原始次序操作。

inputFormat:
输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。

第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

outputFormat:
输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，（1 < = Pi < = N），Pi表示第i次操作前第i小的物品所在的位置。

 注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。


title: [BJWC2008] 秦腾与教学评估

description:
在秦腾进入北京大学学习的第一个学期，就不幸遇到了前所未有的教学评估。

在教学评估期间，同学们被要求八点起床，十一点回宿舍睡觉，不 准旷课，上课不准迟到，上课不准睡觉……甚至连著名的北大三角地也在教学评估期间被以影响校容的理由被拆除。这些“变态”规定令习惯了自由自在随性生活学习的北大同学叫苦不迭。

这一天又到了星期五，一大早就是秦腾最不喜欢的高等代数课。可是因为是教学评估时期，不能迟到，于是他在八点五分的 时候挣扎着爬出了宿舍，希望能赶快混进在八点钟已经上课了的教室。

可是，刚一出宿舍楼门他就傻眼了: 从宿舍到教学楼的路上已经站满了教学评估团的成员。他们的目的就是抓住像他这样迟到的学生，扣除学校的分数。

秦腾当然不能让评估团得逞。他经过观察发现，整个评估团分成了N个小组，每个小组的成员都分布在从宿舍楼到教学楼的路上的某一段，并且同一小组的成员间的距离是相等的。于是，我们可以用三个整数S,
 E, D来描述评估团的小组: 既该小组的成员在从宿舍到教学楼的路上的:S, S + D, S + 2D, …, S + KD (K ∈ Z, S + KD ≤ E, S + (K + 1)D > E)位置。

观 察到了教学评估团的这一特点，又经过了认真的思考，秦腾想出了对策: 如果在路上的某一位置有奇数个教学评估团成员，他就可以运用调虎离山，声东击西，隔山打牛，暗度陈仓……等方法，以这一地点为突破口到达教学楼。

但是由于 教学评估团的成员的十分狡猾，成员位置安排的设计极其精妙，导致在整条路上几乎没有这样的位置出现。即使由于安排不慎重出现了这样的位置，最多也仅有一个。

现在秦腾观察出了所有小组的安排，但是由于整个教学评估团的人数太多，他实在看不出这样的位置是否存在。

现在，你的任务是写一个程序，帮助他做出判断。

inputFormat:
输入文件的第一行为一个整数T。

接下来输入T组相互独立的测试数据。

每组测试数据的第一行包含一个整数，代表N接下来的N行，每行三个整数Si, Ei, Di, 代表第i个小组对应的三个参数。

outputFormat:
对于每个测试数据，如果题目中所求的位置不存在，既任意位置都有偶数个教学评估团的成员存在，在输出文件的中打印一行:`Poor QIN Teng:(` (不包含引号)否则打印两个整数Posi, Count，代表在唯一的位置Posi，有Count个教学评估团的成员。

根据题意，Count应为奇数。

hint:
教学评估团的总人数不大于10^8

Si ≤ Ei
1 ≤ T ≤ 5
N ≤ 200000
0 ≤ Si, Ei, Di ≤ 2^31 – 1

输入文件的大小不大于2048KB


title: [ZJOI2009] 硬币游戏

description:
Orez很喜欢玩游戏，他最近发明了一款硬币游戏。他在桌子的边缘上划分出2*n个位置并按顺时针把它们标号为1，2，……，2n，然后把n个硬币放在标号为奇数的位置上。

接下来每次按如下操作：在任意两个硬币之间放上一个硬币，然后将原来的硬币拿走；所放硬币的正反面由它两边的两个硬币决定，若两个硬币均为正面朝上或反面朝上，则所放硬币为正面朝上，否则为反面朝上。 那么操作T次之后桌子边缘上硬币的情况会是怎样的呢？

inputFormat:
文件的第一行包含两个整数n和T。

 接下的一行包含n个整数，表示最开始桌面边缘的硬币摆放情况，第i个整数ai表示第i个硬币摆放在2*i-1个位置上，ai=1表示正面朝上，ai=2表示反面朝上。

outputFormat: 文件仅包含一行，为2n个整数，其中第i个整数bi桌面边缘的第i个位置上硬币的情况，bi=1表示正面朝上，bi=2表示反面朝上，bi=0表示没有硬币。


title: [JSOI2010] 缓存交换

background: 感谢@ACdreamer 贡献数据

description:
在计算机中，CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时，则需要从主存里把数据调入Cache。此时，如果Cache容量已满，则必须先从中删除一个。

例如，当前Cache容量为3，且已经有编号为10和20的主存单元。
此时，CPU访问编号为10的主存单元，Cache命中。

接着，CPU访问编号为21的主存单元，那么只需将该主存单元移入Cache中，造成一次缺失（Cache Miss）。

接着，CPU访问编号为31的主存单元，则必须从Cache中换出一块，才能将编号为31的主存单元移入Cache，假设我们移出了编号为10的主存单元。

接着，CPU再次访问编号为10的主存单元，则又引起了一次缺失。我们看到，如果在上一次删除时，删除其他的单元，则可以避免本次访问的缺失。

在现代计算机中，往往采用LRU(最近最少使用)的算法来进行Cache调度——可是，从上一个例子就能看出，这并不是最优的算法。
对于一个固定容量的空Cache和连续的若干主存访问请求，聪聪想知道如何在每次Cache缺失时换出正确的主存单元，以达到最少的Cache缺失次数。

inputFormat:
输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。

第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。

outputFormat: 输出一行，为Cache缺失次数的最小值。

hint: 在第4次缺失时将3号单元换出Cache。


title: [IOI2007] Miners 矿工配餐

description:
现有两个煤矿，每个煤矿都雇用一组矿工。采煤工作很辛苦，所以矿工们需要良好饮食。每当一辆食品车到达煤矿时，矿工们便会产出一定数量的煤。

有三种类型的食品车：肉车，鱼车和面包车。
矿工们喜欢变化的食谱。如果提供的食品能够不断变化，他们的产煤量将会增加。每当一个新的食品车到达煤矿时，矿工们就会比较这种新的食品和前两次（或者少于两次，如果前面运送食品的次数不足两次）的食品，并且：

- 如果这几次食品车都是同一类型的食品，则矿工们产出一个单位的煤。
- 如果这几次食品车中有两种不同类型的食品，则矿工们产出两个单位的煤。
- 如果这几次食品车中有三种不同类型的食品，则矿工们产出三个单位的煤。

预先已知食品车的类型及其被配送的顺序。通过确定哪车食品送到哪个煤矿可以影响产煤量。食品车不能被拆分，每个食品车必须被全部送到一个或另一个煤矿。两个煤矿也并不要求接收相同数量的食品车（事实上，也允许将所有食品车都送到一个煤矿）。

给出食品车的类型及其被配送的顺序，要求你写一个程序，确定哪个食品车应被送到煤矿 $1$，哪个食品车应被送到煤矿 $2$，以使得两个煤矿的产煤量的总和最大。

inputFormat:
输入的第一行包含一个整数 $N (1 ≤ N ≤ 100 000)$,  表示食品车的数目。

第二行包含一个由 $N$ 个字符组成的字符串，按照配送顺序依次表示食品车配送的食品的类型。每个字符是以下三个大写字母之一：`M`（表示肉类），`F`（表示鱼类）或 `B`（表示面包）。

outputFormat: 输出一个整数，表示最大的总产煤量。

hint:
在样例 $1$ 中，可以按照如下的顺序运送食品车：煤矿 $1$，煤矿 $1$，煤矿 $2$，煤矿 $2$，煤矿 $1$，煤矿 $2$，依次产生的产煤量为 $1, 2, 1, 2, 3$ 和 $3$ 个单位，一共是 $12$ 个单位。

还有其它运送方式也能产生上述最大总和的产煤量。


title: [九省联考 2018] 一双木棋 chess

description:
菲菲和牛牛在一块 $n$ 行 $m$ 列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。

棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。

落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。

棋盘的每个格子上，都写有两个非负整数，从上到下第 $i$ 行中从左到右第 $j$ 列的格子上的两个整数记作 $a_{i,j}$ 和 $b_{i,j}$。

在游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的 $a_{i,j}$ 之和，牛牛的得分是所有有白棋的格子上的 $b_{i,j}$ 的和。

菲菲和牛牛都希望，自己的得分减去对方的得分得到的结果最大。现在他们想知道，在给定的棋盘上，如果双方都采用最优策略且知道对方会采用最优策略，那么，最终的结果如何？

inputFormat:
第一行有两个整数，分别表示棋盘的行数 $n$ 和列数 $m$。
第 $2$ 到第 $(n + 1)$ 行，每行 $m$ 个整数，第 $(i + 1)$ 行的第 $j$ 个整数表示 $a_{i, j}$。
第 $(n + 2)$ 到第 $(2n + 1)$ 行，每行 $m$ 个整数，第 $(n + i + 1)$ 行的第 $j$ 个整数表示 $b_{i, j}$。

outputFormat: 输出一行一个整数，表示菲菲的得分减去牛牛的得分的结果。

hint:
### 样例 1 说明

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

棋盘如图所示，双方都采用最优策略时，棋局如下：

- 菲菲下在第 $1$ 行第 $1$ 列（这是第一步时唯一可以落子的格子）。
- 牛牛下在第 $1$ 行第 $2$ 列。
- 菲菲下在第 $2$ 行第 $1$ 列。
- 牛牛下在第 $1$ 行第 $3$ 列。
- 菲菲下在第 $2$ 行第 $2$ 列。
- 牛牛下在第 $2$ 行第 $3$ 列（这是这一步时唯一可以落子的格子）。
- 填满棋盘，游戏结束。

盘面如下：

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

菲菲的得分为 $2 + 9 + 1 = 12$，牛牛的得分为 $7 + 2 + 1 = 10$。

### 数据规模与约定

各测试点信息如下表。

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

- 对于编号为奇数的测试点，保证 $b_{i, j} = 0$。
- 对于全部的测试点，保证 $1 \leq n, m \leq 10$，$0 \leq a_{i, j}, b_{i, j} \leq 10^5$。


title: [AHOI2018初中组] 球球的排列

description:
小可可是一个有着特殊爱好的人。他特别喜欢收集各种各样的球球，至今已经收集了$n$ 个球球。

小可可又是一个有着特殊想法的人。他将他的所有球球从 1 到$n$ 编号，并每天都把球球排成一个全新的排列。

小可可又是一个有着特殊情怀的人。他将每个球球的特点用$a[i]$来表示（注意这里不同的球$a[i]$可能相同）。

小可可又是一个爱恨分明的人。他十分讨厌平方数，所以他规定：一个排列$p$，对于所有的$1 ≤ i < n$，$a[p_i]\times a[p_{i+1}]$ 不是一个平方数，这样的排列$p$ 才是合法的。

小可可一直坚持每天排一个全新的合法的排列。有一天，他心血来潮，想知道所有合法排列的个数。小可可十分强，他当然知道怎么算。不过，他想用这个题来考考身在考场的你。这个数可能太大了，所以你只需要告诉小可可合法排列个数对$10^9+7$ 取模的结果就可以了。

你能正确回答小可可的问题吗？如果能的话，他说不定会送个球球给你呢……

inputFormat:
输入有两行：

第一行一个正整数$n$，表示小可可拥有的球球个数。
第二行有$n$ 个整数，第$i$ 个整数$a[i]$表示编号为$i$ 的球球的特点。

outputFormat: 输出一行，包括一个正整数，表示合法排列个数对$10^9+7$（即1000000007）取模的结果。


title: [九省联考 2018] IIIDX

background:
Osu 听过没？那是 Konano 最喜欢的一款音乐游戏，而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在，他在世界知名游戏公司 KONMAI 内工作，离他的梦想也越来越近了。

这款音乐游戏内一般都包含了许多歌曲，歌曲越多，玩家越不易玩腻。同时，为了使玩家在游戏上~~氪更多的金钱~~花更多的时间，游戏一开始一般都不会将所有曲目公开，有些曲目你需要通关某首特定歌曲才会解锁，而且越晚解锁的曲目难度越高。

description:
这一天，Konano 接到了一个任务，他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有 $n$ 首曲目，每首曲目都会有一个难度 $d$，游戏内第 $i$ 首曲目会在玩家 Pass 第 $\left\lfloor \frac i k \right\rfloor$ 首曲目后解锁（$\left\lfloor x \right\rfloor$ 为下取整符号）若 $\left\lfloor \frac i k \right\rfloor = 0$，则说明这首曲目**无需解锁**。

举个例子：当 $k = 2$ 时，第 $1$ 首曲目是无需解锁的（$\left\lfloor \frac 12 \right\rfloor = 0$），第 $7$ 首曲目需要玩家 Pass 第 $\left\lfloor \frac 72 \right\rfloor = 3$ 首曲目才会被解锁。

Konano 的工作，便是安排这些曲目的顺序，使得每次解锁出的曲子的难度**不低于**作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个 $i$ 满足 $d_i \geq d_{\left\lfloor \frac ik \right\rfloor}$。

当然这难不倒曾经在信息学竞赛摸鱼许久的 Konano。那假如是你，你会怎么解决这份任务呢？

inputFormat:
第 $1$ 行 $1$ 个正整数 $n$ 和 $1$ 个小数 $k,n$ 表示曲目数量，$k$ 其含义如题所示。

第 $2$ 行 $n$ 个用空格隔开的正整数 $d$，表示这 $n$ 首曲目的难度。

outputFormat:
输出 $1$ 行 $n$ 个整数，按顺序输出安排完曲目顺序后第 $i$ 首曲目的难度。

若有多解，则输出 $d_1$ **最大**的；若仍有多解，则输出 $d_2$ **最大**的，以此类推。


title: [AHOI2018初中组] 分组

description:
小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：$[1, 2, 3, 4, 5]$ 是合法的分组方案，因为实力值连续；$[1, 2, 3, 5]$ 不是合法的分组方案，因为实力值不连续；$[0, 1, 1, 2]$ 同样不是合法的分组方案，因为出现了两个实力值为 $1$ 的选手。

如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

inputFormat:
输入有两行：

第一行一个正整数 $n$，表示队员数量。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。

outputFormat: 输出一行，包括一个正整数，表示人数最少的组的人数最大值。


title: [九省联考 2018] 秘密袭击 coat

background:
> We could have had it all. . . . . .
>
> 我们本该，拥有一切
>
> Counting on a tree. . . . . .
>
> 何至于此，数数树上

Counting on a Tree（CoaT）即是本题的英文名称。

description:
Access Globe 最近正在玩一款战略游戏。在游戏中，他操控的角色是一名 C 国士兵。他的任务就是服从指挥官的指令参加战斗，并在战斗中取胜。

C 国即将向 D 国发动一场秘密袭击。作战计划是这样的：选择 D 国的 $s$ 个城市，派出 C 国战绩最高的 $s$ 个士兵分别秘密潜入这些城市。每个城市都有一个危险程度 $d_i$。

C 国指挥官会派遣战绩最高的士兵潜入所选择的城市中危险程度最高的城市，派遣战绩第二高的士兵潜入所选择的城市中危险程度次高的城市，以此类推（即派遣战绩第 $i$ 高的士兵潜入所选择城市中危险程度第 $i$ 高的城市）。D 国有 $n$ 个城市，$n - 1$ 条双向道路连接着这些城市，使得这些城市两两之间都可以互相到达。为了任务执行顺利，C 国选出的 $s$ 个城市中，任意两个所选的城市，都可以不经过未被选择的城市互相到达。

Access Globe 操控的士兵的战绩是第 $k$ 高，他希望能估计出最终自己潜入的城市的危险程度。Access Globe 假设 C 国是以等概率选出任意满足条件的城市集合 $S$，他希望你帮他求出所有可能的城市集合中，Access Globe 操控的士兵潜入城市的危险程度之和。如果选择的城市不足 $k$ 个，那么Access Globe 不会被派出，这种情况下危险程度为 $0$。

当然，你并不想帮他解决这个问题，你也不打算告诉他这个值除以 $998\,244\,353$ 的余数，你只打算告诉他这个值除以 $64\,123$ 的余数。

inputFormat:
第 $1$ 行包含 $3$ 个整数 $n,k,W$，表示 D 国城市的个数，Access Globe 所操控士兵潜入的城市战绩排名以及 D 国的所有城市中最大的危险程度；

第 $2$ 行包含 $n$ 个 $1$ 到 $W$ 之间的整数 $d_1, d_2, \ldots, d_n$，表示每个城市的危险程度；

第 $3$ 行到第 $n + 1$ 行，每行两个整数 $x_i, y_i$，表示 D 国存在一条连接城市 $x_i$ 和城市 $y_i$ 的双向道路。

outputFormat: 输出一个整数，表示所有可行的城市集合中，Access Globe 操控的士兵潜入城市的危险程度之和除以 $64\,123$ 的余数。

hint:
D 国地图如下，其中危险程度为 $d$ 的城市的形状是 $d + 3$ 边形。

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

以下是所有符合条件且选择的城市不少于 $3$ 个的方案：

- 选择城市 $1,2,3$，Access Globe 的士兵潜入的城市危险程度为 $1$；
- 选择城市 $1,2,3,4$，Access Globe 的士兵潜入的城市危险程度为 $1$；
- 选择城市 $1,2,3,5$，Access Globe 的士兵潜入的城市危险程度为 $1$；
- 选择城市 $1,2,3,4,5$，Access Globe 的士兵潜入的城市危险程度为 $2$；
- 选择城市 $1,2,4$，Access Globe 的士兵潜入的城市危险程度为 $1$；
- 选择城市 $1,2,5$，Access Globe 的士兵潜入的城市危险程度为 $1$；
- 选择城市 $1,2,4,5$，Access Globe 的士兵潜入的城市危险程度为 $2$；
- 选择城市 $1,4,5$，Access Globe 的士兵潜入的城市危险程度为 $2$；
- 而在选择的城市少于 $3$ 时，Access Globe 的士兵潜入的城市危险程度均为 $0$。

所以你应该输出 $(1 + 1 + 1 + 2 + 1 + 1 + 2 + 2) \bmod 64\,123 = 11$。

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


title: [AHOI2018初中组] 根式化简

description:
小可可在学习“立方根”的知识时碰到这样的问题：

将下面根式化简为最简根式：

(1) $\sqrt[3]{125}$ (2) $\sqrt[3]{81}$ (3) $\sqrt[3]{52}$

这个问题对于小可可来说太简单了，他很快就算出了答案：

(1) $5$ (2) 3$\sqrt[3]{3}$ (3) $\sqrt[3]{52}$

小可可知道任意形如$\sqrt[3]{x}$ 的根式，化简后一定可以被写成形如$a\sqrt[3]{b}$的最简根式。他觉得这很有趣，就仿照出了不少题，但没一会儿就被密密麻麻的根式绕晕了，于是他向你求助：

给定 $n$ 个形如 $\sqrt[3]{x}$ 的根式，请你将它们化简为形如$a\sqrt[3]{b}$的最简形式，为了方便，你只需要输出其中的$a$ 即可。

如果你没有学过这部分数学知识，你可以认为题意是：给你$n$ 个正整数$x$，对于每一个$x$，你需要求出整数$a,b$ 使得$a^3 \times b = x$，输出最大的整数$a$ 即可。

inputFormat:
输入有两行：

第一行一个整数$n$，表示有$n$ 个形如$\sqrt[3]{x}$ 的根式；
第二行$n$ 个正整数，依次给出每个$x$。

outputFormat: 输出$n$ 行，每行一个正整数，第$i$ 行正整数表示你对输入中第$i$ 个$x$ 给出的答案。


title: [八省联考 2018] 劈配

background: 一年一度的综艺节目《中国新代码》又开始了。Zayid 从小就梦想成为一名程序员，他觉得这是一个展示自己的舞台，于是他毫不犹豫地报名了。

description:
轻车熟路的 Zayid 顺利地通过了海选，接下来的环节是导师盲选，这一阶段的规则是这样的：

总共 $n$ 名参赛选手（编号从 $1$ 至 $n$ ）每人写出一份代码并介绍自己的梦想。接着 由所有导师对这些选手进行排名。为了避免后续的麻烦，规定**不存在排名并列的情况**。

同时，每名选手都将独立地填写一份志愿表，来对总共 $m$ 位导师（编号从 $1$ 至 $m$ ）作出评价。志愿表上包含了共 $m$ 档志愿。对于每一档志愿，选手被允许填写最多 $C$ 位导师，每位导师最多被每位选手填写**一次**（**放弃某些导师也是被允许的**）。

在双方的工作都完成后，进行录取工作。每位导师都有自己战队的人数上限，这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。节目组对“前 $i$ 名的录取结果最优”作出如下定义：

- 前 $1$ 名的录取结果最优，**当且仅当**第 $1$ 名被其最高非空志愿录取（**特别地**，如果第 $1$ 名没有填写志愿表，那么该选手出局）。

- 前 $i$ 名的录取结果最优，当且仅当在前 $i - 1$ 名的录取结果最优的情况下，第 $i$ 名 被其理论可能的最高志愿录取（特别地，如果第 $i$ 名没有填写志愿表，或其所有志愿中的导师战队均已满员，那么该选手出局）。

如果一种方案满足“前 $n$ 名的录取结果最优”，那么我们可以简称这种方案是**最优的**。

举例而言，$2$ 位导师 $\rm T$ 老师、 $\rm F$ 老师的战队人数上限分别都是 $1$ 人；$2$ 位选手 Zayid 、DuckD 分列第 $1$ 、 $2$ 名。那么下面 $3$ 种志愿表及其对应的最优录取结果如表中所示：

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

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

可以证明，对于上面的志愿表，对应的方案都是唯一的最优录取结果。

每个人都有一个自己的理想值 $s_i$ ，表示第 $i$ 位同学希望自己被第 $s_i$ 或更高的志愿录取，如果没有，那么他就会非常沮丧。

现在，所有选手的志愿表和排名都已公示。巧合的是，每位选手的排名都恰好与它们的编号相同。

对于每一位选手，Zayid 都想知道下面两个问题的答案：

- 在最优的录取方案中，他会被第几志愿录取。

- 在其他选手相对排名不变的情况下，至少上升多少名才能使得他不沮丧。

作为《中国新代码》的实力派代码手，Zayid 当然轻松地解决了这个问题。不过他还是想请你再算一遍，来检验自己计算的正确性。

inputFormat:
每个测试点包含多组测试数据，第一行 $2$ 个用空格隔开的非负整数 $T,C$ ，分别表示数据组数、每档志愿最多允许填写的导师数目。

接下来依次描述每组数据，对于每组数据：

- 第 $1$ 行两个用空格隔开的正整数 $n,m$ 。

> $n,m$ 分别表示选手的数量、导师的数量。

- 第 $2$ 行 $m$ 个用空格隔开的正整数：其中第 $i$ 个整数为 $b_i$ 。

> $b_i$ 表示编号为 $i$ 的导师战队人数的上限。

第 $3$ 行至第 $n + 2$ 行，每行 $m$ 个用空格隔开的非负整数：其中第 $i + 2$ 行左起第 $j$ 个数为 $a_{i,j}$ 。

> $a_{i,j}$ 表示编号为 $i$ 的选手将编号为 $j$ 的导师编排在了第 $a_{i,j}$ 志愿。特别地，如果 $a_{i,j}= 0$ ，则表示该选手没有将该导师填入志愿表。

> 在这一部分，保证每行中不存在某一个正数出现超过 $C$ 次（ **$0$ 可能出现超过 $C$ 次**），同时保证所有  $a_{i,j} \leqslant m$ 。

- 第 $n + 3$ 行 $n$ 个用空格隔开的正整数，其中第 $i$ 个整数为 $s_i$ 。

> $s_i$ 表示编号为 $i$ 的选手的理想值。

> 在这一部分，保证 $s_i \leqslant m$ 。

outputFormat:
按顺序输出每组数据的答案。对于每组数据，输出 $2$ 行：

- 第 $1$ 行输出 $n$ 个用空格隔开的正整数，其中第 $i$ 个整数的意义为：

	在最优的录取方案中，编号为 $i$ 的选手会被该档志愿录取。

> **特别地，如果该选手出局，则这个数为 $m + 1$** 。

- 第 $2$ 行输出 $n$ 个用空格隔开的非负整数，其中第 $i$ 个整数的意义为：

	使编号为 $i$ 的选手不沮丧，最少需要让他上升的排名数。

> **特别地，如果该选手一定会沮丧，则这个数为 $i$ 。**

hint:
- 样例 $1$ 解释

三组数据分别与【题目描述】中的三个表格对应。

对于第 $1$ 组数据：由于选手 $1$ 没有填写第一志愿，所以他一定无法被第一志愿录取，也就一定会沮丧。选手 $2$ 按原排名就不沮丧，因此他不需要提升排名。

对于第 $2$ 组和第 $3$ 组数据： $1$ 号选手都不需要提升排名。而希望被第一志愿录取的 $2$ 号选手都必须升到第 $1$ 名才能如愿。

- 样例 $2$ 解释

$1$ 号选手的第一志愿只填写了 $2$ 号导师，因此 $1$ 号选手必定被 $2$ 号导师录取。

$2$ 号选手的第一志愿只填写了 $3$ 号导师，因此 $2$ 号选手必定被 $3$ 号导师录取。

由于 $2,3$ 号导师均满员，且 $3,4$ 号选手均填写了 $1$ 号导师，因此他们都会被 $1$ 号导师录取。

所以 $1,2$ 号选手均被第 $1$ 志愿录取，$3$ 号选手被第 $3$ 志愿录取， $4$ 号选手被第 $2$ 志愿录取。

由于他们都如愿以偿了，所以他们都不需要提升名次。

|测试点编号|$n \leqslant$|$m \leqslant$|$C$|其他约定|
|:----:|:---:|:----:|:----:|:----:|
|1| $10$|$1$|$=1$|无|
|2|$10$|$2$|$=2$|$s_i=m$|
|3|$10$|$3$|$=3$|无|
|4|$100$|$100$|$=1$|$b_i=1$|
|5|$100$|$100$|$=1$|无|
|6|$200$|$200$|$=1$|$b_i=1$|
|7|$200$|$200$|$=1$|无|
|8|$100$|$100$|$=10$|无|
|9|$200$|$200$|$=10$|$b_i=1$|
|10|$200$|$200$|$=10$|无|

- 对于所有测试点，保证 $ T \leqslant 5$ 。

- 对于所有测试点钟的所有数据，保证 $ m \leqslant n \leqslant 200, b_i \leqslant n$


title: [八省联考 2018] 林克卡特树

description:
小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做 LCT 的挑战，它的规则是这样子的：现在有一个 $N$ 个点的树，每条边有一个整数边权 $v_i$，若 $v_i \geq 0$，表示走这条边会获得 $v_i$ 的收益；若 $v_i \lt 0$ ，则表示走这条边需要支付 $-v_i$ 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的恰好 $K$ 条边，然后再连接 $K$ 条边权为 0 的边，得到一棵新的树。接着，他会选择树上的两个点 $p,q$，并沿着树上连接这两点的简单路径从 $p$ 走到 $q$，并为经过的每条边支付过路费/ 获取相应收益。

海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使 总收益 - 总过路费 最大化的话，就把传说中的大师之剑送给他。

小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的 总收益 - 总过路费 最大是多少。

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

接下来 $N - 1$ 行，每行包含三个整数 $x_i,y_i,v_i$，表示第 $i$ 条边连接图中的 $x_i, y_i$ 两点，它的边权为 $v_i$。

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

hint:
### 样例解释

一种可能的最优方案为：切掉 $(2, 4, -3)$ 这条边，连接 $(3, 4, 0)$ 这条边，选择 $(p, q) = (1, 5)$。

### 数据范围

- 对于 $10\%$ 的数据，$k = 0$；
- 对于另外 $10\%$ 的数据，$k = 1$；
- 对于另外 $15\%$ 的数据，$k = 2$；
- 对于另外 $25\%$ 的数据，$k \leq 100$；
- 对于其他数据，没有特殊约定。

对于全部的测试数据，保证 $1 \leq N \leq 3 \times 10^5$，$0 \leq K \leq 3 \times 10^5$，$K \lt N$，$1 \leq x_i,y_i \leq N$，$|v_i| \leq 10^6$。

### 提示

题目并不难。


title: [八省联考 2018] 制胡窜

description:
对于一个字符串 $s$，我们定义 $|s|$ 表示 $s$ 的长度。

接着，我们定义 $s_i$ 表示 $s$ 中第 $i$ 个字符，$s_{l,r}$ 表示由 $s$ 中从左往右数，第 $l$ 个字符到第 $r$ 个字符依次连接形成的字符串。特别的，如果 $l \gt r$，或者 $l \notin [1, |s|]$，或者 $r \notin [1, |s|]$，我们可以认为 $s_{l,r}$ 为空串。

给定一个长度为 $n$ 的仅由数字构成的字符串 $s$，现在有 $q$ 次询问，第 $k$ 次询问会给出 $s$ 的一个子串 $s_{l,r}$，请你求出有多少对 $(i, j)$，满足 $1 \leq i \lt j \leq n$，$i + 1 < j$，且 $s_{l,r}$ 出现在 $s_{1,i}$ 中或 $s_{i+1,j-1}$中或 $s_{j,n}$ 中。

inputFormat:
输入的第一行是两个整数，分别表示字符串长度 $n$ 和询问次数 $q$。

第二行有一个长度为 $n$ 的只包含数字字符的字符串，表示 $s$。

接下来 $q$ 行，每行两个正整数 $l$ 和 $r$，表示此次询问的子串是 $s_{l,r}$。

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


title: [SHOI2015] 聚变反应炉

description:
曾经发明了零件组装机的发明家 SHTSC 又公开了他的新发明：聚变反应炉——一种可以产生大量清洁能量的神秘装置。

众所周知，利用核聚变产生的能量有两个难点：一是控制核聚变反应的反应强度，二是使用较少的能量激发聚变反应。而 SHTSC 已经完美解决了第一个问题。一个聚变反应炉由若干个相连的聚变块组成，为了能够使得聚变反应可控，SHTSC 保证任意两个聚能块都可以通过相互之间的链接到达，并且没有一个聚能块可以不重复经过一个链接回到它自己。

但是第二个问题 SHTSC 还没有完全解决。在他设计的聚变反应炉当中，每个聚变块都需要一定的初始能量 $d_i$ 来进行激发，不过 SHTSC 不需要手动激发所有聚变块，这是因为一旦一个聚变块被激发，则会向与其直接相连的所有还未被激发的聚变块传送 $c_i$ 个单位的能量。这样后被触发的聚变块可以以更低的初始能量来激发，甚至可能不需要额外的外界能量就可自行激发，从而降低了总激发能量的消耗。现在给出了一个聚变反应炉，求至少要多少能量才能激发所有聚变块。

inputFormat:
第一行一个整数 $n$，表示共有 $n$ 个聚能块，由 $1$ 至 $n$ 编号。

第二行 $n$ 个整数，依次表示 $d_i$。

第三行 $n$ 个整数，依次表示 $c_i$。

以下 $n - 1$ 行每行两个整数 $u, v$，表示编号为 $u$ 和 $v$ 的聚能块是相连的。

outputFormat: 一行一个整数，表示至少需要多少个单位的能量才能激发所有聚变块。


title: [COCI2009 Final Exam#2] Dvapravca

description:
给定平面上的$N$个点$,$其中有一些是红的$,$其他是蓝的

现在让你找一对平行线$,$在满足在平行线之间没有蓝点$,$并且平行线不经过任何一个点的情况下$,$使得被夹在平行线之间的红色点个数最多

给出的点没有三点共线的情况$,$平行线可以不平行坐标轴

inputFormat:
第一行一个整数$N$表示总点数

接下来$N$行每行两个整数和一个字符$R$或者$B$表示点的坐标和颜色

outputFormat: 一个整数表示最多红点数量


title: [USACO22DEC] Reverse Engineering B

description:
Elsie 有一个程序，接受一个 $N(1 \le N \le 100)$ 个变量的数组 $b[0], \cdots ,b[N−1]$ 作为输入，其中每个变量等于 $0$ 或 $1$，并且返回对输入数组应用一系列 `if / else if / else` 语句的结果。每个语句检查至多一个输入变量的值，并返回 $0$ 或 $1$。这类程序的一个例子是：

```cpp
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
```

例如，如果上方程序的输入是 "10"（即 $b[0]=1$ 及 $b[1]=0$），那么输出应当为 $1$。

Elsie 告诉了 Bessie 对于 $M(1 \le M \le 100)$ 个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能说了谎；可能不存在上述形式的程序行为与 Elsie 所说的均一致。

对于 $T(1 \le T \le 10)$ 个子测试用例中的每一个，判断 Elsie 是否一定在说谎。

inputFormat:
输入的第一行包含 $T$，为子测试用例的数量。

每一个子测试用例的第一行包含两个整数 $N$ 和 $M$，以下 $M$ 行，每行包含一个由 $N$ 个 $0$ 或 $1$ 组成的字符串，表示一个输入（即 $b[0] \cdots b[N−1]$ 的值），以及另一个字符（$0$ 或 $1$）表示输出。相邻的子测试用例之间用空行分隔。

outputFormat: 对于每一个子测试用例，输出一行，包含 $\texttt{OK}$ 或 $\texttt{LIE}$，分别表示 Elsie 可能没有说谎或是一定在说谎。

hint:
### 样例 1 解释

以下是第一个子测试用例的一个合法的程序：

```cpp
if (b[0] == 0) return 0;
else return 1;
```

以下是第一个子测试用例的另一个合法的程序：

```cpp
if (b[0] == 1) return 1;
else return 0;
```

以下是第二个子测试用例的一个合法的程序：

```cpp
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
```

显然，对于第三个子测试用例不存在对应的合法的程序，因为 Elsie 的程序一定始终对相同的输入产生相同的输出。

可以证明对于最后一个子测试用例不存在对应的合法的程序。

### 测试点性质

- 测试点 $2-3$ 满足 $N=2$。
- 测试点 $4-5$ 满足 $M=2$。
- 测试点 $6-12$ 没有额外限制。


title: [USACO23JAN] Leaders B

description:
Farmer John has $N$ cows $(2 \le N \le 10^5)$. Each cow has a breed that is either Guernsey or Holstein. As is often the case, the cows are standing in a line, numbered $1 \cdots N$ in this order.

Over the course of the day, each cow writes down a list of cows. Specifically, cow $i$
's list contains the range of cows starting with herself (cow $i$) up to and including cow $E_i(i \le E_i \le N)$.

FJ has recently discovered that each breed of cow has exactly one distinct leader. FJ does not know who the leaders are, but he knows that each leader must have a list that includes all the cows of their breed, or the other breed's leader (or both).

Help FJ count the number of pairs of cows that could be leaders. It is guaranteed that there is at least one possible pair.

inputFormat:
The first line contains $N$.

The second line contains a string of length $N$
, with the ith character denoting the breed of the $i$-th cow (G meaning Guernsey and H meaning Holstein). It is guaranteed that there is at least one Guernsey and one Holstein.

The third line contains $E_1 \cdots E_N$.

outputFormat: Output the number of possible pairs of leaders.

translation:
### 题面描述

FJ 有 $N$ 头奶牛，每一头奶牛的品种是根西岛 `G` 或荷斯坦 `H` 中的一种。

每一头奶牛都有一个名单，第 $i$ 头奶牛的名单上记录了从第 $i$ 头奶牛到第 $E_i$ 头奶牛的所有奶牛。

每一种奶牛都有且仅有一位“领导者”，对于某一头牛 $i$，如果它能成为“领导者”仅当它满足以下条件的**至少一个**：

- 其记录的名单上包含它的品种的所有奶牛。

- 其记录的名单上记录了另一品种奶牛的“领导者”。

请求出有多少对奶牛可能成为两种奶牛的领导者，保证存在至少一种。

### 数据范围
对于 $100\%$ 的数据：$1\leq N\leq 2\times 10^5,i\leq E_i\leq N$。

hint:
### Explanation for Sample 1

The only valid leader pair is $(1,2)$. Cow $1$'s list contains the other breed's leader (cow $2$). Cow $2$'s list contains all cows of her breed (Holstein).

No other pairs are valid. For example, $(2,4)$
is invalid since cow $4$'s list does not contain the other breed's leader, and it also does not contain all cows of her breed.

### Explanation for Sample 2

There are two valid leader pairs, $(1,3)$ and $(2,3)$.

### Scoring

 - Inputs $3-5$: $N \le 100$
 - Inputs $6-10$: $N \le 3000$
 - Inputs $11-17$: No additional constraints.


title: [HNOI/AHOI2018] 道路

description:
W 国的交通呈一棵树的形状。W 国一共有 $n-1$ 个城市和 $n$ 个乡村，其中城市从 $1$ 到 $n-1$ 编号，乡村从 $1$ 到 $n$ 编号，且 $1$ 号城市是首都。道路都是单向的，本题中我们只考虑从乡村通往首都的道路网络。

对于每一个城市，恰有一条公路和一条铁路通向这座城市。对于城市 $i$， 通向该城市的道路（公路或铁路）的起点，要么是一个乡村，要么是一个编号比 $i$ 大的城市。没有道路通向任何乡村。除了首都以外，从任何城市或乡村出发只有一条道路；首都没有往外的道路。从任何乡村出发，沿着唯一往外的道路走，总可以到达首都。

W 国的国王小 W 获得了一笔资金，他决定用这笔资金来改善交通。由于资金有限，小 W 只能翻修 $n-1$ 条道路。小 W 决定对每个城市翻修恰好一条通向它的道路，即从公路和铁路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利，于是根据人口调查的数据，小 W 对每个乡村制定了三个参数，编号为 $i$ 的乡村的三个参数是 $a_i$，$b_i$ 和 $c_i$。假设从编号为 $i$ 的乡村走到首都一共需要经过 $x$ 条未翻修的公路与 $y$ 条未翻修的铁路，那么该乡村的不便利值为：

$$c_i \cdot (a_i + x) \cdot (b_i + y)$$

在给定的翻修方案下，每个乡村的不便利值相加的和为该翻修方案的不便利值。 翻修 $n-1$ 条道路有很多方案，其中不便利值最小的方案称为最优翻修方案，小 W 自然希望找到最优翻修方案，请你帮助他求出这个最优翻修方案的不便利值。

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

接下来 $n - 1$ 行，每行描述一个城市。其中第 $i$ 行包含两个数 $s_i,t_i$。$s_i$ 表示通向第 $i$ 座城市的公路的起点，$t_i$ 表示通向第 $i$ 座城市的铁路的起点。如果$s_i>0$，那么存在一条从第 $s_i$ 座城市通往第$i$座城市的公路，否则存在一条从第 $-s_i$ 个乡村通往第 $i$ 座城市的公路；$t_i$ 类似地，如果 $t_i > 0$，那么存在一条从第 $t_i$ 座城市通往第 $i$ 座城市的铁路，否则存在一条从第 $-t_i$ 个乡村通往第 $i$ 座城市的铁路。

接下来 $n$ 行，每行描述一个乡村。其中第 $i$ 行包含三个数 $a_i,b_i,c_i$，其意义如题面所示。

outputFormat: 输出一行一个整数，表示最优翻修方案的不便利值。

hint:
【样例解释 1】

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

如图所示，我们分别用蓝色、黄色节点表示城市、乡村；用绿色、红色箭头分别表示 公路、铁路；用加粗箭头表示翻修的道路。

一种不便利值等于54的方法是：翻修通往城市2和城市5的铁路，以及通往其他城市的 公路。用→和⇒表示公路和铁路，用∗→和∗⇒表示翻修的公路和铁路，那么：

编号为1的乡村到达首都的路线为：-1 ∗→ 3 ⇒ 1，经过0条未翻修公路和1条未翻修铁 路，代价为3 × (1 + 0) × (2 + 1) = 9；
编号为2的乡村到达首都的路线为：-2 ⇒ 3 ⇒ 1，经过0条未翻修公路和2条未翻修铁 路，代价为2 × (1 + 0) × (3 + 2) = 10；
编号为3的乡村到达首都的路线为：-3 ∗→ 4 → 2 ∗→ 1，经过1条未翻修公路和0条未 翻修铁路，代价为3 × (2 + 1) × (1 + 0) = 9；
编号为4的乡村到达首都的路线为：-4 ⇒ 4 → 2 ∗→ 1，经过1条未翻修公路和1条未翻 修铁路，代价为1 × (2 + 1) × (3 + 1) = 12；
编号为5的乡村到达首都的路线为：-5 → 5 ∗⇒ 2 ∗→ 1，经过1条未翻修公路和0条未 翻修铁路，代价为2 × (3 + 1) × (1 + 0) = 8；
编号为6的乡村到达首都的路线为：-6 ∗⇒ 5 ∗⇒ 2 ∗→ 1，经过0条未翻修公路和0条未翻修铁路，代价为1 × (3 + 0) × (2 + 0) = 6；

总的不便利值为9 + 10 + 9 + 12 + 8 + 6 = 54。可以证明这是本数据的最优解。

【样例解释 2】

在这个样例中，显然应该翻修所有公路。

【数据范围】
一共20组数据，编号为1 ∼ 20。
对于编号$\le 4$的数据，$n \le 20$；
对于编号为5 ∼ 8的数据，$a_i,b_i,c_i \le 5$，$n \le 50$；
对于编号为9 ∼ 12的数据，$n \le 2000$；
对于所有的数据，$n \le 20000$，$1 \le a_i,b_i \le 60$，$1 \le c_i \le 10^9$，$s_i,t_i$是$[-n,-1] \cup (i,n - 1]$内的整数，任意乡村可以通过不超过40条道路到达首都。


title: [HNOI/AHOI2018] 排列

description:
给定 $n$ 个整数 $a_1, a_2, \dots, a_n, 0 \le a_i \le n$，以及 $n$ 个整数 $w_1, w_2, \dots, w_n$。称 $a_1, a_2, \dots, a_n$的 一个排列 $a_{p[1]}, a_{p[2]}, \dots, a_{p[n]}$为 $a_1, a_2, \dots, a_n$的一个合法排列，当且仅当该排列满足：对于任意 的 $k$ 和任意的 $j$，如果 $j \le k$，那么 $a_{p[j]}$不等于 $p[k]$。（换句话说就是：对于任意的 $k$ 和任意的 $j$，如果 $p[k]$等于 $a_{p[j]}$，那么 $k<j$。）定义这个合法排列的权值为 $w_{p[1]} + 2w_{p[2]} + \dots + nw_{p[n]}$。

你 需要求出在所有合法排列中的最大权值。如果不存在合法排列，输出 $-1$ 。

样例解释中给出了合法排列和非法排列的实例。

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

接下来一行 $n$ 个整数，表示$a_1, a_2, \dots, a_n$ 。 接下来一行 $n$ 个整数，表示 $w_1, w_2, \dots, w_n$ 。

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


title: [SHOI2004] 最小生成树

description:
给定一个筒单图 $G=\langle V.E.W\rangle$，$V$ 为顶点集合，$E$ 为边的集合（无重边，即任意两个顶点之间至多只有一条边)，$W$ 为定义在 $E$ 上的权函数（值为整数)。给出其上的一棵生成树 $T$，现在要求用最小的代价修改 $W$，使得 $T$ 是 $G$ 上的一棵最小生成树（一个图可以有多棵最小生成树，只要 $T$ 的边权和最小即可)。对于任意一条边 $e \in E$ 修改方法为：

- 增加 $e$ 的权值，即令 $W'(e)=W(e)+\Delta(e)$，则修改该边的代价为 $\Delta(e)$
- 减小 $e$ 的权值，即令 $W'(e)=W(e)-\Delta(e)$，则修改该边的代价为 $\Delta(e)$
- 不改变 $e$ 的权，即 $W'(e)=W(e)$，修改代价为 $\Delta(e)=0$。

请注意：修改后的权函数 $W'$ 的值域也为整数。

总的修改代价记为 $S=\sum\limits_{e \in E} \Delta(e)$。

inputFormat:
第一行为 $N,M$，其中 $N$ 表示顶点的数目，$M$ 表示边的数目。顶点的编号为 $1,2,3,\cdots,N-1,N$。

接下来的 $M$ 行，每行三个整数 $U_i,V_i,W_i$，表示顶点 $U_i$ 与 $V_i$ 之间有一条边，其权值为 $W_i$。

所有的边在输入中会且仅会出现一次。再接着 $N-1$ 行，每行两个整数 $X_i,Y_i$，表示顶点 $X_i$ 与 $Y_i$ 之间的边是 $T$ 的一条边。

outputFormat: 输出最小的 $S$。


title: [BJWC2010] 取数游戏

description:
小 C 刚学了辗转相除法，正不亦乐乎，这小 P 又出来捣乱，给小 C 留了个 难题。 给 $N$ 个数，用 $a_1,a_2, \cdots ,a_n$来表示。现在小 P 让小 C 依次取数，第一个数可以 随意取。假使目前取得 $a_j$，下一个数取$a_k(k>j)$，则$a_k$必须满足$\mathrm{gcd}(a_j,a_k)≥L$。

到底要取多少个数呢？自然是越多越好！ 不用多说，这不仅是给小 C 的难题，也是给你的难题。

inputFormat: 第一行包含两个数$N$ 和 $L$。 接下来一行，有 $N$ 个数用空格隔开，依次是 $a_1,a_2,\cdots ,a_n$。

outputFormat: 仅包含一行一个数，表示按上述取法，最多可以取的数的个数。


title: [COCI2006-2007#2] R2

description: The number S is called the mean of two numbers R1 and R2 if S is equal to (R1+R2)/2. Mirko's birthday present for Slavko was two integers R1 and R2. Slavko promptly calculated their mean which also happened to be an integer but then lost R2! Help Slavko restore R2.

inputFormat: The first and only line of input contains two integers R1 and S, both between -1000 and 1000.

outputFormat: Output R2 on a single line.


title: [COCI2006-2007#2] ABC

description:
You will be given three integers A, B and C. The numbers will not be given in that exact order, but we do know that A is less than B and B less than C.
In order to make for a more pleasant viewing, we want to rearrange them in the given order.

inputFormat:
The first line contains three positive integers A, B and C, not necessarily in that order. All three numbers will be less than or equal to 100.
The second line contains three uppercase letters 'A', 'B' and 'C' (with no spaces between them) representing the desired order.

outputFormat: Output the A, B and C in the desired order on a single line, separated by single spaces.

translation:
**【题目描述】**

三个整数分别为 $A,B,C$。这三个数字不会按照这样的顺序给你，但它们始终满足条件：$A < B < C$。为了看起来更加简洁明了，我们希望你可以按照给定的顺序重新排列它们。

**【输入格式】**

第一行包含三个正整数 $A,B,C$，不一定是按这个顺序。这三个数字都小于或等于 $100$。第二行包含三个大写字母 $A$、$B$ 和 $C$（它们之间**没有**空格）表示所需的顺序。

**【输出格式】**

在一行中输出 $A$，$B$ 和 $C$，用一个 ` `（空格）隔开。

感谢 @smartzzh 提供的翻译


title: [COCI2006-2007#2] KOLONE

description:
When moving, ants form rows so that each ant except the first is behind another ant. It is not widely known what happens when two rows of ants moving in opposite directions run into each other in a passage too narrow for both rows to pass through. One theory says that, in that situation, ants will jump over each other.
From the moment the rows meet, each second every ant jumps over (or gets jumped over, as they agree upon) the ant in front of himself so that the two ants swap places, but only if the other ant is moving in the opposite direction. Find the order of the ants after T seconds.

inputFormat:
The first line contains two integers N1 and N2, the numbers of ants in the first and second rows, respectively.
The next two rows contain the orders of ants in the first and second row (first to last). Each ant is uniquely determined by an uppercase letter of the English alphabet (this letter is unique between both rows).
The last line of input contains the integer T (0 ≤ T ≤ 50).

outputFormat: Output the order of the ants after T seconds on a single line. Our viewpoint is such that the first row of ants comes from our left side and the other one from our right side.

translation:
当蚂蚁移动时，蚂蚁排成一行，每个蚂蚁除了第一个蚂蚁都在另一个蚂蚁后面。众所周知，当两排蚂蚁在相反的方向上移动时，在一条太窄的通道中，两排都不能通过。一种理论认为，在这种情况下，蚂蚁会跳过对方。每隔一段时间，每一个蚂蚁都会跳过（或跳过去，就像他们同意的一样）蚂蚁在自己前面，这样两个蚂蚁交换位置，但是只有当另一只蚂蚁朝相反的方向移动时。在T秒后找到蚂蚁的顺序。
输入格式:
第一行包含两个整数N1和N2，分别在第一行和第二行中的蚂蚁的数量。接下来的两行包含第一行和第二行中的蚂蚁顺序（第一到最后一行）。每一个蚂蚁都是由一个大写字母（英文字母）唯一决定的（这两个字母在两行之间是唯一的）。输入的最后一行包含整数T(T小于50）。
输出格式:
在一条线上输出T秒后蚂蚁的顺序。我们的观点是，第一排蚂蚁来自我们的左侧，另一个来自我们的右侧。

感谢@心之所爱 提供的翻译


title: [COCI2017-2018#1] Plahte

description:
Little Donald decided to wash all N of his white sheets one day. After washing them, he put them to dry on the ground in his backyard. Donald placed the sheets so that ** none of them touch on the tips or the sides and that none of their sides intersect**, but it is possible that he placed smaller sheets on top of bigger ones, or that a sheet is completely covering another sheet. After doing this, Donald went to bed.

Donald’s friend Kim somehow got the information that Donald is drying his sheets and
decided to mess with him. He found a paintball gun from his father in the attic. Along with the
gun, there were M paintball balls in different colours, but it is possible that there were more
balls having the same colour. As soon as Donald fell asleep, Kim walked into his backyard
and started shooting the sheets with his paintball gun. We all know that sheets bleed, so
when Kim shoots the topmost sheet, that sheet would bleed the color of the ball down to all
of the sheets beneath it. After Kim used all the balls, he happily left Donald’s backyard.

When Donald woke up and went to get his sheets, shock ensued. On most of Donald’s
sheets, there was a number of new colours. Since Donald is very interested in correct data,
and he’s in shock and not able to think, he is asking you to tell him the number of new
colours on each sheet.

We can represent Donald’s backyard as an infinite coordinate system, and the sheets as
rectangles parallel to the coordinate axes. Kim’s shots can be represented as points in that
system.

Please note: it is possible that Kim’s shot missed all the sheets, but coordinates of each shot
are unique.

inputFormat:
The first line of input contains the positive integers N (1 ≤ N ≤ 80 000), the number of sheets,
and M (1 ≤ M ≤ 80 000), the number of paintball balls.

The $i^{th}$ of the following N lines contains four numbers: the coordinates of the lower left corner $A_i$, $B_i$ (1 ≤ $A_i$, $B_i$ ≤ $10^9$) and the upper right corner $C_i$, $D_i$, (1 ≤ $C_i$, $D_i$ ≤ $10^9$) of the $i^{th}$ sheet.

The $j^{th}$ of the following M lines contains the coordinates where Kim’s $j^{th}$ shot landed $X_j$, $Y_j$ (1 ≤$X_j$, $Y_j$ ≤ $10^9$), and $K_j$(1 ≤ $K_j$ ≤ $10^9$), the colour label of the $j^{th}$ ball.

outputFormat: The $i^{th}$ of N lines must contain the number of new colours on the $i^{th}$ sheet.

translation:
小唐纳德决定一天洗完他的白色床单。洗完后，他把它们放在后院的地上晾干。唐纳德把床单放在上面，使它们之间角或边不会互相接触，边也不会相交，但他可能把较小的床单放在大的上面，或者一个完全覆盖另个。做完这件事后，唐纳德上床睡觉了。

唐纳德的朋友基姆不知怎么地得到了唐纳德正在烘干他的床单的消息，决定和他捣乱。他在阁楼上找到了他父亲的彩弹枪。除了枪之外，还有不同颜色的彩弹球，但有可能有很多的球是相同的颜色。唐纳德一睡着，基姆走进他的后院，开始用他的彩弹枪射击床单。我们都知道床单会渗水，所以当基姆射出最上面的那张床单时，那张床单会把球的颜色渗到下面的所有床单上。基姆用了所有的球后，他愉快地离开了唐纳德的后院。

当唐纳德醒过来去拿床单时，非常震惊。在唐纳德的大部分床单上都有一些新的颜色。由于唐纳德对正确的数据很感兴趣，他太震惊了，以至于无法思考，他要求你告诉他每张床单上的新颜色的数量。

我们可以把唐纳德的后院表示成一个无限坐标系，而这些床单是平行于坐标轴的矩形。基姆的彩弹可以表示为该系统中的点。

请注意：基姆的彩弹可能没有打到任何一张床单，但是每一个彩弹的坐标都是独一无二的。

输入的第一行包含正整数床单的数量n（1≤n≤80000）和彩弹球数m（1≤m≤80000）。

接下来的n行中的每一行包含四个数字：表示左下角的坐标Ai,Bi(1≤Ai,Bi≤1000000000)和右上角的坐标Ci,Di(1 ≤Ci,Di≤1000000000)。

接下来的M行中的每一行包含三个数字，包含基姆投篮的坐标Xj,Yj(1≤Xj,Yj≤1000000000)，第j个球的颜色Kj(1≤Kj≤1000000000)。

共n行，每一行必须包含在第i张床单上的新颜色的数量。


title: [COCI2006-2007#2] STOL

description:
Mirko has bought an apartment and wants to invite to dinner as many people as possible to celebrate with him. For this he needs a large rectangular wooden table for which he will sit down with his guests. The number of people a table can accommodate is equal to its perimeter (the sum of the lengths of all four sides). Mirko wants to buy a table such that it fits in his apartment and that as many people as possible can sit down with him for dinner. The table must be placed so that its edges are parallel to the edges of the apartment.
Given the layout of the apartment, find the number of people Mirko can invite to dinner.

inputFormat:
The first line contains two integers R and C (1 ≤ R, S ≤ 400), the dimensions of the apartment.
Each of the following R rows contains exactly S characters (without spaces), whether a square is free ('.') or blocked ('X').
Mirko can put his table only in free squares.

outputFormat: Output the number of guests Mirko can invite to dinner after he buys his table on a single line.

translation:
## 题目描述
米尔科买了一套别墅，他想要邀请尽量多的人和他一起庆祝。他需要一张大的木质矩形桌子来让他和他的嘉宾坐下。每张桌子可容纳的人数等于它的周长（四边长度的总和）。米尔科想要买一张即可在他的公寓里放下，也可以坐下尽量多的人和他一起享用晚餐的桌子。桌子必须放置成四条边都与公寓的墙平行的样子。题目给出公寓内部的布局，请问米尔科最多可以邀请多少人吃晚餐。
## 输入输出格式
### 输入格式：
第一行包含两个整数R和S（1<=R,S<=400),代表公寓的尺寸（R为宽，S为长），以下的R行中每一行都包含了S个准确的字符（没有空格），代表这个正方形区域是没有东西的('.') ，还是有东西的('X')，米尔科只等把桌子发在没有东西的正方形区域里。
### 输出格式
输出米尔科在放下他的桌子后能够邀请来吃晚餐的人数

感谢@marcoolmap 提供的翻译


title: [COCI2006-2007#2] STRAZA

description:
Near a military base there is a system of trenches, modeled as line segments on a plane. During nighttime, when most soldiers are fast asleep, three guards stand watch of the trenches. Two guards can see each other if there is a trench (or a row of trenches) along the entire straight line segment between them and there is no third guard on that line segment.
For security reasons, the guards must be placed so that each guard sees the other two. How many ways can they be placed?

inputFormat:
The first line contains the integer N (1 ≤ N ≤ 20), the number of trenches. Each of the next N lines contains the description of one trench: four positive integers X1, Y1, X2, Y2 (all less than or equal to 1000), where X1 and Y1 are coordinates of one end, while X2 and Y2 are coordinates of the other end of the trench.
Trenches in the input may overlap and share endpoints.

outputFormat: Output the number of ways the guards can be placed on a single line.

translation:
题目描述：

在军事基地附近有一个战壕场，其中的战壕以平面上的线段为模型。在夜间，当大多数士兵熟睡的时候，三个警卫站在战壕旁边。如果在它们之间的整个直线段上有一条战壕（或一排战壕），且该直线段上没有第三警卫，那么两个警卫可以看到彼此。出于安全原因，必须安排警卫，以便每名警卫看到另外两名警卫。它们有多少种被安排的方式？

输入格式：

第一行包含整数n（1≤n≤20），战壕的数目。接下来的n行中的每一行都包含一个战壕的描述：四个正整数X1,Y1,X2,Y2（都小于或等于1000），其中X1和Y1是一端的坐标，而X2和Y2是战壕另一端的坐标。输入中的战壕可能重叠并共享端点。

输出格式：

在这一行中，有多少种安排警卫的方式。


title: [COCI2017-2018#1] Cezar

description:
Little Caesar likes card games. Everytime he comes to Zagreb, he plays blackjack, the famous card game, with his friends.

In this game, the player draws cards while the sum of the cards in his hand is less than or equal to 21 or until he says “DOSTA” (Croatian for “STOP”).

At the beginning of the game, there are 52 cards in the deck, thirteen ranks of each of the four suits. The card ranks are two, three, …, ten, Jack, Queen, King and Ace. The card values are the following: the cards with numbers on them are worth that number (e.g., “nine” is 9), the cards with pictures (Jack, Queen, and King) are worth 10, whereas the Ace is worth 11.

Caesar has found himself in an interesting situation. During the game, he already drew N cards whose sum is less than or equal to 21 and is now having second thoughts about drawing one more card or not. Let’s assume X is the difference from the sum of the cards so
far to 21. Everybody knows that you don’t draw a card if the number of the remaining cards in the deck whose value is greater than X is greater than or equal to the number of the remaining cards in the deck whose value is less than or equal to X.

Since Caesar is having a difficult time calculating whether he needs to draw another card or not, he’s asking you to do it for him.

inputFormat:
The first line of input contains the positive integer N (1 ≤ N ≤ 52), the number of cards Caesar has drawn so far.

Each of the following N lines contains a single positive integer, the value of the $i^{th}$ card Caesar drew.

outputFormat: If Caesar should draw another card, output “VUCI” (Croatian for “DRAW”), otherwise output “DOSTA” (Croatian for “STOP”).

translation:
小凯撒喜欢玩纸牌游戏，每次他去萨格勒布（克罗地亚的首都 ——译者注）都会和他的朋友们玩 $21$ 点，这是一种很流行的纸牌游戏。

这个游戏的规则是，在纸牌点数之和小于 $21$ 点之前可以连续抓牌，如果决定不抓牌，则喊 `DOSTA`（克罗地亚语“停止”的意思）。

游戏开始时，桌面有 $52$ 张牌 —— $13$ 种不同牌面的牌，每种有 $4$ 个花色。牌面分别是 $2,3,\dots,\text J,\text Q,\text K,\text A$。它们的点数计算规则是：牌面上的数字就是点数（比如，$9$ 的点数就是 $9$），特殊地，$\text J,\text Q,\text K$ 都算 $10$ 点，$\text A$ 算 $11$ 点。

凯撒认为游戏的乐趣在于，当抓了 $N$ 张牌之后，如果点数之和小于或等于 $21$，他就要思考是否要再多抓一张。假设 $X$ 是已抓牌点数之和与 $21$ 之间相差的点数值，我们知道，如果桌面上的剩余牌中点数大于 $X$ 的纸牌数量比小于等于 $X$ 的纸牌数量要多，或两者一样多，那就不应该再抓牌了。

因为凯撒并不擅于计算是否需要抓牌，所以他请你帮他计算和决策。

**【输入格式】**

第一行输入一个正整数 $N$（$1 \le N \le 52$），表示凯撒已经抓牌的张数。

接下来 $N$ 行每行一个正整数，第 $i$ 个正整数是他抓的第 $i$ 张牌点数值。

**【输出格式】**

如果凯撒应该继续抓牌，输出 `VUCI`（克罗地亚语“抓牌”的意思），否则输出 `DOSTA`（克罗地亚语“停止”的意思）。

**【样例解释】**

第一个样例： 已经抓的 $6$ 张牌的总点数是 $15$，它与 $21$ 的差 $X$ 是 $6$。桌面上剩余牌中比 $6$ 大的牌有 $32$ 张（分别是 $4$ 张 $\text A$、$4$ 张 $\text K$、$4$ 张 $\text Q$、$4$ 张 $\text J$、$4$ 张 $10$、$4$ 张 $9$、$4$ 张 $8$、$4$ 张 $7$），而比 $6$ 小的牌有 $14$ 张（分别是 $1$ 张 $2$、$1$ 张 $3$、$4$ 张 $4$、$4$ 张 $5$、$4$ 张 $6$），所以决定不再抓牌，输出 `DOSTA`。

hint:
Clarification of the first test case:

The sum of the already drawn cards is 15, and the difference X to 21 is 6. The number of cards in the
deck with a value greater than 6 is 32 (4 Aces, 4 Kings, 4 Queens, 4 Jacks, 4 tens, 4 nines, 4 eights, and 4 sevens), whereas the number of cards in the deck with a value less than or equal to 6 is 14 (one two, one three, 4 fours, 4 fives, and 4 sixes).