vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Bag of mice

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The dragon and the princess are arguing about what to do on the New Year's Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, while the princess thinks they should just go to bed early. They are desperate to come to an amicable agreement, so they decide to leave this up to chance.

They take turns drawing a mouse from a bag which initially contains *w* white and *b* black mice. The person who is the first to draw a white mouse wins. After each mouse drawn by the dragon the rest of mice in the bag panic, and one of them jumps out of the bag itself (the princess draws her mice carefully and doesn't scare other mice). Princess draws first. What is the probability of the princess winning?

If there are no more mice in the bag and nobody has drawn a white mouse, the dragon wins. Mice which jump out of the bag themselves are not considered to be drawn (do not define the winner). Once a mouse has left the bag, it never returns to it. Every mouse is drawn from the bag with the same probability as every other one, and every mouse jumps out of the bag with the same probability as every other one.

Input Specification:
The only line of input data contains two integers *w* and *b* (0<=≤<=*w*,<=*b*<=≤<=1000).

Output Specification:
Output the probability of the princess winning. The answer is considered to be correct if its absolute or relative error does not exceed 10<=-<=9.

Demo Input:
['1 3\n', '5 5\n']

Demo Output:
['0.500000000\n', '0.658730159\n']

Note:
Let's go through the first sample. The probability of the princess drawing a white mouse on her first turn and winning right away is 1/4. The probability of the dragon drawing a black mouse and not winning on his first turn is 3/4 * 2/3 = 1/2. After this there are two mice left in the bag — one black and one white; one of them jumps out, and the other is drawn by the princess on her second turn. If the princess' mouse is white, she wins (probability is 1/2 * 1/2 = 1/4), otherwise nobody gets the white mouse, so according to the rule the dragon wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given array $a$ of length $n$. You can choose one segment $[l, r]$ ($1 \le l \le r \le n$) and integer value $k$ (positive, negative or even zero) and change $a_l, a_{l + 1}, \dots, a_r$ by $k$ each (i.e. $a_i := a_i + k$ for each $l \le i \le r$).

What is the maximum possible number of elements with value $c$ that can be obtained after one such operation?


-----Input-----

The first line contains two integers $n$ and $c$ ($1 \le n \le 5 \cdot 10^5$, $1 \le c \le 5 \cdot 10^5$) — the length of array and the value $c$ to obtain.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5 \cdot 10^5$) — array $a$.


-----Output-----

Print one integer — the maximum possible number of elements with value $c$ which can be obtained after performing operation described above.


-----Examples-----
Input
6 9
9 9 9 9 9 9

Output
6

Input
3 2
6 2 6

Output
2



-----Note-----

In the first example we can choose any segment and $k = 0$. The array will stay same.

In the second example we can choose segment $[1, 3]$ and $k = -4$. The array will become $[2, -2, 2]$.

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 E_1 < E_2 < ... < E_{n}. 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:   initially the atom is in the state i, we spend E_{k} - E_{i} energy to put the atom in the state k, the atom emits a photon with useful energy E_{k} - E_{j} and changes its state to the state j, the atom spontaneously changes its state to the state i, losing energy E_{j} - E_{i}, the process repeats from step 1. 

Let's define the energy conversion efficiency as $\eta = \frac{E_{k} - E_{j}}{E_{k} - E_{i}}$, 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 E_{k} - E_{i} ≤ 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 ≤ 10^5, 1 ≤ U ≤ 10^9) — the number of states and the maximum possible difference between E_{k} and E_{i}.

The second line contains a sequence of integers E_1, E_2, ..., E_{n} (1 ≤ E_1 < E_2... < E_{n} ≤ 10^9). It is guaranteed that all E_{i} 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 $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-9}$.


-----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 $\eta = \frac{5 - 3}{5 - 1} = 0.5$.

In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to $\eta = \frac{24 - 17}{24 - 16} = 0.875$.

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

I have a cat and a dog.

I got them at the same time as kitten/puppy. That was `humanYears` years ago.

Return their respective ages now as [`humanYears`,`catYears`,`dogYears`]

NOTES:
* humanYears >= 1
* humanYears are whole numbers only

## Cat Years

* `15` cat years for first year
* `+9` cat years for second year
* `+4` cat years for each year after that

## Dog Years

* `15` dog years for first year
* `+9` dog years for second year
* `+5` dog years for each year after that



**References**

* http://www.catster.com/cats-101/calculate-cat-age-in-cat-years
* http://www.slate.com/articles/news_and_politics/explainer/2009/05/a_dogs_life.html



If you liked this Kata there is another related one here

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After a drawn-out mooclear arms race, Farmer John and the Mischievous Mess Makers have finally agreed to establish peace. They plan to divide the territory of Bovinia with a line passing through at least two of the n outposts scattered throughout the land. These outposts, remnants of the conflict, are located at the points (x1, y1), (x2, y2), ..., (xn, yn).

In order to find the optimal dividing line, Farmer John and Elsie have plotted a map of Bovinia on the coordinate plane. Farmer John's farm and the Mischievous Mess Makers' base are located at the points P = (a, 0) and Q = ( - a, 0), respectively. Because they seek a lasting peace, Farmer John and Elsie would like to minimize the maximum difference between the distances from any point on the line to P and Q.

Formally, define the difference of a line <image> relative to two points P and Q as the smallest real number d so that for all points X on line <image>, |PX - QX| ≤ d. (It is guaranteed that d exists and is unique.) They wish to find the line <image> passing through two distinct outposts (xi, yi) and (xj, yj) such that the difference of <image> relative to P and Q is minimized.

Input

The first line of the input contains two integers n and a (2 ≤ n ≤ 100 000, 1 ≤ a ≤ 10 000) — the number of outposts and the coordinates of the farm and the base, respectively.

The following n lines describe the locations of the outposts as pairs of integers (xi, yi) (|xi|, |yi| ≤ 10 000). These points are distinct from each other as well as from P and Q.

Output

Print a single real number—the difference of the optimal dividing line. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Examples

Input

2 5
1 0
2 1


Output

7.2111025509


Input

3 6
0 1
2 5
0 -3


Output

0.0000000000

Note

In the first sample case, the only possible line <image> is y = x - 1. It can be shown that the point X which maximizes |PX - QX| is (13, 12), with <image>, which is <image>.

In the second sample case, if we pick the points (0, 1) and (0, - 3), we get <image> as x = 0. Because PX = QX on this line, the minimum possible difference is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
“A watched pot never boils”, as the saying goes. Chef Edward has been cooking for ages, and empirically the saying seems to be true in his kitchen – he has yet to see a pot actually start boiling. His wife Gunilla is a bit suspicious of Edward’s claim though. She knows how he often loses focus after a little while, and thinks that it is very likely Edward gets tired of watching after about the same period of time starting when he puts it on the stove.

Being scientifically minded, Gunilla quickly designed an experiment which could help Edward gain more insight into the boiling of pots. Every time during the last week when Edward boiled a pot of water, he wrote down the intervals of time when he was not watching the pot. Now, he has a large log of these intervals, and wonders whether Gunilla is right (i.e. it may be the case Edward just happened to watch away every time the pot started boiling), or if his hypothesis is correct.

Given this data, is it possible that the pot actually starts boiling after the same amount of time, every time?

-----Input-----
The first line of the input contains an integer $1 \le N \le 1000$, the number of times Edward boiled water in the last week. Then, $N$ descriptions of a boiling follow. Each description contains two numbers $0 \le a \le b \le 1000$. This means that Edward looked away during seconds $[a, b]$ (i.e. from the start of second $a$, to the end of second $b$), and that Edward first saw the pot boiling once he looked back.

-----Output-----
If it is impossible that all the pots actually started boiling at the same point in time, output edward is right. Otherwise, output gunilla has a point.

-----Examples-----
Sample Input:
2
1 7
5 5
Sample Output:
gunilla has a point

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Background:
Verma was very afraid of his maths test to be held at school, the next day. So, he dreamt of one of the hardest questions that is likely to be asked in the exam.
He calls his friend Mehta, who is already good at maths.
So, he asks Mehta to solve the following task.

Task:
You will given a number N.
F(N) is defined as number of solutions of the following equation.
  such that,1.   2. (x & y & z) > 0,  where '&' refers to Bitwise And operator.
Since, the answer can be too large, you need to calculate F(N) Modulo 1000000007.

Input:
First Line of the input contains number of test cases T.
Next T Lines of the input contains a single integer N as described above.

Output:
Print F(N) for each given N in a separate line.

Constraints:
T  ≤ 10^3
0 ≤ N ≤ 10^18

SAMPLE INPUT
5
10 
123
345
567
231

SAMPLE OUTPUT
3
4105
30142
111295
17551

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N ID cards, and there are M gates.
We can pass the i-th gate if we have one of the following ID cards: the L_i-th, (L_i+1)-th, ..., and R_i-th ID cards.
How many of the ID cards allow us to pass all the gates alone?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - 1 \leq M \leq 10^5
 - 1 \leq L_i \leq R_i \leq N

-----Input-----
Input is given from Standard Input in the following format:
N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

-----Output-----
Print the number of ID cards that allow us to pass all the gates alone.

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

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

Two ID cards allow us to pass all the gates alone, as follows:
 - The first ID card does not allow us to pass the second gate.
 - The second ID card allows us to pass all the gates.
 - The third ID card allows us to pass all the gates.
 - The fourth ID card does not allow us to pass the first gate.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a __moreZeros__ function which will __receive a string__ for input, and __return an array__ (or null terminated string in C) containing only the characters from that string whose __binary representation of its ASCII value__ consists of _more zeros than ones_. 

You should __remove any duplicate characters__, keeping the __first occurence__ of any such duplicates, so they are in the __same order__ in the final array as they first appeared in the input string.

Examples

            
All input will be valid strings of length > 0. Leading zeros in binary should not be counted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vova's house is an array consisting of $n$ elements (yeah, this is the first problem, I think, where someone lives in the array). There are heaters in some positions of the array. The $i$-th element of the array is $1$ if there is a heater in the position $i$, otherwise the $i$-th element of the array is $0$.

Each heater has a value $r$ ($r$ is the same for all heaters). This value means that the heater at the position $pos$ can warm up all the elements in range $[pos - r + 1; pos + r - 1]$.

Vova likes to walk through his house while he thinks, and he hates cold positions of his house. Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater. 

Vova's target is to warm up the whole house (all the elements of the array), i.e. if $n = 6$, $r = 2$ and heaters are at positions $2$ and $5$, then Vova can warm up the whole house if he switches all the heaters in the house on (then the first $3$ elements will be warmed up by the first heater and the last $3$ elements will be warmed up by the second heater).

Initially, all the heaters are off.

But from the other hand, Vova didn't like to pay much for the electricity. So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater.

Your task is to find this number of heaters or say that it is impossible to warm up the whole house.


-----Input-----

The first line of the input contains two integers $n$ and $r$ ($1 \le n, r \le 1000$) — the number of elements in the array and the value of heaters.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$) — the Vova's house description.


-----Output-----

Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.


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

Output
3

Input
5 3
1 0 0 0 1

Output
2

Input
5 10
0 0 0 0 0

Output
-1

Input
10 3
0 0 1 1 0 1 0 0 0 1

Output
3



-----Note-----

In the first example the heater at the position $2$ warms up elements $[1; 3]$, the heater at the position $3$ warms up elements $[2, 4]$ and the heater at the position $6$ warms up elements $[5; 6]$ so the answer is $3$.

In the second example the heater at the position $1$ warms up elements $[1; 3]$ and the heater at the position $5$ warms up elements $[3; 5]$ so the answer is $2$.

In the third example there are no heaters so the answer is -1.

In the fourth example the heater at the position $3$ warms up elements $[1; 5]$, the heater at the position $6$ warms up elements $[4; 8]$ and the heater at the position $10$ warms up elements $[8; 10]$ so the answer is $3$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In the school computer room there are *n* servers which are responsible for processing several computing tasks. You know the number of scheduled tasks for each server: there are *m**i* tasks assigned to the *i*-th server.

In order to balance the load for each server, you want to reassign some tasks to make the difference between the most loaded server and the least loaded server as small as possible. In other words you want to minimize expression *m**a*<=-<=*m**b*, where *a* is the most loaded server and *b* is the least loaded one.

In one second you can reassign a single task. Thus in one second you can choose any pair of servers and move a single task from one server to another.

Write a program to find the minimum number of seconds needed to balance the load of servers.

Input Specification:
The first line contains positive number *n* (1<=≤<=*n*<=≤<=105) — the number of the servers. 

The second line contains the sequence of non-negative integers *m*1,<=*m*2,<=...,<=*m**n* (0<=≤<=*m**i*<=≤<=2·104), where *m**i* is the number of tasks assigned to the *i*-th server.

Output Specification:
Print the minimum number of seconds required to balance the load.

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

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

Note:
In the first example two seconds are needed. In each second, a single task from server #2 should be moved to server #1. After two seconds there should be 3 tasks on server #1 and 4 tasks on server #2.

In the second example the load is already balanced.

A possible sequence of task movements for the third example is:
 1.  move a task from server #4 to server #1 (the sequence *m* becomes: 2 2 3 3 5); 1.  then move task from server #5 to server #1 (the sequence *m* becomes: 3 2 3 3 4); 1.  then move task from server #5 to server #2 (the sequence *m* becomes: 3 3 3 3 3). 
The above sequence is one of several possible ways to balance the load of servers in three seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob has a permutation of integers from 1 to n. Denote this permutation as p. The i-th element of p will be denoted as pi. For all pairs of distinct integers i, j between 1 and n, he wrote the number ai, j = min(pi, pj). He writes ai, i = 0 for all integer i from 1 to n.

Bob gave you all the values of ai, j that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given.

Input

The first line of the input will contain a single integer n (2 ≤ n ≤ 50).

The next n lines will contain the values of ai, j. The j-th number on the i-th line will represent ai, j. The i-th number on the i-th line will be 0. It's guaranteed that ai, j = aj, i and there is at least one solution consistent with the information given.

Output

Print n space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them.

Examples

Input

2
0 1
1 0


Output

2 1


Input

5
0 2 2 1 2
2 0 4 1 3
2 4 0 1 3
1 1 1 0 1
2 3 3 1 0


Output

2 5 4 1 3

Note

In the first case, the answer can be {1, 2} or {2, 1}.

In the second case, another possible answer is {2, 4, 5, 1, 3}.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* parliamentarians in Berland. They are numbered with integers from 1 to *n*. It happened that all parliamentarians with odd indices are Democrats and all parliamentarians with even indices are Republicans.

New parliament assembly hall is a rectangle consisting of *a*<=×<=*b* chairs — *a* rows of *b* chairs each. Two chairs are considered neighbouring if they share as side. For example, chair number 5 in row number 2 is neighbouring to chairs number 4 and 6 in this row and chairs with number 5 in rows 1 and 3. Thus, chairs have four neighbours in general, except for the chairs on the border of the hall

We know that if two parliamentarians from one political party (that is two Democrats or two Republicans) seat nearby they spent all time discussing internal party issues.

Write the program that given the number of parliamentarians and the sizes of the hall determine if there is a way to find a seat for any parliamentarian, such that no two members of the same party share neighbouring seats.

Input Specification:
The first line of the input contains three integers *n*, *a* and *b* (1<=≤<=*n*<=≤<=10<=000, 1<=≤<=*a*,<=*b*<=≤<=100) — the number of parliamentarians, the number of rows in the assembly hall and the number of seats in each row, respectively.

Output Specification:
If there is no way to assigns seats to parliamentarians in a proper way print -1.

Otherwise print the solution in *a* lines, each containing *b* integers. The *j*-th integer of the *i*-th line should be equal to the index of parliamentarian occupying this seat, or 0 if this seat should remain empty. If there are multiple possible solution, you may print any of them.

Demo Input:
['3 2 2\n', '8 4 3\n', '10 2 2\n']

Demo Output:
['0 3\n1 2\n', '7 8 3\n0 1 4\n6 0 5\n0 2 0\n', '-1\n']

Note:
In the first sample there are many other possible solutions. For example, 

and 

The following assignment 

is incorrect, because parliamentarians 1 and 3 are both from Democrats party but will occupy neighbouring seats.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers arr and an integer target.
You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.
 
Example 1:
Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:
Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:
Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:
Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:
Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

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