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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
General Payne has a battalion of *n* soldiers. The soldiers' beauty contest is coming up, it will last for *k* days. Payne decided that his battalion will participate in the pageant. Now he has choose the participants.

All soldiers in the battalion have different beauty that is represented by a positive integer. The value *a**i* represents the beauty of the *i*-th soldier.

On each of *k* days Generals has to send a detachment of soldiers to the pageant. The beauty of the detachment is the sum of the beauties of the soldiers, who are part of this detachment. Payne wants to surprise the jury of the beauty pageant, so each of *k* days the beauty of the sent detachment should be unique. In other words, all *k* beauties of the sent detachments must be distinct numbers.

Help Payne choose *k* detachments of different beauties for the pageant. Please note that Payne cannot just forget to send soldiers on one day, that is, the detachment of soldiers he sends to the pageant should never be empty.

Input Specification:
The first line contains two integers *n*, *k* (1<=≤<=*n*<=≤<=50; 1<=≤<=*k*<=≤<= ) — the number of soldiers and the number of days in the pageant, correspondingly. The second line contains space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=107) — the beauties of the battalion soldiers.

It is guaranteed that Payne's battalion doesn't have two soldiers with the same beauty.

Output Specification:
Print *k* lines: in the *i*-th line print the description of the detachment that will participate in the pageant on the *i*-th day. The description consists of integer *c**i* (1<=≤<=*c**i*<=≤<=*n*) — the number of soldiers in the detachment on the *i*-th day of the pageant and *c**i* distinct integers *p*1,<=*i*,<=*p*2,<=*i*,<=...,<=*p**c**i*,<=*i* — the beauties of the soldiers in the detachment on the *i*-th day of the pageant. The beauties of the soldiers are allowed to print in any order.

Separate numbers on the lines by spaces. It is guaranteed that there is the solution that meets the problem conditions. If there are multiple solutions, print any of them.

Demo Input:
['3 3\n1 2 3\n', '2 1\n7 12\n']

Demo Output:
['1 1\n1 2\n2 3 2\n', '1 12 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Misha hacked the Codeforces site. Then he decided to let all the users change their handles. A user can now change his handle any number of times. But each new handle must not be equal to any handle that is already used or that was used at some point.

Misha has a list of handle change requests. After completing the requests he wants to understand the relation between the original and the new handles of the users. Help him to do that.

Input

The first line contains integer q (1 ≤ q ≤ 1000), the number of handle change requests.

Next q lines contain the descriptions of the requests, one per line.

Each query consists of two non-empty strings old and new, separated by a space. The strings consist of lowercase and uppercase Latin letters and digits. Strings old and new are distinct. The lengths of the strings do not exceed 20.

The requests are given chronologically. In other words, by the moment of a query there is a single person with handle old, and handle new is not used and has not been used by anyone.

Output

In the first line output the integer n — the number of users that changed their handles at least once.

In the next n lines print the mapping between the old and the new handles of the users. Each of them must contain two strings, old and new, separated by a space, meaning that before the user had handle old, and after all the requests are completed, his handle is new. You may output lines in any order.

Each user who changes the handle must occur exactly once in this description.

Examples

Input

5
Misha ILoveCodeforces
Vasya Petrov
Petrov VasyaPetrov123
ILoveCodeforces MikeMirzayanov
Petya Ivanov


Output

3
Petya Ivanov
Misha MikeMirzayanov
Vasya VasyaPetrov123

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two thieves (who strongly “recommended” us not to reveal their names) has broken into the central bank of Logland, where the country’s cash reserve is stored. In Logland, the currency has the $k$ denominations $1, 2, 4, 8, \ldots , 2^{k - 1}$, and the bank currently stores $x_ i$ coins of denominations $2^i$.

Thieves live by a very strict honor code, which stipulates that any loot grabbed must be divided evenly between the theives. Unfortunately (for the thieves), this may mean that some loot must be left behind. For example, if the bank contained a single coin of denomination $8$, and two coins of denomination $2$, there is no way they could bring the $8$ coin. Instead, they would have to take one coin of value $2$ each, leaving more than half of the possible loot!

Since neither leaving loot nor solving NP-hard problems are things thieves like to do, they have asked you to compute the minimum value of the loot they must leave behind, in order to be able to split the remaining loot evenly.

-----Input-----
The first line of input contains the integer $1 \le k \le 10^6$ – the number of denominations in Logland. The next line contains the $k$ integers $0 \le x_0, x_1, \dots , x_{k-1} \le 2^{30}$, the number of coins of the denominations $2^0, 2^1, \dots , 2^{k - 1}$.

-----Output-----
Output a single line, the minimum amount of money the thieves must leave behind. Since this number may be very large, output it modulo the prime number $10^9 + 7$.

-----Examples-----
Sample Input 1:
4
0 2 0 1
Sample Output 1:
8

Sample Input 2:
5
1000000 1 1 1 1
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot to take kayaks and catamarans to the point of departure. It's known that all kayaks are of the same size (and each of them occupies the space of 1 cubic metre), and all catamarans are of the same size, but two times bigger than kayaks (and occupy the space of 2 cubic metres).

Each waterborne vehicle has a particular carrying capacity, and it should be noted that waterborne vehicles that look the same can have different carrying capacities. Knowing the truck body volume and the list of waterborne vehicles in the boat depot (for each one its type and carrying capacity are known), find out such set of vehicles that can be taken in the lorry, and that has the maximum total carrying capacity. The truck body volume of the lorry can be used effectively, that is to say you can always put into the lorry a waterborne vehicle that occupies the space not exceeding the free space left in the truck body.

Input

The first line contains a pair of integer numbers n and v (1 ≤ n ≤ 105; 1 ≤ v ≤ 109), where n is the number of waterborne vehicles in the boat depot, and v is the truck body volume of the lorry in cubic metres. The following n lines contain the information about the waterborne vehicles, that is a pair of numbers ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 104), where ti is the vehicle type (1 – a kayak, 2 – a catamaran), and pi is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.

Output

In the first line print the maximum possible carrying capacity of the set. In the second line print a string consisting of the numbers of the vehicles that make the optimal set. If the answer is not unique, print any of them.

Examples

Input

3 2
1 2
2 7
1 3


Output

7
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers $a$ and $b$. His goal is to find a non-negative integer $k$ such that the least common multiple of $a+k$ and $b+k$ is the smallest possible. If there are multiple optimal integers $k$, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?


-----Input-----

The only line contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$).


-----Output-----

Print the smallest non-negative integer $k$ ($k \ge 0$) such that the lowest common multiple of $a+k$ and $b+k$ is the smallest possible.

If there are many possible integers $k$ giving the same value of the least common multiple, print the smallest one.


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

Output
2
Input
21 31

Output
9
Input
5 10

Output
0


-----Note-----

In the first test, one should choose $k = 2$, as the least common multiple of $6 + 2$ and $10 + 2$ is $24$, which is the smallest least common multiple possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Vova studies programming in an elite school. Vova and his classmates are supposed to write n progress tests, for each test they will get a mark from 1 to p. Vova is very smart and he can write every test for any mark, but he doesn't want to stand out from the crowd too much. If the sum of his marks for all tests exceeds value x, then his classmates notice how smart he is and start distracting him asking to let them copy his homework. And if the median of his marks will be lower than y points (the definition of a median is given in the notes), then his mom will decide that he gets too many bad marks and forbid him to play computer games.

Vova has already wrote k tests and got marks a_1, ..., a_{k}. He doesn't want to get into the first or the second situation described above and now he needs to determine which marks he needs to get for the remaining tests. Help him do that.


-----Input-----

The first line contains 5 space-separated integers: n, k, p, x and y (1 ≤ n ≤ 999, n is odd, 0 ≤ k < n, 1 ≤ p ≤ 1000, n ≤ x ≤ n·p, 1 ≤ y ≤ p). Here n is the number of tests that Vova is planned to write, k is the number of tests he has already written, p is the maximum possible mark for a test, x is the maximum total number of points so that the classmates don't yet disturb Vova, y is the minimum median point so that mom still lets him play computer games.

The second line contains k space-separated integers: a_1, ..., a_{k} (1 ≤ a_{i} ≤ p) — the marks that Vova got for the tests he has already written.


-----Output-----

If Vova cannot achieve the desired result, print "-1".

Otherwise, print n - k space-separated integers — the marks that Vova should get for the remaining tests. If there are multiple possible solutions, print any of them.


-----Examples-----
Input
5 3 5 18 4
3 5 4

Output
4 1

Input
5 3 5 16 4
5 5 5

Output
-1



-----Note-----

The median of sequence a_1, ..., a_{n} where n is odd (in this problem n is always odd) is the element staying on (n + 1) / 2 position in the sorted list of a_{i}.

In the first sample the sum of marks equals 3 + 5 + 4 + 4 + 1 = 17, what doesn't exceed 18, that means that Vova won't be disturbed by his classmates. And the median point of the sequence {1, 3, 4, 4, 5} equals to 4, that isn't less than 4, so his mom lets him play computer games.

Please note that you do not have to maximize the sum of marks or the median mark. Any of the answers: "4 2", "2 4", "5 1", "1 5", "4 1", "1 4" for the first test is correct.

In the second sample Vova got three '5' marks, so even if he gets two '1' marks, the sum of marks will be 17, that is more than the required value of 16. So, the answer to this test is "-1".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N dishes, numbered 1, 2, \ldots, N. Initially, for each i (1 \leq i \leq N), Dish i has a_i (1 \leq a_i \leq 3) pieces of sushi on it.

Taro will perform the following operation repeatedly until all the pieces of sushi are eaten:

* Roll a die that shows the numbers 1, 2, \ldots, N with equal probabilities, and let i be the outcome. If there are some pieces of sushi on Dish i, eat one of them; if there is none, do nothing.



Find the expected number of times the operation is performed before all the pieces of sushi are eaten.

Constraints

* All values in input are integers.
* 1 \leq N \leq 300
* 1 \leq a_i \leq 3

Input

Input is given from Standard Input in the following format:


N
a_1 a_2 \ldots a_N


Output

Print the expected number of times the operation is performed before all the pieces of sushi are eaten. The output is considered correct when the relative difference is not greater than 10^{-9}.

Examples

Input

3
1 1 1


Output

5.5


Input

1
3


Output

3


Input

2
1 2


Output

4.5


Input

10
1 3 2 3 3 2 3 2 1 3


Output

54.48064457488221

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
DropCaps means that the first letter of the starting word of the paragraph should be in caps and the remaining lowercase, just like you see in the newspaper. 

But for a change, let's do that for each and every word of the given String. Your task is to capitalize every word that has length greater than 2, leaving smaller words as they are.

*should work also on Leading and Trailing Spaces and caps.

```python
drop_cap('apple') => "Apple"
drop_cap('apple of banana'); => "Apple of Banana"
drop_cap('one   space'); => "One   Space" 
drop_cap('   space WALK   '); => "   Space Walk   " 
```

**Note:** you will be provided atleast one word and should take string as input and return string as output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set $T$, which is a subset of $S$. The set $S$ consists of $0, 1, ... n-1$. Print all subsets of $T$. Note that we represent $0, 1, ... n-1$ as 00...0001, 00...0010, 00...0100, ..., 10...0000 in binary respectively and the integer representation of a subset is calculated by bitwise OR of existing elements.

Constraints

* $1 \leq n \leq 28$
* $0 \leq k \leq 18$
* $k \leq n$
* $0 \leq b_i < n$

Input

The input is given in the following format.


$n$
$k \; b_0 \; b_1 \; ... \; b_{k-1}$


$k$ is the number of elements in $T$, and $b_i$ represents elements in $T$.

Output

Print the subsets ordered by their decimal integers. Print a subset in the following format.


$d$: $e_0$ $e_1$ ...


Print ':' after the integer value $d$, then print elements $e_i$ in the subset in ascending order. Separate two adjacency elements by a space character.

Example

Input

4
2 0 2


Output

0:
1: 0
4: 2
5: 0 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a number N, Cheffina challenges the chef to check the divisibility of all the permutation of N by 5. If any of the permutations is divisible by 5 then print 1 else print 0.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input,$N$. 

-----Output:-----
For each test case, output in a single line answer 1 or 0.

-----Constraints-----
- $1 \leq T \leq 10^6$
- $1 \leq N \leq 10^6$

-----Sample Input:-----
2
19
385

-----Sample Output:-----
0
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's been almost a week since Polycarp couldn't get rid of insomnia. And as you may already know, one week in Berland lasts k days!

When Polycarp went to a doctor with his problem, the doctor asked him about his sleeping schedule (more specifically, the average amount of hours of sleep per week). Luckily, Polycarp kept records of sleep times for the last n days. So now he has a sequence a_1, a_2, ..., a_{n}, where a_{i} is the sleep time on the i-th day.

The number of records is so large that Polycarp is unable to calculate the average value by himself. Thus he is asking you to help him with the calculations. To get the average Polycarp is going to consider k consecutive days as a week. So there will be n - k + 1 weeks to take into consideration. For example, if k = 2, n = 3 and a = [3, 4, 7], then the result is $\frac{(3 + 4) +(4 + 7)}{2} = 9$.

You should write a program which will calculate average sleep times of Polycarp over all weeks.


-----Input-----

The first line contains two integer numbers n and k (1 ≤ k ≤ n ≤ 2·10^5).

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Output average sleeping time over all weeks. 

The answer is considered to be correct if its absolute or relative error does not exceed 10^{ - 6}. In particular, it is enough to output real number with at least 6 digits after the decimal point.


-----Examples-----
Input
3 2
3 4 7

Output
9.0000000000

Input
1 1
10

Output
10.0000000000

Input
8 2
1 2 4 100000 123 456 789 1

Output
28964.2857142857



-----Note-----

In the third example there are n - k + 1 = 7 weeks, so the answer is sums of all weeks divided by 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two arrays nums1 and nums2.
Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.
A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).
 
Example 1:
Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.
Example 2:
Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.
Example 3:
Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.
 
Constraints:

1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's practice is to improve the ability to read messages hidden from sentences by searching for palindromes in strings. There may be many palindromes, so I'd like to count the number while searching.

Given two strings S and T, we want to find the number of pairs of integers (i, j, k, l) that satisfy the following:

* 1 ≤ i ≤ j ≤ (length of S).
* 1 ≤ k ≤ l ≤ (length of T).
* The substrings extracted from the i-th to j-th characters of S are the same as the substrings extracted from the k-th to l-th characters of T, and these are palindromes (even when read from the left). It is a character string that is the same even when read from the right).



Input


S
T


Both the strings S and T have a length of 1 or more and 50,000 or less, and consist of uppercase letters.

Output

Output the number of pairs of integers (i, j, k, l) that satisfy the condition on one line.

Examples

Input

ICPC
CPCPC


Output

10


Input

BABBAB
ABBA


Output

14


Input

MYON
USAGI


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shil has a permutation p1 , p2 .. pN of numbers from 1 to N and M queries. Each query consists of two integers l and  r . Answer to each query is total number of pairs[i , j] such that l ≤ i ≤ j ≤ r and|pi - pj| ≤ D. 

INPUT:
First line consists of three integers N, M and D. Next line consists of permutation p1 , p2 .. pN of the first N natural numbers. Next M lines consists of two integers l and r . 

OUTPUT:
Output M integers with i^th integer corresponding answer to i^th query.

CONSTRAINTS:
1 ≤ N, M ≤ 10^5
1 ≤ D ≤ 10
1 ≤ pi ≤ N 
1 ≤ l ≤ r ≤ N

SAMPLE INPUT
5 5 1
1 4 2 3 5
1 3
2 4
1 5
2 2
4 5

SAMPLE OUTPUT
4
5
9
1
2

Explanation

For 1^st query , all the pairs are (1,1) , (4,4) , (2,2) , (1,2).
For 2^nd query , all the pairs are (4,4) , (2,2) , (3,3) , (4,3) , (2,3).
For 3^rd query , all the pairs are (1,1) , (4,4) , (2,2) , (3,3) , (5,5) , (1,2) , (4,5) , (4,3) , (2,3).
Note that numbers in the bracket are values not indices of permutation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an unsorted array arr of size N, rearrange the elements of array such that number at the odd index is greater than the number at the previous even index. The task is to complete the function formatArray() which will return formatted array.
NOTE:
If the returned array formed is according to rules, 1 will be printed else 0 will be printed.
Example 1:
Input:
n = 5
arr[] = {5, 4, 3, 2, 1}
Output:
1
Explanation:
The given array after modification
will be as such: 4 5 2 3 1.
Example 2:
Input:
n = 4
arr[] = {4, 3, 2, 1}
Output:
1
User task:
Since this is a functional problem you don't have to worry about the input, you just have to complete the function formatArray(), which accepts array arr and its size  
Constraints:
1 <= T <= 100
1 <= N <= 100
1 <= arr[i] <= 100

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little X used to play a card game called "24 Game", but recently he has found it too easy. So he invented a new game.

Initially you have a sequence of *n* integers: 1,<=2,<=...,<=*n*. In a single step, you can pick two of them, let's denote them *a* and *b*, erase them from the sequence, and append to the sequence either *a*<=+<=*b*, or *a*<=-<=*b*, or *a*<=×<=*b*.

After *n*<=-<=1 steps there is only one number left. Can you make this number equal to 24?

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105).

Output Specification:
If it's possible, print "YES" in the first line. Otherwise, print "NO" (without the quotes).

If there is a way to obtain 24 as the result number, in the following *n*<=-<=1 lines print the required operations an operation per line. Each operation should be in form: "*a* *op* *b* = *c*". Where *a* and *b* are the numbers you've picked at this operation; *op* is either "+", or "-", or "*"; *c* is the result of corresponding operation. Note, that the absolute value of *c* mustn't be greater than 1018. The result of the last operation must be equal to 24. Separate operator sign and equality sign from numbers with spaces.

If there are multiple valid answers, you may print any of them.

Demo Input:
['1\n', '8\n']

Demo Output:
['NO\n', 'YES\n8 * 7 = 56\n6 * 5 = 30\n3 - 4 = -1\n1 - 2 = -1\n30 - -1 = 31\n56 - 31 = 25\n25 + -1 = 24\n']

Note:
none

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