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 a sequence $$$a_1, a_2, \ldots, a_n$$$. Each element of $$$a$$$ is $$$1$$$ or $$$2$$$.

Find out if an integer $$$k$$$ exists so that the following conditions are met.

- $$$1 \leq k \leq n-1$$$, and
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$$$.

If there exist multiple $$$k$$$ that satisfy the given condition, print the smallest.

## 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 one integer $$$n$$$ ($$$2 \leq n \leq 1000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2$$$).

## Output Format
For each test case, if there is no such $$$k$$$, print $$$-1$$$.

Otherwise, print the smallest possible $$$k$$$.

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

## Note
For the first test case, $$$k=2$$$ satisfies the condition since $$$a_1 \cdot a_2 = a_3 \cdot a_4 \cdot a_5 \cdot a_6 = 4$$$. $$$k=3$$$ also satisfies the given condition, but the smallest should be printed.

For the second test case, there is no $$$k$$$ that satisfies $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$$$

For the third test case, $$$k=1$$$, $$$2$$$, and $$$3$$$ satisfy the given condition, so the answer is $$$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
The sum of digits of a non-negative integer $$$a$$$ is the result of summing up its digits together when written in the decimal system. For example, the sum of digits of $$$123$$$ is $$$6$$$ and the sum of digits of $$$10$$$ is $$$1$$$. In a formal way, the sum of digits of $$$\displaystyle a=\sum_{i=0}^{\infty} a_i \cdot 10^i$$$, where $$$0 \leq a_i \leq 9$$$, is defined as $$$\displaystyle\sum_{i=0}^{\infty}{a_i}$$$.

Given an integer $$$n$$$, find two non-negative integers $$$x$$$ and $$$y$$$ which satisfy the following conditions.

- $$$x+y=n$$$, and
- the sum of digits of $$$x$$$ and the sum of digits of $$$y$$$ differ by at most $$$1$$$.

It can be shown that such $$$x$$$ and $$$y$$$ always exist.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$).

Each test case consists of a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$)

## Output Format
For each test case, print two integers $$$x$$$ and $$$y$$$.

If there are multiple answers, print any.

## Examples
```input
5
1
161
67
1206
19
```
```output
1 0
67 94
60 7
1138 68
14 5
```

## Note
In the second test case, the sum of digits of $$$67$$$ and the sum of digits of $$$94$$$ are both $$$13$$$.

In the third test case, the sum of digits of $$$60$$$ is $$$6$$$, and the sum of digits of $$$7$$$ is $$$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
You are given an integer $$$n$$$. Pair the integers $$$1$$$ to $$$2n$$$ (i.e. each integer should be in exactly one pair) so that each sum of matched pairs is consecutive and distinct.

Formally, let $$$(a_i, b_i)$$$ be the pairs that you matched. $$$\{a_1, b_1, a_2, b_2, \ldots, a_n, b_n\}$$$ should be a permutation of $$$\{1, 2, \ldots, 2n\}$$$. Let the sorted list of $$$\{a_1+b_1, a_2+b_2, \ldots, a_n+b_n\}$$$ be $$$s_1 < s_2 < \ldots < s_n$$$. We must have $$$s_{i+1}-s_i = 1$$$ for $$$1 \le i \le n - 1$$$.

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

For each test case, a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) is given.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, if it is impossible to make such a pairing, print "No".

Otherwise, print "Yes" followed by $$$n$$$ lines.

At each line, print two integers that are paired.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If there are multiple solutions, print any.

## Examples
```input
4
1
2
3
4
```
```output
Yes
1 2
No
Yes
1 6
3 5
4 2
No
```

## Note
For the third test case, each integer from $$$1$$$ to $$$6$$$ appears once. The sums of matched pairs are $$$4+2=6$$$, $$$1+6=7$$$, and $$$3+5=8$$$, which are consecutive and distinct.

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

# Problem
We play a game with $$$n$$$ dots on a number line.

The initial coordinate of the $$$i$$$-th dot is $$$x_i$$$. These coordinates are distinct. Every dot starts moving simultaneously with the same constant speed.

Each dot moves in the direction of the closest dot (different from itself) until it meets another dot. In the case of a tie, it goes to the left. Two dots meet if they are in the same coordinate, after that, they stop moving.

After enough time, every dot stops moving. The result of a game is the number of distinct coordinates where the dots stop.

Because this game is too easy, calculate the sum of results when we play the game for every subset of the given $$$n$$$ dots that has at least two dots. As the result can be very large, print the sum modulo $$$10^9+7$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 3000$$$).

The next line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9$$$), where $$$x_i$$$ represents the initial coordinate of $$$i$$$-th dot.

## Output Format
Print the sum of results modulo $$$10^9+7$$$.

## Examples
```input
4
1 2 4 6
```
```output
11
```
-----
```input
5
1 3 5 11 15
```
```output
30
```

## Note
In the first example, for a subset of size $$$2$$$, two dots move toward each other, so there is $$$1$$$ coordinate where the dots stop.

For a subset of size $$$3$$$, the first dot and third dot move toward the second dot, so there is $$$1$$$ coordinate where the dots stop no matter the direction where the second dot moves.

For $$$[1, 2, 4, 6]$$$, the first and second dots move toward each other. For the third dot, initially, the second dot and the fourth dot are the closest dots. Since it is a tie, the third dot moves left. The fourth dot also moves left. So there is $$$1$$$ coordinate where the dots stop, which is $$$1.5$$$.

Because there are $$$6$$$ subsets of size $$$2$$$, $$$4$$$ subsets of size $$$3$$$ and one subset of size $$$4$$$, the answer is $$$6 \cdot 1 + 4 \cdot 1 + 1 = 11$$$.

In the second example, for a subset of size $$$5$$$ (when there are dots at $$$1$$$, $$$3$$$, $$$5$$$, $$$11$$$, $$$15$$$), dots at $$$1$$$ and $$$11$$$ will move right and dots at $$$3$$$, $$$5$$$, $$$15$$$ will move left. Dots at $$$1$$$, $$$3$$$, $$$5$$$ will eventually meet at $$$2$$$, and dots at $$$11$$$ and $$$15$$$ will meet at $$$13$$$, so there are $$$2$$$ coordinates where the dots stop.

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 an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ integers. Consider $$$S$$$ as a set of segments satisfying the following conditions.

- Each element of $$$S$$$ should be in form $$$[x, y]$$$, where $$$x$$$ and $$$y$$$ are integers between $$$1$$$ and $$$n$$$, inclusive, and $$$x \leq y$$$.
- No two segments in $$$S$$$ intersect with each other. Two segments $$$[a, b]$$$ and $$$[c, d]$$$ intersect if and only if there exists an integer $$$x$$$ such that $$$a \leq x \leq b$$$ and $$$c \leq x \leq d$$$.
- For each $$$[x, y]$$$ in $$$S$$$, $$$a_x+a_{x+1}+ \ldots +a_y \geq 0$$$.

The length of the segment $$$[x, y]$$$ is defined as $$$y-x+1$$$. $$$f(S)$$$ is defined as the sum of the lengths of every element in $$$S$$$. In a formal way, $$$f(S) = \sum_{[x, y] \in S} (y - x + 1)$$$. Note that if $$$S$$$ is empty, $$$f(S)$$$ is $$$0$$$.

What is the maximum $$$f(S)$$$ among all possible $$$S$$$?

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

The next line is followed by $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).

## Output Format
Print a single integer, the maximum $$$f(S)$$$ among every possible $$$S$$$.

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

## Note
In the first example, $$$S=\{[1, 2], [4, 5]\}$$$ can be a possible $$$S$$$ because $$$a_1+a_2=0$$$ and $$$a_4+a_5=1$$$. $$$S=\{[1, 4]\}$$$ can also be a possible solution.

Since there does not exist any $$$S$$$ that satisfies $$$f(S) > 4$$$, the answer is $$$4$$$.

In the second example, $$$S=\{[1, 9]\}$$$ is the only set that satisfies $$$f(S)=9$$$. Since every possible $$$S$$$ satisfies $$$f(S) \leq 9$$$, the answer is $$$9$$$.

In the third example, $$$S$$$ can only be an empty set, so the answer is $$$0$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given three integers $$$a$$$, $$$b$$$, and $$$c$$$ such that exactly one of these two equations is true:

- $$$a+b=c$$$
- $$$a-b=c$$$

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

The description of each test case consists of three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \leq a, b \leq 9$$$, $$$-8 \leq c \leq 18$$$). The additional constraint on the input: it will be generated so that exactly one of the two equations will be true.

## Output Format
For each test case, output either + or - on a new line, representing the correct equation.

## Examples
```input
11
1 2 3
3 2 1
2 9 -7
3 4 7
1 1 2
1 1 0
3 3 6
9 9 18
9 9 0
1 9 -8
1 9 10
```
```output
+
-
-
+
+
-
+
+
-
-
+
```

## Note
In the first test case, $$$1+2=3$$$.

In the second test case, $$$3-2=1$$$.

In the third test case, $$$2-9=-7$$$. Note that $$$c$$$ can be negative.

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
Mushroom Filippov cooked himself a meal and while having his lunch, he decided to watch a video on TubeTube. He can not spend more than $$$t$$$ seconds for lunch, so he asks you for help with the selection of video.

The TubeTube feed is a list of $$$n$$$ videos, indexed from $$$1$$$ to $$$n$$$. The $$$i$$$-th video lasts $$$a_i$$$ seconds and has an entertainment value $$$b_i$$$. Initially, the feed is opened on the first video, and Mushroom can skip to the next video in $$$1$$$ second (if the next video exists). Mushroom can skip videos any number of times (including zero).

Help Mushroom choose one video that he can open and watch in $$$t$$$ seconds. If there are several of them, he wants to choose the most entertaining one. Print the index of any appropriate video, or $$$-1$$$ if there is no such.

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

The description of the test cases follows.

The first line of a test case contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 50$$$, $$$1 \le t \le 200$$$) — the number of videos in the feed and seconds for lunch, respectively.

The second line of a test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$) — durations of videos.

The third line of a test case contains $$$n$$$ integers $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 100$$$) — entertainment values of videos.

## Output Format
Output $$$q$$$ integers, each of which is the answer to the corresponding test case. As an answer, output the index of the most entertaining video that Mushroom will have time to watch. If there are several answers, you are allowed to output any of them. Output $$$-1$$$, if there is no video he can watch during his lunch break.

## Examples
```input
5
5 9
1 5 7 6 6
3 4 7 1 9
4 4
4 3 3 2
1 2 3 4
5 7
5 5 5 5 5
2 1 3 9 7
4 33
54 71 69 96
42 24 99 1
2 179
55 66
77 88
```
```output
3
2
3
-1
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Karina has an array of $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$. She loves multiplying numbers, so she decided that the beauty of a pair of numbers is their product. And the beauty of an array is the maximum beauty of a pair of adjacent elements in the array.

For example, for $$$n = 4$$$, $$$a=[3, 5, 7, 4]$$$, the beauty of the array is $$$\max$$$($$$3 \cdot 5$$$, $$$5 \cdot 7$$$, $$$7 \cdot 4$$$) = $$$\max$$$($$$15$$$, $$$35$$$, $$$28$$$) = $$$35$$$.

Karina wants her array to be as beautiful as possible. In order to achieve her goal, she can remove some elements (possibly zero) from the array. After Karina removes all elements she wants to, the array must contain at least two elements.

Unfortunately, Karina doesn't have enough time to do all her tasks, so she asks you to calculate the maximum beauty of the array that she can get by removing any number of elements (possibly zero).

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

The description of the test cases follows.

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

The second line of a test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

The sum of all values of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Output $$$t$$$ integers, each of which is the answer to the corresponding test case — the maximum beauty of the array that Karina can get.

## Examples
```input
7
4
5 0 2 1
3
-1 1 0
5
2 0 -1 -4 0
6
-8 4 3 7 1 -9
6
0 3 -2 5 -4 -4
2
1000000000 910000000
7
-1 -7 -2 -5 -4 -6 -3
```
```output
10
0
4
72
16
910000000000000000
42
```

## Note
In the first test case of the example, to get the maximum beauty, you need to remove the $$$2$$$-nd element.

In the second and third test cases of the example, there is no need to remove any elements to achieve maximum beauty.

In the fourth test case of the example, you need to leave only the first and last elements.

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
Tema loves cinnabon rolls — buns with cinnabon and chocolate in the shape of a "snail".

Cinnabon rolls come in different sizes and are square when viewed from above. The most delicious part of a roll is the chocolate, which is poured in a thin layer over the cinnabon roll in the form of a spiral and around the bun, as in the following picture:

Cinnabon rolls of sizes 4, 5, 6

For a cinnabon roll of size $$$n$$$, the length of the outer side of the square is $$$n$$$, and the length of the shortest vertical chocolate segment in the central part is one.

Formally, the bun consists of two dough spirals separated by chocolate. A cinnabon roll of size $$$n + 1$$$ is obtained from a cinnabon roll of size $$$n$$$ by wrapping each of the dough spirals around the cinnabon roll for another layer.

It is important that a cinnabon roll of size $$$n$$$ is defined in a unique way.

Tema is interested in how much chocolate is in his cinnabon roll of size $$$n$$$. Since Tema has long stopped buying small cinnabon rolls, it is guaranteed that $$$n \ge 4$$$.

Answer this non-obvious question by calculating the total length of the chocolate layer.

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

The following $$$t$$$ lines describe the test cases.

Each test case is described by a single integer $$$n$$$ ($$$4 \le n \le 10^9$$$) — the size of the cinnabon roll.

## Output Format
Output $$$t$$$ integers. The $$$i$$$-th of them should be equal to the total length of the chocolate layer in the $$$i$$$-th test case.

## Examples
```input
4
4
5
6
179179179
```
```output
26
37
50
32105178545472401
```

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 permutation is a sequence $$$n$$$ integers, where each integer from $$$1$$$ to $$$n$$$ appears 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.

Given a permutation $$$a$$$, we construct an array $$$b$$$, where $$$b_i = (a_1 + a_2 +~\dots~+ a_i) \bmod n$$$.

A permutation of numbers $$$[a_1, a_2, \dots, a_n]$$$ is called a super-permutation if $$$[b_1 + 1, b_2 + 1, \dots, b_n + 1]$$$ is also a permutation of length $$$n$$$.

Grisha became interested whether a super-permutation of length $$$n$$$ exists. Help him solve this non-trivial problem. Output any super-permutation of length $$$n$$$, if it exists. Otherwise, output $$$-1$$$.

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

Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the desired permutation.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output in a separate line:

- $$$n$$$ integers — a super-permutation of length $$$n$$$, if it exists.
- $$$-1$$$, otherwise.

If there are several suitable permutations, output any of them.

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

Now solve the problem and return the code.