Caden has come to understand "fate" in his own way. Leaving theater behind, he wants to use a string to represent his life through synecdoche. But in seeking a pure, original expression true to himself, he again falls into an infinite loop of self-reference. This time, Caden leaves the choice to you: portray his life for him.

Caden's synecdoche is a string $$$T$$$ of length $$$L$$$. We call $$$T$$$ valid if and only if all three conditions below hold:

1. $$$T$$$ consists only of lowercase English letters.
2. For every $$$i = 1, 2, \ldots, K$$$, the character of $$$T$$$ at position $$$p_i$$$ must equal the given character $$$c_i$$$, where $$$1 \le p_i \le L$$$ and $$$c_i$$$ is a lowercase letter.
3. For every $$$i = 1, 2, \ldots, N$$$, the given string $$$s_i$$$ must not occur as a contiguous substring of $$$T$$$.

Given $$$L$$$, $$$K$$$ position constraints $$$(p_i,c_i)$$$, and $$$N$$$ forbidden substrings $$$s_i$$$, count all valid strings $$$T$$$. Output the answer modulo $$$998\,244\,353$$$.

Your AIMC Lab has developed an entirely new three-dimensional quantum matrix!

Consider a three-dimensional grid of size $$$N \times M \times H$$$, with coordinates $$$1 \le x \le N$$$, $$$1 \le y \le M$$$, and $$$1 \le z \le H$$$. A qubit occupies every integer grid point. Let $$$(x_u,y_u,z_u)$$$ be the coordinates of qubit $$$u$$$.

For any two qubits $$$u$$$ and $$$v$$$, define their squared spatial distance as $$$$$$ d^2(u, v) = (x_u - x_v)^2 + (y_u - y_v)^2 + (z_u - z_v)^2. $$$$$$

The system has eight energy matrices $$$A_{D,c}$$$, each of size $$$N \times M \times H$$$, indexed by integers $$$0 \le D \le 3$$$ and $$$0 \le c \le 1$$$.

You may initialize each qubit to either basis state $$$|0\rangle$$$ or $$$|1\rangle$$$. Its corresponding basis-state value is $$$c_P=0$$$ or $$$c_P=1$$$.

After initialization, the total energy is calculated as follows:

• For each integer pair $$$0 \le D \le 3$$$, $$$0 \le c \le 1$$$, qubit $$$P$$$ gains $$$A_{D,c}(x_P,y_P,z_P)$$$ energy if and only if:
  • The basis-state value of $$$P$$$ satisfies $$$c_P=c$$$.
  • For every qubit $$$Q$$$ with $$$d^2(P,Q)=D$$$, the value $$$c_P+c_Q+D$$$ is even.

As the chief scientist of AIMC Lab, initialize every qubit to a basis state so that the system's total energy is maximized. Output this maximum energy.

You are given two arrays $$$a$$$ and $$$b$$$, each of length $$$n$$$.

Choose any $$$k \in [0,n]$$$ and concatenate the first $$$k$$$ elements of $$$a$$$ with the last $$$n-k$$$ elements of $$$b$$$ to form a new array of length $$$n$$$.

Select exactly $$$m$$$ pairwise nonadjacent elements from the new array. Let $$$p$$$ be the smallest selected element. Maximize $$$p$$$.

Construct a set of $$$n$$$ points in the Euclidean plane such that:

• The absolute values of both coordinates of every point are at most $$$10^5$$$;
• Each coordinate of every point becomes an integer when multiplied by $$$10^{13}$$$;
• The distance between any two points is at least $$$10^{-4}$$$;
• At least $$$\left\lfloor \frac12 n\log_2 n-n \right\rfloor$$$ distinct unordered pairs of points have distance in $$$[1-10^{-9},1+10^{-9}]$$$.

We often simplify the square root of a large integer into radical form; for example, $$$\sqrt{432}=12\sqrt3$$$.

Define the number-theoretic function $$$f(n)=\min\{a \mid n=ab^2,\ a,b\in\mathbb N\}$$$ on $$$\mathbb N$$$. In other words, $$$f(n)$$$ is the smallest natural number $$$a$$$ satisfying the equation. Such an $$$a$$$ always exists.

You are given $$$q$$$ queries, each specifying $$$l$$$ and $$$r$$$. For each query, find $$$\sum_{i=l}^r f(i)$$$ modulo $$$998\,244\,353$$$.

You are given $$$n$$$ quadratic inequalities, each of the form

$$$$$$ a_i x^2 + b_i x + c_i \gt 0 $$$$$$

It is guaranteed that $$$a_i \lt 0$$$ for every $$$1 \le i \le n$$$.

Determine whether there is an integer $$$x$$$ satisfying all $$$n$$$ inequalities simultaneously.z

This is a communication problem. Pay attention to its unusual constraints.

That was long ago, in a past forgotten by all of ECUST...

In that forgotten age, Zhulin and Qianwai fought side by side, lived together, and gazed up at the same stars. Later, sand buried their language, oceans severed their roads, and even their names faded from history. Only the vast, silent star chart above them remained: public, radiant, and unchanging. Yet nobody knew which stars they had once quietly joined into a message.

This problem has $$$20$$$ test cases.

You are given an undirected graph $$$G=(V,E)$$$ with $$$|V|=2000$$$ and $$$|E|=43\,600$$$. It has no multiple edges or self-loops and is generated as follows. Initially, $$$G$$$ has $$$|V|$$$ vertices and no edges. Then, $$$|E|$$$ times, the generator uniformly chooses one of the vertex pairs not yet joined by an edge and adds an undirected edge between them.

Your program will be run twice:

First run

In the first run, you play Zhulin. Choose and output $$$n$$$ induced four-cycles in $$$G$$$. They may share vertices.

• Definition of an induced four-cycle: Choose $$$4$$$ vertices of $$$G$$$ that have exactly $$$4$$$ edges among them, forming a simple cycle. In particular, there are no diagonals.

Second run

In the second run, you play Qianwai. The judge has your complete output from the first run. For each of $$$q$$$ queries, it selects one of your four-cycles, deletes one of its vertices, and gives you the other three vertex numbers. Report the index of the four-cycle in Zhulin's output from which they came.

Consider an $$$n \times m$$$ grid. Each cell has one of three states:

1. / (forward-slash mirror): reflects on both sides. A ray turns $$$90^\circ$$$, connecting the top with the left and the bottom with the right.
2. \ (backslash mirror): reflects on both sides. A ray turns $$$90^\circ$$$, connecting the top with the right and the bottom with the left.
3. . (empty cell): contains no obstacle. A ray passes straight through, connecting the top with the bottom and the left with the right.

Initially, some cells contain fixed / or \ mirrors; the rest are empty. You may leave each initially empty cell empty, replace it with a / mirror, or replace it with a \ mirror.

The outside boundary of the grid consists of $$$2(n+m)$$$ unit-length segments. A ray may enter or leave only perpendicularly through the midpoint of one of these segments.

Given an entry point and a target exit point, determine whether the grid can be filled legally so that a ray entering at the specified point, after straight-line travel and reflections, exits at exactly the target point.

If possible, output a valid completed grid that minimizes the number of cells traversed by the ray from the entry point to the target exit point. Count one traversal each time the ray enters a cell; repeated visits to the same cell are counted separately. If there are multiple optimal completions, output any of them. Otherwise, report that it is impossible.

There are $$$n$$$ crystals numbered $$$1$$$ through $$$n$$$ from left to right. Crystal $$$i$$$ initially contains $$$a_i$$$ units of energy. You may collect all $$$n$$$ crystals in any order.

When you collect crystal $$$i$$$:

• You add its current energy to your total score.
• If $$$i \gt 1$$$ and crystal $$$i-1$$$ has not yet been collected, its current energy changes sign.
• If $$$i \lt n$$$ and crystal $$$i+1$$$ has not yet been collected, its current energy changes sign.

The crystals' numbers do not change as you collect them.

What is the maximum total score after collecting all $$$n$$$ crystals?

To prove that he is never late for class, Thirstarfish insists that he entered the classroom at $$$7{:}110$$$ for a class beginning at $$$8{:}00$$$. This inspires a "generalized time notation."

In generalized time notation, a time is written $$$A{:}B$$$, where $$$A,B$$$ are nonnegative integers.

We define two equivalence rules for generalized times:

1. For any $$$B \ge 60$$$, $$$A{:}B$$$ and $$$(A+1){:}(B-60)$$$ represent the same instant.
2. For any $$$A \ge 24$$$, $$$A{:}B$$$ and $$$(A-24){:}B$$$ represent the same instant.

A time $$$h{:}m$$$ is a "standard time" if and only if $$$0 \le h \lt 24$$$ and $$$0 \le m \lt 60$$$.

Given a generalized time, find the unique equivalent standard time.

In the Euclidean plane, you are given a polygon $$$P=P_0P_1\cdots P_{n-1}$$$ whose vertices are listed in counterclockwise order.

An angle $$$\alpha$$$ ($$$0 \le \alpha \lt \pi$$$) is a stable direction if and only if there exists a $$$c \in R$$$ such that, for every point $$$X$$$ in polygon $$$P$$$ (including its boundary), the perpendicular segment from $$$X$$$ to the line $$$$$$ \cos \alpha\,x + \sin \alpha\,y + c = 0 $$$$$$ lies entirely in $$$P$$$ (including its boundary). Here $$$\alpha$$$ is a direction of the line's normal vector.

Find the number of stable directions. This number can be shown to be finite.

Maddy is still purging Baddy's evil army... for the third time!

The game takes place on an infinite Cartesian plane, which you may imagine as an infinite chessboard. Baddy controls $$$n$$$ stationary cannons, placed at $$$(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$$$.

Under Chinese chess rules, a cannon attacks by jumping over a screen. If cannons $$$A$$$ and $$$B$$$ share a row or column and exactly one other cannon $$$C$$$ lies between them, $$$A$$$ attacks $$$B$$$ (and $$$B$$$ attacks $$$A$$$). Cannon $$$C$$$ is their "screen."

At each step, Maddy may destroy a cannon that is not currently attacked by any other cannon. The destroyed cannon is immediately removed; it can no longer attack or serve as a screen.

Maddy wants to destroy all $$$n$$$ cannons. Does there exist an order of destruction that clears the board?

Your trident has struck a villager again. This time, when the trial ends, you discover that you can no longer find it.

You know that the trident landed on a rooted tree $$$T$$$ with $$$n$$$ vertices, rooted at vertex $$$1$$$. Each vertex has a weight $$$a_i$$$, and at every moment these weights form a permutation of $$$1 \sim n$$$. For vertices $$$u,v$$$, let $$$P(u,v)$$$ be their simple path, including both $$$u$$$ and $$$v$$$.

A set $$$S$$$ of tree vertices is a trident if and only if there exist three vertices $$$F,x,y$$$ (which may be equal) satisfying:

• $$$F$$$ is an ancestor of $$$x$$$, or $$$F=x$$$;
• $$$F$$$ is an ancestor of $$$y$$$, or $$$F=y$$$;
• $$$S = P(F,x)\cup P(F,y)$$$；

Process $$$q$$$ operations in order. There are three types:

Operation 1: Lightning. Given vertices $$$x$$$ and $$$y$$$, swap their current weights.

Operation 2: Judgment. Given two distinct weights $$$l \lt r$$$, reverse the weights within $$$[l,r]$$$.

Formally, if vertex $$$x$$$ has weight $$$a_x$$$ before this operation and $$$a'_x$$$ afterward, define $$$$$$ a'_x= \begin{cases} l+r-a_x, & l\le a_x\le r,\\ a_x, & \text{otherwise}. \end{cases} $$$$$$

Then set $$$a_x\leftarrow a'_x$$$ simultaneously for every integer $$$1 \le x \le n$$$. The weights remain a permutation of $$$1 \sim n$$$.

Operation 3: Find the trident. Given $$$l \le r$$$, determine whether $$$S=\{x\in N,\ 1\le x\le n\mid l\le a_x\le r\}$$$ is a trident.

Answer all questions from Operation 3 in order.