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

# Problem
So many wall designs to choose from! Even modulo 106 + 3, it's an enormous number. Given that recently Heidi acquired an unlimited supply of bricks, her choices are endless! She really needs to do something to narrow them down.

Heidi is quick to come up with criteria for a useful wall:

- In a useful wall, at least one segment is wider than W bricks. This should give the zombies something to hit their heads against. Or,
- in a useful wall, at least one column is higher than H bricks. This provides a lookout from which zombies can be spotted at a distance.

This should rule out a fair amount of possibilities, right? Help Heidi compute the number of useless walls that do not confirm to either of these criteria. In other words, a wall is useless if every segment has width at most W and height at most H.

Parameter C, the total width of the wall, has the same meaning as in the easy version. However, note that the number of bricks is now unlimited.

Output the number of useless walls modulo 106 + 3.

## Input Format
The first and the only line of the input contains three space-separated integers C, W and H (1 ≤ C ≤ 108, 1 ≤ W, H ≤ 100).

## Output Format
Output the number of different walls, modulo 106 + 3, which are useless according to Heidi's criteria.

## Examples
```input
1 1 1
```
```output
2
```
-----
```input
1 2 2
```
```output
3
```
-----
```input
1 2 3
```
```output
4
```
-----
```input
3 2 2
```
```output
19
```
-----
```input
5 4 9
```
```output
40951
```
-----
```input
40 37 65
```
```output
933869
```

## Note
If there is no brick in any of the columns, the structure is considered as a useless wall.

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
Dr. Bruce Banner hates his enemies (like others don't). As we all know, he can barely talk when he turns into the incredible Hulk. That's why he asked you to help him to express his feelings.

Hulk likes the Inception so much, and like that his feelings are complicated. They have n layers. The first layer is hate, second one is love, third one is hate and so on...

For example if n = 1, then his feeling is "I hate it" or if n = 2 it's "I hate that I love it", and if n = 3 it's "I hate that I love that I hate it" and so on.

Please help Dr. Banner.

## Input Format
The only line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of layers of love and hate.

## Output Format
Print Dr.Banner's feeling in one line.

## Examples
```input
1
```
```output
I hate it
```
-----
```input
2
```
```output
I hate that I love it
```
-----
```input
3
```
```output
I hate that I love that I hate it
```

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
Sometimes some words like "localization" or "internationalization" are so long that writing them many times in one text is quite tiresome.

Let's consider a word too long, if its length is strictly more than 10 characters. All too long words should be replaced with a special abbreviation.

This abbreviation is made like this: we write down the first and the last letter of a word and between them we write the number of letters between the first and the last letters. That number is in decimal system and doesn't contain any leading zeroes.

Thus, "localization" will be spelt as "l10n", and "internationalization» will be spelt as "i18n".

You are suggested to automatize the process of changing the words with abbreviations. At that all too long words should be replaced by the abbreviation and the words that are not too long should not undergo any changes.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 100). Each of the following n lines contains one word. All the words consist of lowercase Latin letters and possess the lengths of from 1 to 100 characters.

## Output Format
Print n lines. The i-th line should contain the result of replacing of the i-th word from the input data.

## Examples
```input
4
word
localization
internationalization
pneumonoultramicroscopicsilicovolcanoconiosis
```
```output
word
l10n
i18n
p43s
```

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
A progress bar is an element of graphical interface that displays the progress of a process for this very moment before it is completed. Let's take a look at the following form of such a bar.

A bar is represented as n squares, located in line. To add clarity, let's number them with positive integers from 1 to n from the left to the right. Each square has saturation (ai for the i-th square), which is measured by an integer from 0 to k. When the bar for some i (1 ≤ i ≤ n) is displayed, squares 1, 2, ... , i - 1 has the saturation k, squares i + 1, i + 2, ... , n has the saturation 0, and the saturation of the square i can have any value from 0 to k.

So some first squares of the progress bar always have the saturation k. Some last squares always have the saturation 0. And there is no more than one square that has the saturation different from 0 and k.

The degree of the process's completion is measured in percents. Let the process be t% completed. Then the following inequation is fulfilled:

$$\frac{\sum_{i=1}^{n} a_i}{nk} \leq \frac{t}{100} < \frac{(\sum_{i=1}^{n} a_i) + 1}{nk}$$

An example of such a bar can be seen on the picture.

For the given n, k, t determine the measures of saturation for all the squares ai of the progress bar.

## Input Format
We are given 3 space-separated integers n, k, t (1 ≤ n, k ≤ 100, 0 ≤ t ≤ 100).

## Output Format
Print n numbers. The i-th of them should be equal to ai.

## Examples
```input
10 10 54
```
```output
10 10 10 10 10 4 0 0 0 0
```
-----
```input
11 13 37
```
```output
13 13 13 13 0 0 0 0 0 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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
There are n knights sitting at the Round Table at an equal distance from each other. Each of them is either in a good or in a bad mood.

Merlin, the wizard predicted to King Arthur that the next month will turn out to be particularly fortunate if the regular polygon can be found. On all vertices of the polygon knights in a good mood should be located. Otherwise, the next month will bring misfortunes.

A convex polygon is regular if all its sides have same length and all his angles are equal. In this problem we consider only regular polygons with at least 3 vertices, i. e. only nondegenerated.

On a picture below some examples of such polygons are present. Green points mean knights in a good mood. Red points mean ones in a bad mood.

King Arthur knows the knights' moods. Help him find out if the next month will be fortunate or not.

## Input Format
The first line contains number n, which is the number of knights at the round table (3 ≤ n ≤ 105). The second line contains space-separated moods of all the n knights in the order of passing them around the table. "1" means that the knight is in a good mood an "0" means that he is in a bad mood.

## Output Format
Print "YES" without the quotes if the following month will turn out to be lucky. Otherwise, print "NO".

## Examples
```input
3
1 1 1
```
```output
YES
```
-----
```input
6
1 0 1 1 1 0
```
```output
YES
```
-----
```input
6
1 0 0 1 0 1
```
```output
NO
```

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
Every summer Vitya comes to visit his grandmother in the countryside. This summer, he got a huge wart. Every grandma knows that one should treat warts when the moon goes down. Thus, Vitya has to catch the moment when the moon is down.

Moon cycle lasts 30 days. The size of the visible part of the moon (in Vitya's units) for each day is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, and then cycle repeats, thus after the second 1 again goes 0.

As there is no internet in the countryside, Vitya has been watching the moon for n consecutive days and for each of these days he wrote down the size of the visible part of the moon. Help him find out whether the moon will be up or down next day, or this cannot be determined by the data he has.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 92) — the number of consecutive days Vitya was watching the size of the visible part of the moon.

The second line contains n integers ai (0 ≤ ai ≤ 15) — Vitya's records.

It's guaranteed that the input data is consistent.

## Output Format
If Vitya can be sure that the size of visible part of the moon on day n + 1 will be less than the size of the visible part on day n, then print "DOWN" at the only line of the output. If he might be sure that the size of the visible part will increase, then print "UP". If it's impossible to determine what exactly will happen with the moon, print -1.

## Examples
```input
5
3 4 5 6 7
```
```output
UP
```
-----
```input
7
12 13 14 15 14 13 12
```
```output
DOWN
```
-----
```input
1
8
```
```output
-1
```

## Note
In the first sample, the size of the moon on the next day will be equal to 8, thus the answer is "UP".

In the second sample, the size of the moon on the next day will be 11, thus the answer is "DOWN".

In the third sample, there is no way to determine whether the size of the moon on the next day will be 7 or 9, thus the answer is -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
Anatoly lives in the university dorm as many other students do. As you know, cockroaches are also living there together with students. Cockroaches might be of two colors: black and red. There are n cockroaches living in Anatoly's room.

Anatoly just made all his cockroaches to form a single line. As he is a perfectionist, he would like the colors of cockroaches in the line to alternate. He has a can of black paint and a can of red paint. In one turn he can either swap any two cockroaches, or take any single cockroach and change it's color.

Help Anatoly find out the minimum number of turns he needs to make the colors of cockroaches in the line alternate.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of cockroaches.

The second line contains a string of length n, consisting of characters 'b' and 'r' that denote black cockroach and red cockroach respectively.

## Output Format
Print one integer — the minimum number of moves Anatoly has to perform in order to make the colors of cockroaches in the line to alternate.

## Examples
```input
5
rbbrr
```
```output
1
```
-----
```input
5
bbbbb
```
```output
2
```
-----
```input
3
rbr
```
```output
0
```

## Note
In the first sample, Anatoly has to swap third and fourth cockroaches. He needs 1 turn to do this.

In the second sample, the optimum answer is to paint the second and the fourth cockroaches red. This requires 2 turns.

In the third sample, the colors of cockroaches in the line are alternating already, thus the answer is 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
Grigoriy, like the hero of one famous comedy film, found a job as a night security guard at the museum. At first night he received embosser and was to take stock of the whole exposition.

Embosser is a special devise that allows to "print" the text of a plastic tape. Text is printed sequentially, character by character. The device consists of a wheel with a lowercase English letters written in a circle, static pointer to the current letter and a button that print the chosen letter. At one move it's allowed to rotate the alphabetic wheel one step clockwise or counterclockwise. Initially, static pointer points to letter 'a'. Other letters are located as shown on the picture:

After Grigoriy add new item to the base he has to print its name on the plastic tape and attach it to the corresponding exhibit. It's not required to return the wheel to its initial position with pointer on the letter 'a'.

Our hero is afraid that some exhibits may become alive and start to attack him, so he wants to print the names as fast as possible. Help him, for the given string find the minimum number of rotations of the wheel required to print it.

## Input Format
The only line of input contains the name of some exhibit — the non-empty string consisting of no more than 100 characters. It's guaranteed that the string consists of only lowercase English letters.

## Output Format
Print one integer — the minimum number of rotations of the wheel, required to print the name given in the input.

## Examples
```input
zeus
```
```output
18
```
-----
```input
map
```
```output
35
```
-----
```input
ares
```
```output
34
```

## Note
To print the string from the first sample it would be optimal to perform the following sequence of rotations:

1. from 'a' to 'z' (1 rotation counterclockwise),
2. from 'z' to 'e' (5 clockwise rotations),
3. from 'e' to 'u' (10 rotations counterclockwise),
4. from 'u' to 's' (2 counterclockwise rotations).

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
The programming competition season has already started and it's time to train for ICPC. Sereja coaches his teams for a number of year and he knows that to get ready for the training session it's not enough to prepare only problems and editorial. As the training sessions lasts for several hours, teams become hungry. Thus, Sereja orders a number of pizzas so they can eat right after the end of the competition.

Teams plan to train for n times during n consecutive days. During the training session Sereja orders exactly one pizza for each team that is present this day. He already knows that there will be ai teams on the i-th day.

There are two types of discounts in Sereja's favourite pizzeria. The first discount works if one buys two pizzas at one day, while the second is a coupon that allows to buy one pizza during two consecutive days (two pizzas in total).

As Sereja orders really a lot of pizza at this place, he is the golden client and can use the unlimited number of discounts and coupons of any type at any days.

Sereja wants to order exactly ai pizzas on the i-th day while using only discounts and coupons. Note, that he will never buy more pizzas than he need for this particular day. Help him determine, whether he can buy the proper amount of pizzas each day if he is allowed to use only coupons and discounts. Note, that it's also prohibited to have any active coupons after the end of the day n.

## Input Format
The first line of input contains a single integer n (1 ≤ n ≤ 200 000) — the number of training sessions.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 10 000) — the number of teams that will be present on each of the days.

## Output Format
If there is a way to order pizzas using only coupons and discounts and do not buy any extra pizzas on any of the days, then print "YES" (without quotes) in the only line of output. Otherwise, print "NO" (without quotes).

## Examples
```input
4
1 2 1 2
```
```output
YES
```
-----
```input
3
1 0 1
```
```output
NO
```

## Note
In the first sample, Sereja can use one coupon to buy one pizza on the first and the second days, one coupon to buy pizza on the second and the third days and one discount to buy pizzas on the fourth days. This is the only way to order pizzas for this sample.

In the second sample, Sereja can't use neither the coupon nor the discount without ordering an extra pizza. Note, that it's possible that there will be no teams attending the training sessions on some days.

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
Once upon a time Petya and Gena gathered after another programming competition and decided to play some game. As they consider most modern games to be boring, they always try to invent their own games. They have only stickers and markers, but that won't stop them.

The game they came up with has the following rules. Initially, there are n stickers on the wall arranged in a row. Each sticker has some number written on it. Now they alternate turn, Petya moves first.

One move happens as follows. Lets say there are m ≥ 2 stickers on the wall. The player, who makes the current move, picks some integer k from 2 to m and takes k leftmost stickers (removes them from the wall). After that he makes the new sticker, puts it to the left end of the row, and writes on it the new integer, equal to the sum of all stickers he took on this move.

Game ends when there is only one sticker left on the wall. The score of the player is equal to the sum of integers written on all stickers he took during all his moves. The goal of each player is to maximize the difference between his score and the score of his opponent.

Given the integer n and the initial sequence of stickers on the wall, define the result of the game, i.e. the difference between the Petya's and Gena's score if both players play optimally.

## Input Format
The first line of input contains a single integer n (2 ≤ n ≤ 200 000) — the number of stickers, initially located on the wall.

The second line contains n integers a1, a2, ..., an ( - 10 000 ≤ ai ≤ 10 000) — the numbers on stickers in order from left to right.

## Output Format
Print one integer — the difference between the Petya's score and Gena's score at the end of the game if both players play optimally.

## Examples
```input
3
2 4 8
```
```output
14
```
-----
```input
4
1 -7 -2 3
```
```output
-3
```

## Note
In the first sample, the optimal move for Petya is to take all the stickers. As a result, his score will be equal to 14 and Gena's score will be equal to 0.

In the second sample, the optimal sequence of moves is the following. On the first move Petya will take first three sticker and will put the new sticker with value  - 8. On the second move Gena will take the remaining two stickers. The Petya's score is 1 + ( - 7) + ( - 2) =  - 8, Gena's score is ( - 8) + 3 =  - 5, i.e. the score difference will be  - 3.

Now solve the problem and return the code.