The 17th Annual Donald Knuth Programming Contest has just begun, and the very first challenge, the problem A, sets the tone for the event. The problemsetters wanted to test not only algorithmic skill but also a deep intuition about numbers.

This year's opening problem comes with a playful story: Miguel, an enthusiast of mathematics, prepared a mysterious box containing slips of paper with numbers from $$$1$$$ to $$$n$$$. The task is simple at first glance: you may take any subset of these slips and add them together.

But there is a twist — Miguel was not interested in prime numbers. He believed primes were already "too famous," so he asked contestants to ignore them.

A number is called prime if it is greater than $$$1$$$ and has no positive divisors other than $$$1$$$ and itself. In particular, $$$1$$$ is not considered prime.

The question Miguel posed is: among all possible subset sums, what is the largest number that is not prime?

As everyone knows, the Legendary Huron loves playing with magnetic sticks of many colors. After finishing his colorful polygon constructions last Saturday, he now wants to store his sticks in boxes.

Legendary Huron owns $$$m$$$ magnetic sticks. Each stick has a color, represented by an integer in the range $$$[0, m-1]$$$. Sticks of the same color are indistinguishable.

He plans to store these sticks in $$$n$$$ distinct boxes. Each stick must be placed in exactly one box.

Once the sticks are distributed, Legendary Huron will hang the boxes in the form of a colorful rooted tree:

• One box will be chosen as the root and hung directly from the ceiling.
• Every other box will be hung directly from exactly one parent box, forming a tree structure with $$$n$$$ nodes (the boxes).

Legendary Huron defines the beauty of his arrangement as follows:

• Beauty of a box: the MEX of the colors inside that box. Recall that the MEX of a multiset of integers is the smallest non-negative integer that does not belong to the multiset. For example, if a box contains sticks of colors $$$\{0,2,2,5\}$$$, its beauty is $$$1$$$.
• Beauty of a path: the product of the beauties of all boxes along that path.
• Beauty of the tree: the sum of the beauties of all $$$n^2$$$ simple paths in the tree (including single-box paths).

Legendary Huron is still undecided about two things:

1. How to distribute the $$$m$$$ sticks among the $$$n$$$ boxes.
2. How to hang the boxes as a rooted tree.

He wants to know the total sum of beauties of the trees over all possible valid configurations. Two configurations are considered different if:

• The tree structures differ (different root or different set of edges), or
• There exists at least one box whose multiset of colors differs.

Note: The boxes are distinct (labeled), but the sticks of the same color are indistinguishable.

After retiring from competitive programming, May decided to become a Pokémon trainer. She has $$$N$$$ Pokémon, and each Pokémon is described by three values: defense ($$$d$$$), health ($$$h$$$), and attack ($$$a$$$).

May is creating a training plan called Chained Training. Her Pokémon are arranged in a line, and the Pokémon at index $$$i$$$ can only fight a Pokémon at index $$$j$$$ such that $$$j \lt i$$$.

When Pokémon $$$i$$$ battles Pokémon $$$j$$$, Pokémon $$$i$$$ gains experience according to the following formula:

$$$$$$ \text{experience}(i, j) = d_j \cdot a_i + \frac{h_j}{d_i} $$$$$$

May has a gym battle soon, so she wants her Pokémon to gain as much experience as possible by fighting against a single Pokémon. For each Pokémon, determine the maximum amount of experience it can gain if she chooses its rival optimally.

Welcome to the XVII Annual Drone Kaleidoscope (DK for short)! A one-lane track is written as a string $$$s$$$ of $$$n$$$ lowercase characters.

During the annual DK, several teams, one by one, perform a show as follow:

• Each team picks a different palindrome that actually appears somewhere on the track.
• Each team selects some subset of occurrences of their chosen palindrome, and places a drone in the leftmost character of the selected occurrences.
• To avoid radio noise within the team performance, that team's drone starting positions must be at least $$$k$$$ characters apart.
• Finally, the team flies their drones over the selected occurrences of the chosen palindrome.

A team's show value is $$$$$$ \text{(length of its palindrome)} \times \text{(number of drones it places)}. $$$$$$

Choose how many teams to field (each using a distinct palindrome) and, for each chosen team, pick the starting positions of its drones so as to maximize the total show value across all shows.

For example, if we have $$$s=abaaba$$$ and k=3, a valid show configuration is to field $$$3$$$ teams as follows:

1. The first team chooses the palindrome $$$aba$$$ and launches $$$2$$$ drones with initial positions $$$\{1,4\}$$$. This team's show value is $$$3 \times 2=6$$$.
2. The second team chooses the palindrome $$$baab$$$ and launches $$$1$$$ drones with initial position $$$\{2\}$$$. This team's show value is $$$4 \times 1=4$$$.
3. The third team chooses the palindrome $$$a$$$ and launches $$$2$$$ drones with initial positions $$$\{1,6\}$$$. This team's show value is $$$1 \times 2=2$$$. Note that launching $$$3$$$ drones with initial positions $$$\{1,3,6\}$$$ is invalid, since starting positions should be at least $$$k=3$$$ characters apart.

The total show value in this example is $$$6+4+2=12$$$. Note that this is not the configuration that maximizes the total show value.

During the Segunda Fecha del Gran Premio de México, Ángel built his unusual computer prototype. Thanks to your help, he was able to complete his assignment, but a new defect has now appeared.

This time, the problem lies in the rotation instruction. Ángel wants to transform an array $$$A = [a_1, a_2, \dots, a_n]$$$ into another array $$$B = [b_1, b_2, \dots, b_n]$$$. He can perform the following operation any number of times:

• Choose indices $$$l,r$$$ with $$$1 \le l \le r \le n$$$, and an integer $$$k$$$ with $$$0 \leq k \leq 10^6$$$. Rotate the subarray $$$A[l,r]$$$ to the left at the digit level exactly $$$k$$$ times.

For example, if $$$A = [12, 345, 67, 8, 9]$$$ and you apply the operation on the subarray $$$A[2,4]$$$ with $$$k=2$$$, the result is $$$[12, 567, 83, 4, 9]$$$.

Decide whether it is possible to transform $$$A$$$ into $$$B$$$ using a sequence of such operations. If it is possible, you must also output one valid sequence.

The coaches of TCMX 2025 are preparing the fifth contest. Racso came up with the idea of stealing the samples of the problems. Abraham and Ivan want to stop him, so they have protected the samples with laser beams. Each laser beam can be represented as a line segment from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ parallel to one of the axis.

To verify how safe the test cases are, they will check $$$Q$$$ scenarios.

In each scenario, the initial position of Racso and the position of the samples are given. Racso will succeed in stealing the samples if he can move from his starting position to the place where the samples are located. Racso is represented as a point in the plane and fails if he touches any laser beam at any moment, even if it happens at the beginning or at the end of his path.

For each scenario, determine whether Racso can succeed.

The Galactic Empire has organized its planets in a strict chain of command. At the very top lies Coruscant, the capital of the system. The planets are numbered from $$$1$$$ to $$$n$$$ according to their closeness to Coruscant (being Coruscat the planet with number $$$1$$$). Every other planet $$$u$$$ has a direct supervisor $$$p_u$$$ with $$$1 \le p_u \lt u$$$, forming a rooted tree with root in planet Coruscant.

Emperor Palpatine has decreed that all planets must be directly supervised by Coruscant, eliminating intermediate overseers (i.e., in the end every $$$u \ge 2$$$ must satisfy $$$p_u=1$$$).

You are granted the following operation:

• Choose a planet $$$u$$$. For every planet $$$v$$$ on the chain of command from $$$u$$$ up to Coruscant (including $$$u$$$ but excluding Coruscant), reassign its supervisor to be the planet immediately closer to Coruscant; that is, decrement $$$p_v$$$ by one (set $$$p_u \leftarrow p_v - 1$$$). This gradual decrement by one is required to avoid instability within the Empire, since sudden jumps in authority could trigger rebellion and chaos.

Your task is to determine the minimum number of operations required so that, after applying them, every planet reports directly to Coruscant.

In a previous Concurso Anual de Programación "Donald Knuth", Rem faced a peculiar problem: counting the number of different ways to travel across a hive-shaped grid.

The grid is formed by columns of hexagonal cells:

• The first column has exactly 1 cell.
• The second column has 2 cells.
• The third column has 3 cells.
• $$$\dots$$$
• The $$$(n+1)$$$-th column has $$$n+1$$$ cells.
• After that, each subsequent column has one fewer cell than the previous, until the final $$$(2n+1)$$$-th column which has exactly 1 cell.

Thus, the grid consists of $$$2n+1$$$ columns of hexagonal cells, forming the shape of a "diamond hive." The entry cell is the single hexagon in the first column, and the storage cell is the single hexagon in the last column.

Below is an example of the grid with size $$$n=3$$$ with the valid set of movements for a single cell:

Rem solved the original challenge: finding how many paths exist from the entry to the storage without visiting the same hexagonal cell twice.

Later, he wondered: "If someone naïvely tried to simulate every single path with a brute-force depth-first search, how many total steps would such an algorithm actually take?"

In this brute-force simulation, for each valid path, a DFS would traverse the entire path from beginning to end. Therefore, the total cost of this approach equals the sum of the lengths of all distinct paths, where the length of a path is the number of hexagonal cells it visits.

Your task is to compute the sum of the lengths of all distinct paths.

You are given $$$n$$$ identical biased coins. In each toss, every coin shows sol with probability $$$\tfrac{p}{q}$$$ and águila with probability $$$1 - \tfrac{p}{q}$$$. Initially, none of the coins has shown sol.

You perform the following process:

• In each round, you toss all coins that have not shown sol yet.
• Once a coin shows sol for the first time, it is removed from further tosses.
• The process continues until every coin has shown sol at least once.

Let $$$T$$$ denote the number of rounds until this happens. Your task is to compute the expected value of $$$T$$$.

You are given a directed graph $$$G = (V,E)$$$ with $$$n$$$ nodes. The set of vertices is $$$V = \{1,2,\dots,n\}$$$. For every node $$$u \in V$$$, there is a directed edge from $$$u$$$ to each of its proper divisors. Formally: $$$$$$ (u,v) \in E \quad \text{iff} \quad v \mid u \quad \text{and} \quad 1 \leq v \lt u. $$$$$$

For each node $$$u$$$, define:

• $$$I(u)$$$: the length of the longest directed path in $$$G$$$ that ends at $$$u$$$.
• $$$O(u)$$$: the length of the longest directed path in $$$G$$$ that starts at $$$u$$$.

The length of a path is the number of edges it contains.

Your task is to compute the following sum: $$$$$$ S(n) = \sum_{u=1}^{n} \max\big(I(u), O(u)\big). $$$$$$

José is practicing graph and tree problems on the HuronCoder platform, and he came across the following challenge.

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. The parent of each node $$$u$$$ is $$$p_u$$$, with $$$1 \le p_u \lt u$$$. Each node $$$u$$$ has an associated value $$$a_u$$$.

You need to process queries of three types:

1. Assign $$$k$$$ to the value of node $$$u$$$: $$$a_u \leftarrow k$$$.
2. Given $$$u, v$$$, consider the unique path between $$$u$$$ and $$$v$$$. Select a non-empty contiguous subsequence of nodes along that path such that the sum of their values is maximized, and report that sum.
3. For every $$$i$$$ in the range $$$[l, r]$$$, update $$$p_i \leftarrow \max(1,\; p_i - k)$$$, where $$$k$$$ is given in the query.

José needs your help.

Leo is now training for the ICPC 2025 Regional Finals. As part of his preparation, he uses the popular site HuronCoder, which contains many problems with different tags.

The site has $$$N$$$ problems numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ tags numbered from $$$1$$$ to $$$M$$$. Each problem can be tagged with any subset of tags (including the empty subset or the full set of tags).

Leo wonders if it is possible to pick a subset of problems so that, when combined, they cover all tags.

Okarun is studying alien art. Alien art is represented by a square matrix that contains blank characters, digits from $$$1$$$ to $$$9$$$, the symbol '$$$+$$$', or the symbol '$$$*$$$'. We call such square matrix an art matrix, and it is defined recursively as follows:

• A matrix of size $$$1 \times 1$$$ that contains a single digit $$$d$$$ different from $$$0$$$.
• A matrix of size $$$N \times N$$$ ($$$N \gt 1$$$) that has the same character $$$c$$$ ($$$c \in \{+, *\}$$$) in its four corners, and $$$0$$$ or more non-adjacent art matrices placed inside its inner submatrix.

The inner submatrix is obtained by removing the leftmost and rightmost columns, as well as the top and bottom rows. Two art matrices are considered non-adjacent if there is at least one blank character adjacent to every cell on their borders.

Each art matrix has an associated beauty value $$$b$$$, defined as:

• If $$$N = 1$$$, then $$$b = d$$$, where $$$d$$$ is the digit contained in the matrix.
• If $$$N \gt 1$$$ and $$$c = +$$$, then $$$b = \sum\limits_{m \in M} b_m$$$, where $$$M$$$ is the set of art matrices in the inner submatrix. If $$$M$$$ is empty, $$$b = 0$$$.
• If $$$N \gt 1$$$ and $$$c = *$$$, then $$$b = \prod\limits_{m \in M} b_m$$$, where $$$M$$$ is the set of art matrices in the inner submatrix. If $$$M$$$ is empty, $$$b = 1$$$.

Given an art matrix, tell Okarun the beauty of the matrix.