meetforever/GRPO_CL huggingface dataset:
user: Captain Fint is involved in another treasure hunt, but have found only one strange problem. The problem may be connected to the treasure's location or may not. That's why captain Flint decided to leave the solving the problem to his crew and offered an absurdly high reward: one day off. The problem itself sounds like this...

There are two arrays $a$ and $b$ of length $n$. Initially, an $ans$ is equal to $0$ and the following operation is defined:   Choose position $i$ ($1 \le i \le n$);  Add $a_i$ to $ans$;  If $b_i \neq -1$ then add $a_i$ to $a_{b_i}$. 

What is the maximum $ans$ you can get by performing the operation on each $i$ ($1 \le i \le n$) exactly once?

Uncle Bogdan is eager to get the reward, so he is asking your help to find the optimal order of positions to perform the operation on them.


-----Input-----

The first line contains the integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of arrays $a$ and $b$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($−10^6 \le a_i \le 10^6$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$ or $b_i = -1$).

Additional constraint: it's guaranteed that for any $i$ ($1 \le i \le n$) the sequence $b_i, b_{b_i}, b_{b_{b_i}}, \ldots$ is not cyclic, in other words it will always end with $-1$.


-----Output-----

In the first line, print the maximum $ans$ you can get.

In the second line, print the order of operations: $n$ different integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$). The $p_i$ is the position which should be chosen at the $i$-th step. If there are multiple orders, print any of them.


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

Output
10
1 2 3 

Input
2
-1 100
2 -1

Output
99
2 1 

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

Output
-9
3 5 6 1 9 4 10 7 8 2
user: There was once young lass called Mary,  

Whose jokes were occasionally scary.  

On this April's Fool  

Fixed limerick rules  

Allowed her to trip the unwary.



Can she fill all the lines

To work at all times?

On juggling the words

Right around two-thirds

She nearly ran out of rhymes.




-----Input-----

The input contains a single integer $a$ ($4 \le a \le 998$). Not every integer in the range is a valid input for the problem; you are guaranteed that the input will be a valid integer.


-----Output-----

Output a single number.


-----Examples-----
Input
35

Output
57

Input
57

Output
319

Input
391

Output
1723
user: A factory produces thimbles in bulk. Typically, it can produce up to a thimbles a day. However, some of the machinery is defective, so it can currently only produce b thimbles each day. The factory intends to choose a k-day period to do maintenance and construction; it cannot produce any thimbles during this time, but will be restored to its full production of a thimbles per day after the k days are complete.

Initially, no orders are pending. The factory receives updates of the form d_{i}, a_{i}, indicating that a_{i} new orders have been placed for the d_{i}-th day. Each order requires a single thimble to be produced on precisely the specified day. The factory may opt to fill as many or as few of the orders in a single batch as it likes.

As orders come in, the factory owner would like to know the maximum number of orders he will be able to fill if he starts repairs on a given day p_{i}. Help the owner answer his questions.


-----Input-----

The first line contains five integers n, k, a, b, and q (1 ≤ k ≤ n ≤ 200 000, 1 ≤ b < a ≤ 10 000, 1 ≤ q ≤ 200 000) — the number of days, the length of the repair time, the production rates of the factory, and the number of updates, respectively.

The next q lines contain the descriptions of the queries. Each query is of one of the following two forms:   1 d_{i} a_{i} (1 ≤ d_{i} ≤ n, 1 ≤ a_{i} ≤ 10 000), representing an update of a_{i} orders on day d_{i}, or  2 p_{i} (1 ≤ p_{i} ≤ n - k + 1), representing a question: at the moment, how many orders could be filled if the factory decided to commence repairs on day p_{i}? 

It's guaranteed that the input will contain at least one query of the second type.


-----Output-----

For each query of the second type, print a line containing a single integer — the maximum number of orders that the factory can fill over all n days.


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

Output
3
6
4

Input
5 4 10 1 6
1 1 5
1 5 5
1 3 2
1 5 2
2 1
2 2

Output
7
1



-----Note-----

Consider the first sample.

We produce up to 1 thimble a day currently and will produce up to 2 thimbles a day after repairs. Repairs take 2 days.

For the first question, we are able to fill 1 order on day 1, no orders on days 2 and 3 since we are repairing, no orders on day 4 since no thimbles have been ordered for that day, and 2 orders for day 5 since we are limited to our production capacity, for a total of 3 orders filled.

For the third question, we are able to fill 1 order on day 1, 1 order on day 2, and 2 orders on day 5, for a total of 4 orders.
user: Omkar is standing at the foot of Celeste mountain. The summit is $n$ meters away from him, and he can see all of the mountains up to the summit, so for all $1 \leq j \leq n$ he knows that the height of the mountain at the point $j$ meters away from himself is $h_j$ meters. It turns out that for all $j$ satisfying $1 \leq j \leq n - 1$, $h_j < h_{j + 1}$ (meaning that heights are strictly increasing).

Suddenly, a landslide occurs! While the landslide is occurring, the following occurs: every minute, if $h_j + 2 \leq h_{j + 1}$, then one square meter of dirt will slide from position $j + 1$ to position $j$, so that $h_{j + 1}$ is decreased by $1$ and $h_j$ is increased by $1$. These changes occur simultaneously, so for example, if $h_j + 2 \leq h_{j + 1}$ and $h_{j + 1} + 2 \leq h_{j + 2}$ for some $j$, then $h_j$ will be increased by $1$, $h_{j + 2}$ will be decreased by $1$, and $h_{j + 1}$ will be both increased and decreased by $1$, meaning that in effect $h_{j + 1}$ is unchanged during that minute.

The landslide ends when there is no $j$ such that $h_j + 2 \leq h_{j + 1}$. Help Omkar figure out what the values of $h_1, \dots, h_n$ will be after the landslide ends. It can be proven that under the given constraints, the landslide will always end in finitely many minutes.

Note that because of the large amount of input, it is recommended that your code uses fast IO.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^6$). 

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ satisfying $0 \leq h_1 < h_2 < \dots < h_n \leq 10^{12}$ — the heights.


-----Output-----

Output $n$ integers, where the $j$-th integer is the value of $h_j$ after the landslide has stopped.


-----Example-----
Input
4
2 6 7 8

Output
5 5 6 7



-----Note-----

Initially, the mountain has heights $2, 6, 7, 8$.

In the first minute, we have $2 + 2 \leq 6$, so $2$ increases to $3$ and $6$ decreases to $5$, leaving $3, 5, 7, 8$.

In the second minute, we have $3 + 2 \leq 5$ and $5 + 2 \leq 7$, so $3$ increases to $4$, $5$ is unchanged, and $7$ decreases to $6$, leaving $4, 5, 6, 8$.

In the third minute, we have $6 + 2 \leq 8$, so $6$ increases to $7$ and $8$ decreases to $7$, leaving $4, 5, 7, 7$.

In the fourth minute, we have $5 + 2 \leq 7$, so $5$ increases to $6$ and $7$ decreases to $6$, leaving $4, 6, 6, 7$.

In the fifth minute, we have $4 + 2 \leq 6$, so $4$ increases to $5$ and $6$ decreases to $5$, leaving $5, 5, 6, 7$.

In the sixth minute, nothing else can change so the landslide stops and our answer is $5, 5, 6, 7$.
user: This problem is same as the next one, but has smaller constraints.

It was a Sunday morning when the three friends Selena, Shiro and Katie decided to have a trip to the nearby power station (do not try this at home). After arriving at the power station, the cats got impressed with a large power transmission system consisting of many chimneys, electric poles, and wires. Since they are cats, they found those things gigantic.

At the entrance of the station, there is a map describing the complicated wiring system. Selena is the best at math among three friends. He decided to draw the map on the Cartesian plane. Each pole is now a point at some coordinates $(x_i, y_i)$. Since every pole is different, all of the points representing these poles are distinct. Also, every two poles are connected with each other by wires. A wire is a straight line on the plane infinite in both directions. If there are more than two poles lying on the same line, they are connected by a single common wire.

Selena thinks, that whenever two different electric wires intersect, they may interfere with each other and cause damage. So he wonders, how many pairs are intersecting? Could you help him with this problem?


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 50$) — the number of electric poles.

Each of the following $n$ lines contains two integers $x_i$, $y_i$ ($-10^4 \le x_i, y_i \le 10^4$) — the coordinates of the poles.

It is guaranteed that all of these $n$ points are distinct.


-----Output-----

Print a single integer — the number of pairs of wires that are intersecting.


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

Output
14

Input
4
0 0
0 2
0 4
2 0

Output
6

Input
3
-1 -1
1 0
3 1

Output
0



-----Note-----

In the first example: [Image] 

In the second example: [Image] 

Note that the three poles $(0, 0)$, $(0, 2)$ and $(0, 4)$ are connected by a single wire.

In the third example: [Image]
user: Today, Yasser and Adel are at the shop buying cupcakes. There are $n$ cupcake types, arranged from $1$ to $n$ on the shelf, and there are infinitely many of each type. The tastiness of a cupcake of type $i$ is an integer $a_i$. There are both tasty and nasty cupcakes, so the tastiness can be positive, zero or negative.

Yasser, of course, wants to try them all, so he will buy exactly one cupcake of each type.

On the other hand, Adel will choose some segment $[l, r]$ $(1 \le l \le r \le n)$ that does not include all of cupcakes (he can't choose $[l, r] = [1, n]$) and buy exactly one cupcake of each of types $l, l + 1, \dots, r$.

After that they will compare the total tastiness of the cupcakes each of them have bought. Yasser will be happy if the total tastiness of cupcakes he buys is strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel's choice.

For example, let the tastinesses of the cupcakes be $[7, 4, -1]$. Yasser will buy all of them, the total tastiness will be $7 + 4 - 1 = 10$. Adel can choose segments $[7], [4], [-1], [7, 4]$ or $[4, -1]$, their total tastinesses are $7, 4, -1, 11$ and $3$, respectively. Adel can choose segment with tastiness $11$, and as $10$ is not strictly greater than $11$, Yasser won't be happy :(

Find out if Yasser will be happy after visiting the shop.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains $n$ ($2 \le n \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$), where $a_i$ represents the tastiness of the $i$-th type of cupcake.

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


-----Output-----

For each test case, print "YES", if the total tastiness of cupcakes Yasser buys will always be strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel's choice. Otherwise, print "NO".


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

Output
YES
NO
NO



-----Note-----

In the first example, the total tastiness of any segment Adel can choose is less than the total tastiness of all cupcakes.

In the second example, Adel will choose the segment $[1, 2]$ with total tastiness $11$, which is not less than the total tastiness of all cupcakes, which is $10$.

In the third example, Adel can choose the segment $[3, 3]$ with total tastiness of $5$. Note that Yasser's cupcakes' total tastiness is also $5$, so in that case, the total tastiness of Yasser's cupcakes isn't strictly greater than the total tastiness of Adel's cupcakes.
user: This problem is same as the previous one, but has larger constraints.

It was a Sunday morning when the three friends Selena, Shiro and Katie decided to have a trip to the nearby power station (do not try this at home). After arriving at the power station, the cats got impressed with a large power transmission system consisting of many chimneys, electric poles, and wires. Since they are cats, they found those things gigantic.

At the entrance of the station, there is a map describing the complicated wiring system. Selena is the best at math among three friends. He decided to draw the map on the Cartesian plane. Each pole is now a point at some coordinates $(x_i, y_i)$. Since every pole is different, all of the points representing these poles are distinct. Also, every two poles are connected with each other by wires. A wire is a straight line on the plane infinite in both directions. If there are more than two poles lying on the same line, they are connected by a single common wire.

Selena thinks, that whenever two different electric wires intersect, they may interfere with each other and cause damage. So he wonders, how many pairs are intersecting? Could you help him with this problem?


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 1000$) — the number of electric poles.

Each of the following $n$ lines contains two integers $x_i$, $y_i$ ($-10^4 \le x_i, y_i \le 10^4$) — the coordinates of the poles.

It is guaranteed that all of these $n$ points are distinct.


-----Output-----

Print a single integer — the number of pairs of wires that are intersecting.


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

Output
14

Input
4
0 0
0 2
0 4
2 0

Output
6

Input
3
-1 -1
1 0
3 1

Output
0



-----Note-----

In the first example:

 [Image] 

In the second example:

 [Image] 

Note that the three poles $(0, 0)$, $(0, 2)$ and $(0, 4)$ are connected by a single wire.

In the third example:

 [Image]
user: A telephone number is a sequence of exactly 11 digits, where the first digit is 8. For example, the sequence 80011223388 is a telephone number, but the sequences 70011223388 and 80000011223388 are not.

You are given a string $s$ of length $n$, consisting of digits.

In one operation you can delete any character from string $s$. For example, it is possible to obtain strings 112, 111 or 121 from string 1121.

You need to determine whether there is such a sequence of operations (possibly empty), after which the string $s$ becomes a telephone number.


-----Input-----

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

The first line of each test case contains one integer $n$ ($1 \le n \le 100$) — the length of string $s$.

The second line of each test case contains the string $s$ ($|s| = n$) consisting of digits.


-----Output-----

For each test print one line.

If there is a sequence of operations, after which $s$ becomes a telephone number, print YES.

Otherwise, print NO.


-----Example-----
Input
2
13
7818005553535
11
31415926535

Output
YES
NO



-----Note-----

In the first test case you need to delete the first and the third digits. Then the string 7818005553535 becomes 88005553535.
user: You are given two integers $a$ and $b$. Print $a+b$.


-----Input-----

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

Each test case is given as a line of two integers $a$ and $b$ ($-1000 \le a, b \le 1000$).


-----Output-----

Print $t$ integers — the required numbers $a+b$.


-----Example-----
Input
4
1 5
314 15
-99 99
123 987

Output
6
329
0
1110
user: -----Input-----

The input consists of a single string of uppercase letters A-Z. The length of the string is between 1 and 10 characters, inclusive.


-----Output-----

Output "YES" or "NO".


-----Examples-----
Input
GENIUS

Output
YES

Input
DOCTOR

Output
NO

Input
IRENE

Output
YES

Input
MARY

Output
NO

Input
SMARTPHONE

Output
NO

Input
REVOLVER

Output
YES

Input
HOLMES

Output
NO

Input
WATSON

Output
YES
user: Ksenia has an array $a$ consisting of $n$ positive integers $a_1, a_2, \ldots, a_n$. 

In one operation she can do the following:   choose three distinct indices $i$, $j$, $k$, and then  change all of $a_i, a_j, a_k$ to $a_i \oplus a_j \oplus a_k$ simultaneously, where $\oplus$ denotes the bitwise XOR operation. 

She wants to make all $a_i$ equal in at most $n$ operations, or to determine that it is impossible to do so. She wouldn't ask for your help, but please, help her!


-----Input-----

The first line contains one integer $n$ ($3 \leq n \leq 10^5$) — the length of $a$.

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


-----Output-----

Print YES or NO in the first line depending on whether it is possible to make all elements equal in at most $n$ operations.

If it is possible, print an integer $m$ ($0 \leq m \leq n$), which denotes the number of operations you do.

In each of the next $m$ lines, print three distinct integers $i, j, k$, representing one operation. 

If there are many such operation sequences possible, print any. Note that you do not have to minimize the number of operations.


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

Output
YES
1
1 3 4
Input
4
10 4 49 22

Output
NO



-----Note-----

In the first example, the array becomes $[4 \oplus 1 \oplus 7, 2, 4 \oplus 1 \oplus 7, 4 \oplus 1 \oplus 7, 2] = [2, 2, 2, 2, 2]$.
user: Consider a tunnel on a one-way road. During a particular day, $n$ cars numbered from $1$ to $n$ entered and exited the tunnel exactly once. All the cars passed through the tunnel at constant speeds.

A traffic enforcement camera is mounted at the tunnel entrance. Another traffic enforcement camera is mounted at the tunnel exit. Perfectly balanced.

Thanks to the cameras, the order in which the cars entered and exited the tunnel is known. No two cars entered or exited at the same time.

Traffic regulations prohibit overtaking inside the tunnel. If car $i$ overtakes any other car $j$ inside the tunnel, car $i$ must be fined. However, each car can be fined at most once.

Formally, let's say that car $i$ definitely overtook car $j$ if car $i$ entered the tunnel later than car $j$ and exited the tunnel earlier than car $j$. Then, car $i$ must be fined if and only if it definitely overtook at least one other car.

Find the number of cars that must be fined. 


-----Input-----

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), denoting the ids of cars in order of entering the tunnel. All $a_i$ are pairwise distinct.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$), denoting the ids of cars in order of exiting the tunnel. All $b_i$ are pairwise distinct.


-----Output-----

Output the number of cars to be fined.


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

Output
2

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

Output
6

Input
2
1 2
1 2

Output
0



-----Note-----

The first example is depicted below:

[Image]

Car $2$ definitely overtook car $5$, while car $4$ definitely overtook cars $1$, $2$, $3$ and $5$. Cars $2$ and $4$ must be fined.

In the second example car $5$ was definitely overtaken by all other cars.

In the third example no car must be fined.
user: You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$.

You have to construct two sequences of integers $b$ and $c$ with length $n$ that satisfy:  for every $i$ ($1\leq i\leq n$) $b_i+c_i=a_i$  $b$ is non-decreasing, which means that for every $1<i\leq n$, $b_i\geq b_{i-1}$ must hold  $c$ is non-increasing, which means that for every $1<i\leq n$, $c_i\leq c_{i-1}$ must hold 

You have to minimize $\max(b_i,c_i)$. In other words, you have to minimize the maximum number in sequences $b$ and $c$.

Also there will be $q$ changes, the $i$-th change is described by three integers $l,r,x$. You should add $x$ to $a_l,a_{l+1}, \ldots, a_r$. 

You have to find the minimum possible value of $\max(b_i,c_i)$ for the initial sequence and for sequence after each change.


-----Input-----

The first line contains an integer $n$ ($1\leq n\leq 10^5$).

The secound line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq i\leq n$, $-10^9\leq a_i\leq 10^9$).

The third line contains an integer $q$ ($1\leq q\leq 10^5$).

Each of the next $q$ lines contains three integers $l,r,x$ ($1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$), desribing the next change. 


-----Output-----

Print $q+1$ lines.

On the $i$-th ($1 \leq i \leq q+1$) line, print the answer to the problem for the sequence after $i-1$ changes.


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

Output
5
5
6

Input
6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3

Output
3
3
3
1

Input
1
0
2
1 1 -1
1 1 -1

Output
0
0
-1



-----Note-----

In the first test:  The initial sequence $a = (2, -1, 7, 3)$. Two sequences $b=(-3,-3,5,5),c=(5,2,2,-2)$ is a possible choice.  After the first change $a = (2, -4, 4, 0)$. Two sequences $b=(-3,-3,5,5),c=(5,-1,-1,-5)$ is a possible choice.  After the second change $a = (2, -4, 6, 2)$. Two sequences $b=(-4,-4,6,6),c=(6,0,0,-4)$ is a possible choice.
user: You are given two integers $a$ and $b$. You can perform a sequence of operations: during the first operation you choose one of these numbers and increase it by $1$; during the second operation you choose one of these numbers and increase it by $2$, and so on. You choose the number of these operations yourself.

For example, if $a = 1$ and $b = 3$, you can perform the following sequence of three operations:   add $1$ to $a$, then $a = 2$ and $b = 3$;  add $2$ to $b$, then $a = 2$ and $b = 5$;  add $3$ to $a$, then $a = 5$ and $b = 5$. 

Calculate the minimum number of operations required to make $a$ and $b$ equal. 


-----Input-----

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

The only line of each test case contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$).


-----Output-----

For each test case print one integer — the minimum numbers of operations required to make $a$ and $b$ equal. 


-----Example-----
Input
3
1 3
11 11
30 20

Output
3
0
4



-----Note-----

First test case considered in the statement.

In the second test case integers $a$ and $b$ are already equal, so you don't need to perform any operations.

In the third test case you have to apply the first, the second, the third and the fourth operation to $b$ ($b$ turns into $20 + 1 + 2 + 3 + 4 = 30$).
user: The Cybermen solved that first test much quicker than the Daleks. Luckily for us, the Daleks were angry (shocking!) and they destroyed some of the Cybermen.

After the fighting stopped, Heidi gave them another task to waste their time on.

There are $n$ points on a plane. Given a radius $r$, find the maximum number of points that can be covered by an $L^1$-ball with radius $r$.

An $L^1$-ball with radius $r$ and center $(x_0, y_0)$ in a 2D-plane is defined as the set of points $(x, y)$ such that the Manhattan distance between $(x_0, y_0)$ and $(x, y)$ is at most $r$.

Manhattan distance between $(x_0, y_0)$ and $(x, y)$ is defined as $|x - x_0| + |y - y_0|$.


-----Input-----

The first line contains two integers $n, r$ ($1 \le n \le 300\,000, 1 \le r \le 10^6$), the number of points and the radius of the ball, respectively. 

Each of the next $n$ lines contains integers $x_i, y_i$ ($-10^6 \leq x_i, y_i \leq 10^6$), describing the coordinates of the $i$-th point.

It is guaranteed, that all points are distinct.


-----Output-----

Print one integer — the maximum number points that an $L^1$-ball with radius $r$ can cover.


-----Examples-----
Input
5 1
1 1
1 -1
-1 1
-1 -1
2 0

Output
3

Input
5 2
1 1
1 -1
-1 1
-1 -1
2 0

Output
5



-----Note-----

In the first example, a ball centered at $(1, 0)$ covers the points $(1, 1)$, $(1, -1)$, $(2, 0)$.

In the second example, a ball centered at $(0, 0)$ covers all the points.

Note that $x_0$ and $y_0$ need not be integer.