meetforever/GRPO_CL huggingface dataset:
user: n people are standing on a coordinate axis in points with positive integer coordinates strictly less than 10^6. For each person we know in which direction (left or right) he is facing, and his maximum speed.

You can put a bomb in some point with non-negative integer coordinate, and blow it up. At this moment all people will start running with their maximum speed in the direction they are facing. Also, two strange rays will start propagating from the bomb with speed s: one to the right, and one to the left. Of course, the speed s is strictly greater than people's maximum speed.

The rays are strange because if at any moment the position and the direction of movement of some ray and some person coincide, then the speed of the person immediately increases by the speed of the ray.

You need to place the bomb is such a point that the minimum time moment in which there is a person that has run through point 0, and there is a person that has run through point 10^6, is as small as possible. In other words, find the minimum time moment t such that there is a point you can place the bomb to so that at time moment t some person has run through 0, and some person has run through point 10^6.


-----Input-----

The first line contains two integers n and s (2 ≤ n ≤ 10^5, 2 ≤ s ≤ 10^6) — the number of people and the rays' speed.

The next n lines contain the description of people. The i-th of these lines contains three integers x_{i}, v_{i} and t_{i} (0 < x_{i} < 10^6, 1 ≤ v_{i} < s, 1 ≤ t_{i} ≤ 2) — the coordinate of the i-th person on the line, his maximum speed and the direction he will run to (1 is to the left, i.e. in the direction of coordinate decrease, 2 is to the right, i.e. in the direction of coordinate increase), respectively.

It is guaranteed that the points 0 and 10^6 will be reached independently of the bomb's position.


-----Output-----

Print the minimum time needed for both points 0 and 10^6 to be reached.

Your answer is considered correct if its absolute or relative error doesn't exceed 10^{ - 6}. Namely, if your answer is a, and the jury's answer is b, then your answer is accepted, if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-6}$.


-----Examples-----
Input
2 999
400000 1 2
500000 1 1

Output
500000.000000000000000000000000000000

Input
2 1000
400000 500 1
600000 500 2

Output
400.000000000000000000000000000000



-----Note-----

In the first example, it is optimal to place the bomb at a point with a coordinate of 400000. Then at time 0, the speed of the first person becomes 1000 and he reaches the point 10^6 at the time 600. The bomb will not affect on the second person, and he will reach the 0 point at the time 500000.

In the second example, it is optimal to place the bomb at the point 500000. The rays will catch up with both people at the time 200. At this time moment, the first is at the point with a coordinate of 300000, and the second is at the point with a coordinate of 700000. Their speed will become 1500 and at the time 400 they will simultaneously run through points 0 and 10^6.
user: The School №0 of the capital of Berland has n children studying in it. All the children in this school are gifted: some of them are good at programming, some are good at maths, others are good at PE (Physical Education). Hence, for each child we know value t_{i}:  t_{i} = 1, if the i-th child is good at programming,  t_{i} = 2, if the i-th child is good at maths,  t_{i} = 3, if the i-th child is good at PE 

Each child happens to be good at exactly one of these three subjects.

The Team Scientific Decathlon Olympias requires teams of three students. The school teachers decided that the teams will be composed of three children that are good at different subjects. That is, each team must have one mathematician, one programmer and one sportsman. Of course, each child can be a member of no more than one team.

What is the maximum number of teams that the school will be able to present at the Olympiad? How should the teams be formed for that?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 5000) — the number of children in the school. The second line contains n integers t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ 3), where t_{i} describes the skill of the i-th child.


-----Output-----

In the first line output integer w — the largest possible number of teams. 

Then print w lines, containing three numbers in each line. Each triple represents the indexes of the children forming the team. You can print both the teams, and the numbers in the triplets in any order. The children are numbered from 1 to n in the order of their appearance in the input. Each child must participate in no more than one team. If there are several solutions, print any of them.

If no teams can be compiled, print the only line with value w equal to 0.


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

Output
2
3 5 2
6 7 4

Input
4
2 1 1 2

Output
0
user: Alyona has recently bought a miniature fridge that can be represented as a matrix with $h$ rows and $2$ columns. Initially there is only one shelf at the bottom of the fridge, but Alyona can install arbitrary number of shelves inside the fridge between any two rows. A shelf is two cells wide, does not occupy any space but separates the inside of the fridge to the lower and upper part.

 [Image] An example of a fridge with $h = 7$ and two shelves. The shelves are shown in black. The picture corresponds to the first example. 

Alyona has $n$ bottles of milk that she wants to put in the fridge. The $i$-th bottle is $a_i$ cells tall and $1$ cell wide. She can put a bottle on some shelf if the corresponding space above the shelf is at least as tall as the bottle. She can not put a bottle on top of another bottle (if there is no shelf between them). Two bottles can not share a cell.

Alyona is interested in the largest integer $k$ such that she can put bottles $1$, $2$, ..., $k$ in the fridge at the same time. Find this largest $k$.


-----Input-----

The first line contains two integers $n$ and $h$ ($1 \le n \le 10^3$, $1 \le h \le 10^9$) — the number of bottles and the height of the fridge.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le h$) — the heights of the bottles.


-----Output-----

Print the single integer $k$ — the maximum integer such that Alyona can put the bottles $1$, $2$, ..., $k$ in the fridge at the same time. If Alyona can put all bottles in the fridge, print $n$. It is easy to see that Alyona can always put at least one bottle in the fridge.


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

Output
3

Input
10 10
9 1 1 1 1 1 1 1 1 1

Output
4

Input
5 10
3 1 4 2 4

Output
5



-----Note-----

One of optimal locations in the first example is shown on the picture in the statement.

One of optimal locations in the second example is shown on the picture below.

 [Image] 

One of optimal locations in the third example is shown on the picture below.

 [Image]
user: There are n pearls in a row. Let's enumerate them with integers from 1 to n from the left to the right. The pearl number i has the type a_{i}.

Let's call a sequence of consecutive pearls a segment. Let's call a segment good if it contains two pearls of the same type.

Split the row of the pearls to the maximal number of good segments. Note that each pearl should appear in exactly one segment of the partition.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the number of pearls in a row.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) – the type of the i-th pearl.


-----Output-----

On the first line print integer k — the maximal number of segments in a partition of the row.

Each of the next k lines should contain two integers l_{j}, r_{j} (1 ≤ l_{j} ≤ r_{j} ≤ n) — the number of the leftmost and the rightmost pearls in the j-th segment.

Note you should print the correct partition of the row of the pearls, so each pearl should be in exactly one segment and all segments should contain two pearls of the same type.

If there are several optimal solutions print any of them. You can print the segments in any order.

If there are no correct partitions of the row print the number "-1".


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

Output
1
1 5

Input
5
1 2 3 4 5

Output
-1

Input
7
1 2 1 3 1 2 1

Output
2
1 3
4 7
user: Mr. Apple, a gourmet, works as editor-in-chief of a gastronomic periodical. He travels around the world, tasting new delights of famous chefs from the most fashionable restaurants. Mr. Apple has his own signature method of review  — in each restaurant Mr. Apple orders two sets of dishes on two different days. All the dishes are different, because Mr. Apple doesn't like to eat the same food. For each pair of dishes from different days he remembers exactly which was better, or that they were of the same quality. After this the gourmet evaluates each dish with a positive integer.

Once, during a revision of a restaurant of Celtic medieval cuisine named «Poisson», that serves chestnut soup with fir, warm soda bread, spicy lemon pie and other folk food, Mr. Apple was very pleasantly surprised the gourmet with its variety of menu, and hence ordered too much. Now he's confused about evaluating dishes.

The gourmet tasted a set of $n$ dishes on the first day and a set of $m$ dishes on the second day. He made a table $a$ of size $n \times m$, in which he described his impressions. If, according to the expert, dish $i$ from the first set was better than dish $j$ from the second set, then $a_{ij}$ is equal to ">", in the opposite case $a_{ij}$ is equal to "<". Dishes also may be equally good, in this case $a_{ij}$ is "=".

Now Mr. Apple wants you to help him to evaluate every dish. Since Mr. Apple is very strict, he will evaluate the dishes so that the maximal number used is as small as possible. But Mr. Apple also is very fair, so he never evaluates the dishes so that it goes against his feelings. In other words, if $a_{ij}$ is "<", then the number assigned to dish $i$ from the first set should be less than the number of dish $j$ from the second set, if $a_{ij}$ is ">", then it should be greater, and finally if $a_{ij}$ is "=", then the numbers should be the same.

Help Mr. Apple to evaluate each dish from both sets so that it is consistent with his feelings, or determine that this is impossible.


-----Input-----

The first line contains integers $n$ and $m$ ($1 \leq n, m \leq 1000$) — the number of dishes in both days.

Each of the next $n$ lines contains a string of $m$ symbols. The $j$-th symbol on $i$-th line is $a_{ij}$. All strings consist only of "<", ">" and "=".


-----Output-----

The first line of output should contain "Yes", if it's possible to do a correct evaluation for all the dishes, or "No" otherwise.

If case an answer exist, on the second line print $n$ integers — evaluations of dishes from the first set, and on the third line print $m$ integers — evaluations of dishes from the second set.


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

Output
Yes
2 2 2 
1 1 1 1 

Input
3 3
>>>
<<<
>>>

Output
Yes
3 1 3 
2 2 2 

Input
3 2
==
=<
==

Output
No



-----Note-----

In the first sample, all dishes of the first day are better than dishes of the second day. So, the highest score will be $2$, for all dishes of the first day.

In the third sample, the table is contradictory — there is no possible evaluation of the dishes that satisfies it.
user: Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array a_{i} either with a_{i} + x or with a_{i} - x. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. $\prod_{i = 1}^{n} a_{i}$) can reach, if Maxim would apply no more than k operations to it. Please help him in that.


-----Input-----

The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 10^9) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains n integers a_1, a_2, ..., a_{n} ($|a_{i}|\leq 10^{9}$) — the elements of the array found by Maxim.


-----Output-----

Print n integers b_1, b_2, ..., b_{n} in the only line — the array elements after applying no more than k operations to the array. In particular, $a_{i} \equiv b_{i} \operatorname{mod} x$ should stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.


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

Output
5 4 3 5 -1 

Input
5 3 1
5 4 3 5 5

Output
5 4 0 5 5 

Input
5 3 1
5 4 4 5 5

Output
5 1 4 5 5 

Input
3 2 7
5 4 2

Output
5 11 -5
user: Vova is again playing some computer game, now an RPG. In the game Vova's character received a quest: to slay the fearsome monster called Modcrab.

After two hours of playing the game Vova has tracked the monster and analyzed its tactics. The Modcrab has h_2 health points and an attack power of a_2. Knowing that, Vova has decided to buy a lot of strong healing potions and to prepare for battle.

Vova's character has h_1 health points and an attack power of a_1. Also he has a large supply of healing potions, each of which increases his current amount of health points by c_1 when Vova drinks a potion. All potions are identical to each other. It is guaranteed that c_1 > a_2.

The battle consists of multiple phases. In the beginning of each phase, Vova can either attack the monster (thus reducing its health by a_1) or drink a healing potion (it increases Vova's health by c_1; Vova's health can exceed h_1). Then, if the battle is not over yet, the Modcrab attacks Vova, reducing his health by a_2. The battle ends when Vova's (or Modcrab's) health drops to 0 or lower. It is possible that the battle ends in a middle of a phase after Vova's attack.

Of course, Vova wants to win the fight. But also he wants to do it as fast as possible. So he wants to make up a strategy that will allow him to win the fight after the minimum possible number of phases.

Help Vova to make up a strategy! You may assume that Vova never runs out of healing potions, and that he can always win.


-----Input-----

The first line contains three integers h_1, a_1, c_1 (1 ≤ h_1, a_1 ≤ 100, 2 ≤ c_1 ≤ 100) — Vova's health, Vova's attack power and the healing power of a potion.

The second line contains two integers h_2, a_2 (1 ≤ h_2 ≤ 100, 1 ≤ a_2 < c_1) — the Modcrab's health and his attack power.


-----Output-----

In the first line print one integer n denoting the minimum number of phases required to win the battle.

Then print n lines. i-th line must be equal to HEAL if Vova drinks a potion in i-th phase, or STRIKE if he attacks the Modcrab.

The strategy must be valid: Vova's character must not be defeated before slaying the Modcrab, and the monster's health must be 0 or lower after Vova's last action.

If there are multiple optimal solutions, print any of them.


-----Examples-----
Input
10 6 100
17 5

Output
4
STRIKE
HEAL
STRIKE
STRIKE

Input
11 6 100
12 5

Output
2
STRIKE
STRIKE



-----Note-----

In the first example Vova's character must heal before or after his first attack. Otherwise his health will drop to zero in 2 phases while he needs 3 strikes to win.

In the second example no healing needed, two strikes are enough to get monster to zero health and win with 6 health left.
user: Vanya wants to pass n exams and get the academic scholarship. He will get the scholarship if the average grade mark for all the exams is at least avg. The exam grade cannot exceed r. Vanya has passed the exams and got grade a_{i} for the i-th exam. To increase the grade for the i-th exam by 1 point, Vanya must write b_{i} essays. He can raise the exam grade multiple times.

What is the minimum number of essays that Vanya needs to write to get scholarship?


-----Input-----

The first line contains three integers n, r, avg (1 ≤ n ≤ 10^5, 1 ≤ r ≤ 10^9, 1 ≤ avg ≤ min(r, 10^6)) — the number of exams, the maximum grade and the required grade point average, respectively.

Each of the following n lines contains space-separated integers a_{i} and b_{i} (1 ≤ a_{i} ≤ r, 1 ≤ b_{i} ≤ 10^6).


-----Output-----

In the first line print the minimum number of essays.


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

Output
4

Input
2 5 4
5 2
5 2

Output
0



-----Note-----

In the first sample Vanya can write 2 essays for the 3rd exam to raise his grade by 2 points and 2 essays for the 4th exam to raise his grade by 1 point.

In the second sample, Vanya doesn't need to write any essays as his general point average already is above average.
user: Alice became interested in periods of integer numbers. We say positive $X$ integer number is periodic with length $L$ if there exists positive integer number $P$ with $L$ digits such that $X$ can be written as $PPPP…P$. For example:

$X = 123123123$ is periodic number with length $L = 3$ and $L = 9$

$X = 42424242$ is periodic number with length $L = 2,L = 4$ and $L = 8$

$X = 12345$ is periodic number with length $L = 5$

For given positive period length $L$ and positive integer number $A$, Alice wants to find smallest integer number $X$ strictly greater than $A$ that is periodic with length L.


-----Input-----

First line contains one positive integer number $L \ (1 \leq L \leq 10^5)$ representing length of the period. Second line contains one positive integer number $A \ (1 \leq A \leq 10^{100 000})$.


-----Output-----

One positive integer number representing smallest positive number that is periodic with length $L$ and is greater than $A$.


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

Output
124124

Input
3
12345

Output
100100



-----Note-----

In first example 124124 is the smallest number greater than 123456 that can be written with period L = 3 (P = 124).

In the second example 100100 is the smallest number greater than 12345 with period L = 3 (P=100)
user: Anatoly lives in the university dorm as many other students do. As you know, cockroaches are also living there together with students. Cockroaches might be of two colors: black and red. There are n cockroaches living in Anatoly's room.

Anatoly just made all his cockroaches to form a single line. As he is a perfectionist, he would like the colors of cockroaches in the line to alternate. He has a can of black paint and a can of red paint. In one turn he can either swap any two cockroaches, or take any single cockroach and change it's color.

Help Anatoly find out the minimum number of turns he needs to make the colors of cockroaches in the line alternate.


-----Input-----

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

The second line contains a string of length n, consisting of characters 'b' and 'r' that denote black cockroach and red cockroach respectively.


-----Output-----

Print one integer — the minimum number of moves Anatoly has to perform in order to make the colors of cockroaches in the line to alternate.


-----Examples-----
Input
5
rbbrr

Output
1

Input
5
bbbbb

Output
2

Input
3
rbr

Output
0



-----Note-----

In the first sample, Anatoly has to swap third and fourth cockroaches. He needs 1 turn to do this.

In the second sample, the optimum answer is to paint the second and the fourth cockroaches red. This requires 2 turns.

In the third sample, the colors of cockroaches in the line are alternating already, thus the answer is 0.
user: Suppose that you are in a campus and have to go for classes day by day. As you may see, when you hurry to a classroom, you surprisingly find that many seats there are already occupied. Today you and your friends went for class, and found out that some of the seats were occupied.

The classroom contains $n$ rows of seats and there are $m$ seats in each row. Then the classroom can be represented as an $n \times m$ matrix. The character '.' represents an empty seat, while '*' means that the seat is occupied. You need to find $k$ consecutive empty seats in the same row or column and arrange those seats for you and your friends. Your task is to find the number of ways to arrange the seats. Two ways are considered different if sets of places that students occupy differs.


-----Input-----

The first line contains three positive integers $n,m,k$ ($1 \leq n, m, k \leq 2\,000$), where $n,m$ represent the sizes of the classroom and $k$ is the number of consecutive seats you need to find.

Each of the next $n$ lines contains $m$ characters '.' or '*'. They form a matrix representing the classroom, '.' denotes an empty seat, and '*' denotes an occupied seat.


-----Output-----

A single number, denoting the number of ways to find $k$ empty seats in the same row or column.


-----Examples-----
Input
2 3 2
**.
...

Output
3

Input
1 2 2
..

Output
1

Input
3 3 4
.*.
*.*
.*.

Output
0



-----Note-----

In the first sample, there are three ways to arrange those seats. You can take the following seats for your arrangement.   $(1,3)$, $(2,3)$  $(2,2)$, $(2,3)$  $(2,1)$, $(2,2)$
user: You are on the island which can be represented as a $n \times m$ table. The rows are numbered from $1$ to $n$ and the columns are numbered from $1$ to $m$. There are $k$ treasures on the island, the $i$-th of them is located at the position $(r_i, c_i)$.

Initially you stand at the lower left corner of the island, at the position $(1, 1)$. If at any moment you are at the cell with a treasure, you can pick it up without any extra time. In one move you can move up (from $(r, c)$ to $(r+1, c)$), left (from $(r, c)$ to $(r, c-1)$), or right (from position $(r, c)$ to $(r, c+1)$). Because of the traps, you can't move down.

However, moving up is also risky. You can move up only if you are in a safe column. There are $q$ safe columns: $b_1, b_2, \ldots, b_q$. You want to collect all the treasures as fast as possible. Count the minimum number of moves required to collect all the treasures.


-----Input-----

The first line contains integers $n$, $m$, $k$ and $q$ ($2 \le n, \, m, \, k, \, q \le 2 \cdot 10^5$, $q \le m$) — the number of rows, the number of columns, the number of treasures in the island and the number of safe columns.

Each of the next $k$ lines contains two integers $r_i, c_i$, ($1 \le r_i \le n$, $1 \le c_i \le m$) — the coordinates of the cell with a treasure. All treasures are located in distinct cells.

The last line contains $q$ distinct integers $b_1, b_2, \ldots, b_q$ ($1 \le b_i \le m$) — the indices of safe columns.


-----Output-----

Print the minimum number of moves required to collect all the treasures.


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

Output
6
Input
3 5 3 2
1 2
2 3
3 1
1 5

Output
8
Input
3 6 3 2
1 6
2 2
3 4
1 6

Output
15


-----Note-----

In the first example you should use the second column to go up, collecting in each row treasures from the first column. [Image] 

In the second example, it is optimal to use the first column to go up. [Image] 

In the third example, it is optimal to collect the treasure at cell $(1;6)$, go up to row $2$ at column $6$, then collect the treasure at cell $(2;2)$, go up to the top row at column $1$ and collect the last treasure at cell $(3;4)$. That's a total of $15$ moves. [Image]