vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Takahashi will take part in an eating contest. Teams of N members will compete in this contest, and Takahashi's team consists of N players numbered 1 through N from youngest to oldest. The consumption coefficient of Member i is A_i.
In the contest, N foods numbered 1 through N will be presented, and the difficulty of Food i is F_i. The details of the contest are as follows:
 - A team should assign one member to each food, and should not assign the same member to multiple foods.
 - It will take x \times y seconds for a member to finish the food, where x is the consumption coefficient of the member and y is the difficulty of the dish.
 - The score of a team is the longest time it takes for an individual member to finish the food.
Before the contest, Takahashi's team decided to do some training. In one set of training, a member can reduce his/her consumption coefficient by 1, as long as it does not go below 0. However, for financial reasons, the N members can do at most K sets of training in total.
What is the minimum possible score of the team, achieved by choosing the amounts of members' training and allocating the dishes optimally?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2 \times 10^5
 - 0 \leq K \leq 10^{18}
 - 1 \leq A_i \leq 10^6\ (1 \leq i \leq N)
 - 1 \leq F_i \leq 10^6\ (1 \leq i \leq N)

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 ... A_N
F_1 F_2 ... F_N

-----Output-----
Print the minimum possible score of the team.

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

-----Sample Output-----
2

They can achieve the score of 2, as follows:
 - Member 1 does 4 sets of training and eats Food 2 in (4-4) \times 3 = 0 seconds.
 - Member 2 does 1 set of training and eats Food 3 in (2-1) \times 1 = 1 second.
 - Member 3 does 0 sets of training and eats Food 1 in (1-0) \times 2 = 2 seconds.
They cannot achieve a score of less than 2, so the answer is 2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Timofey likes integers a lot. Unfortunately, he is very young and can't work with very big integers, so he does all the operations modulo his favorite prime *m*. Also, Timofey likes to look for arithmetical progressions everywhere.

One of his birthday presents was a sequence of distinct integers *a*1,<=*a*2,<=...,<=*a**n*. Timofey wants to know whether he can rearrange the elements of the sequence so that is will be an arithmetical progression modulo *m*, or not.

Arithmetical progression modulo *m* of length *n* with first element *x* and difference *d* is sequence of integers *x*,<=*x*<=+<=*d*,<=*x*<=+<=2*d*,<=...,<=*x*<=+<=(*n*<=-<=1)·*d*, each taken modulo *m*.

Input Specification:
The first line contains two integers *m* and *n* (2<=≤<=*m*<=≤<=109<=+<=7, 1<=≤<=*n*<=≤<=105, *m* is prime) — Timofey's favorite prime module and the length of the sequence.

The second line contains *n* distinct integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=&lt;<=*m*) — the elements of the sequence.

Output Specification:
Print -1 if it is not possible to rearrange the elements of the sequence so that is will be an arithmetical progression modulo *m*.

Otherwise, print two integers — the first element of the obtained progression *x* (0<=≤<=*x*<=&lt;<=*m*) and its difference *d* (0<=≤<=*d*<=&lt;<=*m*).

If there are multiple answers, print any of them.

Demo Input:
['17 5\n0 2 4 13 15\n', '17 5\n0 2 4 13 14\n', '5 3\n1 2 3\n']

Demo Output:
['13 2\n', '-1\n', '3 4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Let's play Psychic 

A box contains green, red, and blue balls. The total number of balls is given by `n` (`0 < n < 50`).

Each ball has a mass that depends on the ball color. Green balls weigh `5kg`, red balls weigh `4kg`, and blue balls weigh `3kg`.

Given the total number of balls in the box, `n`, and a total mass, `m`, your task is to craft a program that will determine the quantities of each colored ball. Return a list of these quantities as the answer.

Don't forget that some combinations of `n` and `m` may have more than one possibility!

# Examples

## Python
```python
>>> Guess_it(3, 12)
[[0,3,0], [1,1,1]]
```

## Elixir

*Note: Order of the returned elements is unimportant in the Elixir version.*

# Assumptions

1. You can assume that all inputs are of the correct type
2. You can assume that the range of `n` will be `[1, 50]`
3. Each element of the returned list should return the quantities in the order of `g`, `r`, `b`. 

## Python
```python
[[green, red, blue]]
```

## Elixir

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
G, a college student living in a certain sky city, has a hornworm, Imotaro. He disciplined Imotaro to eat all the food in order with the shortest number of steps. You, his friend, decided to write a program because he asked me to find out if Imotaro was really disciplined.



Input


H W N
area


Input is given in H + 1 lines. The first line contains three integers H, W, N (2 ≤ H ≤ 10, 2 ≤ W ≤ 10, 1 ≤ N ≤ 9). H is the height of the area, W is the width, and N is the number of foods (at this time, 6 + N ≤ H × W always holds).

In each line from the 2nd line to H + 1st line, ´S´, ´1´, 2´,… ´9´, ´a´, ´b´, ´c´, ´d´, ´e´, A W character string consisting of ´ # ´ and ´.´ is written, and each represents the state of each section of the area. In addition, ´S´, ´a´, ´b´, ´c´, ´d´, ´e´ represent the initial state of the hornworm. There is no food or obstacles so that it is covered with the hornworm in the initial state. In addition, the initial position of the hornworm and the position of the food are guaranteed to be entered correctly.

Output

Output the minimum number of steps when the hornworm eats food in order, or -1 if that is not possible.

Examples

Input

5 8 3
#.......
#.####2#
#.#.3..#
#.######
.1Sabcde


Output

14


Input

5 8 3
.......
.####2#
.#.3..#
.######
.1Sabcde


Output

14


Input

2 6 2
.1.baS
.2.cde


Output

7


Input

2 6 2
.1#baS
.2.cde


Output

-1

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

A wild chemist wants to prepare his mysterious mixture. 

The recipe is very simple, he has already mixed all the necessary powders and the only remaining thing is to add exactly m nanoliters of any liquids. 

In his lab he has n_1 bottles full of liquid called amulus of various capacities and n_2 bottles full of water, also of various capacities. He knows the capacity of each single bottle and he is curious if he can use the bottles he has to produce the mixture. If he decides to use any bottle, he has to use all the liquid inside it. 

Capacities of bottles of amulus are special, because for any two such bottles with capacities c_i and c_j, the following fact is true:

either 2 \cdot c_i ≤q c_j or 2 \cdot c_j ≤q c_i.

Help the chemist decide if he can prepare the mixture or not.

In one test file you have to handle T test cases.

Input format:

In the first line a single integer T is given denoting the number of test cases. Then descriptions of T test cases follow. In the first line of a description of a single test case there are three integers m, n_1 and n_2 ,denoting the number of nanoliliters of liquids needed for the mixture, the number of bottles of amulus available and the number of bottles of water available. In the second line there are n_1 space separated integers denoting capacities of bottles of amulus. In the third line there are n_2 integers denoting capacities of bottles of water.

Output format:

For each test case output either NO if the mixture cannot be produced, or output YES in the first line followed by the second line containing space separated capacities of bottles of amulus that can be used to achieve the goal in non-decreasing order of their capacities. If there are many possible solutions output the one with the greatest sum of capacities of used bottles of amulus, and in case when there are still many possible such solutions, print any of them.

Constraints:

1 ≤q T ≤q 10
1 ≤q m ≤q 10^{18}  
1 ≤q n_1 ≤q 60  
1 ≤q n_2 ≤q 15
1 ≤q capacity of any bottle ≤q 10^{17}
For any two bottles of amulus with capacities c_1 and c_2, either 2 \cdot c_i ≤q c_j or 2 \cdot c_j ≤q c_i

SAMPLE INPUT
2
7 2 2
2 4
1 3
11 2 2
2 4
1 3

SAMPLE OUTPUT
YES
2 4 
NO

Explanation

There are two test cases in the sample. In both of them we have there are two bottles of amulus with capacities 2 and 4, and two bottles of water with capacities 1 and 3. 

In the first test case a mixture of 7 nanoliters can be mixed using both bottles of amulus and a bottle of water with capacity 1. There are other possible solutions, but this one is the one with greatest sum of nanoliters of amulus used among them.

In the second test case there is no possible combination of bottles giving 11 nanoliters of mixture.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is an integer r.
How many times is the area of a circle of radius r larger than the area of a circle of radius 1?
It can be proved that the answer is always an integer under the constraints given.

-----Constraints-----
 - 1 \leq r \leq 100
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
r

-----Output-----
Print the area of a circle of radius r, divided by the area of a circle of radius 1, as an integer.

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

-----Sample Output-----
4

The area of a circle of radius 2 is 4 times larger than the area of a circle of radius 1.
Note that output must be an integer - for example, 4.0 will not be accepted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ikta has an extraordinary feeling for undirected graphs. Ikta likes the undirected graph G and its two-point s, t pair (G, s, t) that has the greatest "beauty". The "beauty" of a pair (G, s, t) is the edge e = \\ {u, v \\} (u and v are two different points of G), and the shortest path from s to t in G. Is the number of things whose length is greater than the length of the shortest path from s to t in the undirected graph with g plus e.

Your job is to write a program that seeks its "beauty" given a pair (G, s, t).



Input

The input is given in the following format.

> N M s t
> x1 y1
> ...
> xi yi
> ...
> xM yM
>

First, the number of vertices, the number of edges, and the integers N, M, s, t representing the two vertices of the undirected graph are input. From the 2nd line to the M + 1th line, two vertices connected by edges are input. (However, let the set of G vertices be \\ {1, ..., N \\}.)

Constraints

Each variable being input satisfies the following constraints.

* 2 ≤ N ≤ 100,000
* 1 ≤ M ≤ 300,000
* 1 ≤ s, t, xi, yi ≤ N
* Different from s and t
* Guaranteed to reach t from s

Output

When the given graph is G, output the "beauty" of the set (G, s, t) in one line.

Examples

Input

3 2 1 3
1 2
2 3


Output

1


Input

9 8 7 8
2 6
4 9
8 6
9 2
3 8
1 8
8 5
7 9


Output

7


Input

4 3 1 4
1 2
3 4
4 1


Output

0


Input

9 7 8 9
9 6
6 5
3 6
3 7
2 5
8 5
1 4


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 

You are given a sequence a_{1}, a_{2}, ..., a_{N}. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(a_{i}, a_{j}, a_{k}) = 1. Here GCD stands for the Greatest Common Divisor.

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

The first line of input contains a single integer N - the length of the sequence.

The second line contains N space-separated integers - a_{1}, a_{2}, ..., a_{N} respectively.

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

Output the required number of triples on the first line of the output.

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

$1 ≤ N ≤ 100 : 22 points.$
$1 ≤ N ≤ 1000 : 23 points.$
$1 ≤ N ≤ 10^{5} : 55 points.$
$1 ≤ a_{i} ≤ 10^{6}$

------ Example ------ 

Input:
4
1 2 3 4

Output:
4

------ Explanation ------ 

Any triple will be a coprime one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We define the sequence ```SF``` in the following way in terms of four previous sequences: ```S1```, ```S2```, ```S3``` and ```ST```



We are interested in collecting the terms of SF that are multiple of ten.

The first term multiple of ten of this sequence is  ```60```

Make the function ```find_mult10_SF()``` that you introduce the ordinal number of a term multiple of 10 of SF and gives us the value of this term.

Let's see some cases: 
```python
find_mult10_SF(1) == 60

find_mult10_SF(2) == 70080

find_mult10_SF(3) ==  90700800
```
``` haskell
findMult10SF 1 `shouldBe` 60
findMult10SF 2 `shouldBe` 70080
findMult10SF 3 `shouldBe` 90700800
```
Memoization is advisable to have a more agile code for tests.

Your code will be tested up to the 300-th term, multiple of 10.

Happy coding!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu being a small kid, likes to play a lot, but he only likes to play with arrays. While playing he came up with an interesting question which he could not solve, can you please solve it for him?

Given an array consisting of distinct integers. Is it possible to partition the whole array into k disjoint non-empty parts such that p of the parts have even sum (each of them must have even sum) and remaining k - p have odd sum? (note that parts need not to be continuous).

If it is possible to partition the array, also give any possible way of valid partitioning.

Input

The first line will contain three space separated integers n, k, p (1 ≤ k ≤ n ≤ 105; 0 ≤ p ≤ k). The next line will contain n space-separated distinct integers representing the content of array a: a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

In the first line print "YES" (without the quotes) if it is possible to partition the array in the required way. Otherwise print "NO" (without the quotes).

If the required partition exists, print k lines after the first line. The ith of them should contain the content of the ith part. Print the content of the part in the line in the following way: firstly print the number of elements of the part, then print all the elements of the part in arbitrary order. There must be exactly p parts with even sum, each of the remaining k - p parts must have odd sum.

As there can be multiple partitions, you are allowed to print any valid partition.

Examples

Input

5 5 3
2 6 10 5 9


Output

YES
1 9
1 5
1 10
1 6
1 2


Input

5 5 3
7 14 2 9 5


Output

NO


Input

5 3 1
1 2 3 7 5


Output

YES
3 5 1 3
1 7
1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Largest Rectangle in Background

Imagine a photo taken to be used in an advertisement. The background on the left of the motive is whitish and you want to write some text on that background. So you scan the photo with a high resolution scanner and, for each line, count the number of pixels from the left that are sufficiently white and suitable for being written on. Your job is to find the area of the largest text box you can place on those pixels.

Example:
In the figure below, the whitish background pixels of the scanned photo are represented by asterisks.

```
*********************************
*********
*******
******
******
******
**************
**************
**************
***************
*********************

``` 

If you count the pixels on each line from the left you get the list (or array, depending on which language you are using) `[33, 9, 7, 6, 6, 6, 14, 14, 14, 15, 21]`. The largest reactangle that you can place on these pixels has an area of 70, and is represented by the dots in the figure below.

```
*********************************
*********
*******
******
******
******
..............
..............
..............
..............*
..............*******
``` 

Write a function that, given a list of the number whitish pixels on each line in the background, returns the area of the largest rectangle that fits on that background.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While discussing a proper problem A for a Codeforces Round, Kostya created a cyclic array of positive integers $a_1, a_2, \ldots, a_n$. Since the talk was long and not promising, Kostya created a new cyclic array $b_1, b_2, \ldots, b_{n}$ so that $b_i = (a_i \mod a_{i + 1})$, where we take $a_{n+1} = a_1$. Here $mod$ is the modulo operation. When the talk became interesting, Kostya completely forgot how array $a$ had looked like. Suddenly, he thought that restoring array $a$ from array $b$ would be an interesting problem (unfortunately, not A).


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 140582$) — the length of the array $a$.

The second line contains $n$ integers $b_1, b_2, \ldots, b_{n}$ ($0 \le b_i \le 187126$).


-----Output-----

If it is possible to restore some array $a$ of length $n$ so that $b_i = a_i \mod a_{(i \mod n) + 1}$ holds for all $i = 1, 2, \ldots, n$, print «YES» in the first line and the integers $a_1, a_2, \ldots, a_n$ in the second line. All $a_i$ should satisfy $1 \le a_i \le 10^{18}$. We can show that if an answer exists, then an answer with such constraint exists as well.

It it impossible to restore any valid $a$, print «NO» in one line.

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


-----Examples-----
Input
4
1 3 1 0

Output
YES
1 3 5 2

Input
2
4 4

Output
NO



-----Note-----

In the first example:  $1 \mod 3 = 1$  $3 \mod 5 = 3$  $5 \mod 2 = 1$  $2 \mod 1 = 0$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The statement of this problem is the same as the statement of problem C1. The only difference is that, in problem C1, n is always even, and in C2, n is always odd.

You are given a regular polygon with 2 ⋅ n vertices (it's convex and has equal sides and equal angles) and all its sides have length 1. Let's name it as 2n-gon.

Your task is to find the square of the minimum size such that you can embed 2n-gon in the square. Embedding 2n-gon in the square means that you need to place 2n-gon in the square in such way that each point which lies inside or on a border of 2n-gon should also lie inside or on a border of the square.

You can rotate 2n-gon and/or the square.

Input

The first line contains a single integer T (1 ≤ T ≤ 200) — the number of test cases.

Next T lines contain descriptions of test cases — one per line. Each line contains single odd integer n (3 ≤ n ≤ 199). Don't forget you need to embed 2n-gon, not an n-gon.

Output

Print T real numbers — one per test case. For each test case, print the minimum length of a side of the square 2n-gon can be embedded in. Your answer will be considered correct if its absolute or relative error doesn't exceed 10^{-6}.

Example

Input


3
3
5
199


Output


1.931851653
3.196226611
126.687663595

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There are *n* players (including Limak himself) and right now all of them have bids on the table. *i*-th of them has bid with size *a**i* dollars.

Each player can double his bid any number of times and triple his bid any number of times. The casino has a great jackpot for making all bids equal. Is it possible that Limak and his friends will win a jackpot?

Input Specification:
First line of input contains an integer *n* (2<=≤<=*n*<=≤<=105), the number of players.

The second line contains *n* integer numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109) — the bids of players.

Output Specification:
Print "Yes" (without the quotes) if players can make their bids become equal, or "No" otherwise.

Demo Input:
['4\n75 150 75 50\n', '3\n100 150 250\n']

Demo Output:
['Yes\n', 'No\n']

Note:
In the first sample test first and third players should double their bids twice, second player should double his bid once and fourth player should both double and triple his bid.

It can be shown that in the second sample test there is no way to make all bids equal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Providing wireless network coverage for a large office can be tricky. In this problem you are asked to set up wireless network coverage for an entire office floor plan. The floor plan can be viewed as an $N\times M$ grid. Each grid cell represents a single office. Each pair of adjacent offices (cells that share a side) are connected by a corridor. You may install routers in some of the offices. Each installed router provides wireless network for the (at most four) corridors that are incident to the office where the router is located. Installing routers at different offices may have different costs.

However, some issues arise. If neither of the two offices incident to a corridor has a router, the corridor would have weak signal. If both of the two offices incident to a corridor have a router, the corridor would have conflicting signals that would cause both routers to be inaccessible from the corridor. (Unfortunately the routers available are pretty old models that do not collaborate very well.) Consequently, for every corridor that has either weak or conflicting signal, you must additionally install a cellular hub, which provides separate wireless service (that uses cellular network and is independent of the routers). Each cellular hub is sold for $K$ dollars.

Find the minimum total cost to set up a wireless network that covers every corridor.

-----Input-----
The first line of the input has three integers $N$, $M$ ($2 \leq N, M \leq 40$), and $K$ ($0\leq K \leq 200$). The next $N$ lines contains $M$ non-negative integers each. The $j$-th integer on the $i$-th line is the cost (in dollars) of installing a router in the office at the $i$-th row, $j$-th column of the floor plan. All costs are no larger than $200$.

-----Output-----
Output the minimum total cost (in dollars) to provide a wireless network that covers every corridor.

-----Examples-----
Sample Input 1:
2 3 4
10 1 3
0 1 20
Sample Output 1:
9

Sample Input 2:
2 3 100
10 1 10
10 1 10
Sample Output 2:
21

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