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
Victor tries to write his own text editor, with word correction included. However, the rules of word correction are really strange.

Victor thinks that if a word contains two consecutive vowels, then it's kinda weird and it needs to be replaced. So the word corrector works in such a way: as long as there are two consecutive vowels in the word, it deletes the first vowel in a word such that there is another vowel right before it. If there are no two consecutive vowels in the word, it is considered to be correct.

You are given a word s. Can you predict what will it become after correction?

In this problem letters a, e, i, o, u and y are considered to be vowels.

## Input Format
The first line contains one integer n (1 ≤ n ≤ 100) — the number of letters in word s before the correction.

The second line contains a string s consisting of exactly n lowercase Latin letters — the word before the correction.

## Output Format
Output the word s after the correction.

## Examples
```input
5
weird
```
```output
werd
```
-----
```input
4
word
```
```output
word
```
-----
```input
5
aaeaa
```
```output
a
```

## Note
Explanations of the examples:

1. There is only one replace: weird $$\rightarrow$$ werd;
2. No replace needed since there are no two consecutive vowels;
3. aaeaa $$\rightarrow$$ aeaa $$\rightarrow$$ aaa $$\rightarrow$$ aa $$\rightarrow$$ a.

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 and your friend are participating in a TV show "Run For Your Prize".

At the start of the show n prizes are located on a straight line. i-th prize is located at position ai. Positions of all prizes are distinct. You start at position 1, your friend — at position 106 (and there is no prize in any of these two positions). You have to work as a team and collect all prizes in minimum possible time, in any order.

You know that it takes exactly 1 second to move from position x to position x + 1 or x - 1, both for you and your friend. You also have trained enough to instantly pick up any prize, if its position is equal to your current position (and the same is true for your friend). Carrying prizes does not affect your speed (or your friend's speed) at all.

Now you may discuss your strategy with your friend and decide who will pick up each prize. Remember that every prize must be picked up, either by you or by your friend.

What is the minimum number of seconds it will take to pick up all the prizes?

## Input Format
The first line contains one integer n (1 ≤ n ≤ 105) — the number of prizes.

The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 106 - 1) — the positions of the prizes. No two prizes are located at the same position. Positions are given in ascending order.

## Output Format
Print one integer — the minimum number of seconds it will take to collect all prizes.

## Examples
```input
3
2 3 9
```
```output
8
```
-----
```input
2
2 999995
```
```output
5
```

## Note
In the first example you take all the prizes: take the first at 1, the second at 2 and the third at 8.

In the second example you take the first prize in 1 second and your friend takes the other in 5 seconds, you do this simultaneously, so the total time is 5.

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
Let's denote a m-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size m × m of this matrix contains at least one zero.

Consider the following problem:

You are given two integers n and m. You have to construct an m-free square matrix of size n × n such that the number of 1's in this matrix is maximum possible. Print the maximum possible number of 1's in such matrix.

You don't have to solve this problem. Instead, you have to construct a few tests for it.

You will be given t numbers x1, x2, ..., xt. For every $$i \in [1,t]$$, find two integers ni and mi (ni ≥ mi) such that the answer for the aforementioned problem is exactly xi if we set n = ni and m = mi.

## Input Format
The first line contains one integer t (1 ≤ t ≤ 100) — the number of tests you have to construct.

Then t lines follow, i-th line containing one integer xi (0 ≤ xi ≤ 109).

Note that in hacks you have to set t = 1.

## Output Format
For each test you have to construct, output two positive numbers ni and mi (1 ≤ mi ≤ ni ≤ 109) such that the maximum number of 1's in a mi-free ni × ni matrix is exactly xi. If there are multiple solutions, you may output any of them; and if this is impossible to construct a test, output a single integer  - 1.

## Examples
```input
3
21
0
1
```
```output
5 2
1 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 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: 256.0 MB

# Problem
You are given an array a of length n. We define fa the following way:

- Initially fa = 0, M = 1;
- for every 2 ≤ i ≤ n if aM < ai then we set fa = fa + aM and then set M = i.

Calculate the sum of fa over all n! permutations of the array a modulo 109 + 7.

Note: two elements are considered different if their indices differ, so for every array a there are exactly n! permutations.

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

Second line contains n integers a1, a2, ..., an (1 ≤  ai ≤  109).

## Output Format
Print the only integer, the sum of fa over all n! permutations of the array a modulo 109 + 7.

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

## Note
For the second example all the permutations are:

- p = [1, 2, 3] : fa is equal to 1;
- p = [1, 3, 2] : fa is equal to 1;
- p = [2, 1, 3] : fa is equal to 1;
- p = [2, 3, 1] : fa is equal to 1;
- p = [3, 1, 2] : fa is equal to 0;
- p = [3, 2, 1] : fa is equal to 0.

Where p is the array of the indices of initial array a. The sum of fa is equal to 4.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a sequence a consisting of n integers. You may partition this sequence into two sequences b and c in such a way that every element belongs exactly to one of these sequences.

Let B be the sum of elements belonging to b, and C be the sum of elements belonging to c (if some of these sequences is empty, then its sum is 0). What is the maximum possible value of B - C?

## Input Format
The first line contains one integer n (1 ≤ n ≤ 100) — the number of elements in a.

The second line contains n integers a1, a2, ..., an ( - 100 ≤ ai ≤ 100) — the elements of sequence a.

## Output Format
Print the maximum possible value of B - C, where B is the sum of elements of sequence b, and C is the sum of elements of sequence c.

## Examples
```input
3
1 -2 0
```
```output
3
```
-----
```input
6
16 23 16 15 42 8
```
```output
120
```

## Note
In the first example we may choose b = {1, 0}, c = { - 2}. Then B = 1, C =  - 2, B - C = 3.

In the second example we choose b = {16, 23, 16, 15, 42, 8}, c = {} (an empty sequence). Then B = 120, C = 0, B - C = 120.

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 two variables a and b. Consider the following sequence of actions performed with these variables:

1. If a = 0 or b = 0, end the process. Otherwise, go to step 2;
2. If a ≥ 2·b, then set the value of a to a - 2·b, and repeat step 1. Otherwise, go to step 3;
3. If b ≥ 2·a, then set the value of b to b - 2·a, and repeat step 1. Otherwise, end the process.

Initially the values of a and b are positive integers, and so the process will be finite.

You have to determine the values of a and b after the process ends.

## Input Format
The only line of the input contains two integers n and m (1 ≤ n, m ≤ 1018). n is the initial value of variable a, and m is the initial value of variable b.

## Output Format
Print two integers — the values of a and b after the end of the process.

## Examples
```input
12 5
```
```output
0 1
```
-----
```input
31 12
```
```output
7 12
```

## Note
Explanations to the samples:

1. a = 12, b = 5 $$\rightarrow$$ a = 2, b = 5 $$\rightarrow$$ a = 2, b = 1 $$\rightarrow$$ a = 0, b = 1;
2. a = 31, b = 12 $$\rightarrow$$ a = 7, b = 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Yes, that's another problem with definition of "beautiful" numbers.

Let's call a positive integer x beautiful if its decimal representation without leading zeroes contains even number of digits, and there exists a permutation of this representation which is palindromic. For example, 4242 is a beautiful number, since it contains 4 digits, and there exists a palindromic permutation 2442.

Given a positive integer s, find the largest beautiful number which is less than s.

## Input Format
The first line contains one integer t (1 ≤ t ≤ 105) — the number of testcases you have to solve.

Then t lines follow, each representing one testcase and containing one string which is the decimal representation of number s. It is guaranteed that this string has even length, contains no leading zeroes, and there exists at least one beautiful number less than s.

The sum of lengths of s over all testcases doesn't exceed 2·105.

## Output Format
For each testcase print one line containing the largest beautiful number which is less than s (it is guaranteed that the answer exists).

## Examples
```input
4
89
88
1000
28923845
```
```output
88
77
99
28923839
```

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

# Problem
You are given a binary string s (each character of this string is either 0 or 1).

Let's denote the cost of string t as the number of occurences of s in t. For example, if s is 11 and t is 111011, then the cost of t is 3.

Let's also denote the Fibonacci strings sequence as follows:

- F(0) is 0;
- F(1) is 1;
- F(i) = F(i - 1) + F(i - 2) if i > 1, where  +  means the concatenation of two strings.

Your task is to calculate the sum of costs of all subsequences of the string F(x). Since answer may be large, calculate it modulo 109 + 7.

## Input Format
The first line contains two integers n and x (1 ≤ n ≤ 100, 0 ≤ x ≤ 100) — the length of s and the index of a Fibonacci string you are interested in, respectively.

The second line contains s — a string consisting of n characters. Each of these characters is either 0 or 1.

## Output Format
Print the only integer — the sum of costs of all subsequences of the string F(x), taken modulo 109 + 7.

## Examples
```input
2 4
11
```
```output
14
```
-----
```input
10 100
1010101010
```
```output
553403224
```

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
We call an array almost increasing if we can erase not more than one element from it so that the array becomes strictly increasing (that is, every element is striclty greater than every element before it).

You are given an array a consisting of n elements. You are allowed to replace any element with any integer number (and you may do so any number of times you need). What is the minimum number of replacements you have to perform in order to make the array almost increasing?

## Input Format
The first line contains one integer n (2 ≤ n ≤ 200000) — the number of elements in a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the array a.

## Output Format
Print the minimum number of replaces you have to perform so that a is almost increasing.

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

# Problem
You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex $$$a$$$ is connected with a vertex $$$b$$$, a vertex $$$b$$$ is also connected with a vertex $$$a$$$). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices $$$u$$$ and $$$v$$$ belong to the same connected component if and only if there is at least one path along edges connecting $$$u$$$ and $$$v$$$.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

- the first vertex is connected with the second vertex by an edge,
- the second vertex is connected with the third vertex by an edge,
- ...
- the last vertex is connected with the first vertex by an edge,
- all the described edges of a cycle are distinct.

A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.

There are $$$6$$$ connected components, $$$2$$$ of them are cycles: $$$[7, 10, 16]$$$ and $$$[5, 11, 9, 15]$$$.

## Input Format
The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — number of vertices and edges.

The following $$$m$$$ lines contains edges: edge $$$i$$$ is given as a pair of vertices $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$). There is no multiple edges in the given graph, i.e. for each pair ($$$v_i, u_i$$$) there no other pairs ($$$v_i, u_i$$$) and ($$$u_i, v_i$$$) in the list of edges.

## Output Format
Print one integer — the number of connected components which are also cycles.

## Examples
```input
5 4
1 2
3 4
5 4
3 5
```
```output
1
```
-----
```input
17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6
```
```output
2
```

## Note
In the first example only component $$$[3, 4, 5]$$$ is also a cycle.

The illustration above corresponds to the second example.

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're given a row with $$$n$$$ chairs. We call a seating of people "maximal" if the two following conditions hold:

1. There are no neighbors adjacent to anyone seated.
2. It's impossible to seat one more person without violating the first rule.

The seating is given as a string consisting of zeros and ones ($$$0$$$ means that the corresponding seat is empty, $$$1$$$ — occupied). The goal is to determine whether this seating is "maximal".

Note that the first and last seats are not adjacent (if $$$n \ne 2$$$).

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of chairs.

The next line contains a string of $$$n$$$ characters, each of them is either zero or one, describing the seating.

## Output Format
Output "Yes" (without quotation marks) if the seating is "maximal". Otherwise print "No".

You are allowed to print letters in whatever case you'd like (uppercase or lowercase).

## Examples
```input
3
101
```
```output
Yes
```
-----
```input
4
1011
```
```output
No
```
-----
```input
5
10001
```
```output
No
```

## Note
In sample case one the given seating is maximal.

In sample case two the person at chair three has a neighbour to the right.

In sample case three it is possible to seat yet another person into chair three.

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
For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.

Max is a young biologist. For $$$n$$$ days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer $$$k$$$ that if the shark in some day traveled the distance strictly less than $$$k$$$, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to $$$k$$$; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least $$$k$$$.

The shark never returned to the same location after it has moved from it. Thus, in the sequence of $$$n$$$ days we can find consecutive nonempty segments when the shark traveled the distance less than $$$k$$$ in each of the days: each such segment corresponds to one location. Max wants to choose such $$$k$$$ that the lengths of all such segments are equal.

Find such integer $$$k$$$, that the number of locations is as large as possible. If there are several such $$$k$$$, print the smallest one.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of days.

The second line contains $$$n$$$ distinct positive integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the distance traveled in each of the day.

## Output Format
Print a single integer $$$k$$$, such that

1. the shark was in each location the same number of days,
2. the number of locations is maximum possible satisfying the first condition,
3. $$$k$$$ is smallest possible satisfying the first and second conditions.

## Examples
```input
8
1 2 7 3 4 8 5 6
```
```output
7
```
-----
```input
6
25 1 2 3 14 36
```
```output
2
```

## Note
In the first example the shark travels inside a location on days $$$1$$$ and $$$2$$$ (first location), then on $$$4$$$-th and $$$5$$$-th days (second location), then on $$$7$$$-th and $$$8$$$-th days (third location). There are three locations in total.

In the second example the shark only moves inside a location on the $$$2$$$-nd day, so there is only one location.

Now solve the problem and return the code.