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
This problem is a simplified version of D2, but it has significant differences, so read the whole statement.

Polycarp has an array of $$$n$$$ ($$$n$$$ is even) integers $$$a_1, a_2, \dots, a_n$$$. Polycarp conceived of a positive integer $$$k$$$. After that, Polycarp began performing the following operations on the array: take an index $$$i$$$ ($$$1 \le i \le n$$$) and reduce the number $$$a_i$$$ by $$$k$$$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that all numbers in the array became the same. Find the maximum $$$k$$$ at which such a situation is possible, or print $$$-1$$$ if such a number can be arbitrarily large.

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

Each test case consists of two lines. The first line contains an even integer $$$n$$$ ($$$4 \le n \le 40$$$) ($$$n$$$ is even). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

It is guaranteed that the sum of all $$$n$$$ specified in the given test cases does not exceed $$$100$$$.

## Output Format
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 1$$$) — the maximum possible number that Polycarp used in operations on the array, or $$$-1$$$, if such a number can be arbitrarily large.

## Examples
```input
3
6
1 5 3 1 1 5
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
```
```output
2
1
1100
```

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
This problem is a complicated version of D1, but it has significant differences, so read the whole statement.

Polycarp has an array of $$$n$$$ ($$$n$$$ is even) integers $$$a_1, a_2, \dots, a_n$$$. Polycarp conceived of a positive integer $$$k$$$. After that, Polycarp began performing the following operations on the array: take an index $$$i$$$ ($$$1 \le i \le n$$$) and reduce the number $$$a_i$$$ by $$$k$$$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that at least half of the numbers in the array became the same. Find the maximum $$$k$$$ at which such a situation is possible, or print $$$-1$$$ if such a number can be arbitrarily large.

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

Each test case consists of two lines. The first line contains an even integer $$$n$$$ ($$$4 \le n \le 40$$$) ($$$n$$$ is even). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

It is guaranteed that the sum of all $$$n$$$ specified in the given test cases does not exceed $$$100$$$.

## Output Format
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 1$$$) — the maximum possible number that Polycarp used in operations on the array, or $$$-1$$$, if such a number can be arbitrarily large.

## Examples
```input
4
6
48 13 22 -15 16 35
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
4
1 1 1 1
```
```output
13
2
-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: 64.0 MB

# Problem
According to a new ISO standard, a flag of every country should have a chequered field n × m, each square should be of one of 10 colours, and the flag should be «striped»: each horizontal row of the flag should contain squares of the same colour, and the colours of adjacent horizontal rows should be different. Berland's government asked you to find out whether their flag meets the new ISO standard.

## Input Format
The first line of the input contains numbers n and m (1 ≤ n, m ≤ 100), n — the amount of rows, m — the amount of columns on the flag of Berland. Then there follows the description of the flag: each of the following n lines contain m characters. Each character is a digit between 0 and 9, and stands for the colour of the corresponding square.

## Output Format
Output YES, if the flag meets the new ISO standard, and NO otherwise.

## Examples
```input
3 3
000
111
222
```
```output
YES
```
-----
```input
3 3
000
000
111
```
```output
NO
```
-----
```input
3 3
000
111
002
```
```output
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: 0.5 seconds
Memory limit: 64.0 MB

# Problem
A burglar got into a matches warehouse and wants to steal as many matches as possible. In the warehouse there are m containers, in the i-th container there are ai matchboxes, and each matchbox contains bi matches. All the matchboxes are of the same size. The burglar's rucksack can hold n matchboxes exactly. Your task is to find out the maximum amount of matches that a burglar can carry away. He has no time to rearrange matches in the matchboxes, that's why he just chooses not more than n matchboxes so that the total amount of matches in them is maximal.

## Input Format
The first line of the input contains integer n (1 ≤ n ≤ 2·108) and integer m (1 ≤ m ≤ 20). The i + 1-th line contains a pair of numbers ai and bi (1 ≤ ai ≤ 108, 1 ≤ bi ≤ 10). All the input numbers are integer.

## Output Format
Output the only number — answer to the problem.

## Examples
```input
7 3
5 10
2 5
3 6
```
```output
62
```
-----
```input
3 3
1 3
2 2
3 1
```
```output
7
```

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: 0.5 seconds
Memory limit: 64.0 MB

# Problem
Reca company makes monitors, the most popular of their models is AB999 with the screen size a × b centimeters. Because of some production peculiarities a screen parameters are integer numbers. Recently the screen sides ratio x: y became popular with users. That's why the company wants to reduce monitor AB999 size so that its screen sides ratio becomes x: y, at the same time they want its total area to be maximal of all possible variants. Your task is to find the screen parameters of the reduced size model, or find out that such a reduction can't be performed.

## Input Format
The first line of the input contains 4 integers — a, b, x and y (1 ≤ a, b, x, y ≤ 2·109).

## Output Format
If the answer exists, output 2 positive integers — screen parameters of the reduced size model. Output 0 0 otherwise.

## Examples
```input
800 600 4 3
```
```output
800 600
```
-----
```input
1920 1200 16 9
```
```output
1920 1080
```
-----
```input
1 1 1 2
```
```output
0 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: 64.0 MB

# Problem
The main server of Gomble company received a log of one top-secret process, the name of which can't be revealed. The log was written in the following format: «[date:time]: message», where for each «[date:time]» value existed not more than 10 lines. All the files were encoded in a very complicated manner, and only one programmer — Alex — managed to decode them. The code was so complicated that Alex needed four weeks to decode it. Right after the decoding process was finished, all the files were deleted. But after the files deletion, Alex noticed that he saved the recordings in format «[time]: message». So, information about the dates was lost. However, as the lines were added into the log in chronological order, it's not difficult to say if the recordings could appear during one day or not. It is possible also to find the minimum amount of days during which the log was written.

So, to make up for his mistake Alex has to find the minimum amount of days covered by the log. Note that Alex doesn't have to find the minimum amount of days between the beginning and the end of the logging, he has to find the minimum amount of dates in which records could be done. (See Sample test 2 for further clarifications).

We should remind you that the process made not more than 10 recordings in a minute. Consider that a midnight belongs to coming day.

## Input Format
The first input line contains number n (1 ≤ n ≤ 100). The following n lines contain recordings in format «[time]: message», where time is given in format «hh:mm x.m.». For hh two-digit numbers from 01 to 12 are used, for mm two-digit numbers from 00 to 59 are used, and x is either character «a» or character «p». A message is a non-empty sequence of Latin letters and/or spaces, it doesn't start or end with a space. The length of each message doesn't exceed 20.

## Output Format
Output one number — the minimum amount of days covered by the log.

## Examples
```input
5
[05:00 a.m.]: Server is started
[05:00 a.m.]: Rescan initialized
[01:13 p.m.]: Request processed
[01:10 p.m.]: Request processed
[11:40 p.m.]: Rescan completed
```
```output
2
```
-----
```input
3
[09:00 a.m.]: User logged in
[08:00 a.m.]: User logged in
[07:00 a.m.]: User logged in
```
```output
3
```

## Note
Formally the 12-hour time format is described at:

- http://en.wikipedia.org/wiki/12-hour_clock.

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 pair of integers $$$(a, b)$$$ and an integer $$$x$$$.

You can change the pair in two different ways:

- set (assign) $$$a := |a - b|$$$;
- set (assign) $$$b := |a - b|$$$,

The pair $$$(a, b)$$$ is called $$$x$$$-magic if $$$x$$$ is obtainable either as $$$a$$$ or as $$$b$$$ using only the given operations (i.e. the pair $$$(a, b)$$$ is $$$x$$$-magic if $$$a = x$$$ or $$$b = x$$$ after some number of operations applied). You can apply the operations any number of times (even zero).

Your task is to find out if the pair $$$(a, b)$$$ is $$$x$$$-magic or not.

You have to answer $$$t$$$ independent test cases.

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

The only line of the test case contains three integers $$$a$$$, $$$b$$$ and $$$x$$$ ($$$1 \le a, b, x \le 10^{18}$$$).

## Output Format
For the $$$i$$$-th test case, print YES if the corresponding pair $$$(a, b)$$$ is $$$x$$$-magic and NO otherwise.

## Examples
```input
8
6 9 3
15 38 7
18 8 8
30 30 30
40 50 90
24 28 20
365 216 52
537037812705867558 338887693834423551 3199921013340
```
```output
YES
YES
YES
YES
NO
YES
YES
YES
```

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 $$$c = [c_1, c_2, \dots, c_m]$$$. An array $$$a = [a_1, a_2, \dots, a_n]$$$ is constructed in such a way that it consists of integers $$$1, 2, \dots, m$$$, and for each $$$i \in [1,m]$$$, there are exactly $$$c_i$$$ occurrences of integer $$$i$$$ in $$$a$$$. So, the number of elements in $$$a$$$ is exactly $$$\sum\limits_{i=1}^{m} c_i$$$.

Let's define for such array $$$a$$$ the value $$$f(a)$$$ as $$$$$$f(a) = \sum_{\substack{1 \le i < j \le n\\ a_i = a_j}}{j - i}.$$$$$$

In other words, $$$f(a)$$$ is the total sum of distances between all pairs of equal elements.

Your task is to calculate the maximum possible value of $$$f(a)$$$ and the number of arrays yielding the maximum possible value of $$$f(a)$$$. Two arrays are considered different, if elements at some position differ.

## Input Format
The first line contains a single integer $$$m$$$ ($$$1 \le m \le 5 \cdot 10^5$$$) — the size of the array $$$c$$$.

The second line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le 10^6$$$) — the array $$$c$$$.

## Output Format
Print two integers — the maximum possible value of $$$f(a)$$$ and the number of arrays $$$a$$$ with such value. Since both answers may be too large, print them modulo $$$10^9 + 7$$$.

## Examples
```input
6
1 1 1 1 1 1
```
```output
0 720
```
-----
```input
1
1000000
```
```output
499833345 1
```
-----
```input
7
123 451 234 512 345 123 451
```
```output
339854850 882811119
```

## Note
In the first example, all possible arrays $$$a$$$ are permutations of $$$[1, 2, 3, 4, 5, 6]$$$. Since each array $$$a$$$ will have $$$f(a) = 0$$$, so maximum value is $$$f(a) = 0$$$ and there are $$$6! = 720$$$ such arrays.

In the second example, the only possible array consists of $$$10^6$$$ ones and its $$$f(a) = \sum\limits_{1 \le i < j \le 10^6}{j - i} = 166\,666\,666\,666\,500\,000$$$ and $$$166\,666\,666\,666\,500\,000 \bmod{10^9 + 7} = 499\,833\,345$$$.

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 strings $$$S$$$ and $$$T$$$, consisting of lowercase English letters. It is guaranteed that $$$T$$$ is a permutation of the string abc.

Find string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.

String $$$a$$$ is a permutation of string $$$b$$$ if the number of occurrences of each distinct character is the same in both strings.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

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
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a string $$$S$$$ ($$$1 \le |S| \le 100$$$), consisting of lowercase English letters.

The second line of each test case contains a string $$$T$$$ that is a permutation of the string abc. (Hence, $$$|T| = 3$$$).

Note that there is no limit on the sum of $$$|S|$$$ across all test cases.

## Output Format
For each test case, output a single string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.

## Examples
```input
7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc
```
```output
aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac
```

## Note
In the first test case, both aaaabbc and aaaabcb are lexicographically smaller than aaaacbb, but they contain abc as a subsequence.

In the second test case, abccc is the smallest permutation of cccba and does not contain acb as a subsequence.

In the third test case, bcdis is the smallest permutation of dbsic and does not contain bac as a subsequence.

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 three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ such that $$$a + b + c = n$$$ and $$$\operatorname{gcd}(a, b) = c$$$, where $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

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

The first and only line of each test case contains a single integer $$$n$$$ ($$$10 \le n \le 10^9$$$).

## Output Format
For each test case, output three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ satisfying the requirements. If there are multiple solutions, you can print any. We can show that an answer always exists.

## Examples
```input
6
18
63
73
91
438
122690412
```
```output
6 9 3
21 39 3
29 43 1
49 35 7
146 219 73
28622 122661788 2
```

## Note
In the first test case, $$$6 + 9 + 3 = 18$$$ and $$$\operatorname{gcd}(6, 9) = 3$$$.

In the second test case, $$$21 + 39 + 3 = 63$$$ and $$$\operatorname{gcd}(21, 39) = 3$$$.

In the third test case, $$$29 + 43 + 1 = 73$$$ and $$$\operatorname{gcd}(29, 43) = 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
Paprika loves permutations. She has an array $$$a_1, a_2, \dots, a_n$$$. She wants to make the array a permutation of integers $$$1$$$ to $$$n$$$.

In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers $$$i$$$ ($$$1 \le i \le n$$$) and $$$x$$$ ($$$x > 0$$$), then perform $$$a_i := a_i \bmod x$$$ (that is, replace $$$a_i$$$ by the remainder of $$$a_i$$$ divided by $$$x$$$). In different operations, the chosen $$$i$$$ and $$$x$$$ can be different.

Determine the minimum number of operations needed to make the array a permutation of integers $$$1$$$ to $$$n$$$. If it is impossible, output $$$-1$$$.

A permutation 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 a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
For each test case, output the minimum number of operations needed to make the array a permutation of integers $$$1$$$ to $$$n$$$, or $$$-1$$$ if it is impossible.

## Examples
```input
4
2
1 7
3
1 5 4
4
12345678 87654321 20211218 23571113
9
1 2 3 4 18 19 5 6 7
```
```output
1
-1
4
2
```

## Note
For the first test, the only possible sequence of operations which minimizes the number of operations is:

- Choose $$$i=2$$$, $$$x=5$$$. Perform $$$a_2 := a_2 \bmod 5 = 2$$$.

For the second test, it is impossible to obtain a permutation of integers from $$$1$$$ to $$$n$$$.

Now solve the problem and return the code.