meetforever/GRPO_CL huggingface dataset:
user: Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases.

But Zulu warns him that a group of k > 1 Pokemon with strengths {s_1, s_2, s_3, ..., s_{k}} tend to fight among each other if gcd(s_1, s_2, s_3, ..., s_{k}) = 1 (see notes for gcd definition).

Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take? 

Note: A Pokemon cannot fight with itself.


-----Input-----

The input consists of two lines.

The first line contains an integer n (1 ≤ n ≤ 10^5), the number of Pokemon in the lab.

The next line contains n space separated integers, where the i-th of them denotes s_{i} (1 ≤ s_{i} ≤ 10^5), the strength of the i-th Pokemon.


-----Output-----

Print single integer — the maximum number of Pokemons Bash can take.


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

Output
2

Input
5
2 3 4 6 7

Output
3



-----Note-----

gcd (greatest common divisor) of positive integers set {a_1, a_2, ..., a_{n}} is the maximum positive integer that divides all the integers {a_1, a_2, ..., a_{n}}.

In the first sample, we can take Pokemons with strengths {2, 4} since gcd(2, 4) = 2.

In the second sample, we can take Pokemons with strengths {2, 4, 6}, and there is no larger group with gcd ≠ 1.
user: We have a string S of length N consisting of A, B, and C.
You can do the following operation on S zero or more times:
 - Choose i (1 \leq i \leq |S| - 1) such that S_i \neq S_{i + 1}. Replace S_i with the character (among A, B, and C) that is different from both S_i and S_{i + 1}, and remove S_{i + 1} from S.
Find the number of distinct strings that S can be after zero or more operations, and print the count modulo (10^9+7).

-----Constraints-----
 - 1 \leq N \leq 10^6
 - S is a string of length N consisting of A, B, and C.

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

-----Output-----
Print the number of distinct strings that S can be after zero or more operations, modulo (10^9+7).

-----Sample Input-----
5
ABAAC

-----Sample Output-----
11

For example, the following sequence of operations turns S into ACB:
 - First, choose i=2. We replace S_2 with C and remove S_3, turning S into ACAC.
 - Then, choose i=3. We replace S_3 with B and remove S_4, turning S into ACB.
user: Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is h_1 and height of Abol is h_2. Each second, Mike waters Abol and Xaniar.

 [Image] 

So, if height of Xaniar is h_1 and height of Abol is h_2, after one second height of Xaniar will become $(x_{1} h_{1} + y_{1}) \operatorname{mod} m$ and height of Abol will become $(x_{2} h_{2} + y_{2}) \operatorname{mod} m$ where x_1, y_1, x_2 and y_2 are some integer numbers and $a \operatorname{mod} b$ denotes the remainder of a modulo b.

Mike is a competitive programmer fan. He wants to know the minimum time it takes until height of Xania is a_1 and height of Abol is a_2.

Mike has asked you for your help. Calculate the minimum time or say it will never happen.


-----Input-----

The first line of input contains integer m (2 ≤ m ≤ 10^6).

The second line of input contains integers h_1 and a_1 (0 ≤ h_1, a_1 < m).

The third line of input contains integers x_1 and y_1 (0 ≤ x_1, y_1 < m).

The fourth line of input contains integers h_2 and a_2 (0 ≤ h_2, a_2 < m).

The fifth line of input contains integers x_2 and y_2 (0 ≤ x_2, y_2 < m).

It is guaranteed that h_1 ≠ a_1 and h_2 ≠ a_2.


-----Output-----

Print the minimum number of seconds until Xaniar reaches height a_1 and Abol reaches height a_2 or print -1 otherwise.


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

Output
3

Input
1023
1 2
1 0
1 2
1 1

Output
-1



-----Note-----

In the first sample, heights sequences are following:

Xaniar: $4 \rightarrow 0 \rightarrow 1 \rightarrow 2$

Abol: $0 \rightarrow 3 \rightarrow 4 \rightarrow 1$
user: There are infinitely many cards, numbered 1, 2, 3, ...
Initially, Cards x_1, x_2, ..., x_N are face up, and the others are face down.
Snuke can perform the following operation repeatedly:
 - Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.
Snuke's objective is to have all the cards face down.
Find the minimum number of operations required to achieve the objective.

-----Constraints-----
 - 1 ≤ N ≤ 100
 - 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 x_2 ... x_N

-----Output-----
Print the minimum number of operations required to achieve the objective.

-----Sample Input-----
2
4 5

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

Below is one way to achieve the objective in two operations:
 - Select p = 5 and flip Cards 1, 2, 3, 4 and 5.
 - Select p = 3 and flip Cards 1, 2 and 3.
user: An integer sequence is called beautiful if the difference between any two consecutive numbers is equal to $1$. More formally, a sequence $s_1, s_2, \ldots, s_{n}$ is beautiful if $|s_i - s_{i+1}| = 1$ for all $1 \leq i \leq n - 1$.

Trans has $a$ numbers $0$, $b$ numbers $1$, $c$ numbers $2$ and $d$ numbers $3$. He wants to construct a beautiful sequence using all of these $a + b + c + d$ numbers.

However, it turns out to be a non-trivial task, and Trans was not able to do it. Could you please help Trans?


-----Input-----

The only input line contains four non-negative integers $a$, $b$, $c$ and $d$ ($0 < a+b+c+d \leq 10^5$).


-----Output-----

If it is impossible to construct a beautiful sequence satisfying the above constraints, print "NO" (without quotes) in one line.

Otherwise, print "YES" (without quotes) in the first line. Then in the second line print $a + b + c + d$ integers, separated by spaces — a beautiful sequence. There should be $a$ numbers equal to $0$, $b$ numbers equal to $1$, $c$ numbers equal to $2$ and $d$ numbers equal to $3$.

If there are multiple answers, you can print any of them.


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

Output
YES
0 1 0 1 2 3 2

Input
1 2 3 4

Output
NO

Input
2 2 2 3

Output
NO



-----Note-----

In the first test, it is easy to see, that the sequence is beautiful because the difference between any two consecutive numbers is equal to $1$. Also, there are exactly two numbers, equal to $0$, $1$, $2$ and exactly one number, equal to $3$.

It can be proved, that it is impossible to construct beautiful sequences in the second and third tests.
user: You are given a table consisting of n rows and m columns.

Numbers in each row form a permutation of integers from 1 to m.

You are allowed to pick two elements in one row and swap them, but no more than once for each row. Also, no more than once you are allowed to pick two columns and swap them. Thus, you are allowed to perform from 0 to n + 1 actions in total. Operations can be performed in any order.

You have to check whether it's possible to obtain the identity permutation 1, 2, ..., m in each row. In other words, check if one can perform some of the operation following the given rules and make each row sorted in increasing order.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 20) — the number of rows and the number of columns in the given table. 

Each of next n lines contains m integers — elements of the table. It's guaranteed that numbers in each line form a permutation of integers from 1 to m.


-----Output-----

If there is a way to obtain the identity permutation in each row by following the given rules, print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).


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

Output
YES

Input
4 4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Output
NO

Input
3 6
2 1 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5

Output
YES



-----Note-----

In the first sample, one can act in the following way:   Swap second and third columns. Now the table is 1 2 3 4 1 4 3 2  In the second row, swap the second and the fourth elements. Now the table is 1 2 3 4 1 2 3 4
user: Tarly has two different type of items, food boxes and wine barrels. There are f food boxes and w wine barrels. Tarly stores them in various stacks and each stack can consist of either food boxes or wine barrels but not both. The stacks are placed in a line such that no two stacks of food boxes are together and no two stacks of wine barrels are together.

The height of a stack is defined as the number of items in the stack. Two stacks are considered different if either their heights are different or one of them contains food and other contains wine.

Jon Snow doesn't like an arrangement if any stack of wine barrels has height less than or equal to h. What is the probability that Jon Snow will like the arrangement if all arrangement are equiprobably?

Two arrangement of stacks are considered different if exists such i, that i-th stack of one arrangement is different from the i-th stack of the other arrangement.


-----Input-----

The first line of input contains three integers f, w, h (0 ≤ f, w, h ≤ 10^5) — number of food boxes, number of wine barrels and h is as described above. It is guaranteed that he has at least one food box or at least one wine barrel.


-----Output-----

Output the probability that Jon Snow will like the arrangement. The probability is of the form [Image], then you need to output a single integer p·q^{ - 1} mod (10^9 + 7).


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

Output
0

Input
1 2 1

Output
666666672



-----Note-----

In the first example f  =  1, w = 1 and h = 1, there are only two possible arrangement of stacks and Jon Snow doesn't like any of them.

In the second example f = 1, w = 2 and h = 1, there are three arrangements. Jon Snow likes the (1) and (3) arrangement. So the probabilty is $\frac{2}{3}$. [Image]
user: DZY has a sequence a, consisting of n integers.

We'll call a sequence a_{i}, a_{i} + 1, ..., a_{j} (1 ≤ i ≤ j ≤ n) a subsegment of the sequence a. The value (j - i + 1) denotes the length of the subsegment.

Your task is to find the longest subsegment of a, such that it is possible to change at most one number (change one number to any integer you want) from the subsegment to make the subsegment strictly increasing.

You only need to output the length of the subsegment you find.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The next line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

In a single line print the answer to the problem — the maximum length of the required subsegment.


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

Output
5



-----Note-----

You can choose subsegment a_2, a_3, a_4, a_5, a_6 and change its 3rd element (that is a_4) to 4.
user: Sometimes Mister B has free evenings when he doesn't know what to do. Fortunately, Mister B found a new game, where the player can play against aliens.

All characters in this game are lowercase English letters. There are two players: Mister B and his competitor.

Initially the players have a string s consisting of the first a English letters in alphabetical order (for example, if a = 5, then s equals to "abcde").

The players take turns appending letters to string s. Mister B moves first.

Mister B must append exactly b letters on each his move. He can arbitrary choose these letters. His opponent adds exactly a letters on each move.

Mister B quickly understood that his opponent was just a computer that used a simple algorithm. The computer on each turn considers the suffix of string s of length a and generates a string t of length a such that all letters in the string t are distinct and don't appear in the considered suffix. From multiple variants of t lexicographically minimal is chosen (if a = 4 and the suffix is "bfdd", the computer chooses string t equal to "aceg"). After that the chosen string t is appended to the end of s.

Mister B soon found the game boring and came up with the following question: what can be the minimum possible number of different letters in string s on the segment between positions l and r, inclusive. Letters of string s are numerated starting from 1.


-----Input-----

First and only line contains four space-separated integers: a, b, l and r (1 ≤ a, b ≤ 12, 1 ≤ l ≤ r ≤ 10^9) — the numbers of letters each player appends and the bounds of the segment.


-----Output-----

Print one integer — the minimum possible number of different letters in the segment from position l to position r, inclusive, in string s.


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

Output
2
Input
4 2 2 6

Output
3
Input
3 7 4 6

Output
1


-----Note-----

In the first sample test one of optimal strategies generate string s = "abababab...", that's why answer is 2.

In the second sample test string s = "abcdbcaefg..." can be obtained, chosen segment will look like "bcdbc", that's why answer is 3.

In the third sample test string s = "abczzzacad..." can be obtained, chosen, segment will look like "zzz", that's why answer is 1.
user: Let us call a pair of integer numbers m-perfect, if at least one number in the pair is greater than or equal to m. Thus, the pairs (3, 3) and (0, 2) are 2-perfect while the pair (-1, 1) is not.

Two integers x, y are written on the blackboard. It is allowed to erase one of them and replace it with the sum of the numbers, (x + y).

What is the minimum number of such operations one has to perform in order to make the given pair of integers m-perfect?


-----Input-----

Single line of the input contains three integers x, y and m ( - 10^18 ≤ x, y, m ≤ 10^18).

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


-----Output-----

Print the minimum number of operations or "-1" (without quotes), if it is impossible to transform the given pair to the m-perfect one.


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

Output
2

Input
-1 4 15

Output
4

Input
0 -1 5

Output
-1



-----Note-----

In the first sample the following sequence of operations is suitable: (1, 2) $\rightarrow$ (3, 2) $\rightarrow$ (5, 2).

In the second sample: (-1, 4) $\rightarrow$ (3, 4) $\rightarrow$ (7, 4) $\rightarrow$ (11, 4) $\rightarrow$ (15, 4).

Finally, in the third sample x, y cannot be made positive, hence there is no proper sequence of operations.
user: One common way of digitalizing sound is to record sound intensity at particular time moments. For each time moment intensity is recorded as a non-negative integer. Thus we can represent a sound file as an array of $n$ non-negative integers.

If there are exactly $K$ distinct values in the array, then we need $k = \lceil \log_{2} K \rceil$ bits to store each value. It then takes $nk$ bits to store the whole file.

To reduce the memory consumption we need to apply some compression. One common way is to reduce the number of possible intensity values. We choose two integers $l \le r$, and after that all intensity values are changed in the following way: if the intensity value is within the range $[l;r]$, we don't change it. If it is less than $l$, we change it to $l$; if it is greater than $r$, we change it to $r$. You can see that we lose some low and some high intensities.

Your task is to apply this compression in such a way that the file fits onto a disk of size $I$ bytes, and the number of changed elements in the array is minimal possible.

We remind you that $1$ byte contains $8$ bits.

$k = \lceil log_{2} K \rceil$ is the smallest integer such that $K \le 2^{k}$. In particular, if $K = 1$, then $k = 0$.


-----Input-----

The first line contains two integers $n$ and $I$ ($1 \le n \le 4 \cdot 10^{5}$, $1 \le I \le 10^{8}$) — the length of the array and the size of the disk in bytes, respectively.

The next line contains $n$ integers $a_{i}$ ($0 \le a_{i} \le 10^{9}$) — the array denoting the sound file.


-----Output-----

Print a single integer — the minimal possible number of changed elements.


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

Output
2

Input
6 2
2 1 2 3 4 3

Output
0

Input
6 1
1 1 2 2 3 3

Output
2



-----Note-----

In the first example we can choose $l=2, r=3$. The array becomes 2 2 2 3 3 3, the number of distinct elements is $K=2$, and the sound file fits onto the disk. Only two values are changed.

In the second example the disk is larger, so the initial file fits it and no changes are required.

In the third example we have to change both 1s or both 3s.
user: You are given names of two days of the week.

Please, determine whether it is possible that during some non-leap year the first day of some month was equal to the first day of the week you are given, while the first day of the next month was equal to the second day of the week you are given. Both months should belong to one year.

In this problem, we consider the Gregorian calendar to be used. The number of months in this calendar is equal to 12. The number of days in months during any non-leap year is: 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31.

Names of the days of the week are given with lowercase English letters: "monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday".


-----Input-----

The input consists of two lines, each of them containing the name of exactly one day of the week. It's guaranteed that each string in the input is from the set "monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday".


-----Output-----

Print "YES" (without quotes) if such situation is possible during some non-leap year. Otherwise, print "NO" (without quotes).


-----Examples-----
Input
monday
tuesday

Output
NO

Input
sunday
sunday

Output
YES

Input
saturday
tuesday

Output
YES



-----Note-----

In the second sample, one can consider February 1 and March 1 of year 2015. Both these days were Sundays.

In the third sample, one can consider July 1 and August 1 of year 2017. First of these two days is Saturday, while the second one is Tuesday.
user: You are given a positive integer $n$.

Let $S(x)$ be sum of digits in base 10 representation of $x$, for example, $S(123) = 1 + 2 + 3 = 6$, $S(0) = 0$.

Your task is to find two integers $a, b$, such that $0 \leq a, b \leq n$, $a + b = n$ and $S(a) + S(b)$ is the largest possible among all such pairs.


-----Input-----

The only line of input contains an integer $n$ $(1 \leq n \leq 10^{12})$.


-----Output-----

Print largest $S(a) + S(b)$ among all pairs of integers $a, b$, such that $0 \leq a, b \leq n$ and $a + b = n$.


-----Examples-----
Input
35

Output
17

Input
10000000000

Output
91



-----Note-----

In the first example, you can choose, for example, $a = 17$ and $b = 18$, so that $S(17) + S(18) = 1 + 7 + 1 + 8 = 17$. It can be shown that it is impossible to get a larger answer.

In the second test example, you can choose, for example, $a = 5000000001$ and $b = 4999999999$, with $S(5000000001) + S(4999999999) = 91$. It can be shown that it is impossible to get a larger answer.
user: Recently, a start up by two students of a state university of city F gained incredible popularity. Now it's time to start a new company. But what do we call it?

The market analysts came up with a very smart plan: the name of the company should be identical to its reflection in a mirror! In other words, if we write out the name of the company on a piece of paper in a line (horizontally, from left to right) with large English letters, then put this piece of paper in front of the mirror, then the reflection of the name in the mirror should perfectly match the line written on the piece of paper.

There are many suggestions for the company name, so coming up to the mirror with a piece of paper for each name wouldn't be sensible. The founders of the company decided to automatize this process. They asked you to write a program that can, given a word, determine whether the word is a 'mirror' word or not.


-----Input-----

The first line contains a non-empty name that needs to be checked. The name contains at most 10^5 large English letters. The name will be written with the next sans serif font: $\text{ABCDEFGHI JKLMNOPQRSTUVWXYZ}$


-----Output-----

Print 'YES' (without the quotes), if the given name matches its mirror reflection. Otherwise, print 'NO' (without the quotes).


-----Examples-----
Input
AHA

Output
YES

Input
Z

Output
NO

Input
XO

Output
NO
user: "Night gathers, and now my watch begins. It shall not end until my death. I shall take no wife, hold no lands, father no children. I shall wear no crowns and win no glory. I shall live and die at my post. I am the sword in the darkness. I am the watcher on the walls. I am the shield that guards the realms of men. I pledge my life and honor to the Night's Watch, for this night and all the nights to come." — The Night's Watch oath.

With that begins the watch of Jon Snow. He is assigned the task to support the stewards.

This time he has n stewards with him whom he has to provide support. Each steward has his own strength. Jon Snow likes to support a steward only if there exists at least one steward who has strength strictly less than him and at least one steward who has strength strictly greater than him.

Can you find how many stewards will Jon support?


-----Input-----

First line consists of a single integer n (1 ≤ n ≤ 10^5) — the number of stewards with Jon Snow.

Second line consists of n space separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) representing the values assigned to the stewards.


-----Output-----

Output a single integer representing the number of stewards which Jon will feed.


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

Output
0
Input
3
1 2 5

Output
1


-----Note-----

In the first sample, Jon Snow cannot support steward with strength 1 because there is no steward with strength less than 1 and he cannot support steward with strength 5 because there is no steward with strength greater than 5.

In the second sample, Jon Snow can support steward with strength 2 because there are stewards with strength less than 2 and greater than 2.
user: Fox Ciel has a robot on a 2D plane. Initially it is located in (0, 0). Fox Ciel code a command to it. The command was represented by string s. Each character of s is one move operation. There are four move operations at all:  'U': go up, (x, y)  →  (x, y+1);  'D': go down, (x, y)  →  (x, y-1);  'L': go left, (x, y)  →  (x-1, y);  'R': go right, (x, y)  →  (x+1, y). 

The robot will do the operations in s from left to right, and repeat it infinite times. Help Fox Ciel to determine if after some steps the robot will located in (a, b).


-----Input-----

The first line contains two integers a and b, ( - 10^9 ≤ a, b ≤ 10^9). The second line contains a string s (1 ≤ |s| ≤ 100, s only contains characters 'U', 'D', 'L', 'R') — the command.


-----Output-----

Print "Yes" if the robot will be located at (a, b), and "No" otherwise.


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

Output
Yes

Input
1 2
RU

Output
No

Input
-1 1000000000
LRRLU

Output
Yes

Input
0 0
D

Output
Yes



-----Note-----

In the first and second test case, command string is "RU", so the robot will go right, then go up, then right, and then up and so on.

The locations of its moves are (0, 0)  →  (1, 0)  →  (1, 1)  →  (2, 1)  →  (2, 2)  →  ...

So it can reach (2, 2) but not (1, 2).