meetforever/GRPO_CL huggingface dataset:
user: There is an array with n elements a_1, a_2, ..., a_{n} and the number x.

In one operation you can select some i (1 ≤ i ≤ n) and replace element a_{i} with a_{i} & x, where & denotes the bitwise and operation.

You want the array to have at least two equal elements after applying some operations (possibly, none). In other words, there should be at least two distinct indices i ≠ j such that a_{i} = a_{j}. Determine whether it is possible to achieve and, if possible, the minimal number of operations to apply.


-----Input-----

The first line contains integers n and x (2 ≤ n ≤ 100 000, 1 ≤ x ≤ 100 000), number of elements in the array and the number to and with.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 100 000), the elements of the array.


-----Output-----

Print a single integer denoting the minimal number of operations to do, or -1, if it is impossible.


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

Output
1

Input
2 228
1 1

Output
0

Input
3 7
1 2 3

Output
-1



-----Note-----

In the first example one can apply the operation to the last element of the array. That replaces 7 with 3, so we achieve the goal in one move.

In the second example the array already has two equal elements.

In the third example applying the operation won't change the array at all, so it is impossible to make some pair of elements equal.
user: You have a given picture with size $w \times h$. Determine if the given picture has a single "+" shape or not. A "+" shape is described below:

  A "+" shape has one center nonempty cell.  There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction.  All other cells are empty. 

Find out if the given picture has single "+" shape.


-----Input-----

The first line contains two integers $h$ and $w$ ($1 \le h$, $w \le 500$) — the height and width of the picture.

The $i$-th of the next $h$ lines contains string $s_{i}$ of length $w$ consisting "." and "*" where "." denotes the empty space and "*" denotes the non-empty space.


-----Output-----

If the given picture satisfies all conditions, print "YES". Otherwise, print "NO".

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


-----Examples-----
Input
5 6
......
..*...
.****.
..*...
..*...

Output
YES

Input
3 5
..*..
****.
.*...

Output
NO

Input
7 7
.......
...*...
..****.
...*...
...*...
.......
.*.....

Output
NO

Input
5 6
..**..
..**..
******
..**..
..**..

Output
NO

Input
3 7
.*...*.
***.***
.*...*.

Output
NO

Input
5 10
..........
..*.......
.*.******.
..*.......
..........

Output
NO



-----Note-----

In the first example, the given picture contains one "+".

In the second example, two vertical branches are located in a different column.

In the third example, there is a dot outside of the shape.

In the fourth example, the width of the two vertical branches is $2$.

In the fifth example, there are two shapes.

In the sixth example, there is an empty space inside of the shape.
user: Given three numbers $n, a, b$. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to $a$, and the number of components in its complement is $b$. The matrix must be symmetric, and all digits on the main diagonal must be zeroes.

In an undirected graph loops (edges from a vertex to itself) are not allowed. It can be at most one edge between a pair of vertices.

The adjacency matrix of an undirected graph is a square matrix of size $n$ consisting only of "0" and "1", where $n$ is the number of vertices of the graph and the $i$-th row and the $i$-th column correspond to the $i$-th vertex of the graph. The cell $(i,j)$ of the adjacency matrix contains $1$ if and only if the $i$-th and $j$-th vertices in the graph are connected by an edge.

A connected component is a set of vertices $X$ such that for every two vertices from this set there exists at least one path in the graph connecting this pair of vertices, but adding any other vertex to $X$ violates this rule.

The complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are not adjacent in $G$.


-----Input-----

In a single line, three numbers are given $n, a, b \,(1 \le n \le 1000, 1 \le a, b \le n)$: is the number of vertexes of the graph, the required number of connectivity components in it, and the required amount of the connectivity component in it's complement. 


-----Output-----

If there is no graph that satisfies these constraints on a single line, print "NO" (without quotes).

Otherwise, on the first line, print "YES"(without quotes). In each of the next $n$ lines, output $n$ digits such that $j$-th digit of $i$-th line must be $1$ if and only if there is an edge between vertices $i$ and $j$ in $G$ (and $0$ otherwise). Note that the matrix must be symmetric, and all digits on the main diagonal must be zeroes. 

If there are several matrices that satisfy the conditions — output any of them.


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

Output
YES
001
001
110

Input
3 3 3

Output
NO
user: The finalists of the "Russian Code Cup" competition in 2214 will be the participants who win in one of the elimination rounds.

The elimination rounds are divided into main and additional. Each of the main elimination rounds consists of c problems, the winners of the round are the first n people in the rating list. Each of the additional elimination rounds consists of d problems. The winner of the additional round is one person. Besides, k winners of the past finals are invited to the finals without elimination.

As a result of all elimination rounds at least n·m people should go to the finals. You need to organize elimination rounds in such a way, that at least n·m people go to the finals, and the total amount of used problems in all rounds is as small as possible.


-----Input-----

The first line contains two integers c and d (1 ≤ c, d ≤ 100) — the number of problems in the main and additional rounds, correspondingly. The second line contains two integers n and m (1 ≤ n, m ≤ 100). Finally, the third line contains an integer k (1 ≤ k ≤ 100) — the number of the pre-chosen winners. 


-----Output-----

In the first line, print a single integer — the minimum number of problems the jury needs to prepare.


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

Output
2

Input
2 2
2 1
2

Output
0
user: Let’s define a grid to be a set of tiles with 2 rows and 13 columns. Each tile has an English letter written in it. The letters don't have to be unique: there might be two or more tiles with the same letter written on them. Here is an example of a grid: ABCDEFGHIJKLM

NOPQRSTUVWXYZ 

We say that two tiles are adjacent if they share a side or a corner. In the example grid above, the tile with the letter 'A' is adjacent only to the tiles with letters 'B', 'N', and 'O'. A tile is not adjacent to itself.

A sequence of tiles is called a path if each tile in the sequence is adjacent to the tile which follows it (except for the last tile in the sequence, which of course has no successor). In this example, "ABC" is a path, and so is "KXWIHIJK". "MAB" is not a path because 'M' is not adjacent to 'A'. A single tile can be used more than once by a path (though the tile cannot occupy two consecutive places in the path because no tile is adjacent to itself).

You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s. Find a grid that contains a path whose tiles, viewed in the order that the path visits them, form the string s. If there’s no solution, print "Impossible" (without the quotes).


-----Input-----

The only line of the input contains the string s, consisting of 27 upper-case English letters. Each English letter occurs at least once in s.


-----Output-----

Output two lines, each consisting of 13 upper-case English characters, representing the rows of the grid. If there are multiple solutions, print any of them. If there is no solution print "Impossible".


-----Examples-----
Input
ABCDEFGHIJKLMNOPQRSGTUVWXYZ

Output
YXWVUTGHIJKLM
ZABCDEFSRQPON

Input
BUVTYZFQSNRIWOXXGJLKACPEMDH

Output
Impossible
user: Year 2118. Androids are in mass production for decades now, and they do all the work for humans. But androids have to go to school to be able to solve creative tasks. Just like humans before.

It turns out that high school struggles are not gone. If someone is not like others, he is bullied. Vasya-8800 is an economy-class android which is produced by a little-known company. His design is not perfect, his characteristics also could be better. So he is bullied by other androids.

One of the popular pranks on Vasya is to force him to compare $x^y$ with $y^x$. Other androids can do it in milliseconds while Vasya's memory is too small to store such big numbers.

Please help Vasya! Write a fast program to compare $x^y$ with $y^x$ for Vasya, maybe then other androids will respect him.


-----Input-----

On the only line of input there are two integers $x$ and $y$ ($1 \le x, y \le 10^{9}$).


-----Output-----

If $x^y < y^x$, then print '<' (without quotes). If $x^y > y^x$, then print '>' (without quotes). If $x^y = y^x$, then print '=' (without quotes).


-----Examples-----
Input
5 8

Output
>

Input
10 3

Output
<

Input
6 6

Output
=



-----Note-----

In the first example $5^8 = 5 \cdot 5 \cdot 5 \cdot 5 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 390625$, and $8^5 = 8 \cdot 8 \cdot 8 \cdot 8 \cdot 8 = 32768$. So you should print '>'.

In the second example $10^3 = 1000 < 3^{10} = 59049$.

In the third example $6^6 = 46656 = 6^6$.
user: A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius r (the cupboard's top) and two walls of height h (the cupboard's sides). The cupboard's depth is r, that is, it looks like a rectangle with base r and height h + r from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right). [Image] 

Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius $\frac{r}{2}$. Help Xenia calculate the maximum number of balloons she can put in her cupboard. 

You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.


-----Input-----

The single line contains two integers r, h (1 ≤ r, h ≤ 10^7).


-----Output-----

Print a single integer — the maximum number of balloons Xenia can put in the cupboard.


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

Output
3

Input
1 2

Output
5

Input
2 1

Output
2
user: A little bear Limak plays a game. He has five cards. There is one number written on each card. Each number is a positive integer.

Limak can discard (throw out) some cards. His goal is to minimize the sum of numbers written on remaining (not discarded) cards.

He is allowed to at most once discard two or three cards with the same number. Of course, he won't discard cards if it's impossible to choose two or three cards with the same number.

Given five numbers written on cards, cay you find the minimum sum of numbers on remaining cards?


-----Input-----

The only line of the input contains five integers t_1, t_2, t_3, t_4 and t_5 (1 ≤ t_{i} ≤ 100) — numbers written on cards.


-----Output-----

Print the minimum possible sum of numbers written on remaining cards.


-----Examples-----
Input
7 3 7 3 20

Output
26

Input
7 9 3 1 8

Output
28

Input
10 10 10 10 10

Output
20



-----Note-----

In the first sample, Limak has cards with numbers 7, 3, 7, 3 and 20. Limak can do one of the following.

  Do nothing and the sum would be 7 + 3 + 7 + 3 + 20 = 40.  Remove two cards with a number 7. The remaining sum would be 3 + 3 + 20 = 26.  Remove two cards with a number 3. The remaining sum would be 7 + 7 + 20 = 34. 

You are asked to minimize the sum so the answer is 26.

In the second sample, it's impossible to find two or three cards with the same number. Hence, Limak does nothing and the sum is 7 + 9 + 1 + 3 + 8 = 28.

In the third sample, all cards have the same number. It's optimal to discard any three cards. The sum of two remaining numbers is 10 + 10 = 20.
user: Vasya takes part in the orienteering competition. There are n checkpoints located along the line at coordinates x_1, x_2, ..., x_{n}. Vasya starts at the point with coordinate a. His goal is to visit at least n - 1 checkpoint in order to finish the competition. Participant are allowed to visit checkpoints in arbitrary order.

Vasya wants to pick such checkpoints and the order of visiting them that the total distance travelled is minimized. He asks you to calculate this minimum possible value.


-----Input-----

The first line of the input contains two integers n and a (1 ≤ n ≤ 100 000,  - 1 000 000 ≤ a ≤ 1 000 000) — the number of checkpoints and Vasya's starting position respectively.

The second line contains n integers x_1, x_2, ..., x_{n} ( - 1 000 000 ≤ x_{i} ≤ 1 000 000) — coordinates of the checkpoints.


-----Output-----

Print one integer — the minimum distance Vasya has to travel in order to visit at least n - 1 checkpoint.


-----Examples-----
Input
3 10
1 7 12

Output
7

Input
2 0
11 -10

Output
10

Input
5 0
0 0 1000 0 0

Output
0



-----Note-----

In the first sample Vasya has to visit at least two checkpoints. The optimal way to achieve this is the walk to the third checkpoints (distance is 12 - 10 = 2) and then proceed to the second one (distance is 12 - 7 = 5). The total distance is equal to 2 + 5 = 7.

In the second sample it's enough to visit only one checkpoint so Vasya should just walk to the point  - 10.
user: Let's consider equation:x^2 + s(x)·x - n = 0,  

where x, n are positive integers, s(x) is the function, equal to the sum of digits of number x in the decimal number system.

You are given an integer n, find the smallest positive integer root of equation x, or else determine that there are no such roots.


-----Input-----

A single line contains integer n (1 ≤ n ≤ 10^18) — the equation parameter.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier. 


-----Output-----

Print -1, if the equation doesn't have integer positive roots. Otherwise print such smallest integer x (x > 0), that the equation given in the statement holds.


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

Output
1

Input
110

Output
10

Input
4

Output
-1



-----Note-----

In the first test case x = 1 is the minimum root. As s(1) = 1 and 1^2 + 1·1 - 2 = 0.

In the second test case x = 10 is the minimum root. As s(10) = 1 + 0 = 1 and 10^2 + 1·10 - 110 = 0.

In the third test case the equation has no roots.
user: George woke up and saw the current time s on the digital clock. Besides, George knows that he has slept for time t. 

Help George! Write a program that will, given time s and t, determine the time p when George went to bed. Note that George could have gone to bed yesterday relatively to the current time (see the second test sample). 


-----Input-----

The first line contains current time s as a string in the format "hh:mm". The second line contains time t in the format "hh:mm" — the duration of George's sleep. It is guaranteed that the input contains the correct time in the 24-hour format, that is, 00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59.


-----Output-----

In the single line print time p — the time George went to bed in the format similar to the format of the time in the input.


-----Examples-----
Input
05:50
05:44

Output
00:06

Input
00:00
01:00

Output
23:00

Input
00:01
00:00

Output
00:01



-----Note-----

In the first sample George went to bed at "00:06". Note that you should print the time only in the format "00:06". That's why answers "0:06", "00:6" and others will be considered incorrect. 

In the second sample, George went to bed yesterday.

In the third sample, George didn't do to bed at all.
user: You are given array $a_1, a_2, \dots, a_n$. Find the subsegment $a_l, a_{l+1}, \dots, a_r$ ($1 \le l \le r \le n$) with maximum arithmetic mean $\frac{1}{r - l + 1}\sum\limits_{i=l}^{r}{a_i}$ (in floating-point numbers, i.e. without any rounding).

If there are many such subsegments find the longest one.


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 10^5$) — length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the array $a$.


-----Output-----

Print the single integer — the length of the longest subsegment with maximum possible arithmetic mean.


-----Example-----
Input
5
6 1 6 6 0

Output
2



-----Note-----

The subsegment $[3, 4]$ is the longest among all subsegments with maximum arithmetic mean.
user: On his free time, Chouti likes doing some housework. He has got one new task, paint some bricks in the yard.

There are $n$ bricks lined in a row on the ground. Chouti has got $m$ paint buckets of different colors at hand, so he painted each brick in one of those $m$ colors.

Having finished painting all bricks, Chouti was satisfied. He stood back and decided to find something fun with these bricks. After some counting, he found there are $k$ bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure).

So as usual, he needs your help in counting how many ways could he paint the bricks. Two ways of painting bricks are different if there is at least one brick painted in different colors in these two ways. Because the answer might be quite big, you only need to output the number of ways modulo $998\,244\,353$.


-----Input-----

The first and only line contains three integers $n$, $m$ and $k$ ($1 \leq n,m \leq 2000, 0 \leq k \leq n-1$) — the number of bricks, the number of colors, and the number of bricks, such that its color differs from the color of brick to the left of it.


-----Output-----

Print one integer — the number of ways to color bricks modulo $998\,244\,353$.


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

Output
3

Input
3 2 1

Output
4



-----Note-----

In the first example, since $k=0$, the color of every brick should be the same, so there will be exactly $m=3$ ways to color the bricks.

In the second example, suppose the two colors in the buckets are yellow and lime, the following image shows all $4$ possible colorings. [Image]
user: A magic number is a number formed by concatenation of numbers 1, 14 and 144. We can use each of these numbers any number of times. Therefore 14144, 141414 and 1411 are magic numbers but 1444, 514 and 414 are not.

You're given a number. Determine if it is a magic number or not.


-----Input-----

The first line of input contains an integer n, (1 ≤ n ≤ 10^9). This number doesn't contain leading zeros.


-----Output-----

Print "YES" if n is a magic number or print "NO" if it's not.


-----Examples-----
Input
114114

Output
YES

Input
1111

Output
YES

Input
441231

Output
NO
user: Dima and Inna are doing so great! At the moment, Inna is sitting on the magic lawn playing with a pink pony. Dima wanted to play too. He brought an n × m chessboard, a very tasty candy and two numbers a and b.

Dima put the chessboard in front of Inna and placed the candy in position (i, j) on the board. The boy said he would give the candy if it reaches one of the corner cells of the board. He's got one more condition. There can only be actions of the following types:

  move the candy from position (x, y) on the board to position (x - a, y - b);  move the candy from position (x, y) on the board to position (x + a, y - b);  move the candy from position (x, y) on the board to position (x - a, y + b);  move the candy from position (x, y) on the board to position (x + a, y + b). 

Naturally, Dima doesn't allow to move the candy beyond the chessboard borders.

Inna and the pony started shifting the candy around the board. They wonder what is the minimum number of allowed actions that they need to perform to move the candy from the initial position (i, j) to one of the chessboard corners. Help them cope with the task! 


-----Input-----

The first line of the input contains six integers n, m, i, j, a, b (1 ≤ n, m ≤ 10^6; 1 ≤ i ≤ n; 1 ≤ j ≤ m; 1 ≤ a, b ≤ 10^6).

You can assume that the chessboard rows are numbered from 1 to n from top to bottom and the columns are numbered from 1 to m from left to right. Position (i, j) in the statement is a chessboard cell on the intersection of the i-th row and the j-th column. You can consider that the corners are: (1, m), (n, 1), (n, m), (1, 1).


-----Output-----

In a single line print a single integer — the minimum number of moves needed to get the candy.

If Inna and the pony cannot get the candy playing by Dima's rules, print on a single line "Poor Inna and pony!" without the quotes.


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

Output
2

Input
5 5 2 3 1 1

Output
Poor Inna and pony!



-----Note-----

Note to sample 1:

Inna and the pony can move the candy to position (1 + 2, 3 + 2) = (3, 5), from there they can move it to positions (3 - 2, 5 + 2) = (1, 7) and (3 + 2, 5 + 2) = (5, 7). These positions correspond to the corner squares of the chess board. Thus, the answer to the test sample equals two.
user: You are given a string $s$ consisting of lowercase Latin letters. Let the length of $s$ be $|s|$. You may perform several operations on this string.

In one operation, you can choose some index $i$ and remove the $i$-th character of $s$ ($s_i$) if at least one of its adjacent characters is the previous letter in the Latin alphabet for $s_i$. For example, the previous letter for b is a, the previous letter for s is r, the letter a has no previous letters. Note that after each removal the length of the string decreases by one. So, the index $i$ should satisfy the condition $1 \le i \le |s|$ during each operation.

For the character $s_i$ adjacent characters are $s_{i-1}$ and $s_{i+1}$. The first and the last characters of $s$ both have only one adjacent character (unless $|s| = 1$).

Consider the following example. Let $s=$ bacabcab.  During the first move, you can remove the first character $s_1=$ b because $s_2=$ a. Then the string becomes $s=$ acabcab.  During the second move, you can remove the fifth character $s_5=$ c because $s_4=$ b. Then the string becomes $s=$ acabab.  During the third move, you can remove the sixth character $s_6=$'b' because $s_5=$ a. Then the string becomes $s=$ acaba.  During the fourth move, the only character you can remove is $s_4=$ b, because $s_3=$ a (or $s_5=$ a). The string becomes $s=$ acaa and you cannot do anything with it. 

Your task is to find the maximum possible number of characters you can remove if you choose the sequence of operations optimally.


-----Input-----

The first line of the input contains one integer $|s|$ ($1 \le |s| \le 100$) — the length of $s$.

The second line of the input contains one string $s$ consisting of $|s|$ lowercase Latin letters.


-----Output-----

Print one integer — the maximum possible number of characters you can remove if you choose the sequence of moves optimally.


-----Examples-----
Input
8
bacabcab

Output
4

Input
4
bcda

Output
3

Input
6
abbbbb

Output
5



-----Note-----

The first example is described in the problem statement. Note that the sequence of moves provided in the statement is not the only, but it can be shown that the maximum possible answer to this test is $4$.

In the second example, you can remove all but one character of $s$. The only possible answer follows.  During the first move, remove the third character $s_3=$ d, $s$ becomes bca.  During the second move, remove the second character $s_2=$ c, $s$ becomes ba.  And during the third move, remove the first character $s_1=$ b, $s$ becomes a.