作者： chenchen

The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of N intervals (1≤N≤2·10^5), where the ith interval starts at position ai on the number line and ends at position bi≥ai. Both ai and bi are integers in the range 0…M, where 1≤M≤5000.

To play the game, Bessie chooses some interval (say, the ith interval) and her cousin Elsie chooses some interval (say, the jth interval, possibly the same as Bessie's interval). Given some value k, they win if ai+aj≤k≤bi+bj.

For every value of k in the range 0…2M, please count the number of ordered pairs (i,j) for which Bessie and Elsie can win the game.

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

The first line of input contains N and M. Each of the next N lines describes an interval in terms of integers ai and bi.

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

Please print 2M+1 lines as output, one for each value of k in the range 0…2M.

SAMPLE INPUT:

2 5

1 3

2 5

SAMPLE OUTPUT:

0

0

1

3

4

4

4

3

3

1

1

In this example, for just k=3, there are three ordered pairs that will allow Bessie and Elie to win: (1,1), (1,2), and (2,1).

SCORING:

Test cases 1-2 satisfy N≤100,M≤100.

Test cases 3-5 satisfy N≤5000.

Test cases 6-20 satisfy no additional constraints.

Note that output values might be too large to fit into a 32-bit integer, so you may want to use 64-bit integers (e.g., "long long" ints in C or C++).

Farmer John's farm consists of a set of N fields (1≤N≤10^5), conveniently numbered 1…N. Between these fields are M bi-directed paths (0≤M≤10^5), each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field N. Farmer John would like to ensure that there is a way to walk between the two barns along some series of paths. He is willing to build up to two new paths to accomplish this goal. Due to the way the fields are situated, the cost of building a new path between fields i and j is (i−j)2.

Please help Farmer John determine the minimum cost needed such that barns 1 and N become reachable from each-other.

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

Each input test case contains T sub-cases (1≤T≤20), all of which must be solved correctly to solve the input case.

The first line of input contains T, after which T sub-test cases follow.

Each sub-test case starts with two integers, N and M. Next, M lines follow, each one containing two integers i and j, indicating a path between two different fields i and j. It is guaranteed that there is at most one path between any two fields, and that the sum of N+M over all sub-test cases is at most 5·10^5.

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

Output T lines. The ith line should contain a single integer giving the minimum cost for the ith sub-test case.

SAMPLE INPUT:

2

5 2

1 2

4 5

5 3

1 2

2 3

4 5

SAMPLE OUTPUT:

2

1

In the first sub-test case, it is optimal to connect fields 2 and 3 with a path, and fields 3 and 4 with a path.

In the second sub-test case, it is optimal to connect fields 3 and 4 with a path. No second path is needed.

SCORING:

Test case 2 satisfies N≤20.

Test cases 3-5 satisfy N≤10^3.

Test cases 6-10 satisfy no additional constraints.

Farmer John owns a long farm along the highway that can be considered somewhat like a one-dimensional number line. Along the farm, there are K grassy patches (1≤K≤2·10^5); the i-th patch is located at position pi and has an associated tastiness value ti (0≤ti≤109). Farmer John's nemesis, Farmer Nhoj, has already situated his M cows (1≤M≤2·10^5) at locations f1…fM. All K+M of these locations are distinct integers in the range [0,10^9].
Farmer John needs to pick N (1≤N≤2·10^5) locations (not necessarily integers) for his cows to be located. These must be distinct from those already occupied by the cows of Farmer Nhoj, but it is possible for Farmer John to place his cows at the same locations as grassy patches.

Whichever farmer owns a cow closest to a grassy patch can claim ownership of that patch. If there are two cows from rival farmers equally close to the patch, then Farmer Nhoj claims the patch.

Given the locations of Farmer Nhoj's cows and the locations and tastiness values of the grassy patches, determine the maximum total tastiness Farmer John's cows can claim if optimally positioned.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains K, M, and N.
The next K lines each contain two space-separated integers pi and ti.

The next M lines each contain a single integer fi.

OUTPUT FORMAT (print output to the terminal / stdout):
An integer denoting the maximum total tastiness. Note that the answer to this problem can be too large to fit into a 32-bit integer, so you probably want to use 64-bit integers (e.g., "long long"s in C or C++).
SAMPLE INPUT:
6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11
SAMPLE OUTPUT:
36
If Farmer John places cows at positions 11.5 and 8 then he can claim a total tastiness of 10+12+14=36.

Problem credits: Brian Dean

Bessie the cow enjoys arts and crafts. In her free time, she has made N (1≤N≤50) bracelets, conveniently numbered 1…N. The ith bracelet is painted color i out of a set of N different colors. After constructing the bracelets, Bessie placed them on a table for display (which we can think of as the 2D plane). She was careful to arrange the bracelets to satisfy the following three conditions:

Every bracelet was a single closed polygonal chain -- a series of vertices (points) connected sequentially by line segments, where the first and last points are the same (Feel welcome to consult the wikipedia page for more detail: polygonal chain),

No bracelet intersected itself (this corresponds to a "simple" polygonal chain); and

No two bracelets intersected.

Unfortunately, right after Bessie arranged the bracelets in such a careful manner, Farmer John drove by in his tractor, shaking the table and causing the bracelets to shift around and possibly break into multiple (not necessarily closed or simple) polygonal chains! Afterward, Bessie wanted to check whether the three conditions above still held. However, it was dark, so she couldn't see the bracelets anymore.

Fortunately, Bessie had a flashlight. She chose M (1≤M≤50) vertical lines x=1,x=2,…,x=M and for each line, she swept the beam of the flashlight along that line from y=?∞ to y=∞, recording the colors of all bracelets she saw in the order they appeared. Luckily, no beam crossed over any vertex of any polygonal chain or two line segments at the same time. Furthermore, for each beam, every color that appeared appeared exactly twice.

Can you help Bessie use this information to determine whether it is possible that the bracelets still satisfy all three of the conditions above?

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

Each input case contains T sub-cases (1≤T≤50) that must all solved independently to solve the full input case. Consecutive test cases are separated by newlines.

The first line of the input contains T. Each of the T sub-test cases then follow.

The first line of each sub-test case contains two integers N and M. Each sub-test case then contains M additional lines. For each i from 1 to M, the i-th additional line contains an integer ki (0≤ki≤2N, ki even), followed by ki integers ci1,ci2,…,ciki (cij∈[1,N], every cij appears zero or two times). This means that when Bessie swept her flashlight from (i,?∞) to (i,∞), she encountered the colors ci1,ci2,…,ciki in that order.

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

For each sub-test case, print YES if it is possible for the three conditions above to be satisfied. Otherwise, print NO.

SAMPLE INPUT:

5

1 2

2 1 1

2 1 1

1 3

2 1 1

0

2 1 1

2 1

4 1 2 1 2

4 2

6 1 2 2 3 3 1

6 1 2 4 4 2 1

2 2

4 1 1 2 2

4 2 2 1 1

SAMPLE OUTPUT:

YES

NO

NO

YES

NO

An example of a feasible bracelet configuration for the first sub-case is:

For the fourth sub-case, a feasible arrangement is the following:

SCORING:

Test case 2 satisfies N=1.

Test cases 3-5 satisfy N=2.

Test cases 6-8 satisfy M=1.

Test cases 9-14 satisfy M=2.

Test cases 15-20 satisfy no additional constraints.

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