vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In the previous challenge, you wrote code to perform an Insertion Sort on an unsorted array. But how would you prove that the code is correct? I.e. how do you show that for any input your code will provide the right output?

Loop Invariant 

In computer science, you could prove it formally with a loop invariant, where you state that a desired property is maintained in your loop. Such a proof is broken down into the following parts:

Initialization: It is true (in a limited sense) before the loop runs.
Maintenance: If it's true before an iteration of a loop, it remains true before the next iteration.
Termination: It will terminate in a useful way once it is finished. 

Insertion Sort's Invariant 

Say, you have some InsertionSort code, where the outer loop goes through the whole array $\mbox{A}$:

for(int i = 1; i < A.length; i++){
//insertion sort code

You could then state the following loop invariant:

At the start of every iteration of the outer loop (indexed with $\boldsymbol{i}$), the subarray until $ar[i]$ consists of the original elements that were there, but in sorted order. 

To prove Insertion Sort is correct, you will then demonstrate it for the three stages:

Initialization - The subarray starts with the first element of the array, and it is (obviously) sorted to begin with.

Maintenance - Each iteration of the loop expands the subarray, but keeps the sorted property. An element $\mbox{V}$  gets inserted into the array only when it is greater than the element to its left. Since the elements to its left have already been sorted, it means $\mbox{V}$ is greater than all the elements to its left, so the array remains sorted. (In Insertion Sort 2 we saw this by printing the array each time an element was properly inserted.)  

Termination - The code will terminate after $\boldsymbol{i}$ has reached the last element in the array, which means the sorted subarray has expanded to encompass the entire array. The array is now fully sorted.

You can often use a similar process to demonstrate the correctness of many algorithms. You can see these notes for more information.

Challenge

In the InsertionSort code below, there is an error. Can you fix it? Print the array only once, when it is fully sorted. 

Input Format

There will be two lines of input:

$\boldsymbol{\mathrm{~S~}}$ - the size of the array
$\textbf{arr}$ - the list of numbers that makes up the array

Constraints

$1\leq s\leq1000$ 

$-1500\le V\le1500,V\in\textit{arr}$

Output Format

Output the numbers in order, space-separated on one line.

Sample Input
6
7 4 3 5 6 2

Sample Output
2 3 4 5 6 7

Explanation

The corrected code returns the sorted array.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is data that records the altitude of mountains that have been climbed so far. Create a program that reads this data and outputs the elevation difference between the highest and lowest mountains.



Input

The input is given in the following format:


Mountain height
...
...


The height of the mountain is given over multiple lines. All values ​​entered are real numbers greater than or equal to 0 and less than or equal to 1,000,000. The number of mountain heights entered is 50 or less.

Output

The elevation difference between the highest mountain and the lowest mountain is output as a real number. The output may contain an error of 0.01 or less.

Example

Input

3776.0
1819.0
645.2
2004.1
1208.6


Output

3130.8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A smile house is created to raise the mood. It has n rooms. Some of the rooms are connected by doors. For each two rooms (number i and j), which are connected by a door, Petya knows their value cij — the value which is being added to his mood when he moves from room i to room j.

Petya wondered whether he can raise his mood infinitely, moving along some cycle? And if he can, then what minimum number of rooms he will need to visit during one period of a cycle?

Input

The first line contains two positive integers n and m (<image>), where n is the number of rooms, and m is the number of doors in the Smile House. Then follows the description of the doors: m lines each containing four integers i, j, cij и cji (1 ≤ i, j ≤ n, i ≠ j, - 104 ≤ cij, cji ≤ 104). It is guaranteed that no more than one door connects any two rooms. No door connects the room with itself.

Output

Print the minimum number of rooms that one needs to visit during one traverse of the cycle that can raise mood infinitely. If such cycle does not exist, print number 0.

Examples

Input

4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3


Output

4

Note

Cycle is such a sequence of rooms a1, a2, ..., ak, that a1 is connected with a2, a2 is connected with a3, ..., ak - 1 is connected with ak, ak is connected with a1. Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as k, the sequence's length. Note that the minimum possible length equals two.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Hexadecimal's theorem

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently, a chaotic virus Hexadecimal advanced a new theorem which will shake the Universe. She thinks that each Fibonacci number can be represented as sum of three not necessary different Fibonacci numbers.

Let's remember how Fibonacci numbers can be calculated. *F*0<==<=0, *F*1<==<=1, and all the next numbers are *F**i*<==<=*F**i*<=-<=2<=+<=*F**i*<=-<=1.

So, Fibonacci numbers make a sequence of numbers: 0, 1, 1, 2, 3, 5, 8, 13, ...

If you haven't run away from the PC in fear, you have to help the virus. Your task is to divide given Fibonacci number *n* by three not necessary different Fibonacci numbers or say that it is impossible.

Input Specification:
The input contains of a single integer *n* (0<=≤<=*n*<=&lt;<=109) — the number that should be represented by the rules described above. It is guaranteed that *n* is a Fibonacci number.

Output Specification:
Output three required numbers: *a*, *b* and *c*. If there is no answer for the test you have to print "I'm too stupid to solve this problem" without the quotes.

If there are multiple answers, print any of them.

Demo Input:
['3\n', '13\n']

Demo Output:
['1 1 1\n', '2 3 8\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid of square cells with H horizontal rows and W vertical columns. The cell at the i-th row and the j-th column will be denoted as Cell (i, j).
In Cell (i, j), a_{ij} coins are placed.
You can perform the following operation any number of times:
Operation: Choose a cell that was not chosen before and contains one or more coins, then move one of those coins to a vertically or horizontally adjacent cell.
Maximize the number of cells containing an even number of coins.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq H, W \leq 500
 - 0 \leq a_{ij} \leq 9

-----Input-----
Input is given from Standard Input in the following format:
H W
a_{11} a_{12} ... a_{1W}
a_{21} a_{22} ... a_{2W}
:
a_{H1} a_{H2} ... a_{HW}

-----Output-----
Print a sequence of operations that maximizes the number of cells containing an even number of coins, in the following format:
N
y_1 x_1 y_1' x_1'
y_2 x_2 y_2' x_2'
:
y_N x_N y_N' x_N'

That is, in the first line, print an integer N between 0 and H \times W (inclusive), representing the number of operations.
In the (i+1)-th line (1 \leq i \leq N), print four integers y_i, x_i, y_i' and x_i' (1 \leq y_i, y_i' \leq H and 1 \leq x_i, x_i' \leq W), representing the i-th operation. These four integers represents the operation of moving one of the coins placed in Cell (y_i, x_i) to a vertically or horizontally adjacent cell, (y_i', x_i').
Note that if the specified operation violates the specification in the problem statement or the output format is invalid, it will result in Wrong Answer.

-----Sample Input-----
2 3
1 2 3
0 1 1

-----Sample Output-----
3
2 2 2 3
1 1 1 2
1 3 1 2

Every cell contains an even number of coins after the following sequence of operations:
 - Move the coin in Cell (2, 2) to Cell (2, 3).
 - Move the coin in Cell (1, 1) to Cell (1, 2).
 - Move one of the coins in Cell (1, 3) to Cell (1, 2).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vanya and Food Processor

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed *h* and the processor smashes *k* centimeters of potato each second. If there are less than *k* centimeters remaining, than during this second processor smashes all the remaining potato.

Vanya has *n* pieces of potato, the height of the *i*-th piece is equal to *a**i*. He puts them in the food processor one by one starting from the piece number 1 and finishing with piece number *n*. Formally, each second the following happens:
 1.  If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece. 1.  Processor smashes *k* centimeters of potato (or just everything that is inside). 
Provided the information about the parameter of the food processor and the size of each potato in a row, compute how long will it take for all the potato to become smashed.

Input Specification:
The first line of the input contains integers *n*, *h* and *k* (1<=≤<=*n*<=≤<=100<=000,<=1<=≤<=*k*<=≤<=*h*<=≤<=109) — the number of pieces of potato, the height of the food processor and the amount of potato being smashed each second, respectively.

The second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=*h*) — the heights of the pieces.

Output Specification:
Print a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.

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

Demo Output:
['5\n', '10\n', '2\n']

Note:
Consider the first sample. 
 1.  First Vanya puts the piece of potato of height 5 into processor. At the end of the second there is only amount of height 2 remaining inside. 1.  Now Vanya puts the piece of potato of height 4. At the end of the second there is amount of height 3 remaining. 1.  Vanya puts the piece of height 3 inside and again there are only 3 centimeters remaining at the end of this second. 1.  Vanya finally puts the pieces of height 2 and 1 inside. At the end of the second the height of potato in the processor is equal to 3. 1.  During this second processor finally smashes all the remaining potato and the process finishes. 
In the second sample, Vanya puts the piece of height 5 inside and waits for 2 seconds while it is completely smashed. Then he repeats the same process for 4 other pieces. The total time is equal to 2·5 = 10 seconds.

In the third sample, Vanya simply puts all the potato inside the processor and waits 2 seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which manipulates a disjoint set S = {S1, S2, . . . , Sk}.

First of all, the program should read an integer n, then make a disjoint set where each element consists of 0, 1, ... n−1 respectively.

Next, the program should read an integer q and manipulate the set for q queries. There are two kinds of queries for different operations:

* unite(x, y): unites sets that contain x and y, say Sx and Sy, into a new set.
* same(x, y): determine whether x and y are in the same set.

Constraints

* 1 ≤ n ≤ 10000
* 1 ≤ q ≤ 100000
* x ≠ y

Input


n q
com1 x1 y1
com2 x2 y2
...
comq xq yq


In the first line, n and q are given. Then, q queries are given where com represents the type of queries. '0' denotes unite and '1' denotes same operation.

Output

For each same operation, print 1 if x and y are in the same set, otherwise 0, in a line.

Example

Input

5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0


Output

0
0
1
1
1
0
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Paul owns a catering company and business is booming. The company has $k$ catering teams, each in charge of one set of catering equipment. Every week, the company accepts $n$ catering requests for various events. For every request, they send a catering team with their equipment to the event location. The team delivers the food, sets up the equipment, and instructs the host on how to use the equipment and serve the food. After the event, the host is responsible for returning the equipment back to Paul’s company. 

Unfortunately, in some weeks the number of catering teams is less than the number of requests, so some teams may have to be used for more than one event. In these cases, the company cannot wait for the host to return the equipment and must keep the team on-site to move the equipment to another location. The company has an accurate estimate of the cost to move a set of equipment from any location to any other location. Given these costs, Paul wants to prepare an Advance Catering Map to service the requests while minimizing the total moving cost of equipment (including the cost of the first move), even if that means not using all the available teams. Paul needs your help to write a program to accomplish this task. The requests are sorted in ascending order of their event times and they are chosen in such a way that for any $i < j$, there is enough time to transport the equipment used in the $i^{th}$ request to the location of the $j^{th}$ request.

-----Input-----
The first line of input contains two integers $n$ ($1 \le n \le 100$) and $k$ ($1 \le k \le 100$) which are the number of requests and the number of catering teams, respectively. Following that are $n$ lines, where the $i^{th}$ line contains $n-i+1$ integers between $0$ and $1000000$ inclusive. The $j^{th}$ number in the $i^{th}$ line is the cost of moving a set of equipment from location $i$ to location $i+j$. The company is at location $1$ and the $n$ requests are at locations $2$ to $n+1$.

-----Output-----
Display the minimum moving cost to service all requests. (This amount does not include the cost of moving the equipment back to the catering company.)

-----Examples-----
Sample Input:
3 2
40 30 40
50 10
50
Sample Output:
80

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While Grisha was celebrating New Year with Ded Moroz, Misha gifted Sasha a small rectangular pond of size n × m, divided into cells of size 1 × 1, inhabited by tiny evil fishes (no more than one fish per cell, otherwise they'll strife!).

The gift bundle also includes a square scoop of size r × r, designed for fishing. If the lower-left corner of the scoop-net is located at cell (x, y), all fishes inside the square (x, y)...(x + r - 1, y + r - 1) get caught. Note that the scoop-net should lie completely inside the pond when used.

Unfortunately, Sasha is not that skilled in fishing and hence throws the scoop randomly. In order to not frustrate Sasha, Misha decided to release k fishes into the empty pond in such a way that the expected value of the number of caught fishes is as high as possible. Help Misha! In other words, put k fishes in the pond into distinct cells in such a way that when the scoop-net is placed into a random position among (n - r + 1)·(m - r + 1) possible positions, the average number of caught fishes is as high as possible.

Input

The only line contains four integers n, m, r, k (1 ≤ n, m ≤ 105, 1 ≤ r ≤ min(n, m), 1 ≤ k ≤ min(n·m, 105)).

Output

Print a single number — the maximum possible expected number of caught fishes.

You answer is considered correct, is its absolute or relative error does not exceed 10 - 9. Namely, let your answer be a, and the jury's answer be b. Your answer is considered correct, if <image>.

Examples

Input

3 3 2 3


Output

2.0000000000


Input

12 17 9 40


Output

32.8333333333

Note

In the first example you can put the fishes in cells (2, 1), (2, 2), (2, 3). In this case, for any of four possible positions of the scoop-net (highlighted with light green), the number of fishes inside is equal to two, and so is the expected value.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is stuck in a two dimensional maze having N rows and M columns. He needs to get out of the maze as soon as possible and arrive at the kitchen in order to serve his hungry customers. But, he can get out of the maze only if he is able to successfully find any magical path in the given maze.

A path is defined as magical if it starts from any of the cell (a,b) of the maze and ends at the cell (c,d) such that the following conditions are satisfied :-
- |a - c| + |b - d| = 1
- All the cells in the maze are traversed exactly once.
- It is allowed to move only in the four directions - up, down, left and right from the current cell.

-----Input-----
- First line of the input contains an integer T denoting the number of different types of scenarios.
- Each of the next T lines will contain two integers N, M denoting the dimensions of the maze.

-----Output-----
For each of the T scenarios, output a single line containing "Yes" or "No" (without quotes) denoting whether the Chef can get out of the maze or not.

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ N, M ≤ 1018

-----Subtasks-----
Subtask #1 : (30 points)
- 1 ≤ T ≤ 100
- 1 ≤ N, M ≤ 10

Subtask #2 : (70 points) 

Original Constraints

-----Example-----
Input:
1
2 2

Output:
Yes

-----Explanation-----
Example case 1.

Chef can start from (1,1), move down to (2,1), then move right to (2,2) and finally move upwards to reach (1,2). As, he is able to visit all the cells exactly once and sum of absolute differences of corresponding x and y dimension is 1, we can call this path a magical path.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Freddy has a really fat left pinky finger, and every time Freddy tries to type an ```A```, he accidentally hits the CapsLock key!

Given a string that Freddy wants to type, emulate the keyboard misses where each ```A``` supposedly pressed is replaced with CapsLock, and return the string that Freddy actually types. It doesn't matter if the ```A``` in the string is capitalized or not. When CapsLock is enabled, capitalization is reversed, but punctuation is not affected.

Examples:

```
"The quick brown fox jumps over the lazy dog."
-> "The quick brown fox jumps over the lZY DOG."

"The end of the institution, maintenance, and administration of government, is to secure the existence of the body politic, to protect it, and to furnish the individuals who compose it with the power of enjoying in safety and tranquillity their natural rights, and the blessings of life: and whenever these great objects are not obtained, the people have a right to alter the government, and to take measures necessary for their safety, prosperity and happiness."
-> "The end of the institution, mINTENnce, ND dministrTION OF GOVERNMENT, IS TO SECURE THE EXISTENCE OF THE BODY POLITIC, TO PROTECT IT, nd to furnish the individuLS WHO COMPOSE IT WITH THE POWER OF ENJOYING IN Sfety ND TRnquillity their nTURl rights, ND THE BLESSINGS OF LIFE: nd whenever these greT OBJECTS re not obtINED, THE PEOPLE Hve  RIGHT TO lter the government, ND TO Tke meSURES NECESSry for their sFETY, PROSPERITY nd hPPINESS."

"aAaaaaAaaaAAaAa"
-> ""
```

**Note!**

If (Caps Lock is Enabled) and then you (HOLD Shift + alpha character) it will always be the reverse

Examples:
```
(Caps Lock Enabled) + (HOLD Shift + Press 'b') = b
(Caps Lock Disabled) + (HOLD Shift + Press 'b') = B
```

If the given string is `""`, the answer should be evident.

Happy coding!

~~~if:fortran
*NOTE: In Fortran, your returned string is* **not** *permitted to contain any unnecessary leading/trailing whitespace.*
~~~


(Adapted from https://codegolf.stackexchange.com/questions/158132/no-a-just-caps-lock)

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. 

You want to make all these 3 numbers equal. To do this, you can perform any finite number of operations:
In the i^{th} operation, you must add 2^{(i-1)} to any one of these 3 numbers. 

Find whether you can make these 3 numbers equal in finite number of moves.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, three integers A, B, and C.

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

For each test case, output YES if you can make these 3 numbers equal, 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 ≤ 5000$
$1 ≤ A, B, C ≤ 10^{9}$

----- Sample Input 1 ------ 
4
4 4 3
1 6 7
3 4 3
2 3 4

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

----- explanation 1 ------ 
Test Case $1$: It is optimal to do only $1$ operation which is adding $2^{0}$ to $C=3$. After this, all the numbers becomes equal to $4$.

Test Case $2$: 
- In the first operation, add $2^{0}$ to $B=6$. Thus, numbers become $A=1, B=7,$ and $C=7$.
- In the second operation, add $2^{1}$ to $A=1$. Thus, numbers become $A=3, B=7,$ and $C=7$.
- In the third operation, add $2^{2}$ to $A=3$. Thus, numbers become $A=7, B=7,$ and $C=7$.

Thus, all the numbers become equal.

Test case $3$: It can be proven that the numbers cannot be made equal using any number of moves.

Test case $4$: 
- In the first operation, add $2^{0}$ to $B=3$. Thus, numbers become $A=2, B=4,$ and $C=4$.
- In the second operation, add $2^{1}$ to $A=2$. Thus, numbers become $A=4, B=4,$ and $C=4$.

Thus, all the numbers become equal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya wants to turn on Christmas lights consisting of m bulbs. Initially, all bulbs are turned off. There are n buttons, each of them is connected to some set of bulbs. Vasya can press any of these buttons. When the button is pressed, it turns on all the bulbs it's connected to. Can Vasya light up all the bulbs?

If Vasya presses the button such that some bulbs connected to it are already turned on, they do not change their state, i.e. remain turned on.


-----Input-----

The first line of the input contains integers n and m (1 ≤ n, m ≤ 100) — the number of buttons and the number of bulbs respectively. 

Each of the next n lines contains x_{i} (0 ≤ x_{i} ≤ m) — the number of bulbs that are turned on by the i-th button, and then x_{i} numbers y_{ij} (1 ≤ y_{ij} ≤ m) — the numbers of these bulbs.


-----Output-----

If it's possible to turn on all m bulbs print "YES", otherwise print "NO".


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

Output
YES

Input
3 3
1 1
1 2
1 1

Output
NO



-----Note-----

In the first sample you can press each button once and turn on all the bulbs. In the 2 sample it is impossible to turn on the 3-rd lamp.

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