vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Snuke has a sequence p, which is a permutation of (0,1,2, ...,N-1). The i-th element (0-indexed) in p is p_i.

He can perform N-1 kinds of operations labeled 1,2,...,N-1 any number of times in any order. When the operation labeled k is executed, the procedure represented by the following code will be performed:


for(int i=k;i<N;i++)
swap(p[i],p[i-k]);


He would like to sort p in increasing order using between 0 and 10^{5} operations (inclusive). Show one such sequence of operations. It can be proved that there always exists such a sequence of operations under the constraints in this problem.

Constraints

* 2 \leq N \leq 200
* 0 \leq p_i \leq N-1
* p is a permutation of (0,1,2,...,N-1).

Input

Input is given from Standard Input in the following format:


N
p_0 p_1 ... p_{N-1}


Output

Let m be the number of operations in your solution. In the first line, print m. In the i-th of the following m lines, print the label of the i-th executed operation. The solution will be accepted if m is at most 10^5 and p is in increasing order after the execution of the m operations.

Examples

Input

5
4 2 0 1 3


Output

4
2
3
1
2


Input

9
1 0 4 3 5 6 2 8 7


Output

11
3
6
1
3
5
2
4
7
8
6
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $n$ and $m$. You have to construct the array $a$ of length $n$ consisting of non-negative integers (i.e. integers greater than or equal to zero) such that the sum of elements of this array is exactly $m$ and the value $\sum\limits_{i=1}^{n-1} |a_i - a_{i+1}|$ is the maximum possible. Recall that $|x|$ is the absolute value of $x$.

In other words, you have to maximize the sum of absolute differences between adjacent (consecutive) elements. For example, if the array $a=[1, 3, 2, 5, 5, 0]$ then the value above for this array is $|1-3| + |3-2| + |2-5| + |5-5| + |5-0| = 2 + 1 + 3 + 0 + 5 = 11$. Note that this example doesn't show the optimal answer but it shows how the required value for some array is calculated.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^9$) — the length of the array and its sum correspondingly.


-----Output-----

For each test case, print the answer — the maximum possible value of $\sum\limits_{i=1}^{n-1} |a_i - a_{i+1}|$ for the array $a$ consisting of $n$ non-negative integers with the sum $m$.


-----Example-----
Input
5
1 100
2 2
5 5
2 1000000000
1000000000 1000000000

Output
0
2
10
1000000000
2000000000



-----Note-----

In the first test case of the example, the only possible array is $[100]$ and the answer is obviously $0$.

In the second test case of the example, one of the possible arrays is $[2, 0]$ and the answer is $|2-0| = 2$.

In the third test case of the example, one of the possible arrays is $[0, 2, 0, 3, 0]$ and the answer is $|0-2| + |2-0| + |0-3| + |3-0| = 10$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
PolandBall has such a convex polygon with n veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments. 

He chose a number k such that gcd(n, k) = 1. Vertices of the polygon are numbered from 1 to n in a clockwise way. PolandBall repeats the following process n times, starting from the vertex 1: 

Assume you've ended last operation in vertex x (consider x = 1 if it is the first operation). Draw a new segment from vertex x to k-th next vertex in clockwise direction. This is a vertex x + k or x + k - n depending on which of these is a valid index of polygon's vertex.

Your task is to calculate number of polygon's sections after each drawing. A section is a clear area inside the polygon bounded with drawn diagonals or the polygon's sides.


-----Input-----

There are only two numbers in the input: n and k (5 ≤ n ≤ 10^6, 2 ≤ k ≤ n - 2, gcd(n, k) = 1).


-----Output-----

You should print n values separated by spaces. The i-th value should represent number of polygon's sections after drawing first i lines.


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

Output
2 3 5 8 11 
Input
10 3

Output
2 3 4 6 9 12 16 21 26 31 


-----Note-----

The greatest common divisor (gcd) of two integers a and b is the largest positive integer that divides both a and b without a remainder.

For the first sample testcase, you should output "2 3 5 8 11". Pictures below correspond to situations after drawing lines. [Image] [Image] [Image] [Image] [Image] [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu is a renowned classical singer. He is invited to many big functions/festivals. Recently he was invited to "All World Classical Singing Festival". Other than Devu, comedian Churu was also invited.

Devu has provided organizers a list of the songs and required time for singing them. He will sing n songs, i^{th} song will take t_{i} minutes exactly. 

The Comedian, Churu will crack jokes. All his jokes are of 5 minutes exactly.

People have mainly come to listen Devu. But you know that he needs rest of 10 minutes after each song. On the other hand, Churu being a very active person, doesn't need any rest.

You as one of the organizers should make an optimal sсhedule for the event. For some reasons you must follow the conditions:  The duration of the event must be no more than d minutes;  Devu must complete all his songs;  With satisfying the two previous conditions the number of jokes cracked by Churu should be as many as possible. 

If it is not possible to find a way to conduct all the songs of the Devu, output -1. Otherwise find out maximum number of jokes that Churu can crack in the grand event.


-----Input-----

The first line contains two space separated integers n, d (1 ≤ n ≤ 100; 1 ≤ d ≤ 10000). The second line contains n space-separated integers: t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ 100).


-----Output-----

If there is no way to conduct all the songs of Devu, output -1. Otherwise output the maximum number of jokes that Churu can crack in the grand event.


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

Output
5

Input
3 20
2 1 1

Output
-1



-----Note-----

Consider the first example. The duration of the event is 30 minutes. There could be maximum 5 jokes in the following way:  First Churu cracks a joke in 5 minutes.  Then Devu performs the first song for 2 minutes.  Then Churu cracks 2 jokes in 10 minutes.  Now Devu performs second song for 2 minutes.  Then Churu cracks 2 jokes in 10 minutes.  Now finally Devu will perform his last song in 1 minutes.  

Total time spent is 5 + 2 + 10 + 2 + 10 + 1 = 30 minutes.

Consider the second example. There is no way of organizing Devu's all songs. Hence the answer is -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two lists V1 and V2 of sizes n and m respectively. Return the list of elements common to both the lists and return the list in sorted order. Duplicates may be there in the output list.
Example:
Input:
n = 5
v1[] = {3, 4, 2, 2, 4}
m = 4
v2[] = {3, 2, 2, 7}
Output:
2 2 3
Explanation:
The common elements in sorted order are {2 2 3}
Your Task:
This is a function problem. You need to complete the function common_element that takes both the lists as parameters and returns a list of common elements. 
Constraints:
1 ≤ n, m ≤ 10^{5}
1 ≤ V_{i} ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shinchan and Kazama both are playing with numbers. Shinchan gives Kazama an array of numbers and asks him to tell the minimum possible last number of a non decreasing sequence of length L. 
Note- Check the sample I/O for more clarity.  

INPUT-
Input consists of number of test cases T. Each test case contains size of array i.e N.
Next line contains N space separated elements of array.
Next line contains length of the non decreasing sequence i.e. L.  

OUTPUT- 
You have to print the minimum possible last number of a sequence and if their is no non-decreasing sequence of length L, then print "-1" without the quotes.  

CONSTRAINTS-
 1 ≤ T ≤ 100  
1 ≤ N ≤ 10^6
1 ≤ a[i] ≤ 10^6
1 ≤ L ≤ N

SAMPLE INPUT
1
7
9 7 2 5 4 11 12 
3

SAMPLE OUTPUT
11

Explanation

In sample input, possible non-decreasing sequences of length L=3 are   
(9,11,12) , (7,11,12) , (2,5,11) , (2,4,11) , (2,5,12)  , (2,4,12) , (2,11,12) ,  (5,11,12) , (4,11,12)    
and the minimum last number is 11 for the sequences (2,5,11) and (2,4,11). Hence, the answer is 11.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're playing a game called Osu! Here's a simplified version of it. There are n clicks in a game. For each click there are two outcomes: correct or bad. Let us denote correct as "O", bad as "X", then the whole play can be encoded as a sequence of n characters "O" and "X".

Using the play sequence you can calculate the score for the play as follows: for every maximal consecutive "O"s block, add the square of its length (the number of characters "O") to the score. For example, if your play can be encoded as "OOXOOOXXOO", then there's three maximal consecutive "O"s block "OO", "OOO", "OO", so your score will be 22 + 32 + 22 = 17. If there are no correct clicks in a play then the score for the play equals to 0.

You know that the probability to click the i-th (1 ≤ i ≤ n) click correctly is pi. In other words, the i-th character in the play sequence has pi probability to be "O", 1 - pi to be "X". You task is to calculate the expected score for your play.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of clicks. The second line contains n space-separated real numbers p1, p2, ..., pn (0 ≤ pi ≤ 1).

There will be at most six digits after the decimal point in the given pi.

Output

Print a single real number — the expected score for your play. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Examples

Input

3
0.5 0.5 0.5


Output

2.750000000000000


Input

4
0.7 0.2 0.1 0.9


Output

2.489200000000000


Input

5
1 1 1 1 1


Output

25.000000000000000

Note

For the first example. There are 8 possible outcomes. Each has a probability of 0.125.

  * "OOO"  →  32 = 9; 
  * "OOX"  →  22 = 4; 
  * "OXO"  →  12 + 12 = 2; 
  * "OXX"  →  12 = 1; 
  * "XOO"  →  22 = 4; 
  * "XOX"  →  12 = 1; 
  * "XXO"  →  12 = 1; 
  * "XXX"  →  0. 



So the expected score is <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese and Russian as well. 

	Let's consider a set of points S. Initially, S is an empty set. Your task is to implement a data structure that can process the following queries efficiently:

			"+ X Y" - add a new point P with coordinates (X, Y) to S. It's guaranteed that this point will not be in S.
		
			"- N" - remove a point that was added during the N'th adding query from S. All of the adding queries are numbered in the order of their appearance starting from 1 (queries of other types are not included). It's guaranteed that this point is in S.
		
			"? X Y" - calculate the maximal Manhattan distance between a point P with coordinates (X, Y) and any point from S. It's guaranteed that S will not be empty.
		
	In addition, you won't be given the exact query data, but instead should decode it in the following way:

	Let's store the result of the last processed query of the third type in a variable called ANSWER. Initially, ANSWER is equal to 0. You will be given X', Y' and N' instead of the real values of X, Y and N. To get the real data you should perform the following computations:

			X = X' xor ANSWER;
		
			Y = Y' xor ANSWER;
		
			N = N' xor ANSWER.
		
	Don't forget to update the value of ANSWER after processing each query of the third type.

------ Note ------ 

	Maybe some of you aren't familiar with some terms in the statement. Here are some articles that could help you understand the problem correctly:

XOR operation: http://en.wikipedia.org/wiki/Exclusive_{or}
Manhattan distance: http://en.wikipedia.org/wiki/Taxicab_{geometry}

------ Input ------ 

	The first line of the input contains one integer Q denoting the number of queries to process.

	Each of the next Q lines contains a query to process in the format described above.

------ Output ------ 

	For each query on the third type you should output your answer on a new line.

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

1 ≤ Q ≤ 500,000(5 × 10^{5});
0 ≤ X', Y', N'  < 2^{31} for each query;
0 ≤ X, Y ≤ 10^{9} for each query.

------ Example ------ 

Input:
10
+ 8 1
1
+ 3 9
? 8 4
? 8 8
? 12 0
+ 6 5
? 7 8
? 4 5
9

Output:
10
8
2
4
11

------ Explanations ------ 

Here's a non-encrypted version of the example:

10
+ 8 1
1
+ 3 9
? 8 4
? 2 2
? 4 8
+ 4 7
? 5 10
? 0 1
2
The answers are the same.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three multisets of pairs of colored sticks:   $R$ pairs of red sticks, the first pair has length $r_1$, the second pair has length $r_2$, $\dots$, the $R$-th pair has length $r_R$;  $G$ pairs of green sticks, the first pair has length $g_1$, the second pair has length $g_2$, $\dots$, the $G$-th pair has length $g_G$;  $B$ pairs of blue sticks, the first pair has length $b_1$, the second pair has length $b_2$, $\dots$, the $B$-th pair has length $b_B$; 

You are constructing rectangles from these pairs of sticks with the following process:   take a pair of sticks of one color;  take a pair of sticks of another color different from the first one;  add the area of the resulting rectangle to the total area. 

Thus, you get such rectangles that their opposite sides are the same color and their adjacent sides are not the same color.

Each pair of sticks can be used at most once, some pairs can be left unused. You are not allowed to split a pair into independent sticks.

What is the maximum area you can achieve?


-----Input-----

The first line contains three integers $R$, $G$, $B$ ($1 \le R, G, B \le 200$) — the number of pairs of red sticks, the number of pairs of green sticks and the number of pairs of blue sticks.

The second line contains $R$ integers $r_1, r_2, \dots, r_R$ ($1 \le r_i \le 2000$) — the lengths of sticks in each pair of red sticks.

The third line contains $G$ integers $g_1, g_2, \dots, g_G$ ($1 \le g_i \le 2000$) — the lengths of sticks in each pair of green sticks.

The fourth line contains $B$ integers $b_1, b_2, \dots, b_B$ ($1 \le b_i \le 2000$) — the lengths of sticks in each pair of blue sticks.


-----Output-----

Print the maximum possible total area of the constructed rectangles.


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

Output
20

Input
2 1 3
9 5
1
2 8 5

Output
99

Input
10 1 1
11 7 20 15 19 14 2 4 13 14
8
11

Output
372



-----Note-----

In the first example you can construct one of these rectangles: red and green with sides $3$ and $5$, red and blue with sides $3$ and $4$ and green and blue with sides $5$ and $4$. The best area of them is $4 \times 5 = 20$.

In the second example the best rectangles are: red/blue $9 \times 8$, red/blue $5 \times 5$, green/blue $2 \times 1$. So the total area is $72 + 25 + 2 = 99$.

In the third example the best rectangles are: red/green $19 \times 8$ and red/blue $20 \times 11$. The total area is $152 + 220 = 372$. Note that you can't construct more rectangles because you are not allowed to have both pairs taken to be the same color.

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

Given an array a of size n containing only 0,-1,and 1,

x = number of 1's in a[l,r] (in subarray from l to r)

y = number of -1's in a[l,r] (in subarray from l to r)

For any sub array [l,r] function f is defined as follows

if(y == 0)

f([l,r]) = 0;

else

f([l,r]) = x / y;

Your goal is determine the maximum value of the function f.
Print the maximum value in most reduced fraction form i.e. p/q where gcd(p,q) = 1.

Input Format:

First line contains T, the number of test cases (1 ≤ T ≤ 10)

For each test case line,first line contains n, the size of array (1 ≤ n ≤ 10^5)

Second line of each test case contains n space separated integers. (a[i] /belongs to/ {-1,0,1})

Output Format:

Print maximum value of function f in reduced fraction form without any spaces for each test case in a single line

Author : Sumeet Varma

SAMPLE INPUT
2
2
1 1
3
1 1 -1

SAMPLE OUTPUT
0/1
2/1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a 2-D binary matrix of size n*m, where 0 represents an empty space while 1 represents a wall you cannot walk through. You are also given an integer k.
You can walk up, down, left, or right. Given that you can remove up to k walls, return the minimum number of steps to walk from the top left corner (0, 0) to the bottom right corner (n-1, m-1).
Note: If there is no way to walk from the top left corner to the bottom right corner, return -1.
Example 1:
Input: n = 3, m = 3, k = 1
mat = {{0, 0, 0},
       {0, 0, 1},
       {0, 1, 0}}
Output:
4
Explanation:
We can remove any one of the walls and
reach the bottom in 4 moves.  
Example 2:
Input:
n = 2, m = 2, k = 0
mat[] = {{0, 1},
         {1, 0}}
Output:
-1
Explanation:
There's no way of reaching the bottom
corner without removing any walls.
Your Task:
The task is to complete the function shotestPath() which takes three integers n, m, and k and also a matrix of size n*m as input and returns the minimum number of steps to walk from the top left corner to the bottom right corner.
Constraints:
1 ≤ n,m ≤ 50
0 ≤ k ≤ n*m
Top left and bottom right corners doesn't have 1
Expected Time Complexity: O(n*m*k).
Expected Auxiliary Space: O(n*m*k).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Bubble Cup hypothesis stood unsolved for $130$ years. Who ever proves the hypothesis will be regarded as one of the greatest mathematicians of our time! A famous mathematician Jerry Mao managed to reduce the hypothesis to this problem:

Given a number $m$, how many polynomials $P$ with coefficients in set ${\{0,1,2,3,4,5,6,7\}}$ have: $P(2)=m$?

Help Jerry Mao solve the long standing problem!


-----Input-----

The first line contains a single integer $t$ $(1 \leq t \leq 5\cdot 10^5)$ - number of test cases.

On next line there are $t$ numbers, $m_i$ $(1 \leq m_i \leq 10^{18})$ - meaning that in case $i$ you should solve for number $m_i$.


-----Output-----

For each test case $i$, print the answer on separate lines: number of polynomials $P$ as described in statement such that $P(2)=m_i$, modulo $10^9 + 7$.


-----Example-----
Input
2
2 4

Output
2
4



-----Note-----

In first case, for $m=2$, polynomials that satisfy the constraint are $x$ and $2$.

In second case, for $m=4$, polynomials that satisfy the constraint are $x^2$, $x + 2$, $2x$ and $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Artem and Random Variable

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Artyom decided to study probability theory. He found a book with a lot of nice exercises and now wants you to help him with one of them.

Consider two dices. When thrown each dice shows some integer from 1 to *n* inclusive. For each dice the probability of each outcome is given (of course, their sum is 1), and different dices may have different probability distributions.

We throw both dices simultaneously and then calculate values *max*(*a*,<=*b*) and *min*(*a*,<=*b*), where *a* is equal to the outcome of the first dice, while *b* is equal to the outcome of the second dice. You don't know the probability distributions for particular values on each dice, but you know the probability distributions for *max*(*a*,<=*b*) and *min*(*a*,<=*b*). That is, for each *x* from 1 to *n* you know the probability that *max*(*a*,<=*b*) would be equal to *x* and the probability that *min*(*a*,<=*b*) would be equal to *x*. Find any valid probability distribution for values on the dices. It's guaranteed that the input data is consistent, that is, at least one solution exists.

Input Specification:
First line contains the integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of different values for both dices.

Second line contains an array consisting of *n* real values with up to 8 digits after the decimal point  — probability distribution for *max*(*a*,<=*b*), the *i*-th of these values equals to the probability that *max*(*a*,<=*b*)<==<=*i*. It's guaranteed that the sum of these values for one dice is 1. The third line contains the description of the distribution *min*(*a*,<=*b*) in the same format.

Output Specification:
Output two descriptions of the probability distribution for *a* on the first line and for *b* on the second line. 

The answer will be considered correct if each value of max(*a*,<=*b*) and min(*a*,<=*b*) probability distribution values does not differ by more than 10<=-<=6 from ones given in input. Also, probabilities should be non-negative and their sums should differ from 1 by no more than 10<=-<=6.

Demo Input:
['2\n0.25 0.75\n0.75 0.25\n', '3\n0.125 0.25 0.625\n0.625 0.25 0.125\n']

Demo Output:
['0.5 0.5 \n0.5 0.5 \n', '0.25 0.25 0.5 \n0.5 0.25 0.25 \n']

Note:
none

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