meetforever/GRPO_CL huggingface dataset:
user: There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission. 

Heidi has n Jedi Knights standing in front of her, each one with a lightsaber of one of m possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly k_1 knights with lightsabers of the first color, k_2 knights with lightsabers of the second color, ..., k_{m} knights with lightsabers of the m-th color.

However, since the last time, she has learned that it is not always possible to select such an interval. Therefore, she decided to ask some Jedi Knights to go on an indefinite unpaid vacation leave near certain pits on Tatooine, if you know what I mean. Help Heidi decide what is the minimum number of Jedi Knights that need to be let go before she is able to select the desired interval from the subsequence of remaining knights.


-----Input-----

The first line of the input contains n (1 ≤ n ≤ 2·10^5) and m (1 ≤ m ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains m integers k_1, k_2, ..., k_{m} (with $1 \leq \sum_{i = 1}^{m} k_{i} \leq n$) – the desired counts of Jedi Knights with lightsabers of each color from 1 to m.


-----Output-----

Output one number: the minimum number of Jedi Knights that need to be removed from the sequence so that, in what remains, there is an interval with the prescribed counts of lightsaber colors. If this is not possible, output  - 1.


-----Example-----
Input
8 3
3 3 1 2 2 1 1 3
3 1 1

Output
1
user: Polycarpus participates in a competition for hacking into a new secure messenger. He's almost won.

Having carefully studied the interaction protocol, Polycarpus came to the conclusion that the secret key can be obtained if he properly cuts the public key of the application into two parts. The public key is a long integer which may consist of even a million digits!

Polycarpus needs to find such a way to cut the public key into two nonempty parts, that the first (left) part is divisible by a as a separate number, and the second (right) part is divisible by b as a separate number. Both parts should be positive integers that have no leading zeros. Polycarpus knows values a and b.

Help Polycarpus and find any suitable method to cut the public key.


-----Input-----

The first line of the input contains the public key of the messenger — an integer without leading zeroes, its length is in range from 1 to 10^6 digits. The second line contains a pair of space-separated positive integers a, b (1 ≤ a, b ≤ 10^8).


-----Output-----

In the first line print "YES" (without the quotes), if the method satisfying conditions above exists. In this case, next print two lines — the left and right parts after the cut. These two parts, being concatenated, must be exactly identical to the public key. The left part must be divisible by a, and the right part must be divisible by b. The two parts must be positive integers having no leading zeros. If there are several answers, print any of them.

If there is no answer, print in a single line "NO" (without the quotes).


-----Examples-----
Input
116401024
97 1024

Output
YES
11640
1024

Input
284254589153928171911281811000
1009 1000

Output
YES
2842545891539
28171911281811000

Input
120
12 1

Output
NO
user: [Image] 


-----Input-----

The input contains two integers a_1, a_2 (0 ≤ a_{i} ≤ 32), separated by a single space.


-----Output-----

Output a single integer.


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

Output
0

Input
3 7

Output
0

Input
13 10

Output
1
user: The cows have just learned what a primitive root is! Given a prime p, a primitive root $\operatorname{mod} p$ is an integer x (1 ≤ x < p) such that none of integers x - 1, x^2 - 1, ..., x^{p} - 2 - 1 are divisible by p, but x^{p} - 1 - 1 is. 

Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime p, help the cows find the number of primitive roots $\operatorname{mod} p$.


-----Input-----

The input contains a single line containing an integer p (2 ≤ p < 2000). It is guaranteed that p is a prime.


-----Output-----

Output on a single line the number of primitive roots $\operatorname{mod} p$.


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

Output
1

Input
5

Output
2



-----Note-----

The only primitive root $\operatorname{mod} 3$ is 2.

The primitive roots $\operatorname{mod} 5$ are 2 and 3.
user: Natasha's favourite numbers are $n$ and $1$, and Sasha's favourite numbers are $m$ and $-1$. One day Natasha and Sasha met and wrote down every possible array of length $n+m$ such that some $n$ of its elements are equal to $1$ and another $m$ elements are equal to $-1$. For each such array they counted its maximal prefix sum, probably an empty one which is equal to $0$ (in another words, if every nonempty prefix sum is less to zero, then it is considered equal to zero). Formally, denote as $f(a)$ the maximal prefix sum of an array $a_{1, \ldots ,l}$ of length $l \geq 0$. Then: 

$$f(a) = \max (0, \smash{\displaystyle\max_{1 \leq i \leq l}} \sum_{j=1}^{i} a_j )$$

Now they want to count the sum of maximal prefix sums for each such an array and they are asking you to help. As this sum can be very large, output it modulo $998\: 244\: 853$.


-----Input-----

The only line contains two integers $n$ and $m$ ($0 \le n,m \le 2\,000$).


-----Output-----

Output the answer to the problem modulo $998\: 244\: 853$.


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

Output
0

Input
2 0

Output
2

Input
2 2

Output
5

Input
2000 2000

Output
674532367



-----Note-----

In the first example the only possible array is [-1,-1], its maximal prefix sum is equal to $0$. 

In the second example the only possible array is [1,1], its maximal prefix sum is equal to $2$. 

There are $6$ possible arrays in the third example:

[1,1,-1,-1], f([1,1,-1,-1]) = 2

[1,-1,1,-1], f([1,-1,1,-1]) = 1

[1,-1,-1,1], f([1,-1,-1,1]) = 1

[-1,1,1,-1], f([-1,1,1,-1]) = 1

[-1,1,-1,1], f([-1,1,-1,1]) = 0

[-1,-1,1,1], f([-1,-1,1,1]) = 0

So the answer for the third example is $2+1+1+1+0+0 = 5$.
user: Sereja is a coder and he likes to take part in Codesorfes rounds. However, Uzhland doesn't have good internet connection, so Sereja sometimes skips rounds.

Codesorfes has rounds of two types: Div1 (for advanced coders) and Div2 (for beginner coders). Two rounds, Div1 and Div2, can go simultaneously, (Div1 round cannot be held without Div2) in all other cases the rounds don't overlap in time. Each round has a unique identifier — a positive integer. The rounds are sequentially (without gaps) numbered with identifiers by the starting time of the round. The identifiers of rounds that are run simultaneously are different by one, also the identifier of the Div1 round is always greater.

Sereja is a beginner coder, so he can take part only in rounds of Div2 type. At the moment he is taking part in a Div2 round, its identifier equals to x. Sereja remembers very well that he has taken part in exactly k rounds before this round. Also, he remembers all identifiers of the rounds he has taken part in and all identifiers of the rounds that went simultaneously with them. Sereja doesn't remember anything about the rounds he missed.

Sereja is wondering: what minimum and what maximum number of Div2 rounds could he have missed? Help him find these two numbers.


-----Input-----

The first line contains two integers: x (1 ≤ x ≤ 4000) — the round Sereja is taking part in today, and k (0 ≤ k < 4000) — the number of rounds he took part in.

Next k lines contain the descriptions of the rounds that Sereja took part in before. If Sereja took part in one of two simultaneous rounds, the corresponding line looks like: "1 num_2 num_1" (where num_2 is the identifier of this Div2 round, num_1 is the identifier of the Div1 round). It is guaranteed that num_1 - num_2 = 1. If Sereja took part in a usual Div2 round, then the corresponding line looks like: "2 num" (where num is the identifier of this Div2 round). It is guaranteed that the identifiers of all given rounds are less than x.


-----Output-----

Print in a single line two integers — the minimum and the maximum number of rounds that Sereja could have missed.


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

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

Output
2 3
Input
10 0

Output
5 9


-----Note-----

In the second sample we have unused identifiers of rounds 1, 6, 7. The minimum number of rounds Sereja could have missed equals to 2. In this case, the round with the identifier 1 will be a usual Div2 round and the round with identifier 6 will be synchronous with the Div1 round. 

The maximum number of rounds equals 3. In this case all unused identifiers belong to usual Div2 rounds.
user: Valera had two bags of potatoes, the first of these bags contains x (x ≥ 1) potatoes, and the second — y (y ≥ 1) potatoes. Valera — very scattered boy, so the first bag of potatoes (it contains x potatoes) Valera lost. Valera remembers that the total amount of potatoes (x + y) in the two bags, firstly, was not gerater than n, and, secondly, was divisible by k.

Help Valera to determine how many potatoes could be in the first bag. Print all such possible numbers in ascending order.


-----Input-----

The first line of input contains three integers y, k, n (1 ≤ y, k, n ≤ 10^9; $\frac{n}{k}$  ≤ 10^5).


-----Output-----

Print the list of whitespace-separated integers — all possible values of x in ascending order. You should print each possible value of x exactly once.

If there are no such values of x print a single integer -1.


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

Output
-1

Input
10 6 40

Output
2 8 14 20 26
user: The stardate is 1977 and the science and art of detecting Death Stars is in its infancy. Princess Heidi has received information about the stars in the nearby solar system from the Rebel spies and now, to help her identify the exact location of the Death Star, she needs to know whether this information is correct. 

Two rebel spies have provided her with the maps of the solar system. Each map is an N × N grid, where each cell is either occupied by a star or empty. To see whether the information is correct, Heidi needs to know whether the two maps are of the same solar system, or if possibly one of the spies is actually an Empire double agent, feeding her false information.

Unfortunately, spies may have accidentally rotated a map by 90, 180, or 270 degrees, or flipped it along the vertical or the horizontal axis, before delivering it to Heidi. If Heidi can rotate or flip the maps so that two of them become identical, then those maps are of the same solar system. Otherwise, there are traitors in the Rebel ranks! Help Heidi find out.


-----Input-----

The first line of the input contains one number N (1 ≤ N ≤ 10) – the dimension of each map. Next N lines each contain N characters, depicting the first map: 'X' indicates a star, while 'O' indicates an empty quadrant of space. Next N lines each contain N characters, depicting the second map in the same format.


-----Output-----

The only line of output should contain the word Yes if the maps are identical, or No if it is impossible to match them by performing rotations and translations.


-----Examples-----
Input
4
XOOO
XXOO
OOOO
XXXX
XOOO
XOOO
XOXO
XOXX

Output
Yes

Input
2
XX
OO
XO
OX

Output
No



-----Note-----

In the first test, you can match the first map to the second map by first flipping the first map along the vertical axis, and then by rotating it 90 degrees clockwise.
user: Bizon the Champion isn't just a bison. He also is a favorite of the "Bizons" team.

At a competition the "Bizons" got the following problem: "You are given two distinct words (strings of English letters), s and t. You need to transform word s into word t". The task looked simple to the guys because they know the suffix data structures well. Bizon Senior loves suffix automaton. By applying it once to a string, he can remove from this string any single character. Bizon Middle knows suffix array well. By applying it once to a string, he can swap any two characters of this string. The guys do not know anything about the suffix tree, but it can help them do much more. 

Bizon the Champion wonders whether the "Bizons" can solve the problem. Perhaps, the solution do not require both data structures. Find out whether the guys can solve the problem and if they can, how do they do it? Can they solve it either only with use of suffix automaton or only with use of suffix array or they need both structures? Note that any structure may be used an unlimited number of times, the structures may be used in any order.


-----Input-----

The first line contains a non-empty word s. The second line contains a non-empty word t. Words s and t are different. Each word consists only of lowercase English letters. Each word contains at most 100 letters.


-----Output-----

In the single line print the answer to the problem. Print "need tree" (without the quotes) if word s cannot be transformed into word t even with use of both suffix array and suffix automaton. Print "automaton" (without the quotes) if you need only the suffix automaton to solve the problem. Print "array" (without the quotes) if you need only the suffix array to solve the problem. Print "both" (without the quotes), if you need both data structures to solve the problem.

It's guaranteed that if you can solve the problem only with use of suffix array, then it is impossible to solve it only with use of suffix automaton. This is also true for suffix automaton.


-----Examples-----
Input
automaton
tomat

Output
automaton

Input
array
arary

Output
array

Input
both
hot

Output
both

Input
need
tree

Output
need tree



-----Note-----

In the third sample you can act like that: first transform "both" into "oth" by removing the first character using the suffix automaton and then make two swaps of the string using the suffix array and get "hot".
user: One day Alice was cleaning up her basement when she noticed something very curious: an infinite set of wooden pieces! Each piece was made of five square tiles, with four tiles adjacent to the fifth center tile:  [Image]  By the pieces lay a large square wooden board. The board is divided into $n^2$ cells arranged into $n$ rows and $n$ columns. Some of the cells are already occupied by single tiles stuck to it. The remaining cells are free.

Alice started wondering whether she could fill the board completely using the pieces she had found. Of course, each piece has to cover exactly five distinct cells of the board, no two pieces can overlap and every piece should fit in the board entirely, without some parts laying outside the board borders. The board however was too large for Alice to do the tiling by hand. Can you help determine if it's possible to fully tile the board?


-----Input-----

The first line of the input contains a single integer $n$ ($3 \leq n \leq 50$) — the size of the board.

The following $n$ lines describe the board. The $i$-th line ($1 \leq i \leq n$) contains a single string of length $n$. Its $j$-th character ($1 \leq j \leq n$) is equal to "." if the cell in the $i$-th row and the $j$-th column is free; it is equal to "#" if it's occupied.

You can assume that the board contains at least one free cell.


-----Output-----

Output YES if the board can be tiled by Alice's pieces, or NO otherwise. You can print each letter in any case (upper or lower).


-----Examples-----
Input
3
#.#
...
#.#

Output
YES

Input
4
##.#
#...
####
##.#

Output
NO

Input
5
#.###
....#
#....
###.#
#####

Output
YES

Input
5
#.###
....#
#....
....#
#..##

Output
NO



-----Note-----

The following sketches show the example boards and their tilings if such tilings exist:  [Image]
user: You have a nuts and lots of boxes. The boxes have a wonderful feature: if you put x (x ≥ 0) divisors (the spacial bars that can divide a box) to it, you get a box, divided into x + 1 sections.

You are minimalist. Therefore, on the one hand, you are against dividing some box into more than k sections. On the other hand, you are against putting more than v nuts into some section of the box. What is the minimum number of boxes you have to use if you want to put all the nuts in boxes, and you have b divisors?

Please note that you need to minimize the number of used boxes, not sections. You do not have to minimize the number of used divisors.


-----Input-----

The first line contains four space-separated integers k, a, b, v (2 ≤ k ≤ 1000; 1 ≤ a, b, v ≤ 1000) — the maximum number of sections in the box, the number of nuts, the number of divisors and the capacity of each section of the box.


-----Output-----

Print a single integer — the answer to the problem.


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

Output
2

Input
3 10 1 3

Output
3

Input
100 100 1 1000

Output
1



-----Note-----

In the first sample you can act like this:   Put two divisors to the first box. Now the first box has three sections and we can put three nuts into each section. Overall, the first box will have nine nuts.  Do not put any divisors into the second box. Thus, the second box has one section for the last nut. 

In the end we've put all the ten nuts into boxes.

The second sample is different as we have exactly one divisor and we put it to the first box. The next two boxes will have one section each.
user: Rock... Paper!

After Karen have found the deterministic winning (losing?) strategy for rock-paper-scissors, her brother, Koyomi, comes up with a new game as a substitute. The game works as follows.

A positive integer n is decided first. Both Koyomi and Karen independently choose n distinct positive integers, denoted by x_1, x_2, ..., x_{n} and y_1, y_2, ..., y_{n} respectively. They reveal their sequences, and repeat until all of 2n integers become distinct, which is the only final state to be kept and considered.

Then they count the number of ordered pairs (i, j) (1 ≤ i, j ≤ n) such that the value x_{i} xor y_{j} equals to one of the 2n integers. Here xor means the bitwise exclusive or operation on two integers, and is denoted by operators ^ and/or xor in most programming languages.

Karen claims a win if the number of such pairs is even, and Koyomi does otherwise. And you're here to help determine the winner of their latest game.


-----Input-----

The first line of input contains a positive integer n (1 ≤ n ≤ 2 000) — the length of both sequences.

The second line contains n space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 2·10^6) — the integers finally chosen by Koyomi.

The third line contains n space-separated integers y_1, y_2, ..., y_{n} (1 ≤ y_{i} ≤ 2·10^6) — the integers finally chosen by Karen.

Input guarantees that the given 2n integers are pairwise distinct, that is, no pair (i, j) (1 ≤ i, j ≤ n) exists such that one of the following holds: x_{i} = y_{j}; i ≠ j and x_{i} = x_{j}; i ≠ j and y_{i} = y_{j}.


-----Output-----

Output one line — the name of the winner, that is, "Koyomi" or "Karen" (without quotes). Please be aware of the capitalization.


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

Output
Karen

Input
5
2 4 6 8 10
9 7 5 3 1

Output
Karen



-----Note-----

In the first example, there are 6 pairs satisfying the constraint: (1, 1), (1, 2), (2, 1), (2, 3), (3, 2) and (3, 3). Thus, Karen wins since 6 is an even number.

In the second example, there are 16 such pairs, and Karen wins again.
user: Consider a linear function f(x) = Ax + B. Let's define g^{(0)}(x) = x and g^{(}n)(x) = f(g^{(}n - 1)(x)) for n > 0. For the given integer values A, B, n and x find the value of g^{(}n)(x) modulo 10^9 + 7.


-----Input-----

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 10^9, 1 ≤ n ≤ 10^18) — the parameters from the problem statement.

Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Output-----

Print the only integer s — the value g^{(}n)(x) modulo 10^9 + 7.


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

Output
7

Input
3 4 2 1

Output
25

Input
3 4 3 1

Output
79
user: Ivan is going to sleep now and wants to set his alarm clock. There will be many necessary events tomorrow, the $i$-th of them will start during the $x_i$-th minute. Ivan doesn't want to skip any of the events, so he has to set his alarm clock in such a way that it rings during minutes $x_1, x_2, \dots, x_n$, so he will be awake during each of these minutes (note that it does not matter if his alarm clock will ring during any other minute).

Ivan can choose two properties for the alarm clock — the first minute it will ring (let's denote it as $y$) and the interval between two consecutive signals (let's denote it by $p$). After the clock is set, it will ring during minutes $y, y + p, y + 2p, y + 3p$ and so on.

Ivan can choose any minute as the first one, but he cannot choose any arbitrary value of $p$. He has to pick it among the given values $p_1, p_2, \dots, p_m$ (his phone does not support any other options for this setting).

So Ivan has to choose the first minute $y$ when the alarm clock should start ringing and the interval between two consecutive signals $p_j$ in such a way that it will ring during all given minutes $x_1, x_2, \dots, x_n$ (and it does not matter if his alarm clock will ring in any other minutes).

Your task is to tell the first minute $y$ and the index $j$ such that if Ivan sets his alarm clock with properties $y$ and $p_j$ it will ring during all given minutes $x_1, x_2, \dots, x_n$ or say that it is impossible to choose such values of the given properties. If there are multiple answers, you can print any.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5, 1 \le m \le 3 \cdot 10^5$) — the number of events and the number of possible settings for the interval between signals.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^{18}$), where $x_i$ is the minute when $i$-th event starts. It is guaranteed that all $x_i$ are given in increasing order (i. e. the condition $x_1 < x_2 < \dots < x_n$ holds).

The third line of the input contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_j \le 10^{18}$), where $p_j$ is the $j$-th option for the interval between two consecutive signals.


-----Output-----

If it's impossible to choose such values $y$ and $j$ so all constraints are satisfied, print "NO" in the first line.

Otherwise print "YES" in the first line. Then print two integers $y$ ($1 \le y \le 10^{18}$) and $j$ ($1 \le j \le m$) in the second line, where $y$ is the first minute Ivan's alarm clock should start ringing and $j$ is the index of the option for the interval between two consecutive signals (options are numbered from $1$ to $m$ in the order they are given input). These values should be chosen in such a way that the alarm clock will ring during all given minutes $x_1, x_2, \dots, x_n$. If there are multiple answers, you can print any.


-----Examples-----
Input
3 5
3 12 18
2 6 5 3 3

Output
YES
3 4

Input
4 2
1 5 17 19
4 5

Output
NO

Input
4 2
1 5 17 19
2 1

Output
YES
1 1