apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Lindsey Buckingham told Stevie Nicks "Go your own way". Nicks is now sad and wants to go away as quickly as possible, but she lives in a 2D hexagonal world.

Consider a hexagonal tiling of the plane as on the picture below.

Nicks wishes to go from the cell marked $$$(0, 0)$$$ to a certain cell given by the coordinates. She may go from a hexagon to any of its six neighbors you want, but there is a cost associated with each of them. The costs depend only on the direction in which you travel. Going from $$$(0, 0)$$$ to $$$(1, 1)$$$ will take the exact same cost as going from $$$(-2, -1)$$$ to $$$(-1, 0)$$$. The costs are given in the input in the order $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ as in the picture below.

Print the smallest cost of a path from the origin which has coordinates $$$(0, 0)$$$ to the given cell.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$-10^{9} \le x, y \le 10^{9}$$$) representing the coordinates of the target hexagon.

The second line of each test case contains six integers $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ ($$$1 \le c_1, c_2, c_3, c_4, c_5, c_6 \le 10^{9}$$$) representing the six costs of the making one step in a particular direction (refer to the picture above to see which edge is for each value).

## Output Format
For each testcase output the smallest cost of a path from the origin to the given cell.

## Examples
```input
2
-3 1
1 3 5 7 9 11
1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
```
```output
18
1000000000000000000
```

## Note
The picture below shows the solution for the first sample. The cost $$$18$$$ is reached by taking $$$c_3$$$ 3 times and $$$c_2$$$ once, amounting to $$$5+5+5+3=18$$$.

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
While playing yet another strategy game, Mans has recruited $$$n$$$ Swedish heroes, whose powers which can be represented as an array $$$a$$$.

Unfortunately, not all of those mighty heroes were created as capable as he wanted, so that he decided to do something about it. In order to accomplish his goal, he can pick two consecutive heroes, with powers $$$a_i$$$ and $$$a_{i+1}$$$, remove them and insert a hero with power $$$-(a_i+a_{i+1})$$$ back in the same position.

For example if the array contains the elements $$$[5, 6, 7, 8]$$$, he can pick $$$6$$$ and $$$7$$$ and get $$$[5, -(6+7), 8] = [5, -13, 8]$$$.

After he will perform this operation $$$n-1$$$ times, Mans will end up having only one hero. He wants his power to be as big as possible. What's the largest possible power he can achieve?

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 200000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — powers of the heroes.

## Output Format
Print the largest possible power he can achieve after $$$n-1$$$ operations.

## Examples
```input
4
5 6 7 8
```
```output
26
```
-----
```input
5
4 -5 9 -2 1
```
```output
15
```

## Note
Suitable list of operations for the first sample:

$$$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$$$

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
A Ministry for Defense sent a general to inspect the Super Secret Military Squad under the command of the Colonel SuperDuper. Having learned the news, the colonel ordered to all n squad soldiers to line up on the parade ground.

By the military charter the soldiers should stand in the order of non-increasing of their height. But as there's virtually no time to do that, the soldiers lined up in the arbitrary order. However, the general is rather short-sighted and he thinks that the soldiers lined up correctly if the first soldier in the line has the maximum height and the last soldier has the minimum height. Please note that the way other solders are positioned does not matter, including the case when there are several soldiers whose height is maximum or minimum. Only the heights of the first and the last soldier are important.

For example, the general considers the sequence of heights (4, 3, 4, 2, 1, 1) correct and the sequence (4, 3, 1, 2, 2) wrong.

Within one second the colonel can swap any two neighboring soldiers. Help him count the minimum time needed to form a line-up which the general will consider correct.

## Input Format
The first input line contains the only integer n (2 ≤ n ≤ 100) which represents the number of soldiers in the line. The second line contains integers a1, a2, ..., an (1 ≤ ai ≤ 100) the values of the soldiers' heights in the order of soldiers' heights' increasing in the order from the beginning of the line to its end. The numbers are space-separated. Numbers a1, a2, ..., an are not necessarily different.

## Output Format
Print the only integer — the minimum number of seconds the colonel will need to form a line-up the general will like.

## Examples
```input
4
33 44 11 22
```
```output
2
```
-----
```input
7
10 10 58 31 63 40 76
```
```output
10
```

## Note
In the first sample the colonel will need to swap the first and second soldier and then the third and fourth soldier. That will take 2 seconds. The resulting position of the soldiers is (44, 33, 22, 11).

In the second sample the colonel may swap the soldiers in the following sequence:

1. (10, 10, 58, 31, 63, 40, 76)
2. (10, 58, 10, 31, 63, 40, 76)
3. (10, 58, 10, 31, 63, 76, 40)
4. (10, 58, 10, 31, 76, 63, 40)
5. (10, 58, 31, 10, 76, 63, 40)
6. (10, 58, 31, 76, 10, 63, 40)
7. (10, 58, 31, 76, 63, 10, 40)
8. (10, 58, 76, 31, 63, 10, 40)
9. (10, 76, 58, 31, 63, 10, 40)
10. (76, 10, 58, 31, 63, 10, 40)
11. (76, 10, 58, 31, 63, 40, 10)

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
A string t is called an anagram of the string s, if it is possible to rearrange letters in t so that it is identical to the string s. For example, the string "aab" is an anagram of the string "aba" and the string "aaa" is not.

The string t is called a substring of the string s if it can be read starting from some position in the string s. For example, the string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba".

You are given a string s, consisting of lowercase Latin letters and characters "?". You are also given a string p, consisting of lowercase Latin letters only. Let's assume that a string is good if you can obtain an anagram of the string p from it, replacing the "?" characters by Latin letters. Each "?" can be replaced by exactly one character of the Latin alphabet. For example, if the string p = «aba», then the string "a??" is good, and the string «?bc» is not.

Your task is to find the number of good substrings of the string s (identical substrings must be counted in the answer several times).

## Input Format
The first line is non-empty string s, consisting of no more than 105 lowercase Latin letters and characters "?". The second line is non-empty string p, consisting of no more than 105 lowercase Latin letters. Please note that the length of the string p can exceed the length of the string s.

## Output Format
Print the single number representing the number of good substrings of string s.

Two substrings are considered different in their positions of occurrence are different. Thus, if some string occurs several times, then it should be counted the same number of times.

## Examples
```input
bb??x???
aab
```
```output
2
```
-----
```input
ab?c
acb
```
```output
2
```

## Note
Consider the first sample test. Here the string s has two good substrings: "b??" (after we replace the question marks we get "baa"), "???" (after we replace the question marks we get "baa").

Let's consider the second sample test. Here the string s has two good substrings: "ab?" ("?" can be replaced by "c"), "b?c" ("?" can be replaced by "a").

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A country called Berland consists of n cities, numbered with integer numbers from 1 to n. Some of them are connected by bidirectional roads. Each road has some length. There is a path from each city to any other one by these roads. According to some Super Duper Documents, Berland is protected by the Super Duper Missiles. The exact position of the Super Duper Secret Missile Silos is kept secret but Bob managed to get hold of the information. That information says that all silos are located exactly at a distance l from the capital. The capital is located in the city with number s.

The documents give the formal definition: the Super Duper Secret Missile Silo is located at some place (which is either city or a point on a road) if and only if the shortest distance from this place to the capital along the roads of the country equals exactly l.

Bob wants to know how many missile silos are located in Berland to sell the information then to enemy spies. Help Bob.

## Input Format
The first line contains three integers n, m and s (2 ≤ n ≤ 105, $$n-1 \leq m \leq \min(10^5, \frac{n(n-1)}{2})$$, 1 ≤ s ≤ n) — the number of cities, the number of roads in the country and the number of the capital, correspondingly. Capital is the city no. s.

Then m lines contain the descriptions of roads. Each of them is described by three integers vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 1 ≤ wi ≤ 1000), where vi, ui are numbers of the cities connected by this road and wi is its length. The last input line contains integer l (0 ≤ l ≤ 109) — the distance from the capital to the missile silos. It is guaranteed that:

- between any two cities no more than one road exists;
- each road connects two different cities;
- from each city there is at least one way to any other city by the roads.

## Output Format
Print the single number — the number of Super Duper Secret Missile Silos that are located in Berland.

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

## Note
In the first sample the silos are located in cities 3 and 4 and on road (1, 3) at a distance 2 from city 1 (correspondingly, at a distance 1 from city 3).

In the second sample one missile silo is located right in the middle of the road (1, 2). Two more silos are on the road (4, 5) at a distance 3 from city 4 in the direction to city 5 and at a distance 3 from city 5 to city 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Bertown is a city with $$$n$$$ buildings in a straight line.

The city's security service discovered that some buildings were mined. A map was compiled, which is a string of length $$$n$$$, where the $$$i$$$-th character is "1" if there is a mine under the building number $$$i$$$ and "0" otherwise.

Bertown's best sapper knows how to activate mines so that the buildings above them are not damaged. When a mine under the building numbered $$$x$$$ is activated, it explodes and activates two adjacent mines under the buildings numbered $$$x-1$$$ and $$$x+1$$$ (if there were no mines under the building, then nothing happens). Thus, it is enough to activate any one mine on a continuous segment of mines to activate all the mines of this segment. For manual activation of one mine, the sapper takes $$$a$$$ coins. He can repeat this operation as many times as you want.

Also, a sapper can place a mine under a building if it wasn't there. For such an operation, he takes $$$b$$$ coins. He can also repeat this operation as many times as you want.

The sapper can carry out operations in any order.

You want to blow up all the mines in the city to make it safe. Find the minimum number of coins that the sapper will have to pay so that after his actions there are no mines left in the city.

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

Each test case begins with a line containing two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 1000$$$) — the cost of activating and placing one mine, respectively.

The next line contains a map of mines in the city — a string consisting of zeros and ones.

The sum of the string lengths for all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output one integer — the minimum number of coins that the sapper will have to pay.

## Examples
```input
2
1 1
01000010
5 1
01101110
```
```output
2
6
```

## Note
In the second test case, if we place a mine under the fourth building and then activate it, then all mines on the field are activated. The cost of such operations is six, $$$b=1$$$ coin for placing a mine and $$$a=5$$$ coins for activating.

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 a rectangular grid with $$$n$$$ rows and $$$m$$$ columns. The cell located on the $$$i$$$-th row from the top and the $$$j$$$-th column from the left has a value $$$a_{ij}$$$ written in it.

You can perform the following operation any number of times (possibly zero):

- Choose any two adjacent cells and multiply the values in them by $$$-1$$$. Two cells are called adjacent if they share a side.

Note that you can use a cell more than once in different operations.

You are interested in $$$X$$$, the sum of all the numbers in the grid.

What is the maximum $$$X$$$ you can achieve with these operations?

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

The first line of each test case contains two integers $$$n$$$,$$$m$$$ ($$$2 \le n$$$, $$$m \le 10$$$).

The following $$$n$$$ lines contain $$$m$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line is $$$a_{ij}$$$ ($$$-100\leq a_{ij}\le 100$$$).

## Output Format
For each testcase, print one integer $$$X$$$, the maximum possible sum of all the values in the grid after applying the operation as many times as you want.

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

## Note
In the first test case, there will always be at least one $$$-1$$$, so the answer is $$$2$$$.

In the second test case, we can use the operation six times to elements adjacent horizontally and get all numbers to be non-negative. So the answer is: $$$2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$$$.

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 two integers $$$n$$$ and $$$k$$$.

You should create an array of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ such that the sum $$$(a_1 + a_2 + \dots + a_n)$$$ is divisible by $$$k$$$ and maximum element in $$$a$$$ is minimum possible.

What is the minimum possible maximum element in $$$a$$$?

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le k \le 10^9$$$).

## Output Format
For each test case, print one integer — the minimum possible maximum element in array $$$a$$$ such that the sum $$$(a_1 + \dots + a_n)$$$ is divisible by $$$k$$$.

## Examples
```input
4
1 5
4 3
8 8
8 17
```
```output
5
2
1
3
```

## Note
In the first test case $$$n = 1$$$, so the array consists of one element $$$a_1$$$ and if we make $$$a_1 = 5$$$ it will be divisible by $$$k = 5$$$ and the minimum possible.

In the second test case, we can create array $$$a = [1, 2, 1, 2]$$$. The sum is divisible by $$$k = 3$$$ and the maximum is equal to $$$2$$$.

In the third test case, we can create array $$$a = [1, 1, 1, 1, 1, 1, 1, 1]$$$. The sum is divisible by $$$k = 8$$$ and the maximum is equal to $$$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 have a statistic of price changes for one product represented as an array of $$$n$$$ positive integers $$$p_0, p_1, \dots, p_{n - 1}$$$, where $$$p_0$$$ is the initial price of the product and $$$p_i$$$ is how the price was increased during the $$$i$$$-th month.

Using these price changes you are asked to calculate the inflation coefficients for each month as the ratio of current price increase $$$p_i$$$ to the price at the start of this month $$$(p_0 + p_1 + \dots + p_{i - 1})$$$.

Your boss said you clearly that the inflation coefficients must not exceed $$$k$$$ %, so you decided to increase some values $$$p_i$$$ in such a way, that all $$$p_i$$$ remain integers and the inflation coefficients for each month don't exceed $$$k$$$ %.

You know, that the bigger changes — the more obvious cheating. That's why you need to minimize the total sum of changes.

What's the minimum total sum of changes you need to make all inflation coefficients not more than $$$k$$$ %?

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$; $$$1 \le k \le 100$$$) — the length of array $$$p$$$ and coefficient $$$k$$$.

The second line of each test case contains $$$n$$$ integers $$$p_0, p_1, \dots, p_{n - 1}$$$ ($$$1 \le p_i \le 10^9$$$) — the array $$$p$$$.

## Output Format
For each test case, print the minimum total sum of changes you need to make all inflation coefficients not more than $$$k$$$ %.

## Examples
```input
2
4 1
20100 1 202 202
3 100
1 1 1
```
```output
99
0
```

## Note
In the first test case, you can, for example, increase $$$p_0$$$ by $$$50$$$ and $$$p_1$$$ by $$$49$$$ and get array $$$[20150, 50, 202, 202]$$$. Then you get the next inflation coefficients:

1. $$$\frac{50}{20150} \le \frac{1}{100}$$$;
2. $$$\frac{202}{20150 + 50} \le \frac{1}{100}$$$;
3. $$$\frac{202}{20200 + 202} \le \frac{1}{100}$$$;

In the second test case, you don't need to modify array $$$p$$$, since the inflation coefficients are already good:

1. $$$\frac{1}{1} \le \frac{100}{100}$$$;
2. $$$\frac{1}{1 + 1} \le \frac{100}{100}$$$;

Now solve the problem and return the code.