meetforever/GRPO_CL huggingface dataset:
user: Snuke had N cards numbered 1 through N.
Each card has an integer written on it; written on Card i is a_i.
Snuke did the following procedure:
 - Let X and x be the maximum and minimum values written on Snuke's cards, respectively.
 - If X = x, terminate the procedure. Otherwise, replace each card on which X is written with a card on which X-x is written, then go back to step 1.
Under the constraints in this problem, it can be proved that the procedure will eventually terminate. Find the number written on all of Snuke's cards after the procedure.

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

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 \cdots a_N

-----Output-----
Print the number written on all of Snuke's cards after the procedure.

-----Sample Input-----
3
2 6 6

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

 - At the beginning of the procedure, the numbers written on Snuke's cards are (2,6,6).
 - Since x=2 and X=6, he replaces each card on which 6 is written with a card on which 4 is written.
 - Now, the numbers written on Snuke's cards are (2,4,4).
 - Since x=2 and X=4, he replaces each card on which 4 is written with a card on which 2 is written.
 - Now, the numbers written on Snuke's cards are (2,2,2).
 - Since x=2 and X=2, he terminates the procedure.
user: There are N piles of stones. The i-th pile has A_i stones.
Aoki and Takahashi are about to use them to play the following game:
 - Starting with Aoki, the two players alternately do the following operation:
 - Operation: Choose one pile of stones, and remove one or more stones from it.
 - When a player is unable to do the operation, he loses, and the other player wins.
When the two players play optimally, there are two possibilities in this game: the player who moves first always wins, or the player who moves second always wins, only depending on the initial number of stones in each pile.
In such a situation, Takahashi, the second player to act, is trying to guarantee his win by moving at least zero and at most (A_1 - 1) stones from the 1-st pile to the 2-nd pile before the game begins.
If this is possible, print the minimum number of stones to move to guarantee his victory; otherwise, print -1 instead.

-----Constraints-----
 - 2 \leq N \leq 300
 - 1 \leq A_i \leq 10^{12}

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 \ldots A_N

-----Output-----
Print the minimum number of stones to move to guarantee Takahashi's win; otherwise, print -1 instead.

-----Sample Input-----
2
5 3

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

Without moving stones, if Aoki first removes 2 stones from the 1-st pile, Takahashi cannot win in any way.
If Takahashi moves 1 stone from the 1-st pile to the 2-nd before the game begins so that both piles have 4 stones, Takahashi can always win by properly choosing his actions.
user: Let us denote by f(x, m) the remainder of the Euclidean division of x by m.
Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M).
Find \displaystyle{\sum_{i=1}^N A_i}.

-----Constraints-----
 - 1 \leq N \leq 10^{10}
 - 0 \leq X < M \leq 10^5
 - All values in input are integers.

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

-----Output-----
Print \displaystyle{\sum_{i=1}^N A_i}.

-----Sample Input-----
6 2 1001

-----Sample Output-----
1369

The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.
user: Everyone knows that agents in Valorant decide, who will play as attackers, and who will play as defenders. To do that Raze and Breach decided to play $t$ matches of a digit game...

In each of $t$ matches of the digit game, a positive integer is generated. It consists of $n$ digits. The digits of this integer are numerated from $1$ to $n$ from the highest-order digit to the lowest-order digit. After this integer is announced, the match starts.

Agents play in turns. Raze starts. In one turn an agent can choose any unmarked digit and mark it. Raze can choose digits on odd positions, but can not choose digits on even positions. Breach can choose digits on even positions, but can not choose digits on odd positions. The match ends, when there is only one unmarked digit left. If the single last digit is odd, then Raze wins, else Breach wins.

It can be proved, that before the end of the match (for every initial integer with $n$ digits) each agent has an ability to make a turn, i.e. there is at least one unmarked digit, that stands on a position of required parity.

For each of $t$ matches find out, which agent wins, if both of them want to win and play optimally.


-----Input-----

First line of input contains an integer $t$ $(1 \le t \le 100)$  — the number of matches.

The first line of each match description contains an integer $n$ $(1 \le n \le 10^3)$  — the number of digits of the generated number.

The second line of each match description contains an $n$-digit positive integer without leading zeros.


-----Output-----

For each match print $1$, if Raze wins, and $2$, if Breach wins.


-----Example-----
Input
4
1
2
1
3
3
102
4
2069

Output
2
1
1
2



-----Note-----

In the first match no one can make a turn, the only digit left is $2$, it's even, so Breach wins.

In the second match the only digit left is $3$, it's odd, so Raze wins.

In the third match Raze can mark the last digit, after that Breach can only mark $0$. $1$ will be the last digit left, it's odd, so Raze wins.

In the fourth match no matter how Raze plays, Breach can mark $9$, and in the end there will be digit $0$. It's even, so Breach wins.
user: One industrial factory is reforming working plan. The director suggested to set a mythical detail production norm. If at the beginning of the day there were x details in the factory storage, then by the end of the day the factory has to produce $x \operatorname{mod} m$ (remainder after dividing x by m) more details. Unfortunately, no customer has ever bought any mythical detail, so all the details produced stay on the factory. 

The board of directors are worried that the production by the given plan may eventually stop (that means that there will be а moment when the current number of details on the factory is divisible by m). 

Given the number of details a on the first day and number m check if the production stops at some moment.


-----Input-----

The first line contains two integers a and m (1 ≤ a, m ≤ 10^5).


-----Output-----

Print "Yes" (without quotes) if the production will eventually stop, otherwise print "No".


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

Output
No

Input
3 6

Output
Yes
user: You are given n points on a line with their coordinates x_{i}. Find the point x so the sum of distances to the given points is minimal.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the number of points on the line.

The second line contains n integers x_{i} ( - 10^9 ≤ x_{i} ≤ 10^9) — the coordinates of the given n points.


-----Output-----

Print the only integer x — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer.


-----Example-----
Input
4
1 2 3 4

Output
2
user: Ivan is a student at Berland State University (BSU). There are n days in Berland week, and each of these days Ivan might have some classes at the university.

There are m working hours during each Berland day, and each lesson at the university lasts exactly one hour. If at some day Ivan's first lesson is during i-th hour, and last lesson is during j-th hour, then he spends j - i + 1 hours in the university during this day. If there are no lessons during some day, then Ivan stays at home and therefore spends 0 hours in the university.

Ivan doesn't like to spend a lot of time in the university, so he has decided to skip some lessons. He cannot skip more than k lessons during the week. After deciding which lessons he should skip and which he should attend, every day Ivan will enter the university right before the start of the first lesson he does not skip, and leave it after the end of the last lesson he decides to attend. If Ivan skips all lessons during some day, he doesn't go to the university that day at all.

Given n, m, k and Ivan's timetable, can you determine the minimum number of hours he has to spend in the university during one week, if he cannot skip more than k lessons?


-----Input-----

The first line contains three integers n, m and k (1 ≤ n, m ≤ 500, 0 ≤ k ≤ 500) — the number of days in the Berland week, the number of working hours during each day, and the number of lessons Ivan can skip, respectively.

Then n lines follow, i-th line containing a binary string of m characters. If j-th character in i-th line is 1, then Ivan has a lesson on i-th day during j-th hour (if it is 0, there is no such lesson).


-----Output-----

Print the minimum number of hours Ivan has to spend in the university during the week if he skips not more than k lessons.


-----Examples-----
Input
2 5 1
01001
10110

Output
5

Input
2 5 0
01001
10110

Output
8



-----Note-----

In the first example Ivan can skip any of two lessons during the first day, so he spends 1 hour during the first day and 4 hours during the second day.

In the second example Ivan can't skip any lessons, so he spends 4 hours every day.
user: Arthur and Alexander are number busters. Today they've got a competition. 

Arthur took a group of four integers a, b, w, x (0 ≤ b < w, 0 < x < w) and Alexander took integer с. Arthur and Alexander use distinct approaches to number bustings. Alexander is just a regular guy. Each second, he subtracts one from his number. In other words, he performs the assignment: c = c - 1. Arthur is a sophisticated guy. Each second Arthur performs a complex operation, described as follows: if b ≥ x, perform the assignment b = b - x, if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b).

You've got numbers a, b, w, x, c. Determine when Alexander gets ahead of Arthur if both guys start performing the operations at the same time. Assume that Alexander got ahead of Arthur if c ≤ a.


-----Input-----

The first line contains integers a, b, w, x, c (1 ≤ a ≤ 2·10^9, 1 ≤ w ≤ 1000, 0 ≤ b < w, 0 < x < w, 1 ≤ c ≤ 2·10^9).


-----Output-----

Print a single integer — the minimum time in seconds Alexander needs to get ahead of Arthur. You can prove that the described situation always occurs within the problem's limits.


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

Output
2

Input
4 2 3 1 7

Output
4

Input
1 2 3 2 6

Output
13

Input
1 1 2 1 1

Output
0
user: This problem uses a simplified network topology model, please read the problem statement carefully and use it as a formal document as you develop the solution.

Polycarpus continues working as a system administrator in a large corporation. The computer network of this corporation consists of n computers, some of them are connected by a cable. The computers are indexed by integers from 1 to n. It's known that any two computers connected by cable directly or through other computers

Polycarpus decided to find out the network's topology. A network topology is the way of describing the network configuration, the scheme that shows the location and the connections of network devices.

Polycarpus knows three main network topologies: bus, ring and star. A bus is the topology that represents a shared cable with all computers connected with it. In the ring topology the cable connects each computer only with two other ones. A star is the topology where all computers of a network are connected to the single central node.

Let's represent each of these network topologies as a connected non-directed graph. A bus is a connected graph that is the only path, that is, the graph where all nodes are connected with two other ones except for some two nodes that are the beginning and the end of the path. A ring is a connected graph, where all nodes are connected with two other ones. A star is a connected graph, where a single central node is singled out and connected with all other nodes. For clarifications, see the picture. [Image] (1) — bus, (2) — ring, (3) — star 

You've got a connected non-directed graph that characterizes the computer network in Polycarpus' corporation. Help him find out, which topology type the given network is. If that is impossible to do, say that the network's topology is unknown. 


-----Input-----

The first line contains two space-separated integers n and m (4 ≤ n ≤ 10^5; 3 ≤ m ≤ 10^5) — the number of nodes and edges in the graph, correspondingly. Next m lines contain the description of the graph's edges. The i-th line contains a space-separated pair of integers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ n) — the numbers of nodes that are connected by the i-the edge.

It is guaranteed that the given graph is connected. There is at most one edge between any two nodes. No edge connects a node with itself.


-----Output-----

In a single line print the network topology name of the given graph. If the answer is the bus, print "bus topology" (without the quotes), if the answer is the ring, print "ring topology" (without the quotes), if the answer is the star, print "star topology" (without the quotes). If no answer fits, print "unknown topology" (without the quotes).


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

Output
bus topology

Input
4 4
1 2
2 3
3 4
4 1

Output
ring topology

Input
4 3
1 2
1 3
1 4

Output
star topology

Input
4 4
1 2
2 3
3 1
1 4

Output
unknown topology
user: Andrew often reads articles in his favorite magazine 2Char. The main feature of these articles is that each of them uses at most two distinct letters. Andrew decided to send an article to the magazine, but as he hasn't written any article, he just decided to take a random one from magazine 26Char. However, before sending it to the magazine 2Char, he needs to adapt the text to the format of the journal. To do so, he removes some words from the chosen article, in such a way that the remaining text can be written using no more than two distinct letters.

Since the payment depends from the number of non-space characters in the article, Andrew wants to keep the words with the maximum total length.


-----Input-----

The first line of the input contains number n (1 ≤ n ≤ 100) — the number of words in the article chosen by Andrew. Following are n lines, each of them contains one word. All the words consist only of small English letters and their total length doesn't exceed 1000. The words are not guaranteed to be distinct, in this case you are allowed to use a word in the article as many times as it appears in the input.


-----Output-----

Print a single integer — the maximum possible total length of words in Andrew's article.


-----Examples-----
Input
4
abb
cacc
aaa
bbb

Output
9
Input
5
a
a
bcbcb
cdecdecdecdecdecde
aaaa

Output
6


-----Note-----

In the first sample the optimal way to choose words is {'abb', 'aaa', 'bbb'}.

In the second sample the word 'cdecdecdecdecdecde' consists of three distinct letters, and thus cannot be used in the article. The optimal answer is {'a', 'a', 'aaaa'}.
user: Arkady decides to observe a river for n consecutive days. The river's water level on each day is equal to some real value.

Arkady goes to the riverside each day and makes a mark on the side of the channel at the height of the water level, but if it coincides with a mark made before, no new mark is created. The water does not wash the marks away. Arkady writes down the number of marks strictly above the water level each day, on the i-th day this value is equal to m_{i}.

Define d_{i} as the number of marks strictly under the water level on the i-th day. You are to find out the minimum possible sum of d_{i} over all days. There are no marks on the channel before the first day.


-----Input-----

The first line contains a single positive integer n (1 ≤ n ≤ 10^5) — the number of days.

The second line contains n space-separated integers m_1, m_2, ..., m_{n} (0 ≤ m_{i} < i) — the number of marks strictly above the water on each day.


-----Output-----

Output one single integer — the minimum possible sum of the number of marks strictly below the water level among all days.


-----Examples-----
Input
6
0 1 0 3 0 2

Output
6

Input
5
0 1 2 1 2

Output
1

Input
5
0 1 1 2 2

Output
0



-----Note-----

In the first example, the following figure shows an optimal case. [Image] 

Note that on day 3, a new mark should be created because if not, there cannot be 3 marks above water on day 4. The total number of marks underwater is 0 + 0 + 2 + 0 + 3 + 1 = 6.

In the second example, the following figure shows an optimal case. [Image]
user: Polycarp is mad about coding, that is why he writes Sveta encoded messages. He calls the median letter in a word the letter which is in the middle of the word. If the word's length is even, the median letter is the left of the two middle letters. In the following examples, the median letter is highlighted: contest, info. If the word consists of single letter, then according to above definition this letter is the median letter. 

Polycarp encodes each word in the following way: he writes down the median letter of the word, then deletes it and repeats the process until there are no letters left. For example, he encodes the word volga as logva.

You are given an encoding s of some word, your task is to decode it. 


-----Input-----

The first line contains a positive integer n (1 ≤ n ≤ 2000) — the length of the encoded word.

The second line contains the string s of length n consisting of lowercase English letters — the encoding.


-----Output-----

Print the word that Polycarp encoded.


-----Examples-----
Input
5
logva

Output
volga

Input
2
no

Output
no

Input
4
abba

Output
baba



-----Note-----

In the first example Polycarp encoded the word volga. At first, he wrote down the letter l from the position 3, after that his word looked like voga. After that Polycarp wrote down the letter o from the position 2, his word became vga. Then Polycarp wrote down the letter g which was at the second position, the word became va. Then he wrote down the letter v, then the letter a. Thus, the encoding looked like logva.

In the second example Polycarp encoded the word no. He wrote down the letter n, the word became o, and he wrote down the letter o. Thus, in this example, the word and its encoding are the same.

In the third example Polycarp encoded the word baba. At first, he wrote down the letter a, which was at the position 2, after that the word looked like bba. Then he wrote down the letter b, which was at the position 2, his word looked like ba. After that he wrote down the letter b, which was at the position 1, the word looked like a, and he wrote down that letter a. Thus, the encoding is abba.
user: Calculate the value of the sum: n mod 1 + n mod 2 + n mod 3 + ... + n mod m. As the result can be very large, you should print the value modulo 10^9 + 7 (the remainder when divided by 10^9 + 7).

The modulo operator a mod b stands for the remainder after dividing a by b. For example 10 mod 3 = 1.


-----Input-----

The only line contains two integers n, m (1 ≤ n, m ≤ 10^13) — the parameters of the sum.


-----Output-----

Print integer s — the value of the required sum modulo 10^9 + 7.


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

Output
4

Input
4 4

Output
1

Input
1 1

Output
0
user: After returned from forest, Alyona started reading a book. She noticed strings s and t, lengths of which are n and m respectively. As usual, reading bored Alyona and she decided to pay her attention to strings s and t, which she considered very similar.

Alyona has her favourite positive integer k and because she is too small, k does not exceed 10. The girl wants now to choose k disjoint non-empty substrings of string s such that these strings appear as disjoint substrings of string t and in the same order as they do in string s. She is also interested in that their length is maximum possible among all variants.

Formally, Alyona wants to find a sequence of k non-empty strings p_1, p_2, p_3, ..., p_{k} satisfying following conditions:  s can be represented as concatenation a_1p_1a_2p_2... a_{k}p_{k}a_{k} + 1, where a_1, a_2, ..., a_{k} + 1 is a sequence of arbitrary strings (some of them may be possibly empty);  t can be represented as concatenation b_1p_1b_2p_2... b_{k}p_{k}b_{k} + 1, where b_1, b_2, ..., b_{k} + 1 is a sequence of arbitrary strings (some of them may be possibly empty);  sum of the lengths of strings in sequence is maximum possible. 

Please help Alyona solve this complicated problem and find at least the sum of the lengths of the strings in a desired sequence.

A substring of a string is a subsequence of consecutive characters of the string.


-----Input-----

In the first line of the input three integers n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10) are given — the length of the string s, the length of the string t and Alyona's favourite number respectively.

The second line of the input contains string s, consisting of lowercase English letters.

The third line of the input contains string t, consisting of lowercase English letters.


-----Output-----

In the only line print the only non-negative integer — the sum of the lengths of the strings in a desired sequence.

It is guaranteed, that at least one desired sequence exists.


-----Examples-----
Input
3 2 2
abc
ab

Output
2

Input
9 12 4
bbaaababb
abbbabbaaaba

Output
7



-----Note-----

The following image describes the answer for the second sample case: [Image]
user: Memory is performing a walk on the two-dimensional plane, starting at the origin. He is given a string s with his directions for motion: An 'L' indicates he should move one unit left.  An 'R' indicates he should move one unit right.  A 'U' indicates he should move one unit up.  A 'D' indicates he should move one unit down.

But now Memory wants to end at the origin. To do this, he has a special trident. This trident can replace any character in s with any of 'L', 'R', 'U', or 'D'. However, because he doesn't want to wear out the trident, he wants to make the minimum number of edits possible. Please tell Memory what is the minimum number of changes he needs to make to produce a string that, when walked, will end at the origin, or if there is no such string.


-----Input-----

The first and only line contains the string s (1 ≤ |s| ≤ 100 000) — the instructions Memory is given.


-----Output-----

If there is a string satisfying the conditions, output a single integer — the minimum number of edits required. In case it's not possible to change the sequence in such a way that it will bring Memory to to the origin, output -1.


-----Examples-----
Input
RRU

Output
-1

Input
UDUR

Output
1

Input
RUUR

Output
2



-----Note-----

In the first sample test, Memory is told to walk right, then right, then up. It is easy to see that it is impossible to edit these instructions to form a valid walk.

In the second sample test, Memory is told to walk up, then down, then up, then right. One possible solution is to change s to "LDUR". This string uses 1 edit, which is the minimum possible. It also ends at the origin.