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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

Let's call an array $$$a$$$ of odd length $$$2m+1$$$ (with $$$m \ge 1$$$) bad, if element $$$a_{m+1}$$$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $$$m+1$$$-st position remains the same.

Let's call a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$ anti-median, if every its subarray of odd length $$$\ge 3$$$ is not bad.

You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $$$10^9+7$$$.

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

The first line of each test case contains a single integer $$$n$$$ $$$(2 \le n \le 10^6)$$$  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, or $$$p_i = -1$$$)  — the elements of the permutation. If $$$p_i \neq -1$$$, it's given, else it's unknown. It's guaranteed that if for some $$$i \neq j$$$ holds $$$p_i \neq -1, p_j \neq -1$$$, then $$$p_i \neq p_j$$$.

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

## Output Format
For each test case, output a single integer  — the number of ways to set unknown values to obtain an anti-median permutation, modulo $$$10^9+7$$$.

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

## Note
In the first test case, both $$$[1, 2]$$$ and $$$[2, 1]$$$ are anti-median.

In the second test case, permutations $$$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$$ are anti-median. The remaining two permutations, $$$[1, 2, 3]$$$, $$$[3, 2, 1]$$$, are bad arrays on their own, as their median, $$$2$$$, is in their middle.

In the third test case, $$$[1, 2, 3, 4]$$$ isn't anti-median, as it contains bad subarray $$$[1, 2, 3]$$$.

In the fourth test case, the only anti-median array you can get is $$$[5, 6, 3, 4, 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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
MKnez wants to construct an array $$$s_1,s_2, \ldots , s_n$$$ satisfying the following conditions:

- Each element is an integer number different from $$$0$$$;
- For each pair of adjacent elements their sum is equal to the sum of the whole array.

More formally, $$$s_i \neq 0$$$ must hold for each $$$1 \leq i \leq n$$$. Moreover, it must hold that $$$s_1 + s_2 + \cdots + s_n = s_i + s_{i+1}$$$ for each $$$1 \leq i < n$$$.

Help MKnez to construct an array with these properties or determine that it does not exist.

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

The only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 1000$$$) — the length of the array.

## Output Format
For each test case, print "YES" if an array of length $$$n$$$ satisfying the conditions exists. Otherwise, print "NO". If the answer is "YES", on the next line print a sequence $$$s_1,s_2, \ldots, s_n$$$ satisfying the conditions. Each element should be a non-zero integer in the range $$$[-5000,5000]$$$, i. e. $$$-5000 \leq s_i \leq 5000$$$ and $$$s_i \neq 0$$$ should hold for each $$$1 \leq i \leq n$$$.

It can be proved that if a solution exists then there also exists one which satisfies the additional constraints on the range.

If there are several correct answers, print any of them.

## Examples
```input
2
2
3
```
```output
YES
9 5
NO
```

## Note
In the first test case, $$$[9,5]$$$ is a valid answer since $$$9+5$$$ (the sum of the two adjacent elements $$$s_1+s_2$$$) is equal to $$$9+5$$$ (the sum of all elements). Other solutions include $$$[6,-9], [-1,-2], [-5000,5000], \ldots$$$

For the second test case, let us show why some arrays do not satisfy the constraints:

- $$$[1,1,1]$$$  — $$$s_1+s_2 = 1+1 = 2$$$ and $$$s_1+s_2+s_3=1+1+1 = 3$$$ differ;
- $$$[1,-1,1]$$$  — $$$s_1+s_2=1+(-1)=0$$$ and $$$s_1+s_2+s_3=1+(-1)+1 = 1$$$ differ;
- $$$[0,0,0]$$$  — The array $$$s$$$ cannot contain a $$$0$$$.

This is not a proof, but it can be shown that the answer is "NO".

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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
On March 14, the day of the number $$$\pi$$$ is celebrated all over the world. This is a very important mathematical constant equal to the ratio of the circumference of a circle to its diameter.

Polycarp was told at school that the number $$$\pi$$$ is irrational, therefore it has an infinite number of digits in decimal notation. He wanted to prepare for the Day of the number $$$\pi$$$ by memorizing this number as accurately as possible.

Polycarp wrote out all the digits that he managed to remember. For example, if Polycarp remembered $$$\pi$$$ as $$$3.1415$$$, he wrote out 31415.

Polycarp was in a hurry and could have made a mistake, so you decided to check how many first digits of the number $$$\pi$$$ Polycarp actually remembers correctly.

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

Each test case is described by a single string of digits $$$n$$$, which was written out by Polycarp.

The string $$$n$$$ contains up to $$$30$$$ digits.

## Output Format
Output $$$t$$$ integers, each of which is the answer to the corresponding test case, that is how many first digits of the number $$$\pi$$$ Polycarp remembers correctly.

## Examples
```input
9
000
3
4141592653
141592653589793238462643383279
31420
31415
314159265358
27182
314159265358979323846264338327
```
```output
0
1
0
0
3
5
12
0
30
```

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

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Taisia has $$$n$$$ six-sided dice. Each face of the die is marked with a number from $$$1$$$ to $$$6$$$, each number from $$$1$$$ to $$$6$$$ is used once.

Taisia rolls all $$$n$$$ dice at the same time and gets a sequence of values $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 6$$$), where $$$a_i$$$ is the value on the upper face of the $$$i$$$-th dice. The sum of this sequence is equal to $$$s$$$.

Suddenly, Taisia's pet cat steals exactly one dice with maximum value $$$a_i$$$ and calculates the sum of the values on the remaining $$$n-1$$$ dice, which is equal to $$$r$$$.

You only know the number of dice $$$n$$$ and the values of $$$s$$$, $$$r$$$. Restore a possible sequence $$$a$$$ that fulfills the constraints.

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

Each testcase is given on a separate line and contains three integers $$$n$$$, $$$s$$$, $$$r$$$ ($$$2 \le n \le 50$$$, $$$1 \le r < s \le 300$$$).

It is guaranteed that a solution exists.

## Output Format
For each testcase, print: $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ in any order. It is guaranteed that such sequence exists.

If there are multiple solutions, print any.

## Examples
```input
7
2 2 1
2 4 2
4 9 5
5 17 11
3 15 10
4 4 3
5 20 15
```
```output
1 1
2 2 
1 2 2 4
6 4 2 3 2
5 5 5
1 1 1 1
1 4 5 5 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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vlad found two positive numbers $$$a$$$ and $$$b$$$ ($$$a,b>0$$$). He discovered that $$$a \oplus b = \frac{a + b}{2}$$$, where $$$\oplus$$$ means the bitwise exclusive OR , and division is performed without rounding..

Since it is easier to remember one number than two, Vlad remembered only $$$a\oplus b$$$, let's denote this number as $$$x$$$. Help him find any suitable $$$a$$$ and $$$b$$$ or tell him that they do not exist.

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

Each test case is described by a single integer $$$x$$$ ($$$1 \le x \le 2^{29}$$$) — the number that Vlad remembered.

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As the answer, output $$$a$$$ and $$$b$$$ ($$$0 < a,b \le 2^{32}$$$), such that $$$x = a \oplus b = \frac{a + b}{2}$$$. If there are several answers, output any of them. If there are no matching pairs, output -1.

## Examples
```input
6
2
5
10
6
18
36
```
```output
3 1
-1
13 7
-1
25 11
50 22
```

Now solve the problem and return the code.