meetforever/GRPO_CL huggingface dataset:
user: It is raining heavily. But this is the first day for Serval, who just became 3 years old, to go to the kindergarten. Unfortunately, he lives far from kindergarten, and his father is too busy to drive him there. The only choice for this poor little boy is to wait for a bus on this rainy day. Under such circumstances, the poor boy will use the first bus he sees no matter where it goes. If several buses come at the same time, he will choose one randomly.

Serval will go to the bus station at time $t$, and there are $n$ bus routes which stop at this station. For the $i$-th bus route, the first bus arrives at time $s_i$ minutes, and each bus of this route comes $d_i$ minutes later than the previous one.

As Serval's best friend, you wonder which bus route will he get on. If several buses arrive at the same time, you can print any of them.


-----Input-----

The first line contains two space-separated integers $n$ and $t$ ($1\leq n\leq 100$, $1\leq t\leq 10^5$) — the number of bus routes and the time Serval goes to the station. 

Each of the next $n$ lines contains two space-separated integers $s_i$ and $d_i$ ($1\leq s_i,d_i\leq 10^5$) — the time when the first bus of this route arrives and the interval between two buses of this route.


-----Output-----

Print one number — what bus route Serval will use. If there are several possible answers, you can print any of them.


-----Examples-----
Input
2 2
6 4
9 5

Output
1

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

Output
3

Input
3 7
2 2
2 3
2 4

Output
1



-----Note-----

In the first example, the first bus of the first route arrives at time $6$, and the first bus of the second route arrives at time $9$, so the first route is the answer.

In the second example, a bus of the third route arrives at time $5$, so it is the answer.

In the third example, buses of the first route come at times $2$, $4$, $6$, $8$, and so fourth, buses of the second route come at times $2$, $5$, $8$, and so fourth and buses of the third route come at times $2$, $6$, $10$, and so on, so $1$ and $2$ are both acceptable answers while $3$ is not.
user: One day, after a difficult lecture a diligent student Sasha saw a graffitied desk in the classroom. She came closer and read: "Find such positive integer n, that among numbers n + 1, n + 2, ..., 2·n there are exactly m numbers which binary representation contains exactly k digits one".

The girl got interested in the task and she asked you to help her solve it. Sasha knows that you are afraid of large numbers, so she guaranteed that there is an answer that doesn't exceed 10^18.


-----Input-----

The first line contains two space-separated integers, m and k (0 ≤ m ≤ 10^18; 1 ≤ k ≤ 64).


-----Output-----

Print the required number n (1 ≤ n ≤ 10^18). If there are multiple answers, print any of them.


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

Output
1

Input
3 2

Output
5
user: In this problem you will meet the simplified model of game King of Thieves.

In a new ZeptoLab game called "King of Thieves" your aim is to reach a chest with gold by controlling your character, avoiding traps and obstacles on your way. [Image] 

An interesting feature of the game is that you can design your own levels that will be available to other players. Let's consider the following simple design of a level.

A dungeon consists of n segments located at a same vertical level, each segment is either a platform that character can stand on, or a pit with a trap that makes player lose if he falls into it. All segments have the same length, platforms on the scheme of the level are represented as '*' and pits are represented as '.'. 

One of things that affects speedrun characteristics of the level is a possibility to perform a series of consecutive jumps of the same length. More formally, when the character is on the platform number i_1, he can make a sequence of jumps through the platforms i_1 < i_2 < ... < i_{k}, if i_2 - i_1 = i_3 - i_2 = ... = i_{k} - i_{k} - 1. Of course, all segments i_1, i_2, ... i_{k} should be exactly the platforms, not pits. 

Let's call a level to be good if you can perform a sequence of four jumps of the same length or in the other words there must be a sequence i_1, i_2, ..., i_5, consisting of five platforms so that the intervals between consecutive platforms are of the same length. Given the scheme of the level, check if it is good.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of segments on the level.

Next line contains the scheme of the level represented as a string of n characters '*' and '.'.


-----Output-----

If the level is good, print the word "yes" (without the quotes), otherwise print the word "no" (without the quotes).


-----Examples-----
Input
16
.**.*..*.***.**.

Output
yes
Input
11
.*.*...*.*.

Output
no


-----Note-----

In the first sample test you may perform a sequence of jumps through platforms 2, 5, 8, 11, 14.
user: ZS the Coder and Chris the Baboon arrived at the entrance of Udayland. There is a n × n magic grid on the entrance which is filled with integers. Chris noticed that exactly one of the cells in the grid is empty, and to enter Udayland, they need to fill a positive integer into the empty cell.

Chris tried filling in random numbers but it didn't work. ZS the Coder realizes that they need to fill in a positive integer such that the numbers in the grid form a magic square. This means that he has to fill in a positive integer so that the sum of the numbers in each row of the grid ($\sum a_{r, i}$), each column of the grid ($\sum a_{i, c}$), and the two long diagonals of the grid (the main diagonal — $\sum a_{i, i}$ and the secondary diagonal — $\sum a_{i, n - i + 1}$) are equal. 

Chris doesn't know what number to fill in. Can you help Chris find the correct positive integer to fill in or determine that it is impossible?


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the number of rows and columns of the magic grid.

n lines follow, each of them contains n integers. The j-th number in the i-th of them denotes a_{i}, j (1 ≤ a_{i}, j ≤ 10^9 or a_{i}, j = 0), the number in the i-th row and j-th column of the magic grid. If the corresponding cell is empty, a_{i}, j will be equal to 0. Otherwise, a_{i}, j is positive.

It is guaranteed that there is exactly one pair of integers i, j (1 ≤ i, j ≤ n) such that a_{i}, j = 0.


-----Output-----

Output a single integer, the positive integer x (1 ≤ x ≤ 10^18) that should be filled in the empty cell so that the whole grid becomes a magic square. If such positive integer x does not exist, output  - 1 instead.

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


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

Output
9

Input
4
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1

Output
1

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

Output
-1



-----Note-----

In the first sample case, we can fill in 9 into the empty cell to make the resulting grid a magic square. Indeed, 

The sum of numbers in each row is:

4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.

The sum of numbers in each column is:

4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.

The sum of numbers in the two diagonals is:

4 + 5 + 6 = 2 + 5 + 8 = 15.

In the third sample case, it is impossible to fill a number in the empty square such that the resulting grid is a magic square.
user: There are $n$ benches in the Berland Central park. It is known that $a_i$ people are currently sitting on the $i$-th bench. Another $m$ people are coming to the park and each of them is going to have a seat on some bench out of $n$ available.

Let $k$ be the maximum number of people sitting on one bench after additional $m$ people came to the park. Calculate the minimum possible $k$ and the maximum possible $k$.

Nobody leaves the taken seat during the whole process.


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 100)$ — the number of benches in the park.

The second line contains a single integer $m$ $(1 \le m \le 10\,000)$ — the number of people additionally coming to the park.

Each of the next $n$ lines contains a single integer $a_i$ $(1 \le a_i \le 100)$ — the initial number of people on the $i$-th bench.


-----Output-----

Print the minimum possible $k$ and the maximum possible $k$, where $k$ is the maximum number of people sitting on one bench after additional $m$ people came to the park.


-----Examples-----
Input
4
6
1
1
1
1

Output
3 7

Input
1
10
5

Output
15 15

Input
3
6
1
6
5

Output
6 12

Input
3
7
1
6
5

Output
7 13



-----Note-----

In the first example, each of four benches is occupied by a single person. The minimum $k$ is $3$. For example, it is possible to achieve if two newcomers occupy the first bench, one occupies the second bench, one occupies the third bench, and two remaining — the fourth bench. The maximum $k$ is $7$. That requires all six new people to occupy the same bench.

The second example has its minimum $k$ equal to $15$ and maximum $k$ equal to $15$, as there is just a single bench in the park and all $10$ people will occupy it.
user: There is an airplane which has n rows from front to back. There will be m people boarding this airplane.

This airplane has an entrance at the very front and very back of the plane.

Each person has some assigned seat. It is possible for multiple people to have the same assigned seat. The people will then board the plane one by one starting with person 1. Each person can independently choose either the front entrance or back entrance to enter the plane.

When a person walks into the plane, they walk directly to their assigned seat and will try to sit in it. If it is occupied, they will continue walking in the direction they walked in until they are at empty seat - they will take the earliest empty seat that they can find. If they get to the end of the row without finding a seat, they will be angry.

Find the number of ways to assign tickets to the passengers and board the plane without anyone getting angry. Two ways are different if there exists a passenger who chose a different entrance in both ways, or the assigned seat is different. Print this count modulo 10^9 + 7.


-----Input-----

The first line of input will contain two integers n, m (1 ≤ m ≤ n ≤ 1 000 000), the number of seats, and the number of passengers, respectively.


-----Output-----

Print a single number, the number of ways, modulo 10^9 + 7.


-----Example-----
Input
3 3

Output
128



-----Note-----

Here, we will denote a passenger by which seat they were assigned, and which side they came from (either "F" or "B" for front or back, respectively).

For example, one valid way is 3B, 3B, 3B (i.e. all passengers were assigned seat 3 and came from the back entrance). Another valid way would be 2F, 1B, 3F.

One invalid way would be 2B, 2B, 2B, since the third passenger would get to the front without finding a seat.
user: A company of $n$ friends wants to order exactly two pizzas. It is known that in total there are $9$ pizza ingredients in nature, which are denoted by integers from $1$ to $9$.

Each of the $n$ friends has one or more favorite ingredients: the $i$-th of friends has the number of favorite ingredients equal to $f_i$ ($1 \le f_i \le 9$) and your favorite ingredients form the sequence $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

The website of CodePizza restaurant has exactly $m$ ($m \ge 2$) pizzas. Each pizza is characterized by a set of $r_j$ ingredients $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le r_j \le 9$, $1 \le a_{jt} \le 9$) , which are included in it, and its price is $c_j$.

Help your friends choose exactly two pizzas in such a way as to please the maximum number of people in the company. It is known that a person is pleased with the choice if each of his/her favorite ingredients is in at least one ordered pizza. If there are several ways to choose two pizzas so as to please the maximum number of friends, then choose the one that minimizes the total price of two pizzas.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5, 2 \le m \le 10^5$) — the number of friends in the company and the number of pizzas, respectively.

Next, the $n$ lines contain descriptions of favorite ingredients of the friends: the $i$-th of them contains the number of favorite ingredients $f_i$ ($1 \le f_i \le 9$) and a sequence of distinct integers $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

Next, the $m$ lines contain pizza descriptions: the $j$-th of them contains the integer price of the pizza $c_j$ ($1 \le c_j \le 10^9$), the number of ingredients $r_j$ ($1 \le r_j \le 9$) and the ingredients themselves as a sequence of distinct integers $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le a_{jt} \le 9$).


-----Output-----

Output two integers $j_1$ and $j_2$ ($1 \le j_1,j_2 \le m$, $j_1 \ne j_2$) denoting the indices of two pizzas in the required set. If there are several solutions, output any of them. Pizza indices can be printed in any order.


-----Examples-----
Input
3 4
2 6 7
4 2 3 9 5
3 2 3 9
100 1 7
400 3 3 2 5
100 2 9 2
500 3 2 9 5

Output
2 3

Input
4 3
1 1
1 2
1 3
1 4
10 4 1 2 3 4
20 4 1 2 3 4
30 4 1 2 3 4

Output
1 2

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

Output
2 4
user: You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be non-negative integers written in the decimal base without leading zeroes.


-----Input-----

The single line of the input contains a pair of integers m, s (1 ≤ m ≤ 100, 0 ≤ s ≤ 900) — the length and the sum of the digits of the required numbers.


-----Output-----

In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers "-1 -1" (without the quotes).


-----Examples-----
Input
2 15

Output
69 96

Input
3 0

Output
-1 -1
user: You are given two integers $l$ and $r$ ($l \le r$). Your task is to calculate the sum of numbers from $l$ to $r$ (including $l$ and $r$) such that each number contains at most $k$ different digits, and print this sum modulo $998244353$.

For example, if $k = 1$ then you have to calculate all numbers from $l$ to $r$ such that each number is formed using only one digit. For $l = 10, r = 50$ the answer is $11 + 22 + 33 + 44 = 110$.


-----Input-----

The only line of the input contains three integers $l$, $r$ and $k$ ($1 \le l \le r < 10^{18}, 1 \le k \le 10$) — the borders of the segment and the maximum number of different digits.


-----Output-----

Print one integer — the sum of numbers from $l$ to $r$ such that each number contains at most $k$ different digits, modulo $998244353$.


-----Examples-----
Input
10 50 2

Output
1230

Input
1 2345 10

Output
2750685

Input
101 154 2

Output
2189



-----Note-----

For the first example the answer is just the sum of numbers from $l$ to $r$ which equals to $\frac{50 \cdot 51}{2} - \frac{9 \cdot 10}{2} = 1230$. This example also explained in the problem statement but for $k = 1$.

For the second example the answer is just the sum of numbers from $l$ to $r$ which equals to $\frac{2345 \cdot 2346}{2} = 2750685$.

For the third example the answer is $101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189$.
user: Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be represented as a sequence a_1, a_2, ..., a_{n} of n integer numbers — saturation of the color of each pencil. Now Mishka wants to put all the mess in the pack in order. He has an infinite number of empty boxes to do this. He would like to fill some boxes in such a way that:

  Each pencil belongs to exactly one box;  Each non-empty box has at least k pencils in it;  If pencils i and j belong to the same box, then |a_{i} - a_{j}| ≤ d, where |x| means absolute value of x. Note that the opposite is optional, there can be pencils i and j such that |a_{i} - a_{j}| ≤ d and they belong to different boxes. 

Help Mishka to determine if it's possible to distribute all the pencils into boxes. Print "YES" if there exists such a distribution. Otherwise print "NO".


-----Input-----

The first line contains three integer numbers n, k and d (1 ≤ k ≤ n ≤ 5·10^5, 0 ≤ d ≤ 10^9) — the number of pencils, minimal size of any non-empty box and maximal difference in saturation between any pair of pencils in the same box, respectively.

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — saturation of color of each pencil.


-----Output-----

Print "YES" if it's possible to distribute all the pencils into boxes and satisfy all the conditions. Otherwise print "NO".


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

Output
YES

Input
6 2 3
4 5 3 13 4 10

Output
YES

Input
3 2 5
10 16 22

Output
NO



-----Note-----

In the first example it is possible to distribute pencils into 2 boxes with 3 pencils in each with any distribution. And you also can put all the pencils into the same box, difference of any pair in it won't exceed 10.

In the second example you can split pencils of saturations [4, 5, 3, 4] into 2 boxes of size 2 and put the remaining ones into another box.
user: Nothing is eternal in the world, Kostya understood it on the 7-th of January when he saw partially dead four-color garland.

Now he has a goal to replace dead light bulbs, however he doesn't know how many light bulbs for each color are required. It is guaranteed that for each of four colors at least one light is working.

It is known that the garland contains light bulbs of four colors: red, blue, yellow and green. The garland is made as follows: if you take any four consecutive light bulbs then there will not be light bulbs with the same color among them. For example, the garland can look like "RYBGRYBGRY", "YBGRYBGRYBG", "BGRYB", but can not look like "BGRYG", "YBGRYBYGR" or "BGYBGY". Letters denote colors: 'R' — red, 'B' — blue, 'Y' — yellow, 'G' — green.

Using the information that for each color at least one light bulb still works count the number of dead light bulbs of each four colors.


-----Input-----

The first and the only line contains the string s (4 ≤ |s| ≤ 100), which describes the garland, the i-th symbol of which describes the color of the i-th light bulb in the order from the beginning of garland:   'R' — the light bulb is red,  'B' — the light bulb is blue,  'Y' — the light bulb is yellow,  'G' — the light bulb is green,  '!' — the light bulb is dead. 

The string s can not contain other symbols except those five which were described. 

It is guaranteed that in the given string at least once there is each of four letters 'R', 'B', 'Y' and 'G'. 

It is guaranteed that the string s is correct garland with some blown light bulbs, it means that for example the line "GRBY!!!B" can not be in the input data. 


-----Output-----

In the only line print four integers k_{r}, k_{b}, k_{y}, k_{g} — the number of dead light bulbs of red, blue, yellow and green colors accordingly.


-----Examples-----
Input
RYBGRYBGR

Output
0 0 0 0
Input
!RGYB

Output
0 1 0 0
Input
!!!!YGRB

Output
1 1 1 1
Input
!GB!RG!Y!

Output
2 1 1 0


-----Note-----

In the first example there are no dead light bulbs.

In the second example it is obvious that one blue bulb is blown, because it could not be light bulbs of other colors on its place according to the statements.
user: There is a cave consisting of N rooms and M one-directional passages. The rooms are numbered 1 through N.
Takahashi is now in Room 1, and Room N has the exit. The i-th passage connects Room s_i and Room t_i (s_i < t_i) and can only be traversed in the direction from Room s_i to Room t_i. It is known that, for each room except Room N, there is at least one passage going from that room.
Takahashi will escape from the cave. Each time he reaches a room (assume that he has reached Room 1 at the beginning), he will choose a passage uniformly at random from the ones going from that room and take that passage.
Aoki, a friend of Takahashi's, can block one of the passages (or do nothing) before Takahashi leaves Room 1. However, it is not allowed to block a passage so that Takahashi is potentially unable to reach Room N.
Let E be the expected number of passages Takahashi takes before he reaches Room N. Find the value of E when Aoki makes a choice that minimizes E.

-----Constraints-----
 - 2 \leq N \leq 600
 - N-1 \leq M \leq \frac{N(N-1)}{2}
 - s_i < t_i
 - If i != j, (s_i, t_i) \neq (s_j, t_j). (Added 21:23 JST)
 - For every v = 1, 2, ..., N-1, there exists i such that v = s_i.

-----Input-----
Input is given from Standard Input in the following format:
N M
s_1 t_1
:
s_M t_M

-----Output-----
Print the value of E when Aoki makes a choice that minimizes E.
Your output will be judged as correct when the absolute or relative error from the judge's output is at most 10^{-6}.

-----Sample Input-----
4 6
1 4
2 3
1 3
1 2
3 4
2 4

-----Sample Output-----
1.5000000000

If Aoki blocks the passage from Room 1 to Room 2, Takahashi will go along the path 1 → 3 → 4 with probability \frac{1}{2} and 1 → 4 with probability \frac{1}{2}. E = 1.5 here, and this is the minimum possible value of E.
user: Vasya has a non-negative integer n. He wants to round it to nearest integer, which ends up with 0. If n already ends up with 0, Vasya considers it already rounded.

For example, if n = 4722 answer is 4720. If n = 5 Vasya can round it to 0 or to 10. Both ways are correct.

For given n find out to which integer will Vasya round it.


-----Input-----

The first line contains single integer n (0 ≤ n ≤ 10^9) — number that Vasya has.


-----Output-----

Print result of rounding n. Pay attention that in some cases answer isn't unique. In that case print any correct answer.


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

Output
0

Input
113

Output
110

Input
1000000000

Output
1000000000

Input
5432359

Output
5432360



-----Note-----

In the first example n = 5. Nearest integers, that ends up with zero are 0 and 10. Any of these answers is correct, so you can print 0 or 10.
user: Santa Claus decided to disassemble his keyboard to clean it. After he returned all the keys back, he suddenly realized that some pairs of keys took each other's place! That is, Santa suspects that each key is either on its place, or on the place of another key, which is located exactly where the first key should be. 

In order to make sure that he's right and restore the correct order of keys, Santa typed his favorite patter looking only to his keyboard.

You are given the Santa's favorite patter and the string he actually typed. Determine which pairs of keys could be mixed. Each key must occur in pairs at most once.


-----Input-----

The input consists of only two strings s and t denoting the favorite Santa's patter and the resulting string. s and t are not empty and have the same length, which is at most 1000. Both strings consist only of lowercase English letters.


-----Output-----

If Santa is wrong, and there is no way to divide some of keys into pairs and swap keys in each pair so that the keyboard will be fixed, print «-1» (without quotes).

Otherwise, the first line of output should contain the only integer k (k ≥ 0) — the number of pairs of keys that should be swapped. The following k lines should contain two space-separated letters each, denoting the keys which should be swapped. All printed letters must be distinct.

If there are several possible answers, print any of them. You are free to choose the order of the pairs and the order of keys in a pair.

Each letter must occur at most once. Santa considers the keyboard to be fixed if he can print his favorite patter without mistakes.


-----Examples-----
Input
helloworld
ehoolwlroz

Output
3
h e
l o
d z

Input
hastalavistababy
hastalavistababy

Output
0

Input
merrychristmas
christmasmerry

Output
-1