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
You are given three points with integer coordinates $$$x_1$$$, $$$x_2$$$, and $$$x_3$$$ on the $$$X$$$ axis ($$$1 \leq x_i \leq 10$$$). You can choose any point with an integer coordinate $$$a$$$ on the $$$X$$$ axis. Note that the point $$$a$$$ may coincide with $$$x_1$$$, $$$x_2$$$, or $$$x_3$$$. Let $$$f(a)$$$ be the total distance from the given points to the point $$$a$$$. Find the smallest value of $$$f(a)$$$.

The distance between points $$$a$$$ and $$$b$$$ is equal to $$$|a - b|$$$. For example, the distance between points $$$a = 5$$$ and $$$b = 2$$$ is $$$3$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. Then follows their descriptions.

The single line of each test case contains three integers $$$x_1$$$, $$$x_2$$$, and $$$x_3$$$ ($$$1 \leq x_i \leq 10$$$) — the coordinates of the points.

## Output Format
For each test case, output the smallest value of $$$f(a)$$$.

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

## Note
In the first test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 1$$$: $$$f(1) = |1 - 1| + |1 - 1| + |1 - 1| = 0$$$.

In the second test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 5$$$: $$$f(5) = |1 - 5| + |5 - 5| + |9 - 5| = 8$$$.

In the third test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 8$$$: $$$f(8) = |8 - 8| + |2 - 8| + |8 - 8| = 6$$$.

In the fourth test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 9$$$: $$$f(10) = |10 - 9| + |9 - 9| + |3 - 9| = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$. You need to make it beautiful with the least amount of operations.

Before applying operations, you can shuffle the array elements as you like. For one operation, you can do the following:

- Choose an index $$$1 \leq i \leq n$$$,
- Make $$$a_i = a_i + k$$$.

The array $$$b_1, b_2, \ldots, b_n$$$ is beautiful if $$$b_i = b_{n - i + 1}$$$ for all $$$1 \leq i \leq n$$$.

Find the minimum number of operations needed to make the array beautiful, or report that it is impossible.

## Input Format
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the size of the array $$$a$$$ and the number $$$k$$$ from the problem statement.

The second line of each set of input data contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array $$$a$$$.

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

## Output Format
For each set of input data, output the minimum number of operations needed to make the array beautiful, or $$$-1$$$ if it is impossible.

## Examples
```input
11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5
```
```output
0
83966524
1
4
6
1
48
-1
0
14
0
```

## Note
In the first set of input data, the array is already beautiful.

In the second set of input data, you can shuffle the array before the operations and perform the operation with index $$$i = 1$$$ for $$$83966524$$$ times.

In the third set of input data, you can shuffle the array $$$a$$$ and make it equal to $$$[2, 3, 1]$$$. Then apply the operation with index $$$i = 3$$$ to get the array $$$[2, 3, 2]$$$, which is beautiful.

In the eighth set of input data, there is no set of operations and no way to shuffle the elements to make the array beautiful.

In the ninth set of input data, the array is already beautiful.

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

# Problem
This is the hard version of the problem. The only difference is that in this version $$$n \leq 5 \cdot 10^5$$$ and the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

You are given a permutation $$$p$$$ of length $$$n$$$. Calculate the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

A permutation is a sequence of $$$n$$$ integers, in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once. For example, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ are permutations, while $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ are not.

## Input Format
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each set of input data contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

## Output Format
For each set of input data, output the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

## Examples
```input
6
1
1
2
1 2
3
2 3 1
5
2 4 1 3 5
12
8 9 7 12 1 10 6 3 2 4 11 5
15
1 2 4 6 8 10 12 14 3 9 15 5 7 11 13
```
```output
0
1
1
3
9
3
```

## Note
In the first set of input data, there are no index pairs, as the size of the permutation is $$$1$$$.

In the second set of input data, there is one index pair $$$(1, 2)$$$ and it is valid.

In the third set of input data, the index pair $$$(1, 2)$$$ is valid.

In the fourth set of input data, the index pairs $$$(1, 2)$$$, $$$(1, 5)$$$, and $$$(2, 5)$$$ are valid.

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 renowned abstract artist Sasha, drawing inspiration from nowhere, decided to paint a picture entitled "Special Olympics". He justly thought that, if the regular Olympic games have five rings, then the Special ones will do with exactly two rings just fine.

Let us remind you that a ring is a region located between two concentric circles with radii r and R (r < R). These radii are called internal and external, respectively. Concentric circles are circles with centers located at the same point.

Soon a white canvas, which can be considered as an infinite Cartesian plane, had two perfect rings, painted with solid black paint. As Sasha is very impulsive, the rings could have different radii and sizes, they intersect and overlap with each other in any way. We know only one thing for sure: the centers of the pair of rings are not the same.

When Sasha got tired and fell into a deep sleep, a girl called Ilona came into the room and wanted to cut a circle for the sake of good memories. To make the circle beautiful, she decided to cut along the contour.

We'll consider a contour to be a continuous closed line through which there is transition from one color to another (see notes for clarification). If the contour takes the form of a circle, then the result will be cutting out a circle, which Iona wants.

But the girl's inquisitive mathematical mind does not rest: how many ways are there to cut a circle out of the canvas?

## Input Format
The input contains two lines.

Each line has four space-separated integers xi, yi, ri, Ri, that describe the i-th ring; xi and yi are coordinates of the ring's center, ri and Ri are the internal and external radii of the ring correspondingly ( - 100 ≤ xi, yi ≤ 100; 1 ≤ ri < Ri ≤ 100).

It is guaranteed that the centers of the rings do not coinside.

## Output Format
A single integer — the number of ways to cut out a circle from the canvas.

## Examples
```input
60 60 45 55
80 80 8 32
```
```output
1
```
-----
```input
60 60 45 55
80 60 15 25
```
```output
4
```
-----
```input
50 50 35 45
90 50 35 45
```
```output
0
```

## Note
Figures for test samples are given below. The possible cuts are marked with red dotted line.

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
Little Vasya loves orange juice very much. That's why any food and drink in his kitchen necessarily contains orange juice. There are n drinks in his fridge, the volume fraction of orange juice in the i-th drink equals pi percent.

One day Vasya decided to make himself an orange cocktail. He took equal proportions of each of the n drinks and mixed them. Then he wondered, how much orange juice the cocktail has.

Find the volume fraction of orange juice in the final drink.

## Input Format
The first input line contains a single integer n (1 ≤ n ≤ 100) — the number of orange-containing drinks in Vasya's fridge. The second line contains n integers pi (0 ≤ pi ≤ 100) — the volume fraction of orange juice in the i-th drink, in percent. The numbers are separated by a space.

## Output Format
Print the volume fraction in percent of orange juice in Vasya's cocktail. The answer will be considered correct if the absolute or relative error does not exceed 10  - 4.

## Examples
```input
3
50 50 100
```
```output
66.666666666667
```
-----
```input
4
0 25 50 75
```
```output
37.500000000000
```

## Note
Note to the first sample: let's assume that Vasya takes x milliliters of each drink from the fridge. Then the volume of pure juice in the cocktail will equal $$\frac{x}{2} + \frac{x}{2} + x = 2 \cdot x$$ milliliters. The total cocktail's volume equals 3·x milliliters, so the volume fraction of the juice in the cocktail equals $$\frac { 2 \cdot x } { 3 \cdot x } = \frac { 2 } { 3 }$$, that is, 66.(6) percent.

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
While most students still sit their exams, the tractor college has completed the summer exam session. In fact, students study only one subject at this college — the Art of Operating a Tractor. Therefore, at the end of a term a student gets only one mark, a three (satisfactory), a four (good) or a five (excellent). Those who score lower marks are unfortunately expelled.

The college has n students, and oddly enough, each of them can be on scholarship. The size of the scholarships varies each term. Since the end-of-the-term exam has just ended, it's time to determine the size of the scholarship to the end of next term.

The monthly budget for the scholarships of the Tractor college is s rubles. To distribute the budget optimally, you must follow these rules:

- The students who received the same mark for the exam, should receive the same scholarship;
- Let us denote the size of the scholarship (in roubles) for students who have received marks 3, 4 and 5 for the exam, as k3, k4 and k5, respectively. The values k3, k4 and k5 must be integers and satisfy the inequalities 0 ≤ k3 ≤ k4 ≤ k5;
- Let's assume that c3, c4, c5 show how many students received marks 3, 4 and 5 for the exam, respectively. The budget of the scholarship should be fully spent on them, that is, c3·k3 + c4·k4 + c5·k5 = s;
- Let's introduce function $$f(k_{3},k_{4},k_{5})=|c_{3}\cdot k_{3}-c_{4}\cdot k_{4}|+|c_{4}\cdot k_{4}-c_{5}\cdot k_{5}|$$ — the value that shows how well the scholarships are distributed between students. In the optimal distribution function f(k3, k4, k5) takes the minimum possible value.

Given the results of the exam, and the budget size s, you have to find the optimal distribution of the scholarship.

## Input Format
The first line has two integers n, s (3 ≤ n ≤ 300, 1 ≤ s ≤ 3·105) — the number of students and the budget size for the scholarship, respectively. The second line contains n integers, where the i-th number represents the mark that the i-th student got for the exam. It is guaranteed that at each mark was given to at least one student.

## Output Format
On a single line print three integers k3, k4 and k5 — the sought values that represent the optimal distribution of the scholarships. If there are multiple optimal answers, print any of them. If there is no answer, print -1.

## Examples
```input
5 11
3 4 3 5 5
```
```output
1 3 3
```
-----
```input
6 15
5 3 3 4 4 5
```
```output
-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
The Little Elephant has found a ragged old black-and-white string s on the attic.

The characters of string s are numbered from the left to the right from 1 to |s|, where |s| is the length of the string. Let's denote the i-th character of string s as si. As the string is black-and-white, each character of the string is either letter "B", or letter "W". Unfortunately, the string is very old and some characters are damaged. The damaged positions are denoted as "X".

The Little Elephant in determined to restore the string and hang it on the wall. For that he needs to replace each character "X" by a "B" or a "W". The string must look good on the wall, so it must be beautiful. The Little Elephant considers a string beautiful if it has two non-intersecting substrings of a given length k, such that the left one fully consists of characters "B", and the right one fully consists of characters "W". More formally, there are four integers a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ |s|; b - a + 1 = d - c + 1 = k) such that si = "B" (a ≤ i ≤ b) and sj = "W" (c ≤ j ≤ d).

Help the Little Elephant find the number of different beautiful strings he can obtain from string s. Two strings are considered different if there is such position, where the character in the first string differs from the corresponding character in the second string. If this string doesn't contain characters «X» and it is already beautiful — the answer is 1.

As the answer can be rather large, print it modulo 1000000007 (109 + 7).

## Input Format
The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 106). The second line contains string s. String s has length n and only consists of characters "W", "B" and "X".

## Output Format
On a single line print an integer — the answer to the problem modulo 1000000007 (109 + 7).

## Examples
```input
3 2
XXX
```
```output
0
```
-----
```input
4 2
XXXX
```
```output
1
```
-----
```input
10 2
XXBXXWXXXX
```
```output
166
```

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
Valera the Horse is going to the party with friends. He has been following the fashion trends for a while, and he knows that it is very popular to wear all horseshoes of different color. Valera has got four horseshoes left from the last year, but maybe some of them have the same color. In this case he needs to go to the store and buy some few more horseshoes, not to lose face in front of his stylish comrades.

Fortunately, the store sells horseshoes of all colors under the sun and Valera has enough money to buy any four of them. However, in order to save the money, he would like to spend as little money as possible, so you need to help Valera and determine what is the minimum number of horseshoes he needs to buy to wear four horseshoes of different colors to a party.

## Input Format
The first line contains four space-separated integers s1, s2, s3, s4 (1 ≤ s1, s2, s3, s4 ≤ 109) — the colors of horseshoes Valera has.

Consider all possible colors indexed with integers.

## Output Format
Print a single integer — the minimum number of horseshoes Valera needs to buy.

## Examples
```input
1 7 3 3
```
```output
1
```
-----
```input
7 7 7 7
```
```output
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've got two rectangular tables with sizes na × ma and nb × mb cells. The tables consist of zeroes and ones. We will consider the rows and columns of both tables indexed starting from 1. Then we will define the element of the first table, located at the intersection of the i-th row and the j-th column, as ai, j; we will define the element of the second table, located at the intersection of the i-th row and the j-th column, as bi, j.

We will call the pair of integers (x, y) a shift of the second table relative to the first one. We'll call the overlap factor of the shift (x, y) value:

$$\sum_{i,j}a_{i,j}\cdot b_{i+x,j+y}$$

where the variables i, j take only such values, in which the expression ai, j·bi + x, j + y makes sense. More formally, inequalities 1 ≤ i ≤ na, 1 ≤ j ≤ ma, 1 ≤ i + x ≤ nb, 1 ≤ j + y ≤ mb must hold. If there are no values of variables i, j, that satisfy the given inequalities, the value of the sum is considered equal to 0.

Your task is to find the shift with the maximum overlap factor among all possible shifts.

## Input Format
The first line contains two space-separated integers na, ma (1 ≤ na, ma ≤ 50) — the number of rows and columns in the first table. Then na lines contain ma characters each — the elements of the first table. Each character is either a "0", or a "1".

The next line contains two space-separated integers nb, mb (1 ≤ nb, mb ≤ 50) — the number of rows and columns in the second table. Then follow the elements of the second table in the format, similar to the first table.

It is guaranteed that the first table has at least one number "1". It is guaranteed that the second table has at least one number "1".

## Output Format
Print two space-separated integers x, y (|x|, |y| ≤ 109) — a shift with maximum overlap factor. If there are multiple solutions, print any of them.

## Examples
```input
3 2
01
10
00
2 3
001
111
```
```output
0 1
```
-----
```input
3 3
000
010
000
1 1
1
```
```output
-1 -1
```

Now solve the problem and return the code.