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

# Problem
Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset.

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed $$$1$$$.

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.

## Input Format
The first line contains the number of vertices $$$n$$$ ($$$2 \le n \le 700$$$).

The second line features $$$n$$$ distinct integers $$$a_i$$$ ($$$2 \le a_i \le 10^9$$$) — the values of vertices in ascending order.

## Output Format
If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than $$$1$$$, print "Yes" (quotes for clarity).

Otherwise, print "No" (quotes for clarity).

## Examples
```input
6
3 6 9 18 36 108
```
```output
Yes
```
-----
```input
2
7 17
```
```output
No
```
-----
```input
9
4 8 10 12 15 18 33 44 81
```
```output
Yes
```

## Note
The picture below illustrates one of the possible trees for the first example.

The picture below illustrates one of the possible trees for the third example.

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: 7.0 seconds
Memory limit: 512.0 MB

# Problem
A tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths $$$k$$$-valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly $$$k$$$ vertices.

You are given a tree with $$$n$$$ vertices. For each $$$k$$$ from $$$1$$$ to $$$n$$$ inclusive find what is the maximum possible size of a $$$k$$$-valid set of simple paths.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the number of vertices in the tree.

Then following $$$n - 1$$$ lines describe the tree, each of them contains two integers $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$) — endpoints of the corresponding edge.

It is guaranteed, that the given graph is a tree.

## Output Format
Output $$$n$$$ numbers, the $$$i$$$-th of which is the maximum possible number of paths in an $$$i$$$-valid set of paths.

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

## Note
One way to achieve the optimal number of paths for the second sample is illustrated in the following picture:

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
Awruk is taking part in elections in his school. It is the final round. He has only one opponent — Elodreip. The are $$$n$$$ students in the school. Each student has exactly $$$k$$$ votes and is obligated to use all of them. So Awruk knows that if a person gives $$$a_i$$$ votes for Elodreip, than he will get exactly $$$k - a_i$$$ votes from this person. Of course $$$0 \le k - a_i$$$ holds.

Awruk knows that if he loses his life is over. He has been speaking a lot with his friends and now he knows $$$a_1, a_2, \dots, a_n$$$ — how many votes for Elodreip each student wants to give. Now he wants to change the number $$$k$$$ to win the elections. Of course he knows that bigger $$$k$$$ means bigger chance that somebody may notice that he has changed something and then he will be disqualified.

So, Awruk knows $$$a_1, a_2, \dots, a_n$$$ — how many votes each student will give to his opponent. Help him select the smallest winning number $$$k$$$. In order to win, Awruk needs to get strictly more votes than Elodreip.

## Input Format
The first line contains integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of students in the school.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — the number of votes each student gives to Elodreip.

## Output Format
Output the smallest integer $$$k$$$ ($$$k \ge \max a_i$$$) which gives Awruk the victory. In order to win, Awruk needs to get strictly more votes than Elodreip.

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

## Note
In the first example, Elodreip gets $$$1 + 1 + 1 + 5 + 1 = 9$$$ votes. The smallest possible $$$k$$$ is $$$5$$$ (it surely can't be less due to the fourth person), and it leads to $$$4 + 4 + 4 + 0 + 4 = 16$$$ votes for Awruk, which is enough to win.

In the second example, Elodreip gets $$$11$$$ votes. If $$$k = 4$$$, Awruk gets $$$9$$$ votes and loses to Elodreip.

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
Bajtek, known for his unusual gifts, recently got an integer array $$$x_0, x_1, \ldots, x_{k-1}$$$.

Unfortunately, after a huge array-party with his extraordinary friends, he realized that he'd lost it. After hours spent on searching for a new toy, Bajtek found on the arrays producer's website another array $$$a$$$ of length $$$n + 1$$$. As a formal description of $$$a$$$ says, $$$a_0 = 0$$$ and for all other $$$i$$$ ($$$1 \le i \le n$$$) $$$a_i = x_{(i-1)\bmod k} + a_{i-1}$$$, where $$$p \bmod q$$$ denotes the remainder of division $$$p$$$ by $$$q$$$.

For example, if the $$$x = [1, 2, 3]$$$ and $$$n = 5$$$, then:

- $$$a_0 = 0$$$,
- $$$a_1 = x_{0\bmod 3}+a_0=x_0+0=1$$$,
- $$$a_2 = x_{1\bmod 3}+a_1=x_1+1=3$$$,
- $$$a_3 = x_{2\bmod 3}+a_2=x_2+3=6$$$,
- $$$a_4 = x_{3\bmod 3}+a_3=x_0+6=7$$$,
- $$$a_5 = x_{4\bmod 3}+a_4=x_1+7=9$$$.

So, if the $$$x = [1, 2, 3]$$$ and $$$n = 5$$$, then $$$a = [0, 1, 3, 6, 7, 9]$$$.

Now the boy hopes that he will be able to restore $$$x$$$ from $$$a$$$! Knowing that $$$1 \le k \le n$$$, help him and find all possible values of $$$k$$$ — possible lengths of the lost array.

## Input Format
The first line contains exactly one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the array $$$a$$$, excluding the element $$$a_0$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Note that $$$a_0$$$ is always $$$0$$$ and is not given in the input.

## Output Format
The first line of the output should contain one integer $$$l$$$ denoting the number of correct lengths of the lost array.

The second line of the output should contain $$$l$$$ integers — possible lengths of the lost array in increasing order.

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

## Note
In the first example, any $$$k$$$ is suitable, since $$$a$$$ is an arithmetic progression.

Possible arrays $$$x$$$:

- $$$[1]$$$
- $$$[1, 1]$$$
- $$$[1, 1, 1]$$$
- $$$[1, 1, 1, 1]$$$
- $$$[1, 1, 1, 1, 1]$$$

In the second example, Bajtek's array can have three or five elements.

Possible arrays $$$x$$$:

- $$$[1, 2, 2]$$$
- $$$[1, 2, 2, 1, 2]$$$

For example, $$$k = 4$$$ is bad, since it leads to $$$6 + x_0 = 8$$$ and $$$0 + x_0 = 1$$$, which is an obvious contradiction.

In the third example, only $$$k = n$$$ is good.

Array $$$[1, 4, -2]$$$ satisfies the requirements.

Note that $$$x_i$$$ may be negative.

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
IA has so many colorful magnets on her fridge! Exactly one letter is written on each magnet, 'a' or 'b'. She loves to play with them, placing all magnets in a row. However, the girl is quickly bored and usually thinks how to make her entertainment more interesting.

Today, when IA looked at the fridge, she noticed that the word formed by magnets is really messy. "It would look much better when I'll swap some of them!" — thought the girl — "but how to do it?". After a while, she got an idea. IA will look at all prefixes with lengths from $$$1$$$ to the length of the word and for each prefix she will either reverse this prefix or leave it as it is. She will consider the prefixes in the fixed order: from the shortest to the largest. She wants to get the lexicographically smallest possible word after she considers all prefixes. Can you help her, telling which prefixes should be chosen for reversing?

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first and the only line contains a string $$$s$$$ ($$$1 \le |s| \le 1000$$$), describing the initial string formed by magnets. The string $$$s$$$ consists only of characters 'a' and 'b'.

## Output Format
Output exactly $$$|s|$$$ integers. If IA should reverse the $$$i$$$-th prefix (that is, the substring from $$$1$$$ to $$$i$$$), the $$$i$$$-th integer should be equal to $$$1$$$, and it should be equal to $$$0$$$ otherwise.

If there are multiple possible sequences leading to the optimal answer, print any of them.

## Examples
```input
bbab
```
```output
0 1 1 0
```
-----
```input
aaaaa
```
```output
1 0 0 0 1
```

## Note
In the first example, IA can reverse the second and the third prefix and get a string "abbb". She cannot get better result, since it is also lexicographically smallest string obtainable by permuting characters of the initial string.

In the second example, she can reverse any subset of prefixes — all letters are 'a'.

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
Acingel is a small town. There was only one doctor here — Miss Ada. She was very friendly and nobody has ever said something bad about her, so who could've expected that Ada will be found dead in her house? Mr Gawry, world-famous detective, is appointed to find the criminal. He asked $$$m$$$ neighbours of Ada about clients who have visited her in that unlucky day. Let's number the clients from $$$1$$$ to $$$n$$$. Each neighbour's testimony is a permutation of these numbers, which describes the order in which clients have been seen by the asked neighbour.

However, some facts are very suspicious – how it is that, according to some of given permutations, some client has been seen in the morning, while in others he has been seen in the evening? "In the morning some of neighbours must have been sleeping!" — thinks Gawry — "and in the evening there's been too dark to see somebody's face...". Now he wants to delete some prefix and some suffix (both prefix and suffix can be empty) in each permutation, so that they'll be non-empty and equal to each other after that — some of the potential criminals may disappear, but the testimony won't stand in contradiction to each other.

In how many ways he can do it? Two ways are called different if the remaining common part is different.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10$$$) — the number of suspects and the number of asked neighbors.

Each of the next $$$m$$$ lines contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that these integers form a correct permutation (that is, each number from $$$1$$$ to $$$n$$$ appears exactly once).

## Output Format
Output a single integer denoting the number of ways to delete some prefix and some suffix of each permutation (possibly empty), such that the remaining parts will be equal and non-empty.

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

## Note
In the first example, all possible common parts are $$$[1]$$$, $$$[2]$$$, $$$[3]$$$ and $$$[2, 3]$$$.

In the second and third examples, you can only leave common parts of length $$$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: 256.0 MB

# Problem
Janusz is a businessman. He owns a company "Januszex", which produces games for teenagers. Last hit of Januszex was a cool one-person game "Make it one". The player is given a sequence of $$$n$$$ integers $$$a_i$$$.

It is allowed to select any subset of them, and the score is equal to the greatest common divisor of selected elements. The goal is to take as little elements as it is possible, getting the score $$$1$$$. Now Janusz wonders, for given sequence, how much elements should the player choose?

## Input Format
The first line contains an only integer $$$n$$$ ($$$1 \le n \le 300\,000$$$) — the number of integers in the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300\,000$$$).

## Output Format
If there is no subset of the given sequence with gcd equal to $$$1$$$, output -1.

Otherwise, output exactly one integer — the size of the smallest subset with gcd equal to $$$1$$$.

## Examples
```input
3
10 6 15
```
```output
3
```
-----
```input
3
2 4 6
```
```output
-1
```
-----
```input
7
30 60 21 42 70 15 30
```
```output
3
```

## Note
In the first example, selecting a subset of all numbers gives a gcd of $$$1$$$ and for all smaller subsets the gcd is greater than $$$1$$$.

In the second example, for all subsets of numbers the gcd is at least $$$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
Little C loves number «3» very much. He loves all things about it.

Now he has a positive integer $$$n$$$. He wants to split $$$n$$$ into $$$3$$$ positive integers $$$a,b,c$$$, such that $$$a+b+c=n$$$ and none of the $$$3$$$ integers is a multiple of $$$3$$$. Help him to find a solution.

## Input Format
A single line containing one integer $$$n$$$ ($$$3 \leq n \leq 10^9$$$) — the integer Little C has.

## Output Format
Print $$$3$$$ positive integers $$$a,b,c$$$ in a single line, such that $$$a+b+c=n$$$ and none of them is a multiple of $$$3$$$.

It can be proved that there is at least one solution. If there are multiple solutions, print any of them.

## Examples
```input
3
```
```output
1 1 1
```
-----
```input
233
```
```output
77 77 79
```

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$$$ points on the plane, $$$(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$$$.

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.

## Input Format
First line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i,y_i \leq 10^9$$$).

## Output Format
Print the minimum length of the shorter side of the triangle. It can be proved that it's always an integer.

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

## Note
Illustration for the first example:

Illustration for the second example:

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
There is a card game called "Durak", which means "Fool" in Russian. The game is quite popular in the countries that used to form USSR. The problem does not state all the game's rules explicitly — you can find them later yourselves if you want.

To play durak you need a pack of 36 cards. Each card has a suit ("S", "H", "D" and "C") and a rank (in the increasing order "6", "7", "8", "9", "T", "J", "Q", "K" and "A"). At the beginning of the game one suit is arbitrarily chosen as trump.

The players move like that: one player puts one or several of his cards on the table and the other one should beat each of them with his cards.

A card beats another one if both cards have similar suits and the first card has a higher rank then the second one. Besides, a trump card can beat any non-trump card whatever the cards’ ranks are. In all other cases you can not beat the second card with the first one.

You are given the trump suit and two different cards. Determine whether the first one beats the second one or not.

## Input Format
The first line contains the tramp suit. It is "S", "H", "D" or "C".

The second line contains the description of the two different cards. Each card is described by one word consisting of two symbols. The first symbol stands for the rank ("6", "7", "8", "9", "T", "J", "Q", "K" and "A"), and the second one stands for the suit ("S", "H", "D" and "C").

## Output Format
Print "YES" (without the quotes) if the first cards beats the second one. Otherwise, print "NO" (also without the quotes).

## Examples
```input
H
QH 9S
```
```output
YES
```
-----
```input
S
8D 6D
```
```output
YES
```
-----
```input
C
7H AS
```
```output
NO
```

Now solve the problem and return the code.