vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As a treat, I'll let you read part of the script from a classic 'I'm Alan Partridge episode:
```
Lynn: Alan, there’s that teacher chap.
Alan: Michael, if he hits me, will you hit him first?
Michael: No, he’s a customer. I cannot hit customers. I’ve been told. I’ll go and get some stock.
Alan: Yeah, chicken stock.
Phil: Hello Alan.
Alan: Lynn, hand me an apple pie. And remove yourself from the theatre of conflict.
Lynn: What do you mean?
Alan: Go and stand by the yakults. The temperature inside this apple turnover is 1,000 degrees. If I squeeze it, a jet of molten Bramley apple is going to squirt out. Could go your way, could go mine. Either way, one of us is going down.
```

Alan is known for referring to the temperature of the apple turnover as 'Hotter than the sun!'. According to  space.com the temperature of the sun's corona is 2,000,000 degrees C, but we will ignore the science for now. 

Your job is simple, if (x) squared is more than 1000, return  'It's hotter than the sun!!', else, return 'Help yourself to a honeycomb Yorkie for the glovebox.'.

X will be either a number or a string. Both are valid. 

Other katas in this series:
Alan Partridge I - Partridge Watch
Alan Partridge III - London

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N barbecue restaurants along a street.
The restaurants are numbered 1 through N from west to east, and the distance between restaurant i and restaurant i+1 is A_i.
Joisino has M tickets, numbered 1 through M.
Every barbecue restaurant offers barbecue meals in exchange for these tickets.
Restaurant i offers a meal of deliciousness B_{i,j} in exchange for ticket j.
Each ticket can only be used once, but any number of tickets can be used at a restaurant.
Joisino wants to have M barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location.
Her eventual happiness is calculated by the following formula: "(The total deliciousness of the meals eaten) - (The total distance traveled)".
Find her maximum possible eventual happiness.

-----Constraints-----
 - All input values are integers.
 - 2≤N≤5×10^3
 - 1≤M≤200
 - 1≤A_i≤10^9
 - 1≤B_{i,j}≤10^9

-----Input-----
The input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_{N-1}
B_{1,1} B_{1,2} ... B_{1,M}
B_{2,1} B_{2,2} ... B_{2,M}
:
B_{N,1} B_{N,2} ... B_{N,M}

-----Output-----
Print Joisino's maximum possible eventual happiness.

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

-----Sample Output-----
11

The eventual happiness can be maximized by the following strategy: start from restaurant 1 and use tickets 1 and 3, then move to restaurant 2 and use tickets 2 and 4.

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

As some of you know, cubism is a trend in art, where the problem of constructing volumetrical shape on a plane with a combination of three-dimensional geometric shapes comes to the fore. 

A famous sculptor Cicasso, whose self-portrait you can contemplate, hates cubism. He is more impressed by the idea to transmit two-dimensional objects through three-dimensional objects by using his magnificent sculptures. And his new project is connected with this. Cicasso wants to make a coat for the haters of anticubism. To do this, he wants to create a sculpture depicting a well-known geometric primitive — convex polygon.

Cicasso prepared for this a few blanks, which are rods with integer lengths, and now he wants to bring them together. The i-th rod is a segment of length l_{i}.

The sculptor plans to make a convex polygon with a nonzero area, using all rods he has as its sides. Each rod should be used as a side to its full length. It is forbidden to cut, break or bend rods. However, two sides may form a straight angle $180^{\circ}$.

Cicasso knows that it is impossible to make a convex polygon with a nonzero area out of the rods with the lengths which he had chosen. Cicasso does not want to leave the unused rods, so the sculptor decides to make another rod-blank with an integer length so that his problem is solvable. Of course, he wants to make it as short as possible, because the materials are expensive, and it is improper deed to spend money for nothing. 

Help sculptor! 


-----Input-----

The first line contains an integer n (3 ≤ n ≤ 10^5) — a number of rod-blanks.

The second line contains n integers l_{i} (1 ≤ l_{i} ≤ 10^9) — lengths of rods, which Cicasso already has. It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has.


-----Output-----

Print the only integer z — the minimum length of the rod, so that after adding it it can be possible to construct convex polygon with (n + 1) vertices and nonzero area from all of the rods.


-----Examples-----
Input
3
1 2 1

Output
1

Input
5
20 4 3 2 1

Output
11



-----Note-----

In the first example triangle with sides {1 + 1 = 2, 2, 1} can be formed from a set of lengths {1, 1, 1, 2}. 

In the second example you can make a triangle with lengths {20, 11, 4 + 3 + 2 + 1 = 10}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The mysterious pathogen of ACM Nation multiplies mysteriously each day. Maria was able to

decipher the pattern but unable to completely solve the problem. The study of this equation will 

help in combating their growth. 

The summation is - 

S = a + aa + aa*a + ...... a^n times

Where a is the number of pathogen on the first day and S on the nth day.

Input : a and n are taken as input from the user.   First line will contain a,followed by n. 

Output: a single integer depicting the sum

Sample Input:
2
4

Sample Output:
30

SAMPLE INPUT
2
4

SAMPLE OUTPUT
30

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: First Digit Law

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
In the probability theory the following paradox called Benford's law is known: "In many lists of random numbers taken from real sources, numbers starting with digit 1 occur much more often than numbers starting with any other digit" (that's the simplest form of the law).

Having read about it on Codeforces, the Hedgehog got intrigued by the statement and wishes to thoroughly explore it. He finds the following similar problem interesting in particular: there are *N* random variables, the *i*-th of which can take any integer value from some segment [*L**i*;*R**i*] (all numbers from this segment are equiprobable). It means that the value of the *i*-th quantity can be equal to any integer number from a given interval [*L**i*;*R**i*] with probability 1<=/<=(*R**i*<=-<=*L**i*<=+<=1).

The Hedgehog wants to know the probability of the event that the first digits of at least *K*% of those values will be equal to one. In other words, let us consider some set of fixed values of these random variables and leave only the first digit (the MSD — most significant digit) of each value. Then let's count how many times the digit 1 is encountered and if it is encountered in at least *K* per cent of those *N* values, than such set of values will be called a good one. You have to find the probability that a set of values of the given random variables will be a good one.

Input Specification:
The first line contains number *N* which is the number of random variables (1<=≤<=*N*<=≤<=1000). Then follow *N* lines containing pairs of numbers *L**i*,<=*R**i*, each of whom is a description of a random variable. It is guaranteed that 1<=≤<=*L**i*<=≤<=*R**i*<=≤<=1018.

The last line contains an integer *K* (0<=≤<=*K*<=≤<=100).

All the numbers in the input file are integers.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output Specification:
Print the required probability. Print the fractional number with such a precision that the relative or absolute error of the result won't exceed 10<=-<=9.

Demo Input:
['1\n1 2\n50\n', '2\n1 2\n9 11\n50\n']

Demo Output:
['0.500000000000000', '0.833333333333333']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have 2N pots. The market price of the i-th pot (1 ≤ i ≤ 2N) is p_i yen (the currency of Japan).

Now, you and Lunlun the dachshund will alternately take one pot. You will go first, and we will continue until all the pots are taken by you or Lunlun. Since Lunlun does not know the market prices of the pots, she will always choose a pot randomly from the remaining pots with equal probability. You know this behavior of Lunlun, and the market prices of the pots.

Let the sum of the market prices of the pots you take be S yen. Your objective is to maximize the expected value of S. Find the expected value of S when the optimal strategy is adopted.

Constraints

* 1 ≤ N ≤ 10^5
* 1 ≤ p_i ≤ 2 × 10^5
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
p_1
:
p_{2N}


Output

Print the expected value of S when the strategy to maximize the expected value of S is adopted. The output is considered correct if its absolute or relative error from the judge's output is at most 10^{-9}.

Examples

Input

1
150000
108


Output

150000.0


Input

2
50000
50000
100000
100000


Output

183333.3333333333

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Fair Nut found a string $s$. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences $p_1, p_2, \ldots, p_k$, such that:   For each $i$ ($1 \leq i \leq k$), $s_{p_i} =$ 'a'.  For each $i$ ($1 \leq i < k$), there is such $j$ that $p_i < j < p_{i + 1}$ and $s_j =$ 'b'. 

The Nut is upset because he doesn't know how to find the number. Help him.

This number should be calculated modulo $10^9 + 7$.


-----Input-----

The first line contains the string $s$ ($1 \leq |s| \leq 10^5$) consisting of lowercase Latin letters.


-----Output-----

In a single line print the answer to the problem — the number of such sequences $p_1, p_2, \ldots, p_k$ modulo $10^9 + 7$.


-----Examples-----
Input
abbaa

Output
5
Input
baaaa

Output
4
Input
agaa

Output
3


-----Note-----

In the first example, there are $5$ possible sequences. $[1]$, $[4]$, $[5]$, $[1, 4]$, $[1, 5]$.

In the second example, there are $4$ possible sequences. $[2]$, $[3]$, $[4]$, $[5]$.

In the third example, there are $3$ possible sequences. $[1]$, $[3]$, $[4]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the easy version of the problem. The difference is constraints on the number of wise men and the time limit. You can make hacks only if all versions of this task are solved.

$n$ wise men live in a beautiful city. Some of them know each other.

For each of the $n!$ possible permutations $p_1, p_2, \ldots, p_n$ of the wise men, let's generate a binary string of length $n-1$: for each $1 \leq i < n$ set $s_i=1$ if $p_i$ and $p_{i+1}$ know each other, and $s_i=0$ otherwise. 

For all possible $2^{n-1}$ binary strings, find the number of permutations that produce this binary string.


-----Input-----

The first line of input contains one integer $n$ ($2 \leq n \leq 14)$  — the number of wise men in the city.

The next $n$ lines contain a binary string of length $n$ each, such that the $j$-th character of the $i$-th string is equal to '1' if wise man $i$ knows wise man $j$, and equals '0' otherwise.

It is guaranteed that if the $i$-th man knows the $j$-th man, then the $j$-th man knows $i$-th man and no man knows himself.


-----Output-----

Print $2^{n-1}$ space-separated integers. For each $0 \leq x < 2^{n-1}$:

  Let's consider a string $s$ of length $n-1$, such that $s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$ for all $1 \leq i \leq n - 1$.  The $(x+1)$-th number should be equal to the required answer for $s$. 


-----Examples-----
Input
3
011
101
110

Output
0 0 0 6 

Input
4
0101
1000
0001
1010

Output
2 2 6 2 2 6 2 2 



-----Note-----

In the first test, each wise man knows each other, so every permutation will produce the string $11$.

In the second test:

  If $p = \{1, 2, 3, 4\}$, the produced string is $101$, because wise men $1$ and $2$ know each other, $2$ and $3$ don't know each other, and $3$ and $4$ know each other;  If $p = \{4, 1, 2, 3\}$, the produced string is $110$, because wise men $1$ and $4$ know each other, $1$ and $2$ know each other and $2$, and $3$ don't know each other;  If $p = \{1, 3, 2, 4\}$, the produced string is $000$, because wise men $1$ and $3$ don't know each other, $3$ and $2$ don't know each other, and $2$ and $4$ don't know each other.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The MarkiT online virtual market startup wants to organize its grand opening in NIT Patna.
but they want maximum crowd for their inauguration. So the manager told  this  to Praveen a student in NITP who suggested them:
The first-year students come to campus  every x hour,
Second-year students come to campus every y hour,
Third-year students come to campus every z hour and 
Fourth-year is very busy so they don't come regularly.
So Praveen being very clever told him the no of times in n days he can have an audience of all year student (1st,2nd & 3rd) at max. So can you code what Praveen has done?

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a 2 line of input, first line contain one  integers $N$ (No of Days). 
-Next line contain 3 space separated integer the  value of x y z

-----Output:-----
For each testcase, output in a single line answer the no of times audience consists of all year.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^8$
- $1 \leq x,y,z \leq 10^5$

-----Sample Input:-----
1
10
8 10 6

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

-----EXPLANATION:-----
First favourable condition will come on 5th day and Second on 10th day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Diana is planning to make a very long journey. Her journey consists of $N$ bus routes, numbered from $1 to N$ in the order she must take them. The buses themselves are very fast but do not run often. The $i-th$ bus route only runs every $Xi$ days.

More specifically, she can only take the $i-th$ bus on day $Xi, 2Xi, 3Xi$, and so on. Since the buses are very fast, she can take multiple buses on the same day.

Diana must finish her journey by day D, but she would like to start the journey as late as possible. What is the latest day she could take the first bus, and still finish her journey by day $D$?
It is guaranteed that it is possible for Diana to finish her journey by day $D$.  

-----Input:-----
The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the two integers N and D. Then, another line follows containing $N$ integers, the $i-th$ one is $Xi$.

-----Output:-----
For each test case, output one line containing an integer $Y$, where $Y$ is the latest day she could take the first bus, and still finish her journey by day $D$.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq Xi \leq D.$
- $1 \leq N \leq 1000.$
It is guaranteed that it is possible for Diana to finish her journey by day $D$.

-----Sample Input:-----
3

3 10

3 7 2

4 100

11 10 5 50

1 1

1  

-----Sample Output:-----
6  

99

1  

-----EXPLANATION:-----
In Sample $Case 1$, there are $N = 3$ bus routes and Bucket must arrive by day $D = 10$. She could:
- Take the 1st bus on day 6 $(X1 = 3)$,
- Take the 2nd bus on day 7 $(X2 = 7)$ and
- Take the 3rd bus on day 8 $(X3 = 2)$.  
In Sample $Case 2$, there are $N = 4$ bus routes and Bucket must arrive by day $D = 100$. She could:
- Take the 1st bus on day 99 $(X1 = 11)$,
- Take the 2nd bus on day 100$ (X2 = 10)$,
- Take the 3rd bus on day 100 $(X3 = 5)$ and
- Take the 4th bus on day 100 $(X4 = 50)$,  
In Sample Case 3, there is $N = 1$ bus route, and Bucket must arrive by day $D = 1$. She could:
- Take the 1st bus on day 1 $(X1 = 1)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Values You Can Make

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pari wants to buy an expensive chocolate from Arya. She has *n* coins, the value of the *i*-th coin is *c**i*. The price of the chocolate is *k*, so Pari will take a subset of her coins with sum equal to *k* and give it to Arya.

Looking at her coins, a question came to her mind: after giving the coins to Arya, what values does Arya can make with them? She is jealous and she doesn't want Arya to make a lot of values. So she wants to know all the values *x*, such that Arya will be able to make *x* using some subset of coins with the sum *k*.

Formally, Pari wants to know the values *x* such that there exists a subset of coins with the sum *k* such that some subset of this subset has the sum *x*, i.e. there is exists some way to pay for the chocolate, such that Arya will be able to make the sum *x* using these coins.

Input Specification:
The first line contains two integers *n* and *k* (1<=<=≤<=<=*n*,<=*k*<=<=≤<=<=500) — the number of coins and the price of the chocolate, respectively.

Next line will contain *n* integers *c*1,<=*c*2,<=...,<=*c**n* (1<=≤<=*c**i*<=≤<=500) — the values of Pari's coins.

It's guaranteed that one can make value *k* using these coins.

Output Specification:
First line of the output must contain a single integer *q*— the number of suitable values *x*. Then print *q* integers in ascending order — the values that Arya can make for some subset of coins of Pari that pays for the chocolate.

Demo Input:
['6 18\n5 6 1 10 12 2\n', '3 50\n25 25 50\n']

Demo Output:
['16\n0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 \n', '3\n0 25 50 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu has an array A consisting of N positive integers. He would like to perform following operation on array.

Pick some two elements a, b in the array (a could be same as b, but their corresponding indices in the array should not be same).
Remove both the elements a and b and instead add a number x such that x lies between min(a, b) and max(a, b), both inclusive, (i.e. min(a, b) ≤ x ≤ max(a, b)).


Now, as you know after applying the above operation N - 1 times, Devu will end up with a single number in the array. He is wondering whether it is possible to do the operations in such a way that he ends up a number t.


He asks your help in answering Q such queries, each of them will contain an integer t and you have to tell whether it is possible to end up t.


Input
There is only one test case per test file.
First line of the input contains two space separated integers N, Q denoting number of elements in A and number of queries for which Devu asks your help, respectively
Second line contains N space separated integers denoting the content of array A.
Each of the next Q lines, will contain a single integer t corresponding to the query.

Output
Output Q lines, each containing "Yes" or "No" (both without quotes) corresponding to the answer of corresponding query.

Constraints

1 ≤ N, Q ≤ 10^5
0 ≤ t ≤ 10^9


Example
Input 1:
1 2
1
1
2

Output:
Yes
No

Input 2:
2 4
1 3
1
2
3
4

Output:
Yes
Yes
Yes
No

Explanation
In the first example, Devu can't apply any operation. So the final element in the array will be 1 itself.

In the second example,
Devu can replace 1 and 3 with any of the numbers among 1, 2, 3. Hence final element of the array could be 1, 2 or 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The city park of IT City contains n east to west paths and n north to south paths. Each east to west path crosses each north to south path, so there are n^2 intersections.

The city funded purchase of five benches. To make it seems that there are many benches it was decided to place them on as many paths as possible. Obviously this requirement is satisfied by the following scheme: each bench is placed on a cross of paths and each path contains not more than one bench.

Help the park administration count the number of ways to place the benches.


-----Input-----

The only line of the input contains one integer n (5 ≤ n ≤ 100) — the number of east to west paths and north to south paths.


-----Output-----

Output one integer — the number of ways to place the benches.


-----Examples-----
Input
5

Output
120

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have reached the final level of Hunger Games and as usual a tough task awaits you.
You have a circular dining table and N hungery animals.You need to place them on the table.Each animal has a hunger value.
You can place the animals in any order on the circular table.Once you place them you need to calculate the Danger value of your arrangement.
The danger value of the arrangement is the maximum difference of hunger values of all the adjacent seated animals.You need to keep this danger value as low as possible.

Input:
The first line contains N integers.
The second line contains the hunger values of N animals.  

Output:
Print the minimum possible danger value.  

Constraints:
3 ≤ N ≤ 1000
1 ≤ Hunger Value ≤ 1000  

SAMPLE INPUT
4
5 10 6 8

SAMPLE OUTPUT
4

Explanation

The optimal arrangement is :

           5

    /             \
 6                  8
     \           /
          10

The adjacent pair values are 1 for(6-5),3 for(8-5),4 for(10-6),2 for(10-8).Since danger value is the maximum value so it's 4.

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