meetforever/GRPO_CL huggingface dataset:
user: You are given a set of n elements indexed from 1 to n. The weight of i-th element is w_{i}. The weight of some subset of a given set is denoted as $W(S) =|S|\cdot \sum_{i \in S} w_{i}$. The weight of some partition R of a given set into k subsets is $W(R) = \sum_{S \in R} W(S)$ (recall that a partition of a given set is a set of its subsets such that every element of the given set belongs to exactly one subset in partition).

Calculate the sum of weights of all partitions of a given set into exactly k non-empty subsets, and print it modulo 10^9 + 7. Two partitions are considered different iff there exist two elements x and y such that they belong to the same set in one of the partitions, and to different sets in another partition.


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2·10^5) — the number of elements and the number of subsets in each partition, respectively.

The second line contains n integers w_{i} (1 ≤ w_{i} ≤ 10^9)— weights of elements of the set.


-----Output-----

Print one integer — the sum of weights of all partitions of a given set into k non-empty subsets, taken modulo 10^9 + 7.


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

Output
160

Input
5 2
1 2 3 4 5

Output
645



-----Note-----

Possible partitions in the first sample:  {{1, 2, 3}, {4}}, W(R) = 3·(w_1 + w_2 + w_3) + 1·w_4 = 24;  {{1, 2, 4}, {3}}, W(R) = 26;  {{1, 3, 4}, {2}}, W(R) = 24;  {{1, 2}, {3, 4}}, W(R) = 2·(w_1 + w_2) + 2·(w_3 + w_4) = 20;  {{1, 3}, {2, 4}}, W(R) = 20;  {{1, 4}, {2, 3}}, W(R) = 20;  {{1}, {2, 3, 4}}, W(R) = 26; 

Possible partitions in the second sample:  {{1, 2, 3, 4}, {5}}, W(R) = 45;  {{1, 2, 3, 5}, {4}}, W(R) = 48;  {{1, 2, 4, 5}, {3}}, W(R) = 51;  {{1, 3, 4, 5}, {2}}, W(R) = 54;  {{2, 3, 4, 5}, {1}}, W(R) = 57;  {{1, 2, 3}, {4, 5}}, W(R) = 36;  {{1, 2, 4}, {3, 5}}, W(R) = 37;  {{1, 2, 5}, {3, 4}}, W(R) = 38;  {{1, 3, 4}, {2, 5}}, W(R) = 38;  {{1, 3, 5}, {2, 4}}, W(R) = 39;  {{1, 4, 5}, {2, 3}}, W(R) = 40;  {{2, 3, 4}, {1, 5}}, W(R) = 39;  {{2, 3, 5}, {1, 4}}, W(R) = 40;  {{2, 4, 5}, {1, 3}}, W(R) = 41;  {{3, 4, 5}, {1, 2}}, W(R) = 42.
user: Little Elephant loves magic squares very much.

A magic square is a 3 × 3 table, each cell contains some positive integer. At that the sums of integers in all rows, columns and diagonals of the table are equal. The figure below shows the magic square, the sum of integers in all its rows, columns and diagonals equals 15. $\left. \begin{array}{|c|c|c|} \hline 4 & {9} & {2} \\ \hline 3 & {5} & {7} \\ \hline 8 & {1} & {6} \\ \hline \end{array} \right.$ 

The Little Elephant remembered one magic square. He started writing this square on a piece of paper, but as he wrote, he forgot all three elements of the main diagonal of the magic square. Fortunately, the Little Elephant clearly remembered that all elements of the magic square did not exceed 10^5. 

Help the Little Elephant, restore the original magic square, given the Elephant's notes.


-----Input-----

The first three lines of the input contain the Little Elephant's notes. The first line contains elements of the first row of the magic square. The second line contains the elements of the second row, the third line is for the third row. The main diagonal elements that have been forgotten by the Elephant are represented by zeroes.

It is guaranteed that the notes contain exactly three zeroes and they are all located on the main diagonal. It is guaranteed that all positive numbers in the table do not exceed 10^5.


-----Output-----

Print three lines, in each line print three integers — the Little Elephant's magic square. If there are multiple magic squares, you are allowed to print any of them. Note that all numbers you print must be positive and not exceed 10^5.

It is guaranteed that there exists at least one magic square that meets the conditions.


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

Output
1 1 1
1 1 1
1 1 1

Input
0 3 6
5 0 5
4 7 0

Output
6 3 6
5 5 5
4 7 4
user: Initially Ildar has an empty array. He performs $n$ steps. On each step he takes a subset of integers already added to the array and appends the mex of this subset to the array. 

The mex of an multiset of integers is the smallest non-negative integer not presented in the multiset. For example, the mex of the multiset $[0, 2, 3]$ is $1$, while the mex of the multiset $[1, 2, 1]$ is $0$.

More formally, on the step $m$, when Ildar already has an array $a_1, a_2, \ldots, a_{m-1}$, he chooses some subset of indices $1 \leq i_1 < i_2 < \ldots < i_k < m$ (possibly, empty), where $0 \leq k < m$, and appends the $mex(a_{i_1}, a_{i_2}, \ldots a_{i_k})$ to the end of the array.

After performing all the steps Ildar thinks that he might have made a mistake somewhere. He asks you to determine for a given array $a_1, a_2, \ldots, a_n$ the minimum step $t$ such that he has definitely made a mistake on at least one of the steps $1, 2, \ldots, t$, or determine that he could have obtained this array without mistakes.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 100\,000$) — the number of steps Ildar made.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array Ildar obtained.


-----Output-----

If Ildar could have chosen the subsets on each step in such a way that the resulting array is $a_1, a_2, \ldots, a_n$, print $-1$.

Otherwise print a single integer $t$ — the smallest index of a step such that a mistake was made on at least one step among steps $1, 2, \ldots, t$.


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

Output
-1
Input
3
1 0 1

Output
1
Input
4
0 1 2 239

Output
4


-----Note-----

In the first example it is possible that Ildar made no mistakes. Here is the process he could have followed.  $1$-st step. The initial array is empty. He can choose an empty subset and obtain $0$, because the mex of an empty set is $0$. Appending this value to the end he gets the array $[0]$.  $2$-nd step. The current array is $[0]$. He can choose a subset $[0]$ and obtain an integer $1$, because $mex(0) = 1$. Appending this value to the end he gets the array $[0,1]$.  $3$-rd step. The current array is $[0,1]$. He can choose a subset $[0,1]$ and obtain an integer $2$, because $mex(0,1) = 2$. Appending this value to the end he gets the array $[0,1,2]$.  $4$-th step. The current array is $[0,1,2]$. He can choose a subset $[0]$ and obtain an integer $1$, because $mex(0) = 1$. Appending this value to the end he gets the array $[0,1,2,1]$. 

Thus, he can get the array without mistakes, so the answer is $-1$.

In the second example he has definitely made a mistake on the very first step, because he could not have obtained anything different from $0$.

In the third example he could have obtained $[0, 1, 2]$ without mistakes, but $239$ is definitely wrong.
user: While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick's personal stuff and found a sequence a_1, a_2, ..., a_{m} of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence f_1, f_2, ..., f_{n} of length n and for each number a_{i} got number b_{i} = f_{a}_{i}. To finish the prank he erased the initial sequence a_{i}.

It's hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the lengths of sequences f_{i} and b_{i} respectively.

The second line contains n integers, determining sequence f_1, f_2, ..., f_{n} (1 ≤ f_{i} ≤ n).

The last line contains m integers, determining sequence b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ n).


-----Output-----

Print "Possible" if there is exactly one sequence a_{i}, such that b_{i} = f_{a}_{i} for all i from 1 to m. Then print m integers a_1, a_2, ..., a_{m}.

If there are multiple suitable sequences a_{i}, print "Ambiguity".

If Spongebob has made a mistake in his calculations and no suitable sequence a_{i} exists, print "Impossible".


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

Output
Possible
3 2 1 

Input
3 3
1 1 1
1 1 1

Output
Ambiguity

Input
3 3
1 2 1
3 3 3

Output
Impossible



-----Note-----

In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.

In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.

In the third sample f_{i} ≠ 3 for all i, so no sequence a_{i} transforms into such b_{i} and we can say for sure that Spongebob has made a mistake.
user: Pasha is participating in a contest on one well-known website. This time he wants to win the contest and will do anything to get to the first place!

This contest consists of n problems, and Pasha solves ith problem in a_{i} time units (his solutions are always correct). At any moment of time he can be thinking about a solution to only one of the problems (that is, he cannot be solving two problems at the same time). The time Pasha spends to send his solutions is negligible. Pasha can send any number of solutions at the same moment.

Unfortunately, there are too many participants, and the website is not always working. Pasha received the information that the website will be working only during m time periods, jth period is represented by its starting moment l_{j} and ending moment r_{j}. Of course, Pasha can send his solution only when the website is working. In other words, Pasha can send his solution at some moment T iff there exists a period x such that l_{x} ≤ T ≤ r_{x}.

Pasha wants to know his best possible result. We need to tell him the minimal moment of time by which he is able to have solutions to all problems submitted, if he acts optimally, or say that it's impossible no matter how Pasha solves the problems.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 1000) — the number of problems. The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^5) — the time Pasha needs to solve ith problem.

The third line contains one integer m (0 ≤ m ≤ 1000) — the number of periods of time when the website is working. Next m lines represent these periods. jth line contains two numbers l_{j} and r_{j} (1 ≤ l_{j} < r_{j} ≤ 10^5) — the starting and the ending moment of jth period.

It is guaranteed that the periods are not intersecting and are given in chronological order, so for every j > 1 the condition l_{j} > r_{j} - 1 is met.


-----Output-----

If Pasha can solve and submit all the problems before the end of the contest, print the minimal moment of time by which he can have all the solutions submitted.

Otherwise print "-1" (without brackets).


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

Output
7

Input
1
5
1
1 4

Output
-1

Input
1
5
1
1 5

Output
5



-----Note-----

In the first example Pasha can act like this: he solves the second problem in 4 units of time and sends it immediately. Then he spends 3 time units to solve the first problem and sends it 7 time units after the contest starts, because at this moment the website starts working again.

In the second example Pasha invents the solution only after the website stops working for the last time.

In the third example Pasha sends the solution exactly at the end of the first period.
user: You are a rebel leader and you are planning to start a revolution in your country. But the evil Government found out about your plans and set your punishment in the form of correctional labor.

You must paint a fence which consists of $10^{100}$ planks in two colors in the following way (suppose planks are numbered from left to right from $0$):   if the index of the plank is divisible by $r$ (such planks have indices $0$, $r$, $2r$ and so on) then you must paint it red;  if the index of the plank is divisible by $b$ (such planks have indices $0$, $b$, $2b$ and so on) then you must paint it blue;  if the index is divisible both by $r$ and $b$ you can choose the color to paint the plank;  otherwise, you don't need to paint the plank at all (and it is forbidden to spent paint on it). 

Furthermore, the Government added one additional restriction to make your punishment worse. Let's list all painted planks of the fence in ascending order: if there are $k$ consecutive planks with the same color in this list, then the Government will state that you failed the labor and execute you immediately. If you don't paint the fence according to the four aforementioned conditions, you will also be executed.

The question is: will you be able to accomplish the labor (the time is not important) or the execution is unavoidable and you need to escape at all costs.


-----Input-----

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

The next $T$ lines contain descriptions of test cases — one per line. Each test case contains three integers $r$, $b$, $k$ ($1 \le r, b \le 10^9$, $2 \le k \le 10^9$) — the corresponding coefficients.


-----Output-----

Print $T$ words — one per line. For each test case print REBEL (case insensitive) if the execution is unavoidable or OBEY (case insensitive) otherwise.


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

Output
OBEY
REBEL
OBEY
OBEY
user: There are $n$ rectangles in a row. You can either turn each rectangle by $90$ degrees or leave it as it is. If you turn a rectangle, its width will be height, and its height will be width. Notice that you can turn any number of rectangles, you also can turn all or none of them. You can not change the order of the rectangles.

Find out if there is a way to make the rectangles go in order of non-ascending height. In other words, after all the turns, a height of every rectangle has to be not greater than the height of the previous rectangle (if it is such). 


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of rectangles.

Each of the next $n$ lines contains two integers $w_i$ and $h_i$ ($1 \leq w_i, h_i \leq 10^9$) — the width and the height of the $i$-th rectangle.


-----Output-----

Print "YES" (without quotes) if there is a way to make the rectangles go in order of non-ascending height, otherwise print "NO".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
3
3 4
4 6
3 5

Output
YES

Input
2
3 4
5 5

Output
NO



-----Note-----

In the first test, you can rotate the second and the third rectangles so that the heights will be [4, 4, 3].

In the second test, there is no way the second rectangle will be not higher than the first one.
user: You are given a line of $n$ colored squares in a row, numbered from $1$ to $n$ from left to right. The $i$-th square initially has the color $c_i$.

Let's say, that two squares $i$ and $j$ belong to the same connected component if $c_i = c_j$, and $c_i = c_k$ for all $k$ satisfying $i < k < j$. In other words, all squares on the segment from $i$ to $j$ should have the same color.

For example, the line $[3, 3, 3]$ has $1$ connected component, while the line $[5, 2, 4, 4]$ has $3$ connected components.

The game "flood fill" is played on the given line as follows:   At the start of the game you pick any starting square (this is not counted as a turn).  Then, in each game turn, change the color of the connected component containing the starting square to any other color. 

Find the minimum number of turns needed for the entire line to be changed into a single color.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 5000$) — the number of squares.

The second line contains integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 5000$) — the initial colors of the squares.


-----Output-----

Print a single integer — the minimum number of the turns needed.


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

Output
2

Input
8
4 5 2 2 1 3 5 5

Output
4

Input
1
4

Output
0



-----Note-----

In the first example, a possible way to achieve an optimal answer is to pick square with index $2$ as the starting square and then play as follows:  $[5, 2, 2, 1]$  $[5, 5, 5, 1]$  $[1, 1, 1, 1]$ 

In the second example, a possible way to achieve an optimal answer is to pick square with index $5$ as the starting square and then perform recoloring into colors $2, 3, 5, 4$ in that order.

In the third example, the line already consists of one color only.
user: You are given three integers k, p_{a} and p_{b}.

You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability p_{a} / (p_{a} + p_{b}), add 'a' to the end of the sequence. Otherwise (with probability p_{b} / (p_{a} + p_{b})), add 'b' to the end of the sequence.

You stop once there are at least k subsequences that form 'ab'. Determine the expected number of times 'ab' is a subsequence in the resulting sequence. It can be shown that this can be represented by P / Q, where P and Q are coprime integers, and $Q \neq 0 \operatorname{mod}(10^{9} + 7)$. Print the value of $P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$.


-----Input-----

The first line will contain three integers integer k, p_{a}, p_{b} (1 ≤ k ≤ 1 000, 1 ≤ p_{a}, p_{b} ≤ 1 000 000).


-----Output-----

Print a single integer, the answer to the problem.


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

Output
2

Input
3 1 4

Output
370000006



-----Note-----

The first sample, we will keep appending to our sequence until we get the subsequence 'ab' at least once. For instance, we get the sequence 'ab' with probability 1/4, 'bbab' with probability 1/16, and 'aab' with probability 1/8. Note, it's impossible for us to end with a sequence like 'aabab', since we would have stopped our algorithm once we had the prefix 'aab'. 

The expected amount of times that 'ab' will occur across all valid sequences is 2. 

For the second sample, the answer is equal to $\frac{341}{100}$.
user: Yet another Armageddon is coming! This time the culprit is the Julya tribe calendar. 

The beavers in this tribe knew math very well. Smart Beaver, an archaeologist, got a sacred plate with a magic integer on it. The translation from Old Beaverish is as follows: 

"May the Great Beaver bless you! May your chacres open and may your third eye never turn blind from beholding the Truth! Take the magic number, subtract a digit from it (the digit must occur in the number) and get a new magic number. Repeat this operation until a magic number equals zero. The Earth will stand on Three Beavers for the time, equal to the number of subtractions you perform!"

Distinct subtraction sequences can obviously get you different number of operations. But the Smart Beaver is ready to face the worst and is asking you to count the minimum number of operations he needs to reduce the magic number to zero.


-----Input-----

The single line contains the magic integer n, 0 ≤ n.

  to get 20 points, you need to solve the problem with constraints: n ≤ 10^6 (subproblem C1);  to get 40 points, you need to solve the problem with constraints: n ≤ 10^12 (subproblems C1+C2);  to get 100 points, you need to solve the problem with constraints: n ≤ 10^18 (subproblems C1+C2+C3). 


-----Output-----

Print a single integer — the minimum number of subtractions that turns the magic number to a zero.


-----Examples-----
Input
24

Output
5


-----Note-----

In the first test sample the minimum number of operations can be reached by the following sequence of subtractions: 

 24 → 20 → 18 → 10 → 9 → 0
user: You have an n × m rectangle table, its cells are not initially painted. Your task is to paint all cells of the table. The resulting picture should be a tiling of the table with squares. More formally:  each cell must be painted some color (the colors are marked by uppercase Latin letters);  we will assume that two cells of the table are connected if they are of the same color and share a side; each connected region of the table must form a square. 

Given n and m, find lexicographically minimum coloring of the table that meets the described properties.


-----Input-----

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


-----Output-----

Print lexicographically minimum coloring of the table that meets the described conditions. 

One coloring (let's call it X) is considered lexicographically less than the other one (let's call it Y), if:  consider all the table cells from left to right and from top to bottom (first, the first cell in the first row, then the second cell in the first row and so on);  let's find in this order the first cell that has distinct colors in two colorings;  the letter that marks the color of the cell in X, goes alphabetically before the letter that marks the color of the cell in Y. 


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

Output
ABA

Input
2 2

Output
AA
AA

Input
3 4

Output
AAAB
AAAC
AAAB
user: You are going to hold a competition of one-to-one game called AtCoder Janken. (Janken is the Japanese name for Rock-paper-scissors.)N players will participate in this competition, and they are given distinct integers from 1 through N.
The arena has M playing fields for two players. You need to assign each playing field two distinct integers between 1 and N (inclusive).
You cannot assign the same integer to multiple playing fields.
The competition consists of N rounds, each of which proceeds as follows:
 - For each player, if there is a playing field that is assigned the player's integer, the player goes to that field and fight the other player who comes there.
 - Then, each player adds 1 to its integer. If it becomes N+1, change it to 1.
You want to ensure that no player fights the same opponent more than once during the N rounds.
Print an assignment of integers to the playing fields satisfying this condition.
It can be proved that such an assignment always exists under the constraints given.

-----Constraints-----
 - 1 \leq M
 - M \times 2 +1 \leq N \leq 200000

-----Input-----
Input is given from Standard Input in the following format:
N M

-----Output-----
Print M lines in the format below.
The i-th line should contain the two integers a_i and b_i assigned to the i-th playing field.
a_1 b_1
a_2 b_2
:
a_M b_M

-----Sample Input-----
4 1

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

Let us call the four players A, B, C, and D, and assume that they are initially given the integers 1, 2, 3, and 4, respectively.
 - The 1-st round is fought by B and C, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 2, 3, 4, and 1, respectively.
 - The 2-nd round is fought by A and B, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 3, 4, 1, and 2, respectively.
 - The 3-rd round is fought by D and A, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 4, 1, 2, and 3, respectively.
 - The 4-th round is fought by C and D, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 1, 2, 3, and 4, respectively.
No player fights the same opponent more than once during the four rounds, so this solution will be accepted.
user: Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).
There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.
Since this sum can be enormous, print the value modulo (10^9+7).
Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 1 \leq K \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K

-----Output-----
Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

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

-----Sample Output-----
9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)=1+1+1+1+1+1+1+2=9
Thus, the answer is 9.