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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Imagine that you have a twin brother or sister. Having another person that looks exactly like you seems very unusual. It's hard to say if having something of an alter ego is good or bad. And if you do have a twin, then you very well know what it's like.

Now let's imagine a typical morning in your family. You haven't woken up yet, and Mom is already going to work. She has been so hasty that she has nearly forgotten to leave the two of her darling children some money to buy lunches in the school cafeteria. She fished in the purse and found some number of coins, or to be exact, *n* coins of arbitrary values *a*1,<=*a*2,<=...,<=*a**n*. But as Mom was running out of time, she didn't split the coins for you two. So she scribbled a note asking you to split the money equally.

As you woke up, you found Mom's coins and read her note. "But why split the money equally?" — you thought. After all, your twin is sleeping and he won't know anything. So you decided to act like that: pick for yourself some subset of coins so that the sum of values of your coins is strictly larger than the sum of values of the remaining coins that your twin will have. However, you correctly thought that if you take too many coins, the twin will suspect the deception. So, you've decided to stick to the following strategy to avoid suspicions: you take the minimum number of coins, whose sum of values is strictly more than the sum of values of the remaining coins. On this basis, determine what minimum number of coins you need to take to divide them in the described manner.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=100) — the number of coins. The second line contains a sequence of *n* integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=100) — the coins' values. All numbers are separated with spaces.

Output Specification:
In the single line print the single number — the minimum needed number of coins.

Demo Input:
['2\n3 3\n', '3\n2 1 2\n']

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

Note:
In the first sample you will have to take 2 coins (you and your twin have sums equal to 6, 0 correspondingly). If you take 1 coin, you get sums 3, 3. If you take 0 coins, you get sums 0, 6. Those variants do not satisfy you as your sum should be strictly more that your twins' sum.

In the second sample one coin isn't enough for us, too. You can pick coins with values 1, 2 or 2, 2. In any case, the minimum number of coins equals 2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Three sons inherited from their father a rectangular corn fiend divided into *n*<=×<=*m* squares. For each square we know how many tons of corn grows on it. The father, an old farmer did not love all three sons equally, which is why he bequeathed to divide his field into three parts containing *A*, *B* and *C* tons of corn.

The field should be divided by two parallel lines. The lines should be parallel to one side of the field and to each other. The lines should go strictly between the squares of the field. Each resulting part of the field should consist of at least one square. 

Your task is to find the number of ways to divide the field as is described above, that is, to mark two lines, dividing the field in three parts so that on one of the resulting parts grew *A* tons of corn, *B* on another one and *C* on the remaining one.

Input Specification:
The first line contains space-separated integers *n* and *m* — the sizes of the original (1<=≤<=*n*,<=*m*<=≤<=50,<=*max*(*n*,<=*m*)<=≥<=3). Then the field's description follows: *n* lines, each containing *m* space-separated integers *c**ij*, (0<=≤<=*c**ij*<=≤<=100) — the number of tons of corn each square contains. The last line contains space-separated integers *A*,<=*B*,<=*C* (0<=≤<=*A*,<=*B*,<=*C*<=≤<=106).

Output Specification:
Print the answer to the problem: the number of ways to divide the father's field so that one of the resulting parts contained *A* tons of corn, another one contained *B* tons, and the remaining one contained *C* tons. If no such way exists, print 0.

Demo Input:
['3 3\n1 1 1\n1 1 1\n1 1 1\n3 3 3\n', '2 5\n1 1 1 1 1\n2 2 2 2 2\n3 6 6\n', '3 3\n1 2 3\n3 1 2\n2 3 1\n5 6 7\n']

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

Note:
The lines dividing the field can be horizontal or vertical, but they should be parallel to each other.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tanya wants to go on a journey across the cities of Berland. There are $n$ cities situated along the main railroad line of Berland, and these cities are numbered from $1$ to $n$. 

Tanya plans her journey as follows. First of all, she will choose some city $c_1$ to start her journey. She will visit it, and after that go to some other city $c_2 > c_1$, then to some other city $c_3 > c_2$, and so on, until she chooses to end her journey in some city $c_k > c_{k - 1}$. So, the sequence of visited cities $[c_1, c_2, \dots, c_k]$ should be strictly increasing.

There are some additional constraints on the sequence of cities Tanya visits. Each city $i$ has a beauty value $b_i$ associated with it. If there is only one city in Tanya's journey, these beauty values imply no additional constraints. But if there are multiple cities in the sequence, then for any pair of adjacent cities $c_i$ and $c_{i + 1}$, the condition $c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i}$ must hold.

For example, if $n = 8$ and $b = [3, 4, 4, 6, 6, 7, 8, 9]$, there are several three possible ways to plan a journey:  $c = [1, 2, 4]$;  $c = [3, 5, 6, 8]$;  $c = [7]$ (a journey consisting of one city is also valid). 

There are some additional ways to plan a journey that are not listed above.

Tanya wants her journey to be as beautiful as possible. The beauty value of the whole journey is the sum of beauty values over all visited cities. Can you help her to choose the optimal plan, that is, to maximize the beauty value of the journey?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cities in Berland.

The second line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($1 \le b_i \le 4 \cdot 10^5$), where $b_i$ is the beauty value of the $i$-th city.


-----Output-----

Print one integer — the maximum beauty of a journey Tanya can choose.


-----Examples-----
Input
6
10 7 1 9 10 15

Output
26

Input
1
400000

Output
400000

Input
7
8 9 26 11 12 29 14

Output
55



-----Note-----

The optimal journey plan in the first example is $c = [2, 4, 5]$.

The optimal journey plan in the second example is $c = [1]$.

The optimal journey plan in the third example is $c = [3, 6]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Pr and Ms. Ad are at $a$ and $b$ respectively on an infinite number line. Mr. Pr wants to meet Ms. Ad.

Mr. Pr can choose to move  $c$ or $d$ units in 1 second. If Mr. Pr moves $c$ units then Ms. Ad will move $d$ units and vice versa. (Both of them always moved in positive x-direction)

You have to determine if Mr. Pr can meet with Ms. Ad after some integral amount of time, given that Mr. Pr chooses optimally. Note that meeting after a fractional amount of time does not count.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains four space separated integers, $a$, $b$, $c$, and $d$.

------ Output: ------
For each test case, output a single line containing "YES" if Mr. Pr meets with Ms. Ad, otherwise "NO".

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ a,b,c,d ≤ 10^{9}$

----- Sample Input 1 ------ 
2
3 4 1 2
10 20 3 7
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
In the first test case, Mr. Pr will move 2 units in the first second and Ms. Ad moves 1 unit simultaneously and they meet. 

In the second test case, it is impossible to meet (fractional time is not allowed).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Every evening Vitalya sets *n* alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer *a**i* — number of minute after midnight in which it rings. Every alarm clock begins ringing at the beginning of the minute and rings during whole minute. 

Vitalya will definitely wake up if during some *m* consecutive minutes at least *k* alarm clocks will begin ringing. Pay attention that Vitalya considers only alarm clocks which begin ringing during given period of time. He doesn't consider alarm clocks which started ringing before given period of time and continues ringing during given period of time.

Vitalya is so tired that he wants to sleep all day long and not to wake up. Find out minimal number of alarm clocks Vitalya should turn off to sleep all next day. Now all alarm clocks are turned on.

Input Specification:
First line contains three integers *n*, *m* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=2·105, 1<=≤<=*m*<=≤<=106) — number of alarm clocks, and conditions of Vitalya's waking up. 

Second line contains sequence of distinct integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=106) in which *a**i* equals minute on which *i*-th alarm clock will ring. Numbers are given in arbitrary order. Vitalya lives in a Berland in which day lasts for 106 minutes.

Output Specification:
Output minimal number of alarm clocks that Vitalya should turn off to sleep all next day long.

Demo Input:
['3 3 2\n3 5 1\n', '5 10 3\n12 8 18 25 1\n', '7 7 2\n7 3 4 1 6 5 2\n', '2 2 2\n1 3\n']

Demo Output:
['1\n', '0\n', '6\n', '0\n']

Note:
In first example Vitalya should turn off first alarm clock which rings at minute 3.

In second example Vitalya shouldn't turn off any alarm clock because there are no interval of 10 consequence minutes in which 3 alarm clocks will ring.

In third example Vitalya should turn off any 6 alarm clocks.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Limak is a grizzly bear who desires power and adoration. He wants to win in upcoming elections and rule over the Bearland.

There are *n* candidates, including Limak. We know how many citizens are going to vote for each candidate. Now *i*-th candidate would get *a**i* votes. Limak is candidate number 1. To win in elections, he must get strictly more votes than any other candidate.

Victory is more important than everything else so Limak decided to cheat. He will steal votes from his opponents by bribing some citizens. To bribe a citizen, Limak must give him or her one candy - citizens are bears and bears like candies. Limak doesn't have many candies and wonders - how many citizens does he have to bribe?

Input Specification:
The first line contains single integer *n* (2<=≤<=*n*<=≤<=100) - number of candidates.

The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=1000) - number of votes for each candidate. Limak is candidate number 1.

Note that after bribing number of votes for some candidate might be zero or might be greater than 1000.

Output Specification:
Print the minimum number of citizens Limak must bribe to have strictly more votes than any other candidate.

Demo Input:
['5\n5 1 11 2 8\n', '4\n1 8 8 8\n', '2\n7 6\n']

Demo Output:
['4\n', '6\n', '0\n']

Note:
In the first sample Limak has 5 votes. One of the ways to achieve victory is to bribe 4 citizens who want to vote for the third candidate. Then numbers of votes would be 9, 1, 7, 2, 8 (Limak would have 9 votes). Alternatively, Limak could steal only 3 votes from the third candidate and 1 vote from the second candidate to get situation 9, 0, 8, 2, 8.

In the second sample Limak will steal 2 votes from each candidate. Situation will be 7, 6, 6, 6.

In the third sample Limak is a winner without bribing any citizen.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.

We will consider an extremely simplified subset of Python with only two types of statements.

Simple statements are written in a single line, one per line. An example of a simple statement is assignment.

For statements are compound statements: they contain one or several other statements. For statement consists of a header written in a separate line which starts with "for" prefix, and loop body. Loop body is a block of statements indented one level further than the header of the loop. Loop body can contain both types of statements. Loop body can't be empty.

You are given a sequence of statements without indentation. Find the number of ways in which the statements can be indented to form a valid Python program.


-----Input-----

The first line contains a single integer N (1 ≤ N ≤ 5000) — the number of commands in the program. N lines of the program follow, each line describing a single command. Each command is either "f" (denoting "for statement") or "s" ("simple statement"). It is guaranteed that the last line is a simple statement.


-----Output-----

Output one line containing an integer - the number of ways the given sequence of statements can be indented modulo 10^9 + 7. 


-----Examples-----
Input
4
s
f
f
s

Output
1

Input
4
f
s
f
s

Output
2



-----Note-----

In the first test case, there is only one way to indent the program: the second for statement must be part of the body of the first one.

simple statement

for statement

    for statement

        simple statement



In the second test case, there are two ways to indent the program: the second for statement can either be part of the first one's body or a separate statement following the first one.

for statement

    simple statement

    for statement

        simple statement



or

for statement

    simple statement

for statement

    simple statement

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer k and n distinct points with integer coordinates on the Euclidean plane, the i-th point has coordinates (x_i, y_i).

Consider a list of all the (n(n - 1))/(2) pairs of points ((x_i, y_i), (x_j, y_j)) (1 ≤ i < j ≤ n). For every such pair, write out the distance from the line through these two points to the origin (0, 0).

Your goal is to calculate the k-th smallest number among these distances.

Input

The first line contains two integers n, k (2 ≤ n ≤ 10^5, 1 ≤ k ≤ (n(n - 1))/(2)).

The i-th of the next n lines contains two integers x_i and y_i (-10^4 ≤ x_i, y_i ≤ 10^4) — the coordinates of the i-th point. It is guaranteed that all given points are pairwise distinct.

Output

You should output one number — the k-th smallest distance from the origin. Your answer is considered correct if its absolute or relative error does not exceed 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Example

Input


4 3
2 1
-2 -1
0 -1
-2 4


Output


0.707106780737

Note

There are 6 pairs of points: 

  * Line 1-2 : distance 0 from the origin 
  * Line 1-3 : distance \frac{√{2}}{2} ≈ 0.707106781 from the origin 
  * Line 1-4 : distance 2 from the origin 
  * Line 2-3 : distance 1 from the origin 
  * Line 2-4 : distance 2 from the origin 
  * Line 3-4 : distance \frac{2}{√{29}} ≈ 0.371390676 from the origin 

The third smallest distance among those is approximately 0.707106781.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Japanese Crosswords Strike Back

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A one-dimensional Japanese crossword can be represented as a binary string of length *x*. An encoding of this crossword is an array *a* of size *n*, where *n* is the number of segments formed completely of 1's, and *a**i* is the length of *i*-th segment. No two segments touch or intersect.

For example: 
 -  If *x*<==<=6 and the crossword is 111011, then its encoding is an array {3,<=2}; -  If *x*<==<=8 and the crossword is 01101010, then its encoding is an array {2,<=1,<=1}; -  If *x*<==<=5 and the crossword is 11111, then its encoding is an array {5}; -  If *x*<==<=5 and the crossword is 00000, then its encoding is an empty array. 
Mishka wants to create a new one-dimensional Japanese crossword. He has already picked the length and the encoding for this crossword. And now he needs to check if there is exactly one crossword such that its length and encoding are equal to the length and encoding he picked. Help him to check it!

Input Specification:
The first line contains two integer numbers *n* and *x* (1<=≤<=*n*<=≤<=100000, 1<=≤<=*x*<=≤<=109) — the number of elements in the encoding and the length of the crossword Mishka picked.

The second line contains *n* integer numbers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=10000) — the encoding.

Output Specification:
Print YES if there exists exaclty one crossword with chosen length and encoding. Otherwise, print NO.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Good old Marko came across a new feature on his mobile phone – T9 input! His phone has a keyboard consisting of numbers looking like this:

1

2

3 

abc

def

4

5

6

ghi

jkl

mno

7

8

9

pqrs

tuv

wxyz

In order to input a word using this keyboard, one needs to press a key multiple times for the required letter. More specifically, if the required letter is the first letter mapped to the key, one key press is needed, if it’s the second, two key presses are needed and so on. For instance, if we want to input the word “giht”, we will press the following keys: g-4 i-444 h-44 t-8. The new possibility Marko discovered enables you to input text more easily because you don’t need several presses per letter anymore, just one. The software will try to figure out what word from the dictionary you are trying to input.

Marko is quite sceptical of new technologies (at least new for him) and he is afraid that errors will be frequent. That is the reason why he decided to test his hypothesis that the errors are frequent. Marko knows by heart the whole dictionary in the mobile phone. The dictionary consists of $N$ words consisting of lowercase letters from the English alphabet, the total length of the word not exceeding $1000000$ characters. He will give an array of key presses $S$, of total length at most $1000$, and wants to know how many words from the dictionary can be mapped to the given array of key presses if the T9 input feature is used.

-----Input-----
The first line of input contains the integer $N$, the number of words in the dictionary. ($1 \leq N \leq 1000$). Each of the following $N$ lines contains a single word. The last line of input contains the string $S$ ($1 \leq |S| \leq 1000$) consisting of digits $2$–$9$.

-----Output-----
The first and only line of output must contain the number of words from the dictionary possible to construct from the letters on the keys determined by the string $S$.

-----Examples-----
Sample Input 1:
3
tomo
mono
dak
6666
Sample Output 1:
1

Sample Input 2:
2
ja
la
52
Sample Output 2:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Darshak (Dark) was learning about numerals in words and he came across representation of "6743294" as shown below
.tg  {border-collapse:collapse;border-spacing:0;}
.tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}
.tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}

Ten Lakhs
Lakhs
Ten-Thousands
Thousands
Hundreds
Tens
Units
6
7
4
3
2
9
4
This can be extended to very high numbers like crores, ten crores and so on...

He learned two concepts.

1) Face Value:

The Face value of a digit in a numeral is its own value, at whatever place it may be.
eg: Face Value of 6 is 6 (as per above example) let say it is stored in 'f'

2) Place Value:

In a given numeral, 

Place value of unit digit = (unit digit * 1)

Place value of tens digit = (tens digit *10)

and so on,...

eg: place value of '4' at unit place is  4 * 1 = 4.

As always Dark is eager and wants you to find the place value of given digit and count the number of zero's present in it say let it be 'p' 

But, if the value of p comes out to be even number then we need to print the fth prime number or if it comes out to be odd then print the pth prime number. 

Note: Prime numbers start from 2.

Input:

First line contains t number of test case. Each next line contains one numeral say 'n' , 'm' the digit whose place value is to be obtained and 'x' position of the digit from units place towards the higher places.

Note: 
In an example, "6343"  if x=2 then it represents the "thousandth place" and if x=1 then "units place".we have considered digit as 3

Output:

Print the prime number as explained above.

Constraints:

1 ≤ t ≤ 1000
0 ≤ m ≤ 9 
1 ≤ x ≤ 100
1 ≤ n ≤ 10^101

Note:

1) Face value of zero is zero therefore the fth prime number i.e 0th prime number can be considered as 1.

2) Prime number starts from 2.

3)  No leading zeroes in the numeral.

Author : Darshak Mehta

SAMPLE INPUT
3
1005 0 2
7347 3 1
7777 7 4

SAMPLE OUTPUT
1
5
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fennec is fighting with N monsters.
The health of the i-th monster is H_i.
Fennec can do the following two actions:
 - Attack: Fennec chooses one monster. That monster's health will decrease by 1.
 - Special Move: Fennec chooses one monster. That monster's health will become 0.
There is no way other than Attack and Special Move to decrease the monsters' health.
Fennec wins when all the monsters' healths become 0 or below.
Find the minimum number of times Fennec needs to do Attack (not counting Special Move) before winning when she can use Special Move at most K times.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - 0 \leq K \leq 2 \times 10^5
 - 1 \leq H_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
H_1 ... H_N

-----Output-----
Print the minimum number of times Fennec needs to do Attack (not counting Special Move) before winning.

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

-----Sample Output-----
5

By using Special Move on the third monster, and doing Attack four times on the first monster and once on the second monster, Fennec can win with five Attacks.

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