meetforever/GRPO_CL huggingface dataset:
user: Ryouko is an extremely forgetful girl, she could even forget something that has just happened. So in order to remember, she takes a notebook with her, called Ryouko's Memory Note. She writes what she sees and what she hears on the notebook, and the notebook became her memory.

Though Ryouko is forgetful, she is also born with superb analyzing abilities. However, analyzing depends greatly on gathered information, in other words, memory. So she has to shuffle through her notebook whenever she needs to analyze, which is tough work.

Ryouko's notebook consists of n pages, numbered from 1 to n. To make life (and this problem) easier, we consider that to turn from page x to page y, |x - y| pages should be turned. During analyzing, Ryouko needs m pieces of information, the i-th piece of information is on page a_{i}. Information must be read from the notebook in order, so the total number of pages that Ryouko needs to turn is $\sum_{i = 1}^{m - 1}|a_{i + 1} - a_{i}|$.

Ryouko wants to decrease the number of pages that need to be turned. In order to achieve this, she can merge two pages of her notebook. If Ryouko merges page x to page y, she would copy all the information on page x to y (1 ≤ x, y ≤ n), and consequently, all elements in sequence a that was x would become y. Note that x can be equal to y, in which case no changes take place.

Please tell Ryouko the minimum number of pages that she needs to turn. Note she can apply the described operation at most once before the reading. Note that the answer can exceed 32-bit integers.


-----Input-----

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

The next line contains m integers separated by spaces: a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ n).


-----Output-----

Print a single integer — the minimum number of pages Ryouko needs to turn.


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

Output
3

Input
10 5
9 4 3 8 8

Output
6



-----Note-----

In the first sample, the optimal solution is to merge page 4 to 3, after merging sequence a becomes {1, 2, 3, 3, 3, 2}, so the number of pages Ryouko needs to turn is |1 - 2| + |2 - 3| + |3 - 3| + |3 - 3| + |3 - 2| = 3.

In the second sample, optimal solution is achieved by merging page 9 to 4.
user: Paul is at the orchestra. The string section is arranged in an r × c rectangular grid and is filled with violinists with the exception of n violists. Paul really likes violas, so he would like to take a picture including at least k of them. Paul can take a picture of any axis-parallel rectangle in the orchestra. Count the number of possible pictures that Paul can take.

Two pictures are considered to be different if the coordinates of corresponding rectangles are different.


-----Input-----

The first line of input contains four space-separated integers r, c, n, k (1 ≤ r, c, n ≤ 10, 1 ≤ k ≤ n) — the number of rows and columns of the string section, the total number of violas, and the minimum number of violas Paul would like in his photograph, respectively.

The next n lines each contain two integers x_{i} and y_{i} (1 ≤ x_{i} ≤ r, 1 ≤ y_{i} ≤ c): the position of the i-th viola. It is guaranteed that no location appears more than once in the input.


-----Output-----

Print a single integer — the number of photographs Paul can take which include at least k violas. 


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

Output
4

Input
3 2 3 3
1 1
3 1
2 2

Output
1

Input
3 2 3 2
1 1
3 1
2 2

Output
4



-----Note-----

We will use '*' to denote violinists and '#' to denote violists.

In the first sample, the orchestra looks as follows 

*#

**

 Paul can take a photograph of just the viola, the 1 × 2 column containing the viola, the 2 × 1 row containing the viola, or the entire string section, for 4 pictures total.

In the second sample, the orchestra looks as follows 

#*

*#

#*

 Paul must take a photograph of the entire section.

In the third sample, the orchestra looks the same as in the second sample.
user: Dreamoon is a big fan of the Codeforces contests.

One day, he claimed that he will collect all the places from $1$ to $54$ after two more rated contests. It's amazing!

Based on this, you come up with the following problem:

There is a person who participated in $n$ Codeforces rounds. His place in the first round is $a_1$, his place in the second round is $a_2$, ..., his place in the $n$-th round is $a_n$.

You are given a positive non-zero integer $x$.

Please, find the largest $v$ such that this person can collect all the places from $1$ to $v$ after $x$ more rated contests.

In other words, you need to find the largest $v$, such that it is possible, that after $x$ more rated contests, for each $1 \leq i \leq v$, there will exist a contest where this person took the $i$-th place.

For example, if $n=6$, $x=2$ and $a=[3,1,1,5,7,10]$ then answer is $v=5$, because if on the next two contest he will take places $2$ and $4$, then he will collect all places from $1$ to $5$, so it is possible to get $v=5$.


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 5$) denoting the number of test cases in the input.

Each test case contains two lines. The first line contains two integers $n, x$ ($1 \leq n, x \leq 100$). The second line contains $n$ positive non-zero integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 100$).


-----Output-----

For each test case print one line containing the largest $v$, such that it is possible that after $x$ other contests, for each $1 \leq i \leq v$, there will exist a contest where this person took the $i$-th place.


-----Example-----
Input
5
6 2
3 1 1 5 7 10
1 100
100
11 1
1 1 1 1 1 1 1 1 1 1 1
1 1
1
4 57
80 60 40 20

Output
5
101
2
2
60



-----Note-----

The first test case is described in the statement.

In the second test case, the person has one hundred future contests, so he can take place $1,2,\ldots,99$ and place $101$ on them in some order, to collect places $1,2,\ldots,101$.
user: Recently, Anton has found a set. The set consists of small English letters. Anton carefully wrote out all the letters from the set in one line, separated by a comma. He also added an opening curved bracket at the beginning of the line and a closing curved bracket at the end of the line. 

Unfortunately, from time to time Anton would forget writing some letter and write it again. He asks you to count the total number of distinct letters in his set.


-----Input-----

The first and the single line contains the set of letters. The length of the line doesn't exceed 1000. It is guaranteed that the line starts from an opening curved bracket and ends with a closing curved bracket. Between them, small English letters are listed, separated by a comma. Each comma is followed by a space.


-----Output-----

Print a single number — the number of distinct letters in Anton's set.


-----Examples-----
Input
{a, b, c}

Output
3

Input
{b, a, b, a}

Output
2

Input
{}

Output
0
user: The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p_1, p_2, ..., p_{n}. You are to choose k pairs of integers:

 [l_1, r_1], [l_2, r_2], ..., [l_{k}, r_{k}] (1 ≤ l_1 ≤ r_1 < l_2 ≤ r_2 < ... < l_{k} ≤ r_{k} ≤ n; r_{i} - l_{i} + 1 = m), 

in such a way that the value of sum $\sum_{i = 1}^{k} \sum_{j = l_{i}}^{r_{i}} p_{j}$ is maximal possible. Help George to cope with the task.


-----Input-----

The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n integers p_1, p_2, ..., p_{n} (0 ≤ p_{i} ≤ 10^9).


-----Output-----

Print an integer in a single line — the maximum possible value of sum.


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

Output
9

Input
7 1 3
2 10 7 18 5 33 0

Output
61
user: Given an integer N, find two permutations:  Permutation p of numbers from 1 to N such that p_{i} ≠ i and p_{i} & i = 0 for all i = 1, 2, ..., N.  Permutation q of numbers from 1 to N such that q_{i} ≠ i and q_{i} & i ≠ 0 for all i = 1, 2, ..., N. 

& is the bitwise AND operation.


-----Input-----

The input consists of one line containing a single integer N (1 ≤ N ≤ 10^5).


-----Output-----

For each subtask, if the required permutation doesn't exist, output a single line containing the word "NO"; otherwise output the word "YES" in the first line and N elements of the permutation, separated by spaces, in the second line. If there are several possible permutations in a subtask, output any of them.


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

Output
NO
NO

Input
6

Output
YES
6 5 4 3 2 1 
YES
3 6 2 5 1 4
user: You are given a directed graph with $n$ vertices and $m$ directed edges without self-loops or multiple edges.

Let's denote the $k$-coloring of a digraph as following: you color each edge in one of $k$ colors. The $k$-coloring is good if and only if there no cycle formed by edges of same color.

Find a good $k$-coloring of given digraph with minimum possible $k$.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n \le 5000$, $1 \le m \le 5000$) — the number of vertices and edges in the digraph, respectively.

Next $m$ lines contain description of edges — one per line. Each edge is a pair of integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — there is directed edge from $u$ to $v$ in the graph.

It is guaranteed that each ordered pair $(u, v)$ appears in the list of edges at most once.


-----Output-----

In the first line print single integer $k$ — the number of used colors in a good $k$-coloring of given graph.

In the second line print $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le k$), where $c_i$ is a color of the $i$-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize $k$).


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

Output
1
1 1 1 1 1 

Input
3 3
1 2
2 3
3 1

Output
2
1 1 2
user: It can be shown that any positive integer x can be uniquely represented as x = 1 + 2 + 4 + ... + 2^{k} - 1 + r, where k and r are integers, k ≥ 0, 0 < r ≤ 2^{k}. Let's call that representation prairie partition of x.

For example, the prairie partitions of 12, 17, 7 and 1 are:  12 = 1 + 2 + 4 + 5,

17 = 1 + 2 + 4 + 8 + 2,

7 = 1 + 2 + 4,

1 = 1. 

Alice took a sequence of positive integers (possibly with repeating elements), replaced every element with the sequence of summands in its prairie partition, arranged the resulting numbers in non-decreasing order and gave them to Borys. Now Borys wonders how many elements Alice's original sequence could contain. Find all possible options!


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of numbers given from Alice to Borys.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^12; a_1 ≤ a_2 ≤ ... ≤ a_{n}) — the numbers given from Alice to Borys.


-----Output-----

Output, in increasing order, all possible values of m such that there exists a sequence of positive integers of length m such that if you replace every element with the summands in its prairie partition and arrange the resulting numbers in non-decreasing order, you will get the sequence given in the input.

If there are no such values of m, output a single integer -1.


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

Output
2 

Input
6
1 1 1 2 2 2

Output
2 3 

Input
5
1 2 4 4 4

Output
-1



-----Note-----

In the first example, Alice could get the input sequence from [6, 20] as the original sequence.

In the second example, Alice's original sequence could be either [4, 5] or [3, 3, 3].
user: Heidi the Cow is aghast: cracks in the northern Wall? Zombies gathering outside, forming groups, preparing their assault? This must not happen! Quickly, she fetches her HC^2 (Handbook of Crazy Constructions) and looks for the right chapter:

How to build a wall:  Take a set of bricks.  Select one of the possible wall designs. Computing the number of possible designs is left as an exercise to the reader.  Place bricks on top of each other, according to the chosen design. 

This seems easy enough. But Heidi is a Coding Cow, not a Constructing Cow. Her mind keeps coming back to point 2b. Despite the imminent danger of a zombie onslaught, she wonders just how many possible walls she could build with up to n bricks.

A wall is a set of wall segments as defined in the easy version. How many different walls can be constructed such that the wall consists of at least 1 and at most n bricks? Two walls are different if there exist a column c and a row r such that one wall has a brick in this spot, and the other does not.

Along with n, you will be given C, the width of the wall (as defined in the easy version). Return the number of different walls modulo 10^6 + 3.


-----Input-----

The first line contains two space-separated integers n and C, 1 ≤ n ≤ 500000, 1 ≤ C ≤ 200000.


-----Output-----

Print the number of different walls that Heidi could build, modulo 10^6 + 3.


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

Output
5

Input
2 2

Output
5

Input
3 2

Output
9

Input
11 5

Output
4367

Input
37 63

Output
230574



-----Note-----

The number 10^6 + 3 is prime.

In the second sample case, the five walls are: 

            B        B

B., .B, BB, B., and .B



In the third sample case, the nine walls are the five as in the second sample case and in addition the following four: 

B    B

B    B  B        B

B., .B, BB, and BB
user: In order to make the "Sea Battle" game more interesting, Boris decided to add a new ship type to it. The ship consists of two rectangles. The first rectangle has a width of $w_1$ and a height of $h_1$, while the second rectangle has a width of $w_2$ and a height of $h_2$, where $w_1 \ge w_2$. In this game, exactly one ship is used, made up of two rectangles. There are no other ships on the field.

The rectangles are placed on field in the following way:  the second rectangle is on top the first rectangle;  they are aligned to the left, i.e. their left sides are on the same line;  the rectangles are adjacent to each other without a gap. 

See the pictures in the notes: the first rectangle is colored red, the second rectangle is colored blue.

Formally, let's introduce a coordinate system. Then, the leftmost bottom cell of the first rectangle has coordinates $(1, 1)$, the rightmost top cell of the first rectangle has coordinates $(w_1, h_1)$, the leftmost bottom cell of the second rectangle has coordinates $(1, h_1 + 1)$ and the rightmost top cell of the second rectangle has coordinates $(w_2, h_1 + h_2)$.

After the ship is completely destroyed, all cells neighboring by side or a corner with the ship are marked. Of course, only cells, which don't belong to the ship are marked. On the pictures in the notes such cells are colored green.

Find out how many cells should be marked after the ship is destroyed. The field of the game is infinite in any direction.


-----Input-----

Four lines contain integers $w_1, h_1, w_2$ and $h_2$ ($1 \leq w_1, h_1, w_2, h_2 \leq 10^8$, $w_1 \ge w_2$) — the width of the first rectangle, the height of the first rectangle, the width of the second rectangle and the height of the second rectangle. You can't rotate the rectangles.


-----Output-----

Print exactly one integer — the number of cells, which should be marked after the ship is destroyed.


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

Output
12

Input
2 2 1 2

Output
16



-----Note-----

In the first example the field looks as follows (the first rectangle is red, the second rectangle is blue, green shows the marked squares): [Image] 

In the second example the field looks as: [Image]
user: Unlike Knights of a Round Table, Knights of a Polygonal Table deprived of nobility and happy to kill each other. But each knight has some power and a knight can kill another knight if and only if his power is greater than the power of victim. However, even such a knight will torment his conscience, so he can kill no more than $k$ other knights. Also, each knight has some number of coins. After a kill, a knight can pick up all victim's coins.

Now each knight ponders: how many coins he can have if only he kills other knights?

You should answer this question for each knight.


-----Input-----

The first line contains two integers $n$ and $k$ $(1 \le n \le 10^5, 0 \le k \le \min(n-1,10))$ — the number of knights and the number $k$ from the statement.

The second line contains $n$ integers $p_1, p_2 ,\ldots,p_n$ $(1 \le p_i \le 10^9)$ — powers of the knights. All $p_i$ are distinct.

The third line contains $n$ integers $c_1, c_2 ,\ldots,c_n$ $(0 \le c_i \le 10^9)$ — the number of coins each knight has.


-----Output-----

Print $n$ integers — the maximum number of coins each knight can have it only he kills other knights.


-----Examples-----
Input
4 2
4 5 9 7
1 2 11 33

Output
1 3 46 36 
Input
5 1
1 2 3 4 5
1 2 3 4 5

Output
1 3 5 7 9 
Input
1 0
2
3

Output
3 


-----Note-----

Consider the first example.   The first knight is the weakest, so he can't kill anyone. That leaves him with the only coin he initially has.  The second knight can kill the first knight and add his coin to his own two.  The third knight is the strongest, but he can't kill more than $k = 2$ other knights. It is optimal to kill the second and the fourth knights: $2+11+33 = 46$.  The fourth knight should kill the first and the second knights: $33+1+2 = 36$. 

In the second example the first knight can't kill anyone, while all the others should kill the one with the index less by one than their own.

In the third example there is only one knight, so he can't kill anyone.
user: You are given a permutation of n numbers p_1, p_2, ..., p_{n}. We perform k operations of the following type: choose uniformly at random two indices l and r (l ≤ r) and reverse the order of the elements p_{l}, p_{l} + 1, ..., p_{r}. Your task is to find the expected value of the number of inversions in the resulting permutation.


-----Input-----

The first line of input contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10^9). The next line contains n integers p_1, p_2, ..., p_{n} — the given permutation. All p_{i} are different and in range from 1 to n.

The problem consists of three subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

  In subproblem G1 (3 points), the constraints 1 ≤ n ≤ 6, 1 ≤ k ≤ 4 will hold.  In subproblem G2 (5 points), the constraints 1 ≤ n ≤ 30, 1 ≤ k ≤ 200 will hold.  In subproblem G3 (16 points), the constraints 1 ≤ n ≤ 100, 1 ≤ k ≤ 10^9 will hold. 


-----Output-----

Output the answer with absolute or relative error no more than 1e - 9.


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

Output
0.833333333333333

Input
3 4
1 3 2

Output
1.458333333333334



-----Note-----

Consider the first sample test. We will randomly pick an interval of the permutation (1, 2, 3) (which has no inversions) and reverse the order of its elements. With probability $\frac{1}{2}$, the interval will consist of a single element and the permutation will not be altered. With probability $\frac{1}{6}$ we will inverse the first two elements' order and obtain the permutation (2, 1, 3) which has one inversion. With the same probability we might pick the interval consisting of the last two elements which will lead to the permutation (1, 3, 2) with one inversion. Finally, with probability $\frac{1}{6}$ the randomly picked interval will contain all elements, leading to the permutation (3, 2, 1) with 3 inversions. Hence, the expected number of inversions is equal to $\frac{1}{2} \cdot 0 + \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 3 = \frac{5}{6}$.
user: The R1 company wants to hold a web search championship. There were n computers given for the competition, each of them is connected to the Internet. The organizers believe that the data transfer speed directly affects the result. The higher the speed of the Internet is, the faster the participant will find the necessary information. Therefore, before the competition started, each computer had its maximum possible data transfer speed measured. On the i-th computer it was a_{i} kilobits per second.

There will be k participants competing in the championship, each should get a separate computer. The organizing company does not want any of the participants to have an advantage over the others, so they want to provide the same data transfer speed to each participant's computer. Also, the organizers want to create the most comfortable conditions for the participants, so the data transfer speed on the participants' computers should be as large as possible.

The network settings of the R1 company has a special option that lets you to cut the initial maximum data transfer speed of any computer to any lower speed. How should the R1 company configure the network using the described option so that at least k of n computers had the same data transfer speed and the data transfer speed on these computers was as large as possible?


-----Input-----

The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 100) — the number of computers and the number of participants, respectively. In the second line you have a space-separated sequence consisting of n integers: a_1, a_2, ..., a_{n} (16 ≤ a_{i} ≤ 32768); number a_{i} denotes the maximum data transfer speed on the i-th computer.


-----Output-----

Print a single integer — the maximum Internet speed value. It is guaranteed that the answer to the problem is always an integer.


-----Examples-----
Input
3 2
40 20 30

Output
30

Input
6 4
100 20 40 20 50 50

Output
40



-----Note-----

In the first test case the organizers can cut the first computer's speed to 30 kilobits. Then two computers (the first and the third one) will have the same speed of 30 kilobits. They should be used as the participants' computers. This answer is optimal.
user: Let's define the sum of two permutations p and q of numbers 0, 1, ..., (n - 1) as permutation [Image], where Perm(x) is the x-th lexicographically permutation of numbers 0, 1, ..., (n - 1) (counting from zero), and Ord(p) is the number of permutation p in the lexicographical order.

For example, Perm(0) = (0, 1, ..., n - 2, n - 1), Perm(n! - 1) = (n - 1, n - 2, ..., 1, 0)

Misha has two permutations, p and q. Your task is to find their sum.

Permutation a = (a_0, a_1, ..., a_{n} - 1) is called to be lexicographically smaller than permutation b = (b_0, b_1, ..., b_{n} - 1), if for some k following conditions hold: a_0 = b_0, a_1 = b_1, ..., a_{k} - 1 = b_{k} - 1, a_{k} < b_{k}.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 200 000).

The second line contains n distinct integers from 0 to n - 1, separated by a space, forming permutation p.

The third line contains n distinct integers from 0 to n - 1, separated by spaces, forming permutation q.


-----Output-----

Print n distinct integers from 0 to n - 1, forming the sum of the given permutations. Separate the numbers by spaces.


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

Output
0 1

Input
2
0 1
1 0

Output
1 0

Input
3
1 2 0
2 1 0

Output
1 0 2



-----Note-----

Permutations of numbers from 0 to 1 in the lexicographical order: (0, 1), (1, 0).

In the first sample Ord(p) = 0 and Ord(q) = 0, so the answer is $\operatorname{Perm}((0 + 0) \operatorname{mod} 2) = \operatorname{Perm}(0) =(0,1)$.

In the second sample Ord(p) = 0 and Ord(q) = 1, so the answer is $\operatorname{Perm}((0 + 1) \operatorname{mod} 2) = \operatorname{Perm}(1) =(1,0)$.

Permutations of numbers from 0 to 2 in the lexicographical order: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).

In the third sample Ord(p) = 3 and Ord(q) = 5, so the answer is $\operatorname{Perm}((3 + 5) \operatorname{mod} 6) = \operatorname{Perm}(2) =(1,0,2)$.