meetforever/GRPO_CL huggingface dataset:
user: Chilly Willy loves playing with numbers. He only knows prime numbers that are digits yet. These numbers are 2, 3, 5 and 7. But Willy grew rather bored of such numbers, so he came up with a few games that were connected with them.

Chilly Willy wants to find the minimum number of length n, such that it is simultaneously divisible by all numbers Willy already knows (2, 3, 5 and 7). Help him with that.

A number's length is the number of digits in its decimal representation without leading zeros.


-----Input-----

A single input line contains a single integer n (1 ≤ n ≤ 10^5).


-----Output-----

Print a single integer — the answer to the problem without leading zeroes, or "-1" (without the quotes), if the number that meet the problem condition does not exist.


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

Output
-1

Input
5

Output
10080
user: You are given an array a_1, a_2, ..., a_{n} consisting of n integers, and an integer k. You have to split the array into exactly k non-empty subsegments. You'll then compute the minimum integer on each subsegment, and take the maximum integer over the k obtained minimums. What is the maximum possible integer you can get?

Definitions of subsegment and array splitting are given in notes.


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤  10^5) — the size of the array a and the number of subsegments you have to split the array to.

The second line contains n integers a_1,  a_2,  ...,  a_{n} ( - 10^9  ≤  a_{i} ≤  10^9).


-----Output-----

Print single integer — the maximum possible integer you can get if you split the array into k non-empty subsegments and take maximum of minimums on the subsegments.


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

Output
5

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

Output
-5



-----Note-----

A subsegment [l,  r] (l ≤ r) of array a is the sequence a_{l},  a_{l} + 1,  ...,  a_{r}.

Splitting of array a of n elements into k subsegments [l_1, r_1], [l_2, r_2], ..., [l_{k}, r_{k}] (l_1 = 1, r_{k} = n, l_{i} = r_{i} - 1 + 1 for all i > 1) is k sequences (a_{l}_1, ..., a_{r}_1), ..., (a_{l}_{k}, ..., a_{r}_{k}).

In the first example you should split the array into subsegments [1, 4] and [5, 5] that results in sequences (1, 2, 3, 4) and (5). The minimums are min(1, 2, 3, 4) = 1 and min(5) = 5. The resulting maximum is max(1, 5) = 5. It is obvious that you can't reach greater result.

In the second example the only option you have is to split the array into one subsegment [1, 5], that results in one sequence ( - 4,  - 5,  - 3,  - 2,  - 1). The only minimum is min( - 4,  - 5,  - 3,  - 2,  - 1) =  - 5. The resulting maximum is  - 5.
user: Sean is trying to save a large file to a USB flash drive. He has n USB flash drives with capacities equal to a_1, a_2, ..., a_{n} megabytes. The file size is equal to m megabytes. 

Find the minimum number of USB flash drives needed to write Sean's file, if he can split the file between drives.


-----Input-----

The first line contains positive integer n (1 ≤ n ≤ 100) — the number of USB flash drives.

The second line contains positive integer m (1 ≤ m ≤ 10^5) — the size of Sean's file.

Each of the next n lines contains positive integer a_{i} (1 ≤ a_{i} ≤ 1000) — the sizes of USB flash drives in megabytes.

It is guaranteed that the answer exists, i. e. the sum of all a_{i} is not less than m.


-----Output-----

Print the minimum number of USB flash drives to write Sean's file, if he can split the file between drives.


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

Output
2

Input
3
6
2
3
2

Output
3

Input
2
5
5
10

Output
1



-----Note-----

In the first example Sean needs only two USB flash drives — the first and the third.

In the second example Sean needs all three USB flash drives.

In the third example Sean needs only one USB flash drive and he can use any available USB flash drive — the first or the second.
user: Two boys decided to compete in text typing on the site "Key races". During the competition, they have to type a text consisting of s characters. The first participant types one character in v_1 milliseconds and has ping t_1 milliseconds. The second participant types one character in v_2 milliseconds and has ping t_2 milliseconds.

If connection ping (delay) is t milliseconds, the competition passes for a participant as follows:   Exactly after t milliseconds after the start of the competition the participant receives the text to be entered.  Right after that he starts to type it.  Exactly t milliseconds after he ends typing all the text, the site receives information about it. 

The winner is the participant whose information on the success comes earlier. If the information comes from both participants at the same time, it is considered that there is a draw.

Given the length of the text and the information about participants, determine the result of the game.


-----Input-----

The first line contains five integers s, v_1, v_2, t_1, t_2 (1 ≤ s, v_1, v_2, t_1, t_2 ≤ 1000) — the number of characters in the text, the time of typing one character for the first participant, the time of typing one character for the the second participant, the ping of the first participant and the ping of the second participant.


-----Output-----

If the first participant wins, print "First". If the second participant wins, print "Second". In case of a draw print "Friendship".


-----Examples-----
Input
5 1 2 1 2

Output
First

Input
3 3 1 1 1

Output
Second

Input
4 5 3 1 5

Output
Friendship



-----Note-----

In the first example, information on the success of the first participant comes in 7 milliseconds, of the second participant — in 14 milliseconds. So, the first wins.

In the second example, information on the success of the first participant comes in 11 milliseconds, of the second participant — in 5 milliseconds. So, the second wins.

In the third example, information on the success of the first participant comes in 22 milliseconds, of the second participant — in 22 milliseconds. So, it is be a draw.
user: Comrade Dujikov is busy choosing artists for Timofey's birthday and is recieving calls from Taymyr from Ilia-alpinist.

Ilia-alpinist calls every n minutes, i.e. in minutes n, 2n, 3n and so on. Artists come to the comrade every m minutes, i.e. in minutes m, 2m, 3m and so on. The day is z minutes long, i.e. the day consists of minutes 1, 2, ..., z. How many artists should be killed so that there are no artists in the room when Ilia calls? Consider that a call and a talk with an artist take exactly one minute.


-----Input-----

The only string contains three integers — n, m and z (1 ≤ n, m, z ≤ 10^4).


-----Output-----

Print single integer — the minimum number of artists that should be killed so that there are no artists in the room when Ilia calls.


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

Output
10

Input
1 2 5

Output
2

Input
2 3 9

Output
1



-----Note-----

Taymyr is a place in the north of Russia.

In the first test the artists come each minute, as well as the calls, so we need to kill all of them.

In the second test we need to kill artists which come on the second and the fourth minutes.

In the third test — only the artist which comes on the sixth minute.
user: Valera the horse lives on a plane. The Cartesian coordinate system is defined on this plane. Also an infinite spiral is painted on the plane. The spiral consists of segments: [(0, 0), (1, 0)], [(1, 0), (1, 1)], [(1, 1), ( - 1, 1)], [( - 1, 1), ( - 1,  - 1)], [( - 1,  - 1), (2,  - 1)], [(2,  - 1), (2, 2)] and so on. Thus, this infinite spiral passes through each integer point of the plane.

Valera the horse lives on the plane at coordinates (0, 0). He wants to walk along the spiral to point (x, y). Valera the horse has four legs, so he finds turning very difficult. Count how many times he will have to turn if he goes along a spiral from point (0, 0) to point (x, y).


-----Input-----

The first line contains two space-separated integers x and y (|x|, |y| ≤ 100).


-----Output-----

Print a single integer, showing how many times Valera has to turn.


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

Output
0

Input
1 0

Output
0

Input
0 1

Output
2

Input
-1 -1

Output
3
user: As you probably know, Anton goes to school. One of the school subjects that Anton studies is Bracketology. On the Bracketology lessons students usually learn different sequences that consist of round brackets (characters "(" and ")" (without quotes)).

On the last lesson Anton learned about the regular simple bracket sequences (RSBS). A bracket sequence s of length n is an RSBS if the following conditions are met:

  It is not empty (that is n ≠ 0).  The length of the sequence is even.  First $\frac{n}{2}$ charactes of the sequence are equal to "(".  Last $\frac{n}{2}$ charactes of the sequence are equal to ")". 

For example, the sequence "((()))" is an RSBS but the sequences "((())" and "(()())" are not RSBS.

Elena Ivanovna, Anton's teacher, gave him the following task as a homework. Given a bracket sequence s. Find the number of its distinct subsequences such that they are RSBS. Note that a subsequence of s is a string that can be obtained from s by deleting some of its elements. Two subsequences are considered distinct if distinct sets of positions are deleted.

Because the answer can be very big and Anton's teacher doesn't like big numbers, she asks Anton to find the answer modulo 10^9 + 7.

Anton thought of this task for a very long time, but he still doesn't know how to solve it. Help Anton to solve this task and write a program that finds the answer for it!


-----Input-----

The only line of the input contains a string s — the bracket sequence given in Anton's homework. The string consists only of characters "(" and ")" (without quotes). It's guaranteed that the string is not empty and its length doesn't exceed 200 000.


-----Output-----

Output one number — the answer for the task modulo 10^9 + 7.


-----Examples-----
Input
)(()()

Output
6

Input
()()()

Output
7

Input
)))

Output
0



-----Note-----

In the first sample the following subsequences are possible:

  If we delete characters at the positions 1 and 5 (numbering starts with one), we will get the subsequence "(())".  If we delete characters at the positions 1, 2, 3 and 4, we will get the subsequence "()".  If we delete characters at the positions 1, 2, 4 and 5, we will get the subsequence "()".  If we delete characters at the positions 1, 2, 5 and 6, we will get the subsequence "()".  If we delete characters at the positions 1, 3, 4 and 5, we will get the subsequence "()".  If we delete characters at the positions 1, 3, 5 and 6, we will get the subsequence "()". 

The rest of the subsequnces are not RSBS. So we got 6 distinct subsequences that are RSBS, so the answer is 6.
user: Given is a positive integer N. Consider repeatedly applying the operation below on N:
 - First, choose a positive integer z satisfying all of the conditions below:
 - z can be represented as z=p^e, where p is a prime number and e is a positive integer;
 - z divides N;
 - z is different from all integers chosen in previous operations.
 - Then, replace N with N/z.
Find the maximum number of times the operation can be applied.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^{12}

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

-----Output-----
Print the maximum number of times the operation can be applied.

-----Sample Input-----
24

-----Sample Output-----
3

We can apply the operation three times by, for example, making the following choices:
 - Choose z=2 (=2^1). (Now we have N=12.)
 - Choose z=3 (=3^1). (Now we have N=4.)
 - Choose z=4 (=2^2). (Now we have N=1.)
user: Snuke is visiting a shop in Tokyo called 109 to buy some logs.
He wants n logs: one of length 1, one of length 2, ..., and one of length n.
The shop has n+1 logs in stock: one of length 1, one of length 2, \dots, and one of length n+1. Each of these logs is sold for 1 yen (the currency of Japan).
He can cut these logs as many times as he wants after buying them. That is, he can get k logs of length L_1, \dots, L_k from a log of length L, where L = L_1 + \dots + L_k. He can also throw away unwanted logs.
Snuke wants to spend as little money as possible to get the logs he wants.
Find the minimum amount of money needed to get n logs of length 1 to n.

-----Constraints-----
 - 1 \leq n \leq 10^{18}

-----Input-----
Input is given from Standard Input in the following format:
n

-----Output-----
Print the minimum amount of money needed to get n logs of length 1 to n.

-----Sample Input-----
4

-----Sample Output-----
3

One way to get the logs he wants with 3 yen is:
 - Buy logs of length 2, 4, and 5.
 - Cut the log of length 5 into two logs of length 1 each and a log of length 3.
 - Throw away one of the logs of length 1.
user: Let S be the concatenation of 10^{10} copies of the string 110. (For reference, the concatenation of 3 copies of 110 is 110110110.)
We have a string T of length N.
Find the number of times T occurs in S as a contiguous substring.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - T is a string of length N consisting of 0 and 1.

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

-----Output-----
Print the number of times T occurs in S as a contiguous substring.

-----Sample Input-----
4
1011

-----Sample Output-----
9999999999

S is so long, so let us instead count the number of times 1011 occurs in the concatenation of 3 copies of 110, that is, 110110110. We can see it occurs twice:
 - 1 1011 0110
 - 1101 1011 0
user: There are n workers in a company, each of them has a unique id from 1 to n. Exaclty one of them is a chief, his id is s. Each worker except the chief has exactly one immediate superior.

There was a request to each of the workers to tell how how many superiors (not only immediate). Worker's superiors are his immediate superior, the immediate superior of the his immediate superior, and so on. For example, if there are three workers in the company, from which the first is the chief, the second worker's immediate superior is the first, the third worker's immediate superior is the second, then the third worker has two superiors, one of them is immediate and one not immediate. The chief is a superior to all the workers except himself.

Some of the workers were in a hurry and made a mistake. You are to find the minimum number of workers that could make a mistake.


-----Input-----

The first line contains two positive integers n and s (1 ≤ n ≤ 2·10^5, 1 ≤ s ≤ n) — the number of workers and the id of the chief.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n - 1), where a_{i} is the number of superiors (not only immediate) the worker with id i reported about.


-----Output-----

Print the minimum number of workers that could make a mistake.


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

Output
1

Input
5 3
1 0 0 4 1

Output
2



-----Note-----

In the first example it is possible that only the first worker made a mistake. Then:   the immediate superior of the first worker is the second worker,  the immediate superior of the third worker is the first worker,  the second worker is the chief.
user: After playing Neo in the legendary "Matrix" trilogy, Keanu Reeves started doubting himself: maybe we really live in virtual reality? To find if this is true, he needs to solve the following problem.

Let's call a string consisting of only zeroes and ones good if it contains different numbers of zeroes and ones. For example, 1, 101, 0000 are good, while 01, 1001, and 111000 are not good.

We are given a string $s$ of length $n$ consisting of only zeroes and ones. We need to cut $s$ into minimal possible number of substrings $s_1, s_2, \ldots, s_k$ such that all of them are good. More formally, we have to find minimal by number of strings sequence of good strings $s_1, s_2, \ldots, s_k$ such that their concatenation (joining) equals $s$, i.e. $s_1 + s_2 + \dots + s_k = s$.

For example, cuttings 110010 into 110 and 010 or into 11 and 0010 are valid, as 110, 010, 11, 0010 are all good, and we can't cut 110010 to the smaller number of substrings as 110010 isn't good itself. At the same time, cutting of 110010 into 1100 and 10 isn't valid as both strings aren't good. Also, cutting of 110010 into 1, 1, 0010 isn't valid, as it isn't minimal, even though all $3$ strings are good.

Can you help Keanu? We can show that the solution always exists. If there are multiple optimal answers, print any.


-----Input-----

The first line of the input contains a single integer $n$ ($1\le n \le 100$) — the length of the string $s$.

The second line contains the string $s$ of length $n$ consisting only from zeros and ones.


-----Output-----

In the first line, output a single integer $k$ ($1\le k$) — a minimal number of strings you have cut $s$ into.

In the second line, output $k$ strings $s_1, s_2, \ldots, s_k$ separated with spaces. The length of each string has to be positive. Their concatenation has to be equal to $s$ and all of them have to be good.

If there are multiple answers, print any.


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

Output
1
1
Input
2
10

Output
2
1 0
Input
6
100011

Output
2
100 011



-----Note-----

In the first example, the string 1 wasn't cut at all. As it is good, the condition is satisfied.

In the second example, 1 and 0 both are good. As 10 isn't good, the answer is indeed minimal.

In the third example, 100 and 011 both are good. As 100011 isn't good, the answer is indeed minimal.
user: As you know, all the kids in Berland love playing with cubes. Little Petya has n towers consisting of cubes of the same size. Tower with number i consists of a_{i} cubes stacked one on top of the other. Petya defines the instability of a set of towers as a value equal to the difference between the heights of the highest and the lowest of the towers. For example, if Petya built five cube towers with heights (8, 3, 2, 6, 3), the instability of this set is equal to 6 (the highest tower has height 8, the lowest one has height 2). 

The boy wants the instability of his set of towers to be as low as possible. All he can do is to perform the following operation several times: take the top cube from some tower and put it on top of some other tower of his set. Please note that Petya would never put the cube on the same tower from which it was removed because he thinks it's a waste of time. 

Before going to school, the boy will have time to perform no more than k such operations. Petya does not want to be late for class, so you have to help him accomplish this task.


-----Input-----

The first line contains two space-separated positive integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1000) — the number of towers in the given set and the maximum number of operations Petya can perform. The second line contains n space-separated positive integers a_{i} (1 ≤ a_{i} ≤ 10^4) — the towers' initial heights.


-----Output-----

In the first line print two space-separated non-negative integers s and m (m ≤ k). The first number is the value of the minimum possible instability that can be obtained after performing at most k operations, the second number is the number of operations needed for that.

In the next m lines print the description of each operation as two positive integers i and j, each of them lies within limits from 1 to n. They represent that Petya took the top cube from the i-th tower and put in on the j-th one (i ≠ j). Note that in the process of performing operations the heights of some towers can become equal to zero.

If there are multiple correct sequences at which the minimum possible instability is achieved, you are allowed to print any of them.


-----Examples-----
Input
3 2
5 8 5

Output
0 2
2 1
2 3

Input
3 4
2 2 4

Output
1 1
3 2

Input
5 3
8 3 2 6 3

Output
3 3
1 3
1 2
1 3



-----Note-----

In the first sample you need to move the cubes two times, from the second tower to the third one and from the second one to the first one. Then the heights of the towers are all the same and equal to 6.
user: You desperately need to build some string t. For that you've got n more strings s_1, s_2, ..., s_{n}. To build string t, you are allowed to perform exactly |t| (|t| is the length of string t) operations on these strings. Each operation looks like that:  choose any non-empty string from strings s_1, s_2, ..., s_{n};  choose an arbitrary character from the chosen string and write it on a piece of paper;  remove the chosen character from the chosen string. 

Note that after you perform the described operation, the total number of characters in strings s_1, s_2, ..., s_{n} decreases by 1. We are assumed to build string t, if the characters, written on the piece of paper, in the order of performed operations form string t.

There are other limitations, though. For each string s_{i} you know number a_{i} — the maximum number of characters you are allowed to delete from string s_{i}. You also know that each operation that results in deleting a character from string s_{i}, costs i rubles. That is, an operation on string s_1 is the cheapest (it costs 1 ruble), and the operation on string s_{n} is the most expensive one (it costs n rubles).

Your task is to count the minimum amount of money (in rubles) you will need to build string t by the given rules. Consider the cost of building string t to be the sum of prices of the operations you use.


-----Input-----

The first line of the input contains string t — the string that you need to build.

The second line contains a single integer n (1 ≤ n ≤ 100) — the number of strings to which you are allowed to apply the described operation. Each of the next n lines contains a string and an integer. The i-th line contains space-separated string s_{i} and integer a_{i} (0 ≤ a_{i} ≤ 100). Number a_{i} represents the maximum number of characters that can be deleted from string s_{i}.

All strings in the input only consist of lowercase English letters. All strings are non-empty. The lengths of all strings do not exceed 100 characters.


-----Output-----

Print a single number — the minimum money (in rubles) you need in order to build string t. If there is no solution, print -1.


-----Examples-----
Input
bbaze
3
bzb 2
aeb 3
ba 10

Output
8

Input
abacaba
4
aba 2
bcc 1
caa 2
bbb 5

Output
18

Input
xyz
4
axx 8
za 1
efg 4
t 1

Output
-1



-----Note-----

Notes to the samples:

In the first sample from the first string you should take characters "b" and "z" with price 1 ruble, from the second string characters "a", "e" и "b" with price 2 rubles. The price of the string t in this case is 2·1 + 3·2 = 8.

In the second sample from the first string you should take two characters "a" with price 1 ruble, from the second string character "c" with price 2 rubles, from the third string two characters "a" with price 3 rubles, from the fourth string two characters "b" with price 4 rubles. The price of the string t in this case is 2·1 + 1·2 + 2·3 + 2·4 = 18.

In the third sample the solution doesn't exist because there is no character "y" in given strings.