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
It's the year 5555. You have a graph, and you want to find a long cycle and a huge independent set, just because you can. But for now, let's just stick with finding either.

Given a connected graph with $$$n$$$ vertices, you can choose to either:

- find an independent set that has exactly $$$\lceil\sqrt{n}\rceil$$$ vertices.
- find a simple cycle of length at least $$$\lceil\sqrt{n}\rceil$$$.

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice. I have a proof you can always solve one of these problems, but it's too long to fit this margin.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$5 \le n \le 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph.

Each of the next $$$m$$$ lines contains two space-separated integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) that mean there's an edge between vertices $$$u$$$ and $$$v$$$. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.

## Output Format
If you choose to solve the first problem, then on the first line print "1", followed by a line containing $$$\lceil\sqrt{n}\rceil$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print "2", followed by a line containing one integer, $$$c$$$, representing the length of the found cycle, followed by a line containing $$$c$$$ distinct integers integers not exceeding $$$n$$$, the vertices in the desired cycle, in the order they appear in the cycle.

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

## Note
In the first sample:

Notice that you can solve either problem, so printing the cycle $$$2-4-3-1-5-6$$$ is also acceptable.

In the second sample:

Notice that if there are multiple answers you can print any, so printing the cycle $$$2-5-6$$$, for example, is acceptable.

In the third 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 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
Eugene likes working with arrays. And today he needs your help in solving one challenging task.

An array $$$c$$$ is a subarray of an array $$$b$$$ if $$$c$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Let's call a nonempty array good if for every nonempty subarray of this array, sum of the elements of this subarray is nonzero. For example, array $$$[-1, 2, -3]$$$ is good, as all arrays $$$[-1]$$$, $$$[-1, 2]$$$, $$$[-1, 2, -3]$$$, $$$[2]$$$, $$$[2, -3]$$$, $$$[-3]$$$ have nonzero sums of elements. However, array $$$[-1, 2, -1, -3]$$$ isn't good, as his subarray $$$[-1, 2, -1]$$$ has sum of elements equal to $$$0$$$.

Help Eugene to calculate the number of nonempty good subarrays of a given array $$$a$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$)  — the length of array $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)  — the elements of $$$a$$$.

## Output Format
Output a single integer  — the number of good subarrays of $$$a$$$.

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

## Note
In the first sample, the following subarrays are good: $$$[1]$$$, $$$[1, 2]$$$, $$$[2]$$$, $$$[2, -3]$$$, $$$[-3]$$$. However, the subarray $$$[1, 2, -3]$$$ isn't good, as its subarray $$$[1, 2, -3]$$$ has sum of elements equal to $$$0$$$.

In the second sample, three subarrays of size 1 are the only good subarrays. At the same time, the subarray $$$[41, -41, 41]$$$ isn't good, as its subarray $$$[41, -41]$$$ has sum of elements equal to $$$0$$$.

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
Kate has a set $$$S$$$ of $$$n$$$ integers $$$\{1, \dots, n\} $$$.

She thinks that imperfection of a subset $$$M \subseteq S$$$ is equal to the maximum of $$$gcd(a, b)$$$ over all pairs $$$(a, b)$$$ such that both $$$a$$$ and $$$b$$$ are in $$$M$$$ and $$$a \neq b$$$.

Kate is a very neat girl and for each $$$k \in \{2, \dots, n\}$$$ she wants to find a subset that has the smallest imperfection among all subsets in $$$S$$$ of size $$$k$$$. There can be more than one subset with the smallest imperfection and the same size, but you don't need to worry about it. Kate wants to find all the subsets herself, but she needs your help to find the smallest possible imperfection for each size $$$k$$$, will name it $$$I_k$$$.

Please, help Kate to find $$$I_2$$$, $$$I_3$$$, ..., $$$I_n$$$.

## Input Format
The first and only line in the input consists of only one integer $$$n$$$ ($$$2\le n \le 5 \cdot 10^5$$$)  — the size of the given set $$$S$$$.

## Output Format
Output contains only one line that includes $$$n - 1$$$ integers: $$$I_2$$$, $$$I_3$$$, ..., $$$I_n$$$.

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

## Note
First sample: answer is 1, because $$$gcd(1, 2) = 1$$$.

Second sample: there are subsets of $$$S$$$ with sizes $$$2, 3$$$ with imperfection equal to 1. For example, $$$\{2,3\}$$$ and $$$\{1, 2, 3\}$$$.

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: 256.0 MB

# Problem
Note that the only differences between easy and hard versions are the constraints on $$$n$$$ and the time limit. You can make hacks only if all versions are solved.

Slime is interested in sequences. He defined good positive integer sequences $$$p$$$ of length $$$n$$$ as follows:

- For each $$$k>1$$$ that presents in $$$p$$$, there should be at least one pair of indices $$$i,j$$$, such that $$$1 \leq i < j \leq n$$$, $$$p_i = k - 1$$$ and $$$p_j = k$$$.

For the given integer $$$n$$$, the set of all good sequences of length $$$n$$$ is $$$s_n$$$. For the fixed integer $$$k$$$ and the sequence $$$p$$$, let $$$f_p(k)$$$ be the number of times that $$$k$$$ appears in $$$p$$$. For each $$$k$$$ from $$$1$$$ to $$$n$$$, Slime wants to know the following value:

$$$$$$\left(\sum_{p\in s_n} f_p(k)\right)\ \textrm{mod}\ 998\,244\,353$$$$$$

## Input Format
The first line contains one integer $$$n\ (1\le n\le 100\,000)$$$.

## Output Format
Print $$$n$$$ integers, the $$$i$$$-th of them should be equal to $$$\left(\sum_{p\in s_n} f_p(i)\right)\ \textrm{mod}\ 998\,244\,353$$$.

## Examples
```input
2
```
```output
3 1
```
-----
```input
3
```
```output
10 7 1
```
-----
```input
1
```
```output
1
```

## Note
In the first example, $$$s=\{[1,1],[1,2]\}$$$.

In the second example, $$$s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}$$$.

In the third example, $$$s=\{[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: 256.0 MB

# Problem
Find the minimum area of a square land on which you can place two identical rectangular $$$a \times b$$$ houses. The sides of the houses should be parallel to the sides of the desired square land.

Formally,

- You are given two identical rectangles with side lengths $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 100$$$) — positive integers (you are given just the sizes, but not their positions).
- Find the square of the minimum area that contains both given rectangles. Rectangles can be rotated (both or just one), moved, but the sides of the rectangles should be parallel to the sides of the desired square.

Two rectangles can touch each other (side or corner), but cannot intersect. Rectangles can also touch the sides of the square but must be completely inside it. You can rotate the rectangles. Take a look at the examples for a better understanding.

The picture shows a square that contains red and green rectangles.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) —the number of test cases in the input. Then $$$t$$$ test cases follow.

Each test case is a line containing two integers $$$a$$$, $$$b$$$ ($$$1 \le a, b \le 100$$$) — side lengths of the rectangles.

## Output Format
Print $$$t$$$ answers to the test cases. Each answer must be a single integer — minimal area of square land, that contains two rectangles with dimensions $$$a \times b$$$.

## Examples
```input
8
3 2
4 2
1 1
3 1
4 7
1 3
7 4
100 100
```
```output
16
16
4
9
64
9
64
40000
```

## Note
Below are the answers for the first two test cases:

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
There are $$$n$$$ athletes in front of you. Athletes are numbered from $$$1$$$ to $$$n$$$ from left to right. You know the strength of each athlete — the athlete number $$$i$$$ has the strength $$$s_i$$$.

You want to split all athletes into two teams. Each team must have at least one athlete, and each athlete must be exactly in one team.

You want the strongest athlete from the first team to differ as little as possible from the weakest athlete from the second team. Formally, you want to split the athletes into two teams $$$A$$$ and $$$B$$$ so that the value $$$|\max(A) - \min(B)|$$$ is as small as possible, where $$$\max(A)$$$ is the maximum strength of an athlete from team $$$A$$$, and $$$\min(B)$$$ is the minimum strength of an athlete from team $$$B$$$.

For example, if $$$n=5$$$ and the strength of the athletes is $$$s=[3, 1, 2, 6, 4]$$$, then one of the possible split into teams is:

- first team: $$$A = [1, 2, 4]$$$,
- second team: $$$B = [3, 6]$$$.

In this case, the value $$$|\max(A) - \min(B)|$$$ will be equal to $$$|4-3|=1$$$. This example illustrates one of the ways of optimal split into two teams.

Print the minimum value $$$|\max(A) - \min(B)|$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each test case consists of two lines.

The first line contains positive integer $$$n$$$ ($$$2 \le n \le 50$$$) — number of athletes.

The second line contains $$$n$$$ positive integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 1000$$$), where $$$s_i$$$ — is the strength of the $$$i$$$-th athlete. Please note that $$$s$$$ values may not be distinct.

## Output Format
For each test case print one integer — the minimum value of $$$|\max(A) - \min(B)|$$$ with the optimal split of all athletes into two teams. Each of the athletes must be a member of exactly one of the two teams.

## Examples
```input
5
5
3 1 2 6 4
6
2 1 3 2 4 3
4
7 9 3 1
2
1 1000
3
100 150 200
```
```output
1
0
2
999
50
```

## Note
The first test case was explained in the statement. In the second test case, one of the optimal splits is $$$A=[2, 1]$$$, $$$B=[3, 2, 4, 3]$$$, so the answer is $$$|2-2|=0$$$.

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
We call two numbers $$$x$$$ and $$$y$$$ similar if they have the same parity (the same remainder when divided by $$$2$$$), or if $$$|x-y|=1$$$. For example, in each of the pairs $$$(2, 6)$$$, $$$(4, 3)$$$, $$$(11, 7)$$$, the numbers are similar to each other, and in the pairs $$$(1, 4)$$$, $$$(3, 12)$$$, they are not.

You are given an array $$$a$$$ of $$$n$$$ ($$$n$$$ is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other.

For example, for the array $$$a = [11, 14, 16, 12]$$$, there is a partition into pairs $$$(11, 12)$$$ and $$$(14, 16)$$$. The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of two lines.

The first line contains an even positive integer $$$n$$$ ($$$2 \le n \le 50$$$) — length of array $$$a$$$.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$).

## Output Format
For each test case print:

- YES if the such a partition exists,
- NO otherwise.

The letters in the words YES and NO can be displayed in any case.

## Examples
```input
7
4
11 14 16 12
2
1 8
4
1 1 1 1
4
1 2 5 6
2
12 13
6
1 6 3 10 5 8
6
1 12 3 10 5 8
```
```output
YES
NO
YES
YES
YES
YES
NO
```

## Note
The first test case was explained in the statement.

In the second test case, the two given numbers are not similar.

In the third test case, any partition is suitable.

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$$$ strings $$$a_1, a_2, \ldots, a_n$$$: all of them have the same length $$$m$$$. The strings consist of lowercase English letters.

Find any string $$$s$$$ of length $$$m$$$ such that each of the given $$$n$$$ strings differs from $$$s$$$ in at most one position. Formally, for each given string $$$a_i$$$, there is no more than one position $$$j$$$ such that $$$a_i[j] \ne s[j]$$$.

Note that the desired string $$$s$$$ may be equal to one of the given strings $$$a_i$$$, or it may differ from all the given strings.

For example, if you have the strings abac and zbab, then the answer to the problem might be the string abab, which differs from the first only by the last character, and from the second only by the first.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case starts with a line containing two positive integers $$$n$$$ ($$$1 \le n \le 10$$$) and $$$m$$$ ($$$1 \le m \le 10$$$) — the number of strings and their length.

Then follow $$$n$$$ strings $$$a_i$$$, one per line. Each of them has length $$$m$$$ and consists of lowercase English letters.

## Output Format
Print $$$t$$$ answers to the test cases. Each answer (if it exists) is a string of length $$$m$$$ consisting of lowercase English letters. If there are several answers, print any of them. If the answer does not exist, print "-1" ("minus one", without quotes).

## Examples
```input
5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c
```
```output
abab
-1
aaa
ab
z
```

## Note
The first test case was explained in the statement.

In the second test case, the answer does not exist.

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 four positive integers $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$ ($$$1 \le b \le n \le 50$$$; $$$1 \le a \le m \le 50$$$). Find any such rectangular matrix of size $$$n \times m$$$ that satisfies all of the following conditions:

- each row of the matrix contains exactly $$$a$$$ ones;
- each column of the matrix contains exactly $$$b$$$ ones;
- all other elements are zeros.

If the desired matrix does not exist, indicate this.

For example, for $$$n=3$$$, $$$m=6$$$, $$$a=2$$$, $$$b=1$$$, there exists a matrix satisfying the conditions above:

$$$$$$ \begin{vmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \end{vmatrix} $$$$$$

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case is described by four positive integers $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$ ($$$1 \le b \le n \le 50$$$; $$$1 \le a \le m \le 50$$$), where $$$n$$$ and $$$m$$$ are the sizes of the matrix, and $$$a$$$ and $$$b$$$ are the number of ones for rows and columns, respectively.

## Output Format
For each test case print:

- "YES" (without quotes) and the required matrix (if there are several answers, print any) if it exists, or
- "NO" (without quotes) if it does not exist.

To print the matrix $$$n \times m$$$, print $$$n$$$ rows, each of which consists of $$$m$$$ numbers $$$0$$$ or $$$1$$$ describing a row of the matrix. Numbers must be printed without spaces.

## Examples
```input
5
3 6 2 1
2 2 2 1
2 2 2 2
4 4 2 2
2 1 1 2
```
```output
YES
010001
100100
001010
NO
YES
11
11
YES
1100
1100
0011
0011
YES
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
"Hey, it's homework time" — thought Polycarpus and of course he started with his favourite subject, IT. Polycarpus managed to solve all tasks but for the last one in 20 minutes. However, as he failed to solve the last task after some considerable time, the boy asked you to help him.

The sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

You are given an arbitrary sequence a1, a2, ..., an containing n integers. Each integer is not less than 1 and not greater than 5000. Determine what minimum number of elements Polycarpus needs to change to get a permutation (he should not delete or add numbers). In a single change he can modify any single sequence element (i. e. replace it with another integer).

## Input Format
The first line of the input data contains an integer n (1 ≤ n ≤ 5000) which represents how many numbers are in the sequence. The second line contains a sequence of integers ai (1 ≤ ai ≤ 5000, 1 ≤ i ≤ n).

## Output Format
Print the only number — the minimum number of changes needed to get the permutation.

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

## Note
The first sample contains the permutation, which is why no replacements are required.

In the second sample it is enough to replace the first element with the number 1 and that will make the sequence the needed permutation.

In the third sample we can replace the second element with number 4 and the fourth element with number 2.

Now solve the problem and return the code.