meetforever/GRPO_CL huggingface dataset:
user: For the multiset of positive integers $s=\{s_1,s_2,\dots,s_k\}$, define the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of $s$ as follow: $\gcd(s)$ is the maximum positive integer $x$, such that all integers in $s$ are divisible on $x$. $\textrm{lcm}(s)$ is the minimum positive integer $x$, that divisible on all integers from $s$.

For example, $\gcd(\{8,12\})=4,\gcd(\{12,18,6\})=6$ and $\textrm{lcm}(\{4,6\})=12$. Note that for any positive integer $x$, $\gcd(\{x\})=\textrm{lcm}(\{x\})=x$.

Orac has a sequence $a$ with length $n$. He come up with the multiset $t=\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\}$, and asked you to find the value of $\gcd(t)$ for him. In other words, you need to calculate the GCD of LCMs of all pairs of elements in the given sequence.


-----Input-----

The first line contains one integer $n\ (2\le n\le 100\,000)$.

The second line contains $n$ integers, $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 200\,000$).


-----Output-----

Print one integer: $\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})$.


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

Output
1

Input
4
10 24 40 80

Output
40

Input
10
540 648 810 648 720 540 594 864 972 648

Output
54



-----Note-----

For the first example, $t=\{\textrm{lcm}(\{1,1\})\}=\{1\}$, so $\gcd(t)=1$.

For the second example, $t=\{120,40,80,120,240,80\}$, and it's not hard to see that $\gcd(t)=40$.
user: There are many anime that are about "love triangles": Alice loves Bob, and Charlie loves Bob as well, but Alice hates Charlie. You are thinking about an anime which has n characters. The characters are labeled from 1 to n. Every pair of two characters can either mutually love each other or mutually hate each other (there is no neutral state).

You hate love triangles (A-B are in love and B-C are in love, but A-C hate each other), and you also hate it when nobody is in love. So, considering any three characters, you will be happy if exactly one pair is in love (A and B love each other, and C hates both A and B), or if all three pairs are in love (A loves B, B loves C, C loves A).

You are given a list of m known relationships in the anime. You know for sure that certain pairs love each other, and certain pairs hate each other. You're wondering how many ways you can fill in the remaining relationships so you are happy with every triangle. Two ways are considered different if two characters are in love in one way but hate each other in the other. Print this count modulo 1 000 000 007.


-----Input-----

The first line of input will contain two integers n, m (3 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000).

The next m lines will contain the description of the known relationships. The i-th line will contain three integers a_{i}, b_{i}, c_{i}. If c_{i} is 1, then a_{i} and b_{i} are in love, otherwise, they hate each other (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}, $c_{i} \in \{0,1 \}$).

Each pair of people will be described no more than once.


-----Output-----

Print a single integer equal to the number of ways to fill in the remaining pairs so that you are happy with every triangle modulo 1 000 000 007. 


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

Output
4

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

Output
1

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

Output
0



-----Note-----

In the first sample, the four ways are to:   Make everyone love each other  Make 1 and 2 love each other, and 3 hate 1 and 2 (symmetrically, we get 3 ways from this). 

In the second sample, the only possible solution is to make 1 and 3 love each other and 2 and 4 hate each other.
user: Iahub helps his grandfather at the farm. Today he must milk the cows. There are n cows sitting in a row, numbered from 1 to n from left to right. Each cow is either facing to the left or facing to the right. When Iahub milks a cow, all the cows that see the current cow get scared and lose one unit of the quantity of milk that they can give. A cow facing left sees all the cows with lower indices than her index, and a cow facing right sees all the cows with higher indices than her index. A cow that got scared once can get scared again (and lose one more unit of milk). A cow that has been milked once cannot get scared and lose any more milk. You can assume that a cow never loses all the milk she can give (a cow gives an infinitely amount of milk).

Iahub can decide the order in which he milks the cows. But he must milk each cow exactly once. Iahub wants to lose as little milk as possible. Print the minimum amount of milk that is lost.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 200000). The second line contains n integers a_1, a_2, ..., a_{n}, where a_{i} is 0 if the cow number i is facing left, and 1 if it is facing right.


-----Output-----

Print a single integer, the minimum amount of lost milk.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


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

Output
1
Input
5
1 0 1 0 1

Output
3


-----Note-----

In the first sample Iahub milks the cows in the following order: cow 3, cow 4, cow 2, cow 1. When he milks cow 3, cow 4 loses 1 unit of milk. After that, no more milk is lost.
user: Alice received a set of Toy Train™ from Bob. It consists of one train and a connected railway network of $n$ stations, enumerated from $1$ through $n$. The train occupies one station at a time and travels around the network of stations in a circular manner. More precisely, the immediate station that the train will visit after station $i$ is station $i+1$ if $1 \leq i < n$ or station $1$ if $i = n$. It takes the train $1$ second to travel to its next station as described.

Bob gave Alice a fun task before he left: to deliver $m$ candies that are initially at some stations to their independent destinations using the train. The candies are enumerated from $1$ through $m$. Candy $i$ ($1 \leq i \leq m$), now at station $a_i$, should be delivered to station $b_i$ ($a_i \neq b_i$). [Image] The blue numbers on the candies correspond to $b_i$ values. The image corresponds to the $1$-st example. 

The train has infinite capacity, and it is possible to load off any number of candies at a station. However, only at most one candy can be loaded from a station onto the train before it leaves the station. You can choose any candy at this station. The time it takes to move the candies is negligible.

Now, Alice wonders how much time is needed for the train to deliver all candies. Your task is to find, for each station, the minimum time the train would need to deliver all the candies were it to start from there.


-----Input-----

The first line contains two space-separated integers $n$ and $m$ ($2 \leq n \leq 5\,000$; $1 \leq m \leq 20\,000$) — the number of stations and the number of candies, respectively.

The $i$-th of the following $m$ lines contains two space-separated integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$; $a_i \neq b_i$) — the station that initially contains candy $i$ and the destination station of the candy, respectively.


-----Output-----

In the first and only line, print $n$ space-separated integers, the $i$-th of which is the minimum time, in seconds, the train would need to deliver all the candies were it to start from station $i$.


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

Output
10 9 10 10 9 

Input
2 3
1 2
1 2
1 2

Output
5 6 



-----Note-----

Consider the second sample.

If the train started at station $1$, the optimal strategy is as follows.  Load the first candy onto the train.  Proceed to station $2$. This step takes $1$ second.  Deliver the first candy.  Proceed to station $1$. This step takes $1$ second.  Load the second candy onto the train.  Proceed to station $2$. This step takes $1$ second.  Deliver the second candy.  Proceed to station $1$. This step takes $1$ second.  Load the third candy onto the train.  Proceed to station $2$. This step takes $1$ second.  Deliver the third candy. 

Hence, the train needs $5$ seconds to complete the tasks.

If the train were to start at station $2$, however, it would need to move to station $1$ before it could load the first candy, which would take one additional second. Thus, the answer in this scenario is $5+1 = 6$ seconds.
user: Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 to k. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen. 


-----Input-----

The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain c_{i}, the number of balls of the i-th color (1 ≤ c_{i} ≤ 1000).

The total number of balls doesn't exceed 1000.


-----Output-----

A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1 000 000 007. 


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

Output
3

Input
4
1
2
3
4

Output
1680



-----Note-----

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are: 

1 2 1 2 3

1 1 2 2 3

2 1 1 2 3
user: Nauuo is a girl who loves drawing circles.

One day she has drawn a circle and wanted to draw a tree on it.

The tree is a connected undirected graph consisting of $n$ nodes and $n-1$ edges. The nodes are numbered from $1$ to $n$.

Nauuo wants to draw a tree on the circle, the nodes of the tree should be in $n$ distinct points on the circle, and the edges should be straight without crossing each other.

"Without crossing each other" means that every two edges have no common point or the only common point is an endpoint of both edges.

Nauuo wants to draw the tree using a permutation of $n$ elements. A permutation of $n$ elements is a sequence of integers $p_1,p_2,\ldots,p_n$ in which every integer from $1$ to $n$ appears exactly once.

After a permutation is chosen Nauuo draws the $i$-th node in the $p_i$-th point on the circle, then draws the edges connecting the nodes.

The tree is given, Nauuo wants to know how many permutations are there so that the tree drawn satisfies the rule (the edges are straight without crossing each other). She only wants to know the answer modulo $998244353$, can you help her?

It is obvious that whether a permutation is valid or not does not depend on which $n$ points on the circle are chosen.


-----Input-----

The first line contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$), denoting there is an edge between $u$ and $v$.

It is guaranteed that the given edges form a tree.


-----Output-----

The output contains a single integer — the number of permutations suitable to draw the given tree on a circle satisfying the rule, modulo $998244353$.


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

Output
16
Input
4
1 2
1 3
1 4

Output
24


-----Note-----

Example 1

All valid permutations and their spanning trees are as follows.

[Image]

Here is an example of invalid permutation: the edges $(1,3)$ and $(2,4)$ are crossed.

[Image]

Example 2

Every permutation leads to a valid tree, so the answer is $4! = 24$.
user: There are n student groups at the university. During the study day, each group can take no more than 7 classes. Seven time slots numbered from 1 to 7 are allocated for the classes.

The schedule on Monday is known for each group, i. e. time slots when group will have classes are known.

Your task is to determine the minimum number of rooms needed to hold classes for all groups on Monday. Note that one room can hold at most one group class in a single time slot.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of groups. 

Each of the following n lines contains a sequence consisting of 7 zeroes and ones — the schedule of classes on Monday for a group. If the symbol in a position equals to 1 then the group has class in the corresponding time slot. In the other case, the group has no class in the corresponding time slot.


-----Output-----

Print minimum number of rooms needed to hold all groups classes on Monday.


-----Examples-----
Input
2
0101010
1010101

Output
1

Input
3
0101011
0011001
0110111

Output
3



-----Note-----

In the first example one room is enough. It will be occupied in each of the seven time slot by the first group or by the second group.

In the second example three rooms is enough, because in the seventh time slot all three groups have classes.
user: Mitya has a rooted tree with $n$ vertices indexed from $1$ to $n$, where the root has index $1$. Each vertex $v$ initially had an integer number $a_v \ge 0$ written on it. For every vertex $v$ Mitya has computed $s_v$: the sum of all values written on the vertices on the path from vertex $v$ to the root, as well as $h_v$ — the depth of vertex $v$, which denotes the number of vertices on the path from vertex $v$ to the root. Clearly, $s_1=a_1$ and $h_1=1$.

Then Mitya erased all numbers $a_v$, and by accident he also erased all values $s_v$ for vertices with even depth (vertices with even $h_v$). Your task is to restore the values $a_v$ for every vertex, or determine that Mitya made a mistake. In case there are multiple ways to restore the values, you're required to find one which minimizes the total sum of values $a_v$ for all vertices in the tree.


-----Input-----

The first line contains one integer $n$ — the number of vertices in the tree ($2 \le n \le 10^5$). The following line contains integers $p_2$, $p_3$, ... $p_n$, where $p_i$ stands for the parent of vertex with index $i$ in the tree ($1 \le p_i < i$). The last line contains integer values $s_1$, $s_2$, ..., $s_n$ ($-1 \le s_v \le 10^9$), where erased values are replaced by $-1$.


-----Output-----

Output one integer — the minimum total sum of all values $a_v$ in the original tree, or $-1$ if such tree does not exist.


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

Output
1

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

Output
2

Input
3
1 2
2 -1 1

Output
-1
user: You are given a Young diagram. 

Given diagram is a histogram with $n$ columns of lengths $a_1, a_2, \ldots, a_n$ ($a_1 \geq a_2 \geq \ldots \geq a_n \geq 1$). [Image] Young diagram for $a=[3,2,2,2,1]$. 

Your goal is to find the largest number of non-overlapping dominos that you can draw inside of this histogram, a domino is a $1 \times 2$ or $2 \times 1$ rectangle.


-----Input-----

The first line of input contain one integer $n$ ($1 \leq n \leq 300\,000$): the number of columns in the given histogram.

The next line of input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 300\,000, a_i \geq a_{i+1}$): the lengths of columns.


-----Output-----

Output one integer: the largest number of non-overlapping dominos that you can draw inside of the given Young diagram.


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

Output
4



-----Note-----

Some of the possible solutions for the example:

[Image] $\square$
user: Vasya's got a birthday coming up and his mom decided to give him an array of positive integers a of length n.

Vasya thinks that an array's beauty is the greatest common divisor of all its elements. His mom, of course, wants to give him as beautiful an array as possible (with largest possible beauty). Unfortunately, the shop has only one array a left. On the plus side, the seller said that he could decrease some numbers in the array (no more than by k for each number).

The seller can obtain array b from array a if the following conditions hold: b_{i} > 0; 0 ≤ a_{i} - b_{i} ≤ k for all 1 ≤ i ≤ n.

Help mom find the maximum possible beauty of the array she will give to Vasya (that seller can obtain).


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 3·10^5; 1 ≤ k ≤ 10^6). The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6) — array a.


-----Output-----

In the single line print a single number — the maximum possible beauty of the resulting array.


-----Examples-----
Input
6 1
3 6 10 12 13 16

Output
3

Input
5 3
8 21 52 15 77

Output
7



-----Note-----

In the first sample we can obtain the array:

3 6 9 12 12 15

In the second sample we can obtain the next array:

7 21 49 14 77
user: You are fishing with polar bears Alice and Bob. While waiting for the fish to bite, the polar bears get bored. They come up with a game. First Alice and Bob each writes a 01-string (strings that only contain character "0" and "1") a and b. Then you try to turn a into b using two types of operations:  Write parity(a) to the end of a. For example, $1010 \rightarrow 10100$.  Remove the first character of a. For example, $1001 \rightarrow 001$. You cannot perform this operation if a is empty. 

You can use as many operations as you want. The problem is, is it possible to turn a into b?

The parity of a 01-string is 1 if there is an odd number of "1"s in the string, and 0 otherwise.


-----Input-----

The first line contains the string a and the second line contains the string b (1 ≤ |a|, |b| ≤ 1000). Both strings contain only the characters "0" and "1". Here |x| denotes the length of the string x.


-----Output-----

Print "YES" (without quotes) if it is possible to turn a into b, and "NO" (without quotes) otherwise.


-----Examples-----
Input
01011
0110

Output
YES

Input
0011
1110

Output
NO



-----Note-----

In the first sample, the steps are as follows: 01011 → 1011 → 011 → 0110
user: You are given an array $a$ of length $2n$. Consider a partition of array $a$ into two subsequences $p$ and $q$ of length $n$ each (each element of array $a$ should be in exactly one subsequence: either in $p$ or in $q$).

Let's sort $p$ in non-decreasing order, and $q$ in non-increasing order, we can denote the sorted versions by $x$ and $y$, respectively. Then the cost of a partition is defined as $f(p, q) = \sum_{i = 1}^n |x_i - y_i|$.

Find the sum of $f(p, q)$ over all correct partitions of array $a$. Since the answer might be too big, print its remainder modulo $998244353$.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 150\,000$).

The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \leq a_i \leq 10^9$) — elements of array $a$.


-----Output-----

Print one integer — the answer to the problem, modulo $998244353$.


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

Output
6
Input
2
2 1 2 1

Output
12
Input
3
2 2 2 2 2 2

Output
0
Input
5
13 8 35 94 9284 34 54 69 123 846

Output
2588544


-----Note-----

Two partitions of an array are considered different if the sets of indices of elements included in the subsequence $p$ are different.

In the first example, there are two correct partitions of the array $a$:  $p = [1]$, $q = [4]$, then $x = [1]$, $y = [4]$, $f(p, q) = |1 - 4| = 3$;  $p = [4]$, $q = [1]$, then $x = [4]$, $y = [1]$, $f(p, q) = |4 - 1| = 3$. 

In the second example, there are six valid partitions of the array $a$:   $p = [2, 1]$, $q = [2, 1]$ (elements with indices $1$ and $2$ in the original array are selected in the subsequence $p$);  $p = [2, 2]$, $q = [1, 1]$;  $p = [2, 1]$, $q = [1, 2]$ (elements with indices $1$ and $4$ are selected in the subsequence $p$);  $p = [1, 2]$, $q = [2, 1]$;  $p = [1, 1]$, $q = [2, 2]$;  $p = [2, 1]$, $q = [2, 1]$ (elements with indices $3$ and $4$ are selected in the subsequence $p$).
user: While discussing a proper problem A for a Codeforces Round, Kostya created a cyclic array of positive integers $a_1, a_2, \ldots, a_n$. Since the talk was long and not promising, Kostya created a new cyclic array $b_1, b_2, \ldots, b_{n}$ so that $b_i = (a_i \mod a_{i + 1})$, where we take $a_{n+1} = a_1$. Here $mod$ is the modulo operation. When the talk became interesting, Kostya completely forgot how array $a$ had looked like. Suddenly, he thought that restoring array $a$ from array $b$ would be an interesting problem (unfortunately, not A).


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 140582$) — the length of the array $a$.

The second line contains $n$ integers $b_1, b_2, \ldots, b_{n}$ ($0 \le b_i \le 187126$).


-----Output-----

If it is possible to restore some array $a$ of length $n$ so that $b_i = a_i \mod a_{(i \mod n) + 1}$ holds for all $i = 1, 2, \ldots, n$, print «YES» in the first line and the integers $a_1, a_2, \ldots, a_n$ in the second line. All $a_i$ should satisfy $1 \le a_i \le 10^{18}$. We can show that if an answer exists, then an answer with such constraint exists as well.

It it impossible to restore any valid $a$, print «NO» in one line.

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


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

Output
YES
1 3 5 2

Input
2
4 4

Output
NO



-----Note-----

In the first example:  $1 \mod 3 = 1$  $3 \mod 5 = 3$  $5 \mod 2 = 1$  $2 \mod 1 = 0$
user: Evlampiy was gifted a rooted tree. The vertices of the tree are numbered from $1$ to $n$. Each of its vertices also has an integer $a_i$ written on it. For each vertex $i$, Evlampiy calculated $c_i$ — the number of vertices $j$ in the subtree of vertex $i$, such that $a_j < a_i$. [Image]Illustration for the second example, the first integer is $a_i$ and the integer in parentheses is $c_i$

After the new year, Evlampiy could not remember what his gift was! He remembers the tree and the values of $c_i$, but he completely forgot which integers $a_i$ were written on the vertices.

Help him to restore initial integers!


-----Input-----

The first line contains an integer $n$ $(1 \leq n \leq 2000)$ — the number of vertices in the tree.

The next $n$ lines contain descriptions of vertices: the $i$-th line contains two integers $p_i$ and $c_i$ ($0 \leq p_i \leq n$; $0 \leq c_i \leq n-1$), where $p_i$ is the parent of vertex $i$ or $0$ if vertex $i$ is root, and $c_i$ is the number of vertices $j$ in the subtree of vertex $i$, such that $a_j < a_i$.

It is guaranteed that the values of $p_i$ describe a rooted tree with $n$ vertices.


-----Output-----

If a solution exists, in the first line print "YES", and in the second line output $n$ integers $a_i$ $(1 \leq a_i \leq {10}^{9})$. If there are several solutions, output any of them. One can prove that if there is a solution, then there is also a solution in which all $a_i$ are between $1$ and $10^9$.

If there are no solutions, print "NO".


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

Output
YES
1 2 1 
Input
5
0 1
1 3
2 1
3 0
2 0

Output
YES
2 3 2 1 2