The country of Fairland has very strict laws governing how companies organize and pay their employees:
1. Each company must have exactly one CEO, who has no manager.
2. Every employee except for the CEO must have exactly one manager. (This means that the org chart showing all of the employees in a company is a tree, without cycles.)
3. As long as an employee is working for the company, their manager must never change. This means that if a manager leaves, then all of the employees reporting to that manager must also leave.
4. The CEO must never leave the company.
5. Every employee receives a salary - some amount of Fairland dollars per year. An employee's salary must never change.
6. Different employees may have different salaries, and an employee's salary is not necessarily correlated with where in the org chart that employee is.
The government of Fairland has just passed one additional law:
7. The difference between the largest salary and the smallest salary in the whole company must be at most D Fairland dollars.
Marie is the CEO of the Fairland General Stuff Corporation, and she has to ensure that her company complies with the new law. This may require laying off some employees. She has the list of the company's employees, their managers, and their salaries. What is the largest number of employees she can keep, including herself?
The first line of the input gives the number of test cases, T (1 ≤ T ≤ 100). T test cases follow. Each case begins with one line containing two space-separated integers N (1 ≤ N ≤ 106, the number of employees) and D (1 ≤ D ≤ 106, the maximum allowed salary difference). This is followed by one line with four space-separated integers - S0, As, Cs, Rs (0 ≤ S0 < Rs ≤ 106, 0 ≤ As ≤ 1000, 0 ≤ Cs ≤ 109) and then another line with four more space-separated integers - M0, Am, Cm and Rm (0 ≤ M0 < Rm ≤ 106, 0 ≤ Am ≤ 1000, 0 ≤ Cm ≤ 109). These last eight integers define the following sequences:
Marie's employee ID is 0, and all other employees have IDs from 1 to N - 1, inclusive. The salary of employee i is Si. For every employee i other than Marie, the manager is 
. (Note that this means that M0 does not affect Marie's manager - she has none!).
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the largest number of employees Marie can keep at the company, including herself, such that all of laws 1-7 are obeyed.
3
1 395
18 246 615815 60
73 228 14618 195
6 5
10 1 3 17
5 2 7 19
10 13
28 931 601463 36
231 539 556432 258
Case #1: 1
Case #2: 3
Case #3: 5
In Case #1, the company has only a CEO and no other employees, but it does not violate any of the laws, so no changes need to be made.
Here is the org chart for Case #2:
The optimal strategy is to save employees 0, 1, and 5 (who have salaries of 10, 13, and 8, respectively). It is not possible to save employee 2, for example, because her salary is more than 5 away from employee 0's salary of 10; since employee 0 cannot be laid off, employee 2 must be laid off (along with all employees who report to her).
If you want to check your sequences for employees 1 through 5, they are:
S: 13, 16, 2, 5, 8
M: 17, 3, 13, 14, 16
Manager numbers: 17%1 = 0, 3%2 = 1, 13%3 = 1, 14%4 = 2, 16%5 = 1
Adamma is a climate scientist interested in temperature. Every minute, she records the current temperature as an integer, creating a long list of integers: x1, x2, ..., xN. (Adamma uses her own special temperature scale rather than a familiar one like Celsius or Kelvin, so it's possible for the values to be large and negative!) She often plots these temperatures on her computer screen.
This morning, she decided to compute a sliding average of this list in order to get a smoother plot. She used a smoothing window of size K, which means that she converted the sequence of N temperatures into a sequence of (N - K + 1) average temperatures: s1, s2, ..., sN - K + 1. Each si is the average of the values xi, xi + 1, ..., xi + K - 1. The original xi values were all integers, but some of the si may be fractional.
Unfortunately, Adamma forgot to save the original sequence of temperatures! And now she wants to answer a different question - what was the difference between the largest temperature and the smallest temperature? In other words, she needs to compute max{x1, ..., xN} - min{x1, ..., xN}. But she only has N, K, and the smoothed sequence.
After some thinking, Adamma has realized that this might be impossible because there may be several valid answers. In that case, she wants to know the smallest possible answer among all of the possible original sequences that could have produced her smoothed sequence with the given values of N and K.
The first line of the input gives the number of test cases, T (1 ≤ T ≤ 100). T test cases follow; each test case consists of two lines. The first line contains integers N and K (2 ≤ K ≤ N ≤ 1000, K ≤ 100) separated by a space character. The second line contains integer values sum1, sum2, ..., sumN - K + 1 ( - 10000 ≤ sumi ≤ 10000), separated by space characters. si is given by sumi / K.
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the smallest possible difference between the largest and smallest temperature.
3
10 2
1 2 3 4 5 6 7 8 9
100 100
-100
7 3
0 12 0 12 0
Case #1: 5
Case #2: 0
Case #3: 12
In Case #1, the smoothed sequence is:
0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5
The integer sequence that gives the smallest difference is:
0, 1, 1, 2, 2, 3, 3, 4, 4, 5
Note that the sequence:
0.5, 0.5, 1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 4.5, 4.5
Would give the same smoothed sequence with a maximum difference of 4, but this is not a valid answer because the original temperatures are known to have been integers.
In Case #2, all we know is that the sum of the 100 original values was -100. It's possible that all of the original values were exactly -1, in which case the difference between the largest and smallest temperatures would be 0, which is as small as differences get!
In Case #3, the original sequence could have been:
-4, 8, -4, 8, -4, 8, -4
Oh no - your N pet quail have all gotten loose! You are currently at position 0 on a line; the i-th quail starts off at some nonzero integer (positive or negative) position Pi on that line, in meters, and will continuously run away from you at a constant integer speed of Si meters per second. You can run at a constant integer speed of Y meters per second, and can change direction instantaneously whenever you want. Note that quail constantly run away from you even if you are not running toward them at the time. Whenever you occupy the same point as a quail, that quail is caught (this takes no additional time).
What is the minimum number of seconds it will take you to catch all of the quail?
The first line of the input gives the number of test cases, T (1 ≤ T ≤ 100). T test cases follow. Each begins with one line with two space-separated integers Y (2 ≤ Y ≤ 1000), your speed, and N (1 ≤ N ≤ 500), the number of quail, and is followed by two more lines with N space-separated integers each. The first of these gives the positions Pi (1 ≤ |Pi| ≤ 107) of the quail, and the second gives the speeds Si (1 ≤ Si < Y).
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of seconds needed to catch all the quail.
y will be considered correct if it is within an absolute or relative error of 10 - 6 of the correct answer.
2
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1
Case #1: 3.00000000000000000
Case #2: 5.00000000000000000
In Case #1, you can run to the left and catch all three quail at the same time, 12 meters to the left of the starting position, which takes 3 seconds.
In Case #2, one optimal strategy is to run to the left until the second quail is caught at -2 m, which takes one second, and then run to the right in pursuit of the first quail, which you will catch at 6 m, taking four more seconds.
The power set of a set S is the set of all subsets of S (including the empty set and S itself). It's easy to go from a set to a power set, but in this problem, we'll go in the other direction!
We've started with a set of (not necessarily unique) integers S, found its power set, and then replaced every element in the power set with the sum of elements of that element, forming a new set S". For example, if S = { - 1, 1}, then the power set of S is {{}, { - 1}, {1}, { - 1, 1}}, and so S" = {0, - 1, 1, 0}. S" is allowed to contain duplicates, so if S has N elements, then S" always has exactly 2N elements.
Given a description of the elements in S" and their frequencies, can you determine our original S? It is guaranteed that S exists. If there are multiple possible sets S that could have produced S", we guarantee that our original set S was the earliest one of those possibilities. To determine whether a set S1 is earlier than a different set S2 of the same length, sort each set into nondecreasing order and then examine the leftmost position at which the sets differ. S1 is earlier iff the element at that position in S1 is smaller than the element at that position in S2.
The first line of the input gives the number of test cases, T (1 ≤ T ≤ 100). T test cases follow. Each consists of one line with an integer P (1 ≤ P ≤ 10000), followed by two more lines, each of which has P space-separated integers. The first of those lines will have all of the different elements E1, E2, ..., EP ( - 1010 ≤ Ei ≤ 1010) that appear in S", sorted in ascending order. The second of those lines will have the number of times F1, F2, ..., FP (Fi ≥ 1) that each of those values appears in S". That is, for any i, the element Ei appears Fi times in S". S will contain between 1 and 60 elements.
For each test case, output one line containing "Case #x: ", where x is the test case number (starting from 1), followed by the elements of our original set S, separated by spaces, in nondecreasing order. (You will be listing the elements of S directly, and not providing two lists of elements and frequencies as we do for S".)
5
8
0 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
4
0 1 2 3
1 3 3 1
4
0 1 3 4
4 4 4 4
3
-1 0 1
1 2 1
5
-2 -1 0 1 2
1 2 2 2 1
Case #1: 1 2 4
Case #2: 1 1 1
Case #3: 0 0 1 3
Case #4: -1 1
Case #5: -2 1 1
In Case #4, S = { - 1, 1} is the only possible set that satisfies the conditions. (Its subsets are {}, {-1}, {1}, and {-1, 1}. Those have sums 0, -1, 1, and 0, respectively, so S" has one copy of -1, two copies of 0, and one copy of 1, which matches the specifications in the input.)
For Case #5, note that S = { - 1, - 1, 2} also produces the same S" = { - 2, - 1, - 1, 0, 0, 1, 1, 2}, but S = { - 2, 1, 1} is earlier than { - 1, - 1, 2}, since at the first point of difference, - 2 < - 1. So -1 -1 2 would not be an acceptable answer. 1 -2 1 would also be unacceptable, even though it is the correct set, because the elements are not listed in nondecreasing order.
The city you live in lies on the banks of the spectacular Binary river. The water in the river comes from some tributary streams that start way up in the mountains. Unfortunately for your city, there are farmers who live in the mountains who need to use up some of the water in the tributary streams for their crops.
Long ago, the city struck a deal with the farmers to allow them to farm while keeping the river flowing: each farmer was allowed to use the water for her crops exactly half the time. The farmers would alternately divert water for their crops for a day and leave the water to run down the river for a day. The result was a disaster! Because the farmers' water usage was synchronized, with everyone either diverting or not diverting water at the same time, the river would run dry every other day and then flood the city the next.
To solve this problem, the city went back to the farmers and asked each one to choose some integer power of 2 (this is the Binary River after all) between 1 and D, inclusive, and toggle her water usage (either start or stop collecting water) every time that number of days has elapsed. (Not every power of 2 between 1 and D was necessarily represented, and multiple farmers may have selected the same integer. 1 counts as a power of 2.) The idea was that this would make the water usage more even overall, and so the droughts and flooding would become less frequent.
This all happened a long time ago, and you and the other citizens have recently become suspicious that the farmers aren't sticking to the agreement. (You're not even sure how many farmers there are right now!) However, the only data you have is N days' history of the amount of water flowing through the city. Can you tell if the farmers are being honest?
Each tributary stream has flow 1 and the flow through the main river is the sum of all the tributary streams that are not being diverted for farming. (Before looking at the records, you don't know how many tributary streams there are.) At most 1 farmer will divert the water from each tributary stream, but there may be some tributary streams from which no farmers ever divert water. Note that the farmers started their water diversion cycles long before the city started recording the water flow, but there is no guarantee that they all started on the same day.
The first line of the input gives the number of test cases, T (1 ≤ T ≤ 50). T test cases follow. Each test case starts with a line containing two space-separated integers N and D (1 ≤ N ≤ 5000, 1 ≤ D ≤ floor(N / 2), D will be a power of 2). The next line contains N space-separated integers, with the i-th integer di (0 ≤ di ≤ 1000) giving the river flow on the i-th day.
For each case, output one line containing "Case #x: M", where x is the test case number (starting from 1) and M is the smallest number of farmers who could be diverting water from the streams according to the described model, consistent with the observed flow through the river.
If you are sure that at least one farmer is active, but there is no way that the supplied input could be explained by farmers obeying the rules, then output "CHEATERS!" instead of a number.
4
5 2
2 2 2 2 2
6 2
1 1 1 0 0 0
8 4
2 1 1 0 0 1 1 2
8 4
0 1 1 3 1 2 2 2
Case #1: 0
Case #2: CHEATERS!
Case #3: 2
Case #4: 3
Case #1 is consistent with two tributary streams with no farmers drawing from them.
Case #2 could a single tributary stream being diverted every 4 days. However, D is 2 in this case, so this farmer is breaking the agreement.
Case #3 could be two farmers each with a diversion cycle of 4 days.
Case #4 could be three farmers with diversion cycles of 1, 2 and 4 days.