vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Degree Set

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a sequence of *n* positive integers *d*1,<=*d*2,<=...,<=*d**n* (*d*1<=&lt;<=*d*2<=&lt;<=...<=&lt;<=*d**n*). Your task is to construct an undirected graph such that:
 -  there are exactly *d**n*<=+<=1 vertices; -  there are no self-loops; -  there are no multiple edges; -  there are no more than 106 edges; -  its degree set is equal to *d*. 
Vertices should be numbered 1 through (*d**n*<=+<=1).

Degree sequence is an array *a* with length equal to the number of vertices in a graph such that *a**i* is the number of vertices adjacent to *i*-th vertex.

Degree set is a sorted in increasing order sequence of all distinct values from the degree sequence.

It is guaranteed that there exists such a graph that all the conditions hold, and it contains no more than 106 edges.

Print the resulting graph.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=300) — the size of the degree set.

The second line contains *n* integers *d*1,<=*d*2,<=...,<=*d**n* (1<=≤<=*d**i*<=≤<=1000, *d*1<=&lt;<=*d*2<=&lt;<=...<=&lt;<=*d**n*) — the degree set.

Output Specification:
In the first line print one integer *m* (1<=≤<=*m*<=≤<=106) — the number of edges in the resulting graph. It is guaranteed that there exists such a graph that all the conditions hold and it contains no more than 106 edges.

Each of the next *m* lines should contain two integers *v**i* and *u**i* (1<=≤<=*v**i*,<=*u**i*<=≤<=*d**n*<=+<=1) — the description of the *i*-th edge.

Demo Input:
['3\n2 3 4\n', '3\n1 2 3\n']

Demo Output:
['8\n3 1\n4 2\n4 5\n2 5\n5 1\n3 2\n2 1\n5 3\n', '4\n1 2\n1 3\n1 4\n2 3\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day, as Sherlock Holmes was tracking down one very important criminal, he found a wonderful painting on the wall. This wall could be represented as a plane. The painting had several concentric circles that divided the wall into several parts. Some parts were painted red and all the other were painted blue. Besides, any two neighboring parts were painted different colors, that is, the red and the blue color were alternating, i. e. followed one after the other. The outer area of the wall (the area that lied outside all circles) was painted blue. Help Sherlock Holmes determine the total area of red parts of the wall.

Let us remind you that two circles are called concentric if their centers coincide. Several circles are called concentric if any two of them are concentric.

Input Specification:
The first line contains the single integer *n* (1<=≤<=*n*<=≤<=100). The second line contains *n* space-separated integers *r**i* (1<=≤<=*r**i*<=≤<=1000) — the circles' radii. It is guaranteed that all circles are different.

Output Specification:
Print the single real number — total area of the part of the wall that is painted red. The answer is accepted if absolute or relative error doesn't exceed 10<=-<=4.

Demo Input:
['1\n1\n', '3\n1 4 2\n']

Demo Output:
['3.1415926536\n', '40.8407044967\n']

Note:
In the first sample the picture is just one circle of radius 1. Inner part of the circle is painted red. The area of the red part equals π × 1<sup class="upper-index">2</sup> = π.

In the second sample there are three circles of radii 1, 4 and 2. Outside part of the second circle is painted blue. Part between the second and the third circles is painted red. Part between the first and the third is painted blue. And, finally, the inner part of the first circle is painted red. Overall there are two red parts: the ring between the second and the third circles and the inner part of the first circle. Total area of the red parts is equal (π × 4<sup class="upper-index">2</sup> - π × 2<sup class="upper-index">2</sup>) + π × 1<sup class="upper-index">2</sup> = π × 12 + π = 13π

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Paul hates palindromes. He assumes that string *s* is tolerable if each its character is one of the first *p* letters of the English alphabet and *s* doesn't contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string *s* of length *n*. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.

Input Specification:
The first line contains two space-separated integers: *n* and *p* (1<=≤<=*n*<=≤<=1000; 1<=≤<=*p*<=≤<=26). The second line contains string *s*, consisting of *n* small English letters. It is guaranteed that the string is tolerable (according to the above definition).

Output Specification:
If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print "NO" (without the quotes).

Demo Input:
['3 3\ncba\n', '3 4\ncba\n', '4 4\nabcd\n']

Demo Output:
['NO\n', 'cbd\n', 'abda\n']

Note:
String *s* is lexicographically larger (or simply larger) than string *t* with the same length, if there is number *i*, such that *s*<sub class="lower-index">1</sub> = *t*<sub class="lower-index">1</sub>, ..., *s*<sub class="lower-index">*i*</sub> = *t*<sub class="lower-index">*i*</sub>, *s*<sub class="lower-index">*i* + 1</sub> &gt; *t*<sub class="lower-index">*i* + 1</sub>.

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N. Check if it is perfect or not. A number is perfect if sum of factorial of its digit is equal to the given number.
Example 1:
Input: N = 23
Output: 0
Explanation: The sum of factorials of 
digits of 23 is 2! + 3! = 2 + 6 = 8 
which is not equal to 23. Thus, answer 
is 0.
Example 2:
Input: N = 145
Output: 1
Explanation: The sum of factorials of digits 
of 145 is 1! + 4! + 5! = 1 + 24 + 120 = 145 
which is equal to 145.Thus, answer is 1.
Your Task:
You don't need to read input or print anything.Your task is to complete the function isPerfect() which takes a number N as input parameter and returns 1 if N is perfect.Otherwise, it returns 0.
Expected Time Complexity: O(Log_{10}N)
Expected Auxillary Space: O(constant)
Constraints:
1<=N<=10^{9}

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

You are in Poland and want to order a drink. You need to ask "One beer please": "Jedno piwo poprosze"

``` java
Translator.orderingBeers(1) = "Jedno piwo poprosze"
```

But let's say you are really thirsty and want several beers. Then you need to count in Polish. And more difficult, you need to understand the Polish grammar and cases (nominative, genitive, accustative and more).

## The grammar

In English, the plural of "beer" is simply "beers", with an "s". 

In Polish, the plural of "piwo" (nominative singular) is "piw" (genitive plural) or "piwa" (nominative plural). It depends!


The rules:

* usually the plural is genitive: "piw"
* but after the numerals 2, 3, 4, and compound numbers ending with them (e.g. 22, 23, 24), the noun is plural and takes the same case as the numeral, so nominative: "piwa"
* and exception to the exception: for 12, 13 and 14, it's the genitive plural again: "piw" (yes, I know, it's crazy!)


## The numbers

From 0 to 9:
    
    "zero", "jeden", "dwa", "trzy", "cztery", "piec", "szesc" , "siedem", "osiem", "dziewiec"

From 10 to 19 it's nearly the same, with "-ascie" at the end:

    "dziesiec", "jedenascie", "dwanascie", "trzynascie", "czternascie", "pietnascie", "szesnascie", "siedemnascie", "osiemnascie", "dziewietnascie"

Tens from 10 to 90 are nearly the same, with "-ziesci" or "ziesiat" at the end:

    "dziesiec", "dwadziescia", "trzydziesci", "czterdziesci", "piecdziesiat", "szescdziesiat", "siedemdziesiat", "osiemdziesiat", "dziewiecdziesiat"

Compound numbers are constructed similarly to English: tens + units. For example, 22 is "dwadziescia dwa".

"One" could be male ("Jeden"), female ("Jedna") or neuter ("Jedno"), which is the case for "beer" (piwo). But all other numbers are invariant, even if ending with "jeden".

Ah, and by the way, if you don't want to drink alcohol (so no beers are ordered), ask for mineral water instead: "Woda mineralna".

Note: if the number of beers is outside your (limited) Polish knowledge (0-99), raise an error!

---
More about the crazy polish grammar: https://en.wikipedia.org/wiki/Polish_grammar

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The government has invited bids from contractors to run canteens at all railway stations. Contractors will be allowed to bid for the catering contract at more than one station. However, to avoid monopolistic price-fixing, the government has declared that no contractor may bid for a pair of neighbouring stations.
The railway network has exactly one route between any pair of stations. Each station is directly connected by a railway line to at most $50$ neighbouring stations.
To help contractors plan their bids, the government has provided data on the number of passengers who pass through each station each year. Contractors would like to bid for stations with a higher volume of passenger traffic to increase their turnover.
For instance, suppose the railway network is as follows, where the volume of passenger traffic is indicated by the side of each station.

In this network, the best option for the contractor is to bid for stations $1, 2, 5$ and $6$, for a total passenger volume of $90$.
Your task is to choose a set of stations that the contractor should bid for so that the total volume of traffic across all the stations in the bid is maximized.

-----Input:-----
The first line of the input contains one integer $N$ indicating the number of railways stations in the network. The stations are numbered $1,2,...,N$. This is followed by $N$ lines of input, lines $2, 3,..., N+1$, indicating the volume of traffic at each station. The volume of traffic at station $i, 1 \leq i \leq N$, is given by a single integer in line $i+1$. The next $N-1$ lines of input, lines $N+2, N+3, ..., 2N$, describe the railway network. Each of these lines contains two integers, denoting a pair of stations that are neighbours.

-----Output:-----
The output should be a single integer, corresponding to the total volume of traffic across the set of stations in the optimal bid made by the contractor.

-----Constraints:-----
- $1 \leq N \leq 100000$. 
- Each railway station has at most $50$ neighbours.

-----Sample Input-----
6
10
20
25
40
30
30
4 5
1 3
3 4
2 3
6 4

-----Sample Output-----
90

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anthony and Cora play a very exciting game. Initially, Anthony has $N$ points and Cora has $M$ points. The game then goes on for several rounds, during each round, either Anthony wins or Cora wins, the loser of the round loses $1$ point while nothing happens to the winner of the round. The game ends when either Anthony or Cora has no points left, and the one still left with points is the winner of the game.

Cora promises Anthony a sweet prize if he wins the game, but will cruelly humiliate Anthony if he loses. Anthony can very accurately evaluate himself and perfectly predict that his probability of winning the round $i$ is exactly $p_ i$. Now, in order to decide whether to play this game with Cora or not, he needs to know the probability of him winning the game.

Help Anthony find his probability of winning!

-----Input-----
The first line contain integers $1\leq N,M\leq 1000$. $N+M-1$ lines follow, with the $i$-th line containing $0\leq p_ i\leq 1$, $p_ i$ has at most $6$ decimal digits.

-----Output-----
Output a single line containing the probability of Anthony winning this game. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$.

-----Examples-----
Sample Input:
1 1
0.500000
Sample Output:
0.500000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the method which returns the number which is most frequent in the given input array. If there is a tie for most frequent number, return the largest number among them.

Note: no empty arrays will be given.


## Examples

```
[12, 10, 8, 12, 7, 6, 4, 10, 12]              -->  12
[12, 10, 8, 12, 7, 6, 4, 10, 12, 10]          -->  12
[12, 10, 8, 8, 3, 3, 3, 3, 2, 4, 10, 12, 10]  -->   3
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the founder of the Bruce Arden Programming Collective, which is a tutoring programme that matches experienced programmers with newbies to teach them. You have $N$ students and $N$ tutors, but now you have to match them up. Since the students will have to travel to their tutors’ houses from their own (or vice versa) you decide to do your matching based on travel distance.

Minimising overall distance doesn’t seem fair; it might happen that one student has to travel a huge distance while all the other students get a tutor very close by, even though the tutors could have been split up so that each gets a tutor that is at least somewhat close.

Thus, you opt to minimise the distance travelled by the student who is worst off; one pairing of students to tutors is better than another if the student who has to travel farthest in the first pairing has to travel less far than the student who has to travel farthest in the second pairing.

Because the students live in a city, the distance that a student needs to travel is not the literal distance between them and their tutor. Instead, the distance between points $(X,Y)$ and $(X’,Y’)$ in the city is\[ |X - X’| + |Y - Y’|. \]

-----Input-----
The first line of the input contains an integer $N$, with $1 \leq N \leq 100$, the number of students and the number of tutors to pair up.

Then, there are $N$ lines, each with two integers with absolute value at most $10^8$, which give the locations of the $N$ students.

These are followed by $N$ lines, each with two integers with absolute value at most $10^8$, which give the locations of the $N$ tutors.

Note that it is possible for students and/or tutors to have identical locations (they may share a house).

-----Output-----
Output a single line containing a single integer $K$, where $K$ is the least integer such that there exists a pairing of students to tutors so that no pair has distance greater than $K$ between them.

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

Sample Input 2:
4
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
Sample Output 2:
2

Sample Input 3:
3
0 5
5 2
4 5
3 3
5 2
5 2
Sample Output 3:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Wall (hard)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
So many wall designs to choose from! Even modulo 106<=+<=3, it's an enormous number. Given that recently Heidi acquired an unlimited supply of bricks, her choices are endless! She really needs to do something to narrow them down.

Heidi is quick to come up with criteria for a useful wall:
 -  In a useful wall, at least one segment is wider than *W* bricks. This should give the zombies something to hit their heads against. Or, -  in a useful wall, at least one column is higher than *H* bricks. This provides a lookout from which zombies can be spotted at a distance. 
This should rule out a fair amount of possibilities, right? Help Heidi compute the number of useless walls that do not confirm to either of these criteria. In other words, a wall is useless if every segment has width at most *W* and height at most *H*.

Parameter *C*, the total width of the wall, has the same meaning as in the easy version. However, note that the number of bricks is now unlimited.

Output the number of useless walls modulo 106<=+<=3.

Input Specification:
The first and the only line of the input contains three space-separated integers *C*, *W* and *H* (1<=≤<=*C*<=≤<=108, 1<=≤<=*W*,<=*H*<=≤<=100).

Output Specification:
Output the number of different walls, modulo 106<=+<=3, which are useless according to Heidi's criteria.

Demo Input:
['1 1 1\n', '1 2 2\n', '1 2 3\n', '3 2 2\n', '5 4 9\n', '40 37 65\n']

Demo Output:
['2\n', '3\n', '4\n', '19\n', '40951\n', '933869\n']

Note:
If there is no brick in any of the columns, the structure is considered as a useless wall.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
General Payne has a battalion of n soldiers. The soldiers' beauty contest is coming up, it will last for k days. Payne decided that his battalion will participate in the pageant. Now he has choose the participants.

All soldiers in the battalion have different beauty that is represented by a positive integer. The value ai represents the beauty of the i-th soldier.

On each of k days Generals has to send a detachment of soldiers to the pageant. The beauty of the detachment is the sum of the beauties of the soldiers, who are part of this detachment. Payne wants to surprise the jury of the beauty pageant, so each of k days the beauty of the sent detachment should be unique. In other words, all k beauties of the sent detachments must be distinct numbers.

Help Payne choose k detachments of different beauties for the pageant. Please note that Payne cannot just forget to send soldiers on one day, that is, the detachment of soldiers he sends to the pageant should never be empty.

Input

The first line contains two integers n, k (1 ≤ n ≤ 50; 1 ≤ k ≤  <image>) — the number of soldiers and the number of days in the pageant, correspondingly. The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 107) — the beauties of the battalion soldiers.

It is guaranteed that Payne's battalion doesn't have two soldiers with the same beauty.

Output

Print k lines: in the i-th line print the description of the detachment that will participate in the pageant on the i-th day. The description consists of integer ci (1 ≤ ci ≤ n) — the number of soldiers in the detachment on the i-th day of the pageant and ci distinct integers p1, i, p2, i, ..., pci, i — the beauties of the soldiers in the detachment on the i-th day of the pageant. The beauties of the soldiers are allowed to print in any order.

Separate numbers on the lines by spaces. It is guaranteed that there is the solution that meets the problem conditions. If there are multiple solutions, print any of them.

Examples

Input

3 3
1 2 3


Output

1 1
1 2
2 3 2


Input

2 1
7 12


Output

1 12 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation $p$ of $n$ integers $1$, $2$, ..., $n$ (a permutation is an array where each element from $1$ to $n$ occurs exactly once).

Let's call some subsegment $p[l, r]$ of this permutation special if $p_l + p_r = \max \limits_{i = l}^{r} p_i$. Please calculate the number of special subsegments.


-----Input-----

The first line contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $p_1$, $p_2$, ..., $p_n$ ($1 \le p_i \le n$). All these integers are pairwise distinct.


-----Output-----

Print the number of special subsegments of the given permutation.


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

Output
2

Input
3
1 3 2

Output
1



-----Note-----

Special subsegments in the first example are $[1, 5]$ and $[1, 3]$.

The only special subsegment in the second example is $[1, 3]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your friend recently gave you some slimes for your birthday. You have a very large amount of slimes with value 1 and 2, and you decide to invent a game using these slimes.

You initialize a row with n empty spaces. You also choose a number p to be used in the game. Then, you will perform the following steps while the last space is empty. 

  1. With probability <image>, you will choose a slime with value 1, and with probability <image>, you will choose a slime with value 2. You place the chosen slime on the last space of the board. 
  2. You will push the slime to the left as far as possible. If it encounters another slime, and they have the same value v, you will merge the slimes together to create a single slime with value v + 1. This continues on until the slime reaches the end of the board, or encounters a slime with a different value than itself. 



You have played the game a few times, but have gotten bored of it. You are now wondering, what is the expected sum of all values of the slimes on the board after you finish the game.

Input

The first line of the input will contain two integers n, p (1 ≤ n ≤ 109, 1 ≤ p < 109).

Output

Print the expected sum of all slimes on the board after the game finishes. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

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 500000000


Output

3.562500000000000


Input

10 1


Output

64.999983360007620


Input

100 123456789


Output

269.825611298854770

Note

In the first sample, we have a board with two squares, and there is a 0.5 probability of a 1 appearing and a 0.5 probability of a 2 appearing.

Our final board states can be 1 2 with probability 0.25, 2 1 with probability 0.375, 3 2 with probability 0.1875, 3 1 with probability 0.1875. The expected value is thus (1 + 2)·0.25 + (2 + 1)·0.375 + (3 + 2)·0.1875 + (3 + 1)·0.1875 = 3.5625.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_{1}, a_{2}, \ldots, a_{n}$. You can remove at most one subsegment from it. The remaining elements should be pairwise distinct.

In other words, at most one time you can choose two integers $l$ and $r$ ($1 \leq l \leq r \leq n$) and delete integers $a_l, a_{l+1}, \ldots, a_r$ from the array. Remaining elements should be pairwise distinct. 

Find the minimum size of the subsegment you need to remove to make all remaining elements distinct.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 2000$) — the number of elements in the given array.

The next line contains $n$ spaced integers $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \le a_{i} \le 10^{9}$) — the elements of the array. 


-----Output-----

Print a single integer — the minimum size of the subsegment you need to remove to make all elements of the array pairwise distinct. If no subsegment needs to be removed, print $0$.


-----Examples-----
Input
3
1 2 3

Output
0

Input
4
1 1 2 2

Output
2

Input
5
1 4 1 4 9

Output
2



-----Note-----

In the first example all the elements are already distinct, therefore no subsegment needs to be removed.

In the second example you can remove the subsegment from index $2$ to $3$.

In the third example you can remove the subsegments from index $1$ to $2$, or from index $2$ to $3$, or from index $3$ to $4$.

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