vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We have a string S of length N consisting of A, T, C, and G.
Strings T_1 and T_2 of the same length are said to be complementary when, for every i (1 \leq i \leq l), the i-th character of T_1 and the i-th character of T_2 are complementary. Here, A and T are complementary to each other, and so are C and G.
Find the number of non-empty contiguous substrings T of S that satisfies the following condition:
 - There exists a string that is a permutation of T and is complementary to T.
Here, we distinguish strings that originate from different positions in S, even if the contents are the same.

-----Constraints-----
 - 1 \leq N \leq 5000
 - S consists of A, T, C, and G.

-----Input-----
Input is given from Standard Input in the following format:
N S

-----Output-----
Print the number of non-empty contiguous substrings T of S that satisfies the condition.

-----Sample Input-----
4 AGCT

-----Sample Output-----
2

The following two substrings satisfy the condition:
 - GC (the 2-nd through 3-rd characters) is complementary to CG, which is a permutation of GC.
 - AGCT (the 1-st through 4-th characters) is complementary to TCGA, which is a permutation of AGCT.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Left-handers, Right-handers and Ambidexters

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are at a water bowling training. There are *l* people who play with their left hand, *r* people, who play with their right hand, and *a* ambidexters, who can play with left or right hand.

The coach decided to form a team of even number of players, exactly half of the players should play with their right hand, and exactly half of the players should play with their left hand. One player should use only on of his hands.

Ambidexters play as well with their right hand as with their left hand. In the team, an ambidexter can play with their left hand, or with their right hand.

Please find the maximum possible size of the team, where equal number of players use their left and right hands, respectively.

Input Specification:
The only line contains three integers *l*, *r* and *a* (0<=≤<=*l*,<=*r*,<=*a*<=≤<=100) — the number of left-handers, the number of right-handers and the number of ambidexters at the training.

Output Specification:
Print a single even integer — the maximum number of players in the team. It is possible that the team can only have zero number of players.

Demo Input:
['1 4 2\n', '5 5 5\n', '0 2 0\n']

Demo Output:
['6\n', '14\n', '0\n']

Note:
In the first example you can form a team of 6 players. You should take the only left-hander and two ambidexters to play with left hand, and three right-handers to play with right hand. The only person left can't be taken into the team.

In the second example you can form a team of 14 people. You have to take all five left-handers, all five right-handers, two ambidexters to play with left hand and two ambidexters to play with right hand.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a Directed Graph having V nodes numbered from 0 to V-1, and E directed edges. Given two nodes, source and destination, count the number of ways or paths between these two vertices in the directed graph. These paths should not contain any cycle.
Note: Graph doesn't contain multiple edges, self-loop, and cycles.
Example 1:
Input:
V = 5, E = 7
Edges of Graph = 
{0, 1}
{0, 2}
{0, 4}
{1, 3}
{1, 4}
{2, 4}
{3, 2}
source = 0 
destination = 4
Output: 4
Explanation: 
There are 4 paths from 0 to 4.
0 -> 4
0 -> 1 -> 4
0 -> 2 -> 4
0 -> 1 -> 3 -> 2 -> 4
Example 2:
Input:
V = 4, E = 5
Edges of Graph = 
{0, 1}
{0, 3}
{1, 2}
{1, 3}
{2, 3}
source = 0 
destination = 3
Output: 3
Explanation:
There are 3 paths from 0 to 3.
0 -> 3
0 -> 1 -> 3
0 -> 1 -> 2 -> 3
Your task:
You don't need to read, input, or print anything. Your task is to complete the function countPaths(), which takes the integer V denoting the number of vertices, adjacency list adj, integer source, and destination as input parameters and returns the number of paths in the graph from the source vertex to the destination vertex.
Expected Time Complexity: O(V!)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V, E ≤ 100
1 ≤ source, destination ≤ V

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A family of $n$ gnomes likes to line up for a group picture. Each gnome can be uniquely identified by a number $1..n$ written on their hat.

Suppose there are $5$ gnomes. The gnomes could line up like so: $1, 3, 4, 2, 5$.

Now, an evil magician will remove some of the gnomes from the lineup and wipe your memory of the order of the gnomes. The result is a subsequence, perhaps like so: $1, 4, 2$.

He then tells you that if you ordered all permutations of $1..n$ in lexicographical order, the original sequence of gnomes is the first such permutation which contains the remaining subsequence. Your task is to find the original sequence of gnomes.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers $n$ and then $m$ ($1 \le m \le n \le 10^5$), where $n$ is the number of gnomes originally, and $m$ is the number of gnomes remaining after the evil magician pulls his trick. Each of the next $m$ lines will contain a single integer $g$ ($1 \le g \le n$). These are the remaining gnomes, in order. The values of $g$ are guaranteed to be unique.

-----Output-----
Output $n$ lines, each containing a single integer, representing the first permutation of gnomes that could contain the remaining gnomes in order.

-----Examples-----
Sample Input:
5 3
1
4
2
Sample Output:
1
3
4
2
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Giga Tower is the tallest and deepest building in Cyberland. There are 17 777 777 777 floors, numbered from  - 8 888 888 888 to 8 888 888 888. In particular, there is floor 0 between floor  - 1 and floor 1. Every day, thousands of tourists come to this place to enjoy the wonderful view. 

In Cyberland, it is believed that the number "8" is a lucky number (that's why Giga Tower has 8 888 888 888 floors above the ground), and, an integer is lucky, if and only if its decimal notation contains at least one digit "8". For example, 8,  - 180, 808 are all lucky while 42,  - 10 are not. In the Giga Tower, if you write code at a floor with lucky floor number, good luck will always be with you (Well, this round is #278, also lucky, huh?).

Tourist Henry goes to the tower to seek good luck. Now he is at the floor numbered a. He wants to find the minimum positive integer b, such that, if he walks b floors higher, he will arrive at a floor with a lucky number. 


-----Input-----

The only line of input contains an integer a ( - 10^9 ≤ a ≤ 10^9).


-----Output-----

Print the minimum b in a line.


-----Examples-----
Input
179

Output
1

Input
-1

Output
9

Input
18

Output
10



-----Note-----

For the first sample, he has to arrive at the floor numbered 180.

For the second sample, he will arrive at 8.

Note that b should be positive, so the answer for the third sample is 10, not 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Buses run between the cities A and B, the first one is at 05:00 AM and the last one departs not later than at 11:59 PM. A bus from the city A departs every a minutes and arrives to the city B in a t_{a} minutes, and a bus from the city B departs every b minutes and arrives to the city A in a t_{b} minutes.

The driver Simion wants to make his job diverse, so he counts the buses going towards him. Simion doesn't count the buses he meet at the start and finish.

You know the time when Simion departed from the city A to the city B. Calculate the number of buses Simion will meet to be sure in his counting.


-----Input-----

The first line contains two integers a, t_{a} (1 ≤ a, t_{a} ≤ 120) — the frequency of the buses from the city A to the city B and the travel time. Both values are given in minutes.

The second line contains two integers b, t_{b} (1 ≤ b, t_{b} ≤ 120) — the frequency of the buses from the city B to the city A and the travel time. Both values are given in minutes.

The last line contains the departure time of Simion from the city A in the format hh:mm. It is guaranteed that there are a bus from the city A at that time. Note that the hours and the minutes are given with exactly two digits.


-----Output-----

Print the only integer z — the number of buses Simion will meet on the way. Note that you should not count the encounters in cities A and B.


-----Examples-----
Input
10 30
10 35
05:20

Output
5

Input
60 120
24 100
13:00

Output
9



-----Note-----

In the first example Simion departs form the city A at 05:20 AM and arrives to the city B at 05:50 AM. He will meet the first 5 buses from the city B that departed in the period [05:00 AM - 05:40 AM]. Also Simion will meet a bus in the city B at 05:50 AM, but he will not count it.

Also note that the first encounter will be between 05:26 AM and 05:27 AM (if we suggest that the buses are go with the sustained speed).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
DZY has a sequence a, consisting of n integers.

We'll call a sequence a_{i}, a_{i} + 1, ..., a_{j} (1 ≤ i ≤ j ≤ n) a subsegment of the sequence a. The value (j - i + 1) denotes the length of the subsegment.

Your task is to find the longest subsegment of a, such that it is possible to change at most one number (change one number to any integer you want) from the subsegment to make the subsegment strictly increasing.

You only need to output the length of the subsegment you find.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The next line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

In a single line print the answer to the problem — the maximum length of the required subsegment.


-----Examples-----
Input
6
7 2 3 1 5 6

Output
5



-----Note-----

You can choose subsegment a_2, a_3, a_4, a_5, a_6 and change its 3rd element (that is a_4) to 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef goes to the supermarket to buy some items. Luckily there's a sale going on under which Chef gets the following offer: 

If Chef buys 3 items then he gets the item (out of those 3 items) having the lowest price as free. 

For e.g. if Chef bought 3 items with the cost 6, 2 and 4, then he would get the item with cost 2 as free. So he would only have to pay the cost of the other two items which will be 6 + 4 = 10.

Chef buys 3 items having prices A, B and C respectively. What is the amount of money Chef needs to pay?

------ Input Format ------ 

- The first line will contain an integer T - number of test cases. Then the test cases follow.
- The first and only line of each test case contains three integers A, B, C - the prices of the items bought by Chef.

------ Output Format ------ 

For each test case, output the price paid by Chef.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ A, B, C ≤ 10$

----- Sample Input 1 ------ 
3
6 2 4
3 3 3
8 4 4

----- Sample Output 1 ------ 
10
6
12

----- explanation 1 ------ 
Test case-1: Explained in the problem statement.

Test case-2: Since all the three items have the same price, Chef will get one of them free and will have to pay the cost of the other two items which will be $3 + 3 = 6$. 

Test case-3: Chef will get one of the items having price $4$ as free and will have to pay the cost of the other two items which will be $8 + 4 = 12$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
**Story**  
On some island lives a chameleon population. Chameleons here can be of only one of three colors - red, green and blue. Whenever two chameleons of different colors meet, they can change their colors to a third one (i.e. when red and blue chameleons meet, they can both become green). There is no other way for chameleons to change their color (in particular, when red and blue chameleons meet, they can't become both red, only third color can be assumed).  
Chameleons want to become of one certain color. They may plan they meetings to reach that goal. Chameleons want to know, how fast their goal can be achieved (if it can be achieved at all).

**Formal problem**  
*Input:*  
Color is coded as integer, 0 - red, 1 - green, 2 - blue.
Chameleon starting population is given as an array of three integers, with index corresponding to color (i.e. [2, 5, 3] means 2 red, 5 green and 3 blue chameleons). All numbers are non-negative, their sum is between `1` and `int.MaxValue` (maximal possible value for `int` type, in other languages). Desired color is given as an integer from 0 to 2.  
*Output:*  
`Kata.Chameleon` should return *minimal* number of meetings required to change all chameleons to a given color, or -1 if it is impossible (for example, if all chameleons are initially of one other color).  
  
**Notes and hints**  
-- Some tests use rather big input values. Be effective.  
-- There is a strict proof that answer is either -1 or no greater than total number of chameleons (thus, return type `int` is justified). Don't worry about overflow.  
  
**Credits**  
Kata based on "Chameleons" puzzle from braingames.ru: http://www.braingames.ru/?path=comments&puzzle=226 (russian, not translated).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Alternative Thinking

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length *n*. Each character of Kevin's string represents Kevin's score on one of the *n* questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.

However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define an alternating subsequence of a string as a not-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0,<=1,<=0,<=1}, {1,<=0,<=1}, and {1,<=0,<=1,<=0} are alternating sequences, while {1,<=0,<=0} and {0,<=1,<=0,<=1,<=1} are not.

Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.

Input Specification:
The first line contains the number of questions on the olympiad *n* (1<=≤<=*n*<=≤<=100<=000).

The following line contains a binary string of length *n* representing Kevin's results on the USAICO.

Output Specification:
Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.

Demo Input:
['8\n10000011\n', '2\n01\n']

Demo Output:
['5\n', '2\n']

Note:
In the first sample, Kevin can flip the bolded substring '10000011' and turn his string into '10011011', which has an alternating subsequence of length 5: '10011011'.

In the second sample, Kevin can flip the entire string and still have the same score.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length k is vowelly if there are positive integers n and m such that n⋅ m = k and when the word is written by using n rows and m columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer k and you must either print a vowelly word of length k or print -1 if no such word exists.

In this problem the vowels of the English alphabet are 'a', 'e', 'i', 'o' ,'u'.

Input

Input consists of a single line containing the integer k (1≤ k ≤ 10^4) — the required length.

Output

The output must consist of a single line, consisting of a vowelly word of length k consisting of lowercase English letters if it exists or -1 if it does not.

If there are multiple possible words, you may output any of them.

Examples

Input


7


Output


-1


Input


36


Output


agoeuioaeiruuimaeoieauoweouoiaouimae

Note

In the second example, the word "agoeuioaeiruuimaeoieauoweouoiaouimae" can be arranged into the following 6 × 6 grid:

<image>

It is easy to verify that every row and every column contain all the vowels.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Justin likes to play a game called “Weight of Words.” In this game, a player must find words of a given length and a given weight. The weight of a word is the sum of the weights of its letters. Letters are English lowercase characters from ‘a’ to ‘z’ and have weights from $1 \ldots 26$. 

You are asked to write an AI that can play this game!

-----Input-----
The input consists of a single line with two integers $l$ ($0 < l \le 40$) and $w$ ($0 < w \le 1000$).

-----Output-----
Output a string of length $l$ with weight $w$ consisting of lowercase English letters if it exists, otherwise output impossible. If more than one string exists, you may output any of them.

-----Examples-----
Sample Input 1:
11 131
Sample Output 1:
programming

Sample Input 2:
7 96
Sample Output 2:
contest

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After returning to shore, uncle Bogdan usually visits the computer club "The Rock", to solve tasks in a pleasant company. One day, uncle Bogdan met his good old friend who told him one unusual task...

There are n non-intersecting horizontal segments with ends in integers points on the plane with the standard cartesian coordinate system. All segments are strictly above the OX axis. You can choose an arbitrary vector (a, b), where b < 0 and coordinates are real numbers, and project all segments to OX axis along this vector. The projections shouldn't intersect but may touch each other.

Find the minimum possible difference between x coordinate of the right end of the rightmost projection and x coordinate of the left end of the leftmost projection.

Input

The first line contains the single integer n (1 ≤ n ≤ 2000) — the number of segments.

The i-th of the next n lines contains three integers xl_i, xr_i and y_i (-10^6 ≤ xl_i < xr_i ≤ 10^6; 1 ≤ y_i ≤ 10^6) — coordinates of the corresponding segment.

It's guaranteed that the segments don't intersect or touch.

Output

Print the minimum possible difference you can get.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10^{-6}.

Formally, if your answer is a and jury's answer is b then your answer will be considered correct if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Examples

Input


3
1 6 2
4 6 4
4 6 6


Output


9.000000000


Input


3
2 5 1
4 6 4
7 8 2


Output


6.333333333


Input


2
1 3 1
4 7 1


Output


6.000000000

Note

In the first example if we project segments along the vector (1, -1) then we get an answer 12-3=9 and (it can be proven) it is impossible to get less. 

<image>

It is optimal to project along the vector (1, -3) in the second example. The answer is 82/3-21/3=61/3 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easier version of the problem with smaller constraints.

Korney Korneevich dag up an array $a$ of length $n$. Korney Korneevich has recently read about the operation bitwise XOR , so he wished to experiment with it. For this purpose, he decided to find all integers $x \ge 0$ such that there exists an increasing subsequence of the array $a$, in which the bitwise XOR of numbers is equal to $x$.

It didn't take a long time for Korney Korneevich to find all such $x$, and he wants to check his result. That's why he asked you to solve this problem!

A sequence $s$ is a subsequence of a sequence $b$ if $s$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements.

A sequence $s_1, s_2, \ldots , s_m$ is called increasing if $s_1 < s_2 < \ldots < s_m$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 500$) — the elements of the array $a$.


-----Output-----

In the first line print a single integer $k$ — the number of found $x$ values.

In the second line print $k$ integers in increasing order $x_1, x_2, \ldots x_k$ ($0 \le x_1 < \ldots < x_k$) — found $x$ values.


-----Examples-----

Input
4
4 2 2 4
Output
4
0 2 4 6
Input
8
1 0 1 7 12 5 3 2
Output
12
0 1 2 3 4 5 6 7 10 11 12 13


-----Note-----

In the first test case:

To get value $x = 0$ it is possible to choose and empty subsequence

To get value $x = 2$ it is possible to choose a subsequence $[2]$

To get value $x = 4$ it is possible to choose a subsequence $[4]$

To get value $x = 6$ it is possible to choose a subsequence $[2, 4]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Forecast

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Department of economic development of IT City created a model of city development till year 2100.

To prepare report about growth perspectives it is required to get growth estimates from the model.

To get the growth estimates it is required to solve a quadratic equation. Since the Department of economic development of IT City creates realistic models only, that quadratic equation has a solution, moreover there are exactly two different real roots.

The greater of these roots corresponds to the optimistic scenario, the smaller one corresponds to the pessimistic one. Help to get these estimates, first the optimistic, then the pessimistic one.

Input Specification:
The only line of the input contains three integers *a*,<=*b*,<=*c* (<=-<=1000<=≤<=*a*,<=*b*,<=*c*<=≤<=1000) — the coefficients of *ax*2<=+<=*bx*<=+<=*c*<==<=0 equation.

Output Specification:
In the first line output the greater of the equation roots, in the second line output the smaller one. Absolute or relative error should not be greater than 10<=-<=6.

Demo Input:
['1 30 200\n']

Demo Output:
['-10.000000000000000\n-20.000000000000000']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.