meetforever/GRPO_CL huggingface dataset:
user: Luba has a ticket consisting of 6 digits. In one move she can choose digit in any position and replace it with arbitrary digit. She wants to know the minimum number of digits she needs to replace in order to make the ticket lucky.

The ticket is considered lucky if the sum of first three digits equals to the sum of last three digits.


-----Input-----

You are given a string consisting of 6 characters (all characters are digits from 0 to 9) — this string denotes Luba's ticket. The ticket can start with the digit 0.


-----Output-----

Print one number — the minimum possible number of digits Luba needs to replace to make the ticket lucky.


-----Examples-----
Input
000000

Output
0

Input
123456

Output
2

Input
111000

Output
1



-----Note-----

In the first example the ticket is already lucky, so the answer is 0.

In the second example Luba can replace 4 and 5 with zeroes, and the ticket will become lucky. It's easy to see that at least two replacements are required.

In the third example Luba can replace any zero with 3. It's easy to see that at least one replacement is required.
user: The campus has $m$ rooms numbered from $0$ to $m - 1$. Also the $x$-mouse lives in the campus. The $x$-mouse is not just a mouse: each second $x$-mouse moves from room $i$ to the room $i \cdot x \mod{m}$ (in fact, it teleports from one room to another since it doesn't visit any intermediate room). Starting position of the $x$-mouse is unknown.

You are responsible to catch the $x$-mouse in the campus, so you are guessing about minimum possible number of traps (one trap in one room) you need to place. You are sure that if the $x$-mouse enters a trapped room, it immediately gets caught.

And the only observation you made is $\text{GCD} (x, m) = 1$.


-----Input-----

The only line contains two integers $m$ and $x$ ($2 \le m \le 10^{14}$, $1 \le x < m$, $\text{GCD} (x, m) = 1$) — the number of rooms and the parameter of $x$-mouse. 


-----Output-----

Print the only integer — minimum number of traps you need to install to catch the $x$-mouse.


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

Output
3

Input
5 2

Output
2



-----Note-----

In the first example you can, for example, put traps in rooms $0$, $2$, $3$. If the $x$-mouse starts in one of this rooms it will be caught immediately. If $x$-mouse starts in the $1$-st rooms then it will move to the room $3$, where it will be caught.

In the second example you can put one trap in room $0$ and one trap in any other room since $x$-mouse will visit all rooms $1..m-1$ if it will start in any of these rooms.
user: ZS the Coder has recently found an interesting concept called the Birthday Paradox. It states that given a random set of 23 people, there is around 50% chance that some two of them share the same birthday. ZS the Coder finds this very interesting, and decides to test this with the inhabitants of Udayland.

In Udayland, there are 2^{n} days in a year. ZS the Coder wants to interview k people from Udayland, each of them has birthday in one of 2^{n} days (each day with equal probability). He is interested in the probability of at least two of them have the birthday at the same day. 

ZS the Coder knows that the answer can be written as an irreducible fraction $\frac{A}{B}$. He wants to find the values of A and B (he does not like to deal with floating point numbers). Can you help him?


-----Input-----

The first and only line of the input contains two integers n and k (1 ≤ n ≤ 10^18, 2 ≤ k ≤ 10^18), meaning that there are 2^{n} days in a year and that ZS the Coder wants to interview exactly k people.


-----Output-----

If the probability of at least two k people having the same birthday in 2^{n} days long year equals $\frac{A}{B}$ (A ≥ 0, B ≥ 1, $\operatorname{gcd}(A, B) = 1$), print the A and B in a single line.

Since these numbers may be too large, print them modulo 10^6 + 3. Note that A and B must be coprime before their remainders modulo 10^6 + 3 are taken.


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

Output
1 8
Input
1 3

Output
1 1
Input
4 3

Output
23 128


-----Note-----

In the first sample case, there are 2^3 = 8 days in Udayland. The probability that 2 people have the same birthday among 2 people is clearly $\frac{1}{8}$, so A = 1, B = 8.

In the second sample case, there are only 2^1 = 2 days in Udayland, but there are 3 people, so it is guaranteed that two of them have the same birthday. Thus, the probability is 1 and A = B = 1.
user: In this problem we assume the Earth to be a completely round ball and its surface a perfect sphere. The length of the equator and any meridian is considered to be exactly 40 000 kilometers. Thus, travelling from North Pole to South Pole or vice versa takes exactly 20 000 kilometers.

Limak, a polar bear, lives on the North Pole. Close to the New Year, he helps somebody with delivering packages all around the world. Instead of coordinates of places to visit, Limak got a description how he should move, assuming that he starts from the North Pole. The description consists of n parts. In the i-th part of his journey, Limak should move t_{i} kilometers in the direction represented by a string dir_{i} that is one of: "North", "South", "West", "East".

Limak isn’t sure whether the description is valid. You must help him to check the following conditions:  If at any moment of time (before any of the instructions or while performing one of them) Limak is on the North Pole, he can move only to the South.  If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North.  The journey must end on the North Pole. 

Check if the above conditions are satisfied and print "YES" or "NO" on a single line.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 50).

The i-th of next n lines contains an integer t_{i} and a string dir_{i} (1 ≤ t_{i} ≤ 10^6, $\operatorname{dir}_{i} \in \{\text{North, South, West, East} \}$) — the length and the direction of the i-th part of the journey, according to the description Limak got.


-----Output-----

Print "YES" if the description satisfies the three conditions, otherwise print "NO", both without the quotes.


-----Examples-----
Input
5
7500 South
10000 East
3500 North
4444 West
4000 North

Output
YES

Input
2
15000 South
4000 East

Output
NO

Input
5
20000 South
1000 North
1000000 West
9000 North
10000 North

Output
YES

Input
3
20000 South
10 East
20000 North

Output
NO

Input
2
1000 North
1000 South

Output
NO

Input
4
50 South
50 North
15000 South
15000 North

Output
YES



-----Note-----

Drawings below show how Limak's journey would look like in first two samples. In the second sample the answer is "NO" because he doesn't end on the North Pole. [Image]
user: You are given two arithmetic progressions: a_1k + b_1 and a_2l + b_2. Find the number of integers x such that L ≤ x ≤ R and x = a_1k' + b_1 = a_2l' + b_2, for some integers k', l' ≥ 0.


-----Input-----

The only line contains six integers a_1, b_1, a_2, b_2, L, R (0 < a_1, a_2 ≤ 2·10^9,  - 2·10^9 ≤ b_1, b_2, L, R ≤ 2·10^9, L ≤ R).


-----Output-----

Print the desired number of integers x.


-----Examples-----
Input
2 0 3 3 5 21

Output
3

Input
2 4 3 0 6 17

Output
2
user: It's New Year's Eve soon, so Ivan decided it's high time he started setting the table. Ivan has bought two cakes and cut them into pieces: the first cake has been cut into a pieces, and the second one — into b pieces.

Ivan knows that there will be n people at the celebration (including himself), so Ivan has set n plates for the cakes. Now he is thinking about how to distribute the cakes between the plates. Ivan wants to do it in such a way that all following conditions are met:  Each piece of each cake is put on some plate;  Each plate contains at least one piece of cake;  No plate contains pieces of both cakes. 

To make his guests happy, Ivan wants to distribute the cakes in such a way that the minimum number of pieces on the plate is maximized. Formally, Ivan wants to know the maximum possible number x such that he can distribute the cakes according to the aforementioned conditions, and each plate will contain at least x pieces of cake.

Help Ivan to calculate this number x!


-----Input-----

The first line contains three integers n, a and b (1 ≤ a, b ≤ 100, 2 ≤ n ≤ a + b) — the number of plates, the number of pieces of the first cake, and the number of pieces of the second cake, respectively.


-----Output-----

Print the maximum possible number x such that Ivan can distribute the cake in such a way that each plate will contain at least x pieces of cake.


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

Output
1

Input
4 7 10

Output
3



-----Note-----

In the first example there is only one way to distribute cakes to plates, all of them will have 1 cake on it.

In the second example you can have two plates with 3 and 4 pieces of the first cake and two plates both with 5 pieces of the second cake. Minimal number of pieces is 3.
user: The flag of Berland is such rectangular field n × m that satisfies following conditions:

  Flag consists of three colors which correspond to letters 'R', 'G' and 'B'.  Flag consists of three equal in width and height stripes, parralel to each other and to sides of the flag. Each stripe has exactly one color.  Each color should be used in exactly one stripe. 

You are given a field n × m, consisting of characters 'R', 'G' and 'B'. Output "YES" (without quotes) if this field corresponds to correct flag of Berland. Otherwise, print "NO" (without quotes).


-----Input-----

The first line contains two integer numbers n and m (1 ≤ n, m ≤ 100) — the sizes of the field.

Each of the following n lines consisting of m characters 'R', 'G' and 'B' — the description of the field.


-----Output-----

Print "YES" (without quotes) if the given field corresponds to correct flag of Berland . Otherwise, print "NO" (without quotes).


-----Examples-----
Input
6 5
RRRRR
RRRRR
BBBBB
BBBBB
GGGGG
GGGGG

Output
YES

Input
4 3
BRG
BRG
BRG
BRG

Output
YES

Input
6 7
RRRGGGG
RRRGGGG
RRRGGGG
RRRBBBB
RRRBBBB
RRRBBBB

Output
NO

Input
4 4
RRRR
RRRR
BBBB
GGGG

Output
NO



-----Note-----

The field in the third example doesn't have three parralel stripes.

Rows of the field in the fourth example are parralel to each other and to borders. But they have different heights — 2, 1 and 1.
user: Ayrat is looking for the perfect code. He decided to start his search from an infinite field tiled by hexagons. For convenience the coordinate system is introduced, take a look at the picture to see how the coordinates of hexagon are defined: 

[Image] [Image] Ayrat is searching through the field. He started at point (0, 0) and is moving along the spiral (see second picture). Sometimes he forgets where he is now. Help Ayrat determine his location after n moves.


-----Input-----

The only line of the input contains integer n (0 ≤ n ≤ 10^18) — the number of Ayrat's moves.


-----Output-----

Print two integers x and y — current coordinates of Ayrat coordinates.


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

Output
-2 0

Input
7

Output
3 2
user: Dante is engaged in a fight with "The Savior". Before he can fight it with his sword, he needs to break its shields. He has two guns, Ebony and Ivory, each of them is able to perform any non-negative number of shots.

For every bullet that hits the shield, Ebony deals a units of damage while Ivory deals b units of damage. In order to break the shield Dante has to deal exactly c units of damage. Find out if this is possible.


-----Input-----

The first line of the input contains three integers a, b, c (1 ≤ a, b ≤ 100, 1 ≤ c ≤ 10 000) — the number of units of damage dealt by Ebony gun and Ivory gun, and the total number of damage required to break the shield, respectively.


-----Output-----

Print "Yes" (without quotes) if Dante can deal exactly c damage to the shield and "No" (without quotes) otherwise.


-----Examples-----
Input
4 6 15

Output
No

Input
3 2 7

Output
Yes

Input
6 11 6

Output
Yes



-----Note-----

In the second sample, Dante can fire 1 bullet from Ebony and 2 from Ivory to deal exactly 1·3 + 2·2 = 7 damage. In the third sample, Dante can fire 1 bullet from ebony and no bullets from ivory to do 1·6 + 0·11 = 6 damage.
user: Running with barriers on the circle track is very popular in the country where Dasha lives, so no wonder that on her way to classes she saw the following situation:

The track is the circle with length L, in distinct points of which there are n barriers. Athlete always run the track in counterclockwise direction if you look on him from above. All barriers are located at integer distance from each other along the track. 

Her friends the parrot Kefa and the leopard Sasha participated in competitions and each of them ran one lap. Each of the friends started from some integral point on the track. Both friends wrote the distance from their start along the track to each of the n barriers. Thus, each of them wrote n integers in the ascending order, each of them was between 0 and L - 1, inclusively. [Image] Consider an example. Let L = 8, blue points are barriers, and green points are Kefa's start (A) and Sasha's start (B). Then Kefa writes down the sequence [2, 4, 6], and Sasha writes down [1, 5, 7]. 

There are several tracks in the country, all of them have same length and same number of barriers, but the positions of the barriers can differ among different tracks. Now Dasha is interested if it is possible that Kefa and Sasha ran the same track or they participated on different tracks. 

Write the program which will check that Kefa's and Sasha's tracks coincide (it means that one can be obtained from the other by changing the start position). Note that they always run the track in one direction — counterclockwise, if you look on a track from above. 


-----Input-----

The first line contains two integers n and L (1 ≤ n ≤ 50, n ≤ L ≤ 100) — the number of barriers on a track and its length. 

The second line contains n distinct integers in the ascending order — the distance from Kefa's start to each barrier in the order of its appearance. All integers are in the range from 0 to L - 1 inclusively.

The second line contains n distinct integers in the ascending order — the distance from Sasha's start to each barrier in the order of its overcoming. All integers are in the range from 0 to L - 1 inclusively.


-----Output-----

Print "YES" (without quotes), if Kefa and Sasha ran the coinciding tracks (it means that the position of all barriers coincides, if they start running from the same points on the track). Otherwise print "NO" (without quotes).


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

Output
YES

Input
4 9
2 3 5 8
0 1 3 6

Output
YES

Input
2 4
1 3
1 2

Output
NO



-----Note-----

The first test is analyzed in the statement.
user: A string is a palindrome if it reads the same from the left to the right and from the right to the left. For example, the strings "kek", "abacaba", "r" and "papicipap" are palindromes, while the strings "abb" and "iq" are not.

A substring $s[l \ldots r]$ ($1 \leq l \leq r \leq |s|$) of a string $s = s_{1}s_{2} \ldots s_{|s|}$ is the string $s_{l}s_{l + 1} \ldots s_{r}$.

Anna does not like palindromes, so she makes her friends call her Ann. She also changes all the words she reads in a similar way. Namely, each word $s$ is changed into its longest substring that is not a palindrome. If all the substrings of $s$ are palindromes, she skips the word at all.

Some time ago Ann read the word $s$. What is the word she changed it into?


-----Input-----

The first line contains a non-empty string $s$ with length at most $50$ characters, containing lowercase English letters only.


-----Output-----

If there is such a substring in $s$ that is not a palindrome, print the maximum length of such a substring. Otherwise print $0$.

Note that there can be multiple longest substrings that are not palindromes, but their length is unique.


-----Examples-----
Input
mew

Output
3

Input
wuffuw

Output
5

Input
qqqqqqqq

Output
0



-----Note-----

"mew" is not a palindrome, so the longest substring of it that is not a palindrome, is the string "mew" itself. Thus, the answer for the first example is $3$.

The string "uffuw" is one of the longest non-palindrome substrings (of length $5$) of the string "wuffuw", so the answer for the second example is $5$.

All substrings of the string "qqqqqqqq" consist of equal characters so they are palindromes. This way, there are no non-palindrome substrings. Thus, the answer for the third example is $0$.
user: Is it rated?

Here it is. The Ultimate Question of Competitive Programming, Codeforces, and Everything. And you are here to answer it.

Another Codeforces round has been conducted. No two participants have the same number of points. For each participant, from the top to the bottom of the standings, their rating before and after the round is known.

It's known that if at least one participant's rating has changed, then the round was rated for sure.

It's also known that if the round was rated and a participant with lower rating took a better place in the standings than a participant with higher rating, then at least one round participant's rating has changed.

In this problem, you should not make any other assumptions about the rating system.

Determine if the current round is rated, unrated, or it's impossible to determine whether it is rated of not.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 1000) — the number of round participants.

Each of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 4126) — the rating of the i-th participant before and after the round, respectively. The participants are listed in order from the top to the bottom of the standings.


-----Output-----

If the round is rated for sure, print "rated". If the round is unrated for sure, print "unrated". If it's impossible to determine whether the round is rated or not, print "maybe".


-----Examples-----
Input
6
3060 3060
2194 2194
2876 2903
2624 2624
3007 2991
2884 2884

Output
rated

Input
4
1500 1500
1300 1300
1200 1200
1400 1400

Output
unrated

Input
5
3123 3123
2777 2777
2246 2246
2246 2246
1699 1699

Output
maybe



-----Note-----

In the first example, the ratings of the participants in the third and fifth places have changed, therefore, the round was rated.

In the second example, no one's rating has changed, but the participant in the second place has lower rating than the participant in the fourth place. Therefore, if the round was rated, someone's rating would've changed for sure.

In the third example, no one's rating has changed, and the participants took places in non-increasing order of their rating. Therefore, it's impossible to determine whether the round is rated or not.
user: You are given the array of integer numbers a_0, a_1, ..., a_{n} - 1. For each element find the distance to the nearest zero (to the element which equals to zero). There is at least one zero element in the given array.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2·10^5) — length of the array a. The second line contains integer elements of the array separated by single spaces ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

Print the sequence d_0, d_1, ..., d_{n} - 1, where d_{i} is the difference of indices between i and nearest j such that a_{j} = 0. It is possible that i = j.


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

Output
2 1 0 1 0 0 1 2 3 
Input
5
0 1 2 3 4

Output
0 1 2 3 4 
Input
7
5 6 0 1 -2 3 4

Output
2 1 0 1 2 3 4
user: You are given a binary string $s$.

Find the number of distinct cyclical binary strings of length $n$ which contain $s$ as a substring.

The cyclical string $t$ contains $s$ as a substring if there is some cyclical shift of string $t$, such that $s$ is a substring of this cyclical shift of $t$.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 40$) — the length of the target string $t$.

The next line contains the string $s$ ($1 \le |s| \le n$) — the string which must be a substring of cyclical string $t$. String $s$ contains only characters '0' and '1'.


-----Output-----

Print the only integer — the number of distinct cyclical binary strings $t$, which contain $s$ as a substring.


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

Output
3
Input
4
1010

Output
2
Input
20
10101010101010

Output
962


-----Note-----

In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".
user: You are given the set of vectors on the plane, each of them starting at the origin. Your task is to find a pair of vectors with the minimal non-oriented angle between them.

Non-oriented angle is non-negative value, minimal between clockwise and counterclockwise direction angles. Non-oriented angle is always between 0 and π. For example, opposite directions vectors have angle equals to π.


-----Input-----

First line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vectors.

The i-th of the following n lines contains two integers x_{i} and y_{i} (|x|, |y| ≤ 10 000, x^2 + y^2 > 0) — the coordinates of the i-th vector. Vectors are numbered from 1 to n in order of appearing in the input. It is guaranteed that no two vectors in the input share the same direction (but they still can have opposite directions).


-----Output-----

Print two integer numbers a and b (a ≠ b) — a pair of indices of vectors with the minimal non-oriented angle. You can print the numbers in any order. If there are many possible answers, print any.


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

Output
3 4

Input
6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6

Output
6 5
user: Vasiliy has a car and he wants to get from home to the post office. The distance which he needs to pass equals to d kilometers.

Vasiliy's car is not new — it breaks after driven every k kilometers and Vasiliy needs t seconds to repair it. After repairing his car Vasiliy can drive again (but after k kilometers it will break again, and so on). In the beginning of the trip the car is just from repair station.

To drive one kilometer on car Vasiliy spends a seconds, to walk one kilometer on foot he needs b seconds (a < b).

Your task is to find minimal time after which Vasiliy will be able to reach the post office. Consider that in every moment of time Vasiliy can left his car and start to go on foot.


-----Input-----

The first line contains 5 positive integers d, k, a, b, t (1 ≤ d ≤ 10^12; 1 ≤ k, a, b, t ≤ 10^6; a < b), where:  d — the distance from home to the post office;  k — the distance, which car is able to drive before breaking;  a — the time, which Vasiliy spends to drive 1 kilometer on his car;  b — the time, which Vasiliy spends to walk 1 kilometer on foot;  t — the time, which Vasiliy spends to repair his car. 


-----Output-----

Print the minimal time after which Vasiliy will be able to reach the post office.


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

Output
14

Input
5 2 1 4 5

Output
13



-----Note-----

In the first example Vasiliy needs to drive the first 2 kilometers on the car (in 2 seconds) and then to walk on foot 3 kilometers (in 12 seconds). So the answer equals to 14 seconds.

In the second example Vasiliy needs to drive the first 2 kilometers on the car (in 2 seconds), then repair his car (in 5 seconds) and drive 2 kilometers more on the car (in 2 seconds). After that he needs to walk on foot 1 kilometer (in 4 seconds). So the answer equals to 13 seconds.