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
Arkady and his friends love playing checkers on an $$$n \times n$$$ field. The rows and the columns of the field are enumerated from $$$1$$$ to $$$n$$$.

The friends have recently won a championship, so Arkady wants to please them with some candies. Remembering an old parable (but not its moral), Arkady wants to give to his friends one set of candies per each cell of the field: the set of candies for cell $$$(i, j)$$$ will have exactly $$$(i^2 + j^2)$$$ candies of unique type.

There are $$$m$$$ friends who deserve the present. How many of these $$$n \times n$$$ sets of candies can be split equally into $$$m$$$ parts without cutting a candy into pieces? Note that each set has to be split independently since the types of candies in different sets are different.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 1000$$$) — the size of the field and the number of parts to split the sets into.

## Output Format
Print a single integer — the number of sets that can be split equally.

## Examples
```input
3 3
```
```output
1
```
-----
```input
6 5
```
```output
13
```
-----
```input
1000000000 1
```
```output
1000000000000000000
```

## Note
In the first example, only the set for cell $$$(3, 3)$$$ can be split equally ($$$3^2 + 3^2 = 18$$$, which is divisible by $$$m=3$$$).

In the second example, the sets for the following cells can be divided equally:

- $$$(1, 2)$$$ and $$$(2, 1)$$$, since $$$1^2 + 2^2 = 5$$$, which is divisible by $$$5$$$;
- $$$(1, 3)$$$ and $$$(3, 1)$$$;
- $$$(2, 4)$$$ and $$$(4, 2)$$$;
- $$$(2, 6)$$$ and $$$(6, 2)$$$;
- $$$(3, 4)$$$ and $$$(4, 3)$$$;
- $$$(3, 6)$$$ and $$$(6, 3)$$$;
- $$$(5, 5)$$$.

In the third example, sets in all cells can be divided equally, since $$$m = 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
There is one apple tree in Arkady's garden. It can be represented as a set of junctions connected with branches so that there is only one way to reach any junctions from any other one using branches. The junctions are enumerated from $$$1$$$ to $$$n$$$, the junction $$$1$$$ is called the root.

A subtree of a junction $$$v$$$ is a set of junctions $$$u$$$ such that the path from $$$u$$$ to the root must pass through $$$v$$$. Note that $$$v$$$ itself is included in a subtree of $$$v$$$.

A leaf is such a junction that its subtree contains exactly one junction.

The New Year is coming, so Arkady wants to decorate the tree. He will put a light bulb of some color on each leaf junction and then count the number happy junctions. A happy junction is such a junction $$$t$$$ that all light bulbs in the subtree of $$$t$$$ have different colors.

Arkady is interested in the following question: for each $$$k$$$ from $$$1$$$ to $$$n$$$, what is the minimum number of different colors needed to make the number of happy junctions be greater than or equal to $$$k$$$?

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of junctions in the tree.

The second line contains $$$n - 1$$$ integers $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i < i$$$), where $$$p_i$$$ means there is a branch between junctions $$$i$$$ and $$$p_i$$$. It is guaranteed that this set of branches forms a tree.

## Output Format
Output $$$n$$$ integers. The $$$i$$$-th of them should be the minimum number of colors needed to make the number of happy junctions be at least $$$i$$$.

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

## Note
In the first example for $$$k = 1$$$ and $$$k = 2$$$ we can use only one color: the junctions $$$2$$$ and $$$3$$$ will be happy. For $$$k = 3$$$ you have to put the bulbs of different colors to make all the junctions happy.

In the second example for $$$k = 4$$$ you can, for example, put the bulbs of color $$$1$$$ in junctions $$$2$$$ and $$$4$$$, and a bulb of color $$$2$$$ into junction $$$5$$$. The happy junctions are the ones with indices $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ then.

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
One of Arkady's friends works at a huge radio telescope. A few decades ago the telescope has sent a signal $$$s$$$ towards a faraway galaxy. Recently they've received a response $$$t$$$ which they believe to be a response from aliens! The scientists now want to check if the signal $$$t$$$ is similar to $$$s$$$.

The original signal $$$s$$$ was a sequence of zeros and ones (everyone knows that binary code is the universe-wide language). The returned signal $$$t$$$, however, does not look as easy as $$$s$$$, but the scientists don't give up! They represented $$$t$$$ as a sequence of English letters and say that $$$t$$$ is similar to $$$s$$$ if you can replace all zeros in $$$s$$$ with some string $$$r_0$$$ and all ones in $$$s$$$ with some other string $$$r_1$$$ and obtain $$$t$$$. The strings $$$r_0$$$ and $$$r_1$$$ must be different and non-empty.

Please help Arkady's friend and find the number of possible replacements for zeros and ones (the number of pairs of strings $$$r_0$$$ and $$$r_1$$$) that transform $$$s$$$ to $$$t$$$.

## Input Format
The first line contains a string $$$s$$$ ($$$2 \le |s| \le 10^5$$$) consisting of zeros and ones — the original signal.

The second line contains a string $$$t$$$ ($$$1 \le |t| \le 10^6$$$) consisting of lowercase English letters only — the received signal.

It is guaranteed, that the string $$$s$$$ contains at least one '0' and at least one '1'.

## Output Format
Print a single integer — the number of pairs of strings $$$r_0$$$ and $$$r_1$$$ that transform $$$s$$$ to $$$t$$$.

In case there are no such pairs, print $$$0$$$.

## Examples
```input
01
aaaaaa
```
```output
4
```
-----
```input
001
kokokokotlin
```
```output
2
```

## Note
In the first example, the possible pairs $$$(r_0, r_1)$$$ are as follows:

- "a", "aaaaa"
- "aa", "aaaa"
- "aaaa", "aa"
- "aaaaa", "a"

The pair "aaa", "aaa" is not allowed, since $$$r_0$$$ and $$$r_1$$$ must be different.

In the second example, the following pairs are possible:

- "ko", "kokotlin"
- "koko", "tlin"

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
JATC and his friend Giraffe are currently in their room, solving some problems. Giraffe has written on the board an array $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ of integers, such that $$$1 \le a_1 < a_2 < \ldots < a_n \le 10^3$$$, and then went to the bathroom.

JATC decided to prank his friend by erasing some consecutive elements in the array. Since he doesn't want for the prank to go too far, he will only erase in a way, such that Giraffe can still restore the array using the information from the remaining elements. Because Giraffe has created the array, he's also aware that it's an increasing array and all the elements are integers in the range $$$[1, 10^3]$$$.

JATC wonders what is the greatest number of elements he can erase?

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in the array.

The second line of the input contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_1<a_2<\dots<a_n \le 10^3$$$) — the array written by Giraffe.

## Output Format
Print a single integer — the maximum number of consecutive elements in the array that JATC can erase.

If it is impossible to erase even a single element, print $$$0$$$.

## Examples
```input
6
1 3 4 5 6 9
```
```output
2
```
-----
```input
3
998 999 1000
```
```output
2
```
-----
```input
5
1 2 3 4 5
```
```output
4
```

## Note
In the first example, JATC can erase the third and fourth elements, leaving the array $$$[1, 3, \_, \_, 6, 9]$$$. As you can see, there is only one way to fill in the blanks.

In the second example, JATC can erase the second and the third elements. The array will become $$$[998, \_, \_]$$$. Because all the elements are less than or equal to $$$1000$$$, the array is still can be restored. Note, that he can't erase the first $$$2$$$ elements.

In the third example, JATC can erase the first $$$4$$$ elements. Since all the elements are greater than or equal to $$$1$$$, Giraffe can still restore the array. Note, that he can't erase the last $$$4$$$ 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
JATC's math teacher always gives the class some interesting math problems so that they don't get bored. Today the problem is as follows. Given an integer $$$n$$$, you can perform the following operations zero or more times:

- mul $$$x$$$: multiplies $$$n$$$ by $$$x$$$ (where $$$x$$$ is an arbitrary positive integer).
- sqrt: replaces $$$n$$$ with $$$\sqrt{n}$$$ (to apply this operation, $$$\sqrt{n}$$$ must be an integer).

You can perform these operations as many times as you like. What is the minimum value of $$$n$$$, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Apparently, no one in the class knows the answer to this problem, maybe you can help them?

## Input Format
The only line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the initial number.

## Output Format
Print two integers: the minimum integer $$$n$$$ that can be achieved using the described operations and the minimum number of operations required.

## Examples
```input
20
```
```output
10 2
```
-----
```input
5184
```
```output
6 4
```

## Note
In the first example, you can apply the operation mul $$$5$$$ to get $$$100$$$ and then sqrt to get $$$10$$$.

In the second example, you can first apply sqrt to get $$$72$$$, then mul $$$18$$$ to get $$$1296$$$ and finally two more sqrt and you get $$$6$$$.

Note, that even if the initial value of $$$n$$$ is less or equal $$$10^6$$$, it can still become greater than $$$10^6$$$ after applying one or more 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 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
You are given a positive integer $$$n$$$ greater or equal to $$$2$$$. For every pair of integers $$$a$$$ and $$$b$$$ ($$$2 \le |a|, |b| \le n$$$), you can transform $$$a$$$ into $$$b$$$ if and only if there exists an integer $$$x$$$ such that $$$1 < |x|$$$ and ($$$a \cdot x = b$$$ or $$$b \cdot x = a$$$), where $$$|x|$$$ denotes the absolute value of $$$x$$$.

After such a transformation, your score increases by $$$|x|$$$ points and you are not allowed to transform $$$a$$$ into $$$b$$$ nor $$$b$$$ into $$$a$$$ anymore.

Initially, you have a score of $$$0$$$. You can start at any integer and transform it as many times as you like. What is the maximum score you can achieve?

## Input Format
A single line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the given integer described above.

## Output Format
Print an only integer — the maximum score that can be achieved with the transformations. If it is not possible to perform even a single transformation for all possible starting integers, print $$$0$$$.

## Examples
```input
4
```
```output
8
```
-----
```input
6
```
```output
28
```
-----
```input
2
```
```output
0
```

## Note
In the first example, the transformations are $$$2 \rightarrow 4 \rightarrow (-2) \rightarrow (-4) \rightarrow 2$$$.

In the third example, it is impossible to perform even a single transformation.

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
Mishka is trying really hard to avoid being kicked out of the university. In particular, he was doing absolutely nothing for the whole semester, miraculously passed some exams so that just one is left.

There were $$$n$$$ classes of that subject during the semester and on $$$i$$$-th class professor mentioned some non-negative integer $$$a_i$$$ to the students. It turned out, the exam was to tell the whole sequence back to the professor.

Sounds easy enough for those who attended every class, doesn't it?

Obviously Mishka didn't attend any classes. However, professor left some clues on the values of $$$a$$$ to help out students like Mishka:

- $$$a$$$ was sorted in non-decreasing order ($$$a_1 \le a_2 \le \dots \le a_n$$$);
- $$$n$$$ was even;
- the following sequence $$$b$$$, consisting of $$$\frac n 2$$$ elements, was formed and given out to students: $$$b_i = a_i + a_{n - i + 1}$$$.

Professor also mentioned that any sequence $$$a$$$, which produces sequence $$$b$$$ with the presented technique, will be acceptable.

Help Mishka to pass that last exam. Restore any sorted sequence $$$a$$$ of non-negative integers, which produces sequence $$$b$$$ with the presented technique. It is guaranteed that there exists at least one correct sequence $$$a$$$, which produces the given sequence $$$b$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of sequence $$$a$$$. $$$n$$$ is always even.

The second line contains $$$\frac n 2$$$ integers $$$b_1, b_2, \dots, b_{\frac n 2}$$$ ($$$0 \le b_i \le 10^{18}$$$) — sequence $$$b$$$, where $$$b_i = a_i + a_{n - i + 1}$$$.

It is guaranteed that there exists at least one correct sequence $$$a$$$, which produces the given sequence $$$b$$$.

## Output Format
Print $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{18}$$$) in a single line.

$$$a_1 \le a_2 \le \dots \le a_n$$$ should be satisfied.

$$$b_i = a_i + a_{n - i + 1}$$$ should be satisfied for all valid $$$i$$$.

## Examples
```input
4
5 6
```
```output
2 3 3 3
```
-----
```input
6
2 1 2
```
```output
0 0 1 1 1 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 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: 512.0 MB

# Problem
Vasya has got an array consisting of $$$n$$$ integers, and two integers $$$k$$$ and $$$len$$$ in addition. All numbers in the array are either between $$$1$$$ and $$$k$$$ (inclusive), or equal to $$$-1$$$. The array is good if there is no segment of $$$len$$$ consecutive equal numbers.

Vasya will replace each $$$-1$$$ with some number from $$$1$$$ to $$$k$$$ (inclusive) in such a way that the resulting array is good. Tell him the number of ways to do this replacement. Since the answer may be large, print it modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n, k$$$ and $$$len$$$ ($$$1 \le n \le 10^5, 1 \le k \le 100, 1 \le len \le n$$$).

The second line contains $$$n$$$ numbers — the array. Each number is either $$$-1$$$ or between $$$1$$$ and $$$k$$$ (inclusive).

## Output Format
Print one integer — the number of ways to replace each $$$-1$$$ with some number from $$$1$$$ to $$$k$$$ (inclusive) so the array is good. The answer may be large, so print it modulo $$$998244353$$$.

## Examples
```input
5 2 3
1 -1 1 -1 2
```
```output
2
```
-----
```input
6 3 2
1 1 -1 -1 -1 -1
```
```output
0
```
-----
```input
10 42 7
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
```
```output
645711643
```

## Note
Possible answers in the first test:

1. $$$[1, 2, 1, 1, 2]$$$;
2. $$$[1, 2, 1, 2, 2]$$$.

There is no way to make the array good in the second test, since first two elements are equal.

There are too many answers in the third test, so we won't describe any of them.

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
Gennady owns a small hotel in the countryside where he lives a peaceful life. He loves to take long walks, watch sunsets and play cards with tourists staying in his hotel. His favorite game is called "Mau-Mau".

To play Mau-Mau, you need a pack of $$$52$$$ cards. Each card has a suit (Diamonds — D, Clubs — C, Spades — S, or Hearts — H), and a rank (2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, or A).

At the start of the game, there is one card on the table and you have five cards in your hand. You can play a card from your hand if and only if it has the same rank or the same suit as the card on the table.

In order to check if you'd be a good playing partner, Gennady has prepared a task for you. Given the card on the table and five cards in your hand, check if you can play at least one card.

## Input Format
The first line of the input contains one string which describes the card on the table. The second line contains five strings which describe the cards in your hand.

Each string is two characters long. The first character denotes the rank and belongs to the set $$$\{{\tt 2}, {\tt 3}, {\tt 4}, {\tt 5}, {\tt 6}, {\tt 7}, {\tt 8}, {\tt 9}, {\tt T}, {\tt J}, {\tt Q}, {\tt K}, {\tt A}\}$$$. The second character denotes the suit and belongs to the set $$$\{{\tt D}, {\tt C}, {\tt S}, {\tt H}\}$$$.

All the cards in the input are different.

## Output Format
If it is possible to play a card from your hand, print one word "YES". Otherwise, print "NO".

You can print each letter in any case (upper or lower).

## Examples
```input
AS
2H 4C TH JH AD
```
```output
YES
```
-----
```input
2H
3D 4C AC KD AS
```
```output
NO
```
-----
```input
4D
AS AC AD AH 5H
```
```output
YES
```

## Note
In the first example, there is an Ace of Spades (AS) on the table. You can play an Ace of Diamonds (AD) because both of them are Aces.

In the second example, you cannot play any card.

In the third example, you can play an Ace of Diamonds (AD) because it has the same suit as a Four of Diamonds (4D), which lies on the table.

Now solve the problem and return the code.