meetforever/GRPO_CL huggingface dataset:
user: Saitama accidentally destroyed a hotel again. To repay the hotel company, Genos has volunteered to operate an elevator in one of its other hotels. The elevator is special — it starts on the top floor, can only move down, and has infinite capacity. Floors are numbered from 0 to s and elevator initially starts on floor s at time 0.

The elevator takes exactly 1 second to move down exactly 1 floor and negligible time to pick up passengers. Genos is given a list detailing when and on which floor passengers arrive. Please determine how long in seconds it will take Genos to bring all passengers to floor 0.


-----Input-----

The first line of input contains two integers n and s (1 ≤ n ≤ 100, 1 ≤ s ≤ 1000) — the number of passengers and the number of the top floor respectively.

The next n lines each contain two space-separated integers f_{i} and t_{i} (1 ≤ f_{i} ≤ s, 1 ≤ t_{i} ≤ 1000) — the floor and the time of arrival in seconds for the passenger number i.


-----Output-----

Print a single integer — the minimum amount of time in seconds needed to bring all the passengers to floor 0.


-----Examples-----
Input
3 7
2 1
3 8
5 2

Output
11

Input
5 10
2 77
3 33
8 21
9 12
10 64

Output
79



-----Note-----

In the first sample, it takes at least 11 seconds to bring all passengers to floor 0. Here is how this could be done:

1. Move to floor 5: takes 2 seconds.

2. Pick up passenger 3.

3. Move to floor 3: takes 2 seconds.

4. Wait for passenger 2 to arrive: takes 4 seconds.

5. Pick up passenger 2.

6. Go to floor 2: takes 1 second.

7. Pick up passenger 1.

8. Go to floor 0: takes 2 seconds.

This gives a total of 2 + 2 + 4 + 1 + 2 = 11 seconds.
user: There was an electronic store heist last night.

All keyboards which were in the store yesterday were numbered in ascending order from some integer number $x$. For example, if $x = 4$ and there were $3$ keyboards in the store, then the devices had indices $4$, $5$ and $6$, and if $x = 10$ and there were $7$ of them then the keyboards had indices $10$, $11$, $12$, $13$, $14$, $15$ and $16$.

After the heist, only $n$ keyboards remain, and they have indices $a_1, a_2, \dots, a_n$. Calculate the minimum possible number of keyboards that have been stolen. The staff remember neither $x$ nor the number of keyboards in the store before the heist.


-----Input-----

The first line contains single integer $n$ $(1 \le n \le 1\,000)$ — the number of  keyboards in the store that remained after the heist.

The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^{9})$ — the indices of the remaining keyboards. The integers $a_i$ are given in arbitrary order and are pairwise distinct.


-----Output-----

Print the minimum possible number of keyboards that have been stolen if the staff remember neither $x$ nor the number of keyboards in the store before the heist.


-----Examples-----
Input
4
10 13 12 8

Output
2

Input
5
7 5 6 4 8

Output
0



-----Note-----

In the first example, if $x=8$ then minimum number of stolen keyboards is equal to $2$. The keyboards with indices $9$ and $11$ were stolen during the heist.

In the second example, if $x=4$ then nothing was stolen during the heist.
user: There are n cities situated along the main road of Berland. Cities are represented by their coordinates — integer numbers a_1, a_2, ..., a_{n}. All coordinates are pairwise distinct.

It is possible to get from one city to another only by bus. But all buses and roads are very old, so the Minister of Transport decided to build a new bus route. The Minister doesn't want to spend large amounts of money — he wants to choose two cities in such a way that the distance between them is minimal possible. The distance between two cities is equal to the absolute value of the difference between their coordinates.

It is possible that there are multiple pairs of cities with minimal possible distance, so the Minister wants to know the quantity of such pairs. 

Your task is to write a program that will calculate the minimal possible distance between two pairs of cities and the quantity of pairs which have this distance.


-----Input-----

The first line contains one integer number n (2 ≤ n ≤ 2·10^5).

The second line contains n integer numbers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9). All numbers a_{i} are pairwise distinct.


-----Output-----

Print two integer numbers — the minimal distance and the quantity of pairs with this distance.


-----Examples-----
Input
4
6 -3 0 4

Output
2 1

Input
3
-2 0 2

Output
2 2



-----Note-----

In the first example the distance between the first city and the fourth city is |4 - 6| = 2, and it is the only pair with this distance.
user: Very soon there will be a parade of victory over alien invaders in Berland. Unfortunately, all soldiers died in the war and now the army consists of entirely new recruits, many of whom do not even know from which leg they should begin to march. The civilian population also poorly understands from which leg recruits begin to march, so it is only important how many soldiers march in step.

There will be n columns participating in the parade, the i-th column consists of l_{i} soldiers, who start to march from left leg, and r_{i} soldiers, who start to march from right leg.

The beauty of the parade is calculated by the following formula: if L is the total number of soldiers on the parade who start to march from the left leg, and R is the total number of soldiers on the parade who start to march from the right leg, so the beauty will equal |L - R|.

No more than once you can choose one column and tell all the soldiers in this column to switch starting leg, i.e. everyone in this columns who starts the march from left leg will now start it from right leg, and vice versa. Formally, you can pick no more than one index i and swap values l_{i} and r_{i}. 

Find the index of the column, such that switching the starting leg for soldiers in it will maximize the the beauty of the parade, or determine, that no such operation can increase the current beauty.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 10^5) — the number of columns. 

The next n lines contain the pairs of integers l_{i} and r_{i} (1 ≤ l_{i}, r_{i} ≤ 500) — the number of soldiers in the i-th column which start to march from the left or the right leg respectively.


-----Output-----

Print single integer k — the number of the column in which soldiers need to change the leg from which they start to march, or 0 if the maximum beauty is already reached.

Consider that columns are numbered from 1 to n in the order they are given in the input data.

If there are several answers, print any of them.


-----Examples-----
Input
3
5 6
8 9
10 3

Output
3

Input
2
6 5
5 6

Output
1

Input
6
5 9
1 3
4 8
4 5
23 54
12 32

Output
0



-----Note-----

In the first example if you don't give the order to change the leg, the number of soldiers, who start to march from the left leg, would equal 5 + 8 + 10 = 23, and from the right leg — 6 + 9 + 3 = 18. In this case the beauty of the parade will equal |23 - 18| = 5.

If you give the order to change the leg to the third column, so the number of soldiers, who march from the left leg, will equal 5 + 8 + 3 = 16, and who march from the right leg — 6 + 9 + 10 = 25. In this case the beauty equals |16 - 25| = 9.

It is impossible to reach greater beauty by giving another orders. Thus, the maximum beauty that can be achieved is 9.
user: You are given an array a with n elements. Each element of a is either 0 or 1.

Let's denote the length of the longest subsegment of consecutive elements in a, consisting of only numbers one, as f(a). You can change no more than k zeroes to ones to maximize f(a).


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 3·10^5, 0 ≤ k ≤ n) — the number of elements in a and the parameter k.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 1) — the elements of a.


-----Output-----

On the first line print a non-negative integer z — the maximal value of f(a) after no more than k changes of zeroes to ones.

On the second line print n integers a_{j} — the elements of the array a after the changes.

If there are multiple answers, you can print any one of them.


-----Examples-----
Input
7 1
1 0 0 1 1 0 1

Output
4
1 0 0 1 1 1 1

Input
10 2
1 0 0 1 0 1 0 1 0 1

Output
5
1 0 0 1 1 1 1 1 0 1
user: IA has so many colorful magnets on her fridge! Exactly one letter is written on each magnet, 'a' or 'b'. She loves to play with them, placing all magnets in a row. However, the girl is quickly bored and usually thinks how to make her entertainment more interesting.

Today, when IA looked at the fridge, she noticed that the word formed by magnets is really messy. "It would look much better when I'll swap some of them!" — thought the girl — "but how to do it?". After a while, she got an idea. IA will look at all prefixes with lengths from $1$ to the length of the word and for each prefix she will either reverse this prefix or leave it as it is. She will consider the prefixes in the fixed order: from the shortest to the largest. She wants to get the lexicographically smallest possible word after she considers all prefixes. Can you help her, telling which prefixes should be chosen for reversing?

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: $a$ is a prefix of $b$, but $a \ne b$; in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.


-----Input-----

The first and the only line contains a string $s$ ($1 \le |s| \le 1000$), describing the initial string formed by magnets. The string $s$ consists only of characters 'a' and 'b'.


-----Output-----

Output exactly $|s|$ integers. If IA should reverse the $i$-th prefix (that is, the substring from $1$ to $i$), the $i$-th integer should be equal to $1$, and it should be equal to $0$ otherwise.

If there are multiple possible sequences leading to the optimal answer, print any of them.


-----Examples-----
Input
bbab

Output
0 1 1 0

Input
aaaaa

Output
1 0 0 0 1



-----Note-----

In the first example, IA can reverse the second and the third prefix and get a string "abbb". She cannot get better result, since it is also lexicographically smallest string obtainable by permuting characters of the initial string.

In the second example, she can reverse any subset of prefixes — all letters are 'a'.
user: Petya has k matches, placed in n matchboxes lying in a line from left to right. We know that k is divisible by n. Petya wants all boxes to have the same number of matches inside. For that, he can move a match from its box to the adjacent one in one move. How many such moves does he need to achieve the desired configuration?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 50000). The second line contains n non-negative numbers that do not exceed 10^9, the i-th written number is the number of matches in the i-th matchbox. It is guaranteed that the total number of matches is divisible by n.


-----Output-----

Print the total minimum number of moves.


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

Output
12
user: Yaroslav has an array that consists of n integers. In one second Yaroslav can swap two neighboring array elements. Now Yaroslav is wondering if he can obtain an array where any two neighboring elements would be distinct in a finite time.

Help Yaroslav.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array. The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000) — the array elements.


-----Output-----

In the single line print "YES" (without the quotes) if Yaroslav can obtain the array he needs, and "NO" (without the quotes) otherwise.


-----Examples-----
Input
1
1

Output
YES

Input
3
1 1 2

Output
YES

Input
4
7 7 7 7

Output
NO



-----Note-----

In the first sample the initial array fits well.

In the second sample Yaroslav can get array: 1, 2, 1. He can swap the last and the second last elements to obtain it.

In the third sample Yarosav can't get the array he needs.
user: Notice that the memory limit is non-standard.

Recently Arthur and Sasha have studied correct bracket sequences. Arthur understood this topic perfectly and become so amazed about correct bracket sequences, so he even got himself a favorite correct bracket sequence of length 2n. Unlike Arthur, Sasha understood the topic very badly, and broke Arthur's favorite correct bracket sequence just to spite him.

All Arthur remembers about his favorite sequence is for each opening parenthesis ('(') the approximate distance to the corresponding closing one (')'). For the i-th opening bracket he remembers the segment [l_{i}, r_{i}], containing the distance to the corresponding closing bracket.

Formally speaking, for the i-th opening bracket (in order from left to right) we know that the difference of its position and the position of the corresponding closing bracket belongs to the segment [l_{i}, r_{i}].

Help Arthur restore his favorite correct bracket sequence!


-----Input-----

The first line contains integer n (1 ≤ n ≤ 600), the number of opening brackets in Arthur's favorite correct bracket sequence. 

Next n lines contain numbers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} < 2n), representing the segment where lies the distance from the i-th opening bracket and the corresponding closing one. 

The descriptions of the segments are given in the order in which the opening brackets occur in Arthur's favorite sequence if we list them from left to right.


-----Output-----

If it is possible to restore the correct bracket sequence by the given data, print any possible choice.

If Arthur got something wrong, and there are no sequences corresponding to the given information, print a single line "IMPOSSIBLE" (without the quotes).


-----Examples-----
Input
4
1 1
1 1
1 1
1 1

Output
()()()()

Input
3
5 5
3 3
1 1

Output
((()))

Input
3
5 5
3 3
2 2

Output
IMPOSSIBLE

Input
3
2 3
1 4
1 4

Output
(())()
user: The Little Girl loves problems on games very much. Here's one of them.

Two players have got a string s, consisting of lowercase English letters. They play a game that is described by the following rules:  The players move in turns; In one move the player can remove an arbitrary letter from string s.  If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins. A palindrome is a string that reads the same both ways (from left to right, and vice versa). For example, string "abba" is a palindrome and string "abc" isn't. 

Determine which player will win, provided that both sides play optimally well — the one who moves first or the one who moves second.


-----Input-----

The input contains a single line, containing string s (1 ≤ |s|  ≤  10^3). String s consists of lowercase English letters.


-----Output-----

In a single line print word "First" if the first player wins (provided that both players play optimally well). Otherwise, print word "Second". Print the words without the quotes.


-----Examples-----
Input
aba

Output
First

Input
abca

Output
Second
user: Today Patrick waits for a visit from his friend Spongebob. To prepare for the visit, Patrick needs to buy some goodies in two stores located near his house. There is a d_1 meter long road between his house and the first shop and a d_2 meter long road between his house and the second shop. Also, there is a road of length d_3 directly connecting these two shops to each other. Help Patrick calculate the minimum distance that he needs to walk in order to go to both shops and return to his house. [Image] 

Patrick always starts at his house. He should visit both shops moving only along the three existing roads and return back to his house. He doesn't mind visiting the same shop or passing the same road multiple times. The only goal is to minimize the total distance traveled.


-----Input-----

The first line of the input contains three integers d_1, d_2, d_3 (1 ≤ d_1, d_2, d_3 ≤ 10^8) — the lengths of the paths.   d_1 is the length of the path connecting Patrick's house and the first shop;  d_2 is the length of the path connecting Patrick's house and the second shop;  d_3 is the length of the path connecting both shops. 


-----Output-----

Print the minimum distance that Patrick will have to walk in order to visit both shops and return to his house.


-----Examples-----
Input
10 20 30

Output
60

Input
1 1 5

Output
4



-----Note-----

The first sample is shown on the picture in the problem statement. One of the optimal routes is: house $\rightarrow$ first shop $\rightarrow$ second shop $\rightarrow$ house.

In the second sample one of the optimal routes is: house $\rightarrow$ first shop $\rightarrow$ house $\rightarrow$ second shop $\rightarrow$ house.
user: Little boy Valera studies an algorithm of sorting an integer array. After studying the theory, he went on to the practical tasks. As a result, he wrote a program that sorts an array of n integers a_1, a_2, ..., a_{n} in the non-decreasing order. The pseudocode of the program, written by Valera, is given below. The input of the program gets number n and array a.

loop integer variable i from 1 to n - 1

    loop integer variable j from i to n - 1

        if (a_{j} > a_{j} + 1), then swap the values of elements a_{j} and a_{j} + 1



But Valera could have made a mistake, because he hasn't yet fully learned the sorting algorithm. If Valera made a mistake in his program, you need to give a counter-example that makes his program work improperly (that is, the example that makes the program sort the array not in the non-decreasing order). If such example for the given value of n doesn't exist, print -1.


-----Input-----

You've got a single integer n (1 ≤ n ≤ 50) — the size of the sorted array.


-----Output-----

Print n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100) — the counter-example, for which Valera's algorithm won't work correctly. If the counter-example that meets the described conditions is impossible to give, print -1.

If there are several counter-examples, consisting of n numbers, you are allowed to print any of them.


-----Examples-----
Input
1

Output
-1
user: Bizon the Champion isn't just attentive, he also is very hardworking.

Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height of a_{i} meters.

Bizon the Champion bought a brush in the shop, the brush's width is 1 meter. He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 5000) — the number of fence planks. The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single integer — the minimum number of strokes needed to paint the whole fence.


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

Output
3

Input
2
2 2

Output
2

Input
1
5

Output
1



-----Note-----

In the first sample you need to paint the fence in three strokes with the brush: the first stroke goes on height 1 horizontally along all the planks. The second stroke goes on height 2 horizontally and paints the first and second planks and the third stroke (it can be horizontal and vertical) finishes painting the fourth plank.

In the second sample you can paint the fence with two strokes, either two horizontal or two vertical strokes.

In the third sample there is only one plank that can be painted using a single vertical stroke.
user: Recently Irina arrived to one of the most famous cities of Berland — the Berlatov city. There are n showplaces in the city, numbered from 1 to n, and some of them are connected by one-directional roads. The roads in Berlatov are designed in a way such that there are no cyclic routes between showplaces.

Initially Irina stands at the showplace 1, and the endpoint of her journey is the showplace n. Naturally, Irina wants to visit as much showplaces as she can during her journey. However, Irina's stay in Berlatov is limited and she can't be there for more than T time units.

Help Irina determine how many showplaces she may visit during her journey from showplace 1 to showplace n within a time not exceeding T. It is guaranteed that there is at least one route from showplace 1 to showplace n such that Irina will spend no more than T time units passing it.


-----Input-----

The first line of the input contains three integers n, m and T (2 ≤ n ≤ 5000,  1 ≤ m ≤ 5000,  1 ≤ T ≤ 10^9) — the number of showplaces, the number of roads between them and the time of Irina's stay in Berlatov respectively.

The next m lines describes roads in Berlatov. i-th of them contains 3 integers u_{i}, v_{i}, t_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}, 1 ≤ t_{i} ≤ 10^9), meaning that there is a road starting from showplace u_{i} and leading to showplace v_{i}, and Irina spends t_{i} time units to pass it. It is guaranteed that the roads do not form cyclic routes.

It is guaranteed, that there is at most one road between each pair of showplaces.


-----Output-----

Print the single integer k (2 ≤ k ≤ n) — the maximum number of showplaces that Irina can visit during her journey from showplace 1 to showplace n within time not exceeding T, in the first line.

Print k distinct integers in the second line — indices of showplaces that Irina will visit on her route, in the order of encountering them.

If there are multiple answers, print any of them.


-----Examples-----
Input
4 3 13
1 2 5
2 3 7
2 4 8

Output
3
1 2 4 

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

Output
4
1 2 4 6 

Input
5 5 6
1 3 3
3 5 3
1 2 2
2 4 3
4 5 2

Output
3
1 3 5
user: Roma works in a company that sells TVs. Now he has to prepare a report for the last year.

Roma has got a list of the company's incomes. The list is a sequence that consists of n integers. The total income of the company is the sum of all integers in sequence. Roma decided to perform exactly k changes of signs of several numbers in the sequence. He can also change the sign of a number one, two or more times.

The operation of changing a number's sign is the operation of multiplying this number by -1.

Help Roma perform the changes so as to make the total income of the company (the sum of numbers in the resulting sequence) maximum. Note that Roma should perform exactly k changes.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 10^5), showing, how many numbers are in the sequence and how many swaps are to be made.

The second line contains a non-decreasing sequence, consisting of n integers a_{i} (|a_{i}| ≤ 10^4).

The numbers in the lines are separated by single spaces. Please note that the given sequence is sorted in non-decreasing order.


-----Output-----

In the single line print the answer to the problem — the maximum total income that we can obtain after exactly k changes.


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

Output
3

Input
3 1
-1 -1 1

Output
1



-----Note-----

In the first sample we can get sequence [1, 1, 1], thus the total income equals 3.

In the second test, the optimal strategy is to get sequence [-1, 1, 1], thus the total income equals 1.