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

# Problem
A little boy Gerald entered a clothes shop and found out something very unpleasant: not all clothes turns out to match. For example, Gerald noticed that he looks rather ridiculous in a smoking suit and a baseball cap.

Overall the shop sells n clothing items, and exactly m pairs of clothing items match. Each item has its price, represented by an integer number of rubles. Gerald wants to buy three clothing items so that they matched each other. Besides, he wants to spend as little money as possible. Find the least possible sum he can spend.

## Input Format
The first input file line contains integers n and m — the total number of clothing items in the shop and the total number of matching pairs of clothing items ($$3 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2}$$).

Next line contains n integers ai (1 ≤ ai ≤ 106) — the prices of the clothing items in rubles.

Next m lines each contain a pair of space-separated integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi). Each such pair of numbers means that the ui-th and the vi-th clothing items match each other. It is guaranteed that in each pair ui and vi are distinct and all the unordered pairs (ui, vi) are different.

## Output Format
Print the only number — the least possible sum in rubles that Gerald will have to pay in the shop. If the shop has no three clothing items that would match each other, print "-1" (without the quotes).

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

## Note
In the first test there only are three pieces of clothing and they all match each other. Thus, there is only one way — to buy the 3 pieces of clothing; in this case he spends 6 roubles.

The second test only has three pieces of clothing as well, yet Gerald can't buy them because the first piece of clothing does not match the third one. Thus, there are no three matching pieces of clothing. The answer is -1.

In the third example there are 4 pieces of clothing, but Gerald can't buy any 3 of them simultaneously. The answer is -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: 2.0 seconds
Memory limit: 265.0 MB

# Problem
Having watched the last Harry Potter film, little Gerald also decided to practice magic. He found in his father's magical book a spell that turns any number in the sum of its digits. At the moment Gerald learned that, he came across a number n. How many times can Gerald put a spell on it until the number becomes one-digit?

## Input Format
The first line contains the only integer n (0 ≤ n ≤ 10100000). It is guaranteed that n doesn't contain any leading zeroes.

## Output Format
Print the number of times a number can be replaced by the sum of its digits until it only contains one digit.

## Examples
```input
0
```
```output
0
```
-----
```input
10
```
```output
1
```
-----
```input
991
```
```output
3
```

## Note
In the first sample the number already is one-digit — Herald can't cast a spell.

The second test contains number 10. After one casting of a spell it becomes 1, and here the process is completed. Thus, Gerald can only cast the spell once.

The third test contains number 991. As one casts a spell the following transformations take place: 991 → 19 → 10 → 1. After three transformations the number becomes one-digit.

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

# Problem
During the research on properties of the greatest common divisor (GCD) of a set of numbers, Ildar, a famous mathematician, introduced a brand new concept of the weakened common divisor (WCD) of a list of pairs of integers.

For a given list of pairs of integers $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, ..., $$$(a_n, b_n)$$$ their WCD is arbitrary integer greater than $$$1$$$, such that it divides at least one element in each pair. WCD may not exist for some lists.

For example, if the list looks like $$$[(12, 15), (25, 18), (10, 24)]$$$, then their WCD can be equal to $$$2$$$, $$$3$$$, $$$5$$$ or $$$6$$$ (each of these numbers is strictly greater than $$$1$$$ and divides at least one number in each pair).

You're currently pursuing your PhD degree under Ildar's mentorship, and that's why this problem was delegated to you. Your task is to calculate WCD efficiently.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 150\,000$$$) — the number of pairs.

Each of the next $$$n$$$ lines contains two integer values $$$a_i$$$, $$$b_i$$$ ($$$2 \le a_i, b_i \le 2 \cdot 10^9$$$).

## Output Format
Print a single integer — the WCD of the set of pairs.

If there are multiple possible answers, output any; if there is no answer, print $$$-1$$$.

## Examples
```input
3
17 18
15 24
12 15
```
```output
6
```
-----
```input
2
10 16
7 17
```
```output
-1
```
-----
```input
5
90 108
45 105
75 40
165 175
33 30
```
```output
5
```

## Note
In the first example the answer is $$$6$$$ since it divides $$$18$$$ from the first pair, $$$24$$$ from the second and $$$12$$$ from the third ones. Note that other valid answers will also be accepted.

In the second example there are no integers greater than $$$1$$$ satisfying the conditions.

In the third example one of the possible answers is $$$5$$$. Note that, for example, $$$15$$$ is also allowed, but it's not necessary to maximize the output.

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
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 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: 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 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
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 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
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 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
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 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
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.