vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Sinking Ship

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The ship crashed into a reef and is sinking. Now the entire crew must be evacuated. All *n* crew members have already lined up in a row (for convenience let's label them all from left to right with positive integers from 1 to *n*) and await further instructions. However, one should evacuate the crew properly, in a strict order. Specifically:

The first crew members to leave the ship are rats. Then women and children (both groups have the same priority) leave the ship. After that all men are evacuated from the ship. The captain leaves the sinking ship last.

If we cannot determine exactly who should leave the ship first for any two members of the crew by the rules from the previous paragraph, then the one who stands to the left in the line leaves the ship first (or in other words, the one whose number in the line is less).

For each crew member we know his status as a crew member, and also his name. All crew members have different names. Determine the order in which to evacuate the crew.

Input Specification:
The first line contains an integer *n*, which is the number of people in the crew (1<=≤<=*n*<=≤<=100). Then follow *n* lines. The *i*-th of those lines contains two words — the name of the crew member who is *i*-th in line, and his status on the ship. The words are separated by exactly one space. There are no other spaces in the line. The names consist of Latin letters, the first letter is uppercase, the rest are lowercase. The length of any name is from 1 to 10 characters. The status can have the following values: rat for a rat, woman for a woman, child for a child, man for a man, captain for the captain. The crew contains exactly one captain.

Output Specification:
Print *n* lines. The *i*-th of them should contain the name of the crew member who must be the *i*-th one to leave the ship.

Demo Input:
['6\nJack captain\nAlice woman\nCharlie man\nTeddy rat\nBob child\nJulia woman\n']

Demo Output:
['Teddy\nAlice\nBob\nJulia\nCharlie\nJack\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has $K$ chocolates and he wants to distribute them to $N$ people (numbered $1$ through $N$). These people are standing in a line in such a way that for each $i$ ($1 \le i \le N-1$), person $i$ and person $i+1$ are adjacent.
First, consider some way to distribute chocolates such that for each valid $i$, the number of chocolates the $i$-th person would receive from Chef is $A_i$ and the sum $S_1 = \sum_{i=1}^{N-1} \left|A_i - A_{i+1}\right|$ is minimum possible. Of course, each person must receive a non-negative integer number of chocolates.
Then, Chef wants to create a new sequence $B_1, B_2, \ldots, B_N$ by rearranging (permuting) the elements of the sequence $A_1, A_2, \ldots, A_N$. For each valid $i$, the number of chocolates the $i$-th person actually receives from Chef is $B_i$. Chef wants to distribute the chocolates (choose $B_1, B_2, \ldots, B_N$ by permuting the sequence $A$ and give $B_i$ chocolates to the $i$-th person for each valid $i$) in such a way that $S_2 = \sum_{i=1}^{N-1} \left|B_i – B_{i+1}\right|$ is maximum possible. You need to find the maximum value of $S_2$.
It is guaranteed that $S_2$ does not depend on the exact choice of the sequence $A_1, A_2, \ldots, A_N$, as long as it is a sequence that minimises $S_1$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains a single integer $K$.

-----Output-----
For each test case, print a single line containing one integer — the maximum value of the sum $S_2$.

-----Constraints-----
- $1 \le T \le 10$
- $2 \le N \le 10^5$
- $2 \le K \le 10^{100,000}$

-----Subtasks-----
Subtask #1 (30 points): $2 \le N, K \le 1,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
3
2

-----Example Output-----
2

-----Explanation-----
Example case 1: To minimise $S_1$, Chef could give $1$ chocolate to person $1$ and $1$ chocolate to person $2$, so $S_1 = |1-1| + |1-0| = 1$.
To maximise $S_2$, Chef can give $1$ chocolate to person $1$ and $1$ chocolate to person $3$, since the sequence $B = (1, 0, 1)$ is a permutation of $A = (1, 1, 0)$. Then, $S_2 = |1-0| + |0-1| = 2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are n bamboos in a row, and the i-th from the left is a_{i} meters high. 

Vladimir has just planted n bamboos in a row, each of which has height 0 meters right now, but they grow 1 meter each day. In order to make the partition nice Vladimir can cut each bamboo once at any height (no greater that the height of the bamboo), and then the bamboo will stop growing.

Vladimir wants to check the bamboos each d days (i.e. d days after he planted, then after 2d days and so on), and cut the bamboos that reached the required height. Vladimir wants the total length of bamboo parts he will cut off to be no greater than k meters.

What is the maximum value d he can choose so that he can achieve what he wants without cutting off more than k meters of bamboo?


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10^11) — the number of bamboos and the maximum total length of cut parts, in meters.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the required heights of bamboos, in meters.


-----Output-----

Print a single integer — the maximum value of d such that Vladimir can reach his goal.


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

Output
3

Input
3 40
10 30 50

Output
32



-----Note-----

In the first example Vladimir can check bamboos each 3 days. Then he will cut the first and the second bamboos after 3 days, and the third bamboo after 6 days. The total length of cut parts is 2 + 0 + 1 = 3 meters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I'm sure you're familiar with factorials – that is, the product of an integer and all the integers below it. 

For example, `5! = 120`, as `5 * 4 * 3 * 2 * 1 = 120`

Your challenge is to create a function that takes any number and returns the number that it is a factorial of. So, if your function receives `120`, it should return `"5!"` (as a string).

Of course, not every number is a factorial of another. In this case, your function would return `"None"` (as a string).

### Examples

* `120` will return `"5!"`
* `24` will return `"4!"`
* `150` will return `"None"`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program that, given a date in $2009$, determines the day of week on that date.

-----Input-----
The first line contains two positive integers $D$ (day) and $M$ (month) separated by a space. The numbers will be a valid date in $2009$.

-----Output-----
Output the day of the week on day $D$ of month $M$ in $2009$. The output should be one of the words “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday” or “Sunday”.

-----Examples-----
Sample Input 1:
1 1
Sample Output 1:
Thursday

Sample Input 2:
17 1
Sample Output 2:
Saturday

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On Children's Day, the child got a toy from Delayyy as a present. However, the child is so naughty that he can't wait to destroy the toy.

The toy consists of n parts and m ropes. Each rope links two parts, but every pair of parts is linked by at most one rope. To split the toy, the child must remove all its parts. The child can remove a single part at a time, and each remove consume an energy. Let's define an energy value of part i as v_{i}. The child spend v_{f}_1 + v_{f}_2 + ... + v_{f}_{k} energy for removing part i where f_1, f_2, ..., f_{k} are the parts that are directly connected to the i-th and haven't been removed.

Help the child to find out, what is the minimum total energy he should spend to remove all n parts.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000). The second line contains n integers: v_1, v_2, ..., v_{n} (0 ≤ v_{i} ≤ 10^5). Then followed m lines, each line contains two integers x_{i} and y_{i}, representing a rope from part x_{i} to part y_{i} (1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i}).

Consider all the parts are numbered from 1 to n.


-----Output-----

Output the minimum total energy the child should spend to remove all n parts of the toy.


-----Examples-----
Input
4 3
10 20 30 40
1 4
1 2
2 3

Output
40

Input
4 4
100 100 100 100
1 2
2 3
2 4
3 4

Output
400

Input
7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4

Output
160



-----Note-----

One of the optimal sequence of actions in the first sample is:  First, remove part 3, cost of the action is 20.  Then, remove part 2, cost of the action is 10.  Next, remove part 4, cost of the action is 10.  At last, remove part 1, cost of the action is 0. 

So the total energy the child paid is 20 + 10 + 10 + 0 = 40, which is the minimum.

In the second sample, the child will spend 400 no matter in what order he will remove the parts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jeff got 2n real numbers a1, a2, ..., a2n as a birthday present. The boy hates non-integer numbers, so he decided to slightly "adjust" the numbers he's got. Namely, Jeff consecutively executes n operations, each of them goes as follows:

  * choose indexes i and j (i ≠ j) that haven't been chosen yet; 
  * round element ai to the nearest integer that isn't more than ai (assign to ai: ⌊ ai ⌋); 
  * round element aj to the nearest integer that isn't less than aj (assign to aj: ⌈ aj ⌉). 



Nevertheless, Jeff doesn't want to hurt the feelings of the person who gave him the sequence. That's why the boy wants to perform the operations so as to make the absolute value of the difference between the sum of elements before performing the operations and the sum of elements after performing the operations as small as possible. Help Jeff find the minimum absolute value of the difference.

Input

The first line contains integer n (1 ≤ n ≤ 2000). The next line contains 2n real numbers a1, a2, ..., a2n (0 ≤ ai ≤ 10000), given with exactly three digits after the decimal point. The numbers are separated by spaces.

Output

In a single line print a single real number — the required difference with exactly three digits after the decimal point.

Examples

Input

3
0.000 0.500 0.750 1.000 2.000 3.000


Output

0.250


Input

3
4469.000 6526.000 4864.000 9356.383 7490.000 995.896


Output

0.279

Note

In the first test case you need to perform the operations as follows: (i = 1, j = 4), (i = 2, j = 3), (i = 5, j = 6). In this case, the difference will equal |(0 + 0.5 + 0.75 + 1 + 2 + 3) - (0 + 0 + 1 + 1 + 2 + 3)| = 0.25.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An agent called Cypher is decrypting a message, that contains a composite number $n$. All divisors of $n$, which are greater than $1$, are placed in a circle. Cypher can choose the initial order of numbers in the circle.

In one move Cypher can choose two adjacent numbers in a circle and insert their least common multiple between them. He can do that move as many times as needed.

A message is decrypted, if every two adjacent numbers are not coprime. Note that for such constraints it's always possible to decrypt the message.

Find the minimal number of moves that Cypher should do to decrypt the message, and show the initial order of numbers in the circle for that.


-----Input-----

The first line contains an integer $t$ $(1 \le t \le 100)$ — the number of test cases. Next $t$ lines describe each test case.

In a single line of each test case description, there is a single composite number $n$ $(4 \le n \le 10^9)$ — the number from the message.

It's guaranteed that the total number of divisors of $n$ for all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case in the first line output the initial order of divisors, which are greater than $1$, in the circle. In the second line output, the minimal number of moves needed to decrypt the message.

If there are different possible orders with a correct answer, print any of them.


-----Example-----
Input
3
6
4
30

Output
2 3 6 
1
2 4 
0
2 30 6 3 15 5 10 
0



-----Note-----

In the first test case $6$ has three divisors, which are greater than $1$: $2, 3, 6$. Regardless of the initial order, numbers $2$ and $3$ are adjacent, so it's needed to place their least common multiple between them. After that the circle becomes $2, 6, 3, 6$, and every two adjacent numbers are not coprime.

In the second test case $4$ has two divisors greater than $1$: $2, 4$, and they are not coprime, so any initial order is correct, and it's not needed to place any least common multiples.

In the third test case all divisors of $30$ greater than $1$ can be placed in some order so that there are no two adjacent numbers that are coprime.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.
Example 1:
Input:
5
4 2 -3 1 6
Output: 
Yes
Explanation: 
2, -3, 1 is the subarray 
with sum 0.
Example 2:
Input:
5
4 2 0 1 6
Output: 
Yes
Explanation: 
0 is one of the element 
in the array so there exist a 
subarray with sum 0.
Your Task:
You only need to complete the function subArrayExists() that takes array and n as parameters and returns true or false depending upon whether there is a subarray present with 0-sum or not. Printing will be taken care by the drivers code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).
Constraints:
1 <= n <= 10^{4}
-10^{5} <= a[i] <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrewid the Android is a galaxy-famous detective. In his free time he likes to think about strings containing zeros and ones.

Once he thought about a string of length n consisting of zeroes and ones. Consider the following operation: we choose any two adjacent positions in the string, and if one them contains 0, and the other contains 1, then we are allowed to remove these two digits from the string, obtaining a string of length n - 2 as a result.

Now Andreid thinks about what is the minimum length of the string that can remain after applying the described operation several times (possibly, zero)? Help him to calculate this number.


-----Input-----

First line of the input contains a single integer n (1 ≤ n ≤ 2·10^5), the length of the string that Andreid has.

The second line contains the string of length n consisting only from zeros and ones.


-----Output-----

Output the minimum length of the string that may remain after applying the described operations several times.


-----Examples-----
Input
4
1100

Output
0

Input
5
01010

Output
1

Input
8
11101111

Output
6



-----Note-----

In the first sample test it is possible to change the string like the following: $1100 \rightarrow 10 \rightarrow(\text{empty})$.

In the second sample test it is possible to change the string like the following: $01010 \rightarrow 010 \rightarrow 0$.

In the third sample test it is possible to change the string like the following: $11101111 \rightarrow 111111$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya and his friends are walking along the fence of height h and they do not want the guard to notice them. In order to achieve this the height of each of the friends should not exceed h. If the height of some person is greater than h he can bend down and then he surely won't be noticed by the guard. The height of the i-th person is equal to a_{i}.

Consider the width of the person walking as usual to be equal to 1, while the width of the bent person is equal to 2. Friends want to talk to each other while walking, so they would like to walk in a single row. What is the minimum width of the road, such that friends can walk in a row and remain unattended by the guard?


-----Input-----

The first line of the input contains two integers n and h (1 ≤ n ≤ 1000, 1 ≤ h ≤ 1000) — the number of friends and the height of the fence, respectively.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 2h), the i-th of them is equal to the height of the i-th person.


-----Output-----

Print a single integer — the minimum possible valid width of the road.


-----Examples-----
Input
3 7
4 5 14

Output
4

Input
6 1
1 1 1 1 1 1

Output
6

Input
6 5
7 6 8 9 10 5

Output
11



-----Note-----

In the first sample, only person number 3 must bend down, so the required width is equal to 1 + 1 + 2 = 4.

In the second sample, all friends are short enough and no one has to bend, so the width 1 + 1 + 1 + 1 + 1 + 1 = 6 is enough.

In the third sample, all the persons have to bend, except the last one. The required minimum width of the road is equal to 2 + 2 + 2 + 2 + 2 + 1 = 11.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Guilty --- to the kitchen!

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
It's a very unfortunate day for Volodya today. He got bad mark in algebra and was therefore forced to do some work in the kitchen, namely to cook borscht (traditional Russian soup). This should also improve his algebra skills.

According to the borscht recipe it consists of *n* ingredients that have to be mixed in proportion  litres (thus, there should be *a*1<=·*x*,<=...,<=*a**n*<=·*x* litres of corresponding ingredients mixed for some non-negative *x*). In the kitchen Volodya found out that he has *b*1,<=...,<=*b**n* litres of these ingredients at his disposal correspondingly. In order to correct his algebra mistakes he ought to cook as much soup as possible in a *V* litres volume pan (which means the amount of soup cooked can be between 0 and *V* litres). What is the volume of borscht Volodya will cook ultimately?

Input Specification:
The first line of the input contains two space-separated integers *n* and *V* (1<=≤<=*n*<=≤<=20,<=1<=≤<=*V*<=≤<=10000). The next line contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=100). Finally, the last line contains *n* space-separated integers *b**i* (0<=≤<=*b**i*<=≤<=100).

Output Specification:
Your program should output just one real number — the volume of soup that Volodya will cook. Your answer must have a relative or absolute error less than 10<=-<=4.

Demo Input:
['1 100\n1\n40\n', '2 100\n1 1\n25 30\n', '2 100\n1 1\n60 60\n']

Demo Output:
['40.0\n', '50.0\n', '100.0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imp is watching a documentary about cave painting. [Image] 

Some numbers, carved in chaotic order, immediately attracted his attention. Imp rapidly proposed a guess that they are the remainders of division of a number n by all integers i from 1 to k. Unfortunately, there are too many integers to analyze for Imp.

Imp wants you to check whether all these remainders are distinct. Formally, he wants to check, if all $n \text{mod} i$, 1 ≤ i ≤ k, are distinct, i. e. there is no such pair (i, j) that:   1 ≤ i < j ≤ k,  $n \operatorname{mod} i = n \operatorname{mod} j$, where $x \operatorname{mod} y$ is the remainder of division x by y. 


-----Input-----

The only line contains two integers n, k (1 ≤ n, k ≤ 10^18).


-----Output-----

Print "Yes", if all the remainders are distinct, and "No" otherwise.

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


-----Examples-----
Input
4 4

Output
No

Input
5 3

Output
Yes



-----Note-----

In the first sample remainders modulo 1 and 4 coincide.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You want to build a standard house of cards, but you don't know how many cards you will need. Write a program which will count the minimal number of cards according to the number of floors you want to have. For example, if you want a one floor house, you will need 7 of them (two pairs of two cards on the base floor, one horizontal card and one pair to get the first floor). Here you can see which kind of house of cards I mean:
http://www.wikihow.com/Build-a-Tower-of-Cards

## Note about floors:
This kata uses the British numbering system for building floors. If you want your house of cards to have a first floor, it needs a ground floor and then a first floor above that.

### Details (Ruby & JavaScript & Python & R)
The input must be an integer greater than 0, for other input raise an error.

### Details (Haskell)
The input must be an integer greater than 0, for other input return `Nothing`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The administration of the Tomsk Region firmly believes that it's time to become a megacity (that is, get population of one million). Instead of improving the demographic situation, they decided to achieve its goal by expanding the boundaries of the city.

The city of Tomsk can be represented as point on the plane with coordinates (0; 0). The city is surrounded with n other locations, the i-th one has coordinates (x_{i}, y_{i}) with the population of k_{i} people. You can widen the city boundaries to a circle of radius r. In such case all locations inside the circle and on its border are included into the city.

Your goal is to write a program that will determine the minimum radius r, to which is necessary to expand the boundaries of Tomsk, so that it becomes a megacity.


-----Input-----

The first line of the input contains two integers n and s (1 ≤ n ≤ 10^3; 1 ≤ s < 10^6) — the number of locatons around Tomsk city and the population of the city. Then n lines follow. The i-th line contains three integers — the x_{i} and y_{i} coordinate values of the i-th location and the number k_{i} of people in it (1 ≤ k_{i} < 10^6). Each coordinate is an integer and doesn't exceed 10^4 in its absolute value.

It is guaranteed that no two locations are at the same point and no location is at point (0; 0).


-----Output-----

In the output, print "-1" (without the quotes), if Tomsk won't be able to become a megacity. Otherwise, in the first line print a single real number — the minimum radius of the circle that the city needs to expand to in order to become a megacity.

The answer is considered correct if the absolute or relative error don't exceed 10^{ - 6}.


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

Output
2.8284271

Input
4 999998
1 1 2
2 2 1
3 3 1
2 -2 1

Output
1.4142136

Input
2 1
1 1 999997
2 2 1

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your website is divided vertically in sections, and each can be of different size (height).  
You need to establish the section index (starting at `0`) you are at, given the `scrollY` and `sizes` of all sections.  
Sections start with `0`, so if first section is `200` high, it takes `0-199` "pixels" and second starts at `200`.

### Example:

`getSectionIdFromScroll( 300, [300,200,400,600,100] )`

will output number `1` as it's the second section.

`getSectionIdFromScroll( 1600, [300,200,400,600,100] )`

will output number `-1` as it's past last section.

Given the `scrollY` integer (always non-negative) and an array of non-negative integers (with at least one element), calculate the index (starting at `0`) or `-1` if `scrollY` falls beyond last section (indication of an error).

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