title: [POI2009] SLO-Elephants

description:
A parade of all elephants is to commence soon at the Byteotian zoo.

The zoo employees have encouraged these enormous animals to form a single line,  as the manager wills it to be the initial figure of the parade.

Unfortunately, the manager himself came to the parade and did not quite like  what he saw - he had intended an entirely different order of the elephants.

Therefore he enforced his ordering, claiming the animals would seem most  majestic this way, and made the employees reorder the elephants accordingly.

As a pack of moving elephants can wreak havoc, the employees decided to have  them rearranged by swapping one pair at a time. Luckily the animals need not  stand next to each other in order to swap positions in the line. Making an elephant  move, however, is not as easy as it sounds. In fact, the effort one has to put  into it is proportional to the animal's mass. Hence, the effort involved in  swapping a pair of elephants of respective masses $m_1$ and $m_2$ can be  estimated by $m_1+m_2$. What is the minimum effort involved in rearranging  the elephants according to manager's will?

Write a programme that:

- reads from the standard input the masses of all elephants from the zoo,        along with their current and desired order in the line,
- determines a sequence of elephant swaps leading from the initial to the        desired order of animals in the line, such that this sequence minimises        the summary effort involved in all the swaps,
- prints out the summary effort on the standard output.

inputFormat:
The first line of the standard input contains a single integer $n$  ($1\le n\le 1{,}000{,}000$) denoting the number of elephants in the zoo.

We assume that the elephants are numbered from $1$ to $n$ to simplify things.

The second line holds $n$ integers $m_i$ ($100\le m_i\le 6{,}500$ dla $1\le i\le n$)  separated by single spaces and denoting the masses of respective elephants  (in kilogrammes).

The third line of input contains $n$ pairwise different integers $a_i$  ($1\le a_i\le n$) separated by single spaces and denoting the numbers of successive elephants in the initial ordering.

The fourth line holds $n$ pairwise different integers $b_i$ ($1 \le  b_i \le  n$) separated by single spaces and denoting the numbers of successive elephants in the ordering desired by the zoo manager. You may assume that the sequences $(a_i)$ and $(b_i)$ differ.

outputFormat: The first and only line of the standard output should contain a single integer  denoting the minimum summary effort involved in reordering the elephants  from the order represented by the sequence to the one represented by $(b_i)$.

translation:
对于一个  $1-N$ 的排列 $a$，每次你可以交换两个数 $a_x$ 与 $a_y$($x\neq y$)，代价为 $W_{a_x}+W_{a_y}$。若干次交换的代价为每次交换的代价之和。请问将 $a_i$ 变为 $b_i$ 所需的最小代价是多少。

对于 $100\%$ 的数据，$2\leq N\leq 1000000$，$100\leq w_i\leq 6500$，$1\leq a_i,b_i\leq n$。保证 $a_i$ 各不相等，$b_i$ 各不相等。


title: [POI2009] STR-Fire Brigade

type: P

description:
In the capital of Byteotia, Bytau, the layout of streets is highly regular. Every street leads either from north to south, or from east to west. Therefore every north-south street intersects every east-west street in exactly one spot. Furthermore, along every street its successive intersections are exactly 1 km apart.

Bytau is not only the capital, but also one of the oldest cities in Byteotia. No wonder that there are as many as  historic buildings, each at one of the intersections. The City Council cares for their protection very much, and is now concerned with the risk of fire. Hence they have decided to establish two main fire stations in the city. Each monument is going to be protected by the nearest station; by both, should both fire stations be equally close.

Housing is very dense in Bytau, so Euclidean distance is not the measure of choice. The distance between a monument and fire station should rather be defined as the length of the shortest path along the streets between them.

The City Council has prepared several projects of the stations' location. And you have been asked to determine, for each of them, the number of monuments protected by: the first station only, the second station only, and both stations, respectively.

inputFormat:
In the first line of the standard input there are four integers $n$, $m$, $z$ and $p$ ($1\le n,m\le 1{,}000{,}000{,}000$, $1\le z,p\le 100{,}000$)      separated by single spaces and denoting respectively: the number of streets leading from north to south, the number of streets leading from east to west,      the number of historic buildings in Bytau, and the number of projects proposed by the City Council.

The north-south streets are numbered from $1$ to $n$, west to east. The east-west streets are numbered from $1$ to $m$, north to south. The intersection of $x$-th north-south and $y$-th east-west street will be denoted by the coordinates $(x,y)$.

In each of the following  lines there are two integers $x_i$ and $y_i$ ($1 ≤ xi ≤ n$, $1 ≤ yi ≤ m$) separated by a single space and denoting the coordinates of the i-th monument. No pair of different monuments is located at the same intersection.

Each of the following $p$ lines contains one proposal of the City Council - four integers $x_{j,1}, y_{j,1}, x_{j,2}, y_{j,2}$ separated by single spaces, $1 ≤ x_{j,1},x_{j,2} ≤ n$, $1 ≤ y_{j,1},y_{j,2} ≤ m$, $(x_{j,1},y_{j,1})≠(x_{j,2},y_{j,2})$. The coordinates $(x_{j,1},y_{j,1})$ and $(x_{j,2},y_{j,2})$ describe the intersections at which the fire stations are to be located according to the $j$-th proposal $(1 ≤ j ≤ p)$.

outputFormat:
Your programme should print out exactly $p$ lines on the standard output.

There should be three integers in the $j$-th line, denoting:

the number of monuments protected by the first station of $j$-th proposal of the City Council only, the number of monuments protected by the second      station only and the number of monuments protected by both stations, respectively.

These numbers should be separated by single spaces.

translation: 平面上有 $z$ 个点，给你 $p$ 个形如 $p_1(x_1,y_1),p_2(x_2,y_2)$ 的询问，要你求出 $z$ 个点中离 $p_1$ 更近的点，离 $p_2$ 更近的点，与 $p_1$ 和 $p_2$ 的距离相等的点各有多少个。这里的距离指的是曼哈顿距离，即x坐标之差的绝对值加上y坐标之差的绝对值。


title: [POI2009] WYS-Isles in a Triangular Grid

description:
A triangular grid consists in equilateral triangles with side length 1  (see p. 3). A path in the triangular grid is an arbitrary finite  sequence of triangles (with side length 1) of the grid such that every two  successive ones share a side.

A shape formed by the points of any finite number of triangles is called an  isle if any two triangles of the grid contained in this shape are  connected by some path formed by the triangles contained in the shape.

![](https://szkopul.edu.pl/problemset/problem/x71UmM6wnV9BdT-ld0uFb33p/site/images/OI16/wyspy.gif)

The shapes in the figures 1.1, 1.2 and 1.3 are isles.

The shape in the figure 1.4 is not an isle.

The shapes in the figures 2.2, 2.3 and 2.5 are congruent.

We aim at obtaining a systematic description, for each ![](http://main.edu.pl/images/OI16/wys-en-tex.1.png), of all  non-congruent isles that can be formed by ![](http://main.edu.pl/images/OI16/wys-en-tex.2.png) triangles with side length 1,  and calculating how many such isles there are.

The boundary of every isle formed by at most ten triangles is a polygonal  chain consisting of unitary segments of the grid. It can be revolved  about, i.e.

it can be contoured without detaching pencil from the sheet, in such a way  that its every segment is followed once, and we come back to the initial  point. It may happen though that some point has to be crossed more than  once (see Figure 2.4).

Luckily, in case of isles formed by at most ten triangles the shape's  perimeter is connected (and can be thus contoured without detaching pencil  from the sheet), unlike the one in Figure 1.2.

While circling around the perimeter, after each unit segment we make a turn  of either of the following types:

a - 120 degrees left,         b - 60 degrees left,         c - 0 degrees (i.e. no turn, actually),         d - 60 degrees right,         e - 120 degrees right.

Each cycle around the isle can be described by a word consisting of letters  from the set ![](http://main.edu.pl/images/OI16/wys-en-tex.3.png),  where each letter tells which turn should be made after each successive unit  segment the perimeter consists of. The cycle description has as many letters  as there are such unit segments. This means we also describe the turn after  the last segment of the polygonal chain, even though it is not required to  uniquely determine the shape. This redundant letter is, however, very helpful  in transforming one description of a cycle around the shape to another one  that differs only in the initial point.

The words cdddcddd, dcdddcdd, cbbbcbbb describe  different cycles around the shape of the Figure 2.1.

The words cbeddcde, adcabcbb, abcbbadc describe  different cycles around the shape of the Figure 2.2.

The words acdabbcb i cddebced describe  different cycles around the shape of the Figure 2.3.

If the inside of the shape is constantly on right hand side during a cycle  around some shape, we call such cycle a clockwise cycle.

One can determine, for each isle, the set of all isles congruent with it and  these isles' clockwise cycles.

The code of an isle is such a word that:

it is a description of a clockwise cycle around the contour of some isle congruent with the latter,         it is the lexicographically smallest of all words satisfying the previous condition.

For the isle depicted in Figures 2.2 and 2.3, which are congruent, we take  into account all clockwise cycles around each of them:

beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd,  decbeddc, ecbeddcd, cbeddcde  and  bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced,  ddebcedc, debcedcd, ebcedcdd  so their common code is: bcedcdde, the lexicographically smallest of  all the words above.

The code of the isle depicted in Figure 2.4 is: aadecddcddde.

Write a programme that:

for a given code of an isle of size ![](http://main.edu.pl/images/OI16/wys-en-tex.4.png) generates the codes of all isles of size ![](http://main.edu.pl/images/OI16/wys-en-tex.5.png) that can be obtained from the latter by adding one triangle to it,         for a given integer ![](http://main.edu.pl/images/OI16/wys-en-tex.6.png) generates the codes of all isles of size ![](http://main.edu.pl/images/OI16/wys-en-tex.7.png).

inputFormat:
In the first line of the standard input an integer ![](http://main.edu.pl/images/OI16/wys-en-tex.8.png) (![](http://main.edu.pl/images/OI16/wys-en-tex.9.png)),  denoting the number of queries, is given.

Each of the following ![](http://main.edu.pl/images/OI16/wys-en-tex.10.png) lines contains a query of some type.

The query of type 1 consists of the letter K and a code of an isle  formed by at most ten triangles, separated by a single space.

The query of type 2 consists of the letter N and an integer ![](http://main.edu.pl/images/OI16/wys-en-tex.11.png)  (![](http://main.edu.pl/images/OI16/wys-en-tex.12.png)), separated by a single space.

outputFormat:
The answers to the queries should be printed out to the standard output.

For queries of type 1 the number of distinct codes of isles that can be  obtained by adding one triangle from isles congruent to the one described  by the given code.

In the following line all these codes, separated by single spaces, should be  printed in lexicographic order.

For queries of type 2 the number of distinct codes of isles formed by ![](http://main.edu.pl/images/OI16/wys-en-tex.13.png)  triangles should be printed.

In the following line all these codes should be printed in lexicographic  order.

translation:
三角形网格由侧长1的等边三角形组成（请参阅第3页）。三角形网格中的路径是三角形的任意有限序列（具有侧面长度1）的网格，使每两个连续的连续序列共享一个侧面。

如果任何有限数量的三角形的点形成的形状称为岛，则该形状中包含的两个三角形的形状与形状包含的三角形形成的某些路径连接。

![](https://szkopul.edu.pl/problemset/problem/x71UmM6wnV9BdT-ld0uFb33p/site/images/OI16/wyspy.gif)

图1.1、1.2和1.3中的形状是小岛。

图1.4中的形状不是小岛。

图2.2、2.3和2.5中的形状是一致的。

我们的目的是为每个非统一的小岛中的每个群岛获得一个系统的描述，该群岛可以由带有侧长1的三角形形成，并计算有多少此类小岛。

最多十个三角形形成的每个小岛的边界是由网格的单一段组成的多边形链。它可以旋转，即

它可以在不从纸上脱离铅笔的情况下进行轮廓，以使其每个部分都遵循一次，然后我们回到初始点。尽管必须将某个点越多一次，但可能会发生（见图2.4）。

幸运的是，与图1.2中的那个不同，如果最多是由十个三角形形成的小岛，则形状的周长是连接的（因此可以在不从纸上脱离铅笔的情况下轮廓）。

在周围盘旋时，每个单元段之后，我们进行以下两种类型的转弯：

A -120度左，B -60度左，C -0度（即实际上没有转弯），D -60度右，E -120度右侧。

岛周围的每个循环都可以通过一个由集合的字母组成的单词来描述，每个字母都告诉每个连续的单元段之后应进行哪个转弯。周期描述的字母与此类单元段一样多。这意味着我们还描述了多边形链最后一段之后的转弯，即使不需要唯一地确定形状。但是，这个冗余字母在将周围的一个周期的描述转换为仅在初始点上有所不同的一个周期的描述非常有帮助。

CDDDCDD，DCDDDCDD，CBBBCBBB一词描述了图2.1形状的不同周期。

cbeddcde，adcabcbb，abcbbadc词描述了图2.2形状的不同周期。

acdabbcb i cddebced词描述了图2.3形状的不同循环。

如果形状的内部在某个形状的周期中不断在右侧，我们将这种周期称为顺时针周期。

对于每个小岛，都可以确定与它一致的所有小岛的集合，这些小岛的顺时针循环。

小岛的代码是一个词：

这是对与后者一致的小岛轮廓周围顺时针周期的描述，它是满足先前情况的所有单词中最小的。

对于图2.2和2.3中描述的小岛，这是一致的，我们考虑了它们周围的所有顺时针周期：

beddcdec，eddcdecb，ddcdecbe，dcdecbed，cdecbedd，decbeddc，ecbeddcd，ceddcde和bcedcdde，cedcddeb，edcddebc，dcddebce，dcddebce上面的所有单词。

图2.4中描述的小岛的代码为：AADECDDCDDDE。

编写一个程序：

对于一个大小的给定代码，可以通过向其添加一个三角形来从后者获得所有大小的代码，对于给定的整数生成了所有大小岛的代码。

### 输出格式

查询的答案应将其打印到标准输出中。

对于类型1的查询，可以通过与给定代码描述的岛添加一个三角形来获得的不同小岛代码的数量。

在以下行中，应按词典顺序打印所有这些代码，分别为单个空间。

对于2型查询，应打印由三角形形成的群岛的不同代码的数量。

在以下行中，所有这些代码均应按词典形式打印。

samples:
5
acedccecced addebcecced adebebecced adecbedcced cceccecce
4
aedddde bdecdde bececde ccedcde


title: [POI2009] BAJ-The Walk of Bytie-boy

background: [English Edition](/paste/9lmt83m9)

description:
给出一张 $n$ 个点 $m$ 条边的有向图，每条边上有一个字母，并给出一个整数 $d$ 和一个序列 $s_1, s_2, \dots, s_d$。

你需要对每一个 $i(1\le i<n)$ 求出一条从 $s_i$ 到 $s_{i+1}$ 的最短路径满足这条路径上的边上的字母连起来后是回文的。

不保证每个点最多只在 $s$ 中出现一次。

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

之后 $m$ 行，每行两个整数 $x_i, y_i$ 与一个字母 $c_i$，表示有一条从 $x_i$ 到 $y_i$ 的边，这条边上的字母是 $c_i$。

之后一行一个整数 $d$。

之后一行 $d$ 个整数， 表示序列 $s$。

outputFormat:
输出共 $d-1$ 行，第 $i$ 行输出一条从 $s_i$ 到 $s_{i+1}$ 的满足条件的路径。

若不存在这样的路径，则输出 `-1`，否则输出这条路径上的所有字母。

如果有多条满足条件的路径，任意输出一条即可。

hint:
对于 $100\%$ 的数据，$2\le n\le 400$，$1\le m\le 6\times10^4$，$1\le x_i,y_i\le n$，$2\le d\le100$，$1\le s_i\le n$。

同时保证不会出现重边与自环。


title: [POI2009] KON-Ticket Inspector

description:
Byteasar works as a ticket inspector in a Byteotian National Railways (BNR)    express train that connects Byteburg with Bitwise.

The third stage of the BNR reform (The never ending saga of BNR reforms and the Bitwise hub was presented in the problems Railway from the third stage of XIV Polish OI and Station from the third stage of XV Polish OI. Their knowledge, however, is not required at all in order to solve this        problem.) has begun. In particular, the salaries system has already been changed.

For example, to encourage Byteasar and other ticket inspectors to efficient work, their salaries now depend on the number of tickets (passengers) they    inspect. Byteasar is able to control all the passengers on the train in the time between two successive stations, but he is not eager to waste his energy in doing so. Eventually he decided he would check the tickets exactly $k$ times per ride.

Before setting out, Byteasar is given a detailed summary from which he knows    exactly how many passengers will travel from each station to another. Based    on that he would like to choose the moments of control in such a way that    the number of passengers checked is maximal. Obviously, Byteasar is not    paid extra for checking someone multiple times - that would be pointless,    and would only disturb the passengers. Write a programme that will determine    for Byteasar when he should check the tickets in order to maximise his    revenue.

inputFormat:
In the first line of the standard input two positive integers $n$ and $k$ ($1 ≤ k < n ≤ 600$, $k ≤ 50$) are given. These are separated by a single space and denote, respectively, the number of stations en route and the number of controls Byteasar intends to make. The stations are numbered from $1$ to $n$ in the order of appearance on the route.

In the next $n-1$ lines the summary on passengers is given. The $(i+1)$-th line contains information on the passengers who enter the train on the station $i$ - it is a sequence of $n-i$ nonnegative integers $x_{i,i+1},x_{i,i+2},…,x_{i,n}$ separated by single spaces. The number $x_{i,j}$ (for $1 ≤ i < j ≤ n$) denotes the number of passengers who enter the train on station $i$ and leave it on station $j$. The total number of passengers (i.e. the sum of all $x_{i,j}$) does not exceed $2{,}000{,}000{,}000$.

outputFormat: Your programme should print out (in a single line) an increasing sequence of $k$ integers from the interval from $1$ to $n-1$ separated by single spaces to the standard output. These numbers should be the numbers of stations upon leaving which Byteasar should control the tickets.

translation:
有 $n$ 个车站，现在有一辆火车从 $1$ 到 $n$ 驶过，给出 $a_{i,j}$ 代表从 $i$ 站上车 $j$ 站下车的人的个数。列车行驶过程中你有 $K$ 次检票机会，所有当前在车上的人会被检票，问最多能检多少个不同的人的票。

### 输入格式

第一行正整数 $N,K$，$1≤K＜N≤600$，$K≤50$。接下来 $N-1$ 行，第 $i$ 行第 $j$ 个数描述第 $i$ 站上，到第 $i+j$ 站下的乘客个数。总乘客数 $≤2\times 10^9$。

### 输出格式

单调增的 $K$ 个整数，用空格隔开，表示经过哪些站以后查票。


title: [POI2009] ARC-Architects

description:
给定一个序列 $a_i$（$1\leq a_i\leq 10^9$）且 $1\leq i\le n$ 且 $n\leq
 1.5\times 10^7$，和一个整数 $k$（$k\leq n$ 且 $k\leq 10^6$），求出 $a$ 的一个长度为 $k$ 的子序列 $a_{b_i}$ 满足：

1. $1\leq b_1\leq b_2\leq \ldots\leq b_k$
2. 在满足 $1$ 的情况下 $a_{b_1}, a_{b_2},\ldots , a_{b_k}$ 字典序最大。

inputFormat: 第一行一个数 $k$，以下一行，为序列 $a_i$。以一个单独的 $0$ 结束。

outputFormat: $k$ 行，每行一个数，其中第 $i$ 行为 $a_{b_i}$。

hint:
本题原为交互题，为了正常评测，你需要[下载](http://oi.edu.pl/static/attachment/20110704/oi16-etap2-arc.zip)后解压，并把etap2/arc/prog里的carclib.c贴到程序之前。

### 评测方式

首先请按 `说明/提示` 中说的做

然后将 `#include "carclib.h"` 去掉

将第一次输入改为 `=inicjuj()` 形式，将之后的每一次输入改为 `=wczytaj()` 形式，将输出改为 `wypisz(jakoscProjektu)` 形式（`jakoscProjektu` 代表你输出的数）

最后切记不能开O2


title: [POI2009] LYZ-Ice Skates

description:
Byteasar runs a skate club. Its members meet on a regular basis and train    together, and they always use the club's ice-skates. The skate sizes are    (by convention) numbered from ![](http://main.edu.pl/images/OI16/lyz-en-tex.1.png) to ![](http://main.edu.pl/images/OI16/lyz-en-tex.2.png). Naturally, each club member has    some foot size, but that is not all to it! Skaters have skate size tolerance    factor ![](http://main.edu.pl/images/OI16/lyz-en-tex.3.png): a skater with foot size ![](http://main.edu.pl/images/OI16/lyz-en-tex.4.png) can wear skates with    sizes from ![](http://main.edu.pl/images/OI16/lyz-en-tex.5.png) up to ![](http://main.edu.pl/images/OI16/lyz-en-tex.6.png). It should be noted, though, that    no skater ever wears two skates of different size simultaneously.

To supply the club, Byteasar bought ![](http://main.edu.pl/images/OI16/lyz-en-tex.7.png) pairs of ice-skates of each size,    i.e. from ![](http://main.edu.pl/images/OI16/lyz-en-tex.8.png) to ![](http://main.edu.pl/images/OI16/lyz-en-tex.9.png). As time passes, some people join the club, just as    some established members leave it. Byteasar worries if he will have enough    skates of appropriate size for every member at each training.

We assume that initially the club has no members at all. Byteasar will give    you a sequence of ![](http://main.edu.pl/images/OI16/lyz-en-tex.10.png) events of the following form: ![](http://main.edu.pl/images/OI16/lyz-en-tex.11.png) (new) members with    foot size ![](http://main.edu.pl/images/OI16/lyz-en-tex.12.png) have joined/left the club. Right after each such event    Byteasar wants to know whether he has enough skates of appropriate size for    every club member. He asks you to write a programme that will check it for    him.

inputFormat: The first line of the standard input contains four integers ![](http://main.edu.pl/images/OI16/lyz-en-tex.13.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.14.png),      ![](http://main.edu.pl/images/OI16/lyz-en-tex.15.png) and ![](http://main.edu.pl/images/OI16/lyz-en-tex.16.png) (![](http://main.edu.pl/images/OI16/lyz-en-tex.17.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.18.png),      ![](http://main.edu.pl/images/OI16/lyz-en-tex.19.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.20.png)), separated by single spaces, that      denote, respectively: maximum skate size, number of events, number of      skate pairs of each size Byteasar initially bought, and the skate size      tolerance factor. The following ![](http://main.edu.pl/images/OI16/lyz-en-tex.21.png) lines contain the sequence of ![](http://main.edu.pl/images/OI16/lyz-en-tex.22.png)      events, one per line. The ![](http://main.edu.pl/images/OI16/lyz-en-tex.23.png)-th line (for ![](http://main.edu.pl…

outputFormat:
Your programme should print out ![](http://main.edu.pl/images/OI16/lyz-en-tex.35.png) lines to the standard output.

The ![](http://main.edu.pl/images/OI16/lyz-en-tex.36.png)-th line (for ![](http://main.edu.pl/images/OI16/lyz-en-tex.37.png)) should either contain the word      TAK (Polish for yes), or the word NIE (Polish for      no), depending on whether Byteasar has the skates of appropriate      size for every club member right after the ![](http://main.edu.pl/images/OI16/lyz-en-tex.38.png)-th event.

translation:
滑冰俱乐部初始有 $[1,n]$ 号码溜冰鞋各 $k$ 双，已知 $x$ 号脚的人可以穿 $[x,x+d]$ 号码的鞋子。

现在有 $m$ 次操作，每次两个数 $r,x$，表示来了 $x$ 个 $r$ 号脚的人，$x$ 为负则表示离开。在每次操作之后，你需要判断溜冰鞋是否足够。

### 输入格式：

第一行 $4$ 个整数 $n,m,k,d$。

接下来 $m$ 行，每行两个整数 $r_i,x_i$，代表一次操作。

### 输出格式：

$m$ 行，每行一个字符串，若此次操作后满足题意则输出 `TAK`，否则输出 `NIE`。

### 数据范围：

$n\le 2\times 10^5,m\le 5\times 10^5,k\le 10^9,1\le r_i\le n-d,-10^9\le x_i\le 10^9,0\le d<n$


title: [POI2009] WIE-Hexer

description:
Byteasar has become a hexer - a conqueror of monsters.

Currently he is to return to his hometown Byteburg. The way home, alas, leads through a land full of beasts. Fortunately the habitants, forced to fight the monsters for centuries, have mastered the art of blacksmithery - they are now capable of making special swords that are very efficient against the beasts.

The land Byteasar wanders through is quite vast: many towns lie there, and many roads connect them.

These roads do not cross outside the towns (mostly because some of them are underground passages).

Byteasar has gathered all practical information about the land (all hexers like to know these things).

He knows what kind of monsters he may come across each of the roads and how much time he needs to walk it down.

He also knows in which villages there are blacksmiths and against what kinds of monsters the swords that they make work.

Byteasar wants to get back to Byteburg as soon as possible.

As a hexer he is quite ashamed that he does not know the best route, and that he has no sword on him at the moment.

Help him find the shortest path to Byteburg such that whenever he could meet some king of monster, previously he would have a chance to get an appropriate sword to fight the beast.

You need not worry about the number or weight of the swords - every hexer is as strong as an ox, so he can carry (virtually) unlimited number of equipment, swords in particular.

inputFormat:
The first line of the standard input holds four integers: $n,m,p,k$ ($1\le n\le 200,0\le m\le 3000,1\le p\le 13,0\le k\le n$),separated by single spaces, that denote respectively:

the number of towns, the number of roads connecting them,the number of different kinds of monsters and the number of blacksmiths.

The towns are numbered from $1$ to $n$ in such a way that $n$ is Byteburg's number and $1$ is the number of the village which Byteasar starts in. The monster kinds are numbered from $1$ to $p$.

In the following $k$ lines the profiles of successive blacksmiths are given,one per line. The $(i+1)$-st line holds the integers $w_i,q_i,r_{i,1}<r_{i,2}<...<r_{i,q_i}$($1\le w_i\le n,1\le q_i\le p,1\le r_{i,j}\le p$),separated by single spaces, that denote respectively: the number of town in which the blacksmith lives, the number of different kinds of monsters against which his swords are efficient, and the kinds of monsters themselves (in increasing order). Note that a town may have more than one blacksmith.

Then $m$ lines with roads' descriptions follow.The $(k+i+1)$-th line holds the integers$v_i,w_i,t_i,s_i,u_{i,1}<u_{i,2}<...<u_{i,s_i}$($1\le v_i<w_i\le n,1\le t_i\le 500,0\le s_i\le p,1\le u_{i,j}\le p$)separated by single spaces, that denote respectively: the towns that the road connects, the time needed to walk down the road (same in both directions), the number of different kinds of monsters that may appear on that road, and finally the kinds of monsters themselves (in increasing order). No two roads connect the same pair of towns.

outputFormat:
Your programme is to print out one integer to the standard output -  the minimum summary time required to reach Byteburg.

Should reaching Byteburg be impossible, the number should be $-1$.

translation:
大陆上有 $n$ 个村庄，$m$ 条双向道路，$p$ 种怪物，$k$ 个铁匠，每个铁匠会居住在一个村庄里，你到了那个村庄后可以让他给你打造剑，每个铁匠打造的剑都可以对付一些特定种类的怪物。

每条道路上都可能出现一些特定种类的怪物，每条道路都有一个通过所需要的时间，现在要从 $1$ 走到 $n$，初始的时候你没有剑，要求在经过一条道路的时候，对于任意一种可能出现在这条道路上的的怪物，你都有已经有至少一把剑可以对付他，求从$1$ 走到 $n$ 的最短时间（打造剑不需要时间）


title: [POI2009] FIB-Words 2

background: 征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

description:
The following task is a significantly harder version of task Words from the third stage of 16th Polish OI. It wasn't used in the contest itself, but is an extension for those who solved "Words" and want more. :-)    Let ![](http://main.edu.pl/images/OI16/fib-en-tex.1.png) be a function acting on strings composed of the digits 0    and 1.

The function ![](http://main.edu.pl/images/OI16/fib-en-tex.2.png) transforms the string ![](http://main.edu.pl/images/OI16/fib-en-tex.3.png) by replacing (independently    and concurrently) every digit 0 with 1 and every digit    1 with the string ![](http://main.edu.pl/images/OI16/fib-en-tex.4.png).

For example ![](http://main.edu.pl/images/OI16/fib-en-tex.5.png), ![](http://main.edu.pl/images/OI16/fib-en-tex.6.png)    (i.e. ![](http://main.edu.pl/images/OI16/fib-en-tex.7.png) assigns an empty string to the empty string).

Note that ![](http://main.edu.pl/images/OI16/fib-en-tex.8.png) is an injection, or a one-to-one function.

By ![](http://main.edu.pl/images/OI16/fib-en-tex.9.png) we denote the function ![](http://main.edu.pl/images/OI16/fib-en-tex.10.png) composed with itself ![](http://main.edu.pl/images/OI16/fib-en-tex.11.png) times.

In particular, ![](http://main.edu.pl/images/OI16/fib-en-tex.12.png) is the identity function ![](http://main.edu.pl/images/OI16/fib-en-tex.13.png).

We are interested in the strings of the form ![](http://main.edu.pl/images/OI16/fib-en-tex.14.png)    for ![](http://main.edu.pl/images/OI16/fib-en-tex.15.png) This sequence begins with the following strings:

![](http://main.edu.pl/images/OI16/fib-en-tex.16.png), ![](http://main.edu.pl/images/OI16/fib-en-tex.17.png), ![](http://main.edu.pl/images/OI16/fib-en-tex.18.png), ![](http://main.edu.pl/images/OI16/fib-en-tex.19.png),    ![](http://main.edu.pl/images/OI16/fib-en-tex.20.png), ![](http://main.edu.pl/images/OI16/fib-en-tex.21.png).

We call the string ![](http://main.edu.pl/images/OI16/fib-en-tex.22.png) a substring of the string ![](http://main.edu.pl/images/OI16/fib-en-tex.23.png) if it occurs    in ![](http://main.edu.pl/images/OI16/fib-en-tex.24.png) as  a contiguous (i.e. one-block) subsequence.

A sequence of integers ![](http://main.edu.pl/images/OI16/fib-en-tex.25.png) is given.

Your task is to check whether a string of the form    ![](http://main.edu.pl/images/OI16/fib-en-tex.26.png)    is a substring of ![](http://main.edu.pl/images/OI16/fib-en-tex.27.png) for some ![](http://main.edu.pl/images/OI16/fib-en-tex.28.png), and if it is,    you shuold find minimal such ![](http://main.edu.pl/images/OI16/fib-en-tex.29.png).

inputFormat:
The first line of the standard input contains a single integer ![](http://main.edu.pl/images/OI16/fib-en-tex.30.png),      ![](http://main.edu.pl/images/OI16/fib-en-tex.31.png).

The second line of standard input holds ![](http://main.edu.pl/images/OI16/fib-en-tex.32.png) non-negative integers      ![](http://main.edu.pl/images/OI16/fib-en-tex.33.png)(![](http://main.edu.pl/images/OI16/fib-en-tex.34.png)), separated by single spaces.

outputFormat:
Your programme should print out ![](http://main.edu.pl/images/OI16/fib-en-tex.35.png) lines to the standard output,     one for each test unit.

Your programm should print to standard output minimal non-negative integer ![](http://main.edu.pl/images/OI16/fib-en-tex.36.png),     such that ![](http://main.edu.pl/images/OI16/fib-en-tex.37.png) is a substring of      ![](http://main.edu.pl/images/OI16/fib-en-tex.38.png), or NIE (no in Polish) if such ![](http://main.edu.pl/images/OI16/fib-en-tex.39.png) doesn't exist.

translation:
## 题目描述
下面的任务是第16届波兰语竞赛第三阶段的任务“单词”的一个明显的难度增强版本。它并没有在比赛中使用，但对于那些解决了“单词”的人来说，它是一个扩展 :) 。

函数  $h$ 作用于由数字  $0$ 和  $1$ 组成的字符串，其通过将每一个数字  $0$ 替换为  $1$，将每一个数字  $1$ 替换为字符串  $10$ 来独立且同时地变换字符串  $w$。

例如：

 $$h(``1001")=``101110"$$
 $$h(``\ ")=``\ "$$

其中例二即把空字符串赋值给空字符串。

注意， $h$ 是一个一对一的函数。

我们用  $h^k$ 表示函数  $h$ 使用  $k$ 次。

特别的， $h^0(w)=w$。

我们对  $k = 0, 1, 2, ...$ 的  $h^k(``0")$ 形式的字符串感兴趣，这个序列为:

 $$ ``0", ``1", ``10", ``101", ``10110", ``10110101", \ldots $$

如果字符串  $x$ 在  $y$ 中以一个连续的（即一个块）子串出现，我们就称  $x$ 为字符串  $y$ 的子串。给出整数  $k_1, k_2, k_3, ..., k_n $ 的序列。你的任务是检查对于一些  $m$ 来说， $h^{k_1}(``0") \cdot h^{k_2}(``0") \cdot \ldots \cdot h^{k_n}(``0") $ 形式的字符串是否是  $h^m(``0")$ 的子串，如果有，你应该找到最小的  $m$。

## 输入内容
输入的第一行包含一个整数  $n$， $1 \leq n \leq 1000000$。输入的第二行包含  $n$ 个非负整数  $k_1, k_2, k_3, ..., k_n $，用单个空格分隔。

## 输出内容
您的程序应该输出  $t$ 行，每个测试输出一行。你的程序应该输出的最小非负整数  $m$，使  $h^{k_1}(``0") \cdot h^{k_2}(``0") \cdot \ldots \cdot h^{k_n}(``0") $ 是  $h^m(``0")$ 的子串。如果不存在  $m$，则输出 `NIE`（波兰语中的 _no_ ）。

_Translated By in\_young\_ren_


title: [POI2009] SLW-Words

description:
Let ![](http://main.edu.pl/images/OI16/slw-en-tex.1.png) be a function acting on strings composed of the digits 0    and 1.

The function ![](http://main.edu.pl/images/OI16/slw-en-tex.2.png) transforms the string ![](http://main.edu.pl/images/OI16/slw-en-tex.3.png) by replacing (independently    and concurrently) every digit 0 with 1 and every digit    1 with the string ![](http://main.edu.pl/images/OI16/slw-en-tex.4.png).

For example ![](http://main.edu.pl/images/OI16/slw-en-tex.5.png), ![](http://main.edu.pl/images/OI16/slw-en-tex.6.png)    (i.e. ![](http://main.edu.pl/images/OI16/slw-en-tex.7.png) assigns an empty string to the empty string).

Note that ![](http://main.edu.pl/images/OI16/slw-en-tex.8.png) is an injection, or a one-to-one function.

By ![](http://main.edu.pl/images/OI16/slw-en-tex.9.png) we denote the function ![](http://main.edu.pl/images/OI16/slw-en-tex.10.png) composed with itself ![](http://main.edu.pl/images/OI16/slw-en-tex.11.png) times.

In particular, ![](http://main.edu.pl/images/OI16/slw-en-tex.12.png) is the identity function ![](http://main.edu.pl/images/OI16/slw-en-tex.13.png).

We are interested in the strings of the form ![](http://main.edu.pl/images/OI16/slw-en-tex.14.png)    for ![](http://main.edu.pl/images/OI16/slw-en-tex.15.png) This sequence begins with the following strings:

![](http://main.edu.pl/images/OI16/slw-en-tex.16.png), ![](http://main.edu.pl/images/OI16/slw-en-tex.17.png), ![](http://main.edu.pl/images/OI16/slw-en-tex.18.png), ![](http://main.edu.pl/images/OI16/slw-en-tex.19.png),    ![](http://main.edu.pl/images/OI16/slw-en-tex.20.png), ![](http://main.edu.pl/images/OI16/slw-en-tex.21.png).

We call the string ![](http://main.edu.pl/images/OI16/slw-en-tex.22.png) a substring of the string ![](http://main.edu.pl/images/OI16/slw-en-tex.23.png) if it occurs    in ![](http://main.edu.pl/images/OI16/slw-en-tex.24.png) as  a contiguous (i.e. one-block) subsequence.

A sequence of integers ![](http://main.edu.pl/images/OI16/slw-en-tex.25.png) is given.

Your task is to check whether a string of the form    ![](http://main.edu.pl/images/OI16/slw-en-tex.26.png)    is a substring of ![](http://main.edu.pl/images/OI16/slw-en-tex.27.png) for some ![](http://main.edu.pl/images/OI16/slw-en-tex.28.png).

inputFormat:
The first line of the standard input contains a single integer ![](http://main.edu.pl/images/OI16/slw-en-tex.29.png),      ![](http://main.edu.pl/images/OI16/slw-en-tex.30.png), denoting the number of test units.

The first line of each test unit's description contains one integer ![](http://main.edu.pl/images/OI16/slw-en-tex.31.png),      ![](http://main.edu.pl/images/OI16/slw-en-tex.32.png).

The second line of each description holds ![](http://main.edu.pl/images/OI16/slw-en-tex.33.png) non-negative integers      ![](http://main.edu.pl/images/OI16/slw-en-tex.34.png), separated by single spaces.

The sum of the numbers in the second line of any test unit description      does not exceed ![](http://main.edu.pl/images/OI16/slw-en-tex.35.png).

outputFormat:
Your programme should print out ![](http://main.edu.pl/images/OI16/slw-en-tex.36.png) lines to the standard output,     one for each test unit.

Each line corresponding to a test unit should contain one word:

TAK (yes in Polish - if      ![](http://main.edu.pl/images/OI16/slw-en-tex.37.png) is a substring of      ![](http://main.edu.pl/images/OI16/slw-en-tex.38.png) for some ![](http://main.edu.pl/images/OI16/slw-en-tex.39.png) in that test unit,      or NIE (no in Polish) otherwise.

translation:
## 题目描述

函数  $h$ 作用于由数字  $0$ 和  $1$ 组成的字符串，其通过将每一个数字  $0$ 替换为  $1$，将每一个数字  $1$ 替换为字符串  $10$ 来独立且同时地变换字符串  $w$。

例如：

 $$h(``1001")=``101110"$$
 $$h(``\ ")=``\ "$$

其中例二即把空字符串赋值给空字符串。

注意， $h$ 是一个一对一的函数。

我们用  $h^k$ 表示函数  $h$ 使用  $k$ 次。

特别的， $h^0(w)=w$。

我们对  $k = 0, 1, 2, ...$ 的  $h^k(``0")$ 形式的字符串感兴趣，这个序列为:

 $$ ``0", ``1", ``10", ``101", ``10110", ``10110101", \ldots $$

如果字符串  $x$ 在  $y$ 中以一个连续的（即一个块）子串出现，我们就称  $x$ 为字符串  $y$ 的子串。给出整数  $k_1, k_2, k_3, ..., k_n $ 的序列。你的任务是检查是否有  $m$ ，使 $h^{k_1}(``0") \cdot h^{k_2}(``0") \cdot \ldots \cdot h^{k_n}(``0") $ 形式的字符串是  $h^m(``0")$ 的子串。

## 输入内容
输入的第一行包含一个整数  $t$ 表示样例数，  $1 \leq t \leq 13$。每个样例输入两行，一行  $n$ ， $1 \leq n \leq 100000$ ，另一行为  $n$ 个非负整数  $k_1, k_2, k_3, ..., k_n $，用单个空格分隔。

## 输出内容
您的程序应该输出  $t$ 行，每个测试输出一行。如果存在  $m$ 使  $h^{k_1}(``0") \cdot h^{k_2}(``0") \cdot \ldots \cdot h^{k_n}(``0") $ 是  $h^m(``0")$ 的子串，就输出 `TAK`（波兰语中的 _yes_ ），如果不存在  $m$，则输出 `NIE`（波兰语中的 _no_ ）。

_Translated By in\_young\_ren_


title: [POI2009] TAB-Arrays

description:
Let us consider an array of size ![](http://main.edu.pl/images/OI16/tab-en-tex.1.png) filled with pairwise different integers.

The following operations are allowed on the array:

interchanging two rows,              interchanging two columns.

We call two arrays alike if one of them can be obtained from the other by a sequence of aforementioned operations.

Write a programme that for a given set of pairs of arrays tells which pairs are alike.

inputFormat:
The first line of the standard input contains one integer ![](http://main.edu.pl/images/OI16/tab-en-tex.2.png) (![](http://main.edu.pl/images/OI16/tab-en-tex.3.png))   denoting the number of pairs of arrays.

Then descriptions of successive array pairs follow in subsequent lines.

Each description starts with a line holding two integers ![](http://main.edu.pl/images/OI16/tab-en-tex.4.png) and ![](http://main.edu.pl/images/OI16/tab-en-tex.5.png) (![](http://main.edu.pl/images/OI16/tab-en-tex.6.png)), separated by a single space, that denote the common number of rows and columns of the arrays, respectively.

The ![](http://main.edu.pl/images/OI16/tab-en-tex.7.png) lines that follow describe the first array.

In the ![](http://main.edu.pl/images/OI16/tab-en-tex.8.png)-th of them there are ![](http://main.edu.pl/images/OI16/tab-en-tex.9.png) integers ![](http://main.edu.pl/images/OI16/tab-en-tex.10.png) (![](http://main.edu.pl/images/OI16/tab-en-tex.11.png)), separated by single spaces…

outputFormat:
Your programme should print out ![](http://main.edu.pl/images/OI16/tab-en-tex.19.png) lines to the standard output.

The ![](http://main.edu.pl/images/OI16/tab-en-tex.20.png)-th of these should hold one word: "TAK" (yes in Polish) if the  arrays of the ![](http://main.edu.pl/images/OI16/tab-en-tex.21.png)-th pair are alike, or "NIE" (no in Polish) otherwise.

translation: 给出两个 $n$ 行 $m$ 列的矩阵 ($n,m\leq 150$)，保证每个矩阵内元素互不相同且权值均在 $[-10^6,10^6]$ 之间，你需要报告能否把其中一个矩阵通过若干次交换两行或者交换两列的操作变成另外一个矩阵。


title: [POI2009] WSP-Island

description:
Byteasar is the king of Byteotia, an island in The Ocean of Happiness.

The island is a convex shape, and all the towns of Byteotia are located on the shore.

One of these towns is Byteburg, the famous capital of Byteotia.

Every pair of towns is connected by a road that goes along the line segment between the towns.

Some roads that connect different pairs of towns intersect - there is a crossroad at each such intersection.

Bitratio, Byteasar's rival to the throne, had hatched a sordid plot.

While Byteasar was travelling from the capital to an adjacent town, Bitratio's people seized Byteburg.

Now Byteasar has to return to Byteburg as soon as possible in order to restore his rule.

Unfortunately, some of the roads are controlled by Bitratio's guerrilla.

Byteasar cannot risk the use of such roads, he can however cross them at the crossroads.

Needless to say, he has to travel along the roads and hence turn only at the crossroads, for otherwise the journey would take far too long.

Byteasar's loyal servants have informed him which roads are safe.

Byteasar believes your loyalty, and thus entrusts you with a task to find the shortest safe route from the town he is currently in to Byteburg.

Byteotia岛屿是一个凸多边形。城市全都在海岸上。按顺时针编号1到n。任意两个城市之间都有一条笔直的道路相连。道路相交处可以自由穿行。有一些道路被游击队控制了，不能走，但是可以经过这条道路与未被控制的道路的交点。问从城市1到n的最短距离。

inputFormat:
In the first line of the standard input two integers ![](http://main.edu.pl/images/OI16/wsp-en-tex.1.png) and ![](http://main.edu.pl/images/OI16/wsp-en-tex.2.png) are given     (![](http://main.edu.pl/images/OI16/wsp-en-tex.3.png), ![](http://main.edu.pl/images/OI16/wsp-en-tex.4.png)),     separated by a single space,     that denote respectively: the number of towns and      the number of roads controlled by Bitratio's guerrilla.

Let us number the towns from ![](http://main.edu.pl/images/OI16/wsp-en-tex.5.png) to ![](http://main.edu.pl/images/OI16/wsp-en-tex.6.png) starting from Byteburg      and moving clockwise along the shore.

Bytesar is currently in the town no. ![](http://main.edu.pl/images/OI16/wsp-en-tex.7.png).

Each of the following ![](http://main.edu.pl/images/OI16/wsp-en-tex.8.png) lines holds a pair of integers ![](http://main.edu.pl/images/OI16/wsp-en-tex.9.png) and ![](http://main.edu.pl/images/OI16/wsp-en-tex.10.png)      (![](http://main.edu.pl/images/O…

outputFormat:
Your programme is to print out one floating point number     to the standard output:

the length of the shortest safe route leading from the town no. ![](http://main.edu.pl/images/OI16/wsp-en-tex.19.png)     to Byteburg.

The absolute difference between the number returned and the correct one  has to be at most ![](http://main.edu.pl/images/OI16/wsp-en-tex.20.png).

translation:
### 题目大意

Byteotia岛屿是一个凸多边形,城市全都在海岸上,按顺时针编号  $1$ 到  $n$ 。

任意两个城市之间都有一条笔直的道路相连。道路相交处可以自由穿行。

有一些道路被游击队控制了，不能走，但是可以经过这条道路与未被控制的道路的交点。

问从城市  $1$ 到  $n$ 的最短距离。

### 输入格式

第一行两个正整数  $n$ 和  $m$ 表示城市数和被控制的道路数。

接下来  $n$ 行，每行两个整数  $x,y$ 表示每个城市的坐标。

接下来  $m$ 行，每行两个整数  $u,v$ 。表示城市  $u$ 和  $v$ 之间的道路不能走，数据保证有解。

### 输入格式

输出一个实数，表示从  $1$ 到  $n$ 最短道路距离，误差在  $10^{-5}$ 以内均算正确。

### 数据范围和提示

 $3 \le n \le 10^5,1 \le m \le 10^6,|x|,|y| \le 10^6$

by Rainy7 & Piwry

hint: spj-


title: [POI2009] KOD-The Code

description:
The Byteotian Institute of Telecommunication (BIT) sets standards for data transmission in telecommunication networks all over Byteotia.

Byteasar, one of the engineers employed at BIT, works on prefix codes - a certain way of representing characters.

For each and every character of the Byteotian alphabet there is a corresponding sequence of bits, called the code word of that character.

The code words of all characters have the following properties:

None of the code words is a prefix (i.e. a leading       fragment) of another code word.

For example, if 010010 is the code word of the letter   A, then neither the bit sequence 0,   01, 010,  0100 nor 01001   is a code word of another letter.

Likewise, 0100100, 0100101 and longer   sequences starting with 010010 are not code words.

If a given bit sequence ![](http://main.edu.pl/images/OI16/kod-en-tex.1.png) is a prefix of another code word,       but not the complete code, then each of the bit sequences       ![](http://main.edu.pl/images/OI16/kod-en-tex.2.png) and ![](http://main.edu.pl/images/OI16/kod-en-tex.3.png) (that is, ![](http://main.edu.pl/images/OI16/kod-en-tex.4.png) with zero or one       appended at the end) is a prefix of some code word, or the       complete code word.

For example, if 0100 is the prefix of the code word of the       letter A, then 01000 and 01001 each       is a prefix of some code word, or a complete code word.

Let us consider the following exemplary prefix code for the alphabet consisting of the characters    A, B, C, D and E:

charactercode word    A00    B10    C11    D010    E011         Encoding a sequence of characters with a prefix code consists in concatenating the code words of its successive characters.

For example, the encoding of the sequence BACAEBABAE is 1000110001110001000011.

Byteasar noticed that if some leading bits are lost, the sequence may be decoded wrong, or it may even be not decoded at all.

For example, if five initial bits of the sequence given above are removed, the resulting sequence 10001110001000011 will be decoded as BACBABAE.

The last five letter (BABAE) are correct, but the first three (BAC) are not.

Byteasar further noticed that all the letters after the first E are decoded correct.

He concluded that whenever all the bits of the code word of E are intact, all the characters succeeding E will be decoded correct.

The same holds for every encoded sequence obtained from one that contains E.

He also noticed that the letter D shares this feature, but A, B and C do not.

Because of the properties of the code words of E and D Byteasar called them synchronising code words.

He trusted you with the task of writing a programme that finds all the synchronising code words of a given prefix code.

To save some time, he intends to present you all the code words on his binary monitor.

This interesting device has four buttons:

0 - append ![](http://main.edu.pl/im…

inputFormat:
In the first line of the standard input there is an integer ![](http://main.edu.pl/images/OI16/kod-en-tex.7.png)      (![](http://main.edu.pl/images/OI16/kod-en-tex.8.png)) denoting the number of buttons pressed      by Byteasar.

In the following line an ![](http://main.edu.pl/images/OI16/kod-en-tex.9.png) letters long string consisting of the      characters '0', '1', 'B' and      'X' is given; the characters correspond to the buttons,      of course.

Each time the button X is pressed, a code word is      completed and another one starts.

The code words are numbered starting with 1.

The sum of lengths of all code words will not exceed ![](http://main.edu.pl/images/OI16/kod-en-tex.10.png).

outputFormat:
The number ![](http://main.edu.pl/images/OI16/kod-en-tex.11.png) of synchronising code words should be printed out in the     first line of the standard output.

The following ![](http://main.edu.pl/images/OI16/kod-en-tex.12.png) lines should contain the numbers of code words that  are synchronising in increasing order, each in a separate line.

If the given prefix code contains no synchronising code words, the first  line should contain the number 0, and no more lines should follow.

translation:
## 题面翻译

有若干个字符，对于每一个，用一个 $01$ 串编码它。所有的 $01$ 串由一棵完全的 trie (每个点有两个儿子)给出(具体方式见输入格式)，保证有且仅有每个叶子对应一个字符。定义一个串 $s$ 编码的结果是其中各个字符的编码按顺序接起来，记为 $\mathrm{encode}(s)$。

定义对一个 $01$ 串进行解码的过程是，每次找到一个前缀，满足它对应一个字符，容易知道这样的前缀是唯一的。将这个字符加入答案，将这个前缀从原串中删掉，如果不存在这样的前缀，则解码的结果是未定义。记 $s$ 解码的结果是 $\mathrm{decode}(s)$。

设一个字符编码为 $a$，定义它是好的，当且仅当对于任意两个串 $s,t$，对于 $\mathrm{encode}(s)$ 的任意后缀 $p$，有 $\mathrm{decode}(p+a)$ 不是未定义，且 $\mathrm{decode}(p+a+\mathrm{encode}(t))=\mathrm{decode}(p+a)+t$。求哪些字符是好的。

## 输入格式

第一行一个数 $n$，表示操作次数。接下来一行一个长 $n$ 的字符串，其中 `0`/`1` 表示在当前结点添加一个儿子，边权为 `0`/`1`，并移动过去；`B`表示添加一个父亲；`X`表示当前结点是一个字符的编码。保证输入是描述这棵 trie 的最短的可能输入。$n\leq 3\times 10^6$ ，所有字符编码的总长 $\leq 10^8$ 。

## 输出格式

一行一个数，表示好的字符的数量。

接下来若干行，从小到大输出每个好的字符是第几个`X`生成的。


title: [POI2010] GIL-Guilds

description:
King Byteasar faces a serious matter.

Two competing trade organisations, The Tailors Guild and The Sewers Guild asked,    at the same time, for permissions to open their offices in each town of the kingdom.

There are ![](http://main.edu.pl/images/OI17/gil-en-tex.1.png) towns in Byteotia.

Some of them are connected with bidirectional roads.

Each of the guilds postulate that every town should:

have an office of the guild, or           be directly connected to another town that does.

The king, however, suspects foul play. He fears that if there is just a single    town holding the offices of both guilds, it could lead to a clothing cartel.

For this reason he asks your help.

给一张无向图，要求你用黑白灰给点染色，且满足对于任意一个黑点，至少有一个白点和他相邻；对于任意一个白点，至少有一个黑点与他相邻，对于任意一个灰点，至少同时有一个黑点和白点和灰点与他相邻，问能否成功

inputFormat:
Two integers, n(<=200000) and m(<=500000),      are given in the first line of the standard input. These denote the number      of towns and roads in Byteotia, respectively.

The towns are numbered from 1 to n.

Then the roads are given as follows: the input line no. i+1 describes      the i-th road;

outputFormat:
Your program should print out one word in the first line of the standard output:

TAK (yes in Polish) - if the offices can be placed in towns according to these rules, or      NIE (no in Polish) - in the opposite case.

If the answers is TAK, then the following nlines should give an      exemplary placement of the offices. Thus the line no. i+1 should hold:

the letter K if there should be an office of The Tailors Guild in the town i, or the letter S if there should be an office of The Sewers Guild in the town i, or                      the letter N if there should be no office in the town i.


title: [POI2010] KOL-Railway

description:
A railroad siding consists of two (dead-end) sidetracks 1 and 2.

The siding is entered by track A, and left by track B (see figure below).

There are ![](http://main.edu.pl/images/OI17/kol-en-tex.1.png) cars on track A, numbered from ![](http://main.edu.pl/images/OI17/kol-en-tex.2.png) to ![](http://main.edu.pl/images/OI17/kol-en-tex.3.png).

They are arranged in such a way that they enter the siding in the order    ![](http://main.edu.pl/images/OI17/kol-en-tex.4.png).

The cars are to be transferred to the siding, so that they leave it by track B    in the order ![](http://main.edu.pl/images/OI17/kol-en-tex.5.png).

Each car is to be transferred once from track A to one of the sidetracks 1 or 2,    and later (possibly after some transfers of the remaining cars) once from that    sidetrack to the track B.

The sidetracks are long enough to store even the longest trains, so there is    no need to worry about their capacity.

数据范围10W的双栈排序..双栈排序是啥呢？给你一个序列和两个栈，每次你可以把序列头入到两个栈的任意一个，或者把两个栈的任意一个弹出到最终序列，最后要求最终序列是有序的，求一种字典序最小的入栈方案

inputFormat:
The first line of the standard input holds one integer ![](http://main.edu.pl/images/OI17/kol-en-tex.6.png) (![](http://main.edu.pl/images/OI17/kol-en-tex.7.png))      that denotes the number of cars for transfer.

The second line stores the numbers ![](http://main.edu.pl/images/OI17/kol-en-tex.8.png) that are a permutation of ![](http://main.edu.pl/images/OI17/kol-en-tex.9.png)      (i.e., each ![](http://main.edu.pl/images/OI17/kol-en-tex.10.png) belongs to ![](http://main.edu.pl/images/OI17/kol-en-tex.11.png), and all these numbers are unique),      separated by single spaces.

outputFormat:
The first line of the standard output should contain the word TAK      (yes in Polish) if there is a way of transferring the cars so that they      enter track B in the order ![](http://main.edu.pl/images/OI17/kol-en-tex.12.png), or the word NIE      (no in Polish) if it is impossible.

If the answer is TAK, the second line should give, separated by      single spaces, the numbers of sidetracks (1 or 2) to which successive cars      ![](http://main.edu.pl/images/OI17/kol-en-tex.13.png) are moved in a correct transfer.

If there are several ways of making the transfer, choose one arbitrarily.


title: [POI2010] KOR-Beads

description:
Byteasar once decided to start manufacturing necklaces.

He subsequently bought a very long string of colourful coral beads for a bargain price.

Byteasar now also has a machine that, for a given ![](http://main.edu.pl/images/OI17/kor-en-tex.1.png) (![](http://main.edu.pl/images/OI17/kor-en-tex.2.png)), can cut the string    into pieces (or substrings) of ![](http://main.edu.pl/images/OI17/kor-en-tex.3.png) coral beads (i.e., the first piece consists of the beads no.

![](http://main.edu.pl/images/OI17/kor-en-tex.4.png), the second of ![](http://main.edu.pl/images/OI17/kor-en-tex.5.png), etc.).

If the length of the string (measured in coral beads) is not a multiple of ![](http://main.edu.pl/images/OI17/kor-en-tex.6.png),    then the last piece is not used, as it has length smaller than ![](http://main.edu.pl/images/OI17/kor-en-tex.7.png).

From now on we denote the colours of the beads with positive integers.

Byteasar, always praising diversity, wonders how he should choose the number ![](http://main.edu.pl/images/OI17/kor-en-tex.8.png)    in order to get as many different substrings as possible.

The ends of the long string that will be cut are different: there are specific    beginning and ending (rather than two interchangeable endpoints), and the machine    of course starts cutting at the beginning. On the other hand, in the substrings    obtained from cutting the endpoints are interchangeable, and so the substrings    can be reversed. In other words, the substrings ![](http://main.edu.pl/images/OI17/kor-en-tex.9.png) and ![](http://main.edu.pl/images/OI17/kor-en-tex.10.png) are    identical to us. Write a program that determines the optimum value of ![](http://main.edu.pl/images/OI17/kor-en-tex.11.png) for Byteasar.

Zxl有一次决定制造一条项链，她以非常便宜的价格买了一长条鲜艳的珊瑚珠子，她现在也有一个机器，能把这条珠子切成很多块（子串），每块有k（k>0）个珠子，如果这条珠子的长度不是k的倍数，最后一块小于k的就不要拉（nc真浪费），保证珠子的长度为正整数。 Zxl喜欢多样的项链，为她应该怎样选择数字k来尽可能得到更多的不同的子串感到好奇，子串都是可以反转的，换句话说，子串（1，2，3）和（3,2,1）是一样的。写一个程序，为Zxl决定最适合的k从而获得最多不同的子串。 例如：这一串珠子是： (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)， k=1的时候，我们得到3个不同的子串： (1),(2),(3) k=2的时候，我们得到6个不同的子串： (1,1),(1,2),(2,2),(3,3),(3,1),(2,3) k=3的时候，我们得到5个不同的子串：  (1,1,1),(2,2,2),(3,3,3),(1,2,3),(3,1,2) k=4的时候，我们得到5个不同的子串： (1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)

inputFormat:
In the first line of the standard input there is an integer ![](http://main.edu.pl/images/OI17/kor-en-tex.37.png)      (![](http://main.edu.pl/images/OI17/kor-en-tex.38.png)) denoting the length of the string to cut.

In the second line there are ![](http://main.edu.pl/images/OI17/kor-en-tex.39.png) positive integers ![](http://main.edu.pl/images/OI17/kor-en-tex.40.png)      (![](http://main.edu.pl/images/OI17/kor-en-tex.41.png)), separated by single spaces, that denote      the colours of successive beads in Byteasar's string.

outputFormat:
Two integers, separated by a single space, should be printed out to the first line of the standard ouput:

the (maximum) number of different substrings that can be obtained with an optimal choice    of parameter ![](http://main.edu.pl/images/OI17/kor-en-tex.42.png), and the number ![](http://main.edu.pl/images/OI17/kor-en-tex.43.png) of such optimal values of ![](http://main.edu.pl/images/OI17/kor-en-tex.44.png).

The second line should contain ![](http://main.edu.pl/images/OI17/kor-en-tex.45.png) integers separated by single spaces:

the values of parameter ![](http://main.edu.pl/images/OI17/kor-en-tex.46.png) that yield an optimum solution;    these can be given in arbitrary order.

输出两行，第一行第一个数为最多可以得到的不同子串的个数，第二个数为取到最优解时的不同的k的个数。第二行包含若干个数，为取到最优解时的不同的k 。第二行中的不同的k可以按任意位置输出。

translation:
### 【题目描述】

Byteasar 有 $n$ 个珠子，第 $i$ 个颜色为 $a_i$，和一台机器。

Byteasar 可以选定一个值 $k$，然后机器会让 $1\sim k$ 的珠子组成项链 $b_1$，$k+1\sim 2k$ 的珠子组成项链 $b_2$，以此类推，**最后 $n\bmod k$ 个珠子不会组成项链，而是被丢弃**。

现在让你求出一个 $k$ 值，使得在 $\left\lfloor\dfrac{n}{k}\right\rfloor$ 个项链 $b$ 中，存在 **不同的** 项链数量最多。

项链可以反转，形式化地，$b_x$ 和 $b_y$ 不同，当且仅当存在至少一个 $i$，使得 $b_{x,i}\ne b_{y,i}$ 且 $b_{x,i} \ne b_{y,k-i+1}$。

例如 $[1,2,3]$ 和 $[3,2,1]$ 是相同的，而 $[1,2,3]$ 和 $[2,3,1]$ 是不同的。

### 【输入格式】

输入两行，第一行为 $n$。

第二行为 $n$ 个正整数，第 $i$ 个正整数代表 $a_i$。

### 【输出格式】

输出两行。

第一行两个整数，分别代表不同的项链最多的数量，以及不同的项链最多时，$k$ 的个数。

第二行若干个整数，代表所有能使不同的项链最多的 $k$ 值，这可以按任意顺序输出。

### 【样例解释】

$a$ 为 $[1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1]$。

- $k=1$ 的时候，我们得到 $3$ 个不同的项链 $b$：$[1],[2],[3]$。
- $k=2$ 的时候，我们得到 $6$ 个不同的项链：$[1,1],[1,2],[2,2],[2,3],[3,3],[3,1]$。
- $k=3$ 的时候，我们得到 $5$ 个不同的项链：$[1,1,1],[2,2,2],[3,3,3],[1,2,3],[3,1,2]$。
- $k=4$ 的时候，我们得到 $5$ 个不同的项链：$[1,1,1,2],[2,2,3,3],[3,1,2,3],[3,1,2,2],[1,3,3,2]$。

### 【数据范围】

对于全部数据，$1\le n\le2\times 10^5$，且 $\forall 1\le i\le n$，有 $1\le a_i\le n$。

hint: $1≤n≤2\times 10^5$，且 $\forall 1\le i\le n$，有 $1\le a_i\le n$


title: [POI2010] NAJ-Divine Divisor

description:
An integer ![](http://main.edu.pl/images/OI17/naj-en-tex.1.png) is given.

We say that an integer ![](http://main.edu.pl/images/OI17/naj-en-tex.2.png) is a divisor of ![](http://main.edu.pl/images/OI17/naj-en-tex.3.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.4.png)    (![](http://main.edu.pl/images/OI17/naj-en-tex.5.png) is integer) if ![](http://main.edu.pl/images/OI17/naj-en-tex.6.png) and ![](http://main.edu.pl/images/OI17/naj-en-tex.7.png) does not divide ![](http://main.edu.pl/images/OI17/naj-en-tex.8.png).

For example, the number ![](http://main.edu.pl/images/OI17/naj-en-tex.9.png) has the following divisors:

2 with multiplicity 4, 3 with multiplicity 1, 4 with multiplicity 2, 6 with multiplicity 1, and so on.

We say that a number ![](http://main.edu.pl/images/OI17/naj-en-tex.10.png) is a  divine divisor of the number ![](http://main.edu.pl/images/OI17/naj-en-tex.11.png)    if ![](http://main.edu.pl/images/OI17/naj-en-tex.12.png) is a divisor of ![](http://main.edu.pl/images/OI17/naj-en-tex.13.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.14.png) and ![](http://main.edu.pl/images/OI17/naj-en-tex.15.png) has no divisors    with multiplicities greater than ![](http://main.edu.pl/images/OI17/naj-en-tex.16.png).

For example, the sole divine divisor of 48 is 2 (with multiplicity 4),    and the divine divisors of 6 are: 2, 3 and 6 (each with multiplicity 1).

Your task is to determine the multiplicity of divine divisors of ![](http://main.edu.pl/images/OI17/naj-en-tex.17.png)    and the number of its divine divisors.

给定一个正整数 $m$ 以及长度为 $m$ 的正整数序列  $a$ ,同时给出  $n = \prod_{i=1}^{m}{a_i}$。你需要找出一个最大的 $k$ 使得存在一个 $d$ , $d > 1$ 并且 $d^k | n$。求这个最大的 $k$ 以及在 $k$ 最大的情况下有多少个 $d$ 满足条件。

inputFormat:
The number ![](http://main.edu.pl/images/OI17/naj-en-tex.18.png) is given on the standard input, though in a somewhat unusual way.

The first line holds a single integer ![](http://main.edu.pl/images/OI17/naj-en-tex.19.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.20.png)).

The second line holds ![](http://main.edu.pl/images/OI17/naj-en-tex.21.png) integers ![](http://main.edu.pl/images/OI17/naj-en-tex.22.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.23.png))    separated by single spaces.

These denote that ![](http://main.edu.pl/images/OI17/naj-en-tex.24.png).

outputFormat:
The first line of the standard output should hold the maximum integer ![](http://main.edu.pl/images/OI17/naj-en-tex.25.png)    such that there exists a divisor ![](http://main.edu.pl/images/OI17/naj-en-tex.26.png) of ![](http://main.edu.pl/images/OI17/naj-en-tex.27.png) such that ![](http://main.edu.pl/images/OI17/naj-en-tex.28.png).

The second line should hold a single integer ![](http://main.edu.pl/images/OI17/naj-en-tex.29.png) that is the number of    (divine) divisors of ![](http://main.edu.pl/images/OI17/naj-en-tex.30.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.31.png).

hint: $1\le m\le 600$，且$\forall 1\le i\le m$，有$1\le a_i\le 10^{18}$


title: [POI2010] TES-Intelligence Test

description:
One of the tasks in the Byteotian Intelligence Test (BIT) is to cross out    numbers from an initial sequence in such a way that leaves as a result    certain given sequences.

Byteasar longs to become the IQ Master of Byteotia, but he is no good in    this kind of tasks.

But since practice makes perfect, he intends to practise a lot.

So much in fact that he asks you to write a program that will facilitate    the training by verifying his answers quickly.

Byteotian智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Byteasar很渴望成为Byteotian智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。

inputFormat:
The first line of the standard input contains one integer $m$ ($1\le m\le 1\ 000\ 000$).

The second line holds $m$ integers $a_1,a_2,\cdots,a_m$ ($1\le a_i\le 1\ 000\ 000$ for $1\le i\le m$), separated by single spaces,      that constitute the initial sequence of the test.

The third line of the input holds one integer $n$.

The following $2n$ lines describe the sequences to be obtained by crossing out      numbers from the initial sequence.

Each sequence's description takes two successive lines.

The first of these two lines contains an integer $m_i$ ($1\le m_i\le 1\ 000\ 000$).

The second contains an $m_i$-element long sequence of integers $b_{i,1},b_{i,2},\cdots,b_{i,m_i}$($1\le b_{i,j}\le 1\ 000\ 000$ for $1\le j\le m_i$)separated by single spaces. You may assume that the total length on given $n$ sequences does not exceed $1\ 000\ 000$.

第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=1000000），表示n个Byteasar经过一系列删除得到的序列，每个序列两行，第一行给出长度L（1<=L<=m），然后下一行为L个由空格分开的整数bi（1<=bi<=1000000）。

outputFormat:
Your program should print out $n$ lines to the standard output.

The $i$-th line (for $1\le i\le n$) should hold one word,      "TAK" (yes in Polish) if the $i$-th input sequence can be obtained by      crossing out (i.e., removing) some, not necessarily contiguous, numbers from the initial sequence,      or "NIE" (no in Polish) otherwise. Mind you, only the words should be printed,      no quotation marks. Of course, the order of the numbers left after crossing out is important,      as can be seen in the example.

共n行，如果Byteasar的序列确实是由最初的序列删除一些数得到，就输出TAK，否则输出NIE。

hint:
题目简述：给定一个数串，和m个小数串，问这些小串都是不是大数字串的子序列

感谢@Yhy9630 提供翻译


title: [POI2010] ANT-Antisymmetry

description:
Byteasar studies certain strings of zeroes and ones.

Let ![](http://main.edu.pl/images/OI17/ant-en-tex.1.png) be such a string. By ![](http://main.edu.pl/images/OI17/ant-en-tex.2.png) we will denote the reversed (i.e., "read backwards") string ![](http://main.edu.pl/images/OI17/ant-en-tex.3.png),    and by ![](http://main.edu.pl/images/OI17/ant-en-tex.4.png) we will denote the string obtained from ![](http://main.edu.pl/images/OI17/ant-en-tex.5.png) by changing all the zeroes to ones and ones to zeroes.

Byteasar is interested in antisymmetry, while all things symmetric bore him.

Antisymmetry however is not a mere lack of symmetry.

We will say that a (nonempty) string ![](http://main.edu.pl/images/OI17/ant-en-tex.6.png) is antisymmetric if, for every position ![](http://main.edu.pl/images/OI17/ant-en-tex.7.png) in ![](http://main.edu.pl/images/OI17/ant-en-tex.8.png),    the ![](http://main.edu.pl/images/OI17/ant-en-tex.9.png)-th last character is different than the ![](http://main.edu.pl/images/OI17/ant-en-tex.10.png)-th (first) character.

In particular, a string ![](http://main.edu.pl/images/OI17/ant-en-tex.11.png) consisting of zeroes and ones is antisymmetric if and only if    ![](http://main.edu.pl/images/OI17/ant-en-tex.12.png).

For example, the strings 00001111 and 010101 are antisymmetric, while 1001 is not.

In a given string consisting of zeroes and ones we would like to determine the number of contiguous    nonempty antisymmetric fragments.

Different fragments corresponding to the same substrings should be counted multiple times.

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。

现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

inputFormat:
The first line of the standard input contains an integer ![](http://main.edu.pl/images/OI17/ant-en-tex.13.png) (![](http://main.edu.pl/images/OI17/ant-en-tex.14.png)) that denotes the length of the string.

The second line gives a string of 0 and/or 1 of length ![](http://main.edu.pl/images/OI17/ant-en-tex.15.png).

There are no spaces in the string.

outputFormat: The first and only line of the standard output should contain a single integer,      namely the number of contiguous (non empty) fragments of the given string      that are antisymmetric.

hint:
7个反对称子串分别是：01（出现两次），10（出现两次），0101，1100和001011

$n \le 5 \times 10^5$


title: [POI2010] CHO-Hamsters

description:
Byteasar breeds hamsters.

Each hamster has a unique name,    consisting of lower case letters of the English alphabet.

    The hamsters have a vast and comfortable cage.

    Byteasar intends to place a display under the cage to visualize the names of his hamsters.

    This display is simply a sequence of letters, each of which can be either lit or not independently.

Only one name will be displayed simultaneously.

The lit letters forming the name have to stand next to each other,    i.e., form a contiguous subsequence.

Byteasar wants to be able to display the names of the hamsters on at least ![](http://main.edu.pl/images/OI17/cho-en-tex.1.png) different positions.

However, he allows displaying the same name on multiple different positions,    and does not require to be able to display each and every hamster's name.

Note that the occurrences of the names on the display can overlap.

You can assume that no hamster's name occurs (as a contiguous fragment) in any other hamster's name.

Bytesar asks your help in determining the minimum number of letters the display has to have.

In other words, you are to determine the minimum length of a string    (consisting of non-capital letters of the English alphabet)    that has at least ![](http://main.edu.pl/images/OI17/cho-en-tex.2.png) total occurrences of the hamsters' names (counting multiplicities).

(We say that a string ![](http://main.edu.pl/images/OI17/cho-en-tex.3.png) occurs in the string ![](http://main.edu.pl/images/OI17/cho-en-tex.4.png) if ![](http://main.edu.pl/images/OI17/cho-en-tex.5.png) forms a contiguous fragment of ![](http://main.edu.pl/images/OI17/cho-en-tex.6.png).)

inputFormat:
The first line of the standard input holds two integers ![](http://main.edu.pl/images/OI17/cho-en-tex.7.png) and ![](http://main.edu.pl/images/OI17/cho-en-tex.8.png)      (![](http://main.edu.pl/images/OI17/cho-en-tex.9.png), ![](http://main.edu.pl/images/OI17/cho-en-tex.10.png)), separated by a single space, that denote      the number of Byteasar's hamsters and the minimum number of occurrences of the hamsters' names on the display.

Each of the following ![](http://main.edu.pl/images/OI17/cho-en-tex.11.png) lines contains a non-empty string of non-capital letters of the English alphabet      that is the hamster's name.

The total length of all names does not exceed ![](http://main.edu.pl/images/OI17/cho-en-tex.12.png) letters.

outputFormat: The first and only line of the standard output should hold a single integer      - the minimum number of letters the display has to have.

translation: 给出 $n$ 个互不包含的字符串，要求你求出一个最短的字符串 $S$，使得这 $n$ 个字符串在 $S$ 中总共至少出现 $m$ 次，问 $S$ 最短是多少。


title: [POI2010] KLO-Blocks

description:
    Bytie has got a set of wooden blocks for his birthday.

The blocks are indistinguishable from one another, as they are all cubes of the same size.

    Bytie forms piles by putting one block atop another.

Soon he had a whole rank of such piles, one next to another in a straight line.

Of course, the piles can have different heights.

Bytie's father, Byteasar, gave his son a puzzle.

He gave him a number ![](http://main.edu.pl/images/OI17/klo-en-tex.1.png) and asked to rearrange the blocks in such a way that    the number of successive piles of height at least ![](http://main.edu.pl/images/OI17/klo-en-tex.2.png) is maximised.

However, Bytie is only ever allowed to pick the top block from a pile strictly    higher than ![](http://main.edu.pl/images/OI17/klo-en-tex.3.png) and place it atop one of the piles next to it.

Further, Bytie is not allowed to form new piles, he can only move blocks    between those already existing.

inputFormat:
In the first line of the standard input there are two integers separated by a single space:

![](http://main.edu.pl/images/OI17/klo-en-tex.4.png) (![](http://main.edu.pl/images/OI17/klo-en-tex.5.png)), denoting the number of piles, and ![](http://main.edu.pl/images/OI17/klo-en-tex.6.png) (![](http://main.edu.pl/images/OI17/klo-en-tex.7.png)),      denoting the number of Byteasar's requests.

The piles are numbered from ![](http://main.edu.pl/images/OI17/klo-en-tex.8.png) to ![](http://main.edu.pl/images/OI17/klo-en-tex.9.png).

In the second line there are ![](http://main.edu.pl/images/OI17/klo-en-tex.10.png) integers ![](http://main.edu.pl/images/OI17/klo-en-tex.11.png)      separated by single spaces (![](http://main.edu.pl/images/OI17/klo-en-tex.12.png)).

The number ![](http://main.edu.pl/images/OI17/klo-en-tex.13.png) denotes the height of the ![](http://main.edu.pl/images/OI17/klo-en-tex.14.png)-th pile.

The third line holds ![](http://main.edu.pl…

outputFormat: Your program should print out ![](http://main.edu.pl/images/OI17/klo-en-tex.21.png) integers, separated by single spaces,      to the standard output - the ![](http://main.edu.pl/images/OI17/klo-en-tex.22.png)-th of which should be the answer to the puzzle      for the given initial piles set-up and the parameter ![](http://main.edu.pl/images/OI17/klo-en-tex.23.png).

translation:
给出 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，再给出一个正整数 $k$，现在可以进行如下操作：

- 每次选择一个大于 $k$ 的正整数 $a_i$，将 $a_i$ 减去 $1$ ，选择 $a_{i-1}$ 或 $a_{i+1}$ 中的一个加上 $1$。

经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于 $k$。$m$ 组询问。


title: [POI2010] OWC-Sheep

description:
The habitants of the Byteotian Highland bred sheep for centuries.

Every sane shepherd has a fenced pasture in the shape of a convex1 polygon    for the sheep to graze on.

Every sane sheep in turn has its own favourite feeding spot on the pasture where it spends all days.

Sometimes however, the sheep want to play. As they play in pairs, every shepherd keeps an even number of sheep,    so that his every sheep has a partner to play with.

The shepherds are concerned about a decree recently issued by the Byteburg's High Commissioner for Agriculture.

The decree states that as of the next year the sheep can only graze on triangle-shaped pastures.

Thus every shepherd whose pasture is an ![](http://main.edu.pl/images/OI17/owc-en-tex.1.png)-gon for ![](http://main.edu.pl/images/OI17/owc-en-tex.2.png) is to partition it into triangles by putting ![](http://main.edu.pl/images/OI17/owc-en-tex.3.png)    fences inside.

Each single new fence, of course, is going to be a segment connecting two vertices of the polygon (pasture).

Additionally, the fences can intersect only in these vertices.

A shepherd who does not fulfil these requirements will no longer be subsidized.

Byteasar, as a shepherd, has to decide on a way of partitioning his pasture.

In fact, he is unsure how many partitions are possible. He is only interested in such partitions    that no fence is drawn through a favourite spot of any sheep, and such that every resulting triangle    contains the favourite spots of an even number of sheep, so that these sheep can play in pairs.

Help Byteasar by writing a program that calculates the number of such partitions!

inputFormat:
The first line of the standard input contains three integers ![](http://main.edu.pl/images/OI17/owc-en-tex.4.png), ![](http://main.edu.pl/images/OI17/owc-en-tex.5.png) and ![](http://main.edu.pl/images/OI17/owc-en-tex.6.png)    (![](http://main.edu.pl/images/OI17/owc-en-tex.7.png), ![](http://main.edu.pl/images/OI17/owc-en-tex.8.png), ![](http://main.edu.pl/images/OI17/owc-en-tex.9.png), ![](http://main.edu.pl/images/OI17/owc-en-tex.10.png)),    separated by single spaces, that denote respectively:

the number of vertices of the polygon forming the pasture,    the number of the sheep, and a certain positive integer ![](http://main.edu.pl/images/OI17/owc-en-tex.11.png).

Each of the following ![](http://main.edu.pl/images/OI17/owc-en-tex.12.png) lines contains two integers ![](http://main.edu.pl/images/OI17/owc-en-tex.13.png) and ![](http://main.edu.pl/images/OI17/owc-en-tex.14.png)    (![](http://main.edu.pl/images/OI17/owc-en-tex.15.png)), separated by a single space,    de…

outputFormat: Your program should print one integer on the standard output,    namely the remainder of division by ![](http://main.edu.pl/images/OI17/owc-en-tex.22.png) of the number of partitions of the pasture in triangles,    such that no fence is drawn through a favourite spot of any sheep, and every resulting triangle    contains the favourite spots of an even number of sheep.

translation: 给一个n个点的凸多边形，再给出k个在多边形内的点，要求你把多边形划分成三角形，使得每个三角形内都有偶数个点，且三角形边上不能有点。

hint: $4\le n\le 600$，$2\le k$，$m\le 20\ 000$，$2\mid k$，$-15\ 000\le x_i,y_i,p_i,q_i\le 15\ 000$ ，牧场的顶点坐标按顺时针顺序给出，保证羊严格在多边形内部。


title: [POI2010] TEL-Teleportation

description:
King Byteasar is the ruler of the whole solar system that contains ![](http://main.edu.pl/images/OI17/tel-en-tex.1.png) planets.

This number is so large that people have abandoned the silly custom of naming the planets    and use numbers instead. The planets are thus conveniently numbered from 1 to ![](http://main.edu.pl/images/OI17/tel-en-tex.2.png).

Byteasar's palace is on the planet no. 1, while his military base on the planet no. 2.

A long time ago Byteasar had a teleportation portal established between these two planets,    which allows travelling from either planet to another in two hundred and fifty minutes    (slightly over four hours).

Nowadays the teleportation technology is more mature, and the recent teleportation devices shorten    the travel time to just a single hour. Let us note here, that all the portals, both the Byteasar's old one    and the new ones available on the market, are of course bidirectional, and that the teleportation    travel time is irrespective of the distance travelled.

Some planets of the system are already connected with these new teleportation portals.

In fact, it is already possible to travel between the planets no. 1 and 2 without using the king's private portal,    though this involves several other portals and is thus no faster than the king's portal.

Byteasar finds this rather fortunate, as he believes that such possibility would be a security breach.

The technology itself is increasingly available, and as everyone realises its economic significance,    each pair of planets that are not currently directly connected with a portal are petitioning for establishing    such a connection. Being a wise ruler, Byteasar intends to give his consent to as many constructions as possible,    though keeping himself secure, i.e., not allowing the travel between planets 1 and 2 faster than with his private portal.

Help the king determine how many portals he can agree to.

给一张图，要求你再尽可能的多连边，使得从1到2至少要经过5条边

inputFormat:
Two integers are given in the first line of the standard input, ![](http://main.edu.pl/images/OI17/tel-en-tex.3.png) and ![](http://main.edu.pl/images/OI17/tel-en-tex.4.png)      (![](http://main.edu.pl/images/OI17/tel-en-tex.5.png), ![](http://main.edu.pl/images/OI17/tel-en-tex.6.png)), separated by a single space,      denoting the number of planets in Byteasar's realm and the number of new portals      that already exist.

These teleportation portals are described in the ![](http://main.edu.pl/images/OI17/tel-en-tex.7.png) lines that follow.

Each such line contains two integers ![](http://main.edu.pl/images/OI17/tel-en-tex.8.png) and ![](http://main.edu.pl/images/OI17/tel-en-tex.9.png) (![](http://main.edu.pl/images/OI17/tel-en-tex.10.png)),      separated by a single space, denoting that there is a teleportation portal of the new kind      connecting ![](http://main.edu.pl/images/OI17/tel-en-tex.11.png) and ![](http://main.edu.pl/images/OI17/tel-en-tex.12.png).

No pair of numbers appears twice.

You may assume that the existing network of new portals allows travel from      planet no. 1 to planet no. 2, but in no less than 250 minutes.

outputFormat: Your program should print out just a single integer, namely the maximum number of portals      Byteasar can agree to without breaching his security.

hint: $2\le n\le 40\ 000$，$0\le m\le 10^6$，$1\le u_i,v_i\le n$，保证只考虑已有的边时， $1$ 号点与 $2$ 号点联通，且最短路长度大于 $250\min$ 。


title: [POI2010] MOT-Monotonicity 2

description:
This task is a harder version of task Monotonicity from the third stage of 17th Polish OI. It wasn't used in the contest itself.

For an integer sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.1.png) we define its monotonicity scheme as the sequence    ![](http://main.edu.pl/images/OI17/mot-en-tex.2.png) of symbols ![](http://main.edu.pl/images/OI17/mot-en-tex.3.png), ![](http://main.edu.pl/images/OI17/mot-en-tex.4.png) or ![](http://main.edu.pl/images/OI17/mot-en-tex.5.png).

The symbol ![](http://main.edu.pl/images/OI17/mot-en-tex.6.png) represents the relation between ![](http://main.edu.pl/images/OI17/mot-en-tex.7.png) and ![](http://main.edu.pl/images/OI17/mot-en-tex.8.png).

For example, the monotonicity scheme of the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.9.png) is ![](http://main.edu.pl/images/OI17/mot-en-tex.10.png).

We say that an integer sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.11.png) with monotonicity scheme    ![](http://main.edu.pl/images/OI17/mot-en-tex.12.png), realizes another monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.13.png)    if for every ![](http://main.edu.pl/images/OI17/mot-en-tex.14.png) it holds that ![](http://main.edu.pl/images/OI17/mot-en-tex.15.png).

In other words, the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.16.png) can be obtained by repeating the sequence    ![](http://main.edu.pl/images/OI17/mot-en-tex.17.png) and removing appropriate suffix from that repetition.

For example, the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.18.png) realizes each and every one of the following schemes:

![](http://main.edu.pl/images/OI17/mot-en-tex.19.png)           ![](http://main.edu.pl/images/OI17/mot-en-tex.20.png)           ![](http://main.edu.pl/images/OI17/mot-en-tex.21.png)           ![](http://main.edu.pl/images/OI17/mot-en-tex.22.png)                  as well as many others.

An integer sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.23.png) and a monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.24.png) are given.

Your task is to find the longest subsequence ![](http://main.edu.pl/images/OI17/mot-en-tex.25.png) (![](http://main.edu.pl/images/OI17/mot-en-tex.26.png))    of the former that realizes the latter.

给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。

选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。

求出L的最大值。

感谢@cn：苏卿念 提供spj

inputFormat:
The first line of the standard input holds two integers ![](http://main.edu.pl/images/OI17/mot-en-tex.27.png) and ![](http://main.edu.pl/images/OI17/mot-en-tex.28.png) (![](http://main.edu.pl/images/OI17/mot-en-tex.29.png), ![](http://main.edu.pl/images/OI17/mot-en-tex.30.png)),    separated by a single space, denoting the lengths of the sequences ![](http://main.edu.pl/images/OI17/mot-en-tex.31.png) and monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.32.png) respectively.

The second input line gives the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.33.png), i.e, it holds ![](http://main.edu.pl/images/OI17/mot-en-tex.34.png) integers ![](http://main.edu.pl/images/OI17/mot-en-tex.35.png) separated by single spaces (![](http://main.edu.pl/images/OI17/mot-en-tex.36.png)).

Finally, the third lines gives the monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.37.png), i.e., it holds ![](http://main.edu.pl/images/OI17/mot-en-tex.38.png) s…

outputFormat:
In the first line of the standard output your program should print out a single integer ![](http://main.edu.pl/images/OI17/mot-en-tex.40.png),    the maximum length of a subsequence of ![](http://main.edu.pl/images/OI17/mot-en-tex.41.png) that realizes the scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.42.png).

In the second line it should print out any such subsequence ![](http://main.edu.pl/images/OI17/mot-en-tex.43.png), separating its elements by single spaces.


title: [POI2010] GRA-The Minima Game

description:
Alice and Bob learned the minima game, which they like very much, recently.

The rules of the game are as follows.

A certain number of cards lies on a table, each inscribed with a positive integer.

The players make alternate moves, Alice making the first one.

A move consists in picking an arbitrary positive number of cards from the table.

For such move the player receives a number of points equal to the minimum    of the numbers inscribed on the cards he collected.

The game ends when the last card is removed from the table.

The goal of each player is maximizing the difference between their and their opponent's score.

Alice and Bob have duly noted that there is an optimal strategy in the game.

Thus they are asking you to write a program that, for a given set of cards,    determines the outcome of the game when both players play optimally.

给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下，最终A的得分减去B的得分为多少。

inputFormat:
In the first line of the standard input there is one integer ![](http://main.edu.pl/images/OI17/gra-en-tex.1.png) (![](http://main.edu.pl/images/OI17/gra-en-tex.2.png)) given,      denoting the number of cards.

The second line holds ![](http://main.edu.pl/images/OI17/gra-en-tex.3.png) positive integers ![](http://main.edu.pl/images/OI17/gra-en-tex.4.png) (![](http://main.edu.pl/images/OI17/gra-en-tex.5.png)),      separated by single spaces, that are inscribed on the cards.

outputFormat: Your program should print out a single line with a single integer to the standard      output - the number of points by which Alice wins over Bob, assuming they both play optimally;      if it is Bob who has more points, the result should be negative.


title: [POI2010] LAT-Lamp

description:
In the middle of the night Bitratio turned on the lamp at the entrance to the building that Byteasar lives in.

Now the strong light prevents Byteasar from sleeping.

While the lamp does not shine directly on Byteasar's windows, it does so by reflecting in other windows.

Deprived of sleep, Byteasar is becoming irritated.

To remedy that he tries to occupy his mind, but all he can think of is the light.

Thus Byteasar looked out the window and wondered if his neighbours suffer similar torture,    i.e., whether the light shines on their windows as well.

Now that is an interesting question, at least in Byteasar's opinion.

You learn of the puzzle sooner than you would wish: unable to solve the problem all by himself,    thinking little of sleep now (be it his and yours), Byteasar calls you to ask for help.

You know him well enough to understand that you too will not get any sleep until you write a program    that solves his problem.

Byteasar lives in the building ![](http://main.edu.pl/images/OI17/lat-en-tex.1.png), which has ![](http://main.edu.pl/images/OI17/lat-en-tex.2.png) windows.

The lamp is situated on a wall at the very bottom of this building.

Opposite the building ![](http://main.edu.pl/images/OI17/lat-en-tex.3.png), exactly 10 meters apart, there is another building, ![](http://main.edu.pl/images/OI17/lat-en-tex.4.png).

The wall of this ![](http://main.edu.pl/images/OI17/lat-en-tex.5.png)-windowed building is parallel to the wall of ![](http://main.edu.pl/images/OI17/lat-en-tex.6.png), the Byteasar's building.

The lamp light behaves like you would expect, i.e., in the way predicted by geometrical optics (or ray optics).

Namely the light propagates along rays, and if a ray hits a window, it is reflected.

Due to The Law of Reflection, the angle of the ray's reflection equals the angle of incidence.

We introduce coordinate systems on the the walls of the two buildings in the following way.

Both ![](http://main.edu.pl/images/OI17/lat-en-tex.7.png) axes are horizontal, while both ![](http://main.edu.pl/images/OI17/lat-en-tex.8.png) axes are vertical; the axes on both walls are identically oriented,    and the ![](http://main.edu.pl/images/OI17/lat-en-tex.9.png) points of the walls are opposite one another.

The windows (on either building) are simply rectangles with sides parallel to the axes of the coordinate system.

A ray is reflected only in the interior of any window; it is absorbed on the window's boundary.

In each building, no two windows share any part of their interiors.

The lamp is located on the wall of the ![](http://main.edu.pl/images/OI17/lat-en-tex.10.png) building at the point ![](http://main.edu.pl/images/OI17/lat-en-tex.11.png),    which is neither inside nor at the boundary of any window.

inputFormat:
In the first line of the standard input there are two integers ![](http://main.edu.pl/images/OI17/lat-en-tex.12.png) and ![](http://main.edu.pl/images/OI17/lat-en-tex.13.png) (![](http://main.edu.pl/images/OI17/lat-en-tex.14.png)),      separated by a single space, denoting the number of windows in the first and second building respectively.

The ![](http://main.edu.pl/images/OI17/lat-en-tex.15.png) lines that follow describe the windows in Byteasar's building (the ![](http://main.edu.pl/images/OI17/lat-en-tex.16.png) building), one per line.

The line no. ![](http://main.edu.pl/images/OI17/lat-en-tex.17.png) (for ![](http://main.edu.pl/images/OI17/lat-en-tex.18.png)) holds four integers ![](http://main.edu.pl/images/OI17/lat-en-tex.19.png), ![](http://main.edu.pl/images/OI17/lat-en-tex.20.png), ![](http://main.edu.pl/images/OI17/lat-en-tex.21.png), ![](http://main.edu.pl/images/OI17/lat-en-tex.22.png)      (![](http://main.edu.pl/images/OI17/lat-en-tex.23.png),      !…

outputFormat:
In the first line of the standard output your program should print the number of windows in the ![](http://main.edu.pl/images/OI17/lat-en-tex.31.png) building      whose interiors are hit by some ray.

You may assume that in every test instance there will be at least one such window (the Byteasar's window).

In the second line the numbers of these windows (windows are numbered starting from 1) should be printed in increasing order,      separated by single spaces.

translation:
一天，~~**缺德的**~~ Bitratio 打开了 Byteasar 所居住的大楼处的灯光。

Byteasar 无法入睡的时候，~~**缺德的**~~ 他开始想知道他的邻居是否也遭受了类似的折磨，也就是说，光线是否也照在他们的窗户上。

已知这个世界归牛顿管理。也就是说，光沿着光线传播，如果光线击中窗口，就会被反射。且根据反射定律，光线的反射角等于入射角。

~~**缺德的**~~ Bitratio 所住的大楼与 Byteasar 的大楼相距 $10m$ 。它们的墙壁都是平行的，光线只在任何窗户的内部反射，反之，它在窗口的边界上被吸收。

我们以以下方式在这两栋建筑的墙上引入坐标系：两个轴都是水平的，而两个轴是垂直的；两个墙上的轴线方向相同，墙的点彼此相对。窗户（在任何一栋建筑上）都是简单的矩形，侧面平行于坐标系的轴。在每栋建筑中，没有两扇窗户共享其内部的任何部分。该灯位于建筑物的墙上，该点既不在任何窗户的内部，也不在任何窗口的边界。

## 输入输出格式

**输入部分**：第一行为两个整数 $n$ , $m$ ，分别表示第一栋和第二栋建筑中的窗户数量。之后 $n+m$ 行，描述了 Byteasar 与 Bitratio 的大楼中窗户的位置。每行包含四个整数 $x_1$ , $y_1$ , $x_2$ , $y_2$ ，表示窗户左上角和右下角的坐标。

**输出部分**：两行，第一行表示 Byteasar 的大楼中被照射到的窗户的数量 $k$ ，第二行输出 $k$ 个整数，表示被照射到的窗户的编号。


title: [POI2010] ZAB-Frog

description:
On the bed of one particularly long and straight Byteotian brook there lie $n$ rocks jutting above the water level. Their distances from the brook's spring are $p_1 < p_2 < \cdots < p_n$ respectively. A small frog sitting on one of these is about to begin its leaping training. Each time the frog leaps to the rock that is the -th closest to the one it is sitting on. Specifically, if the frog is sitting on the rock at position $p_i$, then it will leap onto such $p_j$ that:
$$
|\{ p_a : |p _ a - p _ i| < |p_j - p_i| \}| \le k \text{ and } |\{ p_a : |p _ a - p _ i| \le |p_j - p_i| \}| > k
$$
If $p_j$ is not unique, then the frog chooses among them the rock that is closest to the spring. On which rock the frog will be sitting after $m$ leaps depending on the rock is started from?

inputFormat: The first line of the standard input holds three integers, $n$, $k$ and $m$ ($1 \le k < n \le 1 \, 000 \, 000, 1 \le m \le 10^{18}$), separated by single spaces, that denote respectively: the number of rocks, the parameter $k$, and the number of intended leaps. The second line holds $n$ integers $p_j$ ($1 \le p_1 < p_2 < \cdots < p_n \le 10^{18}$), separated by single spaces, that denote the positions of successive rocks on the bed of the brook.

outputFormat: Your program should print a single line on the standard output, with $n$ integers $r_1, r_2, \cdots, r_n$ from the interval $[1, n]$ in it, separated by single spaces. The number $r_i$ denotes the number of the rock that the frog ends on after making $m$ leaps starting from the rock no. $i$ (in the input order).

translation:
有 $n$ 个点，升序给出每个点到起点的距离。有编号为 $1 \sim n$ 的 $n$ 只青蛙分别在第 $1 \sim n$ 个点上，每次它们会跳到距离自己第 $k$ 近的点上。

如果有相同距离的点，就跳到下标更小的点上。

求跳 $m$ 次之后，第 $i$ 只的青蛙在哪个点上。

输入共一行三个整数：代表 $n, k, m$。

输出共一行 $n$ 个整数，代表每只青蛙最终所处在的点。

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

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

The figure presents where the frog leaps to (in a single leap) from each and every rock.


title: [POI2010] JED-Ones

description:
Let $x$ be a sequence of zeros and ones.

An utterly forlorn one (UFO) in $x$ is the extreme (either first or last) one    that additionally does not neighbour with any other one.

For instance, the sequence 10001010 has two UFOs,    while the sequence 1101011000 has no UFO,    and the sequence 1000 has only one UFO.

Let us denote the total number of UFOs in the binary representations of the numbers    from 1 to $n$ with $sks(n)$.

For example,    $sks(5)=5$, $sks(64)=59$, $sks(128)=122$, $sks(256)=249$.

We will be working with very large numbers.

```plain
Therefore, we shall represent them in a succinct way.
```
Suppose $x$ is a positive integer and $x_2$ is its binary representation    (starting with 1). Then the succinct representation of $x$ is the sequence    $REP(x)$ consisting of positive integers denoting the lengths of successive    blocks of the same digits.

For example:

$REP(460\ 288)=REP(1110000011000000000_2)=(3,5,2,9)$ $REP(408)=REP(110011000_2)=(2,2,2,3)$

Your task is to write a program that finds the sequence $REP(sks(n))$ given $REP(n)$.

inputFormat:
The first line of the standard input holds one integer $k$  ($1\le k\le 1\ 000\ 000$) denoting the length of the succinct representation      of a positive integer $n$.

The second line of the standard input holds $k$ integers $x_1,x_2,\cdots,x_k$  ($0<x_i\le 1\ 000\ 000\ 000$), separated by single spaces.

The sequence $x_1,x_2,\cdots,x_k$ forms the succinct representation of the number $n$.

You may assume that $x_1+x_2+\cdots+x_k\le 1\ 000\ 000\ 000$, i.e., $0<n<2^{1\ 000\ 000\ 000}$.

outputFormat:
Your program is to print out two lines to the standard output.

The first one should contain a single positive integer $l$.

The second line should hold $l$ positive integers $y_1,y_2,\cdots,y_l$,      separated by single spaces.

The sequence $y_1,y_2,\cdots,y_l$ is to form the succinct representation of $sks(n)$.

translation:
设 $x$ 是一个由 $\texttt{01}$ 组成的序列。一个 UFO 指的是序列中第一个 $1$ 或者最后一个 $1$ 且不和任何一个 $1$ 相邻。例如 $\texttt{10001010}$ 有两个 UFO，$\texttt{1101011000}$ 没有 UFO，$\texttt{1000}$ 只有一个 UFO。

设 $1$ 到 $n$ 的数的二进制表示中 UFO 的总数为 $sks(n)$。例如，$sks(5)=5, sks(64)=59, sks(128)=122, sks(256)=249$.

我们需要处理非常大的数字。因此 $n$ 会用压缩的形式表示。设 $x$ 是一个正整数 $x_2$ 是其二进制表示（最高位为 $1$），则该数的压缩形式 $REP(x)$ 为一个序列，表示连续相同数位的数量。例如：

$$REP(460288)=REP(1110000011000000000_2)=(3,5,2,9)$$

$$REP(408)=REP(110011000_2)=(2,2,2,3)$$

已知 $REP(n)$，求 $REP(sks(n))$。

## 输入格式:
第一行有一个整数 $k$，表示一个正整数 $n$ 的压缩形式。
接下来一行有 $k$ 个整数 $x _ 1, x _ 2, \cdots, x _ k$，用空格分隔，表示 $n$ 的压缩形式的序列。保证 $x _ 1 + x _ 2 + \cdots + x _ k \le 10 ^ 9$，也就是说 $0<n< 2 ^ {10 ^ 9}$。

## 输出格式:
输出两行，第一行有一个正整数 $l$，第二行有 $l$ 个正整数，用空格分隔，表示 $sks(n)$ 的压缩形式。


title: [POI2010] MOS-Bridges

description:
San Bytecisco is a beautifully situated coastal town.

It consists of ![](http://main.edu.pl/images/OI17/mos-en-tex.1.png) small, yet densely populated islands,  numbered from ![](http://main.edu.pl/images/OI17/mos-en-tex.2.png) to ![](http://main.edu.pl/images/OI17/mos-en-tex.3.png).

Certain islands are connected with bridges, used for (bidirectional)  road traffic.

Each pair of islands can be connected with at most one bridge.

The islands are connected in such a way that every island can be reached  from every other by using the bridges only.

Byteasar and Bytie are going for a bike trip in San Bytecisco.

The will start their ride at the island no. 1.

They intend to visit every island, while passing along every bridge once  and ending the trip where it began, i.e., the island no. 1.

Being quite seasoned riders, they expect some serious trouble from... the wind!

After all, it is very windy along the coast, and especially so on the bridges between  the islands. Obviously, depending on its speed and direction, the wind makes it  hard to cross the bridge in different extent for either direction.

For simplicity we will assume for every bridge and direction of crossing,  the opposing wind speed is constant.

Help Byteasar and Bytie to find a route as they desire that will in addition  be the least tiresome. Byteasar and Bytie agreed on the maximum opposing wind speed as  a measure of a route's tiresomeness.

inputFormat: In the first line of the standard input there are two integers separated by a single space: $n$ and $m$ ($2 \le n \le 1000$, $1 \le m \le 2000$), denoting the number of islands and the number of bridges in San Bytecisco respectively. The islands are numbered from 1 to n, while the bridges from 1 to m. The following  lines specify the bridges. The line no.($n+1$)  contains four integers $a_i,b_i,l_i,p_i$ ($1\le l_i,p_i \le 1000$), separated by single spaces. These denote that the bridge no. $i$ connects the islands no. $a$ and $b$. The opposing wind speeds are  when one goes moves from  to , and  if one goes from $a$ to $b$.

outputFormat:
If there is no route satisfying the requirements of the daring two riders,   the first and only line of the standard output should hold the word NIE   (no in Polish).

Otherwise, the output should have two lines, specifying the least tiresome route   over San Bytecisco.

The first line should hold the maximum opposing wind speed for that route, i.e.,   the number we wish to minimize.

The second line should hold ![](http://main.edu.pl/images/OI17/mos-en-tex.28.png) integers, separated by single spaces, giving   the numbers of successive bridges one crosses on the least tiresome route.

Should there be more than one least tiresome route, your program can pick one   arbitrarily.

translation:
给定一个图，边有权值且正着走和逆着走有不同权值，在这个图上求一条最大边权最小的欧拉回路，从点  $1$ 出发，要求输出方案。

第一行包括两个整数  $n$ 和  $m$，分别代表点的个数和边的个数。接下来  $m$ 行每行包括  $4$ 个整数  $a,b,l,p$，分别代表边的两个端点和正着走的权值和逆着走的权值。

如果没有符合要求的路径输出 `NIE`，否则输出两行。第一行一个整数表示最小的权值，第二行  $m$ 个整数表示依次经过的边的编号。

Translated by @Schwarzkopf_Henkal


title: [POI2010] PIL-Pilots

description:
In the Byteotian Training Centre, the pilots prepare for missions requiring extraordinary precision and control.

One measure of a pilot's capability is the duration he is able to fly along a desired route without deviating too much -    simply put, whether he can fly steadily. This is not an easy task, as the simulator is so sensitive that it registers    even a slightest move of the yoke1.

At each moment the simulator stores a single parameter describing the yoke's position.

Before each training session a certain tolerance level ![](http://main.edu.pl/images/OI17/pil-en-tex.1.png) is set.

The pilots' task then is to fly as long as they can in such a way that all the yoke's position measured during the    flight differ by at most ![](http://main.edu.pl/images/OI17/pil-en-tex.2.png). In other words, a fragment of the flight starting at time ![](http://main.edu.pl/images/OI17/pil-en-tex.3.png) and ending at time ![](http://main.edu.pl/images/OI17/pil-en-tex.4.png)    is within tolerance level ![](http://main.edu.pl/images/OI17/pil-en-tex.5.png) if the position measurements, starting with ![](http://main.edu.pl/images/OI17/pil-en-tex.6.png)-th and ending with ![](http://main.edu.pl/images/OI17/pil-en-tex.7.png)-th,    form such a sequence ![](http://main.edu.pl/images/OI17/pil-en-tex.8.png) that for all elements ![](http://main.edu.pl/images/OI17/pil-en-tex.9.png) of this sequence, the inequality ![](http://main.edu.pl/images/OI17/pil-en-tex.10.png) holds.

Your task is to write a program that, given a number ![](http://main.edu.pl/images/OI17/pil-en-tex.11.png) and the sequence of yoke's position measurements,    determines the length of the longest fragment of the flight that is within the tolerance level ![](http://main.edu.pl/images/OI17/pil-en-tex.12.png).

给定 $n, k$ 和一个长度为 $n$ 的序列，求最长的最大值最小值相差不超过 $k$ 的子段。

inputFormat:
In the first line of the standard input two integers are given, ![](http://main.edu.pl/images/OI17/pil-en-tex.13.png) and ![](http://main.edu.pl/images/OI17/pil-en-tex.14.png)      (![](http://main.edu.pl/images/OI17/pil-en-tex.15.png), ![](http://main.edu.pl/images/OI17/pil-en-tex.16.png)), separated by a single space,      denoting the tolerance level and the number of yoke's position measurements taken.

The second line gives those measurements, separated by single spaces. Each measurement      is an integer from the interval from ![](http://main.edu.pl/images/OI17/pil-en-tex.17.png) to ![](http://main.edu.pl/images/OI17/pil-en-tex.18.png).

第一行两个由空格隔开的整数 $k, n$（$0\leq k\leq 2\times 10 ^ 9$，$1\leq n\leq 3\times 10 ^ 6$），$k$ 表示设定的极差的最大值，$n$ 表示序列的长度。

第二行 $n$ 个由空格隔开的整数 $a_i$（$1\leq a_i\leq 2\times 10^ 9$）表示序列。

outputFormat:
Your program should print a single integer to the standard output:

the maximum length of a fragment of the flight that is within the given tolerance level.

一个整数表示符合条件的子段的长度最大值。


title: [POI2011] KON-Conspiracy

description:
Hostile Bitotia launched a sneak attack on Byteotia and occupied a significant part of its territory.

The King of Byteotia, Byteasar, intends to organise resistance movement in the occupied area.

Byteasar naturally started with selecting the people who will form the skeleton of the movement.

They are to be partitioned into two groups:

the conspirators who will operate directly in the occupied territory, and    the support group that will operate inside free Byteotia.

There is however one issue - the partition has to satisfy the following conditions:

Every pair of people from the support group have to know each other - this        will make the whole group cooperative and efficient.

The conspirators must not know each other.

None of the groups may be empty, i.e., there has to be at least one conspirator        and at least one person in the support group.

Byteasar wonders how many ways there are of partitioning selected people into    the two groups.

And most of all, whether such partition is possible at all.

As he has absolutely no idea how to approach this problem, he asks you for help.

inputFormat:
The first line of the standard input holds one integer $n$ ($2\le n\le 5000$),      denoting the number of people engaged in forming the resistance movement.

These people are numbered from 1 to $n$ (for the sake of conspiracy!).

The $n$ lines that follow describe who knows who in the group.

The $i$-th of these lines describes the acquaintances of the person $i$ with a sequence of integers separated by single spaces.

The first of those numbers, $k_i$ ($0\le k_i\le n-1$), denotes the number of acquaintances of the person $i$.

Next in the line there are $k_i$ integers $a_{i,1},a_{i,2},\cdots,a_{i,k_i}$ - the numbers of $i$'s acquaintances.The numbers $a_{i,j}$ are given in increasing order and satisfy $1\le a_{i,j}\le n$,$a_{i,j}\ne i$. You may assume that if $x$ occurs in the sequence $a_i$ (i.e., among $i$'s acquaintances), then also $i$ occurs in the sequence $a_x$(i.e., among $x$'s acquaintances).

outputFormat:
In the first and only line of the standard output your program should print out one integer:

the number of ways to partition selected people into the conspirators and the support group.

If there is no partition satisfying aforementioned conditions, then 0 is obviously the right answer.

translation:
## 描述

Byteotia的领土被占领了，国王Byteasar正在打算组织秘密抵抗运动。国王需要选一些人来进行这场运动，而这些人被分为两部分：一部分成为同谋者活动在被占领区域，另一部分是后勤组织在未被占领的领土上运转。但是这里出现了一个问题：

1. 后勤组织里的任意两人都必须是熟人，以促进合作和提高工作效率。
2. 同谋者的团体中任意两人都不能是熟人。
3. 每一部分都至少要有一个人。国王想知道有多少种分配方案满足以上条件，当然也有可能不存在合理方案。

现在国王将这个问题交由你来解决！

## 输入

第一行一个整数n（2<=n<=5000）表示有n个人参与该抵抗运动，标号为1..n。

 之后有n行，第i行的第一个数ki（0<=ki<=n-1）表示i认识ki个人,随后的ki个数表示i的熟人。

输入满足如果i是x的熟人，x会在i的序列中出现同时i也会出现在x的熟人序列中。

## 输出

符合条件的方案总数。