meetforever/GRPO_CL huggingface dataset:
user: Anna is a girl so brave that she is loved by everyone in the city and citizens love her cookies. She is planning to hold a party with cookies. Now she has $a$ vanilla cookies and $b$ chocolate cookies for the party.

She invited $n$ guests of the first type and $m$ guests of the second type to the party. They will come to the party in some order. After coming to the party, each guest will choose the type of cookie (vanilla or chocolate) to eat. There is a difference in the way how they choose that type:

If there are $v$ vanilla cookies and $c$ chocolate cookies at the moment, when the guest comes, then  if the guest of the first type: if $v>c$ the guest selects a vanilla cookie. Otherwise, the guest selects a chocolate cookie.  if the guest of the second type: if $v>c$ the guest selects a chocolate cookie. Otherwise, the guest selects a vanilla cookie. 

After that:  If there is at least one cookie of the selected type, the guest eats one.  Otherwise (there are no cookies of the selected type), the guest gets angry and returns to home. 

Anna wants to know if there exists some order of guests, such that no one guest gets angry. Your task is to answer her question.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case, the only line contains four integers $a$, $b$, $n$, $m$ ($0 \le a,b,n,m \le 10^{18}, n+m \neq 0$).


-----Output-----

For each test case, print the answer in one line. If there exists at least one valid order, print "Yes". Otherwise, print "No".

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


-----Example-----
Input
6
2 2 1 2
0 100 0 1
12 13 25 1
27 83 14 25
0 0 1 0
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Output
Yes
No
No
Yes
No
Yes



-----Note-----

In the first test case, let's consider the order $\{1, 2, 2\}$ of types of guests. Then:  The first guest eats a chocolate cookie. After that, there are $2$ vanilla cookies and $1$ chocolate cookie.  The second guest eats a chocolate cookie. After that, there are $2$ vanilla cookies and $0$ chocolate cookies.  The last guest selects a chocolate cookie, but there are no chocolate cookies. So, the guest gets angry. 

So, this order can't be chosen by Anna.

Let's consider the order $\{2, 2, 1\}$ of types of guests. Then:  The first guest eats a vanilla cookie. After that, there is $1$ vanilla cookie and $2$ chocolate cookies.  The second guest eats a vanilla cookie. After that, there are $0$ vanilla cookies and $2$ chocolate cookies.  The last guest eats a chocolate cookie. After that, there are $0$ vanilla cookies and $1$ chocolate cookie. 

So, the answer to this test case is "Yes".

In the fifth test case, it is illustrated, that the number of cookies ($a + b$) can be equal to zero, but the number of guests ($n + m$) can't be equal to zero.

In the sixth test case, be careful about the overflow of $32$-bit integer type.
user: You are given an array $a_1, a_2, \dots, a_n$ where all $a_i$ are integers and greater than $0$.

 In one operation, you can choose two different indices $i$ and $j$ ($1 \le i, j \le n$). If $gcd(a_i, a_j)$ is equal to the minimum element of the whole array $a$, you can swap $a_i$ and $a_j$. $gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

 Now you'd like to make $a$ non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.

 An array $a$ is non-decreasing if and only if $a_1 \le a_2 \le \ldots \le a_n$.


-----Input-----

 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

 The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of array $a$.

 The second line of each test case contains $n$ positive integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 10^9$) — the array itself.

 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

 For each test case, output "YES" if it is possible to make the array $a$ non-decreasing using the described operation, or "NO" if it is impossible to do so.


-----Example-----
Input
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4

Output
YES
YES
YES
NO



-----Note-----

 In the first and third sample, the array is already non-decreasing.

 In the second sample, we can swap $a_1$ and $a_3$ first, and swap $a_1$ and $a_5$ second to make the array non-decreasing.

 In the forth sample, we cannot the array non-decreasing using the operation.
user: Gleb ordered pizza home. When the courier delivered the pizza, he was very upset, because several pieces of sausage lay on the crust, and he does not really like the crust.

The pizza is a circle of radius r and center at the origin. Pizza consists of the main part — circle of radius r - d with center at the origin, and crust around the main part of the width d. Pieces of sausage are also circles. The radius of the i -th piece of the sausage is r_{i}, and the center is given as a pair (x_{i}, y_{i}).

Gleb asks you to help determine the number of pieces of sausage caught on the crust. A piece of sausage got on the crust, if it completely lies on the crust.


-----Input-----

First string contains two integer numbers r and d (0 ≤ d < r ≤ 500) — the radius of pizza and the width of crust.

Next line contains one integer number n — the number of pieces of sausage (1 ≤ n ≤ 10^5).

Each of next n lines contains three integer numbers x_{i}, y_{i} and r_{i} ( - 500 ≤ x_{i}, y_{i} ≤ 500, 0 ≤ r_{i} ≤ 500), where x_{i} and y_{i} are coordinates of the center of i-th peace of sausage, r_{i} — radius of i-th peace of sausage.


-----Output-----

Output the number of pieces of sausage that lay on the crust.


-----Examples-----
Input
8 4
7
7 8 1
-7 3 2
0 2 1
0 -2 2
-3 -3 1
0 6 2
5 3 1

Output
2

Input
10 8
4
0 0 9
0 0 10
1 0 1
1 0 2

Output
0



-----Note-----

Below is a picture explaining the first example. Circles of green color denote pieces of sausage lying on the crust.

 [Image]
user: Little Mishka is a great traveller and she visited many countries. After thinking about where to travel this time, she chose XXX — beautiful, but little-known northern country.

Here are some interesting facts about XXX:  XXX consists of n cities, k of whose (just imagine!) are capital cities.  All of cities in the country are beautiful, but each is beautiful in its own way. Beauty value of i-th city equals to c_{i}.  All the cities are consecutively connected by the roads, including 1-st and n-th city, forming a cyclic route 1 — 2 — ... — n — 1. Formally, for every 1 ≤ i < n there is a road between i-th and i + 1-th city, and another one between 1-st and n-th city.  Each capital city is connected with each other city directly by the roads. Formally, if city x is a capital city, then for every 1 ≤ i ≤ n,  i ≠ x, there is a road between cities x and i.  There is at most one road between any two cities.  Price of passing a road directly depends on beauty values of cities it connects. Thus if there is a road between cities i and j, price of passing it equals c_{i}·c_{j}.

Mishka started to gather her things for a trip, but didn't still decide which route to follow and thus she asked you to help her determine summary price of passing each of the roads in XXX. Formally, for every pair of cities a and b (a < b), such that there is a road between a and b you are to find sum of products c_{a}·c_{b}. Will you help her?


-----Input-----

The first line of the input contains two integers n and k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n) — the number of cities in XXX and the number of capital cities among them.

The second line of the input contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10 000) — beauty values of the cities.

The third line of the input contains k distinct integers id_1, id_2, ..., id_{k} (1 ≤ id_{i} ≤ n) — indices of capital cities. Indices are given in ascending order.


-----Output-----

Print the only integer — summary price of passing each of the roads in XXX.


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

Output
17
Input
5 2
3 5 2 2 4
1 4

Output
71


-----Note-----

This image describes first sample case:

[Image]

It is easy to see that summary price is equal to 17.

This image describes second sample case:

[Image]

It is easy to see that summary price is equal to 71.
user: Chef Monocarp has just put $n$ dishes into an oven. He knows that the $i$-th dish has its optimal cooking time equal to $t_i$ minutes.

At any positive integer minute $T$ Monocarp can put no more than one dish out of the oven. If the $i$-th dish is put out at some minute $T$, then its unpleasant value is $|T - t_i|$ — the absolute difference between $T$ and $t_i$. Once the dish is out of the oven, it can't go back in.

Monocarp should put all the dishes out of the oven. What is the minimum total unpleasant value Monocarp can obtain?


-----Input-----

The first line contains a single integer $q$ ($1 \le q \le 200$) — the number of testcases.

Then $q$ testcases follow.

The first line of the testcase contains a single integer $n$ ($1 \le n \le 200$) — the number of dishes in the oven.

The second line of the testcase contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le n$) — the optimal cooking time for each dish.

The sum of $n$ over all $q$ testcases doesn't exceed $200$.


-----Output-----

Print a single integer for each testcase — the minimum total unpleasant value Monocarp can obtain when he puts out all the dishes out of the oven. Remember that Monocarp can only put the dishes out at positive integer minutes and no more than one dish at any minute.


-----Example-----
Input
6
6
4 2 4 4 5 2
7
7 7 7 7 7 7 7
1
1
5
5 1 2 4 3
4
1 4 4 4
21
21 8 1 4 1 5 21 1 8 21 11 21 11 3 12 8 19 15 9 11 13

Output
4
12
0
0
2
21



-----Note-----

In the first example Monocarp can put out the dishes at minutes $3, 1, 5, 4, 6, 2$. That way the total unpleasant value will be $|4 - 3| + |2 - 1| + |4 - 5| + |4 - 4| + |6 - 5| + |2 - 2| = 4$.

In the second example Monocarp can put out the dishes at minutes $4, 5, 6, 7, 8, 9, 10$.

In the third example Monocarp can put out the dish at minute $1$.

In the fourth example Monocarp can put out the dishes at minutes $5, 1, 2, 4, 3$.

In the fifth example Monocarp can put out the dishes at minutes $1, 3, 4, 5$.
user: A string is called beautiful if no two consecutive characters are equal. For example, "ababcb", "a" and "abab" are beautiful strings, while "aaaaaa", "abaa" and "bb" are not.

Ahcl wants to construct a beautiful string. He has a string $s$, consisting of only characters 'a', 'b', 'c' and '?'. Ahcl needs to replace each character '?' with one of the three characters 'a', 'b' or 'c', such that the resulting string is beautiful. Please help him!

More formally, after replacing all characters '?', the condition $s_i \neq s_{i+1}$ should be satisfied for all $1 \leq i \leq |s| - 1$, where $|s|$ is the length of the string $s$.


-----Input-----

The first line contains positive integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Next $t$ lines contain the descriptions of test cases.

Each line contains a non-empty string $s$ consisting of only characters 'a', 'b', 'c' and '?'. 

It is guaranteed that in each test case a string $s$ has at least one character '?'. The sum of lengths of strings $s$ in all test cases does not exceed $10^5$.


-----Output-----

For each test case given in the input print the answer in the following format:

  If it is impossible to create a beautiful string, print "-1" (without quotes);  Otherwise, print the resulting beautiful string after replacing all '?' characters. If there are multiple answers, you can print any of them. 


-----Example-----
Input
3
a???cb
a??bbc
a?b?c

Output
ababcb
-1
acbac



-----Note-----

In the first test case, all possible correct answers are "ababcb", "abcacb", "abcbcb", "acabcb" and "acbacb". The two answers "abcbab" and "abaabc" are incorrect, because you can replace only '?' characters and the resulting string must be beautiful.

In the second test case, it is impossible to create a beautiful string, because the $4$-th and $5$-th characters will be always equal.

In the third test case, the only answer is "acbac".
user: There are $n$ segments on a $Ox$ axis $[l_1, r_1]$, $[l_2, r_2]$, ..., $[l_n, r_n]$. Segment $[l, r]$ covers all points from $l$ to $r$ inclusive, so all $x$ such that $l \le x \le r$.

Segments can be placed arbitrarily  — be inside each other, coincide and so on. Segments can degenerate into points, that is $l_i=r_i$ is possible.

Union of the set of segments is such a set of segments which covers exactly the same set of points as the original set. For example:  if $n=3$ and there are segments $[3, 6]$, $[100, 100]$, $[5, 8]$ then their union is $2$ segments: $[3, 8]$ and $[100, 100]$;  if $n=5$ and there are segments $[1, 2]$, $[2, 3]$, $[4, 5]$, $[4, 6]$, $[6, 6]$ then their union is $2$ segments: $[1, 3]$ and $[4, 6]$. 

Obviously, a union is a set of pairwise non-intersecting segments.

You are asked to erase exactly one segment of the given $n$ so that the number of segments in the union of the rest $n-1$ segments is maximum possible.

For example, if $n=4$ and there are segments $[1, 4]$, $[2, 3]$, $[3, 6]$, $[5, 7]$, then:  erasing the first segment will lead to $[2, 3]$, $[3, 6]$, $[5, 7]$ remaining, which have $1$ segment in their union;  erasing the second segment will lead to $[1, 4]$, $[3, 6]$, $[5, 7]$ remaining, which have $1$ segment in their union;  erasing the third segment will lead to $[1, 4]$, $[2, 3]$, $[5, 7]$ remaining, which have $2$ segments in their union;  erasing the fourth segment will lead to $[1, 4]$, $[2, 3]$, $[3, 6]$ remaining, which have $1$ segment in their union. 

Thus, you are required to erase the third segment to get answer $2$.

Write a program that will find the maximum number of segments in the union of $n-1$ segments if you erase any of the given $n$ segments.

Note that if there are multiple equal segments in the given set, then you can erase only one of them anyway. So the set after erasing will have exactly $n-1$ segments.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. Then the descriptions of $t$ test cases follow.

The first of each test case contains a single integer $n$ ($2 \le n \le 2\cdot10^5$) — the number of segments in the given set. Then $n$ lines follow, each contains a description of a segment — a pair of integers $l_i$, $r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), where $l_i$ and $r_i$ are the coordinates of the left and right borders of the $i$-th segment, respectively.

The segments are given in an arbitrary order.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

Print $t$ integers — the answers to the $t$ given test cases in the order of input. The answer is the maximum number of segments in the union of $n-1$ segments if you erase any of the given $n$ segments.


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

Output
2
1
5
user: This is the hard version of this problem. The only difference is the constraint on $k$ — the number of gifts in the offer. In this version: $2 \le k \le n$.

Vasya came to the store to buy goods for his friends for the New Year. It turned out that he was very lucky — today the offer "$k$ of goods for the price of one" is held in store.

Using this offer, Vasya can buy exactly $k$ of any goods, paying only for the most expensive of them. Vasya decided to take this opportunity and buy as many goods as possible for his friends with the money he has.

More formally, for each good, its price is determined by $a_i$ — the number of coins it costs. Initially, Vasya has $p$ coins. He wants to buy the maximum number of goods. Vasya can perform one of the following operations as many times as necessary:

  Vasya can buy one good with the index $i$ if he currently has enough coins (i.e $p \ge a_i$). After buying this good, the number of Vasya's coins will decrease by $a_i$, (i.e it becomes $p := p - a_i$).  Vasya can buy a good with the index $i$, and also choose exactly $k-1$ goods, the price of which does not exceed $a_i$, if he currently has enough coins (i.e $p \ge a_i$). Thus, he buys all these $k$ goods, and his number of coins decreases by $a_i$ (i.e it becomes $p := p - a_i$). 

Please note that each good can be bought no more than once.

For example, if the store now has $n=5$ goods worth $a_1=2, a_2=4, a_3=3, a_4=5, a_5=7$, respectively, $k=2$, and Vasya has $6$ coins, then he can buy $3$ goods. A good with the index $1$ will be bought by Vasya without using the offer and he will pay $2$ coins. Goods with the indices $2$ and $3$ Vasya will buy using the offer and he will pay $4$ coins. It can be proved that Vasya can not buy more goods with six coins.

Help Vasya to find out the maximum number of goods he can buy.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The next lines contain a description of $t$ test cases. 

The first line of each test case contains three integers $n, p, k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le p \le 2\cdot10^9$, $2 \le k \le n$) — the number of goods in the store, the number of coins Vasya has and the number of goods that can be bought by the price of the most expensive of them.

The second line of each test case contains $n$ integers $a_i$ ($1 \le a_i \le 10^4$) — the prices of goods.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case in a separate line print one integer $m$ — the maximum number of goods that Vasya can buy.


-----Example-----
Input
8
5 6 2
2 4 3 5 7
5 11 2
2 4 3 5 7
3 2 3
4 2 6
5 2 3
10 1 3 9 2
2 10000 2
10000 10000
2 9999 2
10000 10000
4 6 4
3 2 3 2
5 5 3
1 2 2 1 2

Output
3
4
1
1
2
0
4
5
user: There are $n$ models in the shop numbered from $1$ to $n$, with sizes $s_1, s_2, \ldots, s_n$.

Orac will buy some of the models and will arrange them in the order of increasing numbers (i.e. indices, but not sizes).

Orac thinks that the obtained arrangement is beatiful, if for any two adjacent models with indices $i_j$ and $i_{j+1}$ (note that $i_j < i_{j+1}$, because Orac arranged them properly), $i_{j+1}$ is divisible by $i_j$ and $s_{i_j} < s_{i_{j+1}}$.

For example, for $6$ models with sizes $\{3, 6, 7, 7, 7, 7\}$, he can buy models with indices $1$, $2$, and $6$, and the obtained arrangement will be beautiful. Also, note that the arrangement with exactly one model is also considered beautiful.

Orac wants to know the maximum number of models that he can buy, and he may ask you these queries many times.


-----Input-----

The first line contains one integer $t\ (1 \le t\le 100)$: the number of queries.

Each query contains two lines. The first line contains one integer $n\ (1\le n\le 100\,000)$: the number of models in the shop, and the second line contains $n$ integers $s_1,\dots,s_n\ (1\le s_i\le 10^9)$: the sizes of models.

It is guaranteed that the total sum of $n$ is at most $100\,000$.


-----Output-----

Print $t$ lines, the $i$-th of them should contain the maximum number of models that Orac can buy for the $i$-th query.


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

Output
2
3
1
1



-----Note-----

In the first query, for example, Orac can buy models with indices $2$ and $4$, the arrangement will be beautiful because $4$ is divisible by $2$ and $6$ is more than $3$. By enumerating, we can easily find that there are no beautiful arrangements with more than two models. 

In the second query, Orac can buy models with indices $1$, $3$, and $6$. By enumerating, we can easily find that there are no beautiful arrangements with more than three models. 

In the third query, there are no beautiful arrangements with more than one model.
user: You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ positive integers. 

Initially you are standing at index $1$ and have a score equal to $a_1$. You can perform two kinds of moves:   move right — go from your current index $x$ to $x+1$ and add $a_{x+1}$ to your score. This move can only be performed if $x<n$.  move left — go from your current index $x$ to $x-1$ and add $a_{x-1}$ to your score. This move can only be performed if $x>1$. Also, you can't perform two or more moves to the left in a row. 

You want to perform exactly $k$ moves. Also, there should be no more than $z$ moves to the left among them.

What is the maximum score you can achieve?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains three integers $n, k$ and $z$ ($2 \le n \le 10^5$, $1 \le k \le n - 1$, $0 \le z \le min(5, k)$) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.

The second line of each testcase contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$) — the given array.

The sum of $n$ over all testcases does not exceed $3 \cdot 10^5$.


-----Output-----

Print $t$ integers — for each testcase output the maximum score you can achieve if you make exactly $k$ moves in total, no more than $z$ of them are to the left and there are no two or more moves to the left in a row.


-----Example-----
Input
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9

Output
15
19
150
56



-----Note-----

In the first testcase you are not allowed to move left at all. So you make four moves to the right and obtain the score $a_1 + a_2 + a_3 + a_4 + a_5$.

In the second example you can move one time to the left. So we can follow these moves: right, right, left, right. The score will be $a_1 + a_2 + a_3 + a_2 + a_3$.

In the third example you can move four times to the left but it's not optimal anyway, you can just move four times to the right and obtain the score $a_1 + a_2 + a_3 + a_4 + a_5$.