1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Subset Mex
Contest: Codeforces Round 670 (Div. 2)
Difficulty rating: 900
Tags: greedy, implementation, math

Given a set of integers (it can contain equal elements).

You have to split it into two subsets $$$A$$$ and $$$B$$$ (both of them can contain equal elements or be empty). You have to maximize the value of $$$mex(A)+mex(B)$$$.

Here $$$mex$$$ of a set denotes the smallest non-negative integer that doesn't exist in the set. For example:

- $$$mex(\{1,4,0,2,2,1\})=3$$$
- $$$mex(\{3,3,2,1,3,0,0\})=4$$$
- $$$mex(\varnothing)=0$$$ ($$$mex$$$ for empty set)

The set is splitted into two subsets $$$A$$$ and $$$B$$$ if for any integer number $$$x$$$ the number of occurrences of $$$x$$$ into this set is equal to the sum of the number of occurrences of $$$x$$$ into $$$A$$$ and the number of occurrences of $$$x$$$ into $$$B$$$.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1\leq n\leq 100$$$) — the size of the set.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\dots a_n$$$ ($$$0\leq a_i\leq 100$$$) — the numbers in the set.

Output format:
For each test case, print the maximum value of $$$mex(A)+mex(B)$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In the first test case, $$$A=\left\{0,1,2\right\},B=\left\{0,1,5\right\}$$$ is a possible choice.

In the second test case, $$$A=\left\{0,1,2\right\},B=\varnothing$$$ is a possible choice.

In the third test case, $$$A=\left\{0,1,2\right\},B=\left\{0\right\}$$$ is a possible choice.

In the fourth test case, $$$A=\left\{1,3,5\right\},B=\left\{2,4,6\right\}$$$ is a possible choice.

Example input:
4
6
0 2 1 5 0 1
3
0 1 2
4
0 2 0 1
6
1 2 3 4 5 6

Example output:
5
3
4
0

Editorial:
Let us store the count of each number from $$$0$$$ to $$$100$$$ in array $$$cnt$$$.
Now $$$mex(A)$$$ would be the smallest $$$i$$$ for which $$$cnt_i=0$$$.Let this $$$i$$$ be $$$x$$$. $$$mex(B)$$$ would be smallest $$$i$$$ for which $$$cnt_i\leq 1$$$. This is because one count of each number less than $$$x$$$ would go to $$$A$$$ therefore the element which was present initially once would now not be available for $$$B$$$.
Overall Complexity: $$$O(n)$$$.
Maximum Product
Contest: Codeforces Round 670 (Div. 2)
Difficulty rating: 1200
Tags: brute force, dp, greedy, implementation, sortings

You are given an array of integers $$$a_1,a_2,\ldots,a_n$$$. Find the maximum possible value of $$$a_ia_ja_ka_la_t$$$ among all five indices $$$(i, j, k, l, t)$$$ ($$$i<j<k<l<t$$$).

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$5\le n\le 10^5$$$) — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-3\times 10^3\le a_i\le 3\times 10^3$$$) — given array.

It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, print one integer — the answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, choosing $$$a_1,a_2,a_3,a_4,a_5$$$ is a best choice: $$$(-1)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120$$$.

In the second test case, choosing $$$a_1,a_2,a_3,a_5,a_6$$$ is a best choice: $$$(-1)\cdot (-2) \cdot (-3)\cdot 2\cdot (-1)=12$$$.

In the third test case, choosing $$$a_1,a_2,a_3,a_4,a_5$$$ is a best choice: $$$(-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0$$$.

In the fourth test case, choosing $$$a_1,a_2,a_3,a_4,a_6$$$ is a best choice: $$$(-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945$$$.

Example input:
4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1

Example output:
-120
12
0
945

Editorial:
First, if all numbers are less than $$$0$$$, then you should print the product of the five biggest numbers of them.
Otherwise, the maximum product must be non-negative. Sort the numbers by their absolute value from big to small.
If the first five numbers' product is positive then print it. Then we can always change one of the five to one of the $$$n-5$$$ other numbers to make this product positive. Enumerate which one to replace, and you can solve this problem in $$$O(n)$$$ time.
Three Sequences
Contest: Codeforces Round 670 (Div. 2)
Difficulty rating: 2200
Tags: constructive algorithms, data structures, greedy, math

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$.

You have to construct two sequences of integers $$$b$$$ and $$$c$$$ with length $$$n$$$ that satisfy:

- for every $$$i$$$ ($$$1\leq i\leq n$$$) $$$b_i+c_i=a_i$$$
- $$$b$$$ is non-decreasing, which means that for every $$$1<i\leq n$$$, $$$b_i\geq b_{i-1}$$$ must hold
- $$$c$$$ is non-increasing, which means that for every $$$1<i\leq n$$$, $$$c_i\leq c_{i-1}$$$ must hold

You have to minimize $$$\max(b_i,c_i)$$$. In other words, you have to minimize the maximum number in sequences $$$b$$$ and $$$c$$$.

Also there will be $$$q$$$ changes, the $$$i$$$-th change is described by three integers $$$l,r,x$$$. You should add $$$x$$$ to $$$a_l,a_{l+1}, \ldots, a_r$$$.

You have to find the minimum possible value of $$$\max(b_i,c_i)$$$ for the initial sequence and for sequence after each change.

Input format:
The first line contains an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$).

The secound line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq i\leq n$$$, $$$-10^9\leq a_i\leq 10^9$$$).

The third line contains an integer $$$q$$$ ($$$1\leq q\leq 10^5$$$).

Each of the next $$$q$$$ lines contains three integers $$$l,r,x$$$ ($$$1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$$$), desribing the next change.

Output format:
Print $$$q+1$$$ lines.

On the $$$i$$$-th ($$$1 \leq i \leq q+1$$$) line, print the answer to the problem for the sequence after $$$i-1$$$ changes.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test:

- The initial sequence $$$a = (2, -1, 7, 3)$$$. Two sequences $$$b=(-3,-3,5,5),c=(5,2,2,-2)$$$ is a possible choice.
- After the first change $$$a = (2, -4, 4, 0)$$$. Two sequences $$$b=(-3,-3,5,5),c=(5,-1,-1,-5)$$$ is a possible choice.
- After the second change $$$a = (2, -4, 6, 2)$$$. Two sequences $$$b=(-4,-4,6,6),c=(6,0,0,-4)$$$ is a possible choice.

Example input:
4
2 -1 7 3
2
2 4 -3
3 4 2

Example output:
5
5
6

Example input:
6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3

Example output:
3
3
3
1

Editorial:
Since sequence $$$b$$$ is non-decreasing and sequence $$$c$$$ is non-increasing, we need to mimimize $$$\max(c_1,b_n)$$$.
Now observe that if $$$a_i>a_{i-1}$$$ then $$$b_i=b_{i-1}+a_i-a_{i-1}$$$ and $$$c_i=c_{i-1}$$$.Else if $$$a_i<a_{i-1}$$$ then $$$b_i=b_{i-1}$$$ but $$$c_i=c_{i-1}+a_i-a_{i-1}$$$. Now we calculate $$$\sum\limits_{i=2}^{n}\max(0,a_i-a_{i-1})$$$.Let this sum be $$$K$$$. Now lets assume $$$c_1$$$ is $$$x$$$. So then $$$b_1$$$ is $$$a_1-x$$$.And as observed before $$$b_n = a_1-x+K$$$.
Now we just need to minimize $$$\max(x,a_1-x+K)$$$. Now it is easily observable that $$$x$$$ should be $$$\dfrac{a_1+K}{2}$$$.
For the changes, since we only need to know $$$\sum\max(0,a_i-a_{i-1})$$$, so only $$$a_l-a_{l-1}$$$ and $$$a_r-a_{r-1}$$$ will change.
Total time complexity: $$$O(n+q)$$$.
The Miracle and the Sleeper
Contest: Codeforces Round 741 (Div. 2)
Difficulty rating: 800
Tags: greedy, math

You are given two integers $$$l$$$ and $$$r$$$, $$$l\le r$$$. Find the largest possible value of $$$a \bmod b$$$ over all pairs $$$(a, b)$$$ of integers for which $$$r\ge a \ge b \ge l$$$.

As a reminder, $$$a \bmod b$$$ is a remainder we get when dividing $$$a$$$ by $$$b$$$. For example, $$$26 \bmod 8 = 2$$$.

Input format:
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ $$$(1\le t\le 10^4)$$$, denoting the number of test cases. Description of the test cases follows.

The only line of each test case contains two integers $$$l$$$, $$$r$$$ ($$$1\le l \le r \le 10^9$$$).

Output format:
For every test case, output the largest possible value of $$$a \bmod b$$$ over all pairs $$$(a, b)$$$ of integers for which $$$r\ge a \ge b \ge l$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the only allowed pair is $$$(a, b) = (1, 1)$$$, for which $$$a \bmod b = 1 \bmod 1 = 0$$$.

In the second test case, the optimal choice is pair $$$(a, b) = (1000000000, 999999999)$$$, for which $$$a \bmod b = 1$$$.

Example input:
4
1 1
999999999 1000000000
8 26
1 999999999

Example output:
0
1
12
499999999

Editorial:
It's not hard to see that if $$$l \le \lfloor \frac{r}{2} \rfloor + 1$$$, then $$$r \bmod (\lfloor \frac{r}{2} \rfloor + 1) = \lfloor \frac{r-1}{2} \rfloor$$$. It can be shown that the maximal possible answer.
At the same time, let the segment not contain number $$$\lfloor \frac{r}{2} \rfloor + 1$$$, that is, $$$l > \lfloor \frac{r}{2} \rfloor + 1$$$. Then we can show that the maximal answer is $$$r \bmod l = r-l$$$.
Asymptotics: $$$O(1)$$$ per test case.
Road Repairs
Contest: Codeforces Round 145 (Div. 1, ACM-ICPC Rules)
Difficulty rating: 2800
Tags: dfs and similar, graphs, greedy

A country named Berland has n cities. They are numbered with integers from 1 to n. City with index 1 is the capital of the country. Some pairs of cities have monodirectional roads built between them. However, not all of them are in good condition. For each road we know whether it needs repairing or not. If a road needs repairing, then it is forbidden to use it. However, the Berland government can repair the road so that it can be used.

Right now Berland is being threatened by the war with the neighbouring state. So the capital officials decided to send a military squad to each city. The squads can move only along the existing roads, as there's no time or money to build new roads. However, some roads will probably have to be repaired in order to get to some cities.

Of course the country needs much resources to defeat the enemy, so you want to be careful with what you're going to throw the forces on. That's why the Berland government wants to repair the minimum number of roads that is enough for the military troops to get to any city from the capital, driving along good or repaired roads. Your task is to help the Berland government and to find out, which roads need to be repaired.

Input format:
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the number of cities and the number of roads in Berland.

Next m lines contain three space-separated integers ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ ci ≤ 1), describing the road from city ai to city bi. If ci equals 0, than the given road is in a good condition. If ci equals 1, then it needs to be repaired.

It is guaranteed that there is not more than one road between the cities in each direction.

Output format:
If even after all roads are repaired, it is still impossible to get to some city from the capital, print  - 1. Otherwise, on the first line print the minimum number of roads that need to be repaired, and on the second line print the numbers of these roads, separated by single spaces.

The roads are numbered starting from 1 in the order, in which they are given in the input.

If there are multiple sets, consisting of the minimum number of roads to repair to make travelling to any city from the capital possible, print any of them.

If it is possible to reach any city, driving along the roads that already are in a good condition, print 0 in the only output line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 2
1 3 0
3 2 1

Example output:
1
2

Example input:
4 4
2 3 0
3 4 0
4 1 0
4 2 1

Example output:
-1

Editorial:
TorCoder
Contest: Codeforces Round 145 (Div. 1, ACM-ICPC Rules)
Difficulty rating: 2600
Tags: data structures

A boy named Leo doesn't miss a single TorCoder contest round. On the last TorCoder round number 100666 Leo stumbled over the following problem. He was given a string s, consisting of n lowercase English letters, and m queries. Each query is characterised by a pair of integers li, ri (1 ≤ li ≤ ri ≤ n).

We'll consider the letters in the string numbered from 1 to n from left to right, that is, s = s1s2... sn.

After each query he must swap letters with indexes from li to ri inclusive in string s so as to make substring (li, ri) a palindrome. If there are multiple such letter permutations, you should choose the one where string (li, ri) will be lexicographically minimum. If no such permutation exists, you should ignore the query (that is, not change string s).

Everybody knows that on TorCoder rounds input line and array size limits never exceed 60, so Leo solved this problem easily. Your task is to solve the problem on a little bit larger limits. Given string s and m queries, print the string that results after applying all m queries to string s.

Input format:
The first input line contains two integers n and m (1 ≤ n, m ≤ 105) — the string length and the number of the queries.

The second line contains string s, consisting of n lowercase Latin letters.

Each of the next m lines contains a pair of integers li, ri (1 ≤ li ≤ ri ≤ n) — a query to apply to the string.

Output format:
In a single line print the result of applying m queries to string s. Print the queries in the order in which they are given in the input.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
A substring (li, ri) 1 ≤ li ≤ ri ≤ n) of string s = s1s2... sn of length n is a sequence of characters slisli + 1...sri.

A string is a palindrome, if it reads the same from left to right and from right to left.

String x1x2... xp is lexicographically smaller than string y1y2... yq, if either p < q and x1 = y1, x2 = y2, ... , xp = yp, or exists such number r (r < p, r < q), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 < yr + 1.

Example input:
7 2
aabcbaa
1 3
5 7

Example output:
abacaba

Example input:
3 2
abc
1 2
2 3

Example output:
abc

Editorial:
Omkar and Password
Contest: Codeforces Global Round 10
Difficulty rating: 800
Tags: greedy, math

Lord Omkar has permitted you to enter the Holy Church of Omkar! To test your worthiness, Omkar gives you a password which you must interpret!

A password is an array $$$a$$$ of $$$n$$$ positive integers. You apply the following operation to the array: pick any two adjacent numbers that are not equal to each other and replace them with their sum. Formally, choose an index $$$i$$$ such that $$$1 \leq i < n$$$ and $$$a_{i} \neq a_{i+1}$$$, delete both $$$a_i$$$ and $$$a_{i+1}$$$ from the array and put $$$a_{i}+a_{i+1}$$$ in their place.

For example, for array $$$[7, 4, 3, 7]$$$ you can choose $$$i = 2$$$ and the array will become $$$[7, 4+3, 7] = [7, 7, 7]$$$. Note that in this array you can't apply this operation anymore.

Notice that one operation will decrease the size of the password by $$$1$$$. What is the shortest possible length of the password after some number (possibly $$$0$$$) of operations?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the password.

The second line of each test case contains $$$n$$$ integers $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1 \leq a_{i} \leq 10^9$$$) — the initial contents of your password.

The sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output format:
For each password, print one integer: the shortest possible length of the password after some number of operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can do the following to achieve a length of $$$1$$$:

Pick $$$i=2$$$ to get $$$[2, 4, 1]$$$

Pick $$$i=1$$$ to get $$$[6, 1]$$$

Pick $$$i=1$$$ to get $$$[7]$$$

In the second test case, you can't perform any operations because there is no valid $$$i$$$ that satisfies the requirements mentioned above.

Example input:
2
4
2 1 3 1
2
420 420

Example output:
1
2

Editorial:
If your array consists of one number repeated $$$n$$$ times, then you obviously can't do any moves to shorten the password. Otherwise, you can show that it is always possible to shorten the password to $$$1$$$ number.
For an array consisting of $$$2$$$ or more distinct elements, considering the maximum value of the array. If its max value appears once, you can just repeat operations on the maximum array value until you are left with one number. What if the maximum elements appears more than once? Well, because there must exist at least $$$2$$$ distinct numbers, you can always pick a maximum element adjacent to a different number to perform an operation on. The array will then have one occurrence of a maximum and you can simply repeat using aforementioned logic.
Omkar and Infinity Clock
Contest: Codeforces Global Round 10
Difficulty rating: 800
Tags: implementation, math

Being stuck at home, Ray became extremely bored. To pass time, he asks Lord Omkar to use his time bending power: Infinity Clock! However, Lord Omkar will only listen to mortals who can solve the following problem:

You are given an array $$$a$$$ of $$$n$$$ integers. You are also given an integer $$$k$$$. Lord Omkar wants you to do $$$k$$$ operations with this array.

Define one operation as the following:

1. Set $$$d$$$ to be the maximum value of your array.
2. For every $$$i$$$ from $$$1$$$ to $$$n$$$, replace $$$a_{i}$$$ with $$$d-a_{i}$$$.

The goal is to predict the contents in the array after $$$k$$$ operations. Please help Ray determine what the final sequence will look like!

Input format:
Each test contains multiple test cases. The first line contains the number of cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{18}$$$) – the length of your array and the number of operations to perform.

The second line of each test case contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n}$$$ $$$(-10^9 \leq a_{i} \leq 10^9)$$$ – the initial contents of your array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each case, print the final version of array $$$a$$$ after $$$k$$$ operations described above.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case the array changes as follows:

- Initially, the array is $$$[-199, 192]$$$. $$$d = 192$$$.
- After the operation, the array becomes $$$[d-(-199), d-192] = [391, 0]$$$.

Example input:
3
2 1
-199 192
5 19
5 -1 4 2 0
1 2
69

Example output:
391 0
0 6 1 3 5
0

Editorial:
There's only two possible states the array can end up as. Which state it becomes after $$$k$$$ turns is determined solely by the parity of $$$k$$$.
After the first move, the array will consists of all non-negative numbers ($$$d-a_{i}$$$ will never be negative because $$$a_{i}$$$ never exceeds $$$d$$$). After one turn, let's define $$$x$$$ as max($$$a_{i}$$$) over all $$$i$$$. For any number $$$a_{i}$$$, it will turn into $$$x-a_{i}$$$. Because a zero will always exist after any one operation, $$$x$$$ will be the maximum of the array in the next turn as well. Then the value at index $$$i$$$ will turn into $$$x-(x-a_{i})$$$. This is just equal to $$$a_{i}$$$!
Now that it's obvious that our array will enter a cycle with a period of $$$2$$$, we simply do the following: If $$$k$$$ is odd, perform $$$1$$$ operation. Otherwise perform $$$2$$$ operations.
You're Given a String...
Contest: Codeforces Beta Round 23
Difficulty rating: 1200
Tags: brute force, greedy

You're given a string of lower-case Latin letters. Your task is to find the length of its longest substring that can be met in the string at least twice. These occurrences can overlap (see sample test 2).

Input format:
The first input line contains the string. It's guaranteed, that the string is non-empty, consists of lower-case Latin letters, and its length doesn't exceed 100.

Output format:
Output one number — length of the longest substring that can be met in the string at least twice.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
abcd

Example output:
0

Example input:
ababa

Example output:
3

Editorial:
Party
Contest: Codeforces Beta Round 23
Difficulty rating: 1600
Tags: constructive algorithms, graphs, math

n people came to a party. Then those, who had no friends among people at the party, left. Then those, who had exactly 1 friend among those who stayed, left as well. Then those, who had exactly 2, 3, ..., n - 1 friends among those who stayed by the moment of their leaving, did the same.

What is the maximum amount of people that could stay at the party in the end?

Input format:
The first input line contains one number t — amount of tests (1 ≤ t ≤ 105). Each of the following t lines contains one integer number n (1 ≤ n ≤ 105).

Output format:
For each test output in a separate line one number — the maximum amount of people that could stay in the end.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
1
3

Example output:
1

Editorial:
Oranges and Apples
Contest: Codeforces Beta Round 23
Difficulty rating: 2500
Tags: constructive algorithms, sortings

In 2N - 1 boxes there are apples and oranges. Your task is to choose N boxes so, that they will contain not less than half of all the apples and not less than half of all the oranges.

Input format:
The first input line contains one number T — amount of tests. The description of each test starts with a natural number N — amount of boxes. Each of the following 2N - 1 lines contains numbers ai and oi — amount of apples and oranges in the i-th box (0 ≤ ai, oi ≤ 109). The sum of N in all the tests in the input doesn't exceed 105. All the input numbers are integer.

Output format:
For each test output two lines. In the first line output YES, if it's possible to choose N boxes, or NO otherwise. If the answer is positive output in the second line N numbers — indexes of the chosen boxes. Boxes are numbered from 1 in the input order. Otherwise leave the second line empty. Separate the numbers with one space.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Example input:
2
2
10 15
5 7
20 18
1
0 0

Example output:
YES
1 3
YES
1

Editorial:
Tetragon
Contest: Codeforces Beta Round 23
Difficulty rating: 2600
Tags: geometry, math

You're given the centers of three equal sides of a strictly convex tetragon. Your task is to restore the initial tetragon.

Input format:
The first input line contains one number T — amount of tests (1 ≤ T ≤ 5·104). Each of the following T lines contains numbers x1, y1, x2, y2, x3, y3 — coordinates of different points that are the centers of three equal sides (non-negative integer numbers, not exceeding 10).

Output format:
For each test output two lines. If the required tetragon exists, output in the first line YES, in the second line — four pairs of numbers — coordinates of the polygon's vertices in clockwise or counter-clockwise order. Don't forget, please, that the tetragon should be strictly convex, i.e. no 3 of its points lie on one line. Output numbers with 9 characters after a decimal point.

If the required tetragon doen't exist, output NO in the first line, and leave the second line empty.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3
1 1 2 2 3 3
0 1 1 0 2 2
9 3 7 9 9 8

Example output:
NO
YES
3.5 1.5 0.5 2.5 -0.5 -0.5 2.5 0.5
NO

Editorial: