meetforever/GRPO_CL huggingface dataset:
user: Recall that the 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 ($n=3$ but there is $4$ in the array).

A sequence $a$ is a subsegment of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as $[l, r]$, where $l, r$ are two integers with $1 \le l \le r \le n$. This indicates the subsegment where $l-1$ elements from the beginning and $n-r$ elements from the end are deleted from the sequence.

For a permutation $p_1, p_2, \ldots, p_n$, we define a framed segment as a subsegment $[l,r]$ where $\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$. For example, for the permutation $(6, 7, 1, 8, 5, 3, 2, 4)$ some of its framed segments are: $[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$. In particular, a subsegment $[i,i]$ is always a framed segments for any $i$ between $1$ and $n$, inclusive.

We define the happiness of a permutation $p$ as the number of pairs $(l, r)$ such that $1 \le l \le r \le n$, and $[l, r]$ is a framed segment. For example, the permutation $[3, 1, 2]$ has happiness $5$: all segments except $[1, 2]$ are framed segments.

Given integers $n$ and $m$, Jongwon wants to compute the sum of happiness for all permutations of length $n$, modulo the prime number $m$. Note that there exist $n!$ (factorial of $n$) different permutations of length $n$.


-----Input-----

The only line contains two integers $n$ and $m$ ($1 \le n \le 250\,000$, $10^8 \le m \le 10^9$, $m$ is prime).


-----Output-----

Print $r$ ($0 \le r < m$), the sum of happiness for all permutations of length $n$, modulo a prime number $m$.


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

Output
1

Input
2 993244853

Output
6

Input
3 993244853

Output
32

Input
2019 993244853

Output
923958830

Input
2020 437122297

Output
265955509



-----Note-----

For sample input $n=3$, let's consider all permutations of length $3$:  $[1, 2, 3]$, all subsegments are framed segment. Happiness is $6$.  $[1, 3, 2]$, all subsegments except $[1, 2]$ are framed segment. Happiness is $5$.  $[2, 1, 3]$, all subsegments except $[2, 3]$ are framed segment. Happiness is $5$.  $[2, 3, 1]$, all subsegments except $[2, 3]$ are framed segment. Happiness is $5$.  $[3, 1, 2]$, all subsegments except $[1, 2]$ are framed segment. Happiness is $5$.  $[3, 2, 1]$, all subsegments are framed segment. Happiness is $6$. 

Thus, the sum of happiness is $6+5+5+5+5+6 = 32$.
user: Родители Васи хотят, чтобы он как можно лучше учился. Поэтому если он получает подряд три положительные оценки («четвёрки» или «пятёрки»), они дарят ему подарок. Соответственно, оценки «единица», «двойка» и «тройка» родители Васи считают плохими. Когда Вася получает подряд три хорошие оценки, ему сразу вручают подарок, но для того, чтобы получить ещё один подарок, ему вновь надо получить подряд ещё три хорошие оценки.

Например, если Вася получит подряд пять «четвёрок» оценок, а потом «двойку», то ему дадут только один подарок, а вот если бы «четвёрок» было уже шесть, то подарков было бы два. 

За месяц Вася получил n оценок. Вам предстоит посчитать количество подарков, которые получил Вася. Оценки будут даны именно в том порядке, в котором Вася их получал. 


-----Входные данные-----

В первой строке входных данных следует целое положительное число n (3 ≤ n ≤ 1000) — количество оценок, полученных Васей.

Во второй строке входных данных следует последовательность из n чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 5) — оценки, полученные Васей. Оценки заданы в том порядке, в котором Вася их получил. 


-----Выходные данные-----

Выведите одно целое число — количество подарков, полученных Васей.


-----Примеры-----
Входные данные
6
4 5 4 5 4 4

Выходные данные
2

Входные данные
14
1 5 4 5 2 4 4 5 5 4 3 4 5 5

Выходные данные
3



-----Примечание-----

В первом примере Вася получит два подарка — за первые три положительные оценки и за следующую тройку положительных оценок соответственно.
user: Valera is a little boy. Yesterday he got a huge Math hometask at school, so Valera didn't have enough time to properly learn the English alphabet for his English lesson. Unfortunately, the English teacher decided to have a test on alphabet today. At the test Valera got a square piece of squared paper. The length of the side equals n squares (n is an odd number) and each unit square contains some small letter of the English alphabet.

Valera needs to know if the letters written on the square piece of paper form letter "X". Valera's teacher thinks that the letters on the piece of paper form an "X", if:  on both diagonals of the square paper all letters are the same;  all other squares of the paper (they are not on the diagonals) contain the same letter that is different from the letters on the diagonals. 

Help Valera, write the program that completes the described task for him.


-----Input-----

The first line contains integer n (3 ≤ n < 300; n is odd). Each of the next n lines contains n small English letters — the description of Valera's paper.


-----Output-----

Print string "YES", if the letters on the paper form letter "X". Otherwise, print string "NO". Print the strings without quotes.


-----Examples-----
Input
5
xooox
oxoxo
soxoo
oxoxo
xooox

Output
NO

Input
3
wsw
sws
wsw

Output
YES

Input
3
xpx
pxp
xpe

Output
NO
user: Petya and Vasya decided to play a little. They found n red cubes and m blue cubes. The game goes like that: the players take turns to choose a cube of some color (red or blue) and put it in a line from left to right (overall the line will have n + m cubes). Petya moves first. Petya's task is to get as many pairs of neighbouring cubes of the same color as possible. Vasya's task is to get as many pairs of neighbouring cubes of different colors as possible. 

The number of Petya's points in the game is the number of pairs of neighboring cubes of the same color in the line, the number of Vasya's points in the game is the number of neighbouring cubes of the different color in the line. Your task is to calculate the score at the end of the game (Petya's and Vasya's points, correspondingly), if both boys are playing optimally well. To "play optimally well" first of all means to maximize the number of one's points, and second — to minimize the number of the opponent's points.


-----Input-----

The only line contains two space-separated integers n and m (1 ≤ n, m ≤ 10^5) — the number of red and blue cubes, correspondingly.


-----Output-----

On a single line print two space-separated integers — the number of Petya's and Vasya's points correspondingly provided that both players play optimally well.


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

Output
2 1

Input
2 4

Output
3 2



-----Note-----

In the first test sample the optimal strategy for Petya is to put the blue cube in the line. After that there will be only red cubes left, so by the end of the game the line of cubes from left to right will look as [blue, red, red, red]. So, Petya gets 2 points and Vasya gets 1 point. 

If Petya would choose the red cube during his first move, then, provided that both boys play optimally well, Petya would get 1 point and Vasya would get 2 points.
user: Alice got an array of length $n$ as a birthday present once again! This is the third year in a row! 

And what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decided to apply some changes to the array to cheer up Alice.

Bob has chosen $m$ changes of the following form. For some integer numbers $x$ and $d$, he chooses an arbitrary position $i$ ($1 \le i \le n$) and for every $j \in [1, n]$ adds $x + d \cdot dist(i, j)$ to the value of the $j$-th cell. $dist(i, j)$ is the distance between positions $i$ and $j$ (i.e. $dist(i, j) = |i - j|$, where $|x|$ is an absolute value of $x$).

For example, if Alice currently has an array $[2, 1, 2, 2]$ and Bob chooses position $3$ for $x = -1$ and $d = 2$ then the array will become $[2 - 1 + 2 \cdot 2,~1 - 1 + 2 \cdot 1,~2 - 1 + 2 \cdot 0,~2 - 1 + 2 \cdot 1]$ = $[5, 2, 1, 3]$. Note that Bob can't choose position $i$ outside of the array (that is, smaller than $1$ or greater than $n$).

Alice will be the happiest when the elements of the array are as big as possible. Bob claimed that the arithmetic mean value of the elements will work fine as a metric.

What is the maximum arithmetic mean value Bob can achieve?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of elements of the array and the number of changes.

Each of the next $m$ lines contains two integers $x_i$ and $d_i$ ($-10^3 \le x_i, d_i \le 10^3$) — the parameters for the $i$-th change.


-----Output-----

Print the maximal average arithmetic mean of the elements Bob can achieve.

Your answer is considered correct if its absolute or relative error doesn't exceed $10^{-6}$.


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

Output
-2.500000000000000

Input
3 2
0 2
5 0

Output
7.000000000000000
user: Devu being a small kid, likes to play a lot, but he only likes to play with arrays. While playing he came up with an interesting question which he could not solve, can you please solve it for him?

Given an array consisting of distinct integers. Is it possible to partition the whole array into k disjoint non-empty parts such that p of the parts have even sum (each of them must have even sum) and remaining k - p have odd sum? (note that parts need not to be continuous).

If it is possible to partition the array, also give any possible way of valid partitioning.


-----Input-----

The first line will contain three space separated integers n, k, p (1 ≤ k ≤ n ≤ 10^5; 0 ≤ p ≤ k). The next line will contain n space-separated distinct integers representing the content of array a: a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

In the first line print "YES" (without the quotes) if it is possible to partition the array in the required way. Otherwise print "NO" (without the quotes).

If the required partition exists, print k lines after the first line. The i^{th} of them should contain the content of the i^{th} part. Print the content of the part in the line in the following way: firstly print the number of elements of the part, then print all the elements of the part in arbitrary order. There must be exactly p parts with even sum, each of the remaining k - p parts must have odd sum.

As there can be multiple partitions, you are allowed to print any valid partition.


-----Examples-----
Input
5 5 3
2 6 10 5 9

Output
YES
1 9
1 5
1 10
1 6
1 2

Input
5 5 3
7 14 2 9 5

Output
NO

Input
5 3 1
1 2 3 7 5

Output
YES
3 5 1 3
1 7
1 2
user: Vasya is studying in the last class of school and soon he will take exams. He decided to study polynomials. Polynomial is a function P(x) = a_0 + a_1x^1 + ... + a_{n}x^{n}. Numbers a_{i} are called coefficients of a polynomial, non-negative integer n is called a degree of a polynomial.

Vasya has made a bet with his friends that he can solve any problem with polynomials. They suggested him the problem: "Determine how many polynomials P(x) exist with integer non-negative coefficients so that $P(t) = a$, and $P(P(t)) = b$, where $t, a$ and b are given positive integers"? 

Vasya does not like losing bets, but he has no idea how to solve this task, so please help him to solve the problem.


-----Input-----

The input contains three integer positive numbers $t, a, b$ no greater than 10^18.


-----Output-----

If there is an infinite number of such polynomials, then print "inf" without quotes, otherwise print the reminder of an answer modulo 10^9 + 7.


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

Output
2

Input
2 3 3

Output
1
user: After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market.

This morning, as usual, Petya will come to the market. Petya has n different souvenirs to sell; ith souvenir is characterised by its weight w_{i} and cost c_{i}. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than m, and total cost is maximum possible.

Help Petya to determine maximum possible total cost.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market.

Then n lines follow. ith line contains two integers w_{i} and c_{i} (1 ≤ w_{i} ≤ 3, 1 ≤ c_{i} ≤ 10^9) — the weight and the cost of ith souvenir.


-----Output-----

Print one number — maximum possible total cost of souvenirs that Petya can carry to the market.


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

Output
0

Input
2 2
1 3
2 2

Output
3

Input
4 3
3 10
2 7
2 8
1 1

Output
10
user: Snuke has an integer sequence A of length N.
He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E.
The positions of the cuts can be freely chosen.
Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

-----Constraints-----
 - 4 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

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

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

If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3.
Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2.
We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.
user: We have N locked treasure boxes, numbered 1 to N.
A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.
Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 12
 - 1 \leq M \leq 10^3
 - 1 \leq a_i \leq 10^5
 - 1 \leq b_i \leq N
 - 1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

-----Input-----
Input is given from Standard Input in the following format:
N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}

-----Output-----
Print the minimum cost required to unlock all the treasure boxes.
If it is impossible to unlock all of them, print -1.

-----Sample Input-----
2 3
10 1
1
15 1
2
30 2
1 2

-----Sample Output-----
25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.
user: Vanya is doing his maths homework. He has an expression of form $x_{1} \diamond x_{2} \diamond x_{3} \diamond \ldots \diamond x_{n}$, where x_1, x_2, ..., x_{n} are digits from 1 to 9, and sign [Image] represents either a plus '+' or the multiplication sign '*'. Vanya needs to add one pair of brackets in this expression so that to maximize the value of the resulting expression.


-----Input-----

The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs  +  and  * . 

The number of signs  *  doesn't exceed 15.


-----Output-----

In the first line print the maximum possible value of an expression.


-----Examples-----
Input
3+5*7+8*4

Output
303

Input
2+3*5

Output
25

Input
3*4*5

Output
60



-----Note-----

Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.

Note to the second sample test. (2 + 3) * 5 = 25.

Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).
user: Ksenia has ordinary pan scales and several weights of an equal mass. Ksenia has already put some weights on the scales, while other weights are untouched. Ksenia is now wondering whether it is possible to put all the remaining weights on the scales so that the scales were in equilibrium. 

The scales is in equilibrium if the total sum of weights on the left pan is equal to the total sum of weights on the right pan.


-----Input-----

The first line has a non-empty sequence of characters describing the scales. In this sequence, an uppercase English letter indicates a weight, and the symbol "|" indicates the delimiter (the character occurs in the sequence exactly once). All weights that are recorded in the sequence before the delimiter are initially on the left pan of the scale. All weights that are recorded in the sequence after the delimiter are initially on the right pan of the scale. 

The second line contains a non-empty sequence containing uppercase English letters. Each letter indicates a weight which is not used yet. 

It is guaranteed that all the English letters in the input data are different. It is guaranteed that the input does not contain any extra characters.


-----Output-----

If you cannot put all the weights on the scales so that the scales were in equilibrium, print string "Impossible". Otherwise, print the description of the resulting scales, copy the format of the input.

If there are multiple answers, print any of them.


-----Examples-----
Input
AC|T
L

Output
AC|TL

Input
|ABC
XYZ

Output
XYZ|ABC

Input
W|T
F

Output
Impossible

Input
ABC|
D

Output
Impossible
user: Soon after the Chunga-Changa island was discovered, it started to acquire some forms of civilization and even market economy. A new currency arose, colloquially called "chizhik". One has to pay in chizhiks to buy a coconut now.

Sasha and Masha are about to buy some coconuts which are sold at price $z$ chizhiks per coconut. Sasha has $x$ chizhiks, Masha has $y$ chizhiks. Each girl will buy as many coconuts as she can using only her money. This way each girl will buy an integer non-negative number of coconuts.

The girls discussed their plans and found that the total number of coconuts they buy can increase (or decrease) if one of them gives several chizhiks to the other girl. The chizhiks can't be split in parts, so the girls can only exchange with integer number of chizhiks.

Consider the following example. Suppose Sasha has $5$ chizhiks, Masha has $4$ chizhiks, and the price for one coconut be $3$ chizhiks. If the girls don't exchange with chizhiks, they will buy $1 + 1 = 2$ coconuts. However, if, for example, Masha gives Sasha one chizhik, then Sasha will have $6$ chizhiks, Masha will have $3$ chizhiks, and the girls will buy $2 + 1 = 3$ coconuts. 

It is not that easy to live on the island now, so Sasha and Mash want to exchange with chizhiks in such a way that they will buy the maximum possible number of coconuts. Nobody wants to have a debt, so among all possible ways to buy the maximum possible number of coconuts find such a way that minimizes the number of chizhiks one girl gives to the other (it is not important who will be the person giving the chizhiks).


-----Input-----

The first line contains three integers $x$, $y$ and $z$ ($0 \le x, y \le 10^{18}$, $1 \le z \le 10^{18}$) — the number of chizhics Sasha has, the number of chizhics Masha has and the price of a coconut. 


-----Output-----

Print two integers: the maximum possible number of coconuts the girls can buy and the minimum number of chizhiks one girl has to give to the other.


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

Output
3 1

Input
6 8 2

Output
7 0



-----Note-----

The first example is described in the statement. In the second example the optimal solution is to dot exchange any chizhiks. The girls will buy $3 + 4 = 7$ coconuts.
user: Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal.

Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points.


-----Input-----

The input consists of three lines, each containing a pair of integer coordinates x_{i} and y_{i} ( - 1000 ≤ x_{i}, y_{i} ≤ 1000). It's guaranteed that these three points do not lie on the same line and no two of them coincide.


-----Output-----

First print integer k — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices.

Then print k lines, each containing a pair of integer — possible coordinates of the fourth point.


-----Example-----
Input
0 0
1 0
0 1

Output
3
1 -1
-1 1
1 1



-----Note-----

If you need clarification of what parallelogram is, please check Wikipedia page:

https://en.wikipedia.org/wiki/Parallelogram
user: Polycarpus has been working in the analytic department of the "F.R.A.U.D." company for as much as n days. Right now his task is to make a series of reports about the company's performance for the last n days. We know that the main information in a day report is value a_{i}, the company's profit on the i-th day. If a_{i} is negative, then the company suffered losses on the i-th day.

Polycarpus should sort the daily reports into folders. Each folder should include data on the company's performance for several consecutive days. Of course, the information on each of the n days should be exactly in one folder. Thus, Polycarpus puts information on the first few days in the first folder. The information on the several following days goes to the second folder, and so on.

It is known that the boss reads one daily report folder per day. If one folder has three or more reports for the days in which the company suffered losses (a_{i} < 0), he loses his temper and his wrath is terrible.

Therefore, Polycarpus wants to prepare the folders so that none of them contains information on three or more days with the loss, and the number of folders is minimal.

Write a program that, given sequence a_{i}, will print the minimum number of folders.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100), n is the number of days. The second line contains a sequence of integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 100), where a_{i} means the company profit on the i-th day. It is possible that the company has no days with the negative a_{i}.


-----Output-----

Print an integer k — the required minimum number of folders. In the second line print a sequence of integers b_1, b_2, ..., b_{k}, where b_{j} is the number of day reports in the j-th folder.

If there are multiple ways to sort the reports into k days, print any of them.


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

Output
3
5 3 3 
Input
5
0 -1 100 -1 0

Output
1
5 


-----Note-----

Here goes a way to sort the reports from the first sample into three folders:  1 2 3 -4 -5 | -6 5 -5 | -6 -7 6 

In the second sample you can put all five reports in one folder.