作者： chenchen

Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.
Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are N class periods (1≤N≤10^5), and Elsie logs that Bessie fell asleep ai times (0≤ai≤10^6) in the i-th class period. The total number of times Bessie fell asleep across all class periods is at most 106.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures. The only way Elsie may modify the log is by combining two adjacent class periods. For example, if a=[1,2,3,4,5], then if Elsie combines the second and third class periods the log will become [1,5,4,5].

Help Elsie compute the minimum number of modifications to the log that she needs to make so that she can make all the numbers in the log equal.

INPUT FORMAT (input arrives from the terminal / stdin):
Each input will contain T (1≤T≤10) test cases that should be solved independently.
The first line contains T, 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 a1,a2,…,aN.

It is guaranteed that within each test case, the sum of all values in a is at most 106. It is also guaranteed that the sum of N over all test cases is at most 105.

OUTPUT FORMAT (print output to the terminal / stdout):
Please write T lines of output, giving the minimum number of modifications Elsie could perform to make all the log entries equal for each case.

SAMPLE INPUT:
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
SAMPLE OUTPUT:
3
2
0
For the first test case in this example, Elsie can change her log to consist solely of 3s with 3 modifications.

1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
For the second test case, Elsie can change her log to 7 with 2 modifications.

2 2 3
-> 2 5
-> 7
For the last test case, Elsie doesn’t need to perform any operations; the log already consists of equal entries.

Problem credits: Jesse Choe

Farmer John has fallen behind on organizing his inbox. The way his screen is organized, there is a vertical list of folders on the left side of the screen and a vertical list of emails on the right side of the screen. There are M total folders, numbered 1…M (1≤M≤104). His inbox currently contains N emails numbered 1…N (1≤N≤105); the ith email needs to be filed into folder fi (1≤fi≤M).
FJ's screen is rather small, so he can only view K (1≤K≤min(N,M)) folders and K emails at once. Initially, his screen starts out displaying folders 1…K on the left and emails 1…K on the right. To access other folders and emails, he needs to scroll through these respective lists. For example, if he scrolls down one position in the list of folders, his screen will display folders 2…K+1, and then scrolling down one position further it will display folders 3…K+2. When FJ drags an email into a folder, the email disappears from the email list, and the emails after the one that disappeared shift up by one position. For example, if emails 1,2,3,4,5 are currently displayed and FJ drags email 3 into its appropriate folder, the email list will now show emails 1,2,4,5,6. FJ can only drag an email into the folder to which it needs to be filed.

Unfortunately, the scroll wheel on FJ's mouse is broken, and he can only scroll downwards, not upwards. The only way he can achieve some semblance of upward scrolling is if he is viewing the last set of K emails in his email list, and he files one of these. In this case, the email list will again show the last K emails that haven't yet been filed, effectively scrolling the top email up by one. If there are fewer than K emails remaining, then all of them will be displayed.

Please help FJ determine if it is possible to file all of his emails.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains T (1≤T≤10), the number of subcases in this input, all of which must be solved correctly to solve the input case. The T subcases then follow. For each subcase, the first line of input contains M, N, and K. The next line contains f1…fN.
It is guaranteed that the sum of M over all subcases does not exceed 104, and that the sum of N over all subcases does not exceed 10^5.

OUTPUT FORMAT (print output to the terminal / stdout):
Output T lines, each one either containing either YES or NO, specifying whether FJ can successfully file all his emails in each of the T subcases.
SAMPLE INPUT:
6
5 5 1
1 2 3 4 5
5 5 1
1 2 3 5 4
5 5 1
1 2 4 5 3
5 5 2
1 2 4 5 3
3 10 2
1 3 2 1 3 2 1 3 2 1
3 10 1
1 3 2 1 3 2 1 3 2 1
SAMPLE OUTPUT:
YES
YES
NO
YES
YES
NO
SCORING:
In inputs 2-10, the sum of M over all subcases does not exceed 10^3.
In inputs 11-12, no additional constraints.
Problem credits: Brian Dean

Bessie is learning how to control a robot she has recently received as a gift.
The robot begins at point (0,0) on the coordinate plane and Bessie wants the robot to end at point (xg,yg). Bessie initially has a list of N (1≤N≤40) instructions to give to the robot, the i-th of which will move the robot xi units right and yi units up (or left or down when xi and yi are negative, respectively).

For each K from 1 to N, help Bessie count the number of ways she can select K instructions from the original N such that after the K instructions are executed, the robot will end at point (xg,yg).

**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N. The next line contains xg and yg, each in the range −10^9…10^9. The final N lines describe the instructions. Each line has two integers xi and yi, also in the range −10^9…10^9.
It is guaranteed that (xg,yg)≠(0,0) and (xi,yi)≠(0,0) for all i.

OUTPUT FORMAT (print output to the terminal / stdout):
Print N lines, the number of ways Bessie can select K instructions from the original N for each K from 1 to N.
SAMPLE INPUT:
7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10
SAMPLE OUTPUT:
0
2
0
3
0
1
0
In this example, there are six ways Bessie can select the instructions:

(-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 5)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 7)
(5,0) (0,10) (0,-10) (0,10) (4 5 6 7)
(5,0) (0,10) (4 5)
(5,0) (0,10) (4 7)
For the first way, the robot's path looks as follows:

(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)
SCORING:
Test cases 2-4 satisfy N≤20.
Test cases 5-16 satisfy no additional constraints.
Problem credits: Alex Liang

Farmer John has N gifts labeled 1…N for his N cows, also labeled 1…N (1≤N≤500). Each cow has a wishlist, which is a permutation of all N gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.
FJ was lazy and just assigned gift i to cow i for all i. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

For each i from 1 to N, compute the most preferred gift cow i could hope to receive after reassignment.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N. The next N lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1…N.
OUTPUT FORMAT (print output to the terminal / stdout):
Please output N lines, the i-th of which contains the most preferred gift cow i could hope to receive after reassignment.
SAMPLE INPUT:
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
SAMPLE OUTPUT:
1
3
2
4
In this example, there are two possible reassignments:

The original assignment: cow 1 receives gift 1, cow 2 receives gift 2, cow 3 receives gift 3, and cow 4 receives gift 4.
Cow 1 receives gift 1, cow 2 receives gift 3, cow 3 receives gift 2, and cow 4 receives gift 4.
Observe that both cows 1 and 4 cannot hope to receive better gifts than they were originally assigned. However, both cows 2 and 3 can.

SCORING:
Test cases 2-3 satisfy N≤8.
Test cases 4-11 satisfy no additional constraints.

Farmer John's N cows (1≤N≤10^5) are spread far apart on his farm and would like to build a communication network so they can more easily exchange electronic text messages (all of which of course contain variations of "moo").
The ith cow is located at a distinct location (xi,yi) where 0≤xi≤10^6 and 0≤yi≤10. The cost of building a communication link between cows i and j is the squared distance between them: (xi?xj)2+(yi?yj)2.

Please calculate the minimum cost required to build a communication network across which all the cows can communicate. Two cows can communicate if they are directly connected by a link, or if there is a sequence of links along which their message can travel.

**Note: the time limit for this problem is 4s, twice the default.**

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N, and the next N lines each describe the x and y coordinates of a cow, all integers.
OUTPUT FORMAT (print output to the terminal / stdout):
Please output the minimum cost of a network that will allow all cows to communicate. Note that this cost might be too large to fit into a 32-bit integer and may require use of 64-bit integers (e.g., "long long" integers in C++).
SAMPLE INPUT:
10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0
SAMPLE OUTPUT:
660
SCORING:
Test cases 2-3 satisfy N≤1000.
Test cases 4-15 satisfy no additional constraints.
Problem credits: Brian Dean

To qualify for cow camp, Bessie needs to earn a good score on the last problem of the USACOW Open contest. This problem has T distinct test cases (2≤T≤10^3) weighted equally, with the first test case being the sample case. Her final score will equal the number of test cases that her last submission passes.
Unfortunately, Bessie is way too tired to think about the problem, but since the answer to each test case is either "yes" or "no," she has a plan! Precisely, she decides to repeatedly submit the following nondeterministic solution:

if input == sample_input:
print sample_output
else:
print "yes" or "no" each with probability 1/2, independently for each test case
Note that for all test cases besides the sample, this program may produce a different output when resubmitted, so the number of test cases that it passes will vary.

Bessie knows that she cannot submit more than K (1≤K≤10^9) times in total because then she will certainly be disqualified. What is the maximum possible expected value of Bessie's final score, assuming that she follows the optimal strategy?

INPUT FORMAT (input arrives from the terminal / stdin):
The only line of input contains two space-separated integers T and K.
OUTPUT FORMAT (print output to the terminal / stdout):
The answer as a decimal that differs by at most 10?6 absolute or relative error from the actual answer.
SAMPLE INPUT:
2 3
SAMPLE OUTPUT:
1.875
In this example, Bessie should keep resubmitting until she has reached 3 submissions or she receives full credit. Bessie will receive full credit with probability 78 and half credit with probability 18, so the expected value of Bessie's final score under this strategy is 78?2+18?1=158=1.875. As we see from this formula, the expected value of Bessie's score can be calculated by taking the sum over x of p(x)?x, where p(x) is the probability of receiving a score of x.

SAMPLE INPUT:
4 2
SAMPLE OUTPUT:
2.8750000000000000000
Here, Bessie should only submit twice if she passes fewer than 3 test cases on her first try.

SCORING
Test cases 3-6 satisfy T≤25 and K≤10^0.
Test cases 7-9 satisfy K≤10^6.
Test cases 10-17 satisfy no additional constraints.
Problem credits: Benjamin Qi

Farmer John has N gifts labeled 1…N for his N cows, also labeled 1…N (1≤N≤18). Each cow has a wishlist, which is a permutation of all N gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.
FJ was lazy and just assigned gift i to cow i for all i. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.
There is also an additional constraint: a gift may only be reassigned to a cow if it was originally assigned to a cow of the same type (each cow is either a Holstein or a Guernsey). Given Q (1≤Q≤min(105,2N)) length-N breed strings, for each one count the number of reassignments that are consistent with it.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The next N lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1…N.
The next line contains Q.
The final Q lines each contain a breed string, each N characters long and consisting only of the characters G and H. No breed string occurs more than once.
OUTPUT FORMAT (print output to the terminal / stdout):
For each breed string, print the number of reassignments that are consistent with it on a new line.
SAMPLE INPUT:
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG
SAMPLE OUTPUT:
2
1
1
2
2
In this example, for the first breed string, there are two possible reassignments:
The original assignment: cow 1 receives gift 1, cow 2 receives gift 2, cow 3 receives gift 3, and cow 4 receives gift 4.
Cow 1 receives gift 1, cow 2 receives gift 3, cow 3 receives gift 2, and cow 4 receives gift 4.
For the second breed string, the only reassignment consistent with it is the original assignment.
SCORING:
For T=2,…,13, test case T satisfies N=T+4.
Test cases 14-18 satisfy N=18.
Problem credits: Benjamin Qi

Bessie has a new cell phone with nine buttons, laid out as follows:
123
456
789
Bessie is trying to type out a given phone number in a hurry, so she decides to save time by pressing multiple buttons at the same time with one of her hooves. Specifically, Bessie's hoof might press a single digit, two digits that share a side (for twelve possible pairs in total), or four digits that form a square (1245, 2356, 4578, or 5689).
For example, if the phone number Bessie is trying to type is 123659874, she might attempt to save time by
Pressing 1 and 2 at the same time.
Pressing 3.
Pressing 6, 5, 9, and 8 at the same time.
Pressing 7 and 4 at the same time.
Unfortunately, Bessie drastically overestimated her skill at performing this task - if Bessie's hoof pressess multiple buttons at the same time, then all of the digits will be typed in arbitrary order. So if Bessie attempts the above sequence of presses, she may end up typing 123596847 or 213659874 instead (or one of many other possibilities).
Given a sequence of digits that Bessie has typed, count the number of phone numbers that she could have been trying to type modulo 109+7.
**Note: the time limit for this problem is 4s, twice the default.**
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases to solve.
The next T lines each contain a nonempty string of the digits 1 through 9. It is guaranteed that the total length of these strings does not exceed 105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, the number of phone numbers Bessie might have been trying to type modulo 109+7.
SAMPLE INPUT:
5
1478
4455
5968
31313211
123659874
SAMPLE OUTPUT:
5
2
24
3
255
For the first case, Bessie might be trying to type any of the following five phone numbers:
1478
1487
4178
4187
1748
For example, if Bessie was trying to type 4187, she might have tried pressing 1 and 4 at the same time and then tried pressing 7 and 8 at the same time.
For the third case, as the numbers form a square, Bessie might have been trying to type any permutation of the input sequence.
SCORING:
In inputs 2-3, all phone numbers have length at most 8.
In inputs 4-5, the phone number only contains 1, 2, and 3.
In inputs 6-7, the phone number doesn't contain the digit 5.
In inputs 8-9, the phone number only contains 5, 6, 8, and 9.
In inputs 10-12, the sum of the string lengths does not exceed 102.
In inputs 13-15, the sum of the string lengths does not exceed 103.
In inputs 16-18, the sum of the string lengths does not exceed 104.
In inputs 19-21, no additional constraints.
Problem credits: Nick Wu

Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.
Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are N class periods (2≤N≤10^5), and Elsie logs that Bessie fell asleep ai times (1≤ai≤10^18) in the i-th class period. The total number of times Bessie fell asleep across all class periods is at most 1018.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures.

The only ways Elsie may modify the log are by combining two adjacent class periods or splitting a class period into two. For example, if a=[1,2,3,4,5], then if Elsie combines the second and third class periods the log will become [1,5,4,5]. If Elsie then chooses to split the third class period into two, the log can become any of [1,5,0,4,5], [1,5,1,3,5], [1,5,2,2,5], [1,5,3,1,5], or [1,5,4,0,5].

Given Q (1≤Q≤10^5) candidates q1,…,qQ for Bessie's least favorite number (1≤qi≤1018), for each of them help Elsie compute the minimum number of modifications to the log that she needs to perform so that all the numbers in the log become the same.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of each test case contains N, and the second contains a1,a2,…,aN. The third contains Q, followed by Q lines each containing an integer qi, a candidate for Bessie's least favorite number.
OUTPUT FORMAT (print output to the terminal / stdout):
For each qi, compute the minimum number of modifications required for Elsie to convert every entry of the log into qi, or −1 if it is impossible.
SAMPLE INPUT:
6
1 2 3 1 1 4
7
1
2
3
4
5
6
12
SAMPLE OUTPUT:
6
6
4
5
-1
4
5
Elsie needs at least four modifications to convert the log into all 3s.

1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3
It is impossible for Elsie to convert the log into all 5s, which is why the correct output for that candidate is −1.

SCORING:
In test cases 2-4, N,Q≤5000
In test cases 5-7, all ai are at most 109.
Test cases 8-26 satisfy no additional constraints.
Problem credits: Jesse Choe and Benjamin Qi

After her previous artwork was met with critical acclaim, Bessie was offered a job designing painting sets. She designs these paintings by choosing 1≤N≤105 axis-aligned rectangles in the plane such that no two edges are collinear. The boundaries of these rectangles define the boundaries of the painting's colored regions.
Still being an avant-garde artist, Bessie decides that the painting should resemble a Holstein cow. More specifically, each region formed by the rectangles is colored either black or white, no two adjacent regions have the same color, and the region outside of all the rectangles is colored white.

After choosing the rectangles, Bessie would like you to output one of two things based on a parameter T:

If T=1, output the total number of regions.
If T=2, output the number of white regions followed by the number of black regions.
**Note: the time limit for this problem is 4s, twice the default.**

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and T.
The next N lines each contain the description of a rectangle in the form (x1,y1),(x2,y2) where 1≤x1<x2≤2N and 1≤y1<y2≤2N. (x1,y1) and (x2,y2) are the bottom left and top right corners of the rectangle respectively.

It is guaranteed that all the xi form a permutation of 1…2N, and the same holds for all the yi.

OUTPUT FORMAT (print output to the terminal / stdout):
A single integer if T=1, otherwise two separated by spaces.
SAMPLE INPUT:
2 1
1 1 3 3
2 2 4 4
SAMPLE OUTPUT:
4
There are two white regions and two black regions, for a total of four regions. The boundaries of all rectangles are connected, so this input would satisfy the conditions of subtask 3.

SAMPLE INPUT:
5 2
1 5 3 6
5 4 7 9
4 1 8 3
9 8 10 10
2 2 6 7
SAMPLE OUTPUT:
4 5
The boundary of the rectangle in the upper-right is not connected to the rest of the boundaries, so this input would not satisfy the conditions of subtask 4.

SCORING:
Test cases 3-4 satisfy N≤103.
In test cases 5-7, no two rectangle boundaries intersect.
In test cases 8-10, T=1 and the boundaries of all rectangles are connected.
In test cases 11-13, T=2 and the boundaries of all rectangles are connected.
In test cases 14-18, T=1.
In test cases 19-23, T=2.
Problem credits: Andi Qu