meetforever/GRPO_CL huggingface dataset:
user: Arya has n opponents in the school. Each day he will fight with all opponents who are present this day. His opponents have some fighting plan that guarantees they will win, but implementing this plan requires presence of them all. That means if one day at least one of Arya's opponents is absent at the school, then Arya will beat all present opponents. Otherwise, if all opponents are present, then they will beat Arya.

For each opponent Arya knows his schedule — whether or not he is going to present on each particular day. Tell him the maximum number of consecutive days that he will beat all present opponents.

Note, that if some day there are no opponents present, Arya still considers he beats all the present opponents.


-----Input-----

The first line of the input contains two integers n and d (1 ≤ n, d ≤ 100) — the number of opponents and the number of days, respectively.

The i-th of the following d lines contains a string of length n consisting of characters '0' and '1'. The j-th character of this string is '0' if the j-th opponent is going to be absent on the i-th day.


-----Output-----

Print the only integer — the maximum number of consecutive days that Arya will beat all present opponents.


-----Examples-----
Input
2 2
10
00

Output
2

Input
4 1
0100

Output
1

Input
4 5
1101
1111
0110
1011
1111

Output
2



-----Note-----

In the first and the second samples, Arya will beat all present opponents each of the d days.

In the third sample, Arya will beat his opponents on days 1, 3 and 4 and his opponents will beat him on days 2 and 5. Thus, the maximum number of consecutive winning days is 2, which happens on days 3 and 4.
user: Vus the Cossack holds a programming competition, in which $n$ people participate. He decided to award them all with pens and notebooks. It is known that Vus has exactly $m$ pens and $k$ notebooks.

Determine whether the Cossack can reward all participants, giving each of them at least one pen and at least one notebook.


-----Input-----

The first line contains three integers $n$, $m$, and $k$ ($1 \leq n, m, k \leq 100$) — the number of participants, the number of pens, and the number of notebooks respectively.


-----Output-----

Print "Yes" if it possible to reward all the participants. Otherwise, print "No".

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


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

Output
Yes

Input
3 9 3

Output
Yes

Input
8 5 20

Output
No



-----Note-----

In the first example, there are $5$ participants. The Cossack has $8$ pens and $6$ notebooks. Therefore, he has enough pens and notebooks.

In the second example, there are $3$ participants. The Cossack has $9$ pens and $3$ notebooks. He has more than enough pens but only the minimum needed number of notebooks.

In the third example, there are $8$ participants but only $5$ pens. Since the Cossack does not have enough pens, the answer is "No".
user: This year, as in previous years, MemSQL is inviting the top 25 competitors from the Start[c]up qualification round to compete onsite for the final round. Not everyone who is eligible to compete onsite can afford to travel to the office, though. Initially the top 25 contestants are invited to come onsite. Each eligible contestant must either accept or decline the invitation. Whenever a contestant declines, the highest ranked contestant not yet invited is invited to take the place of the one that declined. This continues until 25 contestants have accepted invitations.

After the qualifying round completes, you know K of the onsite finalists, as well as their qualifying ranks (which start at 1, there are no ties). Determine the minimum possible number of contestants that declined the invitation to compete onsite in the final round.


-----Input-----

The first line of input contains K (1 ≤ K ≤ 25), the number of onsite finalists you know. The second line of input contains r_1, r_2, ..., r_{K} (1 ≤ r_{i} ≤ 10^6), the qualifying ranks of the finalists you know. All these ranks are distinct.


-----Output-----

Print the minimum possible number of contestants that declined the invitation to compete onsite.


-----Examples-----
Input
25
2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 28

Output
3

Input
5
16 23 8 15 4

Output
0

Input
3
14 15 92

Output
67



-----Note-----

In the first example, you know all 25 onsite finalists. The contestants who ranked 1-st, 13-th, and 27-th must have declined, so the answer is 3.
user: A permutation p of size n is an array such that every integer from 1 to n occurs exactly once in this array.

Let's call a permutation an almost identity permutation iff there exist at least n - k indices i (1 ≤ i ≤ n) such that p_{i} = i.

Your task is to count the number of almost identity permutations for given numbers n and k.


-----Input-----

The first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).


-----Output-----

Print the number of almost identity permutations for given n and k.


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

Output
1

Input
4 2

Output
7

Input
5 3

Output
31

Input
5 4

Output
76
user: Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight $u \oplus v$ (where $\oplus$ is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.


-----Input-----

The only line contains an integer n (2 ≤ n ≤ 10^12), the number of vertices in the graph.


-----Output-----

The only line contains an integer x, the weight of the graph's minimum spanning tree.


-----Example-----
Input
4

Output
4


-----Note-----

In the first sample: [Image] The weight of the minimum spanning tree is 1+2+1=4.
user: Many computer strategy games require building cities, recruiting army, conquering tribes, collecting resources. Sometimes it leads to interesting problems. 

Let's suppose that your task is to build a square city. The world map uses the Cartesian coordinates. The sides of the city should be parallel to coordinate axes. The map contains mines with valuable resources, located at some points with integer coordinates. The sizes of mines are relatively small, i.e. they can be treated as points. The city should be built in such a way that all the mines are inside or on the border of the city square. 

Building a city takes large amount of money depending on the size of the city, so you have to build the city with the minimum area. Given the positions of the mines find the minimum possible area of the city.


-----Input-----

The first line of the input contains number n — the number of mines on the map (2 ≤ n ≤ 1000). Each of the next n lines contains a pair of integers x_{i} and y_{i} — the coordinates of the corresponding mine ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9). All points are pairwise distinct.


-----Output-----

Print the minimum area of the city that can cover all the mines with valuable resources.


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

Output
4

Input
2
0 0
0 3

Output
9
user: Thanos sort is a supervillain sorting algorithm, which works as follows: if the array is not sorted, snap your fingers* to remove the first or the second half of the items, and repeat the process.

Given an input array, what is the size of the longest sorted array you can obtain from it using Thanos sort?

*Infinity Gauntlet required.


-----Input-----

The first line of input contains a single number $n$ ($1 \le n \le 16$) — the size of the array. $n$ is guaranteed to be a power of 2.

The second line of input contains $n$ space-separated integers $a_i$ ($1 \le a_i \le 100$) — the elements of the array.


-----Output-----

Return the maximal length of a sorted array you can obtain using Thanos sort. The elements of the array have to be sorted in non-decreasing order.


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

Output
4

Input
8
11 12 1 2 13 14 3 4

Output
2

Input
4
7 6 5 4

Output
1



-----Note-----

In the first example the array is already sorted, so no finger snaps are required.

In the second example the array actually has a subarray of 4 sorted elements, but you can not remove elements from different sides of the array in one finger snap. Each time you have to remove either the whole first half or the whole second half, so you'll have to snap your fingers twice to get to a 2-element sorted array.

In the third example the array is sorted in decreasing order, so you can only save one element from the ultimate destruction.
user: You are given a string $s$ of length $n$ consisting only of lowercase Latin letters.

A substring of a string is a contiguous subsequence of that string. So, string "forces" is substring of string "codeforces", but string "coder" is not.

Your task is to calculate the number of ways to remove exactly one substring from this string in such a way that all remaining characters are equal (the number of distinct characters either zero or one).

It is guaranteed that there is at least two different characters in $s$.

Note that you can remove the whole string and it is correct. Also note that you should remove at least one character.

Since the answer can be rather large (not very large though) print it modulo $998244353$.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of the input contains the string $s$ of length $n$ consisting only of lowercase Latin letters.

It is guaranteed that there is at least two different characters in $s$.


-----Output-----

Print one integer — the number of ways modulo $998244353$ to remove exactly one substring from $s$ in such way that all remaining characters are equal.


-----Examples-----
Input
4
abaa

Output
6

Input
7
aacdeee

Output
6
Input
2
az

Output
3


-----Note-----

Let $s[l; r]$ be the substring of $s$ from the position $l$ to the position $r$ inclusive.

Then in the first example you can remove the following substrings:   $s[1; 2]$;  $s[1; 3]$;  $s[1; 4]$;  $s[2; 2]$;  $s[2; 3]$;  $s[2; 4]$. 

In the second example you can remove the following substrings:   $s[1; 4]$;  $s[1; 5]$;  $s[1; 6]$;  $s[1; 7]$;  $s[2; 7]$;  $s[3; 7]$. 

In the third example you can remove the following substrings:   $s[1; 1]$;  $s[1; 2]$;  $s[2; 2]$.
user: You are given $n$ blocks, each of them is of the form [color$_1$|value|color$_2$], where the block can also be flipped to get [color$_2$|value|color$_1$]. 

A sequence of blocks is called valid if the touching endpoints of neighboring blocks have the same color. For example, the sequence of three blocks A, B and C is valid if the left color of the B is the same as the right color of the A and the right color of the B is the same as the left color of C.

The value of the sequence is defined as the sum of the values of the blocks in this sequence.

Find the maximum possible value of the valid sequence that can be constructed from the subset of the given blocks. The blocks from the subset can be reordered and flipped if necessary. Each block can be used at most once in the sequence.


-----Input-----

The first line of input contains a single integer $n$ ($1 \le n \le 100$) — the number of given blocks.

Each of the following $n$ lines describes corresponding block and consists of $\mathrm{color}_{1,i}$, $\mathrm{value}_i$ and $\mathrm{color}_{2,i}$ ($1 \le \mathrm{color}_{1,i}, \mathrm{color}_{2,i} \le 4$, $1 \le \mathrm{value}_i \le 100\,000$).


-----Output-----

Print exactly one integer — the maximum total value of the subset of blocks, which makes a valid sequence.


-----Examples-----
Input
6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2

Output
63
Input
7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3

Output
300000
Input
4
1 1000 1
2 500 2
3 250 3
4 125 4

Output
1000


-----Note-----

In the first example, it is possible to form a valid sequence from all blocks.

One of the valid sequences is the following:

[4|2|1] [1|32|2] [2|8|3] [3|16|3] [3|4|4] [4|1|2]

The first block from the input ([2|1|4] $\to$ [4|1|2]) and second ([1|2|4] $\to$ [4|2|1]) are flipped.

In the second example, the optimal answers can be formed from the first three blocks as in the following (the second or the third block from the input is flipped):

[2|100000|1] [1|100000|1] [1|100000|2]

In the third example, it is not possible to form a valid sequence of two or more blocks, so the answer is a sequence consisting only of the first block since it is the block with the largest value.
user: Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length $k$ is vowelly if there are positive integers $n$ and $m$ such that $n\cdot m = k$ and when the word is written by using $n$ rows and $m$ columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer $k$ and you must either print a vowelly word of length $k$ or print $-1$ if no such word exists.

In this problem the vowels of the English alphabet are 'a', 'e', 'i', 'o' ,'u'.


-----Input-----

Input consists of a single line containing the integer $k$ ($1\leq k \leq 10^4$) — the required length.


-----Output-----

The output must consist of a single line, consisting of a vowelly word of length $k$ consisting of lowercase English letters if it exists or $-1$ if it does not.

If there are multiple possible words, you may output any of them.


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

Output
-1

Input
36

Output
agoeuioaeiruuimaeoieauoweouoiaouimae


-----Note-----

In the second example, the word "agoeuioaeiruuimaeoieauoweouoiaouimae" can be arranged into the following $6 \times 6$ grid: $\left. \begin{array}{|c|c|c|c|c|c|} \hline a & {g} & {o} & {e} & {u} & {i} \\ \hline o & {a} & {e} & {i} & {r} & {u} \\ \hline u & {i} & {m} & {a} & {e} & {o} \\ \hline i & {e} & {a} & {u} & {o} & {w} \\ \hline e & {o} & {u} & {o} & {i} & {a} \\ \hline o & {u} & {i} & {m} & {a} & {e} \\ \hline \end{array} \right.$ 

It is easy to verify that every row and every column contain all the vowels.
user: As you must know, the maximum clique problem in an arbitrary graph is NP-hard. Nevertheless, for some graphs of specific kinds it can be solved effectively.

Just in case, let us remind you that a clique in a non-directed graph is a subset of the vertices of a graph, such that any two vertices of this subset are connected by an edge. In particular, an empty set of vertexes and a set consisting of a single vertex, are cliques.

Let's define a divisibility graph for a set of positive integers A = {a_1, a_2, ..., a_{n}} as follows. The vertices of the given graph are numbers from set A, and two numbers a_{i} and a_{j} (i ≠ j) are connected by an edge if and only if either a_{i} is divisible by a_{j}, or a_{j} is divisible by a_{i}.

You are given a set of non-negative integers A. Determine the size of a maximum clique in a divisibility graph for set A.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6), that sets the size of set A.

The second line contains n distinct positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — elements of subset A. The numbers in the line follow in the ascending order.


-----Output-----

Print a single number — the maximum size of a clique in a divisibility graph for set A.


-----Examples-----
Input
8
3 4 6 8 10 18 21 24

Output
3



-----Note-----

In the first sample test a clique of size 3 is, for example, a subset of vertexes {3, 6, 18}. A clique of a larger size doesn't exist in this graph.
user: You've got a 5 × 5 matrix, consisting of 24 zeroes and a single number one. Let's index the matrix rows by numbers from 1 to 5 from top to bottom, let's index the matrix columns by numbers from 1 to 5 from left to right. In one move, you are allowed to apply one of the two following transformations to the matrix:  Swap two neighboring matrix rows, that is, rows with indexes i and i + 1 for some integer i (1 ≤ i < 5).  Swap two neighboring matrix columns, that is, columns with indexes j and j + 1 for some integer j (1 ≤ j < 5). 

You think that a matrix looks beautiful, if the single number one of the matrix is located in its middle (in the cell that is on the intersection of the third row and the third column). Count the minimum number of moves needed to make the matrix beautiful.


-----Input-----

The input consists of five lines, each line contains five integers: the j-th integer in the i-th line of the input represents the element of the matrix that is located on the intersection of the i-th row and the j-th column. It is guaranteed that the matrix consists of 24 zeroes and a single number one.


-----Output-----

Print a single integer — the minimum number of moves needed to make the matrix beautiful.


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

Output
3

Input
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

Output
1
user: Ford Prefect got a job as a web developer for a small company that makes towels. His current work task is to create a search engine for the website of the company. During the development process, he needs to write a subroutine for comparing strings S and T of equal length to be "similar". After a brief search on the Internet, he learned about the Hamming distance between two strings S and T of the same length, which is defined as the number of positions in which S and T have different characters. For example, the Hamming distance between words "permanent" and "pergament" is two, as these words differ in the fourth and sixth letters.

Moreover, as he was searching for information, he also noticed that modern search engines have powerful mechanisms to correct errors in the request to improve the quality of search. Ford doesn't know much about human beings, so he assumed that the most common mistake in a request is swapping two arbitrary letters of the string (not necessarily adjacent). Now he wants to write a function that determines which two letters should be swapped in string S, so that the Hamming distance between a new string S and string T would be as small as possible, or otherwise, determine that such a replacement cannot reduce the distance between the strings.

Help him do this!


-----Input-----

The first line contains integer n (1 ≤ n ≤ 200 000) — the length of strings S and T.

The second line contains string S.

The third line contains string T.

Each of the lines only contains lowercase Latin letters.


-----Output-----

In the first line, print number x — the minimum possible Hamming distance between strings S and T if you swap at most one pair of letters in S.

In the second line, either print the indexes i and j (1 ≤ i, j ≤ n, i ≠ j), if reaching the minimum possible distance is possible by swapping letters on positions i and j, or print "-1 -1", if it is not necessary to swap characters.

If there are multiple possible answers, print any of them.


-----Examples-----
Input
9
pergament
permanent

Output
1
4 6

Input
6
wookie
cookie

Output
1
-1 -1

Input
4
petr
egor

Output
2
1 2

Input
6
double
bundle

Output
2
4 1



-----Note-----

In the second test it is acceptable to print i = 2, j = 3.
user: Peter wrote on the board a strictly increasing sequence of positive integers a_1, a_2, ..., a_{n}. Then Vasil replaced some digits in the numbers of this sequence by question marks. Thus, each question mark corresponds to exactly one lost digit.

Restore the the original sequence knowing digits remaining on the board.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 10^5) — the length of the sequence. Next n lines contain one element of the sequence each. Each element consists only of digits and question marks. No element starts from digit 0. Each element has length from 1 to 8 characters, inclusive.


-----Output-----

If the answer exists, print in the first line "YES" (without the quotes). Next n lines must contain the sequence of positive integers — a possible variant of Peter's sequence. The found sequence must be strictly increasing, it must be transformed from the given one by replacing each question mark by a single digit. All numbers on the resulting sequence must be written without leading zeroes. If there are multiple solutions, print any of them.

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


-----Examples-----
Input
3
?
18
1?

Output
YES
1
18
19

Input
2
??
?

Output
NO

Input
5
12224
12??5
12226
?0000
?00000

Output
YES
12224
12225
12226
20000
100000
user: Adilbek's house is located on a street which can be represented as the OX axis. This street is really dark, so Adilbek wants to install some post lamps to illuminate it. Street has $n$ positions to install lamps, they correspond to the integer numbers from $0$ to $n - 1$ on the OX axis. However, some positions are blocked and no post lamp can be placed there.

There are post lamps of different types which differ only by their power. When placed in position $x$, post lamp of power $l$ illuminates the segment $[x; x + l]$. The power of each post lamp is always a positive integer number.

The post lamp shop provides an infinite amount of lamps of each type from power $1$ to power $k$. Though each customer is only allowed to order post lamps of exactly one type. Post lamps of power $l$ cost $a_l$ each.

What is the minimal total cost of the post lamps of exactly one type Adilbek can buy to illuminate the entire segment $[0; n]$ of the street? If some lamps illuminate any other segment of the street, Adilbek does not care, so, for example, he may place a lamp of power $3$ in position $n - 1$ (even though its illumination zone doesn't completely belong to segment $[0; n]$).


-----Input-----

The first line contains three integer numbers $n$, $m$ and $k$ ($1 \le k \le n \le 10^6$, $0 \le m \le n$) — the length of the segment of the street Adilbek wants to illuminate, the number of the blocked positions and the maximum power of the post lamp available.

The second line contains $m$ integer numbers $s_1, s_2, \dots, s_m$ ($0 \le s_1 < s_2 < \dots s_m < n$) — the blocked positions.

The third line contains $k$ integer numbers $a_1, a_2, \dots, a_k$ ($1 \le a_i \le 10^6$) — the costs of the post lamps.


-----Output-----

Print the minimal total cost of the post lamps of exactly one type Adilbek can buy to illuminate the entire segment $[0; n]$ of the street.

If illumintaing the entire segment $[0; n]$ is impossible, print -1.


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

Output
6

Input
4 3 4
1 2 3
1 10 100 1000

Output
1000

Input
5 1 5
0
3 3 3 3 3

Output
-1

Input
7 4 3
2 4 5 6
3 14 15

Output
-1