vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As usual Gary and Flo are sitting at their favourite burger restaurant called Jim's Burgers. They want to treat themselves with delicious burger after an interesting day with lots of competitive programming. So they have ordered their burgers and are waiting for them. But with nothing to do, they get bored and decide to play a game.

The game is played on a sheet of paper with $n$ rows and $m$ columns and goes as follows: 

Flo places his white lotus tile somewhere at the top row and Gary places a caterpillar tile somewhere on the bottom row. Flo begins the game and their turns alternate. Flo can move his tile to any of the 8 adjacent cells, while Gary's caterpillar tile can only move  left or right, or stay at the same cell. Of course, they cannot step outside of the grid. Flo's goal is to catch Gary as fast as possible, that is, with the minimum number of moves, while Gary (with the caterpillar tile) has to survive for as long as possible.  

Now they are wondering: If they place their tiles in the corresponding rows and some random columns, what is the expected number of moves Flo has to make to win the game (assuming they will play optimally)? 

Can you help them answer this question?

Constraints

$2\leq n,m\leq5000$

Input Format

You will be given two space separated integers $n$ and $m$, denoting the number of rows and the number of columns on the board respectively. 

Output Format

Output the answer in one line. 

Note: The answer will be considered valid if it differs from the correct answer by at most $\mathbf{10^{-6}}$.

Sample input

2 3

Sample output

1.2222222

Consider the pair $(x,y)$ as the starting column of the lotus and the starting column of the caterpillar respectively. 

For $n=2$ and $m=3$ we get the following scenario. 

$(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)$ will lead to 1 move. 
The remaining pairs $(1,3)$ and $(3,1)$ will lead to 2 moves. So the expected value  is $\frac{1+1+1+1+1+1+1+2+2}{9}=1.222..$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given 3 numbers A, B, and C.

Determine whether the average of A and B is strictly greater than C or not?

NOTE: Average of A and B is defined as \frac{(A+B)}{2}. For example, average of 5 and 9 is 7, average of 5 and 8 is 6.5.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of 3 integers A, B, and C.

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

For each test case, output YES if average of A and B is strictly greater than C, NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YeS, yEs, yes and YES will all be treated as identical).

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

$1 ≤ T ≤ 1000$
$1 ≤ A, B, C ≤ 10$

----- Sample Input 1 ------ 
5
5 9 6
5 8 6
5 7 6
4 9 8
3 7 2

----- Sample Output 1 ------ 
YES
YES
NO
NO
YES

----- explanation 1 ------ 
Test case $1$: The average value of $5$ and $9$ is $7$ which is strictly greater than $6$.

Test case $2$: The average value of $5$ and $8$ is $6.5$ which is strictly greater than $6$.

Test case $3$: The average value of $5$ and $7$ is $6$ which is not strictly greater than $6$.

Test case $4$: The average value of $4$ and $9$ is $6.5$ which is not strictly greater than $8$.

Test case $5$: The average value of $3$ and $7$ is $5$ which is strictly greater than $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n water tanks in a row, i-th of them contains a_i liters of water. The tanks are numbered from 1 to n from left to right.

You can perform the following operation: choose some subsegment [l, r] (1≤ l ≤ r ≤ n), and redistribute water in tanks l, l+1, ..., r evenly. In other words, replace each of a_l, a_{l+1}, ..., a_r by \frac{a_l + a_{l+1} + ... + a_r}{r-l+1}. For example, if for volumes [1, 3, 6, 7] you choose l = 2, r = 3, new volumes of water will be [1, 4.5, 4.5, 7]. You can perform this operation any number of times.

What is the lexicographically smallest sequence of volumes of water that you can achieve?

As a reminder:

A sequence a is lexicographically smaller than a sequence b of the same length if and only if the following holds: in the first (leftmost) position where a and b differ, the sequence a has a smaller element than the corresponding element in b.

Input

The first line contains an integer n (1 ≤ n ≤ 10^6) — the number of water tanks.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6) — initial volumes of water in the water tanks, in liters.

Because of large input, reading input as doubles is not recommended.

Output

Print the lexicographically smallest sequence you can get. In the i-th line print the final volume of water in the i-th tank.

Your answer is considered correct if the absolute or relative error of each a_i does not exceed 10^{-9}.

Formally, let your answer be a_1, a_2, ..., a_n, and the jury's answer be b_1, b_2, ..., b_n. Your answer is accepted if and only if \frac{|a_i - b_i|}{max{(1, |b_i|)}} ≤ 10^{-9} for each i.

Examples

Input


4
7 5 5 7


Output


5.666666667
5.666666667
5.666666667
7.000000000


Input


5
7 8 8 10 12


Output


7.000000000
8.000000000
8.000000000
10.000000000
12.000000000


Input


10
3 9 5 5 1 7 5 3 8 7


Output


3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000

Note

In the first sample, you can get the sequence by applying the operation for subsegment [1, 3].

In the second sample, you can't get any lexicographically smaller sequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rooted tree with n vertices. The vertices are numbered from 1 to n, the root is the vertex number 1.

Each vertex has a color, let's denote the color of vertex v by c_{v}. Initially c_{v} = 0.

You have to color the tree into the given colors using the smallest possible number of steps. On each step you can choose a vertex v and a color x, and then color all vectices in the subtree of v (including v itself) in color x. In other words, for every vertex u, such that the path from root to u passes through v, set c_{u} = x.

It is guaranteed that you have to color each vertex in a color different from 0.

You can learn what a rooted tree is using the link: https://en.wikipedia.org/wiki/Tree_(graph_theory).


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^4) — the number of vertices in the tree.

The second line contains n - 1 integers p_2, p_3, ..., p_{n} (1 ≤ p_{i} < i), where p_{i} means that there is an edge between vertices i and p_{i}.

The third line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ n), where c_{i} is the color you should color the i-th vertex into.

It is guaranteed that the given graph is a tree. 


-----Output-----

Print a single integer — the minimum number of steps you have to perform to color the tree into given colors.


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

Output
3

Input
7
1 1 2 3 1 4
3 3 1 1 1 2 3

Output
5



-----Note-----

The tree from the first sample is shown on the picture (numbers are vetices' indices):

$A$

On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors):

[Image]

On seond step we color all vertices in the subtree of vertex 5 into color 1:

[Image]

On third step we color all vertices in the subtree of vertex 2 into color 1:

[Image]

The tree from the second sample is shown on the picture (numbers are vetices' indices):

[Image]

On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors):

[Image]

On second step we color all vertices in the subtree of vertex 3 into color 1:

$8$

On third step we color all vertices in the subtree of vertex 6 into color 2:

[Image]

On fourth step we color all vertices in the subtree of vertex 4 into color 1:

[Image]

On fith step we color all vertices in the subtree of vertex 7 into color 3:

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef likes to solve difficult tasks. This time, he tried to solve the Big Famous Unsolvable $A+B=C$. One of his friends played a prank on Chef and randomly shuffled the bits in $A$ and $B$ (independently in each number). However, the funny thing is that the sum of the resulting numbers remained $C$ even after shuffling.
Chef is now wondering: in how many ways is it possible to shuffle the bits of $A$ and the bits of $B$ such that their sum after shuffling is equal to $C$? Let's denote the integers obtained by shuffling the bits of $A$ and $B$ by $A_s$ and $B_s$ respectively; two ways $(A_{s1}, B_{s1})$ and $(A_{s2}, B_{s2})$ are considered distinct if $A_{s1} \neq A_{s2}$ or $B_{s1} \neq B_{s2}$.
It is allowed to add any number (possibly zero) of leading zeroes, i.e. bits $0$, to $A$ and any number of leading zeroes to $B$ before shuffling the bits.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains three space-separated integers $A$, $B$ and $C$. 

-----Output-----
For each test case, print a single line containing one integer — the number of ways to shuffle the bits.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le A, B, C \le 10^9$
- $A+B = C$

-----Subtasks-----
Subtask #1 (50 points): $1 \le A, B, C \le 10^5$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
1 2 3
369 428 797

-----Example Output-----
2
56

-----Explanation-----
Example case 1: We can consider $A=01$ and $B=10$ in binary. Then, there are two possible ways: swapping the two bits of $A$ and the two bits of $B$ ($A_s=10$, $B_s=01$ in binary, $2$ and $1$ in decimal representation) or not shuffling any bits.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Give a pair of integers (A, B) such that A^5-B^5 = X. It is guaranteed that there exists such a pair for the given integer X.

Constraints

* 1 \leq X \leq 10^9
* X is an integer.
* There exists a pair of integers (A, B) satisfying the condition in Problem Statement.

Input

Input is given from Standard Input in the following format:


X


Output

Print A and B, with space in between. If there are multiple pairs of integers (A, B) satisfying the condition, you may print any of them.


A B

Output

Print A and B, with space in between. If there are multiple pairs of integers (A, B) satisfying the condition, you may print any of them.


A B

Examples

Input

33


Output

2 -1


Input

1


Output

0 -1

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
On Bertown's main street *n* trees are growing, the tree number *i* has the height of *a**i* meters (1<=≤<=*i*<=≤<=*n*). By the arrival of the President of Berland these trees were decided to be changed so that their heights formed a beautiful sequence. This means that the heights of trees on ends (the 1st one and the *n*-th one) should be equal to each other, the heights of the 2-nd and the (*n*<=-<=1)-th tree must also be equal to each other, at that the height of the 2-nd tree should be larger than the height of the first tree by 1, and so on. In other words, the heights of the trees, standing at equal distance from the edge (of one end of the sequence) must be equal to each other, and with the increasing of the distance from the edge by 1 the tree height must also increase by 1. For example, the sequences "2 3 4 5 5 4 3 2" and "1 2 3 2 1" are beautiful, and '1 3 3 1" and "1 2 3 1" are not. 

Changing the height of a tree is a very expensive operation, using advanced technologies invented by Berland scientists. In one operation you can choose any tree and change its height to any number, either increase or decrease. Note that even after the change the height should remain a positive integer, i. e, it can't be less than or equal to zero. Identify the smallest number of changes of the trees' height needed for the sequence of their heights to become beautiful.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) which is the number of trees. The second line contains integers *a**i* (1<=≤<=*a**i*<=≤<=105) which are the heights of the trees.

Output Specification:
Print a single number which is the minimal number of trees whose heights will have to be changed for the sequence to become beautiful.

Demo Input:
['3\n2 2 2\n', '4\n1 2 2 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.
Title: Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Two players play a simple game. Each player is provided with a box with balls. First player's box contains exactly *n*1 balls and second player's box contains exactly *n*2 balls. In one move first player can take from 1 to *k*1 balls from his box and throw them away. Similarly, the second player can take from 1 to *k*2 balls from his box in his move. Players alternate turns and the first player starts the game. The one who can't make a move loses. Your task is to determine who wins if both players play optimally.

Input Specification:
The first line contains four integers *n*1,<=*n*2,<=*k*1,<=*k*2. All numbers in the input are from 1 to 50.

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

Output Specification:
Output "First" if the first player wins and "Second" otherwise.

Demo Input:
['2 2 1 2\n', '2 1 1 1\n']

Demo Output:
['Second\n', 'First\n']

Note:
Consider the first sample test. Each player has a box with 2 balls. The first player draws a single ball from his box in one move and the second player can either take 1 or 2 balls from his box in one move. No matter how the first player acts, the second player can always win if he plays wisely.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja has got an array, consisting of n integers, a_1, a_2, ..., a_{n}. Sereja is an active boy, so he is now going to complete m operations. Each operation will have one of the three forms:  Make v_{i}-th array element equal to x_{i}. In other words, perform the assignment a_{v}_{i} = x_{i}.  Increase each array element by y_{i}. In other words, perform n assignments a_{i} = a_{i} + y_{i} (1 ≤ i ≤ n).  Take a piece of paper and write out the q_{i}-th array element. That is, the element a_{q}_{i}. 

Help Sereja, complete all his operations.


-----Input-----

The first line contains integers n, m (1 ≤ n, m ≤ 10^5). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the original array.

Next m lines describe operations, the i-th line describes the i-th operation. The first number in the i-th line is integer t_{i} (1 ≤ t_{i} ≤ 3) that represents the operation type. If t_{i} = 1, then it is followed by two integers v_{i} and x_{i}, (1 ≤ v_{i} ≤ n, 1 ≤ x_{i} ≤ 10^9). If t_{i} = 2, then it is followed by integer y_{i} (1 ≤ y_{i} ≤ 10^4). And if t_{i} = 3, then it is followed by integer q_{i} (1 ≤ q_{i} ≤ n).


-----Output-----

For each third type operation print value a_{q}_{i}. Print the values in the order, in which the corresponding queries follow in the input.


-----Examples-----
Input
10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9

Output
2
9
11
20
30
40
39

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Levko loves sports pathfinding competitions in his city very much. In order to boost his performance, Levko spends his spare time practicing. The practice is a game.

The city consists of n intersections connected by m + k directed roads. Two or more roads can connect the same pair of intersections. Besides, there can be roads leading from an intersection to itself. 

Levko and Zenyk are playing a game. First Levko stands on intersection s1, and Zenyk stands on intersection s2. They both want to get to intersection f. The person who does it quicker wins. If they get there at the same time, the game ends with a draw. By agreement both players start simultaneously and move with the same speed.

Levko wants to win very much. He knows the lengths of all the roads in the city. Also he knows that he can change the lengths of some roads (there are k such roads at all) if he pays the government. So, the government can change the length of the i-th road to any integer value in the segment [li, ri] (both borders inclusive). Levko wondered if he can reconstruct the roads so as to win the game and whether he can hope for the draw if he cannot win.

You should consider that both players play optimally well. It is guaranteed that we can get from intersections s1 and s2 to intersection f. 

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 104, 1 ≤ k ≤ 100). The second line contains three integers s1, s2 and f (1 ≤ s1, s2, f ≤ n).

The next m lines contains the descriptions of the roads that cannot be changed by Levko. Each line contains three integers ai, bi and ci (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109), representing a road from intersection ai to intersection bi of length ci.

The next k lines contains the descriptions of the roads that can be changed by Levko. Each line contains four integers ai, bi, li and ri (1 ≤ ai, bi ≤ n, 1 ≤ li ≤ ri ≤ 109), representing a road from intersection ai to intersection bi, Levko can set the road's length within limits [li, ri].

Consider all intersections numbered from 1 to n. It is guaranteed that you can get from intersections s1 and s2 to intersection f.

Output

In the first line print string "WIN" (without the quotes) if Levko can win this game, string "DRAW" (without the quotes) if Levko can end the game with a draw and "LOSE" (without the quotes) if he loses for sure.

If the answer is "WIN" or "DRAW", then print on the second line k space-separated integers — the length of the roads Levko sets in the order they occur in the input.

Examples

Input

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


Output

WIN
1 1 3 

Input

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


Output

DRAW
1 1 2 

Input

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


Output

LOSE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
With your birthday coming up soon, your eccentric friend sent you a message to say "happy birthday":

    hhhappyyyy biirrrrrthddaaaayyyyyyy to youuuu
    hhapppyyyy biirtttthdaaay too youuu
    happy birrrthdayy to youuu
    happpyyyy birrtthdaaay tooooo youu

At first it looks like a song, but upon closer investigation, you realize that your friend hid the phrase "happy birthday" thousands of times inside his message. In fact, it contains it more than 2 million times! To thank him, you'd like to reply with exactly how many times it occurs.

To count all the occurences, the procedure is as follows: look through the paragraph and find a `'h'`; then find an `'a'` later in the paragraph; then find an `'p'` after that, and so on. Now count the number of ways in which you can choose letters in this way to make the full phrase.

More precisely, given a text string, you are to determine how many times the search string appears as a sub-sequence of that string.

Write a function called `countSubsequences` that takes two arguments: `needle`, the string to be search for and `haystack`, the string to search in. In our example, `"happy birthday"` is the needle and the birthday message is the haystack. The function should return the number of times `needle` occurs as a sub-sequence of `haystack`.  Spaces are also considered part of the needle.

Since the answers can be very large, return only the last 8 digits of the answer in case it exceeds 8 digits. The answers to the test cases will all be shorter than 8 digits.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
5-year-old Shinchan had just started learning mathematics. Meanwhile, one of his studious classmates, Kazama, had already written a basic calculator which supports only three operations on integers: multiplication $\left(\times)$, addition $\left(+\right)$, and subtraction $\left({-}\right)$.  Since he had just learned about these operations, he didn't know about operator precedence, and so, in his calculator, all operators had the same precedence and were left-associative.

As always, Shinchan started to irritate him with his silly questions. He gave Kazama a list of $n$ integers and asked him to insert one of the above operators between each pair of consecutive integers such that the result obtained after feeding the resulting expression in Kazama's calculator is divisible by $\mathbf{101}$. At his core, Shinchan is actually a good guy, so he only gave lists of integers for which an answer exists.  

Can you help Kazama create the required expression? If multiple solutions exist, print any one of them.   

Input Format

The first line contains a single integer $n$ denoting the number of elements in the list. The second line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ denoting the elements of the list.

Constraints

$2\leq n\leq10^4$
$1\leq a_i\leq100$
The length of the output expression should not exceed $\textbf{10n}$.

Output Format

Print a single line containing the required expressoin. You may insert spaces between operators and operands.

Note

You are not allowed to permute the list.
All operators have the same precedence and are left-associative, e.g., $a+b\times c-d\times e$ is interpreted as $((((a+b)\times c)-d)\times e)$
Unary plus and minus are not supported, e.g., statements like ${-a}$, $a\times-b$, or $-a\times b+c$ are invalid.

Sample Input 0
3
22 79 21

Sample Output 0
22*79-21

Explanation 0

Solution 1: $22\times79-21=1717$, where $1717\div101=17$, so it is perfectly divisible by $\mathbf{101}$. 

Solution 2: $22+79\times21=(22+79)\times21=2121$, which is also divisible by $\mathbf{101}$.

Sample Input 1
5
55 3 45 33 25

Sample Output 1
55+3-45*33-25

Explanation 1

$55+3-45\times33-25=((((55+3)-45)\times33)-25)=404$ which is divisible by $\mathbf{101}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given a set of distinct numbers. Your task is to find that even length subset which will give you a maximum value of P % (10^9 + 7). This value of P for a subset of length N is defined as below :

          P = (product of N/2 maximum values) / (product of N/2 minimum values)

Now suppose we have a subset S = {A1 , A3 ,  A4 , A5}
where A1 < A3  < A4 <  A5 , then P = (A4 *  A5) / (A1 *  A3)

Note : Subset should be of even length and should be non-empty and you have to output the maximum value of P % (10^9 + 7) i.e. that value which should be maximum after taking this mod.

 Input
First line of the input will contian T (number of test cases). Then for every test case first line will contain N (size of the set) and the next line will contain N space separated integers (elements of the set).
Output
For every test case print the required maximum value.
Constraints
1 ≤ T ≤ 5
2 ≤ N ≤ 16 
1 ≤ S[i] ≤ 10^9

SAMPLE INPUT
2
2
2 4
3
2 4 8

SAMPLE OUTPUT
2
4

Explanation

In the first test case the only subset of even length is { 2, 4} , so ans is 4/2 = 2. 
In the second test case the ans will be {2, 8} i.e. 8/2 = 4.

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