meetforever/GRPO_CL huggingface dataset:
user: When registering in a social network, users are allowed to create their own convenient login to make it easier to share contacts, print it on business cards, etc.

Login is an arbitrary sequence of lower and uppercase latin letters, digits and underline symbols («_»). However, in order to decrease the number of frauds and user-inattention related issues, it is prohibited to register a login if it is similar with an already existing login. More precisely, two logins s and t are considered similar if we can transform s to t via a sequence of operations of the following types:   transform lowercase letters to uppercase and vice versa;  change letter «O» (uppercase latin letter) to digit «0» and vice versa;  change digit «1» (one) to any letter among «l» (lowercase latin «L»), «I» (uppercase latin «i») and vice versa, or change one of these letters to other. 

For example, logins «Codeforces» and «codef0rces» as well as «OO0OOO00O0OOO0O00OOO0OO_lol» and «OO0OOO0O00OOO0O00OO0OOO_1oI» are considered similar whereas «Codeforces» and «Code_forces» are not.

You're given a list of existing logins with no two similar amonst and a newly created user login. Check whether this new login is similar with any of the existing ones.


-----Input-----

The first line contains a non-empty string s consisting of lower and uppercase latin letters, digits and underline symbols («_») with length not exceeding 50  — the login itself.

The second line contains a single integer n (1 ≤ n ≤ 1 000) — the number of existing logins.

The next n lines describe the existing logins, following the same constraints as the user login (refer to the first line of the input). It's guaranteed that no two existing logins are similar.


-----Output-----

Print «Yes» (without quotes), if user can register via this login, i.e. none of the existing logins is similar with it.

Otherwise print «No» (without quotes).


-----Examples-----
Input
1_wat
2
2_wat
wat_1

Output
Yes

Input
000
3
00
ooA
oOo

Output
No

Input
_i_
3
__i_
_1_
I

Output
No

Input
La0
3
2a0
La1
1a0

Output
No

Input
abc
1
aBc

Output
No

Input
0Lil
2
LIL0
0Ril

Output
Yes



-----Note-----

In the second sample case the user wants to create a login consisting of three zeros. It's impossible due to collision with the third among the existing.

In the third sample case the new login is similar with the second one.
user: Connect the countless points with lines, till we reach the faraway yonder.

There are n points on a coordinate plane, the i-th of which being (i, y_{i}).

Determine whether it's possible to draw two parallel and non-overlapping lines, such that every point in the set lies on exactly one of them, and each of them passes through at least one point in the set.


-----Input-----

The first line of input contains a positive integer n (3 ≤ n ≤ 1 000) — the number of points.

The second line contains n space-separated integers y_1, y_2, ..., y_{n} ( - 10^9 ≤ y_{i} ≤ 10^9) — the vertical coordinates of each point.


-----Output-----

Output "Yes" (without quotes) if it's possible to fulfill the requirements, and "No" otherwise.

You can print each letter in any case (upper or lower).


-----Examples-----
Input
5
7 5 8 6 9

Output
Yes

Input
5
-1 -2 0 0 -5

Output
No

Input
5
5 4 3 2 1

Output
No

Input
5
1000000000 0 0 0 0

Output
Yes



-----Note-----

In the first example, there are five points: (1, 7), (2, 5), (3, 8), (4, 6) and (5, 9). It's possible to draw a line that passes through points 1, 3, 5, and another one that passes through points 2, 4 and is parallel to the first one.

In the second example, while it's possible to draw two lines that cover all points, they cannot be made parallel.

In the third example, it's impossible to satisfy both requirements at the same time.
user: Vasya had three strings $a$, $b$ and $s$, which consist of lowercase English letters. The lengths of strings $a$ and $b$ are equal to $n$, the length of the string $s$ is equal to $m$. 

Vasya decided to choose a substring of the string $a$, then choose a substring of the string $b$ and concatenate them. Formally, he chooses a segment $[l_1, r_1]$ ($1 \leq l_1 \leq r_1 \leq n$) and a segment $[l_2, r_2]$ ($1 \leq l_2 \leq r_2 \leq n$), and after concatenation he obtains a string $a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}$.

Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions:

  segments $[l_1, r_1]$ and $[l_2, r_2]$ have non-empty intersection, i.e. there exists at least one integer $x$, such that $l_1 \leq x \leq r_1$ and $l_2 \leq x \leq r_2$;  the string $a[l_1, r_1] + b[l_2, r_2]$ is equal to the string $s$. 


-----Input-----

The first line contains integers $n$ and $m$ ($1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n$) — the length of strings $a$ and $b$ and the length of the string $s$.

The next three lines contain strings $a$, $b$ and $s$, respectively. The length of the strings $a$ and $b$ is $n$, while the length of the string $s$ is $m$.

All strings consist of lowercase English letters.


-----Output-----

Print one integer — the number of ways to choose a pair of segments, which satisfy Vasya's conditions.


-----Examples-----
Input
6 5
aabbaa
baaaab
aaaaa

Output
4

Input
5 4
azaza
zazaz
azaz

Output
11

Input
9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz

Output
2



-----Note-----

Let's list all the pairs of segments that Vasya could choose in the first example:

  $[2, 2]$ and $[2, 5]$;  $[1, 2]$ and $[2, 4]$;  $[5, 5]$ and $[2, 5]$;  $[5, 6]$ and $[3, 5]$;
user: During a New Year special offer the "Sudislavl Bars" offered n promo codes. Each promo code consists of exactly six digits and gives right to one free cocktail at the bar "Mosquito Shelter". Of course, all the promocodes differ.

As the "Mosquito Shelter" opens only at 9, and partying in Sudislavl usually begins at as early as 6, many problems may arise as to how to type a promotional code without errors. It is necessary to calculate such maximum k, that the promotional code could be uniquely identified if it was typed with no more than k errors. At that, k = 0 means that the promotional codes must be entered exactly.

A mistake in this problem should be considered as entering the wrong numbers. For example, value "123465" contains two errors relative to promocode "123456". Regardless of the number of errors the entered value consists of exactly six digits.


-----Input-----

The first line of the output contains number n (1 ≤ n ≤ 1000) — the number of promocodes.

Each of the next n lines contains a single promocode, consisting of exactly 6 digits. It is guaranteed that all the promocodes are distinct. Promocodes can start from digit "0".


-----Output-----

Print the maximum k (naturally, not exceeding the length of the promocode), such that any promocode can be uniquely identified if it is typed with at most k mistakes.


-----Examples-----
Input
2
000000
999999

Output
2

Input
6
211111
212111
222111
111111
112111
121111

Output
0



-----Note-----

In the first sample k < 3, so if a bar customer types in value "090909", then it will be impossible to define which promocode exactly corresponds to it.
user: Little Alyona is celebrating Happy Birthday! Her mother has an array of n flowers. Each flower has some mood, the mood of i-th flower is a_{i}. The mood can be positive, zero or negative.

Let's define a subarray as a segment of consecutive flowers. The mother suggested some set of subarrays. Alyona wants to choose several of the subarrays suggested by her mother. After that, each of the flowers will add to the girl's happiness its mood multiplied by the number of chosen subarrays the flower is in.

For example, consider the case when the mother has 5 flowers, and their moods are equal to 1,  - 2, 1, 3,  - 4. Suppose the mother suggested subarrays (1,  - 2), (3,  - 4), (1, 3), (1,  - 2, 1, 3). Then if the girl chooses the third and the fourth subarrays then:   the first flower adds 1·1 = 1 to the girl's happiness, because he is in one of chosen subarrays,  the second flower adds ( - 2)·1 =  - 2, because he is in one of chosen subarrays,  the third flower adds 1·2 = 2, because he is in two of chosen subarrays,  the fourth flower adds 3·2 = 6, because he is in two of chosen subarrays,  the fifth flower adds ( - 4)·0 = 0, because he is in no chosen subarrays. 

Thus, in total 1 + ( - 2) + 2 + 6 + 0 = 7 is added to the girl's happiness. Alyona wants to choose such subarrays from those suggested by the mother that the value added to her happiness would be as large as possible. Help her do this!

Alyona can choose any number of the subarrays, even 0 or all suggested by her mother.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of flowers and the number of subarrays suggested by the mother.

The second line contains the flowers moods — n integers a_1, a_2, ..., a_{n} ( - 100 ≤ a_{i} ≤ 100).

The next m lines contain the description of the subarrays suggested by the mother. The i-th of these lines contain two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) denoting the subarray a[l_{i}], a[l_{i} + 1], ..., a[r_{i}].

Each subarray can encounter more than once.


-----Output-----

Print single integer — the maximum possible value added to the Alyona's happiness.


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

Output
7

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

Output
16

Input
2 2
-1 -2
1 1
1 2

Output
0



-----Note-----

The first example is the situation described in the statements.

In the second example Alyona should choose all subarrays.

The third example has answer 0 because Alyona can choose none of the subarrays.
user: Luke Skywalker gave Chewbacca an integer number x. Chewbacca isn't good at numbers but he loves inverting digits in them. Inverting digit t means replacing it with digit 9 - t. 

Help Chewbacca to transform the initial number x to the minimum possible positive number by inverting some (possibly, zero) digits. The decimal representation of the final number shouldn't start with a zero.


-----Input-----

The first line contains a single integer x (1 ≤ x ≤ 10^18) — the number that Luke Skywalker gave to Chewbacca.


-----Output-----

Print the minimum possible positive number that Chewbacca can obtain after inverting some digits. The number shouldn't contain leading zeroes.


-----Examples-----
Input
27

Output
22

Input
4545

Output
4444
user: Programmer Rostislav got seriously interested in the Link/Cut Tree data structure, which is based on Splay trees. Specifically, he is now studying the expose procedure.

Unfortunately, Rostislav is unable to understand the definition of this procedure, so he decided to ask programmer Serezha to help him. Serezha agreed to help if Rostislav solves a simple task (and if he doesn't, then why would he need Splay trees anyway?)

Given integers l, r and k, you need to print all powers of number k within range from l to r inclusive. However, Rostislav doesn't want to spent time doing this, as he got interested in playing a network game called Agar with Gleb. Help him!


-----Input-----

The first line of the input contains three space-separated integers l, r and k (1 ≤ l ≤ r ≤ 10^18, 2 ≤ k ≤ 10^9).


-----Output-----

Print all powers of number k, that lie within range from l to r in the increasing order. If there are no such numbers, print "-1" (without the quotes).


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

Output
1 2 4 8 
Input
2 4 5

Output
-1


-----Note-----

Note to the first sample: numbers 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8 lie within the specified range. The number 2^4 = 16 is greater then 10, thus it shouldn't be printed.
user: Pig is visiting a friend.

Pig's house is located at point 0, and his friend's house is located at point m on an axis.

Pig can use teleports to move along the axis.

To use a teleport, Pig should come to a certain point (where the teleport is located) and choose where to move: for each teleport there is the rightmost point it can move Pig to, this point is known as the limit of the teleport.

Formally, a teleport located at point x with limit y can move Pig from point x to any point within the segment [x; y], including the bounds. [Image] 

Determine if Pig can visit the friend using teleports only, or he should use his car.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of teleports and the location of the friend's house.

The next n lines contain information about teleports.

The i-th of these lines contains two integers a_{i} and b_{i} (0 ≤ a_{i} ≤ b_{i} ≤ m), where a_{i} is the location of the i-th teleport, and b_{i} is its limit.

It is guaranteed that a_{i} ≥ a_{i} - 1 for every i (2 ≤ i ≤ n).


-----Output-----

Print "YES" if there is a path from Pig's house to his friend's house that uses only teleports, and "NO" otherwise.

You can print each letter in arbitrary case (upper or lower).


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

Output
YES

Input
3 7
0 4
2 5
6 7

Output
NO



-----Note-----

The first example is shown on the picture below: [Image] 

Pig can use the first teleport from his house (point 0) to reach point 2, then using the second teleport go from point 2 to point 3, then using the third teleport go from point 3 to point 5, where his friend lives.

The second example is shown on the picture below: [Image] 

You can see that there is no path from Pig's house to his friend's house that uses only teleports.
user: There are N blocks arranged in a row. Let us paint these blocks.
We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.
Find the number of ways to paint the blocks under the following conditions:
 - For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.
 - There may be at most K pairs of adjacent blocks that are painted in the same color.
Since the count may be enormous, print it modulo 998244353.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N, M \leq 2 \times 10^5
 - 0 \leq K \leq N - 1

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

-----Output-----
Print the answer.

-----Sample Input-----
3 2 1

-----Sample Output-----
6

The following ways to paint the blocks satisfy the conditions: 112, 121, 122, 211, 212, and 221. Here, digits represent the colors of the blocks.
user: Given are a prime number p and a sequence of p integers a_0, \ldots, a_{p-1} consisting of zeros and ones.
Find a polynomial of degree at most p-1, f(x) = b_{p-1} x^{p-1} + b_{p-2} x^{p-2} + \ldots + b_0, satisfying the following conditions:
 - For each i (0 \leq i \leq p-1), b_i is an integer such that 0 \leq b_i \leq p-1.
 - For each i (0 \leq i \leq p-1), f(i) \equiv a_i \pmod p.

-----Constraints-----
 - 2 \leq p \leq 2999
 - p is a prime number.
 - 0 \leq a_i \leq 1

-----Input-----
Input is given from Standard Input in the following format:
p
a_0 a_1 \ldots a_{p-1}

-----Output-----
Print b_0, b_1, \ldots, b_{p-1} of a polynomial f(x) satisfying the conditions, in this order, with spaces in between.
It can be proved that a solution always exists. If multiple solutions exist, any of them will be accepted.

-----Sample Input-----
2
1 0

-----Sample Output-----
1 1

f(x) = x + 1 satisfies the conditions, as follows:
 - f(0) = 0 + 1 = 1 \equiv 1 \pmod 2
 - f(1) = 1 + 1 = 2 \equiv 0 \pmod 2
user: You are given a rectangular cake, represented as an r × c grid. Each cell either has an evil strawberry, or is empty. For example, a 3 × 4 cake may look as follows: [Image] 

The cakeminator is going to eat the cake! Each time he eats, he chooses a row or a column that does not contain any evil strawberries and contains at least one cake cell that has not been eaten before, and eats all the cake cells there. He may decide to eat any number of times.

Please output the maximum number of cake cells that the cakeminator can eat.


-----Input-----

The first line contains two integers r and c (2 ≤ r, c ≤ 10), denoting the number of rows and the number of columns of the cake. The next r lines each contains c characters — the j-th character of the i-th line denotes the content of the cell at row i and column j, and is either one of these:   '.' character denotes a cake cell with no evil strawberry;  'S' character denotes a cake cell with an evil strawberry. 


-----Output-----

Output the maximum number of cake cells that the cakeminator can eat.


-----Examples-----
Input
3 4
S...
....
..S.

Output
8



-----Note-----

For the first example, one possible way to eat the maximum number of cake cells is as follows (perform 3 eats). [Image]  [Image]  [Image]
user: Everybody knows what an arithmetic progression is. Let us remind you just in case that an arithmetic progression is such sequence of numbers a_1, a_2, ..., a_{n} of length n, that the following condition fulfills: a_2 - a_1 = a_3 - a_2 = a_4 - a_3 = ... = a_{i} + 1 - a_{i} = ... = a_{n} - a_{n} - 1.

For example, sequences [1, 5], [10], [5, 4, 3] are arithmetic progressions and sequences [1, 3, 2], [1, 2, 4] are not.

Alexander has n cards containing integers. Arthur wants to give Alexander exactly one more card with a number so that he could use the resulting n + 1 cards to make an arithmetic progression (Alexander has to use all of his cards).

Arthur has already bought a card but he hasn't written a number on it. Help him, print all integers that you can write on a card so that the described condition fulfilled.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of cards. The next line contains the sequence of integers — the numbers on Alexander's cards. The numbers are positive integers, each of them doesn't exceed 10^8.


-----Output-----

If Arthur can write infinitely many distinct integers on the card, print on a single line -1.

Otherwise, print on the first line the number of integers that suit you. In the second line, print the numbers in the increasing order. Note that the numbers in the answer can exceed 10^8 or even be negative (see test samples).


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

Output
2
-2 10

Input
1
10

Output
-1

Input
4
1 3 5 9

Output
1
7

Input
4
4 3 4 5

Output
0

Input
2
2 4

Output
3
0 3 6
user: Polycarp is a great fan of television.

He wrote down all the TV programs he is interested in for today. His list contains n shows, i-th of them starts at moment l_{i} and ends at moment r_{i}.

Polycarp owns two TVs. He can watch two different shows simultaneously with two TVs but he can only watch one show at any given moment on a single TV. If one show ends at the same moment some other show starts then you can't watch them on a single TV.

Polycarp wants to check out all n shows. Are two TVs enough to do so?


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 2·10^5) — the number of shows.

Each of the next n lines contains two integers l_{i} and r_{i} (0 ≤ l_{i} < r_{i} ≤ 10^9) — starting and ending time of i-th show.


-----Output-----

If Polycarp is able to check out all the shows using only two TVs then print "YES" (without quotes). Otherwise, print "NO" (without quotes).


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

Output
YES

Input
4
1 2
2 3
2 3
1 2

Output
NO
user: Your friend has recently learned about coprime numbers. A pair of numbers {a, b} is called coprime if the maximum number that divides both a and b is equal to one. 

Your friend often comes up with different statements. He has recently supposed that if the pair (a, b) is coprime and the pair (b, c) is coprime, then the pair (a, c) is coprime. 

You want to find a counterexample for your friend's statement. Therefore, your task is to find three distinct numbers (a, b, c), for which the statement is false, and the numbers meet the condition l ≤ a < b < c ≤ r. 

More specifically, you need to find three numbers (a, b, c), such that l ≤ a < b < c ≤ r, pairs (a, b) and (b, c) are coprime, and pair (a, c) is not coprime.


-----Input-----

The single line contains two positive space-separated integers l, r (1 ≤ l ≤ r ≤ 10^18; r - l ≤ 50).


-----Output-----

Print three positive space-separated integers a, b, c — three distinct numbers (a, b, c) that form the counterexample. If there are several solutions, you are allowed to print any of them. The numbers must be printed in ascending order. 

If the counterexample does not exist, print the single number -1.


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

Output
2 3 4

Input
10 11

Output
-1

Input
900000000000000009 900000000000000029

Output
900000000000000009 900000000000000010 900000000000000021



-----Note-----

In the first sample pair (2, 4) is not coprime and pairs (2, 3) and (3, 4) are. 

In the second sample you cannot form a group of three distinct integers, so the answer is -1. 

In the third sample it is easy to see that numbers 900000000000000009 and 900000000000000021 are divisible by three.
user: Sereja showed an interesting game to his friends. The game goes like that. Initially, there is a table with an empty cup and n water mugs on it. Then all players take turns to move. During a move, a player takes a non-empty mug of water and pours all water from it into the cup. If the cup overfills, then we assume that this player lost.

As soon as Sereja's friends heard of the game, they wanted to play it. Sereja, on the other hand, wanted to find out whether his friends can play the game in such a way that there are no losers. You are given the volumes of all mugs and the cup. Also, you know that Sereja has (n - 1) friends. Determine if Sereja's friends can play the game so that nobody loses.


-----Input-----

The first line contains integers n and s (2 ≤ n ≤ 100; 1 ≤ s ≤ 1000) — the number of mugs and the volume of the cup. The next line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10). Number a_{i} means the volume of the i-th mug.


-----Output-----

In a single line, print "YES" (without the quotes) if his friends can play in the described manner, and "NO" (without the quotes) otherwise.


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

Output
YES

Input
3 4
3 1 3

Output
YES

Input
3 4
4 4 4

Output
NO
user: Alice and Bob are decorating a Christmas Tree. 

Alice wants only $3$ types of ornaments to be used on the Christmas Tree: yellow, blue and red. They have $y$ yellow ornaments, $b$ blue ornaments and $r$ red ornaments.

In Bob's opinion, a Christmas Tree will be beautiful if:  the number of blue ornaments used is greater by exactly $1$ than the number of yellow ornaments, and  the number of red ornaments used is greater by exactly $1$ than the number of blue ornaments. 

That is, if they have $8$ yellow ornaments, $13$ blue ornaments and $9$ red ornaments, we can choose $4$ yellow, $5$ blue and $6$ red ornaments ($5=4+1$ and $6=5+1$).

Alice wants to choose as many ornaments as possible, but she also wants the Christmas Tree to be beautiful according to Bob's opinion.

In the example two paragraphs above, we would choose $7$ yellow, $8$ blue and $9$ red ornaments. If we do it, we will use $7+8+9=24$ ornaments. That is the maximum number.

Since Alice and Bob are busy with preparing food to the New Year's Eve, they are asking you to find out the maximum number of ornaments that can be used in their beautiful Christmas Tree! 

It is guaranteed that it is possible to choose at least $6$ ($1+2+3=6$) ornaments.


-----Input-----

The only line contains three integers $y$, $b$, $r$ ($1 \leq y \leq 100$, $2 \leq b \leq 100$, $3 \leq r \leq 100$) — the number of yellow, blue and red ornaments. 

It is guaranteed that it is possible to choose at least $6$ ($1+2+3=6$) ornaments.


-----Output-----

Print one number — the maximum number of ornaments that can be used. 


-----Examples-----
Input
8 13 9

Output
24
Input
13 3 6

Output
9


-----Note-----

In the first example, the answer is $7+8+9=24$.

In the second example, the answer is $2+3+4=9$.