squawk squawk chirp quack chirp chirp squak [sic] Credits to Ephraim Wu for the photograph, and to Kris Darilay for the accompanying message

Have you heard the good news? Alice, Bob, and Cindy have a new friend, Penchick! Penchick has been helping them (and many students in NOI.PH) learn competitive programming, providing sage wisdom and moral support throughout their journeys. This shall be known as A Penchick's Tale (APT).

It is well known that Penchick can only say one of three things, and for each thing Penchick can say, one of Alice or Bob or Cindy becomes happy!

• When Penchick says squawk, Alice's happiness increases by $$$a$$$.
• When Penchick says chirp, Bob's happiness increases by $$$b$$$.
• When Penchick says quack, Cindy's happiness increases by $$$c$$$.

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq |s| \leq 10^5 \\ \text{$s$ consists only of lowercase English letters} \\ 1 \leq a, b, c \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{50} & |s| \leq 10 \\ \hline 2 & \mathbf{20} & \text{$a = b = c = 1$,} \\ && \text{or the answer is }\mathtt{penchickdead}\text{} \\ \hline 3 & \mathbf{20} & \text{$a = 6$ and $b = c = 5$,} \\ && \text{or the answer is }\mathtt{penchickdead}\text{} \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

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

Bob is playing one of his favorite board games, Tiny Towns! Let's look at a simplified version of it.

All gameplay takes place on a grid with $$$r$$$ rows and $$$c$$$ columns. Each cell in this grid can either be empty, or can contain a fountain.

A fountain is considered active if and only if it satisfies the following condition:

• It is adjacent to another fountain (i.e. the cell it's in shares an edge—not just a corner—with another cell that also has a fountain).

Bob gets $$$2$$$ points for every active fountain on his board. If he can place one more fountain on the board, and he does so at the optimal spot, what is the maximum score Bob can get?

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{There is at least one empty cell.} \\ 1 \leq r, c \\ rc \leq 160000 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{34} & rc \leq 50 \\ \hline 2 & \mathbf{33} & rc \leq 1600 \\ \hline 3 & \mathbf{33} & \text{No further constraints.} \\ \hline \end{array}\\

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

For her social studies project, Cindy is doing extensive research into the Three Kingdoms period of Chinese History. Her primary sources are works of media centered on legendary Shu tactician Zhuge Liang (courtesy name Kongming)—these range from speculative fiction of how a strategist of Kongming's caliber would fare in cutthroat industries of the modern day, as well as rigorous combat simulations that highlight Zhuge Liang's own personal combat prowess and ability to decimate hundreds of enemies en masse using magic.

Through her research, she encountered this quite interesting excerpt:

I asked my army to divide themselves into squadrons such that each squadron contained the same number of soldiers. I know that they will do this task to the best of their ability, forming as many groups of that size as possible, as much as possible. However, depending on the squadron size I choose, it may be possible that despite their efforts, there may be soldiers left over who are unable to form a complete squadron.

I asked them to divide themselves into squadrons of size $$$a_1$$$, but this unfortunately resulted in $$$k$$$ people left over.

I asked them to divide themselves into squadrons of size $$$a_2$$$, but this unfortunately resulted in $$$k$$$ people left over.

I asked them to divide themselves into squadrons of size $$$a_3$$$, but this unfortunately resulted in $$$k$$$ people left over.

...and so on. I did this $$$n$$$ times—asking them to form as many squadrons as possible of sizes $$$a_1$$$, then $$$a_2$$$, ..., then $$$a_n$$$—but every single time, there were exactly $$$k$$$ people left over and unable to form a complete squadron. What a coincidence!

Cindy found, through another source, that the number of soldiers in Zhuge Liang's army was between $$$\ell$$$ and $$$r$$$, inclusive. Given this information, how many soldiers were in Zhuge Liang's army?

If there are multiple possible answers, output any of them. If there are no possible answers (meaning the historical sources are inaccurate), you must say so as well.

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 10^5 \\ 1 \leq \ell \leq r \leq 10^{10} \\ 1 \leq k \leq 10^9 \\ \text{$2 \leq a_i \leq 10^{10}$ for all $i$} \\ \text{$a_i \neq a_j$ if $i \neq j$} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & r - \ell \leq 10 \\ \hline 2 & \mathbf{20} & n = 1 \\ \hline 3 & \mathbf{20} & \text{$a_i$ is prime, for all $i$} \\ \hline 4 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

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

Earlier in this year, Bob was incredibly bullish on deer stocks, going all-in on the bet that it would be the beloved meme animal of 2024. Unfortunately for him, local markets can behave differently from international ones, and everyone else at his school is obsessed with penchicks instead, causing the value of his deer stonks to nosedive dramatically.

Still, Bob is contractually obligated to preside over his school's "Deer Club" until the end of the school year.

Deer Club consists of $$$n$$$ deer, and $$$m$$$ caretakers. The job of the caretaker is to pamper each deer for some amount of time.

The $$$i$$$th deer wants to be taken care of for $$$x_i$$$ units of time, straight. It also has a deerness value of $$$d_i$$$.

The $$$j$$$th caretaker will work for $$$y_j$$$ units of time, straight. Each one also has a care value of $$$c_j$$$.

When a deer is being taken care of, it will not leave until its $$$x_i$$$ units of time are up, after which it leaves and does not return. When a caretaker starts their shift, they will not leave until their $$$y_j$$$ units of time are done, and then they will not take another shift after that.

Only one deer can be taken care of at a time, and also only one caretaker can work at a time. Thankfully, $$$\sum x_i = \sum y_j$$$, so all you have to do is schedule an order for the deer to arrive, and also an order for the caretakers to work their shifts.

The happiness of the club at time $$$t$$$ is equal to the product of the deerness value of the deer currently being cared for, and the care value of the caretaker currently working. The overall happiness of Deer Club is equal to the sum of its happiness over all times $$$t=1, 2, 3, \dots$$$ until the end of the final shift.

For example, suppose we have $$$n=3$$$ deer and $$$m=2$$$ caretakers, and we have $$$x = [1, 3, 2]$$$ and $$$d=[3, 4, 1]$$$ and $$$y = [2, 4]$$$ and $$$c = [7, 2]$$$. Note that $$$1 + 3 + 2 = 2 + 4 = 6$$$, so the day lasts for $$$6$$$ units of time. Suppose we schedule the deer and caretakers to arrive in that order, then the scenario would look like this:

The overall happiness of Deer Club would be computed over the $$$6$$$ intervals of time, whose happiness values are: $$$3 \times 7$$$ and $$$4 \times 7$$$ and $$$4 \times 2$$$ and $$$4 \times 2$$$ and $$$1 \times 2$$$ and $$$1 \times 2$$$. This yields a sum of $$$69$$$.

However, if Bob cared more, he could choose a better schedule that makes the happiness even higher. If he wanted to be more spiteful, he could also find a worse schedule that makes the happiness even smaller.

What are the maximum and minimum possible total happinesses of Deer Club, across all possible schedules that Bob could pick?

Let $$$N$$$ and $$$M$$$ be the sum of $$$n$$$ and $$$m$$$ (respectively) across all test cases.

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 1000 \\ 1 \leq n, m \\ N, M \leq 10^5 \\ \text{$1 \leq x_i \leq 10^6$ for all $i$} \\ \text{$1 \leq d_i \leq 10^6$ for all $i$} \\ \text{$1 \leq y_j \leq 10^6$ for all $j$} \\ \text{$1 \leq c_j \leq 10^6$ for all $j$} \\ \text{$\sum x_i = \sum y_i$ in each test case} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{51} & \text{$n, m \leq 4$} \\ && \text{$\sum x_i \leq 10$ in each test case} \\ \hline 2 & \mathbf{17} & n, m \leq 4 \\ \hline 3 & \mathbf{16} & n, m \leq 1000 \\ \hline 4 & \mathbf{16} & \text{No further constraints.} \\ \hline \end{array}\\

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

Credits to Saji Tan

For their English class, Alice, Bob, and Cindy must recreate a scene from one of their favorite movies—and if possible (if they have the audacity to), they must attempt to improve upon it in some way. Our friends decided to re-enact the climax of one of their favorite movies of all time, Bad Genius.

Bad Genius is a Thai heist-thriller film... where the "heists" being pulled off are elaborate cheating methods on academic exams! The movie features striking social commentary about the pressure put on students by the school system, but that aside, the "heist scenes" themselves are well-crafted in both idea and execution. We highly recommend it.

For their project, Alice and Bob and Cindy are going to "improve" the climax of the film by fleshing out the details of the plan, providing rigorous justification that shows that the final heist is actually mathematically possible! This is a hypothetical scenario only, and NOI.PH does not endorse actual cheating in any shape or form.

Alice will fly to Sydney to take the Big-Ahh Internal Test (BAIT) early relative to her home country (due to how timezones work). The test consists of $$$100$$$ True or False questions. Alice is a (bad) genius, and she knows the answers to all $$$100$$$ questions the moment she sees them.

Back in their home country, Bob and Cindy are selling custom-made pencils that will help their customers cheat. Each pencil will contain a $$$16$$$-digit code (this code is always in decimal, so its characters are among the digits 0123456789—it may contain leading zeros). Unbeknownst to the test proctors, this $$$16$$$-digit code actually contains the answers (or some of the answers) to the BAIT—or at least, it does if you know how to decipher it.

After taking the exam, Alice—knowing all the answers—phones her friends and tells them what digits should be printed on each pencil. The cheaters do not know the actual $$$16$$$-digit code in advance, until they receive their pencils on the day of the exam—however, there was ample time beforehand for them to have been briefed on the proper decoding scheme for how to extract the answers from it.

These customers will pay more if you can guarantee them a higher score. Configure your scheme to try and guarantee as high a score as possible, across $$$10000$$$ possible answer keys.

Implementation Details

This is an IOI-style problem which may only be solved in Python or C++.

If coding in C++, please implement the following three functions:

void init();

string encode(string answer_key);

string decode(string code);

If coding in Python, please implement the following three functions:

def init():
    ...

def encode(answer_key: str) -> str:
    ...

def decode(code: str) -> str:
    ...

You may use the code templates linked here. These functions should have the following behavior:

• encode accepts an answer key, which is a string of length $$$100$$$, where each of its characters is T (for True) or F (for False). It should then return a string containing exactly $$$16$$$ digits—these are what should be printed on the pencils, if this is the answer key. The digits are among 0123456789 and the code may have leading zeros.
• decode accepts a code, which is a string of exactly $$$16$$$ digits. It should then return an answer sheet, which is a string of length $$$100$$$, where each of its characters is T or F—this is how a cheating student should answer the BAIT if they see this code on their pencil.
• Your goal is to create encode and decode functions such that decode(encode(answer_key)) matches answer_key in as many places as possible.

There will be $$$10000$$$ different answer keys—some were randomly generated, while others were specifically handcrafted. The grade of your program on some test case is equal to the number of items it got correct. Formally, let answer_sheet := decode(encode(answer_key)); then, your grade is equal to the number of indices $$$i$$$ such that answer_key[i] == answer_sheet[i]. Your overall grade is equal to the minimum grade across all test cases.

If your program crashes, or if the return value of encode or decode is invalid, then you get a grade of $$$0$$$.

Some technical details: Your program will be run two separate times. In the first execution, init() is called, and then encode(answer_key) will be called on all $$$10000$$$ answer keys. In the second execution, init() is called, and then decode(code) will be called on all codes produced by the first run, in a randomized order.

Because these are totally separate executions, no information can be sent from encode to decode, other than the parameter code passed into it as argument.

Let $$$g$$$ be your overall grade. If $$$g=0$$$, you will get $$$0$$$ points. Otherwise, the number of points you get is $$$$$$3 + e^{g/19}$$$$$$ capped at a maximum of $$$100$$$ points.

Consider this classic riddle. There are $$$n$$$ coins (labeled $$$1$$$ to $$$n$$$), and exactly one among them is fake. All real coins weigh $$$2$$$ grams, whereas the fake coin weighs $$$1$$$ gram. Then, $$$q$$$ times, you may do the following: Choose any subset of the coins and put them in a weighing scale, giving you the total mass of this selection of coins (in grams).

You know how to solve this problem right? Of course you do. Unfortunately, Bob doesn't, and he may have squandered all his guesses.

After using the weighing scale $$$q$$$ times, he called in Alice for help, who was made aware of all the queries that Bob made (and the respective responses to each one). Once she was done processing all this information: one-by-one, Bob pointed at each coin on the table and asked her, "Is this coin the fake one?" For each of these, Alice (who is honest and a perfect logician) answered one of: Yes, No, or Maybe. In the end, how many times did Alice end up saying each of these responses?

It is guaranteed that all values given by the weighing scales are correct, and corresponds to a valid sequence of responses in the scenario posed by the original riddle.

Let $$$K$$$ be the sum of $$$k_i$$$ across all queries.

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 10^9 \\ 1 \leq K \leq 2\cdot 10^5 \\ \text{$1 \leq k_i \leq n$ in each query} \\ \text{The chosen coins are distinct, in each query.} \\ \text{The responses are guaranteed to all be correct.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{$k_i = 1$ in each query} \\ \hline 2 & \mathbf{30} & n, K \leq 2000 \\ \hline 3 & \mathbf{20} & n \leq 2 \cdot 10^5 \\ \hline 4 & \mathbf{30} & \text{No further constraints.} \\ \hline \end{array}\\

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

Alice and Bob are playing the co-op video game Glacier Adventure from UFD 50, a compilation of retro-inspired edutainment games! Alice and Bob control a shared character, Penchick, and they need to help Penchick scale an ice shelf. The twist of the game is that the actions available to each player (to control Penchick) are different.

The ice shelf extends infinitely to the east and to the north, and is subdivided into rows and columns. The ice shelf does have a south-west-most corner, which we denote by $$$(1, 1)$$$. In general, let the cell in the $$$x'$$$th column from the left and $$$y'$$$th row from the bottom be denoted by $$$(x', y')$$$.

Penchick's current coordinates shall be denoted by the value $$$(x, y)$$$, and its initial value is $$$(x_s, y_s)$$$. Consider the set of all cells that Penchick can reach from its current position by only going west and south—the size of this set is called Penchick's score, and the objective of the game is to maximize this score.

For example, in the following position, Penchick's initial coordinates have $$$x_s = 6$$$ and $$$y_s=3$$$, and Penchick's score is $$$18$$$. If Penchick moves $$$1$$$ step east and $$$2$$$ steps north, Penchick's position updates from $$$(x, y) = (6, 3)$$$ into $$$(x, y) = (7, 5)$$$, and the score improves to $$$35$$$.

Credits to Aldrich Asuncion

Alice can move penchick using Action Cards. There are $$$n$$$ cards, labeled $$$1$$$ to $$$n$$$. When Alice uses card $$$i$$$, Penchick moves $$$+x_i$$$ steps east and $$$+y_i$$$ steps north. However, each card can only be used at most once, and also only at most $$$p$$$ of these cards can be used overall.

Bob, on the other hand, has three different special abilities to choose from.

• Balance, which simultaneously sets Penchick's $$$x$$$ and $$$y$$$ coordinates to their average ($$$x$$$ rounded up, $$$y$$$ rounded down). Precisely, it simultaneously assigns $$$x = \left\lceil \dfrac{x + y}{2} \right\rceil$$$ and $$$y = \left\lfloor \dfrac{x + y}{2} \right\rfloor$$$.
  • Bob can use this skill up to $$$100$$$ times.
• Climb, which moves Penchick $$$c$$$ steps west and $$$c$$$ steps north (where $$$c$$$ is a given fixed constant).
  • Bob can use this skill up to $$$5$$$ times.
• Dive, which moves Penchick $$$d$$$ steps east and $$$d$$$ steps south (where $$$d$$$ is a given fixed constant).
  • Bob can use this skill up to $$$42$$$ times.

Alice and Bob can collaborate, and can perform any sequence of actions, in any order. What is the maximum possible value of Penchick's score that can be attained?

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 100 \\ 1 \leq x_s, y_s, c, d \leq 10^6 \\ 1 \leq p \leq n \le 3000 \\ \text{$1 \leq x_i, y_i \leq 10^6$ for all $i$} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{60} & \text{$n \leq 6$} \\ && \text{$x_s, y_s, c, d \leq 5$} \\ && \text{$x_i, y_i \leq 5$ for all $i$} \\ \hline 2 & \mathbf{15} & n \leq 6 \\ \hline 3 & \mathbf{10} & n \leq 80 \\ \hline 4 & \mathbf{10} & n \leq 300 \\ \hline 5 & \mathbf{5} & \text{No further constraints.} \\ \hline \end{array}\\

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

Welcome one, welcome all, to the Great Penchick Race!

Alice, Bob, and Cindy have started racing their respective penchicks in a three-way parkour race battle. Alice's penchick has already traversed a distance of $$$a$$$ units, Bob's penchick has already traversed a distance of $$$b$$$ units, and Cindy's penchick has already traversed a distance of $$$c$$$ units.

The way the penchicks move is a bit quirky, actually.

• At the start of each round, one of the contestants chooses a positive integer $$$k$$$.
• First, one of the penchicks hops and moves forward by $$$k$$$ units.
• Then, a different penchick skips and moves forward by $$$2k$$$ units.
• Finally, the remaining penchick jumps and moves forward by $$$3k$$$ units.

Thus, Alice and Bob and Cindy agreed to collude such that all three of their penchicks will be equally distant from the starting line, and then end the race there. They can choose the integer $$$k$$$ each round, and also they can decide whose penchicks hop, skip, and jump.

Determine if this task is possible, and if it is, try to achieve it in as few rounds as possible.

There will be exactly one file with $$$T = 10^4$$$ test cases, with $$$1 \leq a, b, c \leq 10^9$$$ in each one; also, it is not the case that $$$a = b = c$$$. If your answer is incorrect on any of the test cases (said yes when it's impossible; said no when it is possible; used too many rounds; proposed a construction doesn't achieve the goal; etc.), you get a $$$0$$$.

Otherwise, you get a higher score the fewer rounds you use (in the cases where the task is possible), with a perfect score if you use the minimal number of rounds in all (possible) test cases.

Let $$$n$$$ be the number of rounds you used in some test case, and let $$$m$$$ be the number of rounds used by the judge.

• If your solution is correct, you get $$$50$$$ points
• But if $$$n \leq 2m$$$ in all (possible) test cases (i.e. you never use more than twice the optimal number of rounds, for any test case), you get $$$75$$$ points instead.
• But if $$$n=m$$$ in all (possible) test cases (i.e. always optimal), you get $$$100$$$ points.

The sample test file is also included (with $$$T=2$$$) but you do not actually need to get it correct in order to get points.

The RXA cryptosystem is the same in both problems. Skip to paragraph beginning with "Cindy" for the difference between the two problems.

Alice and Bob were attending a cryptography seminar in the province of Siquijor, where they learned about the famous RSA cryptosystem used for public-key encryption. Inspired by this, they decided to create their own cryptosystem which they called RXA.

Suppose Alice wants to send Bob a secret message $$$M$$$, which is a string. They have developed the following three-pass protocol.

First, Alice encodes the string $$$M$$$ into a (possibly very large) integer $$$m$$$ (by a process described below). Now, she communicates this integer $$$m$$$ to Bob by the following procedure.

Let $$$a \oplus b$$$ denote the bitwise XOR of two non-negative integers $$$a$$$ and $$$b$$$ (see Notes for an explanation).

• Alice generates a secret non-negative integer $$$a$$$, then sends to Bob the value $$$x := a \oplus m$$$.
• Bob also generates a secret non-negative integer $$$b$$$, and sends back to Alice the value $$$y := b \oplus x$$$.
• Alice then sends back to Bob the value $$$z := a \oplus y$$$.

Note that the only values that can be heard by the public are $$$x$$$, $$$y$$$, and $$$z$$$. The secret integers $$$a$$$ and $$$b$$$ are not revealed by Alice and Bob, not even to each other.

Cindy calls them both idiots, because this cryptographic scheme has a fatal flaw. The message $$$M$$$ can actually be retrieved by a malicious third party! Let's prove it. Given $$$n$$$ (the length of the message), and $$$x$$$, $$$y$$$, and $$$z$$$ (the values broadcasted to the public), see if you can recover the secret message $$$M$$$ that Alice wanted to secretly share to Bob.

The encopding process from $$$M$$$ to $$$m$$$ is as follows. Replace each character of $$$M$$$ with a $$$5$$$-bit string as follows:

• a becomes 00000
• b becomes 00001
• c becomes 00010
• d becomes 00011
• e becomes 00100
• f becomes 00101
• $$$\vdots$$$
• y becomes 11000
• z becomes 11001
• _ becomes 11010
• . becomes 11011
• ? becomes 11100
• ! becomes 11101
• - becomes 11110
• , becomes 11111

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 10^4 \\ 1 \leq |M| \leq 25 \\ 0 \leq x, y, z \lt 32^{|M|} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{75} & |M| \le 6 \\ \hline 2 & \mathbf{20} & |M| \leq 12 \\ \hline 3 & \mathbf{5} & \text{No further constraints.} \\ \hline \end{array}\\

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

Note that $$$x$$$, $$$y$$$, and $$$z$$$ can be quite large... beware integer overflow.

The RXA cryptosystem is the same in both problems. Skip to paragraph beginning with "Cindy" for the difference between the two problems.

Alice and Bob were attending a cryptography seminar in the province of Siquijor, where they learned about the famous RSA cryptosystem used for public-key encryption. Inspired by this, they decided to create their own cryptosystem which they called RXA.

Suppose Alice wants to send Bob a secret message $$$M$$$, which is a string—let $$$n$$$ be the length of this string. They have developed the following three-pass protocol.

First, Alice encodes the string $$$M$$$ into a (possibly very large) integer $$$m$$$ (by a process described below). Now, she communicates this integer $$$m$$$ to Bob by the following procedure.

Let $$$a \oplus b$$$ denote the bitwise XOR of two non-negative integers $$$a$$$ and $$$b$$$ (see Notes for an explanation).

• Alice generates a secret non-negative integer $$$a$$$, then sends to Bob the value $$$x := a \oplus m$$$.
• Bob also generates a secret non-negative integer $$$b$$$, and sends back to Alice the value $$$y := b \oplus x$$$.
• Alice then sends back to Bob the value $$$z := a \oplus y$$$.

Note that the only values that can be heard by the public are $$$x$$$, $$$y$$$, and $$$z$$$. The secret integers $$$a$$$ and $$$b$$$ are not revealed by Alice and Bob, not even to each other.

Cindy calls them both idiots, because this cryptographic scheme has a fatal flaw. The message $$$M$$$ can actually be retrieved by a malicious third party! In fact, not only can it be retrieved—it's actually super easy to do so.

To prove her point, she considers the following problem.

Let $$$v_1, v_2, \dots, v_n$$$ be an array of positive integers. There are $$$n(n-1)(n-2)$$$ triples $$$(i, j, k)$$$ such that $$$1 \leq i, j, k \leq n$$$ and $$$i \neq j$$$ and $$$i \neq k$$$ and $$$j \neq k$$$.

Let $$$m(i, j, k)$$$ be the value of $$$m$$$ recovered from Alice and Bob's scheme, if $$$x = v_i$$$ and $$$y = v_j$$$ and $$$z = v_k$$$. Cindy believes that it should be possible to find the sum of $$$m(i, j, k)$$$ across all $$$n(n-1)(n-2)$$$ such triples of $$$(i, j, k)$$$.

We believe her. Which is why we're making you solve this problem!

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 3 \leq n \leq 150000 \\ \text{$0 \leq v_i \lt 2^{30}$ for each $i$} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & n \le 15 \\ \hline 2 & \mathbf{25} & n \le 200 \\ \hline 3 & \mathbf{25} & n \le 2000 \\ \hline 4 & \mathbf{25} & \text{No further constraints.} \\ \hline \end{array}\\

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

Alice, Bob,and Cindy are playing the exciting board game Jumanji. If you die in the game, you die for real!

Each of them starts with $$$a$$$, $$$b$$$, and $$$c$$$ points of HP (Health Points) respectively.

All gameplay takes place on a long path with $$$n+1$$$ squares, labeled $$$0$$$ to $$$n$$$. Each square has a damage value written on it—the damage value of square $$$i$$$ is $$$d_i$$$. You are guaranteed that $$$d_0 = d_n = 0$$$.

Gameplay goes as follows:

• All three of them start on square $$$0$$$. The goal is to reach square $$$n$$$.
• The three of them take turns rolling a pair of fair six-sided dice, with turn order: Alice, then Bob, then Cindy (then back to Alice).
• The turn player moves a number of steps forward equal to the sum of the two die rolls (or up to square $$$n$$$ only, if the number of steps they would take would make them go past square $$$n$$$).
• Then, the damage value of the square they stop on is subtracted from their HP. If their HP ever equals $$$0$$$ or below at any given time, they die (forever).
• The game ends when all three have reached square $$$n$$$ alive.

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 200 \\ 1 \leq a, b, c \leq 2024 \\ \text{$1 \leq d_i \leq 2024$ for $0 \lt i \lt n$} \\ d_0 = d_n = 0 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & n \leq 5 \\ \hline 2 & \mathbf{25} & n \leq 7 \\ \hline 3 & \mathbf{25} & d_i, a, b, c \leq 70 \\ \hline 4 & \mathbf{25} & \text{No further constraints.} \\ \hline \end{array}\\

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

This is an interactive problem.

Bob wanted to communicate an $$$n$$$-digit code to Alice (each character is from 0123456789 and the code may have leading zeros). Alice forgot her contact lenses today, so her eyesight is a bit bad. To help make it easier for her to see, Bob blew up this code into ASCII art and printed it out on a gigantic billboard.

Each digit can be encoded using a grid with $$$8$$$ rows and $$$5$$$ columns. Here are the designs that Bob used for this project:

In Bob's ASCII art, black pixels are represented with the # character, while white pixels are represented with the . character. Also, for clarity, Bob put a column of . characters between each digit's representation in the grid. So, for example, 069 would be encoded like this:

.###...###...###.
#...#.#.....#...#
#..##.#.....#...#
#.#.#.####..#...#
##..#.#...#..####
#...#.#...#.....#
#...#.#...#.#...#
.###...###...###.

Unfortunately, Alice's eyesight really is quite bad, so she can only see one row or one column at a time, and doing so takes a lot of effort! Help Alice decipher Bob's code using as few observations as possible.

The interactor will first send the integer $$$T=5000$$$, the number of test cases. Each test case goes as follows.

First, the interactor will send a positive integer $$$n$$$, the length of the string (where $$$1 \leq n \leq 10$$$ always). From here, you have three options.

You can send "ASK ROW <i>", where $$$1 \leq i \leq 8$$$. Then, the judge responds with a string of length $$$6n-1$$$, the characters in the $$$i$$$th row from the top.

You can send "ASK COL <j>", where $$$1 \leq j \leq 6n-1$$$. Then, the judge responds with $$$8$$$ lines, each containing a string of length 1, corresponding to the characters in the $$$j$$$th column from the left.

When ready, you can send "ANSWER <ans>" where ans is what you believe the original string to be. If your answer is correct, you proceed immediately to the next test case. If not, the judge gives you a Wrong Answer verdict, and no further communication will happen.

The judge will also give you a Wrong Answer verdict and cease communication if you attempt to make more than $$$20$$$ ASK queries in the same test case. We can prove that the task is always doable in $$$20$$$ or fewer ASK queries.

If you got a Wrong Answer or did anything invalid, your score is $$$0$$$.

Otherwise, let $$$M$$$ be the maximum number of ASK queries used in any test case, across all test cases. You get more points the closer this is to optimal. Let $$$m$$$ be the judge's such number.

• If your solution is correct, you get $$$50$$$ points
• But if $$$M \leq 2m$$$, you get $$$75$$$ points instead.
• But if $$$M=m$$$, you get $$$100$$$ points.

Bob was considering all of the quantum ramifications of multiverse theory. If you consider that there are other dimensions out there with alternate versions of you, across all possible choices you could have made in your lifetime, then for every good version of you, there must be an evil version of you as well. And sometimes the good and evil multiversal counterparts can annihilate each other like antimatter if they ever come into contact with each other.

Anyway, that is all to say, Bob is having a lot of fun writing a sci-fi short story.

Alice is somewhat fatigued with all this multiverse nonsense in the current cultural mass media zeitgeist. So while Bob's doing all that, why don't you solve this fun math puzzle with her?

A positive integer $$$n$$$ is called zero-multiversal if its digits can be rearranged into two different positive integers $$$p$$$ and $$$q$$$ such that $$$|p-q|$$$ contains at least one $$$0$$$.

So, for example, $$$128$$$ is zero-multiversal, because $$$821 - 218 = 603$$$. On the other hand, it can be shown that $$$69$$$ is not zero-multiversal.

Given positive integers $$$\ell$$$ and $$$r$$$, count the number of zero-multiversal integers between $$$\ell$$$ and $$$r$$$ (inclusive).

Formally, let $$$\mathrm{digits}(m)$$$ be the multiset containing all the digits of some positive integer $$$m$$$ (by default, we assume integers are never written with leading zeros). Then, a positive integer $$$n$$$ is called zero-multiversal if there exist distinct positive integers $$$p$$$ and $$$q$$$ such that:

• $$$p \neq q$$$
• $$$\mathrm{digits}(p) = \mathrm{digits}(q) = \mathrm{digits}(n)$$$
• The digit 0 appears in $$$\mathrm{digits}(|p-q|)$$$

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 150000 \\ 0 \lt \ell \leq r \lt 10^{18} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & r \lt 10^4 \\ \hline 2 & \mathbf{30} & r \lt 10^6 \\ \hline 3 & \mathbf{20} & r \lt 10^9 \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

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

Bob is making yet another grid-based painting for his school's art exhibit. This year, he decided to take some inspiration from Alice and inject some fun mathematics into his construction this year!

A magic square is an $$$n \times n$$$ grid such that:

• Each of its squares contains a distinct positive integer.
• The sum of the entries along each row and column, as well as the sum of the entries along the main diagonal (top-left to bottom-right corners) and along the anti-diagonal (top-right to bottom-left corners) are all the same.

• Each of its squares contains a distinct positive integer from 1 to 101.
• The sum of the entries along each row and column, as well as the sum of the entries along the main diagonal and along the anti-diagonal, are all the same modulo 101.
  • These sums do not necessarily have to all be exactly the same... they just need to all give the same remainder when divided by $$$101$$$.

• The rows sum up to: $$$241$$$, $$$39$$$, $$$241$$$, and $$$241$$$ (from top to bottom).
• The columns sum up to: $$$241$$$, $$$140$$$, $$$241$$$, and $$$140$$$ (from left to right).
• The main diagonal sums up to $$$241$$$, and the anti-diagonal sums up to $$$140$$$.

Bob will pre-fill in at most two values in an $$$n \times n$$$ grid, since those values at those position are very important for the message he wants to communicate with his art. Can you help him by constructing any Mondrialayagic square around them? That is, find any Mondrialayagic square that has those pre-filled values at those positions.

If none exist, you should say so as well.

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 5000 \\ 3 \leq n \leq 6 \\ \text{The pre-filled squares contain distinct values from $1$ to $101$.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{23} & \text{There are no pre-filled squares.} \\ \hline 2 & \mathbf{33} & \text{There is at most one pre-filled square.} \\ \hline 3 & \mathbf{44} & \text{There are at most two pre-filled squares.} \\ \hline \end{array}\\

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