vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Esports is a form of competitive sports using video games. Dota 2 is one of the most popular competitive video games in Esports. Recently, a new video game Dota 3 was released. In Dota 3 a player can buy some relics for their hero. Relics are counters that track hero's actions and statistics in a game.

Gloria likes to play Dota 3, so she wants to buy all n available relics for her favorite hero.

Relics can be bought using an in-game currency called shards. Each relic has its own price — c_i shards for the i-th relic. A player can buy a relic using one of the following options: 

  * Pay c_i shards to buy the i-th relic; 
  * Pay x shards and randomly get one of all n relics. The probability of getting a relic is the same for all n relics. If a duplicate relic is received, then the relic is recycled and x/2 shards are given back to the player. 



Gloria wants to buy all n relics. Help her minimize the expected number of shards she spends to buy all the relics.

Input

The first line contains two integers n and x (1 ≤ n ≤ 100; 1 ≤ x ≤ 10 000) — the number of relics and the cost to receive a random relic.

The second line consists of n integers c_1, c_2, …, c_n (x ≤ c_i ≤ 10 000; ∑{c_i} ≤ 10 000) — the prices of n relics.

Output

Print a single real number — the minimum expected number of shards that Gloria must spend to buy all the relics.

The absolute or relative error should not exceed 10^{-9}.

Examples

Input


2 20
25 100


Output


47.50000000000000000


Input


4 30
60 50 60 80


Output


171.25000000000000000

Note

In the first example, the optimal strategy is to randomly get one of the two relics paying 20 shards. Then there are two scenarios. 

The first one happens if Gloria receives the first relic. Then she keeps getting random relics until she obtains the second relic. The expected number of shards to spend in this scenario is 20 + 30 = 50.

In the second scenario, Gloria initially gets the second relic. Then it is better to buy the first relic for 25 shards, so the expected number of shards to spend in this scenario is 20 + 25 = 45.

Thus, the expected number of shards to spend is (50 + 45)/(2) = 47.5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.
You are also given an integer maxCost.
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.
If there is no substring from s that can be changed to its corresponding substring from t, return 0.
 
Example 1:
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.

 
Constraints:

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s and t only contain lower case English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose you have a Matrix size n*n, and given an integer k and a set of coordinates arr of size k*2. Initially, the matrix contains only 0. You are given k tasks and for each task, you are given two coordinates (r = arr[i][0],c = arr[i][1]) [1 based index r and c]. Where coordinates (r,c) denotes r^{th }row and c^{th }column of the given matrix.
You have to perform each task sequentially in the given order. For each task, You have to put 1 in all cells of r^{th} row  and all cells of c^{th} column.
After each task, You have to calculate the number of 0 present in the matrix and return it.
Example 1:
Input:
n = 3, k= 3
arr =
{{2, 2},
 {2, 3},
 {3, 2}}
Output: 4 2 1
Explanation: 
After 1st Operation, all the 2nd row
and all the 2nd column will be filled by
1. So remaning cell with value 0 will be 4
After 2nd Operation, all the 2nd row and all
the 3rd column will be filled by 1. So 
remaning cell with value 0 will be 2.
After 3rd Operation cells having value 0 will
be 1.
Example 2:
Input:
n = 2, k = 2
arr = 
{{1, 2},
 {1, 1}}
Output: 1 0
Explanation: 
After 1st Operation, all the 1st row and 
all the 2nd column will be filled by 1. 
So remaning cell with value 0 will be 1.
After 2nd Operation, all the 1st row and 
all the 1st column will be filled by 1. 
So remaning cell with value 0 will be 0. 
Your Task:
The task is to complete the function countZero(), which takes parameter n, size of
the matrix, k no of operation and array arr[][], which denotes the position of the cells.
You have to return an array that contains all the results.
Expected Time Complexity: O( k ).
Expected Auxiliary Space: O( n+n+k ).
Constraints:
1 <= n, k <= 10^{5}
1 <= r, c <= n

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
in Chefland, there is a very famous street where $N$ types of street food (numbered $1$ through $N$) are offered. For each valid $i$, there are $S_i$ stores that offer food of the $i$-th type, the price of one piece of food of this type is $V_i$ (the same in each of these stores) and each day, $P_i$ people come to buy it; each of these people wants to buy one piece of food of the $i$-th type.
Chef is planning to open a new store at this street, where he would offer food of one of these $N$ types. Chef assumes that the people who want to buy the type of food he'd offer will split equally among all stores that offer it, and if this is impossible, i.e. the number of these people $p$ is not divisible by the number of these stores $s$, then only $\left\lfloor\frac{p}{s}\right\rfloor$ people will buy food from Chef.
Chef wants to maximise his daily profit. Help Chef choose which type of food to offer and find the maximum daily profit he can make.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$. 
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains three space-separated integers $S_i$, $P_i$ and $V_i$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum profit.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 100$
- $1 \le S_i, V_i, P_i \le 10,000$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
3
4 6 8
2 6 6
1 4 3
1
7 7 4

-----Example Output-----
12
0

-----Explanation-----
Example case 1: Chef should offer food of the second type. On each day, two people would buy from him, so his daily profit would be $12$.
Example case 2: Chef has no option other than to offer the only type of food, but he does not expect anyone to buy from him anyway, so his daily profit is $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jay runs a small carnival that has various rides and attractions. Unfortunately, times are tough. A recent roller coaster accident, flooding in the restrooms, and an unfortunate clown incident have given Jay’s carnival a bad reputation with the public. With fewer paying customers and reduced revenue, he will need to cut some costs to stay in business.

One of the biggest carnival attractions is a large, confusing maze. It consists of a variety of circular rooms connected by narrow, twisting corridors. Visitors love getting lost in it and trying to map it out. It has come to Jay’s attention that some of the rooms might be effectively identical to each other. If that’s the case, he will be able to reduce its size without anyone noticing.

Two rooms $A$ and $B$ are effectively identical if, when you are dropped into either room $A$ or $B$ (and you know the map of the maze), you cannot tell whether you began in $A$ or $B$ just by exploring the maze. The corridor exits are evenly spaced around each room, and you cannot mark or leave anything in a room (in particular, you cannot tell whether you have previously visited it). The only identifying feature that rooms have is their number of exits. Corridors are also twisty enough to be indistinguishable from each other, but when you enter a room you know which corridor you came from, so you can navigate a little by using the order they appear around the room.

Jay has appealed to the Association for Carnival Mazery for help. That’s you! Write a program to determine all the sets of effectively identical rooms in the maze.

-----Input-----
The input consists of a single test case. The first line contains an integer $n$, the number of rooms in the maze ($1 \leq n \leq 100$). Rooms are numbered from 1 to $n$. Following this are $n$ lines, describing each room in order. Each line consists of an integer $k$, indicating that this room has $k$ corridors ($0 \leq k < 100$), and then $k$ distinct integers listing the rooms each corridor connects to (in clockwise order, from an arbitrary starting point). Rooms do not connect to themselves.

-----Output-----
Display one line for each maximal set of effectively identical rooms (ignoring sets of size 1) containing the room numbers in the set in increasing order. Order the sets by their smallest room numbers. If there are no such sets, display none instead.

-----Examples-----
Sample Input:
13
2 2 4
3 1 3 5
2 2 4
3 1 3 6
2 2 6
2 4 5
2 8 9
2 7 9
2 7 8
2 11 13
2 10 12
2 11 13
2 10 12
Sample Output:
2 4
5 6
7 8 9 10 11 12 13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Twilight Sparkle was playing Ludo with her friends Rainbow Dash, Apple Jack and Flutter Shy. But she kept losing. Having returned to the castle, Twilight Sparkle became interested in the dice that were used in the game.

The dice has m faces: the first face of the dice contains a dot, the second one contains two dots, and so on, the m-th face contains m dots. Twilight Sparkle is sure that when the dice is tossed, each face appears with probability <image>. Also she knows that each toss is independent from others. Help her to calculate the expected maximum number of dots she could get after tossing the dice n times.

Input

A single line contains two integers m and n (1 ≤ m, n ≤ 105).

Output

Output a single real number corresponding to the expected maximum. The answer will be considered correct if its relative or absolute error doesn't exceed 10  - 4.

Examples

Input

6 1


Output

3.500000000000


Input

6 3


Output

4.958333333333


Input

2 2


Output

1.750000000000

Note

Consider the third test example. If you've made two tosses:

  1. You can get 1 in the first toss, and 2 in the second. Maximum equals to 2. 
  2. You can get 1 in the first toss, and 1 in the second. Maximum equals to 1. 
  3. You can get 2 in the first toss, and 1 in the second. Maximum equals to 2. 
  4. You can get 2 in the first toss, and 2 in the second. Maximum equals to 2. 



The probability of each outcome is 0.25, that is expectation equals to: 

<image>

You can read about expectation using the following link: http://en.wikipedia.org/wiki/Expected_value

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mysterious numbers - 2

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The only line of input contains three integers *a*1,<=*a*2,<=*a*3 (1<=≤<=*a*1,<=*a*2,<=*a*3<=≤<=20), separated by spaces.

Output a single integer.

Input Specification:
The only line of input contains three integers *a*1,<=*a*2,<=*a*3 (1<=≤<=*a*1,<=*a*2,<=*a*3<=≤<=20), separated by spaces.

Output Specification:
Output a single integer.

Demo Input:
['2 3 2\n', '13 14 1\n', '14 5 9\n', '17 18 3\n']

Demo Output:
['5\n', '14\n', '464\n', '53\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus loves lucky numbers. Everybody knows that lucky numbers are positive integers, whose decimal representation (without leading zeroes) contain only the lucky digits x and y. For example, if x = 4, and y = 7, then numbers 47, 744, 4 are lucky.

Let's call a positive integer a undoubtedly lucky, if there are such digits x and y (0 ≤ x, y ≤ 9), that the decimal representation of number a (without leading zeroes) contains only digits x and y.

Polycarpus has integer n. He wants to know how many positive integers that do not exceed n, are undoubtedly lucky. Help him, count this number.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^9) — Polycarpus's number.


-----Output-----

Print a single integer that says, how many positive integers that do not exceed n are undoubtedly lucky.


-----Examples-----
Input
10

Output
10

Input
123

Output
113



-----Note-----

In the first test sample all numbers that do not exceed 10 are undoubtedly lucky.

In the second sample numbers 102, 103, 104, 105, 106, 107, 108, 109, 120, 123 are not undoubtedly lucky.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Berland, there is the national holiday coming — the Flag Day. In the honor of this event the president of the country decided to make a big dance party and asked your agency to organize it. He has several conditions:  overall, there must be m dances; exactly three people must take part in each dance; each dance must have one dancer in white clothes, one dancer in red clothes and one dancer in blue clothes (these are the colors of the national flag of Berland). 

The agency has n dancers, and their number can be less than 3m. That is, some dancers will probably have to dance in more than one dance. All of your dancers must dance on the party. However, if some dance has two or more dancers from a previous dance, then the current dance stops being spectacular. Your agency cannot allow that to happen, so each dance has at most one dancer who has danced in some previous dance. 

You considered all the criteria and made the plan for the m dances: each dance had three dancers participating in it. Your task is to determine the clothes color for each of the n dancers so that the President's third condition fulfilled: each dance must have a dancer in white, a dancer in red and a dancer in blue. The dancers cannot change clothes between the dances.


-----Input-----

The first line contains two space-separated integers n (3 ≤ n ≤ 10^5) and m (1 ≤ m ≤ 10^5) — the number of dancers and the number of dances, correspondingly. Then m lines follow, describing the dances in the order of dancing them. The i-th line contains three distinct integers — the numbers of the dancers that take part in the i-th dance. The dancers are numbered from 1 to n. Each dancer takes part in at least one dance.


-----Output-----

Print n space-separated integers: the i-th number must represent the color of the i-th dancer's clothes (1 for white, 2 for red, 3 for blue). If there are multiple valid solutions, print any of them. It is guaranteed that at least one solution exists.


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

Output
1 2 3 3 2 2 1 

Input
9 3
3 6 9
2 5 8
1 4 7

Output
1 1 1 2 2 2 3 3 3 

Input
5 2
4 1 5
3 1 2

Output
2 3 1 1 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mishka got a six-faced dice. It has integer numbers from $2$ to $7$ written on its faces (all numbers on faces are different, so this is an almost usual dice).

Mishka wants to get exactly $x$ points by rolling his dice. The number of points is just a sum of numbers written at the topmost face of the dice for all the rolls Mishka makes.

Mishka doesn't really care about the number of rolls, so he just wants to know any number of rolls he can make to be able to get exactly $x$ points for them. Mishka is very lucky, so if the probability to get $x$ points with chosen number of rolls is non-zero, he will be able to roll the dice in such a way. Your task is to print this number. It is guaranteed that at least one answer exists.

Mishka is also very curious about different number of points to score so you have to answer $t$ independent queries.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of queries.

Each of the next $t$ lines contains one integer each. The $i$-th line contains one integer $x_i$ ($2 \le x_i \le 100$) — the number of points Mishka wants to get.


-----Output-----

Print $t$ lines. In the $i$-th line print the answer to the $i$-th query (i.e. any number of rolls Mishka can make to be able to get exactly $x_i$ points for them). It is guaranteed that at least one answer exists.


-----Example-----
Input
4
2
13
37
100

Output
1
3
8
27


-----Note-----

In the first query Mishka can roll a dice once and get $2$ points.

In the second query Mishka can roll a dice $3$ times and get points $5$, $5$ and $3$ (for example).

In the third query Mishka can roll a dice $8$ times and get $5$ points $7$ times and $2$ points with the remaining roll.

In the fourth query Mishka can roll a dice $27$ times and get $2$ points $11$ times, $3$ points $6$ times and $6$ points $10$ times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice got a message M. It is in an alien language. A string in an alien language is said to be valid if it contains the letter a or z.  Alice decided to count the number of valid substrings  of the message M. Help him to do this. Two substrings are different if it occurs at different positions in the message.  

Input
First line of the input contains the number of test cases T. It is followed by T lines. Each line has a single string M.  

Output
For each test case, output a single number, the number of valid substrings.   

Constraints
|M| ≤ 10^6 
M contains only lower case latin latters, that is characters a to z.

Read the editorial here.

SAMPLE INPUT
4
abcd
azazaz
abbzbba
flkjdh

SAMPLE OUTPUT
4
21
22
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef Tobby is trying to run a code given to him by Bhuvan for an experiment they want to include in the manuscript to be submitted to a conference. The deadline to submit the manuscript is within a couple of hours and Chef Tobby needs to finish the experiments before then.
The code given by Bhuvan is the following which runs given an array of N integers and another integer K :
void recurse ( array a, int n )
{
	// n = size of array
	define array b currently empty
	consider all 2^n subsets of a[]
	{
		x = bitwise OR of elements in the subsets
		add x into "b" if it is not present yet
	}
	if (sizeof( b ) == 1 << k)
	{
		printf(“Won”);
		return;
	}
	recurse ( b, sizeof( b ) );
}

Chef Tobby tried to run an experiment with only one integer in the array with value 2 and K = 3. To his horror, he found out that the algorithm is resulting in an infinite loop. He is livid with the possibility that the algorithm can lead to infinite loops for certain cases. On closer inspection he determines that it might be possible to insert additional elements in the initial array to subvert the problem. Since time is very less, Chef Tobby would like to insert the minimum number of elements.
Chef Tobby has to finish writing the paper, so he asks his graduate student Leamas to fix it. Leamas has no idea how to fix the problem so he asks you for help.

-----Input section-----
The first line contains T, the number of test cases.
Each test case consists of 2 lines. The first line contains 2 integers N and K, denoting the number of elements in the array and parameter mentioned in problem statement.
Next line contains N space separated integers, denoting the elements of the array.

-----Output section-----
Output the minimum number of elements that need to be inserted so that inifinite loop can be avoided.

-----Input constraints-----
1 ≤ T ≤ 10
1 ≤ Sum of N over all test cases ≤ 105
1 ≤ K ≤ 20
0 ≤ A[i] ≤ 2K-1, where A[i] denotes the ith element of the array.

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

-----Sample Output - 1-----
1

-----Explanation - 1-----
You can win the game by inserting the element 2 into the array.

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

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

-----Explanation - 2-----
The initial array will result will terminate in the first step of algorithm only. Thus there is no need to insert any new element.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The ZCO Scholarship Contest has just finished, and you finish with a rank of R. You know that Rank 1 to Rank 50 will get 100 \% scholarship on the ZCO exam fee and Rank 51 to Rank 100 will get 50 \% percentage scholarship on the ZCO exam fee. The rest do not get any scholarship.   
What percentage of scholarship will you get ?

------ Input Format ------ 

- Input consist of single line of input containing one integer R.

------ Output Format ------ 

- Output a single line containing one integer — the percentage of scholarship you will get.

------ Constraints ------ 

$1 ≤R  ≤10^{9}$

----- Sample Input 1 ------ 
49
----- Sample Output 1 ------ 
100
----- explanation 1 ------ 
Since $ 1 ≤ 49 ≤ 50$, answer is $100$ percentage scholarship.

----- Sample Input 2 ------ 
317
----- Sample Output 2 ------ 
0
----- explanation 2 ------ 
Since $317 > 100$, you do not get any scholarship.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Most programmers will tell you that one of the ways to improve your performance in competitive programming is to [practice a lot of problems].

Our Chef took the above advice very seriously and decided to set a target for himself.
Chef decides to solve at least 10 problems every week for 4 weeks. 

Given the number of problems he actually solved in each week over 4 weeks as P_{1}, P_{2}, P_{3}, and P_{4}, output the number of weeks in which Chef met his target.

------ Input Format ------ 

There is a single line of input, with 4 integers P_{1}, P_{2}, P_{3}, and P_{4}. These are the number of problems solved by Chef in each of the 4 weeks.

------ Output Format ------ 

Output a single integer in a single line - the number of weeks in which Chef solved at least 10 problems.

------ Constraints ------ 

$1 ≤ P_{1}, P_{2}, P_{3}, P_{4} ≤ 100$

----- Sample Input 1 ------ 
12 15 8 10

----- Sample Output 1 ------ 
3

----- explanation 1 ------ 
Chef solved at least $10$ problems in the first, second and fourth weeks. He failed to solve at least $10$ problems in the third week. Hence, the number of weeks in which Chef met his target is $3$.

----- Sample Input 2 ------ 
2 3 1 10

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

----- explanation 2 ------ 
Chef solved at least $10$ problems in the fourth week. He failed to solve at least $10$ problems in all the other three weeks. Hence, the number of weeks in which Chef met his target is $1$.

----- Sample Input 3 ------ 
12 100 99 11

----- Sample Output 3 ------ 
4

----- explanation 3 ------ 
Chef solved at least $10$ problems in all the four weeks. Hence, the number of weeks in which Chef met his target is $4$.

----- Sample Input 4 ------ 
1 1 1 1

----- Sample Output 4 ------ 
0

----- explanation 4 ------ 
Chef was not able to solve at least $10$ problems in any of the four weeks. Hence, the number of weeks in which Chef met his target is $0$.

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