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

# Problem
You are given a positive integer $$$k$$$. For a multiset of integers $$$S$$$, define $$$f(S)$$$ as the following.

- If the number of elements in $$$S$$$ is less than $$$k$$$, $$$f(S)=0$$$.
- Otherwise, define $$$f(S)$$$ as the maximum product you can get by choosing exactly $$$k$$$ integers from $$$S$$$.

More formally, let $$$|S|$$$ denote the number of elements in $$$S$$$. Then,

- If $$$|S|<k$$$, $$$f(S)=0$$$.
- Otherwise, $$$f(S)=\max\limits_{T\subseteq S,|T|=k}\left(\prod\limits_{i\in T}i\right)$$$.

You are given a multiset of integers, $$$A$$$. Compute $$$\sum\limits_{B\subseteq A} f(B)$$$ modulo $$$10^9+7$$$.

Note that in this problem, we distinguish the elements by indices instead of values. That is, a multiset consisting of $$$n$$$ elements always has $$$2^n$$$ distinct subsets regardless of whether some of its elements are equal.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$k$$$, where $$$n$$$ is the number of elements in $$$A$$$ ($$$1\le k\le n\le 600$$$).

The second line of input contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, describing the elements in $$$A$$$ ($$$-10^9\le a_i\le 10^9$$$).

## Output Format
Output $$$\sum\limits_{B\subseteq A} f(B)$$$ modulo $$$10^9+7$$$.

## Examples
```input
3 2
-1 2 4
```
```output
10
```
-----
```input
3 1
1 1 1
```
```output
7
```
-----
```input
10 4
-24 -41 9 -154 -56 14 18 53 -7 120
```
```output
225905161
```
-----
```input
15 5
0 0 2 -2 2 -2 3 -3 -3 4 5 -4 -4 4 5
```
```output
18119684
```

## Note
Consider the first sample. From the definitions we know that

- $$$f(\varnothing)=0$$$
- $$$f(\{-1\})=0$$$
- $$$f(\{2\})=0$$$
- $$$f(\{4\})=0$$$
- $$$f(\{-1,2\})=-2$$$
- $$$f(\{-1,4\})=-4$$$
- $$$f(\{2,4\})=8$$$
- $$$f(\{-1,2,4\})=8$$$

So we should print $$$(0+0+0+0-2-4+8+8)\bmod (10^9+7)=10$$$.

In the second example, note that although the multiset consists of three same values, it still has $$$8$$$ distinct subsets: $$$\varnothing,\{1\},\{1\},\{1\},\{1,1\},\{1,1\},\{1,1\},\{1,1,1\}$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are living on an infinite plane with the Cartesian coordinate system on it. In one move you can go to any of the four adjacent points (left, right, up, down).

More formally, if you are standing at the point $$$(x, y)$$$, you can:

- go left, and move to $$$(x - 1, y)$$$, or
- go right, and move to $$$(x + 1, y)$$$, or
- go up, and move to $$$(x, y + 1)$$$, or
- go down, and move to $$$(x, y - 1)$$$.

There are $$$n$$$ boxes on this plane. The $$$i$$$-th box has coordinates $$$(x_i,y_i)$$$. It is guaranteed that the boxes are either on the $$$x$$$-axis or the $$$y$$$-axis. That is, either $$$x_i=0$$$ or $$$y_i=0$$$.

You can collect a box if you and the box are at the same point. Find the minimum number of moves you have to perform to collect all of these boxes if you have to start and finish at the point $$$(0,0)$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of boxes.

The $$$i$$$-th line of the following $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-100 \le x_i, y_i \le 100$$$) — the coordinate of the $$$i$$$-th box. It is guaranteed that either $$$x_i=0$$$ or $$$y_i=0$$$.

Do note that the sum of $$$n$$$ over all test cases is not bounded.

## Output Format
For each test case output a single integer — the minimum number of moves required.

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

## Note
In the first test case, a possible sequence of moves that uses the minimum number of moves required is shown below.

$$$$$$(0,0) \to (1,0) \to (1,1) \to (1, 2) \to (0,2) \to (-1,2) \to (-1,1) \to (-1,0) \to (-1,-1) \to (-1,-2) \to (0,-2) \to (0,-1) \to (0,0)$$$$$$

In the second test case, a possible sequence of moves that uses the minimum number of moves required is shown below.

$$$$$$(0,0) \to (0,1) \to (0,2) \to (-1, 2) \to (-2,2) \to (-3,2) \to (-3,1) \to (-3,0) \to (-3,-1) \to (-2,-1) \to (-1,-1) \to (0,-1) \to (0,0)$$$$$$

In the third test case, we can collect all boxes without making any moves.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Consider an array $$$a$$$ of $$$n$$$ positive integers.

You may perform the following operation:

- select two indices $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), then
- decrease all elements $$$a_l, a_{l + 1}, \dots, a_r$$$ by $$$1$$$.

Let's call $$$f(a)$$$ the minimum number of operations needed to change array $$$a$$$ into an array of $$$n$$$ zeros.

Determine if for all permutations$$$^\dagger$$$ $$$b$$$ of $$$a$$$, $$$f(a) \leq f(b)$$$ is true.

$$$^\dagger$$$ An array $$$b$$$ is a permutation of an array $$$a$$$ if $$$b$$$ consists of the elements of $$$a$$$ in arbitrary order. For example, $$$[4,2,3,4]$$$ is a permutation of $$$[3,2,4,4]$$$ while $$$[1,2,2]$$$ is not a permutation of $$$[1,2,3]$$$.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — description of the array $$$a$$$.

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

## Output Format
For each test case, print "YES" (without quotes) if for all permutations $$$b$$$ of $$$a$$$, $$$f(a) \leq f(b)$$$ is true, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

## Examples
```input
3
4
2 3 5 4
3
1 2 3
4
3 1 3 2
```
```output
YES
YES
NO
```

## Note
In the first test case, we can change all elements to $$$0$$$ in $$$5$$$ operations. It can be shown that no permutation of $$$[2, 3, 5, 4]$$$ requires less than $$$5$$$ operations to change all elements to $$$0$$$.

In the third test case, we need $$$5$$$ operations to change all elements to $$$0$$$, while $$$[2, 3, 3, 1]$$$ only needs $$$3$$$ operations.

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
A $$$\mathbf{0}$$$-indexed array $$$a$$$ of size $$$n$$$ is called good if for all valid indices $$$i$$$ ($$$0 \le i \le n-1$$$), $$$a_i + i$$$ is a perfect square$$$^\dagger$$$.

Given an integer $$$n$$$. Find a permutation$$$^\ddagger$$$ $$$p$$$ of $$$[0,1,2,\ldots,n-1]$$$ that is good or determine that no such permutation exists.

$$$^\dagger$$$ An integer $$$x$$$ is said to be a perfect square if there exists an integer $$$y$$$ such that $$$x = y^2$$$.

$$$^\ddagger$$$ An array $$$b$$$ is a permutation of an array $$$a$$$ if $$$b$$$ consists of the elements of $$$a$$$ in arbitrary order. For example, $$$[4,2,3,4]$$$ is a permutation of $$$[3,2,4,4]$$$ while $$$[1,2,2]$$$ is not a permutation of $$$[1,2,3]$$$.

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the permutation $$$p$$$.

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

## Output Format
For each test case, output $$$n$$$ distinct integers $$$p_0, p_1, \dots, p_{n-1}$$$ ($$$0 \le p_i \le n-1$$$) — the permutation $$$p$$$ — if the answer exists, and $$$-1$$$ otherwise.

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

## Note
In the first test case, we have $$$n=3$$$. The array $$$p = [1, 0, 2]$$$ is good since $$$1 + 0 = 1^2$$$, $$$0 + 1 = 1^2$$$, and $$$2 + 2 = 2^2$$$

In the second test case, we have $$$n=4$$$. The array $$$p = [0, 3, 2, 1]$$$ is good since $$$0 + 0 = 0^2$$$, $$$3 + 1 = 2^2$$$, $$$2+2 = 2^2$$$, and $$$1+3 = 2^2$$$.

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
A long time ago, Spyofgame invented the famous array $$$a$$$ ($$$1$$$-indexed) of length $$$n$$$ that contains information about the world and life. After that, he decided to convert it into the matrix $$$b$$$ ($$$0$$$-indexed) of size $$$(n + 1) \times (n + 1)$$$ which contains information about the world, life and beyond.

Spyofgame converted $$$a$$$ into $$$b$$$ with the following rules.

- $$$b_{i,0} = 0$$$ if $$$0 \leq i \leq n$$$;
- $$$b_{0,i} = a_{i}$$$ if $$$1 \leq i \leq n$$$;
- $$$b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}$$$ if $$$1 \leq i, j \leq n$$$.

Here $$$\oplus$$$ denotes the bitwise XOR operation.

Today, archaeologists have discovered the famous matrix $$$b$$$. However, many elements of the matrix has been lost. They only know the values of $$$b_{i,n}$$$ for $$$1 \leq i \leq n$$$ (note that these are some elements of the last column, not the last row).

The archaeologists want to know what a possible array of $$$a$$$ is. Can you help them reconstruct any array that could be $$$a$$$?

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$b_{1,n}, b_{2,n}, \ldots, b_{n,n}$$$ ($$$0 \leq b_{i,n} < 2^{30}$$$).

## Output Format
If some array $$$a$$$ is consistent with the information, print a line containing $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. If there are multiple solutions, output any.

If such an array does not exist, output $$$-1$$$ instead.

## Examples
```input
3
0 2 1
```
```output
1 2 3
```
-----
```input
1
199633
```
```output
199633
```
-----
```input
10
346484077 532933626 858787727 369947090 299437981 416813461 865836801 141384800 157794568 691345607
```
```output
725081944 922153789 481174947 427448285 516570428 509717938 855104873 280317429 281091129 1050390365
```

## Note
If we let $$$a = [1,2,3]$$$, then $$$b$$$ will be:

$$$\bf{0}$$$$$$\bf{1}$$$$$$\bf{2}$$$$$$\bf{3}$$$$$$\bf{0}$$$$$$1$$$$$$3$$$$$$0$$$$$$\bf{0}$$$$$$1$$$$$$2$$$$$$2$$$$$$\bf{0}$$$$$$1$$$$$$3$$$$$$1$$$

The values of $$$b_{1,n}, b_{2,n}, \ldots, b_{n,n}$$$ generated are $$$[0,2,1]$$$ which is consistent with what the archaeologists have discovered.

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
Madoka is a very strange girl, and therefore she suddenly wondered how many pairs of integers $$$(a, b)$$$ exist, where $$$1 \leq a, b \leq n$$$, for which $$$\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3$$$.

In this problem, $$$\operatorname{gcd}(a, b)$$$ denotes the greatest common divisor of the numbers $$$a$$$ and $$$b$$$, and $$$\operatorname{lcm}(a, b)$$$ denotes the smallest common multiple of the numbers $$$a$$$ and $$$b$$$.

## Input Format
The input consists of 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 and the only line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 10^8$$$).

## Output Format
For each test case output a single integer — the number of pairs of integers satisfying the condition.

## Examples
```input
6
1
2
3
4
5
100000000
```
```output
1
4
7
10
11
266666666
```

## Note
For $$$n = 1$$$ there is exactly one pair of numbers — $$$(1, 1)$$$ and it fits.

For $$$n = 2$$$, there are only $$$4$$$ pairs — $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$ and they all fit.

For $$$n = 3$$$, all $$$9$$$ pair are suitable, except $$$(2, 3)$$$ and $$$(3, 2)$$$, since their $$$\operatorname{lcm}$$$ is $$$6$$$, and $$$\operatorname{gcd}$$$ is $$$1$$$, which doesn't fit the condition.

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
Madoka decided to participate in an underground sports programming competition. And there was exactly one task in it:

A square table of size $$$n \times n$$$, where $$$n$$$ is a multiple of $$$k$$$, is called good if only the characters '.' and 'X' are written in it, as well as in any subtable of size $$$1 \times k$$$ or $$$k \times 1$$$, there is at least one character 'X'. In other words, among any $$$k$$$ consecutive vertical or horizontal cells, there must be at least one containing the character 'X'.

Output any good table that has the minimum possible number of characters 'X', and also the symbol 'X' is written in the cell $$$(r, c)$$$. Rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, columns are numbered from $$$1$$$ to $$$n$$$ from left to right.

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

The first and the only line of each test case contains four integers $$$n$$$, $$$k$$$, $$$r$$$, $$$c$$$ ($$$1 \le n \le 500, 1 \le k \le n, 1 \le r, c \le n$$$) — the size of the table, the integer $$$k$$$ and the coordinates of the cell, which must contain the character 'X'. It is guaranteed that $$$n$$$ is a multiple of $$$k$$$.

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

## Output Format
For each test case, output $$$n$$$ lines, each consisting of $$$n$$$ characters '.' and 'X', — the desired table. If there are several answers, then you can output anyone.

## Examples
```input
3
3 3 3 2
2 1 1 2
6 3 4 2
```
```output
X..
..X
.X.
XX
XX
.X..X.
X..X..
..X..X
.X..X.
X..X..
..X..X
```

## Note
Let's analyze the first test case.

The following tables can be printed as the correct answer:

X....X.X. or ..XX...X.

Note that the following table is invalid because cell $$$(3, 2)$$$ does not contain the character 'X':

X...X...X

In the second test case, the only correct table is:

XXXX

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
Given an array of integer $$$a_1, a_2, \ldots, a_n$$$. In one operation you can make $$$a_i := a_i + 1$$$ if $$$i < n$$$ and $$$a_i \leq a_{i + 1}$$$, or $$$i = n$$$ and $$$a_i \leq a_1$$$.

You need to check whether the array $$$a_1, a_2, \ldots, a_n$$$ can become equal to the array $$$b_1, b_2, \ldots, b_n$$$ in some number of operations (possibly, zero). Two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ are called equal if $$$a_i = b_i$$$ for all integers $$$i$$$ from $$$1$$$ to $$$n$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) – the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) – the elements of the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) – the elements of the array $$$b$$$.

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 "YES" if you can get the array $$$b$$$, otherwise output "NO".

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

## Examples
```input
5
3
1 2 5
1 2 5
2
2 2
1 3
4
3 4 1 2
6 4 2 5
3
2 4 1
4 5 3
5
1 2 3 4 5
6 5 6 7 6
```
```output
YES
NO
NO
NO
YES
```

## Note
In the first test case, the array $$$a$$$ is already equal to the array $$$b$$$.

In the second test case, we can't get the array $$$b$$$, because to do this we need to decrease $$$a_1$$$.

In the fifth test case, we can apply operations in order to the elements with indices $$$4, 3, 3,2,2,2,1,1,1,1$$$, and then get the array $$$[5,5,5,5,5]$$$. After that, you can apply operations in order to elements with indices $$$5,4,4,3,1$$$ and already get an array $$$[6,5,6,7,6]$$$.

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
Madoka wants to enter to "Novosibirsk State University", but in the entrance exam she came across a very difficult task:

Given an integer $$$n$$$, it is required to calculate $$$\sum{\operatorname{lcm}(c, \gcd(a, b))}$$$, for all triples of positive integers $$$(a, b, c)$$$, where $$$a + b + c = n$$$.

In this problem $$$\gcd(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$, and $$$\operatorname{lcm}(x, y)$$$ denotes the least common multiple of $$$x$$$ and $$$y$$$.

Solve this problem for Madoka and help her to enter to the best university!

## Input Format
The first and the only line contains a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$).

## Output Format
Print exactly one interger — $$$\sum{\operatorname{lcm}(c, \gcd(a, b))}$$$. Since the answer can be very large, then output it modulo $$$10^9 + 7$$$.

## Examples
```input
3
```
```output
1
```
-----
```input
5
```
```output
11
```
-----
```input
69228
```
```output
778304278
```

## Note
In the first example, there is only one suitable triple $$$(1, 1, 1)$$$. So the answer is $$$\operatorname{lcm}(1, \gcd(1, 1)) = \operatorname{lcm}(1, 1) = 1$$$.

In the second example, $$$\operatorname{lcm}(1, \gcd(3, 1)) + \operatorname{lcm}(1, \gcd(2, 2)) + \operatorname{lcm}(1, \gcd(1, 3)) + \operatorname{lcm}(2, \gcd(2, 1)) + \operatorname{lcm}(2, \gcd(1, 2)) + \operatorname{lcm}(3, \gcd(1, 1)) = \operatorname{lcm}(1, 1) + \operatorname{lcm}(1, 2) + \operatorname{lcm}(1, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(3, 1) = 1 + 2 + 1 + 2 + 2 + 3 = 11$$$

Now solve the problem and return the code.