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

# Problem
One day a bear lived on the Oxy axis. He was afraid of the dark, so he couldn't move at night along the plane points that aren't lit. One day the bear wanted to have a night walk from his house at point (l, 0) to his friend's house at point (r, 0), along the segment of length (r - l). Of course, if he wants to make this walk, he needs each point of the segment to be lit. That's why the bear called his friend (and yes, in the middle of the night) asking for a very delicate favor.

The Oxy axis contains n floodlights. Floodlight i is at point (xi, yi) and can light any angle of the plane as large as ai degree with vertex at point (xi, yi). The bear asked his friend to turn the floodlights so that he (the bear) could go as far away from his house as possible during the walking along the segment. His kind friend agreed to fulfill his request. And while he is at it, the bear wonders: what is the furthest he can go away from his house? Hep him and find this distance.

Consider that the plane has no obstacles and no other light sources besides the floodlights. The bear's friend cannot turn the floodlights during the bear's walk. Assume that after all the floodlights are turned in the correct direction, the bear goes for a walk and his friend goes to bed.

## Input Format
The first line contains three space-separated integers n, l, r (1 ≤ n ≤ 20;  - 105 ≤ l ≤ r ≤ 105). The i-th of the next n lines contain three space-separated integers xi, yi, ai ( - 1000 ≤ xi ≤ 1000; 1 ≤ yi ≤ 1000; 1 ≤ ai ≤ 90) — the floodlights' description.

Note that two floodlights can be at the same point of the plane.

## Output Format
Print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

## Examples
```input
2 3 5
3 1 45
5 1 45
```
```output
2.000000000
```
-----
```input
1 0 1
1 1 30
```
```output
0.732050808
```
-----
```input
1 0 1
1 1 45
```
```output
1.000000000
```
-----
```input
1 0 2
0 2 90
```
```output
2.000000000
```

## Note
In the first sample, one of the possible solutions is:

In the second sample, a single solution is:

In the third sample, a single solution is:

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
User ainta is making a web site. This time he is going to make a navigation of the pages. In his site, there are n pages numbered by integers from 1 to n. Assume that somebody is on the p-th page now. The navigation will look like this:

<< p - k p - k + 1 ... p - 1 (p) p + 1 ... p + k - 1 p + k >>

When someone clicks the button "<<" he is redirected to page 1, and when someone clicks the button ">>" he is redirected to page n. Of course if someone clicks on a number, he is redirected to the corresponding page.

There are some conditions in the navigation:

- If page 1 is in the navigation, the button "<<" must not be printed.
- If page n is in the navigation, the button ">>" must not be printed.
- If the page number is smaller than 1 or greater than n, it must not be printed.

You can see some examples of the navigations. Make a program that prints the navigation.

## Input Format
The first and the only line contains three integers n, p, k (3 ≤ n ≤ 100; 1 ≤ p ≤ n; 1 ≤ k ≤ n)

## Output Format
Print the proper navigation. Follow the format of the output from the test samples.

## Examples
```input
17 5 2
```
```output
<< 3 4 (5) 6 7 >>
```
-----
```input
6 5 2
```
```output
<< 3 4 (5) 6
```
-----
```input
6 1 2
```
```output
(1) 2 3 >>
```
-----
```input
6 2 2
```
```output
1 (2) 3 4 >>
```
-----
```input
9 6 3
```
```output
<< 3 4 5 (6) 7 8 9
```
-----
```input
10 6 3
```
```output
<< 3 4 5 (6) 7 8 9 >>
```
-----
```input
8 5 4
```
```output
1 2 3 4 (5) 6 7 8
```

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
User ainta has a stack of n red and blue balls. He can apply a certain operation which changes the colors of the balls inside the stack.

- While the top ball inside the stack is red, pop the ball from the top of the stack.
- Then replace the blue ball on the top with a red ball.
- And finally push some blue balls to the stack until the stack has total of n balls inside.

If there are no blue balls inside the stack, ainta can't apply this operation. Given the initial state of the stack, ainta wants to know the maximum number of operations he can repeatedly apply.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 50) — the number of balls inside the stack.

The second line contains a string s (|s| = n) describing the initial state of the stack. The i-th character of the string s denotes the color of the i-th ball (we'll number the balls from top to bottom of the stack). If the character is "R", the color is red. If the character is "B", the color is blue.

## Output Format
Print the maximum number of operations ainta can repeatedly apply.

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

## Examples
```input
3
RBR
```
```output
2
```
-----
```input
4
RBBR
```
```output
6
```
-----
```input
5
RBBRR
```
```output
6
```

## Note
The first example is depicted below.

The explanation how user ainta applies the first operation. He pops out one red ball, changes the color of the ball in the middle from blue to red, and pushes one blue ball.

The explanation how user ainta applies the second operation. He will not pop out red balls, he simply changes the color of the ball on the top from blue to red.

From now on, ainta can't apply any operation because there are no blue balls inside the stack. ainta applied two operations, so the answer is 2.

The second example is depicted below. The blue arrow denotes a single operation.

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
Two teams meet in The Game World Championship. Some scientists consider this game to be the most intellectually challenging game in the world. You are given two strings describing the teams' actions in the final battle. Figure out who became the champion.

## Input Format
The input contains two strings of equal length (between 2 and 20 characters, inclusive). Each line describes the actions of one team.

## Output Format
Output "TEAM 1 WINS" if the first team won, "TEAM 2 WINS" if the second team won, and "TIE" if there was a tie.

## Examples
```input
[]()[]8<
8<[]()8<
```
```output
TEAM 2 WINS
```
-----
```input
8<8<()
[]8<[]
```
```output
TIE
```

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
Salve, mi amice.

Et tu quidem de lapis philosophorum. Barba non facit philosophum. Labor omnia vincit. Non potest creatio ex nihilo. Necesse est partibus.

Rp:

I Aqua Fortis

I Aqua Regia

II Amalgama

VII Minium

IV Vitriol

Misce in vitro et æstus, et nil admirari. Festina lente, et nulla tenaci invia est via.

Fac et spera,

Vale,

Nicolas Flamel

## Input Format
The first line of input contains several space-separated integers ai (0 ≤ ai ≤ 100).

## Output Format
Print a single integer.

## Examples
```input
2 4 6 8 10
```
```output
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
Little Petya wanted to give an April Fools Day present to some scientists. After some hesitation he decided to give them the array that he got as a present in Codeforces Round #153 (Div.2). The scientists rejoiced at the gift and decided to put some important facts to this array. Here are the first few of the facts:

- The highest mountain above sea level in the world is Mount Everest. Its peak rises to 8848 m.
- The largest board game tournament consisted of 958 participants playing chapaev.
- The largest online maths competition consisted of 12766 participants.
- The Nile is credited as the longest river in the world. From its farthest stream in Burundi, it extends 6695 km in length.
- While not in flood, the main stretches of the Amazon river in South America can reach widths of up to 1100 km at its widest points.
- Angel Falls is the highest waterfall. Its greatest single drop measures 807 m.
- The Hotel Everest View above Namche, Nepal — the village closest to Everest base camp – is at a record height of 31962 m
- Uranium is the heaviest of all the naturally occurring elements. Its most common isotope has a nucleus containing 146 neutrons.
- The coldest permanently inhabited place is the Siberian village of Oymyakon, where the temperature of -68°C was registered in the twentieth century.
- The longest snake held in captivity is over 25 feet long. Its name is Medusa.
- Colonel Meow holds the world record for longest fur on a cat — almost 134 centimeters.
- Sea otters can have up to 10000 hairs per square inch. This is the most dense fur in the animal kingdom.
- The largest state of USA is Alaska; its area is 663268 square miles
- Alaska has a longer coastline than all of the other 49 U.S. States put together: it is 154103 miles long.
- Lake Baikal is the largest freshwater lake in the world. It reaches 1642 meters in depth and contains around one-fifth of the world’s unfrozen fresh water.
- The most colorful national flag is the one of Turkmenistan, with 106 colors.

## Input Format
The input will contain a single integer between 1 and 16.

## Output Format
Output a single integer.

## Examples
```input
1
```
```output
1
```
-----
```input
7
```
```output
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
A + B is often used as an example of the easiest problem possible to show some contest platform. However, some scientists have observed that sometimes this problem is not so easy to get accepted. Want to try?

## Input Format
The input contains two integers a and b (0 ≤ a, b ≤ 103), separated by a single space.

## Output Format
Output the sum of the given integers.

## Examples
```input
5 14
```
```output
19
```
-----
```input
381 492
```
```output
873
```

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
Golorps are mysterious creatures who feed on variables. Golorp's name is a program in some programming language. Some scientists believe that this language is Befunge; golorps are tantalizingly silent.

Variables consumed by golorps can take values from 0 to 9, inclusive. For each golorp its daily diet is defined by its name. Some golorps are so picky that they can't be fed at all. Besides, all golorps are very health-conscious and try to eat as little as possible. Given a choice of several valid sequences of variable values, each golorp will choose lexicographically smallest one.

For the purposes of this problem you can assume that a golorp consists of jaws and a stomach. The number of variables necessary to feed a golorp is defined by the shape of its jaws. Variables can get to the stomach only via the jaws.

A hungry golorp is visiting you. You know its name; feed it or figure out that it's impossible.

## Input Format
The input is a single string (between 13 and 1024 characters long) — the name of the visiting golorp. All names are similar and will resemble the ones given in the samples. The name is guaranteed to be valid.

## Output Format
Output lexicographically smallest sequence of variable values fit for feeding this golorp. Values should be listed in the order in which they get into the jaws. If the golorp is impossible to feed, output "false".

## Examples
```input
?(_-_/___*__):-___>__.
```
```output
0010
```
-----
```input
?(__-_+_/_____):-__>__,_____<__.
```
```output
false
```
-----
```input
?(______________________/____+_______*__-_____*______-___):-__<___,___<____,____<_____,_____<______,______<_______.
```
```output
0250341
```
-----
```input
?(__+___+__-___):-___>__.
```
```output
0101
```

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
You have probably registered on Internet sites many times. And each time you should enter your invented password. Usually the registration form automatically checks the password's crypt resistance. If the user's password isn't complex enough, a message is displayed. Today your task is to implement such an automatic check.

Web-developers of the company Q assume that a password is complex enough, if it meets all of the following conditions:

- the password length is at least 5 characters;
- the password contains at least one large English letter;
- the password contains at least one small English letter;
- the password contains at least one digit.

You are given a password. Please implement the automatic check of its complexity for company Q.

## Input Format
The first line contains a non-empty sequence of characters (at most 100 characters). Each character is either a large English letter, or a small English letter, or a digit, or one of characters: "!", "?", ".", ",", "_".

## Output Format
If the password is complex enough, print message "Correct" (without the quotes), otherwise print message "Too weak" (without the quotes).

## Examples
```input
abacaba
```
```output
Too weak
```
-----
```input
X12345
```
```output
Too weak
```
-----
```input
CONTEST_is_STARTED!!11
```
```output
Correct
```

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 research center Q has developed a new multi-core processor. The processor consists of n cores and has k cells of cache memory. Consider the work of this processor.

At each cycle each core of the processor gets one instruction: either do nothing, or the number of the memory cell (the core will write an information to the cell). After receiving the command, the core executes it immediately. Sometimes it happens that at one cycle, multiple cores try to write the information into a single cell. Unfortunately, the developers did not foresee the possibility of resolving conflicts between cores, so in this case there is a deadlock: all these cores and the corresponding memory cell are locked forever. Each of the locked cores ignores all further commands, and no core in the future will be able to record an information into the locked cell. If any of the cores tries to write an information into some locked cell, it is immediately locked.

The development team wants to explore the deadlock situation. Therefore, they need a program that will simulate the processor for a given set of instructions for each core within m cycles . You're lucky, this interesting work is entrusted to you. According to the instructions, during the m cycles define for each core the number of the cycle, during which it will become locked. It is believed that initially all cores and all memory cells are not locked.

## Input Format
The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 100). Then follow n lines describing instructions. The i-th line contains m integers: xi1, xi2, ..., xim (0 ≤ xij ≤ k), where xij is the instruction that must be executed by the i-th core at the j-th cycle. If xij equals 0, then the corresponding instruction is «do nothing». But if xij is a number from 1 to k, then the corresponding instruction is «write information to the memory cell number xij».

We assume that the cores are numbered from 1 to n, the work cycles are numbered from 1 to m and the memory cells are numbered from 1 to k.

## Output Format
Print n lines. In the i-th line print integer ti. This number should be equal to 0 if the i-th core won't be locked, or it should be equal to the number of the cycle when this core will be locked.

## Examples
```input
4 3 5
1 0 0
1 0 2
2 3 1
3 2 0
```
```output
1
1
3
0
```
-----
```input
3 2 2
1 2
1 2
2 2
```
```output
1
1
0
```
-----
```input
1 1 1
0
```
```output
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
Mashmokh works in a factory. At the end of each day he must turn off all of the lights.

The lights on the factory are indexed from 1 to n. There are n buttons in Mashmokh's room indexed from 1 to n as well. If Mashmokh pushes button with index i, then each light with index not less than i that is still turned on turns off.

Mashmokh is not very clever. So instead of pushing the first button he pushes some of the buttons randomly each night. He pushed m distinct buttons b1, b2, ..., bm (the buttons were pushed consecutively in the given order) this night. Now he wants to know for each light the index of the button that turned this light off. Please note that the index of button bi is actually bi, not i.

Please, help Mashmokh, print these indices.

## Input Format
The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 100), the number of the factory lights and the pushed buttons respectively. The next line contains m distinct space-separated integers b1, b2, ..., bm (1 ≤ bi ≤ n).

It is guaranteed that all lights will be turned off after pushing all buttons.

## Output Format
Output n space-separated integers where the i-th number is index of the button that turns the i-th light off.

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

## Note
In the first sample, after pressing button number 4, lights 4 and 5 are turned off and lights 1, 2 and 3 are still on. Then after pressing button number 3, light number 3 is turned off as well. Pressing button number 1 turns off lights number 1 and 2 as well so pressing button number 2 in the end has no effect. Thus button number 4 turned lights 4 and 5 off, button number 3 turned light 3 off and button number 1 turned light 1 and 2 off.

Now solve the problem and return the code.