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: 3.0 seconds
Memory limit: 1024.0 MB

# Problem
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$m$$$. You can make hacks only if both versions of the problem are solved.

You are given an array $$$a$$$ of length $$$n$$$ and two integers $$$m$$$ and $$$k$$$. Each element in $$$a$$$ satisfies $$$1\le a_i \le m$$$.

In one operation, you choose two indices $$$i$$$ and $$$j$$$ such that $$$1 \le i < j \le |a|$$$, then append $$$\gcd(a_i,a_j)$$$ to the back of the array and delete $$$a_i$$$ and $$$a_j$$$ from the array. Note that the length of the array decreases by one after this operation.

Find the maximum possible sum of the array after performing exactly $$$k$$$ operations.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$1\le m \le 10^6$$$; $$$1 \le k \le n-1$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le m$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output the maximum possible sum of the array after performing $$$k$$$ operations optimally.

## Examples
```input
3
3 8 1
4 7 8
5 114 2
7 2 4 1 6
3 514 2
2 3 3
```
```output
11
14
1
```

## Note
In the first test case, the best way is to choose $$$i=1$$$, $$$j=3$$$ in the first operation. The final sequence is $$$[7,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 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
Vlad decided to compose a melody on his guitar. Let's represent the melody as a sequence of notes corresponding to the characters 'a', 'b', 'c', 'd', 'e', 'f', and 'g'.

However, Vlad is not very experienced in playing the guitar and can only record exactly two notes at a time. Vlad wants to obtain the melody $$$s$$$, and to do this, he can merge the recorded melodies together. In this case, the last sound of the first melody must match the first sound of the second melody.

For example, if Vlad recorded the melodies "ab" and "ba", he can merge them together and obtain the melody "aba", and then merge the result with "ab" to get "abab".

Help Vlad determine the minimum number of melodies consisting of two notes that he needs to record in order to obtain the melody $$$s$$$.

## Input Format
The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Following that are the descriptions of the test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the melody $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of characters 'a', 'b', 'c', 'd', 'e', 'f', 'g'.

## Output Format
Output $$$t$$$ integers, each representing the answer for the corresponding test case. As the answer output minimum number of melodies consisting of two notes that Vlad needs to record.

## Examples
```input
5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd
```
```output
2
4
1
6
4
```

## Note
In the first sample, you need to record the melodies "ab" and "ba", as described in the problem statement.

In the second sample, you need to record the melodies "ab", "ba", "ac", and "ca".

In the third sample, the only necessary melody is "aa".

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
Vlad was given an array $$$a$$$ of $$$n$$$ positive integers. Now he wants to build a beautiful array $$$b$$$ of length $$$n$$$ from it.

Vlad considers an array beautiful if all the numbers in it are positive and have the same parity. That is, all numbers in the beautiful array are greater than zero and are either all even or all odd.

To build the array $$$b$$$, Vlad can assign each $$$b_i$$$ either the value $$$a_i$$$ or $$$a_i - a_j$$$, where any $$$j$$$ from $$$1$$$ to $$$n$$$ can be chosen.

To avoid trying to do the impossible, Vlad asks you to determine whether it is possible to build a beautiful array $$$b$$$ of length $$$n$$$ using his array $$$a$$$.

## Input Format
The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each case contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Output $$$t$$$ strings, each of which is the answer to the corresponding test case. As the answer, output "YES" if Vlad can build a beautiful array $$$b$$$, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
7
5
2 6 8 4 3
5
1 4 7 6 9
4
2 6 4 10
7
5 29 13 9 10000001 11 3
5
2 1 2 4 2
5
2 4 5 4 3
4
2 5 5 4
```
```output
NO
YES
YES
YES
YES
NO
NO
```

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
Ksyusha has a pet chinchilla, a tree on $$$n$$$ vertices and huge scissors. A tree is a connected graph without cycles. During a boring physics lesson Ksyusha thought about how to entertain her pet.

Chinchillas like to play with branches. A branch is a tree of $$$3$$$ vertices.

The branch looks like this.

A cut is the removal of some (not yet cut) edge in the tree. Ksyusha has plenty of free time, so she can afford to make enough cuts so that the tree splits into branches. In other words, after several (possibly zero) cuts, each vertex must belong to exactly one branch.

Help Ksyusha choose the edges to be cut or tell that it is impossible.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The next $$$n - 1$$$ rows of each testcase contain integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — the numbers of vertices that the $$$i$$$-th edge connects.

It is guaranteed that this set of edges forms a tree. It is also guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Print the answer for each testcase.

If the desired way to cut the tree does not exist, print $$$-1$$$.

Otherwise, print an integer $$$k$$$ — the number of edges to be cut. In the next line, print $$$k$$$ different integers $$$e_i$$$ ($$$1 \le e_i < n$$$) — numbers of the edges to be cut. If $$$k = 0$$$, print an empty string instead.

If there are several solutions, you can print any.

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

1
2 
2
4 3
```

## Note
The first testcase in first test.

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 two integers $$$x$$$ and $$$k$$$. Grasshopper starts in a point $$$0$$$ on an OX axis. In one move, it can jump some integer distance, that is not divisible by $$$k$$$, to the left or to the right.

What's the smallest number of moves it takes the grasshopper to reach point $$$x$$$? What are these moves? If there are multiple answers, print any of them.

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

The only line of each testcase contains two integers $$$x$$$ and $$$k$$$ ($$$1 \le x \le 100$$$; $$$2 \le k \le 100$$$) — the endpoint and the constraint on the jumps, respectively.

## Output Format
For each testcase, in the first line, print a single integer $$$n$$$ — the smallest number of moves it takes the grasshopper to reach point $$$x$$$.

In the second line, print $$$n$$$ integers, each of them not divisible by $$$k$$$. A positive integer would mean jumping to the right, a negative integer would mean jumping to the left. The endpoint after the jumps should be exactly $$$x$$$.

Each jump distance should be from $$$-10^9$$$ to $$$10^9$$$. In can be shown that, for any solution with the smallest number of jumps, there exists a solution with the same number of jumps such that each jump is from $$$-10^9$$$ to $$$10^9$$$.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.

## Examples
```input
3
10 2
10 3
3 4
```
```output
2
7 3
1
10
1
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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a string $$$s$$$ of length $$$n$$$, where each character is either < or >.

An array $$$a$$$ consisting of $$$n+1$$$ elements is compatible with the string $$$s$$$ if, for every $$$i$$$ from $$$1$$$ to $$$n$$$, the character $$$s_i$$$ represents the result of comparing $$$a_i$$$ and $$$a_{i+1}$$$, i. e.:

- $$$s_i$$$ is < if and only if $$$a_i < a_{i+1}$$$;
- $$$s_i$$$ is > if and only if $$$a_i > a_{i+1}$$$.

For example, the array $$$[1, 2, 5, 4, 2]$$$ is compatible with the string <<>>. There are other arrays with are compatible with that string, for example, $$$[13, 37, 42, 37, 13]$$$.

The cost of the array is the number of different elements in it. For example, the cost of $$$[1, 2, 5, 4, 2]$$$ is $$$4$$$; the cost of $$$[13, 37, 42, 37, 13]$$$ is $$$3$$$.

You have to calculate the minimum cost among all arrays which are compatible with the given string $$$s$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$1 \le n \le 100$$$);
- the second line contains the string $$$s$$$, consisting of $$$n$$$ characters. Each character of $$$s$$$ is either < or >.

## Output Format
For each test case, print one integer — the minimum cost among all arrays which are compatible with the given string $$$s$$$.

## Examples
```input
4
4
<<>>
4
>><<
5
>>>>>
7
<><><><
```
```output
3
3
6
2
```

## Note
In the first test case of the example, the array can be $$$[13, 37, 42, 37, 13]$$$.

In the second test case of the example, the array can be $$$[42, 37, 13, 37, 42]$$$.

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

# Problem
Berland Intercollegiate Contest has just finished. Monocarp and Polycarp, as the jury, are going to conduct an editorial. Unfortunately, the time is limited, since they have to finish before the closing ceremony.

There were $$$n$$$ problems in the contest. The problems are numbered from $$$1$$$ to $$$n$$$. The editorial for the $$$i$$$-th problem takes $$$a_i$$$ minutes. Monocarp and Polycarp are going to conduct an editorial for exactly $$$k$$$ of the problems.

The editorial goes as follows. They have a full problemset of $$$n$$$ problems before them, in order. They remove $$$n - k$$$ problems without changing the order of the remaining $$$k$$$ problems. Then, Monocarp takes some prefix of these $$$k$$$ problems (possibly, an empty one or all problems). Polycarp takes the remaining suffix of them. After that, they go to different rooms and conduct editorials for their problems in parallel. So, the editorial takes as much time as the longer of these two does.

Please, help Monocarp and Polycarp to choose the problems and the split in such a way that the editorial finishes as early as possible. Print the duration of the editorial.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — the number of problems in the full problemset and the number of problems Monocarp and Polycarp are going to conduct an editorial for.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the time each editorial takes.

The sum of $$$n$$$ over all testcases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the smallest amount of time the editorial takes, if Monocarp and Polycarp can choose which $$$k$$$ of $$$n$$$ problems to conduct an editorial for and how to split them among themselves.

## Examples
```input
6
5 4
1 10 1 1 1
5 3
1 20 5 15 3
5 3
1 20 3 15 5
10 6
10 8 20 14 3 8 6 4 16 11
10 5
9 9 2 13 15 19 4 9 13 12
1 1
1
```
```output
2
6
5
21
18
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
You are given an integer $$$n$$$, which you want to obtain. You have an unlimited supply of every integer from $$$1$$$ to $$$k$$$, except integer $$$x$$$ (there are no integer $$$x$$$ at all).

You are allowed to take an arbitrary amount of each of these integers (possibly, zero). Can you make the sum of taken integers equal to $$$n$$$?

If there are multiple answers, print any of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases.

The only line of each testcase contains three integers $$$n, k$$$ and $$$x$$$ ($$$1 \le x \le k \le n \le 100$$$).

## Output Format
For each test case, in the first line, print "YES" or "NO" — whether you can take an arbitrary amount of each integer from $$$1$$$ to $$$k$$$, except integer $$$x$$$, so that their sum is equal to $$$n$$$.

If you can, the second line should contain a single integer $$$m$$$ — the total amount of taken integers. The third line should contain $$$m$$$ integers — each of them from $$$1$$$ to $$$k$$$, not equal to $$$x$$$, and their sum is $$$n$$$.

If there are multiple answers, print any of them.

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

## Note
Another possible answer for the first testcase is $$$[3, 3, 3, 1]$$$. Note that you don't have to minimize the amount of taken integers. There also exist other answers.

In the second testcase, you only have an unlimited supply of integer $$$2$$$. There is no way to get sum $$$5$$$ using only them.

In the fifth testcase, there are no integers available at all, so you can't get any positive sum.

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
Bob and Carol hanged out with Alice the whole day, but now it's time to go home. Alice, Bob and Carol live on an infinite 2D grid in cells $$$A$$$, $$$B$$$, and $$$C$$$ respectively. Right now, all of them are in cell $$$A$$$.

If Bob (or Carol) is in some cell, he (she) can move to one of the neighboring cells. Two cells are called neighboring if they share a side. For example, the cell $$$(3, 5)$$$ has four neighboring cells: $$$(2, 5)$$$, $$$(4, 5)$$$, $$$(3, 6)$$$ and $$$(3, 4)$$$.

Bob wants to return to the cell $$$B$$$, Carol — to the cell $$$C$$$. Both of them want to go along the shortest path, i. e. along the path that consists of the minimum possible number of cells. But they would like to walk together as well.

What is the maximum possible number of cells that Bob and Carol can walk together if each of them walks home using one of the shortest paths?

## Input Format
The first line contains the single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$x_A$$$ and $$$y_A$$$ ($$$1 \le x_A, y_A \le 10^8$$$) — the position of cell $$$A$$$, where both Bob and Carol are right now.

The second line contains two integers $$$x_B$$$ and $$$y_B$$$ ($$$1 \le x_B, y_B \le 10^8$$$) — the position of cell $$$B$$$ (Bob's house).

The third line contains two integers $$$x_C$$$ and $$$y_C$$$ ($$$1 \le x_C, y_C \le 10^8$$$) — the position of cell $$$C$$$ (Carol's house).

Additional constraint on the input: the cells $$$A$$$, $$$B$$$, and $$$C$$$ are pairwise distinct in each test case.

## Output Format
For each test case, print the single integer — the maximum number of cells Bob and Carol can walk together if each of them goes home along one of the shortest paths.

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

## Note
In all pictures, red color denotes cells belonging only to Bob's path, light blue color — cells belonging only to Carol's path, and dark blue color — cells belonging to both paths.

One of the optimal routes for the first test case is shown below:

The optimal answer for the second test case is shown below:

One of the optimal answers for the third test case is shown below:

Now solve the problem and return the code.