vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef has obtained the results of a past Cook-Off. He wants to estimate the skill level of each contestant. The contestants can be classified with high probability (w.h.p.) based on the number of solved problems:

A contestant that solved exactly 0 problems is a beginner.
A contestant that solved exactly 1 problem is a junior developer.
A contestant that solved exactly 2 problems is a middle developer.
A contestant that solved exactly 3 problems is a senior developer.
A contestant that solved exactly 4 problems is a hacker.
A contestant that solved all five problems is Jeff Dean.

Please help Chef to identify the programming level of each participant. 

------ Input ------ 

The first line of the input contains a single integer N denoting the number of competitors.
N lines follow. The i-th of these lines contains five space-separated integers A_{i, 1}, A_{i, 2}, A_{i, 3}, A_{i, 4}, A_{i, 5}. The j-th of these integers (1 ≤ j ≤ 5) is 1 if the i-th contestant solved the j-th problem and 0 otherwise.

------ Output ------ 

For each participant, print a single line containing one string denoting Chef's classification of that contestant — one of the strings "Beginner", "Junior Developer", "Middle Developer", "Senior Developer", "Hacker", "Jeff Dean" (without quotes).

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

$1 ≤ N ≤ 5000$
$0 ≤ A_{i, j} ≤ 1 for each valid i, j$

----- Sample Input 1 ------ 
7
0 0 0 0 0
0 1 0 1 0
0 0 1 0 0
1 1 1 1 1
0 1 1 1 0
0 1 1 1 1
1 1 1 1 0
----- Sample Output 1 ------ 
Beginner
Middle Developer
Junior Developer
Jeff Dean
Senior Developer
Hacker
Hacker
----- explanation 1 ------ 
The first contestant has no solved problems, therefore he is a beginner. The second contestant solved 2 problems (the second and fourth problem), therefore he has the skills of a middle developer. The third contestant solved 1 problem, therefore he's at the expected level of a junior developer. The fourth contestant solved 5 problems — we can guess it was Jeff Dean. The fifth contestant solved 3 problems, so he is a senior developer. And the last two contestants should be hackers because they solved exactly 4 problems each.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On Miu's smart phone, there is a search feature which lets her search for a contact name by typing digits on the keypad where each digit may correspond to any of the characters given below it. For example, to search for TOM, she can type 866 and for MAX she can type 629.
+------+-----+------+
|   1  |  2  |   3  |
|      | ABC |  DEF |
+------+-----+------+
|   4  |  5  |   6  |
|  GHI | JKL |  MNO |
+------+-----+------+
|   7  |  8  |   9  |
| PQRS | TUV | WXYZ |
+------+-----+------+
|      |  0  |      |
+------+-----+------+

Miu typed a random string of digits $S$ on the keypad while playing around, where each digit is between 2 and 9 inclusive. Now she wants to know the number of possible strings which would map to $S$. 
Since this number can be very large, output it modulo 10^9 + 7 (1000000007)

-----Input:-----
- 
The first line of the input consists of a single integer $T$ denoting the number of test cases.
- 
Each test case consists of a string $S$.

-----Output:-----
- For each test case, print a single line containing one integer - the count of all possible strings mod 1,000,000,007

-----Constraints-----
- 
1 <= $T$ <= 10
- 
1 <= $|S|$ <= 105

-----Subtasks-----
Subtask #1 (10 points):
- 1 <= $|S|$ <= 10
Subtask #2 (90 points):
- Original Constraints

-----Sample Input:-----
2

5

72  

-----Sample Output:-----
3

12  

-----EXPLANATION:-----
- 
Example Case 1:

On the key 5, we have the character set JKL.

Hence the possible strings are J,K,L.

Hence the answer is 3 % (1000000007) = 3.  
- 
Example Case 2:
On key 7, we have the character set PQRS.

On key 2, we have the character set ABC.

Hence the possible strings are PA,PB,PC,QA,QB,QC,RA,RB,RC,SA,SB,SC.

Hence the answer is 12 % (1000000007) = 12.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Last year, some of the judges tried to travel to NWERC’10 by train. This turned into a big disaster: on the way there, a fire in a control room caused huge delays, while on the return trip, trains in Bremen were delayed due to a terrorist threat in Hamburg. Of course, these huge delays caused other delays in the train schedule, so the big question was which trains to take: would it be better to take this slow regional train now, or wait for that intercity train, which has a big chance of being delayed?

This year, the judges have planned ahead and carefully analyzed the train schedule. They even kept track of how often trains were delayed and by how much. Now that they have all this information, they want to travel as quickly possible, minimizing the expected duration of the journey. Can you help them?

For each train connection, the judges know exactly what its scheduled departure time and duration are, as well as the probability that its arrival at the destination will be delayed. You may assume that the probabilities of delays are independent and that the judges can adapt their itinerary as they go, depending on any delays which they might already have incurred. Trains always depart on time, but may arrive late and the judges do not know whether a train’s arrival will be delayed until they have boarded it. It takes judges no time to switch trains, so they can take a connecting train that departs at the same time as they arrive at a place.

The judges can choose the time of their initial departure as they wish and they want to minimize the expected duration1 of their total trip.

-----Input-----
 - one line with the judges’ place of origin and destination, these are different.
 - one line with an integer $n$ ($1 \leq n \leq 1000$): the number of train connections.
 - $n$ lines, each describing a train connection:
 - the origin and destination of this connection, these are different.
 - an integer $m$ ($0\leq m\leq 59$), the departure time in minutes after each full hour.
 - an integer $t$ ($1\leq t\leq 300$), the standard journey time (assuming no delays).
 - an integer $p$ ($0\leq p\leq 100$), the probability of delays as a percentage.
 - an integer $d$ ($1\leq d\leq 120$), the maximum delay in minutes.

All place names are given as strings of upper and lower case alphabetical characters, of length at most 20. If a train is delayed, then the length of the delay will be a whole number of minutes, and will be uniformly distributed in the range $[1,d]$.

-----Output-----
Output a floating point number: the minimum expected duration of the total trip in minutes. This number should be accurate up to $10^{-6}$ relative or absolute precision. Output IMPOSSIBLE instead if the destination is not reachable.

-----Examples-----
Sample Input 1:
Hamburg Bremen
3
Hamburg Bremen 15 68 10 5
Hamburg Bremen 46 55 50 60
Bremen Frankfurt 14 226 10 120
Sample Output 1:
68.3

Sample Input 2:
Amsterdam Rotterdam
1
Amsterdam Utrecht 10 22 5 10
Sample Output 2:
IMPOSSIBLE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The biggest event of the year – Cota 2 world championship "The Innernational" is right around the corner. $2^n$ teams will compete in a double-elimination format (please, carefully read problem statement even if you know what is it) to identify the champion. 

Teams are numbered from $1$ to $2^n$ and will play games one-on-one. All teams start in the upper bracket.

All upper bracket matches will be held played between teams that haven't lost any games yet. Teams are split into games by team numbers. Game winner advances in the next round of upper bracket, losers drop into the lower bracket.

Lower bracket starts with $2^{n-1}$ teams that lost the first upper bracket game. Each lower bracket round consists of two games. In the first game of a round $2^k$ teams play a game with each other (teams are split into games by team numbers). $2^{k-1}$ loosing teams are eliminated from the championship, $2^{k-1}$ winning teams are playing $2^{k-1}$ teams that got eliminated in this round of upper bracket (again, teams are split into games by team numbers). As a result of each round both upper and lower bracket have $2^{k-1}$ teams remaining. See example notes for better understanding.

Single remaining team of upper bracket plays with single remaining team of lower bracket in grand-finals to identify championship winner.

You are a fan of teams with numbers $a_1, a_2, ..., a_k$. You want the championship to have as many games with your favourite teams as possible. Luckily, you can affect results of every championship game the way you want. What's maximal possible number of championship games that include teams you're fan of?


-----Input-----

First input line has two integers $n, k$ — $2^n$ teams are competing in the championship. You are a fan of $k$ teams ($2 \le n \le 17; 0 \le k \le 2^n$).

Second input line has $k$ distinct integers $a_1, \ldots, a_k$ — numbers of teams you're a fan of ($1 \le a_i \le 2^n$).


-----Output-----

Output single integer — maximal possible number of championship games that include teams you're fan of.


-----Examples-----
Input
3 1
6

Output
6

Input
3 3
1 7 8

Output
11

Input
3 4
1 3 5 7

Output
14



-----Note-----

On the image, each game of the championship is denoted with an English letter ($a$ to $n$). Winner of game $i$ is denoted as $Wi$, loser is denoted as $Li$. Teams you're a fan of are highlighted with red background.

In the first example, team $6$ will play in 6 games if it looses the first upper bracket game (game $c$) and wins all lower bracket games (games $h, j, l, m$). [Image]

In the second example, teams $7$ and $8$ have to play with each other in the first game of upper bracket (game $d$). Team $8$ can win all remaining games in upper bracket, when teams $1$ and $7$ will compete in the lower bracket. [Image]

In the third example, your favourite teams can play in all games of the championship. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
E869120 is initially standing at the origin (0, 0) in a two-dimensional plane.
He has N engines, which can be used as follows:
 - When E869120 uses the i-th engine, his X- and Y-coordinate change by x_i and y_i, respectively. In other words, if E869120 uses the i-th engine from coordinates (X, Y), he will move to the coordinates (X + x_i, Y + y_i).
 - E869120 can use these engines in any order, but each engine can be used at most once. He may also choose not to use some of the engines.
He wants to go as far as possible from the origin.
Let (X, Y) be his final coordinates. Find the maximum possible value of \sqrt{X^2 + Y^2}, the distance from the origin.

-----Constraints-----
 - 1 \leq N \leq 100
 - -1 \ 000 \ 000 \leq x_i \leq 1 \ 000 \ 000
 - -1 \ 000 \ 000 \leq y_i \leq 1 \ 000 \ 000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
 : :
x_N y_N

-----Output-----
Print the maximum possible final distance from the origin, as a real value.
Your output is considered correct when the relative or absolute error from the true answer is at most 10^{-10}.

-----Sample Input-----
3
0 10
5 -5
-5 -5

-----Sample Output-----
10.000000000000000000000000000000000000000000000000

The final distance from the origin can be 10 if we use the engines in one of the following three ways:
 - Use Engine 1 to move to (0, 10).
 - Use Engine 2 to move to (5, -5), and then use Engine 3 to move to (0, -10).
 - Use Engine 3 to move to (-5, -5), and then use Engine 2 to move to (0, -10).
The distance cannot be greater than 10, so the maximum possible distance is 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation $p_1,p_2...p_N$ of $\{1, 2, ..., N\}$ is beautiful if $p_i \& p_{i+1}$ is greater than 0 for every $1 \leq i < N$ . You are given an integer $N$, and your task is toconstruct a beautiful permutation of length $N$ or determine that it's impossible.
Note that $a \& b$ denotes the bitwise AND of $a$ and $b$.

-----Input:-----
First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains a single line of input, an integer $N$.

-----Output:-----
For each test case output $-1$ if there is no suitable permutation of length $N$, otherwise output $N$ integers in a single line which form a beautiful permutation. If there are multiple answers output any of them.

-----Constraints-----
- $1 \leq N \leq 10^5$
- The sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
- 50 points : $1 \leq N,T \leq 9$
- 50 points : Original constraints

-----Sample Input:-----
3
4
3
5

-----Sample Output:-----
-1
1 3 2
2 3 1 5 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.

At some points on the road there are n friends, and i-th of them is standing at the point xi meters and can move with any speed no greater than vi meters per second in any of the two directions along the road: south or north.

You are to compute the minimum time needed to gather all the n friends at some point on the road. Note that the point they meet at doesn't need to have integer coordinate. 

Input

The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.

The second line contains n integers x1, x2, ..., xn (1 ≤ xi ≤ 109) — the current coordinates of the friends, in meters.

The third line contains n integers v1, v2, ..., vn (1 ≤ vi ≤ 109) — the maximum speeds of the friends, in meters per second.

Output

Print the minimum time (in seconds) needed for all the n friends to meet at some point on the road. 

Your answer will be considered correct, if its absolute or relative error isn't greater than 10 - 6. Formally, let your answer be a, while jury's answer be b. Your answer will be considered correct if <image> holds.

Examples

Input

3
7 1 3
1 2 1


Output

2.000000000000


Input

4
5 10 3 2
2 3 2 4


Output

1.400000000000

Note

In the first sample, all friends can gather at the point 5 within 2 seconds. In order to achieve this, the first friend should go south all the time at his maximum speed, while the second and the third friends should go north at their maximum speeds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two neighbours, Alan and Bob, live in the city, where there are three buildings only: a cinema, a shop and the house, where they live. The rest is a big asphalt square. 

Once they went to the cinema, and the film impressed them so deeply, that when they left the cinema, they did not want to stop discussing it.

Bob wants to get home, but Alan has to go to the shop first, and only then go home. So, they agreed to cover some distance together discussing the film (their common path might pass through the shop, or they might walk circles around the cinema together), and then to part each other's company and go each his own way. After they part, they will start thinking about their daily pursuits; and even if they meet again, they won't be able to go on with the discussion. Thus, Bob's path will be a continuous curve, having the cinema and the house as its ends. Alan's path — a continuous curve, going through the shop, and having the cinema and the house as its ends.

The film ended late, that's why the whole distance covered by Alan should not differ from the shortest one by more than t1, and the distance covered by Bob should not differ from the shortest one by more than t2.

Find the maximum distance that Alan and Bob will cover together, discussing the film.

Input

The first line contains two integers: t1, t2 (0 ≤ t1, t2 ≤ 100). The second line contains the cinema's coordinates, the third one — the house's, and the last line — the shop's. 

All the coordinates are given in meters, are integer, and do not exceed 100 in absolute magnitude. No two given places are in the same building.

Output

In the only line output one number — the maximum distance that Alan and Bob will cover together, discussing the film. Output the answer accurate to not less than 4 decimal places.

Examples

Input

0 2
0 0
4 0
-3 0


Output

1.0000000000


Input

0 0
0 0
2 0
1 0


Output

2.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob has ladder. He wants to climb this ladder, but being a precocious child, he wonders about exactly how many ways he could to climb this `n` size ladder using jumps of up to distance `k`.

Consider this example...

n = 5\
k = 3

Here, Bob has ladder of length 5, and with each jump, he can ascend up to 3 steps (he can either jump step 1 or 2 or 3). This gives the below possibilities

```
1 1 1 1 1
1 1 1 2
1 1 2 1 
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3
3 2
```

Your task to calculate number of ways to climb ladder of length `n` with upto `k` steps for Bob. (13 in above case)

Constraints:

```python
1<=n<=50
1<=k<=15
```

_Tip: try fibonacci._

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Can you imagine our life if we removed all zeros from it? For sure we will have many problems.

In this problem we will have a simple example if we removed all zeros from our life, it's the addition operation. Let's assume you are given this equation *a*<=+<=*b*<==<=*c*, where *a* and *b* are positive integers, and *c* is the sum of *a* and *b*. Now let's remove all zeros from this equation. Will the equation remain correct after removing all zeros?

For example if the equation is 101<=+<=102<==<=203, if we removed all zeros it will be 11<=+<=12<==<=23 which is still a correct equation.

But if the equation is 105<=+<=106<==<=211, if we removed all zeros it will be 15<=+<=16<==<=211 which is not a correct equation.

Input Specification:
The input will consist of two lines, the first line will contain the integer *a*, and the second line will contain the integer *b* which are in the equation as described above (1<=≤<=*a*,<=*b*<=≤<=109). There won't be any leading zeros in both. The value of *c* should be calculated as *c*<==<=*a*<=+<=*b*.

Output Specification:
The output will be just one line, you should print "YES" if the equation will remain correct after removing all zeros, and print "NO" otherwise.

Demo Input:
['101\n102\n', '105\n106\n']

Demo Output:
['YES\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence a_1, a_2, …, a_n of non-negative integers.

You need to find the largest number m of triples (i_1, j_1, k_1), (i_2, j_2, k_2), ..., (i_m, j_m, k_m) such that:

  * 1 ≤ i_p < j_p < k_p ≤ n for each p in 1, 2, …, m;
  * a_{i_p} = a_{k_p} = 0, a_{j_p} ≠ 0;
  * all a_{j_1}, a_{j_2}, …, a_{j_m} are different;
  * all i_1, j_1, k_1, i_2, j_2, k_2, …, i_m, j_m, k_m are different.

Input

The first line of input contains one integer t (1 ≤ t ≤ 500 000): the number of test cases.

The first line of each test case contains one integer n (1 ≤ n ≤ 500 000).

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ n).

The total sum of n is at most 500 000.

Output

For each test case, print one integer m: the largest number of proper triples that you can find.

Example

Input


8
1
1
2
0 0
3
0 1 0
6
0 0 1 2 0 0
6
0 1 0 0 1 0
6
0 1 3 2 0 0
6
0 0 0 0 5 0
12
0 1 0 2 2 2 0 0 3 3 4 0


Output


0
0
1
2
1
1
1
2

Note

In the first two test cases, there are not enough elements even for a single triple, so the answer is 0.

In the third test case we can select one triple (1, 2, 3).

In the fourth test case we can select two triples (1, 3, 5) and (2, 4, 6).

In the fifth test case we can select one triple (1, 2, 3). We can't select two triples (1, 2, 3) and (4, 5, 6), because a_2 = a_5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an unsorted permutation P of size N. An operation is defined as:

Swap P_{i} and P_{i+K} for any i in the range [1,N-K].

Find the maximum value of K, such that, the permutation P can be sorted by applying any finite number of operations.

Note that, a permutation of size N contains all integers from 1 to N exactly once.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N, the size of permutation.
- The next line contains N integers describing the permutation P.
- It is guaranteed that the given permutation is not sorted.

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

For each test case, output on a new line the maximum possible value of K.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

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

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

----- explanation 1 ------ 
- Test Case $1$: Permutation can be sorted by swapping $P_{1}$ and $P_{4}$. So, the maximum possible value of $K$ is $3$. It can be shown that we cannot sort the permutation for any $K> 3$.

- Test Case $2$: Swapping $P_{2}$ and $P_{4}$ will sort the permutation. So, the maximum possible value of $K$ is $2$. It can be shown that we cannot sort the permutation for any $K> 2$.

- Test Case $3$: Swapping $P_{1}$ and $P_{2}$ will sort the permutation. So, the maximum possible value of $K$ is $1$. It can be shown that we cannot sort the permutation for any $K> 1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Last time, Dominic and his family brought it home, to the city they know best. After a fierce battle with Shaw in the town, the town gained a lot of heat. In order to calm things down, the police in town are working on improving the traffic capacity of the road, the town's mayor ordered to place on traffic sign, thus limiting the maximum speed. The traffic signs in the town seem to be a bit odd. The reason being, they only limit the speed where the traffic signals are placed and just after passing the sign the cars are allowed to drive at any speed.

It is given that the cars of the town have an average acceleration/deceleration of x km/h^2, and has a maximum speed of y km/h. The road has the length of L km, and the speed sign, limiting the speed to w km/h, is placed d km (1 ≤ d ≤ L) away from the town. You have to find the minimum time that an average car will need to get from the town, if the car drives at the optimal speed.

Note: The car has a zero speed at the beginning of the journey.

Input: 
The first line of the input file contains two integer numbers x and y (1 ≤ x, y ≤ 10000). The second line contains three integer numbers L, d and w (2 ≤ L ≤ 10000; 1 ≤ d < L; 1 ≤ w ≤ 10000).

Output: 
Print the answer with nine digits after the decimal point.

SAMPLE INPUT
1 1
2 1 3

SAMPLE OUTPUT
2.500000000

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