meetforever/GRPO_CL huggingface dataset:
user: You have a Petri dish with bacteria and you are preparing to dive into the harsh micro-world. But, unfortunately, you don't have any microscope nearby, so you can't watch them.

You know that you have $n$ bacteria in the Petri dish and size of the $i$-th bacteria is $a_i$. Also you know intergalactic positive integer constant $K$.

The $i$-th bacteria can swallow the $j$-th bacteria if and only if $a_i > a_j$ and $a_i \le a_j + K$. The $j$-th bacteria disappear, but the $i$-th bacteria doesn't change its size. The bacteria can perform multiple swallows. On each swallow operation any bacteria $i$ can swallow any bacteria $j$ if $a_i > a_j$ and $a_i \le a_j + K$. The swallow operations go one after another.

For example, the sequence of bacteria sizes $a=[101, 53, 42, 102, 101, 55, 54]$ and $K=1$. The one of possible sequences of swallows is: $[101, 53, 42, 102, \underline{101}, 55, 54]$ $\to$ $[101, \underline{53}, 42, 102, 55, 54]$ $\to$ $[\underline{101}, 42, 102, 55, 54]$ $\to$ $[42, 102, 55, \underline{54}]$ $\to$ $[42, 102, 55]$. In total there are $3$ bacteria remained in the Petri dish.

Since you don't have a microscope, you can only guess, what the minimal possible number of bacteria can remain in your Petri dish when you finally will find any microscope.


-----Input-----

The first line contains two space separated positive integers $n$ and $K$ ($1 \le n \le 2 \cdot 10^5$, $1 \le K \le 10^6$) — number of bacteria and intergalactic constant $K$.

The second line contains $n$ space separated integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — sizes of bacteria you have.


-----Output-----

Print the only integer — minimal possible number of bacteria can remain.


-----Examples-----
Input
7 1
101 53 42 102 101 55 54

Output
3

Input
6 5
20 15 10 15 20 25

Output
1

Input
7 1000000
1 1 1 1 1 1 1

Output
7



-----Note-----

The first example is clarified in the problem statement.

In the second example an optimal possible sequence of swallows is: $[20, 15, 10, 15, \underline{20}, 25]$ $\to$ $[20, 15, 10, \underline{15}, 25]$ $\to$ $[20, 15, \underline{10}, 25]$ $\to$ $[20, \underline{15}, 25]$ $\to$ $[\underline{20}, 25]$ $\to$ $[25]$.

In the third example no bacteria can swallow any other bacteria.
user: Ivan unexpectedly saw a present from one of his previous birthdays. It is array of $n$ numbers from $1$ to $200$. Array is old and some numbers are hard to read. Ivan remembers that for all elements at least one of its neighbours ls not less than it, more formally:

$a_{1} \le a_{2}$,

$a_{n} \le a_{n-1}$ and

$a_{i} \le max(a_{i-1}, \,\, a_{i+1})$ for all $i$ from $2$ to $n-1$.

Ivan does not remember the array and asks to find the number of ways to restore it. Restored elements also should be integers from $1$ to $200$. Since the number of ways can be big, print it modulo $998244353$.


-----Input-----

First line of input contains one integer $n$ ($2 \le n \le 10^{5}$) — size of the array.

Second line of input contains $n$ integers $a_{i}$ — elements of array. Either $a_{i} = -1$ or $1 \le a_{i} \le 200$. $a_{i} = -1$ means that $i$-th element can't be read.


-----Output-----

Print number of ways to restore the array modulo $998244353$.


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

Output
1

Input
2
-1 -1

Output
200



-----Note-----

In the first example, only possible value of $a_{2}$ is $2$.

In the second example, $a_{1} = a_{2}$ so there are $200$ different values because all restored elements should be integers between $1$ and $200$.
user: Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if   the sequence consists of at least two elements  f_0 and f_1 are arbitrary  f_{n} + 2 = f_{n} + 1 + f_{n} for all n ≥ 0. 

You are given some sequence of integers a_1, a_2, ..., a_{n}. Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 1000) — the length of the sequence a_{i}.

The second line contains n integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 10^9).


-----Output-----

Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.


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

Output
3

Input
5
28 35 7 14 21

Output
4



-----Note-----

In the first sample, if we rearrange elements of the sequence as  - 1, 2, 1, the whole sequence a_{i} would be Fibonacci-ish.

In the second sample, the optimal way to rearrange elements is $7$, $14$, $21$, $35$, 28.
user: Recently Pashmak has been employed in a transportation company. The company has k buses and has a contract with a school which has n students. The school planned to take the students to d different places for d days (each day in one place). Each day the company provides all the buses for the trip. Pashmak has to arrange the students in the buses. He wants to arrange the students in a way that no two students become close friends. In his ridiculous idea, two students will become close friends if and only if they are in the same buses for all d days.

Please help Pashmak with his weird idea. Assume that each bus has an unlimited capacity.


-----Input-----

The first line of input contains three space-separated integers n, k, d (1 ≤ n, d ≤ 1000; 1 ≤ k ≤ 10^9).


-----Output-----

If there is no valid arrangement just print -1. Otherwise print d lines, in each of them print n integers. The j-th integer of the i-th line shows which bus the j-th student has to take on the i-th day. You can assume that the buses are numbered from 1 to k.


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

Output
1 1 2 
1 2 1 

Input
3 2 1

Output
-1



-----Note-----

Note that two students become close friends only if they share a bus each day. But the bus they share can differ from day to day.
user: You've got an n × m matrix. The matrix consists of integers. In one move, you can apply a single transformation to the matrix: choose an arbitrary element of the matrix and increase it by 1. Each element can be increased an arbitrary number of times.

You are really curious about prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors: itself and number one. For example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not. 

A matrix is prime if at least one of the two following conditions fulfills:  the matrix has a row with prime numbers only;  the matrix has a column with prime numbers only; 

Your task is to count the minimum number of moves needed to get a prime matrix from the one you've got.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 500) — the number of rows and columns in the matrix, correspondingly.

Each of the following n lines contains m integers — the initial matrix. All matrix elements are positive integers. All numbers in the initial matrix do not exceed 10^5.

The numbers in the lines are separated by single spaces.


-----Output-----

Print a single integer — the minimum number of moves needed to get a prime matrix from the one you've got. If you've got a prime matrix, print 0.


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

Output
1

Input
2 3
4 8 8
9 2 9

Output
3

Input
2 2
1 3
4 2

Output
0



-----Note-----

In the first sample you need to increase number 1 in cell (1, 1). Thus, the first row will consist of prime numbers: 2, 2, 3.

In the second sample you need to increase number 8 in cell (1, 2) three times. Thus, the second column will consist of prime numbers: 11, 2.

In the third sample you don't have to do anything as the second column already consists of prime numbers: 3, 2.
user: Shaass has n books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the i-th book is t_{i} and its pages' width is equal to w_{i}. The thickness of each book is either 1 or 2. All books have the same page heights. $1$ 

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure. [Image] 

Help Shaass to find the minimum total thickness of the vertical books that we can achieve.


-----Input-----

The first line of the input contains an integer n, (1 ≤ n ≤ 100). Each of the next n lines contains two integers t_{i} and w_{i} denoting the thickness and width of the i-th book correspondingly, (1 ≤ t_{i} ≤ 2, 1 ≤ w_{i} ≤ 100).


-----Output-----

On the only line of the output print the minimum total thickness of the vertical books that we can achieve.


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

Output
5

Input
3
1 10
2 1
2 4

Output
3
user: The Saratov State University Olympiad Programmers Training Center (SSU OPTC) has n students. For each student you know the number of times he/she has participated in the ACM ICPC world programming championship. According to the ACM ICPC rules, each person can participate in the world championship at most 5 times.

The head of the SSU OPTC is recently gathering teams to participate in the world championship. Each team must consist of exactly three people, at that, any person cannot be a member of two or more teams. What maximum number of teams can the head make if he wants each team to participate in the world championship with the same members at least k times?


-----Input-----

The first line contains two integers, n and k (1 ≤ n ≤ 2000; 1 ≤ k ≤ 5). The next line contains n integers: y_1, y_2, ..., y_{n} (0 ≤ y_{i} ≤ 5), where y_{i} shows the number of times the i-th person participated in the ACM ICPC world championship.


-----Output-----

Print a single number — the answer to the problem.


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

Output
1

Input
6 4
0 1 2 3 4 5

Output
0

Input
6 5
0 0 0 0 0 0

Output
2



-----Note-----

In the first sample only one team could be made: the first, the fourth and the fifth participants.

In the second sample no teams could be created.

In the third sample two teams could be created. Any partition into two teams fits.
user: You are given a tree consisting of $n$ vertices. A tree is an undirected connected acyclic graph. [Image] Example of a tree. 

You have to paint each vertex into one of three colors. For each vertex, you know the cost of painting it in every color.

You have to paint the vertices so that any path consisting of exactly three distinct vertices does not contain any vertices with equal colors. In other words, let's consider all triples $(x, y, z)$ such that $x \neq y, y \neq z, x \neq z$, $x$ is connected by an edge with $y$, and $y$ is connected by an edge with $z$. The colours of $x$, $y$ and $z$ should be pairwise distinct. Let's call a painting which meets this condition good.

You have to calculate the minimum cost of a good painting and find one of the optimal paintings. If there is no good painting, report about it.


-----Input-----

The first line contains one integer $n$ $(3 \le n \le 100\,000)$ — the number of vertices.

The second line contains a sequence of integers $c_{1, 1}, c_{1, 2}, \dots, c_{1, n}$ $(1 \le c_{1, i} \le 10^{9})$, where $c_{1, i}$ is the cost of painting the $i$-th vertex into the first color.

The third line contains a sequence of integers $c_{2, 1}, c_{2, 2}, \dots, c_{2, n}$ $(1 \le c_{2, i} \le 10^{9})$, where $c_{2, i}$ is the cost of painting the $i$-th vertex into the second color.

The fourth line contains a sequence of integers $c_{3, 1}, c_{3, 2}, \dots, c_{3, n}$ $(1 \le c_{3, i} \le 10^{9})$, where $c_{3, i}$ is the cost of painting the $i$-th vertex into the third color.

Then $(n - 1)$ lines follow, each containing two integers $u_j$ and $v_j$ $(1 \le u_j, v_j \le n, u_j \neq v_j)$ — the numbers of vertices connected by the $j$-th undirected edge. It is guaranteed that these edges denote a tree.


-----Output-----

If there is no good painting, print $-1$.

Otherwise, print the minimum cost of a good painting in the first line. In the second line print $n$ integers $b_1, b_2, \dots, b_n$ $(1 \le b_i \le 3)$, where the $i$-th integer should denote the color of the $i$-th vertex. If there are multiple good paintings with minimum cost, print any of them.


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

Output
6
1 3 2 

Input
5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 3

Output
-1

Input
5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 4

Output
9
1 3 2 1 3 



-----Note-----

All vertices should be painted in different colors in the first example. The optimal way to do it is to paint the first vertex into color $1$, the second vertex — into color $3$, and the third vertex — into color $2$. The cost of this painting is $3 + 2 + 1 = 6$.
user: It's another Start[c]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly S slices.

It is known that the i-th contestant will eat s_{i} slices of pizza, and gain a_{i} happiness for each slice of type 1 pizza they eat, and b_{i} happiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved?


-----Input-----

The first line of input will contain integers N and S (1 ≤ N ≤ 10^5, 1 ≤ S ≤ 10^5), the number of contestants and the number of slices per pizza, respectively. N lines follow.

The i-th such line contains integers s_{i}, a_{i}, and b_{i} (1 ≤ s_{i} ≤ 10^5, 1 ≤ a_{i} ≤ 10^5, 1 ≤ b_{i} ≤ 10^5), the number of slices the i-th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively.


-----Output-----

Print the maximum total happiness that can be achieved.


-----Examples-----
Input
3 12
3 5 7
4 6 7
5 9 5

Output
84

Input
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6

Output
314



-----Note-----

In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be 3·5 + 4·6 + 5·9 = 84, and if you buy a type 2 pizza, the total happiness will be 3·7 + 4·7 + 5·5 = 74.
user: All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. 

The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has n discount coupons, the i-th of them can be used with products with ids ranging from l_{i} to r_{i}, inclusive. Today Fedor wants to take exactly k coupons with him.

Fedor wants to choose the k coupons in such a way that the number of such products x that all coupons can be used with this product x is as large as possible (for better understanding, see examples). Fedor wants to save his time as well, so he asks you to choose coupons for him. Help Fedor!


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 3·10^5) — the number of coupons Fedor has, and the number of coupons he wants to choose.

Each of the next n lines contains two integers l_{i} and r_{i} ( - 10^9 ≤ l_{i} ≤ r_{i} ≤ 10^9) — the description of the i-th coupon. The coupons can be equal.


-----Output-----

In the first line print single integer — the maximum number of products with which all the chosen coupons can be used. The products with which at least one coupon cannot be used shouldn't be counted.

In the second line print k distinct integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — the ids of the coupons which Fedor should choose.

If there are multiple answers, print any of them.


-----Examples-----
Input
4 2
1 100
40 70
120 130
125 180

Output
31
1 2 

Input
3 2
1 12
15 20
25 30

Output
0
1 2 

Input
5 2
1 10
5 15
14 50
30 70
99 100

Output
21
3 4 



-----Note-----

In the first example if we take the first two coupons then all the products with ids in range [40, 70] can be bought with both coupons. There are 31 products in total.

In the second example, no product can be bought with two coupons, that is why the answer is 0. Fedor can choose any two coupons in this example.
user: You are given a string $s=s_1s_2\dots s_n$ of length $n$, which only contains digits $1$, $2$, ..., $9$.

A substring $s[l \dots r]$ of $s$ is a string $s_l s_{l + 1} s_{l + 2} \ldots s_r$. A substring $s[l \dots r]$ of $s$ is called even if the number represented by it is even. 

Find the number of even substrings of $s$. Note, that even if some substrings are equal as strings, but have different $l$ and $r$, they are counted as different substrings.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 65000$) — the length of the string $s$.

The second line contains a string $s$ of length $n$. The string $s$ consists only of digits $1$, $2$, ..., $9$.


-----Output-----

Print the number of even substrings of $s$.


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

Output
6
Input
4
2244

Output
10


-----Note-----

In the first example, the $[l, r]$ pairs corresponding to even substrings are:   $s[1 \dots 2]$

 $s[2 \dots 2]$

 $s[1 \dots 4]$

 $s[2 \dots 4]$

 $s[3 \dots 4]$

 $s[4 \dots 4]$ 

In the second example, all $10$ substrings of $s$ are even substrings. Note, that while substrings $s[1 \dots 1]$ and $s[2 \dots 2]$ both define the substring "2", they are still counted as different substrings.
user: Inna and Dima bought a table of size n × m in the shop. Each cell of the table contains a single letter: "D", "I", "M", "A".

Inna loves Dima, so she wants to go through his name as many times as possible as she moves through the table. For that, Inna acts as follows:

  initially, Inna chooses some cell of the table where letter "D" is written;  then Inna can move to some side-adjacent table cell that contains letter "I"; then from this cell she can go to one of the side-adjacent table cells that contains the written letter "M"; then she can go to a side-adjacent cell that contains letter "A". Then Inna assumes that she has gone through her sweetheart's name;  Inna's next move can be going to one of the side-adjacent table cells that contains letter "D" and then walk on through name DIMA in the similar manner. Inna never skips a letter. So, from the letter "D" she always goes to the letter "I", from the letter "I" she always goes the to letter "M", from the letter "M" she always goes to the letter "A", and from the letter "A" she always goes to the letter "D". 

Depending on the choice of the initial table cell, Inna can go through name DIMA either an infinite number of times or some positive finite number of times or she can't go through his name once. Help Inna find out what maximum number of times she can go through name DIMA.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 10^3). 

Then follow n lines that describe Inna and Dima's table. Each line contains m characters. Each character is one of the following four characters: "D", "I", "M", "A". 

Note that it is not guaranteed that the table contains at least one letter "D".


-----Output-----

If Inna cannot go through name DIMA once, print on a single line "Poor Dima!" without the quotes. If there is the infinite number of names DIMA Inna can go through, print "Poor Inna!" without the quotes. Otherwise print a single integer — the maximum number of times Inna can go through name DIMA.


-----Examples-----
Input
1 2
DI

Output
Poor Dima!

Input
2 2
MA
ID

Output
Poor Inna!

Input
5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID

Output
4



-----Note-----

Notes to the samples:

In the first test sample, Inna cannot go through name DIMA a single time.

In the second test sample, Inna can go through the infinite number of words DIMA. For that, she should move in the clockwise direction starting from the lower right corner.

In the third test sample the best strategy is to start from the cell in the upper left corner of the table. Starting from this cell, Inna can go through name DIMA four times.
user: The Cybernetics Failures (CF) organisation made a prototype of a bomb technician robot. To find the possible problems it was decided to carry out a series of tests. At the beginning of each test the robot prototype will be placed in cell (x_0, y_0) of a rectangular squared field of size x × y, after that a mine will be installed into one of the squares of the field. It is supposed to conduct exactly x·y tests, each time a mine is installed into a square that has never been used before. The starting cell of the robot always remains the same.

After placing the objects on the field the robot will have to run a sequence of commands given by string s, consisting only of characters 'L', 'R', 'U', 'D'. These commands tell the robot to move one square to the left, to the right, up or down, or stay idle if moving in the given direction is impossible. As soon as the robot fulfills all the sequence of commands, it will blow up due to a bug in the code. But if at some moment of time the robot is at the same square with the mine, it will also blow up, but not due to a bug in the code.

Moving to the left decreases coordinate y, and moving to the right increases it. Similarly, moving up decreases the x coordinate, and moving down increases it.

The tests can go on for very long, so your task is to predict their results. For each k from 0 to length(s) your task is to find in how many tests the robot will run exactly k commands before it blows up.


-----Input-----

The first line of the input contains four integers x, y, x_0, y_0 (1 ≤ x, y ≤ 500, 1 ≤ x_0 ≤ x, 1 ≤ y_0 ≤ y) — the sizes of the field and the starting coordinates of the robot. The coordinate axis X is directed downwards and axis Y is directed to the right.

The second line contains a sequence of commands s, which should be fulfilled by the robot. It has length from 1 to 100 000 characters and only consists of characters 'L', 'R', 'U', 'D'.


-----Output-----

Print the sequence consisting of (length(s) + 1) numbers. On the k-th position, starting with zero, print the number of tests where the robot will run exactly k commands before it blows up.


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

Output
1 1 0 1 1 1 1 0 6

Input
2 2 2 2
ULD

Output
1 1 1 1



-----Note-----

In the first sample, if we exclude the probable impact of the mines, the robot's route will look like that: $(2,2) \rightarrow(1,2) \rightarrow(1,2) \rightarrow(1,3) \rightarrow(2,3) \rightarrow(2,4) \rightarrow(3,4) \rightarrow(3,4) \rightarrow(3,3)$.