meetforever/GRPO_CL huggingface dataset:
user: A new dog show on TV is starting next week. On the show dogs are required to demonstrate bottomless stomach, strategic thinking and self-preservation instinct. You and your dog are invited to compete with other participants and naturally you want to win!

On the show a dog needs to eat as many bowls of dog food as possible (bottomless stomach helps here). Dogs compete separately of each other and the rules are as follows:

At the start of the show the dog and the bowls are located on a line. The dog starts at position x = 0 and n bowls are located at positions x = 1, x = 2, ..., x = n. The bowls are numbered from 1 to n from left to right. After the show starts the dog immediately begins to run to the right to the first bowl.

The food inside bowls is not ready for eating at the start because it is too hot (dog's self-preservation instinct prevents eating). More formally, the dog can eat from the i-th bowl after t_{i} seconds from the start of the show or later.

It takes dog 1 second to move from the position x to the position x + 1. The dog is not allowed to move to the left, the dog runs only to the right with the constant speed 1 distance unit per second. When the dog reaches a bowl (say, the bowl i), the following cases are possible:  the food had cooled down (i.e. it passed at least t_{i} seconds from the show start): the dog immediately eats the food and runs to the right without any stop,  the food is hot (i.e. it passed less than t_{i} seconds from the show start): the dog has two options: to wait for the i-th bowl, eat the food and continue to run at the moment t_{i} or to skip the i-th bowl and continue to run to the right without any stop. 

After T seconds from the start the show ends. If the dog reaches a bowl of food at moment T the dog can not eat it. The show stops before T seconds if the dog had run to the right of the last bowl.

You need to help your dog create a strategy with which the maximum possible number of bowls of food will be eaten in T seconds.


-----Input-----

Two integer numbers are given in the first line - n and T (1 ≤ n ≤ 200 000, 1 ≤ T ≤ 2·10^9) — the number of bowls of food and the time when the dog is stopped.

On the next line numbers t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ 10^9) are given, where t_{i} is the moment of time when the i-th bowl of food is ready for eating.


-----Output-----

Output a single integer — the maximum number of bowls of food the dog will be able to eat in T seconds.


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

Output
2

Input
1 2
1

Output
1

Input
1 1
1

Output
0



-----Note-----

In the first example the dog should skip the second bowl to eat from the two bowls (the first and the third).
user: Suppose you have two polynomials $A(x) = \sum_{k = 0}^{n} a_{k} x^{k}$ and $B(x) = \sum_{k = 0}^{m} b_{k} x^{k}$. Then polynomial $A(x)$ can be uniquely represented in the following way:$A(x) = B(x) \cdot D(x) + R(x), \operatorname{deg} R(x) < \operatorname{deg} B(x)$

This can be done using long division. Here, $\operatorname{deg} P(x)$ denotes the degree of polynomial P(x). $R(x)$ is called the remainder of division of polynomial $A(x)$ by polynomial $B(x)$, it is also denoted as $A \operatorname{mod} B$. 

Since there is a way to divide polynomials with remainder, we can define Euclid's algorithm of finding the greatest common divisor of two polynomials. The algorithm takes two polynomials $(A, B)$. If the polynomial $B(x)$ is zero, the result is $A(x)$, otherwise the result is the value the algorithm returns for pair $(B, A \operatorname{mod} B)$. On each step the degree of the second argument decreases, so the algorithm works in finite number of steps. But how large that number could be? You are to answer this question. 

You are given an integer n. You have to build two polynomials with degrees not greater than n, such that their coefficients are integers not exceeding 1 by their absolute value, the leading coefficients (ones with the greatest power of x) are equal to one, and the described Euclid's algorithm performs exactly n steps finding their greatest common divisor. Moreover, the degree of the first polynomial should be greater than the degree of the second. By a step of the algorithm we mean the transition from pair $(A, B)$ to pair $(B, A \operatorname{mod} B)$. 


-----Input-----

You are given a single integer n (1 ≤ n ≤ 150) — the number of steps of the algorithm you need to reach.


-----Output-----

Print two polynomials in the following format.

In the first line print a single integer m (0 ≤ m ≤ n) — the degree of the polynomial. 

In the second line print m + 1 integers between  - 1 and 1 — the coefficients of the polynomial, from constant to leading. 

The degree of the first polynomial should be greater than the degree of the second polynomial, the leading coefficients should be equal to 1. Euclid's algorithm should perform exactly n steps when called using these polynomials.

If there is no answer for the given n, print -1.

If there are multiple answer, print any of them.


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

Output
1
0 1
0
1

Input
2

Output
2
-1 0 1
1
0 1



-----Note-----

In the second example you can print polynomials x^2 - 1 and x. The sequence of transitions is(x^2 - 1, x) → (x,  - 1) → ( - 1, 0).

There are two steps in it.
user: The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer x and reduce it to the number of bits set to 1 in the binary representation of x. For example for number 13 it's true that 13_10 = 1101_2, so it has 3 bits set and 13 will be reduced to 3 in one operation.

He calls a number special if the minimum number of operations to reduce it to 1 is k.

He wants to find out how many special numbers exist which are not greater than n. Please help the Travelling Salesman, as he is about to reach his destination!

Since the answer can be large, output it modulo 10^9 + 7.


-----Input-----

The first line contains integer n (1 ≤ n < 2^1000).

The second line contains integer k (0 ≤ k ≤ 1000).

Note that n is given in its binary representation without any leading zeros.


-----Output-----

Output a single integer — the number of special numbers not greater than n, modulo 10^9 + 7.


-----Examples-----
Input
110
2

Output
3

Input
111111011
2

Output
169



-----Note-----

In the first sample, the three special numbers are 3, 5 and 6. They get reduced to 2 in one operation (since there are two set bits in each of 3, 5 and 6) and then to 1 in one more operation (since there is only one set bit in 2).
user: It was recycling day in Kekoland. To celebrate it Adil and Bera went to Central Perk where they can take bottles from the ground and put them into a recycling bin.

We can think Central Perk as coordinate plane. There are n bottles on the ground, the i-th bottle is located at position (x_{i}, y_{i}). Both Adil and Bera can carry only one bottle at once each. 

For both Adil and Bera the process looks as follows:   Choose to stop or to continue to collect bottles.  If the choice was to continue then choose some bottle and walk towards it.  Pick this bottle and walk to the recycling bin.  Go to step 1. 

Adil and Bera may move independently. They are allowed to pick bottles simultaneously, all bottles may be picked by any of the two, it's allowed that one of them stays still while the other one continues to pick bottles.

They want to organize the process such that the total distance they walk (the sum of distance walked by Adil and distance walked by Bera) is minimum possible. Of course, at the end all bottles should lie in the recycling bin.


-----Input-----

First line of the input contains six integers a_{x}, a_{y}, b_{x}, b_{y}, t_{x} and t_{y} (0 ≤ a_{x}, a_{y}, b_{x}, b_{y}, t_{x}, t_{y} ≤ 10^9) — initial positions of Adil, Bera and recycling bin respectively.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of bottles on the ground.

Then follow n lines, each of them contains two integers x_{i} and y_{i} (0 ≤ x_{i}, y_{i} ≤ 10^9) — position of the i-th bottle.

It's guaranteed that positions of Adil, Bera, recycling bin and all bottles are distinct.


-----Output-----

Print one real number — the minimum possible total distance Adil and Bera need to walk in order to put all bottles into recycling bin. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


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

Output
11.084259940083

Input
5 0 4 2 2 0
5
5 2
3 0
5 5
3 5
3 3

Output
33.121375178000



-----Note-----

Consider the first sample.

Adil will use the following path: $(3,1) \rightarrow(2,1) \rightarrow(0,0) \rightarrow(1,1) \rightarrow(0,0)$.

Bera will use the following path: $(1,2) \rightarrow(2,3) \rightarrow(0,0)$.

Adil's path will be $1 + \sqrt{5} + \sqrt{2} + \sqrt{2}$ units long, while Bera's path will be $\sqrt{2} + \sqrt{13}$ units long.
user: Tanechka is shopping in the toy shop. There are exactly $n$ toys in the shop for sale, the cost of the $i$-th toy is $i$ burles. She wants to choose two toys in such a way that their total cost is $k$ burles. How many ways to do that does she have?

Each toy appears in the shop exactly once. Pairs $(a, b)$ and $(b, a)$ are considered equal. Pairs $(a, b)$, where $a=b$, are not allowed.


-----Input-----

The first line of the input contains two integers $n$, $k$ ($1 \le n, k \le 10^{14}$) — the number of toys and the expected total cost of the pair of toys.


-----Output-----

Print the number of ways to choose the pair of toys satisfying the condition above. Print 0, if Tanechka can choose no pair of toys in such a way that their total cost is $k$ burles.


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

Output
2

Input
8 15

Output
1

Input
7 20

Output
0

Input
1000000000000 1000000000001

Output
500000000000



-----Note-----

In the first example Tanechka can choose the pair of toys ($1, 4$) or the pair of toys ($2, 3$).

In the second example Tanechka can choose only the pair of toys ($7, 8$).

In the third example choosing any pair of toys will lead to the total cost less than $20$. So the answer is 0.

In the fourth example she can choose the following pairs: $(1, 1000000000000)$, $(2, 999999999999)$, $(3, 999999999998)$, ..., $(500000000000, 500000000001)$. The number of such pairs is exactly $500000000000$.
user: You've got a string $a_1, a_2, \dots, a_n$, consisting of zeros and ones.

Let's call a sequence of consecutive elements $a_i, a_{i + 1}, \ldots, a_j$ ($1\leq i\leq j\leq n$) a substring of string $a$. 

You can apply the following operations any number of times:  Choose some substring of string $a$ (for example, you can choose entire string) and reverse it, paying $x$ coins for it (for example, «0101101» $\to$ «0111001»);  Choose some substring of string $a$ (for example, you can choose entire string or just one symbol) and replace each symbol to the opposite one (zeros are replaced by ones, and ones — by zeros), paying $y$ coins for it (for example, «0101101» $\to$ «0110001»). 

You can apply these operations in any order. It is allowed to apply the operations multiple times to the same substring.

What is the minimum number of coins you need to spend to get a string consisting only of ones?


-----Input-----

The first line of input contains integers $n$, $x$ and $y$ ($1 \leq n \leq 300\,000, 0 \leq x, y \leq 10^9$) — length of the string, cost of the first operation (substring reverse) and cost of the second operation (inverting all elements of substring).

The second line contains the string $a$ of length $n$, consisting of zeros and ones.


-----Output-----

Print a single integer — the minimum total cost of operations you need to spend to get a string consisting only of ones. Print $0$, if you do not need to perform any operations.


-----Examples-----
Input
5 1 10
01000

Output
11

Input
5 10 1
01000

Output
2

Input
7 2 3
1111111

Output
0



-----Note-----

In the first sample, at first you need to reverse substring $[1 \dots 2]$, and then you need to invert substring $[2 \dots 5]$. 

Then the string was changed as follows:

«01000» $\to$ «10000» $\to$ «11111».

The total cost of operations is $1 + 10 = 11$.

In the second sample, at first you need to invert substring $[1 \dots 1]$, and then you need to invert substring $[3 \dots 5]$. 

Then the string was changed as follows:

«01000» $\to$ «11000» $\to$ «11111».

The overall cost is $1 + 1 = 2$.

In the third example, string already consists only of ones, so the answer is $0$.
user: The well-known Fibonacci sequence $F_0, F_1, F_2,\ldots $ is defined as follows:   $F_0 = 0, F_1 = 1$.  For each $i \geq 2$: $F_i = F_{i - 1} + F_{i - 2}$. 

Given an increasing arithmetic sequence of positive integers with $n$ elements: $(a, a + d, a + 2\cdot d,\ldots, a + (n - 1)\cdot d)$.

You need to find another increasing arithmetic sequence of positive integers with $n$ elements $(b, b + e, b + 2\cdot e,\ldots, b + (n - 1)\cdot e)$ such that:  $0 < b, e < 2^{64}$,  for all $0\leq i < n$, the decimal representation of $a + i \cdot d$ appears as substring in the last $18$ digits of the decimal representation of $F_{b + i \cdot e}$ (if this number has less than $18$ digits, then we consider all its digits). 


-----Input-----

The first line contains three positive integers $n$, $a$, $d$ ($1 \leq n, a, d, a + (n - 1) \cdot d < 10^6$).


-----Output-----

If no such arithmetic sequence exists, print $-1$.

Otherwise, print two integers $b$ and $e$, separated by space in a single line ($0 < b, e < 2^{64}$).

If there are many answers, you can output any of them.


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

Output
2 1
Input
5 1 2

Output
19 5



-----Note-----

In the first test case, we can choose $(b, e) = (2, 1)$, because $F_2 = 1, F_3 = 2, F_4 = 3$.

In the second test case, we can choose $(b, e) = (19, 5)$ because:  $F_{19} = 4181$ contains $1$;  $F_{24} = 46368$ contains $3$;  $F_{29} = 514229$ contains $5$;  $F_{34} = 5702887$ contains $7$;  $F_{39} = 63245986$ contains $9$.
user: The Holmes children are fighting over who amongst them is the cleverest.

Mycroft asked Sherlock and Eurus to find value of f(n), where f(1) = 1 and for n ≥ 2, f(n) is the number of distinct ordered positive integer pairs (x, y) that satisfy x + y = n and gcd(x, y) = 1. The integer gcd(a, b) is the greatest common divisor of a and b.

Sherlock said that solving this was child's play and asked Mycroft to instead get the value of $g(n) = \sum_{d|n} f(n / d)$. Summation is done over all positive integers d that divide n.

Eurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft.

She defined a k-composite function F_{k}(n) recursively as follows:

$F_{k}(n) = \left\{\begin{array}{ll}{f(g(n)),} & {\text{for} k = 1} \\{g(F_{k - 1}(n)),} & {\text{for} k > 1 \text{and} k \operatorname{mod} 2 = 0} \\{f(F_{k - 1}(n)),} & {\text{for} k > 1 \text{and} k \operatorname{mod} 2 = 1} \end{array} \right.$

She wants them to tell the value of F_{k}(n) modulo 1000000007.


-----Input-----

A single line of input contains two space separated integers n (1 ≤ n ≤ 10^12) and k (1 ≤ k ≤ 10^12) indicating that Eurus asks Sherlock and Mycroft to find the value of F_{k}(n) modulo 1000000007.


-----Output-----

Output a single integer — the value of F_{k}(n) modulo 1000000007.


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

Output
6
Input
10 2

Output
4


-----Note-----

In the first case, there are 6 distinct ordered pairs (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) satisfying x + y = 7 and gcd(x, y) = 1. Hence, f(7) = 6. So, F_1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6.
user: Let's call a string a phone number if it has length 11 and fits the pattern "8xxxxxxxxxx", where each "x" is replaced by a digit.

For example, "80123456789" and "80000000000" are phone numbers, while "8012345678" and "79000000000" are not.

You have $n$ cards with digits, and you want to use them to make as many phone numbers as possible. Each card must be used in at most one phone number, and you don't have to use all cards. The phone numbers do not necessarily have to be distinct.


-----Input-----

The first line contains an integer $n$ — the number of cards with digits that you have ($1 \leq n \leq 100$).

The second line contains a string of $n$ digits (characters "0", "1", ..., "9") $s_1, s_2, \ldots, s_n$. The string will not contain any other characters, such as leading or trailing spaces.


-----Output-----

If at least one phone number can be made from these cards, output the maximum number of phone numbers that can be made. Otherwise, output 0.


-----Examples-----
Input
11
00000000008

Output
1

Input
22
0011223344556677889988

Output
2

Input
11
31415926535

Output
0



-----Note-----

In the first example, one phone number, "8000000000", can be made from these cards.

In the second example, you can make two phone numbers from the cards, for example, "80123456789" and "80123456789".

In the third example you can't make any phone number from the given cards.
user: On the way to school, Karen became fixated on the puzzle game on her phone! [Image] 

The game is played as follows. In each level, you have a grid with n rows and m columns. Each cell originally contains the number 0.

One move consists of choosing one row or column, and adding 1 to all of the cells in that row or column.

To win the level, after all the moves, the number in the cell at the i-th row and j-th column should be equal to g_{i}, j.

Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!


-----Input-----

The first line of input contains two integers, n and m (1 ≤ n, m ≤ 100), the number of rows and the number of columns in the grid, respectively.

The next n lines each contain m integers. In particular, the j-th integer in the i-th of these rows contains g_{i}, j (0 ≤ g_{i}, j ≤ 500).


-----Output-----

If there is an error and it is actually not possible to beat the level, output a single integer -1.

Otherwise, on the first line, output a single integer k, the minimum number of moves necessary to beat the level.

The next k lines should each contain one of the following, describing the moves in the order they must be done:  row x, (1 ≤ x ≤ n) describing a move of the form "choose the x-th row".  col x, (1 ≤ x ≤ m) describing a move of the form "choose the x-th column". 

If there are multiple optimal solutions, output any one of them.


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

Output
4
row 1
row 1
col 4
row 3

Input
3 3
0 0 0
0 1 0
0 0 0

Output
-1

Input
3 3
1 1 1
1 1 1
1 1 1

Output
3
row 1
row 2
row 3



-----Note-----

In the first test case, Karen has a grid with 3 rows and 5 columns. She can perform the following 4 moves to beat the level: [Image] 

In the second test case, Karen has a grid with 3 rows and 3 columns. It is clear that it is impossible to beat the level; performing any move will create three 1s on the grid, but it is required to only have one 1 in the center.

In the third test case, Karen has a grid with 3 rows and 3 columns. She can perform the following 3 moves to beat the level: [Image] 

Note that this is not the only solution; another solution, among others, is col 1, col 2, col 3.
user: In some game by Playrix it takes t minutes for an oven to bake k carrot cakes, all cakes are ready at the same moment t minutes after they started baking. Arkady needs at least n cakes to complete a task, but he currently don't have any. However, he has infinitely many ingredients and one oven. Moreover, Arkady can build one more similar oven to make the process faster, it would take d minutes to build the oven. While the new oven is being built, only old one can bake cakes, after the new oven is built, both ovens bake simultaneously. Arkady can't build more than one oven.

Determine if it is reasonable to build the second oven, i.e. will it decrease the minimum time needed to get n cakes or not. If the time needed with the second oven is the same as with one oven, then it is unreasonable.


-----Input-----

The only line contains four integers n, t, k, d (1 ≤ n, t, k, d ≤ 1 000) — the number of cakes needed, the time needed for one oven to bake k cakes, the number of cakes baked at the same time, the time needed to build the second oven. 


-----Output-----

If it is reasonable to build the second oven, print "YES". Otherwise print "NO".


-----Examples-----
Input
8 6 4 5

Output
YES

Input
8 6 4 6

Output
NO

Input
10 3 11 4

Output
NO

Input
4 2 1 4

Output
YES



-----Note-----

In the first example it is possible to get 8 cakes in 12 minutes using one oven. The second oven can be built in 5 minutes, so after 6 minutes the first oven bakes 4 cakes, the second oven bakes 4 more ovens after 11 minutes. Thus, it is reasonable to build the second oven. 

In the second example it doesn't matter whether we build the second oven or not, thus it takes 12 minutes to bake 8 cakes in both cases. Thus, it is unreasonable to build the second oven.

In the third example the first oven bakes 11 cakes in 3 minutes, that is more than needed 10. It is unreasonable to build the second oven, because its building takes more time that baking the needed number of cakes using the only oven.
user: Iahub got lost in a very big desert. The desert can be represented as a n × n square matrix, where each cell is a zone of the desert. The cell (i, j) represents the cell at row i and column j (1 ≤ i, j ≤ n). Iahub can go from one cell (i, j) only down or right, that is to cells (i + 1, j) or (i, j + 1). 

Also, there are m cells that are occupied by volcanoes, which Iahub cannot enter. 

Iahub is initially at cell (1, 1) and he needs to travel to cell (n, n). Knowing that Iahub needs 1 second to travel from one cell to another, find the minimum time in which he can arrive in cell (n, n).


-----Input-----

The first line contains two integers n (1 ≤ n ≤ 10^9) and m (1 ≤ m ≤ 10^5). Each of the next m lines contains a pair of integers, x and y (1 ≤ x, y ≤ n), representing the coordinates of the volcanoes.

Consider matrix rows are numbered from 1 to n from top to bottom, and matrix columns are numbered from 1 to n from left to right. There is no volcano in cell (1, 1). No two volcanoes occupy the same location. 


-----Output-----

Print one integer, the minimum time in which Iahub can arrive at cell (n, n). If no solution exists (there is no path to the final cell), print -1.


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

Output
6

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

Output
12

Input
2 2
1 2
2 1

Output
-1



-----Note-----

Consider the first sample. A possible road is: (1, 1)  →  (1, 2)  →  (2, 2)  →  (2, 3)  →  (3, 3)  →  (3, 4)  →  (4, 4).
user: Snark and Philip are preparing the problemset for the upcoming pre-qualification round for semi-quarter-finals. They have a bank of n problems, and they want to select any non-empty subset of it as a problemset.

k experienced teams are participating in the contest. Some of these teams already know some of the problems. To make the contest interesting for them, each of the teams should know at most half of the selected problems.

Determine if Snark and Philip can make an interesting problemset!


-----Input-----

The first line contains two integers n, k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ 4) — the number of problems and the number of experienced teams.

Each of the next n lines contains k integers, each equal to 0 or 1. The j-th number in the i-th line is 1 if j-th team knows i-th problem and 0 otherwise.


-----Output-----

Print "YES" (quotes for clarity), if it is possible to make an interesting problemset, and "NO" otherwise.

You can print each character either upper- or lowercase ("YeS" and "yes" are valid when the answer is "YES").


-----Examples-----
Input
5 3
1 0 1
1 1 0
1 0 0
1 0 0
1 0 0

Output
NO

Input
3 2
1 0
1 1
0 1

Output
YES



-----Note-----

In the first example you can't make any interesting problemset, because the first team knows all problems.

In the second example you can choose the first and the third problems.