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
Карта звёздного неба представляет собой прямоугольное поле, состоящее из n строк по m символов в каждой строке. Каждый символ — это либо «.» (означает пустой участок неба), либо «*» (означает то, что в этом месте на небе есть звезда).

Новое издание карты звёздного неба будет напечатано на квадратных листах, поэтому требуется найти минимально возможную сторону квадрата, в который могут поместиться все звезды. Границы искомого квадрата должны быть параллельны сторонам заданного прямоугольного поля.

## Input Format
В первой строке входных данных записаны два числа n и m (1 ≤ n, m ≤ 1000) — количество строк и столбцов на карте звездного неба.

В следующих n строках задано по m символов. Каждый символ — это либо «.» (пустой участок неба), либо «*» (звезда).

Гарантируется, что на небе есть хотя бы одна звезда.

## Output Format
Выведите одно число — минимально возможную сторону квадрата, которым можно накрыть все звезды.

## Examples
```input
4 4
....
..*.
...*
..**
```
```output
3
```
-----
```input
1 3
*.*
```
```output
3
```
-----
```input
2 1
.
*
```
```output
1
```

## Note
Один из возможных ответов на первый тестовый пример:

Один из возможных ответов на второй тестовый пример (обратите внимание, что покрывающий квадрат выходит за пределы карты звездного неба):

Ответ на третий тестовый пример:

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
Limak is a little polar bear. He has n balls, the i-th ball has size ti.

Limak wants to give one ball to each of his three friends. Giving gifts isn't easy — there are two rules Limak must obey to make friends happy:

- No two friends can get balls of the same size.
- No two friends can get balls of sizes that differ by more than 2.

For example, Limak can choose balls with sizes 4, 5 and 3, or balls with sizes 90, 91 and 92. But he can't choose balls with sizes 5, 5 and 6 (two friends would get balls of the same size), and he can't choose balls with sizes 30, 31 and 33 (because sizes 30 and 33 differ by more than 2).

Your task is to check whether Limak can choose three balls that satisfy conditions above.

## Input Format
The first line of the input contains one integer n (3 ≤ n ≤ 50) — the number of balls Limak has.

The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 1000) where ti denotes the size of the i-th ball.

## Output Format
Print "YES" (without quotes) if Limak can choose three balls of distinct sizes, such that any two of them differ by no more than 2. Otherwise, print "NO" (without quotes).

## Examples
```input
4
18 55 16 17
```
```output
YES
```
-----
```input
6
40 41 43 44 44 44
```
```output
NO
```
-----
```input
8
5 972 3 4 1 4 970 971
```
```output
YES
```

## Note
In the first sample, there are 4 balls and Limak is able to choose three of them to satisfy the rules. He must must choose balls with sizes 18, 16 and 17.

In the second sample, there is no way to give gifts to three friends without breaking the rules.

In the third sample, there is even more than one way to choose balls:

1. Choose balls with sizes 3, 4 and 5.
2. Choose balls with sizes 972, 970, 971.

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
The life goes up and down, just like nice sequences. Sequence t1, t2, ..., tn is called nice if the following two conditions are satisfied:

- ti < ti + 1 for each odd i < n;
- ti > ti + 1 for each even i < n.

For example, sequences (2, 8), (1, 5, 1) and (2, 5, 1, 100, 99, 120) are nice, while (1, 1), (1, 2, 3) and (2, 5, 3, 2) are not.

Bear Limak has a sequence of positive integers t1, t2, ..., tn. This sequence is not nice now and Limak wants to fix it by a single swap. He is going to choose two indices i < j and swap elements ti and tj in order to get a nice sequence. Count the number of ways to do so. Two ways are considered different if indices of elements chosen for a swap are different.

## Input Format
The first line of the input contains one integer n (2 ≤ n ≤ 150 000) — the length of the sequence.

The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 150 000) — the initial sequence. It's guaranteed that the given sequence is not nice.

## Output Format
Print the number of ways to swap two elements exactly once in order to get a nice sequence.

## Examples
```input
5
2 8 4 7 7
```
```output
2
```
-----
```input
4
200 150 100 50
```
```output
1
```
-----
```input
10
3 2 1 4 1 4 1 4 1 4
```
```output
8
```
-----
```input
9
1 2 3 4 5 6 7 8 9
```
```output
0
```

## Note
In the first sample, there are two ways to get a nice sequence with one swap:

1. Swap t2 = 8 with t4 = 7.
2. Swap t1 = 2 with t5 = 7.

In the second sample, there is only one way — Limak should swap t1 = 200 with t4 = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A tree is a connected undirected graph consisting of n vertices and n  -  1 edges. Vertices are numbered 1 through n.

Limak is a little polar bear. He once had a tree with n vertices but he lost it. He still remembers something about the lost tree though.

You are given m pairs of vertices (a1, b1), (a2, b2), ..., (am, bm). Limak remembers that for each i there was no edge between ai and bi. He also remembers that vertex 1 was incident to exactly k edges (its degree was equal to k).

Is it possible that Limak remembers everything correctly? Check whether there exists a tree satisfying the given conditions.

## Input Format
The first line of the input contains three integers n, m and k ($$2 \leq n \leq 300 \, 000, \, 0 \leq m \leq \min(300 \, 000, \frac{n(n-1)}{2}), \, 1 \leq k \leq n - 1$$) — the number of vertices in Limak's tree, the number of forbidden pairs of vertices, and the degree of vertex 1, respectively.

The i-th of next m lines contains two distinct integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the i-th pair that is forbidden. It's guaranteed that each pair of vertices will appear at most once in the input.

## Output Format
Print "possible" (without quotes) if there exists at least one tree satisfying the given conditions. Otherwise, print "impossible" (without quotes).

## Examples
```input
5 4 2
1 2
2 3
4 2
4 1
```
```output
possible
```
-----
```input
6 5 3
1 2
1 3
1 4
1 5
1 6
```
```output
impossible
```

## Note
In the first sample, there are n = 5 vertices. The degree of vertex 1 should be k = 2. All conditions are satisfied for a tree with edges 1 - 5, 5 - 2, 1 - 3 and 3 - 4.

In the second sample, Limak remembers that none of the following edges existed: 1 - 2, 1 - 3, 1 - 4, 1 - 5 and 1 - 6. Hence, vertex 1 couldn't be connected to any other vertex and it implies that there is no suitable tree.

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

# Problem
Alex was programming while Valentina (his toddler daughter) got there and started asking many questions about the round brackets (or parenthesis) in the code. He explained her a bit and when she got it he gave her a task in order to finish his code on time.

For the purpose of this problem we consider only strings consisting of opening and closing round brackets, that is characters '(' and ')'.

The sequence of brackets is called correct if:

1. it's empty;
2. it's a correct sequence of brackets, enclosed in a pair of opening and closing brackets;
3. it's a concatenation of two correct sequences of brackets.

For example, the sequences "()()" and "((()))(())" are correct, while ")(()", "(((((" and "())" are not.

Alex took a piece of paper, wrote a string s consisting of brackets and asked Valentina to count the number of distinct non-empty substrings of s that are correct sequences of brackets. In other words, her task is to count the number of non-empty correct sequences of brackets that occur in a string s as a substring (don't mix up with subsequences).

When Valentina finished the task, Alex noticed he doesn't know the answer. Help him don't loose face in front of Valentina and solve the problem!

## Input Format
The first line of the input contains an integer n (1 ≤ n ≤ 500 000) — the length of the string s.

The second line contains a string s of length n consisting of only '(' and ')'.

## Output Format
Print the number of distinct non-empty correct sequences that occur in s as substring.

## Examples
```input
10
()()()()()
```
```output
5
```
-----
```input
7
)(())()
```
```output
3
```

## Note
In the first sample, there are 5 distinct substrings we should count: "()", "()()", "()()()", "()()()()" and "()()()()()".

In the second sample, there are 3 distinct substrings we should count: "()", "(())" and "(())()".

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 Petya has recently started attending a programming club. Naturally he is facing the problem of choosing a programming language. After long considerations he realized that Java is the best choice. The main argument in favor of choosing Java was that it has a very large integer data type, called BigInteger.

But having attended several classes of the club, Petya realized that not all tasks require using the BigInteger type. It turned out that in some tasks it is much easier to use small data types. That's why a question arises: "Which integer type to use if one wants to store a positive integer n?"

Petya knows only 5 integer types:

1) byte occupies 1 byte and allows you to store numbers from  - 128 to 127

2) short occupies 2 bytes and allows you to store numbers from  - 32768 to 32767

3) int occupies 4 bytes and allows you to store numbers from  - 2147483648 to 2147483647

4) long occupies 8 bytes and allows you to store numbers from  - 9223372036854775808 to 9223372036854775807

5) BigInteger can store any integer number, but at that it is not a primitive type, and operations with it are much slower.

For all the types given above the boundary values are included in the value range.

From this list, Petya wants to choose the smallest type that can store a positive integer n. Since BigInteger works much slower, Peter regards it last. Help him.

## Input Format
The first line contains a positive number n. It consists of no more than 100 digits and doesn't contain any leading zeros. The number n can't be represented as an empty string.

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).

## Output Format
Print the first type from the list "byte, short, int, long, BigInteger", that can store the natural number n, in accordance with the data given above.

## Examples
```input
127
```
```output
byte
```
-----
```input
130
```
```output
short
```
-----
```input
123456789101112131415161718192021222324
```
```output
BigInteger
```

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 Petya has a birthday soon. Due this wonderful event, Petya's friends decided to give him sweets. The total number of Petya's friends equals to n.

Let us remind you the definition of the greatest common divisor: GCD(a1, ..., ak) = d, where d represents such a maximal positive number that each ai (1 ≤ i ≤ k) is evenly divisible by d. At that, we assume that all ai's are greater than zero.

Knowing that Petya is keen on programming, his friends has agreed beforehand that the 1-st friend gives a1 sweets, the 2-nd one gives a2 sweets, ..., the n-th one gives an sweets. At the same time, for any i and j (1 ≤ i, j ≤ n) they want the GCD(ai, aj) not to be equal to 1. However, they also want the following condition to be satisfied: GCD(a1, a2, ..., an) = 1. One more: all the ai should be distinct.

Help the friends to choose the suitable numbers a1, ..., an.

## Input Format
The first line contains an integer n (2 ≤ n ≤ 50).

## Output Format
If there is no answer, print "-1" without quotes. Otherwise print a set of n distinct positive numbers a1, a2, ..., an. Each line must contain one number. Each number must consist of not more than 100 digits, and must not contain any leading zeros. If there are several solutions to that problem, print any of them.

Do not forget, please, that all of the following conditions must be true:

- For every i and j (1 ≤ i, j ≤ n): GCD(ai, aj) ≠ 1
- GCD(a1, a2, ..., an) = 1
- For every i and j (1 ≤ i, j ≤ n, i ≠ j): ai ≠ aj

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
3
```
```output
99
55
11115
```
-----
```input
4
```
```output
385
360
792
8360
```

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
Nicholas has an array a that contains n distinct integers from 1 to n. In other words, Nicholas has a permutation of size n.

Nicholas want the minimum element (integer 1) and the maximum element (integer n) to be as far as possible from each other. He wants to perform exactly one swap in order to maximize the distance between the minimum and the maximum elements. The distance between two elements is considered to be equal to the absolute difference between their positions.

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

The second line of the input contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n), where ai is equal to the element at the i-th position.

## Output Format
Print a single integer — the maximum possible distance between the minimum and the maximum elements Nicholas can achieve by performing exactly one swap.

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

## Note
In the first sample, one may obtain the optimal answer by swapping elements 1 and 2.

In the second sample, the minimum and the maximum elements will be located in the opposite ends of the array if we swap 7 and 2.

In the third sample, the distance between the minimum and the maximum elements is already maximum possible, so we just perform some unnecessary swap, for example, one can swap 5 and 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
High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?

## Input Format
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters 'a' and 'b' only.

## Output Format
Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.

## Examples
```input
4 2
abba
```
```output
4
```
-----
```input
8 1
aabaabaa
```
```output
5
```

## Note
In the first sample, Vasya can obtain both strings "aaaa" and "bbbb".

In the second sample, the optimal answer is obtained with the string "aaaaabaa" or with the string "aabaaaaa".

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
100 years have passed since the last victory of the man versus computer in Go. Technologies made a huge step forward and robots conquered the Earth! It's time for the final fight between human and robot that will decide the faith of the planet.

The following game was chosen for the fights: initially there is a polynomial

P(x) = anxn + an - 1xn - 1 + ... + a1x + a0,

Polynomial P(x) is said to be divisible by polynomial Q(x) if there exists a representation P(x) = B(x)Q(x), where B(x) is also some polynomial.

Some moves have been made already and now you wonder, is it true that human can guarantee the victory if he plays optimally?

## Input Format
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, |k| ≤ 10 000) — the size of the polynomial and the integer k.

The i-th of the following n + 1 lines contain character '?' if the coefficient near xi - 1 is yet undefined or the integer value ai, if the coefficient is already known ( - 10 000 ≤ ai ≤ 10 000). Each of integers ai (and even an) may be equal to 0.

Please note, that it's not guaranteed that you are given the position of the game where it's computer's turn to move.

## Output Format
Print "Yes" (without quotes) if the human has winning strategy, or "No" (without quotes) otherwise.

## Examples
```input
1 2
-1
?
```
```output
Yes
```
-----
```input
2 100
-10000
0
1
```
```output
Yes
```
-----
```input
4 5
?
1
?
1
?
```
```output
No
```

## Note
In the first sample, computer set a0 to  - 1 on the first move, so if human can set coefficient a1 to 0.5 and win.

In the second sample, all coefficients are already set and the resulting polynomial is divisible by x - 100, so the human has won.

Now solve the problem and return the code.