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
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 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
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 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: 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 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
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 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
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 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
A group of n friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the i-th friend is ri.

The friends decided to take part in the championship as a team. But they should have equal ratings to be allowed to compose a single team consisting of all n friends. So the friends are faced with the problem: how to make all their ratings equal.

One way to change ratings is to willingly lose in some matches. Friends can form a party consisting of two to five (but not more than n) friends and play a match in the game. When the party loses, the rating of each of its members decreases by 1. A rating can't become negative, so ri = 0 doesn't change after losing.

The friends can take part in multiple matches, each time making a party from any subset of friends (but remember about constraints on party size: from 2 to 5 members).

The friends want to make their ratings equal but as high as possible.

Help the friends develop a strategy of losing the matches so that all their ratings become equal and the resulting rating is maximum possible.

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 100) — the number of friends.

The second line contains n non-negative integers r1, r2, ..., rn (0 ≤ ri ≤ 100), where ri is the initial rating of the i-th friend.

## Output Format
In the first line, print a single integer R — the final rating of each of the friends.

In the second line, print integer t — the number of matches the friends have to play. Each of the following t lines should contain n characters '0' or '1', where the j-th character of the i-th line is equal to:

- '0', if friend j should not play in match i,
- '1', if friend j should play in match i.

Each line should contain between two and five characters '1', inclusive.

The value t should not exceed 104, it is guaranteed that such solution exists.

Remember that you shouldn't minimize the value t, but you should maximize R. If there are multiple solutions, print any of them.

## Examples
```input
5
4 5 1 7 4
```
```output
1
8
01010
00011
01010
10010
00011
11000
00011
11000
```
-----
```input
2
1 2
```
```output
0
2
11
11
```
-----
```input
3
1 1 1
```
```output
1
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 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: 512.0 MB

# Problem
Polycarp is a regular customer at the restaurant "Ber Patio". He likes having lunches there.

"Ber Patio" has special discount program for regular customers. A customer can collect bonuses and partially cover expenses in the restaurant.

Let's assume a customer currently has b bonuses and she has to pay r burles for a lunch. In this case the customer can use bonuses (1 bonus = 1 burle) to reduce the payment. She can cover at most half of the payment using bonuses. However, 1 bonus will be added to the customer's bonus balance per each 10 burles she paid.

Formally:

1. a customer can choose any number x of bonuses to use ($$0 \leq x \leq \min(b, \left\lfloor \frac{r}{2} \right\rfloor)$$)),
2. the customer's bonus balance is reduced by x,
3. the customer pays r - x burles,
4. the customer's bonus balance is increased by ⌊(r - x) / 10⌋ (i.e. integer division rounded down is used).

Initially, there are b bonuses on Polycarp's account. Polycarp is going to have a lunch in "Ber Patio" for the next n days. He estimated the values a1, a2, ..., an, where ai is the number of burles in a receipt for the i-th day. The sum over all receipts doesn't exceed 105 burles.

Write a program to find the minimum number of burles Polycarp has to spend and an optimal strategy to use bonuses.

## Input Format
The first line contains two integer numbers n and b (1 ≤ n ≤ 5000, 0 ≤ b ≤ 105) — number of days and initial number of bonuses Polycarp has.

The second line contains the integer sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai is the amount of burles in the i-th day's receipt.

It is guaranteed that the sum of all receipts does not exceed 105 burles.

## Output Format
On the first line, print the expected minimal number of burles to pay for all n receipts.

On the second line, print the sequence of integer numbers b1, b2, ..., bn, where bi is the number of bonuses to use on the i-th day. If there are multiple solutions, print any of them.

## Examples
```input
3 21
12 75 52
```
```output
110
2 5 22
```
-----
```input
3 39
58 64 33
```
```output
107
28 4 16
```

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
Polycarp starts his own business. Tomorrow will be the first working day of his car repair shop. For now the car repair shop is very small and only one car can be repaired at a given time.

Polycarp is good at marketing, so he has already collected n requests from clients. The requests are numbered from 1 to n in order they came.

The i-th request is characterized by two values: si — the day when a client wants to start the repair of his car, di — duration (in days) to repair the car. The days are enumerated from 1, the first day is tomorrow, the second day is the day after tomorrow and so on.

Polycarp is making schedule by processing requests in the order from the first to the n-th request. He schedules the i-th request as follows:

- If the car repair shop is idle for di days starting from si (si, si + 1, ..., si + di - 1), then these days are used to repair a car of the i-th client.
- Otherwise, Polycarp finds the first day x (from 1 and further) that there are di subsequent days when no repair is scheduled starting from x. In other words he chooses the smallest positive x that all days x, x + 1, ..., x + di - 1 are not scheduled for repair of any car. So, the car of the i-th client will be repaired in the range [x, x + di - 1]. It is possible that the day x when repair is scheduled to start will be less than si.

Given n requests, you are asked to help Polycarp schedule all of them according to the rules above.

## Input Format
The first line contains integer n (1 ≤ n ≤ 200) — the number of requests from clients.

The following n lines contain requests, one request per line. The i-th request is given as the pair of integers si, di (1 ≤ si ≤ 109, 1 ≤ di ≤ 5·106), where si is the preferred time to start repairing the i-th car, di is the number of days to repair the i-th car.

The requests should be processed in the order they are given in the input.

## Output Format
Print n lines. The i-th line should contain two integers — the start day to repair the i-th car and the finish day to repair the i-th car.

## Examples
```input
3
9 2
7 3
2 4
```
```output
9 10
1 3
4 7
```
-----
```input
4
1000000000 1000000
1000000000 1000000
100000000 1000000
1000000000 1000000
```
```output
1000000000 1000999999
1 1000000
100000000 100999999
1000001 2000000
```

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
Polycarp is a beginner programmer. He is studying how to use a command line.

Polycarp faced the following problem. There are n files in a directory and he needs to delete some of them. Polycarp wants to run a single delete command with filename pattern as an argument. All the files to be deleted should match the pattern and all other files shouldn't match the pattern.

Polycarp doesn't know about an asterisk '*', the only special character he knows is a question mark '?' which matches any single character. All other characters in the pattern match themselves only.

Formally, a pattern matches a filename if and only if they have equal lengths and all characters in the corresponding positions are equal except when the character in the pattern is '?', in which case the corresponding filename character does not matter.

For example, the filename pattern "a?ba?":

- matches filenames "aabaa", "abba.", "a.ba9" and "a.ba.";
- does not match filenames "aaba", "abaab", "aabaaa" and "aabaa.".

Help Polycarp find a pattern which matches files to be deleted and only them or report if there is no such pattern.

## Input Format
The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 100) — the total number of files and the number of files to be deleted.

The following n lines contain filenames, single filename per line. All filenames are non-empty strings containing only lowercase English letters, digits and dots ('.'). The length of each filename doesn't exceed 100. It is guaranteed that all filenames are distinct.

The last line of the input contains m distinct integer numbers in ascending order a1, a2, ..., am (1 ≤ ai ≤ n) — indices of files to be deleted. All files are indexed from 1 to n in order of their appearance in the input.

## Output Format
If the required pattern exists, print "Yes" in the first line of the output. The second line should contain the required pattern. If there are multiple solutions, print any of them.

If the required pattern doesn't exist, print the only line containing "No".

## Examples
```input
3 2
ab
ac
cd
1 2
```
```output
Yes
a?
```
-----
```input
5 3
test
tezt
test.
.est
tes.
1 4 5
```
```output
Yes
?es?
```
-----
```input
4 4
a
b
c
dd
1 2 3 4
```
```output
No
```
-----
```input
6 3
.svn
.git
....
...
..
.
1 2 3
```
```output
Yes
.???
```

Now solve the problem and return the code.