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: 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 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 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 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
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 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.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 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: 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 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
An array $$$b$$$ of length $$$k$$$ is called good if its arithmetic mean is equal to $$$1$$$. More formally, if $$$$$$\frac{b_1 + \cdots + b_k}{k}=1.$$$$$$

Note that the value $$$\frac{b_1+\cdots+b_k}{k}$$$ is not rounded up or down. For example, the array $$$[1,1,1,2]$$$ has an arithmetic mean of $$$1.25$$$, which is not equal to $$$1$$$.

You are given an integer array $$$a$$$ of length $$$n$$$. In an operation, you can append a non-negative integer to the end of the array. What's the minimum number of operations required to make the array good?

We have a proof that it is always possible with finitely many operations.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

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

The second line of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$-10^4\leq a_i \leq 10^4$$$), the elements of the array.

## Output Format
For each test case, output a single integer — the minimum number of non-negative integers you have to append to the array so that the arithmetic mean of the array will be exactly $$$1$$$.

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

## Note
In the first test case, we don't need to add any element because the arithmetic mean of the array is already $$$1$$$, so the answer is $$$0$$$.

In the second test case, the arithmetic mean is not $$$1$$$ initially so we need to add at least one more number. If we add $$$0$$$ then the arithmetic mean of the whole array becomes $$$1$$$, so the answer is $$$1$$$.

In the third test case, the minimum number of elements that need to be added is $$$16$$$ since only non-negative integers can be added.

In the fourth test case, we can add a single integer $$$4$$$. The arithmetic mean becomes $$$\frac{-2+4}{2}$$$ which is 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Riley is a very bad boy, but at the same time, he is a yo-yo master. So, he decided to use his yo-yo skills to annoy his friend Anton.

Anton's room can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Let $$$(i, j)$$$ denote the cell in row $$$i$$$ and column $$$j$$$. Anton is currently standing at position $$$(i, j)$$$ in his room. To annoy Anton, Riley decided to throw exactly two yo-yos in cells of the room (they can be in the same cell).

Because Anton doesn't like yo-yos thrown on the floor, he has to pick up both of them and return back to the initial position. The distance travelled by Anton is the shortest path that goes through the positions of both yo-yos and returns back to $$$(i, j)$$$ by travelling only to adjacent by side cells. That is, if he is in cell $$$(x, y)$$$ then he can travel to the cells $$$(x + 1, y)$$$, $$$(x - 1, y)$$$, $$$(x, y + 1)$$$ and $$$(x, y - 1)$$$ in one step (if a cell with those coordinates exists).

Riley is wondering where he should throw these two yo-yos so that the distance travelled by Anton is maximized. But because he is very busy, he asked you to tell him.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of each test case contains four integers $$$n$$$, $$$m$$$, $$$i$$$, $$$j$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$1\le i\le n$$$, $$$1\le j\le m$$$) — the dimensions of the room, and the cell at which Anton is currently standing.

## Output Format
For each test case, print four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \leq x_1, x_2 \leq n$$$, $$$1\le y_1, y_2\le m$$$) — the coordinates of where the two yo-yos should be thrown. They will be thrown at coordinates $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$.

If there are multiple answers, you may print any.

## Examples
```input
7
2 3 1 1
4 4 1 2
3 5 2 2
5 1 2 1
3 1 3 1
1 1 1 1
1000000000 1000000000 1000000000 50
```
```output
1 2 2 3
4 1 4 4
3 1 1 5
5 1 1 1
1 1 2 1
1 1 1 1
50 1 1 1000000000
```

## Note
Here is a visualization of the first test case.

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
Alice and Bob are playing a game.

They start with a positive integer $$$n$$$ and take alternating turns doing operations on it. Each turn a player can subtract from $$$n$$$ one of its divisors that isn't $$$1$$$ or $$$n$$$. The player who cannot make a move on his/her turn loses. Alice always moves first.

Note that they subtract a divisor of the current number in each turn.

You are asked to find out who will win the game if both players play optimally.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — the initial number.

## Output Format
For each test case output "Alice" if Alice will win the game or "Bob" if Bob will win, if both players play optimally.

## Examples
```input
4
1
4
12
69
```
```output
Bob
Alice
Alice
Bob
```

## Note
In the first test case, the game ends immediately because Alice cannot make a move.

In the second test case, Alice can subtract $$$2$$$ making $$$n = 2$$$, then Bob cannot make a move so Alice wins.

In the third test case, Alice can subtract $$$3$$$ so that $$$n = 9$$$. Bob's only move is to subtract $$$3$$$ and make $$$n = 6$$$. Now, Alice can subtract $$$3$$$ again and $$$n = 3$$$. Then Bob cannot make a move, so Alice wins.

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
This is the easy version of the problem. The only difference is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

You have a string $$$s$$$, and you can do two types of operations on it:

- Delete the last character of the string.
- Duplicate the string: $$$s:=s+s$$$, where $$$+$$$ denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly $$$k$$$ that can be obtained by doing these operations on string $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a\ne b$$$;
- In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 5000$$$) — the length of the original string $$$s$$$ and the length of the desired string.

The second line contains the string $$$s$$$, consisting of $$$n$$$ lowercase English letters.

## Output Format
Print the lexicographically smallest string of length $$$k$$$ that can be obtained by doing the operations on string $$$s$$$.

## Examples
```input
8 16
dbcadabc
```
```output
dbcadabcdbcadabc
```
-----
```input
4 5
abcd
```
```output
aaaaa
```

## Note
In the first test, it is optimal to make one duplication: "dbcadabc" $$$\to$$$ "dbcadabcdbcadabc".

In the second test it is optimal to delete the last $$$3$$$ characters, then duplicate the string $$$3$$$ times, then delete the last $$$3$$$ characters to make the string have length $$$k$$$.

"abcd" $$$\to$$$ "abc" $$$\to$$$ "ab" $$$\to$$$ "a" $$$\to$$$ "aa" $$$\to$$$ "aaaa" $$$\to$$$ "aaaaaaaa" $$$\to$$$ "aaaaaaa" $$$\to$$$ "aaaaaa" $$$\to$$$ "aaaaa".

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
This is the hard version of the problem. The only difference is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

You have a string $$$s$$$, and you can do two types of operations on it:

- Delete the last character of the string.
- Duplicate the string: $$$s:=s+s$$$, where $$$+$$$ denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly $$$k$$$ that can be obtained by doing these operations on string $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a\ne b$$$;
- In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 5\cdot 10^5$$$) — the length of the original string $$$s$$$ and the length of the desired string.

The second line contains the string $$$s$$$, consisting of $$$n$$$ lowercase English letters.

## Output Format
Print the lexicographically smallest string of length $$$k$$$ that can be obtained by doing the operations on string $$$s$$$.

## Examples
```input
8 16
dbcadabc
```
```output
dbcadabcdbcadabc
```
-----
```input
4 5
abcd
```
```output
aaaaa
```

## Note
In the first test, it is optimal to make one duplication: "dbcadabc" $$$\to$$$ "dbcadabcdbcadabc".

In the second test it is optimal to delete the last $$$3$$$ characters, then duplicate the string $$$3$$$ times, then delete the last $$$3$$$ characters to make the string have length $$$k$$$.

"abcd" $$$\to$$$ "abc" $$$\to$$$ "ab" $$$\to$$$ "a" $$$\to$$$ "aa" $$$\to$$$ "aaaa" $$$\to$$$ "aaaaaaaa" $$$\to$$$ "aaaaaaa" $$$\to$$$ "aaaaaa" $$$\to$$$ "aaaaa".

Now solve the problem and return the code.