Multi-Heads Cup, or MHC for short, is a worldwide programming contest made for the participants with many many heads. The Chief Judge of the competition, Little Cyan Fish, is considering to design an identification number for each participant.

"And that's it," Little Cyan Fish thought, "Let's use some bracket sequences!" He assigned a unique balanced bracket sequence to each participant, with two kinds of the brackets - the round brackets (also known as parentheses), and the square brackets. To make sure you understand the concepts of balanced bracket sequence, Little Cyan Fish prepared a formal definition of the balanced bracket sequence:

• $$$\varepsilon$$$ (an empty string) is a balanced bracket sequence.
• If $$$A$$$ is a balacned bracket sequence, then $$$(A)$$$ and $$$[A]$$$ are both balanced bracket sequences.
• If $$$A$$$ and $$$B$$$ are balanced bracket sequences, then $$$AB$$$ is also a balanced bracket sequence.

For example, "()", "[()]" and "[()]()" are balanced bracket sequences, but ")(", "[(])" and "[)" are not.

For our multi-headed participants, memorizing a bracket sequence is not a difficult task. However, the challenge lies in their unique ability: because they have too much heads, they can't discern the direction of each bracket! Consequently, compared to the original balanced bracket sequence, they might recall the sequence with some brackets changing their directions. For example, the bracket sequence "[()]()" might be memorized as "]))]))" or "]()]))". Fortunately, the type of brackets are guaranteed to remain unchanged.

On the contest day, as Little Cyan Fish receives each participant's bracket sequence, a question arises: Can the original bracket sequence be deduced uniquely? In other words, Little Cyan Fish needs to determine if the provided bracket sequence maps to exactly one balanced bracket sequence.

Please, help Little Cyan Fish to finish this task, so our multi-heads friends will be able to participate in the contest!

After successfully solving the problem Cut Cut Cut!, Little Cyan Fish seeks to further hone his skills in partitioning connected components within graphs.

One day, Little Cyan Fish is challenged by a mysterious sage with a unique problem. He is presented with an unrooted tree containing $$$n$$$ vertices and is given an integer $$$k$$$. Let $$$E$$$ represent the set of all edges in the tree. Little Cyan Fish's objective is to identify a subset $$$E' \subseteq E$$$. Upon removing all edges in $$$E'$$$, the graph should split into several connected components, each with a size of either $$$k$$$ or $$$(k+1)$$$.

As an expert in partitioning, Little Cyan Fish adeptly solves this problem. However, the mysterious sage's curiosity extends beyond mere mastery. He seeks to explore all potential outcomes. Consequently, he tasks Little Cyan Fish with determining the total number of different ways to select $$$E' \subseteq E$$$ while adhering to the stated condition. Two ways are considered different if the selected subsets of edges are different.

Please help Little Cyan Fish to finish this challenge. As the answer may be large, you only need to provide the answer modulo $$$998\,244\,353$$$.

The much-anticipated Universal Cup Final is around the corner! Little Cyan Fish is busy preparing the venue for the competition. To make the venue gorgeous, Little Cyan Fish is planning to hang some light bulbs.

Little Cyan Fish has $$$m$$$ wires and plans to connect $$$n$$$ light bulbs using these wires. Each wire needs to connect two distinct bulbs and make all the bulbs form a single connected component. To maintain safety, for any two bulbs there can be at most one wire connecting them directly, and no more than $$$d$$$ wires can be attached to a single bulb.

Once the bulbs are connected, Little Cyan Fish wants to illuminate some of them. Given that active bulbs generate heat, positioning two lit bulbs adjacent to each other could be dangerous. Therefore, if two bulbs are directly connected by a wire, they must not be illuminated at the same time. On the other hand, he doesn't want too few lights on, so he does not want to see an unlit bulb, such that all bulbs directly connected to it are also unlit.

This leads Little Cyan Fish to wonder about the number of different plans to turn on those bulbs to fulfill the requirements. More so, he is keen on finding the optimal way to connect all the light bulbs to maximize the number of the feasible lighting plans.

Given the integers $$$m$$$ and $$$d$$$, your goal is to assist Little Cyan Fish in determining the optimal way to connect $$$n$$$ bulbs using all $$$m$$$ wires, with the intent of maximizing the number of the ways to illuminate the bulbs. Note that you have to determine the value of $$$n$$$ by yourself.

Let $$$f(x)$$$ be the largest digit in the decimal representation of a positive integer $$$x$$$. For example, $$$f(4523) = 5$$$ and $$$f(1001) = 1$$$.

Given four positive integers $$$l_a$$$, $$$r_a$$$, $$$l_b$$$ and $$$r_b$$$ such that $$$l_a \le r_a$$$ and $$$l_b \le r_b$$$, calculate the maximum value of $$$f(a + b)$$$, where $$$l_a \le a \le r_a$$$ and $$$l_b \le b \le r_b$$$.

After writing the paper Sandpile Prediction on Structured Undirected Graphs, Little Cyan Fish wants everyone to solve more graph theory tasks. "We cannot survive without graph theory problems, and everyone should come to do the sandpile prediction!"

A bipartite graph is a graph whose vertices can be divided into two disjoint sets $$$U$$$ and $$$V$$$, such that every edge in the graph connects a vertex in $$$U$$$ to one in $$$V$$$. If the number of vertices in $$$U$$$ and $$$V$$$ are the same, then this graph is called a balanced bipartite graph.

A matching in an undirected graph is a set of edges, in which any two edges have no common vertices. A maximum matching of the graph is a matching containing the largest possible number of edges. The matching number of a graph is the number of edges in its maximum matching.

Now, Little Cyan Fish gives you a balanced bipartite graph. You are asked to count the number of ways to add exactly one edge between a vertex in $$$U$$$ and a vertex in $$$V$$$, such that the matching number of the graph is increased.

A long time ago, Little Cyan Fish prepared a programming contest with his best friend Little $$$\mathcal{F}$$$. They proposed $$$n$$$ problems in total, indexed with the integers from $$$1$$$ to $$$n$$$. The $$$i$$$-th problem ($$$1 \leq i \leq n$$$) has a difficulty rating $$$a_i$$$.

Time flies fast. It has been fifteen months since their contest. Instead of being a participant in the Informatics Olympiad, Little Cyan Fish has transitioned into a coach. But they once had a pact to run a series of championships together.

Little Cyan Fish didn't forget about it.

Now, Little Cyan Fish would like to group these $$$n$$$ problems into several training activities. To ensure the stories in the statements of the tasks are consistent, Little Cyan Fish wants to divide these $$$n$$$ tasks into several intervals. A dividing plan of the problems can be represented by a sequence of integers $$$0 = r_0 \lt r_1 \lt r_2 \lt \cdots \lt r_k = n$$$, meaning that there will be $$$k$$$ training activities, and the $$$i$$$-th training activity will contain all tasks whose indices are between $$$(r_{i - 1} + 1)$$$ and $$$r_i$$$ (both inclusive).

Furthermore, Little Cyan Fish doesn't want an activity to be too unbalanced. If there is a hard problem in an activity, then the activity needs to contain more problems. Formally, if task $$$j$$$ is in the $$$i$$$-th activity (i.e. $$$r_{i - 1} \lt j \leq r_i$$$), then the inequality $$$r_i - r_{i - 1} \geq a_j$$$ must hold.

Little Cyan Fish is interested in how many ways he could divide the problems to satisfy all the requirements above, denoted by $$$f(a)$$$. This question is easy for him, so Little Cyan Fish calculated it easily.

One day before the activities, Little Cyan Fish suddenly realized that those problems were too hard for the participants. Therefore, he came up with a new easy problem with a difficulty rating of only $$$1$$$. He is wondering, for each $$$1 \leq j \leq n$$$, if we define the sequence $$$a^{(j)}$$$ in the following way, what is the value of $$$f(a^{(j)})$$$.

$$$$$$a^{(j)}_i = \begin{cases}1 & i = j \\ a_i & \text{otherwise}\end{cases}$$$$$$

Since the value of $$$f(a^{(j)})$$$ can be extremely large, you only need to output it modulo $$$998\,244\,353$$$.

After studying the paper Solving Sparse Linear Systems Faster than Matrix Multiplication by Richard Peng, and Santosh Vempala, Little Cyan Fish becomes obsessed with anything that is sparse. For example, a sparse matrix. Here, a sparse matrix refers to a matrix in which the number of zero elements is much higher than the number of non-zero elements. Now, Little Cyan Fish comes up with a problem about binary sparse matrices and he wants you to try solving it.

Given a binary matrix (a matrix containing only $$$0$$$s and $$$1$$$s) with $$$r$$$ rows and $$$c$$$ columns, you can choose whether to reverse each row or not. Find the number of ways to choose a set of rows to reverse (it is allowed not to choose any row), so that every column has at most one $$$1$$$. Two ways are considered different if a row is chosen in one of them but not the other.

By reversing a row, we mean this: Let the elements on the $$$i$$$-th row be $$$b_{i, 1}, b_{i, 2}, \cdots, b_{i, c}$$$ from the first column to the last column. If you reverse the $$$i$$$-th row, it becomes $$$b_{i, c}, b_{i, c - 1}, \cdots, b_{i, 1}$$$.

After writing the paper Faster Algorithms for Internal Dictionary Queries, Little Cyan Fish and Kiwihadron decided to write this problem.

Let $$$\text{lcp}(s,t)$$$ be the length of the longest common prefix of two strings $$$s = s_1 s_2 \dots s_n$$$ and $$$t = t_1 t_2 \dots t_m$$$, which is defined as the maximum integer $$$k$$$ such that $$$0 \le k \le \min(n,m)$$$ and $$$s_1 s_2 \dots s_k$$$ equals $$$t_1 t_2 \dots t_k$$$.

Little Cyan Fish gives you a non-empty string $$$s=s_1 s_2 \dots s_n$$$. Let $$$f(s)=\sum\limits_{i=1}^{n} \text{lcp}(s, \text{suf}(s, i))$$$, where $$$\text{suf}(s, i)$$$ is the suffix of $$$s$$$ starting from $$$s_i$$$ (i.e. $$$\text{suf}(s, i) = s_i s_{i+1} \dots s_n$$$). Note that in this problem, the alphabet contains $$$n$$$ letters, not just $$$26$$$.

For each $$$i = 1, 2, \cdots, n$$$, you are asked to answer the following query: if you MUST change $$$s_i$$$ to another different character $$$c$$$ ($$$c \ne s_i$$$), choose the best character $$$c$$$ and calculate the maximum value of $$$f(s^{(i)})$$$, where $$$s^{(i)}=s_1 \dots s_{i-1} c s_{i+1} \dots s_n$$$.

After learning the strange sorting algorithm in the problem Paimon Sorting of The 2021 ICPC Asia Nanjing Regional Contest, Little Cyan Fish comes up with the following task.

Given a sequence $$$a_1, a_2, \cdots, a_n$$$ which is a permutation of $$$n$$$, your task is to sort the permutation in ascending order by applying the following operation for at most $$$\lfloor \frac{n}{2} \rfloor$$$ times: Choose two indices $$$l$$$ and $$$r$$$ satisfying $$$1 \le l \lt r \le n$$$ and $$$a_l \gt a_r$$$, and then sort $$$a_l, a_{l + 1}, \cdots, a_r$$$ in ascending order.

Recall that a permutation of $$$n$$$ is a sequence of length $$$n$$$, in which each integer from $$$1$$$ to $$$n$$$ (both inclusive) appears exactly once. Also recall that $$$\lfloor x \rfloor$$$ indicates the largest integer less than or equal to $$$x$$$.

Given two straight line segments on a two-dimensional Cartesian plane, you need to pick a point uniformly at random on each of them and calculate the expected Euclidean distance between the two picked points.

TEN is an exciting push-your-luck and auction board game. Players may push their luck to draw more cards and use currency to buy additional cards in their attempt to build the longest number sequence in each color. Here let's consider a related problem to the game.

Photo by @freethemeeple on Instagram

Given a sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$, we say its continuous subarray $$$a_l, a_{l + 1}, a_{l + 2}, \cdots, a_r$$$ is a rainbow subarray if $$$a_{i + 1} - a_i = 1$$$ for all $$$l \le i \lt r$$$. Specifically, a subarray of length $$$1$$$ is always a rainbow subarray.

You can perform at most $$$k$$$ operations. Each operation allows you to increase or decrease an element in the sequence by one. Calculate the maximum possible length of the longest rainbow subarray after performing the operations.

Please note the UNUSUAL MEMORY LIMIT of this problem.

Ticket to Ride is a railway-themed German-style board game. In the game, players collect and play train cards to build railroads across the map. Points are earned based on the length of the built routes, and whether the player can connect distant cities which are determined by drawing ticket cards.

Photo by @garyjames on BoardGameGeek

Consider a one-dimensional version of the game. There are $$$(n + 1)$$$ cities arranged in a row, numbered from $$$0$$$ to $$$n$$$ from left to right. For each $$$1 \le i \le n$$$, you can connect city $$$(i - 1)$$$ and city $$$i$$$ by placing a railroad between them.

There are $$$m$$$ ticket cards which reward the player for connecting cities. The $$$i$$$-th card can be represented by three integers $$$l_i$$$, $$$r_i$$$ and $$$v_i$$$, indicating that if city $$$l_i$$$ and $$$r_i$$$ are connected through railroads (that is, for all $$$l_i \lt j \le r_i$$$, there is a railroad placed between city $$$(j - 1)$$$ and $$$j$$$), you will gain $$$v_i$$$ points.

For each $$$1 \le k \le n$$$, calculate the maximum points you can gain if you place exactly $$$k$$$ railroads. If you fail to gain any reward then you get $$$0$$$ points.

This is a story about Kevin, a friend of Little Cyan Fish.

Kevin is the chief judge of the International Convex Polygon Championship (ICPC). He proposed a geometry task for the contest. However, since he is inexperienced in computational geometry, he couldn't generate a correct convex polygon for the tests of the task.

Kevin was very saddened by this. His good friend, Little Cyan Fish, consoled him by saying, "Although the data you generated is not a convex polygon, you can call it an almost-convex polygon!"

Given a set of points $$$S$$$ (containing at least $$$3$$$ points) in a two-dimensional plane, where no two points coincide and no three points are collinear. Little Cyan Fish calls a polygon $$$P$$$ an almost-convex polygon, if and only if:

• The polygon $$$P$$$ is simple, i.e., its vertices are distinct and no two edges of the polygon intersect or touch, except that consecutive edges touch at their common vertex.
• The vertices of the polygon belong to $$$S$$$, and all points in $$$S$$$ are either inside or on the boundary of the polygon.

Let $$$\mathbb{U}$$$ be the set consisting of all almost-convex polygons. It can be shown that $$$\mathbb{U}$$$ is a finite set and is not empty. Therefore, there exists a polygon $$$R$$$ such that $$$|R|$$$ is the minimum among all polygons in $$$\mathbb{U}$$$ ($$$|R|$$$ is the number of vertices of polygon $$$R$$$).

Kevin and Little Cyan Fish want you to calculate the number of polygons $$$Q \in \mathbb{U}$$$ such that $$$|Q| \le |R| + 1$$$.