meetforever/GRPO_CL huggingface dataset:
user: Berland annual chess tournament is coming!

Organizers have gathered 2·n chess players who should be divided into two teams with n people each. The first team is sponsored by BerOil and the second team is sponsored by BerMobile. Obviously, organizers should guarantee the win for the team of BerOil.

Thus, organizers should divide all 2·n players into two teams with n people each in such a way that the first team always wins.

Every chess player has its rating r_{i}. It is known that chess player with the greater rating always wins the player with the lower rating. If their ratings are equal then any of the players can win.

After teams assignment there will come a drawing to form n pairs of opponents: in each pair there is a player from the first team and a player from the second team. Every chess player should be in exactly one pair. Every pair plays once. The drawing is totally random.

Is it possible to divide all 2·n players into two teams with n people each so that the player from the first team in every pair wins regardless of the results of the drawing?


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100).

The second line contains 2·n integers a_1, a_2, ... a_2n (1 ≤ a_{i} ≤ 1000).


-----Output-----

If it's possible to divide all 2·n players into two teams with n people each so that the player from the first team in every pair wins regardless of the results of the drawing, then print "YES". Otherwise print "NO".


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

Output
YES

Input
1
3 3

Output
NO
user: You are given an array of n elements, you must make it a co-prime array in as few moves as possible.

In each move you can insert any positive integral number you want not greater than 10^9 in any place in the array.

An array is co-prime if any two adjacent numbers of it are co-prime.

In the number theory, two integers a and b are said to be co-prime if the only positive integer that divides both of them is 1.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of elements in the given array.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the elements of the array a.


-----Output-----

Print integer k on the first line — the least number of elements needed to add to the array a to make it co-prime.

The second line should contain n + k integers a_{j} — the elements of the array a after adding k elements to it. Note that the new array should be co-prime, so any two adjacent values should be co-prime. Also the new array should be got from the original array a by adding k elements to it.

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


-----Example-----
Input
3
2 7 28

Output
1
2 7 9 28
user: We have a sequence of N integers: A_1, A_2, \cdots, A_N.
You can perform the following operation between 0 and K times (inclusive):
 - Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.
Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

-----Constraints-----
 - 2 \leq N \leq 500
 - 1 \leq A_i \leq 10^6
 - 0 \leq K \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_{N-1} A_{N}

-----Output-----
Print the maximum possible positive integer that divides every element of A after the operations.

-----Sample Input-----
2 3
8 20

-----Sample Output-----
7

7 will divide every element of A if, for example, we perform the following operation:
 - Choose i = 2, j = 1. A becomes (7, 21).
We cannot reach the situation where 8 or greater integer divides every element of A.
user: Cat Furrier Transform is a popular algorithm among cat programmers to create longcats. As one of the greatest cat programmers ever exist, Neko wants to utilize this algorithm to create the perfect longcat.

Assume that we have a cat with a number $x$. A perfect longcat is a cat with a number equal $2^m - 1$ for some non-negative integer $m$. For example, the numbers $0$, $1$, $3$, $7$, $15$ and so on are suitable for the perfect longcats.

In the Cat Furrier Transform, the following operations can be performed on $x$:  (Operation A): you select any non-negative integer $n$ and replace $x$ with $x \oplus (2^n - 1)$, with $\oplus$ being a bitwise XOR operator. (Operation B): replace $x$ with $x + 1$. 

The first applied operation must be of type A, the second of type B, the third of type A again, and so on. Formally, if we number operations from one in the order they are executed, then odd-numbered operations must be of type A and the even-numbered operations must be of type B.

Neko wants to produce perfect longcats at industrial scale, thus for each cat Neko only wants to perform at most $40$ operations. Can you help Neko writing a transformation plan?

Note that it is not required to minimize the number of operations. You just need to use no more than $40$ operations.


-----Input-----

The only line contains a single integer $x$ ($1 \le x \le 10^6$).


-----Output-----

The first line should contain a single integer $t$ ($0 \le t \le 40$) — the number of operations to apply.

Then for each odd-numbered operation print the corresponding number $n_i$ in it. That is, print $\lceil \frac{t}{2} \rceil$ integers $n_i$ ($0 \le n_i \le 30$), denoting the replacement $x$ with $x \oplus (2^{n_i} - 1)$ in the corresponding step.

If there are multiple possible answers, you can print any of them. It is possible to show, that there is at least one answer in the constraints of this problem.


-----Examples-----
Input
39

Output
4
5 3 
Input
1

Output
0

Input
7

Output
0



-----Note-----

In the first test, one of the transforms might be as follows: $39 \to 56 \to 57 \to 62 \to 63$. Or more precisely: Pick $n = 5$. $x$ is transformed into $39 \oplus 31$, or $56$.  Increase $x$ by $1$, changing its value to $57$.  Pick $n = 3$. $x$ is transformed into $57 \oplus 7$, or $62$.  Increase $x$ by $1$, changing its value to $63 = 2^6 - 1$. 

In the second and third test, the number already satisfies the goal requirement.
user: Luba thinks about watering her garden. The garden can be represented as a segment of length k. Luba has got n buckets, the i-th bucket allows her to water some continuous subsegment of garden of length exactly a_{i} each hour. Luba can't water any parts of the garden that were already watered, also she can't water the ground outside the garden.

Luba has to choose one of the buckets in order to water the garden as fast as possible (as mentioned above, each hour she will water some continuous subsegment of length a_{i} if she chooses the i-th bucket). Help her to determine the minimum number of hours she has to spend watering the garden. It is guaranteed that Luba can always choose a bucket so it is possible water the garden.

See the examples for better understanding.


-----Input-----

The first line of input contains two integer numbers n and k (1 ≤ n, k ≤ 100) — the number of buckets and the length of the garden, respectively.

The second line of input contains n integer numbers a_{i} (1 ≤ a_{i} ≤ 100) — the length of the segment that can be watered by the i-th bucket in one hour.

It is guaranteed that there is at least one bucket such that it is possible to water the garden in integer number of hours using only this bucket.


-----Output-----

Print one integer number — the minimum number of hours required to water the garden.


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

Output
2

Input
6 7
1 2 3 4 5 6

Output
7



-----Note-----

In the first test the best option is to choose the bucket that allows to water the segment of length 3. We can't choose the bucket that allows to water the segment of length 5 because then we can't water the whole garden.

In the second test we can choose only the bucket that allows us to water the segment of length 1.
user: On the way to Rio de Janeiro Ostap kills time playing with a grasshopper he took with him in a special box. Ostap builds a line of length n such that some cells of this line are empty and some contain obstacles. Then, he places his grasshopper to one of the empty cells and a small insect in another empty cell. The grasshopper wants to eat the insect.

Ostap knows that grasshopper is able to jump to any empty cell that is exactly k cells away from the current (to the left or to the right). Note that it doesn't matter whether intermediate cells are empty or not as the grasshopper makes a jump over them. For example, if k = 1 the grasshopper can jump to a neighboring cell only, and if k = 2 the grasshopper can jump over a single cell.

Your goal is to determine whether there is a sequence of jumps such that grasshopper will get from his initial position to the cell with an insect.


-----Input-----

The first line of the input contains two integers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1) — the number of cells in the line and the length of one grasshopper's jump.

The second line contains a string of length n consisting of characters '.', '#', 'G' and 'T'. Character '.' means that the corresponding cell is empty, character '#' means that the corresponding cell contains an obstacle and grasshopper can't jump there. Character 'G' means that the grasshopper starts at this position and, finally, 'T' means that the target insect is located at this cell. It's guaranteed that characters 'G' and 'T' appear in this line exactly once.


-----Output-----

If there exists a sequence of jumps (each jump of length k), such that the grasshopper can get from his initial position to the cell with the insect, print "YES" (without quotes) in the only line of the input. Otherwise, print "NO" (without quotes).


-----Examples-----
Input
5 2
#G#T#

Output
YES

Input
6 1
T....G

Output
YES

Input
7 3
T..#..G

Output
NO

Input
6 2
..GT..

Output
NO



-----Note-----

In the first sample, the grasshopper can make one jump to the right in order to get from cell 2 to cell 4.

In the second sample, the grasshopper is only able to jump to neighboring cells but the way to the insect is free — he can get there by jumping left 5 times.

In the third sample, the grasshopper can't make a single jump.

In the fourth sample, the grasshopper can only jump to the cells with odd indices, thus he won't be able to reach the insect.
user: Vasiliy spent his vacation in a sanatorium, came back and found that he completely forgot details of his vacation! 

Every day there was a breakfast, a dinner and a supper in a dining room of the sanatorium (of course, in this order). The only thing that Vasiliy has now is a card from the dining room contaning notes how many times he had a breakfast, a dinner and a supper (thus, the card contains three integers). Vasiliy could sometimes have missed some meal, for example, he could have had a breakfast and a supper, but a dinner, or, probably, at some days he haven't been at the dining room at all.

Vasiliy doesn't remember what was the time of the day when he arrived to sanatorium (before breakfast, before dinner, before supper or after supper), and the time when he left it (before breakfast, before dinner, before supper or after supper). So he considers any of these options. After Vasiliy arrived to the sanatorium, he was there all the time until he left. Please note, that it's possible that Vasiliy left the sanatorium on the same day he arrived.

According to the notes in the card, help Vasiliy determine the minimum number of meals in the dining room that he could have missed. We shouldn't count as missed meals on the arrival day before Vasiliy's arrival and meals on the departure day after he left.


-----Input-----

The only line contains three integers b, d and s (0 ≤ b, d, s ≤ 10^18,  b + d + s ≥ 1) — the number of breakfasts, dinners and suppers which Vasiliy had during his vacation in the sanatorium. 


-----Output-----

Print single integer — the minimum possible number of meals which Vasiliy could have missed during his vacation. 


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

Output
1


Input
1 0 0

Output
0


Input
1 1 1

Output
0


Input
1000000000000000000 0 1000000000000000000

Output
999999999999999999





-----Note-----

In the first sample, Vasiliy could have missed one supper, for example, in case he have arrived before breakfast, have been in the sanatorium for two days (including the day of arrival) and then have left after breakfast on the third day. 

In the second sample, Vasiliy could have arrived before breakfast, have had it, and immediately have left the sanatorium, not missing any meal.

In the third sample, Vasiliy could have been in the sanatorium for one day, not missing any meal.
user: There is a matrix A of size x × y filled with integers. For every $i \in [ 1 . . x ]$, $j \in [ 1 . . y ]$ A_{i}, j = y(i - 1) + j. Obviously, every integer from [1..xy] occurs exactly once in this matrix. 

You have traversed some path in this matrix. Your path can be described as a sequence of visited cells a_1, a_2, ..., a_{n} denoting that you started in the cell containing the number a_1, then moved to the cell with the number a_2, and so on.

From the cell located in i-th line and j-th column (we denote this cell as (i, j)) you can move into one of the following cells: (i + 1, j) — only if i < x;  (i, j + 1) — only if j < y;  (i - 1, j) — only if i > 1;  (i, j - 1) — only if j > 1.

Notice that making a move requires you to go to an adjacent cell. It is not allowed to stay in the same cell. You don't know x and y exactly, but you have to find any possible values for these numbers such that you could start in the cell containing the integer a_1, then move to the cell containing a_2 (in one step), then move to the cell containing a_3 (also in one step) and so on. Can you choose x and y so that they don't contradict with your sequence of moves?


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 200000) — the number of cells you visited on your path (if some cell is visited twice, then it's listed twice).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the integers in the cells on your path.


-----Output-----

If all possible values of x and y such that 1 ≤ x, y ≤ 10^9 contradict with the information about your path, print NO.

Otherwise, print YES in the first line, and in the second line print the values x and y such that your path was possible with such number of lines and columns in the matrix. Remember that they must be positive integers not exceeding 10^9.


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

Output
YES
3 3

Input
6
1 2 1 2 5 3

Output
NO

Input
2
1 10

Output
YES
4 9



-----Note-----

The matrix and the path on it in the first test looks like this: [Image] 

Also there exist multiple correct answers for both the first and the third examples.
user: You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a subsequence of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.

Subsequence of string s is any such string that can be obtained by erasing zero or more characters (not necessarily consecutive) from string s.


-----Input-----

The first line contains string a, and the second line — string b. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 10^5 characters.


-----Output-----

On the first line output a subsequence of string a, obtained from b by erasing the minimum number of consecutive characters.

If the answer consists of zero characters, output «-» (a minus sign).


-----Examples-----
Input
hi
bob

Output
-

Input
abca
accepted

Output
ac

Input
abacaba
abcdcba

Output
abcba



-----Note-----

In the first example strings a and b don't share any symbols, so the longest string that you can get is empty.

In the second example ac is a subsequence of a, and at the same time you can obtain it by erasing consecutive symbols cepted from string b.
user: Vasya has a pile, that consists of some number of stones. $n$ times he either took one stone from the pile or added one stone to the pile. The pile was non-empty before each operation of taking one stone from the pile.

You are given $n$ operations which Vasya has made. Find the minimal possible number of stones that can be in the pile after making these operations.


-----Input-----

The first line contains one positive integer $n$ — the number of operations, that have been made by Vasya ($1 \leq n \leq 100$).

The next line contains the string $s$, consisting of $n$ symbols, equal to "-" (without quotes) or "+" (without quotes). If Vasya took the stone on $i$-th operation, $s_i$ is equal to "-" (without quotes), if added, $s_i$ is equal to "+" (without quotes).


-----Output-----

Print one integer — the minimal possible number of stones that can be in the pile after these $n$ operations.


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

Output
0
Input
4
++++

Output
4
Input
2
-+

Output
1
Input
5
++-++

Output
3


-----Note-----

In the first test, if Vasya had $3$ stones in the pile at the beginning, after making operations the number of stones will be equal to $0$. It is impossible to have less number of piles, so the answer is $0$. Please notice, that the number of stones at the beginning can't be less, than $3$, because in this case, Vasya won't be able to take a stone on some operation (the pile will be empty).

In the second test, if Vasya had $0$ stones in the pile at the beginning, after making operations the number of stones will be equal to $4$. It is impossible to have less number of piles because after making $4$ operations the number of stones in the pile increases on $4$ stones. So, the answer is $4$.

In the third test, if Vasya had $1$ stone in the pile at the beginning, after making operations the number of stones will be equal to $1$. It can be proved, that it is impossible to have less number of stones after making the operations.

In the fourth test, if Vasya had $0$ stones in the pile at the beginning, after making operations the number of stones will be equal to $3$.
user: Kolya Gerasimov loves kefir very much. He lives in year 1984 and knows all the details of buying this delicious drink. One day, as you probably know, he found himself in year 2084, and buying kefir there is much more complicated.

Kolya is hungry, so he went to the nearest milk shop. In 2084 you may buy kefir in a plastic liter bottle, that costs a rubles, or in glass liter bottle, that costs b rubles. Also, you may return empty glass bottle and get c (c < b) rubles back, but you cannot return plastic bottles.

Kolya has n rubles and he is really hungry, so he wants to drink as much kefir as possible. There were no plastic bottles in his 1984, so Kolya doesn't know how to act optimally and asks for your help.


-----Input-----

First line of the input contains a single integer n (1 ≤ n ≤ 10^18) — the number of rubles Kolya has at the beginning.

Then follow three lines containing integers a, b and c (1 ≤ a ≤ 10^18, 1 ≤ c < b ≤ 10^18) — the cost of one plastic liter bottle, the cost of one glass liter bottle and the money one can get back by returning an empty glass bottle, respectively.


-----Output-----

Print the only integer — maximum number of liters of kefir, that Kolya can drink.


-----Examples-----
Input
10
11
9
8

Output
2

Input
10
5
6
1

Output
2



-----Note-----

In the first sample, Kolya can buy one glass bottle, then return it and buy one more glass bottle. Thus he will drink 2 liters of kefir.

In the second sample, Kolya can buy two plastic bottle and get two liters of kefir, or he can buy one liter glass bottle, then return it and buy one plastic bottle. In both cases he will drink two liters of kefir.
user: Two bored soldiers are playing card war. Their card deck consists of exactly n cards, numbered from 1 to n, all values are different. They divide cards between them in some manner, it's possible that they have different number of cards. Then they play a "war"-like card game. 

The rules are following. On each turn a fight happens. Each of them picks card from the top of his stack and puts on the table. The one whose card value is bigger wins this fight and takes both cards from the table to the bottom of his stack. More precisely, he first takes his opponent's card and puts to the bottom of his stack, and then he puts his card to the bottom of his stack. If after some turn one of the player's stack becomes empty, he loses and the other one wins. 

You have to calculate how many fights will happen and who will win the game, or state that game won't end.


-----Input-----

First line contains a single integer n (2 ≤ n ≤ 10), the number of cards.

Second line contains integer k_1 (1 ≤ k_1 ≤ n - 1), the number of the first soldier's cards. Then follow k_1 integers that are the values on the first soldier's cards, from top to bottom of his stack.

Third line contains integer k_2 (k_1 + k_2 = n), the number of the second soldier's cards. Then follow k_2 integers that are the values on the second soldier's cards, from top to bottom of his stack.

All card values are different.


-----Output-----

If somebody wins in this game, print 2 integers where the first one stands for the number of fights before end of game and the second one is 1 or 2 showing which player has won.

If the game won't end and will continue forever output  - 1.


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

Output
6 2
Input
3
1 2
2 1 3

Output
-1


-----Note-----

First sample:  [Image] 

Second sample:  [Image]
user: You have probably registered on Internet sites many times. And each time you should enter your invented password. Usually the registration form automatically checks the password's crypt resistance. If the user's password isn't complex enough, a message is displayed. Today your task is to implement such an automatic check.

Web-developers of the company Q assume that a password is complex enough, if it meets all of the following conditions:  the password length is at least 5 characters;  the password contains at least one large English letter;  the password contains at least one small English letter;  the password contains at least one digit. 

You are given a password. Please implement the automatic check of its complexity for company Q.


-----Input-----

The first line contains a non-empty sequence of characters (at most 100 characters). Each character is either a large English letter, or a small English letter, or a digit, or one of characters: "!", "?", ".", ",", "_".


-----Output-----

If the password is complex enough, print message "Correct" (without the quotes), otherwise print message "Too weak" (without the quotes).


-----Examples-----
Input
abacaba

Output
Too weak

Input
X12345

Output
Too weak

Input
CONTEST_is_STARTED!!11

Output
Correct