meetforever/GRPO_CL huggingface dataset:
user: Lunar New Year is approaching, and Bob is struggling with his homework – a number division problem.

There are $n$ positive integers $a_1, a_2, \ldots, a_n$ on Bob's homework paper, where $n$ is always an even number. Bob is asked to divide those numbers into groups, where each group must contain at least $2$ numbers. Suppose the numbers are divided into $m$ groups, and the sum of the numbers in the $j$-th group is $s_j$. Bob's aim is to minimize the sum of the square of $s_j$, that is $$\sum_{j = 1}^{m} s_j^2.$$

Bob is puzzled by this hard problem. Could you please help him solve it?


-----Input-----

The first line contains an even integer $n$ ($2 \leq n \leq 3 \cdot 10^5$), denoting that there are $n$ integers on Bob's homework paper.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^4$), describing the numbers you need to deal with.


-----Output-----

A single line containing one integer, denoting the minimum of the sum of the square of $s_j$, which is $$\sum_{i = j}^{m} s_j^2,$$ where $m$ is the number of groups.


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

Output
164

Input
6
1 1 1 2 2 2

Output
27



-----Note-----

In the first sample, one of the optimal solutions is to divide those $4$ numbers into $2$ groups $\{2, 8\}, \{5, 3\}$. Thus the answer is $(2 + 8)^2 + (5 + 3)^2 = 164$.

In the second sample, one of the optimal solutions is to divide those $6$ numbers into $3$ groups $\{1, 2\}, \{1, 2\}, \{1, 2\}$. Thus the answer is $(1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27$.
user: Ilya is a very good-natured lion. He likes maths. Of all mathematical objects, his favourite one is matrices. Now he's faced a complicated matrix problem he needs to solve.

He's got a square 2^{n} × 2^{n}-sized matrix and 4^{n} integers. You need to arrange all these numbers in the matrix (put each number in a single individual cell) so that the beauty of the resulting matrix with numbers is maximum.

The beauty of a 2^{n} × 2^{n}-sized matrix is an integer, obtained by the following algorithm:  Find the maximum element in the matrix. Let's denote it as m.  If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2^{n} - 1 × 2^{n} - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices. 

As you can see, the algorithm is recursive.

Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.


-----Input-----

The first line contains integer 4^{n} (1 ≤ 4^{n} ≤ 2·10^6). The next line contains 4^{n} integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the numbers you need to arrange in the 2^{n} × 2^{n}-sized matrix.


-----Output-----

On a single line print the maximum value of the beauty of the described matrix.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


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

Output
13

Input
4
1 2 3 4

Output
14



-----Note-----

Consider the second sample. You need to arrange the numbers in the matrix as follows:

1 2

3 4



Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 14.
user: Pasha has recently bought a new phone jPager and started adding his friends' phone numbers there. Each phone number consists of exactly n digits.

Also Pasha has a number k and two sequences of length n / k (n is divisible by k) a_1, a_2, ..., a_{n} / k and b_1, b_2, ..., b_{n} / k. Let's split the phone number into blocks of length k. The first block will be formed by digits from the phone number that are on positions 1, 2,..., k, the second block will be formed by digits from the phone number that are on positions k + 1, k + 2, ..., 2·k and so on. Pasha considers a phone number good, if the i-th block doesn't start from the digit b_{i} and is divisible by a_{i} if represented as an integer. 

To represent the block of length k as an integer, let's write it out as a sequence c_1, c_2,...,c_{k}. Then the integer is calculated as the result of the expression c_1·10^{k} - 1 + c_2·10^{k} - 2 + ... + c_{k}.

Pasha asks you to calculate the number of good phone numbers of length n, for the given k, a_{i} and b_{i}. As this number can be too big, print it modulo 10^9 + 7. 


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(n, 9)) — the length of all phone numbers and the length of each block, respectively. It is guaranteed that n is divisible by k.

The second line of the input contains n / k space-separated positive integers — sequence a_1, a_2, ..., a_{n} / k (1 ≤ a_{i} < 10^{k}).

The third line of the input contains n / k space-separated positive integers — sequence b_1, b_2, ..., b_{n} / k (0 ≤ b_{i} ≤ 9). 


-----Output-----

Print a single integer — the number of good phone numbers of length n modulo 10^9 + 7.


-----Examples-----
Input
6 2
38 56 49
7 3 4

Output
8

Input
8 2
1 22 3 44
5 4 3 2

Output
32400



-----Note-----

In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.
user: Little Robber Girl likes to scare animals in her zoo for fun. She decided to arrange the animals in a row in the order of non-decreasing height. However, the animals were so scared that they couldn't stay in the right places.

The robber girl was angry at first, but then she decided to arrange the animals herself. She repeatedly names numbers l and r such that r - l + 1 is even. After that animals that occupy positions between l and r inclusively are rearranged as follows: the animal at position l swaps places with the animal at position l + 1, the animal l + 2 swaps with the animal l + 3, ..., finally, the animal at position r - 1 swaps with the animal r.

Help the robber girl to arrange the animals in the order of non-decreasing height. You should name at most 20 000 segments, since otherwise the robber girl will become bored and will start scaring the animals again.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — number of animals in the robber girl's zoo.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the height of the animal occupying the i-th place.


-----Output-----

Print the sequence of operations that will rearrange the animals by non-decreasing height.

The output should contain several lines, i-th of the lines should contain two space-separated integers l_{i} and r_{i} (1 ≤ l_{i} < r_{i} ≤ n) — descriptions of segments the robber girl should name. The segments should be described in the order the operations are performed.

The number of operations should not exceed 20 000.

If the animals are arranged correctly from the start, you are allowed to output nothing.


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

Output
1 4

Input
7
36 28 57 39 66 69 68

Output
1 4
6 7

Input
5
1 2 1 2 1

Output
2 5
3 4
1 4
1 4



-----Note-----

Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.
user: Little Vitaly loves different algorithms. Today he has invented a new algorithm just for you. Vitaly's algorithm works with string s, consisting of characters "x" and "y", and uses two following operations at runtime:  Find two consecutive characters in the string, such that the first of them equals "y", and the second one equals "x" and swap them. If there are several suitable pairs of characters, we choose the pair of characters that is located closer to the beginning of the string.  Find in the string two consecutive characters, such that the first of them equals "x" and the second one equals "y". Remove these characters from the string. If there are several suitable pairs of characters, we choose the pair of characters that is located closer to the beginning of the string. 

The input for the new algorithm is string s, and the algorithm works as follows:  If you can apply at least one of the described operations to the string, go to step 2 of the algorithm. Otherwise, stop executing the algorithm and print the current string.  If you can apply operation 1, then apply it. Otherwise, apply operation 2. After you apply the operation, go to step 1 of the algorithm. 

Now Vitaly wonders, what is going to be printed as the result of the algorithm's work, if the input receives string s.


-----Input-----

The first line contains a non-empty string s. 

It is guaranteed that the string only consists of characters "x" and "y". It is guaranteed that the string consists of at most 10^6 characters. It is guaranteed that as the result of the algorithm's execution won't be an empty string.


-----Output-----

In the only line print the string that is printed as the result of the algorithm's work, if the input of the algorithm input receives string s.


-----Examples-----
Input
x

Output
x

Input
yxyxy

Output
y

Input
xxxxxy

Output
xxxx



-----Note-----

In the first test the algorithm will end after the first step of the algorithm, as it is impossible to apply any operation. Thus, the string won't change.

In the second test the transformation will be like this:  string "yxyxy" transforms into string "xyyxy";  string "xyyxy" transforms into string "xyxyy";  string "xyxyy" transforms into string "xxyyy";  string "xxyyy" transforms into string "xyy";  string "xyy" transforms into string "y". 

As a result, we've got string "y". 

In the third test case only one transformation will take place: string "xxxxxy" transforms into string "xxxx". Thus, the answer will be string "xxxx".
user: Little Vasya had n boxes with balls in the room. The boxes stood in a row and were numbered with numbers from 1 to n from left to right.

Once Vasya chose one of the boxes, let's assume that its number is i, took all balls out from it (it is guaranteed that this box originally had at least one ball), and began putting balls (one at a time) to the boxes with numbers i + 1, i + 2, i + 3 and so on. If Vasya puts a ball into the box number n, then the next ball goes to box 1, the next one goes to box 2 and so on. He did it until he had no balls left in his hands. It is possible that Vasya puts multiple balls to the same box, and it is also possible that one or more balls will go to the box number i. If i = n, Vasya puts the first ball into the box number 1, then the next ball goes to box 2 and so on. 

For example, let's suppose that initially Vasya had four boxes, and the first box had 3 balls, the second one had 2, the third one had 5 and the fourth one had 4 balls. Then, if i = 3, then Vasya will take all five balls out of the third box and put them in the boxes with numbers: 4, 1, 2, 3, 4. After all Vasya's actions the balls will lie in the boxes as follows: in the first box there are 4 balls, 3 in the second one, 1 in the third one and 6 in the fourth one.

At this point Vasya has completely forgotten the original arrangement of the balls in the boxes, but he knows how they are arranged now, and the number x — the number of the box, where he put the last of the taken out balls.

He asks you to help to find the initial arrangement of the balls in the boxes.


-----Input-----

The first line of the input contains two integers n and x (2 ≤ n ≤ 10^5, 1 ≤ x ≤ n), that represent the number of the boxes and the index of the box that got the last ball from Vasya, correspondingly. The second line contains n space-separated integers a_1, a_2, ..., a_{n}, where integer a_{i} (0 ≤ a_{i} ≤ 10^9, a_{x} ≠ 0) represents the number of balls in the box with index i after Vasya completes all the actions. 

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

Print n integers, where the i-th one represents the number of balls in the box number i before Vasya starts acting. Separate the numbers in the output by spaces. If there are multiple correct solutions, you are allowed to print any of them.


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

Output
3 2 5 4 
Input
5 2
3 2 0 2 7

Output
2 1 4 1 6 
Input
3 3
2 3 1

Output
1 2 3
user: Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order. 

After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!

She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.

Lexicographical order is defined in following way. When we compare s and t, first we find the leftmost position with differing characters: s_{i} ≠ t_{i}. If there is no such position (i. e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters s_{i} and t_{i} according to their order in alphabet.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 100): number of names.

Each of the following n lines contain one string name_{i} (1 ≤ |name_{i}| ≤ 100), the i-th name. Each name contains only lowercase Latin letters. All names are different.


-----Output-----

If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on).

Otherwise output a single word "Impossible" (without quotes).


-----Examples-----
Input
3
rivest
shamir
adleman

Output
bcdefghijklmnopqrsatuvwxyz

Input
10
tourist
petr
wjmzbmr
yeputons
vepifanov
scottwu
oooooooooooooooo
subscriber
rowdark
tankengineer

Output
Impossible

Input
10
petr
egor
endagorion
feferivan
ilovetanyaromanova
kostka
dmitriyh
maratsnowbear
bredorjaguarturnik
cgyforever

Output
aghjlnopefikdmbcqrstuvwxyz

Input
7
car
care
careful
carefully
becarefuldontforgetsomething
otherwiseyouwillbehacked
goodluck

Output
acbdefhijklmnogpqrstuvwxyz
user: Andrew and Jerry are playing a game with Harry as the scorekeeper. The game consists of three rounds. In each round, Andrew and Jerry draw randomly without replacement from a jar containing n balls, each labeled with a distinct positive integer. Without looking, they hand their balls to Harry, who awards the point to the player with the larger number and returns the balls to the jar. The winner of the game is the one who wins at least two of the three rounds.

Andrew wins rounds 1 and 2 while Jerry wins round 3, so Andrew wins the game. However, Jerry is unhappy with this system, claiming that he will often lose the match despite having the higher overall total. What is the probability that the sum of the three balls Jerry drew is strictly higher than the sum of the three balls Andrew drew?


-----Input-----

The first line of input contains a single integer n (2 ≤ n ≤ 2000) — the number of balls in the jar.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 5000) — the number written on the ith ball. It is guaranteed that no two balls have the same number.


-----Output-----

Print a single real value — the probability that Jerry has a higher total, given that Andrew wins the first two rounds and Jerry wins the third. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


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

Output
0.0000000000

Input
3
1 2 10

Output
0.0740740741



-----Note-----

In the first case, there are only two balls. In the first two rounds, Andrew must have drawn the 2 and Jerry must have drawn the 1, and vice versa in the final round. Thus, Andrew's sum is 5 and Jerry's sum is 4, so Jerry never has a higher total.

In the second case, each game could've had three outcomes — 10 - 2, 10 - 1, or 2 - 1. Jerry has a higher total if and only if Andrew won 2 - 1 in both of the first two rounds, and Jerry drew the 10 in the last round. This has probability $\frac{1}{3} \cdot \frac{1}{3} \cdot \frac{2}{3} = \frac{2}{27}$.
user: Pasha loves his phone and also putting his hair up... But the hair is now irrelevant.

Pasha has installed a new game to his phone. The goal of the game is following. There is a rectangular field consisting of n row with m pixels in each row. Initially, all the pixels are colored white. In one move, Pasha can choose any pixel and color it black. In particular, he can choose the pixel that is already black, then after the boy's move the pixel does not change, that is, it remains black. Pasha loses the game when a 2 × 2 square consisting of black pixels is formed. 

Pasha has made a plan of k moves, according to which he will paint pixels. Each turn in his plan is represented as a pair of numbers i and j, denoting respectively the row and the column of the pixel to be colored on the current move.

Determine whether Pasha loses if he acts in accordance with his plan, and if he does, on what move the 2 × 2 square consisting of black pixels is formed.


-----Input-----

The first line of the input contains three integers n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10^5) — the number of rows, the number of columns and the number of moves that Pasha is going to perform. 

The next k lines contain Pasha's moves in the order he makes them. Each line contains two integers i and j (1 ≤ i ≤ n, 1 ≤ j ≤ m), representing the row number and column number of the pixel that was painted during a move.


-----Output-----

If Pasha loses, print the number of the move when the 2 × 2 square consisting of black pixels is formed.

If Pasha doesn't lose, that is, no 2 × 2 square consisting of black pixels is formed during the given k moves, print 0.


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

Output
4

Input
2 3 6
2 3
2 2
1 3
2 2
1 2
1 1

Output
5

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

Output
0
user: Vasya often uses public transport. The transport in the city is of two types: trolleys and buses. The city has n buses and m trolleys, the buses are numbered by integers from 1 to n, the trolleys are numbered by integers from 1 to m.

Public transport is not free. There are 4 types of tickets:   A ticket for one ride on some bus or trolley. It costs c_1 burles;  A ticket for an unlimited number of rides on some bus or on some trolley. It costs c_2 burles;  A ticket for an unlimited number of rides on all buses or all trolleys. It costs c_3 burles;  A ticket for an unlimited number of rides on all buses and trolleys. It costs c_4 burles. 

Vasya knows for sure the number of rides he is going to make and the transport he is going to use. He asked you for help to find the minimum sum of burles he will have to spend on the tickets.


-----Input-----

The first line contains four integers c_1, c_2, c_3, c_4 (1 ≤ c_1, c_2, c_3, c_4 ≤ 1000) — the costs of the tickets.

The second line contains two integers n and m (1 ≤ n, m ≤ 1000) — the number of buses and trolleys Vasya is going to use.

The third line contains n integers a_{i} (0 ≤ a_{i} ≤ 1000) — the number of times Vasya is going to use the bus number i.

The fourth line contains m integers b_{i} (0 ≤ b_{i} ≤ 1000) — the number of times Vasya is going to use the trolley number i.


-----Output-----

Print a single number — the minimum sum of burles Vasya will have to spend on the tickets.


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

Output
12

Input
4 3 2 1
1 3
798
1 2 3

Output
1

Input
100 100 8 100
3 5
7 94 12
100 1 47 0 42

Output
16



-----Note-----

In the first sample the profitable strategy is to buy two tickets of the first type (for the first bus), one ticket of the second type (for the second bus) and one ticket of the third type (for all trolleys). It totals to (2·1) + 3 + 7 = 12 burles.

In the second sample the profitable strategy is to buy one ticket of the fourth type.

In the third sample the profitable strategy is to buy two tickets of the third type: for all buses and for all trolleys.
user: Vlad likes to eat in cafes very much. During his life, he has visited cafes n times. Unfortunately, Vlad started to feel that his last visits are not any different from each other. To fix that Vlad had a small research.

First of all, Vlad assigned individual indices to all cafes. Then, he wrote down indices of cafes he visited in a row, in order of visiting them. Now, Vlad wants to find such a cafe that his last visit to that cafe was before his last visits to every other cafe. In other words, he wants to find such a cafe that he hasn't been there for as long as possible. Help Vlad to find that cafe.


-----Input-----

In first line there is one integer n (1 ≤ n ≤ 2·10^5) — number of cafes indices written by Vlad.

In second line, n numbers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 2·10^5) are written — indices of cafes in order of being visited by Vlad. Vlad could visit some cafes more than once. Note that in numeration, some indices could be omitted.


-----Output-----

Print one integer — index of the cafe that Vlad hasn't visited for as long as possible.


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

Output
3

Input
6
2 1 2 2 4 1

Output
2



-----Note-----

In first test, there are three cafes, and the last visits to cafes with indices 1 and 2 were after the last visit to cafe with index 3; so this cafe is the answer. 

In second test case, there are also three cafes, but with indices 1, 2 and 4. Cafes with indices 1 and 4 were visited after the last visit of cafe with index 2, so the answer is 2. Note that Vlad could omit some numbers while numerating the cafes.