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

# Problem
Sasha found an array $$$a$$$ consisting of $$$n$$$ integers and asked you to paint elements.

You have to paint each element of the array. You can use as many colors as you want, but each element should be painted into exactly one color, and for each color, there should be at least one element of that color.

The cost of one color is the value of $$$\max(S) - \min(S)$$$, where $$$S$$$ is the sequence of elements of that color. The cost of the whole coloring is the sum of costs over all colors.

For example, suppose you have an array $$$a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$, and you painted its elements into two colors as follows: elements on positions $$$1$$$, $$$2$$$ and $$$5$$$ have color $$$1$$$; elements on positions $$$3$$$ and $$$4$$$ have color $$$2$$$. Then:

- the cost of the color $$$1$$$ is $$$\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$$$;
- the cost of the color $$$2$$$ is $$$\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$$$;
- the total cost of the coloring is $$$7$$$.

For the given array $$$a$$$, you have to calculate the maximum possible cost of the coloring.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$) — length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — array $$$a$$$.

## Output Format
For each test case output the maximum possible cost of the coloring.

## Examples
```input
6
5
1 5 6 3 4
1
5
4
1 6 3 9
6
1 13 9 3 7 2
4
2 2 2 2
5
4 5 2 2 3
```
```output
7
0
11
23
0
5
```

## Note
In the first example one of the optimal coloring is $$$[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$. The answer is $$$(5 - 1) + (6 - 3) = 7$$$.

In the second example, the only possible coloring is $$$[\color{blue}{5}]$$$, for which the answer is $$$5 - 5 = 0$$$.

In the third example, the optimal coloring is $$$[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$$$, the answer is $$$(9 - 1) + (6 - 3) = 11$$$.

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
Today Alex was brought array $$$a_1, a_2, \dots, a_n$$$ of length $$$n$$$. He can apply as many operations as he wants (including zero operations) to change the array elements.

In $$$1$$$ operation Alex can choose any $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$, and multiply all elements of the array from $$$l$$$ to $$$r$$$ inclusive by $$$-1$$$. In other words, Alex can replace the subarray $$$[a_l, a_{l + 1}, \dots, a_r]$$$ by $$$[-a_l, -a_{l + 1}, \dots, -a_r]$$$ in $$$1$$$ operation.

For example, let $$$n = 5$$$, the array is $$$[1, -2, 0, 3, -1]$$$, $$$l = 2$$$ and $$$r = 4$$$, then after the operation the array will be $$$[1, 2, 0, -3, -1]$$$.

Alex is late for school, so you should help him find the maximum possible sum of numbers in the array, which can be obtained by making any number of operations, as well as the minimum number of operations that must be done for this.

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

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

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

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

## Output Format
For each test case output two space-separated numbers: the maximum possible sum of numbers in the array and the minimum number of operations to get this sum.

Pay attention that an answer may not fit in a standard integer type, so do not forget to use 64-bit integer type.

## Examples
```input
5
6
-1 7 -4 -2 5 -8
8
-1 0 0 -2 1 0 -3 0
5
2 -1 0 -3 -7
5
0 -17 0 1 0
4
-1 0 -2 -1
```
```output
27 3
7 2
13 1
18 1
4 1
```

## Note
Below, for each test case, only one of the possible shortest sequences of operations is provided among many. There are others that have the same length and lead to the maximum sum of elements.

In the first test case, Alex can make operations: $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(6, 6)$$$.

In the second test case, to get the largest sum you need to make operations: $$$(1, 8)$$$, $$$(5, 6)$$$.

In the fourth test case, it is necessary to make only one operation: $$$(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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ zeros. You are also given a set of $$$m$$$ not necessarily different segments. Each segment is defined by two numbers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) and represents a subarray $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$ of the array $$$a$$$.

Let's call the segment $$$l_i, r_i$$$ beautiful if the number of ones on this segment is strictly greater than the number of zeros. For example, if $$$a = [1, 0, 1, 0, 1]$$$, then the segment $$$[1, 5]$$$ is beautiful (the number of ones is $$$3$$$, the number of zeros is $$$2$$$), but the segment $$$[3, 4]$$$ is not is beautiful (the number of ones is $$$1$$$, the number of zeros is $$$1$$$).

You also have $$$q$$$ changes. For each change you are given the number $$$1 \le x \le n$$$, which means that you must assign an element $$$a_x$$$ the value $$$1$$$.

You have to find the first change after which at least one of $$$m$$$ given segments becomes beautiful, or report that none of them is beautiful after processing all $$$q$$$ changes.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 10^5$$$) — the size of the array $$$a$$$ and the number of segments, respectively.

Then there are $$$m$$$ lines consisting of two numbers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) —the boundaries of the segments.

The next line contains an integer $$$q$$$ ($$$1 \le q \le n$$$) — the number of changes.

The following $$$q$$$ lines each contain a single integer $$$x$$$ ($$$1 \le x \le n$$$) — the index of the array element that needs to be set to $$$1$$$. It is guaranteed that indexes in queries are distinct.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output one integer  — the minimum change number after which at least one of the segments will be beautiful, or $$$-1$$$ if none of the segments will be beautiful.

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

## Note
In the first case, after first 2 changes we won't have any beautiful segments, but after the third one on a segment $$$[1; 5]$$$ there will be 3 ones and only 2 zeros, so the answer is 3.

In the second case, there won't be any beautiful segments.

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
Dalton is the teacher of a class with $$$n$$$ students, numbered from $$$1$$$ to $$$n$$$. The classroom contains $$$n$$$ chairs, also numbered from $$$1$$$ to $$$n$$$. Initially student $$$i$$$ is seated on chair $$$p_i$$$. It is guaranteed that $$$p_1,p_2,\dots, p_n$$$ is a permutation of length $$$n$$$.

A student is happy if his/her number is different from the number of his/her chair. In order to make all of his students happy, Dalton can repeatedly perform the following operation: choose two distinct students and swap their chairs. What is the minimum number of moves required to make all the students happy? One can show that, under the constraints of this problem, it is possible to make all the students happy with a finite number of moves.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of students.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — $$$p_i$$$ denotes the initial chair of student $$$i$$$. It is guaranteed that $$$p$$$ is a permutation.

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

## Output Format
For each test case, output the minimum number of moves required.

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

## Note
In the first test case, both students are already happy, so Dalton can perform $$$0$$$ moves.

In the second test case, Dalton can swap the chairs of students $$$1$$$ and $$$2$$$ to get the array $$$[2, 1, 3]$$$. Then he can swap chairs of students $$$2$$$ and $$$3$$$ to get the array $$$[2, 3, 1]$$$. At this point all the students are happy, and he performed $$$2$$$ moves. It is impossible to perform the task with fewer moves.

In the third test case, by swapping the chairs of students $$$1$$$ and $$$2$$$ and then swapping the chairs of students $$$4$$$ and $$$5$$$, Dalton gets the array $$$[2, 1, 5, 3, 4]$$$ in $$$2$$$ moves.

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
Given a positive integer $$$n$$$, find the maximum size of an interval $$$[l, r]$$$ of positive integers such that, for every $$$i$$$ in the interval (i.e., $$$l \leq i \leq r$$$), $$$n$$$ is a multiple of $$$i$$$.

Given two integers $$$l\le r$$$, the size of the interval $$$[l, r]$$$ is $$$r-l+1$$$ (i.e., it coincides with the number of integers belonging to the interval).

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

The only line of the description of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

## Output Format
For each test case, print a single integer: the maximum size of a valid interval.

## Examples
```input
10
1
40
990990
4204474560
169958913706572972
365988220345828080
387701719537826430
620196883578129853
864802341280805662
1000000000000000000
```
```output
1
2
3
6
4
22
3
1
2
2
```

## Note
In the first test case, a valid interval with maximum size is $$$[1, 1]$$$ (it's valid because $$$n = 1$$$ is a multiple of $$$1$$$) and its size is $$$1$$$.

In the second test case, a valid interval with maximum size is $$$[4, 5]$$$ (it's valid because $$$n = 40$$$ is a multiple of $$$4$$$ and $$$5$$$) and its size is $$$2$$$.

In the third test case, a valid interval with maximum size is $$$[9, 11]$$$.

In the fourth test case, a valid interval with maximum size is $$$[8, 13]$$$.

In the seventh test case, a valid interval with maximum size is $$$[327869, 327871]$$$.

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
Some dwarves that are finishing the StUDY (State University for Dwarven Youngsters) Bachelor courses, have been told "no genome, no degree". That means that all dwarves should write a thesis on genome. Dwarven genome is far from simple. It is represented by a string that consists of lowercase Latin letters.

Dwarf Misha has already chosen the subject for his thesis: determining by two dwarven genomes, whether they belong to the same race. Two dwarves belong to the same race if we can swap two characters in the first dwarf's genome and get the second dwarf's genome as a result. Help Dwarf Misha and find out whether two gnomes belong to the same race or not.

## Input Format
The first line contains the first dwarf's genome: a non-empty string, consisting of lowercase Latin letters.

The second line contains the second dwarf's genome: a non-empty string, consisting of lowercase Latin letters.

The number of letters in each genome doesn't exceed 105. It is guaranteed that the strings that correspond to the genomes are different. The given genomes may have different length.

## Output Format
Print "YES", if the dwarves belong to the same race. Otherwise, print "NO".

## Examples
```input
ab
ba
```
```output
YES
```
-----
```input
aa
ab
```
```output
NO
```

## Note
- First example: you can simply swap two letters in string "ab". So we get "ba".
- Second example: we can't change string "aa" into string "ab", because "aa" does not contain letter "b".

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
You are given three integers $$$x$$$, $$$y$$$, and $$$n$$$.

Your task is to construct an array $$$a$$$ consisting of $$$n$$$ integers which satisfies the following conditions:

1. $$$a_1=x$$$, $$$a_n=y$$$;
2. $$$a$$$ is strictly increasing (i.e. $$$a_1 < a_2 < \ldots < a_n$$$);
3. if we denote $$$b_i=a_{i+1}-a_{i}$$$ for $$$1 \leq i \leq n-1$$$, then $$$b$$$ is strictly decreasing (i.e. $$$b_1 > b_2 > \ldots > b_{n-1}$$$).

If there is no such array $$$a$$$, print a single integer $$$-1$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The only line of each test case contains three integers $$$x$$$, $$$y$$$, $$$n$$$ ($$$1 \le x < y \le 1000,3 \le n \le 1000$$$).

## Output Format
For each test case, output $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$. If there are multiple solutions, print any of them.

If there is no solution, print a single integer $$$-1$$$.

## Examples
```input
3
1 4 3
1 3 3
100 200 4
```
```output
1 3 4
-1
100 150 180 200
```

## Note
In the first test case, $$$a=[1,3,4]$$$, which is strictly increasing. Next, $$$b_1=a_2-a_1=3-1=2$$$, $$$b_2=a_3-a_2=4-3=1$$$, thus $$$b=[2,1]$$$, which is strictly decreasing.

In the second test case, there is no array $$$a$$$ that satisfies all the conditions above.

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
You are given an integer $$$x$$$. Your task is to reduce $$$x$$$ to $$$1$$$.

To do that, you can do the following operation:

- select a divisor $$$d$$$ of $$$x$$$, then change $$$x$$$ to $$$x-d$$$, i.e. reduce $$$x$$$ by $$$d$$$. (We say that $$$d$$$ is a divisor of $$$x$$$ if $$$d$$$ is an positive integer and there exists an integer $$$q$$$ such that $$$x = d \cdot q$$$.)

There is an additional constraint: you cannot select the same value of $$$d$$$ more than twice.

For example, for $$$x=5$$$, the following scheme is invalid because $$$1$$$ is selected more than twice: $$$5\xrightarrow{-1}4\xrightarrow{-1}3\xrightarrow{-1}2\xrightarrow{-1}1$$$. The following scheme is however a valid one: $$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$.

Output any scheme which reduces $$$x$$$ to $$$1$$$ with at most $$$1000$$$ operations. It can be proved that such a scheme always exists.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$x$$$ ($$$2\le x \le 10^{9}$$$).

## Output Format
For each test case, output two lines.

The first line should contain an integer $$$k$$$ ($$$1 \le k \le 1001$$$).

The next line should contain $$$k$$$ integers $$$a_1,a_2,\ldots,a_k$$$, which satisfy the following:

- $$$a_1=x$$$;
- $$$a_k=1$$$;
- for each $$$2 \le i \le k$$$, the value $$$(a_{i-1}-a_i)$$$ is a divisor of $$$a_{i-1}$$$. Each number may occur as a divisor at most twice.

## Examples
```input
3
3
5
14
```
```output
3
3 2 1
4
5 4 2 1
6
14 12 6 3 2 1
```

## Note
In the first test case, we use the following scheme: $$$3\xrightarrow{-1}2\xrightarrow{-1}1$$$.

In the second test case, we use the following scheme: $$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$.

In the third test case, we use the following scheme: $$$14\xrightarrow{-2}12\xrightarrow{-6}6\xrightarrow{-3}3\xrightarrow{-1}2\xrightarrow{-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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have two vessels with water. The first vessel contains $$$a$$$ grams of water, and the second vessel contains $$$b$$$ grams of water. Both vessels are very large and can hold any amount of water.

You also have an empty cup that can hold up to $$$c$$$ grams of water.

In one move, you can scoop up to $$$c$$$ grams of water from any vessel and pour it into the other vessel. Note that the mass of water poured in one move does not have to be an integer.

What is the minimum number of moves required to make the masses of water in the vessels equal? Note that you cannot perform any actions other than the described moves.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

Each test case consists of a single line containing three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a, b, c \le 100$$$) — the mass of water in the vessels and the capacity of the cup, respectively.

## Output Format
For each test case, output a single number — the minimum number of moves required to make the masses of water in the vessels equal. It can be shown, that it is always possible.

## Examples
```input
6
3 7 2
17 4 3
17 17 1
17 21 100
1 100 1
97 4 3
```
```output
1
3
0
1
50
16
```

## Note
In the first test case, only one move is enough: if we pour $$$2$$$ grams of water from the second vessel into the first one, both vessels will contain $$$5$$$ grams of water.

In the second example test case, three moves are enough:

- Pour $$$3$$$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $$$17 - 3 = 14$$$ grams of water, and the second vessel will contain $$$4 + 3 = 7$$$ grams.
- Pour $$$2$$$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $$$14 - 2 = 12$$$ grams of water, and the second vessel will contain $$$7 + 2 = 9$$$ grams.
- Finally, pour $$$1.5$$$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $$$12 - 1.5 = 10.5$$$ grams of water, and the second vessel will contain $$$9 + 1.5 = 10.5$$$ grams.

Note that this is not the only way to equalize the vessels in $$$3$$$ moves, but there is no way to do it in $$$2$$$ moves.

In the third example test case, the vessels initially contain the same amount of water, so no moves are needed. The answer is $$$0$$$.

Now solve the problem and return the code.