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
Baby Ehab was toying around with arrays. He has an array $$$a$$$ of length $$$n$$$. He defines an array to be good if there's no way to partition it into $$$2$$$ subsequences such that the sum of the elements in the first is equal to the sum of the elements in the second. Now he wants to remove the minimum number of elements in $$$a$$$ so that it becomes a good array. Can you help him?

A sequence $$$b$$$ is a subsequence of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly zero or all) elements. A partitioning of an array is a way to divide it into $$$2$$$ subsequences such that every element belongs to exactly one subsequence, so you must use all the elements, and you can't share any elements.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 2000$$$) — the elements of the array $$$a$$$.

## Output Format
The first line should contain the minimum number of elements you need to remove.

The second line should contain the indices of the elements you're removing, separated by spaces.

We can show that an answer always exists. If there are multiple solutions, you can print any.

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

## Note
In the first example, you can partition the array into $$$[6,9]$$$ and $$$[3,12]$$$, so you must remove at least $$$1$$$ element. Removing $$$3$$$ is sufficient.

In the second example, the array is already good, so you don't need to remove any elements.

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
This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array $$$a$$$ of length $$$n$$$ written on it, and then he does the following:

- he picks a range $$$(l, r)$$$ and cuts the subsegment $$$a_l, a_{l + 1}, \ldots, a_r$$$ out, removing the rest of the array.
- he then cuts this range into multiple subranges.
- to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their least common multiple (LCM).

Formally, he partitions the elements of $$$a_l, a_{l + 1}, \ldots, a_r$$$ into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for $$$q$$$ independent ranges $$$(l, r)$$$, tell Baby Ehab the minimum number of subarrays he needs.

## Input Format
The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — the length of the array $$$a$$$ and the number of queries.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the elements of the array $$$a$$$.

Each of the next $$$q$$$ lines contains $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of this query's interval.

## Output Format
For each query, print its answer on a new line.

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

## Note
The first query asks about the whole array. You can partition it into $$$[2]$$$, $$$[3,10,7]$$$, and $$$[5,14]$$$. The first subrange has product and LCM equal to $$$2$$$. The second has product and LCM equal to $$$210$$$. And the third has product and LCM equal to $$$70$$$. Another possible partitioning is $$$[2,3]$$$, $$$[10,7]$$$, and $$$[5,14]$$$.

The second query asks about the range $$$(2,4)$$$. Its product is equal to its LCM, so you don't need to partition it further.

The last query asks about the range $$$(3,5)$$$. You can partition it into $$$[10,7]$$$ and $$$[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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This time around, Baby Ehab will play with permutations. He has $$$n$$$ cubes arranged in a row, with numbers from $$$1$$$ to $$$n$$$ written on them. He'll make exactly $$$j$$$ operations. In each operation, he'll pick up $$$2$$$ cubes and switch their positions.

He's wondering: how many different sequences of cubes can I have at the end? Since Baby Ehab is a turbulent person, he doesn't know how many operations he'll make, so he wants the answer for every possible $$$j$$$ between $$$1$$$ and $$$k$$$.

## Input Format
The only line contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le k \le 200$$$) — the number of cubes Baby Ehab has, and the parameter $$$k$$$ from the statement.

## Output Format
Print $$$k$$$ space-separated integers. The $$$i$$$-th of them is the number of possible sequences you can end up with if you do exactly $$$i$$$ operations. Since this number can be very large, print the remainder when it's divided by $$$10^9+7$$$.

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

## Note
In the second example, there are $$$3$$$ sequences he can get after $$$1$$$ swap, because there are $$$3$$$ pairs of cubes he can swap. Also, there are $$$3$$$ sequences he can get after $$$2$$$ swaps:

- $$$[1,2,3]$$$,
- $$$[3,1,2]$$$,
- $$$[2,3,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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vika has decided to go on a trip to Bertown. She comes to Bertown on the $$$k$$$-th day. Vika does not want to spend money on hotels, fortunately she has $$$n$$$ friends who live in Bertown and allow Vika to stay at their houses. The $$$i$$$-th friend told Vika that she could stay at their house from the $$$l_i$$$-th day till the $$$r_i$$$-th day, inclusive.

Vika decided that she would stay at no more than one friend's house. Help Vika determine the maximum number of days that she will be able to stay in Bertown.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 100$$$) — the number of Vika's friends and the day when Vika comes to Bertown.

Then follow $$$n$$$ lines, each containing two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 100$$$) denoting the period when Vika can stay at the $$$i$$$-th friend's house.

## Output Format
For each test case, output a single integer — the maximum number of days that Vika can stay in Bertown (or $$$0$$$ if none of Vika's friends can host her on day $$$k$$$).

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

## Note
In the first example, Vika can stay at the $$$2$$$-nd friend's house from $$$3$$$-rd to $$$6$$$-th day.

In the second example, none of Vika's friends can host her on the $$$4$$$-th day.

In the third example, Vika can stay at the $$$1$$$-st friend's house, but only for the $$$4$$$-th day.

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 an array $$$s$$$ consisting of $$$n$$$ different strings. Each string consists of $$$m$$$ lowercase Latin letters.

You have to respond to $$$q$$$ queries. Each query contains a string $$$t$$$ of length $$$m+1$$$. Count the number of indices $$$i$$$, such that the string $$$t$$$ can be obtained from the string $$$s_i$$$, if it is allowed to insert one letter in an arbitrary position.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le m \le 10$$$) — the number of strings in the array and the length of each string.

The following $$$n$$$ lines contain strings $$$s_i$$$. All of the given strings are different.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain query strings $$$t$$$ of length $$$m + 1$$$.

## Output Format
For each query, print the number of indices $$$i$$$, such that a string from the query can be obtained from the string $$$s_i$$$, if it is allowed to insert one letter in an arbitrary position.

## Examples
```input
2 1
a
c
4
aa
ca
mm
cf
```
```output
1
2
0
1
```
-----
```input
6 3
dba
abd
cbb
ada
add
bdd
5
ccbb
abdd
adba
bada
dddd
```
```output
1
3
2
1
0
```

## Note
Explanation of the first test of the example:

- the string a can be transformed into aa by inserting one letter;
- both strings a and c can be transformed into ca by inserting one letter;
- neither a nor c can be transformed into mm by inserting one letter;
- c can be transformed into cf by inserting one letter.

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
Let's call a string $$$t$$$ consisting of characters 0 and/or 1 beautiful, if either the number of occurrences of character 0 in this string does not exceed $$$k$$$, or the number of occurrences of characters 1 in this string does not exceed $$$k$$$ (or both). For example, if $$$k = 3$$$, the strings 101010, 111, 0, 00000, 1111111000 are beautiful, and the strings 1111110000, 01010101 are not beautiful.

You are given a string $$$s$$$. You have to divide it into the minimum possible number of beautiful strings, i. e., find a sequence of strings $$$t_1, t_2, \dots, t_m$$$ such that every $$$t_i$$$ is beautiful, $$$t_1 + t_2 + \dots + t_m = s$$$ (where $$$+$$$ is the concatenation operator), and $$$m$$$ is minimum possible.

For every $$$k$$$ from $$$1$$$ to $$$|s|$$$, find the minimum possible number of strings such that $$$s$$$ can be divided into them (i. e. the minimum possible $$$m$$$ in the partition).

## Input Format
The only line contains one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). Each character of $$$s$$$ is either 0 or 1.

## Output Format
Print $$$|s|$$$ integers. The $$$i$$$-th integer should be equal to the minimum number of strings in the partition of $$$s$$$, when $$$k = i$$$.

## Examples
```input
00100010
```
```output
2 1 1 1 1 1 1 1
```
-----
```input
1001011100
```
```output
3 2 2 2 1 1 1 1 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp decided to generate a biome map for his game. A map is a matrix divided into cells $$$1 \times 1$$$. Each cell of the map must contain one of the available biomes.

Each biome is defined by two parameters: temperature (an integer from $$$1$$$ to $$$n$$$) and humidity (an integer from $$$1$$$ to $$$m$$$). But not for every temperature/humidity combination, a corresponding biome is available.

The biome map should be generated according to the following rules:

- each cell of the map belongs to exactly one biome;
- each available biome has at least one cell on the map;
- if two cells of the map are adjacent by the side and they belong to biomes with parameters ($$$t_1, h_1$$$) and ($$$t_2, h_2$$$), respectively, then the equality $$$|t_1-t_2| + |h_1-h_2| = 1$$$ holds;
- let the number of available biomes be equal to $$$k$$$, then the number of rows and columns of the map (separately) should not exceed $$$k$$$.

Help Polycarp generate a biome map that meets all the conditions described above (or report that this is impossible).

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10$$$) — maximum temperature and humidity parameters.

The following $$$n$$$ lines contain $$$m$$$ integers each $$$a_{i,1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 100$$$), where $$$a_{i, j}$$$ — the biome identifier with the parameters $$$(i, j)$$$, if $$$a_{i, j} \neq 0$$$, otherwise the biome with such parameters is not available.

All biome identifiers are different, and there are at least two biomes available.

## Output Format
For each test case, print the answer in the following format:

- print $$$-1$$$ in a single line if there is no map that meets all the conditions;
- otherwise, in the first line, print two integers $$$h$$$ and $$$w$$$ — the number of rows and columns of the map, respectively. In the following $$$h$$$ lines, print $$$w$$$ integers — the identifiers of the biomes in the corresponding cells of the map.

## Examples
```input
4
2 3
0 2 5
0 1 0
3 5
0 3 4 9 11
1 5 0 10 12
0 6 7 0 0
2 2
2 0
0 5
1 2
13 37
```
```output
1 3
5 2 1 
2 8
11 9 4 3 5 1 5 6 
12 10 9 4 3 5 6 7 
-1
1 2
13 37
```

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

# Problem
You are given matrix $$$s$$$ that contains $$$n$$$ rows and $$$m$$$ columns. Each element of a matrix is one of the $$$5$$$ first Latin letters (in upper case).

For each $$$k$$$ ($$$1 \le k \le 5$$$) calculate the number of submatrices that contain exactly $$$k$$$ different letters. Recall that a submatrix of matrix $$$s$$$ is a matrix that can be obtained from $$$s$$$ after removing several (possibly zero) first rows, several (possibly zero) last rows, several (possibly zero) first columns, and several (possibly zero) last columns. If some submatrix can be obtained from $$$s$$$ in two or more ways, you have to count this submatrix the corresponding number of times.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 800$$$).

Then $$$n$$$ lines follow, each containing the string $$$s_i$$$ ($$$|s_i| = m$$$) — $$$i$$$-th row of the matrix.

## Output Format
For each $$$k$$$ ($$$1 \le k \le 5$$$) print one integer — the number of submatrices that contain exactly $$$k$$$ different letters.

## Examples
```input
2 3
ABB
ABA
```
```output
9 9 0 0 0
```
-----
```input
6 6
EDCECE
EDDCEB
ACCECC
BAEEDC
DDDDEC
DDAEAD
```
```output
56 94 131 103 57
```
-----
```input
3 10
AEAAEEEEEC
CEEAAEEEEE
CEEEEAACAA
```
```output
78 153 99 0 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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
There is an infinite chessboard, divided into cells. The cell $$$(x, y)$$$ is the cell on the intersection of the $$$x_i$$$-th row and $$$y_i$$$-th column. $$$n$$$ black pawns are placed on the board, the $$$i$$$-th black pawn occupies the cell $$$(x_i, y_i)$$$.

You want to capture all black pawns. In order to do so, you may perform the following actions:

- place a white pawn into any empty cell (any cell having integer coordinates can be chosen, as long as it doesn't contain any pawns);
- make a move with one of the white pawns according to the chess rules.

Recall that when you make a move with a white pawn in the cell $$$(x, y)$$$, the chess rules allow you to choose exactly one of these actions:

- if there is a black pawn in the cell $$$(x + 1, y - 1)$$$, you can capture it — the black pawn is removed from the board, and the white pawn moves to $$$(x + 1, y - 1)$$$;
- if there is a black pawn in the cell $$$(x + 1, y + 1)$$$, you can capture it — the black pawn is removed from the board, and the white pawn moves to $$$(x + 1, y + 1)$$$;
- if the cell $$$(x + 1, y)$$$ is empty, you can move the white pawn to that cell.

You may perform any finite sequence of actions (placing white pawns and moving them). You want to capture all of the black pawns, and it can be shown that it is always possible; and you want to do it placing as few white pawns as possible.

What is the minimum number of white pawns you have to place to capture all $$$n$$$ black pawns?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of black pawns.

Then $$$n$$$ lines follow. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 5 \cdot 10^5$$$) denoting a black pawn in the cell $$$(x_i, y_i)$$$. No cell is occupied by two or more black pawns.

## Output Format
Print one integer — the minimum number of white pawns you have to place to capture all $$$n$$$ black pawns.

## Examples
```input
3
1 1
5 1
2 2
```
```output
1
```
-----
```input
3
3 2
1 3
1 1
```
```output
2
```
-----
```input
2
1 1
2 2
```
```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
Gregor is learning about RSA cryptography, and although he doesn't understand how RSA works, he is now fascinated with prime numbers and factoring them.

Gregor's favorite prime number is $$$P$$$. Gregor wants to find two bases of $$$P$$$. Formally, Gregor is looking for two integers $$$a$$$ and $$$b$$$ which satisfy both of the following properties.

- $$$P \bmod a = P \bmod b$$$, where $$$x \bmod y$$$ denotes the remainder when $$$x$$$ is divided by $$$y$$$, and
- $$$2 \le a < b \le P$$$.

Help Gregor find two bases of his favorite prime number!

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

Each subsequent line contains the integer $$$P$$$ ($$$5 \le P \le {10}^9$$$), with $$$P$$$ guaranteed to be prime.

## Output Format
Your output should consist of $$$t$$$ lines. Each line should consist of two integers $$$a$$$ and $$$b$$$ ($$$2 \le a < b \le P$$$). If there are multiple possible solutions, print any.

## Examples
```input
2
17
5
```
```output
3 5
2 4
```

## Note
The first query is $$$P=17$$$. $$$a=3$$$ and $$$b=5$$$ are valid bases in this case, because $$$17 \bmod 3 = 17 \bmod 5 = 2$$$. There are other pairs which work as well.

In the second query, with $$$P=5$$$, the only solution is $$$a=2$$$ and $$$b=4$$$.

Now solve the problem and return the code.