meetforever/GRPO_CL huggingface dataset:
user: You are given a multiset S consisting of positive integers (initially empty). There are two kind of queries:   Add a positive integer to S, the newly added integer is not less than any number in it.  Find a subset s of the set S such that the value $\operatorname{max}(s) - \operatorname{mean}(s)$ is maximum possible. Here max(s) means maximum value of elements in s, $\operatorname{mean}(s)$ — the average value of numbers in s. Output this maximum possible value of $\operatorname{max}(s) - \operatorname{mean}(s)$. 


-----Input-----

The first line contains a single integer Q (1 ≤ Q ≤ 5·10^5) — the number of queries.

Each of the next Q lines contains a description of query. For queries of type 1 two integers 1 and x are given, where x (1 ≤ x ≤ 10^9) is a number that you should add to S. It's guaranteed that x is not less than any number in S. For queries of type 2, a single integer 2 is given.

It's guaranteed that the first query has type 1, i. e. S is not empty when a query of type 2 comes.


-----Output-----

Output the answer for each query of the second type in the order these queries are given in input. Each number should be printed in separate line.

Your answer is considered correct, if each of your answers has absolute or relative error not greater than 10^{ - 6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-6}$.


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

Output
0.0000000000
0.5000000000
3.0000000000

Input
4
1 1
1 4
1 5
2

Output
2.0000000000
user: Bimokh is Mashmokh's boss. For the following n days he decided to pay to his workers in a new way. At the beginning of each day he will give each worker a certain amount of tokens. Then at the end of each day each worker can give some of his tokens back to get a certain amount of money. The worker can save the rest of tokens but he can't use it in any other day to get more money. If a worker gives back w tokens then he'll get $\lfloor \frac{w \cdot a}{b} \rfloor$ dollars. 

Mashmokh likes the tokens however he likes money more. That's why he wants to save as many tokens as possible so that the amount of money he gets is maximal possible each day. He has n numbers x_1, x_2, ..., x_{n}. Number x_{i} is the number of tokens given to each worker on the i-th day. Help him calculate for each of n days the number of tokens he can save.


-----Input-----

The first line of input contains three space-separated integers n, a, b (1 ≤ n ≤ 10^5; 1 ≤ a, b ≤ 10^9). The second line of input contains n space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^9).


-----Output-----

Output n space-separated integers. The i-th of them is the number of tokens Mashmokh can save on the i-th day.


-----Examples-----
Input
5 1 4
12 6 11 9 1

Output
0 2 3 1 1 
Input
3 1 2
1 2 3

Output
1 0 1 
Input
1 1 1
1

Output
0
user: Johnny drives a truck and must deliver a package from his hometown to the district center. His hometown is located at point 0 on a number line, and the district center is located at the point d.

Johnny's truck has a gas tank that holds exactly n liters, and his tank is initially full. As he drives, the truck consumes exactly one liter per unit distance traveled. Moreover, there are m gas stations located at various points along the way to the district center. The i-th station is located at the point x_{i} on the number line and sells an unlimited amount of fuel at a price of p_{i} dollars per liter. Find the minimum cost Johnny must pay for fuel to successfully complete the delivery.


-----Input-----

The first line of input contains three space separated integers d, n, and m (1 ≤ n ≤ d ≤ 10^9, 1 ≤ m ≤ 200 000) — the total distance to the district center, the volume of the gas tank, and the number of gas stations, respectively.

Each of the next m lines contains two integers x_{i}, p_{i} (1 ≤ x_{i} ≤ d - 1, 1 ≤ p_{i} ≤ 10^6) — the position and cost of gas at the i-th gas station. It is guaranteed that the positions of the gas stations are distinct.


-----Output-----

Print a single integer — the minimum cost to complete the delivery. If there is no way to complete the delivery, print -1.


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

Output
22

Input
16 5 2
8 2
5 1

Output
-1



-----Note-----

In the first sample, Johnny's truck holds 4 liters. He can drive 3 units to the first gas station, buy 2 liters of gas there (bringing the tank to 3 liters total), drive 3 more units to the third gas station, buy 4 liters there to fill up his tank, and then drive straight to the district center. His total cost is 2·5 + 4·3 = 22 dollars.

In the second sample, there is no way for Johnny to make it to the district center, as his tank cannot hold enough gas to take him from the latest gas station to the district center.
user: Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Empire may be evil, but it is not stupid!). The encryption has several levels of security, and here is how the first one looks.

Heidi is presented with a screen that shows her a sequence of integers A and a positive integer p. She knows that the encryption code is a single number S, which is defined as follows:

Define the score of X to be the sum of the elements of X modulo p.

Heidi is given a sequence A that consists of N integers, and also given an integer p. She needs to split A into 2 parts such that:   Each part contains at least 1 element of A, and each part consists of contiguous elements of A.  The two parts do not overlap.  The total sum S of the scores of those two parts is maximized. This is the encryption code. 

Output the sum S, which is the encryption code.


-----Input-----

The first line of the input contains two space-separated integer N and p (2 ≤ N ≤ 100 000, 2 ≤ p ≤ 10 000) – the number of elements in A, and the modulo for computing scores, respectively.

The second line contains N space-separated integers which are the elements of A. Each integer is from the interval [1, 1 000 000].


-----Output-----

Output the number S as described in the problem statement.


-----Examples-----
Input
4 10
3 4 7 2

Output
16

Input
10 12
16 3 24 13 9 8 7 5 12 12

Output
13



-----Note-----

In the first example, the score is maximized if the input sequence is split into two parts as (3, 4), (7, 2). It gives the total score of $(3 + 4 \operatorname{mod} 10) +(7 + 2 \operatorname{mod} 10) = 16$.

In the second example, the score is maximized if the first part consists of the first three elements, and the second part consists of the rest. Then, the score is $(16 + 3 + 24 \operatorname{mod} 12) +(13 + 9 + 8 + 7 + 5 + 12 + 12 \operatorname{mod} 12) = 7 + 6 = 13$.
user: Amr bought a new video game "Guess Your Way Out! II". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.

Let's index all the nodes of the tree such that   The root is number 1  Each internal node i (i ≤ 2^{h} - 1 - 1) will have a left child with index = 2i and a right child with index = 2i + 1 

The level of a node is defined as 1 for a root, or 1 + level of parent of the node otherwise. The vertices of the level h are called leaves. The exit to the maze is located at some leaf node n, the player doesn't know where the exit is so he has to guess his way out! 

In the new version of the game the player is allowed to ask questions on the format "Does the ancestor(exit, i) node number belong to the range [L, R]?". Here ancestor(v, i) is the ancestor of a node v that located in the level i. The game will answer with "Yes" or "No" only. The game is designed such that it doesn't always answer correctly, and sometimes it cheats to confuse the player!.

Amr asked a lot of questions and got confused by all these answers, so he asked you to help him. Given the questions and its answers, can you identify whether the game is telling contradictory information or not? If the information is not contradictory and the exit node can be determined uniquely, output its number. If the information is not contradictory, but the exit node isn't defined uniquely, output that the number of questions is not sufficient. Otherwise output that the information is contradictory.


-----Input-----

The first line contains two integers h, q (1 ≤ h ≤ 50, 0 ≤ q ≤ 10^5), the height of the tree and the number of questions respectively.

The next q lines will contain four integers each i, L, R, ans (1 ≤ i ≤ h, 2^{i} - 1 ≤ L ≤ R ≤ 2^{i} - 1, $\text{ans} \in \{0,1 \}$), representing a question as described in the statement with its answer (ans = 1 if the answer is "Yes" and ans = 0 if the answer is "No").


-----Output-----

If the information provided by the game is contradictory output "Game cheated!" without the quotes.

Else if you can uniquely identify the exit to the maze output its index. 

Otherwise output "Data not sufficient!" without the quotes.


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

Output
7
Input
4 3
4 10 14 1
3 6 6 0
2 3 3 1

Output
14
Input
4 2
3 4 6 1
4 12 15 1

Output
Data not sufficient!
Input
4 2
3 4 5 1
2 3 3 1

Output
Game cheated!


-----Note-----

Node u is an ancestor of node v if and only if   u is the same node as v,  u is the parent of node v,  or u is an ancestor of the parent of node v. 

In the first sample test there are 4 leaf nodes 4, 5, 6, 7. The first question says that the node isn't in the range [4, 6] so the exit is node number 7.

In the second sample test there are 8 leaf nodes. After the first question the exit is in the range [10, 14]. After the second and the third questions only node number 14 is correct. Check the picture below to fully understand.

[Image]
user: Vladimir would like to prepare a present for his wife: they have an anniversary! He decided to buy her exactly $n$ flowers.

Vladimir went to a flower shop, and he was amazed to see that there are $m$ types of flowers being sold there, and there is unlimited supply of flowers of each type. Vladimir wants to choose flowers to maximize the happiness of his wife. He knows that after receiving the first flower of the $i$-th type happiness of his wife increases by $a_i$ and after receiving each consecutive flower of this type her happiness increases by $b_i$. That is, if among the chosen flowers there are $x_i > 0$ flowers of type $i$, his wife gets $a_i + (x_i - 1) \cdot b_i$ additional happiness (and if there are no flowers of type $i$, she gets nothing for this particular type).

Please help Vladimir to choose exactly $n$ flowers to maximize the total happiness of his wife.


-----Input-----

The first line contains the only integer $t$ ($1 \leq t \leq 10\,000$), the number of test cases. It is followed by $t$ descriptions of the test cases.

Each test case description starts with two integers $n$ and $m$ ($1 \le n \le 10^9$, $1 \le m \le 100\,000$), the number of flowers Vladimir needs to choose and the number of types of available flowers.

The following $m$ lines describe the types of flowers: each line contains integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$) for $i$-th available type of flowers.

The test cases are separated by a blank line. It is guaranteed that the sum of values $m$ among all test cases does not exceed $100\,000$.


-----Output-----

For each test case output a single integer: the maximum total happiness of Vladimir's wife after choosing exactly $n$ flowers optimally.


-----Example-----
Input
2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1

Output
14
16



-----Note-----

In the first example case Vladimir can pick 1 flower of the first type and 3 flowers of the second type, in this case the total happiness equals $5 + (1 + 2 \cdot 4) = 14$.

In the second example Vladimir can pick 2 flowers of the first type, 2 flowers of the second type, and 1 flower of the third type, in this case the total happiness equals $(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$.
user: People in the Tomskaya region like magic formulas very much. You can see some of them below.

Imagine you are given a sequence of positive integer numbers p_1, p_2, ..., p_{n}. Lets write down some magic formulas:$q_{i} = p_{i} \oplus(i \operatorname{mod} 1) \oplus(i \operatorname{mod} 2) \oplus \cdots \oplus(i \operatorname{mod} n)$$Q = q_{1} \oplus q_{2} \oplus \ldots \oplus q_{n}$

Here, "mod" means the operation of taking the residue after dividing.

The expression $x \oplus y$ means applying the bitwise xor (excluding "OR") operation to integers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by "^", in Pascal — by "xor".

People in the Tomskaya region like magic formulas very much, but they don't like to calculate them! Therefore you are given the sequence p, calculate the value of Q.


-----Input-----

The first line of the input contains the only integer n (1 ≤ n ≤ 10^6). The next line contains n integers: p_1, p_2, ..., p_{n} (0 ≤ p_{i} ≤ 2·10^9).


-----Output-----

The only line of output should contain a single integer — the value of Q.


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

Output
3
user: There are n points marked on the plane. The points are situated in such a way that they form a regular polygon (marked points are its vertices, and they are numbered in counter-clockwise order). You can draw n - 1 segments, each connecting any two marked points, in such a way that all points have to be connected with each other (directly or indirectly).

But there are some restrictions. Firstly, some pairs of points cannot be connected directly and have to be connected undirectly. Secondly, the segments you draw must not intersect in any point apart from the marked points (that is, if any two segments intersect and their intersection is not a marked point, then the picture you have drawn is invalid).

How many ways are there to connect all vertices with n - 1 segments? Two ways are considered different iff there exist some pair of points such that a segment is drawn between them in the first way of connection, but it is not drawn between these points in the second one. Since the answer might be large, output it modulo 10^9 + 7.


-----Input-----

The first line contains one number n (3 ≤ n ≤ 500) — the number of marked points.

Then n lines follow, each containing n elements. a_{i}, j (j-th element of line i) is equal to 1 iff you can connect points i and j directly (otherwise a_{i}, j = 0). It is guaranteed that for any pair of points a_{i}, j = a_{j}, i, and for any point a_{i}, i = 0.


-----Output-----

Print the number of ways to connect points modulo 10^9 + 7.


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

Output
1

Input
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Output
12

Input
3
0 0 0
0 0 1
0 1 0

Output
0
user: "The zombies are lurking outside. Waiting. Moaning. And when they come..."

"When they come?"

"I hope the Wall is high enough."

Zombie attacks have hit the Wall, our line of defense in the North. Its protection is failing, and cracks are showing. In places, gaps have appeared, splitting the wall into multiple segments. We call on you for help. Go forth and explore the wall! Report how many disconnected segments there are.

The wall is a two-dimensional structure made of bricks. Each brick is one unit wide and one unit high. Bricks are stacked on top of each other to form columns that are up to R bricks high. Each brick is placed either on the ground or directly on top of another brick. Consecutive non-empty columns form a wall segment. The entire wall, all the segments and empty columns in-between, is C columns wide.


-----Input-----

The first line of the input consists of two space-separated integers R and C, 1 ≤ R, C ≤ 100. The next R lines provide a description of the columns as follows:   each of the R lines contains a string of length C,  the c-th character of line r is B if there is a brick in column c and row R - r + 1, and . otherwise.  The input will contain at least one character B and it will be valid.


-----Output-----

The number of wall segments in the input configuration.


-----Examples-----
Input
3 7
.......
.......
.BB.B..

Output
2

Input
4 5
..B..
..B..
B.B.B
BBB.B

Output
2

Input
4 6
..B...
B.B.BB
BBB.BB
BBBBBB

Output
1

Input
1 1
B

Output
1

Input
10 7
.......
.......
.......
.......
.......
.......
.......
.......
...B...
B.BB.B.

Output
3

Input
8 8
........
........
........
........
.B......
.B.....B
.B.....B
.BB...BB

Output
2



-----Note-----

In the first sample case, the 2nd and 3rd columns define the first wall segment, and the 5th column defines the second.
user: Mike and !Mike are old childhood rivals, they are opposite in everything they do, except programming. Today they have a problem they cannot solve on their own, but together (with you) — who knows? 

Every one of them has an integer sequences a and b of length n. Being given a query of the form of pair of integers (l, r), Mike can instantly tell the value of $\operatorname{max}_{i = l}^{r} a_{i}$ while !Mike can instantly tell the value of $\operatorname{min}_{i = l} b_{i}$.

Now suppose a robot (you!) asks them all possible different queries of pairs of integers (l, r) (1 ≤ l ≤ r ≤ n) (so he will make exactly n(n + 1) / 2 queries) and counts how many times their answers coincide, thus for how many pairs $\operatorname{max}_{i = l}^{r} a_{i} = \operatorname{min}_{i = l} b_{i}$ is satisfied.

How many occasions will the robot count?


-----Input-----

The first line contains only integer n (1 ≤ n ≤ 200 000).

The second line contains n integer numbers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the sequence a.

The third line contains n integer numbers b_1, b_2, ..., b_{n} ( - 10^9 ≤ b_{i} ≤ 10^9) — the sequence b.


-----Output-----

Print the only integer number — the number of occasions the robot will count, thus for how many pairs $\operatorname{max}_{i = l}^{r} a_{i} = \operatorname{min}_{i = l} b_{i}$ is satisfied.


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

Output
2

Input
3
3 3 3
1 1 1

Output
0



-----Note-----

The occasions in the first sample case are:

1.l = 4,r = 4 since max{2} = min{2}.

2.l = 4,r = 5 since max{2, 1} = min{2, 3}.

There are no occasions in the second sample case since Mike will answer 3 to any query pair, but !Mike will always answer 1.
user: Pushok the dog has been chasing Imp for a few hours already. $48$ 

Fortunately, Imp knows that Pushok is afraid of a robot vacuum cleaner. 

While moving, the robot generates a string t consisting of letters 's' and 'h', that produces a lot of noise. We define noise of string t as the number of occurrences of string "sh" as a subsequence in it, in other words, the number of such pairs (i, j), that i < j and $t_{i} = s$ and $t_{j} = h$. 

The robot is off at the moment. Imp knows that it has a sequence of strings t_{i} in its memory, and he can arbitrary change their order. When the robot is started, it generates the string t as a concatenation of these strings in the given order. The noise of the resulting string equals the noise of this concatenation.

Help Imp to find the maximum noise he can achieve by changing the order of the strings.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of strings in robot's memory.

Next n lines contain the strings t_1, t_2, ..., t_{n}, one per line. It is guaranteed that the strings are non-empty, contain only English letters 's' and 'h' and their total length does not exceed 10^5.


-----Output-----

Print a single integer — the maxumum possible noise Imp can achieve by changing the order of the strings.


-----Examples-----
Input
4
ssh
hs
s
hhhs

Output
18

Input
2
h
s

Output
1



-----Note-----

The optimal concatenation in the first sample is ssshhshhhs.
user: Ayush and Ashish play a game on an unrooted tree consisting of $n$ nodes numbered $1$ to $n$. Players make the following move in turns:   Select any leaf node in the tree and remove it together with any edge which has this node as one of its endpoints. A leaf node is a node with degree less than or equal to $1$. 

A tree is a connected undirected graph without cycles.

There is a special node numbered $x$. The player who removes this node wins the game. 

Ayush moves first. Determine the winner of the game if each player plays optimally.


-----Input-----

The first line of the input contains a single integer $t$ $(1 \leq t \leq 10)$ — the number of testcases. The description of the test cases follows.

The first line of each testcase contains two integers $n$ and $x$ $(1\leq n \leq 1000, 1 \leq x \leq n)$ — the number of nodes in the tree and the special node respectively.

Each of the next $n-1$ lines contain two integers $u$, $v$ $(1 \leq u, v \leq n, \text{ } u \ne v)$, meaning that there is an edge between nodes $u$ and $v$ in the tree.


-----Output-----

For every test case, if Ayush wins the game, print "Ayush", otherwise print "Ashish" (without quotes).


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

Output
Ashish

Input
1
3 2
1 2
1 3

Output
Ayush



-----Note-----

For the $1$st test case, Ayush can only remove node $2$ or $3$, after which node $1$ becomes a leaf node and Ashish can remove it in his turn.

For the $2$nd test case, Ayush can remove node $2$ in the first move itself.
user: Smart Beaver recently got interested in a new word game. The point is as follows: count the number of distinct good substrings of some string s. To determine if a string is good or not the game uses rules. Overall there are n rules. Each rule is described by a group of three (p, l, r), where p is a string and l and r (l ≤ r) are integers. We’ll say that string t complies with rule (p, l, r), if the number of occurrences of string t in string p lies between l and r, inclusive. For example, string "ab", complies with rules ("ab", 1, 2) and ("aab", 0, 1), but does not comply with rules ("cd", 1, 2) and ("abab", 0, 1).

A substring s[l... r] (1 ≤ l ≤ r ≤ |s|) of string s = s_1s_2... s_{|}s| (|s| is a length of s) is string s_{l}s_{l} + 1... s_{r}.

Consider a number of occurrences  of string t in string p as a number of pairs of integers l, r (1 ≤ l ≤ r ≤ |p|) such that p[l... r] = t.

We’ll say that string t is good if it complies with all n rules. Smart Beaver asks you to help him to write a program that can calculate the number of distinct good substrings of string s. Two substrings s[x... y] and s[z... w] are cosidered to be distinct iff s[x... y] ≠ s[z... w].


-----Input-----

The first line contains string s. The second line contains integer n. Next n lines contain the rules, one per line. Each of these lines contains a string and two integers p_{i}, l_{i}, r_{i}, separated by single spaces (0 ≤ l_{i} ≤ r_{i} ≤ |p_{i}|). It is guaranteed that all the given strings are non-empty and only contain lowercase English letters.

The input limits for scoring 30 points are (subproblem G1):   0 ≤ n ≤ 10.  The length of string s and the maximum length of string p is  ≤ 200. 

The input limits for scoring 70 points are (subproblems G1+G2):   0 ≤ n ≤ 10.  The length of string s and the maximum length of string p is  ≤ 2000. 

The input limits for scoring 100 points are (subproblems G1+G2+G3):   0 ≤ n ≤ 10.  The length of string s and the maximum length of string p is  ≤ 50000. 


-----Output-----

Print a single integer — the number of good substrings of string s.


-----Examples-----
Input
aaab
2
aa 0 0
aab 1 1

Output
3

Input
ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1

Output
2

Input
a
0

Output
1



-----Note-----

There are three good substrings in the first sample test: «aab», «ab» and «b».

In the second test only substrings «e» and «t» are good.
user: Find an n × n matrix with different numbers from 1 to n^2, so the sum in each row, column and both main diagonals are odd.


-----Input-----

The only line contains odd integer n (1 ≤ n ≤ 49).


-----Output-----

Print n lines with n integers. All the integers should be different and from 1 to n^2. The sum in each row, column and both main diagonals should be odd.


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

Output
1

Input
3

Output
2 1 4
3 5 7
6 9 8