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
You are given an array $$$a$$$ of size $$$n$$$. Each element in this array is an integer between $$$1$$$ and $$$10^9$$$.

You can perform several operations to this array. During an operation, you can replace an element in the array with any integer between $$$1$$$ and $$$10^9$$$.

Output the minimum number of operations needed such that the resulting array doesn't contain any local maximums, and the resulting array after the operations.

An element $$$a_i$$$ is a local maximum if it is strictly larger than both of its neighbors (that is, $$$a_i > a_{i - 1}$$$ and $$$a_i > a_{i + 1}$$$). Since $$$a_1$$$ and $$$a_n$$$ have only one neighbor each, they will never be a local maximum.

## Input Format
Each test contains multiple test cases. The first line will contain a single integer $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ — the size 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 10^9)$$$, the elements of 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, first output a line containing a single integer $$$m$$$ — minimum number of operations required. Then ouput a line consist of $$$n$$$ integers — the resulting array after the operations. Note that this array should differ in exactly $$$m$$$ elements from the initial array.

If there are multiple answers, print any.

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

## Note
In the first example, the array contains no local maximum, so we don't need to perform operations.

In the second example, we can change $$$a_2$$$ to $$$3$$$, then the array don't have local maximums.

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 an array $$$a$$$ of $$$n$$$ elements.

Your can perform the following operation no more than $$$n$$$ times: Select three indices $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$ and replace $$$a_x$$$ with $$$a_y - a_z$$$. After the operation, $$$|a_x|$$$ need to be less than $$$10^{18}$$$.

Your goal is to make the resulting array non-decreasing. If there are multiple solutions, you can output any. If it is impossible to achieve, you should report it as well.

## Input Format
Each test contains multiple test cases. The first line will contain a single integer $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots ,a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$, the elements of $$$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, print $$$-1$$$ in a single line if there is no solution. Otherwise in the first line you should print a single integer $$$m$$$ $$$(0 \leq m \leq n)$$$ — number of operations you performed.

Then the $$$i$$$-th of the following $$$m$$$ lines should contain three integers $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$— description of the $$$i$$$-th operation.

If there are multiple solutions, you can output any. Note that you don't have to minimize the number of operations in this task.

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

## Note
In the first example, the array becomes

$$$[-6,-4,2,-1,2]$$$ after the first operation,

$$$[-6,-4,-3,-1,2]$$$ after the second operation.

In the second example, it is impossible to make the array sorted after any sequence of operations.

In the third example, the array is already sorted, so we don't need to perform any operations.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ distinct positive integers.

Let's consider an infinite integer set $$$S$$$ which contains all integers $$$x$$$ that satisfy at least one of the following conditions:

1. $$$x = a_i$$$ for some $$$1 \leq i \leq n$$$.
2. $$$x = 2y + 1$$$ and $$$y$$$ is in $$$S$$$.
3. $$$x = 4y$$$ and $$$y$$$ is in $$$S$$$.

For example, if $$$a = [1,2]$$$ then the $$$10$$$ smallest elements in $$$S$$$ will be $$$\{1,2,3,4,5,7,8,9,11,12\}$$$.

Find the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$p$$$ $$$(1 \leq n, p \leq 2 \cdot 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.

It is guaranteed that all the numbers in $$$a$$$ are distinct.

## Output Format
Print a single integer, the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Remember to print it modulo $$$10^9 + 7$$$.

## Examples
```input
2 4
6 1
```
```output
9
```
-----
```input
4 7
20 39 5 200
```
```output
14
```
-----
```input
2 200000
48763 1000000000
```
```output
448201910
```

## Note
In the first example, the elements smaller than $$$2^4$$$ are $$$\{1, 3, 4, 6, 7, 9, 12, 13, 15\}$$$.

In the second example, the elements smaller than $$$2^7$$$ are $$$\{5,11,20,23,39,41,44,47,79,80,83,89,92,95\}$$$.

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
There's a chip in the point $$$(0, 0)$$$ of the coordinate plane. In one operation, you can move the chip from some point $$$(x_1, y_1)$$$ to some point $$$(x_2, y_2)$$$ if the Euclidean distance between these two points is an integer (i.e. $$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$$ is integer).

Your task is to determine the minimum number of operations required to move the chip from the point $$$(0, 0)$$$ to the point $$$(x, y)$$$.

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

The single line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 50$$$) — the coordinates of the destination point.

## Output Format
For each test case, print one integer — the minimum number of operations required to move the chip from the point $$$(0, 0)$$$ to the point $$$(x, y)$$$.

## Examples
```input
3
8 6
0 0
9 15
```
```output
1
0
2
```

## Note
In the first example, one operation $$$(0, 0) \rightarrow (8, 6)$$$ is enough. $$$\sqrt{(0-8)^2+(0-6)^2}=\sqrt{64+36}=\sqrt{100}=10$$$ is an integer.

In the second example, the chip is already at the destination point.

In the third example, the chip can be moved as follows: $$$(0, 0) \rightarrow (5, 12) \rightarrow (9, 15)$$$. $$$\sqrt{(0-5)^2+(0-12)^2}=\sqrt{25+144}=\sqrt{169}=13$$$ and $$$\sqrt{(5-9)^2+(12-15)^2}=\sqrt{16+9}=\sqrt{25}=5$$$ are integers.

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 four integers $$$n$$$, $$$B$$$, $$$x$$$ and $$$y$$$. You should build a sequence $$$a_0, a_1, a_2, \dots, a_n$$$ where $$$a_0 = 0$$$ and for each $$$i \ge 1$$$ you can choose:

- either $$$a_i = a_{i - 1} + x$$$
- or $$$a_i = a_{i - 1} - y$$$.

Your goal is to build such a sequence $$$a$$$ that $$$a_i \le B$$$ for all $$$i$$$ and $$$\sum\limits_{i=0}^{n}{a_i}$$$ is maximum possible.

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

The first and only line of each test case contains four integers $$$n$$$, $$$B$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le B, x, y \le 10^9$$$).

It's guaranteed that the total sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the maximum possible $$$\sum\limits_{i=0}^{n}{a_i}$$$.

## Examples
```input
3
5 100 1 30
7 1000000000 1000000000 1000000000
4 1 7 3
```
```output
15
4000000000
-10
```

## Note
In the first test case, the optimal sequence $$$a$$$ is $$$[0, 1, 2, 3, 4, 5]$$$.

In the second test case, the optimal sequence $$$a$$$ is $$$[0, 10^9, 0, 10^9, 0, 10^9, 0, 10^9]$$$.

In the third test case, the optimal sequence $$$a$$$ is $$$[0, -3, -6, 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
You are given a bracket sequence consisting of $$$n$$$ characters '(' and/or )'. You perform several operations with it.

During one operation, you choose the shortest prefix of this string (some amount of first characters of the string) that is good and remove it from the string.

The prefix is considered good if one of the following two conditions is satisfied:

- this prefix is a regular bracket sequence;
- this prefix is a palindrome of length at least two.

A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not.

The bracket sequence is called palindrome if it reads the same back and forth. For example, the bracket sequences )), (( and )(() are palindromes, while bracket sequences (), )( and ))( are not palindromes.

You stop performing the operations when it's not possible to find a good prefix. Your task is to find the number of operations you will perform on the given string and the number of remaining characters in the string.

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of the bracket sequence.

The second line of the test case contains $$$n$$$ characters '(' and/or ')' — the bracket sequence itself.

It is guaranteed that the sum of $$$n$$$ over all test cases do not exceed $$$5 \cdot 10^5$$$ ($$$\sum n \le 5 \cdot 10^5$$$).

## Output Format
For each test case, print two integers $$$c$$$ and $$$r$$$ — the number of operations you will perform on the given bracket sequence and the number of characters that remain in the string after performing all operations.

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

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

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

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

Execution time limit: 6.0 seconds
Memory limit: 512.0 MB

# Problem
In this problem, we will consider complete undirected graphs consisting of $$$n$$$ vertices with weighted edges. The weight of each edge is an integer from $$$1$$$ to $$$k$$$.

An undirected graph is considered beautiful if the sum of weights of all edges incident to vertex $$$1$$$ is equal to the weight of MST in the graph. MST is the minimum spanning tree — a tree consisting of $$$n-1$$$ edges of the graph, which connects all $$$n$$$ vertices and has the minimum sum of weights among all such trees; the weight of MST is the sum of weights of all edges in it.

Calculate the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 250$$$; $$$1 \le k \le 250$$$).

## Output Format
Print one integer — the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

## Examples
```input
3 2
```
```output
5
```
-----
```input
4 4
```
```output
571
```
-----
```input
6 9
```
```output
310640163
```
-----
```input
42 13
```
```output
136246935
```

Now solve the problem and return the code.