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

# Problem
There are $$$n$$$ people on the number line; the $$$i$$$-th person is at point $$$a_i$$$ and wants to go to point $$$b_i$$$. For each person, $$$a_i < b_i$$$, and the starting and ending points of all people are distinct. (That is, all of the $$$2n$$$ numbers $$$a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$$$ are distinct.)

All the people will start moving simultaneously at a speed of $$$1$$$ unit per second until they reach their final point $$$b_i$$$. When two people meet at the same point, they will greet each other once. How many greetings will there be?

Note that a person can still greet other people even if they have reached their final point.

## Input Format
The first line of the input 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$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of people.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$-10^9 \leq a_i < b_i \leq 10^9$$$) — the starting and ending positions of each person.

For each test case, all of the $$$2n$$$ numbers $$$a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$$$ are distinct.

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

## Output Format
For each test case, output a single integer denoting the number of greetings that will happen.

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

## Note
In the first test case, the two people will meet at point $$$3$$$ and greet each other.

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
Alex is solving a problem. He has $$$n$$$ constraints on what the integer $$$k$$$ can be. There are three types of constraints:

1. $$$k$$$ must be greater than or equal to some integer $$$x$$$;
2. $$$k$$$ must be less than or equal to some integer $$$x$$$;
3. $$$k$$$ must be not equal to some integer $$$x$$$.

Help Alex find the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints. It is guaranteed that the answer is finite (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). Also, it is guaranteed that no two constraints are the exact same.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of constraints.

The following $$$n$$$ lines describe the constraints. Each line contains two integers $$$a$$$ and $$$x$$$ ($$$a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$$$). $$$a$$$ denotes the type of constraint. If $$$a=1$$$, $$$k$$$ must be greater than or equal to $$$x$$$. If $$$a=2$$$, $$$k$$$ must be less than or equal to $$$x$$$. If $$$a=3$$$, $$$k$$$ must be not equal to $$$x$$$.

It is guaranteed that there is a finite amount of integers satisfying all $$$n$$$ constraints (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). It is also guaranteed that no two constraints are the exact same (in other words, all pairs $$$(a, x)$$$ are distinct).

## Output Format
For each test case, output a single integer — the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints.

## Examples
```input
6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
1 3
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001
```
```output
7
0
90
0
0
800000000
```

## Note
In the first test case, $$$k \geq 3$$$ and $$$k \leq 10$$$. Furthermore, $$$k \neq 1$$$ and $$$k \neq 5$$$. The possible integers $$$k$$$ that satisfy the constraints are $$$3,4,6,7,8,9,10$$$. So the answer is $$$7$$$.

In the second test case, $$$k \ge 5$$$ and $$$k \le 4$$$, which is impossible. 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
Alice and Bob are playing a game. They have an array $$$a_1, a_2,\ldots,a_n$$$. The game consists of two steps:

- First, Alice will remove at most $$$k$$$ elements from the array.
- Second, Bob will multiply at most $$$x$$$ elements of the array by $$$-1$$$.

Alice wants to maximize the sum of elements of the array while Bob wants to minimize it. Find the sum of elements of the array after the game if both players play optimally.

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

The first line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x,k \leq n$$$) — the number of elements in the array, the limit on the number of elements of the array that Alice can remove, and the limit on the number of elements of the array that Bob can multiply $$$-1$$$ to.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — the elements of the array.

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 a single integer — the sum of elements of the array after the game if both players play optimally.

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

## Note
In the first test case, it is optimal for Alice to remove the only element of the array. Then, the sum of elements of the array is $$$0$$$ after the game is over.

In the second test case, it is optimal for Alice to not remove any elements. Bob will then multiply $$$4$$$ by $$$-1$$$. So the final sum of elements of the array is $$$3+1+2-4=2$$$.

In the fifth test case, it is optimal for Alice to remove $$$9, 9$$$. Bob will then multiply $$$5, 5, 3$$$ by $$$-1$$$. So the final sum of elements of the array is $$$-5-5-3+3+3+2=-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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Allen has an array $$$a_1, a_2,\ldots,a_n$$$. For every positive integer $$$k$$$ that is a divisor of $$$n$$$, Allen does the following:

- He partitions the array into $$$\frac{n}{k}$$$ disjoint subarrays of length $$$k$$$. In other words, he partitions the array into the following subarrays: $$$$$$[a_1,a_2,\ldots,a_k],[a_{k+1}, a_{k+2},\ldots,a_{2k}],\ldots,[a_{n-k+1},a_{n-k+2},\ldots,a_{n}]$$$$$$
- Allen earns one point if there exists some positive integer $$$m$$$ ($$$m \geq 2$$$) such that if he replaces every element in the array with its remainder when divided by $$$m$$$, then all subarrays will be identical.

Help Allen find the number of points he will earn.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array $$$a$$$.

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 a single integer — the number of points Allen will earn.

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

## Note
In the first test case, $$$k=2$$$ earns a point since Allen can pick $$$m = 2$$$ and both subarrays will be equal to $$$[1, 0]$$$. $$$k=4$$$ also earns a point, since no matter what $$$m$$$ Allen chooses, there will be only one subarray and thus all subarrays are equal.

In the second test case, Allen earns $$$1$$$ point for $$$k=3$$$, where his choice for $$$m$$$ does not matter.

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

# Problem
Patrick calls a substring$$$^\dagger$$$ of a binary string$$$^\ddagger$$$ good if this substring contains exactly one 1.

Help Patrick count the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Note that substrings are differentiated by their location in the string, so if $$$s =$$$ 1010 you should count both occurrences of 10.

$$$^\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$$$^\ddagger$$$ A binary string is a string that only contains the characters 0 and 1.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2500$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2500$$$, $$$1 \leq k \leq n$$$) — the number of required good substrings and the maximum allowed length of a good substring.

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

## Output Format
For each test case, output a single integer — the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Since this integer can be too large, output it modulo $$$998\,244\,353$$$.

## Examples
```input
6
1 1
3 2
4 2
5 4
6 2
2450 2391
```
```output
1
3
5
12
9
259280854
```

## Note
In the first test case, the only suitable binary string is 1. String 01 is not suitable because it contains a substring 01 with length $$$2 > 1$$$.

In the second test case, suitable binary strings are 011, 110 and 111.

In the third test case, suitable binary strings are 101, 0110, 0111, 1110, and 1111.

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 sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

You are given three integers $$$n$$$, $$$m$$$ and $$$k$$$. Find the number of sequences consisting of $$$n$$$ '(' and $$$m$$$ ')', such that the longest balanced subsequence is of length $$$2 \cdot k$$$. Since the answer can be large calculate it modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3 \cdot 10^3$$$). Description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^3$$$)

## Output Format
For each test case, print one integer — the answer to the problem.

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

## Note
For the first test case "()()", "(())" are the $$$2$$$ sequences

For the second test case no sequence is possible.

For the third test case ")((()", ")(()(", ")()((", "())((" are the $$$4$$$ sequences.

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
There is a rectangular sheet of paper with initial height $$$n$$$ and width $$$m$$$. Let the current height and width be $$$h$$$ and $$$w$$$ respectively. We introduce a $$$xy$$$-coordinate system so that the four corners of the sheet are $$$(0, 0), (w, 0), (0, h)$$$, and $$$(w, h)$$$. The sheet can then be cut along the lines $$$x = 1,2,\ldots,w-1$$$ and the lines $$$y = 1,2,\ldots,h-1$$$. In each step, the paper is cut randomly along any one of these $$$h+w-2$$$ lines. After each vertical and horizontal cut, the right and bottom piece of paper respectively are discarded.

Find the expected number of steps required to make the area of the sheet of paper strictly less than $$$k$$$. It can be shown that this answer can always be expressed as a fraction $$$\dfrac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers. Calculate $$$p\cdot q^{-1} \bmod (10^9+7)$$$.

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

The first line of each test case contains 3 integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 10^6$$$, $$$2 \le k \le 10^{12}$$$).

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

## Output Format
For each test case, print one integer — the answer to the problem.

## Examples
```input
4
2 4 10
2 4 8
2 4 2
2 4 6
```
```output
0
1
833333342
250000003
```

## Note
For the first test case, the area is already less than $$$10$$$ so no cuts are required.

For the second test case, the area is exactly $$$8$$$ so any one of the $$$4$$$ possible cuts would make the area strictly less than $$$8$$$.

For the third test case, the final answer is $$$\frac{17}{6} = 833\,333\,342\bmod (10^9+7)$$$.

For the fourth test case, the final answer is $$$\frac{5}{4} = 250\,000\,003\bmod (10^9+7)$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call an array $$$a$$$ sorted if $$$a_1 \leq a_2 \leq \ldots \leq a_{n - 1} \leq a_{n}$$$.

You are given two of Farmer John's favorite integers, $$$n$$$ and $$$k$$$. He challenges you to find any array $$$a_1, a_2, \ldots, a_{n}$$$ satisfying the following requirements:

- $$$1 \leq a_i \leq 10^9$$$ for each $$$1 \leq i \leq n$$$;
- Out of the $$$n$$$ total cyclic shifts of $$$a$$$, exactly $$$k$$$ of them are sorted.$$$^\dagger$$$

If there is no such array $$$a$$$, output $$$-1$$$.

$$$^\dagger$$$The $$$x$$$-th ($$$1 \leq x \leq n$$$) cyclic shift of the array $$$a$$$ is $$$a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}$$$. If $$$c_{x, i}$$$ denotes the $$$i$$$'th element of the $$$x$$$'th cyclic shift of $$$a$$$, exactly $$$k$$$ such $$$x$$$ should satisfy $$$c_{x,1} \leq c_{x,2} \leq \ldots \leq c_{x, n - 1} \leq c_{x, n}$$$.

For example, the cyclic shifts for $$$a = [1, 2, 3, 3]$$$ are the following:

- $$$x = 1$$$: $$$[1, 2, 3, 3]$$$ (sorted);
- $$$x = 2$$$: $$$[2, 3, 3, 1]$$$ (not sorted);
- $$$x = 3$$$: $$$[3, 3, 1, 2]$$$ (not sorted);
- $$$x = 4$$$: $$$[3, 1, 2, 3]$$$ (not sorted).

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

Each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^3$$$) — the length of $$$a$$$ and the number of sorted cyclic shifts $$$a$$$ must have.

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

## Output Format
For each test case, print a single line:

- if there is a valid array $$$a$$$, output $$$n$$$ integers, representing $$$a_1, a_2, \ldots, a_{n}$$$;
- otherwise, output $$$-1$$$.

If there are multiple solutions, print any of them.

## Examples
```input
3
2 2
3 1
3 2
```
```output
1 1
69420 69 420
-1
```

## Note
In the first testcase, $$$a = [1, 1]$$$ satisfies $$$n = 2, k = 2$$$:

The two cyclic shifts of $$$a$$$ are $$$[a_1, a_2]$$$ and $$$[a_2, a_1]$$$, which are both $$$[1, 1]$$$ and are sorted.

In the second testcase, $$$a = [69\,420, 69, 420]$$$ satisfies $$$n = 3, k = 1$$$:

The three cyclic shifts of $$$a$$$ are $$$[a_1, a_2, a_3]$$$, $$$[a_2, a_3, a_1]$$$, $$$[a_3, a_1, a_2]$$$, which are $$$[69\,420, 69, 420]$$$, $$$[69, 420, 69\,420]$$$, and $$$[420, 69\,420, 69]$$$, respectively.

Only $$$[69, 420, 69\,420]$$$ is sorted.

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

# Problem
Farmer John has a permutation $$$p_1, p_2, \ldots, p_n$$$, where every integer from $$$0$$$ to $$$n-1$$$ occurs exactly once. He gives Bessie an array $$$a$$$ of length $$$n$$$ and challenges her to construct $$$p$$$ based on $$$a$$$.

The array $$$a$$$ is constructed so that $$$a_i$$$ = $$$\texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i$$$, where the $$$\texttt{MEX}$$$ of an array is the minimum non-negative integer that does not appear in that array. For example, $$$\texttt{MEX}(1, 2, 3) = 0$$$ and $$$\texttt{MEX}(3, 1, 0) = 2$$$.

Help Bessie construct any valid permutation $$$p$$$ that satisfies $$$a$$$. The input is given in such a way that at least one valid $$$p$$$ exists. If there are multiple possible $$$p$$$, it is enough to print one of them.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the lengths of $$$p$$$ and $$$a$$$.

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

It is guaranteed that there is at least one valid $$$p$$$ for the given data.

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 $$$n$$$ integers on a new line, the elements of $$$p$$$.

If there are multiple solutions, print any of them.

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

## Note
In the first case, $$$p = [0, 1, 4, 2, 3]$$$ is one possible output.

$$$a$$$ will then be calculated as $$$a_1 = \texttt{MEX}(0) - 0 = 1$$$, $$$a_2 = \texttt{MEX}(0, 1) - 1 = 1$$$, $$$a_3 = \texttt{MEX}(0, 1, 4) - 4 = -2$$$, $$$a_4 = \texttt{MEX}(0, 1, 4, 2) - 2 = 1$$$, $$$a_5 = \texttt{MEX}(0, 1, 4, 2, 3) - 3 = 2$$$.

So, as required, $$$a$$$ will be $$$[1, 1, -2, 1, 2]$$$.

Now solve the problem and return the code.