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

# Problem
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$y$$$. In this version $$$y = 0$$$. You can make hacks only if both versions are solved.

Bessie has received a birthday cake from her best friend Elsie, and it came in the form of a regular polygon with $$$n$$$ sides. The vertices of the cake are numbered from $$$1$$$ to $$$n$$$ clockwise. You and Bessie are going to choose some of those vertices to cut non-intersecting diagonals into the cake. In other words, the endpoints of the diagonals must be part of the chosen vertices.

Bessie would only like to give out pieces of cake which result in a triangle to keep consistency. The size of the pieces doesn't matter, and the whole cake does not have to be separated into all triangles (other shapes are allowed in the cake, but those will not be counted).

Bessie has already chosen $$$x$$$ of those vertices that can be used to form diagonals. She wants you to choose no more than $$$y$$$ other vertices such that the number of triangular pieces of cake she can give out is maximized.

What is the maximum number of triangular pieces of cake Bessie can give out?

## 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 consists of three integers, $$$n$$$, $$$x$$$, and $$$y$$$ ($$$4 \leq n \leq 10^9$$$, $$$2 \leq x \leq \min(n, 2 \cdot 10^5)$$$, $$$y = 0$$$) — the number of sides of the polygon, number of vertices Bessie has chosen, and the maximum number of other vertices you can choose.

The second line consists of $$$x$$$ distinct integers from $$$1$$$ to $$$n$$$, representing the vertices Bessie has chosen.

It is guaranteed the sum of $$$x$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer: the maximum number of non-intersecting triangular pieces of cake she can give out.

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

## Note
In test cases $$$1$$$, $$$2$$$ and $$$3$$$, you can get $$$2$$$, $$$6$$$ and $$$2$$$ non-intersecting triangular pieces of cake, respectively. A possible construction is shown in the following pictures:

The green dots represent vertices that can be used, the blue lines represent diagonals that are drawn, and the red numbers represent triangles that are counted.

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
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$y$$$. In this version $$$0 \leq y \leq n - x$$$. You can make hacks only if both versions are solved.

Bessie has received a birthday cake from her best friend Elsie, and it came in the form of a regular polygon with $$$n$$$ sides. The vertices of the cake are numbered from $$$1$$$ to $$$n$$$ clockwise. You and Bessie are going to choose some of those vertices to cut non-intersecting diagonals into the cake. In other words, the endpoints of the diagonals must be part of the chosen vertices.

Bessie would only like to give out pieces of cake which result in a triangle to keep consistency. The size of the pieces doesn't matter, and the whole cake does not have to be separated into all triangles (other shapes are allowed in the cake, but those will not be counted).

Bessie has already chosen $$$x$$$ of those vertices that can be used to form diagonals. She wants you to choose no more than $$$y$$$ other vertices such that the number of triangular pieces of cake she can give out is maximized.

What is the maximum number of triangular pieces of cake Bessie can give out?

## 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 consists of three integers, $$$n$$$, $$$x$$$, and $$$y$$$ ($$$4 \leq n \leq 10^9$$$, $$$2 \leq x \leq \min(n, 2 \cdot 10^5)$$$, $$$0 \leq y \leq n - x$$$) — the number of sides of the polygon, number of vertices Bessie has chosen, and the maximum number of other vertices you can choose.

The second line consists of $$$x$$$ distinct integers from $$$1$$$ to $$$n$$$, representing the vertices Bessie has chosen.

It is guaranteed the sum of $$$x$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer: the maximum number of non-intersecting triangular pieces of cake she can give out.

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

## Note
In test cases $$$1$$$, $$$2$$$ and $$$3$$$, you can get $$$6$$$, $$$5$$$ and $$$2$$$ non-intersecting triangular pieces of cake, respectively. A possible construction is shown in the following pictures:

The green dots represent vertices that Bessie chose, the yellow dots represent vertices that you chose, the blue lines represent diagonals that are drawn, and the red numbers represent triangles that are counted.

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

# Problem
Elsie is learning how to paint. She has a canvas of $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$ and can paint any (potentially empty) subset of cells.

Elsie has a 2D array $$$a$$$ which she will use to evaluate paintings. Let the maximal contiguous intervals of painted cells in a painting be $$$[l_1,r_1],[l_2,r_2],\ldots,[l_x,r_x]$$$. The beauty of the painting is the sum of $$$a_{l_i,r_i}$$$ over all $$$1 \le i \le x$$$. In the image above, the maximal contiguous intervals of painted cells are $$$[2,4],[6,6],[8,9]$$$ and the beauty of the painting is $$$a_{2,4}+a_{6,6}+a_{8,9}$$$.

There are $$$2^n$$$ ways to paint the strip. Help Elsie find the $$$k$$$ largest possible values of the beauty of a painting she can obtain, among all these ways. Note that these $$$k$$$ values do not necessarily have to be distinct. It is guaranteed that there are at least $$$k$$$ different ways to paint the canvas.

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

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^3$$$, $$$1 \leq k \leq \min(2^n, 5 \cdot 10^3)$$$) — the number of cells and the number of largest values of the beauty of a painting you must find.

The next $$$n$$$ lines of each test case describe $$$a$$$ where the $$$i$$$-th of which contains $$$n-i+1$$$ integers $$$a_{i,i},a_{i,i+1},\ldots,a_{i,n}$$$ ($$$-10^6 \leq a_{i,j} \leq 10^6$$$).

It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$ and the sum of $$$k$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.

## Output Format
For each test case, output $$$k$$$ integers in one line: the $$$i$$$-th of them must represent the $$$i$$$-th largest value of the beauty of a painting Elsie can obtain.

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

## Note
In the first test case, Elsie can either paint the only cell or not paint it. If she paints the only cell, the beauty of the painting is $$$-5$$$. If she chooses not to paint it, the beauty of the painting is $$$0$$$. Thus, the largest beauty she can obtain is $$$0$$$ and the second largest beauty she can obtain is $$$-5$$$.

Below is an illustration of the third test case.

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
Fox loves permutations! She came up with the following problem and asked Cat to solve it:

You are given an even positive integer $$$n$$$ and a permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$.

The score of another permutation $$$q$$$ of length $$$n$$$ is the number of local maximums in the array $$$a$$$ of length $$$n$$$, where $$$a_i = p_i + q_i$$$ for all $$$i$$$ ($$$1 \le i \le n$$$). In other words, the score of $$$q$$$ is the number of $$$i$$$ such that $$$1 < i < n$$$ (note the strict inequalities), $$$a_{i-1} < a_i$$$, and $$$a_i > a_{i+1}$$$ (once again, note the strict inequalities).

Find the permutation $$$q$$$ that achieves the maximum score for given $$$n$$$ and $$$p$$$. If there exist multiple such permutations, you can pick any of them.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

## Input Format
The first line of input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases in the input you will have to solve.

The first line of each test case contains one even integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$, $$$n$$$ is even) — the length of the permutation $$$p$$$.

The second line of each test case contains the $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). It is guaranteed that $$$p$$$ is a permutation of length $$$n$$$.

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

## Output Format
For each test case, output one line containing any permutation of length $$$n$$$ (the array $$$q$$$), such that $$$q$$$ maximizes the score under the given constraints.

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

## Note
In the first example, $$$a = [3, 6, 4, 7]$$$. The array has just one local maximum (on the second position), so the score of the chosen permutation $$$q$$$ is $$$1$$$. It can be proven that this score is optimal under the constraints.

In the last example, the resulting array $$$a = [6, 6, 12, 7, 14, 7, 14, 6]$$$ has $$$3$$$ local maximums — on the third, fifth and seventh positions.

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
You are given two integer arrays: array $$$a$$$ of length $$$n$$$ and array $$$b$$$ of length $$$n+1$$$.

You can perform the following operations any number of times in any order:

- choose any element of the array $$$a$$$ and increase it by $$$1$$$;
- choose any element of the array $$$a$$$ and decrease it by $$$1$$$;
- choose any element of the array $$$a$$$, copy it and append the copy to the end of the array $$$a$$$.

Your task is to calculate the minimum number of aforementioned operations (possibly zero) required to transform the array $$$a$$$ into the array $$$b$$$. It can be shown that under the constraints of the problem, it is always possible.

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

Each test case consists of three lines:

- the first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$);
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);
- the third line contains $$$n + 1$$$ integers $$$b_1, b_2, \dots, b_{n + 1}$$$ ($$$1 \le b_i \le 10^9$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the minimum number of operations (possibly zero) required to transform the array $$$a$$$ into the array $$$b$$$.

## Examples
```input
3
1
2
1 3
2
3 3
3 3 3
4
4 2 1 2
2 1 5 2 3
```
```output
3
1
8
```

## Note
In the first example, you can transform $$$a$$$ into $$$b$$$ as follows: $$$[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]$$$.

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 regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example:

- bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
- bracket sequences ")(", "(" and ")" are not.

Let's define the inverse of the bracket sequence as follows: replace all brackets '(' with ')', and vice versa (all brackets ')' with '('). For example, strings "()((" and ")())" are inverses of each other.

You are given a regular bracket sequence $$$s$$$. Calculate the number of pairs of integers $$$(l,r)$$$ ($$$1 \le l \le r \le |s|$$$) such that if you replace the substring of $$$s$$$ from the $$$l$$$-th character to the $$$r$$$-th character (inclusive) with its inverse, $$$s$$$ will still be a regular bracket sequence.

## 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 non-empty regular bracket sequence; it consists only of characters '(' and/or ')'.

Additional constraint on the input: the total length of the regular bracket sequences over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of pairs $$$(l,r)$$$ meeting the conditions from the statement.

## Examples
```input
4
(())
()
()()()
(()())(())
```
```output
1
0
3
13
```

## Note
In the first example, there is only one pair:

- $$$(2, 3)$$$: (()) $$$\rightarrow$$$ ()().

In the second example, there are no pairs.

In the third example, there are three pairs:

- $$$(2, 3)$$$: ()()() $$$\rightarrow$$$ (())();
- $$$(4, 5)$$$: ()()() $$$\rightarrow$$$ ()(());
- $$$(2, 5)$$$: ()()() $$$\rightarrow$$$ (()());

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
Initially, we had one array, which was a permutation of size $$$n$$$ (an array of size $$$n$$$ where each integer from $$$1$$$ to $$$n$$$ appears exactly once).

We performed $$$q$$$ operations. During the $$$i$$$-th operation, we did the following:

- choose any array we have with at least $$$2$$$ elements;
- split it into two non-empty arrays (prefix and suffix);
- write two integers $$$l_i$$$ and $$$r_i$$$, where $$$l_i$$$ is the maximum element in the left part which we get after the split, and $$$r_i$$$ is the maximum element in the right part;
- remove the array we've chosen from the pool of arrays we can use, and add the two resulting parts into the pool.

For example, suppose the initial array was $$$[6, 3, 4, 1, 2, 5]$$$, and we performed the following operations:

1. choose the array $$$[6, 3, 4, 1, 2, 5]$$$ and split it into $$$[6, 3]$$$ and $$$[4, 1, 2, 5]$$$. Then we write $$$l_1 = 6$$$ and $$$r_1 = 5$$$, and the arrays we have are $$$[6, 3]$$$ and $$$[4, 1, 2, 5]$$$;
2. choose the array $$$[4, 1, 2, 5]$$$ and split it into $$$[4, 1, 2]$$$ and $$$[5]$$$. Then we write $$$l_2 = 4$$$ and $$$r_2 = 5$$$, and the arrays we have are $$$[6, 3]$$$, $$$[4, 1, 2]$$$ and $$$[5]$$$;
3. choose the array $$$[4, 1, 2]$$$ and split it into $$$[4]$$$ and $$$[1, 2]$$$. Then we write $$$l_3 = 4$$$ and $$$r_3 = 2$$$, and the arrays we have are $$$[6, 3]$$$, $$$[4]$$$, $$$[1, 2]$$$ and $$$[5]$$$.

You are given two integers $$$n$$$ and $$$q$$$, and two sequences $$$[l_1, l_2, \dots, l_q]$$$ and $$$[r_1, r_2, \dots, r_q]$$$. A permutation of size $$$n$$$ is called valid if we can perform $$$q$$$ operations and produce the given sequences $$$[l_1, l_2, \dots, l_q]$$$ and $$$[r_1, r_2, \dots, r_q]$$$.

Calculate the number of valid permutations.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le q < n \le 3 \cdot 10^5$$$).

The second line contains $$$q$$$ integers $$$l_1, l_2, \dots, l_q$$$ ($$$1 \le l_i \le n$$$).

The third line contains $$$q$$$ integers $$$r_1, r_2, \dots, r_q$$$ ($$$1 \le r_i \le n$$$).

Additional constraint on the input: there exists at least one permutation which can produce the given sequences $$$[l_1, l_2, \dots, l_q]$$$ and $$$[r_1, r_2, \dots, r_q]$$$.

## Output Format
Print one integer — the number of valid permutations, taken modulo $$$998244353$$$.

## Examples
```input
6 3
6 4 4
5 5 2
```
```output
30
```
-----
```input
10 1
10
9
```
```output
1814400
```
-----
```input
4 1
2
4
```
```output
8
```

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
Recently, the first-year student Maxim learned about the Collatz conjecture, but he didn't pay much attention during the lecture, so he believes that the following process is mentioned in the conjecture:

There is a variable $$$x$$$ and a constant $$$y$$$. The following operation is performed $$$k$$$ times:

- increase $$$x$$$ by $$$1$$$, then
- while the number $$$x$$$ is divisible by $$$y$$$, divide it by $$$y$$$.

For example, if the number $$$x = 16$$$, $$$y = 3$$$, and $$$k = 2$$$, then after one operation $$$x$$$ becomes $$$17$$$, and after another operation $$$x$$$ becomes $$$2$$$, because after adding one, $$$x = 18$$$ is divisible by $$$3$$$ twice.

Given the initial values of $$$x$$$, $$$y$$$, and $$$k$$$, Maxim wants to know what is the final value of $$$x$$$.

## Input Format
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. Then follows the description of the test cases.

The only line of each test case contains three integers $$$x$$$, $$$y$$$, and $$$k$$$ ($$$1 \le x, k \le 10^{9}$$$, $$$2 \le y \le 10^{9}$$$) — the initial variable, constant and the number of operations.

## Output Format
For each test case, output a single integer — the number obtained after applying $$$k$$$ operations.

## Examples
```input
13
1 3 1
2 3 1
24 5 5
16 3 2
2 2 1
1337 18 1
1 2 144133
12345678 3 10
998244353 2 998244353
998244353 123456789 998244352
998244354 998241111 998244352
998244355 2 9982443
1000000000 1000000000 1000000000
```
```output
2
1
1
2
3
1338
1
16936
1
21180097
6486
1
2
```

## Note
In the first test case, there is only one operation applied to $$$x = 1$$$, resulting in $$$x$$$ becoming $$$2$$$.

In the second test case, for $$$x = 2$$$, within one operation, one is added to $$$x$$$ and it's divided by $$$y = 3$$$, resulting in $$$x$$$ becoming $$$1$$$.

In the third test case, $$$x$$$ changes as follows:

- After the first operation, $$$x = 1$$$, because $$$24 + 1 = 25$$$ and $$$25$$$ is divisible by $$$y = 5$$$ twice within one operation.
- After the second operation, $$$x = 2$$$.
- After the third operation, $$$x = 3$$$.
- After the fourth operation, $$$x = 4$$$.
- After the fifth operation, $$$x = 1$$$.

Now solve the problem and return the code.