vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Winter Is Coming

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The winter in Berland lasts *n* days. For each day we know the forecast for the average air temperature that day. 

Vasya has a new set of winter tires which allows him to drive safely no more than *k* days at any average air temperature. After *k* days of using it (regardless of the temperature of these days) the set of winter tires wears down and cannot be used more. It is not necessary that these *k* days form a continuous segment of days.

Before the first winter day Vasya still uses summer tires. It is possible to drive safely on summer tires any number of days when the average air temperature is non-negative. It is impossible to drive on summer tires at days when the average air temperature is negative. 

Vasya can change summer tires to winter tires and vice versa at the beginning of any day.

Find the minimum number of times Vasya needs to change summer tires to winter tires and vice versa to drive safely during the winter. At the end of the winter the car can be with any set of tires.

Input Specification:
The first line contains two positive integers *n* and *k* (1<=≤<=*n*<=≤<=2·105, 0<=≤<=*k*<=≤<=*n*) — the number of winter days and the number of days winter tires can be used. It is allowed to drive on winter tires at any temperature, but no more than *k* days in total.

The second line contains a sequence of *n* integers *t*1,<=*t*2,<=...,<=*t**n* (<=-<=20<=≤<=*t**i*<=≤<=20) — the average air temperature in the *i*-th winter day.

Output Specification:
Print the minimum number of times Vasya has to change summer tires to winter tires and vice versa to drive safely during all winter. If it is impossible, print -1.

Demo Input:
['4 3\n-5 20 -3 0\n', '4 2\n-5 20 -3 0\n', '10 6\n2 -5 1 3 0 0 -4 -3 1 0\n']

Demo Output:
['2\n', '4\n', '3\n']

Note:
In the first example before the first winter day Vasya should change summer tires to winter tires, use it for three days, and then change winter tires to summer tires because he can drive safely with the winter tires for just three days. Thus, the total number of tires' changes equals two. 

In the second example before the first winter day Vasya should change summer tires to winter tires, and then after the first winter day change winter tires to summer tires. After the second day it is necessary to change summer tires to winter tires again, and after the third day it is necessary to change winter tires to summer tires. Thus, the total number of tires' changes equals four.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n kangaroos with pockets. Each kangaroo has a size (integer number). A kangaroo can go into another kangaroo's pocket if and only if the size of kangaroo who hold the kangaroo is at least twice as large as the size of kangaroo who is held.

Each kangaroo can hold at most one kangaroo, and the kangaroo who is held by another kangaroo cannot hold any kangaroos.

The kangaroo who is held by another kangaroo cannot be visible from outside. Please, find a plan of holding kangaroos with the minimal number of kangaroos who is visible.


-----Input-----

The first line contains a single integer — n (1 ≤ n ≤ 5·10^5). Each of the next n lines contains an integer s_{i} — the size of the i-th kangaroo (1 ≤ s_{i} ≤ 10^5).


-----Output-----

Output a single integer — the optimal number of visible kangaroos.


-----Examples-----
Input
8
2
5
7
6
9
8
4
2

Output
5

Input
8
9
1
6
2
6
5
8
3

Output
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little girl Susie accidentally found her elder brother's notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to ask you about it. So, the problem statement is as follows.

Let's assume that we are given a connected weighted undirected graph G = (V, E) (here V is the set of vertices, E is the set of edges). The shortest-path tree from vertex u is such graph G1 = (V, E1) that is a tree with the set of edges E1 that is the subset of the set of edges of the initial graph E, and the lengths of the shortest paths from u to any vertex to G and to G1 are the same. 

You are given a connected weighted undirected graph G and vertex u. Your task is to find the shortest-path tree of the given graph from vertex u, the total weight of whose edges is minimum possible.

Input

The first line contains two numbers, n and m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of vertices and edges of the graph, respectively.

Next m lines contain three integers each, representing an edge — ui, vi, wi — the numbers of vertices connected by an edge and the weight of the edge (ui ≠ vi, 1 ≤ wi ≤ 109). It is guaranteed that graph is connected and that there is no more than one edge between any pair of vertices.

The last line of the input contains integer u (1 ≤ u ≤ n) — the number of the start vertex.

Output

In the first line print the minimum total weight of the edges of the tree.

In the next line print the indices of the edges that are included in the tree, separated by spaces. The edges are numbered starting from 1 in the order they follow in the input. You may print the numbers of the edges in any order.

If there are multiple answers, print any of them.

Examples

Input

3 3
1 2 1
2 3 1
1 3 2
3


Output

2
1 2 


Input

4 4
1 2 1
2 3 1
3 4 1
4 1 2
4


Output

4
2 3 4 

Note

In the first sample there are two possible shortest path trees:

  * with edges 1 – 3 and 2 – 3 (the total weight is 3); 
  * with edges 1 – 2 and 2 – 3 (the total weight is 2); 



And, for example, a tree with edges 1 – 2 and 1 – 3 won't be a shortest path tree for vertex 3, because the distance from vertex 3 to vertex 2 in this tree equals 3, and in the original graph it is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Brandon Greg Jr. is moving to the United States to double his salary. He has $n$ items that he needs to pack into $k$ big boxes. The $n$ items are currently arranged in a row, and Brandon doesn’t want to bother reordering them, so he will partition the $n$ items into $k$ groups of consecutive items, and put each of the $k$ groups into their own box. For convenience when moving, Brandon wants to minimize the weight of the heaviest box. The weights of the boxes themselves are negligible.

-----Input-----
The first line contains two space-separated integers $n$ and $k$ ($1\le k\le n\le 10^5$), denoting the number of items and the number of boxes respectively.

The second line of input contains $n$ space-separated integers $w_ i$ ($1\le w_ i\le 10^4$), representing the weight of each item in order.

-----Output-----
The only line of output should contain a single integer, denoting the minimum possible weight of the heaviest box.

-----Examples-----
Sample Input 1:
7 2
3 1 1 3 9 5 2
Sample Output 1:
16

Sample Input 2:
7 4
1 2 8 3 5 2 7
Sample Output 2:
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given a series of times at which an alarm goes off. Your task will be to determine the maximum time interval between alarms. Each alarm starts ringing at the beginning of the corresponding minute and rings for exactly one minute. The times in the array are not in chronological order. Ignore duplicate times, if any.

```Haskell
For example:
solve(["14:51"]) = "23:59". If the alarm goes off now, it will not go off for another 23 hours and 59 minutes.
solve(["23:00","04:22","18:05","06:24"]) == "11:40". The max interval that the alarm will not go off is 11 hours and 40 minutes.
```
In the second example, the alarm goes off `4` times in a day.

More examples in test cases. Good luck!

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

JOI, who came to Australia for a trip, enjoyed sightseeing in various places and finally returned to Japan. Now, JOI is in the town with the international airport where the return flight departs. The town is divided into north, south, east and west, and each section has roads, souvenir shops, houses, and an international airport. JOI starts from the northwestern section and heads for the international airport in the southeastern section.

JOI can move from the current parcel to an adjacent parcel, but cannot enter a parcel with a house. Also, move only to the east or south section of the current section in order to make it in time for the flight. However, there is some time to spare, so you can move to the north or west section of the section you are up to K times.

When JOI enters the area where the souvenir shop is located, he buys souvenirs for his Japanese friends. JOI did a lot of research on the souvenir shops, so he knows which souvenir shop to buy and how many souvenirs to buy. Create a program to find the maximum number of souvenirs you can buy.

However, the time to buy souvenirs can be ignored, and if you visit the same souvenir shop more than once, you will only buy souvenirs the first time you visit.





Example

Input

5 4 2
...#
.#.#
.#73
8##.
....


Output

11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko has $N$ items (labeled with numbers from $1$ to $N$) and $L$ drawers (labeled with numbers from $1$ to $L$). All items are currently scattered throughout his room, so he decided to clean them up. Each drawer can contain one item, and in order to make it easier for Mirko to find them later, he has determined in advance exactly two drawers ($A_ i$ and $B_ i$) for each item $i$.

Mirko stores the items in order from $1$ to $N$ using the first rule he can apply:
 - If the drawer $A_ i$ is empty, he stores the item $i$ in that drawer.
 - If the drawer $B_ i$ is empty, he stores the item $i$ in that drawer.
 - Try to move the item from $A_ i$ to its other drawer; if that one’s filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item $i$ in the drawer $A_ i$. In case of failure, continue to next rule.
 - Try moving the item from $B_ i$ to its other drawer; if that one’s filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item $i$ in the drawer $B_ i$. In case of failure, continue to next rule.
 - Give up and throw away the item $i$.

For given pairs of drawers for each item, determine which items will be stored and which will be thrown away.

-----Input-----
The first line of input consists of two integers, $N$ and $L$ ($1 \leq N, L \leq 300000$), the number of items and the number of drawers.

Each of the following $N$ lines contains two integers: $A_ i$ and $B_ i$ ($1 \leq A_ i, B_ i \leq L$), the pair of drawers corresponding to item $i$. The numbers $A_ i$ and $B_ i$ will be different.

-----Output-----
For each item, respectively, output where it ends up. In case the item is stored successfully, output “LADICA” (without quotes, Croatian word for drawer). In case the item is thrown away, output “SMECE” (without quotes, Croatian word for trash).

-----Examples-----
Sample Input:
5 3
1 2
1 3
1 2
1 3
1 2
Sample Output:
LADICA
LADICA
LADICA
SMECE
SMECE

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Even the most successful company can go through a crisis period when you have to make a hard decision — to restructure, discard and merge departments, fire employees and do other unpleasant stuff. Let's consider the following model of a company.

There are *n* people working for the Large Software Company. Each person belongs to some department. Initially, each person works on his own project in his own department (thus, each company initially consists of *n* departments, one person in each).

However, harsh times have come to the company and the management had to hire a crisis manager who would rebuild the working process in order to boost efficiency. Let's use *team*(*person*) to represent a team where person *person* works. A crisis manager can make decisions of two types:
 1.  Merge departments *team*(*x*) and *team*(*y*) into one large department containing all the employees of *team*(*x*) and *team*(*y*), where *x* and *y* (1<=≤<=*x*,<=*y*<=≤<=*n*) — are numbers of two of some company employees. If *team*(*x*) matches *team*(*y*), then nothing happens. 1.  Merge departments *team*(*x*),<=*team*(*x*<=+<=1),<=...,<=*team*(*y*), where *x* and *y* (1<=≤<=*x*<=≤<=*y*<=≤<=*n*) — the numbers of some two employees of the company. 
At that the crisis manager can sometimes wonder whether employees *x* and *y* (1<=≤<=*x*,<=*y*<=≤<=*n*) work at the same department.

Help the crisis manager and answer all of his queries.

Input Specification:
The first line of the input contains two integers *n* and *q* (1<=≤<=*n*<=≤<=200<=000, 1<=≤<=*q*<=≤<=500<=000) — the number of the employees of the company and the number of queries the crisis manager has.

Next *q* lines contain the queries of the crisis manager. Each query looks like *type* *x* *y*, where . If *type*<==<=1 or *type*<==<=2, then the query represents the decision of a crisis manager about merging departments of the first and second types respectively. If *type*<==<=3, then your task is to determine whether employees *x* and *y* work at the same department. Note that *x* can be equal to *y* in the query of any type.

Output Specification:
For each question of type 3 print "YES" or "NO" (without the quotes), depending on whether the corresponding people work in the same department.

Demo Input:
['8 6\n3 2 5\n1 2 5\n3 2 5\n2 4 7\n2 1 2\n3 1 7\n']

Demo Output:
['NO\nYES\nYES\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bijan is new to programming. He learned recently that programmers do not code every bit of their apps from scratch.

For example they never write a code to sum two integers, because their languages have the ability to do the sum. But can they use it? Can an experienced coder who has attended more than 100 contests, sum two integers?

Bijan is not sure about this. What's your opinion?

Input

You are given two integers a and b, one per line (1 ≤ a, b < 10500). These numbers will not have any leading zeros.

Output

Write sum of the two integers. Do not put any leading zeros.

Examples

Input

2
3


Output

5


Input

1390
2011


Output

3401


Input

12345
54321


Output

66666

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S, composed of different combinations of '(' , ')', '{', '}', '[', ']'. The task is to verify the validity of the arrangement.
An input string is valid if:
         1. Open brackets must be closed by the same type of brackets.
         2. Open brackets must be closed in the correct order.
Example 1:
Input:
S = ()[]{}
Output: 1
Explanation: The arrangement is valid.
 
Example 2:
Input:
S = ())({}
Output: 0
Explanation: Arrangement is not valid.
Example 3:
Input:
S = ([)]
Output: 0
Explanation: Arrangement is not valid.
 
Your Task:  
You dont need to read input or print anything. Complete the function valid() which takes S as input and returns a boolean value denoting whether the arrangement is valid or not.
Expected Time Complexity: O(N) where N is the length of S.
Expected Auxiliary Space: O(N) 
Constraints:
1 <= N <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string str your task is to complete the function spaceString which takes only one argument the string str and  finds all possible strings that can be made by placing spaces (zero or one) in between them. 
For eg .  for the string abc all valid strings will be
                abc
                ab c
                a bc
                a b c
Example 1:
Input:
str = abc
Output: abc$ab c$a bc$a b c$
Example 2:
Input:
str = xy
Output: xy$x y$
Your Task:
Complete the function spaceString() which takes a character array as an input parameter and returns list of all possible answers in lexographically reverse order(largest String first then smaller). The driver code will print the all possible answer '$' separated.
Expected Time Complexity: O(N * 2^{N})
Expected Auxiliary Space: O(N)
Constraints:
1<= length of string str <=10
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size *k*.

Now Marmot wonders in how many ways he can eat between *a* and *b* flowers. As the number of ways could be very large, print it modulo 1000000007 (109<=+<=7).

Input Specification:
Input contains several test cases.

The first line contains two integers *t* and *k* (1<=≤<=*t*,<=*k*<=≤<=105), where *t* represents the number of test cases.

The next *t* lines contain two integers *a**i* and *b**i* (1<=≤<=*a**i*<=≤<=*b**i*<=≤<=105), describing the *i*-th test.

Output Specification:
Print *t* lines to the standard output. The *i*-th line should contain the number of ways in which Marmot can eat between *a**i* and *b**i* flowers at dinner modulo 1000000007 (109<=+<=7).

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

Demo Output:
['6\n5\n5\n']

Note:
-  For *K* = 2 and length 1 Marmot can eat (*R*). -  For *K* = 2 and length 2 Marmot can eat (*RR*) and (*WW*). -  For *K* = 2 and length 3 Marmot can eat (*RRR*), (*RWW*) and (*WWR*). -  For *K* = 2 and length 4 Marmot can eat, for example, (*WWWW*) or (*RWWR*), but for example he can't eat (*WWWR*).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N ticket sellers where the ith ticket seller has A[i] tickets. 
The price of a ticket is the number of tickets remaining with the ticket seller. They are allowed to sell at most K tickets. Find the maximum amount they can earn by selling K tickets. 
The amount of tickets of each seller is provided in array A. Give the answer modulo 10^{9} + 7.
Example 1:
Input: N = 5, K = 3
A = {4, 3, 6, 2, 4}
Output: 15
Explaination: Consider 0 based indexing. 
For first two turns the 2nd seller sells. 
For the third turn either 0th or 2nd 
seller can sell. So the total becomes 
6 + 5 + 4 = 15.
Example 2:
Input: N = 6, K = 2
A = {5, 3, 5, 2, 4, 4}
Output: 10
Explaination: The turns are taken by 
0th and 2nd seller. 5 + 5 = 10 is the 
maximum amount.
Your Task:
You do not need to take input or print anything. Your task is to complete the function maxAmount() which takes N, K, and the array A as input parameters and returns the maximum amount they can get by selling K tickets.
Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i], K ≤ 10^{6}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ted has a pineapple. This pineapple is able to bark like a bulldog! At time *t* (in seconds) it barks for the first time. Then every *s* seconds after it, it barks twice with 1 second interval. Thus it barks at times *t*, *t*<=+<=*s*, *t*<=+<=*s*<=+<=1, *t*<=+<=2*s*, *t*<=+<=2*s*<=+<=1, etc.

Barney woke up in the morning and wants to eat the pineapple, but he can't eat it when it's barking. Barney plans to eat it at time *x* (in seconds), so he asked you to tell him if it's gonna bark at that time.

Input Specification:
The first and only line of input contains three integers *t*, *s* and *x* (0<=≤<=*t*,<=*x*<=≤<=109, 2<=≤<=*s*<=≤<=109) — the time the pineapple barks for the first time, the pineapple barking interval, and the time Barney wants to eat the pineapple respectively.

Output Specification:
Print a single "YES" (without quotes) if the pineapple will bark at time *x* or a single "NO" (without quotes) otherwise in the only line of output.

Demo Input:
['3 10 4\n', '3 10 3\n', '3 8 51\n', '3 8 52\n']

Demo Output:
['NO\n', 'YES\n', 'YES\n', 'YES\n']

Note:
In the first and the second sample cases pineapple will bark at moments 3, 13, 14, ..., so it won't bark at the moment 4 and will bark at the moment 3.

In the third and fourth sample cases pineapple will bark at moments 3, 11, 12, 19, 20, 27, 28, 35, 36, 43, 44, 51, 52, 59, ..., so it will bark at both moments 51 and 52.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a table G of size n × m such that G(i, j) = GCD(i, j) for all 1 ≤ i ≤ n, 1 ≤ j ≤ m. GCD(a, b) is the greatest common divisor of numbers a and b.

You have a sequence of positive integer numbers a_1, a_2, ..., a_{k}. We say that this sequence occurs in table G if it coincides with consecutive elements in some row, starting from some position. More formally, such numbers 1 ≤ i ≤ n and 1 ≤ j ≤ m - k + 1 should exist that G(i, j + l - 1) = a_{l} for all 1 ≤ l ≤ k.

Determine if the sequence a occurs in table G.


-----Input-----

The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 10^12; 1 ≤ k ≤ 10000). The second line contains k space-separated integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ 10^12).


-----Output-----

Print a single word "YES", if the given sequence occurs in table G, otherwise print "NO".


-----Examples-----
Input
100 100 5
5 2 1 2 1

Output
YES

Input
100 8 5
5 2 1 2 1

Output
NO

Input
100 100 7
1 2 3 4 5 6 7

Output
NO



-----Note-----

Sample 1. The tenth row of table G starts from sequence {1, 2, 1, 2, 5, 2, 1, 2, 1, 10}. As you can see, elements from fifth to ninth coincide with sequence a.

Sample 2. This time the width of table G equals 8. Sequence a doesn't occur there.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – .... 

We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.

Input

Only one line containing two positive integers a and b (1 ≤ a, b ≤ 109).

Output

Output the only line containing the answer. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 9. If there is no such x then output  - 1 as the answer.

Examples

Input

3 1


Output

1.000000000000


Input

1 3


Output

-1


Input

4 1


Output

1.250000000000

Note

You can see following graphs for sample 1 and sample 3. 

<image> <image>

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