apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Marcos loves strings a lot, so he has a favorite string $$$s$$$ consisting of lowercase English letters. For this string, he wrote down all its non-empty prefixes and suffixes (except for $$$s$$$) on a piece of paper in arbitrary order. You see all these strings and wonder if Marcos' favorite string is a palindrome or not. So, your task is to decide whether $$$s$$$ is a palindrome by just looking at the piece of paper.

A string $$$a$$$ is a prefix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the end.

A string $$$a$$$ is a suffix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning.

A palindrome is a string that reads the same backward as forward, for example, strings "gg", "ioi", "abba", "icpci" are palindromes, but strings "codeforces", "abcd", "alt" are not.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n \le 20$$$) — the length of the string $$$s$$$.

The second line of each test case contains $$$2n-2$$$ strings $$$a_1, a_2, \cdots, a_{2n-2}$$$ — all non-empty prefixes and suffixes of $$$s$$$, not including itself, in arbitrary order.

It is guaranteed that these strings are all the non-empty prefixes and suffixes of some string consisting of lowercase English letters.

## Output Format
For each test case, output "YES" if $$$s$$$ is a palindrome, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
5
4
bcd cd a d abc ab
3
i io i oi
2
g g
3
t al lt a
4
bba a ab a abb ba
```
```output
NO
YES
YES
NO
YES
```

## Note
In the first test case, $$$s$$$ is "abcd". Its prefixes are "a", "ab" and "abc", and its suffixes are "d", "cd" and "bcd". As the string "abcd" is not a palindrome, the answer is NO.

In the second test case, $$$s$$$ is "ioi". Its prefixes are "i" and "io", and its suffixes are "i" and "oi". As the string "ioi" is a palindrome, the answer is YES.

In the third test case, $$$s$$$ is "gg" which is a palindrome.

In the fourth test case, $$$s$$$ is "alt" which is not a palindrome.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$. In one operation, you can choose any number of the array and add $$$1$$$ to it.

Make at most $$$2n$$$ operations so that the array satisfies the following property: $$$a_{i+1}$$$ is not divisible by $$$a_i$$$, for each $$$i = 1, 2, \ldots, n-1$$$.

You do not need to minimize the number of operations.

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

The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 10^4$$$) — the length of the given array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq 10^9$$$) — the given array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^4$$$.

## Output Format
For each test case, print the answer on a separate line.

In the only line, print $$$n$$$ integers — the resulting array $$$a$$$ after applying at most $$$2n$$$ operations.

We can show that an answer always exists under the given constraints. If there are multiple answers, print any of them.

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

## Note
In the first test case, the array $$$[4, 5, 6, 7]$$$ can be achieved by applying $$$2$$$ operations to the first element, $$$1$$$ operation to the second element, $$$3$$$ operations to the third element, and $$$1$$$ operation to the last element. The total number of operations performed is $$$7$$$, which is less than the allowed $$$8$$$ operations in this case.

In the second test case, the array $$$[3, 2, 3]$$$ can be achieved by applying two operations to the first element. Another possible resulting array could be $$$[2, 3, 5]$$$, because the total number of operations does not need to be minimum.

In the third test case, not applying any operations results in an array that satisfies the statement's property. Observe that it is not mandatory to make operations.

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

# Problem
The score of a sequence $$$[s_1, s_2, \ldots, s_d]$$$ is defined as $$$\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$$$, where $$$d!=1\cdot 2\cdot \ldots \cdot d$$$. In particular, the score of an empty sequence is $$$1$$$.

For a sequence $$$[s_1, s_2, \ldots, s_d]$$$, let $$$m$$$ be the maximum score among all its subsequences. Its cost is defined as the maximum length of a subsequence with a score of $$$m$$$.

You are given a non-decreasing sequence $$$[a_1, a_2, \ldots, a_n]$$$ of integers of length $$$n$$$. In other words, the condition $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$ is satisfied. For each $$$k=1, 2, \ldots , n$$$, find the cost of the sequence $$$[a_1, a_2, \ldots , a_k]$$$.

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements.

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

The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 10^5$$$) — the length of the given sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq n$$$) — the given sequence. It is guaranteed that its elements are in non-decreasing order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

## Output Format
For each test case, output $$$n$$$ integers — the costs of sequences $$$[a_1, a_2, \ldots , a_k]$$$ in ascending order of $$$k$$$.

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

## Note
In the first test case:

- The maximum score among the subsequences of $$$[1]$$$ is $$$1$$$. The subsequences $$$[1]$$$ and $$$[]$$$ (the empty sequence) are the only ones with this score. Thus, the cost of $$$[1]$$$ is $$$1$$$.
- The maximum score among the subsequences of $$$[1, 2]$$$ is $$$2$$$. The only subsequence with this score is $$$[2]$$$. Thus, the cost of $$$[1, 2]$$$ is $$$1$$$.
- The maximum score among the subsequences of $$$[1, 2, 3]$$$ is $$$3$$$. The subsequences $$$[2, 3]$$$ and $$$[3]$$$ are the only ones with this score. Thus, the cost of $$$[1, 2, 3]$$$ is $$$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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
The prime factorization of a positive integer $$$m$$$ is the unique way to write it as $$$\displaystyle m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}$$$, where $$$p_1, p_2, \ldots, p_k$$$ are prime numbers, $$$p_1 < p_2 < \ldots < p_k$$$ and $$$e_1, e_2, \ldots, e_k$$$ are positive integers.

For each positive integer $$$m$$$, $$$f(m)$$$ is defined as the multiset of all numbers in its prime factorization, that is $$$f(m)=\{p_1,e_1,p_2,e_2,\ldots,p_k,e_k\}$$$.

For example, $$$f(24)=\{2,3,3,1\}$$$, $$$f(5)=\{1,5\}$$$ and $$$f(1)=\{\}$$$.

You are given a list consisting of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$. Count how many positive integers $$$m$$$ satisfy that $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$. Since this value may be large, print it modulo $$$998\,244\,353$$$.

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

The second line contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1\le a_i\le 10^6$$$)  — the given list.

## Output Format
Print one integer, the number of positive integers $$$m$$$ satisfying $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$ modulo $$$998\,244\,353$$$.

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

## Note
In the first sample, the two values of $$$m$$$ such that $$$f(m)=\{1,2,3,3\}$$$ are $$$m=24$$$ and $$$m=54$$$. Their prime factorizations are $$$24=2^3\cdot 3^1$$$ and $$$54=2^1\cdot 3^3$$$.

In the second sample, the five values of $$$m$$$ such that $$$f(m)=\{2,2,3,5\}$$$ are $$$200, 225, 288, 500$$$ and $$$972$$$.

In the third sample, there is no value of $$$m$$$ such that $$$f(m)=\{1,4\}$$$. Neither $$$1^4$$$ nor $$$4^1$$$ are prime factorizations because $$$1$$$ and $$$4$$$ are not primes.

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
You are given an unweighted tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ and a list of $$$n-1$$$ integers $$$a_1, a_2, \ldots, a_{n-1}$$$. A tree is a connected undirected graph without cycles. You will use each element of the list to label one vertex. No vertex should be labeled twice. You can label the only remaining unlabeled vertex with any integer.

A vertex $$$x$$$ is called good if it is possible to do this labeling so that for each vertex $$$i$$$, its label is the distance between $$$x$$$ and $$$i$$$. The distance between two vertices $$$s$$$ and $$$t$$$ on a tree is the minimum number of edges on a path that starts at vertex $$$s$$$ and ends at vertex $$$t$$$.

Find all good vertices.

## Input Format
The first line contains one integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n - 1$$$ integers $$$a_1,a_2,\ldots,a_{n-1}$$$ ($$$0\le a_i < n$$$) — the given list.

Then, $$$n−1$$$ lines follow. Each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$) denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the edges form a tree.

## Output Format
In the first line print the number of good vertices.

In the second line, print the indices of all good vertices in ascending order.

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

## Note
This is the tree for the first example:

And these are two possible labelings with the elements on the list so that $$$2$$$ is a good vertex (left) and $$$4$$$ is a good vertex (right).

The square below each vertex represents its label. The black squares contain the numbers which were on the given list and the only white square contains the only number which was not on the given list.

In the second example, the only good vertex is vertex $$$3$$$.

In the third example, there are no good vertices.

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

# Problem
In one one-dimensional world there are n platforms. Platform with index k (platforms are numbered from 1) is a segment with coordinates [(k - 1)m, (k - 1)m + l], and l < m. Grasshopper Bob starts to jump along the platforms from point 0, with each jump he moves exactly d units right. Find out the coordinate of the point, where Bob will fall down. The grasshopper falls down, if he finds himself not on the platform, but if he finds himself on the edge of the platform, he doesn't fall down.

## Input Format
The first input line contains 4 integer numbers n, d, m, l (1 ≤ n, d, m, l ≤ 106, l < m) — respectively: amount of platforms, length of the grasshopper Bob's jump, and numbers m and l needed to find coordinates of the k-th platform: [(k - 1)m, (k - 1)m + l].

## Output Format
Output the coordinates of the point, where the grosshopper will fall down. Don't forget that if Bob finds himself on the platform edge, he doesn't fall down.

## Examples
```input
2 2 5 3
```
```output
4
```
-----
```input
5 4 11 8
```
```output
20
```

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

# Problem
Once Bob took a paper stripe of n squares (the height of the stripe is 1 square). In each square he wrote an integer number, possibly negative. He became interested in how many ways exist to cut this stripe into two pieces so that the sum of numbers from one piece is equal to the sum of numbers from the other piece, and each piece contains positive integer amount of squares. Would you help Bob solve this problem?

## Input Format
The first input line contains integer n (1 ≤ n ≤ 105) — amount of squares in the stripe. The second line contains n space-separated numbers — they are the numbers written in the squares of the stripe. These numbers are integer and do not exceed 10000 in absolute value.

## Output Format
Output the amount of ways to cut the stripe into two non-empty pieces so that the sum of numbers from one piece is equal to the sum of numbers from the other piece. Don't forget that it's allowed to cut the stripe along the squares' borders only.

## Examples
```input
9
1 5 -6 7 9 -16 0 -2 2
```
```output
3
```
-----
```input
3
1 1 1
```
```output
0
```
-----
```input
2
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: 2.0 seconds
Memory limit: 128.0 MB

# Problem
According to a new ISO standard, a flag of every country should have, strangely enough, a chequered field n × m, each square should be wholly painted one of 26 colours. The following restrictions are set:

- In each row at most two different colours can be used.
- No two adjacent squares can be painted the same colour.

Pay attention, please, that in one column more than two different colours can be used.

Berland's government took a decision to introduce changes into their country's flag in accordance with the new standard, at the same time they want these changes to be minimal. By the given description of Berland's flag you should find out the minimum amount of squares that need to be painted different colour to make the flag meet the new ISO standard. You are as well to build one of the possible variants of the new Berland's flag.

## Input Format
The first input line contains 2 integers n and m (1 ≤ n, m ≤ 500) — amount of rows and columns in Berland's flag respectively. Then there follows the flag's description: each of the following n lines contains m characters. Each character is a letter from a to z, and it stands for the colour of the corresponding square.

## Output Format
In the first line output the minimum amount of squares that need to be repainted to make the flag meet the new ISO standard. The following n lines should contain one of the possible variants of the new flag. Don't forget that the variant of the flag, proposed by you, should be derived from the old flag with the minimum amount of repainted squares. If the answer isn't unique, output any.

## Examples
```input
3 4
aaaa
bbbb
cccc
```
```output
6
abab
baba
acac
```
-----
```input
3 3
aba
aba
zzz
```
```output
4
aba
bab
zbz
```

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 Berland capital is shaken with three bold crimes committed by the Pihsters, a notorious criminal gang.

The Berland capital's map is represented by an n × m rectangular table. Each cell of the table on the map represents some districts of the capital.

The capital's main detective Polycarpus took a map and marked there the districts where the first three robberies had been committed as asterisks. Deduction tells Polycarpus that the fourth robbery will be committed in such district, that all four robbed districts will form the vertices of some rectangle, parallel to the sides of the map.

Polycarpus is good at deduction but he's hopeless at math. So he asked you to find the district where the fourth robbery will be committed.

## Input Format
The first line contains two space-separated integers n and m (2 ≤ n, m ≤ 100) — the number of rows and columns in the table, correspondingly.

Each of the next n lines contains m characters — the description of the capital's map. Each character can either be a "." (dot), or an "*" (asterisk). A character equals "*" if the corresponding district has been robbed. Otherwise, it equals ".".

It is guaranteed that the map has exactly three characters "*" and we can always find the fourth district that meets the problem requirements.

## Output Format
Print two integers — the number of the row and the number of the column of the city district that is the fourth one to be robbed. The rows are numbered starting from one from top to bottom and the columns are numbered starting from one from left to right.

## Examples
```input
3 2
.*
..
**
```
```output
1 1
```
-----
```input
3 3
*.*
*..
...
```
```output
2 3
```

Now solve the problem and return the code.