meetforever/GRPO_CL huggingface dataset:
user: Vasily the bear has a favorite rectangle, it has one vertex at point (0, 0), and the opposite vertex at point (x, y). Of course, the sides of Vasya's favorite rectangle are parallel to the coordinate axes. 

Vasya also loves triangles, if the triangles have one vertex at point B = (0, 0). That's why today he asks you to find two points A = (x_1, y_1) and C = (x_2, y_2), such that the following conditions hold:  the coordinates of points: x_1, x_2, y_1, y_2 are integers. Besides, the following inequation holds: x_1 < x_2;  the triangle formed by point A, B and C is rectangular and isosceles ($\angle A B C$ is right);  all points of the favorite rectangle are located inside or on the border of triangle ABC;  the area of triangle ABC is as small as possible. 

Help the bear, find the required points. It is not so hard to proof that these points are unique.


-----Input-----

The first line contains two integers x, y ( - 10^9 ≤ x, y ≤ 10^9, x ≠ 0, y ≠ 0).


-----Output-----

Print in the single line four integers x_1, y_1, x_2, y_2 — the coordinates of the required points.


-----Examples-----
Input
10 5

Output
0 15 15 0

Input
-10 5

Output
-15 0 0 15



-----Note-----

[Image]

Figure to the first sample
user: Everyone loves a freebie. Especially students.

It is well-known that if in the night before exam a student opens window, opens the student's record-book and shouts loudly three times "Fly, freebie, fly!" — then flown freebie helps him to pass the upcoming exam.

In the night before the exam on mathematical analysis n students living in dormitory shouted treasured words. The i-th student made a sacrament at the time t_{i}, where t_{i} is the number of seconds elapsed since the beginning of the night.

It is known that the freebie is a capricious and willful lady. That night the freebie was near dormitory only for T seconds. Therefore, if for two students their sacrament times differ for more than T, then the freebie didn't visit at least one of them.

Since all students are optimists, they really want to know what is the maximal number of students visited by the freebie can be.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 100), where n — the number of students shouted "Fly, freebie, fly!" The second line contains n positive integers t_{i} (1 ≤ t_{i} ≤ 1000).

The last line contains integer T (1 ≤ T ≤ 1000) — the time interval during which the freebie was near the dormitory.


-----Output-----

Print a single integer — the largest number of people who will pass exam tomorrow because of the freebie visit.


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

Output
3
user: Now Vasya is taking an exam in mathematics. In order to get a good mark, Vasya needs to guess the matrix that the teacher has constructed!

Vasya knows that the matrix consists of n rows and m columns. For each row, he knows the xor (bitwise excluding or) of the elements in this row. The sequence a_1, a_2, ..., a_{n} denotes the xor of elements in rows with indices 1, 2, ..., n, respectively. Similarly, for each column, he knows the xor of the elements in this column. The sequence b_1, b_2, ..., b_{m} denotes the xor of elements in columns with indices 1, 2, ..., m, respectively.

Help Vasya! Find a matrix satisfying the given constraints or tell him that there is no suitable matrix.


-----Input-----

The first line contains two numbers n and m (2 ≤ n, m ≤ 100) — the dimensions of the matrix.

The second line contains n numbers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9), where a_{i} is the xor of all elements in row i.

The third line contains m numbers b_1, b_2, ..., b_{m} (0 ≤ b_{i} ≤ 10^9), where b_{i} is the xor of all elements in column i.


-----Output-----

If there is no matrix satisfying the given constraints in the first line, output "NO".

Otherwise, on the first line output "YES", and then n rows of m numbers in each c_{i}1, c_{i}2, ... , c_{im} (0 ≤ c_{ij} ≤ 2·10^9) — the description of the matrix.

If there are several suitable matrices, it is allowed to print any of them.


-----Examples-----
Input
2 3
2 9
5 3 13

Output
YES
3 4 5
6 7 8

Input
3 3
1 7 6
2 15 12

Output
NO
user: Ancient Egyptians are known to have used a large set of symbols $\sum$ to write on the walls of the temples. Fafa and Fifa went to one of the temples and found two non-empty words S_1 and S_2 of equal lengths on the wall of temple written one below the other. Since this temple is very ancient, some symbols from the words were erased. The symbols in the set $\sum$ have equal probability for being in the position of any erased symbol.

Fifa challenged Fafa to calculate the probability that S_1 is lexicographically greater than S_2. Can you help Fafa with this task?

You know that $|\sum|= m$, i. e. there were m distinct characters in Egyptians' alphabet, in this problem these characters are denoted by integers from 1 to m in alphabet order. A word x is lexicographically greater than a word y of the same length, if the words are same up to some position, and then the word x has a larger character, than the word y.

We can prove that the probability equals to some fraction $P / Q$, where P and Q are coprime integers, and $Q \neq 0 \text{mod}(10^{9} + 7)$. Print as the answer the value $R = P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$, i. e. such a non-negative integer less than 10^9 + 7, such that $R \cdot Q \equiv P \operatorname{mod}(10^{9} + 7)$, where $a \equiv b \text{mod}(m)$ means that a and b give the same remainders when divided by m.


-----Input-----

The first line contains two integers n and m (1 ≤ n,  m ≤ 10^5) — the length of each of the two words and the size of the alphabet $\sum$, respectively.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ m) — the symbols of S_1. If a_{i} = 0, then the symbol at position i was erased.

The third line contains n integers representing S_2 with the same format as S_1.


-----Output-----

Print the value $P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$, where P and Q are coprime and $P / Q$ is the answer to the problem.


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

Output
500000004

Input
1 2
1
0

Output
0

Input
7 26
0 15 12 9 13 0 14
11 1 0 13 15 12 0

Output
230769233



-----Note-----

In the first sample, the first word can be converted into (1) or (2). The second option is the only one that will make it lexicographically larger than the second word. So, the answer to the problem will be $\frac{1}{2} \operatorname{mod}(10^{9} + 7)$, that is 500000004, because $(500000004 \cdot 2) \operatorname{mod}(10^{9} + 7) = 1$.

In the second example, there is no replacement for the zero in the second word that will make the first one lexicographically larger. So, the answer to the problem is $\frac{0}{1} \operatorname{mod}(10^{9} + 7)$, that is 0.
user: You are given integers N and M.
Consider a sequence a of length N consisting of positive integers such that a_1 + a_2 + ... + a_N = M. Find the maximum possible value of the greatest common divisor of a_1, a_2, ..., a_N.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - N \leq M \leq 10^9

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

-----Output-----
Print the maximum possible value of the greatest common divisor of a sequence a_1, a_2, ..., a_N that satisfies the condition.

-----Sample Input-----
3 14

-----Sample Output-----
2

Consider the sequence (a_1, a_2, a_3) = (2, 4, 8). Their greatest common divisor is 2, and this is the maximum value.
user: You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges.

The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i.

Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).

A connected graph is a graph where there is a path between every pair of different vertices.

Find the number of the edges that are not contained in any shortest path between any pair of different vertices.  

-----Constraints-----
 - 2≤N≤100 
 - N-1≤M≤min(N(N-1)/2,1000) 
 - 1≤a_i,b_i≤N 
 - 1≤c_i≤1000
 - c_i is an integer.
 - The given graph contains neither self-loops nor double edges.
 - The given graph is connected.

-----Input-----
The input is given from Standard Input in the following format:
N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

-----Output-----
Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.

-----Sample Input-----
3 3
1 2 1
1 3 1
2 3 3

-----Sample Output-----
1

In the given graph, the shortest paths between all pairs of different vertices are as follows:
 - The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2, with the length of 1.
 - The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3, with the length of 1.
 - The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1, with the length of 1.
 - The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3, with the length of 2.
 - The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1, with the length of 1.
 - The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2, with the length of 2.
Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3, hence the output should be 1.
user: Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.
Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.
Since the answer can be enormous, print the count modulo 10^9+7.

-----Constraints-----
 - S is a string consisting of digits (0, ..., 9) and ?.
 - 1 \leq |S| \leq 10^5

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

-----Output-----
Print the number of integers satisfying the condition, modulo 10^9+7.

-----Sample Input-----
??2??5

-----Sample Output-----
768

For example, 482305, 002865, and 972665 satisfy the condition.
user: Since the giant heads have appeared in the sky all humanity is in danger, so all Ricks and Mortys from all parallel universes are gathering in groups to find a solution to get rid of them. 

There are n parallel universes participating in this event (n Ricks and n Mortys). I. e. each of n universes has one Rick and one Morty. They're gathering in m groups. Each person can be in many groups and a group can contain an arbitrary number of members.

Ricks and Mortys have registered online in these groups. So, a person can have joined a group more than once (developer of this website hadn't considered this possibility). [Image] 

Summer from universe #1 knows that in each parallel universe (including hers) exactly one of Rick and Morty from that universe is a traitor and is loyal, but no one knows which one. She knows that we are doomed if there's a group such that every member in that group is a traitor (they will plan and destroy the world). 

Summer knows that if there's a possibility that world ends (there's a group where all members are traitors) she should immediately cancel this event. So she wants to know if she should cancel the event. You have to tell her yes if and only if there's at least one scenario (among all 2^{n} possible scenarios, 2 possible scenarios for who a traitor in each universe) such that in that scenario the world will end.


-----Input-----

The first line of input contains two integers n and m (1 ≤ n, m ≤ 10^4) — number of universes and number of groups respectively.

The next m lines contain the information about the groups. i-th of them first contains an integer k (number of times someone joined i-th group, k > 0) followed by k integers v_{i}, 1, v_{i}, 2, ..., v_{i}, k. If v_{i}, j is negative, it means that Rick from universe number  - v_{i}, j has joined this group and otherwise it means that Morty from universe number v_{i}, j has joined it.

Sum of k for all groups does not exceed 10^4.


-----Output-----

In a single line print the answer to Summer's question. Print "YES" if she should cancel the event and "NO" otherwise.


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

Output
YES

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

Output
NO

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

Output
YES



-----Note-----

In the first sample testcase, 1st group only contains the Rick from universe number 3, so in case he's a traitor, then all members of this group are traitors and so Summer should cancel the event.
user: n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins k games in a row. This player becomes the winner.

For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner.


-----Input-----

The first line contains two integers: n and k (2 ≤ n ≤ 500, 2 ≤ k ≤ 10^12) — the number of people and the number of wins.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n) — powers of the player. It's guaranteed that this line contains a valid permutation, i.e. all a_{i} are distinct.


-----Output-----

Output a single integer — power of the winner.


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

Output
2 
Input
4 2
3 1 2 4

Output
3 
Input
6 2
6 5 3 1 2 4

Output
6 
Input
2 10000000000
2 1

Output
2



-----Note-----

Games in the second sample:

3 plays with 1. 3 wins. 1 goes to the end of the line.

3 plays with 2. 3 wins. He wins twice in a row. He becomes the winner.
user: You are given an array $a$ of $n$ integers, where $n$ is odd. You can make the following operation with it:  Choose one of the elements of the array (for example $a_i$) and increase it by $1$ (that is, replace it with $a_i + 1$). 

You want to make the median of the array the largest possible using at most $k$ operations.

The median of the odd-sized array is the middle element after the array is sorted in non-decreasing order. For example, the median of the array $[1, 5, 2, 3, 5]$ is $3$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $n$ is odd, $1 \le k \le 10^9$) — the number of elements in the array and the largest number of operations you can make.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

Print a single integer — the maximum possible median after the operations.


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

Output
5
Input
5 5
1 2 1 1 1

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

Output
5


-----Note-----

In the first example, you can increase the second element twice. Than array will be $[1, 5, 5]$ and it's median is $5$.

In the second example, it is optimal to increase the second number and than increase third and fifth. This way the answer is $3$.

In the third example, you can make four operations: increase first, fourth, sixth, seventh element. This way the array will be $[5, 1, 2, 5, 3, 5, 5]$ and the median will be $5$.
user: You are given a text of single-space separated words, consisting of small and capital Latin letters.

Volume of the word is number of capital letters in the word. Volume of the text is maximum volume of all words in the text.

Calculate the volume of the given text.


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 200) — length of the text.

The second line contains text of single-space separated words s_1, s_2, ..., s_{i}, consisting only of small and capital Latin letters.


-----Output-----

Print one integer number — volume of text.


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

Output
5

Input
24
this is zero answer text

Output
0

Input
24
Harbour Space University

Output
1



-----Note-----

In the first example there is only one word, there are 5 capital letters in it.

In the second example all of the words contain 0 capital letters.
user: Caisa is going to have a party and he needs to buy the ingredients for a big chocolate cake. For that he is going to the biggest supermarket in town.

Unfortunately, he has just s dollars for sugar. But that's not a reason to be sad, because there are n types of sugar in the supermarket, maybe he able to buy one. But that's not all. The supermarket has very unusual exchange politics: instead of cents the sellers give sweets to a buyer as a change. Of course, the number of given sweets always doesn't exceed 99, because each seller maximizes the number of dollars in the change (100 cents can be replaced with a dollar).

Caisa wants to buy only one type of sugar, also he wants to maximize the number of sweets in the change. What is the maximum number of sweets he can get? Note, that Caisa doesn't want to minimize the cost of the sugar, he only wants to get maximum number of sweets as change. 


-----Input-----

The first line contains two space-separated integers n, s (1 ≤ n, s ≤ 100).

The i-th of the next n lines contains two integers x_{i}, y_{i} (1 ≤ x_{i} ≤ 100; 0 ≤ y_{i} < 100), where x_{i} represents the number of dollars and y_{i} the number of cents needed in order to buy the i-th type of sugar.


-----Output-----

Print a single integer representing the maximum number of sweets he can buy, or -1 if he can't buy any type of sugar.


-----Examples-----
Input
5 10
3 90
12 0
9 70
5 50
7 0

Output
50

Input
5 5
10 10
20 20
30 30
40 40
50 50

Output
-1



-----Note-----

In the first test sample Caisa can buy the fourth type of sugar, in such a case he will take 50 sweets as a change.
user: Ralph has a magic field which is divided into n × m blocks. That is to say, there are n rows and m columns on the field. Ralph can put an integer in each block. However, the magic field doesn't always work properly. It works only if the product of integers in each row and each column equals to k, where k is either 1 or -1.

Now Ralph wants you to figure out the number of ways to put numbers in each block in such a way that the magic field works properly. Two ways are considered different if and only if there exists at least one block where the numbers in the first way and in the second way are different. You are asked to output the answer modulo 1000000007 = 10^9 + 7.

Note that there is no range of the numbers to put in the blocks, but we can prove that the answer is not infinity.


-----Input-----

The only line contains three integers n, m and k (1 ≤ n, m ≤ 10^18, k is either 1 or -1).


-----Output-----

Print a single number denoting the answer modulo 1000000007.


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

Output
1

Input
1 3 1

Output
1

Input
3 3 -1

Output
16



-----Note-----

In the first example the only way is to put -1 into the only block.

In the second example the only way is to put 1 into every block.
user: Toad Ivan has $m$ pairs of integers, each integer is between $1$ and $n$, inclusive. The pairs are $(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)$. 

He asks you to check if there exist two integers $x$ and $y$ ($1 \leq x < y \leq n$) such that in each given pair at least one integer is equal to $x$ or $y$.


-----Input-----

The first line contains two space-separated integers $n$ and $m$ ($2 \leq n \leq 300\,000$, $1 \leq m \leq 300\,000$) — the upper bound on the values of integers in the pairs, and the number of given pairs.

The next $m$ lines contain two integers each, the $i$-th of them contains two space-separated integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n, a_i \neq b_i$) — the integers in the $i$-th pair.


-----Output-----

Output "YES" if there exist two integers $x$ and $y$ ($1 \leq x < y \leq n$) such that in each given pair at least one integer is equal to $x$ or $y$. Otherwise, print "NO". You can print each letter in any case (upper or lower).


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

Output
NO

Input
5 4
1 2
2 3
3 4
4 5

Output
YES

Input
300000 5
1 2
1 2
1 2
1 2
1 2

Output
YES



-----Note-----

In the first example, you can't choose any $x$, $y$ because for each such pair you can find a given pair where both numbers are different from chosen integers.

In the second example, you can choose $x=2$ and $y=4$.

In the third example, you can choose $x=1$ and $y=2$.
user: Vasiliy is fond of solving different tasks. Today he found one he wasn't able to solve himself, so he asks you to help.

Vasiliy is given n strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).

To reverse the i-th string Vasiliy has to spent c_{i} units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.

String A is lexicographically smaller than string B if it is shorter than B (|A| < |B|) and is its prefix, or if none of them is a prefix of the other and at the first position where they differ character in A is smaller than the character in B.

For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of strings.

The second line contains n integers c_{i} (0 ≤ c_{i} ≤ 10^9), the i-th of them is equal to the amount of energy Vasiliy has to spent in order to reverse the i-th string. 

Then follow n lines, each containing a string consisting of lowercase English letters. The total length of these strings doesn't exceed 100 000.


-----Output-----

If it is impossible to reverse some of the strings such that they will be located in lexicographical order, print  - 1. Otherwise, print the minimum total amount of energy Vasiliy has to spent.


-----Examples-----
Input
2
1 2
ba
ac

Output
1

Input
3
1 3 1
aa
ba
ac

Output
1

Input
2
5 5
bbb
aaa

Output
-1

Input
2
3 3
aaa
aa

Output
-1



-----Note-----

In the second sample one has to reverse string 2 or string 3. To amount of energy required to reverse the string 3 is smaller.

In the third sample, both strings do not change after reverse and they go in the wrong order, so the answer is  - 1.

In the fourth sample, both strings consists of characters 'a' only, but in the sorted order string "aa" should go before string "aaa", thus the answer is  - 1.
user: Petya studies in a school and he adores Maths. His class has been studying arithmetic expressions. On the last class the teacher wrote three positive integers a, b, c on the blackboard. The task was to insert signs of operations '+' and '*', and probably brackets between the numbers so that the value of the resulting expression is as large as possible. Let's consider an example: assume that the teacher wrote numbers 1, 2 and 3 on the blackboard. Here are some ways of placing signs and brackets:  1+2*3=7  1*(2+3)=5  1*2*3=6  (1+2)*3=9 

Note that you can insert operation signs only between a and b, and between b and c, that is, you cannot swap integers. For instance, in the given sample you cannot get expression (1+3)*2.

It's easy to see that the maximum value that you can obtain is 9.

Your task is: given a, b and c print the maximum value that you can get.


-----Input-----

The input contains three integers a, b and c, each on a single line (1 ≤ a, b, c ≤ 10).


-----Output-----

Print the maximum value of the expression that you can obtain.


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

Output
9

Input
2
10
3

Output
60