vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This is an easier version of the problem. In this version, $n \le 2000$.

There are $n$ distinct points in three-dimensional space numbered from $1$ to $n$. The $i$-th point has coordinates $(x_i, y_i, z_i)$. The number of points $n$ is even.

You'd like to remove all $n$ points using a sequence of $\frac{n}{2}$ snaps. In one snap, you can remove any two points $a$ and $b$ that have not been removed yet and form a perfectly balanced pair. A pair of points $a$ and $b$ is perfectly balanced if no other point $c$ (that has not been removed yet) lies within the axis-aligned minimum bounding box of points $a$ and $b$.

Formally, point $c$ lies within the axis-aligned minimum bounding box of points $a$ and $b$ if and only if $\min(x_a, x_b) \le x_c \le \max(x_a, x_b)$, $\min(y_a, y_b) \le y_c \le \max(y_a, y_b)$, and $\min(z_a, z_b) \le z_c \le \max(z_a, z_b)$. Note that the bounding box might be degenerate. 

Find a way to remove all points in $\frac{n}{2}$ snaps.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 2000$; $n$ is even), denoting the number of points.

Each of the next $n$ lines contains three integers $x_i$, $y_i$, $z_i$ ($-10^8 \le x_i, y_i, z_i \le 10^8$), denoting the coordinates of the $i$-th point.

No two points coincide.


-----Output-----

Output $\frac{n}{2}$ pairs of integers $a_i, b_i$ ($1 \le a_i, b_i \le n$), denoting the indices of points removed on snap $i$. Every integer between $1$ and $n$, inclusive, must appear in your output exactly once.

We can show that it is always possible to remove all points. If there are many solutions, output any of them.


-----Examples-----
Input
6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0

Output
3 6
5 1
2 4

Input
8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 2 3

Output
4 5
1 6
2 7
3 8



-----Note-----

In the first example, here is what points and their corresponding bounding boxes look like (drawn in two dimensions for simplicity, as all points lie on $z = 0$ plane). Note that order of removing matters: for example, points $5$ and $1$ don't form a perfectly balanced pair initially, but they do after point $3$ is removed.  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N piles of stones arranged in a row.  The i-th pile has stones[i] stones.
A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.
Find the minimum cost to merge all piles of stones into one pile.  If it is impossible, return -1.
 

Example 1:
Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.


Example 2:
Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.


Example 3:
Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation: 
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

 
Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Task
To charge your mobile phone battery, do you know how much time it takes from 0% to 100%? It depends on your cell phone battery capacity and the power of the charger. A rough calculation method is:

```
0% --> 85%  (fast charge)
(battery capacity(mAh) * 85%) / power of the charger(mA)

85% --> 95% (decreasing charge)
(battery capacity(mAh) * 10%) / (power of the charger(mA) * 50%)

95% --> 100% (trickle charge)
(battery capacity(mAh) * 5%) / (power of the charger(mA) * 20%)
```
For example: Your battery capacity is 1000 mAh and you use a charger 500 mA,  to charge your mobile phone battery from 0% to 100% needs time:

```
0% --> 85%  (fast charge) 1.7 (hour)

85% --> 95% (decreasing charge) 0.4 (hour)

95% --> 100% (trickle charge) 0.5 (hour)

total times = 1.7 + 0.4 + 0.5 = 2.6 (hour)
```

 Complete function `calculateTime` that accepts two arguments `battery` and `charger`, return how many hours can charge the battery from 0% to 100%. The result should be a number, round to 2 decimal places (In Haskell, no need to round it).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:


Input Specification:
The input contains a single integer *a* (0<=≤<=*a*<=≤<=1<=000<=000).

Output Specification:
Output a single integer.

Demo Input:
['129\n']

Demo Output:
['1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string s written on the door consisting of characters '(', ')' and '#'. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each '#' with one or more ')' characters so that the final string becomes beautiful. 

Below there was also written that a string is called beautiful if for each i (1 ≤ i ≤ |s|) there are no more ')' characters than '(' characters among the first i characters of s and also the total number of '(' characters is equal to the total number of ')' characters. 

Help Malek open the door by telling him for each '#' character how many ')' characters he must replace it with.


-----Input-----

The first line of the input contains a string s (1 ≤ |s| ≤ 10^5). Each character of this string is one of the characters '(', ')' or '#'. It is guaranteed that s contains at least one '#' character.


-----Output-----

If there is no way of replacing '#' characters which leads to a beautiful string print  - 1. Otherwise for each character '#' print a separate line containing a positive integer, the number of ')' characters this character must be replaced with.

If there are several possible answers, you may output any of them.


-----Examples-----
Input
(((#)((#)

Output
1
2

Input
()((#((#(#()

Output
2
2
1
Input
#

Output
-1

Input
(#)

Output
-1



-----Note-----

|s| denotes the length of the string s.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jafar has n cans of cola. Each can is described by two integers: remaining volume of cola a_{i} and can's capacity b_{i} (a_{i}  ≤  b_{i}).

Jafar has decided to pour all remaining cola into just 2 cans, determine if he can do this or not!


-----Input-----

The first line of the input contains one integer n (2 ≤ n ≤ 100 000) — number of cola cans.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — volume of remaining cola in cans.

The third line contains n space-separated integers that b_1, b_2, ..., b_{n} (a_{i} ≤ b_{i} ≤ 10^9) — capacities of the cans.


-----Output-----

Print "YES" (without quotes) if it is possible to pour all remaining cola in 2 cans. Otherwise print "NO" (without quotes).

You can print each letter in any case (upper or lower).


-----Examples-----
Input
2
3 5
3 6

Output
YES

Input
3
6 8 9
6 10 12

Output
NO

Input
5
0 0 5 0 0
1 1 8 10 5

Output
YES

Input
4
4 1 0 3
5 2 2 3

Output
YES



-----Note-----

In the first sample, there are already 2 cans, so the answer is "YES".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
AtCoDeer the deer has N square tiles. The tiles are numbered 1 through N, and the number given to each tile is written on one side of the tile. Also, each corner of each tile is painted in one of the 1000 colors, which are represented by the integers 0 between 999. The top-left, top-right, bottom-right and bottom-left corner of the tile with the number i are painted in color C_{i,0}, C_{i,1}, C_{i,2} and C_{i,3}, respectively, when seen in the direction of the number written on the tile (See Figure 1).
Figure 1: The correspondence between the colors of a tile and the input
AtCoDeer is constructing a cube using six of these tiles, under the following conditions:
 - For each tile, the side with the number must face outward.
 - For each vertex of the cube, the three corners of the tiles that forms it must all be painted in the same color.
Help him by finding the number of the different cubes that can be constructed under the conditions.
Since each tile has a number written on it, two cubes are considered different if the set of the used tiles are different, or the tiles are used in different directions, even if the formation of the colors are the same. (Each tile can be used in one of the four directions, obtained by 90° rotations.) Two cubes are considered the same only if rotating one in the three dimensional space can obtain an exact copy of the other, including the directions of the tiles.
Figure 2: The four directions of a tile

-----Constraints-----
 - 6≦N≦400
 - 0≦C_{i,j}≦999 (1≦i≦N , 0≦j≦3)

-----Input-----
The input is given from Standard Input in the following format:
N
C_{1,0} C_{1,1} C_{1,2} C_{1,3}
C_{2,0} C_{2,1} C_{2,2} C_{2,3}
:
C_{N,0} C_{N,1} C_{N,2} C_{N,3}

-----Output-----
Print the number of the different cubes that can be constructed under the conditions.

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

-----Sample Output-----
1

The cube below can be constructed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arpa is researching the Mexican wave.

There are n spectators in the stadium, labeled from 1 to n. They start the Mexican wave at time 0. 

  At time 1, the first spectator stands.  At time 2, the second spectator stands.  ...  At time k, the k-th spectator stands.  At time k + 1, the (k + 1)-th spectator stands and the first spectator sits.  At time k + 2, the (k + 2)-th spectator stands and the second spectator sits.  ...  At time n, the n-th spectator stands and the (n - k)-th spectator sits.  At time n + 1, the (n + 1 - k)-th spectator sits.  ...  At time n + k, the n-th spectator sits. 

Arpa wants to know how many spectators are standing at time t.


-----Input-----

The first line contains three integers n, k, t (1 ≤ n ≤ 10^9, 1 ≤ k ≤ n, 1 ≤ t < n + k).


-----Output-----

Print single integer: how many spectators are standing at time t.


-----Examples-----
Input
10 5 3

Output
3

Input
10 5 7

Output
5

Input
10 5 12

Output
3



-----Note-----

In the following a sitting spectator is represented as -, a standing spectator is represented as ^.

  At t = 0  ---------- $\Rightarrow$ number of standing spectators = 0.  At t = 1  ^--------- $\Rightarrow$ number of standing spectators = 1.  At t = 2  ^^-------- $\Rightarrow$ number of standing spectators = 2.  At t = 3  ^^^------- $\Rightarrow$ number of standing spectators = 3.  At t = 4  ^^^^------ $\Rightarrow$ number of standing spectators = 4.  At t = 5  ^^^^^----- $\Rightarrow$ number of standing spectators = 5.  At t = 6  -^^^^^---- $\Rightarrow$ number of standing spectators = 5.  At t = 7  --^^^^^--- $\Rightarrow$ number of standing spectators = 5.  At t = 8  ---^^^^^-- $\Rightarrow$ number of standing spectators = 5.  At t = 9  ----^^^^^- $\Rightarrow$ number of standing spectators = 5.  At t = 10 -----^^^^^ $\Rightarrow$ number of standing spectators = 5.  At t = 11 ------^^^^ $\Rightarrow$ number of standing spectators = 4.  At t = 12 -------^^^ $\Rightarrow$ number of standing spectators = 3.  At t = 13 --------^^ $\Rightarrow$ number of standing spectators = 2.  At t = 14 ---------^ $\Rightarrow$ number of standing spectators = 1.  At t = 15 ---------- $\Rightarrow$ number of standing spectators = 0.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
DO YOU EXPECT ME TO FIND THIS OUT?

WHAT BASE AND/XOR LANGUAGE INCLUDES string?

DON'T BYTE OF MORE THAN YOU CAN CHEW

YOU CAN ONLY DISTORT THE LARGEST OF MATHEMATICS SO FAR

SAYING "ABRACADABRA" WITHOUT A MAGIC AND WON'T DO YOU ANY GOOD

THE LAST STACK RUPTURES. ALL DIE. OH, THE EMBARRASSMENT!

I HAVE NO ARRAY AND I MUST SCREAM

ELEMENTS MAY NOT BE STORED IN WEST HYPERSPACE

Input Specification:
The first line of input data contains a single integer *n* (1<=≤<=*n*<=≤<=10).

The second line of input data contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=11).

Output Specification:
Output a single integer.

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

Demo Output:
['4\n']

Note:
none

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

Write a function that takes a single argument `n` that is a string representation of a simple mathematical expression and evaluates it as a floating point value. 

# Commands : 
- positive or negative decimal numbers
- `+, -, *, /, ( / ).`

---

Expressions use [infix notation](https://en.wikipedia.org/wiki/Infix_notation). 

# Evaluation : 

Operators should be evaluated in the order they appear and not as in `BODMAS`, though brackets __should__ be correctly observed. 

The function should return the correct result for any possible expression of this form.

# Note : 

- All given input will be valid.
- It will consist entirely of numbers or one of the operators.
- Parentheses will alway be matched.
- Use of `eval` or its equivalent is forbidden
- use of `exec` is forbidden (Python) 
- Use of `Function` or any of their (Function, eval) equivalent is also forbidden.
- Using `require` is also forbidden. (`import` for python)
- Using more than 7 (8 for python) lines is also forbidden.
- Using more than 260 (JS) / 240 (python) characters is also forbidden.
- Having more than 100 chars per line is forbidden.
- Having more than 6 semi-colons is forbidden

and that is about it.

--- 

# Examples : 

    e("2*3*4*5+99")               ---> 219
    e("2*3*4*5+99*321-12312312")  ---> -12242013
    e("1-2*2/2*2-1*7+3")          ---> -18

---

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ chips arranged in a circle, numbered from $1$ to $n$. 

Initially each chip has black or white color. Then $k$ iterations occur. During each iteration the chips change their colors according to the following rules. For each chip $i$, three chips are considered: chip $i$ itself and two its neighbours. If the number of white chips among these three is greater than the number of black chips among these three chips, then the chip $i$ becomes white. Otherwise, the chip $i$ becomes black. 

Note that for each $i$ from $2$ to $(n - 1)$ two neighbouring chips have numbers $(i - 1)$ and $(i + 1)$. The neighbours for the chip $i = 1$ are $n$ and $2$. The neighbours of $i = n$ are $(n - 1)$ and $1$.

The following picture describes one iteration with $n = 6$. The chips $1$, $3$ and $4$ are initially black, and the chips $2$, $5$ and $6$ are white. After the iteration $2$, $3$ and $4$ become black, and $1$, $5$ and $6$ become white.

 [Image] 

Your task is to determine the color of each chip after $k$ iterations.


-----Input-----

The first line contains two integers $n$ and $k$ $(3 \le n \le 200\,000, 1 \le k \le 10^{9})$ — the number of chips and the number of iterations, respectively.

The second line contains a string consisting of $n$ characters "W" and "B". If the $i$-th character is "W", then the $i$-th chip is white initially. If the $i$-th character is "B", then the $i$-th chip is black initially.


-----Output-----

Print a string consisting of $n$ characters "W" and "B". If after $k$ iterations the $i$-th chip is white, then the $i$-th character should be "W". Otherwise the $i$-th character should be "B".


-----Examples-----
Input
6 1
BWBBWW

Output
WBBBWW

Input
7 3
WBWBWBW

Output
WWWWWWW

Input
6 4
BWBWBW

Output
BWBWBW



-----Note-----

The first example is described in the statement.

The second example: "WBWBWBW" $\rightarrow$ "WWBWBWW" $\rightarrow$ "WWWBWWW" $\rightarrow$ "WWWWWWW". So all chips become white.

The third example: "BWBWBW" $\rightarrow$ "WBWBWB" $\rightarrow$ "BWBWBW" $\rightarrow$ "WBWBWB" $\rightarrow$ "BWBWBW".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bear Limak likes watching sports on TV. He is going to watch a game today. The game lasts 90 minutes and there are no breaks.

Each minute can be either interesting or boring. If 15 consecutive minutes are boring then Limak immediately turns TV off.

You know that there will be n interesting minutes t_1, t_2, ..., t_{n}. Your task is to calculate for how many minutes Limak will watch the game.


-----Input-----

The first line of the input contains one integer n (1 ≤ n ≤ 90) — the number of interesting minutes.

The second line contains n integers t_1, t_2, ..., t_{n} (1 ≤ t_1 < t_2 < ... t_{n} ≤ 90), given in the increasing order.


-----Output-----

Print the number of minutes Limak will watch the game.


-----Examples-----
Input
3
7 20 88

Output
35

Input
9
16 20 30 40 50 60 70 80 90

Output
15

Input
9
15 20 30 40 50 60 70 80 90

Output
90



-----Note-----

In the first sample, minutes 21, 22, ..., 35 are all boring and thus Limak will turn TV off immediately after the 35-th minute. So, he would watch the game for 35 minutes.

In the second sample, the first 15 minutes are boring.

In the third sample, there are no consecutive 15 boring minutes. So, Limak will watch the whole game.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An atom of element X can exist in n distinct states with energies E1 < E2 < ... < En. Arkady wants to build a laser on this element, using a three-level scheme. Here is a simplified description of the scheme. 

Three distinct states i, j and k are selected, where i < j < k. After that the following process happens: 

  1. initially the atom is in the state i,
  2. we spend Ek - Ei energy to put the atom in the state k,
  3. the atom emits a photon with useful energy Ek - Ej and changes its state to the state j,
  4. the atom spontaneously changes its state to the state i, losing energy Ej - Ei,
  5. the process repeats from step 1. 



Let's define the energy conversion efficiency as <image>, i. e. the ration between the useful energy of the photon and spent energy.

Due to some limitations, Arkady can only choose such three states that Ek - Ei ≤ U.

Help Arkady to find such the maximum possible energy conversion efficiency within the above constraints.

Input

The first line contains two integers n and U (3 ≤ n ≤ 105, 1 ≤ U ≤ 109) — the number of states and the maximum possible difference between Ek and Ei.

The second line contains a sequence of integers E1, E2, ..., En (1 ≤ E1 < E2... < En ≤ 109). It is guaranteed that all Ei are given in increasing order.

Output

If it is not possible to choose three states that satisfy all constraints, print -1.

Otherwise, print one real number η — the maximum possible energy conversion efficiency. Your answer is considered correct its absolute or relative error does not exceed 10 - 9.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if <image>.

Examples

Input

4 4
1 3 5 7


Output

0.5


Input

10 8
10 13 15 16 17 19 20 22 24 25


Output

0.875


Input

3 1
2 5 10


Output

-1

Note

In the first example choose states 1, 2 and 3, so that the energy conversion efficiency becomes equal to <image>.

In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to <image>.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mike is trying rock climbing but he is awful at it. 

There are *n* holds on the wall, *i*-th hold is at height *a**i* off the ground. Besides, let the sequence *a**i* increase, that is, *a**i*<=&lt;<=*a**i*<=+<=1 for all *i* from 1 to *n*<=-<=1; we will call such sequence a track. Mike thinks that the track *a*1, ..., *a**n* has difficulty . In other words, difficulty equals the maximum distance between two holds that are adjacent in height.

Today Mike decided to cover the track with holds hanging on heights *a*1, ..., *a**n*. To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence (1,<=2,<=3,<=4,<=5) and remove the third element from it, we obtain the sequence (1,<=2,<=4,<=5)). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.

Help Mike determine the minimum difficulty of the track after removing one hold.

Input Specification:
The first line contains a single integer *n* (3<=≤<=*n*<=≤<=100) — the number of holds.

The next line contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=1000), where *a**i* is the height where the hold number *i* hangs. The sequence *a**i* is increasing (i.e. each element except for the first one is strictly larger than the previous one).

Output Specification:
Print a single number — the minimum difficulty of the track after removing a single hold.

Demo Input:
['3\n1 4 6\n', '5\n1 2 3 4 5\n', '5\n1 2 3 7 8\n']

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

Note:
In the first sample you can remove only the second hold, then the sequence looks like (1, 6), the maximum difference of the neighboring elements equals 5.

In the second test after removing every hold the difficulty equals 2.

In the third test you can obtain sequences (1, 3, 7, 8), (1, 2, 7, 8), (1, 2, 3, 8), for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
BerDonalds, a well-known fast food restaurant, is going to open a cafe in Bertown. The important thing is to choose the new restaurant's location so that it would be easy to get there. The Bertown road system is represented by n junctions, connected by m bidirectional roads. For each road we know its length. We also know that we can get from any junction to any other one, moving along the roads.

Your task is to find such location of the restaurant, that the shortest distance along the roads from the cafe to the farthest junction would be minimum. Note that the restaurant can be located not only on the junction, but at any point of any road.

Input

The first line contains two integers n and m (<image>) — the number of junctions and the number of roads, correspondingly. Then m lines follow, describing all Bertown roads. Each road is described by three integers ai, bi, wi (1 ≤ ai, bi ≤ n, ai ≠ bi; 1 ≤ wi ≤ 105), where ai and bi are the numbers of the junctions, connected by the i-th road, and wi is the length of the i-th road. 

It is guaranteed that each road connects two distinct junctions, there is at most one road between any two junctions, and you can get from any junction to any other one.

Output

Print a single real number — the shortest distance from the optimal restaurant location to the farthest junction. The answer will be considered correct, if its absolute or relative error doesn't exceed 10 - 9.

Examples

Input

2 1
1 2 1


Output

0.50


Input

3 3
1 2 1
2 3 1
1 3 1


Output

1.00


Input

3 2
1 2 100
2 3 1


Output

50.50

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