## [Mirror] VNOI Cup 2022 - Final

**Time limit:**2.0s /

**Memory limit:**256M

**Points:** 100

You are given an undirected graph with ~n~ vertices and ~m~ edges, in which no edges connect a node to itself, as well as no pair of nodes are connected by more than one edge. Initially, each node in the graph is colored white. Your task is to color some nodes blue, such that ~q~ requirements are satisfied, the ~i~-th requirement stating that the shortest distance from node ~c_i~ to any blue node (possibly itself) is exactly ~d_i~.

#### Input

The first line contains three integers ~n~, ~m~ and ~q~ (~1 \le q \le n \le 5 \times 10^5~, ~0 \le m \le 5 \times 10^5~), denoting the number of nodes, the number of edges, and the number of requirements, respectively.

Each of the next ~m~ lines contains two integers ~u~ and ~v~ (~1 \le u, v \le n~, ~u \ne v~), denoting an edge between the two nodes ~u~ and ~v~. It is guaranteed that no pair of nodes are connected by more than one edge.

The next ~q~ lines, the ~i~-th of which contains two integers ~c_i~ and ~d_i~ (~1 \le c_i \le n~, ~0 \le d_i < n~) denoting the ~i~-th condition: the shortest distance from node ~c_i~ to any blue node (possibly itself) is exactly ~d_i~. It is guaranteed that each node appears in at most one condition.

#### Output

If there does not exist a coloring satisfying all requirements, output
`NO`

.

Otherwise, output `YES`

on the first line. On the second line, output a
single integer ~k~, the number of nodes to be colored blue. The third
line, output ~k~ integers ~p_1, p_2, \ldots, p_k~ (~p_i \ne p_j~ for
~i \ne j~), the indices of the nodes to be colored blue.

If there are multiple valid colorings, you may output any.

#### Scoring

**Not the final scoring**

Subtask 1 (~10~ points): ~n \le 16~.

Subtask 2 (~20~ points): ~n \le 5000~.

Subtask 3 (~70~ points): No additional constraints

The total score for this problem is ~100~.

#### Sample Input 1

```
7 8 3
1 2
2 3
3 4
4 1
4 5
5 6
6 4
5 7
7 2
4 1
2 1
```

#### Sample Output 1

```
YES
2
1 6
```

#### Sample Input 2

```
4 3 1
1 2
2 3
3 1
4 0
```

#### Sample Output 2

```
YES
2
1 4
```

#### Sample Input 3

```
3 3 1
1 2
2 3
3 1
1 2
```

#### Sample Output 3

```
NO
```

#### Notes

In the first example, we can color two nodes ~1~ and ~6~ blue:

From node ~7~, the closest blue node is node ~6~ can be reached by following the path ~7 \rightarrow 5 \rightarrow 6~.

From node ~4~, the closest blue node is node ~1~ can be reached by following the path ~4 \rightarrow 1~.

From node ~2~, the closest blue node is node ~1~ can be reached by following the path ~2 \rightarrow 1~.

Illustration of the first sample.

Another solution would be to color the nodes ~3~ and ~6~ blue.

In the second example, we can color the node ~4~ blue. The other nodes can be colored arbitrarily.

Illustration of the second sample.

In the third example, the distance from node ~1~ to both of the other two nodes is ~1~, therefore it is impossible to color a node such that the closest distance from ~1~ to a blue node is exactly ~2~.

**Time limit:**1.0s /

**Memory limit:**256M

**Points:** 100

You are given an integer ~n~. Construct an array ~a~ of positive integers satisfying the following requirements:

The elements of ~a~ do not exceed ~n + 1~.

All the elements of ~a~ are distinct.

For each ~x~ from ~2~ to ~n~, there exists a pair of indices ~(i, j)~ such that ~i \neq j~ and ~a_i \equiv a_j \pmod x~.

The length of ~a~ is as small as possible.

#### Input

The input contains a single integer ~n~ (~2 \le n \le 10^5~).

#### Output

In the first line, output a single integer ~k~ – the length of the constructed array ~a~.

In the second line, output ~k~ integers ~a_1, a_2, \ldots, a_k~. The array must satisfy all requirements in the statement.

If there are multiple possible answers, output any.

#### Scoring

Subtask 1 (~10~ points): ~n \le 16~.

Subtask 2 (~90~ points): No additional constraints

The total score for this problem is ~100~.

#### Sample Input 1

```
5
```

#### Sample Output 1

```
4
1 3 5 6
```

#### Notes

It can be easily seen that the array ~[1, 3, 5, 6]~ satisfies the first two requirements. We show that it satisfies the third requirement as well:

The pair of values ~1~ and ~5~ both has remainder ~1~ when divided by ~x = 2~.

The pair of values ~3~ and ~6~ are both divisible by ~x = 3~.

The pair of values ~1~ and ~5~ both has remainder ~1~ when divided by ~x = 4~.

The pair of values ~1~ and ~6~ both has remainder ~1~ when divided by ~x = 5~.

It can be shown that, for ~n = 5~, there exists no array ~a~ with length less than ~4~ satisfying all requirements.

**Time limit:**3.0s /

**Memory limit:**1G

**Points:** 100

Lục bát is a Vietnamese form of poem. As its Sino-Vietnamese namesake implies, a pair of lines in this poem contains one six-syllable line, and one eight-syllable line, rhyming with each other. A lục bát poem consists of many pairs of lines following said rule, without limits on the number of lines. Lục bát poem is a very popular form of poem in Vietnam, due to having simple rules, but is very easy to reminiscent in one's memory.

Specifically, in this problem, we define a lục bát poem as follow:

The poem has ~2 \cdot n~ lines, in which ~n~ of the lines are six-syllable, and ~n~ of the lines are eight-syllable.

The six-syllable lines will be in positions 1, 3, 5, ~\ldots~

The eight-syllable lines will be in positions 2, 4, 6, ~\ldots~

Each line's last syllable must

*rhyme*with the sixth syllable of its following line.Two lines are considered to

*rhyme*with each other if the*multiset*of*vowels*(the letters`a`

,`e`

,`i`

,`o`

và`u`

) of those two words are the same.

You are given ~n~ six-syllable lines and ~n~ eight-syllable lines, arrange these lines into a lục bát poem.

#### Input

The first line contains a single integer ~n~ (~1 \le n \le 10^5~), denoting the number of six-syllable lines and eight-syllable lines.

The ~i~-th line out of the next ~n~ lines each contain ~6~ words belonging to a six-syllable line.

The ~i~-th line out of the next ~n~ lines each contain ~8~ words belonging to a eight-syllable line.

Each word consists of only lowercase latin letters. The sum of length of all words do not exceed ~10^7~.

#### Output

If it is impossible to arrange these ~2n~ lines into a single poem
following the rule, output `NO`

.

Otherwise, output `YES`

on the first line. On the following ~2n~ lines,
output the poem.

#### Scoring

Subtask 1 (~10~ points): ~n \le 6~.

Subtask 2 (~90~ points): No additional constraints

The total score for this problem is ~100~.

#### Sample Input 1

```
2
nhi vang bong trang la xanh
trong dam gi dep bang sen
gan bun ma chang hoi tanh mui bun
la xanh bong trang lai chen nhi vang
```

#### Sample Output 1

```
YES
trong dam gi dep bang sen
la xanh bong trang lai chen nhi vang
nhi vang bong trang la xanh
gan bun ma chang hoi tanh mui bun
```

#### Sample Input 2

```
3
trai qua mot cuoc be dau
la gi bi sac tu phong
tram nam trong coi nguoi ta
troi xanh quen thoi ma hong danh ghen
chu tai chu menh kheo la ghet nhau
nhung dieu trong thay ma dau don long
```

#### Sample Output 2

```
YES
tram nam trong coi nguoi ta
chu tai chu menh kheo la ghet nhau
trai qua mot cuoc be dau
nhung dieu trong thay ma dau don long
la gi bi sac tu phong
troi xanh quen thoi ma hong danh ghen
```

**Time limit:**10.0s /

**Memory limit:**256M

**Points:** 150

**This is an interactive problem.**

Tài and his brother really takes play the number-making game. Firstly,
they will pick a prime number ~n~. Then they both prepare ~n~ blank
pieces of paper and arrange them horizontally. The papers are numbered
~1~ to ~n~ from **right to left**.

The game goes as follow. Two brothers will take turns, with Tài going first. On their turn, the player will pick a blank piece of paper that hasn't been written on, then write a single digit from ~0~ to ~9~ of their choice. The game ends when all of the papers have been written on.

Tài is learning algebra, and is much interested in divisibility of
numbers. Therefore Tài wants that after the game ends, the number
obtained by reading the digits on the papers from **left to right** will
be divisible by ~n~. Tài's brother on the other hand, wanting to add
some friendly competitiveness to be game, will actively try to make the
resulting number not divisible by ~n~.

Given the number ~n~ that the brothers picked, help Tài win the game by creating a number divisible by ~n~. Note that it is allowed that the resulting number may have leading zeroes.

#### Interaction

In this problem, you will play as Tài, and the jury will play as his brother.

The jury program will first print a single integer ~t~ (~1 \le t \le 10~), the number of game matches. Each match will happen as follow.

The jury program first prints a single integer ~n~ (~1 \le n \le 100\,000~, ~n~ is a prime number), the integer that the brothers picked.

Then you and the jury program will, ~n~ times in total, take turns printing two integers ~p~ and ~d~ (~1 \le p \le n~, ~0 \le d \le 9~), denoting on their respective turn, the player chooses to fill in the digit ~d~ into the paper indexed ~p~ **from right to left**.

After making ~n~ turns in total, the jury outputs a single integer ~x~ denoting the result. If the number created is indeed divisible by ~n~, the jury program outputs ~x = 1~. Afterwards you can proceed with the next match (if any). If the number created is not divisible by ~n~, the jury program outputs ~x = 0~, and will not provide you with additional inputs from that point onwards. In such case, your program must terminate to receive a `Wrong answer`

verdict, otherwise it may receive arbitrary verdict.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get `Time Limit Exceeded`

. To do this, use:

`fflush(stdout)`

or`cout.flush()`

in C++;`System.out.flush()`

in Java;`flush(output)`

in Pascal;`stdout.flush()`

in Python;- see documentation for other languages.

#### Scoring

Subtask 1 (~30~ points): ~n < 10~.

Subtask 2 (~120~ points): No additional constraints

The total score for this problem is ~150~.

#### Sample 1

Jury's program | Participant's program |
---|---|

2 2 2 5 1 3 2 3 1 |
1 8 1 5 3 7 |

#### Notes

There are ~t = 2~ matches.

In the first match with ~n = 2~, Tài goes first and fills in the first paper from right to left with the digit ~8~. The digits are now:

`_8`

Afterwards, the jury program chooses to fill in ~5~ to the remaining sheet. The digits are now:

`58`

The digits on the papers read ~58~, which is divisible by ~2~. Thereby the jury program outputs ~x = 1~ and begins the next match.

In the second match with ~n = 3~, Tài goes first and fills in the first paper from right to left with the digit ~5~. The digits are now:

`__5`

Afterwards, the jury program chooses to fill in ~3~ to the second sheet from right to left. The digits are now:

`_35`

Finally, Tài chooses the digit ~7~ to fill in the final sheet. The digits are now:

`735`

The row of paper reads ~735~, which is ~3~ so the jury outputs ~x = 1~ and terminates. Tài emerges victorious for all the matches.

**Time limit:**2.0s /

**Memory limit:**1G

**Points:** 150

Lộc likes dark cyan, because of that, when Lộc registers his first
account on a mysterious Online Judge, he chose the nickname `darkcyan`

.
Unfortunately, this nickname was taken. The system recommends Lộc a
couple of other nicknames, some of which are `darkcyan_no1`

,
`darkcyan_pro`

and `darkcyan_vip`

, none of which Lộc liked at all. After
spending a few eternities pondering, the nickname chosen by Lộc was
`dar`

, very similar to the initial nickname, only duplication the
__kk__cyan`k`

. This nickname turns out wasn't taken! So it became Lộc's new
nickname for many other different Online Judges.

Lộc finds changing nicknames like this interesting, and he applies this idea to create an entirely novel nickname suggestion system! For a nickname that's represented by a string with ~k~ characters ~t_1 t_2 \ldots t_l~, the system can change the nickname using the following operation several (possibly zero) times:

- The system selects an integer ~i~ (~1 \le i \le l~)
**at random**. Each position has equal probability of being chosen. The system then inserts ~c~ occurrences of the character ~t_i~ right after position ~i~. The new character's indices are ~i + 1, i + 2, \ldots, i + c - 1~ and the indices of every following characters are increased by ~c~. The length of the new nickname will be ~l + c~.

The exact value of ~c~, the number of extra characters inserted, is calculated as follow:

Initially, ~c \leftarrow 1~.

The system tosses a fair coin, having 50/50 chance of landing on either sides. While the coin lands on heads, ~c~ is increased by one.

The previous step may be repeated many times. However if ~c~ has already reached the limit ~k~, the system stops at that value of ~c~.

Formally, the value ~c~ is calculated with the following pseudocode

```
c = 1;
while c != k and coinToss() == head:
c = c + 1;
```

For example, suppose the starting nickname is `darkcyan`

(with length
~8~) and the limit ~k = 3~.

Nickname

`dar`

has a creation probability of ~\frac{1}{8} \cdot 50\% = \frac{1}{16}~ (the probability of choosing the character__kk__cyan`k`

is ~\frac{1}{8}~ and the probability of the coin toss landing*tails*is ~50\%~). Some other nicknames such as

,__dd__arkcyan`da`

or__rr__kcyan`darkcya`

has equal probability of being created to this one.__nn__Nickname

`dar`

has a creation probability of ~\frac{1}{8} \cdot 50\% \cdot 50\% = \frac{1}{32}~ (the probability of choosing the character__kkk__cyan`k`

is ~\frac{1}{8}~ and the probability of the first coin toss landing*heads*~50\%~, the probability of the second coin toss landing*tails*~50\%~). Some other nicknames such as

,__ddd__arkcyan`da`

or__rrr__kcyan`darkcya`

has equal probability of being created to this one.__nnn__Nicknames

`dar`

,__kkkk__cyan

,__dddd__arkkcyan`da`

or__rrrr__kcyan`darkcya`

has a probability of creation__nnnn__**not**~\frac{1}{64}~, but also ~\frac{1}{32}~, because at this point, ~c~ has already reached the ~k = 3~ limit.

**Note:** For ~k = -1~, the number of possible coin tosses is **not
limited**.

This design uses randomization to generate new nicknames. Lộc decides to go for this design choice to reduce cost of checking nickname availability, yet the probability of generating a brand new unused nickname is very high without needing to expect too many steps in the generating process.

Lộc thinks it's a pity if there's no existing nickname recommendation
system like this. So he decides to implement this system for the social
network *Virtual Network for Online Intercommunication* (VNOI) that he's
developing. On VNOI there are currently ~n~ users, the ~i~-th of which
has the nickname ~S_i~. Lộc wants to know, for each nickname ~S_i~, if
there is a new user who attempts to register with this nickname, what is
the **expected** number of steps needed to transform this username into
a brand new, unused username, following the aforementioned procedure. As
Lộc is a very busy developing other parts of the system, he needs your
help to solve this problem.

Given the list of nicknames of the ~n~ users on the system, for each
nickname ~S_i~, calculate the **expected** number of operations to turn
~S_i~ into a new, unused nickname, on the system. To ensure your
calculations are correct, output the answer modulo ~10^9 + 7~.

Formally, let ~M = 10^9 + 7~. We can show that the answer can be represented as an irreducible fraction ~\frac{p}{q}~, where ~p~ and ~q~ are integers and ~q \not \equiv 0 \pmod{M}~. Output ~p \cdot q^{-1} \bmod M~. In other words, output such an integer ~x~ that ~0 \le x < M~ and ~x \cdot q \equiv p \pmod{M}~.

#### Input

The first line contains two integers ~n~ and ~k~ (~1 \le n \le 10^5~,
~1 \le k \le 10^9~ or ~k = -1~), denoting the number of VNOI users and
the character limit in one operation. If ~k = -1~, the number of
characters that may be added in one operation is **not limited**.

The ~i~-th out of the next ~n~ lines each contain a single string ~S_i~ (~1 \le |S_i| \le 10^5~, ~S_i~ consists only of lowercase latin letters) denoting the nickname of the ~i~-th user.

Is it guaranteed that the total length of all nicknames do not exceed ~10^5~, and no two nicknames are the same.

#### Output

Output ~n~ lines. The ~i~-th line should contain the *expected number*
of operations needed to transform nickname ~S_i~ into a nickname that
has not appeared in the system, modulo ~10^9 + 7~.

#### Scoring

Subtask 1 (~45~ points): ~1 \le k \le 10~.

Subtask 2 (~105~ points): no additional constraints.

The total score for this problem is ~150~.

#### Sample Input 1

```
3 2
aaa
aa
a
```

#### Sample Output 1

```
1
500000005
250000004
```

#### Sample Input 2

```
2 -1
b
bbb
```

#### Sample Output 2

```
250000003
1
```

#### Sample Input 3

```
3 1
ab
aab
abb
```

#### Sample Output 3

```
2
1
1
```

#### Notes

In the first sample, the nickname `aa`

is expected to take ~\frac{3}{2}~
operations. Since the two operations are the same, we can skip the
character selection, and only look at the coin tossing process:

The probability of the result string being

`aaa`

would be ~50\%~ for getting tails on the first coin toss. Since this nickname has already appeared, we need another operation. Regardless of how the second operation turns out, we get a new nickname, thus the number of operations is ~2~.The probability of the result string being

`aaaa`

is ~50\%~ for the character addition limit is ~k = 2~. Since there is no other nickname matching this, we need ~1~ operation in this case.

Therefore the expected number of operations is ~50\% \cdot (2 + 1) = \frac{3}{2}~.

For the nickname `a`

in the first sample, the expected number of
operations is ~\frac{9}{4}~.

In the second sample, the number of characters that can be added in one
operation is unlimited. The nickname `b`

thus has the following
outcomes:

Creating the nickname

`bbb`

with probability ~50\% \cdot 50\% = 25\%~. In this case, we need one more operation to create a new nickname, thus the number of operations needed is ~2~.Creating the nickname

**other than**`bbb`

with probability ~1 - 25\% = 75\%~. In this case we have already obtained a new nickname, thus ~1~ is the number of operations needed.

Therefore, the expected number of operations is ~25\% \cdot 2 + 75\% \cdot 1 = \frac{5}{4}~.

**Time limit:**4.0s /

**Memory limit:**256M

**Points:** 200

**This is an interactive problem**.

~\textit{ngfam}~ has a *quantum* supercomputer peculiarly structures with ~n~
*quantum gates* numbered from ~1~ to ~n~. The ~i~-th *quantum gate* has
a characteristic parameter ~c_i~ ~(0 \leq c_i \leq 100)~.

To use the supercomputer, the user needs to input a non-negative integer
~a~. At the same time, the computer initializes a variable ~x = 1~.
Afterwards, the quantum gates from ~1~ to ~n~ will be activated
sequentially. When activating the ~i~-th gate, the computer changes ~x~
according to **one of the following possibilities**:

~x \leftarrow (x \times a) \bmod 998\,244\,353~

~x \leftarrow (x \times c_i) \bmod 998\,244\,353~

in which ~a \bmod b~ denoting the remainder of ~a~ when divided by ~b~.

Each outcome has the same probability of happening, and there are
totally ~2^n~ outcomes in the activation process of all *quantum gates*.
However, since this is a *quantum* supercomputer, so instead of
returning a specific value of ~x~, it returns the *overloaded* value of
~x~, equivalent to the expected value of ~x~ for all possible scenarios.

As the creator of the supercomputer, ~\textit{ngfam}~ has initialized the ~c_i~ parameter of the ~n~ gates to his liking, but ~\textit{ngfam}~ won't be telling you this info. On the other hand, ~\textit{ngfam}~ will let you play with his computer ~2 \cdot n~ times: you can pick the parameters ~a~ you want, and the computer returns the corresponding ~x~. When you're done, ~\textit{ngfam}~ wants to make sure that you understand what's going on in his supercomputer, therefore you need to answer to ~\textit{ngfam}~ ~q~ of the same questions from ~\textit{ngfam}~ without using his computer this time.

Note that the overloaded value itself may not be an integer, but the computer will return said value modulo ~998\,244\,353~.

Formally, let ~M = 998\,244\,353~ and the overloaded value is an irreducible fraction ~\frac{p}{q}~, where ~p~ and ~q~ are integers and ~q \not \equiv 0 \pmod{M}~. The computer returns ~p \cdot q^{-1} \bmod M~. In other words, the computer returns such an integer ~r~ that ~0 \le r < M~ and ~r \cdot q \equiv p \pmod{M}~.

#### Input

The first line contains two integers ~n~ and ~q~ (~1\le n \le 50\,000~, ~1 \le q \le 50~) denoting the number of quantum gates, and the number of questions you should answer, respectively.

Afterwards you should interact with the jury program.

#### Interaction

You are allowed to pose a maximum of ~2 \cdot n~ questions, each question must be printed by the form `? a`

(~0 \leq a < 998\,244\,353~). The jury responds with a single integer, that is the *overloaded value* of ~x~ after using the value ~a~.

When you're done, output on a single line `!`

denoting you are ready to answer questions.

Afterwards, you have to answer ~q~ questions from ~\textit{ngfam}~. For each question, the jury program gives you a single integer ~a~ (~0 \le a \le 998\,244\,353~). You need to calculate and provide the *overloaded value* of ~x~ that the computer would've returned if supplied with said value ~a~. You have to answer the questions sequentially, meaning you won't receive the next question (if any) without answering the current one first.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get `Time Limit Exceeded`

. To do this, use:

`fflush(stdout)`

or`cout.flush()`

in C++;`System.out.flush()`

in Java;`flush(output)`

in Pascal;`stdout.flush()`

in Python;- see documentation for other languages.

#### Scoring

Subtask 1 (~20~ points): ~n \le 50~ and ~1 \le c_i \le 2~.

Subtask 2 (~60~ points): ~n \le 50~.

Subtask 3 (~120~ points): No additional constraints.

The total score for this problem is ~200~.

#### Sample 1

Jury's program | Participant's program |
---|---|

2 2 5 499122184 1 2 |
? 3 ? 4 ! 499122178 3 |

#### Sample 2

Jury's program | Participant's program |
---|---|

1 5 3 1 2 3 4 5 |
? 1 ! 3 499122180 4 499122181 5 |

#### Notes

In the first sample, the distinctive parameters of the quantum gates are ~c_1 = 1~ and ~c_2 = 2~. The two questions asked were ~a = 3~ and ~a = 4~. For ~a = 3~, the following possibilities exist:

Therefore for ~a = 3~, the different possible values of ~x~ are ~[9, 6, 3, 2]~, and the expected value of ~x~ is ~\frac{9 + 6 + 3 + 2} {2^2} = \frac{20} {4} = 5~

For ~a = 4~, the possible values are:

~1 \times a \times a = 1 \times 4 \times 4 = 16~

~1 \times a \times c_2 = 1 \times 4 \times 2 = 8~

~1 \times c_1 \times a = 1 \times 1 \times 4 = 4~

~1 \times c_1 \times c_2 = 1 \times 1 \times 2 = 2~

The overloaded value of ~x~ on this computer for ~a = 4~ would be ~\frac{16 + 8 + 4 + 2} {2^2} = \frac{30}{4} = \frac{15}{2}~. The output is ~499122184~ since ~499122184 \times 2 \equiv 15 \bmod (998\,244\,353)~.

For ~a = 1~, the different possible values of ~x~ are ~[1, 2, 1, 2]~, and for ~a = 2~, the different possible values of ~x~ are ~[4, 4, 2, 2]~.

In the second example, the distinctive parameter of the only quantum gate is ~c_1 = 5~.

**Time limit:**2.0s /

**Memory limit:**256M

**Points:** 200

The *lower envelope* of a set of ~n~ lines, in which the ~i~-th line has
the equation ~y_i = a_i \cdot x + b_i~, has the graphical representation
~y = \min_{i = 1}^n\{ a_i \cdot x + b_i \}~.

We call the *vertices* of a lower envelope the points that lie on the
lower envelope that are also the intersection of two different segments
in the set. Let us suppose that the lower envelope has ~k~ vertices
~p_1, p_2, \ldots, p_k~, with vertex ~p_i~ at a smaller x-coordinate
than ~p_{i + 1}~ (~1 \le i < k~). We call the *perimeter* of the lower
envelope being the sum of distances between every two consecutive
vertices of the lower envelope, formally
~p_1 p_2 + p_2 p_3 + \ldots p_{k - 1} p_k~. If the lower envelope
contains less than two vertices, we consider the *perimeter* to be ~0~.

The lower envelope is colored orange. It has three vertices ~p_1~, ~p_2~ and
~p_3~. The perimeter is denoted by the **continuous** orange segment.

You are given ~n~ lines. For each line, find the *perimeter* of the
lower envelope created by the *remaining* ~n - 1~ lines.

#### Input

The first line contains an integer ~n~ (~2 \le n \le 100\, 000~), the number of lines.

The ~i~-th out of the next ~n~ lines contains two integers ~a_i~ và ~b_i~ (~|a_i|, |b_i| \le 10^9~), the parameters of the ~i~-th line.

It is guaranteed that there are no two lines that are the same.

#### Output

Output ~n~ lines. The ~i~-th of which contains the *perimeter* of the
lower envelope made by the other ~n - 1~ lines, that is, excluding line
~i~.

Your answer is considered correct if its absolute or relative error does not exceed ~10^{-6}~.

Formally, let your answer be ~a~, and the jury's answer be ~b~. Your answer is accepted if and only if ~\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}~.

#### Scoring

Subtask 1 (~30~ points): ~n \le 100~.

Subtask 2 (~40~ points): ~n \le 1000~.

Subtask 3 (~130~ points): No additional constraints.

The total score for this problem is ~200~.

#### Sample Input 1

```
4
0 0
0 1
1 0
-1 3
```

#### Sample Output 1

```
1.0
3.0
0
0
```

#### Sample Input 2

```
5
4 21
-3 -13
1 -3
3 15
1 -1
```

#### Sample Output 2

```
9.1923881554
0.0000000000
6.1282587703
7.7781745931
7.7781745931
```

#### Notes

Below is the illustration for sample 1.

The first line has the equation ~y = 0x + 0~ colored red. Excluding this line, the lower envelope has vertices ~B~ và ~C~.

The second line has the equation ~y = 0x + 1~ colored blue. Excluding this line, the lower envelope has vertices ~A~ và ~D~.

The third line has the equation ~y = x~ colored green. Excluding this line, the lower envelope has vertices ~D~.

The fourth line has the equation ~y = -x + 3~ colored purple. Excluding this line, the lower envelope has vertices ~A~.