meetforever/GRPO_CL huggingface dataset:
user: Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a_1, a_2, ..., a_{n} are good.

Now she is interested in good sequences. A sequence x_1, x_2, ..., x_{k} is called good if it satisfies the following three conditions:  The sequence is strictly increasing, i.e. x_{i} < x_{i} + 1 for each i (1 ≤ i ≤ k - 1).  No two adjacent elements are coprime, i.e. gcd(x_{i}, x_{i} + 1) > 1 for each i (1 ≤ i ≤ k - 1) (where gcd(p, q) denotes the greatest common divisor of the integers p and q).  All elements of the sequence are good integers. 

Find the length of the longest good sequence.


-----Input-----

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of good integers. The second line contains a single-space separated list of good integers a_1, a_2, ..., a_{n} in strictly increasing order (1 ≤ a_{i} ≤ 10^5; a_{i} < a_{i} + 1).


-----Output-----

Print a single integer — the length of the longest good sequence.


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

Output
4

Input
9
1 2 3 5 6 7 8 9 10

Output
4



-----Note-----

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.
user: For a permutation P[1... N] of integers from 1 to N, function f is defined as follows:

 $f(i, j) = \left\{\begin{array}{ll}{P [ i ]} & {\text{if} j = 1} \\{f(P [ i ], j - 1)} & {\text{otherwise}} \end{array} \right.$ 

Let g(i) be the minimum positive integer j such that f(i, j) = i. We can show such j always exists.

For given N, A, B, find a permutation P of integers from 1 to N such that for 1 ≤ i ≤ N, g(i) equals either A or B.


-----Input-----

The only line contains three integers N, A, B (1 ≤ N ≤ 10^6, 1 ≤ A, B ≤ N).


-----Output-----

If no such permutation exists, output -1. Otherwise, output a permutation of integers from 1 to N.


-----Examples-----
Input
9 2 5

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

Output
1 2 3 


-----Note-----

In the first example, g(1) = g(6) = g(7) = g(9) = 2 and g(2) = g(3) = g(4) = g(5) = g(8) = 5 

In the second example, g(1) = g(2) = g(3) = 1
user: Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.

For each of next $n$ days Vasya knows $a_i$ — number of units of garbage he will produce on the $i$-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to $k$ units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.

Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given $n$ days. No garbage should be left after the $n$-th day.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2\cdot10^5, 1 \le k \le 10^9$) — number of days to consider and bag's capacity. The second line contains $n$ space separated integers $a_i$ ($0 \le a_i \le 10^9$) — the number of units of garbage produced on the $i$-th day.


-----Output-----

Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the $n$-th day. In a day it is allowed to compose and drop multiple bags.


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

Output
3

Input
5 1
1000000000 1000000000 1000000000 1000000000 1000000000

Output
5000000000

Input
3 2
1 0 1

Output
2

Input
4 4
2 8 4 1

Output
4
user: Is there anything better than going to the zoo after a tiresome week at work? No wonder Grisha feels the same while spending the entire weekend accompanied by pretty striped zebras. 

Inspired by this adventure and an accidentally found plasticine pack (represented as a sequence of black and white stripes), Grisha now wants to select several consequent (contiguous) pieces of alternating colors to create a zebra. Let's call the number of selected pieces the length of the zebra.

Before assembling the zebra Grisha can make the following operation $0$ or more times. He splits the sequence in some place into two parts, then reverses each of them and sticks them together again. For example, if Grisha has pieces in the order "bwbbw" (here 'b' denotes a black strip, and 'w' denotes a white strip), then he can split the sequence as bw|bbw (here the vertical bar represents the cut), reverse both parts and obtain "wbwbb".

Determine the maximum possible length of the zebra that Grisha can produce.


-----Input-----

The only line contains a string $s$ ($1 \le |s| \le 10^5$, where $|s|$ denotes the length of the string $s$) comprised of lowercase English letters 'b' and 'w' only, where 'w' denotes a white piece and 'b' denotes a black piece.


-----Output-----

Print a single integer — the maximum possible zebra length.


-----Examples-----
Input
bwwwbwwbw

Output
5

Input
bwwbwwb

Output
3



-----Note-----

In the first example one of the possible sequence of operations is bwwwbww|bw $\to$ w|wbwwwbwb $\to$ wbwbwwwbw, that gives the answer equal to $5$.

In the second example no operation can increase the answer.
user: You are playing some computer game. One of its levels puts you in a maze consisting of n lines, each of which contains m cells. Each cell either is free or is occupied by an obstacle. The starting cell is in the row r and column c. In one step you can move one square up, left, down or right, if the target cell is not occupied by an obstacle. You can't move beyond the boundaries of the labyrinth.

Unfortunately, your keyboard is about to break, so you can move left no more than x times and move right no more than y times. There are no restrictions on the number of moves up and down since the keys used to move up and down are in perfect condition.

Now you would like to determine for each cell whether there exists a sequence of moves that will put you from the starting cell to this particular one. How many cells of the board have this property?


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 2000) — the number of rows and the number columns in the labyrinth respectively.

The second line contains two integers r, c (1 ≤ r ≤ n, 1 ≤ c ≤ m) — index of the row and index of the column that define the starting cell.

The third line contains two integers x, y (0 ≤ x, y ≤ 10^9) — the maximum allowed number of movements to the left and to the right respectively.

The next n lines describe the labyrinth. Each of them has length of m and consists only of symbols '.' and '*'. The j-th character of the i-th line corresponds to the cell of labyrinth at row i and column j. Symbol '.' denotes the free cell, while symbol '*' denotes the cell with an obstacle.

It is guaranteed, that the starting cell contains no obstacles.


-----Output-----

Print exactly one integer — the number of cells in the labyrinth, which are reachable from starting cell, including the starting cell itself.


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

Output
10

Input
4 4
2 2
0 1
....
..*.
....
....

Output
7



-----Note-----

Cells, reachable in the corresponding example, are marked with '+'.

First example:  

+++..

+***.

+++**

*+++.

 

Second example:  

.++.

.+*.

.++.

.++.
user: You have a set of $n$ weights. You know that their masses are $a_1$, $a_2$, ..., $a_n$ grams, but you don't know which of them has which mass. You can't distinguish the weights.

However, your friend does know the mass of each weight. You can ask your friend to give you exactly $k$ weights with the total mass $m$ (both parameters $k$ and $m$ are chosen by you), and your friend will point to any valid subset of weights, if it is possible.

You are allowed to make this query only once. Find the maximum possible number of weights you can reveal after this query.


-----Input-----

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$) — the masses of the weights.


-----Output-----

Print the maximum number of weights you can learn the masses for after making a single query.


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

Output
2

Input
6
1 2 4 4 4 9

Output
2



-----Note-----

In the first example we can ask for a subset of two weights with total mass being equal to $4$, and the only option is to get $\{2, 2\}$.

Another way to obtain the same result is to ask for a subset of two weights with the total mass of $5$ and get $\{1, 4\}$. It is easy to see that the two remaining weights have mass of $2$ grams each.

In the second example we can ask for a subset of two weights with total mass being $8$, and the only answer is $\{4, 4\}$. We can prove it is not possible to learn masses for three weights in one query, but we won't put the proof here.
user: Suppose you are given a string $s$ of length $n$ consisting of lowercase English letters. You need to compress it using the smallest possible number of coins.

To compress the string, you have to represent $s$ as a concatenation of several non-empty strings: $s = t_{1} t_{2} \ldots t_{k}$. The $i$-th of these strings should be encoded with one of the two ways:  if $|t_{i}| = 1$, meaning that the current string consists of a single character, you can encode it paying $a$ coins;  if $t_{i}$ is a substring of $t_{1} t_{2} \ldots t_{i - 1}$, then you can encode it paying $b$ coins. 

A string $x$ is a substring of a string $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

So your task is to calculate the minimum possible number of coins you need to spend in order to compress the given string $s$.


-----Input-----

The first line contains three positive integers, separated by spaces: $n$, $a$ and $b$ ($1 \leq n, a, b \leq 5000$) — the length of the string, the cost to compress a one-character string and the cost to compress a string that appeared before.

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


-----Output-----

Output a single integer — the smallest possible number of coins you need to spend to compress $s$.


-----Examples-----
Input
3 3 1
aba

Output
7

Input
4 1 1
abcd

Output
4

Input
4 10 1
aaaa

Output
12



-----Note-----

In the first sample case, you can set $t_{1} =$ 'a', $t_{2} =$ 'b', $t_{3} =$ 'a' and pay $3 + 3 + 1 = 7$ coins, since $t_{3}$ is a substring of $t_{1}t_{2}$.

In the second sample, you just need to compress every character by itself.

In the third sample, you set $t_{1} = t_{2} =$ 'a', $t_{3} =$ 'aa' and pay $10 + 1 + 1 = 12$ coins, since $t_{2}$ is a substring of $t_{1}$ and $t_{3}$ is a substring of $t_{1} t_{2}$.
user: Snuke has decided to play with N cards and a deque (that is, a double-ended queue).
Each card shows an integer from 1 through N, and the deque is initially empty.
Snuke will insert the cards at the beginning or the end of the deque one at a time, in order from 1 to N.
Then, he will perform the following action N times: take out the card from the beginning or the end of the deque and eat it.
Afterwards, we will construct an integer sequence by arranging the integers written on the eaten cards, in the order they are eaten. Among the sequences that can be obtained in this way, find the number of the sequences such that the K-th element is 1. Print the answer modulo 10^{9} + 7.

-----Constraints-----
 - 1 ≦ K ≦ N ≦ 2{,}000

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

-----Output-----
Print the answer modulo 10^{9} + 7.

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

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

There is one sequence satisfying the condition: 1,2. One possible way to obtain this sequence is the following:
 - Insert both cards, 1 and 2, at the end of the deque.
 - Eat the card at the beginning of the deque twice.
user: Molly Hooper has n different kinds of chemicals arranged in a line. Each of the chemicals has an affection value, The i-th of them has affection value a_{i}.

Molly wants Sherlock to fall in love with her. She intends to do this by mixing a contiguous segment of chemicals together to make a love potion with total affection value as a non-negative integer power of k. Total affection value of a continuous segment of chemicals is the sum of affection values of each chemical in that segment.

Help her to do so in finding the total number of such segments.


-----Input-----

The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection value is a non-negative power of this number k. (1 ≤ n ≤ 10^5, 1 ≤ |k| ≤ 10).

Next line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — affection values of chemicals.


-----Output-----

Output a single integer — the number of valid segments.


-----Examples-----
Input
4 2
2 2 2 2

Output
8

Input
4 -3
3 -6 -3 12

Output
3



-----Note-----

Do keep in mind that k^0 = 1.

In the first sample, Molly can get following different affection values:  2: segments [1, 1], [2, 2], [3, 3], [4, 4];

 4: segments [1, 2], [2, 3], [3, 4];

 6: segments [1, 3], [2, 4];

 8: segments [1, 4]. 

Out of these, 2, 4 and 8 are powers of k = 2. Therefore, the answer is 8.

In the second sample, Molly can choose segments [1, 2], [3, 3], [3, 4].
user: Iahub and Iahubina went to a picnic in a forest full of trees. Less than 5 minutes passed before Iahub remembered of trees from programming. Moreover, he invented a new problem and Iahubina has to solve it, otherwise Iahub won't give her the food. 

Iahub asks Iahubina: can you build a rooted tree, such that

  each internal node (a node with at least one son) has at least two sons;  node i has c_{i} nodes in its subtree? 

Iahubina has to guess the tree. Being a smart girl, she realized that it's possible no tree can follow Iahub's restrictions. In this way, Iahub will eat all the food. You need to help Iahubina: determine if there's at least one tree following Iahub's restrictions. The required tree must contain n nodes.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 24). Next line contains n positive integers: the i-th number represents c_{i} (1 ≤ c_{i} ≤ n).


-----Output-----

Output on the first line "YES" (without quotes) if there exist at least one tree following Iahub's restrictions, otherwise output "NO" (without quotes). 


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

Output
YES
Input
5
1 1 5 2 1

Output
NO
user: Vasya came up with his own weather forecasting method. He knows the information about the average air temperature for each of the last n days. Assume that the average air temperature for each day is integral.

Vasya believes that if the average temperatures over the last n days form an arithmetic progression, where the first term equals to the average temperature on the first day, the second term equals to the average temperature on the second day and so on, then the average temperature of the next (n + 1)-th day will be equal to the next term of the arithmetic progression. Otherwise, according to Vasya's method, the temperature of the (n + 1)-th day will be equal to the temperature of the n-th day.

Your task is to help Vasya predict the average temperature for tomorrow, i. e. for the (n + 1)-th day.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 100) — the number of days for which the average air temperature is known.

The second line contains a sequence of integers t_1, t_2, ..., t_{n} ( - 1000 ≤ t_{i} ≤ 1000) — where t_{i} is the average temperature in the i-th day.


-----Output-----

Print the average air temperature in the (n + 1)-th day, which Vasya predicts according to his method. Note that the absolute value of the predicted temperature can exceed 1000.


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

Output
-15

Input
4
1 1 1 1

Output
1

Input
3
5 1 -5

Output
-5

Input
2
900 1000

Output
1100



-----Note-----

In the first example the sequence of the average temperatures is an arithmetic progression where the first term is 10 and each following terms decreases by 5. So the predicted average temperature for the sixth day is  - 10 - 5 =  - 15.

In the second example the sequence of the average temperatures is an arithmetic progression where the first term is 1 and each following terms equals to the previous one. So the predicted average temperature in the fifth day is 1.

In the third example the average temperatures do not form an arithmetic progression, so the average temperature of the fourth day equals to the temperature of the third day and equals to  - 5.

In the fourth example the sequence of the average temperatures is an arithmetic progression where the first term is 900 and each the following terms increase by 100. So predicted average temperature in the third day is 1000 + 100 = 1100.
user: Note that this is the first problem of the two similar problems. You can hack this problem only if you solve both problems.

You are given a tree with $n$ nodes. In the beginning, $0$ is written on all edges. In one operation, you can choose any $2$ distinct leaves $u$, $v$ and any real number $x$ and add $x$ to values written on all edges on the simple path between $u$ and $v$.

For example, on the picture below you can see the result of applying two operations to the graph: adding $2$ on the path from $7$ to $6$, and then adding $-0.5$ on the path from $4$ to $5$. 

 [Image] 

Is it true that for any configuration of real numbers written on edges, we can achieve it with a finite number of operations?

Leaf is a node of a tree of degree $1$. Simple path is a path that doesn't contain any node twice.


-----Input-----

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

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$), meaning that there is an edge between nodes $u$ and $v$. It is guaranteed that these edges form a tree.


-----Output-----

If there is a configuration of real numbers written on edges of the tree that we can't achieve by performing the operations, output "NO". 

Otherwise, output "YES". 

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


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

Output
YES
Input
3
1 2
2 3

Output
NO
Input
5
1 2
1 3
1 4
2 5

Output
NO
Input
6
1 2
1 3
1 4
2 5
2 6

Output
YES


-----Note-----

In the first example, we can add any real $x$ to the value written on the only edge $(1, 2)$.

 [Image] 

In the second example, one of configurations that we can't reach is $0$ written on $(1, 2)$ and $1$ written on $(2, 3)$.

 $8$ 

Below you can see graphs from examples $3$, $4$:

 [Image] 

 [Image]
user: Boy Dima gave Julian a birthday present — set $B$ consisting of positive integers. However, he didn't know, that Julian hates sets, but enjoys bipartite graphs more than anything else!

Julian was almost upset, but her friend Alex said, that he can build an undirected graph using this set in such a way: let all integer numbers be vertices, then connect any two $i$ and $j$ with an edge if $|i - j|$ belongs to $B$.

Unfortunately, Julian doesn't like the graph, that was built using $B$. Alex decided to rectify the situation, so he wants to erase some numbers from $B$, so that graph built using the new set is bipartite. The difficulty of this task is that the graph, Alex has to work with, has an infinite number of vertices and edges! It is impossible to solve this task alone, so Alex asks you for help. Write a program that erases a subset of minimum size from $B$ so that graph constructed on the new set is bipartite.

Recall, that graph is bipartite if all its vertices can be divided into two disjoint sets such that every edge connects a vertex from different sets.


-----Input-----

First line contains an integer $n ~ (1 \leqslant n \leqslant 200\,000)$ — size of $B$

Second line contains $n$ integers $b_1, b_2, \ldots, b_n ~ (1 \leqslant b_i \leqslant 10^{18})$ — numbers of $B$, all $b_i$ are unique


-----Output-----

In the first line print single integer $k$ – the number of erased elements. In the second line print $k$ integers — values of erased elements.

If there are multiple answers, print any of them.


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

Output
1
2 
Input
2
2 6

Output
0
user: We have a board with a 2 \times N grid.
Snuke covered the board with N dominoes without overlaps.
Here, a domino can cover a 1 \times 2 or 2 \times 1 square.
Then, Snuke decided to paint these dominoes using three colors: red, cyan and green.
Two dominoes that are adjacent by side should be painted by different colors.
Here, it is not always necessary to use all three colors.
Find the number of such ways to paint the dominoes, modulo 1000000007.
The arrangement of the dominoes is given to you as two strings S_1 and S_2 in the following manner:
 - Each domino is represented by a different English letter (lowercase or uppercase).
 - The j-th character in S_i represents the domino that occupies the square at the i-th row from the top and j-th column from the left.

-----Constraints-----
 - 1 \leq N \leq 52
 - |S_1| = |S_2| = N
 - S_1 and S_2 consist of lowercase and uppercase English letters.
 - S_1 and S_2 represent a valid arrangement of dominoes.

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

-----Output-----
Print the number of such ways to paint the dominoes, modulo 1000000007.

-----Sample Input-----
3
aab
ccb

-----Sample Output-----
6

There are six ways as shown below:
user: Consider a table G of size n × m such that G(i, j) = GCD(i, j) for all 1 ≤ i ≤ n, 1 ≤ j ≤ m. GCD(a, b) is the greatest common divisor of numbers a and b.

You have a sequence of positive integer numbers a_1, a_2, ..., a_{k}. We say that this sequence occurs in table G if it coincides with consecutive elements in some row, starting from some position. More formally, such numbers 1 ≤ i ≤ n and 1 ≤ j ≤ m - k + 1 should exist that G(i, j + l - 1) = a_{l} for all 1 ≤ l ≤ k.

Determine if the sequence a occurs in table G.


-----Input-----

The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 10^12; 1 ≤ k ≤ 10000). The second line contains k space-separated integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ 10^12).


-----Output-----

Print a single word "YES", if the given sequence occurs in table G, otherwise print "NO".


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

Output
YES

Input
100 8 5
5 2 1 2 1

Output
NO

Input
100 100 7
1 2 3 4 5 6 7

Output
NO



-----Note-----

Sample 1. The tenth row of table G starts from sequence {1, 2, 1, 2, 5, 2, 1, 2, 1, 10}. As you can see, elements from fifth to ninth coincide with sequence a.

Sample 2. This time the width of table G equals 8. Sequence a doesn't occur there.