title: [POI2011] LIZ-Lollipop

description:
Byteasar runs a confectionery in Byteburg.

Strawberry-vanilla flavoured lollipops are the favourite of local children.

These lollipops are composed of multiple segments of the same length, each    segment of either strawberry or vanilla flavour.

The price of the lollipop is the sum of the values of its segments, where    a vanilla segment costs one bythaler, while a strawberry segments costs two.

Fig. 1: An exemplary lollipop of five segments,      three strawberry flavoured and two vanilla, alternately.

The price of this lollipop is $8$ bythalers.

Currently Byteasar is left with only one lollipop, though possibly very long.

As a salesman, he knows only too well that probably no one will want to buy    the whole lollipop. For this reason he thinks of breaking the lollipop at the    joints of the segments in order to get a shorter lollipop. Each fragment for    sale, of course, must stay in one piece.

Byteasar vast experience of a salesman, as well as his understanding of children    psychology, tell him that his young customers will most likely want to spend    all their money on a single lollipop. With this in mind, he wonders for which    values of $k$ the lollipop he has can be broken down in such a way that as a    result one would get, among other pieces, a lollipop worth exactly $k$  bythalers.

Naturally, he is interested in the way of breaking the lollipop as well.

As this task overwhelms him, he asks you for help.

inputFormat:
In the first line of the standard input there are two integers $n$ and $m$      ($1\le n,m \le 1\ 000\ 000$), separated by a single space.

These denote, respectively, the number of segments of the last lollipop left      in store, and the number of values of $k$ to consider.

The lollipop's segments are numbered from 1 to $n$.

The second line gives an $n$-letter description of the lollipop, consisting      of letters T and W, where T denotes a strawberry flavoured segment, while W - vanilla flavoured;the $i$-th of these letters specifies the flavour of the $i$-th segment.

In the following $m$ lines successive values of $k$($1\le k\le 2\ 000\ 000$) to consider are given, one per line.

outputFormat:
Your program should print out exactly $m$ lines, giving, one per line,      the results for successive values of $k$, to the standard output.

If for a given value of $k$ it is impossible to break the lollipop in such a way that there is a contiguous fragment worth exactly $k$ bythalers, then the word      NIE (no in Polish) should be printed. Otherwise, two integers $l$ and $r$ ($1\le l\le r\le n$), separated by single spaces, should      be printed, such that the fragment of the lollipop composed of the segments      numbered from $l$ to $r$ inclusively is worth exactly $k$ bythalers. If there are multiple such pairs, your program is free to choose one arbitrarily.

translation:
给一个只有 $1$ 和 $2$ 的序列，每次询问有没有一个子串的和为 $x$。

### 输入格式

第一行两个整数 $n, m$（$1 \le n, m \le 10 ^ 6$）。

第二行一个长为 $n$ 的只含 $\texttt T$ 和 $\texttt W$ 的字符串，$\texttt T$ 代表 $2$，$\texttt W$ 代表 $1$。

接下来 $m$ 行，每行一个整数 $x$（$1 \le x \le 2\times 10 ^ 6$）表示一次询问。

### 输出格式

$m$ 行，如果有解则输出两个整数 $l, r$ 表示区间 $[l, r]$ 的和是 $x$，如果无解则输出字符串 `NIE`。

hint:
SPJ 对于格式的要求较为严格。对于每个询问后，应紧跟一个换行符。在最后一次输出你的答案以及一个换行符后不应有任何输出。

由 zhouyonglong 提供 SPJ。


title: [POI2011] Lightning Conductor

type: P

description:
Progressive climate change has forced the Byteburg authorities to build a huge lightning conductor    that would protect all the buildings within the city.

These buildings form a row along a single street, and are numbered from ![](http://main.edu.pl/images/OI18/pio-en-tex.1.png) to ![](http://main.edu.pl/images/OI18/pio-en-tex.2.png).

The heights of the buildings and the lightning conductor are non-negative integers.

Byteburg's limited funds allow construction of only a single lightning conductor.

Moreover, as you would expect, the higher it will be, the more expensive.

The lightning conductor of height ![](http://main.edu.pl/images/OI18/pio-en-tex.3.png) located on the roof of the building ![](http://main.edu.pl/images/OI18/pio-en-tex.4.png) (of height ![](http://main.edu.pl/images/OI18/pio-en-tex.5.png))    protects the building ![](http://main.edu.pl/images/OI18/pio-en-tex.6.png) (of height ![](http://main.edu.pl/images/OI18/pio-en-tex.7.png)) if the following inequality holds:

![](http://main.edu.pl/images/OI18/pio-en-tex.8.png)        where ![](http://main.edu.pl/images/OI18/pio-en-tex.9.png) denotes the absolute value of the difference between ![](http://main.edu.pl/images/OI18/pio-en-tex.10.png) and ![](http://main.edu.pl/images/OI18/pio-en-tex.11.png).

Byteasar, the mayor of Byteburg, asks your help.

Write a program that, for every building ![](http://main.edu.pl/images/OI18/pio-en-tex.12.png), determines the minimum height    of a lightning conductor that would protect all the buildings if it were put    on top of the building ![](http://main.edu.pl/images/OI18/pio-en-tex.13.png).

inputFormat:
In the first line of the standard input there is a single integer    ![](http://main.edu.pl/images/OI18/pio-en-tex.14.png) (![](http://main.edu.pl/images/OI18/pio-en-tex.15.png)) that denotes the number of buildings in Byteburg.

Each of the following ![](http://main.edu.pl/images/OI18/pio-en-tex.16.png) lines holds a single integer ![](http://main.edu.pl/images/OI18/pio-en-tex.17.png) (![](http://main.edu.pl/images/OI18/pio-en-tex.18.png))    that denotes the height of the ![](http://main.edu.pl/images/OI18/pio-en-tex.19.png)-th building.

outputFormat:
Your program should print out exactly ![](http://main.edu.pl/images/OI18/pio-en-tex.20.png) lines to the standard output.

The ![](http://main.edu.pl/images/OI18/pio-en-tex.21.png)-th line should give a non-negative integer ![](http://main.edu.pl/images/OI18/pio-en-tex.22.png) denoting the minimum    height of the lightning conductor on the ![](http://main.edu.pl/images/OI18/pio-en-tex.23.png)-th building.

translation:
给定一个长度为 $n$ 的序列 $\{a_n\}$，对于每个 $i\in [1,n]$ ，求出一个最小的非负整数 $p$ ，使得 $\forall j\in[1,n]$，都有 $a_j\le a_i+p-\sqrt{|i-j|}$

$1 \le n \le 5\times 10^{5}$，$0 \le a_i \le 10^{9}$ 。

tags: 凸完全单调性, wqs 二分


title: [POI2011] PRZ-Shift

description:
Byteasar bought his son Bytie a set of blocks numbered from $1$ to $n$ and arranged them in a row in a certain order.

Bytie's goal is to rearrange the blocks so that they are ordered naturally, from the smallest number to the largest.

However, the only moves Bytie is allowed to make are:

putting the last block at the very beginning (move a), and                  putting the third block at the very beginning (move b).

Help Bytie by writing a program that tells whether a given arrangement of    blocks can be properly reordered, and tells the right sequence of moves if it is.

inputFormat:
In the first line of the standard input there is a single integer $n$, $1\le n\le 2\ 000$.

In the second line there are $n$ integers from the range $1$ to $n$, separated by single spaces.

No number appears twice, and thus they represent the initial arrangement of the blocks.

outputFormat:
If there is no sequence of moves leading to an arrangement with increasing blocks' numbers, your program should print out "NIE DA SIE" (there is no way in Polish), without the quotation marks.

Otherwise there should be a single integer $m$ ($m\le n^2$), denoting the number of operations, in the first line.

An operation is a $k$-fold execution of either a or b move.

If $m>0$, then there should be a sequence of $m$ integers with either a or b appended in the second line.

Thus $k$a (for $0<k<n$) denotes the $k$-fold execution of the move a.

Analogously, $k$b (for $0<k<n$) denotes the $k$-fold execution of the move b.

Furthermore, the characters appended to the numbers in the second line have to alternate.

Should there be more than one solution, your program is free to pick one arbitrarily.

hint:
有一个1..n的排列，有两种操作：

(a) 将最后一个数移到最前面

(b) 把第三个数移到最前面

我们将连续进行k次同一个操作称为“一块操作”，表示为ka或kb。

找到一个操作序列使得进行这些操作后，排列变为1,2,3,…,n。

无解输出 `NIE DA SIE`

感谢cn：苏卿念 提供spj


title: [POI2011] WYK-Plot

description:
We call any sequence of points in the plane a plot.

We intend to replace a given plot $(P_1,\cdots,P_n)$ with another that will    have at most $m$ points ($m\le n$) in such a way that it "resembles" the    original plot best.

The new plot is created as follows. The sequence of points $P_1,\cdots,P_n$ can be partitioned into $s$ ($s\le m$) contiguous subsequences:

$(P_{k_0+1},\cdots,P_{k_1}),(P_{k_1+1},\cdots,P_{k_2}),\cdots,(P_{k_{s-1}+1},\cdots,P_{k_s})$ where $0=k_0<k_1<k_2<\cdots<k_s=n$,and afterwards each subsequence $(P_{k_{i-1}+1},\cdots,P_{k_i})$, for $i=1,\cdots,s$,is replaced by a new point $Q_i$.

In that case we say that each of the points $P_{k_{i-1}+1},\cdots,P_{k_i}$ has been contracted to the point $Q_i$.

As a result a new plot, represented by the points $Q_1,\cdots,Q_s$, is created.

The measure of such plot's resemblance to the original is the maximum distance of all the points $P_1,\cdots,P_n$ to the point it has been contracted to:

$max_{i=1,\cdots,s}(max_{j=k_{i-1}+1,\cdots,k_i}(d(P_j,Q_i)))$    where $d(P_j,Q_i)$ denotes the distance between $P_j$ and $Q_i$, given by the well-known formula:

$d((x_1,y_1),(x_2,y_2))=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

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

An exemplary plot $P_1,\cdots,P_7$ and the new plot $(Q_1,Q_2)$, where $(P_1,\cdots,P_4)$ are contracted to $Q_1$, whereas $(P_5,P_6,P_7)$ to $Q_2$.

For a given plot consisting of $n$ points, you are to find the plot that    resembles it most while having at most $m$ points,    where the partitioning into contiguous subsequences is arbitrary.

Due to limited precision of floating point operations, a result is deemed    correct if its resemblance to the given plot is larger than the optimum    resemblance by at most $0.000001$.

给定n个点，要求把n个点分成不多于m段，使得求出每段的最小覆盖圆的半径后，最大的半径最小。

inputFormat:
In the first line of the standard input there are two integers $n$ and $m$,      $1\le m\le n\le 100\ 000$, separated by a single space.

Each of the following $n$ lines holds two integers, separated by a single space.

The $(i+1)$-th line gives $x_i$,$y_i$,$-1\ 000\ 000\le x_i,y_i\le 1\ 000\ 000$ denoting the coordinates $(x_i,y_i)$ of the point $P_i$.

outputFormat:
In the first line of the standard output one real number $d$ should be printed out,      the resemblance measure of the plot found to the original one.

In the second line of the standard output there should be another integer $s$, $1\le s\le m$.

Next, the following $s$ lines should specify the coordinates of the points $Q_1,\cdots,Q_s$,one point per line.

Thus the $(i+2)$-th line should give two real numbers $u_i$ and $v_i$,      separated by a single space, that denote the coordinates $(u_i,v_i)$ of the point $Q_i$.All the real numbers should be printed with at most 15 digits after the decimal point.


title: [POI2011] SEJ-Strongbox

description:
Byteasar is a famous safe-cracker, who renounced his criminal activity and    got into testing and certifying anti-burglary devices.

He has just received a new kind of strongbox for tests: a combinatorial safe.

A combinatorial safe is something different from a combination safe,    even though it is opened with a rotary dial.

The dial can be set in $n$ different positions, numbered from 0 to $n-1$.

Setting the dial in some of these positions opens the safe, while in others it does not.

And here is the combinatorial property, from which the name comes from:

if $x$ and $y$ are opening positions, then so is $(x+y)\ mod\ n$ too;    note that is holds for $x=y$ as well.

Byteasar tried $k$ different positions of the dial: $m_1,m_2,\cdots,m_k$.

The positions $m_1,m_2,\cdots,m_{k-1}$ did not open the safe,only the last position $m_k$ did.

Byteasar is already tired from checking these $k$ positions and has thus    absolutely no intention of trying the remaining ones.

He would like to know however, based on what he already knows about the    positions he tried, what is the maximum possible number of positions that    open the safe.

Help him by writing an appropriate program!

inputFormat:
The first line of the standard input gives two integers $n$ and $k$,      separated by a single space, $1\le k\le 250\ 000$, $k\le n\le 10^{14}$.

The second line holds $k$ different integers, also separated by single      spaces, $m_1,m_2,\cdots,m_k$, $0\le m_i<n$.

You can assume that the input data correspond to a certain combinatorial      safe that complies with the description above.

In tests worth approximately 70% of the points it holds that $k\le 1\ 000$.

In some of those tests, worth approximately 20% of the points,      the following conditions hold in addition: $n\le 10^8$ and $k\le 100$.

outputFormat: Your program should print out to the first and only line of the standard output a single integer: the maximum number of the dial's positions that can open the safe.

translation:
有一个密码箱，$0$ 到 $n-1$ 中的某些整数是它的密码。且满足：若 $a$ 和 $b$ 是它的密码，则 $(a+b)\bmod n$ 也是它的密码（$a$，$b$ 可以相等）。某人试了 $k$ 次密码，前 $k-1$ 次都失败了，最后一次成功了。

问，该密码箱最多有多少种不同的密码。

## 输入格式

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

第二行为 $k$ 个非负整数，表示每次试的密码。

## 输出格式

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


title: [POI2011] ROZ-Difference

description:
A word consisting of ![](http://main.edu.pl/images/OI18/roz-en-tex.1.png) lower-case letters of the English alphabet ('a'-'z') is given.

We would like to choose a non-empty contiguous (i.e. one-piece) fragment    of the word so as to maximise the difference in the number of occurrences    of the most and the least frequent letter in the fragment.

We are assuming that the least frequent letter has to occur at least once in    the resulting fragment.

In particular, should the fragment contain occurrences of only one letter,    then the most and the least frequent letter in it coincide.

inputFormat:
The first line of the standard input holds one integer ![](http://main.edu.pl/images/OI18/roz-en-tex.2.png)      (![](http://main.edu.pl/images/OI18/roz-en-tex.3.png)) that denotes the length of the word.

The second line holds a word consisting of ![](http://main.edu.pl/images/OI18/roz-en-tex.4.png) lower-case letters      of the English alphabet.

In tests worth at least 30% of the points it additionally holds that ![](http://main.edu.pl/images/OI18/roz-en-tex.5.png).

outputFormat: The first and only line of the standard output is to hold a single integer,      equal to the maximum difference in the number of occurrences of the most      and the least frequent letter that is attained in some non-empty contiguous      fragment of the input word.

translation:
给一个字符串，求其中的一段，使得出现次数最多的字符与出现次数最少的字符的出现次数之差最大。

$1 \leq N \leq 10^6$。


title: [POI2011] SMI-Garbage

description:
有一个可以看成无向图的城市，上面有 $n$ 个点和 $m$ 条边。

每一天，有若干辆垃圾车按照**环形**来跑一圈。并且，**对于一辆垃圾车，** 除了起点以外不能跑两次。

一条路有 $2$ 种状态：清洁的（用 `0` 表示）或不清洁的（用 `1` 表示）。每次垃圾车经过，都会改变这条路的状态。

因为有些路上的人不交垃圾清理费，所以市长想要那些路变得不清洁；除此之外的路要清洁。那么，如何安排垃圾车，才能使得市长目的达到呢？

By @[dengziyue](/user/387840)

感谢 @cn：苏卿念 提供SPJ

inputFormat:
输入的第一行包含两个空格分隔的正整数 $n$ 和 $m$ $（ 1 \leqslant n \leqslant 100000，1 \leqslant m \leqslant 1000000）$，表示图的点数和边数。

接下来 $m$ 行，每行包含四个空格分隔的正整数 $a,b,s,t $（ $1 \leqslant a \leqslant b \leqslant n $ , $s，t \in \lbrace0,1\rbrace$  ） ，表示一条联结结点 $a$ 与 $b$ 的边，初始颜色和目标颜色分别为 $s$ 与 $t$ 。

你可以认为若存在合法方案，则存在一个卡车经过总边数不超过 $5m$ 的方案。

对于 $60\%$ 分数的数据，有 $ m \leqslant 10000$。

outputFormat:
如果不存在合法方案，输出一行 `NIE`（波兰语「否」）；

否则按下列格式输出任意一种方案：

- 第一行包含一个整数 $k$，表示卡车行驶环路的总数；
- 接下来 $k$ 行，每行描述一条环路：
   - 首先是一个正整数 $k_i$ 表示环路经过的边数，后接一个空格；
  - 接下来 $ k_i + 1 $ 个空格分隔的整数，依次表示环路上结点的编号。


title: [POI2011] ROT-Tree Rotations

description:
给定一颗有 $n$ 个**叶节点**的二叉树。每个叶节点都有一个权值 $p_i$（注意，根不是叶节点），所有叶节点的权值构成了一个 $1 \sim n$ 的排列。
对于这棵二叉树的任何一个结点，保证其要么是叶节点，要么左右两个孩子都存在。
现在你可以任选一些节点，交换这些节点的左右子树。
在最终的树上，按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 $n$ 的排列，你需要最小化这个排列的逆序对数。

inputFormat:
第一行是一个整数 $n$，表示树的叶节点个数。
接下来若干行，使用递归的形式来读入这棵树，读入任意一个子树的信息时，初始时读入其根节点。对于一个结点 $u$，首先有一行一个整数 $x$。
- 若 $x \neq 0$，则表示 $u$ 是一个叶节点，其权值为 $x$。
- 若 $x = 0$，则表示 $u$ 不是叶节点，则接下来若干行读入其左子树信息，左子树读入结束后接下来若干行读入其右子树信息。

outputFormat: 输出一行一个整数表示最小的逆序对数。

hint:
### 样例 1 解释

下图中，左图是初始读入的树，右图是操作后的树。

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

### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n \leq 5 \times 10^3$。
- 对于 $100\%$ 的数据，保证 $2 \leq n \leq 2 \times 10^5$， $0 \leq x \leq n$，所有叶节点的权值是一个 $1 \sim n$ 的排列。

### 提示

请注意，$n$ **不是**树的结点个数。


title: [POI2011] TEM-Temperature

description:
The Byteotian Institute of Meteorology (BIM) measures the air temperature  daily.

The measurement is done automatically, and its result immediately printed.

Unfortunately, the ink in the printer has long dried out...

The employees of BIM however realised the fact only recently, when the    Byteotian Organisation for Meteorology (BOM) requested access to that data.

An eager intern by the name of Byteasar saved the day, as he systematically    noted down the temperatures reported by two domestic alcohol thermometers    placed on the north and south outside wall of the BIM building.

It was established decades ago by various BIM employees that the temperature    reported by the thermometer on the south wall of the building is never lower    than the actual temperature, while that reported by the thermometer on the    north wall of the building is never higher than the actual temperature.

Thus even though the exact temperatures for each day remain somewhat of    a mystery, the range they were in is known at least.

Fortunately for everyone involved (except Byteasar and you, perhaps),    BOM does not require exact temperatures. They only want to know the longest    period in which the temperature was not dropping (i.e. on each successive    day it was no smaller than on the day before).

In fact, the veteran head of BIM knows very well that BOM would like this    period as long as possible.

To whitewash the negligence he insists that Byteasar determines, based on    his valuable notes, the longest period in which the temperature    could have been not dropping.

Now this is a task that Byteasar did not quite expect on his BIM internship,    and he honestly has no idea how to tackle it.

He asks you for help in writing a program that determines the longest such    period.

某国进行了连续 $ n $ ( $ 1 \le n \le 1,000,000 $）天的温度测量，测量存在误差，测量结果是第 $i$ 天温度在 $[l_i,r_i]$ 范围内。

求最长的连续的一段，满足该段内可能温度不降。

inputFormat:
In the first line of the standard input there is one integer  $ n $ ( $ 1 \le n \le 1,000,000 $) that denotes the number of days for which Byteasar took notes on the temperature. The measurements from day are given in the  $ {(i + 1)}$-th line . Each of those lines holds two integers,  $ x $ and  $ y $ ( $ -10^9 \le x \le y \le 10^9 $). These denote, respectively, the minimum and maximum possible temperature on that particular day, as reported by the two thermometers.

In some of the tests, worth 50 points in total, the temperatures never drop below  $ -50 $ degrees (Celsius, in case you wonder!) and never exceeds  $ 50 $ degrees ( $ -50 \le x \le y \le 50 $).

outputFormat: In the first and only line of the standard output your program should print a single integer, namely the maximum number of days for which the temperature in Byteotia could have been not dropping.


title: [POI2011] DYN-Dynamite

description:
The Byteotian Cave is composed of $n$ chambers and $n-1$ corridors that       connect them.  For every pair of chambers there is unique way to move       from one of them to another without leaving the cave.

Dynamite charges are set up in certain chambers.

A fuse is laid along every corridor.

In every chamber the fuses from the adjacent corridors meet at one point,       and are further connected to the dynamite charge if there is one in the       chamber.  It takes exactly one unit of time for the fuse between two       neighbouring chambers to burn, and the dynamite charge explodes in the       instant that fire reaches the chamber it is inside.

We would like to light the fuses in some $m$ chambers (at the joints of       fuses) in such a way that all the dynamite charges explode in the shortest       time possible since the fuses are lit.  Write a program that will determine       the minimum such time possible.

inputFormat:
The first line of the standard input holds two integers $n$ and $m$($1\le m\le n\le 300\ 000$), separated by a single space, that denote, respectively, the number of chambers in the cave and the number of chambers in which fire can be set to the fuses.

The chambers are numbered from 1 to $n$.

The next line contains $n$ integers $d_1,d_2,\cdots,d_n$ ($d_i\in \{0,1\}$), separated by single spaces.

If $d_i=1$, then there is dynamite in the $i$-th chamber, and if $d_i=0$, there is none.The following $n-1$ lines specify the corridors of the cave. Each of them holds two integers $a,b$($1\le a<b\le n$), separated by a single space, denoting that there is a corridor connecting the chambers $a$ and $b$. Every corridor appears exactly once in the description.

You may assume that in tests worth 10% of the points it holds additionally that $n\le 10$ , while in tests worth 40% of the points it holds that $n\le 1\ 000$

outputFormat: The first and only line of the standard output should hold a single         integer, equal to the minimum time it takes from lighting the fuses         to the explosion of all the charges.

translation: 给一棵树，树上有一些关键节点，要求你选 $m$ 个点，第 $i$ 个关键节点到这些点中每个点距离的最小值记为 $dis_i$，记这全部 $dis$ 的最大值为 $K$，现在要使 $K$ 最小，求这个 $K$。


title: [POI2011] IMP-Party

description:
```plain
Byteasar intends to throw up a party.
```
Naturally, he would like it to be a success.  Furthermore, Byteasar is quite certain that to make it so it suffices if all invited guests  know each other.  He is currently trying to come up with a list of his friends he would like to invite.

Byteasar has $n$ friends, where $n$ is divisible by 3.

```plain
Fortunately, most of Byteasar's friends know one another.
```
Furthermore, Byteasar recalls that he once attended a party where there were $\frac{2}{3}n$ of his friends, and where everyone knew everyone else.

Unfortunately, Byteasar does not quite remember anything else from that    party.

In particular, he has no idea which of his friends attended it.

Byteasar does not feel obliged to throw a huge party, but he would like to    invite at least \frac{n}{3} of his friends.

He has no idea how to choose them, so he asks you for help.

给定一张n个点m条边的图$n\equiv 0(mod\ 3)$，保证存在一个大小为$\frac{2}{3}n$的团，要求输出一个大小为$\frac{n}{3}$的团

inputFormat:
In the first line of the standard input two integers, $n$ and $m$ ($3\le n\le 3\ 000$, $\frac{\frac{2}{3}n(\frac{2}{3}n-1)}{2}\leq m\leq \frac{n(n-1)}{2}$), are given,separated by a single space.  These denote the number of Byteasar's friends and the number of pairs of his friends who know each other, respectively.

Byteasar's friends are numbered from 1 to $n$.

Each of the following $m$ lines holds two integers separated by a single      space.

The numbers in line no. $i+1$ (for $i=1,2,...,m$) are $a_i$ and $b_i$($1\le a_i<b_i\le n$), separated by a single space, which denote that the persons $a_i$ and $b_i$ know each other. Every pair of numbers appears at most once on the input.

outputFormat: In the first and only line of the standard output your program should      print $\frac{n}{3}$ numbers, separated by single spaces, in increasing      order.  These number should specify the numbers of Byteasar's friends whom      he should invite to the party.  As there are multiple solutions, pick one      arbitrarily.

hint:
给定一张n个点m条边的图$n\equiv 0(mod\ 3)$，保证存在一个大小为$\frac{2}{3}n$的团，要求输出一个大小为$\frac{n}{3}$的团

样例图：

![](http://main.edu.pl/images/OI18/impzad1.gif)

由@zhouyonglong提供SPJ


title: [POI2011] INS-Inspection

description:
The railway network of the Byteotian Railways (BR) consists of bidirectional    tracks connecting certain pairs of stations.

Each pair of stations is connected by at most one segment of tracks.

Furthermore, there is a unique route from every station to every other station.

(The route may consist of several segments of tracks, but it may not pass through any station more than once.) Byteasar is an undercover inspector of the BR.

His job is to pick one of the stations (denote it by $S$) for centre of his operations and to travel to all other stations.

His journey should be as follows:

Byteasar starts in station $S$.

Next, he picks one of the stations he did not yet control and goes to it along the shortest path (by train, of course), inspects the station, and        then goes back to $S$.

The crooked employees of BR warn one another of Byteasar's comings.

To deceive them, Byteasar picks the next station for control in such a way that he sets off from the station $S$ in different direction than the last time, i.e., along a different segment of tracks leaving from $S$.

Each station (except $S$) is inspected exactly once.

After inspecting the last station Byteasar does not come back        to $S$.

The travel time along every segment of tracks takes the same amount of time:

one hour.

Byteasar intends to consider all the stations as the initial station $S$.

For each of them he wants to know the order of inspecting the remaining stations that minimises the total travel time, provided that it is possible at all for that particular $S$.

inputFormat:
The first line of the standard input contains a single integer $n$($1\le n\le 1\ 000\ 000$) that denotes the number of stations.

These are numbered from 1 to $n$.

The following $n-1$ lines specify the track segments, one per line.

Each of them holds two integers $a,b$ ($1\le a,b\le n$, $a\ne b$),      separated by a single space, indicating that there is a track segment      connecting the stations $a$ and $b$.

Each track segments appears exactly once in the description.

In tests worth at least 30% of the points it holds additionally that $n\le 2\ 000$.

outputFormat:
Your program should print $n$ lines on the standard output,each holding a single integer.

The one in the $i$-th line should be the minimum number of hours Byteasar has to spend travelling to inspect the stations when $S=i$ - if inspecting them all is possible for $S=i$;if it is not, the $i$-th line should hold the number $-1$.

translation:
一棵 $n$ 个节点的树，行动中心 $S$ 从 $1$ 至 $N$。从 $S$ 出发前往任意一个未标记到的点（沿树上两点的唯一路径走），标记该节点，然后返回 $S$。相邻两次行动所经过的道路不允许有重复，最后一次标记后不需要返回，求路程总和的最小值。

第 $i$ 行输出行动中心为 $i$ 时的答案，如果不可能则输出 $-1$。


title: [POI2011] OKR-Periodicity

description:
Byteasar, the king of Bitotia, has ordained a reform of his subjects' names.

The names of Bitotians often contain repeating phrases,    e.g., the name Abiabuabiab has two occurrences of the phrase    abiab.  Byteasar intends to change the names of his subjects to    sequences of bits matching the lengths of their original names.

Also, he would very much like to reflect the original repetitions in the new    names.

In the following, for simplicity, we will identify the upper- and lower-case    letters in the names.  For any sequence of characters (letters or bits)    ![](http://main.edu.pl/images/OI18/okr-en-tex.1.png) we say that the integer ![](http://main.edu.pl/images/OI18/okr-en-tex.2.png) (![](http://main.edu.pl/images/OI18/okr-en-tex.3.png)) is    a period of ![](http://main.edu.pl/images/OI18/okr-en-tex.4.png) if ![](http://main.edu.pl/images/OI18/okr-en-tex.5.png) for all ![](http://main.edu.pl/images/OI18/okr-en-tex.6.png).

We denote the set of all periods of ![](http://main.edu.pl/images/OI18/okr-en-tex.7.png) by ![](http://main.edu.pl/images/OI18/okr-en-tex.8.png).

For example, ![](http://main.edu.pl/images/OI18/okr-en-tex.9.png), ![](http://main.edu.pl/images/OI18/okr-en-tex.10.png),    and ![](http://main.edu.pl/images/OI18/okr-en-tex.11.png).

Byteasar has decided that every name is to be changed to a sequence of bits    that:

has length matching that of the original name,                  has the same set of periods as the original name,                  is the smallest (lexicographically1)        sequence of bits satisfying the previous conditions.

For example, the name ABIABUABIAB should be changed to    01001101001, BABBAB to 010010, and    BABURBAB to 01000010.

Byteasar has asked you to write a program that would facilitate the    translation of his subjects' current names into new ones.

If you succeed, you may keep your current name as a reward!

inputFormat:
In the first line of the standard input there is a single integer ![](http://main.edu.pl/images/OI18/okr-en-tex.12.png)      - the number of names to be translated (![](http://main.edu.pl/images/OI18/okr-en-tex.13.png)).

The names are given in the following lines, one in each line.

Each name consists of no less than ![](http://main.edu.pl/images/OI18/okr-en-tex.14.png) and no more than ![](http://main.edu.pl/images/OI18/okr-en-tex.15.png)      upper-case (capital) letters (of the English alphabet).

In the test worth 30% of the points each name consists of at most ![](http://main.edu.pl/images/OI18/okr-en-tex.16.png)      letters.

outputFormat:
Your program should print ![](http://main.edu.pl/images/OI18/okr-en-tex.17.png) lines to the standard output.

Each successive line should hold a sequence of zeroes and ones      (without spaces in between) corresponding to the names given on the input.

If an appropriate sequence of bits does not exists for some names, then      "XXX" (without quotation marks) should be printed for that name.

translation:
给定一个字符串 $S$，其长度为 $N$。

定义 $\textrm{Per}(S)$ 为 $S$ 的所有周期的集合。

多组数据，每次给一个 $S$，要求你构造一个 $01$ 串使得其 $\textrm{Per}$ 集合与 $S$ 相同。如果有多种答案，输出字典序最小的一种。

$T \leq 20$，$|S| \leq 2 \times 10^5$。


title: [POI2011] MET-Meteors

description:
Byteotian Interstellar Union (BIU) has recently discovered a new planet in a nearby galaxy.  The planet is unsuitable for colonisation due to strange  meteor showers, which on the other hand make it an exceptionally interesting  object of study.

The member states of BIU have already placed space stations close to the  planet's orbit.  The stations' goal is to take samples of the rocks flying by.

The BIU Commission has partitioned the orbit into $m$ sectors, numbered  from $1$ to $m$, where the sectors $1$ and $m$ are adjacent.  In each sector  there is a single space station, belonging to one of the $n$ member states.

Each state has declared a number of meteor samples it intends to gather before  the mission ends.  Your task is to determine, for each state, when it can  stop taking samples, based on the meter shower predictions for the years to  come.

inputFormat:
The first line of the standard input gives two integers, $n$ and $m$ ($1\le n,m\le 300\ 000$), separated by a single space, that denote,respectively, the number of BIU member states and the number of sectors    the orbit has been partitioned into.

In the second line there are $m$ integers $o_i$ ($1\le o_i\le n$),separated by single spaces, that denote the states owning stations in    successive sectors.

In the third line there are $n$ integers $p_i$ ($1\le p_i\le 10^9$),separated by single spaces, that denote the numbers of meteor samples that the successive states intend to gather.

In the fourth line there is a single integer $k$ ($1\le k\le 300\ 000$) that denotes the number of meteor showers predictions. The following $k$ lines specify the (predicted) meteor showers chronologically. The $i$-th of these lines holds three integers $l_i,r_i,a_i$ (separated by single spaces), which denote that a meteor shower is expected in sectors $l_i,l_{i+1},...,r_i$(if $l_i\le r_i$) or sectors $l_i,l_{i+1},...,m,1,...,r_i$ (if $l_i>r_i$) , which should provide each station in those sectors with $a_i$ meteor samples ($1\le a_i\le 10^9$).

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

The $i$-th of them should contain a single integer $w_i$, denoting the number of shower after which the stations belonging to the $i$-th state are    expected to gather at least $p_i$ samples, or the word NIE (Polish for no) if that state is not expected to gather enough samples in the foreseeable future.

translation:
Byteotian Interstellar Union

有 $n$ 个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为 $m$ 份（第 $m$ 份和第 $1$ 份相邻），第 $i$ 份上有第 $a_i$ 个国家的太空站。

这个星球经常会下陨石雨。BIU 已经预测了接下来 $k$ 场陨石雨的情况。

BIU 的第 $i$ 个成员国希望能够收集 $p_i$ 单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

#### 输入格式

第一行是两个数 $n,m$。

第二行有 $m$ 个数，第 $i$ 个数 $o_i$ 表示第 $i$ 段轨道上有第 $o_i$ 个国家的太空站。

第三行有 $n$ 个数，第 $i$ 个数 $p_i$ 表示第 $i$ 个国家希望收集的陨石数量。

第四行有一个数 $k$，表示 BIU 预测了接下来的 $k$ 场陨石雨。 接下来 $k$ 行，每行有三个数 $l_i,r_i,a_i$ ，表示第 $k$ 场陨石雨的发生地点在从 $l_i$ 顺时针到 $r_i$ 的区间中（如果 $l_i \leq r_i$，则是 $l_i, l_i + 1
\cdots, r_i$，否则就是 $l_i, l_i + 1,
\cdots m - 1, m, 1, 2, \cdots r_i$），向区间中的每个太空站提供 $a_i$ 单位的陨石样本。

#### 输出格式

输出 $n$ 行。第 $i$ 行的数 $w_i$ 表示第 $i$ 个国家在第 $w_i$ 波陨石雨之后能够收集到足够的陨石样本。如果到第 $k$ 波结束后仍然收集不到，输出 `NIE`。

#### 数据范围

$1\le n,m,k\le 3\cdot10^5$；

$1\le p_i,a_i\le 10^9$；


title: [POI2011] PAT-Sticks

description:
Little Johnny was given a birthday present by his grandparents.

This present is a box of sticks of various lengths and colours.

Johnny wonders if there are three sticks in the set he has been given    that would form a triangle with different-coloured sides.

Let us note that Johnny is interested in non-degenerate triangles only, i.e.,    those with positive area.

给你每根木棍的长度和颜色，求一个能拼成三角形且木棍颜色互不相同的方案

inputFormat:
In the first line of the standard input an integer $k$ ($3\le k\le 50$) is given, which is the number of different colours of sticks.

The colours themselves are numbered from $1$ to $k$.

The following $k$ lines contain descriptions of the sticks of particular      colours.

The line no. $i+1$ holds integers that describe the sticks of colour $i$,separated by single spaces.

The first of these numbers, $n_i$ ($1\le n_i\le 1\ 000\ 000$), denotes the number of sticks of colour $i$.

It is followed, in the same line, by $n_i$ integers denoting the lengths of the sticks of colour $i$.All lengths are positive and do not exceed $1\ 000\ 000\ 000$.Furthermore, the total number of all sticks does not exceed $1\ 000\ 000$.

outputFormat:
Your program should print (on the first and only line of the standard output) either:

six integers, separated by single spaces, that describe the construction          of a triangle with different-coloured sides as follows:

the colour and the length of the first stick, the colour and the length          of the second stick, and the colour and the length of the third stick,                      or the word NIE (Polish for no) if no such triple of          sticks exists.

If there are multiple triples of different-coloured sticks that give rise      to a triangle, your program may pick one such triple arbitrarily.

hint:
给你每根木棍的长度和颜色，求一个能拼成三角形且木棍颜色互不相同的方案

由@zhouyonglong提供SPJ


title: [POI2011] PRO-Programming Contest

description:
Bartie and his friends compete in the Team Programming Contest.

There are $n$ contestants on each team, and each team has access to $n$ computers.

The contest lasts $t$ minutes, during which the contestants are to solve $m$ programming problems.

Furthermore, penalties are imposed on the teams: solving a problem $s$ minutes since the beginning of the contest amounts to $s$ penal points.

The team that solved the most problems wins the contest, with ties broken in    favour of the team with smaller penalty.

On the contest day Bartie quickly glances over the problem statements and    distributes them among his teammates.

He knows his team so well that he can exactly assess who is able to solve    which problem.

Solving any problem takes any contestant that is able to solve it exactly $r$ minutes of using the computer.

Bartie's team did not fare well in this year's contest.

Bartie is obsessed with the thought that it might be his fault, due to wrong    decisions regarding the distribution of problems.

He asks you to write a program that, given what Bartie knew at the beginning    of the contest, determines the best possible result of Bytie's team, together    with the assignment of problems to team members that attains the result.

n个人m个题目，每个题要r分钟完成。比赛有t分钟。给出每个人会做哪些题目，请你安排一个每个人在什么时候做什么题目，使得做出来的题目数最多。在做题数一样多的情况下，罚时尽量小。

inputFormat:
Five integers $n$, $m$, $r$, $t$, and $k$ ($1\le n,m\le 500$, $1\le r,t\le 1\ 000\ 000$) are given in the first line of the standard input, separated by single spaces.

These denote, respectively:

the number of contestants on a team, the number of problems, the time it      takes a contestant to solve a problem, the duration of the contest,and the number of contestant-problem pairs given on the input.

Each of the following $k$ lines holds two integers $a$ and $b$($1\le a\le n$,$1\le b\le m$), separated by a single space, denoting that the contestant $a$ is able to solve the problem $b$.Each such pair appears at most once in the input.

In tests worth at least 30% of the points it additionally holds that $n,m\le 100$.

outputFormat:
In the first line of the standard output the best possible result of Bytie's      team should be printed as two numbers separated by a single space:

the number of solved problems $z$ and the total penal points.

An exemplary assignment of problems that attains this result should be given in the following $z$ lines.

Each of those should hold three integers $a$, $b$ and $c$ ($1\le a\le n$,$1\le b\le m$, $0\le c\le t-r$),separated by single spaces, signifying that the contestant $a$ should start solving the problem $b$ at time $c$(the contest starts at time $0$).No contestant should be assigned a problem that they cannot solve. If more that one optimal assignment exists, your program can output any of them.


title: [POI2012] FES-Festival

background:
在 Byteburg 举办了一场慈善活动，你是其中一个筹款人。不幸的是，你错过了一些有趣的活动，包括一场越野赛。

谜题爱好者 Byteasar 承诺：如果你能解开他的谜题，他会捐一大笔钱。

description:
你不知道越野赛的结果，但 Byteasar 会告诉你部分信息。现在，他要你答出：所有参赛者最多能达到多少种不同的成绩，而不违背他给的条件。（他们中的一些人可能平局，也就是同时到达终点，这种情况只算有一种成绩）。

Byteasar 告诉你，所有参赛者的成绩都是整数秒。他还会为你提供了一些参赛者成绩的关系。具体是：他会给你一些数对 $(A, B)$，表示 $A$ 的成绩正好比 $B$ 快 $1$ 秒；他还会给你一些数对 $(C, D)$，表示 $C$ 的成绩不比 $D$ 慢。而你要回答的是：所有参赛者最多能达到多少种不同的成绩，而不违背他给的条件。

请你编程解决这个谜题。

inputFormat:
第一行有三个整数 $n, m_{1}, m_{2}$，分别表示选手人数、数对 $(A, B)$ 的数目、数对 $(C, D)$ 的数目。

接下来 $m_1$ 行，每行两个整数 $a_{i}, b_{i}$（$a_{i} \ne b_{i}$）。这表示选手 $a_{i}$ 的成绩恰比 $b_{i}$ 小 $1$ 秒。

接下来 $m_{2}$ 行，每行两个整数 $c_{i}, d_{i}$（$c_{i} \ne d_{i}$）。这表示选手 $c_{i}$ 的成绩不比 $d_{i}$ 的成绩差（也就是花的时间不会更多）。

outputFormat:
如果有解，输出一行一个整数，表示所有选手最多能拿到的成绩的种数。
如果无解，输出 `NIE`。


title: [POI2012] LIT-Letters

description: 给出两个长度相同的的只含大写字母的字符串 $a, b$，每次可以交换 $a$ 中相邻两个字符，求最少的交换次数，使得 $a$ 交换后的得到的字符串与 $b$ 相同。

inputFormat:
输入的第一行是一个整数，代表字符串的长度 $n$。

第二行是一个长度为 $n$ 的字符串，代表 $a$。

第三行是一个长度为 $n$ 的字符串，代表 $b$。

outputFormat: 输出一行一个整数，代表最少的交换次数。

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

- 对于 $30\%$ 的数据，保证 $n \leq 10^3$。
- 对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$a, b$ 中只含大写字母，且数据保证 $a$ 可以变成 $b$。


title: [POI2012] ODL-Distance

description:
We consider the distance between positive integers in this problem, defined as follows.

A single operation consists in either multiplying a given number by a prime number1    or dividing it by a prime number (if it does divide without a remainder).

The distance between the numbers ![](http://main.edu.pl/images/OI19/odl-en-tex.1.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.2.png), denoted ![](http://main.edu.pl/images/OI19/odl-en-tex.3.png), is the minimum number of operations    it takes to transform the number ![](http://main.edu.pl/images/OI19/odl-en-tex.4.png) into the number ![](http://main.edu.pl/images/OI19/odl-en-tex.5.png).

For example, ![](http://main.edu.pl/images/OI19/odl-en-tex.6.png).

Observe that the function ![](http://main.edu.pl/images/OI19/odl-en-tex.7.png) is indeed a distance function - for any positive integers ![](http://main.edu.pl/images/OI19/odl-en-tex.8.png), ![](http://main.edu.pl/images/OI19/odl-en-tex.9.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.10.png) the following hold:

the distance between a number and itself is 0: ![](http://main.edu.pl/images/OI19/odl-en-tex.11.png),                  the distance from ![](http://main.edu.pl/images/OI19/odl-en-tex.12.png) to ![](http://main.edu.pl/images/OI19/odl-en-tex.13.png) is the same as from ![](http://main.edu.pl/images/OI19/odl-en-tex.14.png) to ![](http://main.edu.pl/images/OI19/odl-en-tex.15.png): ![](http://main.edu.pl/images/OI19/odl-en-tex.16.png), and                  the triangle inequality holds: ![](http://main.edu.pl/images/OI19/odl-en-tex.17.png).

A sequence of ![](http://main.edu.pl/images/OI19/odl-en-tex.18.png) positive integers, ![](http://main.edu.pl/images/OI19/odl-en-tex.19.png), is given.

For each number ![](http://main.edu.pl/images/OI19/odl-en-tex.20.png) we have to determine ![](http://main.edu.pl/images/OI19/odl-en-tex.21.png) such that ![](http://main.edu.pl/images/OI19/odl-en-tex.22.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.23.png) is minimal.

给你一个序列a[]，定义d(i,j)=a[i],a[j]每次操作可以对其中之一乘一个质数p或除以一个数p(p必须为被除数的约数)，让a[i]=a[j]的最少操作步数

对于每个i，求d(i,j)最小的j，若有多个解，输出最小的j

inputFormat:
In the first line of standard input there is a single integer ![](http://main.edu.pl/images/OI19/odl-en-tex.24.png) (![](http://main.edu.pl/images/OI19/odl-en-tex.25.png)).

In the following ![](http://main.edu.pl/images/OI19/odl-en-tex.26.png) lines the numbers ![](http://main.edu.pl/images/OI19/odl-en-tex.27.png) (![](http://main.edu.pl/images/OI19/odl-en-tex.28.png)) are given,      one per line.

In tests worth 30% of total point it additionally holds that ![](http://main.edu.pl/images/OI19/odl-en-tex.29.png).

outputFormat:
Your program should print exactly ![](http://main.edu.pl/images/OI19/odl-en-tex.30.png) lines to the standard output, a single integer in each line.

The ![](http://main.edu.pl/images/OI19/odl-en-tex.31.png)-th line should give the minimum ![](http://main.edu.pl/images/OI19/odl-en-tex.32.png) such that: ![](http://main.edu.pl/images/OI19/odl-en-tex.33.png), ![](http://main.edu.pl/images/OI19/odl-en-tex.34.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.35.png) is minimal.


title: [POI2012] RAN-Rendezvous

description:
Byteasar is a ranger who works in the Arrow Cave - a famous rendezvous destination among lovers.

The cave consists of $n$ chambers connected with one-way corridors.

In each chamber exactly one outgoing corridor is marked with an arrow.

Every corridor leads directly to some (not necessarily different) chamber.

The enamoured couples that agree to meet in the Arrow Cave are notorious for forgetting to agree upon    specific chamber, and consequently often cannot find their dates.

In the past this led to many mix-ups and misunderstandings\dots    But ever since each chamber is equipped with an emergency telephone line to the ranger on duty,    helping the enamoured find their dates has become the rangers' main occupation.

The rangers came up with the following method.

Knowing where the enamoured are, they tell each of them how many times they should follow the corridor marked with an arrow in order to meet their date.

The lovers obviously want to meet as soon as possible - after all, they came to the cave to spend time together, not to wander around alone!

Most rangers are happy to oblige: they do their best to give each couple a valid pair of numbers such that their maximum is minimal.

But some rangers, among their numbers Byteasar, grew tired of this extracurricular activity and ensuing puzzles.  Byteasar has asked you to write a program    that will ease the process.  The program, given a description of the cave and the current location of $k$ couples,    should determine $k$ pairs of numbers $x_i$ and $y_i$ such that if the $i$-th couple follows respectively: he $x_i$ and she $y_i$ corridors marked with arrows,then they will meet in a single chamber of the cave $max(x_i,y_i)$ is minimal,subject to above $min(x_i,y_i)$ is minimal,if above conditions do not determine a unique solution, then the woman should cover smaller distance ($x_i\ge y_i$).

It may happen that such numbers $x_i$ and $y_i$ do not exist - then let $x_i=y_i=-1$.  Note that it is fine for several couples    to meet in a single chamber.  Once the lovers have found their dates, they will be happy to lose themselves in the cave again...

给定一棵内向森林，多次给定两个点a和b，求点对(x,y)满足：

1.从a出发走x步和从b出发走y步会到达同一个点

2.在1的基础上如果有多解，那么要求max(x,y)最小

3.在1和2的基础上如果有多解，那么要求min(x,y)最小

4.如果在1、2、3的基础上仍有多解，那么要求x>=y

inputFormat:
In the first line of the standard input there are two positive integers $n$ and $k$($1\le n,k\le 500\ 000$), separated by a single space, that denote   the number of chambers in the Arrow Cave and the number of couples who want to find their dates, respectively.

The chambers are numbered from 1 to $n$, while the enamoured couples are numbered from 1 to $k$.

The second line of input contains $n$ positive integers separated by single spaces:

the $i$-th such integer determines the number of chamber to which the corridor marked with an arrow going out of chamber $i$ leads.

The following $k$ lines specify the queries by the separated couples. Each such query consists of two positive integers separated by a single space - these denote the numbers of chambers where the lovers are - first him, then her.

In the tests worth 40% of the total points it additionally holds that $n,k\le 2\ 000$.

outputFormat:
Your program should print exactly $k$ lines to the standard output,   one line per each couple specified in the input:

the $i$-th line of the output should give the instructions for the $i$-th couple on the input.

I.e., the $i$-th line of output should contain the integers $x_i,y_i$, separated by a single space.

hint:
给定一棵内向基环森林，多次给定两个点a和b，求点对(x,y)满足：

1.从a出发走x步和从b出发走y步会到达同一个点

2.在1的基础上如果有多解，那么要求max(x,y)最小

3.在1和2的基础上如果有多解，那么要求min(x,y)最小

4.如果在1、2、3的基础上仍有多解，那么要求x>=y


title: [POI2012] STU-Well

description:
Byteasar has set off on a journey along the Dry River, which crosses the Byteotian Desert.

Unfortunately, the Dry River has dried out, and Byteasar has run out of water.

His only hope is to dig a deep enough well in the dried river bed.

Realising the graveness of his situation, Byteasar decides to plan everything carefully before he actually starts digging.

The danger is that he drains his strength before he reaches the water level - in such case he is unlikely to survive.

He managed to determine the depth of the water level.  He also knows how much he can dig before losing strength.

His only worry is a possible landslide, which might bury him alive.

He sends you (via a satellite telephone) a topographic map of the river bed.

And, of course, he asks you to help him determine where he should dig so that he reaches water before draining his strength    while keeping the slope of his excavation as gentle as possible.

He is waiting for your advice!

inputFormat:
In the first line of the standard input two positive integers are given, $n$ and $m$ ($1\le n\le 1\ 000\ 000$, $1\le m\le 10^{18}$), separated by a single space.

The second line holds $n$ positive integers $x_1,x_2,\cdots,x_n$ ($1\le x_i\le 10^9$), also separated by single spaces.

Byteasar has enough energy to perform $m$ swings of the shovel.

The numbers $x_1,x_2,\cdots,x_n$ describe the topography of the Dry River's bed.

They represent the depth of the sand layer above the ground water level in successive one meter spaced spots along the river bed.

With a single swing of the shovel Byteasar can extract an amount of the sand that decreases any of the numbers $x_i$ by 1.If any of these numbers, say $x_k$, drops to 0, this means that Byteasar has dug down to the water. But Byteasar has a secondary goal as well. He wants the following number $z$, characterising the slope of the sand hill, minimised:

$z=max_{i=1,2,\cdots,n-1}|x_i-x_{i+1}|$
If there are multiple correct values of the number $k$,representing the spot where Byteasar is to dig down to reach the water, your program can pick one arbitrarily. The spots $1,2,\cdots,n$ are the only ones suitable for digging - elsewhere there is rock rather than sand. You may assume that Byteasar has enough energy to reach water at one of the spots.

outputFormat:
Your program should print two integers to the standard output, separated by a single space:

the spot $k$, where Byteasar should dig for water, and the minimum value of the number $z$.

translation: 给定一个非负整数序列 $A$，每次操作可以选择一个数然后减掉 $1$，要求进行不超过 $m$ 次操作使得存在一个 $A_k=0$ 且 $\max(|x_i-x_{i-1}|)$ 最小，输出使其最小的 $k$ 与这个最小值。


title: [POI2012] TOU-Tour de Byteotia

description:
给定一个 $n$ 个点 $m$ 条边的无向图，问最少删掉多少条边能使得编号小于等于 $k$ 的点都不在环上。

$n\le 5\times 10^5,m\le 7.5\times 10^5$

inputFormat: 第一行 $n,m,k$，然后是图。

outputFormat: 一个数答案，无需方案。


title: [POI2012] BON-Vouchers

description:
The candy shop owned by Byteasar sells delicious caramel candy.

For every positive integer $c$ there is exactly one package that contains $c$ candies; currently no new deliveries are expected.

To encourage customers to buy the sweets, Byteasar has planted $m$ vouchers for an annual supply of chocolate into some packages,  making sure to put at most one voucher in each package.

The carnival starts next week in Byteburg, and it will last $n$ days;  on the $k$-th day of the carnival a party with $a_k$ guests will be held.

Byteasar is confident that on the $k$-th day's morning each of those guests is going to buy, in his own store, the smallest package  of candy available whose content can be equally distributed between the party guests.  For example, if $n=2$, $a_1=4$, $a_2=2$,  then on the first day of the carnival he expects to sell the packages containing four, eight, twelve, and sixteen candies, selling  those with two and six candies on the second day.

Now he is wondering which customers will end up with the packages holding the vouchers.

He has asked you to write a program that will determine this for him.

定义n个数为幸运数字，一共有n批人，设第i批人有x个，则它们会依次取走余下的x的倍数中最小的x个，问哪些人去走了幸运数字

inputFormat:
On the first line of the standard input there is a single integer $m$ ($1\le m\le 1\ 000\ 000$) that denotes the number of vouchers.

The $k$-th of the $m$ lines that follow holds an integer $b_k$ ($1\le b_k\le 1\ 000\ 000$)denoting the size (i.e., the number of candies inside) of a package in which Byteasar has placed the $k$-th voucher.

These numbers are given in an increasing order.

Then the next line contains a single integer $n$ ($1\le n\le 1\ 000\ 000$) that denotes the number of carnival days.

The $k$-th of the $n$ lines that follow holds an integer $a_k$($1\le a_k\le 1\ 000\ 000$)denoting the number of guests attending the $k$-th party.

You may assume that in tests worth at least 50% of the total points none of the numbers given on the input exceeds $5\ 000$.

outputFormat:
In the first line of the standard output your program should print an integer $z$ - the number of packages with vouchers sold.

The following $z$ lines should specify the numbers of those customers who bought a package with a voucher, in an increasing order.

The customers are numbered from $1$ in the order of their purchases.

translation:
### 题目描述

Byteasar 经营着一家焦糖店。

对于所有正整数 $c$，Byteasar 都有且仅有一个装有 $c$ 个糖果的包裹。

Byteasar 准备了 $m$ 张代金券，并在装有 $b_i$ 个糖果的包裹里分别放入一张。

现在共有 $n$ 批顾客，第 $i$ 批客人有 $a_i$ 人，且每名顾客会买走装有最少糖果的包裹，满足这些糖果可平均分给这一批的 $a_i$ 个人。例如，若 $n = 2, a_1 = 4, a_2 = 8$，则第一批顾客买走的糖果数量分别为  $4, 8, 12, 16$，第二批顾客买走的糖果数量分别为 $2, 6$。

将所有顾客按顺序从 $1$ 开始编号，Byteasar 想知道取走代金券的顾客数量和各自的编号。

### 输入输出格式
#### 输入格式

第一行输入一个整数 $m$ ($1 \le m \le 1\ 000\ 000$)，表示代金券总数。

接下来 $m$ 行，输入 $m$ 个整数 $b_1,b_2,\cdots, b_m$ ($1 \le b_i \le 1\ 000\ 000$)，分别代表放入代金券的包裹装有的糖果数量，保证 $b_i$ 单调递增。

接下来输入一个整数 $n$ ($1 \le n \le 1\ 000\ 000$)，表示共有 $n$ 批顾客。

接下来 $n$ 行，输入 $n$ 个整数 $a_1,a_2,\cdots, a_n$ ($1 \le a_i \le 1\ 000\ 000$)，分别代表每批顾客的人数。

对于不少于 $50\%$ 的数据，保证输入的所有数字不超过 $5\ 000$。

#### 输出格式
第一行一个整数 $z$，代表获得代金券的顾客数量。

接下来 $z$ 行每行一个整数，从小到大输出获得代金券的顾客编号。


title: [POI2012] SZA-Cloakroom

description:
The annual rich citizen's reunion is taking place in Byteotia.

They meet to boast about their incomes, Lebytene's shoes and other luxuries.

Naturally, not all these objects of pride are carried into the banquet - coats,  jackets, umbrellas and such are left in the cloakroom, and picked up upon leave.

Unfortunately for the well off, a gang of Byteotian thieves plans to break into  the cloakroom and steal part of the items stored therein.

At this very moment the gang's leader is examining the plans of the robbery put  forward by other gang members (they are a democratic lot!).

A plan typically looks as follows: the thieves break into the cloakroom at time $m_j$,  take items worth exactly $k_j$ and escape, where the whole heist takes them $s_j$ time.

The gang leader would first of all like to know which of these plans are feasible and which are not.

A plan is feasible if at time $m_j$ it is possible to collect items of total value $k_j$ in such a way  that up to the very $m_j+s_j$ moment no one shows up to retrieve any of the stolen goods  (in such event, they would notify security, and the robbery would fail).

In particular, if at time $m_j$ it is impossible to select items of exact total worth $k_j$,  then the plan is infeasible and consequently rejected.

Knowing the drop off and retrieval times for each item, determine which plans are feasible and which are not.

We assume that an item left in the cloakroom the moment a robbery starts can already be stolen (see the example).

inputFormat:
In the first line of the standard input there is a single integer $n$($1\le n\le 1\ 000$) denoting the number of items that will be left in the cloakroom.

Those items are described in the $n$ lines that follow.

Each of those lines consists of three integers $c_i$, $a_i$, and $b_i$ ($1\le c_i\le 1\ 000$, $1\le a_i<b_i\le 10^9$),  separated by single spaces, that denote respectively: the item's value, the moment it is left in the cloakroom,  and the moment it will be retrieved by the owner.

The next line holds an integer $p$ ($1\le p\le 1\ 000\ 000$),the number of plans the gang came up with. Each is specified in a separate line by three integers,$m_j$,$k_j$ and $s_j$($1\le m_j\le 10^9$,$1\le k_j\le 100\ 000$,$0\le s_j\le 10^9$), separated by single spaces, that denote respectively: the moment the thieves would enter the cloakroom, the value of goods they would like to steal, and the time the robbery would take them.

In test worth 16% of the total points $p\le 10$ holds in addition.

n some other tests, also worth 16% of the points, all the items have the same $a_i$ values.

In yet other tests, worth 24% of the points, all the queries share the same $s_j$ value.

outputFormat:
For each plan put forward by the gang determine if it is feasible, i.e., whether it is possible  to steal items of total worth exactly $k_j$ and escape before anyone asks for their belongings.

If the plan is feasible, your program should print the word TAK (Polish for yes) on the  standard output, otherwise it should print NIE (Polish for no).

translation:
有 $n$ 件物品，每件物品有三个属性 $a_i, b_i, c_i\ (a_i<b_i)$。注意输入顺序为 $c_i, a_i, b_i$。

再给出 $q$ 个询问，每个询问由非负整数 $m, k, s$ 组成，问是否能够选出某些物品使得：

1. 对于每个选的物品 $i$，满足 $a_i\le m$ 且 $b_i>m+s$。
2. 所有选出物品的 $c_i$ 的和正好是 $k$。

$1\le n\le 1000$，$1\le a_i<b_i\le 10^9$，$1\le c_i\le 1000$。

$1\le q\le 10^6$，$1\le m\le 10^9$，$1\le k\le 10^5$，$0\le s\le 10^9$。


title: [POI2012] OKR-A Horrible Poem

description:
Bytie boy has to learn a fragment of a certain poem by heart.  The poem, following the best lines of modern art, is a long string    consisting of lowercase English alphabet letters only.  Obviously, it sounds horrible, but that is the least of Bytie's worries.

First and foremost, he completely forgot which fragment is he supposed to learn.  And they all look quite difficult to memorize...

There is hope, however: some parts of the poem exhibit certain regularity.  In particular, every now and then a fragment, say ![](http://main.edu.pl/images/OI19/okr-en-tex.1.png),    is but a multiple repetition of another fragment, say ![](http://main.edu.pl/images/OI19/okr-en-tex.2.png) (in other words, ![](http://main.edu.pl/images/OI19/okr-en-tex.3.png), i.e., ![](http://main.edu.pl/images/OI19/okr-en-tex.4.png), where ![](http://main.edu.pl/images/OI19/okr-en-tex.5.png) is    an integer).  In such case we say that ![](http://main.edu.pl/images/OI19/okr-en-tex.6.png) is a full period of ![](http://main.edu.pl/images/OI19/okr-en-tex.7.png) (in particular, every string is its own full period).

If a given fragment has a short full period, Bytie's task will be easy.  The question remains... which fragment was that?

Make a gift for Bytie - write a program that will read the whole poem as well as a list of fragments that Bytie suspects might be the    one he is supposed to memorize, and for each of them determines its shortest full period.

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。

如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

inputFormat:
In the first line of the standard input there is a single integer ![](http://main.edu.pl/images/OI19/okr-en-tex.8.png)      (![](http://main.edu.pl/images/OI19/okr-en-tex.9.png)).

In the second line there is a string of length ![](http://main.edu.pl/images/OI19/okr-en-tex.10.png) consisting of lowercase English alphabet letters-the poem.

We number the positions of its successive characters from 1 to ![](http://main.edu.pl/images/OI19/okr-en-tex.11.png).

The next line holds a single integer ![](http://main.edu.pl/images/OI19/okr-en-tex.12.png) (![](http://main.edu.pl/images/OI19/okr-en-tex.13.png)) denoting the number of fragments.

Then the following ![](http://main.edu.pl/images/OI19/okr-en-tex.14.png) lines give queries, one per line.

Each query is a pair of integers ![](http://main.edu.pl/images/OI19/okr-en-tex.15.png) and ![](http://main.edu.pl/images/OI19/okr-en-tex.16.png) (![](http://main.edu.pl/images/OI19/okr-en-tex.17.png)),      separated by a single space, such that the answer to the query should be the length of the shortest full period of the poem's      fragment that begins at position ![](http://main.edu.pl/images/OI19/okr-en-tex.18.png) and ends at position ![](http://main.edu.pl/images/OI19/okr-en-tex.19.png).

In tests worth in total 42% of the points ![](http://main.edu.pl/images/OI19/okr-en-tex.20.png) holds in addition.

In some of those, worth 30% of points in total, ![](http://main.edu.pl/images/OI19/okr-en-tex.21.png) holds as well.

outputFormat:
Your program should print ![](http://main.edu.pl/images/OI19/okr-en-tex.22.png) lines on the standard output.

The ![](http://main.edu.pl/images/OI19/okr-en-tex.23.png)-th of these lines should hold a single integer - the answer to the ![](http://main.edu.pl/images/OI19/okr-en-tex.24.png)-th query.

translation:
给出一个由小写英文字母组成的字符串 $S$，再给出 $q$ 个询问，要求回答 $S$ 某个子串的最短循环节。

如果字符串 $B$ 是字符串 $A$ 的循环节，那么 $A$ 可以由 $B$ 重复若干次得到。

---

第一行一个正整数 $n\ (n\le 5\times 10^5)$，表示 $S$ 的长度。

第二行 $n$ 个小写英文字母，表示字符串 $S$。

第三行一个正整数 $q\ (q\le 2\times 10^6)$，表示询问次数。

下面 $q$ 行每行两个正整数 $a,b(1\le a\le b\le n)$，表示询问字符串 $S[a\cdots b]$ 的最短循环节长度。


title: [POI2012] ROZ-Fibonacci Representation

description:
The Fibonacci sequence is a sequence of integers, called Fibonacci numbers, defined as follows:

$Fib_{0}=0,Fib_{1}=1,Fib_{n}=Fib_{n-2}+Fib_{n-1}\ for\ n>1$

Its initial elements are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Byteasar investigates representations of numbers as sums or differences of Fibonacci numbers. Currently he is wondering what is the minimum representation, i.e., one with the minimum number of (not necessarily different) Fibonacci numbers, for a given positive integer $k$ . For example, the numbers 10, 19, 17, and 1070 can be minimally represented using, respectively, 2, 2, 3, and 4 Fibonacci numbers as follows:

$10=5+5$

$19=21-2$

$17=13+5-1$

$1070=987+89-5-1$

Help Byteasar! Write a program that, for a given positive integer $k$ determines the minimum number of Fibonacci numbers required to represent $k$ as their sum or difference.

给一个数，问最少可以用几个斐波那契数加加减减凑出来

例如
10=5+5
19=21-2

17=13+5-1

1070=987+89-5-1

inputFormat:
In the first line of the standard input a single positive integer $p$ is given ($1\le p\le 10$) that denotes the number of queries. The following $p$ lines hold a single positive integer $k$ each ($1\le k\le 1\times 10^{17}$).

多组数据

outputFormat: For each query your program should print on the standard output the minimum number of Fibonacci numbers needed to represent the number $k$ as their sum or difference.

hint: 给一个数，问最少可以用几个斐波那契数加加减减凑出来


title: [POI2012] SQU-Squarks

description:
A famous Byteotian physicist Byteasar is studying a new constituent of matter - squarks.

These are quite exotic particles that never exist alone but always in pairs.

Moreover, squarks of a particular kind form pairs only with squarks of different kinds.

After years of studies Byteasar has established that there are ![](http://main.edu.pl/images/OI19/squ-en-tex.1.png) different kinds of squarks.

Squarks of each kind have a unique mass, which is a positive integer multiple of (an appropriate) unit.

Byteasar has also measured the total mass of each of the ![](http://main.edu.pl/images/OI19/squ-en-tex.2.png) possible pairs of squarks.

According to standard Byteotian model of physics, the mass of a pair of squarks equals the sum of the masses    of the two squarks forming it.

Now Byteasar desires to determine the individual masses of squarks of every kind.

He has asked your help in writing a program that will determine all solutions to this puzzle,    i.e., will reconstruct all configurations of squark masses that are consistent with his previous measurements.

设有n个互不相同的正整数{X1,X2,…Xn}，任取两个Xi,Xj(i≠j)，能算出Xi+Xj。现在所有取法共n\*(n-1)/2个和，要你求出X1,X2,…Xn。

3<=n<=300, 每个正整数不超过10^8

inputFormat:
In the first line of the standard input there is a single integer ![](http://main.edu.pl/images/OI19/squ-en-tex.3.png) (![](http://main.edu.pl/images/OI19/squ-en-tex.4.png))      that denotes the number of different kinds of squarks.

In the second line there are ![](http://main.edu.pl/images/OI19/squ-en-tex.5.png) positive integers, separated by single spaces,      that denote the total masses of all possible pairs of squarks.

The mass of every pair does not exceed ![](http://main.edu.pl/images/OI19/squ-en-tex.6.png).

For each two different kinds of squarks, the mass of the pair they form is given on the input exactly once.

      The masses on the input are given in a random order.

In tests worth 32% of the points the following conditions hold in addition:

![](http://main.edu.pl/images/OI19/squ-en-tex.7.png) and the mass of every pair of squarks does not exceed ![](http://main.edu.pl/images/OI19/squ-en-tex.8.png).

outputFormat:
In the first line of the standard output your program should print the number ![](http://main.edu.pl/images/OI19/squ-en-tex.9.png) of possible solutions to the problem.

In the ![](http://main.edu.pl/images/OI19/squ-en-tex.10.png) lines that follow it should report successive solutions, one per line.

Each solution should consist of ![](http://main.edu.pl/images/OI19/squ-en-tex.11.png) different positive integers, namely the masses of squarks of all kinds.

In every solution these should be given in increasing order and separated by single spaces.

Solutions can be reported in arbitrary order, but they cannot be repeated.

You may assume that for each test data there exists at least one solution, i.e., ![](http://main.edu.pl/images/OI19/squ-en-tex.12.png).


title: [POI2012] PEN-Salaries

description:
The Byteotian Software Corporation (BSC) has $n$ employees.

In BSC's strict hierarchy, each employee has a direct supervisor, except the CEO, to whom all other BSC employees answer, directly or not.

Each employee has a unique monthly salary, and all their salaries range from 1 to $n$ bythalers.

Each supervisor earns more than each of their subordinates.

According to Byteotian law, the salaries of employees on certain posts may be publicly disclosed.

Furthermore, if the salary of an employee is disclosed, then the salary of their supervisor is also disclosed.

The Byteotian Internal Revenue Anti-Corruption Service (BIRAS) has decided to investigate BSC.

Before BIRAS enters BSC with a warrant, they intend to learn the salaries of all BSC employees    that are not disclosed but can be determined from those that are disclosed.

给出一棵n个结点的有根树，结点用正整数1~n编号。

每个结点有一个1~n的正整数权值，不同结点的权值不相同，

并且一个结点的权值一定比它父结点的权值大（根结点的权值最大，一定是n）。

现在有些结点的权值是已知的，并且如果一个结点的权值已知，它父结点的权值也一定已知。

问还有哪些结点的权值能够唯一确定。

inputFormat:
In the first line of the standard input a single integer $n$ ($1\le n\le 1\ 000\ 000$) is given that denotes the number of BSC employees.

The employees have id's that range from 1 to $n$.

The $n$ lines that follow provide information on these employees.

The line no. $i+1$ describes the employee no. $i$ by two integers $p_i$ and $z_i$ ($1\le p_i\le n$, $0\le z_i\le n$), separated by a single space.

The number $p_i$ is the id of the direct supervisor of the employee $i$.If $p_i=i$, then $i$ is the CEO of BSC. If $z_i>0$,then that is the salary of the employee $i$.If, on the other hand,$z_i=0$, then the salary of employee $i$ is not disclosed.Those $z_i$'s that are positive are also pairwise different.

The input data will always be such that there is at least one assignment of salaries to employees consistent with them, i.e., with the hierarchy and the partial assignment that they provide.

In tests worth 54% of the total points the condition $n\le 10\ 000$  holds in addition.

outputFormat:
Your program should print $n$ lines to the standard output, each line holding a single integer.

If the employee $i$'s salary is disclosed or can be inferred from disclosed salaries, then the $i$-th line should hold employee $i$'s salary.

Otherwise the $i$-th line should contain $0$.

hint:
给出一棵n个结点的有根树，结点用正整数1~n编号。

每个结点有一个1~n的正整数权值，不同结点的权值不相同，

并且一个结点的权值一定比它父结点的权值小（根结点的权值最大，一定是n）。

现在有些结点的权值是已知的，并且如果一个结点的权值已知，它父结点的权值也一定已知。

问还有哪些结点的权值能够唯一确定。


title: [POI2012] WYR-Leveling Ground

description:
Byteasar has decided to build a house.

He has chosen a very narrow valley as its location.

Before Byteasar starts the actual construction work, he has to level the ground first.

He has two excavators at his disposal: the first one can either increase or decrease the  ground level of any connected area in the valley by exactly ![](http://main.edu.pl/images/OI19/wyr-en-tex.1.png) meters;  the other can do the same, i.e., either increase or decrease the  ground level of any connected area in the valley, but by exactly ![](http://main.edu.pl/images/OI19/wyr-en-tex.2.png) meters.

Notice that neither before such an operation nor after it needs the ground in the affected  area be actually leveled.

Given a map of the area, determine the minimum number of operations required to  level the ground in the whole valley, i.e., to make the ground level everywhere  equal 0.  While the operations are performed, the ground level at any point in  the valley can have arbitrary value; in particular, it may be negative.

给定 $n$ 个数和 $a,b$。每次可以选择一段区间 $+a,-a,+b$ 或 $-b$，问最少操作几次能把它们都变成 $0$。如果无解请输出 $-1$。

inputFormat:
In the first line of the standard input there are three integers, ![](http://main.edu.pl/images/OI19/wyr-en-tex.3.png), ![](http://main.edu.pl/images/OI19/wyr-en-tex.4.png), ![](http://main.edu.pl/images/OI19/wyr-en-tex.5.png)    (![](http://main.edu.pl/images/OI19/wyr-en-tex.6.png), ![](http://main.edu.pl/images/OI19/wyr-en-tex.7.png)), separated by single spaces.

The number ![](http://main.edu.pl/images/OI19/wyr-en-tex.8.png) denotes the valley's length in meters.

The second line contains ![](http://main.edu.pl/images/OI19/wyr-en-tex.9.png) integers, ![](http://main.edu.pl/images/OI19/wyr-en-tex.10.png), separated by single spaces.

These numbers, all with absolute value no larger than ![](http://main.edu.pl/images/OI19/wyr-en-tex.11.png), represent the initial ground level in meters    of successive one meter long slices of the valley.

In tests worth 30% of the points the following conditions hold in addition: ![](http://main.edu.pl/images/OI19/wyr-en-tex.12.png) and   ![](http://main.edu.pl/images/OI19/wyr-en-tex.13.png).

In tests worth 60% of the points the following conditions hold in addition: ![](http://main.edu.pl/images/OI19/wyr-en-tex.14.png) and   ![](http://main.edu.pl/images/OI19/wyr-en-tex.15.png).

In tests worth 90% of the points the condition ![](http://main.edu.pl/images/OI19/wyr-en-tex.16.png) holds in addition.

outputFormat: In the first and only line of the standard output your program should print a single    integer: the minimum number of operations required to level the ground in the whole valley,    or ![](http://main.edu.pl/images/OI19/wyr-en-tex.17.png) if leveling the whole valley with given excavators is impossible.


title: [POI2012] BEZ-Minimalist Security

description:
A map of Mafiatown's road network is given.

The network consists of intersections and bidirectional streets that connect them.

The streets cross only at the intersections, but they may lead through tunnels or flyovers.

Each pair of intersections is linked by at most one street.

At every intersection $v$ there is a police station manned by $p(v)$ policemen.

A street linking the intersections $u$ and $v$ is considered safe if there are at least $b(u,v)$ policemen in total in the two stations at the streets ends. Initially    $p(u)+p(v)\ge b(u,v)$ holds for every street.

However, due to an ongoing crisis the mayor Byteasar has ordained the Minimalist Security Act (MSA), which states that:

a certain number (which may be zero) of policemen is to be laid off from each police station        (we denote the number of policemen laid off from the station at the intersection $v$ by $z(v)$),                  after the layoff, the total number of the policemen at both ends of every street connecting some two intersections,        say $u$ and $v$, should equal $b(u,v)$ exactly, i.e.:

$p(u)-z(u)+p(v)-z(v)=b(u,v)$ These rules do not determine uniquely how many policemen are to be laid off.

Byteasar wonders what is the minimum and the maximum number of laid off policemen    (the sum of $z$ values over all intersections) that complies with aforementioned rules.

一张n个点m条边的无向图，有点权有边权都是非负，且每条边的权值小于等于两个顶点的权值和，现在要将每个点减一个非负整数使得每条边权等于两个顶点的点权和，问最大修改代价和最小修改代价

inputFormat:
In the first line of the standard input there are two integers, $n$ and $m$ ($1\le n\le 500\ 000$, $0\le m\le 3\ 000\ 000$), separated by a single space, that denote    the number of intersections and the number of streets in Mafiatown, respectively.

The intersections are numbered from 1 to $n$.

In the second line $n$ nonnegative integers separated by single spaces are given.

These are the numbers of policemen currently employed at successive stations, i.e., the values $p(1),p(2),\cdots,p(n)$($0\le p(i)\le 10^6$).

Each of the following $m$ lines describes a single bidirectional street. Such description consists of three integers,$u_i,v_i,b(u_i,v_i)$($1\le u_i,v_i\le n$,$u_i\ne v_i$,$0\le b(u_i,v_i)\le 10^6$), separated by single spaces, that denote respectively: the numbers of the intersections at the ends of the street and the minimum total number of policemen that have to man the stations at those intersections.

outputFormat:
If Byteasar's ordinance can be carried out, your program should print, on the standard output,    exactly one line with two integers separated by a single space.

The numbers should be the minimum and the maximum number of policemen that should be laid off    in order to carry out the ordinance.

If carrying out the ordinance is impossible, your program should print a single line containing    the word NIE (Polish for no).


title: [POI2012] HUR-Warehouse Store

description:
现在有 $n$ 天。第 $i$ 天上午会进货 $A_i$ 件商品，中午的时候会有顾客需要购买 $B_i$ 件商品，可以选择满足顾客的要求，或是无视掉他。

如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。

inputFormat:
第一行包含一个整数 $n$，表示有 $n$ 天。

第二行有 $n$ 个整数 $a_i$，表示第 $i$ 天上午进货 $a$ 件商品。

第三行包含 $n$ 个整数 $b_i$，表示在第 $i$ 天中午有顾客来买 $b$ 件商品。

outputFormat:
第一行一个整数，表示最多能满足几天中顾客的需求。

第二行输出满足这么哪些天顾客的需求。

hint: 对于 $100\%$ 的数据，$1\leqslant n\leqslant 2.5\times 10^5$，$0\leqslant a_i,b_i \leqslant 10^9$。


title: [POI2012] PRE-Prefixuffix

description:
We consider strings consisting of lowercase letters of the English alphabet in this problem.

An initial fragment of a given string is called its prefix.

A final (terminal) fragment of a given string is called its suffix.

In particular, the empty string is both a prefix and a suffix of any string.

Two strings are cyclically equivalent if one of them can be obtained from another by    moving its certain suffix from the end of the string to its beginning.

For example, the strings ![](http://main.edu.pl/images/OI19/pre-en-tex.1.png) and ![](http://main.edu.pl/images/OI19/pre-en-tex.2.png) are cyclically equivalent, whereas the strings ![](http://main.edu.pl/images/OI19/pre-en-tex.3.png) and ![](http://main.edu.pl/images/OI19/pre-en-tex.4.png) are not.

In particular, every string is cyclically equivalent to itself.

A string ![](http://main.edu.pl/images/OI19/pre-en-tex.5.png) consisting of ![](http://main.edu.pl/images/OI19/pre-en-tex.6.png) letters is given.

We are looking for its prefix ![](http://main.edu.pl/images/OI19/pre-en-tex.7.png) and suffix ![](http://main.edu.pl/images/OI19/pre-en-tex.8.png) of equal length such that:

![](http://main.edu.pl/images/OI19/pre-en-tex.9.png) and ![](http://main.edu.pl/images/OI19/pre-en-tex.10.png) are cyclically equivalent,                  the common length of ![](http://main.edu.pl/images/OI19/pre-en-tex.11.png) and ![](http://main.edu.pl/images/OI19/pre-en-tex.12.png) does not exceed ![](http://main.edu.pl/images/OI19/pre-en-tex.13.png)        (i.e., the prefix ![](http://main.edu.pl/images/OI19/pre-en-tex.14.png) and the suffix ![](http://main.edu.pl/images/OI19/pre-en-tex.15.png) do not overlap in ![](http://main.edu.pl/images/OI19/pre-en-tex.16.png)), and                  the common length of ![](http://main.edu.pl/images/OI19/pre-en-tex.17.png) and ![](http://main.edu.pl/images/OI19/pre-en-tex.18.png) is maximized.

对于两个串 $S_1, S_2$，如果能够将 $S_1$ 的一个后缀移动到开头后变成 $S_2$，就称 $S_1$ 和 $S_2$ 循环相同。例如串 ababba 和串 abbaab 是循环相同的。

给出一个长度为 $n$ 的串 $S$，求满足下面条件的最大的 $L(L\leq \frac n 2)$：$S$ 的 $L$ 前缀和 $S$ 的 $L$ 后缀是循环相同的。

inputFormat:
The first line of the standard input contains a single integer ![](http://main.edu.pl/images/OI19/pre-en-tex.19.png)      (![](http://main.edu.pl/images/OI19/pre-en-tex.20.png)) denoting the length of the string ![](http://main.edu.pl/images/OI19/pre-en-tex.21.png).

The second line of input contains the string ![](http://main.edu.pl/images/OI19/pre-en-tex.22.png) itself, consisting of ![](http://main.edu.pl/images/OI19/pre-en-tex.23.png) lowercase letters of the English alphabet.

In tests worth 30% of the points the condition ![](http://main.edu.pl/images/OI19/pre-en-tex.24.png) holds in addition.

In tests worth 50% of the points the condition ![](http://main.edu.pl/images/OI19/pre-en-tex.25.png) holds in addition.

outputFormat: Your program should print a single integer in the first and only line of the standard output,      namely the common length of the prefix ![](http://main.edu.pl/images/OI19/pre-en-tex.26.png) and the suffix ![](http://main.edu.pl/images/OI19/pre-en-tex.27.png) that we are looking for.


title: [POI2013] CEN-Price List

description:
Railway has always been the most popular mean of transport in Byteotia.

Out of $n$ towns in the land, $m$ pairs are connected by track segments    belonging to Byteotian State Railways (BSR).

The tracks do not cross outside of towns, and may lead through picturesque    bridges and somewhat less picturesque tunnels.

The ticket for travelling between any two towns    directly connected by rail costs $a$ bythalers.

Currently the transportation market in Byteotia is changing.

As of now, BSR faces a new competitor: Byteotian Airlines (BA).

BA plans to operate flights between some pairs of towns.

Since Byteotian railways are quite comfortable, the BA board has decided to    operate flights only between pairs of towns that are not directly    connected by rail.  Due to economy, BA will fly only between towns    for which the cheapest railway connection requires exactly one change.

The ticket for each such flight is going to cost $b$ bythalers.

To help Byteotian citizens in planning their trips, the Byteotian    Ministry for Transport (BMT) has decided to issue leaflets specifying the    cheapest routes between all possible towns.  A sequence of an    arbitrary number of direct railway or airplane connections is    called a route.  A BMT officer by the name of Byteasar has been    commissioned with the task of preparing the price list for the leaflets.

Could you help him in writing a program that will determine the right    prices?

Let us clarify that all the connections in Byteotia, both by railway and    airplane, are bidirectional.

inputFormat:
The first line of the standard input contains five integers,$n$,$m$,$k$,$a$ and $b$ ($2\le n\le 100\ 000$, $\le m\le 100\ 000$, $1\le k\le n$, $1\le a,b\le 1\ 000$),      separated by single spaces.

The numbers $n$ and $m$ denote the number of towns and the number of      direct railway connections in Byteotia, respectively.

For simplicity, we number the towns in Byteotia from $1$ to $n$. The other numbers denote:$k$ - the number of the source town for which the connection prices are to be determined;$a$ - the price of a direct railway connection;$b$ - the price of a direct airplane connection.

Each of the following $m$ lines contains a pair of integers $u_i$ and $v_i$($1\le u_i,v_i\le n$,$u_i\ne v_i$ for $i=1,2,\cdots,m$), separated by a single space, specifying the number of towns directly connected by tracks.

You may assume that all towns are reachable by railway from the town no. $k$.

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

The line no. $i$ (for $i=1,2,\cdots,n$) should contain a single integer:

the cost of the cheapest route from town no. $k$ to town no. $i$.

Among those, the line no. $k$ should contain the number $0$.

translation:
给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $a$。

现在将原来图中满足最短路等于 $2a$ 所有的点对 $(x,y)$ 之间加一条长度为 $b$ 的无向边。

给定 $k$，求点 $k$ 到所有点的最短路是多少。


title: [POI2013] GOB-Tapestries

description:
An exhibition of tapestries is opening in Byteotian Museum of Fine Arts.

The main exhibition room, viewed from top, is a polygon (not necessarily    convex).  A tapestry is hanged on each wall of the room, each tapestry    taking all the area of its wall.

A lamp has been installed in the room in order to illuminate the exhibition.

    The lamp is glowing uniformly in all directions.

However, while some of the tapestries have to be flooded with light,    others cannot be exposed to strong light.

Byteasar, the curator, has been moving the lamp around the room, but so far    he is not satisfied with the results.

Now he is terrified by the prospect of moving the tapestries around    instead - this would require much effort, and the exhibition is to open soon.

Perhaps you will be able to tell him if his attempts are doomed or not?

Your task is to determine if there is such a spot that placing the lamp    in it satisfies the following:

each wall is to be either completely illuminated or completely shaded, as required by the tapestry hanging on it;        there can be no wall that is partly illuminated and partly shaded;                  if the lamp is located exactly on the wall or its extension, this wall is not illuminated;                the lamp can neither be switched off nor taken away from the room; it has      to be on while located (strictly) inside the room (i.e., it cannot be      placed in a corner or on any wall).

一个挂毯的艺术展览在Byteotian优秀艺术品博物馆展开！

主展室的俯视图是一个多边形（不一定是凸的）。房间的每面墙壁上都挂着一个挂毯，每个挂毯都占据了所在墙的全部面积。

一盏灯被安装在房间内以照亮展览品，灯对于所有方向发的光都是均匀的。

然而有些挂毯需要被光照亮，其他的却必须避开强光。

策展人Byteasar，一直在房间里移动灯，但到目前为止，他一直没得出满意的结果。

现在展览即将开放，面对自己捉急的智商，他被水淹没，不知所措。

于是他找来了你，而你需要找出究竟有没有这样一个合适的地方挂灯来满足以下条件：

每堵墙要么完全被照亮，要么被完全遮蔽；因为地毯对光照是十分挑剔的，所以不能有某堵墙被部分照亮/遮蔽；如果灯被安在某堵墙的延长线上，这堵墙不会被照亮；灯既不能被熄灭，也不能移动位置，必须严格固定在房间一个确定的位置上（既不能安角落也不能安墙上）。

输入格式：

第一行是一个整数t(1<=t<=20)，代表有t组数据。

每组数据如下：

第一行是一个整数n(3<=n<=1000)代表展厅里的墙数。

下面的n行指定房间的形状：

每行包括一对整形xi和yi(-30000<=xi,yi<=30000;i=1,2,...n)他们之间被一个空格隔开，对应房间（多边形）顶点的坐标，顶点坐标按顺时针排列。

下面的n行指定了每个墙上挂毯的光照需求：

每行为一个字母S或C，分别代表挂毯需要被照亮或遮蔽。

第i块挂毯（1<=i<=n-1）被挂在第i堵墙和第i+1堵墙。

最后一块挂毯被挂在第一堵墙和最后一堵墙之间。

顶点构成的多边形没有交叉点，也就是说除了连续的边共用一个顶点之外，没有任意两个多边形的边共用一个顶点。而且多边形没有任何三个点共线。

输出格式：

对于每一组数据，你的程序都应该输出一个包含一个单词的单行的标准输出：

如果灯可以放置以满足上述所有要求，输出"TAK"（波兰语的yes），反之输出"NIE"（波兰语的no）

提示：

对于40%的数据点，n<=20;

对于另外10%的数据点，所有地毯都需要被照亮。

inputFormat:
There is a single integer ![](http://main.edu.pl/images/OI20/gob-en-tex.1.png) (![](http://main.edu.pl/images/OI20/gob-en-tex.2.png)) in the first line of      the standard input, denoting the number of data sets.

The following lines describe these data sets.

The first line of a single description holds a single integer ![](http://main.edu.pl/images/OI20/gob-en-tex.3.png) (![](http://main.edu.pl/images/OI20/gob-en-tex.4.png)), denoting the number of walls in the main exhibition room.

Then the following ![](http://main.edu.pl/images/OI20/gob-en-tex.5.png) lines specify the room's shape.

Each of those lines contains a pair of integers ![](http://main.edu.pl/images/OI20/gob-en-tex.6.png) and ![](http://main.edu.pl/images/OI20/gob-en-tex.7.png)      (![](http://main.edu.pl/images/OI20/gob-en-tex.8.png) for ![](http://main.edu.pl/images/OI20/gob-en-tex.9.png)), separated by      a single space, denoting the coordinates of the room's corner or, in      other words, the vertex of corresponding polygon.  The vertices are given      clockwise.

The next ![](http://main.edu.pl/images/OI20/gob-en-tex.10.png) lines specify the tapestries' requirements.

Each of those lines contains a single letter, S or      C, denoting that the wall has to be illuminated or shaded,      respectively.

The letter in the ![](http://main.edu.pl/images/OI20/gob-en-tex.11.png)-th of these lines (for ![](http://main.edu.pl/images/OI20/gob-en-tex.12.png))      regards the wall between the ![](http://main.edu.pl/images/OI20/gob-en-tex.13.png)-th and the ![](http://main.edu.pl/images/OI20/gob-en-tex.14.png)-th vertex.

The letter in the last of these lines regards the wall between the last      and the first vertex.

The polygon depicting the room's shape has no self-crossings, i.e.,      with the exception of successive sides, which share a common vertex,      no two sides of the polygon share a common point.  Furthermore, no three      vertices …

outputFormat:
For each data set your program should print to the standard output      a single line containing a single word:

TAK (Polish for yes) if the lamp can be placed so as   to satisfy all aforementioned requirements, or                      NIE (Polish for no) otherwise.


title: [POI2013] MUL-Multidrink

description:
Byteasar lives in Byteburg, a city famous for its milk bars on every corner.

One day Byteasar came up with an idea of a "milk multidrink": he wants to  visit each milk bar for a drink exactly once.

Ideally, Byteasar would like to come up with a route such that the next bar  is always no further than two blocks (precisely: intersections) away from the  previous one.

The intersections in Byteburg are numbered from ![](http://main.edu.pl/images/OI20/mul-en-tex.1.png) to ![](http://main.edu.pl/images/OI20/mul-en-tex.2.png),  and all the streets are bidirectional.

Between each pair of intersections there is a unique direct route, ie, one  that does not visit any intersection twice.

Byteasar begins at the intersection no. ![](http://main.edu.pl/images/OI20/mul-en-tex.3.png) and finishes at the intersection  no. ![](http://main.edu.pl/images/OI20/mul-en-tex.4.png).

Your task is to find any route that satisfies Byteasar's requirements if such  a route exists.

An exemplary route satisfying the requirements is: ![](http://main.edu.pl/images/OI20/mul-en-tex.5.png)                There is no route that satisfies the requirements.

给一棵树，每次步伐大小只能为1或2，要求不重复的遍历n个节点，且起点为1，终点为n

inputFormat:
In the first line of the standard input there is a single integer ![](http://main.edu.pl/images/OI20/mul-en-tex.6.png)  (![](http://main.edu.pl/images/OI20/mul-en-tex.7.png)), denoting the number of intersections in Byteburg.

Each of the following ![](http://main.edu.pl/images/OI20/mul-en-tex.8.png) lines holds a pair of distinct integers ![](http://main.edu.pl/images/OI20/mul-en-tex.9.png)  and ![](http://main.edu.pl/images/OI20/mul-en-tex.10.png) (![](http://main.edu.pl/images/OI20/mul-en-tex.11.png)), separated by a single space, that  represent the street linking the intersections no. ![](http://main.edu.pl/images/OI20/mul-en-tex.12.png) and ![](http://main.edu.pl/images/OI20/mul-en-tex.13.png).

In tests worth ![](http://main.edu.pl/images/OI20/mul-en-tex.14.png) of all points the condition ![](http://main.edu.pl/images/OI20/mul-en-tex.15.png) holds.

outputFormat: If there is no route satisfying Byteasar's requirements, your program  should print a single word "BRAK" (Polish for none),  without the quotation marks to the standard output.  Otherwise, your program  should print ![](http://main.edu.pl/images/OI20/mul-en-tex.16.png) lines to the standard output, the ![](http://main.edu.pl/images/OI20/mul-en-tex.17.png)-th of which should  contain the number of the ![](http://main.edu.pl/images/OI20/mul-en-tex.18.png)-th intersection on an arbitrary route  satisfying Byteasar's requirements.  Obviously, in that case the first line  should hold the number ![](http://main.edu.pl/images/OI20/mul-en-tex.19.png), and the ![](http://main.edu.pl/images/OI20/mul-en-tex.20.png)-th line - number ![](http://main.edu.pl/images/OI20/mul-en-tex.21.png).

hint:
给一棵树，每次步伐大小只能为 1 或 2，要求不重复的遍历 $n$ 个节点，且起点为 $1$，终点为 $n$。无解输出 BRAK。

$n\le 500000$


title: [POI2013] TAK-Taxis

description:
Byteasar wants to take a taxi from the town Bytehole to the town Bytepit,    which is $m$ kilometres away from Bytehole.

Exactly $d$ kilometres along the way from Bytehole to Bytepit, there is    a base of $n$ taxis, numbered from $1$ to $n$.

The taxi no. $i$ has enough fuel to drive exactly $x_i$ kilometres.

Byteasar can change taxis at any point.

All the taxis start at their base but need not return there.

Your task is to determine whether Byteasar can be driven from Bytehole to    Bytepit, and if so, what it the minimum number of taxis required for such    a journey.

Translation 1:

一条线段有三个点，0为初始位置，d为出租车总部位置，m为家的位置，人要叫车，有n辆车可以提供，每辆车有一个路程上限，并且都从车站出发，叫的车行驶之后不必须回到车站，问最少叫几辆车

.Translation 2:

Byteasar想坐出租车从Bytehole镇到Bytepit镇,恰好有d千米从Bytehole镇到Bytepit镇,这有n个出租车,编号从1到n.第i个出租车有足够的燃料行驶xi千米.Byteasar可以在任意点改变出租车.所有的出租车从他们的总部出发但没必要返回总部.你的任务是判断Byteasar是否能从Bytehole镇到Bytepit镇,如果可以,求出路途需要出租车的最小数量.

inputFormat:
The first line of the standard input holds three integers, $m$, $d$, and $n$ ($1\le d\le m\le 10^{18}$, $1\le n\le 500\ 000$),separated by single spaces.

Those denote, respectively: the distance from Bytehole to Bytepit,the distance from Bytehole to the taxi base, and the number of taxis at the base.

The second line of input contains $n$ integers, $x_1,x_2,\cdots,x_n$ ($1\le x_i\le 10^{18}$), separated by single spaces.

The number $x_i$ denotes the maximum distance (in kilometres) that the      i-th taxi can travel.

第一行的标准输入有三个字母m,d,和n(1≤d≤m≤1e18,1≤n≤500000)中间由空格隔开.

这些分别表示:从Bytehole镇到Bytepit镇的距离,从Bytehole镇到出租车总部的距离,总部的出租车数量.

第二行输入包含n个字母;x1,x2...xn(1≤xi≤1e18),中间由空格隔开.

数字xi表示第i个出租车能行驶的最大距离

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

the minimum number of taxis Byteasar has to take to get from Bytehole to Bytepit.  If getting there is impossible, your program should print the number $0$.

你的程序应该输出一个数字:需要的最小数量的出租车数量.如果不能到达,输出0.

hint: 提示:此题需开long long


title: [POI2013] USU-Take-out

description:
Little Edna has received the take-out game as a present.

Take-out is a single player game, in which the player is given a sequence of $n$ adjacent blocks, numbered from $1$ to $n$.

Each block is either black or white, and there are $k$ times as many white    blocks as there are black ones.

The player's goal is to remove all the blocks by certain permissible moves.

A single move consists in removing exactly $k$ white blocks and a single    black block without changing the positions of other blocks.

The move is permissible if there is no "gap" (a space left by    a previously taken out block) between any two blocks being removed.

Help poor little Edna in finding any sequence of permissible moves that    remove all the blocks.

有n块砖，其中白色是黑色的k倍，求一个消除序列，满足以下条件：

每次消除k+1个砖，其中k块白色，1块黑色，并且这k+1块砖从开始到结束，中间不能路过已经消除过的砖

数据保证有解

inputFormat:
In the first line of the standard input there are two integers, $n$ and $k$ ($2\le n\le 1\ 000\ 000$, $1\le k\le n-1$), separated by a single space, that denote the total number of blocks used in the gameand the number of white blocks per black node (to be removed in every move).  In all the tests the condition $k+1|n$ holds.

In the second line there is a string of $n$ letters b      or c.  These tell the colours of successive blocks (in Polish):

b (for biały) - white, c (for czarny)      - black.  You may assume that in all the tests there exists a sequence      of permissible moves that takes out all the blocks.

outputFormat:
Your program should print $\frac{n}{k+1}$ lines to the standard output.

Successive lines should describe successive moves.

Each line should contain $k+1$ integers, in increasing order,separated by single spaces, that denote the numbers of blocks to be removed in the move.

hint:
有n块砖，其中白色是黑色的k倍，求一个消除序列，满足以下条件：

每次消除k+1个砖，其中k块白色，1块黑色，并且这k+1块砖从开始到结束，中间不能路过已经消除过的砖

数据保证有解

返回`TAT1`：同一个位置输出$2$次

返回`TAT2`：输出的$k+1$个位置不满足白色是黑色$k$倍

返回`TAT3`：未按照升序输出或者中间路过已经消除的砖

SPJ provided by @colazcy


title: [POI2013] SPA-Walk

description:
The names of towns in Byteotia are unique sequences of exactly $n$ bits.

There are $2^n-k$ towns in Byteotia, and thus,only $k$ sequences of $n$ bits do not correspond to any town.

Some pairs of towns are connected with roads.

Specifically, two towns are directly linked by a road if and only if their names differ in a single bit.

The roads do not cross outside of towns.

Byteasar intends to take a stroll - he intends to walk from the town $x$ to the town $y$, taking the existing roads.

Your task is to write a program that will determine if such a walk is possible.

有2^n个长度为n的01串，两个01串之间有边当且仅当这两个01串只有一位不同，现在从这2n个串中拿掉k个，问指定两个串之间能否到达

inputFormat:
In the first line of the standard input, there are two integers,$n$ and $k$($1\le n\le 60$, $0\le k\le 1\ 000\ 000$, $k\le 2^n-1$, $n\times k\le 5\ 000\ 000$),      separated by a single space.

These are the length of town names in bits and the the number of $n$-bit sequences that do not correspond to any town, respectively.

In the second line, there are two strings, separated by a single space,      each consisting of $n$ characters 0 and/or 1.

These are the names of the towns $x$ and $y$.

In the $k$ lines that follow, all the sequences of $n$ bits that do not correspond to any town are given, one sequence per line.In the $k$ lines that follow, all the sequences of $n$ bits that do not correspond to any town are given, one sequence per line.Each such sequence is a string of $n$ characters 0 and/or 1.You may assume that $x$ and $y$ are not among those $k$ sequences.

outputFormat: Your program should print to the standard output the word TAK (Polish for yes) if walking from the town x to the town y is possible, and the word NIE (Polish for no) otherwise.


title: [POI2013] INS-Inspector

description:
Inspector Byteasar is investigating a crime that took place on the premises of a software development company.

He is trying to establish the chain of events.

Unfortunately, the programmers are rather scatterbrained.

Statements of the kind "Well, when I checked at 14:42,    there were five other programmers logged in on the server."    are the most informative of those that Byteasar could get.

It is known that every programmer came to office at some point    during that day, spent some time in there without going out,    and then left for good, never coming back on the same day.

Byteasar, confused by the programmers' statements, is not sure    if he should rely on them.  In fact, he is wondering whether it is at all    possible that they all tell the truth.  He asks you for help in finding    that out.

一天公司有n个员工和m个员工记录，每个员工只会在连续的一段时间内工作。现在给出m条记录分别是谁写的、什么时候写的以及写的时候除了他还有多少人。求最大的k使得前k条记录互不矛盾

inputFormat:
In the first line of the standard input, there is an integer $z$($1\le z\le 50$),      the number of data sets.

The lines that follow contain the $z$ data sets.

The first line of each data set holds two integers, $n$ and $m$,separated by a single space ($1\le n,m\le 100\ 000$).

These are the number of programmers working in the office and the      number of statements recorded by Byteasar.

The programmers are numbered from 1 to $n$.

Each of the $m$ lines that follow describes a single statement.

Each such line contains three integers $t$,$j$ and $i$, separated by single spaces ($1\le t\le m$,$1\le j\le n$,$0\le i\le n$). These indicate that the programmer no. $j$ confessed that at time $t$ he was in the office and there were $i$ more programmers apart from him.We assume that the programmers came in to the office and left it at times different from those appearing in the statements, i.e., either before, after or in between them.

outputFormat:
For each data set, your program should print a single positive integer      to the standard output.

Printing out the number $k$ ($1\le k\le m$) indicates that the first $k$ statements given on the input can be true but the first $k+1$ statements cannot.  In particular, if $k=m$, then all the statements given as input can be true.


title: [POI2013] LUK-Triumphal arch

description:
The king of Byteotia, Byteasar, is returning to his country after a victorious battle.

In Byteotia, there are ![](http://main.edu.pl/images/OI20/luk-en-tex.1.png) towns connected with only ![](http://main.edu.pl/images/OI20/luk-en-tex.2.png) roads.

It is known that every town can be reached from every other town by a unique route,    consisting of one or more (direct) roads.

    (In other words, the road network forms a tree).

The king has just entered the capital.

Therein a triumphal arch, i.e., a gate a victorious king rides through, has been erected.

Byteasar, delighted by a warm welcome by his subjects, has planned a    triumphal procession to visit all the towns of Byteotia, starting with the capital he is currently in.

The other towns are not ready to greet their king just yet -    the constructions of the triumphal arches in those towns did not even begin!

But Byteasar's trusted advisor is seeing to the issue.

    He desires to hire a number of construction crews.

    Every crew can construct a single arch each day, in any town.

    Unfortunately, no one knows the order in which the king will visit the towns.

The only thing that is clear is that every day the king will travel from the city he is currently in to a neighboring one.

The king may visit any town an arbitrary number of times    (but as he is not vain, one arch in each town will suffice).

Byteasar's advisor has to pay each crew the same flat fee, regardless of how many arches this crew builds.

Thus, while he needs to ensure that every town has an arch when it is visited by the king, he wants to hire as few crews as possible.

Help him out by writing a program that will determine the minimum number    of crews that allow a timely delivery of the arches.

给一颗 $n$ 个节点的树（$n \le 3 \times 10^5$），初始时 $1$ 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 $1$ 号节点。每一轮，A 选择 $k$ 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 $k$ 。

inputFormat:
The first line of the standard input contains a single integer ![](http://main.edu.pl/images/OI20/luk-en-tex.3.png)    (![](http://main.edu.pl/images/OI20/luk-en-tex.4.png)), the number of towns in Byteotia.

The towns are numbered from 1 to ![](http://main.edu.pl/images/OI20/luk-en-tex.5.png), where the number 1 corresponds to the capital.

The road network is described in ![](http://main.edu.pl/images/OI20/luk-en-tex.6.png) lines that then follow.

Each of those lines contains two integers, ![](http://main.edu.pl/images/OI20/luk-en-tex.7.png)    (![](http://main.edu.pl/images/OI20/luk-en-tex.8.png)), separated by a single space,    indicating that towns ![](http://main.edu.pl/images/OI20/luk-en-tex.9.png) and ![](http://main.edu.pl/images/OI20/luk-en-tex.10.png) are directly connected with a two way road.

In tests worth 50% of the total points, an additional condition ![](http://main.edu.pl/images/OI20/luk-en-tex.11.png) holds.

outputFormat: The first and only line of the standard output is to hold a single integer,    the minimum number of crews that Byteasar's advisor needs to hire.

hint: 给一颗树，1号节点已经被染黑，其余是白的，两个人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步，如果B能走到A没染的节点则B胜，否则当A染完全部的点时，A胜。求能让A获胜的最小的k


title: [POI2013] MOR-Tales of seafaring

description:
Young Bytensson loves to hang out in the port tavern, where he often    listens to the sea dogs telling their tales of seafaring.

Initially, he believed them all, however incredible they sounded.

Over time though, he became suspicious.

He has decided to write a program that will verify if there may be    any grain of truth in those tall stories.

Bytensson reasoned that while he cannot tell if the sailors indeed    weathered all those storms, he can at least find out if their travel    itineraries make sense.

This is a task for a programmer, which Bytensson, unfortunately, is not.

Help him out!

There are $n$ ports and $m$ waterways connecting them in the waters    frequented by the sailors Bytensson listened to.

If there is a waterway between two ports, then sailing from one to the    other is possible.  Any waterway can be sailed in both    directions.

Bytensson got to know $k$ seafaring tales.

Each tells of a sailor who began his journey in one port,    sailed a number of waterways, and ended up in another port,    which may have been the one he initially set sail from.

The sailor in question may have sailed through the same waterway    many times, each time in any direction.

给n个点m条边无向图，每次询问两个点之间是否有长度为d的路径（不一定是简单路径）

inputFormat:
In the first line of the standard input, there are three integers, $n$,$m$ and $k$ ($2\le n\le 5\ 000$, $1\le m\le 5\ 000$, $1\le k\le 1\ 000\ 000$).

These denote, respectively: the number of ports in the waters      frequented by the sailors who told Bytensson their stories,the number of waterways, and the number of tales.

The $m$ lines that follow specify the waterways.

A single waterway's description consists of a single line that contains two integers, $a$ and $b$ ($1\le a,b\le n$,$a\ne b$), separated by a single space; these specify the numbers of ports at the two ends of this particular waterway.

The $k$ lines that follow specify the tales that Bytensson has heard. A single tale's description consists of a single line with three integers,$s$,$t$,and $d$ ($1\le s,t\le n$,$1\le d\le 1\ 000\ 000\ 000$ ), separated by single spaces. These indicate that the tale's protagonist set sail from port no. $s$ , ended the journey in port no. $t$ , and sailed exactly $d$ times through various waterways.

outputFormat:
Your program should print exactly $k$ lines to the standard output; the $i$-th of them should contain the word TAK (Polish for yes) if the journey described in the $i$-th tale(in input order) could have taken place.

If it could not, then the line should contain the word NIE (Polish for no).