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: 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 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
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 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
PizzaForces is Petya's favorite pizzeria. PizzaForces makes and sells pizzas of three sizes: small pizzas consist of $$$6$$$ slices, medium ones consist of $$$8$$$ slices, and large pizzas consist of $$$10$$$ slices each. Baking them takes $$$15$$$, $$$20$$$ and $$$25$$$ minutes, respectively.

Petya's birthday is today, and $$$n$$$ of his friends will come, so he decided to make an order from his favorite pizzeria. Petya wants to order so much pizza that each of his friends gets at least one slice of pizza. The cooking time of the order is the total baking time of all the pizzas in the order.

Your task is to determine the minimum number of minutes that is needed to make pizzas containing at least $$$n$$$ slices in total. For example:

- if $$$12$$$ friends come to Petya's birthday, he has to order pizzas containing at least $$$12$$$ slices in total. He can order two small pizzas, containing exactly $$$12$$$ slices, and the time to bake them is $$$30$$$ minutes;
- if $$$15$$$ friends come to Petya's birthday, he has to order pizzas containing at least $$$15$$$ slices in total. He can order a small pizza and a large pizza, containing $$$16$$$ slices, and the time to bake them is $$$40$$$ minutes;
- if $$$300$$$ friends come to Petya's birthday, he has to order pizzas containing at least $$$300$$$ slices in total. He can order $$$15$$$ small pizzas, $$$10$$$ medium pizzas and $$$13$$$ large pizzas, in total they contain $$$15 \cdot 6 + 10 \cdot 8 + 13 \cdot 10 = 300$$$ slices, and the total time to bake them is $$$15 \cdot 15 + 10 \cdot 20 + 13 \cdot 25 = 750$$$ minutes;
- if only one friend comes to Petya's birthday, he can order a small pizza, and the time to bake it is $$$15$$$ minutes.

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

Each testcase consists of a single line that contains a single integer $$$n$$$ ($$$1 \le n \le 10^{16}$$$) — the number of Petya's friends.

## Output Format
For each testcase, print one integer — the minimum number of minutes that is needed to bake pizzas containing at least $$$n$$$ slices in total.

## Examples
```input
6
12
15
300
1
9999999999999999
3
```
```output
30
40
750
15
25000000000000000
15
```

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

# Problem
Let's call the string beautiful if it does not contain a substring of length at least $$$2$$$, which is a palindrome. Recall that a palindrome is a string that reads the same way from the first character to the last and from the last character to the first. For example, the strings a, bab, acca, bcabcbacb are palindromes, but the strings ab, abbbaa, cccb are not.

Let's define cost of a string as the minimum number of operations so that the string becomes beautiful, if in one operation it is allowed to change any character of the string to one of the first $$$3$$$ letters of the Latin alphabet (in lowercase).

You are given a string $$$s$$$ of length $$$n$$$, each character of the string is one of the first $$$3$$$ letters of the Latin alphabet (in lowercase).

You have to answer $$$m$$$ queries — calculate the cost of the substring of the string $$$s$$$ from $$$l_i$$$-th to $$$r_i$$$-th position, inclusive.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$ and the number of queries.

The second line contains the string $$$s$$$, it consists of $$$n$$$ characters, each character one of the first $$$3$$$ Latin letters.

The following $$$m$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — parameters of the $$$i$$$-th query.

## Output Format
For each query, print a single integer — the cost of the substring of the string $$$s$$$ from $$$l_i$$$-th to $$$r_i$$$-th position, inclusive.

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

## Note
Consider the queries of the example test.

- in the first query, the substring is baa, which can be changed to bac in one operation;
- in the second query, the substring is baacb, which can be changed to cbacb in two operations;
- in the third query, the substring is cb, which can be left unchanged;
- in the fourth query, the substring is aa, which can be changed to ba in one operation.

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

# Problem
You have an undirected graph consisting of $$$n$$$ vertices with weighted edges.

A simple cycle is a cycle of the graph without repeated vertices. Let the weight of the cycle be the XOR of weights of edges it consists of.

Let's say the graph is good if all its simple cycles have weight $$$1$$$. A graph is bad if it's not good.

Initially, the graph is empty. Then $$$q$$$ queries follow. Each query has the next type:

- $$$u$$$ $$$v$$$ $$$x$$$ — add edge between vertices $$$u$$$ and $$$v$$$ of weight $$$x$$$ if it doesn't make the graph bad.

For each query print, was the edge added or not.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n \le 3 \cdot 10^5$$$; $$$1 \le q \le 5 \cdot 10^5$$$) — the number of vertices and queries.

Next $$$q$$$ lines contain queries — one per line. Each query contains three integers $$$u$$$, $$$v$$$ and $$$x$$$ ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$0 \le x \le 1$$$) — the vertices of the edge and its weight.

It's guaranteed that there are no multiple edges in the input.

## Output Format
For each query, print YES if the edge was added to the graph, or NO otherwise (both case-insensitive).

## Examples
```input
9 12
6 1 0
1 3 1
3 6 0
6 2 0
6 4 1
3 4 1
2 4 0
2 5 0
4 5 0
7 8 1
8 9 1
9 7 0
```
```output
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
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: 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 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: 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 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
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 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 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.