vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Two out of Three

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya has recently developed a new algorithm to optimize the reception of customer flow and he considered the following problem.

Let the queue to the cashier contain *n* people, at that each of them is characterized by a positive integer *a**i* — that is the time needed to work with this customer. What is special about this very cashier is that it can serve two customers simultaneously. However, if two customers need *a**i* and *a**j* of time to be served, the time needed to work with both of them customers is equal to *max*(*a**i*,<=*a**j*). Please note that working with customers is an uninterruptable process, and therefore, if two people simultaneously come to the cashier, it means that they begin to be served simultaneously, and will both finish simultaneously (it is possible that one of them will have to wait).

Vasya used in his algorithm an ingenious heuristic — as long as the queue has more than one person waiting, then some two people of the first three standing in front of the queue are sent simultaneously. If the queue has only one customer number *i*, then he goes to the cashier, and is served within *a**i* of time. Note that the total number of phases of serving a customer will always be equal to ⌈*n*<=/<=2⌉.

Vasya thinks that this method will help to cope with the queues we all hate. That's why he asked you to work out a program that will determine the minimum time during which the whole queue will be served using this algorithm.

Input Specification:
The first line of the input file contains a single number *n* (1<=≤<=*n*<=≤<=1000), which is the number of people in the sequence. The second line contains space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=106). The people are numbered starting from the cashier to the end of the queue.

Output Specification:
Print on the first line a single number — the minimum time needed to process all *n* people. Then on ⌈*n*<=/<=2⌉ lines print the order in which customers will be served. Each line (probably, except for the last one) must contain two numbers separated by a space — the numbers of customers who will be served at the current stage of processing. If *n* is odd, then the last line must contain a single number — the number of the last served customer in the queue. The customers are numbered starting from 1.

Demo Input:
['4\n1 2 3 4\n', '5\n2 4 3 1 4\n']

Demo Output:
['6\n1 2\n3 4\n', '8\n1 3\n2 5\n4\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Cat Noku has obtained a map of the night sky. On this map, he found a constellation with *n* stars numbered from 1 to *n*. For each *i*, the *i*-th star is located at coordinates (*x**i*,<=*y**i*). No two stars are located at the same position.

In the evening Noku is going to take a look at the night sky. He would like to find three distinct stars and form a triangle. The triangle must have positive area. In addition, all other stars must lie strictly outside of this triangle. He is having trouble finding the answer and would like your help. Your job is to find the indices of three stars that would form a triangle that satisfies all the conditions. 

It is guaranteed that there is no line such that all stars lie on that line. It can be proven that if the previous condition is satisfied, there exists a solution to this problem.

Input Specification:
The first line of the input contains a single integer *n* (3<=≤<=*n*<=≤<=100<=000).

Each of the next *n* lines contains two integers *x**i* and *y**i* (<=-<=109<=≤<=*x**i*,<=*y**i*<=≤<=109).

It is guaranteed that no two stars lie at the same point, and there does not exist a line such that all stars lie on that line.

Output Specification:
Print three distinct integers on a single line — the indices of the three points that form a triangle that satisfies the conditions stated in the problem.

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

Demo Input:
['3\n0 1\n1 0\n1 1\n', '5\n0 0\n0 2\n2 0\n2 2\n1 1\n']

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

Note:
In the first sample, we can print the three indices in any order.

In the second sample, we have the following picture. 

Note that the triangle formed by starts 1, 4 and 3 doesn't satisfy the conditions stated in the problem, as point 5 is not strictly outside of this triangle (it lies on it's border).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dreamoon wants to climb up a stair of *n* steps. He can climb 1 or 2 steps at each move. Dreamoon wants the number of moves to be a multiple of an integer *m*. 

What is the minimal number of moves making him climb to the top of the stairs that satisfies his condition?

Input Specification:
The single line contains two space separated integers *n*, *m* (0<=&lt;<=*n*<=≤<=10000,<=1<=&lt;<=*m*<=≤<=10).

Output Specification:
Print a single integer — the minimal number of moves being a multiple of *m*. If there is no way he can climb satisfying condition print <=-<=1 instead.

Demo Input:
['10 2\n', '3 5\n']

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

Note:
For the first sample, Dreamoon could climb in 6 moves with following sequence of steps: {2, 2, 2, 2, 1, 1}.

For the second sample, there are only three valid sequence of steps {2, 1}, {1, 2}, {1, 1, 1} with 2, 2, and 3 steps respectively. All these numbers are not multiples of 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Levko loves permutations very much. A permutation of length n is a sequence of distinct positive integers, each is at most n.

Let’s assume that value gcd(a, b) shows the greatest common divisor of numbers a and b. Levko assumes that element p_{i} of permutation p_1, p_2, ... , p_{n} is good if gcd(i, p_{i}) > 1. Levko considers a permutation beautiful, if it has exactly k good elements. Unfortunately, he doesn’t know any beautiful permutation. Your task is to help him to find at least one of them.


-----Input-----

The single line contains two integers n and k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ n).


-----Output-----

In a single line print either any beautiful permutation or -1, if such permutation doesn’t exist.

If there are multiple suitable permutations, you are allowed to print any of them.


-----Examples-----
Input
4 2

Output
2 4 3 1
Input
1 1

Output
-1



-----Note-----

In the first sample elements 4 and 3 are good because gcd(2, 4) = 2 > 1 and gcd(3, 3) = 3 > 1. Elements 2 and 1 are not good because gcd(1, 2) = 1 and gcd(4, 1) = 1. As there are exactly 2 good elements, the permutation is beautiful.

The second sample has no beautiful permutations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob has a permutation of integers from 1 to n. Denote this permutation as p. The i-th element of p will be denoted as p_{i}. For all pairs of distinct integers i, j between 1 and n, he wrote the number a_{i}, j = min(p_{i}, p_{j}). He writes a_{i}, i = 0 for all integer i from 1 to n.

Bob gave you all the values of a_{i}, j that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given.


-----Input-----

The first line of the input will contain a single integer n (2 ≤ n ≤ 50).

The next n lines will contain the values of a_{i}, j. The j-th number on the i-th line will represent a_{i}, j. The i-th number on the i-th line will be 0. It's guaranteed that a_{i}, j = a_{j}, i and there is at least one solution consistent with the information given.


-----Output-----

Print n space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them.


-----Examples-----
Input
2
0 1
1 0

Output
2 1

Input
5
0 2 2 1 2
2 0 4 1 3
2 4 0 1 3
1 1 1 0 1
2 3 3 1 0

Output
2 5 4 1 3



-----Note-----

In the first case, the answer can be {1, 2} or {2, 1}.

In the second case, another possible answer is {2, 4, 5, 1, 3}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja has two sequences a and b and number p. Sequence a consists of n integers a_1, a_2, ..., a_{n}. Similarly, sequence b consists of m integers b_1, b_2, ..., b_{m}. As usual, Sereja studies the sequences he has. Today he wants to find the number of positions q (q + (m - 1)·p ≤ n; q ≥ 1), such that sequence b can be obtained from sequence a_{q}, a_{q} + p, a_{q} + 2p, ..., a_{q} + (m - 1)p by rearranging elements.

Sereja needs to rush to the gym, so he asked to find all the described positions of q.


-----Input-----

The first line contains three integers n, m and p (1 ≤ n, m ≤ 2·10^5, 1 ≤ p ≤ 2·10^5). The next line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). The next line contains m integers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ 10^9).


-----Output-----

In the first line print the number of valid qs. In the second line, print the valid values in the increasing order.


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

Output
2
1 3

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

Output
2
1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Manao's friends often send him new songs. He never listens to them right away. Instead, he compiles them into a playlist. When he feels that his mind is open to new music, he opens the playlist and starts to listen to the songs.

Of course, there are some songs that Manao doesn't particuarly enjoy. To get more pleasure from the received songs, he invented the following procedure of listening to the playlist:

  * If after listening to some song Manao realizes that he liked it, then he remembers it and starts to listen to the next unlistened song. 
  * If after listening to some song Manao realizes that he did not like it, he listens to all the songs he liked up to this point and then begins to listen to the next unlistened song. 



For example, if Manao has four songs in the playlist, A, B, C, D (in the corresponding order) and he is going to like songs A and C in the end, then the order of listening is the following:

  1. Manao listens to A, he likes it, he remembers it. 
  2. Manao listens to B, he does not like it, so he listens to A, again. 
  3. Manao listens to C, he likes the song and he remembers it, too. 
  4. Manao listens to D, but does not enjoy it and re-listens to songs A and C. 



That is, in the end Manao listens to song A three times, to song C twice and songs B and D once. Note that if Manao once liked a song, he will never dislike it on a subsequent listening.

Manao has received n songs: the i-th of them is li seconds long and Manao may like it with a probability of pi percents. The songs could get on Manao's playlist in any order, so Manao wants to know the maximum expected value of the number of seconds after which the listening process will be over, for all possible permutations of the songs in the playlist.

Input

The first line contains a single integer n (1 ≤ n ≤ 50000). The i-th of the following n lines contains two integers, separated by a single space — li and pi (15 ≤ li ≤ 1000, 0 ≤ pi ≤ 100) — the length of the i-th song in seconds and the probability that Manao will like the song, in percents.

Output

In a single line print a single real number — the maximum expected listening time over all permutations of songs. The answer will be considered valid if the absolute or relative error does not exceed 10 - 9.

Examples

Input

3
150 20
150 50
100 50


Output

537.500000000


Input

4
300 0
300 50
240 50
360 80


Output

2121.000000000

Note

Consider the first test case. If Manao listens to the songs in the order in which they were originally compiled, the mathematical expectation will be equal to 467.5 seconds. The maximum expected value is obtained by putting the first song at the end of the playlist.

Consider the second test case. The song which is 360 seconds long should be listened to first. The song 300 seconds long which Manao will dislike for sure should be put in the end.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a game of Nim with a friend. The rules are are follows:

1) Initially, there are N piles of stones. Two players play alternately.

2) In each turn, a player can choose one non empty pile and remove any number of stones from it. At least one stone must be removed.

3) The player who picks the last stone from the last non empty pile wins the game.

It is currently your friend's turn. You suddenly realize that if your friend was to play optimally in that position, you would lose the game. So while he is not looking, you decide to cheat and add some (possibly 0) stones to each pile. You want the resultant position to be such that your friend has no guaranteed winning strategy, even if plays optimally. You cannot create a new pile of stones. You can only add stones, and not remove stones from a pile. What is the least number of stones you need to add?

Input Format

The first line contains the number of cases T. T cases follow. Each case contains the number N on the first line followed by N numbers on the second line. The ith number denotes si, the number of stones in the ith pile currently.

Constraints

1 <= T <= 20

2 <= N <= 15

1 <= si < 1000000000 ($10^9$)

Output Format

Output T lines, containing the answer for each case. If the current position is already losing for your friend, output 0.

Sample Input

3

2

1 3

3

1 1 1

4

10 4 5 1

Sample Output

2

3

6

Explanation

For the first case, add 2 stones to the first pile. Then, both piles will have 3 stones each. It is easy to verify that your friend cannot win the game unless you make a mistake.

For the second case, add 1 stone to the first pile, and 2 stones to the second pile.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sweet little monster Om Nom loves candies very much. One day he found himself in a rather tricky situation that required him to think a bit in order to enjoy candies the most. Would you succeed with the same task if you were on his place? [Image] 

One day, when he came to his friend Evan, Om Nom didn't find him at home but he found two bags with candies. The first was full of blue candies and the second bag was full of red candies. Om Nom knows that each red candy weighs W_{r} grams and each blue candy weighs W_{b} grams. Eating a single red candy gives Om Nom H_{r} joy units and eating a single blue candy gives Om Nom H_{b} joy units.

Candies are the most important thing in the world, but on the other hand overeating is not good. Om Nom knows if he eats more than C grams of candies, he will get sick. Om Nom thinks that it isn't proper to leave candy leftovers, so he can only eat a whole candy. Om Nom is a great mathematician and he quickly determined how many candies of what type he should eat in order to get the maximum number of joy units. Can you repeat his achievement? You can assume that each bag contains more candies that Om Nom can eat.


-----Input-----

The single line contains five integers C, H_{r}, H_{b}, W_{r}, W_{b} (1 ≤ C, H_{r}, H_{b}, W_{r}, W_{b} ≤ 10^9).


-----Output-----

Print a single integer — the maximum number of joy units that Om Nom can get.


-----Examples-----
Input
10 3 5 2 3

Output
16



-----Note-----

In the sample test Om Nom can eat two candies of each type and thus get 16 joy units.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Despite the unfortunate incident last summer, which resulted in ten little puppies, you have been tasked with taking care of your neighbors’ dogs again. Shadow and Lydia may be very cute mutts, but this year you have strict instructions to walk them one by one. However, you have other things to do during the summer than walking dogs! Like playing fetch and solving programming problems! It seems terribly inefficient to walk the dogs one at a time. 

Shadow and Lydia have a particular walk they each prefer and know by heart. If you just let them out, they will follow their favorite walk, eventually ending up in their respective doghouses. Problem solved!

Sadly, you realize that if you just let both dogs out at the same time and let them do their walks on their own, they might get too close to each other. If they get too close, they will leave their favorite walk to “have some fun’’ and you are not sure you can find good homes for any more puppies. To ensure this does not happen, you need to calculate the minimum distance between the dogs when they are out walking on their own.

Both dogs start at the same time and keep exactly the same pace. Immediately after a dog arrives at its doghouse it stays inside and goes to sleep, so we no longer need to worry about the distance to the other dog, even though the other dog may still walk for a while longer. Note that a dog is still awake at the exact moment of entering its house and falls asleep immediately after entering.

-----Input-----
The first line of input consists of an integer $n$ ($2 \le n \le 100000$), the number of points describing the walk of Shadow. The next $n$ lines contain $2$ integers each, giving the $x$ and $y$ coordinates of Shadow’s walk. Two consecutive points in the walk always differ in at least one coordinate. All coordinates are non-negative and at most $10000$. Similarly, the next line contains an integer $m$ ($2 \le m \le 100000$), the number of points describing the walk of Lydia. The next $m$ lines describe its walk in the same format as for Shadow.

-----Output-----
Output the minimum distance between the two dogs during their walks. The numbers should be accurate to an absolute or relative error of at most $10^{-4}$.

-----Examples-----
Sample Input:
2
0 0
10 0
2
30 0
15 0
Sample Output:
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is enough money available on ATM in nominal value 10, 20, 50, 100, 200 and 500 dollars.

You are given money in nominal value of `n` with `1<=n<=1500`.

Try to find minimal number of notes that must be used to repay in dollars, or output -1 if it is impossible.

Good Luck!!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are hired by the ∀I¶אΞ℘, an extraterrestrial intelligence, as a programmer of their typesetting system. Your task today is to design an algorithm for text justification.

Text justification is to equalize the line widths as much as possible by inserting line breaks at appropriate posi- tions, given a word sequence called a paragraph and the width of the paper. Since you have not developed an automatic hyphenation algorithm yet, you cannot break a line in the middle of a word. And since their language does not put spaces between words, you do not need to consider about spacing.

To measure how well the text is justified in one configuration (i.e., a set of lines generated by inserting line breaks to a paragraph), you have defined its cost as follows:

* The total cost of a paragraph is the sum of the cost of each line.
* The cost for the last line is defined as max(0, s - w).
* The cost for other lines are given by |s - w|.



where s is the sum of the widths of the words in the line, and w is the width of the paper.

Please design the algorithm which takes a paragraph and calculates the configuration of the minimum cost.



Input

The input consists of multiple test cases.

The first line of each test case contains two positive integers n and w (0 ≤ n ≤ 1000 and 0 ≤ w ≤ 1,000,000). n is the length of paragraph and w is the width of the used paper. Each of the following n lines contains one positive integer ai which indicates the width of the i-th word in the paragraph. Here it is guaranteed that 0 ≤ ai ≤ w.

The input terminates with the line containing two zeros. This is not a part of any test case and should not be processed.

Output

For each test case, print the case number and the minimum cost for the paragraph.

Example

Input

4 10
8
6
9
1
4 7
1
2
3
4
0 0


Output

Case 1: 4
Case 2: 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tanechka is shopping in the toy shop. There are exactly $n$ toys in the shop for sale, the cost of the $i$-th toy is $i$ burles. She wants to choose two toys in such a way that their total cost is $k$ burles. How many ways to do that does she have?

Each toy appears in the shop exactly once. Pairs $(a, b)$ and $(b, a)$ are considered equal. Pairs $(a, b)$, where $a=b$, are not allowed.


-----Input-----

The first line of the input contains two integers $n$, $k$ ($1 \le n, k \le 10^{14}$) — the number of toys and the expected total cost of the pair of toys.


-----Output-----

Print the number of ways to choose the pair of toys satisfying the condition above. Print 0, if Tanechka can choose no pair of toys in such a way that their total cost is $k$ burles.


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

Output
2

Input
8 15

Output
1

Input
7 20

Output
0

Input
1000000000000 1000000000001

Output
500000000000



-----Note-----

In the first example Tanechka can choose the pair of toys ($1, 4$) or the pair of toys ($2, 3$).

In the second example Tanechka can choose only the pair of toys ($7, 8$).

In the third example choosing any pair of toys will lead to the total cost less than $20$. So the answer is 0.

In the fourth example she can choose the following pairs: $(1, 1000000000000)$, $(2, 999999999999)$, $(3, 999999999998)$, ..., $(500000000000, 500000000001)$. The number of such pairs is exactly $500000000000$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kyoya Ootori is selling photobooks of the Ouran High School Host Club. He has 26 photos, labeled "a" to "z", and he has compiled them into a photo booklet with some photos in some order (possibly with some photos being duplicated). A photo booklet can be described as a string of lowercase letters, consisting of the photos in the booklet in order. He now wants to sell some "special edition" photobooks, each with one extra photo inserted anywhere in the book. He wants to make as many distinct photobooks as possible, so he can make more money. He asks Haruhi, how many distinct photobooks can he make by inserting one extra photo into the photobook he already has?

Please help Haruhi solve this problem.

Input

The first line of input will be a single string s (1 ≤ |s| ≤ 20). String s consists only of lowercase English letters. 

Output

Output a single integer equal to the number of distinct photobooks Kyoya Ootori can make.

Examples

Input

a


Output

51


Input

hi


Output

76

Note

In the first case, we can make 'ab','ac',...,'az','ba','ca',...,'za', and 'aa', producing a total of 51 distinct photo booklets. 

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