meetforever/GRPO_CL huggingface dataset:
user: While Farmer John rebuilds his farm in an unfamiliar portion of Bovinia, Bessie is out trying some alternative jobs. In her new gig as a reporter, Bessie needs to know about programming competition results as quickly as possible. When she covers the 2016 Robot Rap Battle Tournament, she notices that all of the robots operate under deterministic algorithms. In particular, robot i will beat robot j if and only if robot i has a higher skill level than robot j. And if robot i beats robot j and robot j beats robot k, then robot i will beat robot k. Since rapping is such a subtle art, two robots can never have the same skill level.

Given the results of the rap battles in the order in which they were played, determine the minimum number of first rap battles that needed to take place before Bessie could order all of the robots by skill level.


-----Input-----

The first line of the input consists of two integers, the number of robots n (2 ≤ n ≤ 100 000) and the number of rap battles m ($1 \leq m \leq \operatorname{min}(100000, \frac{n(n - 1)}{2})$).

The next m lines describe the results of the rap battles in the order they took place. Each consists of two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}), indicating that robot u_{i} beat robot v_{i} in the i-th rap battle. No two rap battles involve the same pair of robots.

It is guaranteed that at least one ordering of the robots satisfies all m relations.


-----Output-----

Print the minimum k such that the ordering of the robots by skill level is uniquely defined by the first k rap battles. If there exists more than one ordering that satisfies all m relations, output -1.


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

Output
4

Input
3 2
1 2
3 2

Output
-1



-----Note-----

In the first sample, the robots from strongest to weakest must be (4, 2, 1, 3), which Bessie can deduce after knowing the results of the first four rap battles.

In the second sample, both (1, 3, 2) and (3, 1, 2) are possible orderings of the robots from strongest to weakest after both rap battles.
user: Berland National Library has recently been built in the capital of Berland. In addition, in the library you can take any of the collected works of Berland leaders, the library has a reading room.

Today was the pilot launch of an automated reading room visitors' accounting system! The scanner of the system is installed at the entrance to the reading room. It records the events of the form "reader entered room", "reader left room". Every reader is assigned a registration number during the registration procedure at the library — it's a unique integer from 1 to 10^6. Thus, the system logs events of two forms:  "+ r_{i}" — the reader with registration number r_{i} entered the room;  "- r_{i}" — the reader with registration number r_{i} left the room. 

The first launch of the system was a success, it functioned for some period of time, and, at the time of its launch and at the time of its shutdown, the reading room may already have visitors.

Significant funds of the budget of Berland have been spent on the design and installation of the system. Therefore, some of the citizens of the capital now demand to explain the need for this system and the benefits that its implementation will bring. Now, the developers of the system need to urgently come up with reasons for its existence.

Help the system developers to find the minimum possible capacity of the reading room (in visitors) using the log of the system available to you.


-----Input-----

The first line contains a positive integer n (1 ≤ n ≤ 100) — the number of records in the system log. Next follow n events from the system journal in the order in which the were made. Each event was written on a single line and looks as "+ r_{i}" or "- r_{i}", where r_{i} is an integer from 1 to 10^6, the registration number of the visitor (that is, distinct visitors always have distinct registration numbers).

It is guaranteed that the log is not contradictory, that is, for every visitor the types of any of his two consecutive events are distinct. Before starting the system, and after stopping the room may possibly contain visitors.


-----Output-----

Print a single integer — the minimum possible capacity of the reading room.


-----Examples-----
Input
6
+ 12001
- 12001
- 1
- 1200
+ 1
+ 7

Output
3
Input
2
- 1
- 2

Output
2
Input
2
+ 1
- 1

Output
1


-----Note-----

In the first sample test, the system log will ensure that at some point in the reading room were visitors with registration numbers 1, 1200 and 12001. More people were not in the room at the same time based on the log. Therefore, the answer to the test is 3.
user: Vus the Cossack has $n$ real numbers $a_i$. It is known that the sum of all numbers is equal to $0$. He wants to choose a sequence $b$ the size of which is $n$ such that the sum of all numbers is $0$ and each $b_i$ is either $\lfloor a_i \rfloor$ or $\lceil a_i \rceil$. In other words, $b_i$ equals $a_i$ rounded up or down. It is not necessary to round to the nearest integer.

For example, if $a = [4.58413, 1.22491, -2.10517, -3.70387]$, then $b$ can be equal, for example, to $[4, 2, -2, -4]$. 

Note that if $a_i$ is an integer, then there is no difference between $\lfloor a_i \rfloor$ and $\lceil a_i \rceil$, $b_i$ will always be equal to $a_i$.

Help Vus the Cossack find such sequence!


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 10^5$) — the number of numbers.

Each of the next $n$ lines contains one real number $a_i$ ($|a_i| < 10^5$). It is guaranteed that each $a_i$ has exactly $5$ digits after the decimal point. It is guaranteed that the sum of all the numbers is equal to $0$.


-----Output-----

In each of the next $n$ lines, print one integer $b_i$. For each $i$, $|a_i-b_i|<1$ must be met.

If there are multiple answers, print any.


-----Examples-----
Input
4
4.58413
1.22491
-2.10517
-3.70387

Output
4
2
-2
-4

Input
5
-6.32509
3.30066
-0.93878
2.00000
1.96321

Output
-6
3
-1
2
2



-----Note-----

The first example is explained in the legend.

In the second example, we can round the first and fifth numbers up, and the second and third numbers down. We can round the fourth number neither up, nor down.
user: There are n sharks who grow flowers for Wet Shark. They are all sitting around the table, such that sharks i and i + 1 are neighbours for all i from 1 to n - 1. Sharks n and 1 are neighbours too.

Each shark will grow some number of flowers s_{i}. For i-th shark value s_{i} is random integer equiprobably chosen in range from l_{i} to r_{i}. Wet Shark has it's favourite prime number p, and he really likes it! If for any pair of neighbouring sharks i and j the product s_{i}·s_{j} is divisible by p, then Wet Shark becomes happy and gives 1000 dollars to each of these sharks.

At the end of the day sharks sum all the money Wet Shark granted to them. Find the expectation of this value.


-----Input-----

The first line of the input contains two space-separated integers n and p (3 ≤ n ≤ 100 000, 2 ≤ p ≤ 10^9) — the number of sharks and Wet Shark's favourite prime number. It is guaranteed that p is prime.

The i-th of the following n lines contains information about i-th shark — two space-separated integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 10^9), the range of flowers shark i can produce. Remember that s_{i} is chosen equiprobably among all integers from l_{i} to r_{i}, inclusive.


-----Output-----

Print a single real number — the expected number of dollars that the sharks receive in total. You answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
3 2
1 2
420 421
420420 420421

Output
4500.0

Input
3 5
1 4
2 3
11 14

Output
0.0



-----Note-----

A prime number is a positive integer number that is divisible only by 1 and itself. 1 is not considered to be prime.

Consider the first sample. First shark grows some number of flowers from 1 to 2, second sharks grows from 420 to 421 flowers and third from 420420 to 420421. There are eight cases for the quantities of flowers (s_0, s_1, s_2) each shark grows: (1, 420, 420420): note that s_0·s_1 = 420, s_1·s_2 = 176576400, and s_2·s_0 = 420420. For each pair, 1000 dollars will be awarded to each shark. Therefore, each shark will be awarded 2000 dollars, for a total of 6000 dollars. (1, 420, 420421): now, the product s_2·s_0 is not divisible by 2. Therefore, sharks s_0 and s_2 will receive 1000 dollars, while shark s_1 will receive 2000. The total is 4000. (1, 421, 420420): total is 4000  (1, 421, 420421): total is 0.  (2, 420, 420420): total is 6000.  (2, 420, 420421): total is 6000.  (2, 421, 420420): total is 6000. (2, 421, 420421): total is 4000.

The expected value is $\frac{6000 + 4000 + 4000 + 0 + 6000 + 6000 + 6000 + 4000}{8} = 4500$.

In the second sample, no combination of quantities will garner the sharks any money.
user: Dima has a hamsters farm. Soon N hamsters will grow up on it and Dima will sell them in a city nearby.

Hamsters should be transported in boxes. If some box is not completely full, the hamsters in it are bored, that's why each box should be completely full with hamsters.

Dima can buy boxes at a factory. The factory produces boxes of K kinds, boxes of the i-th kind can contain in themselves a_{i} hamsters. Dima can buy any amount of boxes, but he should buy boxes of only one kind to get a wholesale discount.

Of course, Dima would buy boxes in such a way that each box can be completely filled with hamsters and transported to the city. If there is no place for some hamsters, Dima will leave them on the farm.

Find out how many boxes and of which type should Dima buy to transport maximum number of hamsters.


-----Input-----

The first line contains two integers N and K (0 ≤ N ≤ 10^18, 1 ≤ K ≤ 10^5) — the number of hamsters that will grow up on Dima's farm and the number of types of boxes that the factory produces.

The second line contains K integers a_1, a_2, ..., a_{K} (1 ≤ a_{i} ≤ 10^18 for all i) — the capacities of boxes.


-----Output-----

Output two integers: the type of boxes that Dima should buy and the number of boxes of that type Dima should buy. Types of boxes are numbered from 1 to K in the order they are given in input.

If there are many correct answers, output any of them.


-----Examples-----
Input
19 3
5 4 10

Output
2 4

Input
28 3
5 6 30

Output
1 5
user: There is a fence in front of Polycarpus's home. The fence consists of n planks of the same width which go one after another from left to right. The height of the i-th plank is h_{i} meters, distinct planks can have distinct heights. [Image] Fence for n = 7 and h = [1, 2, 6, 1, 1, 7, 1] 

Polycarpus has bought a posh piano and is thinking about how to get it into the house. In order to carry out his plan, he needs to take exactly k consecutive planks from the fence. Higher planks are harder to tear off the fence, so Polycarpus wants to find such k consecutive planks that the sum of their heights is minimal possible.

Write the program that finds the indexes of k consecutive planks with minimal total height. Pay attention, the fence is not around Polycarpus's home, it is in front of home (in other words, the fence isn't cyclic).


-----Input-----

The first line of the input contains integers n and k (1 ≤ n ≤ 1.5·10^5, 1 ≤ k ≤ n) — the number of planks in the fence and the width of the hole for the piano. The second line contains the sequence of integers h_1, h_2, ..., h_{n} (1 ≤ h_{i} ≤ 100), where h_{i} is the height of the i-th plank of the fence.


-----Output-----

Print such integer j that the sum of the heights of planks j, j + 1, ..., j + k - 1 is the minimum possible. If there are multiple such j's, print any of them.


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

Output
3



-----Note-----

In the sample, your task is to find three consecutive planks with the minimum sum of heights. In the given case three planks with indexes 3, 4 and 5 have the required attribute, their total height is 8.
user: The R1 company has recently bought a high rise building in the centre of Moscow for its main office. It's time to decorate the new office, and the first thing to do is to write the company's slogan above the main entrance to the building.

The slogan of the company consists of n characters, so the decorators hung a large banner, n meters wide and 1 meter high, divided into n equal squares. The first character of the slogan must be in the first square (the leftmost) of the poster, the second character must be in the second square, and so on.

Of course, the R1 programmers want to write the slogan on the poster themselves. To do this, they have a large (and a very heavy) ladder which was put exactly opposite the k-th square of the poster. To draw the i-th character of the slogan on the poster, you need to climb the ladder, standing in front of the i-th square of the poster. This action (along with climbing up and down the ladder) takes one hour for a painter. The painter is not allowed to draw characters in the adjacent squares when the ladder is in front of the i-th square because the uncomfortable position of the ladder may make the characters untidy. Besides, the programmers can move the ladder. In one hour, they can move the ladder either a meter to the right or a meter to the left.

Drawing characters and moving the ladder is very tiring, so the programmers want to finish the job in as little time as possible. Develop for them an optimal poster painting plan!


-----Input-----

The first line contains two integers, n and k (1 ≤ k ≤ n ≤ 100) — the number of characters in the slogan and the initial position of the ladder, correspondingly. The next line contains the slogan as n characters written without spaces. Each character of the slogan is either a large English letter, or digit, or one of the characters: '.', '!', ',', '?'.


-----Output-----

In t lines, print the actions the programmers need to make. In the i-th line print:  "LEFT" (without the quotes), if the i-th action was "move the ladder to the left";  "RIGHT" (without the quotes), if the i-th action was "move the ladder to the right";  "PRINT x" (without the quotes), if the i-th action was to "go up the ladder, paint character x, go down the ladder". 

The painting time (variable t) must be minimum possible. If there are multiple optimal painting plans, you can print any of them.


-----Examples-----
Input
2 2
R1

Output
PRINT 1
LEFT
PRINT R

Input
2 1
R1

Output
PRINT R
RIGHT
PRINT 1

Input
6 4
GO?GO!

Output
RIGHT
RIGHT
PRINT !
LEFT
PRINT O
LEFT
PRINT G
LEFT
PRINT ?
LEFT
PRINT O
LEFT
PRINT G



-----Note-----

Note that the ladder cannot be shifted by less than one meter. The ladder can only stand in front of some square of the poster. For example, you cannot shift a ladder by half a meter and position it between two squares. Then go up and paint the first character and the second character.
user: Chouti is working on a strange math problem.

There was a sequence of $n$ positive integers $x_1, x_2, \ldots, x_n$, where $n$ is even. The sequence was very special, namely for every integer $t$ from $1$ to $n$, $x_1+x_2+...+x_t$ is a square of some integer number (that is, a perfect square).

Somehow, the numbers with odd indexes turned to be missing, so he is only aware of numbers on even positions, i.e. $x_2, x_4, x_6, \ldots, x_n$. The task for him is to restore the original sequence. Again, it's your turn to help him.

The problem setter might make mistakes, so there can be no possible sequence at all. If there are several possible sequences, you can output any.


-----Input-----

The first line contains an even number $n$ ($2 \le n \le 10^5$).

The second line contains $\frac{n}{2}$ positive integers $x_2, x_4, \ldots, x_n$ ($1 \le x_i \le 2 \cdot 10^5$).


-----Output-----

If there are no possible sequence, print "No".

Otherwise, print "Yes" and then $n$ positive integers $x_1, x_2, \ldots, x_n$ ($1 \le x_i \le 10^{13}$), where $x_2, x_4, \ldots, x_n$ should be same as in input data. If there are multiple answers, print any.

Note, that the limit for $x_i$ is larger than for input data. It can be proved that in case there is an answer, there must be a possible sequence satisfying $1 \le x_i \le 10^{13}$.


-----Examples-----
Input
6
5 11 44

Output
Yes
4 5 16 11 64 44

Input
2
9900

Output
Yes
100 9900

Input
6
314 1592 6535

Output
No



-----Note-----

In the first example   $x_1=4$  $x_1+x_2=9$  $x_1+x_2+x_3=25$  $x_1+x_2+x_3+x_4=36$  $x_1+x_2+x_3+x_4+x_5=100$  $x_1+x_2+x_3+x_4+x_5+x_6=144$  All these numbers are perfect squares.

In the second example, $x_1=100$, $x_1+x_2=10000$. They are all perfect squares. There're other answers possible. For example, $x_1=22500$ is another answer.

In the third example, it is possible to show, that no such sequence exists.
user: You have a given integer $n$. Find the number of ways to fill all $3 \times n$ tiles with the shape described in the picture below. Upon filling, no empty spaces are allowed. Shapes cannot overlap. $\square$ This picture describes when $n = 4$. The left one is the shape and the right one is $3 \times n$ tiles. 


-----Input-----

The only line contains one integer $n$ ($1 \le n \le 60$) — the length.


-----Output-----

Print the number of ways to fill.


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

Output
4
Input
1

Output
0


-----Note-----

In the first example, there are $4$ possible cases of filling.

In the second example, you cannot fill the shapes in $3 \times 1$ tiles.
user: Stepan likes to repeat vowel letters when he writes words. For example, instead of the word "pobeda" he can write "pobeeeedaaaaa".

Sergey does not like such behavior, so he wants to write a program to format the words written by Stepan. This program must combine all consecutive equal vowels to a single vowel. The vowel letters are "a", "e", "i", "o", "u" and "y".

There are exceptions: if letters "e" or "o" repeat in a row exactly 2 times, like in words "feet" and "foot", the program must skip them and do not transform in one vowel. For example, the word "iiiimpleeemeentatiioon" must be converted to the word "implemeentatioon".

Sergey is very busy and asks you to help him and write the required program.


-----Input-----

The first line contains the integer n (1 ≤ n ≤ 100 000) — the number of letters in the word written by Stepan.

The second line contains the string s which has length that equals to n and contains only lowercase English letters — the word written by Stepan.


-----Output-----

Print the single string — the word written by Stepan converted according to the rules described in the statement.


-----Examples-----
Input
13
pobeeeedaaaaa

Output
pobeda

Input
22
iiiimpleeemeentatiioon

Output
implemeentatioon

Input
18
aeiouyaaeeiioouuyy

Output
aeiouyaeeioouy

Input
24
aaaoooiiiuuuyyyeeeggghhh

Output
aoiuyeggghhh
user: You are given two arrays of integers a and b. For each element of the second array b_{j} you should find the number of elements in array a that are less than or equal to the value b_{j}.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 2·10^5) — the sizes of arrays a and b.

The second line contains n integers — the elements of array a ( - 10^9 ≤ a_{i} ≤ 10^9).

The third line contains m integers — the elements of array b ( - 10^9 ≤ b_{j} ≤ 10^9).


-----Output-----

Print m integers, separated by spaces: the j-th of which is equal to the number of such elements in array a that are less than or equal to the value b_{j}.


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

Output
3 2 1 4

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

Output
4 2 4 2 5
user: Vova, the Ultimate Thule new shaman, wants to build a pipeline. As there are exactly n houses in Ultimate Thule, Vova wants the city to have exactly n pipes, each such pipe should be connected to the water supply. A pipe can be connected to the water supply if there's water flowing out of it. Initially Vova has only one pipe with flowing water. Besides, Vova has several splitters.

A splitter is a construction that consists of one input (it can be connected to a water pipe) and x output pipes. When a splitter is connected to a water pipe, water flows from each output pipe. You can assume that the output pipes are ordinary pipes. For example, you can connect water supply to such pipe if there's water flowing out from it. At most one splitter can be connected to any water pipe. [Image] The figure shows a 4-output splitter 

Vova has one splitter of each kind: with 2, 3, 4, ..., k outputs. Help Vova use the minimum number of splitters to build the required pipeline or otherwise state that it's impossible.

Vova needs the pipeline to have exactly n pipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.


-----Input-----

The first line contains two space-separated integers n and k (1 ≤ n ≤ 10^18, 2 ≤ k ≤ 10^9).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

Print a single integer — the minimum number of splitters needed to build the pipeline. If it is impossible to build a pipeline with the given splitters, print -1.


-----Examples-----
Input
4 3

Output
2

Input
5 5

Output
1

Input
8 4

Output
-1
user: While playing yet another strategy game, Mans has recruited $n$ Swedish heroes, whose powers which can be represented as an array $a$.

Unfortunately, not all of those mighty heroes were created as capable as he wanted, so that he decided to do something about it. In order to accomplish his goal, he can pick two consecutive heroes, with powers $a_i$ and $a_{i+1}$, remove them and insert a hero with power $-(a_i+a_{i+1})$ back in the same position. 

For example if the array contains the elements $[5, 6, 7, 8]$, he can pick $6$ and $7$ and get $[5, -(6+7), 8] = [5, -13, 8]$.

After he will perform this operation $n-1$ times, Mans will end up having only one hero. He wants his power to be as big as possible. What's the largest possible power he can achieve?


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 200000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — powers of the heroes.


-----Output-----

Print the largest possible power he can achieve after $n-1$ operations.


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

Output
26

Input
5
4 -5 9 -2 1

Output
15



-----Note-----

Suitable list of operations for the first sample:

$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$
user: You are given an undirected graph consisting of n vertices and $\frac{n(n - 1)}{2} - m$ edges. Instead of giving you the edges that exist in the graph, we give you m unordered pairs (x, y) such that there is no edge between x and y, and if some pair of vertices is not listed in the input, then there is an edge between these vertices.

You have to find the number of connected components in the graph and the size of each component. A connected component is a set of vertices X such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to X violates this rule.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 200000, $0 \leq m \leq \operatorname{min}(\frac{n(n - 1)}{2}, 200000)$).

Then m lines follow, each containing a pair of integers x and y (1 ≤ x, y ≤ n, x ≠ y) denoting that there is no edge between x and y. Each pair is listed at most once; (x, y) and (y, x) are considered the same (so they are never listed in the same test). If some pair of vertices is not listed in the input, then there exists an edge between those vertices. 


-----Output-----

Firstly print k — the number of connected components in this graph.

Then print k integers — the sizes of components. You should output these integers in non-descending order.


-----Example-----
Input
5 5
1 2
3 4
3 2
4 2
2 5

Output
2
1 4