At the Tournament of Progressive Combos, better known as TOPC, fighters compete to land the legendary TOPC Crit.

Each attack combo produces three damage values: $$$a$$$, $$$b$$$, and $$$c$$$. Three values form an arithmetic progression if the difference between every pair of consecutive values is the same. In other words, they must satisfy $$$$$$ b-a=c-b. $$$$$$ This shared difference is called the common difference.

A combo triggers a TOPC Crit if and only if its three damage values form an arithmetic progression in the given order. When it does, their common difference $$$x$$$ is known as the secret.

Find this value. It is, indeed, the game's top secret.

Triglycerides are the main components of animal and plant fats, acting as essential substances for energy storage in the human body. Chemically, all triglycerides are formed by combining one glycerol molecule with three fatty acid molecules.

The physical and chemical properties of fats mainly depend on their connected fatty acid chains. Based on the structure of these chains, we can classify fats into two main categories: saturated fat and unsaturated fat.

If we know the total number of carbon (C), hydrogen (H), and oxygen (O) atoms in a triglyceride molecule, we can directly use simple mathematical rules to determine whether it is a saturated or unsaturated fat without needing specialized laboratory instruments.

For a triglyceride completely devoid of carbon-carbon double bonds (i.e., a saturated fat). Derived from the chemical degree of unsaturation formula, the number of carbon atoms ($$$c$$$) and hydrogen atoms ($$$h$$$) of a saturated triglyceride must strictly satisfy the following linear relationship: $$$$$$ h = 2c - 4 $$$$$$ If the number of hydrogen atoms is less than this standard (i.e., $$$h \lt 2c - 4$$$), it indicates the presence of extra carbon-carbon double bonds in the carbon chain, meaning it is an unsaturated fat.

(Note: This problem guarantees that all input test data represents valid triglyceride molecules, and the number of oxygen atoms ($$$o$$$) will always be 6.)

Now, please write a program that reads the C, H, and O atomic counts of several compounds to classify them accordingly.

Madoka was originally an ordinary student who went to school happily every day. However, one day she was suddenly persuaded to become a magical girl, and thus began her endless battles against enemies to protect the world.

The transportation network of this world is shaped like a complete $$$k$$$-ary tree with $$$l$$$ levels. Her base is located in Central City, which is located at the root node (level $$$1$$$), and all enemies lurk at the leaves (level $$$l$$$). Every non-leaf node has exactly $$$k$$$ children, which are ordered from left to right as its $$$1$$$-st, $$$2$$$-nd, $$$\dots$$$, $$$k$$$-th child, exactly as they are drawn in the picture below. Given $$$k$$$ and $$$l$$$, we can determine the total number of nodes in the tree (denoted $$$S$$$), which is at most $$$10^6$$$. Below is an example transportation network with $$$k = 3$$$ and $$$l = 4$$$, where $$$S=40$$$:

Over time, Madoka has already completed $$$n$$$ enemy extermination missions sequentially. For each mission, she started her journey from Central City.

However, the enemies are not the only threat. There exists a special kind of mysterious "white rabbit" in this world that Madoka finds extremely annoying and difficult to deal with. To conserve her precious magical energy for the actual battles, Madoka actively chooses which enemy to hunt based on the safest route. She evaluates the routes to all leaves and always selects a root-to-leaf path that contains the minimum total number of white rabbits along the way.

Several different paths may share this minimum total, so Madoka fixes her route in the following deterministic way. She walks down from the root one node at a time. Standing at a non-leaf node $$$v$$$, she looks at every child $$$c$$$ of $$$v$$$ that keeps her on a path of the minimum total (that is, the number of white rabbits on the road from $$$v$$$ to $$$c$$$, plus the minimum number of white rabbits on a path from $$$c$$$ down to a leaf of $$$c$$$'s subtree, is as small as possible among all children of $$$v$$$), and she always steps into the leftmost such child, that is, the one with the smallest index among them. She repeats this until she arrives at a leaf.

Unfortunately, these white rabbits have a strange affinity for magical girls and are strongly attracted to Madoka's magical trail. After she completes the $$$i$$$-th mission, her residual magic instantly triggers a rapid multiplication of the creatures. Specifically, on every single road segment that Madoka just traveled across during that mission, the number of white rabbits permanently occupying that road increases by $$$w_i$$$. (Initially, the world was peaceful, and there were $$$0$$$ white rabbits on all roads.)

As the missions pile up, the network becomes increasingly congested with these white rabbits. Madoka needs to know how bad the situation has eventually become. Determine the total number of white rabbits Madoka will inevitably encounter on her chosen path during her NEXT ($$$n+1$$$)-th extermination mission.

Yuki likes listening to music. She has $$$n$$$ favorite songs, numbered from $$$1$$$ to $$$n$$$.

She created two playlists, and each playlist contains each of these $$$n$$$ songs exactly once. In the first playlist, the $$$i$$$-th song is song $$$a_i$$$. In the second playlist, the $$$i$$$-th song is song $$$b_i$$$.

Whenever Yuki wants to listen to music, she chooses one of the two playlists and starts playing it from the first song. She may stop after any song finishes, but she will never stop in the middle of a song. In other words, each time she listens to music, she chooses one of the two playlists and listens to a non-empty prefix of it.

A year has passed, and Yuki's music system reports that song $$$i$$$ was listened to exactly $$$c_i$$$ times in total. However, Yuki suspects that this statistic may be incorrect. Please determine whether there exists some possible listening history such that, for every song $$$i$$$, the total number of times song $$$i$$$ was listened to is exactly $$$c_i$$$. Note that Yuki may not have listened to any music at all last year.

Barbara has a garden, represented as an $$$n \times n$$$ grid. She has bought $$$n^2$$$ slabstones indexed from $$$1$$$ to $$$n^2$$$ and placed them in her garden, so she can enjoy stepping slabstones from one to another every day. The slabstones are arranged in row-major order, that is, the slabstone at cell $$$(i, j)$$$ is indexed $$$(i - 1) \times n + j$$$.

Barbara would like to redesign her garden, so she invited Babara, a famous interior designer. After careful consideration, Barbara suggests that the slabstone at cell $$$(i, j)$$$ should be indexed $$$a_{ij}$$$. They will use the following "elegant" process to rearrange the slabstones:

1. Color each slabstone either red or blue.
2. Shift the red slabstones within each row (so they can only move left or right).
3. Shift the blue slabstones within each column (so they can only move up or down).

However, there is an important restriction: Any two slabstones with the same color should remain non-overlapping during the rearrangement of the slabstones. Note that a red slabstone and a blue slabstone can temporarily overlap (but in order to have the desired garden, they should not overlap at the end).

Now Barbara wants to know whether they can rearrange the slabstones as desired.

In a tourist archipelago consisting of $$$n$$$ islands, there are $$$m$$$ bidirectional bridges connecting them. The islands are numbered $$$1, 2, \ldots, n$$$. The $$$i$$$-th bridge connects islands $$$u_i$$$ and $$$v_i$$$, and it takes $$$t_i$$$ minutes to cross. Furthermore, each bridge has a height $$$h_i$$$, representing its height above sea level in centimeters.

An unprecedented natural disaster has struck the archipelago, causing the sea level to rise at a rate of $$$1$$$ centimeter per minute. A bridge $$$i$$$ becomes unusable exactly $$$h_i$$$ minutes after the disaster begins. To ensure safety, a vehicle can only cross bridge $$$i$$$ if the entire traversal completes before the bridge is submerged. Specifically, if a vehicle starts crossing bridge $$$i$$$ at time $$$T$$$, it must arrive at the other end by time $$$T + t_i$$$, and this arrival time must satisfy $$$T + t_i \le h_i$$$.

Island $$$1$$$ serves as the evacuation center. Residents on each island are intelligent; they will choose a route that allows them to reach island $$$1$$$ safely before any bridge they cross becomes submerged. If no such path exists, they will remain on their current island to await rescue.

Given this scenario, for each island $$$k$$$ (where $$$k \in \{1, \ldots, n\}$$$), determine if the residents on island $$$k$$$ can safely reach island $$$1$$$.

Class leader A-Ming is arranging the $$$n$$$ students of his class into a single row to take a graduation photo. The $$$n$$$ students all have distinct heights, and A-Ming holds a roster listing the real height of every student.

The students were already standing in some order. For fun, A-Ming handed each student a slip of paper and asked everyone to look to their right and compute one number: how many of the people standing behind them (i.e. to the right in the row) are shorter than they are? Everyone wrote down their number and handed the slip back. The slips were originally collected in left-to-right order of the row (the first slip belongs to the student standing first, and so on).

Then a sudden gust of wind scattered all the slips on the ground! A-Ming gathered them back up, but their order was completely lost, leaving only an unordered collection of numbers $$$s_1, s_2, \ldots, s_n$$$.

The photographer is about to arrive and everyone has run off to play. A-Ming is left holding only the height roster and the shuffled pile of slips.

Help A-Ming decide: is it possible to reconstruct at least one valid standing order consistent with the numbers on the slips? If so, to make the picture look as harmonious as possible, output the lexicographically smallest height arrangement among all valid orders (placing shorter students as far toward the front as possible). If the numbers cannot fit together at all, output -1.

Fridgeberg is a well-known veteran in the Taiwanese ICPC community. He specializes in counting problems. Since he solves counting problems faster than everyone else, people call him a speed-counter. Today, he has prepared a challenge for you along with the following message.

"Yo, I'm Fridgeberg, and I'm an 18-year-old ICPC speed-counter from Yunlin, Taiwan. Today, I'm challenging you to a counting problem."

The challenge is as follows.

A rooted labelled tree with $$$n$$$ vertices is a tree with vertices labelled $$$1,2,\ldots,n$$$ and one vertex chosen as the root.

Recall that for any two vertices in a tree, there is a unique simple path connecting them. For each vertex $$$v$$$ in a rooted labelled tree, define its subtree as the set of all vertices $$$u$$$ such that $$$v$$$ is on the unique path from the root to $$$u$$$. In particular, a vertex is always in its own subtree. The subtrees of a tree are the collection of all vertices' subtrees.

A rooted labelled tree is $$$k$$$-free if none of its subtrees has exactly $$$k$$$ vertices.

For each $$$k$$$ from $$$2$$$ to $$$n-1$$$, compute the number of different rooted labelled trees with $$$n$$$ vertices that are $$$k$$$-free. Since the numbers can be very large, please compute them modulo $$$998244353$$$.

Two rooted labelled trees are different if at least one of the following holds:

• The labels of the roots are different.
• There exists an edge that is present in one tree but not in the other.

There is a circular track with $$$b$$$ equally spaced positions, numbered $$$0, 1, \dots, b-1$$$ clockwise. Adjacent positions are $$$1$$$ unit apart, so the whole circle measures $$$b$$$ units.

A marker starts at position $$$0$$$ and, at every step, advances by a fixed $$$a$$$ positions clockwise (wrapping back to $$$0$$$ after position $$$b-1$$$). It successively stops at $$$$$$p_k = (a \cdot k) \bmod b, \qquad k = 0, 1, \dots, n-1,$$$$$$ leaving a mark at each stop, for a total of $$$n$$$ marks. It is guaranteed that $$$\gcd(a, b) = 1$$$$$$^{\text{∗}}$$$ and $$$n \leq b$$$, so these $$$n$$$ marks are pairwise distinct.

These $$$n$$$ marks divide the circle into $$$n$$$ arcs. The length of an arc is the number of units it spans (every arc length is a positive integer, and the lengths sum to $$$b$$$).

How many distinct arc-length values are there? For each value, what is it, and how many times does it occur?

Elaina, a magic teacher, has prepared an exam with $$$t$$$ questions. In each question, given a target magic power $$$x$$$, a student must combine exactly two magic crystals with powers $$$2^{a}$$$ and $$$2^{b}$$$ for some non-negative integers $$$a$$$ and $$$b$$$ (possibly $$$a = b$$$), and report the minimum possible difference between the combined power and $$$x$$$, that is, $$$\left|2^{a} + 2^{b} - x\right|$$$. Please help the students finish the exam.

You have a grammar with the start symbol $$$S$$$, a set of variables $$$V$$$, a set of terminal symbols $$$T$$$, and a set of rules $$$P$$$. Every upper-case letter is a variable, so $$$V=\{A,\dots,Z\}$$$, and every lower-case letter is a terminal symbol, so $$$T=\{a,\dots,z\}$$$. A rule is of the form $$$A\to \alpha$$$, where $$$A\in V$$$ is a variable and $$$\alpha$$$ is a string consisting of variables and terminal symbols. The grammar never contains chain rules of the form $$$A\to B$$$, where the right side consists of a single variable. Rules of the form $$$A\to b$$$ are possible, where the right side consists of a single terminal.

A word can be derived by starting with $$$\alpha=S$$$ and then repeatedly choosing some variable $$$X$$$ in $$$\alpha$$$, some rule $$$X\to\beta$$$, and then replacing one $$$X$$$ in $$$\alpha$$$ with $$$\beta$$$. To be precise, if $$$\alpha=\alpha'X\alpha"$$$ and we have a rule $$$X\to\beta$$$, then we can replace $$$\alpha$$$ with $$$\alpha'\beta\alpha"$$$, and we write $$$\alpha\Rightarrow \alpha'\beta\alpha"$$$.

Here is a complete example. The grammar has the rules $$$$$$ S\to SA,\ \ \ S\to b,\ \ \ A\to bS,\ \ \ A\to a. $$$$$$ Then we can derive the word $$$bbb$$$ in four steps: $$$$$$ S\Rightarrow SA\Rightarrow bA\Rightarrow bbS\Rightarrow bbb. $$$$$$

On the other hand, the word $$$aaa$$$ cannot be derived.

Your task is to answer the following question for a grammar $$$G$$$ and a word $$$w$$$ (consisting of terminal symbols):

• Can you add zero or more terminal symbols at the beginning of $$$w$$$ and zero or more terminal symbols at the end of $$$w$$$ such that the resulting word $$$uwv$$$ can be derived by $$$G$$$?

The Park of Three is a famous landmark in the Kingdom of Three. It contains $$$n$$$ magical pillars connected by $$$m$$$ magical connections. The pillars are numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th connection links pillar $$$u_i$$$ and pillar $$$v_i$$$, and all connections are bidirectional.

Believing that the number three holds protective power against evil forces, the park's architects ensured that every pillar is incident to exactly three connections. Note that a connection may link a pillar to itself. In such cases, the self-loop counts twice toward the number of pillar's incident connections.

Triangles formed by the pillars are the source of their protective power. Historically, these triangles successfully repelled evil forces hundreds of years ago. To assess the network's true resilience, you must determine its structural vulnerability.

Formally, three distinct pillars $$$i, j, k$$$ form a triangle if the connections $$$(i, j)$$$, $$$(j, k)$$$, and $$$(k, i)$$$ all exist. When a pillar is destroyed, all connections incident to it are removed. The strength of the park is defined as the minimum number $$$s$$$ such that destroying $$$s$$$ specific pillars eliminates all triangles. Please determine the strength $$$s$$$ and output the indices of $$$s$$$ pillars such that there will be no triangles after destroying them.