vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You may have heard of the pie rule before. It states that if two people wish to fairly share a slice of pie, one person should cut the slice in half, and the other person should choose who gets which slice. Alice and Bob have many slices of pie, and rather than cutting the slices in half, each individual slice will be eaten by just one person.

The way Alice and Bob decide who eats each slice is as follows. First, the order in which the pies are to be handed out is decided. There is a special token called the "decider" token, initially held by Bob. Until all the pie is handed out, whoever has the decider token will give the next slice of pie to one of the participants, and the decider token to the other participant. They continue until no slices of pie are left.

All of the slices are of excellent quality, so each participant obviously wants to maximize the total amount of pie they get to eat. Assuming both players make their decisions optimally, how much pie will each participant receive?


-----Input-----

Input will begin with an integer N (1 ≤ N ≤ 50), the number of slices of pie. 

Following this is a line with N integers indicating the sizes of the slices (each between 1 and 100000, inclusive), in the order in which they must be handed out.


-----Output-----

Print two integers. First, the sum of the sizes of slices eaten by Alice, then the sum of the sizes of the slices eaten by Bob, assuming both players make their decisions optimally.


-----Examples-----
Input
3
141 592 653

Output
653 733

Input
5
10 21 10 21 10

Output
31 41



-----Note-----

In the first example, Bob takes the size 141 slice for himself and gives the decider token to Alice. Then Alice gives the size 592 slice to Bob and keeps the decider token for herself, so that she can then give the size 653 slice to herself.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After a successful field test, Heidi is considering deploying a trap along some Corridor, possibly not the first one. She wants to avoid meeting the Daleks inside the Time Vortex, so for abundance of caution she considers placing the traps only along those Corridors that are not going to be used according to the current Daleks' plan – which is to use a minimum spanning tree of Corridors. Heidi knows that all energy requirements for different Corridors are now different, and that the Daleks have a single unique plan which they are intending to use.

Your task is to calculate the number E_{max}(c), which is defined in the same way as in the easy version – i.e., the largest e ≤ 10^9 such that if we changed the energy of corridor c to e, the Daleks might use it – but now for every corridor that Heidi considers. 

Input

The first line: number n of destinations, number m of Time Corridors (2 ≤ n ≤ 10^5, n - 1 ≤ m ≤ 10^6). The next m lines: destinations a, b and energy e (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ e ≤ 10^9).

No pair \\{a, b\} will repeat. The graph is guaranteed to be connected. All energy requirements e are distinct.

Output

Output m-(n-1) lines, each containing one integer: E_{max}(c_i) for the i-th Corridor c_i from the input that is not part of the current Daleks' plan (minimum spanning tree).

Example

Input

3 3
1 2 8
2 3 3
3 1 4


Output

4

Note

If m = n-1, then you need not output anything.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The bear decided to store some raspberry for the winter. He cunningly found out the price for a barrel of honey in kilos of raspberry for each of the following *n* days. According to the bear's data, on the *i*-th (1<=≤<=*i*<=≤<=*n*) day, the price for one barrel of honey is going to is *x**i* kilos of raspberry.

Unfortunately, the bear has neither a honey barrel, nor the raspberry. At the same time, the bear's got a friend who is ready to lend him a barrel of honey for exactly one day for *c* kilograms of raspberry. That's why the bear came up with a smart plan. He wants to choose some day *d* (1<=≤<=*d*<=&lt;<=*n*), lent a barrel of honey and immediately (on day *d*) sell it according to a daily exchange rate. The next day (*d*<=+<=1) the bear wants to buy a new barrel of honey according to a daily exchange rate (as he's got some raspberry left from selling the previous barrel) and immediately (on day *d*<=+<=1) give his friend the borrowed barrel of honey as well as *c* kilograms of raspberry for renting the barrel.

The bear wants to execute his plan at most once and then hibernate. What maximum number of kilograms of raspberry can he earn? Note that if at some point of the plan the bear runs out of the raspberry, then he won't execute such a plan.

Input Specification:
The first line contains two space-separated integers, *n* and *c* (2<=≤<=*n*<=≤<=100,<=0<=≤<=*c*<=≤<=100), — the number of days and the number of kilos of raspberry that the bear should give for borrowing the barrel.

The second line contains *n* space-separated integers *x*1,<=*x*2,<=...,<=*x**n* (0<=≤<=*x**i*<=≤<=100), the price of a honey barrel on day *i*.

Output Specification:
Print a single integer — the answer to the problem.

Demo Input:
['5 1\n5 10 7 3 20\n', '6 2\n100 1 10 40 10 40\n', '3 0\n1 2 3\n']

Demo Output:
['3\n', '97\n', '0\n']

Note:
In the first sample the bear will lend a honey barrel at day 3 and then sell it for 7. Then the bear will buy a barrel for 3 and return it to the friend. So, the profit is (7 - 3 - 1) = 3.

In the second sample bear will lend a honey barrel at day 1 and then sell it for 100. Then the bear buy the barrel for 1 at the day 2. So, the profit is (100 - 1 - 2) = 97.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It’s that time of the year when students head back to school, which will usually involve moving lots of stuff, and packing lots of that stuff into boxes. However, before we go through that effort, it would be nice to know whether the boxes we have are the right size!

A box has three dimensions, $l$, $w$, and $h$, and a box’s volume $v$ is simply $l\cdot w \cdot h$. We have many small items to pack, and we don’t care about their exact geometry: we know that, as long as a box has a volume of, at least, $\mathbf{V}$, we will be able to pack all those items into that single box. So, given a box $i$, and its volume $v_ i$, then the difference $d_ i=v_ i-\mathbf{V}$ can tell us whether the box is big enough or not to pack all the items. If $d_ i$ is greater than or equal to zero, the box is big enough; otherwise, the box is too small.

So, we want to answer a simple question: given multiple boxes, is the largest box (by volume) large enough to store all our items? For example, suppose $\mathbf{V}=10$ and we have three boxes, $A$, $B$, and $C$, with dimensions $(1,1,2)$, $(2,2,2)$, and $(3,2,1)$, respectively. Their volumes will be $v_ A=2$, $v_ B=8$, and $v_ C=6$, which means the largest box is $B$. Unfortunately, $d_ B=v_ B-\mathbf{V}=8-10=-2$, which means our largest box is not large enough.

On the other hand, suppose $\mathbf{V}=980$, and we had four boxes, $W$, $X$, $Y$, and $Z$ with dimensions $(10,10,10)$, $(10,5,2)$, $(5,3,2)$, and $(90,5,2)$, respectively. Their volumes will be $v_ W=1000$, $v_ X=100$, $v_ Y=30$ and $v_ Z=900$, making $W$ the largest box and, since $d_ W=v_ W-\mathbf{V}=1000-980=20$, that means $W$ is big enough for all our items.

-----Input-----
The input specifies a set of boxes. It begins with a line containing two integers: $n$ ($1 \le n \le 100$), specifying the number of boxes, and $\mathbf{V}$, as defined above. The remaining input is composed of $n$ lines, each specifying one box. Each line contains the dimensions $l$, $w$, and $h$ for the box. You may assume that $1 \leqslant l, w, h, \mathbf{V} < 2^{32}$. You may also assume that, for any given box $i$, its volume $v_ i$ will always be less than $2^{32}$

-----Output-----
The output is a single integer: the value of $d_ i$ for the largest box by volume.

-----Examples-----
Sample Input 1:
3 10
1 1 2
2 2 2
3 2 1
Sample Output 1:
-2

Sample Input 2:
3 30
1 1 1
5 2 3
5 2 1
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N non-negative integers written on the blackboard: A_1, ..., A_N.

Snuke can perform the following two operations at most K times in total in any order:

* Operation A: Replace each integer X on the blackboard with X divided by 2, rounded down to the nearest integer.
* Operation B: Replace each integer X on the blackboard with X minus 1. This operation cannot be performed if one or more 0s are written on the blackboard.



Find the number of the different possible combinations of integers written on the blackboard after Snuke performs the operations, modulo 1,000,000,007.

Constraints

* 1 \leq N \leq 200
* 1 \leq A_i \leq 10^{18}
* 1 \leq K \leq 10^{18}
* A_i and K are integers.

Input

Input is given from Standard Input in the following format:


N K
A_1 A_2 ... A_N


Output

Print the number of the different possible combinations of integers written on the blackboard after Snuke performs the operations, modulo 1,000,000,007.

Examples

Input

2 2
5 7


Output

6


Input

3 4
10 13 22


Output

20


Input

1 100
10


Output

11


Input

10 123456789012345678
228344079825412349 478465001534875275 398048921164061989 329102208281783917 779698519704384319 617456682030809556 561259383338846380 254083246422083141 458181156833851984 502254767369499613


Output

164286011

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice plays the following game, loosely based on the card game "21".
Alice starts with 0 points, and draws numbers while she has less than K points.  During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer.  Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets K or more points.  What is the probability that she has N or less points?
Example 1:
Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation:  Alice gets a single card, then stops.

Example 2:
Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.

Example 3:
Input: N = 21, K = 17, W = 10
Output: 0.73278
Note:

0 <= K <= N <= 10000
1 <= W <= 10000
Answers will be accepted as correct if they are within 10^-5 of the correct answer.
The judging time limit has been reduced for this question.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are a sequence A= {a_1,a_2,......a_N} of N positive even numbers, and an integer M.
Let a semi-common multiple of A be a positive integer X that satisfies the following condition for every k (1 \leq k \leq N):
 - There exists a non-negative integer p such that X= a_k \times (p+0.5).
Find the number of semi-common multiples of A among the integers between 1 and M (inclusive).

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 1 \leq M \leq 10^9
 - 2 \leq a_i \leq 10^9
 - a_i is an even number.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
a_1 a_2 ... a_N

-----Output-----
Print the number of semi-common multiples of A among the integers between 1 and M (inclusive).

-----Sample Input-----
2 50
6 10

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

 - 15 = 6  \times 2.5 
 - 15 = 10 \times 1.5 
 - 45 = 6  \times 7.5 
 - 45 = 10 \times 4.5 
Thus, 15 and 45 are semi-common multiples of A. There are no other semi-common multiples of A between 1 and 50, so the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have two distinct integers A and B.
Print the integer K such that |A - K| = |B - K|.
If such an integer does not exist, print IMPOSSIBLE instead.

-----Constraints-----
 - All values in input are integers.
 - 0 \leq A,\ B \leq 10^9
 - A and B are distinct.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print the integer K satisfying the condition.
If such an integer does not exist, print IMPOSSIBLE instead.

-----Sample Input-----
2 16

-----Sample Output-----
9

|2 - 9| = 7 and |16 - 9| = 7, so 9 satisfies the condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are choreographing a circus show with various animals. For one act, you are given two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity). 

The first kangaroo starts at location $x\mbox{1}$ and moves at a rate of $\mbox{v1}$ meters per jump. 
The second kangaroo starts at location $x2$ and moves at a rate of $v2$ meters per jump.

You have to figure out a way to get both kangaroos at the same location at the same time  as part of the show.  If it is possible, return YES, otherwise return NO.  

Example 

$x1=2$ 

$v1=1$ 

$x2=1$ 

$v2=2$   

After one jump, they are both at $x=3$, ($x1+v1=2+1$, $x2+v2=1+2$), so the answer is YES.

Function Description

Complete the function kangaroo in the editor below.    

kangaroo has the following parameter(s):  

int x1, int v1: starting position and jump distance for kangaroo 1
int x2, int v2: starting position and jump distance for kangaroo 2   

Returns   

string: either YES or NO

Input Format

A single line of four space-separated integers denoting the respective values of $x\mbox{1}$, $\mbox{v1}$, $x2$, and $v2$.

Constraints

$0\leq x1<x2\leq10000$  
$1\leq v1\leq10000$  
$1\leq v2\leq10000$  

Sample Input 0
0 3 4 2

Sample Output 0
YES

Explanation 0

The two kangaroos jump through the following sequence of locations:

From the image, it is clear that the kangaroos meet at the same location (number $12$ on the number line) after same number of jumps ($\begin{array}{c}4\end{array}$ jumps), and we print YES.

Sample Input 1
0 2 5 3

Sample Output 1
NO

Explanation 1

The second kangaroo has a starting location that is ahead (further to the right) of the first kangaroo's starting location (i.e., $x_2>x_1$). Because the second kangaroo moves at a faster rate (meaning $v_2>v_1$) and is already ahead of the first kangaroo, the first kangaroo will never be able to catch up. Thus, we print NO.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given string s. Let's call word any largest sequence of consecutive symbols without symbols ',' (comma) and ';' (semicolon). For example, there are four words in string "aba,123;1a;0": "aba", "123", "1a", "0". A word can be empty: for example, the string s=";;" contains three empty words separated by ';'.

You should find all words in the given string that are nonnegative INTEGER numbers without leading zeroes and build by them new string a. String a should contain all words that are numbers separating them by ',' (the order of numbers should remain the same as in the string s). By all other words you should build string b in the same way (the order of numbers should remain the same as in the string s).

Here strings "101", "0" are INTEGER numbers, but "01" and "1.0" are not.

For example, for the string aba,123;1a;0 the string a would be equal to "123,0" and string b would be equal to "aba,1a".

Input

The only line of input contains the string s (1 ≤ |s| ≤ 105). The string contains only symbols '.' (ASCII 46), ',' (ASCII 44), ';' (ASCII 59), digits, lowercase and uppercase latin letters.

Output

Print the string a to the first line and string b to the second line. Each string should be surrounded by quotes (ASCII 34).

If there are no words that are numbers print dash (ASCII 45) on the first line. If all words are numbers print dash on the second line.

Examples

Input

aba,123;1a;0


Output

"123,0"
"aba,1a"


Input

1;;01,a0,


Output

"1"
",01,a0,"


Input

1


Output

"1"
-


Input

a


Output

-
"a"

Note

In the second example the string s contains five words: "1", "", "01", "a0", "".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are going to be given an array of integers. Your job is to take that array and find an index N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no index that would make this happen, return `-1`.

__For example:__

Let's say you are given the array `{1,2,3,4,3,2,1}`:  
Your function will return the index `3`, because at the 3rd position of the array, the sum of left side of the index (`{1,2,3}`) and the sum of the right side of the index (`{3,2,1}`) both equal `6`.


Let's look at another one.  
You are given the array `{1,100,50,-51,1,1}`:  
Your function will return the index `1`, because at the 1st position of the array, the sum of left side of the index (`{1}`) and the sum of the right side of the index (`{50,-51,1,1}`) both equal `1`.

Last one:  
You are given the array `{20,10,-80,10,10,15,35}`  
At index 0 the left side is `{}`  
The right side is `{10,-80,10,10,15,35}`  
They both are equal to `0` when added. (Empty arrays are equal to 0 in this problem)  
Index 0 is the place where the left side and right side are equal.  

Note: Please remember that in most programming/scripting languages the index of an array starts at 0.

__Input:__  
An integer array of length `0 < arr < 1000`. The numbers in the array can be any integer positive or negative.

__Output:__  
The lowest index `N` where the side to the left of `N` is equal to the side to the right of `N`. If you do not find an index that fits these rules, then you will return `-1`.

__Note:__  
If you are given an array with multiple answers, return the lowest correct index.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Do you like summer? Residents of Berland do. They especially love eating ice cream in the hot summer. So this summer day a large queue of *n* Berland residents lined up in front of the ice cream stall. We know that each of them has a certain amount of berland dollars with them. The residents of Berland are nice people, so each person agrees to swap places with the person right behind him for just 1 dollar. More formally, if person *a* stands just behind person *b*, then person *a* can pay person *b* 1 dollar, then *a* and *b* get swapped. Of course, if person *a* has zero dollars, he can not swap places with person *b*.

Residents of Berland are strange people. In particular, they get upset when there is someone with a strictly smaller sum of money in the line in front of them.

Can you help the residents of Berland form such order in the line so that they were all happy? A happy resident is the one who stands first in the line or the one in front of who another resident stands with not less number of dollars. Note that the people of Berland are people of honor and they agree to swap places only in the manner described above.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of residents who stand in the line.

The second line contains *n* space-separated integers *a**i* (0<=≤<=*a**i*<=≤<=109), where *a**i* is the number of Berland dollars of a man standing on the *i*-th position in the line. The positions are numbered starting from the end of the line.

Output Specification:
If it is impossible to make all the residents happy, print ":(" without the quotes. Otherwise, print in the single line *n* space-separated integers, the *i*-th of them must be equal to the number of money of the person on position *i* in the new line. If there are multiple answers, print any of them.

Demo Input:
['2\n11 8\n', '5\n10 9 7 10 6\n', '3\n12 3 3\n']

Demo Output:
['9 10 ', ':(\n', '4 4 10 ']

Note:
In the first sample two residents should swap places, after that the first resident has 10 dollars and he is at the head of the line and the second resident will have 9 coins and he will be at the end of the line. 

In the second sample it is impossible to achieve the desired result.

In the third sample the first person can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second person (in the new line) swaps with the third one, and the resulting numbers of dollars will equal to: 4 4 10. In this line everybody will be happy.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ann has recently started commuting by subway. We know that a one ride subway ticket costs *a* rubles. Besides, Ann found out that she can buy a special ticket for *m* rides (she can buy it several times). It costs *b* rubles. Ann did the math; she will need to use subway *n* times. Help Ann, tell her what is the minimum sum of money she will have to spend to make *n* rides?

Input Specification:
The single line contains four space-separated integers *n*, *m*, *a*, *b* (1<=≤<=*n*,<=*m*,<=*a*,<=*b*<=≤<=1000) — the number of rides Ann has planned, the number of rides covered by the *m* ride ticket, the price of a one ride ticket and the price of an *m* ride ticket.

Output Specification:
Print a single integer — the minimum sum in rubles that Ann will need to spend.

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

Demo Output:
['6\n', '8\n']

Note:
In the first sample one of the optimal solutions is: each time buy a one ride ticket. There are other optimal solutions. For example, buy three *m* ride tickets.

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