meetforever/GRPO_CL huggingface dataset:
user: Bishwock is a chess figure that consists of three squares resembling an "L-bar". This figure can be rotated by 90, 180 and 270 degrees so it can have four possible states:

 

XX   XX   .X   X.

X.   .X   XX   XX

 

Bishwocks don't attack any squares and can even occupy on the adjacent squares as long as they don't occupy the same square. 

Vasya has a board with $2\times n$ squares onto which he wants to put some bishwocks. To his dismay, several squares on this board are already occupied by pawns and Vasya can't put bishwocks there. However, pawns also don't attack bishwocks and they can occupy adjacent squares peacefully.

Knowing the positions of pawns on the board, help Vasya to determine the maximum amount of bishwocks he can put onto the board so that they wouldn't occupy the same squares and wouldn't occupy squares with pawns.


-----Input-----

The input contains two nonempty strings that describe Vasya's board. Those strings contain only symbols "0" (zero) that denote the empty squares and symbols "X" (uppercase English letter) that denote the squares occupied by pawns. Strings are nonempty and are of the same length that does not exceed $100$.


-----Output-----

Output a single integer — the maximum amount of bishwocks that can be placed onto the given board.


-----Examples-----
Input
00
00

Output
1
Input
00X00X0XXX0
0XXX0X00X00

Output
4
Input
0X0X0
0X0X0

Output
0
Input
0XXX0
00000

Output
2
user: Polycarp loves lowercase letters and dislikes uppercase ones. Once he got a string s consisting only of lowercase and uppercase Latin letters.

Let A be a set of positions in the string. Let's call it pretty if following conditions are met:  letters on positions from A in the string are all distinct and lowercase;  there are no uppercase letters in the string which are situated between positions from A (i.e. there is no such j that s[j] is an uppercase letter, and a_1 < j < a_2 for some a_1 and a_2 from A). 

Write a program that will determine the maximum number of elements in a pretty set of positions.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 200) — length of string s.

The second line contains a string s consisting of lowercase and uppercase Latin letters.


-----Output-----

Print maximum number of elements in pretty set of positions for string s.


-----Examples-----
Input
11
aaaaBaabAbA

Output
2

Input
12
zACaAbbaazzC

Output
3

Input
3
ABC

Output
0



-----Note-----

In the first example the desired positions might be 6 and 8 or 7 and 8. Positions 6 and 7 contain letters 'a', position 8 contains letter 'b'. The pair of positions 1 and 8 is not suitable because there is an uppercase letter 'B' between these position.

In the second example desired positions can be 7, 8 and 11. There are other ways to choose pretty set consisting of three elements.

In the third example the given string s does not contain any lowercase letters, so the answer is 0.
user: You are given a sequence a consisting of n integers. You may partition this sequence into two sequences b and c in such a way that every element belongs exactly to one of these sequences. 

Let B be the sum of elements belonging to b, and C be the sum of elements belonging to c (if some of these sequences is empty, then its sum is 0). What is the maximum possible value of B - C?


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100) — the number of elements in a.

The second line contains n integers a_1, a_2, ..., a_{n} ( - 100 ≤ a_{i} ≤ 100) — the elements of sequence a.


-----Output-----

Print the maximum possible value of B - C, where B is the sum of elements of sequence b, and C is the sum of elements of sequence c.


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

Output
3

Input
6
16 23 16 15 42 8

Output
120



-----Note-----

In the first example we may choose b = {1, 0}, c = { - 2}. Then B = 1, C =  - 2, B - C = 3.

In the second example we choose b = {16, 23, 16, 15, 42, 8}, c = {} (an empty sequence). Then B = 120, C = 0, B - C = 120.
user: A bus moves along the coordinate line Ox from the point x = 0 to the point x = a. After starting from the point x = 0, it reaches the point x = a, immediately turns back and then moves to the point x = 0. After returning to the point x = 0 it immediately goes back to the point x = a and so on. Thus, the bus moves from x = 0 to x = a and back. Moving from the point x = 0 to x = a or from the point x = a to x = 0 is called a bus journey. In total, the bus must make k journeys.

The petrol tank of the bus can hold b liters of gasoline. To pass a single unit of distance the bus needs to spend exactly one liter of gasoline. The bus starts its first journey with a full petrol tank.

There is a gas station in point x = f. This point is between points x = 0 and x = a. There are no other gas stations on the bus route. While passing by a gas station in either direction the bus can stop and completely refuel its tank. Thus, after stopping to refuel the tank will contain b liters of gasoline.

What is the minimum number of times the bus needs to refuel at the point x = f to make k journeys? The first journey starts in the point x = 0.


-----Input-----

The first line contains four integers a, b, f, k (0 < f < a ≤ 10^6, 1 ≤ b ≤ 10^9, 1 ≤ k ≤ 10^4) — the endpoint of the first bus journey, the capacity of the fuel tank of the bus, the point where the gas station is located, and the required number of journeys.


-----Output-----

Print the minimum number of times the bus needs to refuel to make k journeys. If it is impossible for the bus to make k journeys, print -1.


-----Examples-----
Input
6 9 2 4

Output
4

Input
6 10 2 4

Output
2

Input
6 5 4 3

Output
-1



-----Note-----

In the first example the bus needs to refuel during each journey.

In the second example the bus can pass 10 units of distance without refueling. So the bus makes the whole first journey, passes 4 units of the distance of the second journey and arrives at the point with the gas station. Then it can refuel its tank, finish the second journey and pass 2 units of distance from the third journey. In this case, it will again arrive at the point with the gas station. Further, he can refill the tank up to 10 liters to finish the third journey and ride all the way of the fourth journey. At the end of the journey the tank will be empty. 

In the third example the bus can not make all 3 journeys because if it refuels during the second journey, the tanks will contain only 5 liters of gasoline, but the bus needs to pass 8 units of distance until next refueling.
user: You are given the string s of length n and the numbers p, q. Split the string s to pieces of length p and q.

For example, the string "Hello" for p = 2, q = 3 can be split to the two strings "Hel" and "lo" or to the two strings "He" and "llo".

Note it is allowed to split the string s to the strings only of length p or to the strings only of length q (see the second sample test).


-----Input-----

The first line contains three positive integers n, p, q (1 ≤ p, q ≤ n ≤ 100).

The second line contains the string s consists of lowercase and uppercase latin letters and digits.


-----Output-----

If it's impossible to split the string s to the strings of length p and q print the only number "-1".

Otherwise in the first line print integer k — the number of strings in partition of s.

Each of the next k lines should contain the strings in partition. Each string should be of the length p or q. The string should be in order of their appearing in string s — from left to right.

If there are several solutions print any of them.


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

Output
2
He
llo

Input
10 9 5
Codeforces

Output
2
Codef
orces

Input
6 4 5
Privet

Output
-1

Input
8 1 1
abacabac

Output
8
a
b
a
c
a
b
a
c
user: A sportsman starts from point x_{start} = 0 and runs to point with coordinate x_{finish} = m (on a straight line). Also, the sportsman can jump — to jump, he should first take a run of length of not less than s meters (in this case for these s meters his path should have no obstacles), and after that he can jump over a length of not more than d meters. Running and jumping is permitted only in the direction from left to right. He can start andfinish a jump only at the points with integer coordinates in which there are no obstacles. To overcome some obstacle, it is necessary to land at a point which is strictly to the right of this obstacle.

On the way of an athlete are n obstacles at coordinates x_1, x_2, ..., x_{n}. He cannot go over the obstacles, he can only jump over them. Your task is to determine whether the athlete will be able to get to the finish point.


-----Input-----

The first line of the input containsd four integers n, m, s and d (1 ≤ n ≤ 200 000, 2 ≤ m ≤ 10^9, 1 ≤ s, d ≤ 10^9) — the number of obstacles on the runner's way, the coordinate of the finishing point, the length of running before the jump and the maximum length of the jump, correspondingly.

The second line contains a sequence of n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ m - 1) — the coordinates of the obstacles. It is guaranteed that the starting and finishing point have no obstacles, also no point can have more than one obstacle, The coordinates of the obstacles are given in an arbitrary order.


-----Output-----

If the runner cannot reach the finishing point, print in the first line of the output "IMPOSSIBLE" (without the quotes).

If the athlete can get from start to finish, print any way to do this in the following format:  print a line of form "RUN X>" (where "X" should be a positive integer), if the athlete should run for "X" more meters;  print a line of form "JUMP Y" (where "Y" should be a positive integer), if the sportsman starts a jump and should remain in air for "Y" more meters. 

All commands "RUN" and "JUMP" should strictly alternate, starting with "RUN", besides, they should be printed chronologically. It is not allowed to jump over the finishing point but it is allowed to land there after a jump. The athlete should stop as soon as he reaches finish.


-----Examples-----
Input
3 10 1 3
3 4 7

Output
RUN 2
JUMP 3
RUN 1
JUMP 2
RUN 2

Input
2 9 2 3
6 4

Output
IMPOSSIBLE
user: Two positive integers a and b have a sum of s and a bitwise XOR of x. How many possible values are there for the ordered pair (a, b)?


-----Input-----

The first line of the input contains two integers s and x (2 ≤ s ≤ 10^12, 0 ≤ x ≤ 10^12), the sum and bitwise xor of the pair of positive integers, respectively.


-----Output-----

Print a single integer, the number of solutions to the given conditions. If no solutions exist, print 0.


-----Examples-----
Input
9 5

Output
4

Input
3 3

Output
2

Input
5 2

Output
0



-----Note-----

In the first sample, we have the following solutions: (2, 7), (3, 6), (6, 3), (7, 2).

In the second sample, the only solutions are (1, 2) and (2, 1).
user: Long story short, shashlik is Miroslav's favorite food. Shashlik is prepared on several skewers simultaneously. There are two states for each skewer: initial and turned over.

This time Miroslav laid out $n$ skewers parallel to each other, and enumerated them with consecutive integers from $1$ to $n$ in order from left to right. For better cooking, he puts them quite close to each other, so when he turns skewer number $i$, it leads to turning $k$ closest skewers from each side of the skewer $i$, that is, skewers number $i - k$, $i - k + 1$, ..., $i - 1$, $i + 1$, ..., $i + k - 1$, $i + k$ (if they exist). 

For example, let $n = 6$ and $k = 1$. When Miroslav turns skewer number $3$, then skewers with numbers $2$, $3$, and $4$ will come up turned over. If after that he turns skewer number $1$, then skewers number $1$, $3$, and $4$ will be turned over, while skewer number $2$ will be in the initial position (because it is turned again).

As we said before, the art of cooking requires perfect timing, so Miroslav wants to turn over all $n$ skewers with the minimal possible number of actions. For example, for the above example $n = 6$ and $k = 1$, two turnings are sufficient: he can turn over skewers number $2$ and $5$.

Help Miroslav turn over all $n$ skewers.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 1000$, $0 \leq k \leq 1000$) — the number of skewers and the number of skewers from each side that are turned in one step.


-----Output-----

The first line should contain integer $l$ — the minimum number of actions needed by Miroslav to turn over all $n$ skewers. After than print $l$ integers from $1$ to $n$ denoting the number of the skewer that is to be turned over at the corresponding step.


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

Output
2
1 6 

Input
5 1

Output
2
1 4 



-----Note-----

In the first example the first operation turns over skewers $1$, $2$ and $3$, the second operation turns over skewers $4$, $5$, $6$ and $7$.

In the second example it is also correct to turn over skewers $2$ and $5$, but turning skewers $2$ and $4$, or $1$ and $5$ are incorrect solutions because the skewer $3$ is in the initial state after these operations.
user: You are given a positive integer $n$, written without leading zeroes (for example, the number 04 is incorrect). 

In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.

Determine the minimum number of operations that you need to consistently apply to the given integer $n$ to make from it the square of some positive integer or report that it is impossible.

An integer $x$ is the square of some positive integer if and only if $x=y^2$ for some positive integer $y$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{9}$). The number is given without leading zeroes.


-----Output-----

If it is impossible to make the square of some positive integer from $n$, print -1. In the other case, print the minimal number of operations required to do it.


-----Examples-----
Input
8314

Output
2

Input
625

Output
0

Input
333

Output
-1



-----Note-----

In the first example we should delete from $8314$ the digits $3$ and $4$. After that $8314$ become equals to $81$, which is the square of the integer $9$.

In the second example the given $625$ is the square of the integer $25$, so you should not delete anything. 

In the third example it is impossible to make the square from $333$, so the answer is -1.
user: Let's define a function $f(p)$ on a permutation $p$ as follows. Let $g_i$ be the greatest common divisor (GCD) of elements $p_1$, $p_2$, ..., $p_i$ (in other words, it is the GCD of the prefix of length $i$). Then $f(p)$ is the number of distinct elements among $g_1$, $g_2$, ..., $g_n$.

Let $f_{max}(n)$ be the maximum value of $f(p)$ among all permutations $p$ of integers $1$, $2$, ..., $n$.

Given an integers $n$, count the number of permutations $p$ of integers $1$, $2$, ..., $n$, such that $f(p)$ is equal to $f_{max}(n)$. Since the answer may be large, print the remainder of its division by $1000\,000\,007 = 10^9 + 7$.


-----Input-----

The only line contains the integer $n$ ($2 \le n \le 10^6$) — the length of the permutations.


-----Output-----

The only line should contain your answer modulo $10^9+7$.


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

Output
1
Input
3

Output
4
Input
6

Output
120


-----Note-----

Consider the second example: these are the permutations of length $3$:  $[1,2,3]$, $f(p)=1$.  $[1,3,2]$, $f(p)=1$.  $[2,1,3]$, $f(p)=2$.  $[2,3,1]$, $f(p)=2$.  $[3,1,2]$, $f(p)=2$.  $[3,2,1]$, $f(p)=2$. 

The maximum value $f_{max}(3) = 2$, and there are $4$ permutations $p$ such that $f(p)=2$.
user: One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum jump ability he should have in order to be able to reach the far end of the string, jumping only on vowels of the English alphabet. Jump ability is the maximum possible length of his jump. 

Formally, consider that at the begginning the Grasshopper is located directly in front of the leftmost character of the string. His goal is to reach the position right after the rightmost character of the string. In one jump the Grasshopper could jump to the right any distance from 1 to the value of his jump ability. [Image] The picture corresponds to the first example. 

The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'.


-----Input-----

The first line contains non-empty string consisting of capital English letters. It is guaranteed that the length of the string does not exceed 100. 


-----Output-----

Print single integer a — the minimum jump ability of the Grasshopper (in the number of symbols) that is needed to overcome the given string, jumping only on vowels.


-----Examples-----
Input
ABABBBACFEYUKOTT

Output
4
Input
AAA

Output
1
user: Dawid has four bags of candies. The $i$-th of them contains $a_i$ candies. Also, Dawid has two friends. He wants to give each bag to one of his two friends. Is it possible to distribute the bags in such a way that each friend receives the same amount of candies in total?

Note, that you can't keep bags for yourself or throw them away, each bag should be given to one of the friends.


-----Input-----

The only line contains four integers $a_1$, $a_2$, $a_3$ and $a_4$ ($1 \leq a_i \leq 100$) — the numbers of candies in each bag.


-----Output-----

Output YES if it's possible to give the bags to Dawid's friends so that both friends receive the same amount of candies, or NO otherwise. Each character can be printed in any case (either uppercase or lowercase).


-----Examples-----
Input
1 7 11 5

Output
YES

Input
7 3 2 5

Output
NO



-----Note-----

In the first sample test, Dawid can give the first and the third bag to the first friend, and the second and the fourth bag to the second friend. This way, each friend will receive $12$ candies.

In the second sample test, it's impossible to distribute the bags.
user: You may have heard of the pie rule before. It states that if two people wish to fairly share a slice of pie, one person should cut the slice in half, and the other person should choose who gets which slice. Alice and Bob have many slices of pie, and rather than cutting the slices in half, each individual slice will be eaten by just one person.

The way Alice and Bob decide who eats each slice is as follows. First, the order in which the pies are to be handed out is decided. There is a special token called the "decider" token, initially held by Bob. Until all the pie is handed out, whoever has the decider token will give the next slice of pie to one of the participants, and the decider token to the other participant. They continue until no slices of pie are left.

All of the slices are of excellent quality, so each participant obviously wants to maximize the total amount of pie they get to eat. Assuming both players make their decisions optimally, how much pie will each participant receive?


-----Input-----

Input will begin with an integer N (1 ≤ N ≤ 50), the number of slices of pie. 

Following this is a line with N integers indicating the sizes of the slices (each between 1 and 100000, inclusive), in the order in which they must be handed out.


-----Output-----

Print two integers. First, the sum of the sizes of slices eaten by Alice, then the sum of the sizes of the slices eaten by Bob, assuming both players make their decisions optimally.


-----Examples-----
Input
3
141 592 653

Output
653 733

Input
5
10 21 10 21 10

Output
31 41



-----Note-----

In the first example, Bob takes the size 141 slice for himself and gives the decider token to Alice. Then Alice gives the size 592 slice to Bob and keeps the decider token for herself, so that she can then give the size 653 slice to herself.
user: You've got a positive integer sequence a_1, a_2, ..., a_{n}. All numbers in the sequence are distinct. Let's fix the set of variables b_1, b_2, ..., b_{m}. Initially each variable b_{i} (1 ≤ i ≤ m) contains the value of zero. Consider the following sequence, consisting of n operations.

The first operation is assigning the value of a_1 to some variable b_{x} (1 ≤ x ≤ m). Each of the following n - 1 operations is assigning to some variable b_{y} the value that is equal to the sum of values that are stored in the variables b_{i} and b_{j} (1 ≤ i, j, y ≤ m). At that, the value that is assigned on the t-th operation, must equal a_{t}. For each operation numbers y, i, j are chosen anew.

Your task is to find the minimum number of variables m, such that those variables can help you perform the described sequence of operations.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 23). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{k} ≤ 10^9).

It is guaranteed that all numbers in the sequence are distinct.


-----Output-----

In a single line print a single number — the minimum number of variables m, such that those variables can help you perform the described sequence of operations.

If you cannot perform the sequence of operations at any m, print -1.


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

Output
2

Input
3
3 6 5

Output
-1

Input
6
2 4 8 6 10 18

Output
3



-----Note-----

In the first sample, you can use two variables b_1 and b_2 to perform the following sequence of operations.  b_1 := 1;  b_2 := b_1 + b_1;  b_1 := b_1 + b_2;  b_1 := b_1 + b_1;  b_1 := b_1 + b_2.
user: Alice and Bob are playing a game with $n$ piles of stones. It is guaranteed that $n$ is an even number. The $i$-th pile has $a_i$ stones.

Alice and Bob will play a game alternating turns with Alice going first.

On a player's turn, they must choose exactly $\frac{n}{2}$ nonempty piles and independently remove a positive number of stones from each of the chosen piles. They can remove a different number of stones from the piles in a single turn. The first player unable to make a move loses (when there are less than $\frac{n}{2}$ nonempty piles).

Given the starting configuration, determine who will win the game.


-----Input-----

The first line contains one integer $n$ ($2 \leq n \leq 50$) — the number of piles. It is guaranteed that $n$ is an even number.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 50$) — the number of stones in the piles.


-----Output-----

Print a single string "Alice" if Alice wins; otherwise, print "Bob" (without double quotes).


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

Output
Bob

Input
4
3 1 4 1

Output
Alice



-----Note-----

In the first example, each player can only remove stones from one pile ($\frac{2}{2}=1$). Alice loses, since Bob can copy whatever Alice does on the other pile, so Alice will run out of moves first.

In the second example, Alice can remove $2$ stones from the first pile and $3$ stones from the third pile on her first move to guarantee a win.
user: Today, hedgehog Filya went to school for the very first time! Teacher gave him a homework which Filya was unable to complete without your help.

Filya is given an array of non-negative integers a_1, a_2, ..., a_{n}. First, he pick an integer x and then he adds x to some elements of the array (no more than once), subtract x from some other elements (also, no more than once) and do no change other elements. He wants all elements of the array to be equal.

Now he wonders if it's possible to pick such integer x and change some elements of the array using this x in order to make all elements equal.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the number of integers in the Filya's array. The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — elements of the array.


-----Output-----

If it's impossible to make all elements of the array equal using the process given in the problem statement, then print "NO" (without quotes) in the only line of the output. Otherwise print "YES" (without quotes).


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

Output
YES

Input
5
1 2 3 4 5

Output
NO



-----Note-----

In the first sample Filya should select x = 1, then add it to the first and the last elements of the array and subtract from the second and the third elements.