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

# Problem
Pupils Alice and Ibragim are best friends. It's Ibragim's birthday soon, so Alice decided to gift him a new puzzle. The puzzle can be represented as a matrix with $$$2$$$ rows and $$$n$$$ columns, every element of which is either $$$0$$$ or $$$1$$$. In one move you can swap two values in neighboring cells.

More formally, let's number rows $$$1$$$ to $$$2$$$ from top to bottom, and columns $$$1$$$ to $$$n$$$ from left to right. Also, let's denote a cell in row $$$x$$$ and column $$$y$$$ as $$$(x, y)$$$. We consider cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ neighboring if $$$|x_1 - x_2| + |y_1 - y_2| = 1$$$.

Alice doesn't like the way in which the cells are currently arranged, so she came up with her own arrangement, with which she wants to gift the puzzle to Ibragim. Since you are her smartest friend, she asked you to help her find the minimal possible number of operations in which she can get the desired arrangement. Find this number, or determine that it's not possible to get the new arrangement.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — the number of columns in the puzzle.

Following two lines describe the current arrangement on the puzzle. Each line contains $$$n$$$ integers, every one of which is either $$$0$$$ or $$$1$$$.

The last two lines describe Alice's desired arrangement in the same format.

## Output Format
If it is possible to get the desired arrangement, print the minimal possible number of steps, otherwise print $$$-1$$$.

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

## Note
In the first example the following sequence of swaps will suffice:

- $$$(2, 1), (1, 1)$$$,
- $$$(1, 2), (1, 3)$$$,
- $$$(2, 2), (2, 3)$$$,
- $$$(1, 4), (1, 5)$$$,
- $$$(2, 5), (2, 4)$$$.

It can be shown that $$$5$$$ is the minimal possible answer in this case.

In the second example no matter what swaps you do, you won't get the desired arrangement, so the answer is $$$-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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are standing at the point $$$0$$$ on a coordinate line. Your goal is to reach the point $$$n$$$. In one minute, you can move by $$$2$$$ or by $$$3$$$ to the left or to the right (i. e., if your current coordinate is $$$x$$$, it can become $$$x-3$$$, $$$x-2$$$, $$$x+2$$$ or $$$x+3$$$). Note that the new coordinate can become negative.

Your task is to find the minimum number of minutes required to get from the point $$$0$$$ to the point $$$n$$$.

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. Then $$$t$$$ lines describing the test cases follow.

The $$$i$$$-th of these lines contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the goal of the $$$i$$$-th test case.

## Output Format
For each test case, print one integer — the minimum number of minutes required to get from the point $$$0$$$ to the point $$$n$$$ for the corresponding test case.

## Examples
```input
4
1
3
4
12
```
```output
2
1
2
4
```

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 is a grid, consisting of $$$2$$$ rows and $$$m$$$ columns. The rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom. The columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

The robot starts in a cell $$$(1, 1)$$$. In one second, it can perform either of two actions:

- move into a cell adjacent by a side: up, right, down or left;
- remain in the same cell.

The robot is not allowed to move outside the grid.

Initially, all cells, except for the cell $$$(1, 1)$$$, are locked. Each cell $$$(i, j)$$$ contains a value $$$a_{i,j}$$$ — the moment that this cell gets unlocked. The robot can only move into a cell $$$(i, j)$$$ if at least $$$a_{i,j}$$$ seconds have passed before the move.

The robot should visit all cells without entering any cell twice or more (cell $$$(1, 1)$$$ is considered entered at the start). It can finish in any cell.

What is the fastest the robot can achieve that?

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

The first line of each testcase contains a single integer $$$m$$$ ($$$2 \le m \le 2 \cdot 10^5$$$) — the number of columns of the grid.

The $$$i$$$-th of the next $$$2$$$ lines contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 10^9$$$) — the moment of time each cell gets unlocked. $$$a_{1,1} = 0$$$. If $$$a_{i,j} = 0$$$, then cell $$$(i, j)$$$ is unlocked from the start.

The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.

## Examples
```input
4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0
```
```output
5
19
17
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
There is a chip on the coordinate line. Initially, the chip is located at the point $$$0$$$. You can perform any number of moves; each move increases the coordinate of the chip by some positive integer (which is called the length of the move). The length of the first move you make should be divisible by $$$k$$$, the length of the second move — by $$$k+1$$$, the third — by $$$k+2$$$, and so on.

For example, if $$$k=2$$$, then the sequence of moves may look like this: $$$0 \rightarrow 4 \rightarrow 7 \rightarrow 19 \rightarrow 44$$$, because $$$4 - 0 = 4$$$ is divisible by $$$2 = k$$$, $$$7 - 4 = 3$$$ is divisible by $$$3 = k + 1$$$, $$$19 - 7 = 12$$$ is divisible by $$$4 = k + 2$$$, $$$44 - 19 = 25$$$ is divisible by $$$5 = k + 3$$$.

You are given two positive integers $$$n$$$ and $$$k$$$. Your task is to count the number of ways to reach the point $$$x$$$, starting from $$$0$$$, for every $$$x \in [1, n]$$$. The number of ways can be very large, so print it modulo $$$998244353$$$. Two ways are considered different if they differ as sets of visited positions.

## Input Format
The first (and only) line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

## Output Format
Print $$$n$$$ integers — the number of ways to reach the point $$$x$$$, starting from $$$0$$$, for every $$$x \in [1, n]$$$, taken modulo $$$998244353$$$.

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

## Note
Let's look at the first example:

Ways to reach the point $$$1$$$: $$$[0, 1]$$$;

Ways to reach the point $$$2$$$: $$$[0, 2]$$$;

Ways to reach the point $$$3$$$: $$$[0, 1, 3]$$$, $$$[0, 3]$$$;

Ways to reach the point $$$4$$$: $$$[0, 2, 4]$$$, $$$[0, 4]$$$;

Ways to reach the point $$$5$$$: $$$[0, 1, 5]$$$, $$$[0, 3, 5]$$$, $$$[0, 5]$$$;

Ways to reach the point $$$6$$$: $$$[0, 1, 3, 6]$$$, $$$[0, 2, 6]$$$, $$$[0, 4, 6]$$$, $$$[0, 6]$$$;

Ways to reach the point $$$7$$$: $$$[0, 2, 4, 7]$$$, $$$[0, 1, 7]$$$, $$$[0, 3, 7]$$$, $$$[0, 5, 7]$$$, $$$[0, 7]$$$;

Ways to reach the point $$$8$$$: $$$[0, 3, 5, 8]$$$, $$$[0, 1, 5, 8]$$$, $$$[0, 2, 8]$$$, $$$[0, 4, 8]$$$, $$$[0, 6, 8]$$$, $$$[0, 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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array of length $$$2^n$$$. The elements of the array are numbered from $$$1$$$ to $$$2^n$$$.

You have to process $$$q$$$ queries to this array. In the $$$i$$$-th query, you will be given an integer $$$k$$$ ($$$0 \le k \le n-1$$$). To process the query, you should do the following:

- for every $$$i \in [1, 2^n-2^k]$$$ in ascending order, do the following: if the $$$i$$$-th element was already swapped with some other element during this query, skip it; otherwise, swap $$$a_i$$$ and $$$a_{i+2^k}$$$;
- after that, print the maximum sum over all contiguous subsegments of the array (including the empty subsegment).

For example, if the array $$$a$$$ is $$$[-3, 5, -3, 2, 8, -20, 6, -1]$$$, and $$$k = 1$$$, the query is processed as follows:

- the $$$1$$$-st element wasn't swapped yet, so we swap it with the $$$3$$$-rd element;
- the $$$2$$$-nd element wasn't swapped yet, so we swap it with the $$$4$$$-th element;
- the $$$3$$$-rd element was swapped already;
- the $$$4$$$-th element was swapped already;
- the $$$5$$$-th element wasn't swapped yet, so we swap it with the $$$7$$$-th element;
- the $$$6$$$-th element wasn't swapped yet, so we swap it with the $$$8$$$-th element.

So, the array becomes $$$[-3, 2, -3, 5, 6, -1, 8, -20]$$$. The subsegment with the maximum sum is $$$[5, 6, -1, 8]$$$, and the answer to the query is $$$18$$$.

Note that the queries actually change the array, i. e. after a query is performed, the array does not return to its original state, and the next query will be applied to the modified array.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 18$$$).

The second line contains $$$2^n$$$ integers $$$a_1, a_2, \dots, a_{2^n}$$$ ($$$-10^9 \le a_i \le 10^9$$$).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$).

Then $$$q$$$ lines follow, the $$$i$$$-th of them contains one integer $$$k$$$ ($$$0 \le k \le n-1$$$) describing the $$$i$$$-th query.

## Output Format
For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.

## Examples
```input
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1
```
```output
18
8
13
```

## Note
Transformation of the array in the example: $$$[-3, 5, -3, 2, 8, -20, 6, -1] \rightarrow [-3, 2, -3, 5, 6, -1, 8, -20] \rightarrow [2, -3, 5, -3, -1, 6, -20, 8] \rightarrow [5, -3, 2, -3, -20, 8, -1, 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
There are $$$n$$$ bags, each bag contains $$$m$$$ balls with numbers from $$$1$$$ to $$$m$$$. For every $$$i \in [1, m]$$$, there is exactly one ball with number $$$i$$$ in each bag.

You have to take exactly one ball from each bag (all bags are different, so, for example, taking the ball $$$1$$$ from the first bag and the ball $$$2$$$ from the second bag is not the same as taking the ball $$$2$$$ from the first bag and the ball $$$1$$$ from the second bag). After that, you calculate the number of balls with odd numbers among the ones you have taken. Let the number of these balls be $$$F$$$.

Your task is to calculate the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag.

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

Each test case consists of one line containing three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m \le 998244352$$$; $$$1 \le k \le 2000$$$).

## Output Format
For each test case, print one integer — the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag. Since it can be huge, print it modulo $$$998244353$$$.

## Examples
```input
5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000
```
```output
1028
1
3
729229716
652219904
```

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
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 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
Vlad went into his appartment house entrance, now he is on the $$$1$$$-th floor. He was going to call the elevator to go up to his apartment.

There are only two elevators in his house. Vlad knows for sure that:

- the first elevator is currently on the floor $$$a$$$ (it is currently motionless),
- the second elevator is located on floor $$$b$$$ and goes to floor $$$c$$$ ($$$b \ne c$$$). Please note, if $$$b=1$$$, then the elevator is already leaving the floor $$$1$$$ and Vlad does not have time to enter it.

If you call the first elevator, it will immediately start to go to the floor $$$1$$$. If you call the second one, then first it will reach the floor $$$c$$$ and only then it will go to the floor $$$1$$$. It takes $$$|x - y|$$$ seconds for each elevator to move from floor $$$x$$$ to floor $$$y$$$.

Vlad wants to call an elevator that will come to him faster. Help him choose such an elevator.

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

This is followed by $$$t$$$ lines, three integers each $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^8$$$, $$$b \ne c$$$) — floor numbers described in the statement.

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case. As an answer, output:

- $$$1$$$, if it is better to call the first elevator;
- $$$2$$$, if it is better to call the second one;
- $$$3$$$, if it doesn't matter which elevator to call (both elevators will arrive in the same time).

## Examples
```input
3
1 2 3
3 1 2
3 2 1
```
```output
1
3
2
```

## Note
In the first test case of the example, the first elevator is already on the floor of $$$1$$$.

In the second test case of the example, when called, the elevators would move as follows:

- At the time of the call, the first elevator is on the floor of $$$3$$$, and the second one is on the floor of $$$1$$$, but is already going to another floor;
- in $$$1$$$ second after the call, the first elevator would be on the floor $$$2$$$, the second one would also reach the floor $$$2$$$ and now can go to the floor $$$1$$$;
- in $$$2$$$ seconds, any elevator would reach the floor $$$1$$$.

In the third test case of the example, the first elevator will arrive in $$$2$$$ seconds, and the second in $$$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: 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.