This year, Round 1B jumped right into the *Expogo* problem, which had a
pleasing deterministic solution. *Blindfolded Bullseye* was interactive
and involved geometry; arriving at a correct algorithm probably required
drawing some pictures and experimenting bravely! The card-shuffling
*Join the Ranks* had a constructive solution, but one that wasn't easy
to find, and a brute-force approach was too slow even for Test Set 1 without
an insight.

This was a more time-consuming set of problems than Round 1A's set, and we
didn't see our first perfect score until about an hour into the round.
**jiry_2** was in the lead for much of the first hour, and was the first
to solve every problem, but **mnbmvar** swooped in with a penalty time of
1:04:30, and **jiry_2**'s penalty time ended up being slightly larger, at
1:07:08. **isaf27** came in third with 1:08:38, and then
**Marcin.Smulewicz** and **duality** were not far behind in fourth and
fifth. By the end of the contest, there were almost 90 perfect scores.

Once again, we had a five-digit number of contestants on the scoreboard. Tentatively, the advancement cutoff is 34 points plus a small enough penalty time. It wasn't quite enough to solve just Expogo! We saw quite a few pickups of the first Blindfolded Bullseye set; the first Join the Ranks set, on the other hand, was tougher to snag.

Round 1C is two weeks from now, so you will have some extra time to practice if that round will be your last chance to advance. Good luck, and next time you play darts, remember to flush your buffer between throws!

**Cast**

Expogo: Written by Ian Tullis. Prepared by John Dethridge.

Blindfolded Bullseye: Written and prepared by Pablo Heiber.

Join the Ranks: Written by Shik Chen and Pi-Hsun Shih. Prepared by Kevin Gu and Jonathan Irvin Gunawan.

Solutions and other problem preparation and review by Liang Bai, Darcy Best, Timothy Buzzelli, John Dethridge, Kevin Gu, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Andy Huang, Nafis Sadique, Pi-Hsun Shih, Kevin Tran, and Max Ward.

Analysis authors:

- Expogo: Ian Tullis.
- Blindfolded Bullseye: Pablo Heiber.
- Join the Ranks: Pablo Beltran.

You have just received the best gift ever: an Expogo stick. You can stand on it and use it to make increasingly large jumps.

You are currently standing on point (0, 0) in your infinite two-dimensional
backyard, and you are trying to reach a goal point (**X**, **Y**), with
integer coordinates, in as few jumps as possible. You must land exactly on
the goal point; it is not sufficient to pass over it on a jump.

Each time you use your Expogo stick to jump, you pick a cardinal direction:
north, south, east, or west. The i-th jump with your Expogo stick moves you
2^{(i-1)} units in the chosen direction, so your first jump takes you
1 unit, your second jump takes you 2 units, your third jump takes you 4 units,
and so on.

Given a goal point (**X**, **Y**), determine whether it is possible to
get there, and if so, demonstrate how to do it using as few jumps as
possible.

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each consists of a single line with two integers
**X** and **Y**: the coordinates of the goal point.

For each test case, output one line containing `Case #x: y`

, where
`x`

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

is `IMPOSSIBLE`

if the goal point cannot be reached. Otherwise,
`y`

must be a string of one or more characters, each of which is
either `N`

(north), `S`

(south), `E`

(east),
or `W`

(west), representing the directions of the jumps that you
will make, in order. This sequence of jumps must reach the goal point at the
end of the final jump, and it must be as short as possible.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

(**X**, **Y**) ≠ (0, 0).

1 ≤ **T** ≤ 80.

-4 ≤ **X** ≤ 4.

-4 ≤ **Y** ≤ 4.

1 ≤ **T** ≤ 100.

-100 ≤ **X** ≤ 100.

-100 ≤ **Y** ≤ 100.

1 ≤ **T** ≤ 100.

-10^{9} ≤ **X** ≤ 10^{9}.

-10^{9} ≤ **Y** ≤ 10^{9}.

Sample Input

4 2 3 -2 -3 3 0 -1 1

Sample Output

Case #1: SEN Case #2: NWS Case #3: EE Case #4: IMPOSSIBLE

In Sample Case #1, you can jump south from (0, 0) to (0, -1), then jump east to (2, -1), then jump north to (2, 3).

We can be sure there is not a more efficient solution (two moves or fewer) because at least 2 + 3 = 5 units of distance are needed to reach the goal point, but the first two jumps combined only give us 3 units of distance.

Notice that Sample Case #2 is like Sample Case #1 but reflected across both axes, and so the answer comes from reflecting all directions in Sample Case #1's answer.

In Sample Case #3, notice that `EWE`

would not be a valid answer,
even though it reaches the target, because there is a way to get there using
fewer jumps.

We leave it to you to determine why it is impossible to reach the target in Sample Case #4.

Gary has a large square wall that is exactly 2 × 10^{9} nanometers tall and
2 × 10^{9} nanometers wide.
Gary has a dartboard placed on the wall. The dartboard is circular and its radius is
between **A** and **B** nanometers, inclusive.
The dartboard is fully contained within the wall, but it may touch its edges.
The center of the dartboard is an integer number of nanometers from each edge of the wall.

Gary invited his friend Mika over to play an interesting game. Gary blindfolds Mika and challenges her to throw a dart at the center of the dartboard. To help her, whenever Mika throws a dart at the wall, Gary will tell her whether the dart hit the dartboard.

Mika does not know where on the wall the dartboard is, but since Mika is very skilled at darts, she can throw darts with nanometer precision. That is, she can aim and hit exactly any point that is an integer number of nanometers away from each edge of the wall. Immediately after throwing each dart, Gary tells her whether she hit the center of the dartboard, some other part of it, or missed it completely and hit the bare wall.

Can you help Mika hit the center of the dartboard, without throwing more than 300 darts?

Initially, your program should read a single line containing three integers **T**,
**A** and **B**, indicating the number of test cases and the inclusive minimum and maximum
values for the dartboard's radius, in nanometers, respectively. (Notice that **A** and
**B** are the same for every test case within a test set.) Then, you need to process **T**
test cases.

We represent the points that darts can be aimed at as pairs (x, y), where x and y are
integers between -10^{9} and 10^{9}, inclusive. The pair (x, y) is
the point that is x + 10^{9} nanometers away from the left edge of the wall and
y + 10^{9} nanometers away from the bottom edge of the wall. Point (0, 0) is therefore
at the exact center of the wall.

For each test case, there is a secretly chosen radius R for the dartboard, and a secretly chosen center of the dartboard (X, Y). R, X, and Y are integers chosen for each test case by the judges in a designed (not random) way, within the limits. For each test case you need to process up to 300 exchanges with the judge. Your program represents Mika and the judge program represents Gary. Each exchange consists of Mika (your program) choosing where to throw a dart and Gary (the judging program) giving information about that position.

The i-th exchange consists of your program first outputting a single line containing two integers
X_{i} and Y_{i}, both between -10^{9} and 10^{9}, inclusive,
and the judge responding with a single line containing either:

`CENTER`

if X_{i}= X and Y_{i}= Y`HIT`

if 0 < (X - X_{i})^{2}+ (Y - Y_{i})^{2}≤ R^{2}`MISS`

in all other cases.

After sending `CENTER`

, the judge will start waiting for the first
exchange of the next test case, if there is any.

If you output a line that is incorrectly formatted or with an out of bounds value,
the judge will respond with a single line containing `WRONG`

.
If 300 exchanges occur (including 300 responses from the judge) without you receiving
`CENTER`

, or if you ever receive `WRONG`

, the judge will finish all
communication, wait for your own program to also finish, and give a Wrong Answer verdict.
After sending the **T**-th `CENTER`

, on the other hand, the judge will finish all
communication, wait for your own program to finish, and give a Correct verdict.
If, while waiting for your program to finish, time or memory limits are exceeded,
the corresponding verdict will be assigned instead. (Note that verdicts are not messages
sent to your program.)

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 20.

**A** ≤ R ≤ **B**.

-10^{9} + R ≤ X ≤ 10^{9} - R.

-10^{9} + R ≤ Y ≤ 10^{9} - R.

**A** = **B** = 10^{9} - 5.

**A** = **B** = 10^{9} - 50.

**A** = 10^{9} / 2.

**B** = 10^{9}.

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.

**The interactive runner was changed after the 2020 Qualification Round.
Be sure to download the latest version.**

The following sample interaction uses the limits of Test Set 1.

// The following reads 20 into t and 999999995 into a and b. t, a, b = readline_int_list() // The judge secretly picks R = 999999995 (it had no choice) and X = -1, // Y = 3 (it did have a choice here). (Note: the actual Test Set 1 will // not necessarily use the values in this example.) // We try to throw at the upper left corner of the wall, and the dartboard // does not overlap with that point. printline -1000000000 1000000000 to stdout flush stdout r = readline_string() // reads MISS. // We try to throw at the center of the wall. That does hit the dartboard, // but not the center. printline 0 0 to stdout flush stdout r = readline_string() // reads HIT. // We make a super lucky choice and throw at the center of the dartboard. printline -1 3 to stdout flush stdout r = readline_string() // reads CENTER. // The judge begins the next test case. It secretly picks R = 999999995 // and X = 5, Y = 5. // We accidentally throw a dart out of the allowed range. printline -1234567890 1234567890 to stdout flush stdout r = readline_string() // reads WRONG. exit // exits to avoid an ambiguous TLE error.

You recently acquired a new deck of cards. Each card displays a rank, which
is an integer between 1 and **R**, and a suit, which is an integer between
1 and **S**. For each combination of a rank and a suit, there is exactly
one card that displays it, meaning that the deck has **R** ×
**S** cards in total. We will denote a card with rank r and suit s as
(r, s).

Being brand new, the deck is sorted from top to bottom by suit in increasing
order, with ties being broken by ranks in increasing order. That is, (1, 1)
comes first, then (2, 1), ..., (**R**, 1), then (1, 2), (2, 2), ...,
(**R**, 2), and so on up to (**R**, **S**). For example, with
**R** = 4 ranks and **S** = 2 suits, the initial ordering would be:
(1, 1), (2, 1), (3, 1), (4, 1), (1, 2), (2, 2), (3, 2), (4, 2).

You want to reorder the deck to be sorted by rank. That is, you want to put
all the cards of the same rank together, and have the ranks be in increasing
order. You do not care, however, about the order of the suits within each
rank. For example, with **R** = 4 and **S** = 2, one of the various
possible valid new orderings would be: (1, 2), (1, 1), (2, 1), (2, 2), (3, 1),
(3, 2), (4, 2), (4, 1).

You have been learning how to cook, so you want to reorder the deck without putting your spatulas down. You decided to sort the deck using only the following multi-part operation:

- First, take one or more cards from the top of the deck, and set that selection aside as pile A.
- Next, take one or more cards from the new top of the deck, and set that selection aside as pile B.
- Finally, put pile A on top of the deck, and then put pile B on top of the new deck.

Notice that the operation exchanges the pile A part of the deck and the pile B part of the deck, without affecting any other cards deeper in the deck (if there are any).

Continuing with our **R** = 4, **S** = 2 example, if your first move is
to choose 3 cards from the top for pile A and 2 cards for pile B, then these
are the cards you get:

A: (1, 1), (2, 1), (3, 1),

B: (4, 1), (1, 2), and

Remainder of deck: (2, 2), (3, 2), (4, 2).

After putting A on the deck and then B on top of that, the new deck is
ordered like this:

(4, 1), (1, 2), (1, 1), (2, 1), (3, 1), (2, 2), (3, 2), (4, 2).

Given **R** and **S**, find a sequence of operations that reorders the
deck to be sorted by rank, as described above, and uses the minimum possible
number of operations to do so.

The first line of the input gives the number of test cases, **T**.
**T** lines follow. Each of these lines describes a single test case with
two integers **R** and **S**, the number of ranks and suits in the
deck, respectively.

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 operations needed to reorder the deck
as explained above. Then, print `y`

more lines containing
`a`

, meaning that in the i-th operation
in a sequence of moves that reorders the deck, you take
_{i} b_{i}`a`

cards first to form pile A and then
_{i}`b`

cards after that to form pile B.
_{i}

Memory limit: 1GB.

Time limit: 30 seconds.

**T** = 12.

2 ≤ **R** ≤ 5.

2 ≤ **S** ≤ 7.

**R** × **S** ≤ 14.

Time limit: 60 seconds.

1 ≤ **T** ≤ 100.

2 ≤ **R** ≤ 40.

2 ≤ **S** ≤ 40.

Sample Input

3 2 2 3 2 2 3

Sample Output

Case #1: 1 2 1 Case #2: 2 3 2 2 1 Case #3: 2 2 3 2 2

In Sample Case #1, the initial order is

In Sample Case #2, the initial order is

In Sample Case #3, another valid solution is `a`

= 4,
_{1}`b`

= 1 first, and then _{1}`a`

= 3
and _{2}`b`

= 1.
_{2}

Test Set 1 is small enough to solve by hand. We can speed this up with a couple of observations:

- We can notice that every position with an even (X + Y) (apart from the origin) — hereafter an "even" position — seems to be unreachable. We can prove to ourselves that this is true: our initial X and Y coordinates of (0, 0) are both even, but only the first of our possible jumps (the 1-unit one) is of an odd length, and all jumps after that are of even lengths. So there is no way to reach any other "even" position starting from the origin, no matter how much jumping we do.
- We can find that all "odd" positions, on the other hand, can be reached using no more than 3 moves.
- To speed up solving the "odd" positions, we can take advantage of
symmetry, as suggested in the explanation for Sample Case #2. For example,
if we learn that
`EEN`

is a solution for (3, 4), then we also know that`WWS`

is a solution for (-3, -4), and`EES`

is a solution for (3, -4), and so on. Because of all the horizontal, vertical, and diagonal symmetry, there are really only six fundamentally different cases! - We can check that our solutions are optimally short by using an argument
like the one in the explanation for Sample Case #1. Any position with a
Manhattan distance (that is, |
**X**| + |**Y**|) of 1 cannot be reached in fewer than one jump; positions with Manhattan distances up to 3 and 7 require at least two or three jumps, respectively. If our solution lengths match these lower bounds — and they probably do unless we have jumped in an unusually indirect way — then they are valid.

Based on the observations above, we may think to try a breadth-first search of all possible jumping paths, and continue until every "odd" (X, Y) position (with -100 ≤ X ≤ 100 and -100 ≤ Y ≤ 100) has been reached. It turns out that each such position is reachable in no more than 8 moves. We know that these solutions are optimally short because of the breadth-first nature of the search.

Suppose that (**X**, **Y**) = (7, 10). In what direction should we
make our initial 1-unit jump? As we saw above, we need our final X coordinate
to be odd, but it is currently even, and we have only one chance to go from
even to odd. Moving north or south will make our Y coordinate odd, but then
we will never have another chance to make that even and the X coordinate odd.
So we should either move west or east. For now, let's guess that we will go
west; we will revisit the other possibility later.

That jump will take us to (-1, 0), and we will next need to make a 2-unit jump. Notice that we can make this look identical to the original problem setup, if we make two changes:

- Shift (-1, 0) to be the new (0, 0). Then the goal becomes (8, 10) rather than (7, 10).
- Transform the scale of the problem such that a 2-unit jump (to a "neighboring" cell) becomes the new 1-unit jump. Then the goal becomes (4, 5) instead of (8, 10).

With this in mind, let's revisit our original decision to jump to the west. If we had jumped east instead, we would have ended up at (1, 0), and if we had changed the problem in the same way we did above, our new goal would have been (3, 5). But that would be an "even" position (after rescaling), which cannot be reached! So we had no choice after all; we had to move west to be able to eventually reach the goal. It's a good thing we were so lucky!

So now the problem has "reset", and we are at (0, 0) and trying to get to
(4, 5). In what direction should we make our "first" jump? Now we know we
must move vertically, since 5 is odd and we will only have "one chance" to
go from even to odd. If we jump north, the next rescaling will have a target
of (2, 2), but if we jump south, the target will be (2, 3), which is the
"odd" position that we want. From there, we should jump south to change the
target to (1, 2), then east to change the target to (0, 1). At that point,
we have a choice between jumping north and reaching the goal, and jumping
south (which could still allow us to reach the goal after some further moves,
e.g. one more to the south and then one more to the north). But the problem
requires that we choose the shortest solution, so we should jump right to
the goal! Therefore, the answer in this case is `WSSEN`

.

Notice that this method is deterministic: we always have only one choice out of the four possible directions. We can rule out two of them because they will not make the correct coordinate odd. Of the other two, the new goal states they would leave us with must differ only in one of the coordinates and only by exactly 1 unit, and therefore one must be an "odd" position and the other must be an "even" position. It is possible that that "even" position is the goal, in which case we should jump there, but otherwise, we must choose the "odd" position.

The above analysis also shows that the only time we have a choice is when one of those options is to jump directly to the goal, in which case we obviously should. So we can be confident that our method produces the shortest possible solution. (We also know that that solution is unique, since if we were to choose to not jump directly to the goal when we had that option, we would only end up with a longer solution.)

Our method has a running time which is logarithmic in the magnitudes of the coordinates, so it will solve this test set blazingly fast!

This problem is a riff on the Pogo problem from Round 1C in 2013. If you were
familiar with that problem, the analysis might have helped a bit with this
one... but, like a well-designed pogo stick, Expogo is not *too*
difficult to get a handle on anyway.

Test Data

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

In Test Set 1 the radius is both really large and known in advance. The fact that it is large gives
us a major restriction: plugging in the value for R in the limits for X and Y shows that the hidden
center is restricted to a square with side length 10 nanometers, centered on the origin. That means
that there are only 11^{2} = 121 possible positions for the center! We can simply try
throwing a dart at each of them, stopping as soon as we are told that we have hit the
`CENTER`

.

In Test Set 2 the radius is also large and known, but small enough that the square of candidate center points has side 101 nanometers. This means that there are 10201 possible centers, which is a lot more than the number of darts we get. We need to restrict that further.

We can use the fact that we know the exact radius to reduce this number. Every dart we throw can give us a clue. If a dart thrown at point p hits, that means the the distance between p and the center c is no more than R. If a dart thrown at point q misses, that means that the distance between q and c is more than R. If we find two points p and q that are close to each other, the points that are no more than R away from p but more than R away from q form a narrow crescent-shaped region of width equal to the distance between p and q. Intersecting that with the original square of possibilities from the first paragraph can give us a small enough range for c that we can just throw a dart at each possibility without running out of darts.

We can find points p and q that are close to each other by finding the edge of the dartboard. Since
the dartboard is so large, the edge has to be close to the edge of the wall. If we inspect points
(x, 0) for the possible values of x, most points are guaranteed to be inside the dartboard: any
point (x, 0) with -10^{9} + 101 ≤ x ≤ 10^{9} - 101 is no more than R away from
all possible centers, and is thus guaranteed to be inside the circle. Therefore, we can try all
possible x on any one side of that guaranteed interval to find a hit point and a miss point that are
1 nanometer away from each other. Since there are only 101 points on each side that are not
guaranteed to be in the circle — for example [-10^{9}, -10^{9} + 100] —
this requires at most 101 darts.

After finding those points, we know that the center has to be inside a narrow crescent-shaped band of width 1. Intersecting that with the 101-by-101 square of candidates leaves at most 202 candidates, since there can't be more than 2 candidates that share an x value. Moreover, for most x values, the rounding ensures that there are less than 2, so the 199 darts we have left are enough to cover all candidates.

Notice that no complicated geometry is involved to find the candidates; the square is small enough to iterate over all points within it and check the distances to our hit and miss points to see if they are candidates or not.

For Test Set 3, we can take a more typical geometric approach. To find the center of a circle, we can find 3 points on the edge of the circle, and then calculate a center from those. This has an issue: we only have nanometer precision, which means we would typically find points near the edge of the circle, but not exactly in it. The error that this introduces in our calculations could be significant. We can overcome this by bounding the error and then checking not only our calculated center, but also other nearby points too. The math to calculate the center, and most importantly, to bound the error of it, can be hard and time consuming, but it is doable. In addition, you can wing it by not bounding the error and instead starting to throw at your calculated center and then spiral around it on nearby points until you find the actual center. This requires a leap of faith that you won't run out of tries, but it's a reasonable assumption. Fortunately, there is a simpler related approach that is more clearly correct, that we describe below. Of course, we still need to solve the problem of finding "almost-edge" points of the circle, which we also need for our simpler approach.

To find a point in the edge, we can't use the approach in Test Set 1, because if the dartboard's
radius is not very large, those points could be really far away from the wall's edge. A different
way of doing it is via a
binary search.
Say we know that point (x_{0}, y_{0}) is within the dartboard. Then,
we know that for all x in the range [-10^{9}, x_{0}]
the points (x, y_{0}) are grouped such that there is a (possibly empty) interval having
all misses, and then an interval having all hits. The same holds (in reverse) for
[x_{0}, 10^{9}]. Analogously, points (x_{0}, y) for y in
[-10^{9}, y_{0}] or [y_{0}, 10^{9}] are grouped by hits/misses.
Then, for each of those ranges, we can do a binary search to find the switching point —
that is, a point in the edge of the circle. This is exactly what we did in Test Set 2, except
we fixed x_{0} = 0, because the radius is so large that some points
like (0, 0) are guaranteed to be inside the dartboard, and the range is small enough that we
can scan it entirely instead of using binary search.

The searches above get us leftmost and rightmost points inside the dartboard for a given
y-coordinate y_{0}, and topmost and bottommost points for a given x-coordinate
x_{0}. Notice that the dartboard is symmetric with respect to the horizontal and vertical
lines that go through its center. Therefore, the leftmost and rightmost points inside the dartboard
in any fixed y-coordinate mirror each other, and the x-coordinate of the center is the midpoint
between their x-coordinates. Similarly, we can find the y-coordinate of the center
as the midpoint between the y-coordinates of the topmost and bottommost points inside the
dartboard at any fixed x-coordinate.

The remaining task is to find a single point inside the dartboard. Since the area of the dartboard
makes up a significant percentage of the wall area (at least π / 16), we could do this by
throwing darts at random until we hit one point (the probability of hitting could be slightly less
than π / 16 because we consider only points with integer nanometer coordinates, but the
difference is negligible). This has an overwhelmingly high chance of hitting in 100 throws or fewer
for all cases. However, there is a deterministic way that also works, which is to divide
the wall into squares of side **A**. If the center of the dartboard is inside a square, it is
guaranteed that at least one of the corners of that square is inside the dartboard. Therefore, we
can simply try all those corners (there are only 25, and it is even possible to restrict it
further), and we will find a hit point.

So, we need a fixed small number of darts (up to 100, depending on our method of choice)
to find a point inside the dartboard, and each binary search
needs at most 31 = ceil(log_{2} (2 × 10^{9} + 1)). That is at most
4 × 31 + 100, which is a lot less than the 300 limit. In the first version, you need one fewer
binary search — 3 edge points are enough to find a unique center — so after finding
the center with error, you could have 150 darts left to explore its vicinity. Notice that if your
initial point is actually one of the points (X - R, Y), (X + R, Y), (X, Y - R) or (X, Y + R),
you would end up with two points instead of three and be unable to find the center. If we use the
random procedure to find (x_{0}, y_{0}), the probability of this happening is
negligible. Otherwise, we can detect the case and know that the two found points are opposite
each other, so the center is their middle point.

Test set 1 contains the 12 possible inputs allowed by the limits. We can try to solve the problem via a breadth-first search (BFS), on the graph of states, where a state is the current arrangement of cards in the deck. Notice, however, that cases with 14 total cards would yield an enormous graph and make the solution run too slowly — probably even too slowly for us to run the code locally to precompute answers that we can then hardcode!

However, one observation will help us: since the success condition does not involve the suits of
the cards at all, we can ignore them and work only with the ranks. That dramatically cuts down
the number of possible states, by going from
(**R** × **S**)! to (**R** × **S**)! / ((**S**!)^{R}).
This allows a BFS to finish fast enough for this test set. We can also use this observation while
solving the next test set...

For test set 2, the worst case (**R**=40, **S**=40) has around 1.8 x 10^{2517}
unique orderings. This means that the brute force solution will not work.

Our first important observation is that the reordering operation can decrease the
number of adjacent cards of different ranks by at most two. In the starting configuration
there are (**R** × **S**)-1 adjacent cards of different ranks. In the ending
configuration there are **R**-1 adjacent cards of different ranks. So to get from
(**R** × **S**)-1 to **R**-1 we need at least
ceil((**R** × **S** - **R**) / 2) operations.

Now that we know ceil((**R** × **S** - **R**) / 2) is a lower bound on the answer,
if we can come up with a method that is guaranteed to use no more than
ceil((**R** × **S** - **R**) / 2) steps, then it will always produce a valid
answer.

Now we will outline a way to sort the cards using exactly that many operations. The invariant we
maintain is that at all times, for the ranks X and Y of any two consecutive cards, either Y = X,
or Y = (X + 1) mod **R**. This is of course true for the initial ordering of the deck.

We repeatedly perform the following operation, as long as the number of adjacent pairs of cards
of the same rank is less than **R** - 1 and the operation would not pick up the bottom card of
the deck: find the largest block of consecutive cards from the top that contains exactly 2
different ranks to use as pile A. By the invariant, this will be one or more cards with rank X,
followed by one or more cards with rank (X+1) mod **R**. Then, starting from the first card
from the top that is not on pile A, take as pile B the largest block of consecutive cards that
does not contain any cards of rank X, plus all consecutive cards of rank X that immediately
follow that block. Notice that at least one such card of rank X must exist; otherwise, by the
invariant, the number of adjacent pairs of cards of different ranks would already be **R**-1.

We can show that this operation reduces the number of adjacent cards of different ranks by 2 every
time it does not pick up the bottom card of the deck. To show this, notice that the bottom of pile
B is a card of rank X and the first card left over in the deck is, by the invariant,
(X + 1) mod **R**. That means that the new adjacent pairs are two cards of rank X
(the bottom of pile B and the top of pile A) and two cards of rank (X + 1) mod **R**
(the bottom of pile A and the top of the leftover deck). The broken adjacent pairs are —
by definition of piles A and B — both of cards of different rank. Therefore, the number of
adjacent pairs of cards of different rank decreases by 2 with this operation.

Suppose that performing the operation would pick up the bottom card of the deck. That means that
all cards of rank X are in two contiguous blocks at the top and bottom of the deck before the
operation is performed. In addition, since this is the first time the bottom card of the deck is
picked up for an operation, X = **R**. Because of the invariant, that requires every other rank
to be in a single contiguous block. In this ordering, there are exactly **R** adjacent pairs of
cards with different ranks. Instead of the operation above, we finish by making pile A consist of
the largest block of consecutive cards of rank **R**, starting at the top, and pile B be the
rest of the deck. After performing the operation, **R** - 1 pairs of adjacent cards of
different ranks remain (by a similar argument as before, ignoring the broken and created pairs
that involved the leftover deck, since there is none leftover) and the final card of the deck is
still **R**.

After performing the repeated operation floor((**R** × **S** - **R**) / 2)
times, the number of adjacent pairs of cards of the same rank decreases to **R** - 1 if
**R** × **S** - **R** is even or **R** if it's odd. Notice that the number
remains greater than **R** before each such operation, so we would never have picked up the
bottom card of the deck. In the even case, the number of adjacent pairs of cards of the same rank
is now minimum and we never picked up the bottom card of the deck, so we are at exactly the target
ordering. In the odd case, we arrive at the case in which we do pick up the bottom card of the
deck with our last operation, but as argued above, that operation also leaves the deck in the
target order.

Test Data

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