vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Andrew and Jerry are playing a game with Harry as the scorekeeper. The game consists of three rounds. In each round, Andrew and Jerry draw randomly without replacement from a jar containing n balls, each labeled with a distinct positive integer. Without looking, they hand their balls to Harry, who awards the point to the player with the larger number and returns the balls to the jar. The winner of the game is the one who wins at least two of the three rounds.

Andrew wins rounds 1 and 2 while Jerry wins round 3, so Andrew wins the game. However, Jerry is unhappy with this system, claiming that he will often lose the match despite having the higher overall total. What is the probability that the sum of the three balls Jerry drew is strictly higher than the sum of the three balls Andrew drew?

Input

The first line of input contains a single integer n (2 ≤ n ≤ 2000) — the number of balls in the jar.

The second line contains n integers ai (1 ≤ ai ≤ 5000) — the number written on the ith ball. It is guaranteed that no two balls have the same number.

Output

Print a single real value — the probability that Jerry has a higher total, given that Andrew wins the first two rounds and Jerry wins the third. Your 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 <image>.

Examples

Input

2
1 2


Output

0.0000000000


Input

3
1 2 10


Output

0.0740740741

Note

In the first case, there are only two balls. In the first two rounds, Andrew must have drawn the 2 and Jerry must have drawn the 1, and vice versa in the final round. Thus, Andrew's sum is 5 and Jerry's sum is 4, so Jerry never has a higher total.

In the second case, each game could've had three outcomes — 10 - 2, 10 - 1, or 2 - 1. Jerry has a higher total if and only if Andrew won 2 - 1 in both of the first two rounds, and Jerry drew the 10 in the last round. This has probability <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recall that the bracket sequence is considered regular if it is possible to insert symbols '+' and '1' into it so that the result is a correct arithmetic expression. For example, a sequence "(()())" is regular, because we can get correct arithmetic expression insering symbols '+' and '1': "((1+1)+(1+1))". Also the following sequences are regular: "()()()", "(())" and "()". The following sequences are not regular bracket sequences: ")(", "(()" and "())(()".

In this problem you are given two integers n and k. Your task is to construct a regular bracket sequence consisting of round brackets with length 2·n with total sum of nesting of all opening brackets equals to exactly k. The nesting of a single opening bracket equals to the number of pairs of brackets in which current opening bracket is embedded.

For example, in the sequence "()(())" the nesting of first opening bracket equals to 0, the nesting of the second opening bracket equals to 0 and the nesting of the third opening bracket equal to 1. So the total sum of nestings equals to 1.

Input

The first line contains two integers n and k (1 ≤ n ≤ 3·105, 0 ≤ k ≤ 1018) — the number of opening brackets and needed total nesting.

Output

Print the required regular bracket sequence consisting of round brackets.

If there is no solution print "Impossible" (without quotes).

Examples

Input

3 1


Output

()(())

Input

4 6


Output

(((())))

Input

2 5


Output

Impossible

Note

The first example is examined in the statement.

In the second example the answer is "(((())))". The nesting of the first opening bracket is 0, the nesting of the second is 1, the nesting of the third is 2, the nesting of fourth is 3. So the total sum of nestings equals to 0 + 1 + 2 + 3 = 6.

In the third it is impossible to construct a regular bracket sequence, because the maximum possible total sum of nestings for two opening brackets equals to 1. This total sum of nestings is obtained for the sequence "(())".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N people are arranged in a row from left to right.
You are given a string S of length N consisting of 0 and 1, and a positive integer K.
The i-th person from the left is standing on feet if the i-th character of S is 0, and standing on hands if that character is 1.
You will give the following direction at most K times (possibly zero):
Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.
Find the maximum possible number of consecutive people standing on hands after at most K directions.

-----Constraints-----
 - N is an integer satisfying 1 \leq N \leq 10^5.
 - K is an integer satisfying 1 \leq K \leq 10^5.
 - The length of the string S is N.
 - Each character of the string S is 0 or 1.

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

-----Output-----
Print the maximum possible number of consecutive people standing on hands after at most K directions.

-----Sample Input-----
5 1
00010

-----Sample Output-----
4

We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:
 - Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Barney has finally found the one, a beautiful young lady named Lyanna. The problem is, Lyanna and Barney are trapped in Lord Loss' castle. This castle has shape of a convex polygon of n points. Like most of castles in Demonata worlds, this castle has no ceiling.

<image>

Barney and Lyanna have an escape plan, but it requires some geometry knowledge, so they asked for your help.

Barney knows that demons are organized and move in lines. He and Lyanna want to wait for the appropriate time so they need to watch for the demons. Each of them wants to stay in a point inside the castle (possibly on edges or corners), also they may stay in the same position. They both want to pick a real number r and watch all points in the circles with radius r around each of them (these two circles may overlap).

<image>

We say that Barney and Lyanna are watching carefully if and only if for every edge of the polygon, at least one of them can see at least one point on the line this edge lies on, thus such point may not be on the edge but it should be on edge's line. Formally, each edge line should have at least one common point with at least one of two circles.

The greater r is, the more energy and focus they need. So they asked you to tell them the minimum value of r such that they can watch carefully.

Input

The first line of input contains a single integer n (3 ≤ n ≤ 300) — the number of castle polygon vertices.

The next n lines describe the polygon vertices in counter-clockwise order. i-th of them contains two integers xi and yi (|xi|, |yi| ≤ 104) — the coordinates of i-th point of the castle. It is guaranteed that given points form a convex polygon, in particular, any three of them do not line on the same line.

Output

In the first line print the single number r — minimum radius of guys' watching circles.

In the second line print the pair of coordinates of point where Barney should stay.

In the third line print the pair of coordinates of point where Lyanna should stay.

Points should lie inside the polygon.

Coordinates may not be integers. If there are multiple answers print any of them.

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

Examples

Input

4
-41 67
-16 20
25 25
-36 85


Output

0
-16 20
-36 85


Input

7
-7 54
-5 31
-2 17
20 19
32 23
34 27
26 57


Output

2.9342248
32.019503 23.0390067
-6.929116 54.006444

Note

In the first example guys can stay in opposite corners of the castle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your local library needs your help! Given the expected and actual return dates for a library book, create a program that calculates the fine (if any). The fee structure is as follows: 

If the book is returned on or before the expected return date, no fine will be charged (i.e.: $fine=0)$.
If the book is returned after the expected return day but still within the same calendar month and year as the expected return date, $fine=15\ \text{Hackos}\ \times\ \text{(the number of days later)}$. 
If the book is returned after the expected return month but still within the same calendar year as the expected return date, the $fine=500\ \text{Hackos}\ \times\ \text{(the number of months rate)}$.   
If the book is returned after the calendar year in which it was expected, there is a fixed fine of $10000\ \textbf{Hackos}$.

Charges are based only on the least precise measure of lateness.  For example, whether a book is due January 1, 2017 or December 31, 2017, if it is returned January 1, 2018, that is a year late and the fine would be $10,000\ \text{Hackos}$.  

Example 

$d1,m1,y1=14,7,2018$ 

$d2,m2,y2=5,7,2018$  

The first values are the return date and the second are the due date.  The years are the same and the months are the same.  The book is $14-5=9$ days late.  Return $9*15=135$.  

Function Description  

Complete the libraryFine function in the editor below.  

libraryFine has the following parameter(s):  

d1, m1, y1: returned date day, month and year, each an integer  
d2, m2, y2: due date day, month and year, each an integer    

Returns  

int:  the amount of the fine or $\mbox{o}$ if there is none

Input Format

The first line contains $3$ space-separated integers, $d1,m1,y1$, denoting the respective $\boldsymbol{day}$, $\textit{month}$, and $year$ on which the book was returned. 

The second line contains $3$ space-separated integers, $d2,m2,y2$, denoting the respective $\boldsymbol{day}$, $\textit{month}$, and $year$ on which the book was due to be returned.

Constraints

$1\leq d1,d2\leq31$     
$1\leq m1,m2\leq12$     
$1\leq y1,y2\leq3000$  
$\textbf{It is generated that the dates will be valid Gregion calendar dates.}$  

Sample Input
9 6 2015
6 6 2015

Sample Output
45

Explanation

Given the following dates: 

Returned: $d1=9,m1=6,y1=2015$ 

Due: $d2=6,m2=6,y2=2015$

Because $y2\equiv y1$, we know it is less than a year late. 

Because $\textit{m2}\equiv\textit{m1}$, we know it's less than a month late. 

Because $d2<d1$, we know that it was returned late (but still within the same month and year).  

Per the library's fee structure, we know that our fine will be $15\ \text{Hackos}\ \times\ (\#\ \text{days rate})$. We then print the result of $15\times(d1-d2)=15\times(9-6)=45$ as our output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
HTML Element Generator
In this kata, you will be creating a python function that will take arguments and turn them into an HTML element.
An HTML tag has three parts:

The opening tag, which consists of a tag name and potentially attributes, all in between angle brackets.
The element content, which is the data that is shown on the webpage.  This is in between the opening and closing tags.
And the closing tag, which is an opening angle bracket, a forward slash, the name of the tag, and a closing angle bracket


If you were to have multiple attributes, they would each appear with a single space separating them

Some tags do not require a closing tag.  These are called self-closing tags.  For this kata, any tag passed into the function without 'element content' (keyword arguments) will be treated in this way:  after the tag name (and any attributes), there will be a space and then a forward slash.  See the picture to the right.

Data will be passed into the html function as such: 

The first argument will be the tag name
Any other non-keyword arguments will be element content. If no element content is given, the return value will be expected to be a self-closing tag.  If more than one argument is given as element content, you will return multiple of the same element, just with different element content, separated by one or more newline characters.
Ex: 

<p class="paragraph-text" id="example">Hello World!</p>\n<p class="paragraph-text" id="example">This is HTML code!</p>

IMPORTANT:  Because class is a python keyword, and class is a very important HTML attribute, you will also have to implement a keyword argument named cls, as opposed to class.  This attribute will appear as class="variable" in the return value of your function
Any other keyword arguments of the function will be treated as attributes of the element.  The keyword is the attribute name (left of the equals sign), and the keyword's value is the attribute's value (right of the equals sign).
Element attributes will appear in the return value of your function in the order that they appear in the function's arguments when it is called.  If cls is an argument of the function, it will always appear first (before any other keyword arguments).
Several Examples are provided

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gottfried learned about binary number representation. He then came up with this task and presented it to you.

You are given a collection of $n$ non-negative integers $a_1, \ldots, a_n$. You are allowed to perform the following operation: choose two distinct indices $1 \leq i, j \leq n$. If before the operation $a_i = x$, $a_j = y$, then after the operation $a_i = x~\mathsf{AND}~y$, $a_j = x~\mathsf{OR}~y$, where $\mathsf{AND}$ and $\mathsf{OR}$ are bitwise AND and OR respectively (refer to the Notes section for formal description). The operation may be performed any number of times (possibly zero).

After all operations are done, compute $\sum_{i=1}^n a_i^2$ — the sum of squares of all $a_i$. What is the largest sum of squares you can achieve?


-----Input-----

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

The second line contains $n$ integers $a_1, \ldots, a_n$ ($0 \leq a_i < 2^{20}$).


-----Output-----

Print a single integer — the largest possible sum of squares that can be achieved after several (possibly zero) operations.


-----Examples-----
Input
1
123

Output
15129

Input
3
1 3 5

Output
51

Input
2
349525 699050

Output
1099509530625



-----Note-----

In the first sample no operation can be made, thus the answer is $123^2$.

In the second sample we can obtain the collection $1, 1, 7$, and $1^2 + 1^2 + 7^2 = 51$.

If $x$ and $y$ are represented in binary with equal number of bits (possibly with leading zeros), then each bit of $x~\mathsf{AND}~y$ is set to $1$ if and only if both corresponding bits of $x$ and $y$ are set to $1$. Similarly, each bit of $x~\mathsf{OR}~y$ is set to $1$ if and only if at least one of the corresponding bits of $x$ and $y$ are set to $1$. For example, $x = 3$ and $y = 5$ are represented as $011_2$ and $101_2$ (highest bit first). Then, $x~\mathsf{AND}~y = 001_2 = 1$, and $x~\mathsf{OR}~y = 111_2 = 7$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima loves Inna very much. He decided to write a song for her. Dima has a magic guitar with n strings and m frets. Dima makes the guitar produce sounds like that: to play a note, he needs to hold one of the strings on one of the frets and then pull the string. When Dima pulls the i-th string holding it on the j-th fret the guitar produces a note, let's denote it as a_{ij}. We know that Dima's guitar can produce k distinct notes. It is possible that some notes can be produced in multiple ways. In other words, it is possible that a_{ij} = a_{pq} at (i, j) ≠ (p, q).

Dima has already written a song — a sequence of s notes. In order to play the song, you need to consecutively produce the notes from the song on the guitar. You can produce each note in any available way. Dima understood that there are many ways to play a song and he wants to play it so as to make the song look as complicated as possible (try to act like Cobein).

We'll represent a way to play a song as a sequence of pairs (x_{i}, y_{i}) (1 ≤ i ≤ s), such that the x_{i}-th string on the y_{i}-th fret produces the i-th note from the song. The complexity of moving between pairs (x_1, y_1) and (x_2, y_2) equals $|x_{1} - x_{2}|$ + $|y_{1} - y_{2}|$. The complexity of a way to play a song is the maximum of complexities of moving between adjacent pairs.

Help Dima determine the maximum complexity of the way to play his song! The guy's gotta look cool!


-----Input-----

The first line of the input contains four integers n, m, k and s (1 ≤ n, m ≤ 2000, 1 ≤ k ≤ 9, 2 ≤ s ≤ 10^5). 

Then follow n lines, each containing m integers a_{ij} (1 ≤ a_{ij} ≤ k). The number in the i-th row and the j-th column (a_{ij}) means a note that the guitar produces on the i-th string and the j-th fret.

The last line of the input contains s integers q_{i} (1 ≤ q_{i} ≤ k) — the sequence of notes of the song.


-----Output-----

In a single line print a single number — the maximum possible complexity of the song.


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

Output
8

Input
4 4 9 5
4 7 9 5
1 2 1 7
8 3 4 9
5 7 7 2
7 1 9 2 5

Output
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two trees (connected undirected acyclic graphs) S and T.

Count the number of subtrees (connected subgraphs) of S that are isomorphic to tree T. Since this number can get quite large, output it modulo 109 + 7.

Two subtrees of tree S are considered different, if there exists a vertex in S that belongs to exactly one of them.

Tree G is called isomorphic to tree H if there exists a bijection f from the set of vertices of G to the set of vertices of H that has the following property: if there is an edge between vertices A and B in tree G, then there must be an edge between vertices f(A) and f(B) in tree H. And vice versa — if there is an edge between vertices A and B in tree H, there must be an edge between f - 1(A) and f - 1(B) in tree G.

Input

The first line contains a single integer |S| (1 ≤ |S| ≤ 1000) — the number of vertices of tree S.

Next |S| - 1 lines contain two integers ui and vi (1 ≤ ui, vi ≤ |S|) and describe edges of tree S.

The next line contains a single integer |T| (1 ≤ |T| ≤ 12) — the number of vertices of tree T.

Next |T| - 1 lines contain two integers xi and yi (1 ≤ xi, yi ≤ |T|) and describe edges of tree T.

Output

On the first line output a single integer — the answer to the given task modulo 109 + 7.

Examples

Input

5
1 2
2 3
3 4
4 5
3
1 2
2 3


Output

3


Input

3
2 3
3 1
3
1 2
1 3


Output

1


Input

7
1 2
1 3
1 4
1 5
1 6
1 7
4
4 1
4 2
4 3


Output

20


Input

5
1 2
2 3
3 4
4 5
4
4 1
4 2
4 3


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function called `LCS` that accepts two sequences and returns the longest subsequence common to the passed in sequences.

### Subsequence
A subsequence is different from a substring. The terms of a subsequence need not be consecutive terms of the original sequence.

### Example subsequence
Subsequences of `"abc"` = `"a"`, `"b"`, `"c"`, `"ab"`, `"ac"`, `"bc"` and `"abc"`.

### LCS examples
```python
lcs( "abcdef" , "abc" ) => returns "abc"
lcs( "abcdef" , "acf" ) => returns "acf"
lcs( "132535365" , "123456789" ) => returns "12356"
```

### Notes
* Both arguments will be strings
* Return value must be a string
* Return an empty string if there exists no common subsequence
* Both arguments will have one or more characters (in JavaScript)
* All tests will only have a single longest common subsequence. Don't worry about cases such as `LCS( "1234", "3412" )`, which would have two possible longest common subsequences: `"12"` and `"34"`.

Note that the Haskell variant will use randomized testing, but any longest common subsequence will be valid.

Note that the OCaml variant is using generic lists instead of strings, and will also have randomized tests (any longest common subsequence will be valid).

### Tips

Wikipedia has an explanation of the two properties that can be used to solve the problem:

- [First property](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#First_property)
- [Second property](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Second_property)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vedant has a hidden array of N elements. Given the [bitwise AND] of all elements of the array, determine whether the total sum of the elements is odd, even or cannot be determined.

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

- The first line of each input contains T - the number of test cases. The test cases then follow.
- The only line of each test case contains two space-separated integers N and A - the number of elements in the hidden array and the bitwise AND of all the elements in the hidden array.

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

For each test case, output Even if the sum of all elements in the hidden array is even, Odd if the sum of all elements in the hidden array is odd, or Impossible if the parity cannot be determined.

Note: You may print each character of the string in uppercase or lowercase (for example, the strings eVen, EvEn, even and EVEN will all be treated as identical).

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

$1 ≤ T ≤ 10000$
$1 ≤ N ≤ 10^{9}$
$0 ≤ A ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1 11
1 2
74120341 829182732
----- Sample Output 1 ------ 
Odd
Even
Impossible

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