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

# Problem
Burenka has two pictures $$$a$$$ and $$$b$$$, which are tables of the same size $$$n \times m$$$. Each cell of each painting has a color — a number from $$$0$$$ to $$$2 \cdot 10^5$$$, and there are no repeating colors in any row or column of each of the two paintings, except color $$$0$$$.

Burenka wants to get a picture $$$b$$$ from the picture $$$a$$$. To achieve her goal, Burenka can perform one of $$$2$$$ operations: swap any two rows of $$$a$$$ or any two of its columns. Tell Burenka if she can fulfill what she wants, and if so, tell her the sequence of actions.

The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, the columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — the sizes of the table.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$0 \leq a_{i,j} \leq 2 \cdot 10^5$$$) — the colors of the $$$i$$$-th row of picture $$$a$$$. It is guaranteed that there are no identical colors in the same row or column, except color $$$0$$$.

The $$$i$$$-th of the following $$$n$$$ lines contains $$$m$$$ integers $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}$$$ ($$$0 \leq b_{i,j} \leq 2 \cdot 10^5$$$) — the colors of the $$$i$$$-th row of picture $$$b$$$. It is guaranteed that there are no identical colors in the same row or column, except color $$$0$$$.

## Output Format
In the first line print the number $$$-1$$$ if it is impossible to achieve what Burenka wants, otherwise print the number of actions in your solution $$$k$$$ ($$$0 \le k \le 2 \cdot 10^5$$$). It can be proved that if a solution exists, then there exists a solution where $$$k \le 2 \cdot 10^5$$$.

In the next $$$k$$$ lines print the operations. First print the type of the operation ($$$1$$$ — swap rows, $$$2$$$ — columns), and then print the two indices of rows or columns to which the operation is applied.

Note that you don't have to minimize the number of operations.

## Examples
```input
3 3
1 0 2
0 0 0
2 0 1
2 0 1
0 0 0
1 0 2
```
```output
1
1 1 3
```
-----
```input
4 4
0 0 1 2
3 0 0 0
0 1 0 0
1 0 0 0
2 0 0 1
0 3 0 0
0 1 0 0
0 0 1 0
```
```output
4
1 3 4
2 3 4
2 2 3
2 1 2
```
-----
```input
3 3
1 2 0
0 0 0
0 0 0
1 0 0
2 0 0
0 0 0
```
```output
-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
Nikephoros and Polycarpus play rock-paper-scissors. The loser gets pinched (not too severely!).

Let us remind you the rules of this game. Rock-paper-scissors is played by two players. In each round the players choose one of three items independently from each other. They show the items with their hands: a rock, scissors or paper. The winner is determined by the following rules: the rock beats the scissors, the scissors beat the paper and the paper beats the rock. If the players choose the same item, the round finishes with a draw.

Nikephoros and Polycarpus have played n rounds. In each round the winner gave the loser a friendly pinch and the loser ended up with a fresh and new red spot on his body. If the round finished in a draw, the players did nothing and just played on.

Nikephoros turned out to have worked out the following strategy: before the game began, he chose some sequence of items A = (a1, a2, ..., am), and then he cyclically showed the items from this sequence, starting from the first one. Cyclically means that Nikephoros shows signs in the following order: a1, a2, ..., am, a1, a2, ..., am, a1, ... and so on. Polycarpus had a similar strategy, only he had his own sequence of items B = (b1, b2, ..., bk).

Determine the number of red spots on both players after they've played n rounds of the game. You can consider that when the game began, the boys had no red spots on them.

## Input Format
The first line contains integer n (1 ≤ n ≤ 2·109) — the number of the game's rounds.

The second line contains sequence A as a string of m characters and the third line contains sequence B as a string of k characters (1 ≤ m, k ≤ 1000). The given lines only contain characters "R", "S" and "P". Character "R" stands for the rock, character "S" represents the scissors and "P" represents the paper.

## Output Format
Print two space-separated integers: the numbers of red spots Nikephoros and Polycarpus have.

## Examples
```input
7
RPS
RSPP
```
```output
3 2
```
-----
```input
5
RRRRRRRR
R
```
```output
0 0
```

## Note
In the first sample the game went like this:

- R - R. Draw.
- P - S. Nikephoros loses.
- S - P. Polycarpus loses.
- R - P. Nikephoros loses.
- P - R. Polycarpus loses.
- S - S. Draw.
- R - P. Nikephoros loses.

Thus, in total Nikephoros has 3 losses (and 3 red spots), and Polycarpus only has 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 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
The Trinitarian kingdom has exactly n = 3k cities. All of them are located on the shores of river Trissisipi, which flows through the whole kingdom. Some of the cities are located on one side of the river, and all the rest are on the other side.

Some cities are connected by bridges built between them. Each bridge connects two cities that are located on the opposite sides of the river. Between any two cities exists no more than one bridge.

The recently inaugurated King Tristan the Third is busy distributing his deputies among cities. In total there are k deputies and the king wants to commission each of them to control exactly three cities. However, no deputy can be entrusted to manage the cities, which are connected by a bridge — the deputy can set a too high fee for travelling over the bridge to benefit his pocket, which is bad for the reputation of the king.

Help King Tristan the Third distribute the deputies between the cities, if it is possible.

## Input Format
The first line contains two integers n and m — the number of cities and bridges (3 ≤ n < 105, n = 3k, 0 ≤ m ≤ 105). Next m lines describe the bridges. The i-th line contains two integers ai and bi — the numbers of cities that are connected by the i-th bridge (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ i ≤ m).

It is guaranteed that no bridge connects a city with itself and that any two cities are connected with no more than one bridge.

## Output Format
If distributing the deputies in the required manner is impossible, print in a single line "NO" (without the quotes).

Otherwise, in the first line print "YES" (without the quotes), and in the second line print which deputy should be put in charge of each city. The i-th number should represent the number of the deputy (from 1 to k), who should be in charge of city numbered i-th in the input — overall there should be n numbers.

If there are multiple solutions, print any of them.

## Examples
```input
6 6
1 2
4 1
3 5
6 5
2 6
4 6
```
```output
YES
1 2 1 2 2 1
```
-----
```input
3 1
1 2
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Joey is low on money. His friend Chandler wants to lend Joey some money, but can't give him directly, as Joey is too proud of himself to accept it. So, in order to trick him, Chandler asks Joey to play a game.

In this game, Chandler gives Joey an array $$$a_1, a_2, \dots, a_n$$$ ($$$n \geq 2$$$) of positive integers ($$$a_i \ge 1$$$).

Joey can perform the following operation on the array any number of times:

1. Take two indices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n)$$$.
2. Choose two integers $$$x$$$ and $$$y$$$ ($$$x, y \ge 1$$$) such that $$$x \cdot y = a_i \cdot a_j$$$.
3. Replace $$$a_i$$$ by $$$x$$$ and $$$a_j$$$ by $$$y$$$.

In the end, Joey will get the money equal to the sum of elements of the final array.

Find the maximum amount of money $$$\mathrm{ans}$$$ Joey can get but print $$$2022 \cdot \mathrm{ans}$$$. Why multiplied by $$$2022$$$? Because we are never gonna see it again!

It is guaranteed that the product of all the elements of the array $$$a$$$ doesn't exceed $$$10^{12}$$$.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the array itself.

It's guaranteed that the product of all $$$a_i$$$ doesn't exceed $$$10^{12}$$$ (i. e. $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n \le 10^{12}$$$).

## Output Format
For each test case, print the maximum money Joey can get multiplied by $$$2022$$$.

## Examples
```input
3
3
2 3 2
2
1 3
3
1000000 1000000 1
```
```output
28308
8088
2022000000004044
```

## Note
In the first test case, Joey can do the following:

1. He chooses $$$i = 1$$$ and $$$j = 2$$$ (so he has $$$a[i] \cdot a[j] = 6$$$), chooses $$$x = 6$$$ and $$$y = 1$$$ and makes $$$a[i] = 6$$$ and $$$a[j] = 1$$$. $$$$$$[2, 3, 2] \xrightarrow[x = 6,\; y = 1]{i = 1,\; j = 2} [6, 1, 2]$$$$$$
2. He chooses $$$i = 1$$$ and $$$j = 3$$$ (so he has $$$a[i] \cdot a[j] = 12$$$), chooses $$$x = 12$$$ and $$$y = 1$$$ and makes $$$a[i] = 12$$$ and $$$a[j] = 1$$$. $$$$$$[6, 1, 2] \xrightarrow[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 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 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
Demodogs from the Upside-down have attacked Hawkins again. El wants to reach Mike and also kill as many Demodogs in the way as possible.

Hawkins can be represented as an $$$n \times n$$$ grid. The number of Demodogs in a cell at the $$$i$$$-th row and the $$$j$$$-th column is $$$i \cdot j$$$. El is at position $$$(1, 1)$$$ of the grid, and she has to reach $$$(n, n)$$$ where she can find Mike.

The only directions she can move are the right (from $$$(i, j)$$$ to $$$(i, j + 1)$$$) and the down (from $$$(i, j)$$$ to $$$(i + 1, j)$$$). She can't go out of the grid, as there are doors to the Upside-down at the boundaries.

Calculate the maximum possible number of Demodogs $$$\mathrm{ans}$$$ she can kill on the way, considering that she kills all Demodogs in cells she visits (including starting and finishing cells).

Print $$$2022 \cdot \mathrm{ans}$$$ modulo $$$10^9 + 7$$$. Modulo $$$10^9 + 7$$$ because the result can be too large and multiplied by $$$2022$$$ because we are never gonna see it again!

(Note, you firstly multiply by $$$2022$$$ and only after that take the remainder.)

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

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — the size of the grid.

## Output Format
For each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by $$$2022$$$, modulo $$$10^9 + 7$$$.

## Examples
```input
4
2
3
50
1000000000
```
```output
14154
44484
171010650
999589541
```

## Note
In the first test case, for any path chosen by her the number of Demodogs to be killed would be $$$7$$$, so the answer would be $$$2022 \cdot 7 = 14154$$$.

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

# Problem
Suppose you have an integer array $$$a_1, a_2, \dots, a_n$$$.

Let $$$\operatorname{lsl}(i)$$$ be the number of indices $$$j$$$ ($$$1 \le j < i$$$) such that $$$a_j < a_i$$$.

Analogically, let $$$\operatorname{grr}(i)$$$ be the number of indices $$$j$$$ ($$$i < j \le n$$$) such that $$$a_j > a_i$$$.

Let's name position $$$i$$$ good in the array $$$a$$$ if $$$\operatorname{lsl}(i) < \operatorname{grr}(i)$$$.

Finally, let's define a function $$$f$$$ on array $$$a$$$ $$$f(a)$$$ as the sum of all $$$a_i$$$ such that $$$i$$$ is good in $$$a$$$.

Given two integers $$$n$$$ and $$$k$$$, find the sum of $$$f(a)$$$ over all arrays $$$a$$$ of size $$$n$$$ such that $$$1 \leq a_i \leq k$$$ for all $$$1 \leq i \leq n$$$ modulo $$$998\,244\,353$$$.

## Input Format
The first and only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 50$$$; $$$2 \leq k < 998\,244\,353$$$).

## Output Format
Output a single integer — the sum of $$$f$$$ over all arrays $$$a$$$ of size $$$n$$$ modulo $$$998\,244\,353$$$.

## Examples
```input
3 3
```
```output
28
```
-----
```input
5 6
```
```output
34475
```
-----
```input
12 30
```
```output
920711694
```

## Note
In the first test case:

$$$f([1,1,1]) = 0$$$$$$f([2,2,3]) = 2 + 2 = 4$$$$$$f([1,1,2]) = 1 + 1 = 2$$$$$$f([2,3,1]) = 2$$$$$$f([1,1,3]) = 1 + 1 = 2$$$$$$f([2,3,2]) = 2$$$$$$f([1,2,1]) = 1$$$$$$f([2,3,3]) = 2$$$$$$f([1,2,2]) = 1$$$$$$f([3,1,1]) = 0$$$$$$f([1,2,3]) = 1$$$$$$f([3,1,2]) = 1$$$$$$f([1,3,1]) = 1$$$$$$f([3,1,3]) = 1$$$$$$f([1,3,2]) = 1$$$$$$f([3,2,1]) = 0$$$$$$f([1,3,3]) = 1$$$$$$f([3,2,2]) = 0$$$$$$f([2,1,1]) = 0$$$$$$f([3,2,3]) = 2$$$$$$f([2,1,2]) = 1$$$$$$f([3,3,1]) = 0$$$$$$f([2,1,3]) = 2 + 1 = 3$$$$$$f([3,3,2]) = 0$$$$$$f([2,2,1]) = 0$$$$$$f([3,3,3]) = 0$$$$$$f([2,2,2]) = 0$$$

Adding up all of these values, we get $$$28$$$ as the answer.

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
Your working week consists of $$$n$$$ days numbered from $$$1$$$ to $$$n$$$, after day $$$n$$$ goes day $$$1$$$ again. And $$$3$$$ of them are days off. One of the days off is the last day, day $$$n$$$. You have to decide when the other two are.

Choosing days off, you pursue two goals:

- No two days should go one after the other. Note that you can't make day $$$1$$$ a day off because it follows day $$$n$$$.
- Working segments framed by days off should be as dissimilar as possible in duration. More specifically, if the segments are of size $$$l_1$$$, $$$l_2$$$, and $$$l_3$$$ days long, you want to maximize $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$$$.

Output the maximum value of $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$$$ that can be obtained.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.

The only line of each test case contains the integer $$$n$$$ ($$$6 \le n \le 10^9$$$).

## Output Format
For each test case, output one integer — the maximum possible obtained value.

## Examples
```input
3
6
10
1033
```
```output
0
1
342
```

## Note
In the image below you can see the example solutions for the first two test cases. Chosen days off are shown in purple. Working segments are underlined in green.

In test case $$$1$$$, the only options for days off are days $$$2$$$, $$$3$$$, and $$$4$$$ (because $$$1$$$ and $$$5$$$ are next to day $$$n$$$). So the only way to place them without selecting neighboring days is to choose days $$$2$$$ and $$$4$$$. Thus, $$$l_1 = l_2 = l_3 = 1$$$, and the answer $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0$$$.

For test case $$$2$$$, one possible way to choose days off is shown. The working segments have the lengths of $$$2$$$, $$$1$$$, and $$$4$$$ days. So the minimum difference is $$$1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|)$$$. It can be shown that there is no way to make it larger.

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
There are $$$n$$$ pieces of tangerine peel, the $$$i$$$-th of them has size $$$a_i$$$. In one step it is possible to divide one piece of size $$$x$$$ into two pieces of positive integer sizes $$$y$$$ and $$$z$$$ so that $$$y + z = x$$$.

You want that for each pair of pieces, their sizes differ strictly less than twice. In other words, there should not be two pieces of size $$$x$$$ and $$$y$$$, such that $$$2x \le y$$$. What is the minimum possible number of steps needed to satisfy the condition?

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 100$$$).

Then one line follows, containing $$$n$$$ integers $$$a_1 \le a_2 \le \ldots \le a_n$$$ ($$$1 \le a_i \le 10^7$$$).

## Output Format
For each test case, output a single line containing the minimum number of steps.

## Examples
```input
3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550
```
```output
10
0
4
```

## Note
In the first test case, we initially have a piece of size $$$1$$$, so all final pieces must have size $$$1$$$. The total number of steps is: $$$0 + 1 + 2 + 3 + 4 = 10$$$.

In the second test case, we have just one piece, so we don't need to do anything, and the answer is $$$0$$$ steps.

In the third test case, one of the possible cut options is: $$$600,\ 900,\ (600 | 700),\ (1000 | 1000),\ (1000 | 1000 | 550)$$$. You can see this option in the picture below. The maximum piece has size $$$1000$$$, and it is less than $$$2$$$ times bigger than the minimum piece of size $$$550$$$. $$$4$$$ steps are done. We can show that it is the minimum possible number of steps.

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

# Problem
Let's call a positive integer extremely round if it has only one non-zero digit. For example, $$$5000$$$, $$$4$$$, $$$1$$$, $$$10$$$, $$$200$$$ are extremely round integers; $$$42$$$, $$$13$$$, $$$666$$$, $$$77$$$, $$$101$$$ are not.

You are given an integer $$$n$$$. You have to calculate the number of extremely round integers $$$x$$$ such that $$$1 \le x \le n$$$.

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

Then, $$$t$$$ lines follow. The $$$i$$$-th of them contains one integer $$$n$$$ ($$$1 \le n \le 999999$$$) — the description of the $$$i$$$-th test case.

## Output Format
For each test case, print one integer — the number of extremely round integers $$$x$$$ such that $$$1 \le x \le n$$$.

## Examples
```input
5
9
42
13
100
111
```
```output
9
13
10
19
19
```

Now solve the problem and return the code.