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
Blake is the boss of Kris, however, this doesn't spoil their friendship. They often gather at the bar to talk about intriguing problems about maximising some values. This time the problem is really special.

You are given an array a of length n. The characteristic of this array is the value $$c = \sum_{i=1}^{n} a_i \cdot i$$ — the sum of the products of the values ai by i. One may perform the following operation exactly once: pick some element of the array and move to any position. In particular, it's allowed to move the element to the beginning or to the end of the array. Also, it's allowed to put it back to the initial position. The goal is to get the array with the maximum possible value of characteristic.

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

The second line contains n integers ai (1 ≤ i ≤ n, |ai| ≤ 1 000 000) — the elements of the array a.

## Output Format
Print a single integer — the maximum possible value of characteristic of a that can be obtained by performing no more than one move.

## Examples
```input
4
4 3 2 5
```
```output
39
```
-----
```input
5
1 1 2 7 1
```
```output
49
```
-----
```input
3
1 1 2
```
```output
9
```

## Note
In the first sample, one may pick the first element and place it before the third (before 5). Thus, the answer will be 3·1 + 2·2 + 4·3 + 5·4 = 39.

In the second sample, one may pick the fifth element of the array and place it before the third. The answer will be 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49.

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
Карта звёздного неба представляет собой прямоугольное поле, состоящее из 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 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: 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 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: 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 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: 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 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
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 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
As you know, the game of "Nim" is played with n piles of stones, where the i-th pile initially contains ai stones. Two players alternate the turns. During a turn a player picks any non-empty pile and removes any positive number of stones from it. The one who is not able to make a move loses the game.

Petya and Vasya are tired of playing Nim, so they invented their own version of the game and named it the "Gambling Nim". They have n two-sided cards, one side of the i-th card has number ai written on it, while the other side has number bi. At the beginning of the game the players put all the cards on the table, each card only one of its sides up, and this side is chosen independently and uniformly. Thus they obtain a sequence c1, c2, ..., cn, where ci is equal to ai or bi. Then they take n piles of stones, with i-th pile containing exactly ci stones and play Nim. Petya takes the first turn.

Given that both players play optimally, find the probability of Petya's victory. Output the answer as an irreducible fraction.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of cards in the deck.

Each of the following n lines contains the description of one card, consisting of two integers ai and bi (0 ≤ ai, bi ≤ 1018).

## Output Format
Output the answer as an irreducible fraction p / q. If the probability of Petya's victory is 0, print 0/1.

## Examples
```input
2
1 1
1 1
```
```output
0/1
```
-----
```input
2
1 2
1 2
```
```output
1/2
```
-----
```input
3
0 4
1 5
2 3
```
```output
1/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
Ted has a pineapple. This pineapple is able to bark like a bulldog! At time t (in seconds) it barks for the first time. Then every s seconds after it, it barks twice with 1 second interval. Thus it barks at times t, t + s, t + s + 1, t + 2s, t + 2s + 1, etc.

Barney woke up in the morning and wants to eat the pineapple, but he can't eat it when it's barking. Barney plans to eat it at time x (in seconds), so he asked you to tell him if it's gonna bark at that time.

## Input Format
The first and only line of input contains three integers t, s and x (0 ≤ t, x ≤ 109, 2 ≤ s ≤ 109) — the time the pineapple barks for the first time, the pineapple barking interval, and the time Barney wants to eat the pineapple respectively.

## Output Format
Print a single "YES" (without quotes) if the pineapple will bark at time x or a single "NO" (without quotes) otherwise in the only line of output.

## Examples
```input
3 10 4
```
```output
NO
```
-----
```input
3 10 3
```
```output
YES
```
-----
```input
3 8 51
```
```output
YES
```
-----
```input
3 8 52
```
```output
YES
```

## Note
In the first and the second sample cases pineapple will bark at moments 3, 13, 14, ..., so it won't bark at the moment 4 and will bark at the moment 3.

In the third and fourth sample cases pineapple will bark at moments 3, 11, 12, 19, 20, 27, 28, 35, 36, 43, 44, 51, 52, 59, ..., so it will bark at both moments 51 and 52.

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
Barney is standing in a bar and starring at a pretty girl. He wants to shoot her with his heart arrow but he needs to know the distance between him and the girl to make his shot accurate.

Barney asked the bar tender Carl about this distance value, but Carl was so busy talking to the customers so he wrote the distance value (it's a real number) on a napkin. The problem is that he wrote it in scientific notation. The scientific notation of some real number x is the notation of form AeB, where A is a real number and B is an integer and x = A × 10B is true. In our case A is between 0 and 9 and B is non-negative.

Barney doesn't know anything about scientific notation (as well as anything scientific at all). So he asked you to tell him the distance value in usual decimal representation with minimal number of digits after the decimal point (and no decimal point if it is an integer). See the output format for better understanding.

## Input Format
The first and only line of input contains a single string of form a.deb where a, d and b are integers and e is usual character 'e' (0 ≤ a ≤ 9, 0 ≤ d < 10100, 0 ≤ b ≤ 100) — the scientific notation of the desired distance value.

a and b contain no leading zeros and d contains no trailing zeros (but may be equal to 0). Also, b can not be non-zero if a is zero.

## Output Format
Print the only real number x (the desired distance value) in the only line in its decimal notation.

Thus if x is an integer, print it's integer value without decimal part and decimal point and without leading zeroes.

Otherwise print x in a form of p.q such that p is an integer that have no leading zeroes (but may be equal to zero), and q is an integer that have no trailing zeroes (and may not be equal to zero).

## Examples
```input
8.549e2
```
```output
854.9
```
-----
```input
8.549e3
```
```output
8549
```
-----
```input
0.33e0
```
```output
0.33
```

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
Vasiliy lives at point (a, b) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested n available Beru-taxi nearby. The i-th taxi is located at point (xi, yi) and moves with a speed vi.

Consider that each of n drivers will move directly to Vasiliy and with a maximum possible speed. Compute the minimum time when Vasiliy will get in any of Beru-taxi cars.

## Input Format
The first line of the input contains two integers a and b ( - 100 ≤ a, b ≤ 100) — coordinates of Vasiliy's home.

The second line contains a single integer n (1 ≤ n ≤ 1000) — the number of available Beru-taxi cars nearby.

The i-th of the following n lines contains three integers xi, yi and vi ( - 100 ≤ xi, yi ≤ 100, 1 ≤ vi ≤ 100) — the coordinates of the i-th car and its speed.

It's allowed that several cars are located at the same point. Also, cars may be located at exactly the same point where Vasiliy lives.

## Output Format
Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

## Examples
```input
0 0
2
2 0 1
0 2 2
```
```output
1.00000000000000000000
```
-----
```input
1 3
3
3 3 2
-2 3 6
-2 7 10
```
```output
0.50000000000000000000
```

## Note
In the first sample, first taxi will get to Vasiliy in time 2, and second will do this in time 1, therefore 1 is the answer.

In the second sample, cars 2 and 3 will arrive simultaneously.

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
There are three friend living on the straight line Ox in Lineland. The first friend lives at the point x1, the second friend lives at the point x2, and the third friend lives at the point x3. They plan to celebrate the New Year together, so they need to meet at one point. What is the minimum total distance they have to travel in order to meet at some point and celebrate the New Year?

It's guaranteed that the optimal answer is always integer.

## Input Format
The first line of the input contains three distinct integers x1, x2 and x3 (1 ≤ x1, x2, x3 ≤ 100) — the coordinates of the houses of the first, the second and the third friends respectively.

## Output Format
Print one integer — the minimum total distance the friends need to travel in order to meet together.

## Examples
```input
7 1 4
```
```output
6
```
-----
```input
30 20 10
```
```output
20
```

## Note
In the first sample, friends should meet at the point 4. Thus, the first friend has to travel the distance of 3 (from the point 7 to the point 4), the second friend also has to travel the distance of 3 (from the point 1 to the point 4), while the third friend should not go anywhere because he lives at the point 4.

Now solve the problem and return the code.