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
You are given two integers $$$n$$$ and $$$m$$$. Calculate the number of pairs of arrays $$$(a, b)$$$ such that:

- the length of both arrays is equal to $$$m$$$;
- each element of each array is an integer between $$$1$$$ and $$$n$$$ (inclusive);
- $$$a_i \le b_i$$$ for any index $$$i$$$ from $$$1$$$ to $$$m$$$;
- array $$$a$$$ is sorted in non-descending order;
- array $$$b$$$ is sorted in non-ascending order.

As the result can be very large, you should print it modulo $$$10^9+7$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 1000$$$, $$$1 \le m \le 10$$$).

## Output Format
Print one integer – the number of arrays $$$a$$$ and $$$b$$$ satisfying the conditions described above modulo $$$10^9+7$$$.

## Examples
```input
2 2
```
```output
5
```
-----
```input
10 1
```
```output
55
```
-----
```input
723 9
```
```output
157557417
```

## Note
In the first test there are $$$5$$$ suitable arrays:

- $$$a = [1, 1], b = [2, 2]$$$;
- $$$a = [1, 2], b = [2, 2]$$$;
- $$$a = [2, 2], b = [2, 2]$$$;
- $$$a = [1, 1], b = [2, 1]$$$;
- $$$a = [1, 1], b = [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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given $$$n$$$ arrays $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$; each array consists of exactly $$$m$$$ integers. We denote the $$$y$$$-th element of the $$$x$$$-th array as $$$a_{x, y}$$$.

You have to choose two arrays $$$a_i$$$ and $$$a_j$$$ ($$$1 \le i, j \le n$$$, it is possible that $$$i = j$$$). After that, you will obtain a new array $$$b$$$ consisting of $$$m$$$ integers, such that for every $$$k \in [1, m]$$$ $$$b_k = \max(a_{i, k}, a_{j, k})$$$.

Your goal is to choose $$$i$$$ and $$$j$$$ so that the value of $$$\min \limits_{k = 1}^{m} b_k$$$ is maximum possible.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 8$$$) — the number of arrays and the number of elements in each array, respectively.

Then $$$n$$$ lines follow, the $$$x$$$-th line contains the array $$$a_x$$$ represented by $$$m$$$ integers $$$a_{x, 1}$$$, $$$a_{x, 2}$$$, ..., $$$a_{x, m}$$$ ($$$0 \le a_{x, y} \le 10^9$$$).

## Output Format
Print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, it is possible that $$$i = j$$$) — the indices of the two arrays you have to choose so that the value of $$$\min \limits_{k = 1}^{m} b_k$$$ is maximum possible. If there are multiple answers, print any of them.

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

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: 5.0 seconds
Memory limit: 768.0 MB

# Problem
You are given $$$n$$$ pairwise non-collinear two-dimensional vectors. You can make shapes in the two-dimensional plane with these vectors in the following fashion:

1. Start at the origin $$$(0, 0)$$$.
2. Choose a vector and add the segment of the vector to the current point. For example, if your current point is at $$$(x, y)$$$ and you choose the vector $$$(u, v)$$$, draw a segment from your current point to the point at $$$(x + u, y + v)$$$ and set your current point to $$$(x + u, y + v)$$$.
3. Repeat step 2 until you reach the origin again.

You can reuse a vector as many times as you want.

Count the number of different, non-degenerate (with an area greater than $$$0$$$) and convex shapes made from applying the steps, such that the shape can be contained within a $$$m \times m$$$ square, and the vectors building the shape are in counter-clockwise fashion. Since this number can be too large, you should calculate it by modulo $$$998244353$$$.

Two shapes are considered the same if there exists some parallel translation of the first shape to another.

A shape can be contained within a $$$m \times m$$$ square if there exists some parallel translation of this shape so that every point $$$(u, v)$$$ inside or on the border of the shape satisfies $$$0 \leq u, v \leq m$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$  — the number of vectors and the size of the square ($$$1 \leq n \leq 5$$$, $$$1 \leq m \leq 10^9$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$  — the $$$x$$$-coordinate and $$$y$$$-coordinate of the $$$i$$$-th vector ($$$|x_i|, |y_i| \leq 4$$$, $$$(x_i, y_i) \neq (0, 0)$$$).

It is guaranteed, that no two vectors are parallel, so for any two indices $$$i$$$ and $$$j$$$ such that $$$1 \leq i < j \leq n$$$, there is no real value $$$k$$$ such that $$$x_i \cdot k = x_j$$$ and $$$y_i \cdot k = y_j$$$.

## Output Format
Output a single integer  — the number of satisfiable shapes by modulo $$$998244353$$$.

## Examples
```input
3 3
-1 0
1 1
0 -1
```
```output
3
```
-----
```input
3 3
-1 0
2 2
0 -1
```
```output
1
```
-----
```input
3 1776966
-1 0
3 3
0 -2
```
```output
296161
```
-----
```input
4 15
-4 -4
-1 1
-1 -4
4 3
```
```output
1
```
-----
```input
5 10
3 -4
4 -3
1 -3
2 -3
-3 -4
```
```output
0
```
-----
```input
5 1000000000
-2 4
2 -3
0 -4
2 4
-1 -3
```
```output
9248783
```

## Note
The shapes for the first sample are:

The only shape for the second sample is:

The only shape for the fourth sample is:

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
Little Petya likes numbers a lot. He found that number 123 in base 16 consists of two digits: the first is 7 and the second is 11. So the sum of digits of 123 in base 16 is equal to 18.

Now he wonders what is an average value of sum of digits of the number A written in all bases from 2 to A - 1.

Note that all computations should be done in base 10. You should find the result as an irreducible fraction, written in base 10.

## Input Format
Input contains one integer number A (3 ≤ A ≤ 1000).

## Output Format
Output should contain required average value in format «X/Y», where X is the numerator and Y is the denominator.

## Examples
```input
5
```
```output
7/3
```
-----
```input
3
```
```output
2/1
```

## Note
In the first sample number 5 written in all bases from 2 to 4 looks so: 101, 12, 11. Sums of digits are 2, 3 and 2, respectively.

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
Little Petya likes to play very much. And most of all he likes to play the following game:

He is given a sequence of N integer numbers. At each step it is allowed to increase the value of any number by 1 or to decrease it by 1. The goal of the game is to make the sequence non-decreasing with the smallest number of steps. Petya is not good at math, so he asks for your help.

The sequence a is called non-decreasing if a1 ≤ a2 ≤ ... ≤ aN holds, where N is the length of the sequence.

## Input Format
The first line of the input contains single integer N (1 ≤ N ≤ 5000) — the length of the initial sequence. The following N lines contain one integer each — elements of the sequence. These numbers do not exceed 109 by absolute value.

## Output Format
Output one integer — minimum number of steps required to achieve the goal.

## Examples
```input
5
3 2 -1 2 11
```
```output
4
```
-----
```input
5
2 1 1 1 1
```
```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: 64.0 MB

# Problem
Little Petya likes to draw. He drew N red and M blue points on the plane in such a way that no three points lie on the same line. Now he wonders what is the number of distinct triangles with vertices in red points which do not contain any blue point inside.

## Input Format
The first line contains two non-negative integer numbers N and M (0 ≤ N ≤ 500, 0 ≤ M ≤ 500) — the number of red and blue points respectively. The following N lines contain two integer numbers each — coordinates of red points. The following M lines contain two integer numbers each — coordinates of blue points. All coordinates do not exceed 109 by absolute value.

## Output Format
Output one integer — the number of distinct triangles with vertices in red points which do not contain any blue point inside.

## Examples
```input
4 1
0 0
10 0
10 10
5 4
2 1
```
```output
2
```
-----
```input
5 5
5 10
6 1
8 6
-6 -7
7 -1
5 -1
10 -4
-10 -8
-10 5
-2 -8
```
```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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Guy-Manuel and Thomas have an array $$$a$$$ of $$$n$$$ integers [$$$a_1, a_2, \dots, a_n$$$]. In one step they can add $$$1$$$ to any element of the array. Formally, in one step they can choose any integer index $$$i$$$ ($$$1 \le i \le n$$$) and do $$$a_i := a_i + 1$$$.

If either the sum or the product of all elements in the array is equal to zero, Guy-Manuel and Thomas do not mind to do this operation one more time.

What is the minimum number of steps they need to do to make both the sum and the product of all elements in the array different from zero? Formally, find the minimum number of steps to make $$$a_1 + a_2 +$$$ $$$\dots$$$ $$$+ a_n \ne 0$$$ and $$$a_1 \cdot a_2 \cdot$$$ $$$\dots$$$ $$$\cdot a_n \ne 0$$$.

## Input Format
Each test contains multiple test cases.

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — elements of the array .

## Output Format
For each test case, output the minimum number of steps required to make both sum and product of all elements in the array different from zero.

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

## Note
In the first test case, the sum is $$$0$$$. If we add $$$1$$$ to the first element, the array will be $$$[3,-1,-1]$$$, the sum will be equal to $$$1$$$ and the product will be equal to $$$3$$$.

In the second test case, both product and sum are $$$0$$$. If we add $$$1$$$ to the second and the third element, the array will be $$$[-1,1,1,1]$$$, the sum will be equal to $$$2$$$ and the product will be equal to $$$-1$$$. It can be shown that fewer steps can't be enough.

In the third test case, both sum and product are non-zero, we don't need to do anything.

In the fourth test case, after adding $$$1$$$ twice to the first element the array will be $$$[2,-2,1]$$$, the sum will be $$$1$$$ and the product will be $$$-4$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
To become the king of Codeforces, Kuroni has to solve the following problem.

He is given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. Help Kuroni to calculate $$$\prod_{1\le i<j\le n} |a_i - a_j|$$$. As result can be very big, output it modulo $$$m$$$.

If you are not familiar with short notation, $$$\prod_{1\le i<j\le n} |a_i - a_j|$$$ is equal to $$$|a_1 - a_2|\cdot|a_1 - a_3|\cdot$$$ $$$\dots$$$ $$$\cdot|a_1 - a_n|\cdot|a_2 - a_3|\cdot|a_2 - a_4|\cdot$$$ $$$\dots$$$ $$$\cdot|a_2 - a_n| \cdot$$$ $$$\dots$$$ $$$\cdot |a_{n-1} - a_n|$$$. In other words, this is the product of $$$|a_i - a_j|$$$ for all $$$1\le i < j \le n$$$.

## Input Format
The first line contains two integers $$$n$$$, $$$m$$$ ($$$2\le n \le 2\cdot 10^5$$$, $$$1\le m \le 1000$$$) — number of numbers and modulo.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

## Output Format
Output the single number — $$$\prod_{1\le i<j\le n} |a_i - a_j| \bmod m$$$.

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

## Note
In the first sample, $$$|8 - 5| = 3 \equiv 3 \bmod 10$$$.

In the second sample, $$$|1 - 4|\cdot|1 - 5|\cdot|4 - 5| = 3\cdot 4 \cdot 1 = 12 \equiv 0 \bmod 12$$$.

In the third sample, $$$|1 - 4|\cdot|1 - 9|\cdot|4 - 9| = 3 \cdot 8 \cdot 5 = 120 \equiv 1 \bmod 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Kuroni is the coordinator of the next Mathforces round written by the "Proof by AC" team. All the preparation has been done, and he is discussing with the team about the score distribution for the round.

The round consists of $$$n$$$ problems, numbered from $$$1$$$ to $$$n$$$. The problems are ordered in increasing order of difficulty, no two problems have the same difficulty. A score distribution for the round can be denoted by an array $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the score of $$$i$$$-th problem.

Kuroni thinks that the score distribution should satisfy the following requirements:

- The score of each problem should be a positive integer not exceeding $$$10^9$$$.
- A harder problem should grant a strictly higher score than an easier problem. In other words, $$$1 \leq a_1 < a_2 < \dots < a_n \leq 10^9$$$.
- The balance of the score distribution, defined as the number of triples $$$(i, j, k)$$$ such that $$$1 \leq i < j < k \leq n$$$ and $$$a_i + a_j = a_k$$$, should be exactly $$$m$$$.

Help the team find a score distribution that satisfies Kuroni's requirement. In case such a score distribution does not exist, output $$$-1$$$.

## Input Format
The first and single line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5000$$$, $$$0 \leq m \leq 10^9$$$) — the number of problems and the required balance.

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

Otherwise, print a line containing $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, representing a score distribution that satisfies all the requirements. If there are multiple answers, print any of them.

## Examples
```input
5 3
```
```output
4 5 9 13 18
```
-----
```input
8 0
```
```output
10 11 12 13 14 15 16 17
```
-----
```input
4 10
```
```output
-1
```

## Note
In the first example, there are $$$3$$$ triples $$$(i, j, k)$$$ that contribute to the balance of the score distribution.

- $$$(1, 2, 3)$$$
- $$$(1, 3, 4)$$$
- $$$(2, 4, 5)$$$

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

# Problem
Kuroni is very angry at the other setters for using him as a theme! As a punishment, he forced them to solve the following problem:

You have an array $$$a$$$ consisting of $$$n$$$ positive integers. An operation consists of choosing an element and either adding $$$1$$$ to it or subtracting $$$1$$$ from it, such that the element remains positive. We say the array is good if the greatest common divisor of all its elements is not $$$1$$$. Find the minimum number of operations needed to make the array good.

Unable to match Kuroni's intellect, the setters failed to solve the problem. Help them escape from Kuroni's punishment!

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)  — the number of elements in the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. ($$$1 \le a_i \le 10^{12}$$$)  — the elements of the array.

## Output Format
Print a single integer  — the minimum number of operations required to make the array good.

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

## Note
In the first example, the first array is already good, since the greatest common divisor of all the elements is $$$2$$$.

In the second example, we may apply the following operations:

1. Add $$$1$$$ to the second element, making it equal to $$$9$$$.
2. Subtract $$$1$$$ from the third element, making it equal to $$$6$$$.
3. Add $$$1$$$ to the fifth element, making it equal to $$$2$$$.
4. Add $$$1$$$ to the fifth element again, making it equal to $$$3$$$.

The greatest common divisor of all elements will then be equal to $$$3$$$, so the array will be good. It can be shown that no sequence of three or less operations can make the array good.

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

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

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

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Kuroni isn't good at economics. So he decided to found a new financial pyramid called Antihype. It has the following rules:

1. You can join the pyramid for free and get $$$0$$$ coins.
2. If you are already a member of Antihype, you can invite your friend who is currently not a member of Antihype, and get a number of coins equal to your age (for each friend you invite).

$$$n$$$ people have heard about Antihype recently, the $$$i$$$-th person's age is $$$a_i$$$. Some of them are friends, but friendship is a weird thing now: the $$$i$$$-th person is a friend of the $$$j$$$-th person if and only if $$$a_i \text{ AND } a_j = 0$$$, where $$$\text{AND}$$$ denotes the bitwise AND operation.

Nobody among the $$$n$$$ people is a member of Antihype at the moment. They want to cooperate to join and invite each other to Antihype in a way that maximizes their combined gainings. Could you help them?

## Input Format
The first line contains a single integer $$$n$$$ ($$$1\le n \le 2\cdot 10^5$$$)  — the number of people.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i \le 2\cdot 10^5$$$)  — the ages of the people.

## Output Format
Output exactly one integer  — the maximum possible combined gainings of all $$$n$$$ people.

## Examples
```input
3
1 2 3
```
```output
2
```

## Note
Only the first and second persons are friends. The second can join Antihype and invite the first one, getting $$$2$$$ for it.

Now solve the problem and return the code.