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
Polycarp loves geometric progressions — he collects them. However, as such progressions occur very rarely, he also loves the sequences of numbers where it is enough to delete a single element to get a geometric progression.

In this task we shall define geometric progressions as finite sequences of numbers a1, a2, ..., ak, where ai = c·bi - 1 for some real numbers c and b. For example, the sequences [2, -4, 8], [0, 0, 0, 0], [199] are geometric progressions and [0, 1, 2, 3] is not.

Recently Polycarp has found a sequence and he can't classify it. Help him to do it. Determine whether it is a geometric progression. If it is not, check if it can become a geometric progression if an element is deleted from it.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 105) — the number of elements in the given sequence. The second line contains the given sequence. The numbers are space-separated. All the elements of the given sequence are integers and their absolute value does not exceed 104.

## Output Format
Print 0, if the given sequence is a geometric progression. Otherwise, check if it is possible to make the sequence a geometric progression by deleting a single element. If it is possible, print 1. If it is impossible, print 2.

## Examples
```input
4
3 6 12 24
```
```output
0
```
-----
```input
4
-8 -16 24 -32
```
```output
1
```
-----
```input
4
0 1 2 3
```
```output
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: 10.0 seconds
Memory limit: 256.0 MB

# Problem
According to the last order issued by the president of Berland every city of the country must have its own Ministry Defense building (their own Pentagon). A megapolis Berbourg was not an exception. This city has n junctions, some pairs of which are connected by two-way roads. Overall there are m roads in the city, no more than one between each pair of junctions.

At the moment choosing a location place for Pentagon in Berbourg is being discussed. It has been decided that Pentagon should cover the territory of five different junctions which are joined into a cycle by roads. In the order to build Pentagon a special wall will be built along the roads (with high-tension razor, high-voltage wire and other attributes). Thus, the number of possible ways of building Pentagon in the city is equal to the number of different cycles at lengths of 5, composed of junctions and roads.

Your task is to prints the number of ways of building Pentagon in Berbourg. Only well-optimized solutions will be accepted. Please, test your code on the maximal testcase.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 700;0 ≤ m ≤ n·(n - 1) / 2), where n represents the number of junctions and m is the number of roads in the city. Then follow m lines containing the road descriptions, one in each line. Every road is set by a number of integers ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi), where ai and bi represent the numbers of junctions, connected by the road. The junctions are numbered from 1 to n. It is not guaranteed that from any junction one can get to any other one moving along the roads.

## Output Format
Print the single number which represents the required number of ways. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

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

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
An undirected graph is called a caterpillar if it is a connected graph without cycles and it has such a path p that any vertex is located at a distance of at most 1 from the path p. The caterpillar can contain loops (edges from a vertex to itself) but cannot contain multiple (parallel) edges.

The picture contains an example of a caterpillar:

You are given an undirected graph G. You are allowed to do a merging operations, each such operation merges two vertices into one vertex. For that two any vertices a and b (a ≠ b) are chosen. These verteces are deleted together with their edges (which are incident to at least one of the vertices a or b) but a new vertex w is added together with edges (x, w) for each edge (a, w) and/or (b, w). If there was the edge (a, b) it transforms to the loop (w, w). The resulting graph (after the merging operation) may contain multiple (parallel) edges between pairs of vertices and loops. Let us note that this operation decreases the number of vertices of graph by 1 but leaves the number of edges in the graph unchanged.

The merging operation can be informally described as a unity of two vertices of the graph into one with the natural transformation of the graph edges.

You may apply this operation consecutively and make the given graph to be a caterpillar. Write a program that will print the minimal number of merging operations required to make the given graph a caterpillar.

## Input Format
The first line contains a pair of integers n, m (1 ≤ n ≤ 2000;0 ≤ m ≤ 105), where n represents the number of vertices in the graph and m is the number of edges in it. Then the following m lines contain edge descriptions, one edge description per line. Every line contains a pair of integers ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi), ai, bi which represent the indices of the vertices connected by the edge. The vertices are numbered from 1 to n. In the given graph it will be no more than one edge between any pair of vertices. The given graph is not necessarily connected.

## Output Format
Print the minimal required number of operations.

## Examples
```input
4 4
1 2
2 3
3 4
4 2
```
```output
2
```
-----
```input
6 3
1 2
3 4
5 6
```
```output
2
```
-----
```input
7 6
1 2
2 3
1 4
4 5
1 6
6 7
```
```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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Little Tanya decided to present her dad a postcard on his Birthday. She has already created a message — string s of length n, consisting of uppercase and lowercase English letters. Tanya can't write yet, so she found a newspaper and decided to cut out the letters and glue them into the postcard to achieve string s. The newspaper contains string t, consisting of uppercase and lowercase English letters. We know that the length of string t greater or equal to the length of the string s.

The newspaper may possibly have too few of some letters needed to make the text and too many of some other letters. That's why Tanya wants to cut some n letters out of the newspaper and make a message of length exactly n, so that it looked as much as possible like s. If the letter in some position has correct value and correct letter case (in the string s and in the string that Tanya will make), then she shouts joyfully "YAY!", and if the letter in the given position has only the correct value but it is in the wrong case, then the girl says "WHOOPS".

Tanya wants to make such message that lets her shout "YAY!" as much as possible. If there are multiple ways to do this, then her second priority is to maximize the number of times she says "WHOOPS". Your task is to help Tanya make the message.

## Input Format
The first line contains line s (1 ≤ |s| ≤ 2·105), consisting of uppercase and lowercase English letters — the text of Tanya's message.

The second line contains line t (|s| ≤ |t| ≤ 2·105), consisting of uppercase and lowercase English letters — the text written in the newspaper.

Here |a| means the length of the string a.

## Output Format
Print two integers separated by a space:

- the first number is the number of times Tanya shouts "YAY!" while making the message,
- the second number is the number of times Tanya says "WHOOPS" while making the message.

## Examples
```input
AbC
DCbA
```
```output
3 0
```
-----
```input
ABC
abc
```
```output
0 3
```
-----
```input
abacaba
AbaCaBA
```
```output
3 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor.

Let's assume that n people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability p, or the first person in the queue doesn't move with probability (1 - p), paralyzed by his fear of escalators and making the whole queue wait behind him.

Formally speaking, the i-th person in the queue cannot enter the escalator until people with indices from 1 to i - 1 inclusive enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number of people standing on the escalator after t seconds.

Your task is to help him solve this complicated task.

## Input Format
The first line of the input contains three numbers n, p, t (1 ≤ n, t ≤ 2000, 0 ≤ p ≤ 1). Numbers n and t are integers, number p is real, given with exactly two digits after the decimal point.

## Output Format
Print a single real number — the expected number of people who will be standing on the escalator after t seconds. The absolute or relative error mustn't exceed 10 - 6.

## Examples
```input
1 0.50 1
```
```output
0.5
```
-----
```input
1 0.50 4
```
```output
0.9375
```
-----
```input
4 0.20 2
```
```output
0.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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
After bracket sequences Arthur took up number theory. He has got a new favorite sequence of length n (a1, a2, ..., an), consisting of integers and integer k, not exceeding n.

This sequence had the following property: if you write out the sums of all its segments consisting of k consecutive elements (a1  +  a2 ...  +  ak,  a2  +  a3  +  ...  +  ak + 1,  ...,  an - k + 1  +  an - k + 2  +  ...  +  an), then those numbers will form strictly increasing sequence.

For example, for the following sample: n = 5,  k = 3,  a = (1,  2,  4,  5,  6) the sequence of numbers will look as follows: (1  +  2  +  4,  2  +  4  +  5,  4  +  5  +  6) = (7,  11,  15), that means that sequence a meets the described property.

Obviously the sequence of sums will have n - k + 1 elements.

Somebody (we won't say who) replaced some numbers in Arthur's sequence by question marks (if this number is replaced, it is replaced by exactly one question mark). We need to restore the sequence so that it meets the required property and also minimize the sum |ai|, where |ai| is the absolute value of ai.

## Input Format
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105), showing how many numbers are in Arthur's sequence and the lengths of segments respectively.

The next line contains n space-separated elements ai (1 ≤ i ≤ n).

If ai  =  ?, then the i-th element of Arthur's sequence was replaced by a question mark.

Otherwise, ai ( - 109 ≤ ai ≤ 109) is the i-th element of Arthur's sequence.

## Output Format
If Arthur is wrong at some point and there is no sequence that could fit the given information, print a single string "Incorrect sequence" (without the quotes).

Otherwise, print n integers — Arthur's favorite sequence. If there are multiple such sequences, print the sequence with the minimum sum |ai|, where |ai| is the absolute value of ai. If there are still several such sequences, you are allowed to print any of them. Print the elements of the sequence without leading zeroes.

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

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

# Problem
On a certain meeting of a ruling party "A" minister Pavel suggested to improve the sewer system and to create a new pipe in the city.

The city is an n × m rectangular squared field. Each square of the field is either empty (then the pipe can go in it), or occupied (the pipe cannot go in such square). Empty squares are denoted by character '.', occupied squares are denoted by character '#'.

The pipe must meet the following criteria:

- the pipe is a polyline of width 1,
- the pipe goes in empty squares,
- the pipe starts from the edge of the field, but not from a corner square,
- the pipe ends at the edge of the field but not in a corner square,
- the pipe has at most 2 turns (90 degrees),
- the border squares of the field must share exactly two squares with the pipe,
- if the pipe looks like a single segment, then the end points of the pipe must lie on distinct edges of the field,
- for each non-border square of the pipe there are exacly two side-adjacent squares that also belong to the pipe,
- for each border square of the pipe there is exactly one side-adjacent cell that also belongs to the pipe.

Here are some samples of allowed piping routes:

Here are some samples of forbidden piping routes:

In these samples the pipes are represented by characters ' * '.

You were asked to write a program that calculates the number of distinct ways to make exactly one pipe in the city.

The two ways to make a pipe are considered distinct if they are distinct in at least one square.

## Input Format
The first line of the input contains two integers n, m (2 ≤ n, m ≤ 2000) — the height and width of Berland map.

Each of the next n lines contains m characters — the map of the city.

If the square of the map is marked by character '.', then the square is empty and the pipe can through it.

If the square of the map is marked by character '#', then the square is full and the pipe can't through it.

## Output Format
In the first line of the output print a single integer — the number of distinct ways to create a pipe.

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

## Note
In the first sample there are 3 ways to make a pipe (the squares of the pipe are marked by characters ' * '):

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
Many years have passed, and n friends met at a party again. Technologies have leaped forward since the last meeting, cameras with timer appeared and now it is not obligatory for one of the friends to stand with a camera, and, thus, being absent on the photo.

Simply speaking, the process of photographing can be described as follows. Each friend occupies a rectangle of pixels on the photo: the i-th of them in a standing state occupies a wi pixels wide and a hi pixels high rectangle. But also, each person can lie down for the photo, and then he will occupy a hi pixels wide and a wi pixels high rectangle.

The total photo will have size W × H, where W is the total width of all the people rectangles, and H is the maximum of the heights. The friends want to determine what minimum area the group photo can they obtain if no more than n / 2 of them can lie on the ground (it would be strange if more than n / 2 gentlemen lie on the ground together, isn't it?..)

Help them to achieve this goal.

## Input Format
The first line contains integer n (1 ≤ n ≤ 1000) — the number of friends.

The next n lines have two integers wi, hi (1 ≤ wi, hi ≤ 1000) each, representing the size of the rectangle, corresponding to the i-th friend.

## Output Format
Print a single integer equal to the minimum possible area of the photo containing all friends if no more than n / 2 of them can lie on the ground.

## Examples
```input
3
10 1
20 2
30 3
```
```output
180
```
-----
```input
3
3 1
2 2
4 3
```
```output
21
```
-----
```input
1
5 10
```
```output
50
```

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
Today Tavas got his test result as an integer score and he wants to share it with his girlfriend, Nafas.

His phone operating system is Tavdroid, and its keyboard doesn't have any digits! He wants to share his score with Nafas via text, so he has no choice but to send this number using words.

He ate coffee mix without water again, so right now he's really messed up and can't think.

Your task is to help him by telling him what to type.

## Input Format
The first and only line of input contains an integer s (0 ≤ s ≤ 99), Tavas's score.

## Output Format
In the first and only line of output, print a single string consisting only from English lowercase letters and hyphens ('-'). Do not use spaces.

## Examples
```input
6
```
```output
six
```
-----
```input
99
```
```output
ninety-nine
```
-----
```input
20
```
```output
twenty
```

## Note
You can find all you need to know about English numerals in http://en.wikipedia.org/wiki/English_numerals .

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 again Tavas started eating coffee mix without water! Keione told him that it smells awful, but he didn't stop doing that. That's why Keione told his smart friend, SaDDas to punish him! SaDDas took Tavas' headphones and told him: "If you solve the following problem, I'll return it to you."

The problem is:

You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

If we sort all lucky numbers in increasing order, what's the 1-based index of n?

Tavas is not as smart as SaDDas, so he asked you to do him a favor and solve this problem so he can have his headphones back.

## Input Format
The first and only line of input contains a lucky number n (1 ≤ n ≤ 109).

## Output Format
Print the index of n among all lucky numbers.

## Examples
```input
4
```
```output
1
```
-----
```input
7
```
```output
2
```
-----
```input
77
```
```output
6
```

Now solve the problem and return the code.