作者： chenchen

Bessie knows a number x+0.5 where x is some integer between 0 to N, inclusive (1≤N≤2·10^5).

Elsie is trying to guess this number. She can ask questions of the form "is i high or low?" for some integer i between 1 and N, inclusive. Bessie responds by saying "HI" if i is greater than x+0.5, or "LO" if i is less than x+0.5.

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of N numbers, where every number from 1 to N occurs exactly once (in other words, the list is a permutation of size N). Then she goes through the list, guessing numbers that appear in the list in order.

However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number i and Elsie previously guessed some j<i and Bessie responded with "HI", Elsie will not guess i and will move on to the next number in the list. Similarly, if she is about to guess some number i and she previously guessed some j>i and Bessie responded with "LO", Elsie will not guess i and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines x regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string S, then the number of times Bessie says "HILO" is the number of length 4 substrings of S that are equal to "HILO."

Bessie knows that Elsie will use this strategy; furthermore, she also knows the exact permutation that Elsie will use. However, Bessie has not decided on what value of x to choose.

Help Bessie determine how many times she will say "HILO" for each value of x.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The second line contains Elsie's permutation of size N.

OUTPUT FORMAT (print output to the terminal / stdout):

For each x from 0 to N, inclusive, output the number of times Bessie will say HILO on a new line.

SAMPLE INPUT:

5

5 1 2 4 3

SAMPLE OUTPUT:

0

1

1

2

1

0

For x=0, Bessie will say "HIHI," for a total of zero "HILO"s.

For x=2, Bessie will say "HILOLOHIHI," for a total of one "HILO".

For x=3, Bessie will say "HILOLOHILO", for a total of two "HILO"s.

SCORING:

Tests 1 to 4 satisfy N≤5000.

Tests 5 to 8 have a uniformly random permutation.

Tests 9 to 20 satisfy no further constraints.

There are a total of N (1≤N≤10^5) cows on the number line. The location of the i-th cow is given by xi (0≤xi≤10^9), and the weight of the i-th cow is given by yi (1≤yi≤10^4).

At Farmer John's signal, some of the cows will form pairs such that

Every pair consists of two distinct cows a and b whose locations are within K of each other (1≤K≤10^9); that is, |xa?xb|≤K.

Every cow is either part of a single pair or not part of a pair.

The pairing is maximal; that is, no two unpaired cows can form a pair.

It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,

If T=1, compute the minimum possible sum of weights of the unpaired cows.

If T=2, compute the maximum possible sum of weights of the unpaired cows.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains T, N, and K.

In each of the following N lines, the i-th contains xi and yi. It is guaranteed that 0≤x1<x2<?<xN≤10^9.

OUTPUT FORMAT (print output to the terminal / stdout):

Please print out the minimum or maximum possible sum of weights of the unpaired cows.

SAMPLE INPUT:

2 5 2

1 2

3 2

4 2

5 1

7 2

SAMPLE OUTPUT:

6

In this example, cows 2 and 4 can pair up because they are at distance 2, which is at most K=2. This pairing is maximal, because cows 1 and 3 are at distance 3, cows 3 and 5 are at distance 3, and cows 1 and 5 are at distance 6, all of which are more than K=2. The sum of weights of unpaired cows is 2+2+2=6.

SAMPLE INPUT:

1 5 2

1 2

3 2

4 2

5 1

7 2

SAMPLE OUTPUT:

2

Here, cows 1 and 2 can pair up because they are at distance 2≤K=2, and cows 4 and 5 can pair up because they are at distance 2≤K=2. This pairing is maximal because only cow 3 remains. The weight of the only unpaired cow here is simply 2.

SAMPLE INPUT:

2 15 7

3 693

10 196

12 182

14 22

15 587

31 773

38 458

39 58

40 583

41 992

84 565

86 897

92 197

96 146

99 785

SAMPLE OUTPUT:

2470

The answer for this example is 693+992+785=2470.

SCORING:

Test cases 4-8 satisfy T=1.

Test cases 9-14 satisfy T=2 and N≤5000.

Test cases 15-20 satisfy T=2.

Problem credits: Benjamin Qi

Bessie knows a number x+0.5 where x is some integer between 0 to N, inclusive (1≤N≤5000).

Elsie is trying to guess this number. She can ask questions of the form "is i high or low?" for some integer i between 1 and N, inclusive. Bessie responds by saying "HI!" if i is greater than x+0.5, or "LO!" if i is less than x+0.5.

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of N numbers, where every number from 1 to N occurs exactly once (in other words, the list is a permutation of size N.) Then, she goes through the list, guessing numbers that appear in the list in order. However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number i and Elsie previously guessed some j<i such that Bessie responded with "HI!," Elsie will not guess i and will move on to the next number in the list. Similarly, if she is about to guess some number i and she previously guessed some j>i such that Bessie responded with "LO!," Elsie will not guess i and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines x regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string S, the number of times Bessie says "HILO" is the number of length 4 substrings of S that are equal to "HILO."

Bessie knows that Elsie will use this strategy and has already chosen the value of x, but she does not know what permutation Elsie will use. Your goal is to compute the sum of the number of times Bessie says "HILO" over all permutations that Elsie could possibly choose, modulo 10^9+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The only line of input contains N and x.

OUTPUT FORMAT (print output to the terminal / stdout):

The total number of HILOs modulo 10^9+7.

SAMPLE INPUT:

4 2

SAMPLE OUTPUT:

17

In this test case, Bessie's number is 2.5.

For example, if Elsie's permutation is (4,1,3,2), then Bessie will say "HILOHILO," for a total of two "HILO"s. As another example, if Elsie's permutation is (3,1,2,4), then Bessie will say "HILOLO," for a total of one "HILO."

SAMPLE INPUT:

60 10

SAMPLE OUTPUT:

508859913

Make sure to output the sum modulo 10^9+7.

SCORING:

Test cases 3-10 satisfy N≤50.

Test cases 11-18 satisfy N≤500.

Test cases 19-26 satisfy no additional constraints.

There are a total of N (1≤N≤5000) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the i-th cow is given by bi∈{H,G}, the location of the i-th cow is given by xi (0≤xi≤10^9), and the weight of the i-th cow is given by yi (1≤yi≤10^5).
At Farmer John's signal, some of the cows will form pairs such that
Every pair consists of a Holstein h and a Guernsey g whose locations are within K of each other (1≤K≤10^9); that is, |xh?xg|≤K.
Every cow is either part of a single pair or not part of a pair.
The pairing is maximal; that is, no two unpaired cows can form a pair.
It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,
If T=1, compute the minimum possible sum of weights of the unpaired cows.
If T=2, compute the maximum possible sum of weights of the unpaired cows.
INPUT FORMAT (input arrives from the terminal / stdin):
The first input line contains T, N, and K.
Following this are N lines, the i-th of which contains bi,xi,yi. It is guaranteed that 0≤x1<x2<?<xN≤10^9.
OUTPUT FORMAT (print output to the terminal / stdout):
The minimum or maximum possible sum of weights of the unpaired cows.
SAMPLE INPUT:
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
SAMPLE OUTPUT:
16
Cows 2 and 3 can pair up because they are at distance 1, which is at most K=4. This pairing is maximal, because cow 1, the only remaining Guernsey, is at distance 5 from cow 4 and distance 7 from cow 5, which are more than K=4. The sum of weights of unpaired cows is 1+6+9=16.
SAMPLE INPUT:
1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
SAMPLE OUTPUT:
6
Cows 1 and 2 can pair up because they are at distance 2≤K=4, and cows 3 and 5 can pair up because they are at distance 4≤K=4. This pairing is maximal because only cow 4 remains. The sum of weights of unpaired cows is the weight of the only unpaired cow, which is simply 6.
SAMPLE INPUT:
2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 540
SAMPLE OUTPUT:
1893
The answer to this example is 18+465+870+540=1893.
SCORING:
Test cases 4-7 satisfy T=1.
Test cases 8-14 satisfy T=2 and N≤300.
Test cases 15-22 satisfy T=2.
**Note: the memory limit for this problem is 512MB, twice the default.**

Bessie is going on a hiking excursion! The trail that she is currently traversing consists of N checkpoints labeled 1…N (1≤N≤10^5).
There are K (1≤K≤10^5) tickets available for purchase. The i-th ticket can be purchased at checkpoint ci (1≤ci≤N) for price pi (1≤pi≤10^9) and provides access to all of checkpoints [ai,bi] (1≤ai≤bi≤N). Before entering any checkpoint, Bessie must have purchased a ticket that allows access to that checkpoint. Once Bessie has access to a checkpoint, she may return to it at any point in the future. She may travel between two checkpoints to which she has access, regardless of whether their labels differ by 1 or not.
For each of i∈[1,N], output the minimum total price required to purchase access to both checkpoints 1 and N if Bessie initially has access to only checkpoint i. If it is impossible to do so, print ?1 instead.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and K.
Each of the next K lines contains four integers ci, pi, ai, and bi for each 1≤i≤K.
OUTPUT FORMAT (print output to the terminal / stdout):
N lines, one for each checkpoint.
SAMPLE INPUT:
7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6
SAMPLE OUTPUT:
-1
-1
-1
1111
10100
110100
-1
If Bessie starts at checkpoint i=4, then one way for Bessie to purchase access to checkpoints 1 and N is as follows:
Purchase the first ticket at checkpoint 4, giving Bessie access to checkpoints 2 and 3.
Purchase the third ticket at checkpoint 2, giving Bessie access to checkpoint 7.
Return to checkpoint 4 and purchase the second ticket, giving Bessie access to checkpoints 5 and 6.
Purchase the fourth ticket at checkpoint 6, giving Bessie access to checkpoint 1.
SCORING:
Test cases 1-7 satisfy N,K≤10^00.
Test cases 8-19 satisfy no additional constraints.

The grass has dried up in Farmer John's pasture due to a drought. After hours of despair and contemplation, Farmer John comes up with the brilliant idea of purchasing corn to feed his precious cows.
FJ’s N cows (1≤N≤10^5) are arranged in a line such that the ith cow in line has a hunger level of hi (0≤hi≤10^9). As cows are social animals and insist on eating together, the only way FJ can decrease the hunger levels of his cows is to select two adjacent cows i and i+1 and feed each of them a bag of corn, causing each of their hunger levels to decrease by one.
FJ wants to feed his cows until all of them have the same non-negative hunger level. Please help FJ determine the minimum number of bags of corn he needs to feed his cows to make this the case, or print ?1 if it is impossible.
INPUT FORMAT (input arrives from the terminal / stdin):
Each input consists of several independent test cases, all of which need to be solved correctly to solve the entire input case. The first line contains T (1≤T≤10^0), giving the number of test cases to be solved. The T test cases follow, each described by a pair of lines. The first line of each pair contains N, and the second contains h1,h2,…,hN. It is guaranteed that the sum of N over all test cases is at most 105. Values of N might differ in each test case.
OUTPUT FORMAT (print output to the terminal / stdout):
Please write T lines of output, one for each test case.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
SAMPLE INPUT:
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9
SAMPLE OUTPUT:
14
16
-1
-1
-1
For the first test case, give two bags of corn to both cows 2 and 3, then give five bags of corn to both cows 1 and 2, resulting in each cow having a hunger level of 3.
For the second test case, give two bags to both cows 1 and 2, two bags to both cows 2 and 3, two bags to both cows 4 and 5, and two bags to both cows 5 and 6, resulting in each cow having a hunger level of 2.
For the remaining test cases, it is impossible to make the hunger levels of the cows equal.
SCORING:
All test cases in input 2 satisfy N≤3 and hi≤10^0.
All test cases in inputs 3-8 satisfy N≤10^0 and hi≤10^0.
All test cases in inputs 9-14 satisfy N≤10^0.
Input 15 satisfies no additional constraints.
Additionally, N is always even in inputs 3-5 and 9-11, and N is always odd in inputs 6-8 and 12-14.
Problem credits: Arpan Banerjee

To pass the time in the barn, the cows enjoy playing simple dice games. One of these games is played with two dice X and Y. Both are rolled, and the winner is the die with the higher number showing. If both land on the same number, they are re-rolled (they may be re-rolled several times, as long as there continues to be a tie). We say die X beats die Y if it is more likely that X will win this game than Y.
Consider the following 4-sided dice:
Die A has the numbers 4, 5, 6, and 7 on its sides.
Die B has the numbers 2, 4, 5, and 10 on its sides.
Die C has the numbers 1, 4, 8, and 9 on its sides.
These dice satisfy a rather intriguing property: A beats B, B beats C, and C also beats A. In particular, none of the three dice is the "best", beating the other two. In this case, where no two dice tie and no single die is the best, we call the set of three dice "non-transitive". In a non-transitive set of three dice, each die beats one other die, and loses to another die.
Given the numbers on the faces of two 4-sided dice A and B, please help the cows determine whether there is a way to assign numbers to the faces of a third die C so the set of dice is non-transitive. The numbers on the faces of all dices must be integers in the range from 1 through 10 inclusive.
INPUT FORMAT (input arrives from the terminal / stdin):
Each input consists of several independent test cases, all of which need to be solved correctly to solve the entire input case. The first line of input contains T (1≤T≤10^), the number of test cases you need to solve.
The following T lines each describe one test case in terms of 8 numbers: the numbers on the four sides of die A, and the numbers on the four sides of die B. All numbers are in the range 1 through 10, not necessarily in sorted order. The same number might appear multiple times, even on the same die.
OUTPUT FORMAT (print output to the terminal / stdout):
Please write T lines of output. The kth line should be 'yes' if it is possible to design a die C to make the kth test case into a set of non-transitive dice, and 'no' otherwise.
SAMPLE INPUT:
3
4 5 6 7 2 4 5 10
2 2 2 2 1 1 1 1
1 1 1 1 2 2 2 2
SAMPLE OUTPUT:
yes
no
no
The first test case corresponds to the example given above. In the second test case, there is no die C that can make the set of dice non-transitive. The answer is no for the same reason for the third test case.
Problem credits: Brian Dean

The cows have created a new type of puzzle called Herdle that has become a viral sensation in the bovine world.
Each day, a new puzzle is released for the cows to solve. The puzzle takes the form of a 3 by 3 grid representing a field on the farm, with each square of the field occupied by a cow of a certain breed. There are only 26 possible breeds, each identified by a different capital letter in the range A through Z. One is not told the pattern of breeds in the field --- the goal is to figure them out through a series of guesses.
In each guess, the cows enter a 3 by 3 grid of uppercase letters indicating a possible way the field could be filled with cows. Some of the squares in the guess might be correct. These are highlighted in green to let the cows know that they are correct. Other squares in the guess might be filled with a cow of the right breed but in the wrong place. These are highlighted in yellow.
The number of yellow-highlighted squares can help provide an indication of the number of cows of a certain breed. For example, suppose the guess grid contains 4 cows of breed A, and the answer grid contains 2 cows of breed A, where none of the A's line up (i.e., none of them should be colored green). In this case, only two of the A's in the guess grid should be highlighted yellow. More precisely, if there are x cows of a certain breed in the guess grid and y<x cows of this breed in the answer grid (not counting cows in the right place that lead to green highlights), then only y of the x cows in the guess grid should be highlighted yellow.
Given the correct answer grid and a grid representing a guess at this answer, please calculate the number of green and yellow highlighted squares.
INPUT FORMAT (input arrives from the terminal / stdin):
The first 3 lines of input gives the grid representing the correct answer. The next 3 lines of input represent a guess of this answer.
OUTPUT FORMAT (print output to the terminal / stdout):
Print two lines of output. On the first line of output, print the number of squares that should be highlighted in green. On the second line, print the number of squares that should be highlighted in yellow.
SAMPLE INPUT:
COW
SAY
MOO
WIN
THE
IOI
SAMPLE OUTPUT:
1
1
In this example, the O in the middle of the last row is correct, so it is highlighted in green. The letter W is in the wrong place, so it is highlighted in yellow.
SAMPLE INPUT:
AAA
BBB
CCC
AYY
AAA
ZZZ
SAMPLE OUTPUT:
1
2
Here, one of the As is in the correct place, so it is highlighted green. Of the remaining As, none are in the right place, and since there are two of these remaining in the answer grid, two should be highlighted yellow.
Problem credits: Brian Dean, inspired by the 'Wordle' app

Farmer John's cows like nothing more than cereal for breakfast! In fact, the cows have such large appetites that they will each eat an entire box of cereal for a single meal.
The farm has recently received a shipment with M different types of cereal (2≤M≤10^5). Unfortunately, there is only one box of each cereal! Each of the N cows (1≤N≤10^5) has a favorite cereal and a second favorite cereal. When given a selection of cereals to choose from, a cow performs the following process:
If the box of her favorite cereal is still available, take it and leave.
Otherwise, if the box of her second-favorite cereal is still available, take it and leave.
Otherwise, she will moo with disappointment and leave without taking any cereal.
Find the minimum number of cows that go hungry if you permute them optimally. Also, find any permutation of the N cows that achieves this minimum.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains two space-separated integers N and M.
For each 1≤i≤N, the i-th line contains two space-separated integers fi and si (1≤fi,si≤M and fi≠si) denoting the favorite and second-favorite cereals of the i-th cow.
OUTPUT FORMAT (print output to the terminal / stdout):
Print the minimum number of cows that go hungry, followed by any permutation of 1…N that achieves this minimum. If there are multiple permutations, any one will be accepted.
SAMPLE INPUT:
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
SAMPLE OUTPUT:
1
1
3
2
8
4
6
5
7
In this example, there are 8 cows and 10 types of cereal.
Note that we can effectively solve for the first three cows independently of the last five, since they share no favorite cereals in common.
If the first three cows choose in the order [1,2,3], then cow 1 will choose cereal 2, cow 2 will choose cereal 3, and cow 3 will go hungry.
If the first three cows choose in the order [1,3,2], then cow 1 will choose cereal 2, cow 3 will choose cereal 3, and cow 2 will choose cereal 4; none of these cows will go hungry.
Of course, there are other permutations that result in none of the first three cows going hungry. For example, if the first three cows choose in the order [3,1,2] then cow 3 will choose cereal 2, cow 1 will choose cereal 1, and cow 2 will choose cereal 3; again, none of cows [1,2,3] will go hungry.
It can be shown that out of the last five cows, at least one must go hungry.
SCORING:
In 4 out of 14 test cases, N,M≤10^0.
In 10 out of 14 test cases, no additional constraints.

Farmer John's N cows (N≤3×10^5) have heights 1,2,…,N. One day, the cows are standing in a line in some order playing frisbee; let h1…hN denote the heights of the cows in this order (so the h's are a permutation of 1…N).
Two cows at positions i and j in the line can successfully throw the frisbee back and forth if and only if every cow between them has height lower than min(hi,hj).
Please compute the sum of distances between all pairs of locations i<j at which there resides a pair of cows that can successfully throw the frisbee back and forth. The distance between locations i and j is j?i+1.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains a single integer N. The next line of input contains h1…hN, separated by spaces.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the sum of distances of all pairs of locations at which there are cows that can throw the frisbee back and forth. Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
SAMPLE INPUT:
7
4 3 1 2 5 6 7
SAMPLE OUTPUT:
24
The pairs of successful locations in this example are as follows:
(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)
SCORING
Test cases 1-3 satisfy N≤5000.
Test cases 4-11 satisfy no additional constraints.