Though Bob has finally returned to the college, he has to stay in his dorm with the other three roommates. Don't know who proposes.

"Let's play a game!"

It was meant to be light-hearted, and the rules are as follows:

• A roommate is designated in turn, and he writes down on paper the coordinates of $$$n$$$ points in three-dimensional Euclidean space.
• Each of the other roommates selects one of the $$$X$$$-axis, the $$$Y$$$-axis, and the $$$Z$$$-axis, but no two of them make the same choice. After that, each of them counts the number of points after projecting all written points along the direction of the chosen axis. Under the projection, some points may not be distinguishable. Points $$$(1, 2, 1)$$$ and $$$(1, 2, 5)$$$ projected along the direction of the $$$Z$$$-axis, for instance, are not distinguishable.
• The roommate with the most points counted will win the game. In case of a tie, the one with the most points counted whose selected axis has the smallest character in the alphabetical order will be the winner. Note that in the alphabetical order $$$X$$$ is less than $$$Y$$$, $$$Y$$$ is less than $$$Z$$$, and by transitivity, $$$X$$$ is less than $$$Z$$$.

Bob does want to win.

"Please help me; I entreat you."

Add flowers to brocade people, all over finish is; Give timely assistance and have several people?

Beacon towers are built throughout and alongside the Great Wall. There was once a time when there were $$$n$$$ beacon towers built from west to east for defending against the invaders. The altitude of the $$$i$$$-th beacon tower, based on historical records, is $$$a_i$$$.

The defenders divide strategically all beacon towers into $$$k$$$ parts where each part contains several, but at least one, consecutive beacon towers. The scale of an individual part is given by the difference between the highest and the lowest altitudes of beacon towers, and the most sensible partition maximizes the sum of scales of all parts.

As a historian, you are dying to know the maximum sums of scales for every $$$k = 1, 2, \ldots, n$$$.

A number sequence $$$[a_1, a_2, \ldots, a_n]$$$ is lucky if and only if the following requirements are fulfilled.

• Each element $$$a_i$$$ in the sequence is a non-negative integer such that $$$0 \leq \frac{a_i}{i} \lt \frac{\sqrt{5} + 1}{2}$$$;
• For any two elements $$$a_i$$$ and $$$a_j$$$ $$$(i \neq j)$$$ in the sequence, $$$a_i \neq 0$$$ and $$$a_j \neq 0$$$ imply that $$$a_i \neq a_j$$$.

Your task is to figure out how many number sequences of length $$$n$$$ are lucky and report the number modulo $$$998\,244\,353$$$.

Tom, an old rancher who manages $$$n$$$ farms, is planning several new roads to make his farms connected.

For this purpose, an architecture company provides $$$m$$$ building plans, each of which is described by three integers $$$a$$$, $$$b$$$ and $$$c$$$ representing that it would cost $$$c$$$ dollars to build a new road connecting the $$$a$$$-th and the $$$b$$$-th farms.

However, the final decision has to satisfy $$$q$$$ more constraints. A constraint contains two integers $$$u$$$ and $$$v$$$, which requires that Tom must choose at least one of the $$$u$$$-th and the $$$v$$$-th plans.

Because of a looming budget shortfall, Tom prefers to minimize the total cost.

In chemistry, isomerism is the phenomenon in which more than one compounds have the same chemical formula but different chemical structures. Chemical compounds that have identical chemical formulae but differ in properties and the arrangement of atoms in the molecule are called isomers.

Ethylene, which has a carbon-carbon double bond, is one of the most important fundamental chemicals in the petrochemical industry as it is the source material for a variety of products such as polyethene resin, ethylene glycol, vinyl chloride resin, acetic acid, styrene, and alpha-olefin which are produced by polymerization, oxidation, alkylation, hydration, or the addition of halogen. The precise format of an ethylene derivative is given in the figure below, where $$$R_1, R_2, R_3, R_4$$$ are atoms or atomic groups. We always suppose that $$$R_1$$$ and $$$R_2$$$ are on the same side of the carbon-carbon double bond, while $$$R_3$$$ and $$$R_4$$$ are on the other side. The carbon-carbon double bond in an ethylene derivative cannot rotate around the bond axis.

To distinguish isomers of the ethylene derivatives, two different naming methods, say Cis-Trans isomerism and Zasammen-Entgegen isomerism, are invented in the academic circle. The different scopes of application between these two methods are listed as follows:

• If a carbon atom connects with two identical atoms or atomic groups, isomerism of the given ethylene derivative does not exist; otherwise
• if some atoms or atomic groups connecting with carbon atoms are the same, the ethylene derivative is called Cis-Trans isomerism. If the two identical atoms or atomic groups lie on the same side (i.e. upside or downside in the figure above) of the carbon-carbon double bond, it is called Cis-isomerism, or else it is called Trans-isomerism;
• if the four atoms or atomic groups connecting with carbon atoms are pairwise distinct, the ethylene derivative is called Zasammen-Entgegen isomerism. If the atom or the atomic group of $$$R_1$$$ and $$$R_3$$$ with a higher priority and the atom or the atomic group of $$$R_2$$$ and $$$R_4$$$ with a higher priority lie on the same side (i.e. upside or downside in the figure above) of the carbon-carbon double bond, it is called Zasamman-isomerism, or else it is called Entgegen-isomerism.

All the atoms or atomic groups which may appear in $$$R_1$$$, $$$R_2$$$, $$$R_3$$$ and $$$R_4$$$ are listed as follows in descending order of the priority, the first of which is the one with the highest priority.

• -F, -Cl, -Br, -I, -CH3, -CH2CH3, -CH2CH2CH3, -H

Now, you are asked to determine if there is any isomerism for a given ethylene derivative and find out the naming method it fits for when possible.

In geometry, a convex polygon is a simple polygon (which is not self-intersecting) in which no segment joining a point to another one on the boundary goes outside the polygon. Equivalently, it is a simple polygon whose interior is a convex set.

Given $$$n$$$ distinct points on the plane, you may draw some segments such that:

• At least one segment is drawn.
• The length of each segment is positive and finite.
• Each endpoint of any segment belongs to the given set of points.
• For any two segments, they either share an endpoint or have no intersection.
• All segments form a convex polygon.

Let the area of the polygon be $$$A$$$, and let the sum of the squares of the lengths of segments be $$$B$$$. Your task is to maximize the ratio of $$$A$$$ to $$$B$$$.

Graduation season is approaching and it's time to take commemorative photos.

There are $$$n$$$ students in Bob's class, each assigned with a unique student number from $$$1$$$ to $$$n$$$, where the height of the student numbered $$$i$$$ is $$$h_i$$$. They want to take photos at the school gate and $$$q$$$ more memorable places. For each place, students will arrive in a known order, and, as they hope for more personal engagement, once a student arrived they take a new photo so that $$$n$$$ photos will be taken. After finishing all the $$$n$$$ photos at the place, students will go back to their dorms and set up a new time for the next place.

To make the queue orderly, every time students have to stand in a row in ascending order of their student numbers when taking a new photo, and the orderliness of the photo is defined as the sum of the squares of the height differences between every two neighbouring students in the row. Your task is to, for each place, calculate the sum of the orderlinesses of all the $$$n$$$ photos that are taken there.

Xiao Ming is an elementary school student. One day his math teacher instructed the students to create a series of special models, which are called "absolute space". Each model consists of many stars in the three-dimensional space and is associated with a special parameter $$$n$$$ claiming that for any star in the model, there exist exactly $$$n$$$ stars whose Euclidean distance to it is $$$1$$$.

For example, in the case of $$$n = 1$$$, you can create this model by drawing a line of length $$$1$$$, and then drawing the stars at the line's endpoints. Similarly, for $$$n = 2$$$, you can create this model by drawing a regular polygon (i.e. equilateral triangle, square and regular pentagon) with side length $$$1$$$, and then drawing the stars at the polygon's vertices. As you can see, there are infinite kinds of "absolute space".

In this class, the teacher taught them what kind of possibilities look like in the case of $$$n = 1, 2$$$, and their homework was to create a model for $$$n = 3$$$. Since the homework is too easy, Xiao Ming doesn't want to stop at these small cases. He spent a whole night reflecting on that and finally managed to find solutions applicable for any parameter $$$n$$$ $$$(= 1, 2, 3, 4, 5, \ldots)$$$. Furthermore, he found ways to shrink the number of stars when creating these models.

Such great progress brought him ecstasy, as well as insomnia. When he got up the next morning, he completely forgot how he got the idea, and his draft model had also collapsed due to the out-of-date glue he mistakenly used, so he has no proof to convince his teacher about what he has done. Could you please create a model for this poor little boy?

Given the parameter $$$n$$$, your task is to create any possible model such that the number of stars is not greater than a certain limit.

Millions of years ago, a very smart hyperspace race built a supercomputer, DeepThought. They gave DeepThought two positive integers $$$x$$$ and $$$y$$$, and let her calculate The Answer to Life, the Universe and Everything.

DeepThought didn't know how to calculate The Answer and she was in a hurry to watch TV, so she made a big integer using very complicated steps and no one would know how she got the result:

• Firstly, DeepThought chose an integer $$$a$$$ greater than $$$1$$$.
• Secondly, she calculated $$$\left(a^{F_x} - 1\right)$$$ and $$$\left(a^{F_y} - 1\right)$$$, denoted by $$$u$$$ and $$$v$$$ respectively, where $$$F_n$$$ is the $$$n$$$-th term of the Fibonacci sequence, given by the recursion: $$$F_1 = 1$$$, $$$F_2 = 1$$$ and $$$F_n = F_{n - 1} + F_{n - 2}$$$ for integer $$$n \ge 3$$$.
• Lastly, she computed the ratio of these two numbers' least common multiple $$$\mathrm{lcm}(u, v)$$$ to their greatest common divisor $$$\mathrm{gcd}(u, v)$$$ as The Answer, which is obviously an integer.

Since she has gone for leisure activities, the task to calculate The Answer is left to you. For the secrecy of The Answer, you are only asked to report The Answer modulo $$$m$$$.

Bob bought a new jigsaw puzzle yesterday. The puzzle consists of $$$m^2$$$ rectangular pieces, where each piece contains a unique number ranged from $$$1$$$ to $$$m^2$$$ used for identification and four associated numbers indicating the adjacent pieces.

Specifically, the piece numbered $$$i$$$ is described with four numbers $$$n_i$$$, $$$s_i$$$, $$$w_i$$$ and $$$e_i$$$, corresponding to four adjacent pieces: the piece numbered $$$n_i$$$ (resp., $$$s_i$$$, $$$w_i$$$ and $$$e_i$$$) lie on the north side (resp., south side, west side and east side). If an associated number is $$$-1$$$, no more piece would lie on the corresponding side.

Undoubtedly, the goal of this game is to arrange all pieces in the correct locations. The instruction says that the complete image is square, with $$$m$$$ rows and $$$m$$$ columns.

At this juncture, Bob is at the International Collegiate Programming Contest in Yinchuan. He has no time to solve the jigsaw puzzle but has to solve Problem K instead. Can you help him?

In the upcoming $$$n$$$ days, $$$n$$$ browser games will be released on a new website. According to the plan, the administrator will release a new game per day. Users have to open the corresponding URL (Uniform Resource Locator) and get feedback from the server to download a game.

However, the setup of the server uses unreadable legacy codes. Once a user somehow finds the URL of an unreleased game, the data of the game would leak out. To temporarily fix the problem, the administrator decided to add a series of confirmation prefixes, which are non-empty strings, at the server-side. The server will respond with the correct game data when the requested URL does correspond to a game (no matter released or unreleased) and at least one confirmation prefix is a prefix of the URL; otherwise, the server will declare that the game is not found.

To make the work easier, the administrator asks you to find the minimum number of confirmation prefixes the server required to avoid data leaks every time after a new game release.

There is an old country but called Sheep Village which contains $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$ and $$$m$$$ bidirectional roads, each of which connects two different cities.

In Sheep Village, cities are connected through roads. That is, you can always find a path from a city to any other city through some roads. Besides, each road here belongs to at most one simple circuit, where a simple circuit is a set of roads that forms a cyclic path $$$u_1 \to u_2 \to \ldots \to u_m \to u_1$$$ $$$(m \geq 1)$$$ without passing a city more than once. Note that the cyclic paths $$$a \to b \to c \to a$$$, $$$b \to c \to a \to b$$$ and $$$a \to c \to b \to a$$$ correspond to the same circuit.

There are $$$k$$$ sheep living in Sheep Village and also $$$k$$$ lurking wolves. Once all sheep fall asleep, the lurking wolves, led by the wolf king, will launch a blitzkrieg for their static prey. Quietly running through a road does cost energy. For the sake of energy-saving, the wolf king hopes for the best assignments for each wolf to catch a distinct sheep such that the total energy consumed in catching sheep is as small as possible.

As a brilliant strategist as well as a wolf, it's time for you to make the decision to meet the king's requirement.

It may seem that the story is usual. A warrior is trying to save the princess caught in the tower. But this is not a usual ordinary story. Well, this story is even not from this game.

Tower of the Sorcerer appears to be RPG-style; you have a strength (STR) and a health bar showing the health points (HP), and so do all the monsters. When you engage a monster, you and the monster take turns hitting each other until one falls, and you go first. Each attack will cause damages that make the health point of the one being attacked decreased by the strength of the attacker. A character falls if its health point drops to zero or lower after an attack.

As an excellent hacker and a player manipulating the warrior, you set your initial health point as infinity. There are $$$n$$$ monsters inside the tower. You can fight against the monsters in any order. After defeating a monster, you can set your strength to the strength of the defeated monster.

What is the minimum total amount of damages you will receive?