vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Idol --- It's the eternal longing of girls. However, only a handful stand at the top. You have decided to enter such a survival world as an idol producer. And today, I will take your idol and challenge an important audition.

The three elements that determine the audition are visual, dance, and vocal. There are m appeal times during the audition, and each idol can make a visual appeal, a dance appeal, or a vocal appeal for each appeal time. When you make a visual appeal, the idol's visual points are only her visual value, when you make a dance appeal, the dance points are only her dance value, and when you make a vocal appeal, the vocal points are only her vocal value. Will rise.

After m appeals, 3 of the N idols with the highest visual points have 5 audition points, 3 with the highest dance points have 3 audition points, and 3 with the highest vocal points. 2 Earn audition points. On the other hand, if the visual points are the lowest, the audition points will be deducted by 1 point, if the dance points are the lowest, the audition points will be deducted by 1 point, and if the vocal points are the lowest, the audition points will be deducted by 1 point. (Even if the audition point is 1 or less, 1 point will be deducted from it).

At the beginning of the audition, each idol has 0 visual points, dance points, and vocal points. You are the producer of Idol 1 and you can tell which appeal to make at each appeal time. Idols other than Idol 1 will randomly make one of the appeals at equal probability at each appeal time (that is, each with a one-third chance). If idol 1 has the same visual, dance, and vocal points as other idols, idol 1 is always inferior. Find the expected value when instructed to maximize the expected value of the audition points earned by Idol 1. The fate of an idol depends on your instructions!

By the way, all instructions are given before the audition starts, and the instructions cannot be changed during the audition after that. In other words, it is not possible for other idols to see which appeal they have made since the audition began and then give instructions to maximize the expected value in that case.



Input

The input is given in the form:

> n m
> vi1 da1 vo1
> vi2 da2 vo2
> ...
> vin dan von
>

The first line shows the number of idols participating in the audition n (4 ≤ n ≤ 2000) and the number of appeal times in this audition m (1 ≤ m ≤ 2000). The next n lines contain the visual value vii, dance value dai, and vocal value voi (1 ≤ vii, dai, voi ≤ 10,000) for idle i, respectively.

Output

Output the maximum expected value of audition points earned by idle 1 in one line.

Examples

Input

4 1
1 1 1
1 1 1
1 1 1
1 1 1


Output

2.777777777778


Input

4 10
1 1 1
10 10 10
10 10 10
10 10 10


Output

-2.335340954780


Input

9 9
13 5 19
19 21 37
15 1 7
7 11 15
21 23 25
33 29 19
13 19 11
21 5 15
7 13 1


Output

4.678837855075

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly x drops of the potion he made. 

Value of x is calculated as maximum of p·a_{i} + q·a_{j} + r·a_{k} for given p, q, r and array a_1, a_2, ... a_{n} such that 1 ≤ i ≤ j ≤ k ≤ n. Help Snape find the value of x. Do note that the value of x may be negative.


-----Input-----

First line of input contains 4 integers n, p, q, r ( - 10^9 ≤ p, q, r ≤ 10^9, 1 ≤ n ≤ 10^5).

Next line of input contains n space separated integers a_1, a_2, ... a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

Output a single integer the maximum value of p·a_{i} + q·a_{j} + r·a_{k} that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.


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

Output
30

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

Output
12



-----Note-----

In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are four stones on an infinite line in integer coordinates a_1, a_2, a_3, a_4. The goal is to have the stones in coordinates b_1, b_2, b_3, b_4. The order of the stones does not matter, that is, a stone from any position a_i can end up in at any position b_j, provided there is a required number of stones in each position (that is, if a coordinate x appears k times among numbers b_1, …, b_4, there should be exactly k stones at x in the end).

We are allowed to move stones with the following operation: choose two stones at distinct positions x and y with at least one stone each, and move one stone from x to 2y - x. In other words, the operation moves a stone to a symmetric position relative to some other stone. At any moment it is allowed to have any number of stones at the same position.

Find any sequence of operations that achieves the goal, or determine that it is impossible. The sequence does not have to be shortest, but it may contain at most 1000 operations.

Input

The first line contains four integers a_1, …, a_4 (-10^9 ≤ a_i ≤ 10^9) — initial coordinates of the stones. There may be multiple stones sharing the same coordinate.

The second line contains four integers b_1, …, b_4 (-10^9 ≤ b_i ≤ 10^9) — target coordinates of the stones. There may be multiple targets sharing the same coordinate.

Output

If there is no sequence of operations that achieves the goal, print a single integer -1. Otherwise, on the first line print a single integer k (0 ≤ k ≤ 1000) — the number of operations in your sequence. On the next k lines, describe the operations. The i-th of these lines should contain two integers x_i and y_i (x_i ≠ y_i) — coordinates of the moved stone and the center of symmetry stone for the i-th operation.

For each operation i, there should at least one stone in each of the coordinates x_i and y_i, and the resulting coordinate 2y_i - x_i must not exceed 10^{18} by absolute value.

If there are multiple suitable sequences, print any of them. It is guaranteed that if there is a suitable sequence of operations, then there is also a suitable sequence that satisfies all the additional requirement.

Examples

Input


0 1 2 3
3 5 6 8


Output


3
1 3
2 5
0 3


Input


0 0 0 0
1 1 1 1


Output


-1


Input


0 0 0 1
0 1 0 1


Output


-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bandwidth of a matrix A is defined as the smallest non-negative integer K such that A(i, j) = 0 for |i - j| > K.
For example, a matrix with all zeros will have its bandwith equal to zero. Similarly bandwith of diagonal matrix will also be zero.

For example, for the below given matrix, the bandwith of this matrix is 2.

1 0 0
0 1 1
1 1 0 

Bandwidth of the below matrix is 1. 

Bandwidth of the below matrix is 2. 

Bandwidth of the below matrix is also 2. 

You will be a given a binary matrix A of dimensions N × N. You are allowed to make following operation as many times as you wish (possibly zero or more). In a single operation, you can swap any two entries of the matrix. Your aim is to minimize the bandwidth of the matrix. Find the minimum bandwidth of the matrix A you can get after making as many operations of above type as you want.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follow.
First line of each test case contains an integer N denoting the height/width of the matrix.
Next N lines of each test case contain N space separated binary integers (either zero or one) corresponding to the entries of the matrix.

-----Output-----
For each test case, output a single integer corresponding to the minimum bandwidth that you can obtain.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 500
- 0 ≤ A(i, j) ≤ 1

-----Subtasks-----
- Subtask #1 (40 points) : 1 ≤ N ≤ 100
- Subtask #2 (60 points) : original constraints

-----Example-----
Input:
6
2
0 0
0 0
2
1 0
0 1
2
1 0
1 0
2
1 0
1 1
3
1 0 0
0 1 1
1 1 0
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Output:
0
0
0
1
1
3

-----Explanation-----
Example case 1. The bandwidth of a matrix will all zero entries will be zero. This is the minimum bandwidth you can get, so there is no need of performing any swap operation.
Example case 2. The bandwidth of a diagonal matrix will also be zero.
Example case 3. You can make the given matrix a diagonal matrix by swapping A(2, 1) and A(2, 2), which will have zero bandwidth.
Example case 4. You can not make swaps in any way that can reduce the bandwidth of this matrix. Bandwidth of this matrix is equal to 1, which is the minimum bandwidth that you can get.
Example case 5. Bandwidth of the given matrix is 2. You can make it equal to be 1 by swapping A(3, 1) and A(3, 3), i.e. the matrix after the operation will look like

1 0 0
0 1 1
0 1 1

The bandwidth of this matrix is 1.

Example case 6. The swap operations won't have any effect on the matrix. Its bandwidth is equal to 3.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has found a strange device. On the front panel of a device there are: a red button, a blue button and a display showing some positive integer. After clicking the red button, device multiplies the displayed number by two. After clicking the blue button, device subtracts one from the number on the display. If at some point the number stops being positive, the device breaks down. The display can show arbitrarily large numbers. Initially, the display shows number *n*.

Bob wants to get number *m* on the display. What minimum number of clicks he has to make in order to achieve this result?

Input Specification:
The first and the only line of the input contains two distinct integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=104), separated by a space .

Output Specification:
Print a single number — the minimum number of times one needs to push the button required to get the number *m* out of number *n*.

Demo Input:
['4 6\n', '10 1\n']

Demo Output:
['2\n', '9\n']

Note:
In the first example you need to push the blue button once, and then push the red button once.

In the second example, doubling the number is unnecessary, so we need to push the blue button nine times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
SaMer has written the greatest test case of all time for one of his problems. For a given array of integers, the problem asks to find the minimum number of groups the array can be divided into, such that the product of any pair of integers in the same group is a perfect square. 

Each integer must be in exactly one group. However, integers in a group do not necessarily have to be contiguous in the array.

SaMer wishes to create more cases from the test case he already has. His test case has an array $A$ of $n$ integers, and he needs to find the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$ for each integer $k$ between $1$ and $n$ (inclusive).


-----Input-----

The first line of input contains a single integer $n$ ($1 \leq n \leq 5000$), the size of the array.

The second line contains $n$ integers $a_1$,$a_2$,$\dots$,$a_n$ ($-10^8 \leq a_i \leq 10^8$), the values of the array.


-----Output-----

Output $n$ space-separated integers, the $k$-th integer should be the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$.


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

Output
3 0

Input
5
5 -4 2 1 8

Output
5 5 3 2 0

Input
1
0

Output
1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya wrote down two strings *s* of length *n* and *t* of length *m* consisting of small English letters 'a' and 'b'. What is more, he knows that string *t* has a form "abab...", namely there are letters 'a' on odd positions and letters 'b' on even positions.

Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string *s* were replaced by character '?'.

Let's call a sequence of positions *i*,<=*i*<=+<=1,<=...,<=*i*<=+<=*m*<=-<=1 as occurrence of string *t* in *s*, if 1<=≤<=*i*<=≤<=*n*<=-<=*m*<=+<=1 and *t*1<==<=*s**i*,<=*t*2<==<=*s**i*<=+<=1,<=...,<=*t**m*<==<=*s**i*<=+<=*m*<=-<=1.

The boy defines the beauty of the string *s* as maximum number of disjoint occurrences of string *t* in *s*. Vasya can replace some letters '?' with 'a' or 'b' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string *s* is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105) — the length of *s*.

The second line contains the string *s* of length *n*. It contains small English letters 'a', 'b' and characters '?' only.

The third line contains a single integer *m* (1<=≤<=*m*<=≤<=105) — the length of *t*. The string *t* contains letters 'a' on odd positions and 'b' on even positions.

Output Specification:
Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string *s* the maximum possible.

Demo Input:
['5\nbb?a?\n1\n', '9\nab??ab???\n3\n']

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

Note:
In the first sample string *t* has a form 'a'. The only optimal option is to replace all characters '?' by 'a'.

In the second sample using two replacements we can make string equal to "aba?aba??". It is impossible to get more than two occurrences.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A group of n cities is connected by a network of roads. There is an undirected road between every pair of cities, so there are $\frac{n \cdot(n - 1)}{2}$ roads in total. It takes exactly y seconds to traverse any single road.

A spanning tree is a set of roads containing exactly n - 1 roads such that it's possible to travel between any two cities using only these roads.

Some spanning tree of the initial network was chosen. For every road in this tree the time one needs to traverse this road was changed from y to x seconds. Note that it's not guaranteed that x is smaller than y.

You would like to travel through all the cities using the shortest path possible. Given n, x, y and a description of the spanning tree that was chosen, find the cost of the shortest path that starts in any city, ends in any city and visits all cities exactly once.


-----Input-----

The first line of the input contains three integers n, x and y (2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 10^9).

Each of the next n - 1 lines contains a description of a road in the spanning tree. The i-th of these lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n) — indices of the cities connected by the i-th road. It is guaranteed that these roads form a spanning tree.


-----Output-----

Print a single integer — the minimum number of seconds one needs to spend in order to visit all the cities exactly once.


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

Output
9

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

Output
8



-----Note-----

In the first sample, roads of the spanning tree have cost 2, while other roads have cost 3. One example of an optimal path is $5 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2$.

In the second sample, we have the same spanning tree, but roads in the spanning tree cost 3, while other roads cost 2. One example of an optimal path is $1 \rightarrow 4 \rightarrow 5 \rightarrow 2 \rightarrow 3$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have a directed acyclic graph *G*, consisting of *n* vertexes, numbered from 0 to *n*<=-<=1. The graph contains *n* edges numbered from 0 to *n*<=-<=1. An edge with number *i* connects vertexes *i* and (*i*<=+<=1) *mod* *n*, and it can be directed in either direction (from *i* to (*i*<=+<=1) *mod* *n*, or vise versa).

Operation *x* *mod* *y* means taking the remainder after dividing number *x* by number *y*.

Let's call two vertexes *u* and *v* in graph *G* comparable if the graph contains a path either from *u* to *v* or from *v* to *u*. We'll assume that an antichain is a set of vertexes of graph *G*, where any two distinct vertexes are not comparable. The size of an antichain is the number of vertexes in the corresponding set. An antichain is maximum if the graph doesn't have antichains of a larger size.

Your task is to find the size of the maximum antichain in graph *G*.

Input Specification:
The first line contains the sequence of characters *s*0*s*1... *s**n*<=-<=1 (2<=≤<=*n*<=≤<=106), consisting of numbers zero and one. The length of the line (number *n*) corresponds to the number of vertexes and edges in graph *G*. If character *s**i* (*i*<=≥<=0) equals 0, then the edge between vertexes *i* and (*i*<=+<=1) *mod* *n* is directed from the *i*-th vertex to the (*i*<=+<=1) *mod* *n*-th one, otherwise — to the opposite point.

It is guaranteed that the given graph is acyclic.

Output Specification:
Print a single integer — the size of the maximum antichain of graph *G*.

Demo Input:
['001\n', '110010\n']

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

Note:
Consider the first test sample. The graph's *G* edges are: 0 → 1, 1 → 2, 0 → 2. We can choose the set of vertexes [0] as the maximum antichain. We cannot choose an antichain of larger size.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the function/method so that it returns the url with anything after the anchor (`#`) removed. 

## Examples

```python
# returns 'www.codewars.com'
remove_url_anchor('www.codewars.com#about')

# returns 'www.codewars.com?page=1' 
remove_url_anchor('www.codewars.com?page=1') 
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are playing yet another card game. This time the rules are the following. There are $n$ cards lying in a row in front of them. The $i$-th card has value $a_i$. 

First, Alice chooses a non-empty consecutive segment of cards $[l; r]$ ($l \le r$). After that Bob removes a single card $j$ from that segment $(l \le j \le r)$. The score of the game is the total value of the remaining cards on the segment $(a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r)$. In particular, if Alice chooses a segment with just one element, then the score after Bob removes the only card is $0$.

Alice wants to make the score as big as possible. Bob takes such a card that the score is as small as possible.

What segment should Alice choose so that the score is maximum possible? Output the maximum score.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of cards.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-30 \le a_i \le 30$) — the values on the cards.


-----Output-----

Print a single integer — the final score of the game.


-----Examples-----
Input
5
5 -2 10 -1 4

Output
6

Input
8
5 2 5 3 -30 -30 6 9

Output
10

Input
3
-10 6 -15

Output
0



-----Note-----

In the first example Alice chooses a segment $[1;5]$ — the entire row of cards. Bob removes card $3$ with the value $10$ from the segment. Thus, the final score is $5 + (-2) + (-1) + 4 = 6$.

In the second example Alice chooses a segment $[1;4]$, so that Bob removes either card $1$ or $3$ with the value $5$, making the answer $5 + 2 + 3 = 10$.

In the third example Alice can choose any of the segments of length $1$: $[1;1]$, $[2;2]$ or $[3;3]$. Bob removes the only card, so the score is $0$. If Alice chooses some other segment then the answer will be less than $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note : Issues Fixed with python 2.7.6 , Use any one you like :D , ( Thanks to 

Time , time , time . Your task is to write a function that will return the degrees on a analog clock from a digital time that is passed in as parameter . The digital time is type string and will be in the format 00:00 . You also need to return the degrees on the analog clock in type string and format 360:360 . Remember to round of the degrees . Remeber the basic time rules and format like 24:00 = 00:00 and 12:60 = 13:00 . Create your own validation that should return "Check your time !" in any case the time is incorrect or the format is wrong , remember this includes passing in negatives times like "-01:-10".
``` 
A few examples :
clock_degree("00:00") will return : "360:360"
clock_degree("01:01") will return : "30:6"
clock_degree("00:01") will return : "360:6"
clock_degree("01:00") will return : "30:360"
clock_degree("01:30") will return : "30:180"
clock_degree("24:00") will return : "Check your time !"
clock_degree("13:60") will return : "Check your time !"
clock_degree("20:34") will return : "240:204"
```
Remember that discrete hour hand movement is required - snapping to each hour position and also coterminal angles are not allowed. Goodluck and Enjoy !

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is choosing three problems for creating a programming test. Totally he has n problems in his list. The complexity of the i-th problem equals r_i. All problems are numerated from 1 to n.

Help Polycarp to choose such three problems a, b and c, so that the complexity of the first problem strictly less than the complexity of second problem and the complexity of the second problem is strictly less than the complexity of the third problem. So, for chosen problems a, b and c it should be true that r_a < r_b < r_c.

If Polycarp can choose three problems in different ways, you can print any of them.

Input

The first line of the input contains one integer n (3 ≤ n ≤ 3000) — the number of problems in Polycarp's list.

The second line of the input contains n integers r_1, r_2, ..., r_n (1 ≤ r_i ≤ 10^9), where r_i is the complexity of the i-th problem.

Output

If Polycarp has no ways to choose three problems, you should print three numbers -1. Ih there is a way to choose them, you should print three different integers a, b, c (1 ≤ a, b, c ≤ n), where a is the number of the first chosen problem, b is the number of the second chosen problem and c is the number of the third chosen problem.

Examples

Input


6
3 1 4 1 5 9


Output


4 1 3 

Input


5
1 1000000000 1 1000000000 1


Output


-1 -1 -1


Input


9
10 10 11 10 10 10 10 10 1


Output


9 8 3 

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