meetforever/GRPO_CL huggingface dataset:
user: Arkadiy has lots square photos with size a × a. He wants to put some of them on a rectangular wall with size h × w. 

The photos which Arkadiy will put on the wall must form a rectangular grid and the distances between neighboring vertically and horizontally photos and also the distances between outside rows and columns of photos to the nearest bound of the wall must be equal to x, where x is some non-negative real number. Look on the picture below for better understanding of the statement.

 [Image] 

Arkadiy haven't chosen yet how many photos he would put on the wall, however, he want to put at least one photo. Your task is to determine the minimum value of x which can be obtained after putting photos, or report that there is no way to put positive number of photos and satisfy all the constraints. Suppose that Arkadiy has enough photos to make any valid arrangement according to the constraints.

Note that Arkadiy wants to put at least one photo on the wall. The photos should not overlap, should completely lie inside the wall bounds and should have sides parallel to the wall sides.


-----Input-----

The first line contains three integers a, h and w (1 ≤ a, h, w ≤ 10^9) — the size of photos and the height and the width of the wall.


-----Output-----

Print one non-negative real number — the minimum value of x which can be obtained after putting the photos on the wall. The absolute or the relative error of the answer must not exceed 10^{ - 6}.

Print -1 if there is no way to put positive number of photos and satisfy the constraints.


-----Examples-----
Input
2 18 13

Output
0.5

Input
4 4 4

Output
0

Input
3 4 3

Output
-1



-----Note-----

In the first example Arkadiy can put 7 rows of photos with 5 photos in each row, so the minimum value of x equals to 0.5.

In the second example Arkadiy can put only 1 photo which will take the whole wall, so the minimum value of x equals to 0.

In the third example there is no way to put positive number of photos and satisfy the constraints described in the statement, so the answer is -1.
user: After lessons Nastya decided to read a book. The book contains $n$ chapters, going one after another, so that one page of the book belongs to exactly one chapter and each chapter contains at least one page.

Yesterday evening Nastya did not manage to finish reading the book, so she marked the page with number $k$ as the first page which was not read (i.e. she read all pages from the $1$-st to the $(k-1)$-th).

The next day Nastya's friend Igor came and asked her, how many chapters remain to be read by Nastya? Nastya is too busy now, so she asks you to compute the number of chapters she has not completely read yet (i.e. the number of chapters she has not started to read or has finished reading somewhere in the middle).


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 100$) — the number of chapters in the book.

There are $n$ lines then. The $i$-th of these lines contains two integers $l_i$, $r_i$ separated by space ($l_1 = 1$, $l_i \leq r_i$) — numbers of the first and the last pages of the $i$-th chapter. It's guaranteed that $l_{i+1} = r_i + 1$ for all $1 \leq i \leq n-1$, and also that every chapter contains at most $100$ pages.

The $(n+2)$-th line contains a single integer $k$ ($1 \leq k \leq r_n$) — the index of the marked page. 


-----Output-----

Print a single integer — the number of chapters which has not been completely read so far.


-----Examples-----
Input
3
1 3
4 7
8 11
2

Output
3

Input
3
1 4
5 9
10 12
9

Output
2

Input
1
1 7
4

Output
1



-----Note-----

In the first example the book contains $11$ pages and $3$ chapters — $[1;3]$, $[4;7]$ and $[8;11]$. Nastya marked the $2$-nd page, so she finished in the middle of the $1$-st chapter. So, all chapters has not been read so far, so the answer is $3$.

The book in the second example contains $12$ pages and $3$ chapters too, but Nastya finished reading in the middle of the $2$-nd chapter, so that the answer is $2$.
user: A large banner with word CODEFORCES was ordered for the 1000-th onsite round of Codeforces^{ω} that takes place on the Miami beach. Unfortunately, the company that made the banner mixed up two orders and delivered somebody else's banner that contains someone else's word. The word on the banner consists only of upper-case English letters.

There is very little time to correct the mistake. All that we can manage to do is to cut out some substring from the banner, i.e. several consecutive letters. After that all the resulting parts of the banner will be glued into a single piece (if the beginning or the end of the original banner was cut out, only one part remains); it is not allowed change the relative order of parts of the banner (i.e. after a substring is cut, several first and last letters are left, it is allowed only to glue the last letters to the right of the first letters). Thus, for example, for example, you can cut a substring out from string 'TEMPLATE' and get string 'TEMPLE' (if you cut out string AT), 'PLATE' (if you cut out TEM), 'T' (if you cut out EMPLATE), etc.

Help the organizers of the round determine whether it is possible to cut out of the banner some substring in such a way that the remaining parts formed word CODEFORCES.


-----Input-----

The single line of the input contains the word written on the banner. The word only consists of upper-case English letters. The word is non-empty and its length doesn't exceed 100 characters. It is guaranteed that the word isn't word CODEFORCES.


-----Output-----

Print 'YES', if there exists a way to cut out the substring, and 'NO' otherwise (without the quotes).


-----Examples-----
Input
CODEWAITFORITFORCES

Output
YES

Input
BOTTOMCODER

Output
NO

Input
DECODEFORCES

Output
YES

Input
DOGEFORCES

Output
NO
user: You are given a regular polygon with $n$ vertices labeled from $1$ to $n$ in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there is no pair of triangles such that their intersection has non-zero area, and the total area of all triangles is equal to the area of the given polygon. The weight of a triangulation is the sum of weigths of triangles it consists of, where the weight of a triagle is denoted as the product of labels of its vertices.

Calculate the minimum weight among all triangulations of the polygon.


-----Input-----

The first line contains single integer $n$ ($3 \le n \le 500$) — the number of vertices in the regular polygon.


-----Output-----

Print one integer — the minimum weight among all triangulations of the given polygon.


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

Output
6

Input
4

Output
18



-----Note-----

According to Wiki: polygon triangulation is the decomposition of a polygonal area (simple polygon) $P$ into a set of triangles, i. e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$.

In the first example the polygon is a triangle, so we don't need to cut it further, so the answer is $1 \cdot 2 \cdot 3 = 6$.

In the second example the polygon is a rectangle, so it should be divided into two triangles. It's optimal to cut it using diagonal $1-3$ so answer is $1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$.
user: Vanya got an important task — he should enumerate books in the library and label each book with its number. Each of the n books should be assigned with a number from 1 to n. Naturally, distinct books should be assigned distinct numbers.

Vanya wants to know how many digits he will have to write down as he labels the books.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^9) — the number of books in the library.


-----Output-----

Print the number of digits needed to number all the books.


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

Output
17

Input
4

Output
4



-----Note-----

Note to the first test. The books get numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, which totals to 17 digits.

Note to the second sample. The books get numbers 1, 2, 3, 4, which totals to 4 digits.
user: Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another.

The game rules are like this. Firstly Alice chooses some color A, then Bob chooses some color B (A ≠ B). After each car they update the number of cars of their chosen color that have run past them. Let's define this numbers after i-th car cnt_{A}(i) and cnt_{B}(i).

  If cnt_{A}(i) > cnt_{B}(i) for every i then the winner is Alice.  If cnt_{B}(i) ≥ cnt_{A}(i) for every i then the winner is Bob.  Otherwise it's a draw. 

Bob knows all the colors of cars that they will encounter and order of their appearance. Alice have already chosen her color A and Bob now wants to choose such color B that he will win the game (draw is not a win). Help him find this color.

If there are multiple solutions, print any of them. If there is no such color then print -1.


-----Input-----

The first line contains two integer numbers n and A (1 ≤ n ≤ 10^5, 1 ≤ A ≤ 10^6) – number of cars and the color chosen by Alice.

The second line contains n integer numbers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^6) — colors of the cars that Alice and Bob will encounter in the order of their appearance.


-----Output-----

Output such color B (1 ≤ B ≤ 10^6) that if Bob chooses it then he will win the game. If there are multiple solutions, print any of them. If there is no such color then print -1.

It is guaranteed that if there exists any solution then there exists solution with (1 ≤ B ≤ 10^6).


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

Output
2

Input
5 2
2 2 4 5 3

Output
-1

Input
3 10
1 2 3

Output
4



-----Note-----

Let's consider availability of colors in the first example:   cnt_2(i) ≥ cnt_1(i) for every i, and color 2 can be the answer.  cnt_4(2) < cnt_1(2), so color 4 isn't the winning one for Bob.  All the other colors also have cnt_{j}(2) < cnt_1(2), thus they are not available. 

In the third example every color is acceptable except for 10.
user: A one-dimensional Japanese crossword can be represented as a binary string of length x. An encoding of this crossword is an array a of size n, where n is the number of segments formed completely of 1's, and a_{i} is the length of i-th segment. No two segments touch or intersect.

For example:   If x = 6 and the crossword is 111011, then its encoding is an array {3, 2};  If x = 8 and the crossword is 01101010, then its encoding is an array {2, 1, 1};  If x = 5 and the crossword is 11111, then its encoding is an array {5};  If x = 5 and the crossword is 00000, then its encoding is an empty array. 

Mishka wants to create a new one-dimensional Japanese crossword. He has already picked the length and the encoding for this crossword. And now he needs to check if there is exactly one crossword such that its length and encoding are equal to the length and encoding he picked. Help him to check it!


-----Input-----

The first line contains two integer numbers n and x (1 ≤ n ≤ 100000, 1 ≤ x ≤ 10^9) — the number of elements in the encoding and the length of the crossword Mishka picked.

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10000) — the encoding.


-----Output-----

Print YES if there exists exaclty one crossword with chosen length and encoding. Otherwise, print NO.


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

Output
NO

Input
3 10
3 3 2

Output
YES

Input
2 10
1 3

Output
NO
user: You have unlimited number of coins with values $1, 2, \ldots, n$. You want to select some set of coins having the total value of $S$. 

It is allowed to have multiple coins with the same value in the set. What is the minimum number of coins required to get sum $S$?


-----Input-----

The only line of the input contains two integers $n$ and $S$ ($1 \le n \le 100\,000$, $1 \le S \le 10^9$)


-----Output-----

Print exactly one integer — the minimum number of coins required to obtain sum $S$.


-----Examples-----
Input
5 11

Output
3
Input
6 16

Output
3


-----Note-----

In the first example, some of the possible ways to get sum $11$ with $3$ coins are: 

  $(3, 4, 4)$

 $(2, 4, 5)$

 $(1, 5, 5)$

 $(3, 3, 5)$ 

It is impossible to get sum $11$ with less than $3$ coins.

In the second example, some of the possible ways to get sum $16$ with $3$ coins are: 

  $(5, 5, 6)$

 $(4, 6, 6)$ 

It is impossible to get sum $16$ with less than $3$ coins.
user: A string is called palindrome if it reads the same from left to right and from right to left. For example "kazak", "oo", "r" and "mikhailrubinchikkihcniburliahkim" are palindroms, but strings "abb" and "ij" are not.

You are given string s consisting of lowercase Latin letters. At once you can choose any position in the string and change letter in that position to any other lowercase letter. So after each changing the length of the string doesn't change. At first you can change some letters in s. Then you can permute the order of letters as you want. Permutation doesn't count as changes. 

You should obtain palindrome with the minimal number of changes. If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. So firstly you should minimize the number of changes and then minimize the palindrome lexicographically.


-----Input-----

The only line contains string s (1 ≤ |s| ≤ 2·10^5) consisting of only lowercase Latin letters.


-----Output-----

Print the lexicographically smallest palindrome that can be obtained with the minimal number of changes.


-----Examples-----
Input
aabc

Output
abba

Input
aabcd

Output
abcba
user: A and B are preparing themselves for programming contests.

To train their logical thinking and solve problems better, A and B decided to play chess. During the game A wondered whose position is now stronger.

For each chess piece we know its weight:   the queen's weight is 9,  the rook's weight is 5,  the bishop's weight is 3,  the knight's weight is 3,  the pawn's weight is 1,  the king's weight isn't considered in evaluating position. 

The player's weight equals to the sum of weights of all his pieces on the board.

As A doesn't like counting, he asked you to help him determine which player has the larger position weight.


-----Input-----

The input contains eight lines, eight characters each — the board's description.

The white pieces on the board are marked with uppercase letters, the black pieces are marked with lowercase letters.

The white pieces are denoted as follows: the queen is represented is 'Q', the rook — as 'R', the bishop — as'B', the knight — as 'N', the pawn — as 'P', the king — as 'K'.

The black pieces are denoted as 'q', 'r', 'b', 'n', 'p', 'k', respectively.

An empty square of the board is marked as '.' (a dot). 

It is not guaranteed that the given chess position can be achieved in a real game. Specifically, there can be an arbitrary (possibly zero) number pieces of each type, the king may be under attack and so on.


-----Output-----

Print "White" (without quotes) if the weight of the position of the white pieces is more than the weight of the position of the black pieces, print "Black" if the weight of the black pieces is more than the weight of the white pieces and print "Draw" if the weights of the white and black pieces are equal.


-----Examples-----
Input
...QK...
........
........
........
........
........
........
...rk...

Output
White

Input
rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

Output
Draw

Input
rppppppr
...k....
........
........
........
........
K...Q...
........

Output
Black



-----Note-----

In the first test sample the weight of the position of the white pieces equals to 9, the weight of the position of the black pieces equals 5.

In the second test sample the weights of the positions of the black and the white pieces are equal to 39.

In the third test sample the weight of the position of the white pieces equals to 9, the weight of the position of the black pieces equals to 16.
user: Takahashi is playing a board game called Sugoroku.
On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.
The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.
Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.
Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 1 \leq M \leq 10^5
 - |S| = N + 1
 - S consists of 0 and 1.
 - S[0] = 0
 - S[N] = 0

-----Input-----
Input is given from Standard Input in the following format:
N M
S

-----Output-----
If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.
If Takahashi cannot win the game, print -1.

-----Sample Input-----
9 3
0001000100

-----Sample Output-----
1 3 2 3

If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.
user: Jumbo Takahashi will play golf on an infinite two-dimensional grid.
The ball is initially at the origin (0, 0), and the goal is a grid point (a point with integer coordinates) (X, Y). In one stroke, Jumbo Takahashi can perform the following operation:
 - Choose a grid point whose Manhattan distance from the current position of the ball is K, and send the ball to that point.
The game is finished when the ball reaches the goal, and the score will be the number of strokes so far. Jumbo Takahashi wants to finish the game with the lowest score possible.
Determine if the game can be finished. If the answer is yes, find one way to bring the ball to the goal with the lowest score possible.
What is Manhattan distance?
The Manhattan distance between two points (x_1, y_1) and (x_2, y_2) is defined as |x_1-x_2|+|y_1-y_2|.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq K \leq 10^9
 - -10^5 \leq X, Y \leq 10^5
 - (X, Y) \neq (0, 0)

-----Input-----
Input is given from Standard Input in the following format:
K
X Y

-----Output-----
If the game cannot be finished, print -1.
If the game can be finished, print one way to bring the ball to the destination with the lowest score possible, in the following format:
s
x_1 y_1
x_2 y_2
.
.
.
x_s y_s

Here, s is the lowest score possible, and (x_i, y_i) is the position of the ball just after the i-th stroke.

-----Sample Input-----
11
-1 2

-----Sample Output-----
3
7 4
2 10
-1 2

 - The Manhattan distance between (0, 0) and (7, 4) is |0-7|+|0-4|=11.
 - The Manhattan distance between (7, 4) and (2, 10) is |7-2|+|4-10|=11.
 - The Manhattan distance between (2, 10) and (-1, 2) is |2-(-1)|+|10-2|=11.
Thus, this play is valid.
Also, there is no way to finish the game with less than three strokes.
user: Bad news came to Mike's village, some thieves stole a bunch of chocolates from the local factory! Horrible! 

Aside from loving sweet things, thieves from this area are known to be very greedy. So after a thief takes his number of chocolates for himself, the next thief will take exactly k times more than the previous one. The value of k (k > 1) is a secret integer known only to them. It is also known that each thief's bag can carry at most n chocolates (if they intend to take more, the deal is cancelled) and that there were exactly four thieves involved. 

Sadly, only the thieves know the value of n, but rumours say that the numbers of ways they could have taken the chocolates (for a fixed n, but not fixed k) is m. Two ways are considered different if one of the thieves (they should be numbered in the order they take chocolates) took different number of chocolates in them.

Mike want to track the thieves down, so he wants to know what their bags are and value of n will help him in that. Please find the smallest possible value of n or tell him that the rumors are false and there is no such n.


-----Input-----

The single line of input contains the integer m (1 ≤ m ≤ 10^15) — the number of ways the thieves might steal the chocolates, as rumours say.


-----Output-----

Print the only integer n — the maximum amount of chocolates that thieves' bags can carry. If there are more than one n satisfying the rumors, print the smallest one.

If there is no such n for a false-rumoured m, print  - 1.


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

Output
8

Input
8

Output
54

Input
10

Output
-1



-----Note-----

In the first sample case the smallest n that leads to exactly one way of stealing chocolates is n = 8, whereas the amounts of stealed chocolates are (1, 2, 4, 8) (the number of chocolates stolen by each of the thieves).

In the second sample case the smallest n that leads to exactly 8 ways is n = 54 with the possibilities: (1, 2, 4, 8),  (1, 3, 9, 27),  (2, 4, 8, 16),  (2, 6, 18, 54),  (3, 6, 12, 24),  (4, 8, 16, 32),  (5, 10, 20, 40),  (6, 12, 24, 48).

There is no n leading to exactly 10 ways of stealing chocolates in the third sample case.
user: You are given two circles. Find the area of their intersection.


-----Input-----

The first line contains three integers x_1, y_1, r_1 ( - 10^9 ≤ x_1, y_1 ≤ 10^9, 1 ≤ r_1 ≤ 10^9) — the position of the center and the radius of the first circle.

The second line contains three integers x_2, y_2, r_2 ( - 10^9 ≤ x_2, y_2 ≤ 10^9, 1 ≤ r_2 ≤ 10^9) — the position of the center and the radius of the second circle.


-----Output-----

Print the area of the intersection of the circles. The answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 6}.


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

Output
7.25298806364175601379

Input
0 0 5
11 0 5

Output
0.00000000000000000000
user: Chouti was doing a competitive programming competition. However, after having all the problems accepted, he got bored and decided to invent some small games.

He came up with the following game. The player has a positive integer $n$. Initially the value of $n$ equals to $v$ and the player is able to do the following operation as many times as the player want (possibly zero): choose a positive integer $x$ that $x<n$ and $x$ is not a divisor of $n$, then subtract $x$ from $n$. The goal of the player is to minimize the value of $n$ in the end.

Soon, Chouti found the game trivial. Can you also beat the game?


-----Input-----

The input contains only one integer in the first line: $v$ ($1 \le v \le 10^9$), the initial value of $n$.


-----Output-----

Output a single integer, the minimum value of $n$ the player can get.


-----Examples-----
Input
8

Output
1

Input
1

Output
1



-----Note-----

In the first example, the player can choose $x=3$ in the first turn, then $n$ becomes $5$. He can then choose $x=4$ in the second turn to get $n=1$ as the result. There are other ways to get this minimum. However, for example, he cannot choose $x=2$ in the first turn because $2$ is a divisor of $8$.

In the second example, since $n=1$ initially, the player can do nothing.