meetforever/GRPO_CL huggingface dataset:
user: One fine October day a mathematics teacher Vasily Petrov went to a class and saw there n pupils who sat at the $\frac{n}{2}$ desks, two people at each desk. Vasily quickly realized that number n is even. Like all true mathematicians, Vasily has all students numbered from 1 to n.

But Vasily Petrov did not like the way the children were seated at the desks. According to him, the students whose numbers differ by 1, can not sit together, as they talk to each other all the time, distract others and misbehave.

On the other hand, if a righthanded student sits at the left end of the desk and a lefthanded student sits at the right end of the desk, they hit elbows all the time and distract each other. In other cases, the students who sit at the same desk, do not interfere with each other.

Vasily knows very well which students are lefthanders and which ones are righthanders, and he asks you to come up with any order that meets these two uncomplicated conditions (students do not talk to each other and do not bump their elbows). It is guaranteed that the input is such that at least one way to seat the students always exists.


-----Input-----

The first input line contains a single even integer n (4 ≤ n ≤ 100) — the number of students in the class. The second line contains exactly n capital English letters "L" and "R". If the i-th letter at the second line equals "L", then the student number i is a lefthander, otherwise he is a righthander.


-----Output-----

Print $\frac{n}{2}$ integer pairs, one pair per line. In the i-th line print the numbers of students that will sit at the i-th desk. The first number in the pair stands for the student who is sitting to the left, and the second number stands for the student who is sitting to the right. Separate the numbers in the pairs by spaces. If there are multiple solutions, print any of them.


-----Examples-----
Input
6
LLRLLL

Output
1 4
2 5
6 3

Input
4
RRLL

Output
3 1
4 2
user: Okabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.

Consider the point (x, y) in the 2D plane such that x and y are integers and 0 ≤ x, y. There is a tree in such a point, and it has x + y bananas. There are no trees nor bananas in other points. Now, Okabe draws a line with equation $y = - \frac{x}{m} + b$. Okabe can select a single rectangle with axis aligned sides with all points on or under the line and cut all the trees in all points that are inside or on the border of this rectangle and take their bananas. Okabe's rectangle can be degenerate; that is, it can be a line segment or even a point.

Help Okabe and find the maximum number of bananas he can get if he chooses the rectangle wisely.

Okabe is sure that the answer does not exceed 10^18. You can trust him.


-----Input-----

The first line of input contains two space-separated integers m and b (1 ≤ m ≤ 1000, 1 ≤ b ≤ 10000).


-----Output-----

Print the maximum number of bananas Okabe can get from the trees he cuts.


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

Output
30

Input
2 3

Output
25



-----Note----- [Image] 

The graph above corresponds to sample test 1. The optimal rectangle is shown in red and has 30 bananas.
user: One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts flying in different directions. Sometimes those parts also explode after some period of time, splitting into even more parts, and so on.

Limak, who lives in an infinite grid, has a single firework. The behaviour of the firework is described with a recursion depth n and a duration for each level of recursion t_1, t_2, ..., t_{n}. Once Limak launches the firework in some cell, the firework starts moving upward. After covering t_1 cells (including the starting cell), it explodes and splits into two parts, each moving in the direction changed by 45 degrees (see the pictures below for clarification). So, one part moves in the top-left direction, while the other one moves in the top-right direction. Each part explodes again after covering t_2 cells, splitting into two parts moving in directions again changed by 45 degrees. The process continues till the n-th level of recursion, when all 2^{n} - 1 existing parts explode and disappear without creating new parts. After a few levels of recursion, it's possible that some parts will be at the same place and at the same time — it is allowed and such parts do not crash.

Before launching the firework, Limak must make sure that nobody stands in cells which will be visited at least once by the firework. Can you count the number of those cells?


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 30) — the total depth of the recursion.

The second line contains n integers t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ 5). On the i-th level each of 2^{i} - 1 parts will cover t_{i} cells before exploding.


-----Output-----

Print one integer, denoting the number of cells which will be visited at least once by any part of the firework.


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

Output
39

Input
6
1 1 1 1 1 3

Output
85

Input
1
3

Output
3



-----Note-----

For the first sample, the drawings below show the situation after each level of recursion. Limak launched the firework from the bottom-most red cell. It covered t_1 = 4 cells (marked red), exploded and divided into two parts (their further movement is marked green). All explosions are marked with an 'X' character. On the last drawing, there are 4 red, 4 green, 8 orange and 23 pink cells. So, the total number of visited cells is 4 + 4 + 8 + 23 = 39.

 [Image] 

For the second sample, the drawings below show the situation after levels 4, 5 and 6. The middle drawing shows directions of all parts that will move in the next level.

 [Image]
user: -----Input-----

The input consists of a single string of uppercase letters A-Z. The length of the string is between 1 and 10 characters, inclusive.


-----Output-----

Output "YES" or "NO".


-----Examples-----
Input
NEAT

Output
YES

Input
WORD

Output
NO

Input
CODER

Output
NO

Input
APRILFOOL

Output
NO

Input
AI

Output
YES

Input
JUROR

Output
YES

Input
YES

Output
NO
user: Bob programmed a robot to navigate through a 2d maze.

The maze has some obstacles. Empty cells are denoted by the character '.', where obstacles are denoted by '#'.

There is a single robot in the maze. Its start position is denoted with the character 'S'. This position has no obstacle in it. There is also a single exit in the maze. Its position is denoted with the character 'E'. This position has no obstacle in it.

The robot can only move up, left, right, or down.

When Bob programmed the robot, he wrote down a string of digits consisting of the digits 0 to 3, inclusive. He intended for each digit to correspond to a distinct direction, and the robot would follow the directions in order to reach the exit. Unfortunately, he forgot to actually assign the directions to digits.

The robot will choose some random mapping of digits to distinct directions. The robot will map distinct digits to distinct directions. The robot will then follow the instructions according to the given string in order and chosen mapping. If an instruction would lead the robot to go off the edge of the maze or hit an obstacle, the robot will crash and break down. If the robot reaches the exit at any point, then the robot will stop following any further instructions.

Bob is having trouble debugging his robot, so he would like to determine the number of mappings of digits to directions that would lead the robot to the exit.


-----Input-----

The first line of input will contain two integers n and m (2 ≤ n, m ≤ 50), denoting the dimensions of the maze.

The next n lines will contain exactly m characters each, denoting the maze.

Each character of the maze will be '.', '#', 'S', or 'E'.

There will be exactly one 'S' and exactly one 'E' in the maze.

The last line will contain a single string s (1 ≤ |s| ≤ 100) — the instructions given to the robot. Each character of s is a digit from 0 to 3.


-----Output-----

Print a single integer, the number of mappings of digits to directions that will lead the robot to the exit.


-----Examples-----
Input
5 6
.....#
S....#
.#....
.#....
...E..
333300012

Output
1

Input
6 6
......
......
..SE..
......
......
......
01232123212302123021

Output
14

Input
5 3
...
.S.
###
.E.
...
3

Output
0



-----Note-----

For the first sample, the only valid mapping is $0 \rightarrow D, 1 \rightarrow L, 2 \rightarrow U, 3 \rightarrow R$, where D is down, L is left, U is up, R is right.
user: You are given n points on a plane. All the points are distinct and no three of them lie on the same line. Find the number of parallelograms with the vertices at the given points.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 2000) — the number of points.

Each of the next n lines contains two integers (x_{i}, y_{i}) (0 ≤ x_{i}, y_{i} ≤ 10^9) — the coordinates of the i-th point.


-----Output-----

Print the only integer c — the number of parallelograms with the vertices at the given points.


-----Example-----
Input
4
0 1
1 0
1 1
2 0

Output
1
user: Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length $2n$.

The definition of correct bracket sequence is as follows:  The empty sequence is a correct bracket sequence,  If $s$ is a correct bracket sequence, then $(\,s\,)$ is a correct bracket sequence,  If $s$ and $t$ are a correct bracket sequence, then $st$ is also a correct bracket sequence. 

For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo $10^9 + 7$.


-----Input-----

The only line contains a single integer $n$ ($1 \le n \le 1000$).


-----Output-----

Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo $10^9 + 7$.


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

Output
1

Input
2

Output
3

Input
3

Output
9



-----Note-----

The pictures below illustrate tries in the first two examples (for clarity, the round brackets are replaced with angle brackets). The maximum matching is highlighted with blue. [Image] [Image]
user: On a chessboard with a width of $n$ and a height of $n$, rows are numbered from bottom to top from $1$ to $n$, columns are numbered from left to right from $1$ to $n$. Therefore, for each cell of the chessboard, you can assign the coordinates $(r,c)$, where $r$ is the number of the row, and $c$ is the number of the column.

The white king has been sitting in a cell with $(1,1)$ coordinates for a thousand years, while the black king has been sitting in a cell with $(n,n)$ coordinates. They would have sat like that further, but suddenly a beautiful coin fell on the cell with coordinates $(x,y)$...

Each of the monarchs wanted to get it, so they decided to arrange a race according to slightly changed chess rules:

As in chess, the white king makes the first move, the black king makes the second one, the white king makes the third one, and so on. However, in this problem, kings can stand in adjacent cells or even in the same cell at the same time.

The player who reaches the coin first will win, that is to say, the player who reaches the cell with the coordinates $(x,y)$ first will win.

Let's recall that the king is such a chess piece that can move one cell in all directions, that is, if the king is in the $(a,b)$ cell, then in one move he can move from $(a,b)$ to the cells $(a + 1,b)$, $(a - 1,b)$, $(a,b + 1)$, $(a,b - 1)$, $(a + 1,b - 1)$, $(a + 1,b + 1)$, $(a - 1,b - 1)$, or $(a - 1,b + 1)$. Going outside of the field is prohibited.

Determine the color of the king, who will reach the cell with the coordinates $(x,y)$ first, if the white king moves first.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^{18}$) — the length of the side of the chess field.

The second line contains two integers $x$ and $y$ ($1 \le x,y \le n$) — coordinates of the cell, where the coin fell.


-----Output-----

In a single line print the answer "White" (without quotes), if the white king will win, or "Black" (without quotes), if the black king will win.

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


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

Output
White
Input
5
3 5

Output
Black
Input
2
2 2

Output
Black


-----Note-----

An example of the race from the first sample where both the white king and the black king move optimally: The white king moves from the cell $(1,1)$ into the cell $(2,2)$. The black king moves form the cell $(4,4)$ into the cell $(3,3)$. The white king moves from the cell $(2,2)$ into the cell $(2,3)$. This is cell containing the coin, so the white king wins. [Image] 

An example of the race from the second sample where both the white king and the black king move optimally: The white king moves from the cell $(1,1)$ into the cell $(2,2)$. The black king moves form the cell $(5,5)$ into the cell $(4,4)$. The white king moves from the cell $(2,2)$ into the cell $(3,3)$. The black king moves from the cell $(4,4)$ into the cell $(3,5)$. This is the cell, where the coin fell, so the black king wins. [Image] 

In the third example, the coin fell in the starting cell of the black king, so the black king immediately wins. [Image]
user: The winter in Berland lasts n days. For each day we know the forecast for the average air temperature that day. 

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

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

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

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


-----Input-----

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

The second line contains a sequence of n integers t_1, t_2, ..., t_{n} ( - 20 ≤ t_{i} ≤ 20) — the average air temperature in the i-th winter day. 


-----Output-----

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


-----Examples-----
Input
4 3
-5 20 -3 0

Output
2

Input
4 2
-5 20 -3 0

Output
4

Input
10 6
2 -5 1 3 0 0 -4 -3 1 0

Output
3



-----Note-----

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

In the second example before the first winter day Vasya should change summer tires to winter tires, and then after the first winter day change winter tires to summer tires. After the second day it is necessary to change summer tires to winter tires again, and after the third day it is necessary to change winter tires to summer tires. Thus, the total number of tires' changes equals four.
user: During the winter holidays, the demand for Christmas balls is exceptionally high. Since it's already 2018, the advances in alchemy allow easy and efficient ball creation by utilizing magic crystals.

Grisha needs to obtain some yellow, green and blue balls. It's known that to produce a yellow ball one needs two yellow crystals, green — one yellow and one blue, and for a blue ball, three blue crystals are enough.

Right now there are A yellow and B blue crystals in Grisha's disposal. Find out how many additional crystals he should acquire in order to produce the required number of balls.


-----Input-----

The first line features two integers A and B (0 ≤ A, B ≤ 10^9), denoting the number of yellow and blue crystals respectively at Grisha's disposal.

The next line contains three integers x, y and z (0 ≤ x, y, z ≤ 10^9) — the respective amounts of yellow, green and blue balls to be obtained.


-----Output-----

Print a single integer — the minimum number of crystals that Grisha should acquire in addition.


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

Output
2

Input
3 9
1 1 3

Output
1

Input
12345678 87654321
43043751 1000000000 53798715

Output
2147483648



-----Note-----

In the first sample case, Grisha needs five yellow and four blue crystals to create two yellow balls, one green ball, and one blue ball. To do that, Grisha needs to obtain two additional crystals: one yellow and one blue.
user: And while Mishka is enjoying her trip...

Chris is a little brown bear. No one knows, where and when he met Mishka, but for a long time they are together (excluding her current trip). However, best friends are important too. John is Chris' best friend.

Once walking with his friend, John gave Chris the following problem:

At the infinite horizontal road of width w, bounded by lines y = 0 and y = w, there is a bus moving, presented as a convex polygon of n vertices. The bus moves continuously with a constant speed of v in a straight Ox line in direction of decreasing x coordinates, thus in time only x coordinates of its points are changing. Formally, after time t each of x coordinates of its points will be decreased by vt.

There is a pedestrian in the point (0, 0), who can move only by a vertical pedestrian crossing, presented as a segment connecting points (0, 0) and (0, w) with any speed not exceeding u. Thus the pedestrian can move only in a straight line Oy in any direction with any speed not exceeding u and not leaving the road borders. The pedestrian can instantly change his speed, thus, for example, he can stop instantly.

Please look at the sample note picture for better understanding.

We consider the pedestrian is hit by the bus, if at any moment the point he is located in lies strictly inside the bus polygon (this means that if the point lies on the polygon vertex or on its edge, the pedestrian is not hit by the bus).

You are given the bus position at the moment 0. Please help Chris determine minimum amount of time the pedestrian needs to cross the road and reach the point (0, w) and not to be hit by the bus.


-----Input-----

The first line of the input contains four integers n, w, v, u (3 ≤ n ≤ 10 000, 1 ≤ w ≤ 10^9, 1 ≤ v,  u ≤ 1000) — the number of the bus polygon vertices, road width, bus speed and pedestrian speed respectively.

The next n lines describes polygon vertices in counter-clockwise order. i-th of them contains pair of integers x_{i} and y_{i} ( - 10^9 ≤ x_{i} ≤ 10^9, 0 ≤ y_{i} ≤ w) — coordinates of i-th polygon point. It is guaranteed that the polygon is non-degenerate.


-----Output-----

Print the single real t — the time the pedestrian needs to croos the road and not to be hit by the bus. The answer is considered correct if its relative or absolute error doesn't exceed 10^{ - 6}.


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

Output
5.0000000000


-----Note-----

Following image describes initial position in the first sample case:

[Image]
user: Little Petya likes arrays of integers a lot. Recently his mother has presented him one such array consisting of n elements. Petya is now wondering whether he can swap any two distinct integers in the array so that the array got unsorted. Please note that Petya can not swap equal integers even if they are in distinct positions in the array. Also note that Petya must swap some two integers even if the original array meets all requirements.

Array a (the array elements are indexed from 1) consisting of n elements is called sorted if it meets at least one of the following two conditions:  a_1 ≤ a_2 ≤ ... ≤ a_{n};  a_1 ≥ a_2 ≥ ... ≥ a_{n}. 

Help Petya find the two required positions to swap or else say that they do not exist.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5). The second line contains n non-negative space-separated integers a_1, a_2, ..., a_{n} — the elements of the array that Petya's mother presented him. All integers in the input do not exceed 10^9.


-----Output-----

If there is a pair of positions that make the array unsorted if swapped, then print the numbers of these positions separated by a space. If there are several pairs of positions, print any of them. If such pair does not exist, print -1. The positions in the array are numbered with integers from 1 to n.


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

Output
-1

Input
2
1 2

Output
-1

Input
4
1 2 3 4

Output
1 2

Input
3
1 1 1

Output
-1



-----Note-----

In the first two samples the required pairs obviously don't exist.

In the third sample you can swap the first two elements. After that the array will look like this: 2 1 3 4. This array is unsorted.
user: A tennis tournament with n participants is running. The participants are playing by an olympic system, so the winners move on and the losers drop out.

The tournament takes place in the following way (below, m is the number of the participants of the current round):  let k be the maximal power of the number 2 such that k ≤ m,  k participants compete in the current round and a half of them passes to the next round, the other m - k participants pass to the next round directly,  when only one participant remains, the tournament finishes. 

Each match requires b bottles of water for each participant and one bottle for the judge. Besides p towels are given to each participant for the whole tournament.

Find the number of bottles and towels needed for the tournament.

Note that it's a tennis tournament so in each match two participants compete (one of them will win and the other will lose).


-----Input-----

The only line contains three integers n, b, p (1 ≤ n, b, p ≤ 500) — the number of participants and the parameters described in the problem statement.


-----Output-----

Print two integers x and y — the number of bottles and towels need for the tournament.


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

Output
20 15

Input
8 2 4

Output
35 32



-----Note-----

In the first example will be three rounds:  in the first round will be two matches and for each match 5 bottles of water are needed (two for each of the participants and one for the judge),  in the second round will be only one match, so we need another 5 bottles of water,  in the third round will also be only one match, so we need another 5 bottles of water. 

So in total we need 20 bottles of water.

In the second example no participant will move on to some round directly.