If you want a ticket to the Finals, it all comes down to Round 3! With only
two and a half hours and four problems, you have to know what you can solve,
and solve it *fast*. The competitors are among the best in the world,
and there is little room for error!

The round opened with *Zillionim*, an interactive coin-taking game in
which it was far from trivial to outsmart even a randomly playing AI.
*Pancake Pyramid* was the obligatory pancake problem — actually, we
almost didn't have one at all this year! It was challenging, but approachable
with more "standard" techniques. *Datacenter Duplex* and
*Napkin Folding* were more unusual, and the latter in particular was a
very difficult geometry problem. (We wonder how many folded pieces of paper we
created on our contestants' desks!) Napkin Folding was worth a lot of points,
but not enough to render the other problems unnecessary.

After half an hour, each of the first three problems had been fully solved at
least once. Contestants vied to be the first to finish A + B + C + the first
test set of D, knowing that the second test set of D was a real monster that
probably wouldn't get 25 solves. **ACRushTC** was the first to hit 61
points, at 1:37:35, followed by **rng..58** with 1:41:03 and our longtime
defending champion **Gennady.Korotkevich** with 1:41:47. The Code Jam
staff eagerly watched to see if someone would fully solve D, but alas,
nobody did. That made 61 (or a fast enough 57) the (unofficial) advancement
bar.

If you ranked high enough, we will be in touch about the Finals. As always, though, making it to Round 3 is a major accomplishment, and you will soon have the shirt to prove it! Even if you just watched the contest, preparing for next year, you have our thanks and our best wishes for success in 2020. In the meantime, though, get ready for the Finals on August 9!

**Cast**

Zillionim: Written by Pablo Heiber and Igor Naverniouk. Prepared by Pablo Heiber.

Pancake Pyramid: Written by Andy Huang. Prepared by John Dethridge.

Datacenter Duplex: Written by Pablo Heiber. Prepared by Jonathan Irvin Gunawan and Micah Stairs.

Napkin Folding: Written by Pablo Heiber. Prepared by Timothy Buzzelli.

Solutions and other problem preparation and review by David Arthur, Liang Bai, Darcy Best, Timothy Buzzelli, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Igor Naverniouk, Trung Thanh Nguyen, Pi-Hsun Shih, Micah Stairs, Ian Tullis and Tony Wong.

Analysis authors:

- Zillionim: Ian Tullis
- Pancake Pyramid: Darcy Best and Jacek Jurewicz
- Datacenter Duplex: Pablo Heiber
- Napkin Folding: Timothy Buzzelli

Zillionim is a turn-based game for two players. Initially, 10^{12} coins are
arranged end-to-end in a single line, numbered from 1 to 10^{12} from left to right.
During a turn, a player must select 10^{10} consecutive coins and remove them.
Two coins that were not originally consecutive do not become consecutive even if all of
the coins in between them are removed.

On their turn, a player makes a valid move if possible, and then it is their opponent's turn. If a player cannot make a valid move on their turn, they lose the game (and the opponent wins the game).

Because our engineers are still hard at work training our machine learning model to play Zillionim, we have created a simple AI that plays Zillionim by making random moves. The AI always gets the first turn. On each of the AI's turns, the AI determines all valid moves and chooses one of them uniformly at random.

Can you beat this AI... at least most of the time?

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 minimum number of games you need to win
for your solution to be considered correct. Then, you need to process **T** test cases,
each of which is a single game of Zillionim.

Each test case is processed by making exchanges with the judge until one player wins
the game. For each exchange, the judge first outputs a single line with a
single integer **P**, to be interpreted as follows:

- If 1 ≤
**P**≤ 10^{12}- 10^{10}+ 1, then the AI has removed coins numbered**P**,**P**+ 1, ...,**P**+ 10^{10}- 1 and it is your turn. Note that this means there is at least one valid move remaining for you to play. The AI always plays a valid move. - If
**P**=`-2`

, your last move caused you to win the current game. - If
**P**=`-3`

, the AI has made a move that caused it to win the current game. Notice that in this case, the judge does not send you the AI's last move. - If
**P**=`-1`

, the last information you sent to the judge was malformed data or an invalid move (out of range or attempting to remove coins that were not there), meaning that you will get a Wrong Answer verdict for not playing correctly (more below).

After receiving a positive integer **P**, you should send back a single line with a positive
integer Q (1 ≤ Q ≤ 10^{12} - 10^{10} + 1)
representing that you are removing coins numbered Q, Q + 1, ..., Q + 10^{10} - 1.
Each of these coins must not have been previously removed during the current game.

After the judge sends a `-2`

or `-3`

, if it was the last game,
the judge will terminate and so should your program. Otherwise, the judge will proceed
to send data corresponding to the first exchange of the next game. The judge
will not check how many games you have won or lost until all games have been processed correctly.
For example, if you win **T** - 1 games and then send malformed data during the last game,
you will receive a Wrong Answer verdict, regardless of the value of **W**.

After receiving a `-1`

, your program should terminate to receive a
Wrong Answer verdict. 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 normally and within the time limit to receive a Wrong Answer verdict
instead of a Runtime Error or Time Limit Exceeded.

The seed for the random generator is predetermined (and is different) for each game. This means that two submissions that make the exact same sequence of moves in a given game will receive the exact same sequence of moves from the AI for that game. It also means the play of the AI in a game does not depend, even in the pseudo-random generation sense, on the plays made in previous games within the same test set.

Time limit: 50 seconds per test set.

Memory limit: 1GB.

**T** = 500.

-3 ≤ **P** ≤ 10^{12} - 10^{10} + 1.

**P** ≠ 0.

**P** represents a valid play or valid information about the game's status,
as explained above.

**W** = 300.

**W** = 475.

**W** = 499.

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.

For simplicity, the following interaction uses 50 coins in total instead of 10^{12}, and
each move removes 10 consecutive coins instead of 10^{10}. The rules are otherwise the
same.

t, w = readline_int_list() // reads 500 into t and 300 into w p = readline_int() // reads 23 into p; this is the beginning of the first game. The // AI has taken coins 23 through 32, inclusive. printline 38 to stdout // we decide to take coins 38 through 47, inclusive flush stdout p = readline_int() // reads 3 into p. The AI has taken coins 3 through 12, inclusive. printline 13 to stdout // we decide to take coins 13 through 22, inclusive // (and this is our only remaining move!) flush stdout p = readline_int() // reads -2 into p. We won the first game since the AI had no move. p = readline_int() // reads 32 into p; this is the beginning of the second game. The // AI has taken coins 32 through 41, inclusive. printline 13 to stdout // we decide to take coins 13 through 22, inclusive flush stdout p = readline_int() // reads -3 into p. We don't know the AI's move, but it left us // with no valid move, so we lost the second game. p = readline_int() // reads 10 into p; this is the beginning of the third game. The // AI has taken coins 10 through 19, inclusive. printline 0 to stdout // we select an invalid index (coin numbering starts at 1!) flush stdout p = readline_int() // reads -1 into p -- we have made a mistake! exit // exits to avoid an ambiguous TLE error

You have just finished cooking for some diners at the Infinite House of
Pancakes. There are **S** stacks of pancakes in all, and you have arranged
them in a line, such that the i-th stack from the left (counting starting
from 1) has **P _{i}** pancakes.

Your supervisor was about to bring out the stacks to the customers, but
then it occurred to her that a picture of the stacks might make for a good
advertisement. However, she is worried that there might be too many stacks,
so she intends to remove the L leftmost stacks and the R rightmost stacks,
where L and R are nonnegative integers such that L + R ≤ **S** - 3.
(Notice that at least 3 stacks of pancakes will remain after the removal.)

Your supervisor also thinks the remaining stacks will look aesthetically
pleasing if they have the *pyramid property*. A sequence of N stacks
of heights H_{1}, H_{2}, ... , H_{N} has the pyramid
property if there exists an integer j (1 ≤ j ≤ N) such that
H_{1} ≤ H_{2} ≤ ... ≤ H_{j-1} ≤ H_{j} and
H_{j} ≥ H_{j+1} ≥ ... ≥ H_{N-1} ≥ H_{N}.
(It is possible that this sequence might not look much like a typical
"pyramid" — a group of stacks of the same size has the pyramid
property, and so does a group in which the stack heights are nondecreasing
from left to right, among other examples.)

Note that the sequence of stacks remaining after your supervisor removes
the L leftmost and R rightmost stacks might not yet have the pyramid
property... but you can fix that by adding pancakes to one or more of the
stacks! The *pyramidification cost* of a sequence of stacks is the
minimum total number of pancakes that must be added to stacks to give the
sequence the pyramid property.

While your manager is carefully deciding which values of L and R to choose,
you have started to wonder what the sum of the pyramidification costs over
all valid choices of L and R is. Compute this sum, modulo the prime
10^{9}+7 (1000000007).

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each begins with one line containing one integer
**S**: the number of stacks of pancakes. Then, there is one more line
containing **S** integers **P _{1}**,

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 sum of the pyramidification costs over all valid choices of L and R,
modulo the prime 10^{9}+7 (1000000007).

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **P _{i}** ≤ 10

**S** = 3000, for up to 20 test cases.

3 ≤ **S** ≤ 500, for all remaining cases.

**S** = 10^{6}, for up to 1 test case.

**S** = 10^{5}, for up to 3 test cases.

3 ≤ **S** ≤ 10000, for all remaining cases.

Input |
Output |

3 3 2 1 2 5 1 6 2 5 7 4 1000000000 1 1 1000000000 |
Case #1: 1 Case #2: 16 Case #3: 999999991 |

In Sample Case #1, your supervisor must choose L = 0 and R = 0, so that is the only scenario you need to consider. The optimal strategy for that scenario is to add a single pancake to the middle stack. Although the resulting sequence of stacks looks flat, notice that it has the pyramid property; in fact, any index will work as the j value.

In Sample Case #2, here are all possible choices of L and R, the corresponding remaining stacks, and what you should do in each scenario.

- L = 0, R = 0: H = [1 6 2 5 7]. The optimal solution is to add four pancakes to the third stack and one pancake to the fourth stack. Then we have [1 6 6 6 7], which has the pyramid property with j = 5.
- L = 0, R = 1: H = [1 6 2 5]. The optimal solution is to add three pancakes to the third stack. Then we have [1 6 5 5], which has the pyramid property with j = 2.
- L = 0, R = 2: H = [1 6 2]. This already has the pyramid property with j = 2.
- L = 1, R = 0: H = [6 2 5 7]. The optimal solution is to add four pancakes to the second stack and one pancake to the third stack. Then we have [6 6 6 7], which has the pyramid property with j = 4.
- L = 1, R = 1: H = [6 2 5]. The optimal solution is to add three pancakes to the second stack. Then we have [6 5 5], which has the pyramid property with j = 1.
- L = 2, R = 0: H = [2 5 7]. This already has the pyramid property with j = 3.

So the answer is (5 + 3 + 0 + 5 + 3 + 0) modulo (10^{9} + 7), which
is 16.

In Sample Case #3, we only need to add extra pancakes to create the pyramid
property when L = 0 and R = 0. In that case, it is optimal to add 999999999
pancakes to each of the second and third stacks. (We hope the diners are
hungry!) So the answer is (999999999 + 999999999) modulo
(10^{9} + 7) = 999999991.

Two companies, Apricot Rules LLC and Banana Rocks Inc., are sharing the same datacenter.
The datacenter is a matrix of **R** rows and **C** columns, with each cell containing
a single server tower. Each tower contains intellectual property belonging to exactly one of
the two companies.

At first, they built walls on the edges between cells assigned to different companies. This allowed orthogonally adjacent cells belonging to the same company to remain connected. Also, two cells x and y are considered connected if x is connected to a cell that is, directly or indirectly, connected to y. With this definition, it was possible that two cells assigned to the same company were not connected, which was unacceptable.

Both companies agreed to build narrow hallways running through cell corners that allow two diagonally adjacent cells to be connected directly. Let us write (i, j) to represent the cell at row i and column j. At most one narrow hallway can be built through any given vertex, which means either (i, j) and (i + 1, j + 1) can be connected, or (i + 1, j) and (i, j + 1) can be connected, or neither pair, but not both. Of course, only hallways between cells assigned to the same company can be built.

Given a matrix where each cell is labeled `A`

or `B`

depending
on which company it is assigned to, find a way to add
connections through diagonal adjacencies such that all `A`

s are
connected and all `B`

s are connected.

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each test case begins with one line containing
two integers **R** and **C**, the number of rows and columns of the
matrix representing the datacenter. Then, there are **R** more
lines containing **C** characters each. The j-th character on the i-th of these lines
**M _{i,j}**
is either

`A`

or `B`

, indicating which company owns the cell at (i, j).
For each test case, first output one line containing `Case #x: y`

,
where `x`

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

is `IMPOSSIBLE`

if there is no way to assign the
diagonal connections such that the `A`

cells are connected and
the `B`

cells are connected,
or `POSSIBLE`

otherwise. Then, if you output `POSSIBLE`

,
output **R** - 1 more lines of **C** - 1 characters each.
These characters must correspond to a valid arrangement as described in the statement above.
The j-th character of the i-th of those lines must be `\`

if cells (i, j)
and (i + 1, j + 1) are to be connected, `/`

if cells (i + 1, j) and (i, j + 1)
are to be connected, or `.`

if neither pair is to be connected.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

2 ≤ **C** ≤ 100.

**M _{i,j}** = uppercase

`A`

or uppercase `B`

,
for all i and j.`A`

for at least one pair of i and j.`B`

for at least one pair of i and j.
2 ≤ **R** ≤ 4.

2 ≤ **R** ≤ 100.

Input |
Output |

3 2 2 AB BA 2 3 AAB ABB 3 4 BBAA BABA BBAA |
Case #1: IMPOSSIBLE Case #2: POSSIBLE .. Case #3: POSSIBLE //\ .// |

In Sample Case #1, the pair of `A`

cells and the pair of `B`

cells
need to be connected, but since both connections would have to cross the same vertex,
at most one of the connections can exist.

In Sample Case #2, the cells are already connected in the required way in the input,
so no additional connections are necessary. Note that you can add unnecessary valid
connections, so another valid answer would be `//`

, but `\.`

would be wrong.

In Sample Case #3, there are also multiple solutions, one of which is displayed.

Chalk has been actively traveling the world with his friends taking pictures in all the coolest places. Most recently, he made his way to Europe, where he studied the history of napkin folding. Ever since, Chalk has been collecting a wide variety of napkins to practice the art of napkin folding.

Chalk's napkins can be defined as simple polygons. A simple polygon is a polygon in which no edges intersect except for adjacent edges which meet at their shared vertex. Each vertex of the polygon is on exactly two edges.

Chalk folds his napkins by first drawing a *folding pattern* on them. A
folding pattern is a set of **K**-1 line segments
which are drawn on the napkin. Each line segment connects two points with rational
coordinates on the border of the polygon defining the napkin and is fully contained
in the polygon. No two line segments in a folding pattern may touch or overlap, except possibly at
common endpoints. A folding pattern of **K**-1 line segments
splits the napkin into **K** polygonal regions. Two points
are in the same region if there exists some continuous line (not necessarily
straight) between them which does not intersect any edge of the polygon or any line segment in
the folding pattern — even at endpoints.

Chalk is only interested in *neat folding patterns*. A
folding pattern is *neat* if any two regions that
are adjacent to the same folding line segment *F* are
symmetric with
respect to *F*. This means that folding the napkin along
that line segment would result in the two regions lining up perfectly.

The following picture illustrates a neat folding pattern with **K**=8 regions.

Chalk has been successfully folding his collection of napkins using
neat folding patterns. But he has some napkins in his collection that
he has not been able to find a neat folding pattern for. For each
of those napkins, Chalk needs your help to find a neat folding pattern
with **K** regions or determine that no such neat folding pattern exists.

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each test case starts with a line containing two
integers **N** and **K**: the number of points in the polygon defining
Chalk's napkin and the number of regions to split the napkin into with a
neat folding pattern containing **K**-1 line segments.

The polygon defining the napkin is represented as a list of the **N**
vertices, as encountered when traveling along the perimeter of the polygon
in the clockwise direction, with the first vertex being chosen arbitrarily.
The next **N** lines represent that list. The i-th of these
contains two integers **X _{i}** and

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

, where
`x`

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

is
`POSSIBLE`

if it is possible to make a neat folding pattern
with **K** regions and `IMPOSSIBLE`

otherwise.

If it is possible to make a neat folding pattern with **K** regions, output **K**-1
more lines listing the segments of a neat folding pattern with **K** regions, in any order.
Each line should represent a different segment as
`A`

, where
(_{x} A_{y} B_{x} B_{y}`A`

, _{x}`A`

) and
(_{y}`B`

, _{x}`B`

) are the two endpoints
of the segment, in any order. Each of _{y}`A`

, _{x}`A`

,
_{y}`B`

, and _{x}`B`

should be in the
form _{y}`N/D`

where `N`

and `D`

are positive
integers (written with no leading zeroes) sharing no common prime factors,
and representing the rational number `N`

/`D`

. There
must be no whitespace between `N`

and `/`

, or between
`/`

and `D`

.

Time limit: 60 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

3 ≤ **N** ≤ 200.

1 ≤ **X _{i}** ≤ 1000, for all i.

1 ≤

The

No two adjacent edges of the polygon are collinear.

The polygon is a simple polygon with strictly positive area.

No two edges intersect except for adjacent edges at their shared endpoint.

**K** = 2.

2 ≤ **K** ≤ 10.

Input 1 |
Output 1 |

4 4 2 1 1 1 2 2 2 2 1 3 2 1 1 1 2 2 1 8 2 1 3 3 5 5 5 4 4 7 3 5 1 4 2 3 1 8 2 1 3 3 5 4 4 5 5 7 3 5 1 4 2 3 1 |
Case #1: POSSIBLE 1/1 2/1 2/1 1/1 Case #2: POSSIBLE 1/1 1/1 3/2 3/2 Case #3: IMPOSSIBLE Case #4: POSSIBLE 1/1 3/1 7/1 3/1 |

Input 2 |
Output 2 |

1 10 8 4 1 3 1 2 2 2 3 1 3 1 4 2 4 3 3 3 2 4 2 |
Case #1: POSSIBLE 3/1 1/1 4/1 2/1 3/1 1/1 3/1 2/1 2/1 2/1 3/1 2/1 2/1 2/1 3/1 3/1 2/1 3/1 3/1 3/1 2/1 3/1 2/1 4/1 1/1 3/1 2/1 4/1 |

Note: Sample 2 is not valid for Test set 1. Only Sample 1 will be tested prior to
running Test set 1 (the same way samples normally are). Moreover, Sample 2
will __not__ be tested prior to running Test set 2.

For Sample Case #1, a neat folding pattern with **K**=2 can be drawn using any of
the 4 dashed lines:

For Sample Case #2, a neat folding pattern with **K**=2 can be drawn as follows:

For Sample Case #3, there are no neat folding patterns:

For Sample Case #4, there are two possible neat folding patterns with **K**=2:

For the test set 2 sample case, a neat folding pattern with **K**=8 can be drawn as follows:

There may not be a *zillion* possible solutions to this problem, but
there are more than we can discuss in this analysis! We'll only touch on a
few here, some of which work, and some of which don't. You're welcome to
share yours in the
Code Jam Google Group!

What if we always choose a move uniformly at random from among all available moves, just like the AI does? Intuitively, since the overall number of coins is large relative to the size of any one move, going first or second is not very important (given that in this case, both sides are playing randomly and not using any strategy), and every game is close to a fair coin flip. Suppose that we have a 50% chance of winning a game with this strategy; then, per the binomial distribution, we have only about an 0.0004% chance of winning 300 or more games out of 500. So this approach won't even get us the 1 point for test set 1!

If we were allowed to go first in this game, we could guarantee a win using
the following strategy. Imagine a "center line" drawn between the
(10^{12} / 2)-th and ((10^{12} / 2) + 1)-th coins, dividing
the coins into two regions of equal size. On the first turn, we could take
the group of 10^{10} coins bisected by this line — that is,
the coins numbered from ((10^{12} - 10^{10}) / 2) + 1 to
((10^{12} + 10^{10}) / 2). Then, after every move by the
opponent, we could make the same move, but reflected across this center
line. For example, if the opponent were to take the 10^{10} coins
starting from coin number 2, we would respond by taking the group of
10^{10} coins starting from the next-to-last coin and going left.
We would always be guaranteed a move, by symmetry, so the opponent would
have to eventually lose.

Sadly, we cannot move first, but we can try to adapt this strategy by just
making the mirrored version of the opponent's move. This will always be
possible unless the opponent makes a move that crosses the center line, in
which case we cannot mirror it. But if the opponent happens to move close to
the center line without crossing it — specifically, taking a coin fewer
than 10^{10} / 2 coins away from the center without crossing the
center — then they will ensure their own defeat. If they do happen
to make a move that crosses the center line, we can abandon our strategy and
move randomly.

We can run a local simulation and find that this strategy does better than randomness, winning around 57.5% of the time. Unfortunately, this only gives us about a 14% chance of passing test set 1. Moreover, because our moves depend on the judge's moves, we cannot easily tweak the judge's randomness; we only get some control over that once the judge has made a move that hurts our strategy. So, all in all, it's probably best to abandon this approach.

Let's call a remaining set of (at least 10^{10}) contiguous coins a
"run". Observe that a "run" of exactly 2 × 10^{10} remaining
coins can be very useful for us. We have the option of taking the first
10^{10} or the last 10^{10} coins from that run, and leaving
a run of exactly 10^{10} coins (and therefore one possible move)
behind. On the other hand, if we take any other group of 10^{10}
coins from that run, we will leave no moves behind, "destroying" the run.
Also notice that if the AI happens to move within this run, it will virtually
always make the second type of move; the odds of it happening to choose the
first or last 10^{10} coins are negligible.

Because of this, a run of exactly 2 × 10^{10} coins lets us
control the parity of the game. Suppose, as a thought experiment, that the
only remaining runs are of exactly 2 × 10^{10} coins each, and
that it is our turn. If the number of remaining runs is odd, we can move in
a way that destroys one of the runs, and then the AI will do the same, and so
on until we leave the AI with no moves. If the number of remaining runs is
even, we can take the first 10^{10} coins from one run, leaving the
other 10^{10} behind as a smaller run. Now the AI is in the same bad
"even number of remaining runs" situation that we were just in.

We can set up a situation like this by making many moves early on that leave
behind runs of exactly 2 × 10^{10} coins. For example, we
can repeatedly choose the largest remaining run of size
3 × 10^{10} or greater, and start from the
(2 × 10^{10} + 1)-th coin from the left in that group, leaving
a run of exactly size 2 × 10^{10} behind (in addition to any
leftover piece to the right of our move). Then, as long as there are still
runs larger than 2 × 10^{10} but smaller than 3 ×
10^{10}, we can use our moves to destroy them by moving in their
centers. Our goal is to eliminate all runs larger than 2 ×
10^{10} before the AI randomly destroys all of our runs of 2 ×
10^{10}. Intuitively, we do not need to worry too much about this,
since the AI is more likely to move within some remaining larger runs than
within our last remaining run of 2 × 10^{10} runs, so it will
usually be helping us out! Once all runs are of size
2 × 10^{10} or smaller, and we have at least one run of size
2 × 10^{10}, we have imposed the near-lockdown situation
described above.

We hope you will forgive us for not trying to calculate an exact success probability for the above strategy, but one can use a local simulation to show that it wins, e.g., all 100000 of 100000 games. The chances of it losing more than one of 500 games are vanishingly small... and even if the worst somehow happens, in this case, we do have some control over the overall randomness, and we can try again with a slight tweak.

In Round 1C this year, we had Bacterial Tactics , another problem about a turn-taking game. You may recall that the analysis brought up the Sprague–Grundy theorem ; can we use a similar parity-based strategy here?

As in our 2 × 10^{10} strategy, we can try to keep the number
of remaining runs even for the AI by moving in the middle of a run if there
is an even number of runs, or otherwise taking the left end of some other
large run. Empirically, this strategy solves TS1, and it even solves TS2 if
we always take the largest remaining run. It ends up being similar to our
best strategy described above, even though it does not allow for such fine
control.

We can even achieve a perfect solution for this problem by exhaustively
calculating Grundy numbers and storing them using run-length encoding!
However, it is possible to arrive at the 2 × 10^{10} idea above,
which is good enough, without knowing anything about this theory.

We can make a couple of useful observations at the outset. First, if we have an interval of length 1 or 2, we do not need to add any pancakes for it to have the pyramid property, so we can ignore the restriction of length ≥ 3 in the problem. Second, for any interval, the "peak" in the optimal answer is the largest stack in the original interval (we leave this for you to think about). If there are multiple largest stacks in an interval, we will take the leftmost largest stack as the peak.

For each of the ((**S** + 1) choose 2) intervals, determine where the peak will be located once the interval is
turned into a pyramid. Once we know where the peak will be, we have two smaller problems: we need
a non-decreasing sequence to the peak's left and a non-increasing sequence to the peak's right.
To compute how many pancakes we need in the non-decreasing interval, we may simply sweep from the
leftmost point and add pancakes until no stack in the interval to the left of the i-th stack is strictly taller than
the i-th stack. By maintaining the running maximum as we sweep, we can compute the number of needed
pancakes needed per interval in O(**S**) operations. Since there are O(**S**^{2}) intervals, this
algorithm requires O(**S**^{3}) operations in total.

The ideas above lay the framework for a quicker solution. Instead of independently recomputing the number of
pancakes needed to make an interval non-decreasing (or non-increasing), we can use
the results from other intervals. Say we know the index of largest stack of pancakes in the range
[L, R] (call this index M[L, R]) and the smallest number of pancakes needed to make the interval
[L, R] into a non-decreasing sequence (call this number X[L, R]). We can compute both M[L, R+1]
and X[L, R+1] in O(1) time since the height at M[L, R+1]=max(**P _{M[L, R]}**,

For any interval [L, R], the smallest number of pancakes needed to turn the interval into a
pyramid is simply X[L, M[L, R]] + Y[M[L, R], R]. The precomputation takes O(**S**^{2}) time and
memory and the second step uses O(1) time per interval to compute the answer. Thus, in total, this
is O(**S**^{2}).

The above strategy will be too slow and require too much memory to handle the larger bounds. For this test set, we will still use the same underlying idea of needing the number of pancakes to make an interval non-decreasing or non-increasing. But instead of computing X and Y, we will compute cumulative values: define X'[L, R] = X[L, R] + X[L+1, R] + ... + X[R, R] and Y'[L, R] = Y[L, L] + Y[L, L+1] + ... + Y[L, R]. Now, instead of focusing on the left and right endpoints, we will base our strategy on the peaks of the intervals.

Initially, we do not know the value of X' or Y' for any interval. In our analysis, we will assume that we only know the X' and Y' values for maximal intervals. That is, if two intervals are side-by-side, we will merge them (we will never have intersecting intervals). For example, if we know X'[L, k] and X'[k+1, R], we will merge these together into X'[L, R] and forget about X'[L, k] and X'[k+1, R]. The full process of how to merge is explained below. In particular, this means that any given stack is in at most one known interval for X' and one known interval for Y'.

We will process the peaks from smallest to largest. When we process the i-th stack, we are only
interested in intervals that have stack i as their peak. If X'[L, i-1] is computed for some value
of L, then L must be the furthest left index such that P_{L}, P_{L+1}, ...
, P_{i-1} are all less than P_{i} (since we are processing the stacks from
smallest to largest). Similarly, if Y'[i+1, R] is computed for some value R, then R must be the
furthest right index such that P_{i+1}, P_{i+2}, ...
, P_{R} are all at least P_{i}. If such L and R exist, then we can compute the
number of pancakes needed over all intervals that have i as their peak:

X'[L, i-1] * (R - i + 1) + Y'[i+1, R] * (i - L + 1)

Note that if we don't know X'[L, i-1] for any L, then **P _{i-1}** ≥

Now we want to merge X'[L, i-1], X'[i+1, R] and stack i into X'[L, R]. We will do this in two
steps. First, note that X'[L, i] = X'[L, i-1]: since we are processing the stacks from smallest to
largest, P_{i} can be freely added as the right endpoint of any non-decreasing sequence in this
range. Now let's merge X'[L, i] and X'[i+1, R]. Observe that X'[L, R] sums over intervals that
end at the R-th stack. If an interval starts in the range [i+1, R], then it is already counted
in X'[i+1, R]. If an interval starts in [L, i], then we can start with some sequence in [L, i],
but since **P _{i}** is the peak, every value on the right must be exactly

X'[L, R] = X'[i+1, R] + (X'[L, i-1] +
**P _{i}** × (i-L+1) × (

The Y' values can be computed similarly. In terms of complexity, we need to sort the stacks at the
beginning in O(**S** log **S**) time and the remaining steps take constant time per peak,
so O(**S**) overall. This means the algorithm takes O(**S** log **S**) time.

Although the O(**S** log **S**) solution is fast enough to solve test
set 2, an O(**S**) solution is also possible! We present a sketch of the
idea here, which can be read independently of the solution above.

To make things easier, we pretend that the stacks all have different heights. Each time we compare the heights of two stacks of identical height, we break the tie by assuming that the stack with the larger index is higher.

Let us think through the solution starting from the end. For each stack, we want to compute the pyramidification cost for all the ranges in which this stack is the highest; in such cases, it will be the peak of the pyramid. Then we can sum all of those values for all of the stacks, and that will be our overall result.

In order to compute those pyramidification costs, we can compute the
following for each stack *s*:

- The nearest higher stack to the left of
*s*(possibly an infinitely high "guard" stack appended to the beginning of the sequence); call this the "left blocker". Let D_{L}be the absolute distance (in stacks) from*s*to the left blocker. - The nearest higher stack to the right of
*s*(or guard stack) stack added after the sequence); call this "right blocker". Let D_{R}be the absolute distance (in stacks) from*s*to the right blocker. - The pyramidification cost for all the ranges that end with
*s*and in which*s*is the highest; call this "left pyramidification cost" C_{L}. - The pyramidification cost for all the ranges that start with
*s*and in which*s*is the highest; call this "right pyramidification cost" C_{R}.

Then the pyramidification cost for *s* can be calculated as
C_{L} × D_{R} + C_{R} × D_{L}.

Now, how can we compute C_{L} and D_{L} for each stack?
(The solution is analogous for C_{R} and D_{R}; the only
major difference is that the inequality used to compare stacks is strict
on one side and non-strict on the other, due to tie-breaking.)

We can traverse the stacks from left to right, keeping a Stack structure (capital S to avoid confusion) X that remembers the longest decreasing sequence of stacks ending on the current stack. We iterate through the stacks and when seeing a stack s we consume from X all stacks that are lower than s, adding their contributions to the current left pyramidification cost. Let t' = s at the beginning, and later t' = the previously consumed stack. The contribution of a consumed lower stack t is the number of pancakes missing between t and t' (calculated in constant time, if we precompute the cumulative sum of stack sizes) multiplied by the distance to the left blocker of t'. The left blocker of s is the first stack we can't consume from X, because it's higher than s. Once we're done with s, we add s to X and keep going.

We can start by modeling the problem as a graph where each cell of the input matrix represents a node. Orthogonally adjacent cells with the same label are connected by edges, and we can optionally add edges connecting diagonally adjacent cells with the same label. The goal is to end up with exactly two connected components.

Test set 1 can be solved with dynamic programming, iterating over columns. When considering the i-th column from left to right, we can summarize the state of the connections we have added in the submatrix S of columns 1 through i by recording: (1) whether we have seen (at least one cell of) each of A and B so far, and (2) whether any two cells on the i-th column that contain the same label but are not orthogonally adjacent are connected by a path in S. Then, we can use brute force, and consider all possible choices of how to connect each of the up to 3 cell corners between columns i and i+1 (there are at most 4 rows in Test set 1). There are 3 possibilities for each corner, \, / and no connection, but it can be reduced by noticing if at least one of the connections is valid, it is always optimal to use one, which reduces the number of choices per corner to 2 at the most. If at any point we discover a new isolated A component that cannot be connected to previously seen As, we have failed, and same is true for B. If we finish, we can then use a second pass to reconstruct one choice of diagonal connections that led to solving the problem.

This seemingly simple idea has several technical details that we are omitting here. Some of them can be simplified by starting and ending the process in columns that contain both As and Bs and preprocessing to check if any leftmost or rightmost columns that contain only one type already disconnect the other type.

The overall time complexity of this solution is exponential in **R**, because we are trying all
combinations of O(**R**) corners and recording the connected status of O(**R**) cells
at each state, and linear in **C**,
with the exact formula depending on how the technical details are handled. As long as the base of
the exponential factor is not too large, this is fast enough to pass within the
time limit.

The key observation is: after we decide to add some edges (diagonal adjacencies), two cells c and d containing the same label X end up separated regardless of any future decisions if and only if one of the following two conditions holds:

- 1. There is a cycle of cells labeled Y ≠ X in the graph, with one of c and d being inside the cycle and the other one being outside.
- 2. There is a path of cells labeled Y ≠ X in the graph with the first and last cells of the path being border cells of the matrix, with c and d being on opposite sides of the path.

Let us use G to denote the graph with no diagonal edges added and H to denote the final graph with all edges added. Consider the border of the matrix. Suppose that it contains two cells c and d labeled X that are not connected in G. Since they are not connected in G, that means, going around the border, there are cells e and f labeled Y ≠ X such that e is in between c and d in clockwise order and f is between c and d in counter-clockwise order. That means neither c and d nor e and f can be connected in H with a path of only border cells. Therefore, if c and d are connected in H, the path connecting them disconnects e and f, and vice versa. So, by the second condition, having two cells on the border with the same label that are disconnected in G results in an impossible case.

Notice that there is never an incentive to generate an edge from a diagonal adjacency to connect two cells that are already connected. Per the paragraph above, if a case is possible, then all border cells with the same label are already connected in G. Therefore, if an algorithm never adds an edge from a diagonal adjacency that connects two cells that are already connected, it will never generate a path between two border cells. Additionally, if we never connect cells that are already connected, any cycle in H is a cycle that was already present in G, so again, if we end up in a disconnected situation, the case must have been impossible from the start, before we added any connections.

These observations directly suggest the following algorithm: consider each diagonal adjacency and generate an edge if and only if it will connect two previously disconnected cells. If both choices work, we can choose either, since we already established that the decision of not connecting previously connected cells is enough to guarantee an algorithm will not generate an H with more than 2 connected components when a different one with exactly 2 was possible. After this process, check if there are 2 connected components or more than 2, and print the results.

If we implement the algorithm above using a
union-find to maintain
the connected components, we need O(**R** × **C**) checks for whether two cells
are connected and O(**R** × **C**) connections (joins). Since union-find provides
almost constant amortized time for both operations, the overall time complexity of the algorithm
is quasilinear.

An equivalent algorithm is to calculate the connected components of G first and then use shortest paths to join any two components of the same label until we cannot do it anymore. Since shortest paths cannot create new cycles, an argument similar to the one above proves that this solution is also correct. This solution can be implemented in linear time if the partial minimum path tree graph is reused for each new connection we need.

For Test Set 1, we want to find exactly one folding segment such that when we fold the napkin across the segment, the regions on either side of the segment line up perfectly. Because the folding segment must split the napkin into two symmetric regions, we can show that each of the folding segment's endpoints either coincides with a vertex of the polygon defining the napkin, or is the midpoint of an edge of the polygon. If we tried to make a folding segment connecting any other points, the two parts of the split edge could not possibly line up perfectly. Thus, all we need to do is try every line segment connecting any pair of points that are vertices or midpoints of the polygon's edges. Then, for each potential folding segment, we check whether it is valid by making sure it is fully contained within the polygon and that the two regions it creates are symmetric across the folding line segment.

Checking for intersections between line segments can be done by using only integers. Reflecting points across a line or taking the midpoint of a side normally could produce points with non-integer coordinates. But we can scale up our points initially such that if the reflection were to produce a point with non-integer coordinates, it could not possibly be one of the valid endpoints for folding line segments. Of course, we can also choose to work with fractions.

With **N** points in our polygon, we have 2×**N**
points to choose from for our folding segment's endpoints. Each potential
folding segment can be checked in O(**N**) time. Because there are
O(**N**^{2}) possible segments to check, this results in an
O(**N**^{3}) overall time complexity.

Note that in order to check for symmetry across a folding segment, we cannot just check that the sets of vertices of the polygons defining each region are symmetrical. Rather, we must show that for every edge of the polygon of one region, there exists exactly one edge in the polygon defining the second region which is symmetric across the folding line segment. In other words, the order in which the points appear on each side matters.

Finally, we can note that if a given line is indeed an axis of symmetry of the polygon, then it is guaranteed that it doesn't intersect the polygon more than twice. This means that we don't need an explicit check in the code for the folding segment not to intersect the polygon outside its endpoints. A similar simplification can be applied to the solution of Test set 2, coming up next.

Since we want to draw a neat folding pattern of **K**-1 non-intersecting
line segments, we must partition our napkin into **K** regions of identical
size and shape, all of which are symmetric with other regions sharing common line
segments. Each of these **K** regions is a polygon with edges that are made up of folding
line segments and/or edges or parts of edges from the polygon defining the napkin. It can be
shown that at least two of these regions are only adjacent to one line segment
in our folding pattern, with the other edges that define the region's polygon
coming from the original polygon. Let's call these regions *corner regions*.

If we have a corner region, we can reflect that region across its one folding line segment to find the region that must be adjacent to it. If we keep reflecting these regions across the edges of their polygons, being careful not to create intersecting regions or leave the polygon defining the napkin, we can reconstruct the neat folding pattern. Thus, every neat folding pattern can be uniquely defined by just one folding line segment connecting two points on the border of the polygon defining the napkin. That segment cuts off a corner region which can be successively reflected to give us the entire folding pattern.

We need to consider pairs of points on the napkin's border defining a folding line segment.
For a given candidate folding line segment,
we can successively reflect the corner region we form to get the full
folding pattern. If we use more than **K**-1 reflections, or, if after we finish
reflecting we don't end up creating the original polygon, we know that the
chosen line segment does not give us a neat folding pattern.

Now all that remains is to select all pairs of points on the napkin's border.
Clearly we cannot test every pair of points with rational coordinates, because
there are infinitely many such points. Rather, we can show that the endpoints of the line
segments in our neat folding pattern must be either vertices or points on
the polygon's edges that are X/Y of the way between consecutive vertices, where
1 ≤ X ≤ Y-1 and 2 ≤ Y ≤ **K** (the proof for this is below).
Therefore, we can create all of
these candidate points and check every pair. With **K** ≤ 10 and
**N** ≤ 200, there are at most 6400 candidate points for the vertices of
the line segments in our neat folding pattern. This puts an upper bound of
6400^{2} on the number of pairs that we might need to check. But, we can reduce this
significantly by only considering pairs which create a corner region with an
area
equal to 1/**K** of the napkin's area. Every point can pair with at
most 2 other points to create a line segment which is fully within the polygon
and splits off a corner region with the proper area. Therefore, we only need
to check these pairs.

We can check if a single line segment from a pair of points gives us a valid
folding pattern in O(**N**) time if we are careful to stop once a
reflection creates a point which is not on the border of one of our polygon's
line segments. We can precompute all the valid points and use a
hash table for this
check. Because all of the points are of the form X/Y × p, where p is a point
with integer coordinates and Y is between 2 and **K**, we can multiply
everything by lcm(2, 3, ..., **K**) at the beginning and then work in integers,
dividing and simplifying fractions only for the output.

To summarize, the algorithm requires these steps:

- 1. Compute all possible endpoints. (O(
**N**×**K**^{2})) - 2. Find candidate segments to create a corner region. (O(
**N**×**K**^{2})). - 3. For each candidate, fold it up to
**K**-1 times, checking that everything is valid.

There are up to O(**N** × **K**^{2}) possible endpoints. If we fix one endpoint
P and iterate the other, we can compute the area as we advance, finding the up to 2 segments that
have an endpoint in P in O(**N** × **K**^{2}) time. So step 2 takes
O(**N**^{2} × **K**^{4}) time in total. For step 3, each unfolding
requires reflecting the current region and finding new folding segments. All of that is linear in
the size of the region, and the sum over the sizes of all regions is at most the total number
of endpoints plus 2 × **K** shared ones,
so this takes O(**N** × **K**^{2}) time overall. Putting it all
together, the algorithm takes O(**N**^{2} × **K**^{4}) time in total.
It is possible to make it significantly more efficient than that, but the implementation is
complicated enough as it is.

To prove that all folding segments endpoints are X/Y of the way between consecutive vertices for
1 ≤ X ≤ Y-1 and 2 ≤ Y ≤ **K**,
we can prove that the number of folding segments that are incident on a non-vertex point of the
input polygon is odd or zero. If that's true, let P be an endpoint and Q and R be the two vertices
and/or folding segment endpoints that are closest to P towards each side over the same polygon
edge E as P. Then, by reflection PQ and PR are equal. By repeating this over E we can see that
E is divided into equal length sections by every point that is a folding segment endpoint.

Now we prove that the number of incident folding segments in a non-vertex point of the polygon is
odd or zero. Assume that P is a point over an edge E of the polygon with
I > 1 of incident folding segments. Let Q_{i} for i = 1, 2, ..., I
be the non-P endpoints of each of those segments, in clockwise order. Let Q_{0} be the
reflection of Q_{2} across PQ_{1} and Q_{I+1} the reflection of
Q_{I-1} across PQ_{I}. Notice both those points have to be on E. Now, the I+1
angles Q_{i}Q_{i+1} for i = 0, 1, ..., I are all equal. Let R_{i} be the
reflection of Q_{i} across E. Now, because Q_{i} must reflect onto Q_{i+2},
the length of PQ_{0}, PQ_{2}, PQ_{4}, ..., PQ_{I} are all equal,
and equal to the lengths of PR_{2}, PR_{4}, ..., PR_{I}. Since the angles
between two consecutive segments of those are also all equal,
Q_{0}Q_{2}Q_{4}...Q_{I}R_{I}R_{I-2}...R_{2}
is a regular polygon. All points have rational coordinates because they
are either input points, endpoints of folding segments, or reflections calculated from other
points with rational coordinates. It is known that the only regular polygon whose vertices have
rational coordinates in 2 dimensions is the square, which means
I / 2 + 1 + I / 2 = 4, which implies I = 3 is odd.

The following picture illustrates the above proof for the case I = 4. P is the point in the center, and line segments of the same color are guaranteed to be of the same length.

A consequence of this proof is that for any non-vertex point on the original polygon, it must be adjacent to exactly 0, 1 or 3 folding line segments.