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 c++17.

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:
```cpp
<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
There are n parliamentarians in Berland. They are numbered with integers from 1 to n. It happened that all parliamentarians with odd indices are Democrats and all parliamentarians with even indices are Republicans.

New parliament assembly hall is a rectangle consisting of a × b chairs — a rows of b chairs each. Two chairs are considered neighbouring if they share as side. For example, chair number 5 in row number 2 is neighbouring to chairs number 4 and 6 in this row and chairs with number 5 in rows 1 and 3. Thus, chairs have four neighbours in general, except for the chairs on the border of the hall

We know that if two parliamentarians from one political party (that is two Democrats or two Republicans) seat nearby they spent all time discussing internal party issues.

Write the program that given the number of parliamentarians and the sizes of the hall determine if there is a way to find a seat for any parliamentarian, such that no two members of the same party share neighbouring seats.

## Input Format
The first line of the input contains three integers n, a and b (1 ≤ n ≤ 10 000, 1 ≤ a, b ≤ 100) — the number of parliamentarians, the number of rows in the assembly hall and the number of seats in each row, respectively.

## Output Format
If there is no way to assigns seats to parliamentarians in a proper way print -1.

Otherwise print the solution in a lines, each containing b integers. The j-th integer of the i-th line should be equal to the index of parliamentarian occupying this seat, or 0 if this seat should remain empty. If there are multiple possible solution, you may print any of them.

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

## Note
In the first sample there are many other possible solutions. For example,

and

The following assignment

is incorrect, because parliamentarians 1 and 3 are both from Democrats party but will occupy neighbouring seats.

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 History of Magic is perhaps the most boring subject in the Hogwarts school of Witchcraft and Wizardry. Harry Potter is usually asleep during history lessons, and his magical quill writes the lectures for him. Professor Binns, the history of magic teacher, lectures in such a boring and monotonous voice, that he has a soporific effect even on the quill. That's why the quill often makes mistakes, especially in dates.

So, at the end of the semester Professor Binns decided to collect the students' parchments with notes and check them. Ron Weasley is in a panic: Harry's notes may contain errors, but at least he has some notes, whereas Ron does not have any. Ronald also has been sleeping during the lectures and his quill had been eaten by his rat Scabbers. Hermione Granger refused to give Ron her notes, because, in her opinion, everyone should learn on their own. Therefore, Ron has no choice but to copy Harry's notes.

Due to the quill's errors Harry's dates are absolutely confused: the years of goblin rebellions and other important events for the wizarding world do not follow in order, and sometimes even dates from the future occur. Now Ron wants to change some of the digits while he copies the notes so that the dates were in the chronological (i.e. non-decreasing) order and so that the notes did not have any dates strictly later than 2011, or strictly before than 1000. To make the resulting sequence as close as possible to the one dictated by Professor Binns, Ron will change no more than one digit in each date into other digit. Help him do it.

## Input Format
The first input line contains an integer n (1 ≤ n ≤ 1000). It represents the number of dates in Harry's notes. Next n lines contain the actual dates y1, y2, ..., yn, each line contains a date. Each date is a four-digit integer (1000 ≤ yi ≤ 9999).

## Output Format
Print n numbers z1, z2, ..., zn (1000 ≤ zi ≤ 2011). They are Ron's resulting dates. Print each number on a single line. Numbers zi must form the non-decreasing sequence. Each number zi should differ from the corresponding date yi in no more than one digit. It is not allowed to change the first digit of a number into 0. If there are several possible solutions, print any of them. If there's no solution, print "No solution" (without the quotes).

## Examples
```input
3
1875
1936
1721
```
```output
1835
1836
1921
```
-----
```input
4
9999
2000
3000
3011
```
```output
1999
2000
2000
2011
```
-----
```input
3
1999
5055
2000
```
```output
No solution
```

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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya likes everything infinite. Now he is studying the properties of a sequence s, such that its first element is equal to a (s1 = a), and the difference between any two neighbouring elements is equal to c (si - si - 1 = c). In particular, Vasya wonders if his favourite integer b appears in this sequence, that is, there exists a positive integer i, such that si = b. Of course, you are the person he asks for a help.

## Input Format
The first line of the input contain three integers a, b and c ( - 109 ≤ a, b, c ≤ 109) — the first element of the sequence, Vasya's favorite number and the difference between any two neighbouring elements of the sequence, respectively.

## Output Format
If b appears in the sequence s print "YES" (without quotes), otherwise print "NO" (without quotes).

## Examples
```input
1 7 3
```
```output
YES
```
-----
```input
10 10 0
```
```output
YES
```
-----
```input
1 -4 5
```
```output
NO
```
-----
```input
0 60 50
```
```output
NO
```

## Note
In the first sample, the sequence starts from integers 1, 4, 7, so 7 is its element.

In the second sample, the favorite integer of Vasya is equal to the first element of the sequence.

In the third sample all elements of the sequence are greater than Vasya's favorite integer.

In the fourth sample, the sequence starts from 0, 50, 100, and all the following elements are greater than Vasya's favorite integer.

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
Vasya works as a watchman in the gallery. Unfortunately, one of the most expensive paintings was stolen while he was on duty. He doesn't want to be fired, so he has to quickly restore the painting. He remembers some facts about it.

- The painting is a square 3 × 3, each cell contains a single integer from 1 to n, and different cells may contain either different or equal integers.
- The sum of integers in each of four squares 2 × 2 is equal to the sum of integers in the top left square 2 × 2.
- Four elements a, b, c and d are known and are located as shown on the picture below.

Help Vasya find out the number of distinct squares the satisfy all the conditions above. Note, that this number may be equal to 0, meaning Vasya remembers something wrong.

Two squares are considered to be different, if there exists a cell that contains two different integers in different squares.

## Input Format
The first line of the input contains five integers n, a, b, c and d (1 ≤ n ≤ 100 000, 1 ≤ a, b, c, d ≤ n) — maximum possible value of an integer in the cell and four integers that Vasya remembers.

## Output Format
Print one integer — the number of distinct valid squares.

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

## Note
Below are all the possible paintings for the first sample.

In the second sample, only paintings displayed below satisfy all the rules.

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
During the programming classes Vasya was assigned a difficult problem. However, he doesn't know how to code and was unable to find the solution in the Internet, so he asks you to help.

You are given a sequence $$$a$$$, consisting of $$$n$$$ distinct integers, that is used to construct the binary search tree. Below is the formal description of the construction process.

1. First element $$$a_1$$$ becomes the root of the tree.
2. Elements $$$a_2, a_3, \ldots, a_n$$$ are added one by one. To add element $$$a_i$$$ one needs to traverse the tree starting from the root and using the following rules:   The pointer to the current node is set to the root.  If $$$a_i$$$ is greater than the value in the current node, then its right child becomes the current node. Otherwise, the left child of the current node becomes the new current node.  If at some point there is no required child, the new node is created, it is assigned value $$$a_i$$$ and becomes the corresponding child of the current node.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — the length of the sequence $$$a$$$.

The second line contains $$$n$$$ distinct integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the sequence $$$a$$$ itself.

## Output Format
Output $$$n - 1$$$ integers. For all $$$i > 1$$$ print the value written in the node that is the parent of the node with value $$$a_i$$$ in it.

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

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
Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

## Input Format
The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

## Output Format
Print one integer — the number of times Kolya will have to empty the waste section.

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

## Note
In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

Now solve the problem and return the code.