Both Alice and Bob have a set of real numbers, and both sets are the union of some disjoint closed intervals. They will independently pick a real number uniformly at random from their own set, and you need to calculate the expected absolute difference between the two real numbers.

More formally, given a set of real numbers $$$S = \bigcup\ [l,r]$$$, picking a real number $$$x$$$ from the set $$$S$$$ uniformly at random means that $$$P(x \in [l_1, r_1]) = P(x \in [l_2, r_2])$$$ holds for any two intervals $$$[l_1, r_1], [l_2, r_2] \subseteq S$$$ with the same length, i.e., $$$r_1 - l_1 = r_2 - l_2$$$.

Given an integer $$$n$$$, you need to find a string of length $$$n$$$ containing only $$$0$$$s and $$$1$$$s that maximize the number of different nonempty substrings.

Given an integer sequence $$$a_1, a_2, \ldots, a_n$$$ and a positive integer $$$d$$$, you need to clamp the sequence to a range $$$[l,r]$$$ satisfying $$$0 \le r-l \le d$$$ that maximize $$$\sum_{i=1}^{n-1}|a_i - a_{i+1}|$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

More specifically, clamping the sequence to the range $$$[l,r]$$$ makes each element

$$$$$$ a_i := \left\{ \begin{array}{rcl} l, & a_i \lt l; \\ a_i, & l \le a_i \le r; \\ r, & a_i \gt r. \\ \end{array} \right. $$$$$$

Both $$$l$$$ and $$$r$$$ are arbitrary real numbers decided by you under the given constraints. It can be shown that the maximum sum is always an integer.

The League of Legends Worlds Championship, Worlds for short, is the culminating event in the LoL Esports season and decides the ultimate global League of Legends Champion.

Worlds 2022 has been a great tournament thus far. We have seen the legend, Faker, rise once more and the surprise of the DRX run. There have also been massive collapses from other teams like Gen.G and JDG. Regardless, we are in for a compelling Worlds 2022 Finals, which kicks off on November 6 at 08:00 (UTC+8) in San Francisco as DRX and T1 face off.

Being the clear favorite for winning the Finals, T1 has performed dominantly in most games and has found its stride coming into the tournament. They have taken down RNG and JDG, two LPL heavyweights, and are now poised to add another trophy to their cabinet.

On the other side, DRX has practically come out of nowhere. From almost not making Worlds 2022, fighting their way through the Regionals and Play-ins to the Finals. It is a Cinderella run that DRX is on, and they have been doubted at every step of the tournament. With a lot to prove and Deft reaching the Finals in his swan song, winning the trophy might be the best send-off any player can wish for.

As we countdown to a battle for the all-new trophy, you will be given the predicted result of the Finals and required to find which team wins the championship under the prediction. A team must win three out of five games to win the championship, so the predicted result of the Finals is a string of length $$$5$$$ containing only $$$\text{D}$$$s, $$$\text{T}$$$s, and $$$\text{?}$$$s. The $$$i$$$-th character in the string points out who wins the $$$i$$$-th game, where $$$\text{D}$$$ means DRX wins the game, $$$\text{T}$$$ means T1 wins the game, and $$$\text{?}$$$ means no more games are needed since some team has already won $$$3$$$ games and become the champion.

Given a simple connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges, you may add as many edges (possibly zero) as you want and count the number of different ways modulo $$$998\,244\,353$$$ to make the graph biconnected while keeping it simple. Two ways of adding edges are considered different, if and only if there exists at least an edge $$$(u,v)$$$ added in one way and not added in the other.

Note that:

• A simple graph contains no self-loops and no multiple edges.
• For any two different vertices in a connected graph, there always exists at least a path from one vertex to the other.
• For any two different vertices in a biconnected graph, there always exist two or more paths sharing no common edges from one vertex to the other.

Figure: a simple graph, a connected graph, and a biconnected graph

As shown above, the graph on the left is simple but not connected because the $$$3$$$rd vertex can't reach any other vertex by a path, while the graph in the middle is connected but not biconnected because it's impossible to find two paths sharing no common edges from the $$$3$$$rd vertex to any other vertex.

Given two integers $$$n$$$ and $$$m$$$, you need to construct a matrix $$$M$$$ satisfying the following constraints:

• The number of rows and columns of $$$M$$$ are $$$n$$$ and $$$m$$$ respectively.
• The matrix contains only $$$0$$$s and $$$1$$$s, namely, $$$M_{i,j} \in \{0, 1\}$$$ for all $$$1 \le i \le n$$$ and $$$1\le j \le m$$$.
• The number of mixed subrectangles equals to the number of pure subrectangles. The subrectangles that contain both $$$0$$$s and $$$1$$$s are considered as mixed subrectangles, otherwise pure subrectangles. Note that a subrectangle is an intersection of some consecutive rows and some consecutive columns.

If multiple solutions exist, print any one of them. If there is no solution, report it.

Byteland has $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$, and $$$n-1$$$ bidirectional roads and $$$n-1$$$ bidirectional railways connecting them. For each pair of cities, one can always arrive one from another one through the roads only, and the same thing also holds for the railways.

Alice and Bob are planning $$$q$$$ long journeys in Byteland. In each journey, Alice starts from the $$$a$$$-th city and then visits some other cities through the roads only, while Bob starts from the $$$b$$$-th city and then visits some other cities through the railways only. Both of them will finally reach the same destination city without visiting any cities more than once. You need to find the maximum total length of their journey routes among all the selections of the destination city.

Given $$$n$$$ strings $$$S_1, S_2, \ldots S_n$$$, you need to calculate the number of different P-P-Palindromes given by these $$$n$$$ strings.

A palindrome is a string that can be read the same from left to right and from right to left. For example, "a", "level", and "otto" are palindromes, while "aab" and "icpc" are not.

A P-P-Palindrome is an ordered pair of nonempty palindromes $$$(P, Q)$$$ such that both $$$P$$$ and $$$Q$$$ are the substrings of some in $$$S_1, S_2, \ldots S_n$$$ and $$$P + Q$$$ is also a palindrome. Here $$$P + Q$$$ means concatenating $$$P$$$ and $$$Q$$$ in order, or more specifically, let $$$P = p_1 p_2 \ldots p_{|P|}$$$ and $$$Q = q_1 q_2 \ldots q_{|Q|}$$$, then $$$P + Q = p_1 p_2 \ldots p_{|P|} q_1 q_2\ldots q_{|Q|}$$$, where $$$|S|$$$ is the length of string $$$S$$$.

Note that two P-P-Palindromes are considered different if and only if $$$P$$$ differs or $$$Q$$$ differs.

There is a shop selling $$$n$$$ types of quartz in Byteland. Only two pieces of each type of quartz will be on sale every day, and the second piece will be on sale only after the first piece has been sold.

Two wizards Alice and Bob are collecting these $$$n$$$ types of quartz to strengthen their wand. Due to the quartz shortage, they reach an agreement that either of them buy only one piece of each type each day.

Both of them wants to minimize their own cost each day. To reflect fairness, Alice buys one piece of quartz first, and then Bob and Alice buy two pieces in turn until only one piece remains. The one who still hasn't collected all types of quartz buys the last piece.

In each of the following $$$m$$$ days, the prices of the two pieces of one type of quartz will change permanently, and Alice wants to know the minimum cost for her to collect all types of quartz if both Alice and Bob take the best strategy on the first day and each of the following $$$m$$$ days.

Night falls, neon flickers, and the crowd shouts. As the grand show in the Moon Theater begins, Calatonia, a city of assorted anthropomorphic animals, feels ready for a sleepless night. Over the years since its revival, the annual show has never failed to ignite animals' passion for music, mainly due to the various genres it includes. So this time, it adds more attractive elements, such as dance!

If you inquire of some creature in Calatonia about the best dance troupe, they are most likely to answer: Icy Cold Predators Crew (ICPC). Its performance will be a highlight of tonight's show without doubt. And you may overhear how Referee — well, that's his name — led the troupe to its peak. As the director, Referee starts every day by selecting background music and gets busy with choreographing in the afternoon. Before sleep, he tends to make dazzling costumes which are of little use in such a world actually. The routine is exhausting, but he somehow enjoys it.

Referee considers himself a born perfectionist. That's true when it comes to formation design. Offstage, he arranged the whole crew into a matrix of $$$n$$$ rows and $$$m$$$ columns, numbering rows $$$1,2,\ldots,n$$$ from front to back and columns $$$1,2,\ldots,m$$$ from left to right. The species of each dancer can be labeled as a positive integer not more than $$$3 \times 10^6$$$, where there may be animals of identical species. Two arrangements are different if and only if there exists at least a position where the species of dancers in the two arrangements are different.

Unsatisfied with the initial arrangement, Referee intends to reorder the crew without breaking its matrix formation. He thinks it's a good idea to adjust by showing cards. Certainly not red cards — Referee, after all, does not serve as a referee. Instead, he prepared white cards with $$$1,2,\ldots,n$$$ written on them respectively and black cards with $$$1,2,\ldots,m$$$, and commanded the crew to do as follows:

• Once Referee shows the white card with $$$k$$$ ($$$1 \le k \le n$$$), all dancers in the $$$k$$$-th row count off from $$$1$$$ to $$$m$$$ from left to right. Those who count an even number immediately move to the right end of the row. Lastly, align to keep the matrix formation.
• Once Referee shows the black card with $$$k$$$ ($$$1 \le k \le m$$$), all dancers in the $$$k$$$-th column count off from $$$1$$$ to $$$n$$$ from front to back. Those who count an even number immediately move to the back end of the column. Lastly, align to keep the matrix formation.

Figure: Referee shows the white card with 2

Referee can show any card any number (possibly zero) of times he wants, and your task is to calculate the number of different arrangements he may obtain, modulo $$$998\,244\,353$$$ since it could be extremely large.

Recently a museum of arts in Byteland is open to the public. The museum is modeled as a polygon, and there is an art placed on each vertex of the polygon.

A group of thieves are coveting the arts in the museum and they have chosen at least two arts to steal from the museum at night when all is still. After sneaking into the museum, each of them will work on stealing one of the chosen art simultaneously.

To be on the safe side, the thieves have chosen the arts in such a manner that every two thieves can see each other, i.e., every point of the straight line segment between them lies in the interior or on the boundary of the museum, when they are working on stealing the arts.

You, the administrator of the museum, need to anticipate the thieves' actions, i.e., compute the number of different sets of the arts that might be chosen by the thieves, to ruin their plans. The answer could be extremely large, so you only need to output it modulo $$$998\,244\,353$$$.

One day, Alice and Bob are playing an online chess game named "Tavern Chess", where each player can choose at most $$$7$$$ minions to build a team.

Welcome to Tavern

Each minion has its Hit Points (HP) and Attack (ATK), and the HP is the same as the ATK initially. A minion with positive HP is alive and can take attacks, and it dies immediately if its HP becomes zero or lower after an attack.

The battle begins after both Alice and Bob finish building their team and lasts until all the minions from one team are dead and the other team wins. In case the last alive minions from the two teams die simultaneously, the battle ends in a tie.

Alice and Bob's teams take turns to attack, and the team that has more minions takes the first attack. In case of a tie, it will be decided by a coin toss — $$$50\%$$$ probability for Alice taking the first attack and the remaining $$$50\%$$$ probability for Bob taking the first attack.

When a team takes the attack, the leftmost minion taking the minimum number of attacks from the team attacks one of the alive minions from the other team uniformly at random, and then the other team takes the attack.

If a minion with the HP $$$h_1$$$ and the ATK $$$a_1$$$ attacks another minion with the HP $$$h_2$$$ and the ATK $$$a_2$$$, each minion deals damages equal to its ATK to the other one, so the attacker minion will have the HP $$$h_1 - a_2$$$ and the attacked minion will have the HP $$$h_2 - a_1$$$ after the attack.

Given Alice's team and Bob's team, you need to calculate the probabilities that Alice's team wins the battle, Bob's team wins the battle, or the battle ends in a tie, respectively.

In the center of the Summer Triangle nestles a little fox, a constellation named Vulpecula, to be precise. It is situated in a zone with numerous brilliant stars, but it itself is relatively faint. Even the brightest star in the constellation has an apparent magnitude of merely 4.44. However, despite its dimness, Vulpecula captures the attention of many stargazers for various reasons. Say, Mu, the protagonist of our problem, regards Vulpecula as his favorite constellation because there, he can always see his own reflection.

Mu lives a stressful life and only by viewing stars can he find some relief. Every night, he would climb onto the roof, watching skyward with his telescope and identifying constellations of all shapes. While admiring the cosmic wonder, he would occasionally write down some thoughts that crossed his mind. And this night started with a strange question: "What in the world are dreams for?"

Thoughtfully, Mu looked up at the starry fox as the past experience came reeling through his head. Although recent years have been even rougher, his striving for dreams has never diminished all the way. He gave up money because he should not overvalue it. He gave up prestige because he could not maintain it. He gave up the place he longed to settle because he did not deserve it. He gave up everything but...

"Dreams are like the stars, distant and sometimes insignificant, yet enough to spark up the darkest night." Mu jotted it down on a note and squeezed a smile, before immersing himself in the joy of stargazing again.

The Constellation Vulpecula

Now, let's get back to the problem. People have associated constellations with animals and mythological characters since ancient times. Giving free rein to their imagination, they drew straight lines between the stars on a chart and conceived the story behind every constellation. Suppose there are $$$n$$$ stars numbered from $$$1$$$ to $$$n$$$ in Vulpecula with $$$n-1$$$ imaginary lines connecting them. Namely, for each pair of stars $$$(s,t)$$$, there always exists a sequence of stars $$$u_0,u_1,\ldots,u_k$$$ where $$$u_0 = s$$$ and $$$u_k = t$$$, satisfying that star $$$u_{i-1}$$$ and star $$$u_{i}$$$ are linked by a line for each $$$i=1,2,\ldots,k$$$, and the distance between star $$$s$$$ and star $$$t$$$ is defined as the minimum $$$k$$$ among all such sequences.

Mu is prepared to view those stars in Vulpecula, and he will focus his telescope on one of the $$$n$$$ stars. Detailed observation, however, requires advanced technology as there will be several obstacles.

One is that some stars may be too tiny to observe. To tackle it, Mu can screw a knob to zoom in or out. Specifically, after selecting the focused star, he will adjust the focal distance to an integer $$$d$$$ between $$$0$$$ and $$$n-1$$$ and see all stars whose distance from the focused star is not more than $$$d$$$.

The other is that some stars may be too faint to observe. Luckily, Mu can use filters to regulate the rays of a star. Let $$$a_i$$$ represent the visibility of star $$$i$$$ which is initially $$$0$$$. A filter denoted as $$$(i,x)$$$ only applies to star $$$i$$$, and when Mu installs it, $$$a_i$$$ will become $$$a_i \oplus x$$$, where $$$\oplus$$$ denotes the bitwise exclusive-OR operation. Mu can pick a set of filters he has got and install them in arbitrary order. He may also pick no filters or two or more identical filters.

For a pleasant stargazing experience, Mu will make the visibilities of the stars in sight equal and maximized. Playing with a telescope is quite easy, whereas your task is not so simple. Suppose $$$f(d)$$$ is the maximum visibility under a certain focal distance $$$d$$$. Can you calculate the sum of $$$f(d)$$$ over $$$d = 0,1,\ldots,n-1$$$ modulo $$$2^{64}$$$ for each star if it is the focused star?