meetforever/GRPO_CL huggingface dataset:
user: After overcoming the stairs Dasha came to classes. She needed to write a password to begin her classes. The password is a string of length n which satisfies the following requirements:  There is at least one digit in the string,  There is at least one lowercase (small) letter of the Latin alphabet in the string,  There is at least one of three listed symbols in the string: '#', '*', '&'.  [Image] 

Considering that these are programming classes it is not easy to write the password.

For each character of the password we have a fixed string of length m, on each of these n strings there is a pointer on some character. The i-th character displayed on the screen is the pointed character in the i-th string. Initially, all pointers are on characters with indexes 1 in the corresponding strings (all positions are numbered starting from one).

During one operation Dasha can move a pointer in one string one character to the left or to the right. Strings are cyclic, it means that when we move the pointer which is on the character with index 1 to the left, it moves to the character with the index m, and when we move it to the right from the position m it moves to the position 1.

You need to determine the minimum number of operations necessary to make the string displayed on the screen a valid password. 


-----Input-----

The first line contains two integers n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50) — the length of the password and the length of strings which are assigned to password symbols. 

Each of the next n lines contains the string which is assigned to the i-th symbol of the password string. Its length is m, it consists of digits, lowercase English letters, and characters '#', '*' or '&'.

You have such input data that you can always get a valid password.


-----Output-----

Print one integer — the minimum number of operations which is necessary to make the string, which is displayed on the screen, a valid password. 


-----Examples-----
Input
3 4
1**2
a3*0
c4**

Output
1

Input
5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&

Output
3



-----Note-----

In the first test it is necessary to move the pointer of the third string to one left to get the optimal answer.  [Image] 

In the second test one of possible algorithms will be:   to move the pointer of the second symbol once to the right.  to move the pointer of the third symbol twice to the right.  [Image]
user: Some natural number was written on the board. Its sum of digits was not less than k. But you were distracted a bit, and someone changed this number to n, replacing some digits with others. It's known that the length of the number didn't change.

You have to find the minimum number of digits in which these two numbers can differ.


-----Input-----

The first line contains integer k (1 ≤ k ≤ 10^9).

The second line contains integer n (1 ≤ n < 10^100000).

There are no leading zeros in n. It's guaranteed that this situation is possible.


-----Output-----

Print the minimum number of digits in which the initial number and n can differ.


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

Output
1

Input
3
99

Output
0



-----Note-----

In the first example, the initial number could be 12.

In the second example the sum of the digits of n is not less than k. The initial number could be equal to n.
user: Andrew prefers taxi to other means of transport, but recently most taxi drivers have been acting inappropriately. In order to earn more money, taxi drivers started to drive in circles. Roads in Andrew's city are one-way, and people are not necessary able to travel from one part to another, but it pales in comparison to insidious taxi drivers.

The mayor of the city decided to change the direction of certain roads so that the taxi drivers wouldn't be able to increase the cost of the trip endlessly. More formally, if the taxi driver is on a certain crossroads, they wouldn't be able to reach it again if he performs a nonzero trip. 

Traffic controllers are needed in order to change the direction the road goes. For every road it is known how many traffic controllers are needed to change the direction of the road to the opposite one. It is allowed to change the directions of roads one by one, meaning that each traffic controller can participate in reversing two or more roads.

You need to calculate the minimum number of traffic controllers that you need to hire to perform the task and the list of the roads that need to be reversed.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 100\,000$, $1 \leq m \leq 100\,000$) — the number of crossroads and the number of roads in the city, respectively.

Each of the following $m$ lines contain three integers $u_{i}$, $v_{i}$ and $c_{i}$ ($1 \leq u_{i}, v_{i} \leq n$, $1 \leq c_{i} \leq 10^9$, $u_{i} \ne v_{i}$) — the crossroads the road starts at, the crossroads the road ends at and the number of traffic controllers required to reverse this road.


-----Output-----

In the first line output two integers the minimal amount of traffic controllers required to complete the task and amount of roads $k$ which should be reversed. $k$ should not be minimized.

In the next line output $k$ integers separated by spaces — numbers of roads, the directions of which should be reversed. The roads are numerated from $1$ in the order they are written in the input. If there are many solutions, print any of them.


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

Output
2 2
1 3 
Input
5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3

Output
3 3
3 4 7 


-----Note-----

There are two simple cycles in the first example: $1 \rightarrow 5 \rightarrow 2 \rightarrow 1$ and $2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$. One traffic controller can only reverse the road $2 \rightarrow 1$ and he can't destroy the second cycle by himself. Two traffic controllers can reverse roads $2 \rightarrow 1$ and $2 \rightarrow 3$ which would satisfy the condition.

In the second example one traffic controller can't destroy the cycle $ 1 \rightarrow 3 \rightarrow 2 \rightarrow 1 $. With the help of three controllers we can, for example, reverse roads $1 \rightarrow 3$ ,$ 2 \rightarrow 4$, $1 \rightarrow 5$.
user: User ainta has a permutation p_1, p_2, ..., p_{n}. As the New Year is coming, he wants to make his permutation as pretty as possible.

Permutation a_1, a_2, ..., a_{n} is prettier than permutation b_1, b_2, ..., b_{n}, if and only if there exists an integer k (1 ≤ k ≤ n) where a_1 = b_1, a_2 = b_2, ..., a_{k} - 1 = b_{k} - 1 and a_{k} < b_{k} all holds.

As known, permutation p is so sensitive that it could be only modified by swapping two distinct elements. But swapping two elements is harder than you think. Given an n × n binary matrix A, user ainta can swap the values of p_{i} and p_{j} (1 ≤ i, j ≤ n, i ≠ j) if and only if A_{i}, j = 1.

Given the permutation p and the matrix A, user ainta wants to know the prettiest permutation that he can obtain.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 300) — the size of the permutation p.

The second line contains n space-separated integers p_1, p_2, ..., p_{n} — the permutation p that user ainta has. Each integer between 1 and n occurs exactly once in the given permutation.

Next n lines describe the matrix A. The i-th line contains n characters '0' or '1' and describes the i-th row of A. The j-th character of the i-th line A_{i}, j is the element on the intersection of the i-th row and the j-th column of A. It is guaranteed that, for all integers i, j where 1 ≤ i < j ≤ n, A_{i}, j = A_{j}, i holds. Also, for all integers i where 1 ≤ i ≤ n, A_{i}, i = 0 holds.


-----Output-----

In the first and only line, print n space-separated integers, describing the prettiest permutation that can be obtained.


-----Examples-----
Input
7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000

Output
1 2 4 3 6 7 5

Input
5
4 2 1 5 3
00100
00011
10010
01101
01010

Output
1 2 3 4 5



-----Note-----

In the first sample, the swap needed to obtain the prettiest permutation is: (p_1, p_7).

In the second sample, the swaps needed to obtain the prettiest permutation is (p_1, p_3), (p_4, p_5), (p_3, p_4).  [Image] 

A permutation p is a sequence of integers p_1, p_2, ..., p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. The i-th element of the permutation p is denoted as p_{i}. The size of the permutation p is denoted as n.
user: Hongcow is learning to spell! One day, his teacher gives him a word that he needs to learn to spell. Being a dutiful student, he immediately learns how to spell the word.

Hongcow has decided to try to make new words from this one. He starts by taking the word he just learned how to spell, and moves the last character of the word to the beginning of the word. He calls this a cyclic shift. He can apply cyclic shift many times. For example, consecutively applying cyclic shift operation to the word "abracadabra" Hongcow will get words "aabracadabr", "raabracadab" and so on.

Hongcow is now wondering how many distinct words he can generate by doing the cyclic shift arbitrarily many times. The initial string is also counted.


-----Input-----

The first line of input will be a single string s (1 ≤ |s| ≤ 50), the word Hongcow initially learns how to spell. The string s consists only of lowercase English letters ('a'–'z').


-----Output-----

Output a single integer equal to the number of distinct strings that Hongcow can obtain by applying the cyclic shift arbitrarily many times to the given string.


-----Examples-----
Input
abcd

Output
4

Input
bbb

Output
1

Input
yzyz

Output
2



-----Note-----

For the first sample, the strings Hongcow can generate are "abcd", "dabc", "cdab", and "bcda".

For the second sample, no matter how many times Hongcow does the cyclic shift, Hongcow can only generate "bbb".

For the third sample, the two strings Hongcow can generate are "yzyz" and "zyzy".
user: Berland shop sells $n$ kinds of juices. Each juice has its price $c_i$. Each juice includes some set of vitamins in it. There are three types of vitamins: vitamin "A", vitamin "B" and vitamin "C". Each juice can contain one, two or all three types of vitamins in it.

Petya knows that he needs all three types of vitamins to stay healthy. What is the minimum total price of juices that Petya has to buy to obtain all three vitamins? Petya obtains some vitamin if he buys at least one juice containing it and drinks it.


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 1\,000)$ — the number of juices.

Each of the next $n$ lines contains an integer $c_i$ $(1 \le c_i \le 100\,000)$ and a string $s_i$ — the price of the $i$-th juice and the vitamins it contains. String $s_i$ contains from $1$ to $3$ characters, and the only possible characters are "A", "B" and "C". It is guaranteed that each letter appears no more than once in each string $s_i$. The order of letters in strings $s_i$ is arbitrary.


-----Output-----

Print -1 if there is no way to obtain all three vitamins. Otherwise print the minimum total price of juices that Petya has to buy to obtain all three vitamins.


-----Examples-----
Input
4
5 C
6 B
16 BAC
4 A

Output
15

Input
2
10 AB
15 BA

Output
-1

Input
5
10 A
9 BC
11 CA
4 A
5 B

Output
13

Input
6
100 A
355 BCA
150 BC
160 AC
180 B
190 CA

Output
250

Input
2
5 BA
11 CB

Output
16



-----Note-----

In the first example Petya buys the first, the second and the fourth juice. He spends $5 + 6 + 4 = 15$ and obtains all three vitamins. He can also buy just the third juice and obtain three vitamins, but its cost is $16$, which isn't optimal.

In the second example Petya can't obtain all three vitamins, as no juice contains vitamin "C".
user: Основой любой социальной сети является отношение дружбы между двумя пользователями в том или ином смысле. В одной известной социальной сети дружба симметрична, то есть если a является другом b, то b также является другом a. 

В этой же сети есть функция, которая демонстрирует множество людей, имеющих высокую вероятность быть знакомыми для пользователя. Эта функция работает следующим образом. Зафиксируем пользователя x. Пусть некоторый другой человек y, не являющийся другом x на текущий момент, является другом не менее, чем для k% друзей x. Тогда он является предполагаемым другом для x.

У каждого человека в социальной сети есть свой уникальный идентификатор — это целое число от 1 до 10^9. Вам дан список пар пользователей, являющихся друзьями. Определите для каждого упомянутого пользователя множество его предполагаемых друзей.


-----Входные данные-----

В первой строке следуют два целых числа m и k (1 ≤ m ≤ 100, 0 ≤ k ≤ 100) — количество пар друзей и необходимый процент общих друзей для того, чтобы считаться предполагаемым другом.

В последующих m строках записано по два числа a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ 10^9, a_{i} ≠ b_{i}), обозначающих идентификаторы пользователей, являющихся друзьями. 

Гарантируется, что каждая пара людей фигурирует в списке не более одного раза.


-----Выходные данные-----

Для всех упомянутых людей в порядке возрастания id выведите информацию о предполагаемых друзьях. Информация должна иметь вид "id:  k id_1 id_2 ... id_{k}", где id — это id самого человека, k — количество его предполагаемых друзей, а id_1, id_2, ..., id_{k} — идентификаторы его предполагаемых друзей в возрастающем порядке. 


-----Примеры-----
Входные данные
5 51
10 23
23 42
39 42
10 39
39 58

Выходные данные
10: 1 42
23: 1 39
39: 1 23
42: 1 10
58: 2 10 42

Входные данные
5 100
1 2
1 3
1 4
2 3
2 4

Выходные данные
1: 0
2: 0
3: 1 4
4: 1 3
user: As it's the first of April, Heidi is suspecting that the news she reads today are fake, and she does not want to look silly in front of all the contestants. She knows that a newspiece is fake if it contains heidi as a subsequence. Help Heidi assess whether the given piece is true, but please be discreet about it...


-----Input-----

The first and only line of input contains a single nonempty string s of length at most 1000 composed of lowercase letters (a-z).


-----Output-----

Output YES if the string s contains heidi as a subsequence and NO otherwise.


-----Examples-----
Input
abcheaibcdi

Output
YES
Input
hiedi

Output
NO


-----Note-----

A string s contains another string p as a subsequence if it is possible to delete some characters from s and obtain p.
user: Limak is a little polar bear. He likes nice strings — strings of length n, consisting of lowercase English letters only.

The distance between two letters is defined as the difference between their positions in the alphabet. For example, $\operatorname{dist}(c, e) = \operatorname{dist}(e, c) = 2$, and $\operatorname{dist}(a, z) = \operatorname{dist}(z, a) = 25$.

Also, the distance between two nice strings is defined as the sum of distances of corresponding letters. For example, $\operatorname{dist}(a f, d b) = \operatorname{dist}(a, d) + \operatorname{dist}(f, b) = 3 + 4 = 7$, and $\text{dist(bear, roar)} = 16 + 10 + 0 + 0 = 26$.

Limak gives you a nice string s and an integer k. He challenges you to find any nice string s' that $\operatorname{dist}(s, s^{\prime}) = k$. Find any s' satisfying the given conditions, or print "-1" if it's impossible to do so.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^6).

The second line contains a string s of length n, consisting of lowercase English letters.


-----Output-----

If there is no string satisfying the given conditions then print "-1" (without the quotes).

Otherwise, print any nice string s' that $\operatorname{dist}(s, s^{\prime}) = k$.


-----Examples-----
Input
4 26
bear

Output
roar
Input
2 7
af

Output
db

Input
3 1000
hey

Output
-1
user: An n × n square matrix is special, if:  it is binary, that is, each cell contains either a 0, or a 1;  the number of ones in each row and column equals 2. 

You are given n and the first m rows of the matrix. Print the number of special n × n matrices, such that the first m rows coincide with the given ones.

As the required value can be rather large, print the remainder after dividing the value by the given number mod.


-----Input-----

The first line of the input contains three integers n, m, mod (2 ≤ n ≤ 500, 0 ≤ m ≤ n, 2 ≤ mod ≤ 10^9). Then m lines follow, each of them contains n characters — the first rows of the required special matrices. Each of these lines contains exactly two characters '1', the rest characters are '0'. Each column of the given m × n table contains at most two numbers one.


-----Output-----

Print the remainder after dividing the required value by number mod.


-----Examples-----
Input
3 1 1000
011

Output
2

Input
4 4 100500
0110
1010
0101
1001

Output
1



-----Note-----

For the first test the required matrices are: 

011

101

110



011

110

101



In the second test the required matrix is already fully given, so the answer is 1.
user: Vasya likes to solve equations. Today he wants to solve $(x~\mathrm{div}~k) \cdot (x \bmod k) = n$, where $\mathrm{div}$ and $\mathrm{mod}$ stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, $k$ and $n$ are positive integer parameters, and $x$ is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible $x$. Can you help him?


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 10^6$, $2 \leq k \leq 1000$).


-----Output-----

Print a single integer $x$ — the smallest positive integer solution to $(x~\mathrm{div}~k) \cdot (x \bmod k) = n$. It is guaranteed that this equation has at least one positive integer solution.


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

Output
11

Input
1 2

Output
3

Input
4 6

Output
10



-----Note-----

The result of integer division $a~\mathrm{div}~b$ is equal to the largest integer $c$ such that $b \cdot c \leq a$. $a$ modulo $b$ (shortened $a \bmod b$) is the only integer $c$ such that $0 \leq c < b$, and $a - c$ is divisible by $b$.

In the first sample, $11~\mathrm{div}~3 = 3$ and $11 \bmod 3 = 2$. Since $3 \cdot 2 = 6$, then $x = 11$ is a solution to $(x~\mathrm{div}~3) \cdot (x \bmod 3) = 6$. One can see that $19$ is the only other positive integer solution, hence $11$ is the smallest one.
user: Vladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips:

Vladik is at initial train station, and now n people (including Vladik) want to get on the train. They are already lined up in some order, and for each of them the city code a_{i} is known (the code of the city in which they are going to).

Train chief selects some number of disjoint segments of the original sequence of people (covering entire sequence by segments is not necessary). People who are in the same segment will be in the same train carriage. The segments are selected in such way that if at least one person travels to the city x, then all people who are going to city x should be in the same railway carriage. This means that they can’t belong to different segments. Note, that all people who travel to the city x, either go to it and in the same railway carriage, or do not go anywhere at all.

Comfort of a train trip with people on segment from position l to position r is equal to XOR of all distinct codes of cities for people on the segment from position l to position r. XOR operation also known as exclusive OR.

Total comfort of a train trip is equal to sum of comfort for each segment.

Help Vladik to know maximal possible total comfort.


-----Input-----

First line contains single integer n (1 ≤ n ≤ 5000) — number of people.

Second line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 5000), where a_{i} denotes code of the city to which i-th person is going.


-----Output-----

The output should contain a single integer — maximal possible total comfort.


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

Output
14

Input
9
5 1 3 1 5 2 4 2 5

Output
9



-----Note-----

In the first test case best partition into segments is: [4, 4] [2, 5, 2] [3], answer is calculated as follows: 4 + (2 xor 5) + 3 = 4 + 7 + 3 = 14

In the second test case best partition into segments is: 5 1 [3] 1 5 [2, 4, 2] 5, answer calculated as follows: 3 + (2 xor 4) = 3 + 6 = 9.
user: Given is a directed graph G with N vertices and M edges.

The vertices are numbered 1 to N, and the i-th edge is directed from Vertex A_i to Vertex B_i.

It is guaranteed that the graph contains no self-loops or multiple edges.
Determine whether there exists an induced subgraph (see Notes) of G such that the in-degree and out-degree of every vertex are both 1. If the answer is yes, show one such subgraph.

Here the null graph is not considered as a subgraph.

-----Notes-----
For a directed graph G = (V, E), we call a directed graph G' = (V', E') satisfying the following conditions an induced subgraph of G:
 - V' is a (non-empty) subset of V.
 - E' is the set of all the edges in E that have both endpoints in V'.

-----Constraints-----
 - 1 \leq N \leq 1000
 - 0 \leq M \leq 2000
 - 1 \leq A_i,B_i \leq N
 - A_i \neq B_i
 - All pairs (A_i, B_i) are distinct.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
A_2 B_2
:
A_M B_M

-----Output-----
If there is no induced subgraph of G that satisfies the condition, print -1.
Otherwise, print an induced subgraph of G that satisfies the condition, in the following format:
K
v_1
v_2
:
v_K

This represents the induced subgraph of G with K vertices whose vertex set is \{v_1, v_2, \ldots, v_K\}. (The order of v_1, v_2, \ldots, v_K does not matter.)
If there are multiple subgraphs of G that satisfy the condition, printing any of them is accepted.

-----Sample Input-----
4 5
1 2
2 3
2 4
4 1
4 3

-----Sample Output-----
3
1
2
4

The induced subgraph of G whose vertex set is \{1, 2, 4\} has the edge set \{(1, 2), (2, 4), (4, 1)\}. The in-degree and out-degree of every vertex in this graph are both 1.
user: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.
Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.
You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K].
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.
 - When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.
To help Tak, find the number of ways to go to Cell N, modulo 998244353.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq K \leq \min(N, 10)
 - 1 \leq L_i \leq R_i \leq N
 - [L_i, R_i] and [L_j, R_j] do not intersect (i \neq j) 
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
L_1 R_1
L_2 R_2
:
L_K R_K

-----Output-----
Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

-----Sample Input-----
5 2
1 1
3 4

-----Sample Output-----
4

The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.
There are 4 possible ways to get to Cell 5:
 - 1 \to 2 \to 3 \to 4 \to 5,
 - 1 \to 2 \to 5,
 - 1 \to 4 \to 5 and
 - 1 \to 5.