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

# Problem
The Alice's computer is broken, so she can't play her favorite card game now. To help Alice, Bob wants to answer $$$n$$$ her questions.

Initially, Bob holds one card with number $$$0$$$ in the left hand and one in the right hand. In the $$$i$$$-th question, Alice asks Bob to replace a card in the left or right hand with a card with number $$$k_i$$$ (Bob chooses which of two cards he changes, Bob must replace exactly one card).

After this action, Alice wants the numbers on the left and right cards to belong to given segments (segments for left and right cards can be different). Formally, let the number on the left card be $$$x$$$, and on the right card be $$$y$$$. Then after the $$$i$$$-th swap the following conditions must be satisfied: $$$a_{l, i} \le x \le b_{l, i}$$$, and $$$a_{r, i} \le y \le b_{r,i}$$$.

Please determine if Bob can answer all requests. If it is possible, find a way to do it.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 100\,000$$$, $$$2 \le m \le 10^9$$$) — the number of questions and the maximum possible value on the card.

Then $$$n$$$ queries are described. Every description contains 3 lines.

The first line of the description of the $$$i$$$-th query contains a single integer $$$k_i$$$ ($$$0 \le k_i \le m$$$) — the number on a new card.

The second line of the description of the $$$i$$$-th query contains two integers $$$a_{l, i}$$$ and $$$b_{l, i}$$$ ($$$0 \le a_{l, i} \le b_{l, i} \le m$$$) — the minimum and maximum values of the card at the left hand after the replacement.

The third line of the description of the $$$i$$$-th query contains two integers $$$a_{r, i}$$$ and $$$b_{r,i}$$$ ($$$0 \le a_{r, i} \le b_{r,i} \le m$$$) — the minimum and maximum values of the card at the right hand after the replacement.

## Output Format
At the first line, print "Yes", if Bob can answer all queries, and "No" otherwise.

If Bob can answer all $$$n$$$ queries, then at the second line print $$$n$$$ numbers: a way to satisfy all requirements. If in $$$i$$$-th query Bob needs to replace the card in the left hand, print $$$0$$$, otherwise print $$$1$$$. If there are multiple answers, print any.

## Examples
```input
2 10
3
0 3
0 2
2
0 4
0 2
```
```output
Yes
0 1
```
-----
```input
2 10
3
0 3
0 2
2
3 4
0 1
```
```output
No
```
-----
```input
5 10
3
0 3
0 3
7
4 7
1 3
2
2 3
3 7
8
1 8
1 8
6
1 6
7 10
```
```output
Yes
1 0 0 1 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya has an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Vasya thinks that all numbers in his array are strange for some reason. To calculate how strange the $$$i$$$-th number is, Vasya created the following algorithm.

He chooses a subsegment $$$a_l, a_{l+1}, \ldots, a_r$$$, such that $$$1 \le l \le i \le r \le n$$$, sort its elements in increasing order in his head (he can arrange equal elements arbitrary). After that he finds the center of the segment. The center of a segment is the element at position $$$(l + r) / 2$$$, if the length of the segment is odd, and at position $$$(l + r + 1) / 2$$$ otherwise. Now Vasya finds the element that was at position $$$i$$$ before the sorting, and calculates the distance between its current position and the center of the subsegment (the distance between the elements with indices $$$j$$$ and $$$k$$$ is $$$|j - k|$$$).

The strangeness of the number at position $$$i$$$ is the maximum distance among all suitable choices of $$$l$$$ and $$$r$$$.

Vasya wants to calculate the strangeness of each number in his array. Help him to do it.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — Vasya's array.

## Output Format
Print a single line with $$$n$$$ numbers. The $$$i$$$-th of them must be equal to the strangeness of the $$$i$$$-th element of the array.

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

## Note
In the first example:

1. For the first position we choose the segment from $$$1$$$ to $$$5$$$. After sorting, it looks like $$$[1, 2, 3, 4, 5]$$$, the center is $$$3$$$. The distance from the center to $$$5$$$ is $$$2$$$.
2. For the second position we choose the segment from $$$2$$$ to $$$4$$$.
3. For the third position we choose the segment from $$$3$$$ to $$$5$$$.
4. For the fourth position we choose the segment from $$$1$$$ to $$$4$$$. After sorting, it looks like $$$[2, 3, 4, 5]$$$, the center is $$$4$$$. The distance from the center to $$$2$$$ is $$$2$$$.
5. For the fifth position we choose the segment from $$$1$$$ to $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Welcome to Rockport City!

It is time for your first ever race in the game against Ronnie. To make the race interesting, you have bet $$$a$$$ dollars and Ronnie has bet $$$b$$$ dollars. But the fans seem to be disappointed. The excitement of the fans is given by $$$gcd(a,b)$$$, where $$$gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$. To make the race more exciting, you can perform two types of operations:

1. Increase both $$$a$$$ and $$$b$$$ by $$$1$$$.
2. Decrease both $$$a$$$ and $$$b$$$ by $$$1$$$. This operation can only be performed if both $$$a$$$ and $$$b$$$ are greater than $$$0$$$.

In one move, you can perform any one of these operations. You can perform arbitrary (possibly zero) number of moves. Determine the maximum excitement the fans can get and the minimum number of moves required to achieve it.

Note that $$$gcd(x,0)=x$$$ for any $$$x \ge 0$$$.

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

The first and the only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$0\leq a, b\leq 10^{18}$$$).

## Output Format
For each test case, print a single line containing two integers.

If the fans can get infinite excitement, print 0 0.

Otherwise, the first integer must be the maximum excitement the fans can get, and the second integer must be the minimum number of moves required to achieve that excitement.

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

## Note
For the first test case, you can apply the first operation $$$1$$$ time to get $$$a=9$$$ and $$$b=6$$$. It can be shown that $$$3$$$ is the maximum excitement possible.

For the second test case, no matter how many operations you apply, the fans will always have an excitement equal to $$$1$$$. Since the initial excitement is also $$$1$$$, you don't need to apply any operation.

For the third case, the fans can get infinite excitement by applying the first operation an infinite amount of times.

For the fourth test case, you can apply the second operation $$$3$$$ times to get $$$a=0$$$ and $$$b=6$$$. Since, $$$gcd(0,6)=6$$$, the fans will get an excitement of $$$6$$$.

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
Highway 201 is the most busy street in Rockport. Traffic cars cause a lot of hindrances to races, especially when there are a lot of them. The track which passes through this highway can be divided into $$$n$$$ sub-tracks. You are given an array $$$a$$$ where $$$a_i$$$ represents the number of traffic cars in the $$$i$$$-th sub-track. You define the inconvenience of the track as $$$\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \lvert a_i-a_j\rvert$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

You can perform the following operation any (possibly zero) number of times: choose a traffic car and move it from its current sub-track to any other sub-track.

Find the minimum inconvenience you can achieve.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^9$$$).

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 a single line containing a single integer: the minimum inconvenience you can achieve by applying the given operation any (possibly zero) number of times.

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

## Note
For the first test case, you can move a car from the $$$3$$$-rd sub-track to the $$$1$$$-st sub-track to obtain $$$0$$$ inconvenience.

For the second test case, moving any car won't decrease the inconvenience of the track.

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
You are given a strictly convex polygon with $$$n$$$ vertices.

You will make $$$k$$$ cuts that meet the following conditions:

- each cut is a segment that connects two different nonadjacent vertices;
- two cuts can intersect only at vertices of the polygon.

Your task is to maximize the area of the smallest region that will be formed by the polygon and those $$$k$$$ cuts.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$3 \le n \le 200$$$, $$$0 \le k \le n-3$$$).

The following $$$n$$$ lines describe vertices of the polygon in anticlockwise direction. The $$$i$$$-th line contains two integers $$$x_i$$$, $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^8$$$) — the coordinates of the $$$i$$$-th vertex.

It is guaranteed that the polygon is convex and that no two adjacent sides are parallel.

## Output Format
Print one integer: the maximum possible area of the smallest region after making $$$k$$$ cuts multiplied by $$$2$$$.

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

## Note
In the first example, it's optimal to make cuts between the following pairs of vertices:

- $$$(-2, -4)$$$ and $$$(4, 2)$$$,
- $$$(-2, -4)$$$ and $$$(1, 5)$$$,
- $$$(-5, -1)$$$ and $$$(1, 5)$$$,
- $$$(-5, 0)$$$ and $$$(0, 5)$$$.

Points $$$(-5, -1)$$$, $$$(1, 5)$$$, $$$(0, 5)$$$, $$$(-5, 0)$$$ determine the smallest region with double area of $$$11$$$.

In the second example, it's optimal to make cuts between the following pairs of vertices:

- $$$(2, -1)$$$ and $$$(0, 2)$$$,
- $$$(2, -1)$$$ and $$$(1, 0)$$$,
- $$$(-1, 0)$$$ and $$$(0, 2)$$$.

Points $$$(2, -2)$$$, $$$(2, -1)$$$, $$$(-1, 0)$$$ determine one of the smallest regions with double area of $$$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
You are given a string $$$s$$$ of length $$$n$$$ consisting of characters a and/or b.

Let $$$\operatorname{AB}(s)$$$ be the number of occurrences of string ab in $$$s$$$ as a substring. Analogically, $$$\operatorname{BA}(s)$$$ is the number of occurrences of ba in $$$s$$$ as a substring.

In one step, you can choose any index $$$i$$$ and replace $$$s_i$$$ with character a or b.

What is the minimum number of steps you need to make to achieve $$$\operatorname{AB}(s) = \operatorname{BA}(s)$$$?

Reminder:

The number of occurrences of string $$$d$$$ in $$$s$$$ as substring is the number of indices $$$i$$$ ($$$1 \le i \le |s| - |d| + 1$$$) such that substring $$$s_i s_{i + 1} \dots s_{i + |d| - 1}$$$ is equal to $$$d$$$. For example, $$$\operatorname{AB}($$$aabbbabaa$$$) = 2$$$ since there are two indices $$$i$$$: $$$i = 2$$$ where aabbbabaa and $$$i = 6$$$ where aabbbabaa.

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

The first and only line of each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 100$$$, where $$$|s|$$$ is the length of the string $$$s$$$), consisting only of characters a and/or b.

## Output Format
For each test case, print the resulting string $$$s$$$ with $$$\operatorname{AB}(s) = \operatorname{BA}(s)$$$ you'll get making the minimum number of steps.

If there are multiple answers, print any of them.

## Examples
```input
4
b
aabbbabaa
abbb
abbaab
```
```output
b
aabbbabaa
bbbb
abbaaa
```

## Note
In the first test case, both $$$\operatorname{AB}(s) = 0$$$ and $$$\operatorname{BA}(s) = 0$$$ (there are no occurrences of ab (ba) in b), so can leave $$$s$$$ untouched.

In the second test case, $$$\operatorname{AB}(s) = 2$$$ and $$$\operatorname{BA}(s) = 2$$$, so you can leave $$$s$$$ untouched.

In the third test case, $$$\operatorname{AB}(s) = 1$$$ and $$$\operatorname{BA}(s) = 0$$$. For example, we can change $$$s_1$$$ to b and make both values zero.

In the fourth test case, $$$\operatorname{AB}(s) = 2$$$ and $$$\operatorname{BA}(s) = 1$$$. For example, we can change $$$s_6$$$ to a and make both values equal to $$$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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ heroes fighting in the arena. Initially, the $$$i$$$-th hero has $$$a_i$$$ health points.

The fight in the arena takes place in several rounds. At the beginning of each round, each alive hero deals $$$1$$$ damage to all other heroes. Hits of all heroes occur simultaneously. Heroes whose health is less than $$$1$$$ at the end of the round are considered killed.

If exactly $$$1$$$ hero remains alive after a certain round, then he is declared the winner. Otherwise, there is no winner.

Your task is to calculate the number of ways to choose the initial health points for each hero $$$a_i$$$, where $$$1 \le a_i \le x$$$, so that there is no winner of the fight. The number of ways can be very large, so print it modulo $$$998244353$$$. Two ways are considered different if at least one hero has a different amount of health. For example, $$$[1, 2, 1]$$$ and $$$[2, 1, 1]$$$ are different.

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

## Output Format
Print one integer — the number of ways to choose the initial health points for each hero $$$a_i$$$, where $$$1 \le a_i \le x$$$, so that there is no winner of the fight, taken modulo $$$998244353$$$.

## Examples
```input
2 5
```
```output
5
```
-----
```input
3 3
```
```output
15
```
-----
```input
5 4
```
```output
1024
```
-----
```input
13 37
```
```output
976890680
```

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
Given $$$n$$$, find any array $$$a_1, a_2, \ldots, a_n$$$ of integers such that all of the following conditions hold:

- $$$1 \le a_i \le 10^9$$$ for every $$$i$$$ from $$$1$$$ to $$$n$$$.
- $$$a_1 < a_2 < \ldots <a_n$$$
- For every $$$i$$$ from $$$2$$$ to $$$n$$$, $$$a_i$$$ isn't divisible by $$$a_{i-1}$$$

It can be shown that such an array always exists under the constraints of the problem.

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

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

## Output Format
For each test case print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the array you found. If there are multiple arrays satisfying all the conditions, print any of them.

## Examples
```input
3
1
2
7
```
```output
1
2 3
111 1111 11111 111111 1111111 11111111 111111111
```

## Note
In the first test case, array $$$[1]$$$ satisfies all the conditions.

In the second test case, array $$$[2, 3]$$$ satisfies all the conditions, as $$$2<3$$$ and $$$3$$$ is not divisible by $$$2$$$.

In the third test case, array $$$[111, 1111, 11111, 111111, 1111111, 11111111, 111111111]$$$ satisfies all the conditions, as it's increasing and $$$a_i$$$ isn't divisible by $$$a_{i-1}$$$ for any $$$i$$$ from $$$2$$$ to $$$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 three integers $$$n, a, b$$$. Determine if there exists a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, such that:

- There are exactly $$$a$$$ integers $$$i$$$ with $$$2 \le i \le n-1$$$ such that $$$p_{i-1} < p_i > p_{i+1}$$$ (in other words, there are exactly $$$a$$$ local maximums).
- There are exactly $$$b$$$ integers $$$i$$$ with $$$2 \le i \le n-1$$$ such that $$$p_{i-1} > p_i < p_{i+1}$$$ (in other words, there are exactly $$$b$$$ local minimums).

If such permutations exist, find any such permutation.

## 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 only line of each test case contains three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$2 \leq n \leq 10^5$$$, $$$0 \leq a,b \leq n$$$).

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, if there is no permutation with the requested properties, output $$$-1$$$.

Otherwise, print the permutation that you are found. If there are several such permutations, you may print any of them.

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

## Note
In the first test case, one example of such permutations is $$$[1, 3, 2, 4]$$$. In it $$$p_1 < p_2 > p_3$$$, and $$$2$$$ is the only such index, and $$$p_2> p_3 < p_4$$$, and $$$3$$$ the only such index.

One can show that there is no such permutation for the third test case.

Now solve the problem and return the code.