apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 0.5 seconds
Memory limit: 64.0 MB

# Problem
It was decided in IT City to distinguish successes of local IT companies by awards in the form of stars covered with gold from one side. To order the stars it is necessary to estimate order cost that depends on the area of gold-plating. Write a program that can calculate the area of a star.

A "star" figure having n ≥ 5 corners where n is a prime number is constructed the following way. On the circle of radius r n points are selected so that the distances between the adjacent ones are equal. Then every point is connected by a segment with two maximally distant points. All areas bounded by the segments parts are the figure parts.

## Input Format
The only line of the input contains two integers n (5 ≤ n < 109, n is prime) and r (1 ≤ r ≤ 109) — the number of the star corners and the radius of the circumcircle correspondingly.

## Output Format
Output one number — the star area. The relative error of your answer should not be greater than 10 - 7.

## Examples
```input
7 10
```
```output
108.395919545675
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 0.5 seconds
Memory limit: 64.0 MB

# Problem
IT City administration has no rest because of the fame of the Pyramids in Egypt. There is a project of construction of pyramid complex near the city in the place called Emerald Walley. The distinction of the complex is that its pyramids will be not only quadrangular as in Egypt but also triangular and pentagonal. Of course the amount of the city budget funds for the construction depends on the pyramids' volume. Your task is to calculate the volume of the pilot project consisting of three pyramids — one triangular, one quadrangular and one pentagonal.

The first pyramid has equilateral triangle as its base, and all 6 edges of the pyramid have equal length. The second pyramid has a square as its base and all 8 edges of the pyramid have equal length. The third pyramid has a regular pentagon as its base and all 10 edges of the pyramid have equal length.

## Input Format
The only line of the input contains three integers l3, l4, l5 (1 ≤ l3, l4, l5 ≤ 1000) — the edge lengths of triangular, quadrangular and pentagonal pyramids correspondingly.

## Output Format
Output one number — the total volume of the pyramids. Absolute or relative error should not be greater than 10 - 9.

## Examples
```input
2 5 3
```
```output
38.546168065709
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 0.5 seconds
Memory limit: 64.0 MB

# Problem
There is a legend in the IT City college. A student that failed to answer all questions on the game theory exam is given one more chance by his professor. The student has to play a game with the professor.

The game is played on a square field consisting of n × n cells. Initially all cells are empty. On each turn a player chooses and paint an empty cell that has no common sides with previously painted cells. Adjacent corner of painted cells is allowed. On the next turn another player does the same, then the first one and so on. The player with no cells to paint on his turn loses.

The professor have chosen the field size n and allowed the student to choose to be the first or the second player in the game. What should the student choose to win the game? Both players play optimally.

## Input Format
The only line of the input contains one integer n (1 ≤ n ≤ 1018) — the size of the field.

## Output Format
Output number 1, if the player making the first turn wins when both players play optimally, otherwise print number 2.

## Examples
```input
1
```
```output
1
```
-----
```input
2
```
```output
2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The 9-th grade student Gabriel noticed a caterpillar on a tree when walking around in a forest after the classes. The caterpillar was on the height h1 cm from the ground. On the height h2 cm (h2 > h1) on the same tree hung an apple and the caterpillar was crawling to the apple.

Gabriel is interested when the caterpillar gets the apple. He noted that the caterpillar goes up by a cm per hour by day and slips down by b cm per hour by night.

In how many days Gabriel should return to the forest to see the caterpillar get the apple. You can consider that the day starts at 10 am and finishes at 10 pm. Gabriel's classes finish at 2 pm. You can consider that Gabriel noticed the caterpillar just after the classes at 2 pm.

Note that the forest is magic so the caterpillar can slip down under the ground and then lift to the apple.

## Input Format
The first line contains two integers h1, h2 (1 ≤ h1 < h2 ≤ 105) — the heights of the position of the caterpillar and the apple in centimeters.

The second line contains two integers a, b (1 ≤ a, b ≤ 105) — the distance the caterpillar goes up by day and slips down by night, in centimeters per hour.

## Output Format
Print the only integer k — the number of days Gabriel should wait to return to the forest and see the caterpillar getting the apple.

If the caterpillar can't get the apple print the only integer  - 1.

## Examples
```input
10 30
2 1
```
```output
1
```
-----
```input
10 13
1 1
```
```output
0
```
-----
```input
10 19
1 2
```
```output
-1
```
-----
```input
1 50
5 4
```
```output
1
```

## Note
In the first example at 10 pm of the first day the caterpillar gets the height 26. At 10 am of the next day it slips down to the height 14. And finally at 6 pm of the same day the caterpillar gets the apple.

Note that in the last example the caterpillar was slipping down under the ground and getting the apple on the next day.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A student of z-school found a kind of sorting called z-sort. The array a with n elements are z-sorted if two conditions hold:

1. ai ≥ ai - 1 for all even i,
2. ai ≤ ai - 1 for all odd i > 1.

For example the arrays [1,2,1,2] and [1,1,1,1] are z-sorted while the array [1,2,3,4] isn’t z-sorted.

Can you make the array z-sorted?

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of elements in the array a.

The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of the array a.

## Output Format
If it's possible to make the array a z-sorted print n space separated integers ai — the elements after z-sort. Otherwise print the only word "Impossible".

## Examples
```input
4
1 2 2 1
```
```output
1 2 1 2
```
-----
```input
5
1 3 2 2 5
```
```output
1 5 2 3 2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.

Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.

## Output Format
Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.

## Examples
```input
4
1 8
2 3
4 7
5 6
```
```output
3
0
1
0
```
-----
```input
3
3 4
1 5
2 6
```
```output
0
1
1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Johnny is playing a well-known computer game. The game are in some country, where the player can freely travel, pass quests and gain an experience.

In that country there are n islands and m bridges between them, so you can travel from any island to any other. In the middle of some bridges are lying ancient powerful artifacts. Johnny is not interested in artifacts, but he can get some money by selling some artifact.

At the start Johnny is in the island a and the artifact-dealer is in the island b (possibly they are on the same island). Johnny wants to find some artifact, come to the dealer and sell it. The only difficulty is that bridges are too old and destroying right after passing over them. Johnnie's character can't swim, fly and teleport, so the problem became too difficult.

Note that Johnny can't pass the half of the bridge, collect the artifact and return to the same island.

Determine if Johnny can find some artifact and sell it.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of islands and bridges in the game.

Each of the next m lines contains the description of the bridge — three integers xi, yi, zi (1 ≤ xi, yi ≤ n, xi ≠ yi, 0 ≤ zi ≤ 1), where xi and yi are the islands connected by the i-th bridge, zi equals to one if that bridge contains an artifact and to zero otherwise. There are no more than one bridge between any pair of islands. It is guaranteed that it's possible to travel between any pair of islands.

The last line contains two integers a and b (1 ≤ a, b ≤ n) — the islands where are Johnny and the artifact-dealer respectively.

## Output Format
If Johnny can find some artifact and sell it print the only word "YES" (without quotes). Otherwise print the word "NO" (without quotes).

## Examples
```input
6 7
1 2 0
2 3 0
3 1 0
3 4 1
4 5 0
5 6 0
6 4 0
1 6
```
```output
YES
```
-----
```input
5 4
1 2 0
2 3 0
3 4 0
2 5 1
1 4
```
```output
NO
```
-----
```input
5 6
1 2 0
2 3 0
3 1 0
3 4 0
4 5 1
5 3 0
1 2
```
```output
YES
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Barney has finally found the one, a beautiful young lady named Lyanna. The problem is, Lyanna and Barney are trapped in Lord Loss' castle. This castle has shape of a convex polygon of n points. Like most of castles in Demonata worlds, this castle has no ceiling.

Barney and Lyanna have an escape plan, but it requires some geometry knowledge, so they asked for your help.

Barney knows that demons are organized and move in lines. He and Lyanna want to wait for the appropriate time so they need to watch for the demons. Each of them wants to stay in a point inside the castle (possibly on edges or corners), also they may stay in the same position. They both want to pick a real number r and watch all points in the circles with radius r around each of them (these two circles may overlap).

We say that Barney and Lyanna are watching carefully if and only if for every edge of the polygon, at least one of them can see at least one point on the line this edge lies on, thus such point may not be on the edge but it should be on edge's line. Formally, each edge line should have at least one common point with at least one of two circles.

The greater r is, the more energy and focus they need. So they asked you to tell them the minimum value of r such that they can watch carefully.

## Input Format
The first line of input contains a single integer n (3 ≤ n ≤ 300) — the number of castle polygon vertices.

The next n lines describe the polygon vertices in counter-clockwise order. i-th of them contains two integers xi and yi (|xi|, |yi| ≤ 104) — the coordinates of i-th point of the castle. It is guaranteed that given points form a convex polygon, in particular, any three of them do not line on the same line.

## Output Format
In the first line print the single number r — minimum radius of guys' watching circles.

In the second line print the pair of coordinates of point where Barney should stay.

In the third line print the pair of coordinates of point where Lyanna should stay.

Points should lie inside the polygon.

Coordinates may not be integers. If there are multiple answers print any of them.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 6.

## Examples
```input
4
-41 67
-16 20
25 25
-36 85
```
```output
0
-16 20
-36 85
```
-----
```input
7
-7 54
-5 31
-2 17
20 19
32 23
34 27
26 57
```
```output
2.9342248
32.019503 23.0390067
-6.929116 54.006444
```

## Note
In the first example guys can stay in opposite corners of the castle.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Small, but very brave, mouse Brain was not accepted to summer school of young villains. He was upset and decided to postpone his plans of taking over the world, but to become a photographer instead.

As you may know, the coolest photos are on the film (because you can specify the hashtag #film for such).

Brain took a lot of colourful pictures on colored and black-and-white film. Then he developed and translated it into a digital form. But now, color and black-and-white photos are in one folder, and to sort them, one needs to spend more than one hour!

As soon as Brain is a photographer not programmer now, he asks you to help him determine for a single photo whether it is colored or black-and-white.

Photo can be represented as a matrix sized n × m, and each element of the matrix stores a symbol indicating corresponding pixel color. There are only 6 colors:

- 'C' (cyan)
- 'M' (magenta)
- 'Y' (yellow)
- 'W' (white)
- 'G' (grey)
- 'B' (black)

The photo is considered black-and-white if it has only white, black and grey pixels in it. If there are any of cyan, magenta or yellow pixels in the photo then it is considered colored.

## Input Format
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100) — the number of photo pixel matrix rows and columns respectively.

Then n lines describing matrix rows follow. Each of them contains m space-separated characters describing colors of pixels in a row. Each character in the line is one of the 'C', 'M', 'Y', 'W', 'G' or 'B'.

## Output Format
Print the "#Black&White" (without quotes), if the photo is black-and-white and "#Color" (without quotes), if it is colored, in the only line.

## Examples
```input
2 2
C M
Y Y
```
```output
#Color
```
-----
```input
3 2
W W
W W
B B
```
```output
#Black&White
```
-----
```input
1 1
W
```
```output
#Black&White
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Katya studies in a fifth grade. Recently her class studied right triangles and the Pythagorean theorem. It appeared, that there are triples of positive integers such that you can construct a right triangle with segments of lengths corresponding to triple. Such triples are called Pythagorean triples.

For example, triples (3, 4, 5), (5, 12, 13) and (6, 8, 10) are Pythagorean triples.

Here Katya wondered if she can specify the length of some side of right triangle and find any Pythagorean triple corresponding to such length? Note that the side which length is specified can be a cathetus as well as hypotenuse.

Katya had no problems with completing this task. Will you do the same?

## Input Format
The only line of the input contains single integer n (1 ≤ n ≤ 109) — the length of some side of a right triangle.

## Output Format
Print two integers m and k (1 ≤ m, k ≤ 1018), such that n, m and k form a Pythagorean triple, in the only line.

In case if there is no any Pythagorean triple containing integer n, print  - 1 in the only line. If there are many answers, print any of them.

## Examples
```input
3
```
```output
4 5
```
-----
```input
6
```
```output
8 10
```
-----
```input
1
```
```output
-1
```
-----
```input
17
```
```output
144 145
```
-----
```input
67
```
```output
2244 2245
```

## Note
Illustration for the first sample.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya plays The Elder Trolls IV: Oblivon. Oh, those creators of computer games! What they do not come up with! Absolutely unique monsters have been added to the The Elder Trolls IV: Oblivon. One of these monsters is Unkillable Slug. Why it is "Unkillable"? Firstly, because it can be killed with cutting weapon only, so lovers of two-handed amber hammers should find suitable knife themselves. Secondly, it is necessary to make so many cutting strokes to Unkillable Slug. Extremely many. Too many!

Vasya has already promoted his character to 80-th level and in order to gain level 81 he was asked to kill Unkillable Slug. The monster has a very interesting shape. It looks like a rectangular parallelepiped with size x × y × z, consisting of undestructable cells 1 × 1 × 1. At one stroke Vasya can cut the Slug along an imaginary grid, i.e. cut with a plane parallel to one of the parallelepiped side. Monster dies when amount of parts it is divided reaches some critical value.

All parts of monster do not fall after each cut, they remains exactly on its places. I. e. Vasya can cut several parts with one cut.

Vasya wants to know what the maximum number of pieces he can cut the Unkillable Slug into striking him at most k times.

Vasya's character uses absolutely thin sword with infinite length.

## Input Format
The first line of input contains four integer numbers x, y, z, k (1 ≤ x, y, z ≤ 106, 0 ≤ k ≤ 109).

## Output Format
Output the only number — the answer for the problem.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

## Examples
```input
2 2 2 3
```
```output
8
```
-----
```input
2 2 2 1
```
```output
2
```

## Note
In the first sample Vasya make 3 pairwise perpendicular cuts. He cuts monster on two parts with the first cut, then he divides each part on two with the second cut, and finally he divides each of the 4 parts on two.

Now solve the problem and return the code.