meetforever/GRPO_CL huggingface dataset:
user: After the big birthday party, Katie still wanted Shiro to have some more fun. Later, she came up with a game called treasure hunt. Of course, she invited her best friends Kuro and Shiro to play with her.

The three friends are very smart so they passed all the challenges very quickly and finally reached the destination. But the treasure can only belong to one cat so they started to think of something which can determine who is worthy of the treasure. Instantly, Kuro came up with some ribbons.

A random colorful ribbon is given to each of the cats. Each color of the ribbon can be represented as an uppercase or lowercase Latin letter. Let's call a consecutive subsequence of colors that appears in the ribbon a subribbon. The beauty of a ribbon is defined as the maximum number of times one of its subribbon appears in the ribbon. The more the subribbon appears, the more beautiful is the ribbon. For example, the ribbon aaaaaaa has the beauty of $7$ because its subribbon a appears $7$ times, and the ribbon abcdabc has the beauty of $2$ because its subribbon abc appears twice.

The rules are simple. The game will have $n$ turns. Every turn, each of the cats must change strictly one color (at one position) in his/her ribbon to an arbitrary color which is different from the unchanged one. For example, a ribbon aaab can be changed into acab in one turn. The one having the most beautiful ribbon after $n$ turns wins the treasure.

Could you find out who is going to be the winner if they all play optimally?


-----Input-----

The first line contains an integer $n$ ($0 \leq n \leq 10^{9}$) — the number of turns.

Next 3 lines contain 3 ribbons of Kuro, Shiro and Katie one per line, respectively. Each ribbon is a string which contains no more than $10^{5}$ uppercase and lowercase Latin letters and is not empty. It is guaranteed that the length of all ribbons are equal for the purpose of fairness. Note that uppercase and lowercase letters are considered different colors.


-----Output-----

Print the name of the winner ("Kuro", "Shiro" or "Katie"). If there are at least two cats that share the maximum beauty, print "Draw".


-----Examples-----
Input
3
Kuroo
Shiro
Katie

Output
Kuro

Input
7
treasurehunt
threefriends
hiCodeforces

Output
Shiro

Input
1
abcabc
cbabac
ababca

Output
Katie

Input
15
foPaErcvJ
mZaxowpbt
mkuOlaHRE

Output
Draw



-----Note-----

In the first example, after $3$ turns, Kuro can change his ribbon into ooooo, which has the beauty of $5$, while reaching such beauty for Shiro and Katie is impossible (both Shiro and Katie can reach the beauty of at most $4$, for example by changing Shiro's ribbon into SSiSS and changing Katie's ribbon into Kaaaa). Therefore, the winner is Kuro.

In the fourth example, since the length of each of the string is $9$ and the number of turn is $15$, everyone can change their ribbons in some way to reach the maximal beauty of $9$ by changing their strings into zzzzzzzzz after 9 turns, and repeatedly change their strings into azzzzzzzz and then into zzzzzzzzz thrice. Therefore, the game ends in a draw.
user: Mister B once received a gift: it was a book about aliens, which he started read immediately. This book had c pages.

At first day Mister B read v_0 pages, but after that he started to speed up. Every day, starting from the second, he read a pages more than on the previous day (at first day he read v_0 pages, at second — v_0 + a pages, at third — v_0 + 2a pages, and so on). But Mister B is just a human, so he physically wasn't able to read more than v_1 pages per day.

Also, to refresh his memory, every day, starting from the second, Mister B had to reread last l pages he read on the previous day. Mister B finished the book when he read the last page for the first time.

Help Mister B to calculate how many days he needed to finish the book.


-----Input-----

First and only line contains five space-separated integers: c, v_0, v_1, a and l (1 ≤ c ≤ 1000, 0 ≤ l < v_0 ≤ v_1 ≤ 1000, 0 ≤ a ≤ 1000) — the length of the book in pages, the initial reading speed, the maximum reading speed, the acceleration in reading speed and the number of pages for rereading.


-----Output-----

Print one integer — the number of days Mister B needed to finish the book.


-----Examples-----
Input
5 5 10 5 4

Output
1

Input
12 4 12 4 1

Output
3

Input
15 1 100 0 0

Output
15



-----Note-----

In the first sample test the book contains 5 pages, so Mister B read it right at the first day.

In the second sample test at first day Mister B read pages number 1 - 4, at second day — 4 - 11, at third day — 11 - 12 and finished the book.

In third sample test every day Mister B read 1 page of the book, so he finished in 15 days.
user: Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.

More formally, you are given an odd numer n. Find a set of numbers p_{i} (1 ≤ i ≤ k), such that



 1 ≤ k ≤ 3

 p_{i} is a prime

 $\sum_{i = 1}^{k} p_{i} = n$

The numbers p_{i} do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.


-----Input-----

The single line contains an odd number n (3 ≤ n < 10^9).


-----Output-----

In the first line print k (1 ≤ k ≤ 3), showing how many numbers are in the representation you found.

In the second line print numbers p_{i} in any order. If there are multiple possible solutions, you can print any of them.


-----Examples-----
Input
27

Output
3
5 11 11



-----Note-----

A prime is an integer strictly larger than one that is divisible only by one and by itself.
user: You are given a description of a depot. It is a rectangular checkered field of n × m size. Each cell in a field can be empty (".") or it can be occupied by a wall ("*"). 

You have one bomb. If you lay the bomb at the cell (x, y), then after triggering it will wipe out all walls in the row x and all walls in the column y.

You are to determine if it is possible to wipe out all walls in the depot by placing and triggering exactly one bomb. The bomb can be laid both in an empty cell or in a cell occupied by a wall.


-----Input-----

The first line contains two positive integers n and m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the depot field. 

The next n lines contain m symbols "." and "*" each — the description of the field. j-th symbol in i-th of them stands for cell (i, j). If the symbol is equal to ".", then the corresponding cell is empty, otherwise it equals "*" and the corresponding cell is occupied by a wall.


-----Output-----

If it is impossible to wipe out all walls by placing and triggering exactly one bomb, then print "NO" in the first line (without quotes).

Otherwise print "YES" (without quotes) in the first line and two integers in the second line — the coordinates of the cell at which the bomb should be laid. If there are multiple answers, print any of them.


-----Examples-----
Input
3 4
.*..
....
.*..

Output
YES
1 2

Input
3 3
..*
.*.
*..

Output
NO

Input
6 5
..*..
..*..
*****
..*..
..*..
..*..

Output
YES
3 3
user: Berland Football Cup starts really soon! Commentators from all over the world come to the event.

Organizers have already built $n$ commentary boxes. $m$ regional delegations will come to the Cup. Every delegation should get the same number of the commentary boxes. If any box is left unoccupied then the delegations will be upset. So each box should be occupied by exactly one delegation.

If $n$ is not divisible by $m$, it is impossible to distribute the boxes to the delegations at the moment.

Organizers can build a new commentary box paying $a$ burles and demolish a commentary box paying $b$ burles. They can both build and demolish boxes arbitrary number of times (each time paying a corresponding fee). It is allowed to demolish all the existing boxes.

What is the minimal amount of burles organizers should pay to satisfy all the delegations (i.e. to make the number of the boxes be divisible by $m$)?


-----Input-----

The only line contains four integer numbers $n$, $m$, $a$ and $b$ ($1 \le n, m \le 10^{12}$, $1 \le a, b \le 100$), where $n$ is the initial number of the commentary boxes, $m$ is the number of delegations to come, $a$ is the fee to build a box and $b$ is the fee to demolish a box.


-----Output-----

Output the minimal amount of burles organizers should pay to satisfy all the delegations (i.e. to make the number of the boxes be divisible by $m$). It is allowed that the final number of the boxes is equal to $0$.


-----Examples-----
Input
9 7 3 8

Output
15

Input
2 7 3 7

Output
14

Input
30 6 17 19

Output
0



-----Note-----

In the first example organizers can build $5$ boxes to make the total of $14$ paying $3$ burles for the each of them.

In the second example organizers can demolish $2$ boxes to make the total of $0$ paying $7$ burles for the each of them.

In the third example organizers are already able to distribute all the boxes equally among the delegations, each one get $5$ boxes.
user: You are given sequence a_1, a_2, ..., a_{n} of integer numbers of length n. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences. It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.


-----Input-----

The first line contains integer number n (1 ≤ n ≤ 10^5).

The second line contains n integer numbers a_1, a_2, ..., a_{n} ( - 10^4 ≤ a_{i} ≤ 10^4). The sequence contains at least one subsequence with odd sum.


-----Output-----

Print sum of resulting subseqeuence.


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

Output
3

Input
3
2 -5 -3

Output
-1



-----Note-----

In the first example sum of the second and the fourth elements is 3.
user: The only difference between easy and hard versions is constraints.

Polycarp loves to listen to music, so he never leaves the player, even on the way home from the university. Polycarp overcomes the distance from the university to the house in exactly $T$ minutes.

In the player, Polycarp stores $n$ songs, each of which is characterized by two parameters: $t_i$ and $g_i$, where $t_i$ is the length of the song in minutes ($1 \le t_i \le 15$), $g_i$ is its genre ($1 \le g_i \le 3$).

Polycarp wants to create such a playlist so that he can listen to music all the time on the way from the university to his home, and at the time of his arrival home, the playlist is over. Polycarp never interrupts songs and always listens to them from beginning to end. Thus, if he started listening to the $i$-th song, he would spend exactly $t_i$ minutes on its listening. Polycarp also does not like when two songs of the same genre play in a row (i.e. successively/adjacently) or when the songs in his playlist are repeated.

Help Polycarpus count the number of different sequences of songs (their order matters), the total duration is exactly $T$, such that there are no two consecutive songs of the same genre in them and all the songs in the playlist are different.


-----Input-----

The first line of the input contains two integers $n$ and $T$ ($1 \le n \le 15, 1 \le T \le 225$) — the number of songs in the player and the required total duration, respectively.

Next, the $n$ lines contain descriptions of songs: the $i$-th line contains two integers $t_i$ and $g_i$ ($1 \le t_i \le 15, 1 \le g_i \le 3$) — the duration of the $i$-th song and its genre, respectively.


-----Output-----

Output one integer — the number of different sequences of songs, the total length of exactly $T$, such that there are no two consecutive songs of the same genre in them and all the songs in the playlist are different. Since the answer may be huge, output it modulo $10^9 + 7$ (that is, the remainder when dividing the quantity by $10^9 + 7$).


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

Output
6

Input
3 3
1 1
1 1
1 3

Output
2

Input
4 10
5 3
2 1
3 2
5 1

Output
10



-----Note-----

In the first example, Polycarp can make any of the $6$ possible playlist by rearranging the available songs: $[1, 2, 3]$, $[1, 3, 2]$, $[2, 1, 3]$, $[2, 3, 1]$, $[3, 1, 2]$ and $[3, 2, 1]$ (indices of the songs are given).

In the second example, the first and second songs cannot go in succession (since they have the same genre). Thus, Polycarp can create a playlist in one of $2$ possible ways: $[1, 3, 2]$ and $[2, 3, 1]$ (indices of the songs are given).

In the third example, Polycarp can make the following playlists: $[1, 2, 3]$, $[1, 3, 2]$, $[2, 1, 3]$, $[2, 3, 1]$, $[3, 1, 2]$, $[3, 2, 1]$, $[1, 4]$, $[4, 1]$, $[2, 3, 4]$ and $[4, 3, 2]$ (indices of the songs are given).
user: Vivek initially has an empty array $a$ and some integer constant $m$.

He performs the following algorithm:  Select a random integer $x$ uniformly in range from $1$ to $m$ and append it to the end of $a$.  Compute the greatest common divisor of integers in $a$.  In case it equals to $1$, break  Otherwise, return to step $1$. 

Find the expected length of $a$. It can be shown that it can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q\neq 0 \pmod{10^9+7}$. Print the value of $P \cdot Q^{-1} \pmod{10^9+7}$.


-----Input-----

The first and only line contains a single integer $m$ ($1 \leq m \leq 100000$).


-----Output-----

Print a single integer — the expected length of the array $a$ written as $P \cdot Q^{-1} \pmod{10^9+7}$.


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

Output
1

Input
2

Output
2

Input
4

Output
333333338



-----Note-----

In the first example, since Vivek can choose only integers from $1$ to $1$, he will have $a=[1]$ after the first append operation, and after that quit the algorithm. Hence the length of $a$ is always $1$, so its expected value is $1$ as well.

In the second example, Vivek each time will append either $1$ or $2$, so after finishing the algorithm he will end up having some number of $2$'s (possibly zero), and a single $1$ in the end. The expected length of the list is $1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$.
user: Today on Informatics class Nastya learned about GCD and LCM (see links below). Nastya is very intelligent, so she solved all the tasks momentarily and now suggests you to solve one of them as well.

We define a pair of integers (a, b) good, if GCD(a, b) = x and LCM(a, b) = y, where GCD(a, b) denotes the greatest common divisor of a and b, and LCM(a, b) denotes the least common multiple of a and b.

You are given two integers x and y. You are to find the number of good pairs of integers (a, b) such that l ≤ a, b ≤ r. Note that pairs (a, b) and (b, a) are considered different if a ≠ b.


-----Input-----

The only line contains four integers l, r, x, y (1 ≤ l ≤ r ≤ 10^9, 1 ≤ x ≤ y ≤ 10^9).


-----Output-----

In the only line print the only integer — the answer for the problem.


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

Output
2

Input
1 12 1 12

Output
4

Input
50 100 3 30

Output
0



-----Note-----

In the first example there are two suitable good pairs of integers (a, b): (1, 2) and (2, 1).

In the second example there are four suitable good pairs of integers (a, b): (1, 12), (12, 1), (3, 4) and (4, 3).

In the third example there are good pairs of integers, for example, (3, 30), but none of them fits the condition l ≤ a, b ≤ r.
user: Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers $a$ and $b$. His goal is to find a non-negative integer $k$ such that the least common multiple of $a+k$ and $b+k$ is the smallest possible. If there are multiple optimal integers $k$, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?


-----Input-----

The only line contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$).


-----Output-----

Print the smallest non-negative integer $k$ ($k \ge 0$) such that the lowest common multiple of $a+k$ and $b+k$ is the smallest possible.

If there are many possible integers $k$ giving the same value of the least common multiple, print the smallest one.


-----Examples-----
Input
6 10

Output
2
Input
21 31

Output
9
Input
5 10

Output
0


-----Note-----

In the first test, one should choose $k = 2$, as the least common multiple of $6 + 2$ and $10 + 2$ is $24$, which is the smallest least common multiple possible.
user: Noora is a student of one famous high school. It's her final year in school — she is going to study in university next year. However, she has to get an «A» graduation certificate in order to apply to a prestigious one.

In school, where Noora is studying, teachers are putting down marks to the online class register, which are integers from 1 to k. The worst mark is 1, the best is k. Mark that is going to the certificate, is calculated as an average of all the marks, rounded to the closest integer. If several answers are possible, rounding up is produced. For example, 7.3 is rounded to 7, but 7.5 and 7.8784 — to 8. 

For instance, if Noora has marks [8, 9], then the mark to the certificate is 9, because the average is equal to 8.5 and rounded to 9, but if the marks are [8, 8, 9], Noora will have graduation certificate with 8.

To graduate with «A» certificate, Noora has to have mark k.

Noora got n marks in register this year. However, she is afraid that her marks are not enough to get final mark k. Noora decided to ask for help in the internet, where hacker Leha immediately responded to her request. He is ready to hack class register for Noora and to add Noora any number of additional marks from 1 to k. At the same time, Leha want his hack be unseen to everyone, so he decided to add as less as possible additional marks. Please help Leha to calculate the minimal number of marks he has to add, so that final Noora's mark will become equal to k.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100) denoting the number of marks, received by Noora and the value of highest possible mark.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ k) denoting marks received by Noora before Leha's hack.


-----Output-----

Print a single integer — minimal number of additional marks, that Leha has to add in order to change Noora's final mark to k.


-----Examples-----
Input
2 10
8 9

Output
4
Input
3 5
4 4 4

Output
3


-----Note-----

Consider the first example testcase.

Maximal mark is 10, Noora received two marks — 8 and 9, so current final mark is 9. To fix it, Leha can add marks [10, 10, 10, 10] (4 marks in total) to the registry, achieving Noora having average mark equal to $\frac{8 + 9 + 10 + 10 + 10 + 10}{6} = \frac{57}{6} = 9.5$. Consequently, new final mark is 10. Less number of marks won't fix the situation.

In the second example Leha can add [5, 5, 5] to the registry, so that making average mark equal to 4.5, which is enough to have 5 in the certificate.
user: You are given an array of $n$ integers: $a_1, a_2, \ldots, a_n$. Your task is to find some non-zero integer $d$ ($-10^3 \leq d \leq 10^3$) such that, after each number in the array is divided by $d$, the number of positive numbers that are presented in the array is greater than or equal to half of the array size (i.e., at least $\lceil\frac{n}{2}\rceil$). Note that those positive numbers do not need to be an integer (e.g., a $2.5$ counts as a positive number). If there are multiple values of $d$ that satisfy the condition, you may print any of them. In case that there is no such $d$, print a single integer $0$.

Recall that $\lceil x \rceil$ represents the smallest integer that is not less than $x$ and that zero ($0$) is neither positive nor negative.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 100$) — the number of elements in the array.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($-10^3 \le a_i \le 10^3$).


-----Output-----

Print one integer $d$ ($-10^3 \leq d \leq 10^3$ and $d \neq 0$) that satisfies the given condition. If there are multiple values of $d$ that satisfy the condition, you may print any of them. In case that there is no such $d$, print a single integer $0$.


-----Examples-----
Input
5
10 0 -7 2 6
Output
4
Input
7
0 0 1 -1 0 0 2

Output
0


-----Note-----

In the first sample, $n = 5$, so we need at least $\lceil\frac{5}{2}\rceil = 3$ positive numbers after division. If $d = 4$, the array after division is $[2.5, 0, -1.75, 0.5, 1.5]$, in which there are $3$ positive numbers (namely: $2.5$, $0.5$, and $1.5$).

In the second sample, there is no valid $d$, so $0$ should be printed.
user: There are n shovels in Polycarp's shop. The i-th shovel costs i burles, that is, the first shovel costs 1 burle, the second shovel costs 2 burles, the third shovel costs 3 burles, and so on. Polycarps wants to sell shovels in pairs.

Visitors are more likely to buy a pair of shovels if their total cost ends with several 9s. Because of this, Polycarp wants to choose a pair of shovels to sell in such a way that the sum of their costs ends with maximum possible number of nines. For example, if he chooses shovels with costs 12345 and 37454, their total cost is 49799, it ends with two nines.

You are to compute the number of pairs of shovels such that their total cost ends with maximum possible number of nines. Two pairs are considered different if there is a shovel presented in one pair, but not in the other.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^9) — the number of shovels in Polycarp's shop.


-----Output-----

Print the number of pairs of shovels such that their total cost ends with maximum possible number of nines. 

Note that it is possible that the largest number of 9s at the end is 0, then you should count all such ways.

It is guaranteed that for every n ≤ 10^9 the answer doesn't exceed 2·10^9.


-----Examples-----
Input
7

Output
3

Input
14

Output
9

Input
50

Output
1



-----Note-----

In the first example the maximum possible number of nines at the end is one. Polycarp cah choose the following pairs of shovels for that purpose:  2 and 7;  3 and 6;  4 and 5. 

In the second example the maximum number of nines at the end of total cost of two shovels is one. The following pairs of shovels suit Polycarp:  1 and 8;  2 and 7;  3 and 6;  4 and 5;  5 and 14;  6 and 13;  7 and 12;  8 and 11;  9 and 10. 

In the third example it is necessary to choose shovels 49 and 50, because the sum of their cost is 99, that means that the total number of nines is equal to two, which is maximum possible for n = 50.