meetforever/GRPO_CL huggingface dataset:
user: Omkar is building a house. He wants to decide how to make the floor plan for the last floor.

Omkar's floor starts out as $n$ rows of $m$ zeros ($1 \le n,m \le 100$). Every row is divided into intervals such that every $0$ in the row is in exactly $1$ interval. For every interval for every row, Omkar can change exactly one of the $0$s contained in that interval to a $1$. Omkar defines the quality of a floor as the sum of the squares of the sums of the values in each column, i. e. if the sum of the values in the $i$-th column is $q_i$, then the quality of the floor is $\sum_{i = 1}^m q_i^2$.

Help Omkar find the maximum quality that the floor can have.


-----Input-----

The first line contains two integers, $n$ and $m$ ($1 \le n,m \le 100$), which are the number of rows and number of columns, respectively.

You will then receive a description of the intervals in each row. For every row $i$ from $1$ to $n$: The first row contains a single integer $k_i$ ($1 \le k_i \le m$), which is the number of intervals on row $i$. The $j$-th of the next $k_i$ lines contains two integers $l_{i,j}$ and $r_{i,j}$, which are the left and right bound (both inclusive), respectively, of the $j$-th interval of the $i$-th row. It is guaranteed that all intervals other than the first interval will be directly after the interval before it. Formally, $l_{i,1} = 1$, $l_{i,j} \leq r_{i,j}$ for all $1 \le j \le k_i$, $r_{i,j-1} + 1 = l_{i,j}$ for all $2 \le j \le k_i$, and $r_{i,k_i} = m$.


-----Output-----

Output one integer, which is the maximum possible quality of an eligible floor plan.


-----Example-----
Input
4 5
2
1 2
3 5
2
1 3
4 5
3
1 1
2 4
5 5
3
1 1
2 2
3 5

Output
36



-----Note-----

The given test case corresponds to the following diagram. Cells in the same row and have the same number are a part of the same interval.

 [Image] 

The most optimal assignment is:

 [Image] 

The sum of the $1$st column is $4$, the sum of the $2$nd column is $2$, the sum of the $3$rd and $4$th columns are $0$, and the sum of the $5$th column is $4$.

The quality of this floor plan is $4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36$. You can show that there is no floor plan with a higher quality.
user: Pashmak decided to give Parmida a pair of flowers from the garden. There are n flowers in the garden and the i-th of them has a beauty number b_{i}. Parmida is a very strange girl so she doesn't want to have the two most beautiful flowers necessarily. She wants to have those pairs of flowers that their beauty difference is maximal possible!

Your task is to write a program which calculates two things:  The maximum beauty difference of flowers that Pashmak can give to Parmida.  The number of ways that Pashmak can pick the flowers. Two ways are considered different if and only if there is at least one flower that is chosen in the first way and not chosen in the second way. 


-----Input-----

The first line of the input contains n (2 ≤ n ≤ 2·10^5). In the next line there are n space-separated integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^9).


-----Output-----

The only line of output should contain two integers. The maximum beauty difference and the number of ways this may happen, respectively.


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

Output
1 1
Input
3
1 4 5

Output
4 1
Input
5
3 1 2 3 1

Output
2 4


-----Note-----

In the third sample the maximum beauty difference is 2 and there are 4 ways to do this:  choosing the first and the second flowers;  choosing the first and the fifth flowers;  choosing the fourth and the second flowers;  choosing the fourth and the fifth flowers.
user: Are you going to Scarborough Fair?

Parsley, sage, rosemary and thyme.

Remember me to one who lives there.

He once was the true love of mine.

Willem is taking the girl to the highest building in island No.28, however, neither of them knows how to get there.

Willem asks his friend, Grick for directions, Grick helped them, and gave them a task.

Although the girl wants to help, Willem insists on doing it by himself.

Grick gave Willem a string of length n.

Willem needs to do m operations, each operation has four parameters l, r, c_1, c_2, which means that all symbols c_1 in range [l, r] (from l-th to r-th, including l and r) are changed into c_2. String is 1-indexed.

Grick wants to know the final string after all the m operations.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 100).

The second line contains a string s of length n, consisting of lowercase English letters.

Each of the next m lines contains four parameters l, r, c_1, c_2 (1 ≤ l ≤ r ≤ n, c_1, c_2 are lowercase English letters), separated by space.


-----Output-----

Output string s after performing m operations described above.


-----Examples-----
Input
3 1
ioi
1 1 i n

Output
noi
Input
5 3
wxhak
3 3 h x
1 5 x a
1 3 w g

Output
gaaak


-----Note-----

For the second example:

After the first operation, the string is wxxak.

After the second operation, the string is waaak.

After the third operation, the string is gaaak.
user: In 2013, the writers of Berland State University should prepare problems for n Olympiads. We will assume that the Olympiads are numbered with consecutive integers from 1 to n. For each Olympiad we know how many members of the jury must be involved in its preparation, as well as the time required to prepare the problems for her. Namely, the Olympiad number i should be prepared by p_{i} people for t_{i} days, the preparation for the Olympiad should be a continuous period of time and end exactly one day before the Olympiad. On the day of the Olympiad the juries who have prepared it, already do not work on it.

For example, if the Olympiad is held on December 9th and the preparation takes 7 people and 6 days, all seven members of the jury will work on the problems of the Olympiad from December, 3rd to December, 8th (the jury members won't be working on the problems of this Olympiad on December 9th, that is, some of them can start preparing problems for some other Olympiad). And if the Olympiad is held on November 3rd and requires 5 days of training, the members of the jury will work from October 29th to November 2nd.

In order not to overload the jury the following rule was introduced: one member of the jury can not work on the same day on the tasks for different Olympiads. Write a program that determines what the minimum number of people must be part of the jury so that all Olympiads could be prepared in time.


-----Input-----

The first line contains integer n — the number of Olympiads in 2013 (1 ≤ n ≤ 100). Each of the following n lines contains four integers m_{i}, d_{i}, p_{i} and t_{i} — the month and day of the Olympiad (given without leading zeroes), the needed number of the jury members and the time needed to prepare the i-th Olympiad (1 ≤ m_{i} ≤ 12, d_{i} ≥ 1, 1 ≤ p_{i}, t_{i} ≤ 100), d_{i} doesn't exceed the number of days in month m_{i}. The Olympiads are given in the arbitrary order. Several Olympiads can take place in one day.

Use the modern (Gregorian) calendar in the solution. Note that all dates are given in the year 2013. This is not a leap year, so February has 28 days. Please note, the preparation of some Olympiad can start in 2012 year.


-----Output-----

Print a single number — the minimum jury size.


-----Examples-----
Input
2
5 23 1 2
3 13 2 3

Output
2

Input
3
12 9 2 1
12 8 1 3
12 8 2 2

Output
3

Input
1
1 10 1 13

Output
1
user: Vasya wrote down two strings s of length n and t of length m consisting of small English letters 'a' and 'b'. What is more, he knows that string t has a form "abab...", namely there are letters 'a' on odd positions and letters 'b' on even positions.

Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string s were replaced by character '?'.

Let's call a sequence of positions i, i + 1, ..., i + m - 1 as occurrence of string t in s, if 1 ≤ i ≤ n - m + 1 and t_1 = s_{i}, t_2 = s_{i} + 1, ..., t_{m} = s_{i} + m - 1.

The boy defines the beauty of the string s as maximum number of disjoint occurrences of string t in s. Vasya can replace some letters '?' with 'a' or 'b' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string s is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the length of s.

The second line contains the string s of length n. It contains small English letters 'a', 'b' and characters '?' only.

The third line contains a single integer m (1 ≤ m ≤ 10^5) — the length of t. The string t contains letters 'a' on odd positions and 'b' on even positions.


-----Output-----

Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string s the maximum possible.


-----Examples-----
Input
5
bb?a?
1

Output
2

Input
9
ab??ab???
3

Output
2



-----Note-----

In the first sample string t has a form 'a'. The only optimal option is to replace all characters '?' by 'a'.

In the second sample using two replacements we can make string equal to "aba?aba??". It is impossible to get more than two occurrences.
user: Colonel has n badges. He wants to give one badge to every of his n soldiers. Each badge has a coolness factor, which shows how much it's owner reached. Coolness factor can be increased by one for the cost of one coin. 

For every pair of soldiers one of them should get a badge with strictly higher factor than the second one. Exact values of their factors aren't important, they just need to have distinct factors. 

Colonel knows, which soldier is supposed to get which badge initially, but there is a problem. Some of badges may have the same factor of coolness. Help him and calculate how much money has to be paid for making all badges have different factors of coolness.


-----Input-----

First line of input consists of one integer n (1 ≤ n ≤ 3000).

Next line consists of n integers a_{i} (1 ≤ a_{i} ≤ n), which stand for coolness factor of each badge.


-----Output-----

Output single integer — minimum amount of coins the colonel has to pay.


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

Output
1
Input
5
1 2 3 2 5

Output
2


-----Note-----

In first sample test we can increase factor of first badge by 1.

In second sample test we can increase factors of the second and the third badge by 1.
user: Vasya wants to turn on Christmas lights consisting of m bulbs. Initially, all bulbs are turned off. There are n buttons, each of them is connected to some set of bulbs. Vasya can press any of these buttons. When the button is pressed, it turns on all the bulbs it's connected to. Can Vasya light up all the bulbs?

If Vasya presses the button such that some bulbs connected to it are already turned on, they do not change their state, i.e. remain turned on.


-----Input-----

The first line of the input contains integers n and m (1 ≤ n, m ≤ 100) — the number of buttons and the number of bulbs respectively. 

Each of the next n lines contains x_{i} (0 ≤ x_{i} ≤ m) — the number of bulbs that are turned on by the i-th button, and then x_{i} numbers y_{ij} (1 ≤ y_{ij} ≤ m) — the numbers of these bulbs.


-----Output-----

If it's possible to turn on all m bulbs print "YES", otherwise print "NO".


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

Output
YES

Input
3 3
1 1
1 2
1 1

Output
NO



-----Note-----

In the first sample you can press each button once and turn on all the bulbs. In the 2 sample it is impossible to turn on the 3-rd lamp.
user: While Vasya finished eating his piece of pizza, the lesson has already started. For being late for the lesson, the teacher suggested Vasya to solve one interesting problem. Vasya has an array a and integer x. He should find the number of different ordered pairs of indexes (i, j) such that a_{i} ≤ a_{j} and there are exactly k integers y such that a_{i} ≤ y ≤ a_{j} and y is divisible by x.

In this problem it is meant that pair (i, j) is equal to (j, i) only if i is equal to j. For example pair (1, 2) is not the same as (2, 1).


-----Input-----

The first line contains 3 integers n, x, k (1 ≤ n ≤ 10^5, 1 ≤ x ≤ 10^9, 0 ≤ k ≤ 10^9), where n is the size of the array a and x and k are numbers from the statement.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the elements of the array a.


-----Output-----

Print one integer — the answer to the problem.


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

Output
3

Input
4 2 0
5 3 1 7

Output
4

Input
5 3 1
3 3 3 3 3

Output
25



-----Note-----

In first sample there are only three suitable pairs of indexes — (1, 2), (2, 3), (3, 4).

In second sample there are four suitable pairs of indexes(1, 1), (2, 2), (3, 3), (4, 4).

In third sample every pair (i, j) is suitable, so the answer is 5 * 5 = 25.
user: Vika has n jars with paints of distinct colors. All the jars are numbered from 1 to n and the i-th jar contains a_{i} liters of paint of color i.

Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1 × 1. Squares are numbered 1, 2, 3 and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color x, then the next square will be painted in color x + 1. In case of x = n, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.

Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of jars with colors Vika has.

The second line of the input contains a sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is equal to the number of liters of paint in the i-th jar, i.e. the number of liters of color i that Vika has.


-----Output-----

The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.


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

Output
12

Input
3
5 5 5

Output
15

Input
6
10 10 10 1 10 10

Output
11



-----Note-----

In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In the second sample Vika can start to paint using any color.

In the third sample Vika should start painting using color number 5.
user: There is a game called "I Wanna Be the Guy", consisting of n levels. Little X and his friend Little Y are addicted to the game. Each of them wants to pass the whole game.

Little X can pass only p levels of the game. And Little Y can pass only q levels of the game. You are given the indices of levels Little X can pass and the indices of levels Little Y can pass. Will Little X and Little Y pass the whole game, if they cooperate each other?


-----Input-----

The first line contains a single integer n (1 ≤  n ≤ 100). 

The next line contains an integer p (0 ≤ p ≤ n) at first, then follows p distinct integers a_1, a_2, ..., a_{p} (1 ≤ a_{i} ≤ n). These integers denote the indices of levels Little X can pass. The next line contains the levels Little Y can pass in the same format. It's assumed that levels are numbered from 1 to n.


-----Output-----

If they can pass all the levels, print "I become the guy.". If it's impossible, print "Oh, my keyboard!" (without the quotes).


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

Output
I become the guy.

Input
4
3 1 2 3
2 2 3

Output
Oh, my keyboard!



-----Note-----

In the first sample, Little X can pass levels [1 2 3], and Little Y can pass level [2 4], so they can pass all the levels both.

In the second sample, no one can pass level 4.
user: Captain Marmot wants to prepare a huge and important battle against his enemy, Captain Snake. For this battle he has n regiments, each consisting of 4 moles.

Initially, each mole i (1 ≤ i ≤ 4n) is placed at some position (x_{i}, y_{i}) in the Cartesian plane. Captain Marmot wants to move some moles to make the regiments compact, if it's possible.

Each mole i has a home placed at the position (a_{i}, b_{i}). Moving this mole one time means rotating his position point (x_{i}, y_{i}) 90 degrees counter-clockwise around it's home point (a_{i}, b_{i}).

A regiment is compact only if the position points of the 4 moles form a square with non-zero area.

Help Captain Marmot to find out for each regiment the minimal number of moves required to make that regiment compact, if it's possible.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100), the number of regiments.

The next 4n lines contain 4 integers x_{i}, y_{i}, a_{i}, b_{i} ( - 10^4 ≤ x_{i}, y_{i}, a_{i}, b_{i} ≤ 10^4).


-----Output-----

Print n lines to the standard output. If the regiment i can be made compact, the i-th line should contain one integer, the minimal number of required moves. Otherwise, on the i-th line print "-1" (without quotes).


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

Output
1
-1
3
3



-----Note-----

In the first regiment we can move once the second or the third mole.

We can't make the second regiment compact.

In the third regiment, from the last 3 moles we can move once one and twice another one.

In the fourth regiment, we can move twice the first mole and once the third mole.
user: An atom of element X can exist in n distinct states with energies E_1 < E_2 < ... < E_{n}. Arkady wants to build a laser on this element, using a three-level scheme. Here is a simplified description of the scheme. 

Three distinct states i, j and k are selected, where i < j < k. After that the following process happens:   initially the atom is in the state i, we spend E_{k} - E_{i} energy to put the atom in the state k, the atom emits a photon with useful energy E_{k} - E_{j} and changes its state to the state j, the atom spontaneously changes its state to the state i, losing energy E_{j} - E_{i}, the process repeats from step 1. 

Let's define the energy conversion efficiency as $\eta = \frac{E_{k} - E_{j}}{E_{k} - E_{i}}$, i. e. the ration between the useful energy of the photon and spent energy.

Due to some limitations, Arkady can only choose such three states that E_{k} - E_{i} ≤ U.

Help Arkady to find such the maximum possible energy conversion efficiency within the above constraints.


-----Input-----

The first line contains two integers n and U (3 ≤ n ≤ 10^5, 1 ≤ U ≤ 10^9) — the number of states and the maximum possible difference between E_{k} and E_{i}.

The second line contains a sequence of integers E_1, E_2, ..., E_{n} (1 ≤ E_1 < E_2... < E_{n} ≤ 10^9). It is guaranteed that all E_{i} are given in increasing order.


-----Output-----

If it is not possible to choose three states that satisfy all constraints, print -1.

Otherwise, print one real number η — the maximum possible energy conversion efficiency. Your answer is considered correct its absolute or relative error does not exceed 10^{ - 9}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-9}$.


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

Output
0.5

Input
10 8
10 13 15 16 17 19 20 22 24 25

Output
0.875

Input
3 1
2 5 10

Output
-1



-----Note-----

In the first example choose states 1, 2 and 3, so that the energy conversion efficiency becomes equal to $\eta = \frac{5 - 3}{5 - 1} = 0.5$.

In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to $\eta = \frac{24 - 17}{24 - 16} = 0.875$.
user: Ramesses came to university to algorithms practice, and his professor, who is a fairly known programmer, gave him the following task.

You are given two matrices $A$ and $B$ of size $n \times m$, each of which consists of $0$ and $1$ only. You can apply the following operation to the matrix $A$ arbitrary number of times: take any submatrix of the matrix $A$ that has at least two rows and two columns, and invert the values in its corners (i.e. all corners of the submatrix that contain $0$, will be replaced by $1$, and all corners of the submatrix that contain $1$, will be replaced by $0$). You have to answer whether you can obtain the matrix $B$ from the matrix $A$. [Image] An example of the operation. The chosen submatrix is shown in blue and yellow, its corners are shown in yellow. 

Ramesses don't want to perform these operations by himself, so he asks you to answer this question.

A submatrix of matrix $M$ is a matrix which consist of all elements which come from one of the rows with indices $x_1, x_1+1, \ldots, x_2$ of matrix $M$ and one of the columns with indices $y_1, y_1+1, \ldots, y_2$ of matrix $M$, where $x_1, x_2, y_1, y_2$ are the edge rows and columns of the submatrix. In other words, a submatrix is a set of elements of source matrix which form a solid rectangle (i.e. without holes) with sides parallel to the sides of the original matrix. The corners of the submatrix are cells $(x_1, y_1)$, $(x_1, y_2)$, $(x_2, y_1)$, $(x_2, y_2)$, where the cell $(i,j)$ denotes the cell on the intersection of the $i$-th row and the $j$-th column.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 500$) — the number of rows and the number of columns in matrices $A$ and $B$.

Each of the next $n$ lines contain $m$ integers: the $j$-th integer in the $i$-th line is the $j$-th element of the $i$-th row of the matrix $A$ ($0 \leq A_{ij} \leq 1$). 

Each of the next $n$ lines contain $m$ integers: the $j$-th integer in the $i$-th line is the $j$-th element of the $i$-th row of the matrix $B$ ($0 \leq B_{ij} \leq 1$). 


-----Output-----

Print "Yes" (without quotes) if it is possible to transform the matrix $A$ to the matrix $B$ using the operations described above, and "No" (without quotes), if it is not possible. You can print each letter in any case (upper or lower).


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

Output
Yes

Input
6 7
0 0 1 1 0 0 1
0 1 0 0 1 0 1
0 0 0 1 0 0 1
1 0 1 0 1 0 0
0 1 0 0 1 0 1
0 1 0 1 0 0 1
1 1 0 1 0 1 1
0 1 1 0 1 0 0
1 1 0 1 0 0 1
1 0 1 0 0 1 0
0 1 1 0 1 0 0
0 1 1 1 1 0 1

Output
Yes

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

Output
No



-----Note-----

The examples are explained below. [Image] Example 1.  [Image] Example 2.  [Image] Example 3.