vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem

There are $ n $ rectangles on the $ xy $ plane with $ x $ on the horizontal axis and $ y $ on the vertical axis. The $ i $ th rectangle is $ h_i $ in height and $ 1 $ in width, and the vertices are point $ (i-1, 0) $, point $ (i-1, h_i) $, and point $ (i, h_i). ) $, Point $ (i, 0) $.
You choose $ n $ positive integers $ y_1, y_2, ... y_n $ and perform the following $ n $ operations.
(1) In the first operation, draw a line segment connecting the point $ (0, 1) $ and the point $ (1, y_1) $.
(2) In the operation of $ i $ th time $ (2 \ le i \ le n) $, a line segment connecting the point $ (i-1, y_ {i-1}) $ and the point $ (i, y_i) $ pull.

For the $ i $ operation, set $ S_i $ as follows.
Let A be the endpoint with the smaller $ x $ coordinates of the line segment drawn in the $ i $ operation, and B be the endpoint with the larger $ x $ coordinates.
Also, point $ (i-1, 0) $ is C, point $ (i-1, h_i) $ is D, point $ (i, h_i) $ is E, and point $ (i, 0) $ is F. To do.
Let $ S_i $ be the area of ​​the non-intersection between the trapezoid ABFC and the rectangle DEFC.
Five examples are shown below.
<image>
$ S_i $ in each example is the total area of ​​the area containing the star mark. Find $ y_1, y_2, ... y_n $ that minimizes $ S = S_1 + S_2 +… + S_n $, and output the minimum value of $ S $.

Constraints

The input satisfies the following conditions.

* $ 2 \ leq n \ leq 150 $
* $ 1 \ leq h_i \ leq 150 $

Input

The input is given in the following format.


$ n $
$ h_1 $ $ h_2 $ $ ... $ $ h_n $


All inputs are given as integers.

Output

Output the minimum value of $ S $ on one line.
However, absolute or relative errors up to $ 10 ^ {-5} $ are acceptable.

Examples

Input

2
5 3


Output

2.83333333


Input

3
6 1 4


Output

6.25000000


Input

7
3 1 9 2 2 5 1


Output

12.37500000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance:

We will define the distance between two strings *s* and *t* of the same length consisting of digits zero and one as the number of positions *i*, such that *s**i* isn't equal to *t**i*. 

As besides everything else Susie loves symmetry, she wants to find for two strings *s* and *t* of length *n* such string *p* of length *n*, that the distance from *p* to *s* was equal to the distance from *p* to *t*.

It's time for Susie to go to bed, help her find such string *p* or state that it is impossible.

Input Specification:
The first line contains string *s* of length *n*. 

The second line contains string *t* of length *n*.

The length of string *n* is within range from 1 to 105. It is guaranteed that both strings contain only digits zero and one.

Output Specification:
Print a string of length *n*, consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line "impossible" (without the quotes).

If there are multiple possible answers, print any of them.

Demo Input:
['0001\n1011\n', '000\n111\n']

Demo Output:
['0011\n', 'impossible\n']

Note:
In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are currently studying the language $A j o b$ ( which means strange in English ) from a renowned professor. The language has infinite number of letters in its alphabet ( now you know, why it is called ajob ).  

The professor taught you $N$ words, one by one. The number of letters in a word is equal to it's place in the teaching order. Thus, the $1^{st}$ word taught by the professor has $\mbox{1}$ letter, $2^{nd}$ word has $2$ letters, $3^{rd}$ word has $3$ letters, $\ldots$, the $N^{th}$ word has $N$ letters.  

All the letters within a word are distinct to each other.

Now, you are handed an assignment. You have to choose any one of the $N$ words and form a subsequence from it. The length of the subsequence should be exactly $\mbox{K}$ less than the length of original word. For example, if the length of the chosen word is $\mbox{L}$, then the length of the subsequence should be $L-K$. If for any word, $\mbox{L}$ is smaller than $\mbox{K}$ $\left(L<K\right)$, then you must not choose that word. Two subsequences are different to each other if, the lengths of them are different or they contain different characters in the same position.

Find the number of ways you can complete the assignment ${modulo}\:p$ ( ${p}$ will always be a $\textit{prime}$ ).  

1. 

The first line contains ${T}$, the number of testcases. The next ${T}$ lines contain three space separated integers $N$, ${K}$ and ${p}$.  

Output Format 

For each testcase, print one integer in a single line, the number possible ways you can complete the assignment, ${modulo}\:p$.

Constraints 

$1\leq T\leq100$ 

$2\leq N\leq10^{18}$ 

$0<K<N$ 

$2\leq p\leq10^5$ 

$p\:\text{is a Prime}$  

Sample Input #00  

3
2 1 2
2 1 5
5 3 13

Sample Output #00  

1
3
2

Sample Input #01  

5
5 2 3
6 5 11
7 6 3
6 5 7
6 5 5

Sample Output #01  

2
7
2
0
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to decode some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
1
10
10
101
101
101
1010
1010
1010
1010

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kevin Sun wants to move his precious collection of n cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. Before moving, he must pack his cowbells into k boxes of a fixed size. In order to keep his collection safe during transportation, he won't place more than two cowbells into a single box. Since Kevin wishes to minimize expenses, he is curious about the smallest size box he can use to pack his entire collection. 

Kevin is a meticulous cowbell collector and knows that the size of his i-th (1 ≤ i ≤ n) cowbell is an integer s_{i}. In fact, he keeps his cowbells sorted by size, so s_{i} - 1 ≤ s_{i} for any i > 1. Also an expert packer, Kevin can fit one or two cowbells into a box of size s if and only if the sum of their sizes does not exceed s. Given this information, help Kevin determine the smallest s for which it is possible to put all of his cowbells into k boxes of size s.


-----Input-----

The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 2·k ≤ 100 000), denoting the number of cowbells and the number of boxes, respectively.

The next line contains n space-separated integers s_1, s_2, ..., s_{n} (1 ≤ s_1 ≤ s_2 ≤ ... ≤ s_{n} ≤ 1 000 000), the sizes of Kevin's cowbells. It is guaranteed that the sizes s_{i} are given in non-decreasing order.


-----Output-----

Print a single integer, the smallest s for which it is possible for Kevin to put all of his cowbells into k boxes of size s.


-----Examples-----
Input
2 1
2 5

Output
7

Input
4 3
2 3 5 9

Output
9

Input
3 2
3 5 7

Output
8



-----Note-----

In the first sample, Kevin must pack his two cowbells into the same box. 

In the second sample, Kevin can pack together the following sets of cowbells: {2, 3}, {5} and {9}.

In the third sample, the optimal solution is {3, 5} and {7}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
PK is presented a String S by daisy duck on his birthday.The length of this string is LEN.
Being an expert in measuring LULLness of string he wants to show of his
skills to impress daisy duck.The LULLness of a string is the number of such sub-sequences of a string which are GOOD strings.

A GOOD string is an odd length string.It's length is n(n ≥ 3),and it has a unique property, the middle most character of the string is 'u'
and all other characters are 'l'.So if length n=5,GOOD string is "llull".

Input:
the first line consists the input t(1 ≤ t ≤ 10),t is the number of testcases.
Each test case consists two inputs: 
    The string S having length LEN(1 ≤ LEN ≤ 100000)
    The length of the string 'n' to be searched in S,(1 ≤ n ≤ S-1),n is odd.

Output:
Print the LULLNESS of the string modulo 10^9+7(1000000007),as the output might overflow.

P.S. : Subsequence of a string :  http://en.wikipedia.org/wiki/Subsequence

SAMPLE INPUT
2
lul 3
ullullu 5

SAMPLE OUTPUT
1
1

Explanation

In the first test case there is only one GOOD string "lul" in the string S
In the second test case also the only GOOD string is "llull".
P.S. : Both the test cases are having Continuous good strings.
A sub sequence need not necessarily be continuous.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
*n* participants of the competition were split into *m* teams in some manner so that each team has at least one participant. After the competition each pair of participants from the same team became friends.

Your task is to write a program that will find the minimum and the maximum number of pairs of friends that could have formed by the end of the competition.

Input Specification:
The only line of input contains two integers *n* and *m*, separated by a single space (1<=≤<=*m*<=≤<=*n*<=≤<=109) — the number of participants and the number of teams respectively.

Output Specification:
The only line of the output should contain two integers *k**min* and *k**max* — the minimum possible number of pairs of friends and the maximum possible number of pairs of friends respectively.

Demo Input:
['5 1\n', '3 2\n', '6 3\n']

Demo Output:
['10 10\n', '1 1\n', '3 6\n']

Note:
In the first sample all the participants get into one team, so there will be exactly ten pairs of friends.

In the second sample at any possible arrangement one team will always have two participants and the other team will always have one participant. Thus, the number of pairs of friends will always be equal to one.

In the third sample minimum number of newly formed friendships can be achieved if participants were split on teams consisting of 2 people, maximum number can be achieved if participants were split on teams of 1, 1 and 4 people.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A variation of determining leap years, assuming only integers are used and years can be negative and positive.

Write a function which will return the days in the year and the year entered in a string.  For example 2000, entered as an integer, will return as a string 2000 has 366 days

There are a few assumptions we will accept the year 0, even though there is no year 0 in the Gregorian Calendar.

Also the basic rule for validating a leap year are as follows

Most years that can be divided evenly by 4 are leap years. 

Exception: Century years are NOT leap years UNLESS they can be evenly divided by 400.

So the years 0, -64 and 2016 will return 366 days.
Whilst 1974, -10 and 666 will return 365 days.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are N points (x_i, y_i) in a two-dimensional plane.
Find the minimum radius of a circle such that all the points are inside or on it.

-----Constraints-----
 - 2 \leq N \leq 50
 - 0 \leq x_i \leq 1000
 - 0 \leq y_i \leq 1000
 - The given N points are all different.
 - The values in input are all integers.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
:
x_N y_N

-----Output-----
Print the minimum radius of a circle such that all the N points are inside or on it.
Your output will be considered correct if the absolute or relative error from our answer is at most 10^{-6}.

-----Sample Input-----
2
0 0
1 0

-----Sample Output-----
0.500000000000000000

Both points are contained in the circle centered at (0.5,0) with a radius of 0.5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahabir loves matrix and likes to rotate things a lot.

Today he is rotating an array in clock-wise direction. He gives you an array of size N X N and an  positive integer Q.

Each Q number of integers contains an angle A (angle is always multiple of 90 or can be zero).

You have to rotate the array ( clock-wise only ) with angle A and have to tell him the resultant matrix after rotating it.
Mahabir challenges you to write the code.

Input

First line contains two positive integers N and Q separated by a space.

Next N lines contains N numbers each separated by a space.

Next Q lines contains  angle A with which you have to rotate the matrix.

Output

For each query Q print the resultant matrix.

Output of each query must be separated by an empty line.

Constraints

1=<N ≤ 100

1 ≤ Q ≤ 200

0 ≤ A ≤ 100000   (A will be always multiple of 90)

0 ≤ element of matrix ≤1000

SAMPLE INPUT
3 3
1 4 5 
6 7 8 
4 0 5 
90
180
450

SAMPLE OUTPUT
4 6 1 
0 7 4 
5 8 5 

5 0 4 
8 7 6 
5 4 1 

4 6 1 
0 7 4 
5 8 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Weenesia is an archipelago of perfectly circular islands in the 2D plane. Many islands have palm trees growing in them, perfectly straight up, so we can represent a tree by a 2D point and a height.

We want to build a courier system in the islands, i.e., we want to be able to move any object from any land point to any other land point. It is possible to move an object within an island without restrictions. It is also possible to climb to a palm tree and throw the object to a distance proportional to the height of the palm tree (or less), and possibly in a different island.

Unfortunately, this may not be enough to reach our goal, so we might want to build a tunnel between two islands. The tunnel connects two points on two islands and may cross under both the sea and other islands. Each of the two entrances of a tunnel must be at least $1$ meter away from the sea to avoid flooding.

Your task is to find the minimum length of a tunnel such that a courier system is possible.

-----Input-----
The first line contains three integers $n$, $m$, and $k$ ($1 \leq n \leq 5000$, $0 \leq m \leq 10000$, $1 \leq k \leq 1000$), the number of islands and palm trees respectively, and the ratio between object throwing range and palm height.

Each of the next $n$ lines contains three integers $x$, $y$, and $r$ ($|x|,|y|\leq 10^6$, $100 \leq r \leq 10^6$), the center and radius of an island, in centimetres. Each of the next $m$ lines contains three integers $x$, $y$, $h$ ($|x|,|y|\leq 10^6$, $1 \leq h \leq 10^4$), the center and height of a palm tree, in centimetres.

No two islands intersect. Each palm tree lies strictly inside an island. No two palm trees grow in the same spot.

-----Output-----
Output the minimum length of a tunnel in centimetres, $0$ if no tunnel is needed, or “impossible” if no such tunnel exists. Answers with an absolute or relative precision up to $10^{-6}$ will be accepted.

-----Examples-----
Sample Input:
3 2 3
0 0 400
1000 0 400
2000 0 400
300 0 150
1300 0 150
Sample Output:
1400

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cersei wants to be the queen of seven kingdoms.

For this to happen, she needs to address the soldiers in her army. There are n$n$ soldiers in her army (numbered 1$1$ through n$n$). Cersei passes on the message to the first soldier (soldier 1).   
This message needs to reach every soldier in the army. For this, the soldiers communicate among themselves by one soldier passing the message to another soldier through some communication links. It is known that the message could reach every soldier using the given links.
Now, each soldier will receive the message from exactly one soldier or Cersei and could pass on the message to atmost two soldiers. That is each soldier (except soldier 1) has only one incoming link and every soldier (including soldier 1) has atmost two outgoing links.  
Now, the High Sparrow feels that Cersei is planning to kill his people first. Hence, for the sake of his people, he decided to appoint some sparrows to overhear every conversation between the soldiers (The conversation between Cersei and the first soldier needn't be overheard due to the fear of Ser Gregor Clegane).   
To overhear a conversation between soldiers A$A$ and B$B$, there needs to be a sparrow either at soldier A$A$ or soldier B$B$ or both.
Also, by his research, the High Sparrow has found that the soldiers are partitioned into some classes (1$1$ to k$k$). That is, every soldier belongs to exactly one class. He then demands the presence of atleast one sparrow with each class he knows (1$1$ to k$k$).
Find the minimum number of sparrows the High Sparrow needs to recruit for the job or tell that he couldn't.

-----Input:-----
- The first line of the input contains the number of test cases t$t$.
- The first line of each test case gives the number of soldiers n$n$ in the army, the number of communication links m$m$ between the soldiers and the number of classes k$k$ in soldiers.
- The next line of the test case consists of n$n$ integers A1,A2....An$A_1,A_2....A_n$ each denoting the class of the ith$i^{th}$ soldier.
- The next m$m$ lines of the test case contain two integers u$u$ and v$v$, which denotes that soldier u$u$ can pass a message to soldier v$v$ (u≠v$u \neq v$).

-----Output:-----
For each test case, print in a single line the minimum number of sparrows required for the above task or print −1$-1$ if no such way is possible.

-----Constraints-----
- 1≤t≤500$1 \leq t \leq 500$
- 1≤n≤2500$1 \leq n \leq 2500$
- m=n−1$m = n - 1$
- 1≤k≤10$1 \leq k \leq 10$
- 1≤ai≤k$1 \leq a_i \leq k$
- The sum of n$n$ over all test cases is ≤2500$\leq 2500$.

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

-----Sample Output:-----
3

-----EXPLANATION:-----
Selecting soldiers 1,4,5 would satisfy all the conditions.

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

-----Sample Output:-----
-1

-----EXPLANATION:-----
Classes 4 and 5 are not present. So, there is no way possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everybody knows that the capital of Berland is connected to Bercouver (the Olympic capital) by a direct road. To improve the road's traffic capacity, there was placed just one traffic sign, limiting the maximum speed. Traffic signs in Berland are a bit peculiar, because they limit the speed only at that point on the road where they are placed. Right after passing the sign it is allowed to drive at any speed.

It is known that the car of an average Berland citizen has the acceleration (deceleration) speed of a km/h2, and has maximum speed of v km/h. The road has the length of l km, and the speed sign, limiting the speed to w km/h, is placed d km (1 ≤ d < l) away from the capital of Berland. The car has a zero speed at the beginning of the journey. Find the minimum time that an average Berland citizen will need to get from the capital to Bercouver, if he drives at the optimal speed.

The car can enter Bercouver at any speed.

Input

The first line of the input file contains two integer numbers a and v (1 ≤ a, v ≤ 10000). The second line contains three integer numbers l, d and w (2 ≤ l ≤ 10000; 1 ≤ d < l; 1 ≤ w ≤ 10000).

Output

Print the answer with at least five digits after the decimal point.

Examples

Input

1 1
2 1 3


Output

2.500000000000


Input

5 70
200 170 40


Output

8.965874696353

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Even if the world is full of counterfeits, I still regard it as wonderful.

Pile up herbs and incense, and arise again from the flames and ashes of its predecessor — as is known to many, the phoenix does it like this.

The phoenix has a rather long lifespan, and reincarnates itself once every a! years. Here a! denotes the factorial of integer a, that is, a! = 1 × 2 × ... × a. Specifically, 0! = 1.

Koyomi doesn't care much about this, but before he gets into another mess with oddities, he is interested in the number of times the phoenix will reincarnate in a timespan of b! years, that is, [Image]. Note that when b ≥ a this value is always integer.

As the answer can be quite large, it would be enough for Koyomi just to know the last digit of the answer in decimal representation. And you're here to provide Koyomi with this knowledge.


-----Input-----

The first and only line of input contains two space-separated integers a and b (0 ≤ a ≤ b ≤ 10^18).


-----Output-----

Output one line containing a single decimal digit — the last digit of the value that interests Koyomi.


-----Examples-----
Input
2 4

Output
2

Input
0 10

Output
0

Input
107 109

Output
2



-----Note-----

In the first example, the last digit of $\frac{4 !}{2 !} = 12$ is 2;

In the second example, the last digit of $\frac{10 !}{0 !} = 3628800$ is 0;

In the third example, the last digit of $\frac{109 !}{107 !} = 11772$ is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will receive 3 points for solving this problem.

Manao is designing the genetic code for a new type of algae to efficiently produce fuel. Specifically, Manao is focusing on a stretch of DNA that encodes one protein. The stretch of DNA is represented by a string containing only the characters 'A', 'T', 'G' and 'C'.

Manao has determined that if the stretch of DNA contains a maximal sequence of consecutive identical nucleotides that is of even length, then the protein will be nonfunctional. For example, consider a protein described by DNA string "GTTAAAG". It contains four maximal sequences of consecutive identical nucleotides: "G", "TT", "AAA", and "G". The protein is nonfunctional because sequence "TT" has even length.

Manao is trying to obtain a functional protein from the protein he currently has. Manao can insert additional nucleotides into the DNA stretch. Each additional nucleotide is a character from the set {'A', 'T', 'G', 'C'}. Manao wants to determine the minimum number of insertions necessary to make the DNA encode a functional protein.


-----Input-----

The input consists of a single line, containing a string s of length n (1 ≤ n ≤ 100). Each character of s will be from the set {'A', 'T', 'G', 'C'}.

This problem doesn't have subproblems. You will get 3 points for the correct submission.


-----Output-----

The program should print on one line a single integer representing the minimum number of 'A', 'T', 'G', 'C' characters that are required to be inserted into the input string in order to make all runs of identical characters have odd length.


-----Examples-----
Input
GTTAAAG

Output
1

Input
AACCAACCAAAAC

Output
5



-----Note-----

In the first example, it is sufficient to insert a single nucleotide of any type between the two 'T's in the sequence to restore the functionality of the protein.

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