meetforever/GRPO_CL huggingface dataset:
user: This is the easy version of the problem. The difference between versions is the constraints on $n$ and $a_i$. You can make hacks only if all versions of the problem are solved.

First, Aoi came up with the following idea for the competitive programming problem:

Yuzu is a girl who collecting candies. Originally, she has $x$ candies. There are also $n$ enemies numbered with integers from $1$ to $n$. Enemy $i$ has $a_i$ candies.

Yuzu is going to determine a permutation $P$. A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $\{2,3,1,5,4\}$ is a permutation, but $\{1,2,2\}$ is not a permutation ($2$ appears twice in the array) and $\{1,3,4\}$ is also not a permutation (because $n=3$ but there is the number $4$ in the array).

After that, she will do $n$ duels with the enemies with the following rules:  If Yuzu has equal or more number of candies than enemy $P_i$, she wins the duel and gets $1$ candy. Otherwise, she loses the duel and gets nothing.  The candy which Yuzu gets will be used in the next duels. 

Yuzu wants to win all duels. How many valid permutations $P$ exist?

This problem was easy and wasn't interesting for Akari, who is a friend of Aoi. And Akari made the following problem from the above idea:

Let's define $f(x)$ as the number of valid permutations for the integer $x$.

You are given $n$, $a$ and a prime number $p \le n$. Let's call a positive integer $x$ good, if the value $f(x)$ is not divisible by $p$. Find all good integers $x$.

Your task is to solve this problem made by Akari.


-----Input-----

The first line contains two integers $n$, $p$ $(2 \le p \le n \le 2000)$. It is guaranteed, that the number $p$ is prime (it has exactly two divisors $1$ and $p$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 2000)$.


-----Output-----

In the first line, print the number of good integers $x$.

In the second line, output all good integers $x$ in the ascending order.

It is guaranteed that the number of good integers $x$ does not exceed $10^5$.


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

Output
1
3

Input
4 3
2 3 5 6

Output
2
3 4

Input
4 3
9 1 1 1

Output
0




-----Note-----

In the first test, $p=2$.  If $x \le 2$, there are no valid permutations for Yuzu. So $f(x)=0$ for all $x \le 2$. The number $0$ is divisible by $2$, so all integers $x \leq 2$ are not good.  If $x = 3$, $\{1,2,3\}$ is the only valid permutation for Yuzu. So $f(3)=1$, so the number $3$ is good.  If $x = 4$, $\{1,2,3\} , \{1,3,2\} , \{2,1,3\} , \{2,3,1\}$ are all valid permutations for Yuzu. So $f(4)=4$, so the number $4$ is not good.  If $x \ge 5$, all $6$ permutations are valid for Yuzu. So $f(x)=6$ for all $x \ge 5$, so all integers $x \ge 5$ are not good. 

So, the only good number is $3$.

In the third test, for all positive integers $x$ the value $f(x)$ is divisible by $p = 3$.
user: Cucumber boy is fan of Kyubeat, a famous music game.

Kyubeat has 16 panels for playing arranged in 4 × 4 table. When a panel lights up, he has to press that panel.

Each panel has a timing to press (the preffered time when a player should press it), and Cucumber boy is able to press at most k panels in a time with his one hand. Cucumber boy is trying to press all panels in perfect timing, that is he wants to press each panel exactly in its preffered time. If he cannot press the panels with his two hands in perfect timing, his challenge to press all the panels in perfect timing will fail.

You are given one scene of Kyubeat's panel from the music Cucumber boy is trying. Tell him is he able to press all the panels in perfect timing.


-----Input-----

The first line contains a single integer k (1 ≤ k ≤ 5) — the number of panels Cucumber boy can press with his one hand.

Next 4 lines contain 4 characters each (digits from 1 to 9, or period) — table of panels. If a digit i was written on the panel, it means the boy has to press that panel in time i. If period was written on the panel, he doesn't have to press that panel.


-----Output-----

Output "YES" (without quotes), if he is able to press all the panels in perfect timing. If not, output "NO" (without quotes).


-----Examples-----
Input
1
.135
1247
3468
5789

Output
YES

Input
5
..1.
1111
..1.
..1.

Output
YES

Input
1
....
12.1
.2..
.2..

Output
NO



-----Note-----

In the third sample boy cannot press all panels in perfect timing. He can press all the panels in timing in time 1, but he cannot press the panels in time 2 in timing with his two hands.
user: To become the king of Codeforces, Kuroni has to solve the following problem.

He is given $n$ numbers $a_1, a_2, \dots, a_n$. Help Kuroni to calculate $\prod_{1\le i<j\le n} |a_i - a_j|$. As result can be very big, output it modulo $m$.

If you are not familiar with short notation, $\prod_{1\le i<j\le n} |a_i - a_j|$ is equal to $|a_1 - a_2|\cdot|a_1 - a_3|\cdot$ $\dots$ $\cdot|a_1 - a_n|\cdot|a_2 - a_3|\cdot|a_2 - a_4|\cdot$ $\dots$ $\cdot|a_2 - a_n| \cdot$ $\dots$ $\cdot |a_{n-1} - a_n|$. In other words, this is the product of $|a_i - a_j|$ for all $1\le i < j \le n$.


-----Input-----

The first line contains two integers $n$, $m$ ($2\le n \le 2\cdot 10^5$, $1\le m \le 1000$) — number of numbers and modulo.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).


-----Output-----

Output the single number — $\prod_{1\le i<j\le n} |a_i - a_j| \bmod m$.


-----Examples-----
Input
2 10
8 5

Output
3
Input
3 12
1 4 5

Output
0
Input
3 7
1 4 9

Output
1


-----Note-----

In the first sample, $|8 - 5| = 3 \equiv 3 \bmod 10$.

In the second sample, $|1 - 4|\cdot|1 - 5|\cdot|4 - 5| = 3\cdot 4 \cdot 1 = 12 \equiv 0 \bmod 12$.

In the third sample, $|1 - 4|\cdot|1 - 9|\cdot|4 - 9| = 3 \cdot 8 \cdot 5 = 120 \equiv 1 \bmod 7$.
user: We had a string s consisting of n lowercase Latin letters. We made k copies of this string, thus obtaining k identical strings s_1, s_2, ..., s_{k}. After that, in each of these strings we swapped exactly two characters (the characters we swapped could be identical, but they had different indices in the string).

You are given k strings s_1, s_2, ..., s_{k}, and you have to restore any string s so that it is possible to obtain these strings by performing aforementioned operations. Note that the total length of the strings you are given doesn't exceed 5000 (that is, k·n ≤ 5000).


-----Input-----

The first line contains two integers k and n (1 ≤ k ≤ 2500, 2 ≤ n ≤ 5000, k · n ≤ 5000) — the number of strings we obtained, and the length of each of these strings.

Next k lines contain the strings s_1, s_2, ..., s_{k}, each consisting of exactly n lowercase Latin letters.


-----Output-----

Print any suitable string s, or -1 if such string doesn't exist.


-----Examples-----
Input
3 4
abac
caab
acba

Output
acab

Input
3 4
kbbu
kbub
ubkb

Output
kbub

Input
5 4
abcd
dcba
acbd
dbca
zzzz

Output
-1



-----Note-----

In the first example s_1 is obtained by swapping the second and the fourth character in acab, s_2 is obtained by swapping the first and the second character, and to get s_3, we swap the third and the fourth character.

In the second example s_1 is obtained by swapping the third and the fourth character in kbub, s_2 — by swapping the second and the fourth, and s_3 — by swapping the first and the third.

In the third example it's impossible to obtain given strings by aforementioned operations.
user: Igor has fallen in love with Tanya. Now Igor wants to show his feelings and write a number on the fence opposite to Tanya's house. Igor thinks that the larger the number is, the more chance to win Tanya's heart he has. 

Unfortunately, Igor could only get v liters of paint. He did the math and concluded that digit d requires a_{d} liters of paint. Besides, Igor heard that Tanya doesn't like zeroes. That's why Igor won't use them in his number.

Help Igor find the maximum number he can write on the fence.


-----Input-----

The first line contains a positive integer v (0 ≤ v ≤ 10^6). The second line contains nine positive integers a_1, a_2, ..., a_9 (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Print the maximum number Igor can write on the fence. If he has too little paint for any digit (so, he cannot write anything), print -1.


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

Output
55555

Input
2
9 11 1 12 5 8 9 10 6

Output
33

Input
0
1 1 1 1 1 1 1 1 1

Output
-1
user: You got a job as a marketer in a pet shop, and your current task is to boost sales of cat food. One of the strategies is to sell cans of food in packs with discounts. 

Suppose you decided to sell packs with $a$ cans in a pack with a discount and some customer wants to buy $x$ cans of cat food. Then he follows a greedy strategy:   he buys $\left\lfloor \frac{x}{a} \right\rfloor$ packs with a discount;  then he wants to buy the remaining $(x \bmod a)$ cans one by one. 

$\left\lfloor \frac{x}{a} \right\rfloor$ is $x$ divided by $a$ rounded down, $x \bmod a$ is the remainer of $x$ divided by $a$.

But customers are greedy in general, so if the customer wants to buy $(x \bmod a)$ cans one by one and it happens that $(x \bmod a) \ge \frac{a}{2}$ he decides to buy the whole pack of $a$ cans (instead of buying $(x \bmod a)$ cans). It makes you, as a marketer, happy since the customer bought more than he wanted initially.

You know that each of the customers that come to your shop can buy any number of cans from $l$ to $r$ inclusive. Can you choose such size of pack $a$ that each customer buys more cans than they wanted initially?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first and only line of each test case contains two integers $l$ and $r$ ($1 \le l \le r \le 10^9$) — the range of the number of cans customers can buy.


-----Output-----

For each test case, print YES if you can choose such size of pack $a$ that each customer buys more cans than they wanted initially. Otherwise, print NO.

You can print each character in any case.


-----Example-----
Input
3
3 4
1 2
120 150

Output
YES
NO
YES



-----Note-----

In the first test case, you can take, for example, $a = 5$ as the size of the pack. Then if a customer wants to buy $3$ cans, he'll buy $5$ instead ($3 \bmod 5 = 3$, $\frac{5}{2} = 2.5$). The one who wants $4$ cans will also buy $5$ cans.

In the second test case, there is no way to choose $a$.

In the third test case, you can take, for example, $a = 80$.
user: Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly x drops of the potion he made. 

Value of x is calculated as maximum of p·a_{i} + q·a_{j} + r·a_{k} for given p, q, r and array a_1, a_2, ... a_{n} such that 1 ≤ i ≤ j ≤ k ≤ n. Help Snape find the value of x. Do note that the value of x may be negative.


-----Input-----

First line of input contains 4 integers n, p, q, r ( - 10^9 ≤ p, q, r ≤ 10^9, 1 ≤ n ≤ 10^5).

Next line of input contains n space separated integers a_1, a_2, ... a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

Output a single integer the maximum value of p·a_{i} + q·a_{j} + r·a_{k} that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.


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

Output
30

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

Output
12



-----Note-----

In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.
user: Let T be arbitrary binary tree — tree, every vertex of which has no more than two children. Given tree is rooted, so there exists only one vertex which doesn't have a parent — it's the root of a tree. Every vertex has an integer number written on it. Following algorithm is run on every value from the tree T:  Set pointer to the root of a tree.  Return success if the value in the current vertex is equal to the number you are looking for  Go to the left child of the vertex if the value in the current vertex is greater than the number you are looking for  Go to the right child of the vertex if the value in the current vertex is less than the number you are looking for  Return fail if you try to go to the vertex that doesn't exist 

Here is the pseudo-code of the described algorithm: 

bool find(TreeNode t, int x) {

    if (t == null)

        return false;

    if (t.value == x)

        return true;

    if (x < t.value)

        return find(t.left, x);

    else

        return find(t.right, x);

}

find(root, x);



The described algorithm works correctly if the tree is binary search tree (i.e. for each node the values of left subtree are less than the value in the node, the values of right subtree are greater than the value in the node). But it can return invalid result if tree is not a binary search tree.

Since the given tree is not necessarily a binary search tree, not all numbers can be found this way. Your task is to calculate, how many times the search will fail being running on every value from the tree.

If the tree has multiple vertices with the same values on them then you should run algorithm on every one of them separately.


-----Input-----

First line contains integer number n (1 ≤ n ≤ 10^5) — number of vertices in the tree.

Each of the next n lines contains 3 numbers v, l, r (0 ≤ v ≤ 10^9) — value on current vertex, index of the left child of the vertex and index of the right child of the vertex, respectively. If some child doesn't exist then number  - 1 is set instead. Note that different vertices of the tree may contain the same values.


-----Output-----

Print number of times when search algorithm will fail.


-----Examples-----
Input
3
15 -1 -1
10 1 3
5 -1 -1

Output
2

Input
8
6 2 3
3 4 5
12 6 7
1 -1 8
4 -1 -1
5 -1 -1
14 -1 -1
2 -1 -1

Output
1



-----Note-----

In the example the root of the tree in vertex 2. Search of numbers 5 and 15 will return fail because on the first step algorithm will choose the subtree which doesn't contain numbers you are looking for.
user: Today, Wet Shark is given n bishops on a 1000 by 1000 grid. Both rows and columns of the grid are numbered from 1 to 1000. Rows are numbered from top to bottom, while columns are numbered from left to right.

Wet Shark thinks that two bishops attack each other if they share the same diagonal. Note, that this is the only criteria, so two bishops may attack each other (according to Wet Shark) even if there is another bishop located between them. Now Wet Shark wants to count the number of pairs of bishops that attack each other.


-----Input-----

The first line of the input contains n (1 ≤ n ≤ 200 000) — the number of bishops.

Each of next n lines contains two space separated integers x_{i} and y_{i} (1 ≤ x_{i}, y_{i} ≤ 1000) — the number of row and the number of column where i-th bishop is positioned. It's guaranteed that no two bishops share the same position.


-----Output-----

Output one integer — the number of pairs of bishops which attack each other. 


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

Output
6

Input
3
1 1
2 3
3 5

Output
0



-----Note-----

In the first sample following pairs of bishops attack each other: (1, 3), (1, 5), (2, 3), (2, 4), (3, 4) and (3, 5). Pairs (1, 2), (1, 4), (2, 5) and (4, 5) do not attack each other because they do not share the same diagonal.
user: Your search for Heidi is over – you finally found her at a library, dressed up as a human. In fact, she has spent so much time there that she now runs the place! Her job is to buy books and keep them at the library so that people can borrow and read them. There are n different books, numbered 1 through n.

We will look at the library's operation during n consecutive days. Heidi knows in advance that on the i-th day (1 ≤ i ≤ n) precisely one person will come to the library, request to borrow the book a_{i}, read it in a few hours, and return the book later on the same day.

Heidi desperately wants to please all her guests, so she will make sure to always have the book a_{i} available in the library on the i-th day. During the night before the i-th day, she has the option of going to the bookstore (which operates at nights to avoid competition with the library) and buying any book for the price of 1 CHF. Of course, if she already has a book at the library, she does not need to buy it again. Initially, the library contains no books.

There is a problem, though. The capacity of the library is k – this means that at any time, there can be at most k books at the library. If buying a new book would cause Heidi to have more than k books, she must first get rid of some book that she already has, in order to make room for the new book. If she later needs a book that she got rid of, she will need to buy that book again.

You are given k and the sequence of requests for books a_1, a_2, ..., a_{n}. What is the minimum cost (in CHF) of buying new books to satisfy all the requests?


-----Input-----

The first line of input will contain two integers n and k (1 ≤ n, k ≤ 80). The second line will contain n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n) – the sequence of book requests.


-----Output-----

On a single line print the minimum cost of buying books at the store so as to satisfy all requests.


-----Examples-----
Input
4 80
1 2 2 1

Output
2

Input
4 1
1 2 2 1

Output
3

Input
4 2
1 2 3 1

Output
3



-----Note-----

In the first test case, Heidi is able to keep all books forever. Therefore, she only needs to buy the book 1 before the first day and the book 2 before the second day.

In the second test case, she can only keep one book at a time. Therefore she will need to buy new books on the first, second and fourth day.

In the third test case, before buying book 3 on the third day, she must decide which of the books 1 and 2 she should get rid of. Of course, she should keep the book 1, which will be requested on the fourth day.
user: You are given a permutation of the numbers 1, 2, ..., n and m pairs of positions (a_{j}, b_{j}).

At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?

Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so p_{k} = q_{k} for 1 ≤ k < i and p_{i} < q_{i}.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^6) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers p_{i} (1 ≤ p_{i} ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (a_{j}, b_{j}) (1 ≤ a_{j}, b_{j} ≤ n) — the pairs of positions to swap. Note that you are given a positions, not the values to swap.


-----Output-----

Print the only line with n distinct integers p'_{i} (1 ≤ p'_{i} ≤ n) — the lexicographically maximal permutation one can get.


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

Output
7 8 9 4 5 6 1 2 3
user: A classroom in a school has six rows with 3 desks in each row. Two people can use the same desk: one sitting on the left and one sitting on the right. 

Some places are already occupied, and some places are vacant. Petya has just entered the class and wants to occupy the most convenient place. The conveniences of the places are shown on the picture: [Image] 

Here, the desks in the top row are the closest to the blackboard, while the desks in the bottom row are the furthest from the blackboard.

You are given a plan of the class, where '*' denotes an occupied place, '.' denotes a vacant place, and the aisles are denoted by '-'. 

Find any of the most convenient vacant places for Petya.


-----Input-----

The input consists of 6 lines. Each line describes one row of desks, starting from the closest to the blackboard. Each line is given in the following format: two characters, each is '*' or '.' — the description of the left desk in the current row; a character '-' — the aisle; two characters, each is '*' or '.' — the description of the center desk in the current row; a character '-' — the aisle; two characters, each is '*' or '.' — the description of the right desk in the current row. So, the length of each of the six lines is 8.

It is guaranteed that there is at least one vacant place in the classroom.


-----Output-----

Print the plan of the classroom after Petya takes one of the most convenient for him places. Mark this place with the letter 'P'. There should be exactly one letter 'P' in the plan. Petya can only take a vacant place. In all other places the output should coincide with the input.

If there are multiple answers, print any.


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

Output
..-**-..
..-**-..
..-..-..
..-P.-..
..-..-..
..-..-..

Input
**-**-**
**-**-**
..-**-.*
**-**-**
..-..-..
..-**-..

Output
**-**-**
**-**-**
..-**-.*
**-**-**
..-P.-..
..-**-..

Input
**-**-*.
*.-*.-**
**-**-**
**-**-**
..-..-..
..-**-..

Output
**-**-*.
*.-*P-**
**-**-**
**-**-**
..-..-..
..-**-..



-----Note-----

In the first example the maximum convenience is 3.

In the second example the maximum convenience is 2.

In the third example the maximum convenience is 4.
user: You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ integers.

You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.

Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $k$ times.


-----Input-----

The first line contains two integers $n$ and $k$ $(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$ — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.

The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^{9})$.


-----Output-----

Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $k$ times.


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

Output
2

Input
3 10
100 100 100

Output
0

Input
10 9
4 5 5 7 5 4 5 2 4 3

Output
1



-----Note-----

In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes $[3, 3, 5, 5]$, and the difference between maximum and minimum is $2$. You still can perform one operation after that, but it's useless since you can't make the answer less than $2$.

In the second example all elements are already equal, so you may get $0$ as the answer even without applying any operations.
user: We have a tree with N vertices numbered 1 to N.
The i-th edge in this tree connects Vertex a_i and Vertex b_i.

Consider painting each of these edges white or black. There are 2^{N-1} such ways to paint the edges. Among them, how many satisfy all of the following M restrictions?  
 - The i-th (1 \leq i \leq M) restriction is represented by two integers u_i and v_i, which mean that the path connecting Vertex u_i and Vertex v_i must contain at least one edge painted black.

-----Constraints-----
 - 2 \leq N \leq 50
 - 1 \leq a_i,b_i \leq N
 - The graph given in input is a tree.
 - 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
 - 1 \leq u_i < v_i \leq N
 - If i \not= j, either u_i \not=u_j or v_i\not=v_j
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 b_1
:
a_{N-1} b_{N-1}
M
u_1 v_1
:
u_M v_M

-----Output-----
Print the number of ways to paint the edges that satisfy all of the M conditions.

-----Sample Input-----
3
1 2
2 3
1
1 3

-----Sample Output-----
3

The tree in this input is shown below:





All of the M restrictions will be satisfied if Edge 1 and 2 are respectively painted (white, black), (black, white), or (black, black), so the answer is 3.