vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Let N be an even number.
There is a tree with N vertices.
The vertices are numbered 1, 2, ..., N.
For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.
Snuke would like to decorate the tree with ribbons, as follows.
First, he will divide the N vertices into N / 2 pairs.
Here, each vertex must belong to exactly one pair.
Then, for each pair (u, v), put a ribbon through all the edges contained in the shortest path between u and v.
Snuke is trying to divide the vertices into pairs so that the following condition is satisfied: "for every edge, there is at least one ribbon going through it."
How many ways are there to divide the vertices into pairs, satisfying this condition?
Find the count modulo 10^9 + 7.
Here, two ways to divide the vertices into pairs are considered different when there is a pair that is contained in one of the two ways but not in the other.

-----Constraints-----
 - N is an even number.
 - 2 \leq N \leq 5000
 - 1 \leq x_i, y_i \leq N
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}

-----Output-----
Print the number of the ways to divide the vertices into pairs, satisfying the condition, modulo 10^9 + 7.

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

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

There are three possible ways to divide the vertices into pairs, as shown below, and two satisfy the condition: the middle one and the right one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 `N` candles are placed in a row, some of them are initially lit. For each candle from the 1st to the Nth the following algorithm is applied: if the observed candle is lit then states of this candle and all candles before it are changed to the opposite. Which candles will remain lit after applying the algorithm to all candles in the order they are placed in the line?

# Example

 For `a = [1, 1, 1, 1, 1]`, the output should be `[0, 1, 0, 1, 0].`

 Check out the image below for better understanding:
 
 

 ![](https://codefightsuserpics.s3.amazonaws.com/tasks/switchLights/img/example.png?_tm=1484040239470)
 
 
 
 For `a = [0, 0]`, the output should be `[0, 0].`

 The candles are not initially lit, so their states are not altered by the algorithm.

# Input/Output

 - `[input]` integer array `a`

     Initial situation - array of zeros and ones of length N, 1 means that the corresponding candle is lit.

    Constraints: `2 ≤ a.length ≤ 5000.`

 - `[output]` an integer array

    Situation after applying the algorithm - array in the same format as input with the same length.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
HackerLand Enterprise is adopting a new viral advertising strategy. When they launch a new product, they advertise it to exactly $5$ people on social media. 

On the first day, half of those $5$ people (i.e., $floor(\frac{5}{2})=2$) like the advertisement and each shares it with $3$ of their friends. At the beginning of the second day, $floor(\frac{5}{2})\times3=2\times3=6$ people receive the advertisement. 

Each day, $floor(\frac{recipients}{2})$ of the recipients like the advertisement and will share it with $3$ friends on the following day.  Assuming nobody receives the advertisement twice, determine how many people have liked the ad by the end of a given day, beginning with launch day as day $\mbox{1}$.

Example 

$n=5$. 

Day Shared Liked Cumulative
1      5     2       2
2      6     3       5
3      9     4       9
4     12     6      15
5     18     9      24

The progression is shown above.  The cumulative number of likes on the $5^{th}$ day is $24$.  

Function Description  

Complete the viralAdvertising function in the editor below.    

viralAdvertising has the following parameter(s):  

int n: the day number to report  

Returns  

int: the cumulative likes at that day   

Input Format

A single integer, $n$, the day number.

Constraints

$1\leq n\leq50$

Sample Input
3

Sample Output
9

Explanation

This example is depicted in the following diagram:  

$2$ people liked the advertisement on the first day, $3$ people liked the advertisement on the second day and $4$ people liked the advertisement on the third day, so the answer is $2+3+4=9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine two rings with numbers on them. The inner ring spins clockwise (decreasing by 1 each spin) and the outer ring spins counter clockwise (increasing by 1 each spin). We start with both rings aligned on 0 at the top, and on each move we spin each ring one increment. How many moves will it take before both rings show the same number at the top again?

The inner ring has integers from 0 to innerMax and the outer ring has integers from 0 to outerMax, where innerMax and outerMax are integers >= 1.

```
e.g. if innerMax is 2 and outerMax is 3 then after
1 move: inner = 2, outer = 1
2 moves: inner = 1, outer = 2
3 moves: inner = 0, outer = 3
4 moves: inner = 2, outer = 0
5 moves: inner = 1, outer = 1
Therefore it takes 5 moves for the two rings to reach the same number
Therefore spinningRings(2, 3) = 5
```
```
e.g. if innerMax is 3 and outerMax is 2 then after
1 move: inner = 3, outer = 1
2 moves: inner = 2, outer = 2
Therefore it takes 2 moves for the two rings to reach the same number
spinningRings(3, 2) = 2
```

---

for a bigger challenge, check out the [Performance Version](https://www.codewars.com/kata/59b0b7cd2a00d219ab0000c5) of this kata by @Voile

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Arpa's loud Owf and Mehrdad's evil plan

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As you have noticed, there are lovely girls in Arpa’s land.

People in Arpa's land are numbered from 1 to *n*. Everyone has exactly one crush, *i*-th person's crush is person with the number *crush**i*.

Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.

The game consists of rounds. Assume person *x* wants to start a round, he calls *crush**x* and says: "Oww...wwf" (the letter w is repeated *t* times) and cuts off the phone immediately. If *t*<=&gt;<=1 then *crush**x* calls *crush**crush**x* and says: "Oww...wwf" (the letter w is repeated *t*<=-<=1 times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (*t*<==<=1). This person is called the Joon-Joon of the round. There can't be two rounds at the same time.

Mehrdad has an evil plan to make the game more funny, he wants to find smallest *t* (*t*<=≥<=1) such that for each person *x*, if *x* starts some round and *y* becomes the Joon-Joon of the round, then by starting from *y*, *x* would become the Joon-Joon of the round. Find such *t* for Mehrdad if it's possible.

Some strange fact in Arpa's land is that someone can be himself's crush (i.e. *crush**i*<==<=*i*).

Input Specification:
The first line of input contains integer *n* (1<=≤<=*n*<=≤<=100) — the number of people in Arpa's land.

The second line contains *n* integers, *i*-th of them is *crush**i* (1<=≤<=*crush**i*<=≤<=*n*) — the number of *i*-th person's crush.

Output Specification:
If there is no *t* satisfying the condition, print -1. Otherwise print such smallest *t*.

Demo Input:
['4\n2 3 1 4\n', '4\n4 4 4 4\n', '4\n2 1 4 3\n']

Demo Output:
['3\n', '-1\n', '1\n']

Note:
In the first sample suppose *t* = 3. 

If the first person starts some round:

The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if *x* is 1.

The process is similar for the second and the third person.

If the fourth person starts some round:

The fourth person calls himself and says "Owwwf", then he calls himself again and says "Owwf", then he calls himself for another time and says "Owf", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when *x* is 4.

In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Irving & Cohen Petroleum Corporation has decided to develop a new oil field in an area. A preliminary survey has been done and they created a detailed grid map of the area which indicates the reserve of oil.

They are now planning to construct mining plants on several grid blocks according this map, but they decided not to place any two plants on adjacent positions to avoid spreading of fire in case of blaze. Two blocks are considered to be adjacent when they have a common edge. You are one of the programmers working for the company and your task is to write a program which calculates the maximum amount of oil they can mine, given the map of the reserve.



Input

The first line of the input specifies N, the number of test cases. Then N test cases follow, each of which looks like the following:


W H
r1,1 r2,1 . . . rW,1
...
r1,H r2,H . . . rW,H


The first line of a test case contains two integers W and H (1 ≤ W, H ≤ 20). They specifies the dimension of the area. The next H lines, each of which contains W integers, represent the map of the area. Each integer rx,y (0 ≤ rx,y < 10000) indicates the oil reserve at the grid block (x, y).

Output

For each test case, output the case number (starting from 1) and the maximum possible amount of mining in a line. Refer to the sample output section about the format.

Example

Input

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


Output

Case 1: 7
Case 2: 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S of lowercase english characters, find out whether the summation of X and Y is even or odd, where X is the count of distinct characters which occupy even positions in english alphabets and have positive even frequency, and Y is the count of distinct characters which occupy odd positions in english alphabets and have positive odd frequency.
Note: Positive means greater than zero.
Example 1:
Input: S = "abbbcc"
Output: "ODD"
Explanation: X = 0 and Y = 1 so (X + Y) is 
ODD. 'a' occupies 1st place(odd) in english 
alphabets and its frequency is odd(1), 'b' 
occupies 2nd place(even) but its frequency 
is odd(3) so it doesn't get counted and 'c' 
occupies 3rd place(odd) but its frequency 
is even(2) so it also doesn't get counted.
Example 2:
Input: S = "nobitaa"
Output: "EVEN"
Explanation: X = 0 and Y = 2 so (X + Y) is
EVEN.
Your Task:  
You dont need to read input or print anything. Complete the function evenOdd() which takes S as input parameter and returns "EVEN"  if  X + Y is even, "ODD" otherwise.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1) 
Constraints:
1 ≤ |S| ≤ 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's assume that   v(n) is the largest prime number, that does not exceed n;

 u(n) is the smallest prime number strictly greater than n. 

Find $\sum_{i = 2}^{n} \frac{1}{v(i) u(i)}$.


-----Input-----

The first line contains integer t (1 ≤ t ≤ 500) — the number of testscases. 

Each of the following t lines of the input contains integer n (2 ≤ n ≤ 10^9).


-----Output-----

Print t lines: the i-th of them must contain the answer to the i-th test as an irreducible fraction "p/q", where p, q are integers, q > 0.


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

Output
1/6
7/30

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.
Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.
Now, the following Q operations will be performed:
 - Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.
Find the value of the counter on each vertex after all operations.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq Q \leq 2 \times 10^5
 - 1 \leq a_i < b_i \leq N
 - 1 \leq p_j \leq N
 - 1 \leq x_j \leq 10^4
 - The given graph is a tree.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

-----Output-----
Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

-----Sample Input-----
4 3
1 2
2 3
2 4
2 10
1 100
3 1

-----Sample Output-----
100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:
 - Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.
 - Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.
 - Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kleofáš is participating in an n-thlon - a tournament consisting of n different competitions in n different disciplines (numbered 1 through n). There are m participants in the n-thlon and each of them participates in all competitions.

In each of these n competitions, the participants are given ranks from 1 to m in such a way that no two participants are given the same rank - in other words, the ranks in each competition form a permutation of numbers from 1 to m. The score of a participant in a competition is equal to his/her rank in it.

The overall score of each participant is computed as the sum of that participant's scores in all competitions.

The overall rank of each participant is equal to 1 + k, where k is the number of participants with strictly smaller overall score.

The n-thlon is over now, but the results haven't been published yet. Kleofáš still remembers his ranks in each particular competition; however, he doesn't remember anything about how well the other participants did. Therefore, Kleofáš would like to know his expected overall rank.

All competitors are equally good at each discipline, so all rankings (permutations of ranks of everyone except Kleofáš) in each competition are equiprobable.

Input

The first line of the input contains two space-separated integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 1000) — the number of competitions and the number of participants respectively.

Then, n lines follow. The i-th of them contains one integer xi (1 ≤ xi ≤ m) — the rank of Kleofáš in the i-th competition.

Output

Output a single real number – the expected overall rank of Kleofáš. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 9.

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

4 10
2
1
2
1


Output

1.0000000000000000


Input

5 5
1
2
3
4
5


Output

2.7500000000000000


Input

3 6
2
4
2


Output

1.6799999999999999

Note

In the first sample, Kleofáš has overall score 6. Nobody else can have overall score less than 6 (but it's possible for one other person to have overall score 6 as well), so his overall rank must be 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A star is a figure of the following type: an asterisk character '*' in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a star is the length of its rays. The size of a star must be a positive number (i.e. rays of length $0$ are not allowed).

Let's consider empty cells are denoted by '.', then the following figures are stars:

 [Image] The leftmost figure is a star of size $1$, the middle figure is a star of size $2$ and the rightmost figure is a star of size $3$. 

You are given a rectangular grid of size $n \times m$ consisting only of asterisks '*' and periods (dots) '.'. Rows are numbered from $1$ to $n$, columns are numbered from $1$ to $m$. Your task is to draw this grid using any number of stars or find out that it is impossible. Stars can intersect, overlap or even coincide with each other. The number of stars in the output can't exceed $n \cdot m$. Each star should be completely inside the grid. You can use stars of same and arbitrary sizes.

In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most $n \cdot m$ stars.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($3 \le n, m \le 100$) — the sizes of the given grid.

The next $n$ lines contains $m$ characters each, the $i$-th line describes the $i$-th row of the grid. It is guaranteed that grid consists of characters '*' and '.' only.


-----Output-----

If it is impossible to draw the given grid using stars only, print "-1".

Otherwise in the first line print one integer $k$ ($0 \le k \le n \cdot m$) — the number of stars needed to draw the given grid. The next $k$ lines should contain three integers each — $x_j$, $y_j$ and $s_j$, where $x_j$ is the row index of the central star character, $y_j$ is the column index of the central star character and $s_j$ is the size of the star. Each star should be completely inside the grid.


-----Examples-----
Input
6 8
....*...
...**...
..*****.
...**...
....*...
........

Output
3
3 4 1
3 5 2
3 5 1

Input
5 5
.*...
****.
.****
..**.
.....

Output
3
2 2 1
3 3 1
3 4 1

Input
5 5
.*...
***..
.*...
.*...
.....

Output
-1

Input
3 3
*.*
.*.
*.*

Output
-1



-----Note-----

In the first example the output 2

3 4 1

3 5 2



is also correct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is Fibonacci madness.
Given a number n. Print the first n Fibonacci numbers in reverse order.

Input:

First line is number T denoting number of test cases.
T lines follow. Each line has number N.

Output:

Print the first n Fibonacci numbers in reverse order for all test cases.

Constraints:

1 ≤ T ≤ 10

0 ≤ N ≤ 100

Example

Input:
3

1

7

4
Output:
0

8 5 3 2 1 1 0 

2 1 1 0

SAMPLE INPUT
3
1
7
4

SAMPLE OUTPUT
0 
8 5 3 2 1 1 0 
2 1 1 0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bajtek is learning to skate on ice. He's a beginner, so his only mode of transportation is pushing off from a snow drift to the north, east, south or west and sliding until he lands in another snow drift. He has noticed that in this way it's impossible to get from some snow drifts to some other by any sequence of moves. He now wants to heap up some additional snow drifts, so that he can get from any snow drift to any other one. He asked you to find the minimal number of snow drifts that need to be created.

We assume that Bajtek can only heap up snow drifts at integer coordinates.

Input Specification:
The first line of input contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of snow drifts. Each of the following *n* lines contains two integers *x**i* and *y**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=1000) — the coordinates of the *i*-th snow drift.

Note that the north direction coinсides with the direction of *Oy* axis, so the east direction coinсides with the direction of the *Ox* axis. All snow drift's locations are distinct.

Output Specification:
Output the minimal number of snow drifts that need to be created in order for Bajtek to be able to reach any snow drift from any other one.

Demo Input:
['2\n2 1\n1 2\n', '2\n2 1\n4 1\n']

Demo Output:
['1\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Raju has created a program to find the square root of a number. But his program can store only integers. Being a newbie, he didn't know about rounding the numbers. Hence his program returns the absolute value of the result if possible. For example, sqrt(3) = 1.73205080757……. His program will return 1
Given a number $N$, and it's integral square root $S$, His instructor will consider the answer correct if Difference between $N$ and the square of $S$ is within less than or equal to $X$% of $N$.

-----Input:-----
- First line contains $T$ no. of test cases and $X$ separated by space
- For every test case, a line contains an integer $N$

-----Output:-----
For every test case, print yes  if his programs return square root and (N-(S^2)) <= 0.01XN . For everything else, print no on a new line

-----Constraints-----
10 points:
- $1 \leq T \leq 10$
- $0\leq N \leq 10$
20 points:
- $1 \leq T \leq 30000$
- $-10^9 \leq N \leq 10^9$
70 points:
- $1 \leq T \leq 10^6$
- $-10^9 \leq N \leq 10^9$

-----Sample Input:-----
2 20
5
3

-----Sample Output:-----
yes
no

-----EXPLANATION:-----
In #1, sqrt(5) = 2.2360679775. Taking integral value, S = 2.

S2 = 4. Difference=1 which is within 20% of 5
In #1, sqrt(3) = 1.73205080757. Taking integral value, S = 1.

S2 = 1. Difference=2  which is not within 20% of 3

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

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of points on a plane.

Each of the next n lines contains two real coordinates x_{i} and y_{i} of the $i^{\text{th}}$ point, specified with exactly 2 fractional digits. All coordinates are between  - 1000 and 1000, inclusive.


-----Output-----

Output a single real number θ — the answer to the problem statement. The absolute or relative error of your answer should be at most 10^{ - 2}.


-----Examples-----
Input
8
-2.14 2.06
-1.14 2.04
-2.16 1.46
-2.14 0.70
-1.42 0.40
-0.94 -0.48
-1.42 -1.28
-2.16 -1.62

Output
5.410

Input
5
2.26 1.44
2.28 0.64
2.30 -0.30
1.58 0.66
3.24 0.66

Output
5.620

Input
8
6.98 2.06
6.40 1.12
5.98 0.24
5.54 -0.60
7.16 0.30
7.82 1.24
8.34 0.24
8.74 -0.76

Output
5.480

Input
5
10.44 2.06
10.90 0.80
11.48 -0.48
12.06 0.76
12.54 2.06

Output
6.040

Input
8
16.94 2.42
15.72 2.38
14.82 1.58
14.88 0.50
15.76 -0.16
16.86 -0.20
17.00 0.88
16.40 0.92

Output
6.040

Input
7
20.62 3.00
21.06 2.28
21.56 1.36
21.66 0.56
21.64 -0.52
22.14 2.32
22.62 3.04

Output
6.720

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