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

# Problem
Unary is a minimalistic Brainfuck dialect in which programs are written using only one token.

Brainfuck programs use 8 commands: "+", "-", "[", "]", "<", ">", "." and "," (their meaning is not important for the purposes of this problem). Unary programs are created from Brainfuck programs using the following algorithm. First, replace each command with a corresponding binary code, using the following conversion table:

- ">"  →  1000,
- "<"  →  1001,
- "+"  →  1010,
- "-"  →  1011,
- "."  →  1100,
- ","  →  1101,
- "["  →  1110,
- "]"  →  1111.

Next, concatenate the resulting binary codes into one binary number in the same order as in the program. Finally, write this number using unary numeral system — this is the Unary program equivalent to the original Brainfuck one.

You are given a Brainfuck program. Your task is to calculate the size of the equivalent Unary program, and print it modulo 1000003 (106 + 3).

## Input Format
The input will consist of a single line p which gives a Brainfuck program. String p will contain between 1 and 100 characters, inclusive. Each character of p will be "+", "-", "[", "]", "<", ">", "." or ",".

## Output Format
Output the size of the equivalent Unary program modulo 1000003 (106 + 3).

## Examples
```input
,.
```
```output
220
```
-----
```input
++++[>,.<-]
```
```output
61425
```

## Note
To write a number n in unary numeral system, one simply has to write 1 n times. For example, 5 written in unary system will be 11111.

In the first example replacing Brainfuck commands with binary code will give us 1101 1100. After we concatenate the codes, we'll get 11011100 in binary system, or 220 in decimal. That's exactly the number of tokens in the equivalent Unary program.

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

# Problem
Eugene likes working with arrays. And today he needs your help in solving one challenging task.

An array $$$c$$$ is a subarray of an array $$$b$$$ if $$$c$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Let's call a nonempty array good if for every nonempty subarray of this array, sum of the elements of this subarray is nonzero. For example, array $$$[-1, 2, -3]$$$ is good, as all arrays $$$[-1]$$$, $$$[-1, 2]$$$, $$$[-1, 2, -3]$$$, $$$[2]$$$, $$$[2, -3]$$$, $$$[-3]$$$ have nonzero sums of elements. However, array $$$[-1, 2, -1, -3]$$$ isn't good, as his subarray $$$[-1, 2, -1]$$$ has sum of elements equal to $$$0$$$.

Help Eugene to calculate the number of nonempty good subarrays of a given array $$$a$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$)  — the length of array $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)  — the elements of $$$a$$$.

## Output Format
Output a single integer  — the number of good subarrays of $$$a$$$.

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

## Note
In the first sample, the following subarrays are good: $$$[1]$$$, $$$[1, 2]$$$, $$$[2]$$$, $$$[2, -3]$$$, $$$[-3]$$$. However, the subarray $$$[1, 2, -3]$$$ isn't good, as its subarray $$$[1, 2, -3]$$$ has sum of elements equal to $$$0$$$.

In the second sample, three subarrays of size 1 are the only good subarrays. At the same time, the subarray $$$[41, -41, 41]$$$ isn't good, as its subarray $$$[41, -41]$$$ has sum of elements equal to $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Kate has a set $$$S$$$ of $$$n$$$ integers $$$\{1, \dots, n\} $$$.

She thinks that imperfection of a subset $$$M \subseteq S$$$ is equal to the maximum of $$$gcd(a, b)$$$ over all pairs $$$(a, b)$$$ such that both $$$a$$$ and $$$b$$$ are in $$$M$$$ and $$$a \neq b$$$.

Kate is a very neat girl and for each $$$k \in \{2, \dots, n\}$$$ she wants to find a subset that has the smallest imperfection among all subsets in $$$S$$$ of size $$$k$$$. There can be more than one subset with the smallest imperfection and the same size, but you don't need to worry about it. Kate wants to find all the subsets herself, but she needs your help to find the smallest possible imperfection for each size $$$k$$$, will name it $$$I_k$$$.

Please, help Kate to find $$$I_2$$$, $$$I_3$$$, ..., $$$I_n$$$.

## Input Format
The first and only line in the input consists of only one integer $$$n$$$ ($$$2\le n \le 5 \cdot 10^5$$$)  — the size of the given set $$$S$$$.

## Output Format
Output contains only one line that includes $$$n - 1$$$ integers: $$$I_2$$$, $$$I_3$$$, ..., $$$I_n$$$.

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

## Note
First sample: answer is 1, because $$$gcd(1, 2) = 1$$$.

Second sample: there are subsets of $$$S$$$ with sizes $$$2, 3$$$ with imperfection equal to 1. For example, $$$\{2,3\}$$$ and $$$\{1, 2, 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 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
Ichihime is the current priestess of the Mahjong Soul Temple. She claims to be human, despite her cat ears.

These days the temple is holding a math contest. Usually, Ichihime lacks interest in these things, but this time the prize for the winner is her favorite — cookies. Ichihime decides to attend the contest. Now she is solving the following problem.

You are given four positive integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, such that $$$a \leq b \leq c \leq d$$$.

Your task is to find three integers $$$x$$$, $$$y$$$, $$$z$$$, satisfying the following conditions:

- $$$a \leq x \leq b$$$.
- $$$b \leq y \leq c$$$.
- $$$c \leq z \leq d$$$.
- There exists a triangle with a positive non-zero area and the lengths of its three sides are $$$x$$$, $$$y$$$, and $$$z$$$.

Ichihime desires to get the cookie, but the problem seems too hard for her. Can you help her?

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

The next $$$t$$$ lines describe test cases. Each test case is given as four space-separated integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$1 \leq a \leq b \leq c \leq d \leq 10^9$$$).

## Output Format
For each test case, print three integers $$$x$$$, $$$y$$$, $$$z$$$  — the integers you found satisfying the conditions given in the statement.

It is guaranteed that the answer always exists. If there are multiple answers, print any.

## Examples
```input
4
1 3 5 7
1 5 5 7
100000 200000 300000 400000
1 1 977539810 977539810
```
```output
3 4 5
5 5 5
182690 214748 300999
1 977539810 977539810
```

## Note
One of the possible solutions to the first test case:

One of the possible solutions to the second 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Kana was just an ordinary high school girl before a talent scout discovered her. Then, she became an idol. But different from the stereotype, she is also a gameholic.

One day Kana gets interested in a new adventure game called Dragon Quest. In this game, her quest is to beat a dragon.

The dragon has a hit point of $$$x$$$ initially. When its hit point goes to $$$0$$$ or under $$$0$$$, it will be defeated. In order to defeat the dragon, Kana can cast the two following types of spells.

- Void Absorption Assume that the dragon's current hit point is $$$h$$$, after casting this spell its hit point will become $$$\left\lfloor \frac{h}{2} \right\rfloor + 10$$$. Here $$$\left\lfloor \frac{h}{2} \right\rfloor$$$ denotes $$$h$$$ divided by two, rounded down.
- Lightning Strike This spell will decrease the dragon's hit point by $$$10$$$. Assume that the dragon's current hit point is $$$h$$$, after casting this spell its hit point will be lowered to $$$h-10$$$.

Due to some reasons Kana can only cast no more than $$$n$$$ Void Absorptions and $$$m$$$ Lightning Strikes. She can cast the spells in any order and doesn't have to cast all the spells. Kana isn't good at math, so you are going to help her to find out whether it is possible to defeat the dragon.

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

The next $$$t$$$ lines describe test cases. For each test case the only line contains three integers $$$x$$$, $$$n$$$, $$$m$$$ ($$$1\le x \le 10^5$$$, $$$0\le n,m\le30$$$)  — the dragon's intitial hit point, the maximum number of Void Absorptions and Lightning Strikes Kana can cast respectively.

## Output Format
If it is possible to defeat the dragon, print "YES" (without quotes). Otherwise, print "NO" (without quotes).

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

## Examples
```input
7
100 3 4
189 3 4
64 2 3
63 2 3
30 27 7
10 9 1
69117 21 2
```
```output
YES
NO
NO
YES
YES
YES
YES
```

## Note
One possible casting sequence of the first test case is shown below:

- Void Absorption $$$\left\lfloor \frac{100}{2} \right\rfloor + 10=60$$$.
- Lightning Strike $$$60-10=50$$$.
- Void Absorption $$$\left\lfloor \frac{50}{2} \right\rfloor + 10=35$$$.
- Void Absorption $$$\left\lfloor \frac{35}{2} \right\rfloor + 10=27$$$.
- Lightning Strike $$$27-10=17$$$.
- Lightning Strike $$$17-10=7$$$.
- Lightning Strike $$$7-10=-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 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
Note that the only differences between easy and hard versions are the constraints on $$$n$$$ and the time limit. You can make hacks only if all versions are solved.

Slime is interested in sequences. He defined good positive integer sequences $$$p$$$ of length $$$n$$$ as follows:

- For each $$$k>1$$$ that presents in $$$p$$$, there should be at least one pair of indices $$$i,j$$$, such that $$$1 \leq i < j \leq n$$$, $$$p_i = k - 1$$$ and $$$p_j = k$$$.

For the given integer $$$n$$$, the set of all good sequences of length $$$n$$$ is $$$s_n$$$. For the fixed integer $$$k$$$ and the sequence $$$p$$$, let $$$f_p(k)$$$ be the number of times that $$$k$$$ appears in $$$p$$$. For each $$$k$$$ from $$$1$$$ to $$$n$$$, Slime wants to know the following value:

$$$$$$\left(\sum_{p\in s_n} f_p(k)\right)\ \textrm{mod}\ 998\,244\,353$$$$$$

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

## Output Format
Print $$$n$$$ integers, the $$$i$$$-th of them should be equal to $$$\left(\sum_{p\in s_n} f_p(i)\right)\ \textrm{mod}\ 998\,244\,353$$$.

## Examples
```input
2
```
```output
3 1
```
-----
```input
3
```
```output
10 7 1
```
-----
```input
1
```
```output
1
```

## Note
In the first example, $$$s=\{[1,1],[1,2]\}$$$.

In the second example, $$$s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}$$$.

In the third example, $$$s=\{[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
Find the minimum area of a square land on which you can place two identical rectangular $$$a \times b$$$ houses. The sides of the houses should be parallel to the sides of the desired square land.

Formally,

- You are given two identical rectangles with side lengths $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 100$$$) — positive integers (you are given just the sizes, but not their positions).
- Find the square of the minimum area that contains both given rectangles. Rectangles can be rotated (both or just one), moved, but the sides of the rectangles should be parallel to the sides of the desired square.

Two rectangles can touch each other (side or corner), but cannot intersect. Rectangles can also touch the sides of the square but must be completely inside it. You can rotate the rectangles. Take a look at the examples for a better understanding.

The picture shows a square that contains red and green rectangles.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) —the number of test cases in the input. Then $$$t$$$ test cases follow.

Each test case is a line containing two integers $$$a$$$, $$$b$$$ ($$$1 \le a, b \le 100$$$) — side lengths of the rectangles.

## Output Format
Print $$$t$$$ answers to the test cases. Each answer must be a single integer — minimal area of square land, that contains two rectangles with dimensions $$$a \times b$$$.

## Examples
```input
8
3 2
4 2
1 1
3 1
4 7
1 3
7 4
100 100
```
```output
16
16
4
9
64
9
64
40000
```

## Note
Below are the answers for the first two test cases:

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
There are $$$n$$$ athletes in front of you. Athletes are numbered from $$$1$$$ to $$$n$$$ from left to right. You know the strength of each athlete — the athlete number $$$i$$$ has the strength $$$s_i$$$.

You want to split all athletes into two teams. Each team must have at least one athlete, and each athlete must be exactly in one team.

You want the strongest athlete from the first team to differ as little as possible from the weakest athlete from the second team. Formally, you want to split the athletes into two teams $$$A$$$ and $$$B$$$ so that the value $$$|\max(A) - \min(B)|$$$ is as small as possible, where $$$\max(A)$$$ is the maximum strength of an athlete from team $$$A$$$, and $$$\min(B)$$$ is the minimum strength of an athlete from team $$$B$$$.

For example, if $$$n=5$$$ and the strength of the athletes is $$$s=[3, 1, 2, 6, 4]$$$, then one of the possible split into teams is:

- first team: $$$A = [1, 2, 4]$$$,
- second team: $$$B = [3, 6]$$$.

In this case, the value $$$|\max(A) - \min(B)|$$$ will be equal to $$$|4-3|=1$$$. This example illustrates one of the ways of optimal split into two teams.

Print the minimum value $$$|\max(A) - \min(B)|$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each test case consists of two lines.

The first line contains positive integer $$$n$$$ ($$$2 \le n \le 50$$$) — number of athletes.

The second line contains $$$n$$$ positive integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 1000$$$), where $$$s_i$$$ — is the strength of the $$$i$$$-th athlete. Please note that $$$s$$$ values may not be distinct.

## Output Format
For each test case print one integer — the minimum value of $$$|\max(A) - \min(B)|$$$ with the optimal split of all athletes into two teams. Each of the athletes must be a member of exactly one of the two teams.

## Examples
```input
5
5
3 1 2 6 4
6
2 1 3 2 4 3
4
7 9 3 1
2
1 1000
3
100 150 200
```
```output
1
0
2
999
50
```

## Note
The first test case was explained in the statement. In the second test case, one of the optimal splits is $$$A=[2, 1]$$$, $$$B=[3, 2, 4, 3]$$$, so the answer is $$$|2-2|=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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
We call two numbers $$$x$$$ and $$$y$$$ similar if they have the same parity (the same remainder when divided by $$$2$$$), or if $$$|x-y|=1$$$. For example, in each of the pairs $$$(2, 6)$$$, $$$(4, 3)$$$, $$$(11, 7)$$$, the numbers are similar to each other, and in the pairs $$$(1, 4)$$$, $$$(3, 12)$$$, they are not.

You are given an array $$$a$$$ of $$$n$$$ ($$$n$$$ is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other.

For example, for the array $$$a = [11, 14, 16, 12]$$$, there is a partition into pairs $$$(11, 12)$$$ and $$$(14, 16)$$$. The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even.

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

Each test case consists of two lines.

The first line contains an even positive integer $$$n$$$ ($$$2 \le n \le 50$$$) — length of array $$$a$$$.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$).

## Output Format
For each test case print:

- YES if the such a partition exists,
- NO otherwise.

The letters in the words YES and NO can be displayed in any case.

## Examples
```input
7
4
11 14 16 12
2
1 8
4
1 1 1 1
4
1 2 5 6
2
12 13
6
1 6 3 10 5 8
6
1 12 3 10 5 8
```
```output
YES
NO
YES
YES
YES
YES
NO
```

## Note
The first test case was explained in the statement.

In the second test case, the two given numbers are not similar.

In the third test case, any partition is suitable.

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 $$$n$$$ strings $$$a_1, a_2, \ldots, a_n$$$: all of them have the same length $$$m$$$. The strings consist of lowercase English letters.

Find any string $$$s$$$ of length $$$m$$$ such that each of the given $$$n$$$ strings differs from $$$s$$$ in at most one position. Formally, for each given string $$$a_i$$$, there is no more than one position $$$j$$$ such that $$$a_i[j] \ne s[j]$$$.

Note that the desired string $$$s$$$ may be equal to one of the given strings $$$a_i$$$, or it may differ from all the given strings.

For example, if you have the strings abac and zbab, then the answer to the problem might be the string abab, which differs from the first only by the last character, and from the second only by the first.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case starts with a line containing two positive integers $$$n$$$ ($$$1 \le n \le 10$$$) and $$$m$$$ ($$$1 \le m \le 10$$$) — the number of strings and their length.

Then follow $$$n$$$ strings $$$a_i$$$, one per line. Each of them has length $$$m$$$ and consists of lowercase English letters.

## Output Format
Print $$$t$$$ answers to the test cases. Each answer (if it exists) is a string of length $$$m$$$ consisting of lowercase English letters. If there are several answers, print any of them. If the answer does not exist, print "-1" ("minus one", without quotes).

## Examples
```input
5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c
```
```output
abab
-1
aaa
ab
z
```

## Note
The first test case was explained in the statement.

In the second test case, the answer does not exist.

Now solve the problem and return the code.