Alice, Bob, and Cindy are spending their summer abroad together! Not for a vacation though—they all found internship opportunities at a cluster of schools that are located conveniently close together. Thus, the three of them have decided to room together at a shared apartment for the duration of their stay.

They have been staying at this apartment for $$$n$$$ days so far. During each day, exactly one of Alice or Bob or Cindy is responsible for doing the cooking for that day. They don't particularly care about who handles cooking duty on each day, with whoever was in the mood for it usually being the one to take over. But their parents called and expressed their concern about whether the work was being split fairly.

Specifically, the parents want the following property to hold:

• There exists a sequence of three consecutive days such that Alice cooked on one day, Bob on another day, and Cindy on the remaining day (not necessarily in that order).

Find the minimum $$$k$$$ number of extra days of cooking duty needed in order for it to be possible for the parents' condition to be satisfied.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{The string $s$ contains only }\mathtt{A}\text{ or }\mathtt{B}\text{ or }\mathtt{C}\text{ characters.} \\ 1 \leq n \leq 2 \times 10^5 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & n \leq 3 \\ \hline 2 & \mathbf{20} & n \leq 6 \\ \hline 3 & \mathbf{20} & n \leq 500 \\ \hline 4 & \mathbf{20} & \text{There is no }\mathtt{C}\text{ character in $s$.} \\ \hline 5 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Here is a well-known trick question about Tagalog:

The answer is, of course, four, because in Tagalog, "ng" is considered to be a single "letter" (albeit written with two symbols)—that is, the letters are b-u-ng-a. So, for example, the word "pangngalan" has 8 letters.

Since Tagalog is so good, Alice wants to create a Tagalog 2. In Tagalog 2, she will choose two distinct consonants—let's write them as $$$xy$$$—such that this substring of two characters is counted as a single "letter" (each other character, as normal, counts as one letter). Given a string $$$s$$$, she must choose these consonants $$$x$$$ and $$$y$$$ such that the string $$$s$$$ is counted as having $$$k$$$ letters in Tagalog 2. If there are multiple possible answers, Alice wants the lexicographically smallest one (i.e. the one that would come earliest in the dictionary).

Please help Alice answer this question for all integers $$$k$$$ from $$$1$$$ to $$$|s|$$$ (the length of $$$s$$$). Good luck!

For the sake of this problem, y is always considered as a consonant.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{The string $s$ contains only lowercase letters.} \\ 1 \leq |s| \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & |s| \leq 5 \\ \hline 2 & \mathbf{30} & |s| \leq 500 \\ \hline 3 & \mathbf{30} & |s| \leq 5\times 10^4 \\ \hline \end{array}\\

\end{align*}$$$$$$

Here is a well-known joke among Jesuits:

A formation is an $$$r \times c$$$ grid with $$$m$$$ of its squares containing a soldier. The enemy can spend one cannonball to do the following:

• Select a row or column, and eliminate all soldiers in the chosen row or column.

You are given $$$r, c, m, k$$$. Construct any formation such that its resiliency is exactly equal to $$$k$$$ (or say if the task is impossible). Also, please answer $$$T$$$ different test cases per file.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 0 \leq T \leq 1500 \\ 1 \leq r, c \leq 25 \\ 1 \leq m \leq rc \\ 1 \leq k \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & m=k \\ \hline 2 & \mathbf{30} & m=2k \\ \hline 3 & \mathbf{20} & m=3 \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Cindy has been playing the new Pokemon game, and she's having a great time! Her team consists of five Dragon-type Pokemon (because she thinks they look awesome!), as well as her favorite Pokemon Magumaggu (the Lava Pokemon), the pre-evolution of Magcargo.

The latest entry in the Pokemon franchise contains several cooking minigames, where Cindy can prepare meals for her Pokemon to eat. In one cooking minigame, there are $$$n$$$ almonds, labeled $$$1$$$ to $$$n$$$, which her Magumaggu must roast. The $$$i$$$th almond must be roasted at least $$$a_i$$$ times. At the start of the minigame, the almonds are placed in a row in some random order. In one breath, Magumaggu can do the following:

• Choose a subsegment of $$$k$$$ consecutive chestnuts and hit them with its fire breath; all chestnuts in this range get roasted once.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq k \leq n \leq 2 \times 10^5 \\ \text{$1 \leq a_i \leq 10^9$ for each $i$.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & n \leq 5 \\ \hline 2 & \mathbf{40} & \text{$a_i \leq 2$ for each $i$} \\ \hline 3 & \mathbf{5} & \text{$a_i \leq 2023$ for each $i$} \\ \hline 4 & \mathbf{15} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

It is the end of the year 2023. Alice still shouts AMOGUS at the top of her lungs. She believes it to be the funniest joke ever created in all of human history. She has even purchased an inflatable Amogus costume, which she will treasure for years to come. Truly, Amogus is eternal.

The Earth's greatest scientists have designed a new mod of the game, which introduces an interesting twist to the mechanics. Alice has been hired as one of their playtesters, and her job is to determine whether or not this mod is actually fun.

• A lobby can contain an arbitrary number of players—let's call this number $$$n$$$.
• Exactly one player is (secretly) chosen to be the imposter.
• Another different player is (secretly) chosen to be the witness—the witness knows who the imposter is at the start of the game.
• Alice always chooses a special role called the detective; the detective is not a player.

• If the witness is present and the imposter is not, then the detective learns the identity of the imposter.
• If both the witness and the imposter are present, then nothing happens.
• In all other cases, nothing happens as well.

The judge first outputs a single integer $$$k$$$, the number of emergency meetings. For this problem, $$$k=18$$$ always.

Next, you should output a single integer $$$n$$$, the number of players you wish to invite to your lobby; this $$$n$$$ should be at least $$$2$$$ and at most $$$5 \times 10^4$$$. In general, the higher this $$$n$$$, the better your score will be. The players are indexed from $$$1$$$ to $$$n$$$.

The following interaction then plays out up to $$$k$$$ times:

• The detective calls an emergency meeting; you should tell the judge whom you want to invite to this meeting.
  • First, output a single positive integer $$$t$$$, the number of players called to the meeting.
  • Then, output $$$t$$$ distinct space-separated integers (each from $$$1$$$ to $$$n$$$), the indices of the players invited to the meeting.
• Then, the judge responds with the outcome of the meeting.
  • If the witness was invited to the meeting and the imposter was not, the judge responds with <W> REPORTS <I>, where <W> is the index of the witness, and <I> is the index of the killer. If this happens, your program was succesful, and then no further messages will be sent from the judge, so you should exit immediately.
  • In any other case, the judge responds with a line containing SILENCE... and you should proceed with the next emergency meeting.

In this problem, the judge is adaptive! Basically, the judge is designed so that it is impossible for your program to "get lucky" and succeed by sheer coincidence. The judge will always trigger the "unluckiest" worst case scenario for your algorithm, and will only Accept your solution if your algorithm works 100% of the time, no matter what. You may refer to the Notes section for a bit more detail.

If your solution is incorrect, you get $$$0$$$ points. If correct, you are awarded points based on the size of $$$n$$$ outputted in the successful attempt. $$$$$$\begin{align*}

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{35} & n \geq 18 \\ \hline 2 & \mathbf{15} & n \geq 30 \\ \hline 3 & \mathbf{10} & n \geq 80 \\ \hline 4 & \mathbf{26} & n \geq 500 \\ \hline 5 & \mathbf{6} & n \geq 700 \\ \hline 6 & \mathbf{8} & n \geq 48000 \\ \hline \end{array}\\

\end{align*}$$$$$$

For a Media Studies presentation on the history of telecommunication, Alice is going to use her skill in electronics to re-create the five-needle telegraph design. Unlike other communication systems, like the famous Morse telegraph system that succeeded it, the five-needle telegraph had the advantage of not requiring specialist training in order for its operators to send and receive messages.

Alice wants to create a generalized version, so we will actually describe the construction of an $$$n$$$-needle telegraph. Consider a square with $$$n$$$ rows and $$$n$$$ columns which has been rotated $$$45^\circ$$$, such that it now has $$$2n-1$$$ rows—so its first row contains $$$1$$$ entry, its second row contains $$$2$$$ entries, and so on, up until its $$$n$$$th row which contains $$$n$$$ entries; then, the $$$(n+1)$$$th row contains $$$n-1$$$ entries, the $$$(n+2)$$$th row contains $$$n-2$$$ entries, and so on, up until its final row has $$$1$$$ entry again.

The $$$n$$$th row contains a needle in each entry; each other square contains a single letter in each entry. You may refer to this diagram, taken from the Wikipedia page, for an $$$n$$$-needle telegraph with $$$n=5$$$.

Credits to user Dder

Each needle can be in one of $$$3$$$ states: it can be pointed vertically (its default state), it may be rotated $$$45^\circ$$$ counterclockwise (west of north), or it may be rotated $$$45^\circ$$$ clockwise (east of north). A valid message consists of choosing exactly two needles and rotating them in opposite directions (all other needles remain in the default state). The value of this message is equal to the letter that both rotated needles are pointing at. In the above diagram, the third needle has rotated $$$45^\circ$$$ clockwise, and the fifth needle has rotated $$$45^\circ$$$ counterclockwise, and so they point at the letter G

For this problem, you will be given the $$$n(n-1)$$$ letters on Alice's design of her telegraph, as well as $$$m$$$ needle configurations that correspond to valid messages. Please decode Alice's message!

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq n \leq 20 \\ 1 \leq m \leq 400 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{50} & n \leq 5 \\ \hline 2 & \mathbf{30} & \text{All needle configurations point to a letter in the top half.} \\ \hline 3 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

This is an interactive problem.

Cindy is playing a so-called "Kaizo" ROMHack of Pokémon Crystal, meaning that fans had modified the game to massively increase the difficulty to infuriating (unfair?) levels. For some modders, this can include not just the Pokémon battles, but also the overworld puzzles.

The Ghost Gym in Ecruteak city has a puzzle which goes as follows (slightly modified for simplicity).

• There is an $$$r \times c$$$ map that you must traverse. Your character starts at the top-left-most square, and must traverse to the bottom-right-most square.
• In one move, your character may take a single step north, south, east, or west.
• Each tile in the map is flagged as either SAFE or TRAP.
  • If you step on a TRAP tile, you are immediately teleported back to your starting position at the top-left corner!
  • If you exit the bounds of the grid, you are also immediately teleported back to your starting position.
  • It is guaranteed that the top-left-most and bottom-right-most squares are SAFE
• You do not know which tiles are safe, and which ones are trapped!

Of course, the "maze" in the base game is very simple, but the Kaizo modders have gone out of their way to make their maze as painful as possible. Cindy has been attempting this for hours and is starting to get tilted. She asks you if it's possible to develop a program that can solve this problem for her.

The judge first outputs two space-separated integers $$$r$$$ and $$$c$$$, the dimensions of the grid.

Then, you can now move around the grid. You can make statements to the judge:

• You can output one of N or S or E or W in order to move one step north, south, east, or west, respectively. The judge then responds with one of:
  • YAY if the tile you stepped on is the bottom-right corner.
    • You pass the test case!
    • The judge will send no further messages and your program should terminate.
  • SAFE if the tile you stepped on is SAFE (and not the destination); nothing more happens.
  • TRAP if the tile you stepped on is a TRAP, or if you exited the bounds of the grid; your character is immediately teleported back to the top-left corner before your next move.
• At any point, you can output RIGGED to declare that you think it's impossible to reach the bottom-right-most corner.
  • If you are correct, then you pass this test case.
  • If you are incorrect, then you get a Wrong Answer for this test case.
  • In either case, the judge will send no further messages and your program should terminate.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq r, c \leq 20 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{35} & r = c = 2 \\ \hline 2 & \mathbf{20} & r, c \leq 5 \\ \hline 3 & \mathbf{20} & \text{It is possible, and all }\mathtt{OKAY}\text{ squares lie on \\ the unique shortest path from start to finish.} \\ \hline 2 & \mathbf{25} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Puno ang langit ng bituin

At kay lamig pa ng hangin

Sa 'yong tingin ako'y nababaliw giliw

At sa awitin kong ito

Sana'y maibigan mo

Ibubuhos ko ang buong puso ko...

Tonight, Bob has decided that he is going to serenade Cindy with a traditional harana outside her bedroom. Let's ignore the fact that Cindy lives on the 12th floor of a condo—he'll figure out the logistics later. For now, he needs to focus on his singing!

We can massively simplify and describe each note as a single integer, and so describe a song as a sequence of integers (Chord her? I barely know her!) Bob's song consists of the $$$n$$$ notes $$$s_1, s_2, \dots, s_n$$$, and by his practice, the best he can do is sing the notes $$$b_1, b_2, \dots, b_n$$$.

The off-key-ness of his singing is calculated as the sum of the absolute difference between each of his notes and the corresponding note in the song. In symbols: $$$$$$ \text{off-key-ness} = \sum_{i=1}^n |b_i - s_i|. $$$$$$ Bob has a sneaky trick he can do. Instead of fixing his singing, he can just change the key of the backing music! Right now, it is in key $$$0$$$. If a part is to be sung in key $$$k$$$, we add $$$k$$$ to the $$$s_i$$$ of all notes in that part (this $$$k$$$ can be negative, but it must be an integer).

Also, Bob wants to do a key shift at some note $$$m$$$, meaning he will sing notes $$$1$$$ to $$$m$$$ in key $$$k_1$$$, and then sing notes $$$m+1$$$ to $$$n$$$ in key $$$k_2$$$. Note that it is allowed to have $$$k_1 = k_2$$$, if you determine that it would be optimal.

For each $$$m$$$ from $$$1$$$ to $$$n-1$$$: Determine the minimum off-key-ness of Bob's singing if the key shift happens at note $$$m$$$, and the two keys ($$$k_1$$$ and $$$k_2$$$) are chosen optimally.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq n \leq 2 \times 10^5 \\ -10^9 \leq s_i, b_i \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{50} & \text{$0 \leq s_i, b_i \lt 8$ and $n \leq 1000$} \\ \hline 2 & \mathbf{20} & 0 \leq s_i, b_i \lt 8 \\ \hline 3 & \mathbf{20} & n \leq 1000 \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Alice, Bob, and Cindy are having a blast playing the hot new game Injurious Company, an indie horror survival game where players assume the role of underpaid laborers who must persevere through ludicrously unsafe working conditions just to earn scraps for their day's wage (maybe the real horror is capitalism).

The gang are located at position $$$(x, y)$$$ (using the usual Cartesian coordinate system) and must return back to their ship, located at the origin $$$(0, 0)$$$. But they have to move strategically in order to dodge the monsters that are coming after them! The strategy guide describes a winning strategy according to $$$n$$$ pieces of information, each described by an integer $$$K_i$$$ and a direction $$$dir_i$$$ (each of which is H or V). This means that on their $$$i$$$th move they choose a direction $$$d_i$$$ and a number of steps $$$k_i$$$—then, they head $$$k_i$$$ steps in the direction of $$$d_i$$$. Their choice is subject to the following restrictions:

• $$$1 \leq k_i \leq K_i$$$
• If $$$dir_i$$$ is H, then $$$d_i$$$ must be E or W, for east or west, respectively.
• If $$$dir_i$$$ is V, then $$$d_i$$$ must be N or S, for north or south, respectively.

Determine if it is possible for them to return to their ship alive, and if so, provide a series of moves that they can take. Also, please answer $$$T$$$ different test cases per file.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \\ 1 \leq n \\ \text{The sum of $n$ across all test cases is $\leq 2 \times 10^5$.} \\ |x|, |y| \leq 10^{15} \\ \text{$1 \leq K_i \leq 10^9$ for each $i$} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & n \leq 2 \\ \hline 2 & \mathbf{20} & n \leq 3 \\ \hline 3 & \mathbf{20} & \text{$n \leq 15$ and $T \leq 50$} \\ \hline 4 & \mathbf{30} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Alice noticed this trend in some contest problems where they add "flavor" to a pure mathematical statement by introducing some formal abstract arbitrary property and then binding it to an adjective that has absolutely nothing to do with that definition. These problems are usually then titled "adjective + mathematical object". For example, "beautiful numbers", "interesting sequences", and the classic "good colorings". As an aspiring problem setter, Alice wishes to partake in this tradition.

A $$$k$$$-jolly divisor of $$$n$$$ is some positive integer $$$d$$$ such that $$$n$$$ is divisible by $$$d$$$ and by $$$d^k$$$. For example, $$$4$$$ is a $$$3$$$-jolly divisor of $$$960$$$, since both $$$4$$$ and $$$4^3 = 64$$$ divide $$$960$$$. We can show that $$$4$$$ is the largest $$$3$$$-jolly divisor of $$$960$$$.

Given $$$N$$$ and $$$k$$$, find the sum of the largest $$$k$$$-jolly divisors of $$$n$$$ across all $$$n$$$ from $$$1$$$ to $$$N$$$.

Python users are advised to submit to PyPy for this problem.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq k \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & 1 \leq n \leq 10^3 \\ \hline 2 & \mathbf{30} & 1 \leq n \leq 10^5 \\ \hline 3 & \mathbf{30} & 1 \leq n \leq 10^6 \\ \hline 4 & \mathbf{10} & 1 \leq n \leq 5 \times 10^7 \\ \hline \end{array}\\

\end{align*}$$$$$$

Cindy is helping her dojo with the logistics of their upcoming promotion exam.

There is a queue of $$$n$$$ students, each ready to take the exam. Cindy will then hire $$$k$$$ instructors as the ones who will administer the promotion exam. The $$$i$$$th person from the front of the queue takes $$$a_i$$$ seconds to complete their test (pass or fail) under an instructor, and each instructor can only administer the test to one student at a time.

The process is as follows. The person in front of the queue looks around for any free instructors; if they see one, they go up to that instructor and start their test with them. If there are many that are free, one is chosen arbitrarily (the time spent walking to each instructor is negligible). If no instructor is free, the student at the front of the queue (and thus, everyone else behind them) waits until one is free.

Is it possible to finish all tests in at most $$$T$$$ seconds? If yes, what is the smallest $$$k$$$ (the number of instructors to hire) needed in order to achieve this goal? Also, please answer $$$t$$$ different test cases per file.

Here, $$$N$$$ denotes the sum of $$$n$$$s in a single test file.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \le t \le 500 \\ 1 \leq n \\ 1 \leq T, a_i \leq 10^{16} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & \text{$n \leq 3$, $N \leq 1500$} \\ \hline 2 & \mathbf{15} & \text{$n \leq 75$, $N \leq 1500$} \\ \hline 3 & \mathbf{20} & \text{$n \leq 500$, $N \leq 2000$} \\ \hline 4 & \mathbf{20} & \text{$n \leq 2000$, $N \leq 6000$} \\ \hline 5 & \mathbf{20} & \text{$n \leq 150000$, $N \leq 450000$} \\ \hline \end{array}\\

\end{align*}$$$$$$

Fingers on buzzers teams, it's time for the Missing Vowels Round. In this game, we've taken famous words, phrases, or sayings, removed the vowels, and then re-spaced the consonants.

So for example, for the category "Sports for nerds," the clue might be,

Alice, Bob, and Cindy are training for their appearance on Only Connect (their team name is "The Github Heatmappers"), and in particular they would like to train for the Missing Vowels Round. They ask for your help in creating a program that allows them to train.

As a formalization of the rules given above, in the Missing Vowels Round, the following transformation is applied to a string:

• First, remove all characters that aren't consonants, but preserve the order of these consonants.
  • Y is always considered a consonant for this problem
• Capitalize all these consonants
• You may insert spaces anywhere in the remaining letters, so long as when you're done...
  • The phrase does not begin or end in a space.
  • There are no two consecutive spaces anywhere

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq i \leq 10^{18} \\ 1 \leq |s| \leq 2 \times 10^5 \\ \text{$s$ consists of upper and lowercase letters, punctuation }\mathtt{,.!?}\text{ and spaces.} \\ \text{$s$ does not begin or end in a space, and it has no two consecutive spaces.} \\ \text{$s$ contains at least one consonant.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & |s| \leq 15 \\ \hline 2 & \mathbf{40} & i \leq 2 \times 10^5 \\ \hline 3 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

The motivating story and definition of a rectilinear path (and related terms) are the same in Mondridalgo (Verification) and (Optimization). Skip to the bolded text for the first section where the two differ.

Bob created a magnificent painting this year in the Mondridalgo style (a combination of Piet Mondrian's rectangles and Felix Hidalgo's neoclassicism), which both Alice and Cindy adore. Unfortunately, when Cindy asked him if she could keep the painting, he was too lovestruck and immediately said yes... forgetting that he had already previously promised the painting to Alice! Oh no! Remember everyone—don't be like Bob.

Unable to choose between his two friends, Bob decides the best way to resolve this situation is to cut up his painting into two contiguous pieces using a pair of scissors, and then hand one piece to Alice and the other Cindy. That way, each of his friends is equally unhappy.

We formalize "cutting with scissors" by defining a rectilinear path to be a non-empty sequence of "cuts" such that:

• Each cut is represented by a directed line segment, indicating the motion of cutting.
• The first cut starts somewhere along the border of the painting, and moves perpendicular to the border.
• Each next cut in the sequence begins where the previous one ended, and is oriented perpendicular to the previous cut.
• The final cut should end anywhere along the border.

• All cuts are made along the gridlines, and with the exception of the start of the first cut and the end of the last cut, the path must stay entirely within the rectangle at all times.
• Any two non-consecutive cuts should not intersect anywhere, not even at a point.

Let $$$A$$$ be the sum of $$$rc$$$ across all test files.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 100 \\ 2 \leq r, c \leq 400 \\ A \le 10^6 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{$r = c = 2$} \\ && \text{$T \le 16$} \\ \hline 2 & \mathbf{20} & \text{$r = 2$} \\ && \text{$c \leq 50$} \\ \hline 3 & \mathbf{20} & \text{$r \leq 3$} \\ && \text{$c \leq 50$} \\ \hline 4 & \mathbf{30} & \text{$r, c \leq 50$} \\ && \text{$A \le 20000$} \\ \hline 5 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

The motivating story and definition of a rectilinear path (and related terms) are the same in Mondridalgo (Verification) and (Optimization). Skip to the bolded text for the first section where the two differ.

Bob created a magnificent painting this year in the Mondridalgo style (a combination of Piet Mondrian's rectangles and Felix Hidalgo's neoclassicism), which both Alice and Cindy adore. Unfortunately, when Cindy asked him if she could keep the painting, he was too lovestruck and immediately said yes... forgetting that he had already previously promised the painting to Alice! Oh no! Remember everyone—don't be like Bob.

Unable to choose between his two friends, Bob decides the best way to resolve this situation is to cut up his painting into two contiguous pieces using a pair of scissors, and then hand one piece to Alice and the other Cindy. That way, each of his friends is equally unhappy.

We formalize "cutting with scissors" by defining a rectilinear path to be a non-empty sequence of "cuts" such that:

• Each cut is represented by a directed line segment, indicating the motion of cutting.
• The first cut starts somewhere along the border of the painting, and moves perpendicular to the border.
• Each next cut in the sequence begins where the previous one ended, and is oriented perpendicular to the previous cut.
• The final cut should end anywhere along the border.

• All cuts are made along the gridlines, and with the exception of the start of the first cut and the end of the last cut, the path must stay entirely within the rectangle at all times.
• Any two non-consecutive cuts should not intersect anywhere, not even at a point.

Our goal is to try to find a partition which is not "lop-sided"—that is, neither one of Alice nor Cindy should be significantly happier than the other in this interaction. This partition also shouldn't be too complicated.

Formally, given an integer $$$k$$$, find any partition whose valid rectilinear path uses at least $$$1$$$ and at most $$$k$$$ cuts, and which minimizes the value $$$|\text{Alice's happiness} - \text{Cindy's happiness}|$$$ among such partitions.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq r, c \leq 6 \\ 1 \leq k \leq 6 \\ \text{$-10^9 \leq u_{i, j}, v_{i, j} \leq 10^9$ for each $i, j$} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & k=1 \\ \hline 2 & \mathbf{30} & k \leq 2 \\ \hline 3 & \mathbf{20} & r, c \leq 3 \\ \hline 4 & \mathbf{20} & r, c \leq 4 \\ \hline 5 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Alice, Bob, and Cindy are learning networking in the computer club! Each of them started with five computers; each computer has a unique name to identify it. Cables can be used to directly connect two different computers; each cable is two-way. A collection of computers and cables is called a network. Their networks are originally configured in the following shapes (for privacy reasons, we've hidden the computers' names).

• Acquire a new computer (say its name is $$$x$$$)
• Discard the cable connecting $$$u$$$ and $$$v$$$, then add two new cables connecting $$$u$$$ and $$$x$$$, and $$$x$$$ and $$$v$$$.

They decide to give you a little puzzle. They'll give you the setup of a computer network. Whose is it! The answer could be even "none of them", and you also need to be able to identify if this is the case. Also, please answer $$$T$$$ different test cases per file.

Here, $$$N$$$ denotes the sum of $$$n$$$s in a single test file, and $$$M$$$ the sum of $$$m$$$s in a single test file.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 0 \leq T \\ 1 \leq n \leq 2 \times 10^5 \\ N \leq 2 \times 10^5 \\ 0 \leq m \leq 2 \times 10^5 \\ M \leq 2 \times 10^5 \\ \text{Each computer's name is distinct, and consists} \\ \text{of at most $5$ upper and lowercase letters.} \\ \text{No cable connects a computer to itself.} \\ \text{At most one cable connects any pair of computers.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{Someone owns each network.} \\ \hline 2 & \mathbf{20} & \text{Neither Alice nor Bob own each network.} \\ \hline 3 & \mathbf{20} & \text{Neither Alice nor Cindy own each network.} \\ \hline 4 & \mathbf{20} & \text{Neither Bob nor Cindy own each network.} \\ \hline 5 & \mathbf{20} & \text{No further constraints} \\ \hline \end{array}\\

\end{align*}$$$$$$