In the Square Kingdom, $$$n$$$ residents numbered from $$$1$$$ to $$$n$$$ live alone on top of a tall stone pillar. The height of the pillar for the $$$i$$$-th resident is $$$\left(i + \frac{b}{a}\right)^2$$$ units above the ground.

Since everyone lives so high up, the only way to visit a neighbor is by using a ladder. The kingdom builds one ladder for every pair of residents. The length of each ladder is exactly the absolute difference in height between the two pillars it connects.

With $$$\frac{n(n-1)}{2}$$$ ladders in total, it becomes hard to manage them all. You are asked for the length of the $$$k$$$-th ladder in ascending order of length. This information will help the kingdom plan repairs, deliveries, and community events.

Sulfox the fennec fox is a coder who loves creating digital art in his spare time. Worn out from a day of debugging, he opens his painting software as usual, only to find the software itself is also riddled with bugs after the latest update, one major issue being that it stutters noticeably whenever he edits a pixel.

The painting software treats the canvas as an ordered stack of layers. Each layer is a grid of pixels with $$$n$$$ rows and $$$m$$$ columns, each pixel holding a visible value in $$$\{0,1,\ldots,nm\}$$$, where $$$0$$$ denotes transparent, and positive values are identifiers for $$$nm$$$ distinct colors. Since layers may occlude one another, at any position, the visible value of the composite image equals the visible value of the topmost non-transparent pixel among all layers; if all layers are transparent at that position, the visible value is $$$0$$$.

Sulfox already knows exactly what he wants to draw: a target image denoted by a matrix $$$(p_{i,j})_{n \times m}$$$ of visible values. To finish as quickly as possible, he wants to minimize the total "lag cost" caused by the software bug. Starting with no layers, Sulfox may perform the following operations any number of times:

• Create Layer: insert a new layer on top for free and initialize it either as a constant color layer with every pixel set to the same chosen color $$$c$$$ ($$$1 \le c \le nm$$$), or as an empty layer with every pixel transparent;
• Brush Tool: spend $$$a$$$ to set any single pixel of any layer to any chosen color $$$c$$$ ($$$1 \le c \le nm$$$);
• Eraser Tool: spend $$$b$$$ to make any single pixel of any layer transparent.

Help Sulfox determine the minimum total cost needed to perform operations so that the composite image matches the target image, i.e., the visible values at corresponding positions of both images are equal.

This is a communication problem.

Well... after surviving the nightmarish stutter in Problem B. Buggy Painting Software I, Sulfox soon faces a far more serious bug — his painting software saves any color image in black-and-white format.

Here, a color image supports $$$m$$$ distinct colors labeled $$$1$$$ through $$$m$$$, and can be viewed as a sequence of length $$$3m$$$ composed of color labels, where each color appears exactly three times. A black-and-white image supports only black (labeled $$$0$$$) and white (labeled $$$1$$$), and can be viewed as a binary sequence. When saving a color image, the software chooses a non-empty bipartition $$$(S_0,S_1)$$$ of $$$S=\{1,2,\dots,m\}$$$ (so $$$S_0 \cup S_1=S$$$, $$$S_0 \cap S_1=\varnothing$$$, and both $$$S_0$$$ and $$$S_1$$$ are non-empty) and converts the original sequence into a binary sequence of the same length by mapping every color in $$$S_0$$$ to $$$0$$$ and every color in $$$S_1$$$ to $$$1$$$. The resulting binary sequence will be the saved black-and-white image.

To outsmart this bug, Sulfox wants to create $$$n$$$ color images with respective integer feature values $$$x_1, x_2, \ldots, x_n$$$ (values may repeat) ranging from $$$1$$$ to $$$m$$$. Your task is to help Sulfox design these color images so that each image's feature remains identifiable even after the color loss. More specifically, the $$$i$$$-th color image ($$$1 \le i \le n$$$) must satisfy that, no matter how the non-empty bipartition $$$(S_0, S_1)$$$ is chosen, its feature value $$$x_i$$$ can always be recovered from the saved black-and-white image.

To verify the correctness of your design, your program will be run twice on each test: first for constructing $$$n$$$ color images, and then for recovering the original feature values from $$$n$$$ black-and-white images. The second run will receive exactly the $$$n$$$ binary sequences mapped from each of the $$$n$$$ sequences you output in the first run by independently chosen non-empty bipartitions. Apart from that, the second run will receive no additional information from the first run. Your solution passes a test if you correctly recover the corresponding feature value from each black-and-white image.

Note that the applied bipartitions are unpredictable and may be adaptive to your design, and different bipartitions may apply to the color images with the same feature value.

You have an LED display capable of showing an $$$n$$$-digit integer, where each digit is represented using the standard $$$7$$$-segment layout.

Initially, each of the $$$7$$$ digit segments in every digit block may be in one of three states:

• Functional (denoted by 'W'): behaves correctly, i.e., it lights up or turns off as required by the digit being displayed;
• Stuck ON (denoted by '1'): always lit regardless of the digit being displayed;
• Stuck OFF (denoted by '0'): always unlit regardless of the digit being displayed.

You can renovate at most $$$k$$$ digit segments, i.e., convert at most $$$k$$$ digit segments into functional. You need to maximize the number of integers that can be correctly displayed and find the number of ways to achieve the maximum. Note that you can renovate digit segments that are initially functional, and each digit segment can be renovated at most once. Two ways of renovation are considered different if there is at least one digit segment that is renovated in one way but not in the other.

An integer is correctly displayed if and only if:

• It has no leading zeros, unless the integer is exactly $$$0$$$;
• It is right-aligned on the display: if the integer has $$$d$$$ ($$$1 \le d \le n$$$) digits, then only the rightmost $$$d$$$ digit blocks are used, and the leftmost $$$(n - d)$$$ blocks should be left blank and show nothing;
• For each of the $$$d$$$ used digit blocks, all $$$7$$$ digit segments match the target digit's display pattern when functional segments show the correct state for that digit and faulty segments remain stuck in their state.

You are playing a popular card game. There are $$$2n$$$ distinct cards labeled $$$1$$$ through $$$2n$$$, shuffled uniformly at random and piled up into a deck. You draw the top $$$n$$$ cards as your starting hand, and the remaining deck order is hidden from you. Each turn, you choose any one card from your hand, play it by placing it at the bottom of the deck, and then draw the current top card, so your hand size remains $$$n$$$.

You have $$$m$$$ quests to complete in order: the $$$i$$$-th quest requires you to play the card labeled $$$a_i$$$, and it becomes active only after the $$$(i-1)$$$-th quest is completed (unless it is the first quest, which is initially active). Playing the card labeled $$$a_i$$$ before the $$$i$$$-th quest is active does not count toward the $$$i$$$-th quest. You know any of $$$a_1, a_2, \ldots, a_m$$$ (values may repeat) in advance.

Assuming you play cards under the optimal pure strategy, compute the minimum expected number of turns needed to complete all $$$m$$$ quests over the random initial shuffle, modulo $$$998\,244\,353$$$.

Formally, a pure strategy means that at each turn, the card chosen depends only on the observable history, and identical known information (initial hand, respective played and drawn cards in past turns, and quest completion status) deterministically yields the same chosen card. For a pure strategy $$$\sigma$$$ and an initial shuffle $$$\pi$$$, let $$$f_\sigma(\pi)$$$ be the number of turns needed to complete all $$$m$$$ quests when following $$$\sigma$$$; the value to be computed equals $$$\left(\min_{\sigma} E\!\left[f_\sigma(\pi)\right]\right) \bmod 998\,244\,353$$$, where the expectation $$$E[\cdot]$$$ is taken over the uniform distribution on all $$$(2n)!$$$ possible shuffles of the initial deck.

Sulfox the fennec fox has built a maze and invited his two friends, Alice and Bob, to try it. The maze can be abstracted as a simple, connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges, where Alice and Bob start at two distinct specified vertices.

Before any player moves, Sulfox must choose a direction for every undirected edge, turning the maze into a directed graph. Then, in an attempt to find each other, both players move in rounds within the oriented maze. In each round, they act simultaneously and independently, neither leaving marks nor communicating; rather, they adopt the "most brainless" strategy:

• If a player is currently at a vertex that has one or more outgoing edges, they arbitrarily traverse an outgoing edge to the adjacent vertex;
• otherwise, if their current vertex has no outgoing edges, they remain at that vertex.

Sulfox, being proud of his maze-design skills, wants to orient the passages so that Alice and Bob can never meet. Given the undirected graph and the starting vertices of Alice and Bob, please help Sulfox orient every edge so that no matter how Alice and Bob make their choices in every round, they will never occupy the same vertex at the end of any round. If such orientation does not exist, report it.

In a 2D physics-based video game, two characters $$$P$$$ and $$$Q$$$ move across the battlefield. Each character is represented by a convex polygon that serves as its collision box. When the two collision boxes overlap, the game calculates the area of their intersection as the collision damage.

However, due to unpredictable wind currents in the arena, character $$$Q$$$ can be displaced by an arbitrary translation vector $$$\mathbf{t} = (t_x, t_y)$$$, but it cannot rotate or flip. You need to calculate the expected collision damage when $$$Q$$$ is uniformly and randomly placed such that it actually collides with $$$P$$$, i.e., their intersection has a positive area.

More formally, define $$$f(\mathbf{t})$$$ as the area of the intersection between the polygon representing character $$$P$$$ and the polygon representing character $$$Q$$$ after being translated along $$$\mathbf{t}$$$. Let $$$D \subseteq \mathbb{R}^2$$$ be the set of all translation vectors $$$\mathbf{t}$$$ for which $$$f(\mathbf{t}) \gt 0$$$. It can be shown that $$$D$$$ has a positive area, denoted by $$$|D|$$$. You need to calculate $$$\frac{1}{|D|} \iint\limits_{D} f(\mathbf{t}) \, d\mathbf{t}$$$.

A Young diagram is a finite set of cells, arranged in left-aligned rows, with the row lengths in non-increasing order. It can be uniquely represented by an unordered integer partition $$$\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_r)$$$ satisfying $$$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_r\ge 1$$$, where $$$r$$$ corresponds to the number of rows of the Young diagram, and $$$\lambda_i$$$ corresponds to the number of cells in the $$$i$$$-th row for $$$i = 1,2,\ldots,r$$$.

The conjugate of a Young diagram $$$\lambda$$$ is another Young diagram obtained by transposing rows and columns, represented by the conjugate partition $$$\lambda^T$$$. More specifically, if $$$\lambda$$$ has $$$c=\lambda_1$$$ columns, then $$$\lambda^T=(\mu_1,\mu_2,\ldots,\mu_c)$$$ where $$$\mu_j=\lvert\{\,i:\lambda_i\ge j\,\}\rvert$$$ for $$$j = 1,2,\ldots,c$$$.

For a cell at the $$$i$$$-th row and the $$$j$$$-th column that belongs to $$$\lambda$$$, let the subdiagram anchored at $$$(i,j)$$$ be the set of all cells $$$(x,y)$$$ of $$$\lambda$$$ with $$$x\ge i$$$ and $$$y\ge j$$$. It is easy to see that, this set is itself a Young diagram when viewed with $$$(i,j)$$$ as its top-left corner.

Define the cuteness of a Young diagram $$$\lambda$$$ as the number of distinct Young diagrams that can be obtained from $$$\lambda$$$ by performing the following operation any number (possibly zero) of times: choose any cell $$$(i,j)$$$ of the current Young diagram, take the subdiagram anchored at $$$(i,j)$$$, and replace it with its conjugate anchored at the same position. The operation is allowed if and only if the overall set of cells still forms a valid Young diagram; otherwise the operation is denied and undone, as illustrated below.

You are given a non-increasing sequence of positive integers $$$a_1,a_2,\ldots,a_n$$$. For each $$$i = 1,2,\ldots,n$$$, compute the cuteness of the Young diagram $$$\lambda^{(i)}$$$, modulo $$$998\,244\,353$$$, where $$$\lambda^{(i)}=(a_1,a_2,\ldots,a_i)$$$.

In an ICPC contest, there are multiple problems, and the contest lasts for a long duration. There are $$$n$$$ accepted submissions in total, each representing a successful attempt by a team on a problem. When a team makes an accepted submission for a problem, we say that the team has solved that problem. Note that if a team submits multiple accepted solutions for the same problem, only the first such submission is considered as solving the problem for the first time.

You need to determine for each submission whether a balloon should be awarded according to the following rules:

• Before the scoreboard freeze (submission time $$$ \lt 240$$$ minutes): when a team solves a problem for the first time, award a balloon corresponding to that problem.
• After the scoreboard freeze (submission time $$$\geq 240$$$ minutes): when a team solves a problem for the first time, award a balloon corresponding to that problem if and only if the team has received strictly fewer than $$$3$$$ balloons in total so far.

In the year 3142, deep within the rings of Titan, the last archive of pre-Collapse human memory is sealed inside the Chronos Vault. Its entrance is guarded by the Echo Dial, a quantum-entangled lock composed of $$$n$$$ chronal rings arranged in a single filament. Each ring displays a phase value in the range $$$0$$$ to $$$m-1$$$, indicating its alignment with the cosmic rhythm. Initially, the $$$i$$$-th ring shows the value $$$a_i$$$.

The Echo Dial can only be adjusted through resonant tuning, governed by the following rules:

• In a single operation, you may choose any phase value $$$x \in [0, m)$$$ and simultaneously tune all rings currently displaying $$$x$$$ either:
  • forward tuning: $$$x \to (x + 1) \bmod m$$$, or
  • backward tuning: $$$x \to (x - 1) \bmod m$$$.
• This operation affects every ring in the entire dial that currently resonates at phase $$$x$$$, regardless of position.

The Oracle of Echoes, the vault's sentient guardian, issues $$$q$$$ diagnostic trials. Each trial is given as a query $$$(l, r, v)$$$ and asks for the minimum number of resonant tuning operations required to set all rings in positions $$$l$$$ through $$$r$$$ (inclusive) to phase $$$v$$$.

All trials are hypothetical. The Echo Dial always starts from its original initial state for every query, and no trial alters the actual configuration of the dial. As the last Quantum Archivist, your duty is to answer all $$$q$$$ queries efficiently.

There are $$$n$$$ frogs numbered $$$1$$$ through $$$n$$$, each initially located at an integer lattice point in the Cartesian plane. An external disturbance suddenly stimulates one of the frogs, triggering a chain reaction in which the frogs act according to the rules below.

When frog $$$i$$$ ($$$1 \le i \le n$$$) is stimulated, it can choose to either:

• jump toward some other frog $$$j$$$ ($$$1 \le j \le n$$$, $$$j \neq i$$$) and instantly land at the reflection of its current position across the point currently occupied by frog $$$j$$$ (if frog $$$i$$$ coincides with frog $$$j$$$ before the jump, then it lands at the coinciding point); immediately after this jump, frog $$$j$$$ becomes the next and only frog to be stimulated;
• or stay where it is, in which case all jumps end and no frog remains stimulated.

A frog may be stimulated multiple times at different moments, while some frogs may never be stimulated.

You observe that the first stimulated frog is numbered $$$s$$$, but there are too many jumps for you to capture the entire process. Fortunately, you recognize every frog, so you record both their initial positions $$$P_1, P_2, \ldots, P_n$$$ and their final positions $$$Q_1, Q_2, \ldots, Q_n$$$ after all jumps have ended. You also notice that all initial positions are pairwise distinct, and the final positions are pairwise distinct as well.

Let $$$t$$$ be the index of the last stimulated frog, i.e., the frog that chooses to stay still when stimulated, after which no more jumps occur. Please find $$$t$$$.

In a future where digital logic has evolved beyond binary, a new system of signal processing, known as tri-color logic, has become the standard. This system defines four fundamental states in two categories:

• Colored: There are three colored states, denoted by $$$\text{R}$$$ (Red), $$$\text{G}$$$ (Green), and $$$\text{B}$$$ (Blue), respectively. Each serves as a distinguishable "on" state, analogous to the traditional logic $$$1$$$ signal.
• Colorless: The only colorless state is denoted by $$$*$$$ (Transparent). It serves as an "off" state, analogous to the traditional logic $$$0$$$ signal.

Sulfox the fennec fox is designing a computing device based on tri-color logic technology, named Leo. It employs a simple combinational logic architecture, so we can regard it as a directed acyclic graph in which each node holds a state from the set $$$\{\text{R}, \text{G}, \text{B}, *\}$$$. After fixing the machine's input scale to $$$n$$$, the graph is constructed as follows:

• Nodes $$$1, 2, \dots, n$$$ are input nodes, whose states should be given as the input to the machine. Input nodes have no predecessors.
• Nodes $$$n+1, n+2, \dots, n+m$$$ are internal nodes, whose states are computed based on the states of two predecessors, where the two predecessors of each internal node may be the same and are chosen from nodes with indices strictly less than its own. To ensure the machine's operating speed, $$$m$$$ (the number of internal nodes) must not exceed $$$6n$$$.
• The internal node $$$n+m$$$ is also the only output node, whose state is the output of the machine.

Every internal node is of exactly one of the following two types, depending on how it combines the signals from its two predecessors:

• Tri-Color AND: If the states of its predecessors are identical, its own state will be that same state. If they differ, its own state will be $$$*$$$.
• Tri-Color OR: If the states of its predecessors are identical, its own state will be that same state. If one predecessor's state is $$$*$$$ while the other's is colored, its own state will be the colored one. If they differ and both are colored, its own state will be the colored state that is different from both.

With everything prepared, we now specify Leo's intended functionality. The states given to the $$$n$$$ input nodes will be guaranteed to contain at least one occurrence of each of $$$\text{R}$$$, $$$\text{G}$$$, and $$$\text{B}$$$, where $$$*$$$ may appear any number (possibly zero) of times. For every such input, the state of the output node $$$n+m$$$ must be identical to the third distinct colored state encountered when examining the input nodes from node $$$1$$$ to node $$$n$$$ (ignoring all $$$*$$$). In other words, among $$$\text{R}$$$, $$$\text{G}$$$, and $$$\text{B}$$$ it must output the colored state whose first occurrence has the largest index.

Given the machine's fixed input scale $$$n$$$, please complete the design of the internal nodes, i.e., specify the number of internal nodes and the type and predecessors of each internal node.

To verify the correctness of your design, for each test, the judge will generate $$$\left\lfloor\frac{10^7}{n}\right\rfloor$$$ valid input cases, each of which will be provided as your machine's input in turn. Your solution passes a test if your machine's output always meets Leo's intended functionality across all input cases.

At the 2025 League of Legends Season 15 World Championship, T1 battled KT Rolster in a full five-game series, ultimately defeating KT with a 3-2 score to claim the championship. This match was exceptionally significant, giving birth to multiple new historical records.

As T1's star mid-laner, Faker has now achieved six World Championship titles in his personal career with this victory, further cementing his status as the "Greatest Player of All Time" in League of Legends. Besides Faker, his teammates Oner, Gumayusi, and Keria also accomplished the remarkable feat of securing three consecutive World Championship titles. Meanwhile, the newly joined top-laner Doran filled the gap in his personal accolades by winning his first World Championship.

The journey for the LPL region, however, was full of drama. The highly-touted first seed Bilibili Gaming (BLG) suffered a surprising upset loss to the North American team 100 Thieves in the very first round of the Swiss Stage. They were then eliminated in the crucial qualification match by Top Esports (TES), stopping at the Top 16 as a first seed and becoming one of the major upsets of the tournament. TES itself was swept 3-0 by T1 in the semi-finals, leaving the LPL region absent from the finals. Has the LPL reached its conclusion?

When we look back at the journey of the two finalist teams, everything began with the life-or-death knockout stage. The eight-team single-elimination bracket stipulated that teams were placed into the bracket based on their performance in the Swiss Stage, entering a series of head-to-head battles where the loser was immediately eliminated. The entire stage consisted of three rounds: the quarter-finals, where eight teams were narrowed down to four; the semi-finals, where these four teams produced two finalists; and the finals, where one ultimate champion was crowned from these two teams.

For Season 16, can our Team 1 win the championship? Please find the maximum probability of Team 1 winning the entire tournament.

More specifically, there are $$$8$$$ teams participating in a single-elimination tournament. Each team $$$i$$$ has two strength values $$$a_i$$$ and $$$b_i$$$.

Before the tournament starts, you need to assign each team to a distinct seed from $$$1$$$ to $$$8$$$. The tournament follows the standard single-elimination bracket format:

• Round 1: seed $$$1$$$ vs seed $$$2$$$, seed $$$3$$$ vs seed $$$4$$$, seed $$$5$$$ vs seed $$$6$$$, seed $$$7$$$ vs seed $$$8$$$
• Round 2: winner of $$$(1,2)$$$ vs winner of $$$(3,4)$$$, winner of $$$(5,6)$$$ vs winner of $$$(7,8)$$$
• Round 3 (Final): winner of upper bracket $$$(1,2,3,4)$$$ vs winner of lower bracket $$$(5,6,7,8)$$$

When two teams compete against each other, the team with the smaller seed number uses its $$$a$$$-value as its strength, and the team with the larger seed number uses its $$$b$$$-value as its strength. If a team with strength $$$x$$$ competes against a team with strength $$$y$$$, the probability that the first team wins is $$$\frac{x}{x + y}$$$.

You need to find the maximum probability of team $$$1$$$ winning the entire tournament, considering all possible assignments of teams to seeds.