meetforever/GRPO_CL huggingface dataset:
user: The Fair Nut likes kvass very much. On his birthday parents presented him $n$ kegs of kvass. There are $v_i$ liters of kvass in the $i$-th keg. Each keg has a lever. You can pour your glass by exactly $1$ liter pulling this lever. The Fair Nut likes this drink very much, so he wants to pour his glass by $s$ liters of kvass. But he wants to do it, so kvass level in the least keg is as much as possible.

Help him find out how much kvass can be in the least keg or define it's not possible to pour his glass by $s$ liters of kvass.


-----Input-----

The first line contains two integers $n$ and $s$ ($1 \le n \le 10^3$, $1 \le s \le 10^{12}$) — the number of kegs and glass volume.

The second line contains $n$ integers $v_1, v_2, \ldots, v_n$ ($1 \le v_i \le 10^9$) — the volume of $i$-th keg.


-----Output-----

If the Fair Nut cannot pour his glass by $s$ liters of kvass, print $-1$. Otherwise, print a single integer — how much kvass in the least keg can be.


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

Output
3

Input
3 4
5 3 4

Output
2

Input
3 7
1 2 3

Output
-1



-----Note-----

In the first example, the answer is $3$, the Fair Nut can take $1$ liter from the first keg and $2$ liters from the third keg. There are $3$ liters of kvass in each keg.

In the second example, the answer is $2$, the Fair Nut can take $3$ liters from the first keg and $1$ liter from the second keg.

In the third example, the Fair Nut can't pour his cup by $7$ liters, so the answer is $-1$.
user: The 9-th grade student Gabriel noticed a caterpillar on a tree when walking around in a forest after the classes. The caterpillar was on the height h_1 cm from the ground. On the height h_2 cm (h_2 > h_1) on the same tree hung an apple and the caterpillar was crawling to the apple.

Gabriel is interested when the caterpillar gets the apple. He noted that the caterpillar goes up by a cm per hour by day and slips down by b cm per hour by night.

In how many days Gabriel should return to the forest to see the caterpillar get the apple. You can consider that the day starts at 10 am and finishes at 10 pm. Gabriel's classes finish at 2 pm. You can consider that Gabriel noticed the caterpillar just after the classes at 2 pm.

Note that the forest is magic so the caterpillar can slip down under the ground and then lift to the apple.


-----Input-----

The first line contains two integers h_1, h_2 (1 ≤ h_1 < h_2 ≤ 10^5) — the heights of the position of the caterpillar and the apple in centimeters.

The second line contains two integers a, b (1 ≤ a, b ≤ 10^5) — the distance the caterpillar goes up by day and slips down by night, in centimeters per hour.


-----Output-----

Print the only integer k — the number of days Gabriel should wait to return to the forest and see the caterpillar getting the apple.

If the caterpillar can't get the apple print the only integer  - 1.


-----Examples-----
Input
10 30
2 1

Output
1

Input
10 13
1 1

Output
0

Input
10 19
1 2

Output
-1

Input
1 50
5 4

Output
1



-----Note-----

In the first example at 10 pm of the first day the caterpillar gets the height 26. At 10 am of the next day it slips down to the height 14. And finally at 6 pm of the same day the caterpillar gets the apple.

Note that in the last example the caterpillar was slipping down under the ground and getting the apple on the next day.
user: A sweet little monster Om Nom loves candies very much. One day he found himself in a rather tricky situation that required him to think a bit in order to enjoy candies the most. Would you succeed with the same task if you were on his place? [Image] 

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

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


-----Input-----

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


-----Output-----

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


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

Output
16



-----Note-----

In the sample test Om Nom can eat two candies of each type and thus get 16 joy units.
user: Professor GukiZ makes a new robot. The robot are in the point with coordinates (x_1, y_1) and should go to the point (x_2, y_2). In a single step the robot can change any of its coordinates (maybe both of them) by one (decrease or increase). So the robot can move in one of the 8 directions. Find the minimal number of steps the robot should make to get the finish position.


-----Input-----

The first line contains two integers x_1, y_1 ( - 10^9 ≤ x_1, y_1 ≤ 10^9) — the start position of the robot.

The second line contains two integers x_2, y_2 ( - 10^9 ≤ x_2, y_2 ≤ 10^9) — the finish position of the robot.


-----Output-----

Print the only integer d — the minimal number of steps to get the finish position.


-----Examples-----
Input
0 0
4 5

Output
5

Input
3 4
6 1

Output
3



-----Note-----

In the first example robot should increase both of its coordinates by one four times, so it will be in position (4, 4). After that robot should simply increase its y coordinate and get the finish position.

In the second example robot should simultaneously increase x coordinate and decrease y coordinate by one three times.
user: There are n employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.

Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated:   Each of n employees makes a statement. They make statements one by one starting from employees 1 and finishing with employee n. If at the moment when it's time for the i-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting).  When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It's allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end.  When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with n who are still eligible to vote make their statements.  The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction. 

You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of employees. 

The next line contains n characters. The i-th character is 'D' if the i-th employee is from depublicans fraction or 'R' if he is from remocrats.


-----Output-----

Print 'D' if the outcome of the vote will be suitable for depublicans and 'R' if remocrats will win.


-----Examples-----
Input
5
DDRRR

Output
D

Input
6
DDRRRR

Output
R



-----Note-----

Consider one of the voting scenarios for the first sample:   Employee 1 denies employee 5 to vote.  Employee 2 denies employee 3 to vote.  Employee 3 has no right to vote and skips his turn (he was denied by employee 2).  Employee 4 denies employee 2 to vote.  Employee 5 has no right to vote and skips his turn (he was denied by employee 1).  Employee 1 denies employee 4.  Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.
user: Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than $a$ and screen height not greater than $b$. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is $w$, and the height of the screen is $h$, then the following condition should be met: $\frac{w}{h} = \frac{x}{y}$.

There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers $w$ and $h$ there is a TV set with screen width $w$ and height $h$ in the shop.

Monocarp isn't ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers $w$ and $h$, beforehand, such that $(w \le a)$, $(h \le b)$ and $(\frac{w}{h} = \frac{x}{y})$.

In other words, Monocarp wants to determine the number of TV sets having aspect ratio $\frac{x}{y}$, screen width not exceeding $a$, and screen height not exceeding $b$. Two TV sets are considered different if they have different screen width or different screen height.


-----Input-----

The first line contains four integers $a$, $b$, $x$, $y$ ($1 \le a, b, x, y \le 10^{18}$) — the constraints on the screen width and height, and on the aspect ratio.


-----Output-----

Print one integer — the number of different variants to choose TV screen width and screen height so that they meet the aforementioned constraints.


-----Examples-----
Input
17 15 5 3

Output
3

Input
14 16 7 22

Output
0

Input
4 2 6 4

Output
1

Input
1000000000000000000 1000000000000000000 999999866000004473 999999822000007597

Output
1000000063



-----Note-----

In the first example, there are $3$ possible variants: $(5, 3)$, $(10, 6)$, $(15, 9)$.

In the second example, there is no TV set meeting the constraints.

In the third example, there is only one variant: $(3, 2)$.
user: The number "zero" is called "love" (or "l'oeuf" to be precise, literally means "egg" in French), for example when denoting the zero score in a game of tennis. 

Aki is fond of numbers, especially those with trailing zeros. For example, the number $9200$ has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers $n$ and $b$ (in decimal notation), your task is to calculate the number of trailing zero digits in the $b$-ary (in the base/radix of $b$) representation of $n\,!$ (factorial of $n$). 


-----Input-----

The only line of the input contains two integers $n$ and $b$ ($1 \le n \le 10^{18}$, $2 \le b \le 10^{12}$).


-----Output-----

Print an only integer — the number of trailing zero digits in the $b$-ary representation of $n!$


-----Examples-----
Input
6 9

Output
1

Input
38 11

Output
3

Input
5 2

Output
3

Input
5 10

Output
1



-----Note-----

In the first example, $6!_{(10)} = 720_{(10)} = 880_{(9)}$.

In the third and fourth example, $5!_{(10)} = 120_{(10)} = 1111000_{(2)}$.

The representation of the number $x$ in the $b$-ary base is $d_1, d_2, \ldots, d_k$ if $x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$, where $d_i$ are integers and $0 \le d_i \le b - 1$. For example, the number $720$ from the first example is represented as $880_{(9)}$ since $720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$.

You can read more about bases here.
user: A frog is initially at position $0$ on the number line. The frog has two positive integers $a$ and $b$. From a position $k$, it can either jump to position $k+a$ or $k-b$.

Let $f(x)$ be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval $[0, x]$. The frog doesn't need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from $0$.

Given an integer $m$, find $\sum_{i=0}^{m} f(i)$. That is, find the sum of all $f(i)$ for $i$ from $0$ to $m$.


-----Input-----

The first line contains three integers $m, a, b$ ($1 \leq m \leq 10^9, 1 \leq a,b \leq 10^5$).


-----Output-----

Print a single integer, the desired sum.


-----Examples-----
Input
7 5 3

Output
19

Input
1000000000 1 2019

Output
500000001500000001

Input
100 100000 1

Output
101

Input
6 4 5

Output
10



-----Note-----

In the first example, we must find $f(0)+f(1)+\ldots+f(7)$. We have $f(0) = 1, f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3, f(6) = 3, f(7) = 8$. The sum of these values is $19$.

In the second example, we have $f(i) = i+1$, so we want to find $\sum_{i=0}^{10^9} i+1$.

In the third example, the frog can't make any jumps in any case.
user: Where do odds begin, and where do they end? Where does hope emerge, and will they ever break?

Given an integer sequence a_1, a_2, ..., a_{n} of length n. Decide whether it is possible to divide it into an odd number of non-empty subsegments, the each of which has an odd length and begins and ends with odd numbers.

A subsegment is a contiguous slice of the whole sequence. For example, {3, 4, 5} and {1} are subsegments of sequence {1, 2, 3, 4, 5, 6}, while {1, 2, 4} and {7} are not.


-----Input-----

The first line of input contains a non-negative integer n (1 ≤ n ≤ 100) — the length of the sequence.

The second line contains n space-separated non-negative integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 100) — the elements of the sequence.


-----Output-----

Output "Yes" if it's possible to fulfill the requirements, and "No" otherwise.

You can output each letter in any case (upper or lower).


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

Output
Yes

Input
5
1 0 1 5 1

Output
Yes

Input
3
4 3 1

Output
No

Input
4
3 9 9 3

Output
No



-----Note-----

In the first example, divide the sequence into 1 subsegment: {1, 3, 5} and the requirements will be met.

In the second example, divide the sequence into 3 subsegments: {1, 0, 1}, {5}, {1}.

In the third example, one of the subsegments must start with 4 which is an even number, thus the requirements cannot be met.

In the fourth example, the sequence can be divided into 2 subsegments: {3, 9, 9}, {3}, but this is not a valid solution because 2 is an even number.
user: Pashmak has fallen in love with an attractive girl called Parmida since one year ago...

Today, Pashmak set up a meeting with his partner in a romantic garden. Unfortunately, Pashmak has forgotten where the garden is. But he remembers that the garden looks like a square with sides parallel to the coordinate axes. He also remembers that there is exactly one tree on each vertex of the square. Now, Pashmak knows the position of only two of the trees. Help him to find the position of two remaining ones.


-----Input-----

The first line contains four space-separated x_1, y_1, x_2, y_2 ( - 100 ≤ x_1, y_1, x_2, y_2 ≤ 100) integers, where x_1 and y_1 are coordinates of the first tree and x_2 and y_2 are coordinates of the second tree. It's guaranteed that the given points are distinct.


-----Output-----

If there is no solution to the problem, print -1. Otherwise print four space-separated integers x_3, y_3, x_4, y_4 that correspond to the coordinates of the two other trees. If there are several solutions you can output any of them. 

Note that x_3, y_3, x_4, y_4 must be in the range ( - 1000 ≤ x_3, y_3, x_4, y_4 ≤ 1000).


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

Output
1 0 1 1

Input
0 0 1 1

Output
0 1 1 0

Input
0 0 1 2

Output
-1
user: Jzzhu has invented a kind of sequences, they meet the following property:$f_{1} = x ; f_{2} = y ; \forall i(i \geq 2), f_{i} = f_{i - 1} + f_{i + 1}$

You are given x and y, please calculate f_{n} modulo 1000000007 (10^9 + 7).


-----Input-----

The first line contains two integers x and y (|x|, |y| ≤ 10^9). The second line contains a single integer n (1 ≤ n ≤ 2·10^9).


-----Output-----

Output a single integer representing f_{n} modulo 1000000007 (10^9 + 7).


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

Output
1

Input
0 -1
2

Output
1000000006



-----Note-----

In the first sample, f_2 = f_1 + f_3, 3 = 2 + f_3, f_3 = 1.

In the second sample, f_2 =  - 1;  - 1 modulo (10^9 + 7) equals (10^9 + 6).
user: One spring day on his way to university Lesha found an array A. Lesha likes to split arrays into several parts. This time Lesha decided to split the array A into several, possibly one, new arrays so that the sum of elements in each of the new arrays is not zero. One more condition is that if we place the new arrays one after another they will form the old array A.

Lesha is tired now so he asked you to split the array. Help Lesha!


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 100) — the number of elements in the array A.

The next line contains n integers a_1, a_2, ..., a_{n} ( - 10^3 ≤ a_{i} ≤ 10^3) — the elements of the array A.


-----Output-----

If it is not possible to split the array A and satisfy all the constraints, print single line containing "NO" (without quotes).

Otherwise in the first line print "YES" (without quotes). In the next line print single integer k — the number of new arrays. In each of the next k lines print two integers l_{i} and r_{i} which denote the subarray A[l_{i}... r_{i}] of the initial array A being the i-th new array. Integers l_{i}, r_{i} should satisfy the following conditions:  l_1 = 1  r_{k} = n  r_{i} + 1 = l_{i} + 1 for each 1 ≤ i < k. 

If there are multiple answers, print any of them.


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

Output
YES
2
1 2
3 3

Input
8
9 -12 3 4 -4 -10 7 3

Output
YES
2
1 2
3 8

Input
1
0

Output
NO

Input
4
1 2 3 -5

Output
YES
4
1 1
2 2
3 3
4 4
user: Manao is taking part in a quiz. The quiz consists of n consecutive questions. A correct answer gives one point to the player. The game also has a counter of consecutive correct answers. When the player answers a question correctly, the number on this counter increases by 1. If the player answers a question incorrectly, the counter is reset, that is, the number on it reduces to 0. If after an answer the counter reaches the number k, then it is reset, and the player's score is doubled. Note that in this case, first 1 point is added to the player's score, and then the total score is doubled. At the beginning of the game, both the player's score and the counter of consecutive correct answers are set to zero.

Manao remembers that he has answered exactly m questions correctly. But he does not remember the order in which the questions came. He's trying to figure out what his minimum score may be. Help him and compute the remainder of the corresponding number after division by 1000000009 (10^9 + 9).


-----Input-----

The single line contains three space-separated integers n, m and k (2 ≤ k ≤ n ≤ 10^9; 0 ≤ m ≤ n).


-----Output-----

Print a single integer — the remainder from division of Manao's minimum possible score in the quiz by 1000000009 (10^9 + 9).


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

Output
3

Input
5 4 2

Output
6



-----Note-----

Sample 1. Manao answered 3 questions out of 5, and his score would double for each two consecutive correct answers. If Manao had answered the first, third and fifth questions, he would have scored as much as 3 points.

Sample 2. Now Manao answered 4 questions. The minimum possible score is obtained when the only wrong answer is to the question 4.

Also note that you are asked to minimize the score and not the remainder of the score modulo 1000000009. For example, if Manao could obtain either 2000000000 or 2000000020 points, the answer is 2000000000 mod 1000000009, even though 2000000020 mod 1000000009 is a smaller number.
user: You are given a non-negative integer n, its decimal representation consists of at most 100 digits and doesn't contain leading zeroes.

Your task is to determine if it is possible in this case to remove some of the digits (possibly not remove any digit at all) so that the result contains at least one digit, forms a non-negative integer, doesn't have leading zeroes and is divisible by 8. After the removing, it is forbidden to rearrange the digits.

If a solution exists, you should print it.


-----Input-----

The single line of the input contains a non-negative integer n. The representation of number n doesn't contain any leading zeroes and its length doesn't exceed 100 digits. 


-----Output-----

Print "NO" (without quotes), if there is no such way to remove some digits from number n. 

Otherwise, print "YES" in the first line and the resulting number after removing digits from number n in the second line. The printed number must be divisible by 8.

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


-----Examples-----
Input
3454

Output
YES
344

Input
10

Output
YES
0

Input
111111

Output
NO
user: In a building where Polycarp lives there are equal number of flats on each floor. Unfortunately, Polycarp don't remember how many flats are on each floor, but he remembers that the flats are numbered from 1 from lower to upper floors. That is, the first several flats are on the first floor, the next several flats are on the second and so on. Polycarp don't remember the total number of flats in the building, so you can consider the building to be infinitely high (i.e. there are infinitely many floors). Note that the floors are numbered from 1.

Polycarp remembers on which floors several flats are located. It is guaranteed that this information is not self-contradictory. It means that there exists a building with equal number of flats on each floor so that the flats from Polycarp's memory have the floors Polycarp remembers.

Given this information, is it possible to restore the exact floor for flat n? 


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 100), where n is the number of the flat you need to restore floor for, and m is the number of flats in Polycarp's memory.

m lines follow, describing the Polycarp's memory: each of these lines contains a pair of integers k_{i}, f_{i} (1 ≤ k_{i} ≤ 100, 1 ≤ f_{i} ≤ 100), which means that the flat k_{i} is on the f_{i}-th floor. All values k_{i} are distinct.

It is guaranteed that the given information is not self-contradictory.


-----Output-----

Print the number of the floor in which the n-th flat is located, if it is possible to determine it in a unique way. Print -1 if it is not possible to uniquely restore this floor.


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

Output
4

Input
8 4
3 1
6 2
5 2
2 1

Output
-1



-----Note-----

In the first example the 6-th flat is on the 2-nd floor, while the 7-th flat is on the 3-rd, so, the 6-th flat is the last on its floor and there are 3 flats on each floor. Thus, the 10-th flat is on the 4-th floor.

In the second example there can be 3 or 4 flats on each floor, so we can't restore the floor for the 8-th flat.