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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
When registering in a social network, users are allowed to create their own convenient login to make it easier to share contacts, print it on business cards, etc.

Login is an arbitrary sequence of lower and uppercase latin letters, digits and underline symbols («_»). However, in order to decrease the number of frauds and user-inattention related issues, it is prohibited to register a login if it is similar with an already existing login. More precisely, two logins s and t are considered similar if we can transform s to t via a sequence of operations of the following types:

- transform lowercase letters to uppercase and vice versa;
- change letter «O» (uppercase latin letter) to digit «0» and vice versa;
- change digit «1» (one) to any letter among «l» (lowercase latin «L»), «I» (uppercase latin «i») and vice versa, or change one of these letters to other.

For example, logins «Codeforces» and «codef0rces» as well as «OO0OOO00O0OOO0O00OOO0OO_lol» and «OO0OOO0O00OOO0O00OO0OOO_1oI» are considered similar whereas «Codeforces» and «Code_forces» are not.

You're given a list of existing logins with no two similar amonst and a newly created user login. Check whether this new login is similar with any of the existing ones.

## Input Format
The first line contains a non-empty string s consisting of lower and uppercase latin letters, digits and underline symbols («_») with length not exceeding 50  — the login itself.

The second line contains a single integer n (1 ≤ n ≤ 1 000) — the number of existing logins.

The next n lines describe the existing logins, following the same constraints as the user login (refer to the first line of the input). It's guaranteed that no two existing logins are similar.

## Output Format
Print «Yes» (without quotes), if user can register via this login, i.e. none of the existing logins is similar with it.

Otherwise print «No» (without quotes).

## Examples
```input
1_wat
2
2_wat
wat_1
```
```output
Yes
```
-----
```input
000
3
00
ooA
oOo
```
```output
No
```
-----
```input
_i_
3
__i_
_1_
I
```
```output
No
```
-----
```input
La0
3
2a0
La1
1a0
```
```output
No
```
-----
```input
abc
1
aBc
```
```output
No
```
-----
```input
0Lil
2
LIL0
0Ril
```
```output
Yes
```

## Note
In the second sample case the user wants to create a login consisting of three zeros. It's impossible due to collision with the third among the existing.

In the third sample case the new login is similar with the second one.

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
There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued over 10 years ago.

More formal, your message history is a sequence of messages ordered by time sent numbered from 1 to n where n is the total number of messages in the chat.

Each message might contain a link to an earlier message which it is a reply to. When opening a message x or getting a link to it, the dialogue is shown in such a way that k previous messages, message x and k next messages are visible (with respect to message x). In case there are less than k messages somewhere, they are yet all shown.

Digging deep into your message history, you always read all visible messages and then go by the link in the current message x (if there is one) and continue reading in the same manner.

Determine the number of messages you'll read if your start from message number t for all t from 1 to n. Calculate these numbers independently. If you start with message x, the initial configuration is x itself, k previous and k next messages. Messages read multiple times are considered as one.

## Input Format
The first line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ n) — the total amount of messages and the number of previous and next messages visible.

The second line features a sequence of integers a1, a2, ..., an (0 ≤ ai < i), where ai denotes the i-th message link destination or zero, if there's no link from i. All messages are listed in chronological order. It's guaranteed that the link from message x goes to message with number strictly less than x.

## Output Format
Print n integers with i-th denoting the number of distinct messages you can read starting from message i and traversing the links while possible.

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

## Note
Consider i = 6 in sample case one. You will read message 6, then 2, then 1 and then there will be no link to go.

In the second sample case i = 6 gives you messages 5, 6, 7 since k = 1, then 4, 5, 6, then 2, 3, 4 and then the link sequence breaks. The number of distinct messages here is equal to 6.

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
Everybody knows of spaghetti sort. You decided to implement an analog sorting algorithm yourself, but as you survey your pantry you realize you're out of spaghetti! The only type of pasta you have is ravioli, but you are not going to let this stop you...

You come up with the following algorithm. For each number in the array ai, build a stack of ai ravioli. The image shows the stack for ai = 4.

Arrange the stacks in one row in the order in which the corresponding numbers appear in the input array. Find the tallest one (if there are several stacks of maximal height, use the leftmost one). Remove it and add its height to the end of the output array. Shift the stacks in the row so that there is no gap between them. Repeat the procedure until all stacks have been removed.

At first you are very happy with your algorithm, but as you try it on more inputs you realize that it doesn't always produce the right sorted array. Turns out when two stacks of ravioli are next to each other (at any step of the process) and differ in height by two or more, the top ravioli of the taller stack slides down on top of the lower stack.

Given an input array, figure out whether the described algorithm will sort it correctly.

## Input Format
The first line of input contains a single number n (1 ≤ n ≤ 10) — the size of the array.

The second line of input contains n space-separated integers ai (1 ≤ ai ≤ 100) — the elements of the array.

## Output Format
Output "YES" if the array can be sorted using the described procedure and "NO" if it can not.

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

## Note
In the second example the array will change even before the tallest stack is chosen for the first time: ravioli from stack of height 3 will slide on the stack of height 1, and the algorithm will output an array {2, 2, 2}.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Not to be confused with chessboard.

## Input Format
The first line of input contains a single integer N (1 ≤ N ≤ 100) — the number of cheeses you have.

The next N lines describe the cheeses you have. Each line contains two space-separated strings: the name of the cheese and its type. The name is a string of lowercase English letters between 1 and 10 characters long. The type is either "soft" or "hard. All cheese names are distinct.

## Output Format
Output a single number.

## Examples
```input
9
brie soft
camembert soft
feta soft
goat soft
muenster soft
asiago hard
cheddar hard
gouda hard
swiss hard
```
```output
3
```
-----
```input
6
parmesan hard
emmental hard
edam hard
colby hard
gruyere hard
asiago hard
```
```output
4
```

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
One very experienced problem writer decided to prepare a problem for April Fools Day contest. The task was very simple - given an arithmetic expression, return the result of evaluating this expression. However, looks like there is a bug in the reference solution...

## Input Format
The only line of input data contains the arithmetic expression. The expression will contain between 2 and 10 operands, separated with arithmetic signs plus and/or minus. Each operand will be an integer between 0 and 255, inclusive.

## Output Format
Reproduce the output of the reference solution, including the bug.

## Examples
```input
8-7+6-5+4-3+2-1-0
```
```output
4
```
-----
```input
2+2
```
```output
-46
```
-----
```input
112-37
```
```output
375
```

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
Petya loves football very much. One day, as he was watching a football match, he was writing the players' current positions on a piece of paper. To simplify the situation he depicted it as a string consisting of zeroes and ones. A zero corresponds to players of one team; a one corresponds to players of another team. If there are at least 7 players of some team standing one after another, then the situation is considered dangerous. For example, the situation 00100110111111101 is dangerous and 11110111011101 is not. You are given the current situation. Determine whether it is dangerous or not.

## Input Format
The first input line contains a non-empty string consisting of characters "0" and "1", which represents players. The length of the string does not exceed 100 characters. There's at least one player from each team present on the field.

## Output Format
Print "YES" if the situation is dangerous. Otherwise, print "NO".

## Examples
```input
001001
```
```output
NO
```
-----
```input
1000000001
```
```output
YES
```

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
Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

One day Petya came across a positive integer n. Help him to find the least super lucky number which is not less than n.

## Input Format
The only line contains a positive integer n (1 ≤ n ≤ 109). This number doesn't have leading zeroes.

## Output Format
Output the least super lucky number that is more than or equal to n.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

## Examples
```input
4500
```
```output
4747
```
-----
```input
47
```
```output
47
```

Now solve the problem and return the code.