meetforever/GRPO_CL huggingface dataset:
user: An accordion is a string (yes, in the real world accordions are musical instruments, but let's forget about it for a while) which can be represented as a concatenation of: an opening bracket (ASCII code $091$), a colon (ASCII code $058$), some (possibly zero) vertical line characters (ASCII code $124$), another colon, and a closing bracket (ASCII code $093$). The length of the accordion is the number of characters in it.

For example, [::], [:||:] and [:|||:] are accordions having length $4$, $6$ and $7$. (:|:), {:||:}, [:], ]:||:[ are not accordions. 

You are given a string $s$. You want to transform it into an accordion by removing some (possibly zero) characters from it. Note that you may not insert new characters or reorder existing ones. Is it possible to obtain an accordion by removing characters from $s$, and if so, what is the maximum possible length of the result?


-----Input-----

The only line contains one string $s$ ($1 \le |s| \le 500000$). It consists of lowercase Latin letters and characters [, ], : and |.


-----Output-----

If it is not possible to obtain an accordion by removing some characters from $s$, print $-1$. Otherwise print maximum possible length of the resulting accordion.


-----Examples-----
Input
|[a:b:|]

Output
4

Input
|]:[|:]

Output
-1
user: Anton has the integer x. He is interested what positive integer, which doesn't exceed x, has the maximum sum of digits.

Your task is to help Anton and to find the integer that interests him. If there are several such integers, determine the biggest of them. 


-----Input-----

The first line contains the positive integer x (1 ≤ x ≤ 10^18) — the integer which Anton has. 


-----Output-----

Print the positive integer which doesn't exceed x and has the maximum sum of digits. If there are several such integers, print the biggest of them. Printed integer must not contain leading zeros.


-----Examples-----
Input
100

Output
99

Input
48

Output
48

Input
521

Output
499
user: Apart from having lots of holidays throughout the year, residents of Berland also have whole lucky years. Year is considered lucky if it has no more than 1 non-zero digit in its number. So years 100, 40000, 5 are lucky and 12, 3001 and 12345 are not.

You are given current year in Berland. Your task is to find how long will residents of Berland wait till the next lucky year.


-----Input-----

The first line contains integer number n (1 ≤ n ≤ 10^9) — current year in Berland.


-----Output-----

Output amount of years from the current year to the next lucky one.


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

Output
1

Input
201

Output
99

Input
4000

Output
1000



-----Note-----

In the first example next lucky year is 5. In the second one — 300. In the third — 5000.
user: You have a long fence which consists of $n$ sections. Unfortunately, it is not painted, so you decided to hire $q$ painters to paint it. $i$-th painter will paint all sections $x$ such that $l_i \le x \le r_i$.

Unfortunately, you are on a tight budget, so you may hire only $q - 2$ painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose $q - 2$ painters optimally. A section is considered painted if at least one painter paints it.


-----Input-----

The first line contains two integers $n$ and $q$ ($3 \le n, q \le 5000$) — the number of sections and the number of painters availible for hire, respectively.

Then $q$ lines follow, each describing one of the painters: $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).


-----Output-----

Print one integer — maximum number of painted sections if you hire $q - 2$ painters.


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

Output
7

Input
4 3
1 1
2 2
3 4

Output
2

Input
4 4
1 1
2 2
2 3
3 4

Output
3
user: Jamie loves sleeping. One day, he decides that he needs to wake up at exactly hh: mm. However, he hates waking up, so he wants to make waking up less painful by setting the alarm at a lucky time. He will then press the snooze button every x minutes until hh: mm is reached, and only then he will wake up. He wants to know what is the smallest number of times he needs to press the snooze button.

A time is considered lucky if it contains a digit '7'. For example, 13: 07 and 17: 27 are lucky, while 00: 48 and 21: 34 are not lucky.

Note that it is not necessary that the time set for the alarm and the wake-up time are on the same day. It is guaranteed that there is a lucky time Jamie can set so that he can wake at hh: mm.

Formally, find the smallest possible non-negative integer y such that the time representation of the time x·y minutes before hh: mm contains the digit '7'.

Jamie uses 24-hours clock, so after 23: 59 comes 00: 00.


-----Input-----

The first line contains a single integer x (1 ≤ x ≤ 60).

The second line contains two two-digit integers, hh and mm (00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59).


-----Output-----

Print the minimum number of times he needs to press the button.


-----Examples-----
Input
3
11 23

Output
2

Input
5
01 07

Output
0



-----Note-----

In the first sample, Jamie needs to wake up at 11:23. So, he can set his alarm at 11:17. He would press the snooze button when the alarm rings at 11:17 and at 11:20.

In the second sample, Jamie can set his alarm at exactly at 01:07 which is lucky.
user: Luba is surfing the Internet. She currently has n opened tabs in her browser, indexed from 1 to n from left to right. The mouse cursor is currently located at the pos-th tab. Luba needs to use the tabs with indices from l to r (inclusive) for her studies, and she wants to close all the tabs that don't belong to this segment as fast as possible.

Each second Luba can either try moving the cursor to the left or to the right (if the cursor is currently at the tab i, then she can move it to the tab max(i - 1, a) or to the tab min(i + 1, b)) or try closing all the tabs to the left or to the right of the cursor (if the cursor is currently at the tab i, she can close all the tabs with indices from segment [a, i - 1] or from segment [i + 1, b]). In the aforementioned expressions a and b denote the minimum and maximum index of an unclosed tab, respectively. For example, if there were 7 tabs initially and tabs 1, 2 and 7 are closed, then a = 3, b = 6.

What is the minimum number of seconds Luba has to spend in order to leave only the tabs with initial indices from l to r inclusive opened?


-----Input-----

The only line of input contains four integer numbers n, pos, l, r (1 ≤ n ≤ 100, 1 ≤ pos ≤ n, 1 ≤ l ≤ r ≤ n) — the number of the tabs, the cursor position and the segment which Luba needs to leave opened.


-----Output-----

Print one integer equal to the minimum number of seconds required to close all the tabs outside the segment [l, r].


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

Output
5

Input
6 3 1 3

Output
1

Input
5 2 1 5

Output
0



-----Note-----

In the first test Luba can do the following operations: shift the mouse cursor to the tab 2, close all the tabs to the left of it, shift the mouse cursor to the tab 3, then to the tab 4, and then close all the tabs to the right of it.

In the second test she only needs to close all the tabs to the right of the current position of the cursor.

In the third test Luba doesn't need to do anything.
user: You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads! 

 $m$ 

Initially Zmei Gorynich has $x$ heads. You can deal $n$ types of blows. If you deal a blow of the $i$-th type, you decrease the number of Gorynich's heads by $min(d_i, curX)$, there $curX$ is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows $h_i$ new heads. If $curX = 0$ then Gorynich is defeated. 

You can deal each blow any number of times, in any order.

For example, if $curX = 10$, $d = 7$, $h = 10$ then the number of heads changes to $13$ (you cut $7$ heads off, but then Zmei grows $10$ new ones), but if $curX = 10$, $d = 11$, $h = 100$ then number of heads changes to $0$ and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) – the number of queries.

The first line of each query contains two integers $n$ and $x$ ($1 \le n \le 100$, $1 \le x \le 10^9$) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following $n$ lines of each query contain the descriptions of types of blows you can deal. The $i$-th line contains two integers $d_i$ and $h_i$ ($1 \le d_i, h_i \le 10^9$) — the description of the $i$-th blow.


-----Output-----

For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich. 

If Zmei Gorynuch cannot be defeated print $-1$.


-----Example-----
Input
3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100

Output
2
3
-1



-----Note-----

In the first query you can deal the first blow (after that the number of heads changes to $10 - 6 + 3 = 7$), and then deal the second blow.

In the second query you just deal the first blow three times, and Zmei is defeated. 

In third query you can not defeat Zmei Gorynich. Maybe it's better to convince it to stop fighting?
user: Anton likes to listen to fairy tales, especially when Danik, Anton's best friend, tells them. Right now Danik tells Anton a fairy tale:

"Once upon a time, there lived an emperor. He was very rich and had much grain. One day he ordered to build a huge barn to put there all his grain. Best builders were building that barn for three days and three nights. But they overlooked and there remained a little hole in the barn, from which every day sparrows came through. Here flew a sparrow, took a grain and flew away..."

More formally, the following takes place in the fairy tale. At the beginning of the first day the barn with the capacity of n grains was full. Then, every day (starting with the first day) the following happens:  m grains are brought to the barn. If m grains doesn't fit to the barn, the barn becomes full and the grains that doesn't fit are brought back (in this problem we can assume that the grains that doesn't fit to the barn are not taken into account).  Sparrows come and eat grain. In the i-th day i sparrows come, that is on the first day one sparrow come, on the second day two sparrows come and so on. Every sparrow eats one grain. If the barn is empty, a sparrow eats nothing. 

Anton is tired of listening how Danik describes every sparrow that eats grain from the barn. Anton doesn't know when the fairy tale ends, so he asked you to determine, by the end of which day the barn will become empty for the first time. Help Anton and write a program that will determine the number of that day!


-----Input-----

The only line of the input contains two integers n and m (1 ≤ n, m ≤ 10^18) — the capacity of the barn and the number of grains that are brought every day.


-----Output-----

Output one integer — the number of the day when the barn will become empty for the first time. Days are numbered starting with one.


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

Output
4

Input
8 1

Output
5



-----Note-----

In the first sample the capacity of the barn is five grains and two grains are brought every day. The following happens:  At the beginning of the first day grain is brought to the barn. It's full, so nothing happens.  At the end of the first day one sparrow comes and eats one grain, so 5 - 1 = 4 grains remain.  At the beginning of the second day two grains are brought. The barn becomes full and one grain doesn't fit to it.  At the end of the second day two sparrows come. 5 - 2 = 3 grains remain.  At the beginning of the third day two grains are brought. The barn becomes full again.  At the end of the third day three sparrows come and eat grain. 5 - 3 = 2 grains remain.  At the beginning of the fourth day grain is brought again. 2 + 2 = 4 grains remain.  At the end of the fourth day four sparrows come and eat grain. 4 - 4 = 0 grains remain. The barn is empty. 

So the answer is 4, because by the end of the fourth day the barn becomes empty.
user: Tokitsukaze is playing a game derivated from Japanese mahjong. In this game, she has three tiles in her hand. Each tile she owns is a suited tile, which means it has a suit (manzu, pinzu or souzu) and a number (a digit ranged from $1$ to $9$). In this problem, we use one digit and one lowercase letter, which is the first character of the suit, to represent a suited tile. All possible suited tiles are represented as 1m, 2m, $\ldots$, 9m, 1p, 2p, $\ldots$, 9p, 1s, 2s, $\ldots$, 9s.

In order to win the game, she must have at least one mentsu (described below) in her hand, so sometimes she should draw extra suited tiles. After drawing a tile, the number of her tiles increases by one. She can draw any tiles she wants, including those already in her hand.

Do you know the minimum number of extra suited tiles she needs to draw so that she can win?

Here are some useful definitions in this game:  A mentsu, also known as meld, is formed by a koutsu or a shuntsu;  A koutsu, also known as triplet, is made of three identical tiles, such as [1m, 1m, 1m], however, [1m, 1p, 1s] or [1m, 4m, 7m] is NOT a koutsu;  A shuntsu, also known as sequence, is made of three sequential numbered tiles in the same suit, such as [1m, 2m, 3m] and [5s, 7s, 6s], however, [9m, 1m, 2m] or [1m, 2p, 3s] is NOT a shuntsu. 

Some examples:   [2m, 3p, 2s, 4m, 1s, 2s, 4s] — it contains no koutsu or shuntsu, so it includes no mentsu;  [4s, 3m, 3p, 4s, 5p, 4s, 5p] — it contains a koutsu, [4s, 4s, 4s], but no shuntsu, so it includes a mentsu;  [5p, 5s, 9m, 4p, 1s, 7p, 7m, 6p] — it contains no koutsu but a shuntsu, [5p, 4p, 6p] or [5p, 7p, 6p], so it includes a mentsu. 

Note that the order of tiles is unnecessary and you can assume the number of each type of suited tiles she can draw is infinite.


-----Input-----

The only line contains three strings — the tiles in Tokitsukaze's hand. For each string, the first character is a digit ranged from $1$ to $9$ and the second character is m, p or s.


-----Output-----

Print a single integer — the minimum number of extra suited tiles she needs to draw.


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

Output
0

Input
9m 9m 9m

Output
0

Input
3p 9m 2p

Output
1



-----Note-----

In the first example, Tokitsukaze already has a shuntsu.

In the second example, Tokitsukaze already has a koutsu.

In the third example, Tokitsukaze can get a shuntsu by drawing one suited tile — 1p or 4p. The resulting tiles will be [3p, 9m, 2p, 1p] or [3p, 9m, 2p, 4p].
user: Yet another round on DecoForces is coming! Grandpa Maks wanted to participate in it but someone has stolen his precious sofa! And how can one perform well with such a major loss?

Fortunately, the thief had left a note for Grandpa Maks. This note got Maks to the sofa storehouse. Still he had no idea which sofa belongs to him as they all looked the same!

The storehouse is represented as matrix n × m. Every sofa takes two neighbouring by some side cells. No cell is covered by more than one sofa. There can be empty cells.

Sofa A is standing to the left of sofa B if there exist two such cells a and b that x_{a} < x_{b}, a is covered by A and b is covered by B. Sofa A is standing to the top of sofa B if there exist two such cells a and b that y_{a} < y_{b}, a is covered by A and b is covered by B. Right and bottom conditions are declared the same way. 

Note that in all conditions A ≠ B. Also some sofa A can be both to the top of another sofa B and to the bottom of it. The same is for left and right conditions.

The note also stated that there are cnt_{l} sofas to the left of Grandpa Maks's sofa, cnt_{r} — to the right, cnt_{t} — to the top and cnt_{b} — to the bottom.

Grandpa Maks asks you to help him to identify his sofa. It is guaranteed that there is no more than one sofa of given conditions.

Output the number of Grandpa Maks's sofa. If there is no such sofa that all the conditions are met for it then output -1.


-----Input-----

The first line contains one integer number d (1 ≤ d ≤ 10^5) — the number of sofas in the storehouse.

The second line contains two integer numbers n, m (1 ≤ n, m ≤ 10^5) — the size of the storehouse.

Next d lines contains four integer numbers x_1, y_1, x_2, y_2 (1 ≤ x_1, x_2 ≤ n, 1 ≤ y_1, y_2 ≤ m) — coordinates of the i-th sofa. It is guaranteed that cells (x_1, y_1) and (x_2, y_2) have common side, (x_1, y_1)  ≠  (x_2, y_2) and no cell is covered by more than one sofa.

The last line contains four integer numbers cnt_{l}, cnt_{r}, cnt_{t}, cnt_{b} (0 ≤ cnt_{l}, cnt_{r}, cnt_{t}, cnt_{b} ≤ d - 1).


-----Output-----

Print the number of the sofa for which all the conditions are met. Sofas are numbered 1 through d as given in input. If there is no such sofa then print -1.


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

Output
1

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

Output
2

Input
2
2 2
2 1 1 1
1 2 2 2
1 0 0 0

Output
-1



-----Note-----

Let's consider the second example.   The first sofa has 0 to its left, 2 sofas to its right ((1, 1) is to the left of both (5, 5) and (5, 4)), 0 to its top and 2 to its bottom (both 2nd and 3rd sofas are below).  The second sofa has cnt_{l} = 2, cnt_{r} = 1, cnt_{t} = 2 and cnt_{b} = 0.  The third sofa has cnt_{l} = 2, cnt_{r} = 1, cnt_{t} = 1 and cnt_{b} = 1. 

So the second one corresponds to the given conditions.

In the third example   The first sofa has cnt_{l} = 1, cnt_{r} = 1, cnt_{t} = 0 and cnt_{b} = 1.  The second sofa has cnt_{l} = 1, cnt_{r} = 1, cnt_{t} = 1 and cnt_{b} = 0. 

And there is no sofa with the set (1, 0, 0, 0) so the answer is -1.
user: On the planet Mars a year lasts exactly n days (there are no leap years on Mars). But Martians have the same weeks as earthlings — 5 work days and then 2 days off. Your task is to determine the minimum possible and the maximum possible number of days off per year on Mars.


-----Input-----

The first line of the input contains a positive integer n (1 ≤ n ≤ 1 000 000) — the number of days in a year on Mars.


-----Output-----

Print two integers — the minimum possible and the maximum possible number of days off per year on Mars.


-----Examples-----
Input
14

Output
4 4

Input
2

Output
0 2



-----Note-----

In the first sample there are 14 days in a year on Mars, and therefore independently of the day a year starts with there will be exactly 4 days off .

In the second sample there are only 2 days in a year on Mars, and they can both be either work days or days off.
user: Little Joty has got a task to do. She has a line of n tiles indexed from 1 to n. She has to paint them in a strange pattern.

An unpainted tile should be painted Red if it's index is divisible by a and an unpainted tile should be painted Blue if it's index is divisible by b. So the tile with the number divisible by a and b can be either painted Red or Blue.

After her painting is done, she will get p chocolates for each tile that is painted Red and q chocolates for each tile that is painted Blue.

Note that she can paint tiles in any order she wants.

Given the required information, find the maximum number of chocolates Joty can get.


-----Input-----

The only line contains five integers n, a, b, p and q (1 ≤ n, a, b, p, q ≤ 10^9).


-----Output-----

Print the only integer s — the maximum number of chocolates Joty can get.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Examples-----
Input
5 2 3 12 15

Output
39

Input
20 2 3 3 5

Output
51
user: Vova has won $n$ trophies in different competitions. Each trophy is either golden or silver. The trophies are arranged in a row.

The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.

Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of trophies.

The second line contains $n$ characters, each of them is either G or S. If the $i$-th character is G, then the $i$-th trophy is a golden one, otherwise it's a silver trophy. 


-----Output-----

Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.


-----Examples-----
Input
10
GGGSGGGSGG

Output
7

Input
4
GGGG

Output
4

Input
3
SSS

Output
0



-----Note-----

In the first example Vova has to swap trophies with indices $4$ and $10$. Thus he will obtain the sequence "GGGGGGGSGS", the length of the longest subsegment of golden trophies is $7$. 

In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is $4$. 

In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than $0$.
user: Now you can take online courses in the Berland State University! Polycarp needs to pass k main online courses of his specialty to get a diploma. In total n courses are availiable for the passage.

The situation is complicated by the dependence of online courses, for each course there is a list of those that must be passed before starting this online course (the list can be empty, it means that there is no limitation).

Help Polycarp to pass the least number of courses in total to get the specialty (it means to pass all main and necessary courses). Write a program which prints the order of courses. 

Polycarp passes courses consistently, he starts the next course when he finishes the previous one. Each course can't be passed more than once. 


-----Input-----

The first line contains n and k (1 ≤ k ≤ n ≤ 10^5) — the number of online-courses and the number of main courses of Polycarp's specialty. 

The second line contains k distinct integers from 1 to n — numbers of main online-courses of Polycarp's specialty. 

Then n lines follow, each of them describes the next course: the i-th of them corresponds to the course i. Each line starts from the integer t_{i} (0 ≤ t_{i} ≤ n - 1) — the number of courses on which the i-th depends. Then there follows the sequence of t_{i} distinct integers from 1 to n — numbers of courses in random order, on which the i-th depends. It is guaranteed that no course can depend on itself. 

It is guaranteed that the sum of all values t_{i} doesn't exceed 10^5. 


-----Output-----

Print -1, if there is no the way to get a specialty. 

Otherwise, in the first line print the integer m — the minimum number of online-courses which it is necessary to pass to get a specialty. In the second line print m distinct integers — numbers of courses which it is necessary to pass in the chronological order of their passage. If there are several answers it is allowed to print any of them.


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

Output
5
1 2 3 4 5 

Input
9 3
3 9 5
0
0
3 9 4 5
0
0
1 8
1 6
1 2
2 1 2

Output
6
1 2 9 4 5 3 

Input
3 3
1 2 3
1 2
1 3
1 1

Output
-1



-----Note-----

In the first test firstly you can take courses number 1 and 2, after that you can take the course number 4, then you can take the course number 5, which is the main. After that you have to take only the course number 3, which is the last not passed main course.