Round 1B opened with *Manhattan Crepe Cart*, which became a lot easier
if you realized that the multiple dimensions in the problem could be handled
independently. In *Draupnir*, just as in this year's other interactive
problems so far, you were able to ask for only a very small amount of data,
from which you had to extract a lot of information. (Code Jam authors don't
always attend the opera, but when they do, they end up writing contest
problems in their heads instead of paying attention!) Finally,
*Fair Fight* presented a dueling challenge that was tough even for a
third Round 1 problem.

**Benq** earned our first perfect score, only 29 minutes and 41 seconds
into the contest (plus 4 minutes for one penalty attempt). Just as in 1A, our
second perfect score came from a previous Distributed Code Jam champion, and
in this case a two-time one: **bmerry**. That was at 42:35, and the third
perfect score was from **alex20030190** at 52:17. By the end of the
contest, there were almost 200 perfect scores — our contestants never
cease to impress us!

This time, the (tentative) cutoff for advancement is 51 points plus a small enough penalty time. That corresponds to solving all of the first problem and the Visible test sets of the other two. Once again, our interactive problem turned out to be a bit tougher than anticipated!

As usual, we will need some time to review the submissions before finalizing the results, but if you make the cut, you can expect confirmation within the next few days. Otherwise, next weekend's Round 1C will be the last chance to advance to Round 2. Good luck!

**Cast**

Manhattan Crepe Cart: Written by Shane Carr. Prepared by Anubhav Srivastava.

Draupnir: Written by Ian Tullis. Prepared by Pablo Heiber.

Fair Fight: Written by Kevin Tran. Prepared by Darcy Best and Kevin Tran.

Solutions and other problem preparation and review by Patrick Au, Liang Bai, Darcy Best, Shane Carr, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Andy Huang, Ray Robinson, and Kevin Tran.

Analysis authors:

- Manhattan Crepe Cart: Ian Tullis
- Draupnir: Darcy Best
- Fair Fight: Darcy Best and Pablo Heiber

There are a lot of great streetside food vendors in Manhattan, but without a doubt, the one with the tastiest food is the Code Jam Crepe Cart!

You want to find the cart, but you do not know where it is, except that it is at some street intersection. You believe that people from across Manhattan are currently walking toward that intersection, so you will try to identify the intersection toward which the most people are traveling.

For the purposes of this problem, Manhattan is a regular grid with its axes
aligned to compass lines and bounded between 0 and **Q**, inclusive, on
each axis. There are west-east streets corresponding to gridlines
y = 0, y = 1, y = 2, …,
y = **Q** and south-north streets corresponding to gridlines
x = 0, x = 1, x = 2, …,
x = **Q**, and people move only along these streets.
The points where the lines meet — e.g., (0, 0) and (1, 2) — are
intersections. The shortest distance between two intersections is measured via the
Manhattan distance
— that is, by the sum of the absolute horizontal difference and the
absolute vertical difference between the two sets of coordinates.

You know the locations of **P** people, all of whom are standing at
intersections, and the compass direction each person is headed: north
(increasing y direction), south (decreasing y direction), east (increasing x
direction), or west (decreasing x direction). A person is moving toward a
street intersection if their current movement is on a shortest path to that
street intersection within the Manhattan grid. For
example, if a person located at (x_{0}, y_{0}) is moving
north, then they are moving toward all street intersections that have
coordinates (x, y) with y > y_{0}.

You think the crepe cart is at the intersection toward which the most people
are traveling. Moreover, you believe that more southern and western parts of
the island are most likely to have a crepe cart, so if there are multiple
such intersections, you will choose the one with the smallest non-negative
`x`

coordinate, and if there are multiple such intersections with
that same `x`

coordinate, the one among those with the smallest
non-negative `y`

coordinate. Which intersection will you choose?

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each test case starts with one line containing
two integers **P** and **Q**: the number of people, and the maximum
possible value of an x or y coordinate in Manhattan, as described above.
Then, there are **P** more lines. The i-th of those lines contains two
integers **X _{i}** and

`N`

, `S`

, `E`

, or `W`

,
which stand for north, south, east, and west, respectively.
For each test case, output one line containing `Case #t: x y`

,
where `t`

is the test case number (starting from 1) and
`x`

and `y`

are the horizontal and vertical coordinates
of the intersection where you believe the crepe cart is located.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **P** ≤ 500.

0 ≤ **X _{i}** ≤

0 ≤

For all i, if

`W`

.For all i, if

`S`

.For all i, if

`E`

.For all i, if

`N`

.
**Q** = 10.

**Q** = 10^{5}.

Sample Input

3 1 10 5 5 N 4 10 2 4 N 2 6 S 1 5 E 3 5 W 8 10 0 2 S 0 3 N 0 3 N 0 4 N 0 5 S 0 5 S 0 8 S 1 5 W

Sample Output

Case #1: 0 6 Case #2: 2 5 Case #3: 0 4

In Sample Case #1, there is only one person, and they are moving north from (5, 5). This means that all street corners with y ≥ 6 are possible locations for the crepe cart. Of those possibilities, we choose the one with lowest x ≥ 0 and then lowest y ≥ 6.

In Sample Case #2, there are four people, all moving toward location (2, 5). There is no other location that has as many people moving toward it.

In Sample Case #3, six of the eight people are moving toward location (0, 4). There is no other location that has as many people moving toward it.

Odin has some magical rings which produce copies of themselves. Each "X-day ring" produces one more X-day ring every X days after the day it came into existence. These rings come in six possible varieties: 1-day, 2-day, ..., all the way up to 6-day.

For example, a 3-day ring that came into existence on day 0 would do nothing until day 3, when it would produce another 3-day ring. Then, on day 6, each of those two rings would produce another 3-day ring, and so on.

You know that Odin had no rings before day 0. On day 0, some rings came into
existence. At the end of day 0, Odin had R_{i} i-day rings, for each
1 ≤ i ≤ 6. You know that 0 ≤ R_{i} ≤ 100, for all i,
and at least one of the R_{i} values is positive.

Fortunately, you also have access to the secret well of knowledge. Each time
you use it, you can find out the *total* number of rings that Odin had
at the end of a particular day between day 1 and day 500, inclusive. The well
will give you the answer modulo 2^{63}, because even it can only hold
so much information! Moreover, you can only use the well up to **W**
times.

Your goal is to determine how many rings of each type Odin had at the end of
day 0 — that is, you must find each of the R_{i} values.

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.

Initially, your program should read a single line containing two integers
**T**, the number of test cases, and **W**, the number of times you are
allowed to use the well of knowledge per test case. Then, you need to
process **T** test cases.

In each test case, your program processes up to **W** + 1 exchanges
with our judge. You may make up to **W** exchanges of the following form:

- Your program outputs one line with a single integer D between 1 and 500, inclusive.
- The judge responds with one line with a single integer: the total number
of rings that Odin had at the end of day D, modulo 2
^{63}. If you send invalid data (e.g., a number out of range, or a malformed line), the judge instead responds with`-1`

.

After between 0 and **W** exchanges as explained above, you must perform
one more exchange of the following form:

- Your program outputs one line with six integers R
_{1}, R_{2}, R_{3}, R_{4}, R_{5}, R_{6}, where R_{i}represents the number of i-day rings that Odin had at the end of day 0. -
The judge responds with one line with a single integer:
`1`

if your answer is correct, and`-1`

if it is not (or you have provided a malformed line).

After the judge sends `-1`

to your input stream (because of either
invalid data or an incorrect answer), it will not send any other output.
If your program continues to wait for the judge after receiving
`-1`

, your program will time out, resulting in a Time Limit
Exceeded error. Notice that it is your responsibility to have your program
exit in time to receive a Wrong Answer judgment instead of a Time Limit
Exceeded error. As usual, if the memory limit is exceeded, or your program
gets a runtime error, you will receive the appropriate judgment.

1 ≤ **T** ≤ 50.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

**W** = 6.

**W** = 2.

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.

Instructions for the testing tool are included in comments within the tool.
We encourage you to add your own test cases. Please be advised that although
the testing tool is intended to simulate the judging system, it is **NOT**
the real judging system and might behave differently. If your code passes the
testing tool but fails the real judge, please check the
Coding section
of the FAQ to make sure that you are using the same compiler as us.

This interaction corresponds to Test set 1. Suppose that, unbeknownst to us, the judge has decided that Odin had one ring of each of the six types at the end of day 0.

t, w = readline_int_list() // Reads 50 into t and 6 into w printline 3 to stdout // Asks about day 3. flush stdout n = readline_int() // Reads 15 into n. printline 1 to stdout // Asks about day 1. flush stdout n = readline_int() // Reads 7 into n. printline 1 1 1 3 0 0 to stdout flush stdout // We make a guess even though we could have // queried the well up to four more times. verdict = readline_int() // Reads -1 into verdict (judge has decided our // solution is incorrect) exit // Exits to avoid an ambiguous TLE error

Notice that even though the guess was consistent with the information we received from the judge, we were still wrong because we did not find the correct values.

En garde! Charles and Delila are about to face off against each other in the final fight of the Swordmaster fencing tournament.

Along one wall of the fencing arena, there is a rack with **N** different
types of swords; the swords are numbered by type, from 1 to **N**. As the
head judge, you will pick a pair of integers (L, R) (with 1 ≤ L ≤ R
≤ **N**), and only the L-th through R-th types of swords (inclusive)
will be available for the fight.

Different types of sword are used in different ways, and being good with one
type of sword does not necessarily mean you are good with another! Charles
and Delila have skill levels of **C _{i}** and

The fight is *fair* if the absolute difference between Charles's skill
level with his chosen sword type and Delila's skill level with her chosen
sword type is at most **K**. To keep the fight exciting, you'd like to
know how many different pairs (L, R) you can choose that will result in a
fair fight.

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each case begins with a line containing the two
integers **N** and **K**, as described above. Then, two more lines
follow. The first of these lines contains **N** integers
**C _{i}**, giving Charles' skill levels for each type of sword, as
described above. Similarly, the second line contains

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 number of choices you can make that result in a fair fight, as
described above.

1 ≤ **T** ≤ 100.

0 ≤ **K** ≤ 10^{5}.

0 ≤ **C _{i}** ≤ 10

0 ≤

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 100.

**N** = 10^{5}, for exactly 8 test cases.

1 ≤ **N** ≤ 1000, for all but 8 test cases.

Sample Input

6 4 0 1 1 1 8 8 8 8 8 3 0 0 1 1 1 1 0 1 0 3 3 5 0 0 8 0 8 0 4 0 4 0 4 3 0 1 0 0 0 1 2 5 2 1 2 3 4 5 5 5 5 5 10

Sample Output

Case #1: 4 Case #2: 4 Case #3: 1 Case #4: 0 Case #5: 1 Case #6: 7

In Sample Case #1, the fight is fair if and only if Charles can use the last type of sword, so the answer is 4.

In Sample Case #2, there are 4 fair fights: (1, 2), (1, 3), (2, 2), and (2, 3). Notice that for pairs like (1, 3), Charles and Delila both have multiple swords they could choose that they are most skilled with; however, each pair only counts as one fair fight.

In Sample Case #3, there is 1 fair fight: (1, 1).

In Sample Case #4, there are no fair fights, so the answer is 0.

In Sample Case #5, remember that the *duelists* are not trying to make
the fights fair; they choose the type of sword that they are most skilled
with. For example, (1, 3) is not a fair fight, because Charles will choose
the first type of sword, and Delila will choose the third type of sword.
Delila will not go easy on Charles by choosing a weaker sword!

In Sample Case #6, there are 7 fair fights: (1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4), and (4, 4).

Test sets 1 and 2 differ only in how large the available grid area is. In the first test set, people can only be standing in cells with coordinates between 0 and 10, inclusive, in either dimension. Moreover, we can notice that the cart can only be in a cell within this area. The cart's horizontal and vertical coordinates must both be nonnegative per the rules of a problem. Moreover, it cannot have a coordinate larger than 10 (in either dimension). Suppose, for example, that the cart had a horizontal coordinate greater than 10; then that would imply that there must be at least one person standing at horizontal coordinate 10 and facing east. Otherwise, placing the cart at horizontal coordinate 10 would be even better, per the tiebreaker rules. But the rules of the problem do not allow people at (horizontal/vertical) coordinate 10 to face (east/north).

Therefore, to solve test set 1, we can create an array to represent all of
the blocks in the allowed area, and initialize each cell's value to 0. Then,
for each person, we increment all of the cells of the array that they are
walking toward. Finally, we find the cell of the array with the maximum
value, using the tiebreaker rules as needed. This solution takes
O(**P** × **Q**^{2}) time.

In problems that involve multiple dimensions, it is often worth checking whether those dimensions are independent. In this case, they are! A person heading west, for example, gives us a "vote" for the crepe cart being to the west of them, but tells us nothing at all about the north-south location of the cart. So we can solve the two dimensions as separate one-dimensional problems; the horizontal problem includes only the people heading west or east (and their horizontal positions), and the vertical problem includes only the people heading south or north (and their vertical positions). Let us consider the horizontal dimension for now; our arguments also apply to the vertical dimension.

Even if our people are widely spread out along the horizontal axis, the crepe
cart can only possibly be in a limited number of horizontal positions. In
fact, it must be either at position 0, or at a cell that is one cell to the
east of some person. To see why, suppose that the cart is in some other cell
1 ≤ C ≤ **Q**. Let W denote the cell one unit to the west of C. We
know by assumption that W does not contain a person. But then if we move the
cart from C to W, we will not be losing any votes (i.e. any person voting for
C is also voting for W), and we many even gain votes (if there were people in
C who were heading west). (Notice that a person does not vote for the cell
they are in.) Even if we do not gain votes, our tiebreaker gets better. So we
should always make this move, and, therefore, we should always move the cart
west until it is at 0 or immediately to the east of someone. Observe that
this might find only a locally optimal solution, but if we check all such
cells, we will surely find the globally optimal solution.

These observations reduce the number of cells we need to check to
O(**P**) rather than O(**Q**). To check a cell, we can make a linear
pass over all of the people, and count whether each one is voting for that
cell. One such check takes O(**P**) time. Then we choose the cell that
got the most votes, breaking a tie if needed by choosing the westernmost of
the tied cells. The overall time complexity is O(**P**^{2}) for
the one-dimensional problem, and solving it twice (for two dimensions) is
still O(**P**^{2}).

Although the above solution is fast enough to solve test set 2, we can do even better by avoiding making a linear pass over the data for each person.

We can first process our data into a set of tuples like the following:
(coordinate, number of people at that coordinate facing west, number of
people at that coordinate facing east). Let us denote these as
(C_{i}, W_{i}, E_{i}). (Remember that for the
purposes of the horizontal subproblem, we are ignoring people facing north or
south.) Using a hash-based dictionary, this processing takes time linear in
**P**. As we do this, we should also determine the total numbers W and E
of people facing west and east.

Then, we sort these tuples in ascending order of their first values. It is probably most convenient to use a common sorting algorithm (or one built into your language), making this step nonlinear. (We will leave a spirited discussion of which sorting algorithms are truly linear for another day.)

Once we have sorted the tuples, we start by considering cell 0 as a candidate location, and we determine the votes for that cell. We know that quantity is equal to W minus the number of people in cell 0, if any. We make a note of this number of votes and set 0 as our best candidate so far. Then, we look at the first tuple in our sorted list, which represents the people at some cell C (which might be cell 0). The number of votes for cell C + 1 (the cell one unit to the east of C) should be the same as the number of votes we found for cell 0, plus the number of people in cell C facing east (which is all of them in this case), minus the number of people in cell C facing west. If cell C is a better candidate, we store it and its number of votes.

We can do this for every tuple in our list to get our final answer. If we
have one or more people on the eastern border, we do not need to check the
cell one unit to the east of them, since (as explained at the start of the
analysis) the cart can never have a coordinate larger than **Q**. Since
the check for each entry of the tuple takes constant time, the full pass
takes O(**P**) time.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

In this problem, we need to determine the number of each type of X-day ring by querying the total number of rings in existence at the end of a certain day.

Let R_{1} be the number of 1-day rings, R_{2} be the number
of 2-day rings, ... etc. at the end of day 0. The
number of X-day rings doubles at the end of every day that is a
multiple of X. Thus, the total number of rings on day i is

R_{1}*2^{i}+ R_{2}*2^{floor(i/2)}+ R_{3}*2^{floor(i/3)}+ R_{4}*2^{floor(i/4)}+ R_{5}*2^{floor(i/5)}+ R_{6}*2^{floor(i/6)}.

In the first test set, we are allowed six queries to determine the
six unknown variables. Note that if we query any day number larger
than 63, then the number of 1-day rings on that day will be a
multiple of 2^{63} (equivalently, it is 0 modulo
2^{63}). Similarly, if we query any day number larger than
X*63, then the number of X-day rings will be 0 modulo 2^{63}
on that day.

Thus, on day 315 (=5*63), the total number of rings, modulo
2^{63}, is R_{6}*2^{52} (since the number
of 1-day, 2-day, ..., 5-day rings are all 0 modulo
2^{63}). Since R_{6} ≤ 100, we know that
R_{6}*2^{52} does not exceed 2^{63}, so we
can directly determine R_{6}. Then, on day 252 (=4*63), the
total number of rings, modulo 2^{63}, is
R_{6}*2^{42} + R_{5}*2^{50}. Since
we already know R_{6} and we know this sum cannot be more
than 2^{63}, we can solve for R_{5}. We may continue
this process by querying days 189 (=3*63), 126 (=2*63), 63 (=1*63)
and 1 to determine R_{4}, R_{3}, R_{2} and
R_{1}, respectively.

Note that since we are querying six days and attempting to solve for six variables, we may choose to query (for example) days 1,2, ... , 6. This gives us a system of equations with six equations and six variables. Since these equations are linearly independent, we can solve this system, via Gaussian elimination for example, to get the solution.

The second test set requires another insight. We are only given two
queries, so we must be able to solve for multiple R_{i} at
once.

Let's think about what information we get by querying day 189
(=3*63). This gives R_{6}*2^{31} +
R_{5}*2^{37} + R_{4}*2^{47}, modulo
2^{63}. However, it is possible that there is some
overlap between R_{6}*2^{31} and
R_{5}*2^{37}. For example, all other things being equal, we
would not be able to differentiate between the case where R_{6}=64 and
R_{5}=0 and the case where R_{6}=0 and
R_{5}=1. Both of these would have 2^{37} total rings.

We must use the fact that R_{i} ≤ 100. In order for the
number of i-day rings to not interfere with the number of (i-1)-day
rings on day d, we need 2^{floor(d/(i-1))} > 100 *
2^{floor(d/i)} (note that this is equivalent to
floor(d/(i-1)) ≥ floor(d/i)+7 since 2^{7} > 100). If we
ignore the modulo 2^{63} restriction, then we could solve
the question in a single query of (for example) 1000. This would
give us

RSince R_{1}*2^{1000}+ R_{2}*2^{500}+ R_{3}*2^{333}+ R_{4}*2^{250}+ R_{5}*2^{200}+ R_{6}*2^{166}.

We will use one query to determine the values of
R_{4}, R_{5}, and R_{6}, followed by a
second query to determine the values of R_{1},
R_{2}, and R_{3}. We saw above that a query of 189
(=3*63) will not work. However, a query of (for example) 200 will
work:

Rand then solve for each in the same way as for the 1000 case. We can then make a second query of (for example) 56:_{4}*2^{50}+ R_{5}*2^{40}+ R_{6}*2^{33},

RWe know the value of R_{1}*2^{56}+ R_{2}*2^{28}+ R_{3}*2^{18}+ R_{4}*2^{14}+ R_{5}*2^{11}+ R_{6}*2^{9}.

Note that the choice of 200 and 56 above were not the only possible
options. In this problem, we could either guess-and-check for these
values offline or (preferably) write a loop in the program to find
two values that satisfy the criteria. We also need to ensure that
the term with the largest exponent is not too large. For example,
we cannot use a query of 250 in the first step since this gives
R_{4}*2^{62} + R_{5}*2^{50} +
R_{6}*2^{41}, because the first term
(R_{4}*2^{62}) may be at least 2^{63}.

Let us call a pair (L, R) *fair* if choosing it produces a fair fight. Notice that
since there are only 100 entries, there are at most 100*101/2 = 5050 possible intervals.
For each interval, we may simply search for the maximum value is in each array via a
linear search and check if those maximum values are close enough.

Notice the random choice of sword in case of ties does not change whether (L, R)
is fair or not, so we can further assume that, if there are ties, they are broken by choosing
the sword with smallest index. To simplify the write-up below, we assume that each
**C**_{i} is distinct.

Let us consider a sub-problem: for each sword i that Charles can choose, how many fair
intervals (L,R) are there which Charles chooses sword i? Let us call this value F_{i}.
The answer to the original problem is simply the sum of the F_{i}s. For each interval
(L,R), there are three properties we are concerned with:

- (P1) Charles chooses sword i. That is, L ≤ i ≤ R and
max(
**C**_{L},**C**_{L+1},...,**C**_{R}) =**C**_{i}. - (P2) Charles' sword is
*good enough*. That is, max(**D**_{L},**D**_{L+1},...,**D**_{R}) ≤**C**_{i}+**K**. - (P3) Charles' sword is
*too good*. That is, max(**D**_{L},**D**_{L+1},...,**D**_{R}) <**C**_{i}-**K**.

So we have F_{i} = (# of intervals that satisfy P1 and P2) - (# of intervals that satisfy
P1 and P3). These two quantities are computed very similarly since they just have a different
bound on the right-hand side of the inequality in P2 and P3. We explain below just how to compute
(# of intervals that satisfy P1 and P2) and leave computing (# of intervals that satisfy P1 and P3)
to the reader.

Note that if an interval (L,R) satisfies P2, then any subinterval of (L,R) also satisfies P2.
Similarly, if (L,R) satisfies P1, then any subinterval of (L,R) that still contains i
also satisfies P1. Thus, we are really only interested in how far left L can go with R=i (and
how far right R can go with L=i). One option is to do a linear search for how far left L can go,
but this is too slow. Instead, we
binary search
for how far away the left-endpoint is. A
left-endpoint is too far left if P1 or P2 are no longer true. Otherwise, the left endpoint
can be pushed further left. Once we know the furthest left L can go (let this index be L_{i})
and the furthest right R can go (let this index be R_{i}), then
(# of intervals that satisfy P1 and P2) = (i - L_{i} + 1) × (R_{i} - i + 1).
Calculating the maximum element in a range can be computed efficiently using a
range minimum (maximum) query-type
data structure in O(1) time per query, meaning O(log **N**) total time for the binary search.

In terms of time complexity, for each i, we need to perform 4 binary searches, which take
O(log **N**) time each, for an overall O(**N** log **N**) total time.
Setting up the range maximum query data structure takes an additional
O(**N** log **N**) time, yielding an overall O(**N** log **N**) time for
the full algorithm. There are solutions that can compute all of
the required L_{i} and R_{i} values (defined above) in O(**N**) total time
by doing a couple of clever sweeps of the data to count the number of unfair
intervals, but this was not needed for this problem.

Test Data

We recommend that you practice debugging solutions without looking at the test data.