vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In code world all genders are considered equal ( It means their is nothing like male or female). Now their are N distinct  persons living in this hypothetical world. Each person can pair up with any other person or can even  remain single. One day Vbhu planned to visit code world. Being a maths guy , he always try to be mathematical. So he started counting the ways in which N persons living in code world can make pairs or  remain single. A single person can make pair with at most one other person.Seeing that N can be large , Vibhu ask you for help. Now being a great programmer you need to help Vbhu count the number of ways in which N persons living in code world can make pairs or remain single. 

Note : Its not necessary that everyone is required to make pair with someone.  Person can remain single also.

Input Format :  First line contain number of test cases T. Then next T lines contain a single integer N , denoting the number of persons living in code world.

Output Format : You need to print the number of ways in which N different persons can make their pairs or stay single. As answer can be large so print it modulo 10^9+7.

Constraints :
1 ≤ T ≤10^5
1 ≤ N ≤10^6
Warning: Large Input/Output data, be careful with certain languages

SAMPLE INPUT
2
2
3


SAMPLE OUTPUT
2
4


Explanation

In first test case , For N=2 answer will be 2. Possible ways are :
    {1},{2} (It means Person 1 and Person 2 are single)
    {1,2}  (It means Person 1 and Person 2 had formed a pair)

For second test case , For N=3 , answer will be 4. Possible ways are :
    {1},{2},{3} (It means all three Persons are single)
    {1,2},{3} (It means Person 1 and Person 2 had formed a pair and Person 3 is single)
    {1},{2,3} (It means Person 2 and Person 3 had formed a pair and Person 1 is single)
    {1,3},{2} (It means Person 1 and Person 3 had formed a pair and Person 2 is single)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have $N$ items that you want to put them into a knapsack of capacity $W$. Item $i$ ($1 \le i \le N$) has weight $w_i$ and value $v_i$ for the weight.

When you put some items into the knapsack, the following conditions must be satisfied:

* The total value of the items is as large as possible.
* The total weight of the selected items is at most $W$.
* You can break some items if you want. If you put $w'$($0 \le w' \le w_i$) of item $i$, its value becomes $\displaystyle v_i \times \frac{w'}{w_i}.$



Find the maximum total value of items in the knapsack.

Constraints

* $1 \le N \le 10^5$
* $1 \le W \le 10^9$
* $1 \le v_i \le 10^9 (1 \le i \le N)$
* $1 \le w_i \le 10^9 (1 \le i \le N)$

Input


$N$ $W$
$v_1$ $w_1$
$v_2$ $w_2$
:
$v_N$ $w_N$


The first line consists of the integers $N$ and $W$. In the following $N$ lines, the value and weight of the $i$-th item are given.

Output

Print the maximum total value of the items in a line. The output must not contain an error greater than $10^{-6}$.

Examples

Input

3 50
60 10
100 20
120 30


Output

240


Input

3 50
60 13
100 23
120 33


Output

210.90909091


Input

1 100
100000 100000


Output

100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a certain integer, ```n, n > 0```. You have to search the partition or partitions, of n, with maximum product value.

Let'see the case for ```n = 8```.
```
Partition                 Product
[8]                          8
[7, 1]                       7
[6, 2]                      12
[6, 1, 1]                    6
[5, 3]                      15
[5, 2, 1]                   10
[5, 1, 1, 1]                 5
[4, 4]                      16
[4, 3, 1]                   12
[4, 2, 2]                   16
[4, 2, 1, 1]                 8
[4, 1, 1, 1, 1]              4
[3, 3, 2]                   18   <---- partition with maximum product value
[3, 3, 1, 1]                 9
[3, 2, 2, 1]                12
[3, 2, 1, 1, 1]              6
[3, 1, 1, 1, 1, 1]           3
[2, 2, 2, 2]                16
[2, 2, 2, 1, 1]              8
[2, 2, 1, 1, 1, 1]           4
[2, 1, 1, 1, 1, 1, 1]        2
[1, 1, 1, 1, 1, 1, 1, 1]     1
```
So our needed function will work in that way for Python and Ruby:
```
find_part_max_prod(8) == [[3, 3, 2], 18]
```
For javascript
```
findPartMaxProd(8) --> [[3, 3, 2], 18]
```
If there are more than one partition with maximum product value, the function should output the patitions in a length sorted way.
Python and Ruby
```
find_part_max_prod(10) == [[4, 3, 3], [3, 3, 2, 2], 36]
```
Javascript
```
findPartMaxProd(10) --> [[4, 3, 3], [3, 3, 2, 2], 36]
```
Enjoy it!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Scrooge, a very busy man, decided to count the time he wastes on all sorts of useless stuff to evaluate the lost profit. He has already counted the time he wastes sleeping and eating. And now Mr. Scrooge wants to count the time he has wasted signing papers.

Mr. Scrooge's signature can be represented as a polyline A1A2... An. Scrooge signs like that: first it places a pen at the point A1, then draws a segment from point A1 to point A2, then he draws a segment from point A2 to point A3 and so on to point An, where he stops signing and takes the pen off the paper. At that the resulting line can intersect with itself and partially repeat itself but Scrooge pays no attention to it and never changes his signing style. As Scrooge makes the signature, he never takes the pen off the paper and his writing speed is constant — 50 millimeters per second.

Scrooge signed exactly k papers throughout his life and all those signatures look the same.

Find the total time Scrooge wasted signing the papers.

Input

The first line contains two integers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ 1000). Each of the following n lines contains the coordinates of the polyline's endpoints. The i-th one contains coordinates of the point Ai — integers xi and yi, separated by a space.

All points Ai are different. The absolute value of all coordinates does not exceed 20. The coordinates are measured in millimeters.

Output

Print one real number — the total time Scrooges wastes on signing the papers in seconds. The absolute or relative error should not exceed 10 - 6.

Examples

Input

2 1
0 0
10 0


Output

0.200000000

Input

5 10
3 1
-5 6
-2 -1
3 2
10 0


Output

6.032163204

Input

6 10
5 0
4 0
6 0
3 0
7 0
2 0


Output

3.000000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The map of Berland is a rectangle of the size *n*<=×<=*m*, which consists of cells of size 1<=×<=1. Each cell is either land or water. The map is surrounded by the ocean. 

Lakes are the maximal regions of water cells, connected by sides, which are not connected with the ocean. Formally, lake is a set of water cells, such that it's possible to get from any cell of the set to any other without leaving the set and moving only to cells adjacent by the side, none of them is located on the border of the rectangle, and it's impossible to add one more water cell to the set such that it will be connected with any other cell.

You task is to fill up with the earth the minimum number of water cells so that there will be exactly *k* lakes in Berland. Note that the initial number of lakes on the map is not less than *k*.

Input Specification:
The first line of the input contains three integers *n*, *m* and *k* (1<=≤<=*n*,<=*m*<=≤<=50, 0<=≤<=*k*<=≤<=50) — the sizes of the map and the number of lakes which should be left on the map.

The next *n* lines contain *m* characters each — the description of the map. Each of the characters is either '.' (it means that the corresponding cell is water) or '*' (it means that the corresponding cell is land).

It is guaranteed that the map contain at least *k* lakes.

Output Specification:
In the first line print the minimum number of cells which should be transformed from water to land. 

In the next *n* lines print *m* symbols — the map after the changes. The format must strictly follow the format of the map in the input data (there is no need to print the size of the map). If there are several answers, print any of them. 

It is guaranteed that the answer exists on the given data.

Demo Input:
['5 4 1\n****\n*..*\n****\n**.*\n..**\n', '3 3 0\n***\n*.*\n***\n']

Demo Output:
['1\n****\n*..*\n****\n****\n..**\n', '1\n***\n***\n***\n']

Note:
In the first example there are only two lakes — the first consists of the cells (2, 2) and (2, 3), the second consists of the cell (4, 3). It is profitable to cover the second lake because it is smaller. Pay attention that the area of water in the lower left corner is not a lake because this area share a border with the ocean.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's your birthday today, right? If it is, then we wish you Happy Birthday and good luck in the contest. But, even if it is not, you have to be ready to give candies to your friend when this day comes!

You have N candies to distribute and you decide to give them to anyone who shows up. Because this is your day, you invented your own method of distributing all these candies . The process is the following:

Initially, there are N candies placed in one pile. While there are any candies left, a person shows up and do the following:
Picks up the first pile with candies, let's call this pile P.
If P has one or two candies, he takes all the candies from P. Otherwise, he takes just one candy, divide the rest into some number of piles, at least 2, of equal sizes and put them in front the other piles.

Because at HackerEarth we like math, we are interested how many different such processes are there. We consider two processes different if and only if one distributes candies to different number of people than the other or both distribute candies to the same number of people and there exists a person who decides to distribute candies differently in them. You have to return the number of different such processes modulo M = 10^9 + 7.

Input format:

In the first and only line there is one integer N.

Output format:

In one line output a single integer - the answer to the problem modulo M = 10^9 + 7.

Constraints:

1 ≤ N ≤ 10^12

SAMPLE INPUT
5

SAMPLE OUTPUT
2

Explanation

There are 5 candies initially. The first person after taking one candy for himself can divide the other 4 candies in two ways: 
into 4 piles with 1 candy on each of them 
into 2 piles with 2 candies. 

In the first case, 4 people will show up and each of them will take one candy for himself. 
In the second case, 2 people will show up and each of the will take 2 candies for himself.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has many friends, but his best friend is Hemant. They both love to watch anime.
In fact, their weekends are meant for that only. Also, Hemant is highly into games, of which Chef is unaware. Hemant once gave a game to Chef and asked him to determine the winner of the game. Since the Chef is busy, and you are also his friend, he asked you to help him.
The Game is played between two players, $A$ and $B$. There are $N$ marbles. $A$ and $B$ plays alternately, and $A$ goes first. Each player can choose $1$ marble or $even$ number of marbles in his turn. The player who is not able to choose any marbles loses the game.

-----Input:-----
- The first line consists of a single integer $T$ denoting the number of test cases.
- The Second line contains an integers $N$, denoting the number of marbles.

-----Output:-----
For each test case, print the name of the player who loses the game.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^9$

-----Sample Input:-----
3
1 
3
7 

-----Sample Output:-----
B
A
B

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a weighted tree consisting of $n$ vertices. Recall that a tree is a connected graph without cycles. Vertices $u_i$ and $v_i$ are connected by an edge with weight $w_i$.

You are given $m$ queries. The $i$-th query is given as an integer $q_i$. In this query you need to calculate the number of pairs of vertices $(u, v)$ ($u < v$) such that the maximum weight of an edge on a simple path between $u$ and $v$ doesn't exceed $q_i$.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of vertices in the tree and the number of queries.

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by three integers $u_i$, $v_i$ and $w_i$ — the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) and the weight of the edge ($1 \le w_i \le 2 \cdot 10^5$). It is guaranteed that the given edges form a tree.

The last line of the input contains $m$ integers $q_1, q_2, \dots, q_m$ ($1 \le q_i \le 2 \cdot 10^5$), where $q_i$ is the maximum weight of an edge in the $i$-th query.


-----Output-----

Print $m$ integers — the answers to the queries. The $i$-th value should be equal to the number of pairs of vertices $(u, v)$ ($u < v$) such that the maximum weight of an edge on a simple path between $u$ and $v$ doesn't exceed $q_i$.

Queries are numbered from $1$ to $m$ in the order of the input.


-----Examples-----
Input
7 5
1 2 1
3 2 3
2 4 1
4 5 2
5 7 4
3 6 2
5 2 3 4 1

Output
21 7 15 21 3 

Input
1 2
1 2

Output
0 0 

Input
3 3
1 2 1
2 3 2
1 3 2

Output
1 3 3 



-----Note-----

The picture shows the tree from the first example: [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of words followed by two words, the task to find the minimum distance between the given two words in the list of words
Example 1:
Input:
S = { "the", "quick", "brown", "fox", 
     "quick"}
word1 = "the"
word2 = "fox"
Output: 3
Explanation: Minimum distance between the 
words "the" and "fox" is 3
Example 2:
Input:
S = {"geeks", "for", "geeks", "contribute", 
     "practice"}
word1 = "geeks"
word2 = "practice"
Output: 2
Explanation: Minimum distance between the
words "geeks" and "practice" is 2
Your Task:  
You don't need to read input or print anything. Your task is to complete the function 
shortestDistance() which list of words, two strings as inputs and returns the minimum distance between two words
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
Sum of lengths of words ≤ 10^{5}
Note: word1 and word2 are both in the list.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Optimal Point on a Line

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given *n* points on a line with their coordinates *x**i*. Find the point *x* so the sum of distances to the given points is minimal.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=3·105) — the number of points on the line.

The second line contains *n* integers *x**i* (<=-<=109<=≤<=*x**i*<=≤<=109) — the coordinates of the given *n* points.

Output Specification:
Print the only integer *x* — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer.

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

Demo Output:
['2\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got a 5<=×<=5 matrix, consisting of 24 zeroes and a single number one. Let's index the matrix rows by numbers from 1 to 5 from top to bottom, let's index the matrix columns by numbers from 1 to 5 from left to right. In one move, you are allowed to apply one of the two following transformations to the matrix:
 1.  Swap two neighboring matrix rows, that is, rows with indexes *i* and *i*<=+<=1 for some integer *i* (1<=≤<=*i*<=&lt;<=5). 1.  Swap two neighboring matrix columns, that is, columns with indexes *j* and *j*<=+<=1 for some integer *j* (1<=≤<=*j*<=&lt;<=5). 
You think that a matrix looks beautiful, if the single number one of the matrix is located in its middle (in the cell that is on the intersection of the third row and the third column). Count the minimum number of moves needed to make the matrix beautiful.

Input Specification:
The input consists of five lines, each line contains five integers: the *j*-th integer in the *i*-th line of the input represents the element of the matrix that is located on the intersection of the *i*-th row and the *j*-th column. It is guaranteed that the matrix consists of 24 zeroes and a single number one.

Output Specification:
Print a single integer — the minimum number of moves needed to make the matrix beautiful.

Demo Input:
['0 0 0 0 0\n0 0 0 0 1\n0 0 0 0 0\n0 0 0 0 0\n0 0 0 0 0\n', '0 0 0 0 0\n0 0 0 0 0\n0 1 0 0 0\n0 0 0 0 0\n0 0 0 0 0\n']

Demo Output:
['3\n', '1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Make your strings more nerdy: Replace all 'a'/'A' with 4, 'e'/'E' with 3 and 'l' with 1
e.g. "Fundamentals" --> "Fund4m3nt41s"


```if:csharp
Documentation:
Kata.Nerdify Method (String)

Nerdifies a string. Returns a copy of the original string with 'a'/'A' characters replaced with '4', 'e'/'E' characters replaced with '3', and 'l' characters replaced with '1'.

Syntax


public
static
string Nerdify(
string str
    )
  



Parameters

str

Type: System.String
The string to be nerdified.

Return Value

Type: System.String
  The nerdified string.


Exceptions



Exception
Condition

ArgumentNullException
str is null.



```

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

In English we often use "neutral vowel sounds" such as "umm", "err", "ahh" as fillers in conversations to help them run smoothly.

Bob always finds himself saying "err". Infact he adds an "err" to every single word he says that ends in a consonant! Because Bob is odd, he likes to stick to this habit even when emailing. 

Task

Bob is begging you to write a function that adds "err" to the end of every word whose last letter is a consonant (not a vowel, y counts as a consonant). 

The input is a string that can contain upper and lowercase characters, some punctuation but no numbers. The solution should be returned as a string.

NOTE: If the word ends with an uppercase consonant, the following "err" will be uppercase --> "ERR".

eg:
```
"Hello, I am Mr Bob" --> "Hello, I amerr Mrerr Boberr"

"THIS IS CRAZY!"  --> "THISERR ISERR CRAZYERR!"
```


Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are n flights that must depart today, the i-th of them is planned to depart at the i-th minute of the day.

Metropolis airport is the main transport hub of Metropolia, so it is difficult to keep the schedule intact. This is exactly the case today: because of technical issues, no flights were able to depart during the first k minutes of the day, so now the new departure schedule must be created.

All n scheduled flights must now depart at different minutes between (k + 1)-th and (k + n)-th, inclusive. However, it's not mandatory for the flights to depart in the same order they were initially scheduled to do so — their order in the new schedule can be different. There is only one restriction: no flight is allowed to depart earlier than it was supposed to depart in the initial schedule.

Helen knows that each minute of delay of the i-th flight costs airport c_{i} burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 300 000), here n is the number of flights, and k is the number of minutes in the beginning of the day that the flights did not depart.

The second line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^7), here c_{i} is the cost of delaying the i-th flight for one minute.


-----Output-----

The first line must contain the minimum possible total cost of delaying the flights.

The second line must contain n different integers t_1, t_2, ..., t_{n} (k + 1 ≤ t_{i} ≤ k + n), here t_{i} is the minute when the i-th flight must depart. If there are several optimal schedules, print any of them.


-----Example-----
Input
5 2
4 2 1 10 2

Output
20
3 6 7 4 5 



-----Note-----

Let us consider sample test. If Helen just moves all flights 2 minutes later preserving the order, the total cost of delaying the flights would be (3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38 burles. 

However, the better schedule is shown in the sample answer, its cost is (3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20 burles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
`late_clock` function receive an array with 4 digits and should return the latest time that can be built with those digits.
The time should be in `HH:MM` format.

Examples:
```
[1, 9, 8, 3] => 19:38
[9, 1, 2, 5] => 21:59
```

You can suppose the input is correct and you can build from it a correct 24-hour time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Scrooge has a sum of money 'P' that he wants to invest. Before he does, he wants to know how many years 'Y' this sum 'P' has to be kept in the bank in order for it to amount to a desired sum of money 'D'.

The sum is kept for 'Y' years in the bank where interest 'I' is paid yearly. After paying taxes 'T' for the year the new sum is re-invested.

Note to Tax: not the invested principal is taxed, but only the year's accrued interest

Example:

      Let P be the Principal = 1000.00      
      Let I be the Interest Rate = 0.05      
      Let T be the Tax Rate = 0.18      
      Let D be the Desired Sum = 1100.00


    After 1st Year -->
      P = 1041.00
    After 2nd Year -->
      P = 1083.86
    After 3rd Year -->
      P = 1128.30
  
Thus Mr. Scrooge has to wait for 3 years for the initial principal to amount to the desired sum.
 
Your task is to complete the method provided and return the number of years 'Y' as a whole in order for Mr. Scrooge to get the desired sum.  

Assumption: Assume that Desired Principal 'D' is always greater than the initial principal. However it is best to take into consideration that if Desired Principal 'D' is equal to Principal 'P' this should return 0 Years.

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