meetforever/GRPO_CL huggingface dataset:
user: The end of the school year is near and Ms. Manana, the teacher, will soon have to say goodbye to a yet another class. She decided to prepare a goodbye present for her n students and give each of them a jigsaw puzzle (which, as wikipedia states, is a tiling puzzle that requires the assembly of numerous small, often oddly shaped, interlocking and tessellating pieces).

The shop assistant told the teacher that there are m puzzles in the shop, but they might differ in difficulty and size. Specifically, the first jigsaw puzzle consists of f_1 pieces, the second one consists of f_2 pieces and so on.

Ms. Manana doesn't want to upset the children, so she decided that the difference between the numbers of pieces in her presents must be as small as possible. Let A be the number of pieces in the largest puzzle that the teacher buys and B be the number of pieces in the smallest such puzzle. She wants to choose such n puzzles that A - B is minimum possible. Help the teacher and find the least possible value of A - B.


-----Input-----

The first line contains space-separated integers n and m (2 ≤ n ≤ m ≤ 50). The second line contains m space-separated integers f_1, f_2, ..., f_{m} (4 ≤ f_{i} ≤ 1000) — the quantities of pieces in the puzzles sold in the shop.


-----Output-----

Print a single integer — the least possible difference the teacher can obtain.


-----Examples-----
Input
4 6
10 12 10 7 5 22

Output
5



-----Note-----

Sample 1. The class has 4 students. The shop sells 6 puzzles. If Ms. Manana buys the first four puzzles consisting of 10, 12, 10 and 7 pieces correspondingly, then the difference between the sizes of the largest and the smallest puzzle will be equal to 5. It is impossible to obtain a smaller difference. Note that the teacher can also buy puzzles 1, 3, 4 and 5 to obtain the difference 5.
user: A group of n schoolboys decided to ride bikes. As nobody of them has a bike, the boys need to rent them.

The renting site offered them m bikes. The renting price is different for different bikes, renting the j-th bike costs p_{j} rubles.

In total, the boys' shared budget is a rubles. Besides, each of them has his own personal money, the i-th boy has b_{i} personal rubles. The shared budget can be spent on any schoolchildren arbitrarily, but each boy's personal money can be spent on renting only this boy's bike.

Each boy can rent at most one bike, one cannot give his bike to somebody else.

What maximum number of schoolboys will be able to ride bikes? What minimum sum of personal money will they have to spend in total to let as many schoolchildren ride bikes as possible?


-----Input-----

The first line of the input contains three integers n, m and a (1 ≤ n, m ≤ 10^5; 0 ≤ a ≤ 10^9). The second line contains the sequence of integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^4), where b_{i} is the amount of the i-th boy's personal money. The third line contains the sequence of integers p_1, p_2, ..., p_{m} (1 ≤ p_{j} ≤ 10^9), where p_{j} is the price for renting the j-th bike.


-----Output-----

Print two integers r and s, where r is the maximum number of schoolboys that can rent a bike and s is the minimum total personal money needed to rent r bikes. If the schoolchildren cannot rent any bikes, then r = s = 0.


-----Examples-----
Input
2 2 10
5 5
7 6

Output
2 3

Input
4 5 2
8 1 1 2
6 3 7 5 2

Output
3 8



-----Note-----

In the first sample both schoolchildren can rent a bike. For instance, they can split the shared budget in half (5 rubles each). In this case one of them will have to pay 1 ruble from the personal money and the other one will have to pay 2 rubles from the personal money. In total, they spend 3 rubles of their personal money. This way of distribution of money minimizes the amount of spent personal money.
user: Let's call a number k-good if it contains all digits not exceeding k (0, ..., k). You've got a number k and an array a containing n numbers. Find out how many k-good numbers are in a (count each number every time it occurs in array a).


-----Input-----

The first line contains integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 9). The i-th of the following n lines contains integer a_{i} without leading zeroes (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single integer — the number of k-good numbers in a.


-----Examples-----
Input
10 6
1234560
1234560
1234560
1234560
1234560
1234560
1234560
1234560
1234560
1234560

Output
10

Input
2 1
1
10

Output
1
user: Little Tanya decided to present her dad a postcard on his Birthday. She has already created a message — string s of length n, consisting of uppercase and lowercase English letters. Tanya can't write yet, so she found a newspaper and decided to cut out the letters and glue them into the postcard to achieve string s. The newspaper contains string t, consisting of uppercase and lowercase English letters. We know that the length of string t greater or equal to the length of the string s.

The newspaper may possibly have too few of some letters needed to make the text and too many of some other letters. That's why Tanya wants to cut some n letters out of the newspaper and make a message of length exactly n, so that it looked as much as possible like s. If the letter in some position has correct value and correct letter case (in the string s and in the string that Tanya will make), then she shouts joyfully "YAY!", and if the letter in the given position has only the correct value but it is in the wrong case, then the girl says "WHOOPS".

Tanya wants to make such message that lets her shout "YAY!" as much as possible. If there are multiple ways to do this, then her second priority is to maximize the number of times she says "WHOOPS". Your task is to help Tanya make the message.


-----Input-----

The first line contains line s (1 ≤ |s| ≤ 2·10^5), consisting of uppercase and lowercase English letters — the text of Tanya's message.

The second line contains line t (|s| ≤ |t| ≤ 2·10^5), consisting of uppercase and lowercase English letters — the text written in the newspaper.

Here |a| means the length of the string a.


-----Output-----

Print two integers separated by a space:  the first number is the number of times Tanya shouts "YAY!" while making the message,  the second number is the number of times Tanya says "WHOOPS" while making the message. 


-----Examples-----
Input
AbC
DCbA

Output
3 0

Input
ABC
abc

Output
0 3

Input
abacaba
AbaCaBA

Output
3 4
user: Bob has a string $s$ consisting of lowercase English letters. He defines $s'$ to be the string after removing all "a" characters from $s$ (keeping all other characters in the same order). He then generates a new string $t$ by concatenating $s$ and $s'$. In other words, $t=s+s'$ (look at notes for an example).

You are given a string $t$. Your task is to find some $s$ that Bob could have used to generate $t$. It can be shown that if an answer exists, it will be unique.


-----Input-----

The first line of input contains a string $t$ ($1 \leq |t| \leq 10^5$) consisting of lowercase English letters.


-----Output-----

Print a string $s$ that could have generated $t$. It can be shown if an answer exists, it is unique. If no string exists, print ":(" (without double quotes, there is no space between the characters).


-----Examples-----
Input
aaaaa

Output
aaaaa

Input
aacaababc

Output
:(

Input
ababacacbbcc

Output
ababacac

Input
baba

Output
:(



-----Note-----

In the first example, we have $s = $ "aaaaa", and $s' = $ "".

In the second example, no such $s$ can work that will generate the given $t$.

In the third example, we have $s = $ "ababacac", and $s' = $ "bbcc", and $t = s + s' = $ "ababacacbbcc".
user: Stepan has a very big positive integer.

Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they do not have leading zeros). Let's call such shifts as good shifts. For example, for the integer 10203 the good shifts are the integer itself 10203 and integers 20310 and 31020.

Stepan wants to know the minimum remainder of the division by the given number m among all good shifts. Your task is to determine the minimum remainder of the division by m.


-----Input-----

The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.

The second line contains the integer m (2 ≤ m ≤ 10^8) — the number by which Stepan divides good shifts of his integer.


-----Output-----

Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number m.


-----Examples-----
Input
521
3

Output
2

Input
1001
5

Output
0

Input
5678901234567890123456789
10000

Output
123



-----Note-----

In the first example all good shifts of the integer 521 (good shifts are equal to 521, 215 and 152) has same remainder 2 when dividing by 3.

In the second example there are only two good shifts: the Stepan's integer itself and the shift by one position to the right. The integer itself is 1001 and the remainder after dividing it by 5 equals 1. The shift by one position to the right equals to 1100 and the remainder after dividing it by 5 equals 0, which is the minimum possible remainder.
user: Iahub is training for the IOI. What is a better way to train than playing a Zuma-like game? 

There are n balls put in a row. Each ball is colored in one of k colors. Initially the row doesn't contain three or more contiguous balls with the same color. Iahub has a single ball of color x. He can insert his ball at any position in the row (probably, between two other balls). If at any moment there are three or more contiguous balls of the same color in the row, they are destroyed immediately. This rule is applied multiple times, until there are no more sets of 3 or more contiguous balls of the same color. 

For example, if Iahub has the row of balls [black, black, white, white, black, black] and a white ball, he can insert the ball between two white balls. Thus three white balls are destroyed, and then four black balls become contiguous, so all four balls are destroyed. The row will not contain any ball in the end, so Iahub can destroy all 6 balls.

Iahub wants to destroy as many balls as possible. You are given the description of the row of balls, and the color of Iahub's ball. Help Iahub train for the IOI by telling him the maximum number of balls from the row he can destroy.


-----Input-----

The first line of input contains three integers: n (1 ≤ n ≤ 100), k (1 ≤ k ≤ 100) and x (1 ≤ x ≤ k). The next line contains n space-separated integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ k). Number c_{i} means that the i-th ball in the row has color c_{i}.

It is guaranteed that the initial row of balls will never contain three or more contiguous balls of the same color. 


-----Output-----

Print a single integer — the maximum number of balls Iahub can destroy.


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

Output
6

Input
1 1 1
1

Output
0
user: A country has n cities. Initially, there is no road in the country. One day, the king decides to construct some roads connecting pairs of cities. Roads can be traversed either way. He wants those roads to be constructed in such a way that it is possible to go from each city to any other city by traversing at most two roads. You are also given m pairs of cities — roads cannot be constructed between these pairs of cities.

Your task is to construct the minimum number of roads that still satisfy the above conditions. The constraints will guarantee that this is always possible.


-----Input-----

The first line consists of two integers n and m $(1 \leq n \leq 10^{3}, 0 \leq m < \frac{n}{2})$.

Then m lines follow, each consisting of two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}), which means that it is not possible to construct a road connecting cities a_{i} and b_{i}. Consider the cities are numbered from 1 to n.

It is guaranteed that every pair of cities will appear at most once in the input.


-----Output-----

You should print an integer s: the minimum number of roads that should be constructed, in the first line. Then s lines should follow, each consisting of two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}), which means that a road should be constructed between cities a_{i} and b_{i}.

If there are several solutions, you may print any of them.


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

Output
3
1 2
4 2
2 3



-----Note-----

This is one possible solution of the example:  [Image] 

These are examples of wrong solutions: [Image]  The above solution is wrong because it doesn't use the minimum number of edges (4 vs 3). In addition, it also tries to construct a road between cities 1 and 3, while the input specifies that it is not allowed to construct a road between the pair. [Image]  The above solution is wrong because you need to traverse at least 3 roads to go from city 1 to city 3, whereas in your country it must be possible to go from any city to another by traversing at most 2 roads. [Image]  Finally, the above solution is wrong because it must be possible to go from any city to another, whereas it is not possible in this country to go from city 1 to 3, 2 to 3, and 4 to 3.
user: One day Vasya was on a physics practical, performing the task on measuring the capacitance. He followed the teacher's advice and did as much as n measurements, and recorded the results in the notebook. After that he was about to show the results to the teacher, but he remembered that at the last lesson, the teacher had made his friend Petya redo the experiment because the largest and the smallest results differed by more than two times. Vasya is lazy, and he does not want to redo the experiment. He wants to do the task and go home play computer games. So he decided to cheat: before Vasya shows the measurements to the teacher, he will erase some of them, so as to make the largest and the smallest results of the remaining measurements differ in no more than two times. In other words, if the remaining measurements have the smallest result x, and the largest result y, then the inequality y ≤ 2·x must fulfill. Of course, to avoid the teacher's suspicion, Vasya wants to remove as few measurement results as possible from his notes.

Help Vasya, find what minimum number of measurement results he will have to erase from his notes so that the largest and the smallest of the remaining results of the measurements differed in no more than two times.


-----Input-----

The first line contains integer n (2 ≤ n ≤ 10^5) — the number of measurements Vasya made. The second line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 5000) — the results of the measurements. The numbers on the second line are separated by single spaces.


-----Output-----

Print a single integer — the minimum number of results Vasya will have to remove.


-----Examples-----
Input
6
4 5 3 8 3 7

Output
2

Input
4
4 3 2 4

Output
0



-----Note-----

In the first sample you can remove the fourth and the sixth measurement results (values 8 and 7). Then the maximum of the remaining values will be 5, and the minimum one will be 3. Or else, you can remove the third and fifth results (both equal 3). After that the largest remaining result will be 8, and the smallest one will be 4.
user: You are given $n$ segments on a Cartesian plane. Each segment's endpoints have integer coordinates. Segments can intersect with each other. No two segments lie on the same line.

Count the number of distinct points with integer coordinates, which are covered by at least one segment.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of segments.

Each of the next $n$ lines contains four integers $Ax_i, Ay_i, Bx_i, By_i$ ($-10^6 \le Ax_i, Ay_i, Bx_i, By_i \le 10^6$) — the coordinates of the endpoints $A$, $B$ ($A \ne B$) of the $i$-th segment.

It is guaranteed that no two segments lie on the same line.


-----Output-----

Print a single integer — the number of distinct points with integer coordinates, which are covered by at least one segment.


-----Examples-----
Input
9
0 0 4 4
-1 5 4 0
4 0 4 4
5 2 11 2
6 1 6 7
5 6 11 6
10 1 10 7
7 0 9 8
10 -1 11 -1

Output
42

Input
4
-1 2 1 2
-1 0 1 0
-1 0 0 3
0 3 1 0

Output
7



-----Note-----

The image for the first example: [Image] 

Several key points are marked blue, the answer contains some non-marked points as well.

The image for the second example: [Image]
user: Today Adilbek is taking his probability theory test. Unfortunately, when Adilbek arrived at the university, there had already been a long queue of students wanting to take the same test. Adilbek has estimated that he will be able to start the test only $T$ seconds after coming. 

Fortunately, Adilbek can spend time without revising any boring theorems or formulas. He has an app on this smartphone which contains $n$ Japanese crosswords to solve. Adilbek has decided to solve them all one by one in the order they are listed in the app, without skipping any crossword. For each crossword, a number $t_i$ is given that represents the time it takes an average crossword expert to solve this crossword (the time is given in seconds).

Adilbek is a true crossword expert, but, unfortunately, he is sometimes unlucky in choosing the way to solve the crossword. So, it takes him either $t_i$ seconds or $t_i + 1$ seconds to solve the $i$-th crossword, equiprobably (with probability $\frac{1}{2}$ he solves the crossword in exactly $t_i$ seconds, and with probability $\frac{1}{2}$ he has to spend an additional second to finish the crossword). All these events are independent.

After $T$ seconds pass (or after solving the last crossword, if he manages to do it in less than $T$ seconds), Adilbek closes the app (if he finishes some crossword at the same moment, that crossword is considered solved; otherwise Adilbek does not finish solving the current crossword at all). He thinks it would be an interesting probability theory problem to calculate $E$ — the expected number of crosswords he will be able to solve completely. Can you calculate it? 

Recall that the expected value of a discrete random variable is the probability-weighted average of all possible values — in this problem it means that the expected value of the number of solved crosswords can be calculated as $E = \sum \limits_{i = 0}^{n} i p_i$, where $p_i$ is the probability that Adilbek will solve exactly $i$ crosswords. 

We can represent $E$ as rational fraction $\frac{P}{Q}$ with $Q > 0$. To give the answer, you should print $P \cdot Q^{-1} \bmod (10^9 + 7)$.


-----Input-----

The first line contains two integers $n$ and $T$ ($1 \le n \le 2 \cdot 10^5$, $1 \le T \le 2 \cdot 10^{14}$) — the number of crosswords and the time Adilbek has to spend, respectively.

The second line contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), where $t_i$ is the time it takes a crossword expert to solve the $i$-th crossword.

Note that Adilbek solves the crosswords in the order they are given in the input without skipping any of them.


-----Output-----

Print one integer — the expected value of the number of crosswords Adilbek solves in $T$ seconds, expressed in the form of $P \cdot Q^{-1} \bmod (10^9 + 7)$.


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

Output
750000007

Input
3 5
2 1 2

Output
125000003



-----Note-----

The answer for the first sample is equal to $\frac{14}{8}$.

The answer for the second sample is equal to $\frac{17}{8}$.
user: Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > a_{u}, where a_{u} is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?


-----Input-----

In the first line of the input integer n (1 ≤ n ≤ 10^5) is given — the number of vertices in the tree.

In the second line the sequence of n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) is given, where a_{i} is the number written on vertex i.

The next n - 1 lines describe tree edges: i^{th} of them consists of two integers p_{i} and c_{i} (1 ≤ p_{i} ≤ n,  - 10^9 ≤ c_{i} ≤ 10^9), meaning that there is an edge connecting vertices i + 1 and p_{i} with number c_{i} written on it.


-----Output-----

Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.


-----Example-----
Input
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

Output
5



-----Note-----

The following image represents possible process of removing leaves from the tree:  [Image]
user: Yaroslav thinks that two strings s and w, consisting of digits and having length n are non-comparable if there are two numbers, i and j (1 ≤ i, j ≤ n), such that s_{i} > w_{i} and s_{j} < w_{j}. Here sign s_{i} represents the i-th digit of string s, similarly, w_{j} represents the j-th digit of string w.

A string's template is a string that consists of digits and question marks ("?").

Yaroslav has two string templates, each of them has length n. Yaroslav wants to count the number of ways to replace all question marks by some integers in both templates, so as to make the resulting strings incomparable. Note that the obtained strings can contain leading zeroes and that distinct question marks can be replaced by distinct or the same integers.

Help Yaroslav, calculate the remainder after dividing the described number of ways by 1000000007 (10^9 + 7).


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the length of both templates. The second line contains the first template — a string that consists of digits and characters "?". The string's length equals n. The third line contains the second template in the same format.


-----Output-----

In a single line print the remainder after dividing the answer to the problem by number 1000000007 (10^9 + 7).


-----Examples-----
Input
2
90
09

Output
1

Input
2
11
55

Output
0

Input
5
?????
?????

Output
993531194



-----Note-----

The first test contains no question marks and both strings are incomparable, so the answer is 1.

The second test has no question marks, but the given strings are comparable, so the answer is 0.