The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The $$$i$$$-th edge connects vertex $$$u_i$$$ and vertex $$$v_i$$$ with traversal cost $$$w_i$$$.

Now, you may increase the traversal cost of all edges simultaneously by $$$k$$$, where $$$k$$$ is any non-negative real number. Question: how many distinct $$$^{\dagger}$$$ paths from vertex $$$1$$$ to vertex $$$n$$$ exist such that there is at least one value of $$$k$$$ for which that path is one of the shortest paths from $$$1$$$ to $$$n$$$?

$$$^{\dagger}$$$ Two paths are considered different if and only if they have different numbers of edges, or there exists an index $$$i$$$ such that the $$$i$$$-th edge on the two paths has a different edge index.

You are given an ellipse on a 2D plane defined by the standard equation:

$$$$$$ \frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 $$$$$$

where $$$a$$$ and $$$b$$$ are positive real numbers representing the semi-major and semi-minor axes.

You are also given a line in the plane defined by the linear equation:

$$$$$$ y = kx + c $$$$$$

Your task is to compute the area of the larger part when the line divides the ellipse into two regions.

The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Given a tree with $$$n$$$ nodes, there are $$$q$$$ queries.

In the $$$i$$$-th query, a sequence $$$a=(a_1,a_2,\dots,a_k)$$$ without duplicate elements is given. Initially:

• Node $$$a_j$$$ is labeled with $$$j$$$;
• Other nodes are labeled with $$$0$$$ (this label does not expand).

Then labels keep propagating as follows:

• Propagation proceeds in the order $$$1,2,\dots,k,1,2,\dots$$$ in an infinite cycle;
• When label $$$x$$$ propagates: if a node has a neighbor labeled $$$x$$$, then that node is immediately overwritten to $$$x$$$; existing labels can be overwritten;
• Propagation is sequential, i.e., only the current $$$x$$$ is processed at a time, the result takes effect immediately, and then the next $$$x+1$$$ is processed.

We are interested in, for each label $$$j$$$, the maximum number $$$t_j$$$ of nodes labeled $$$j$$$ at any time during the whole process (including the initial state and after any propagation step).

Little-L has a box divided into an $$$n \times m$$$ grid of cells.

Initially, all cells are empty. You can perform several operations, each of which can be one of the following two types:

1. Choose a cell and place a small ball in every empty cell in the same row and the same column as the chosen cell.
2. Choose a cell and place a small ball in every empty cell on the two diagonals passing through the chosen cell.

For example, in a $$$5 \times 5$$$ box, choosing cell $$$(3,4)$$$ for either the first or the second operation would yield the following results:

The left figure shows the first operation, and the right figure shows the second operation.

Little-L wants to know: what is the minimum number of operations needed to fill all cells in the box with balls?

Note: You can perform an operation on a cell that already contains a ball.

The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Today, Alice wants to fill a permutation of length $$$n \times m$$$$$$^{\dagger}$$$ into an $$$n \times m$$$ matrix $$$A$$$, such that the sum of numbers in any contiguous submatrix with both height and width at least $$$2$$$ is a composite number.

In other words, for any $$$1 \leq a \lt c \leq n, 1 \leq b \lt d \leq m$$$, Alice wants $$$\sum_{i=a}^{c} \sum_{j=b}^{d} A_{i,j}$$$ to be a composite number.

For example, when $$$n=2$$$ and $$$m=3$$$, matrix $$$B$$$ is a valid construction, while matrix $$$C$$$ is not, because $$$C_{1,2}+C_{1,3}+C_{2,2}+C_{2,3}=17$$$.

$$$$$$ B = \begin{bmatrix} 1 & 3 & 2 \\ 6 & 5 & 4 \end{bmatrix}, \quad C = \begin{bmatrix} 1 & 6 & 2 \\ 3 & 5 & 4 \end{bmatrix} $$$$$$

Given $$$n$$$ and $$$m$$$, can the above requirement be satisfied? If yes, output one valid construction.

$$$^{\dagger}$$$ A permutation of length $$$n$$$ is an array containing the integers from $$$1$$$ to $$$n$$$ exactly once in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, while $$$[1,2,2]$$$ is not (since $$$2$$$ appears twice), and $$$[1,3,4]$$$ is not (since $$$n=3$$$ but the array contains $$$4$$$).

To train your ability to calculate huge numerical values, $$$Irelia$$$ requires you to perform $$$n$$$ operations. Let $$$a_i$$$ denote the result produced by the $$$i$$$-th operation.

Each operation is one of the following four forms:

• = v: assign $$$a_i = v$$$.
• + j k: assign $$$a_i = a_j + a_k$$$.
• * j k: assign $$$a_i = a_j \times a_k$$$.
• ^ j k: assign $$$a_i = a_j^{a_k}$$$.

After each operation, output the value of $$$a_i$$$ modulo $$$m$$$.

Please note that the modulo operation is only applied to the answer, and the actual value of $$$a_i$$$ may be huge.

The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Given a road of length $$$l$$$ kilometers. The road is divided into $$$n$$$ segments, each with its own speed limit. The $$$i$$$-th segment starts at distance $$$a_{i-1}$$$ kilometers from the road's start, ends at distance $$$a_i$$$ kilometers from the road's start, and has a speed limit of $$$v_i$$$ kilometers per hour.

Bob drove through the entire road. There are $$$m$$$ cameras on the road; the $$$i$$$-th camera is located at position $$$x_i$$$ kilometers from the road's start, and recorded Bob passing it at time $$$t_i$$$ hours after Bob departed from the start. Bob finally took $$$t_{end}$$$ hours to reach the end of the road.

Cameras themselves do not measure speed, but by combining Bob's passing times at multiple cameras, the traffic police may deduce that Bob must have sped on some segments. Suppose there are two cameras at positions $$$x_a$$$ and $$$x_b$$$. If driving from $$$x_a$$$ to $$$x_b$$$ while always traveling at the maximum allowed speed takes $$$t_0$$$ hours, and $$$t_b - t_a \lt t_0$$$, then Bob must have sped on some part of the road between them. (Ignore time spent accelerating or decelerating.)

Now Bob wants to know the minimum number of camera records that must be removed so that the police cannot deduce that Bob definitely sped on any segment. Note: the records at the road's start and end cannot be removed; the police always know when Bob entered and left the road.

Link has a sequence of length $$$n$$$ consisting of positive integers $$$a$$$.

Link wants to know how many subarrays of this sequence have a sum that is a prime number. In other words, how many pairs $$$(l,r)$$$ ($$$1 \leq l \leq r \leq n$$$) satisfy $$$\sum_{i=l}^{r} a_i$$$ being a prime number.

The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Alice has a sheet of paper; some region on the paper contains important information, but the paper was torn into two pieces by Bob. Assuming the tear is random, Alice wants to know the probability that the important information is completely preserved in one of the two halves.

Formally:

There is an $$$n\times m$$$ sheet of paper on the plane, and the coordinate system partitions it into unit square grid cells. There is a "critical region" on the paper — a closed rectangle with vertices $$$(a,b)$$$, $$$(a,d)$$$, $$$(c,d)$$$, $$$(c,b)$$$, where

$$$$$$ 0 \leq a \lt c \leq n,\quad 0 \leq b \lt d \leq m. $$$$$$

Now Bob will tear the paper along a "legal path" from $$$(0,0)$$$ to $$$(n,m)$$$, and this path is chosen uniformly at random among all legal paths. A legal path means a lattice path from $$$(0,0)$$$ to $$$(n,m)$$$ where each step is either to the right (increase $$$x$$$ by $$$1$$$) or up (increase $$$y$$$ by $$$1$$$). Such a path necessarily divides the whole sheet into a "upper-left" part and a "lower-right" part. For convenience, a path that leaves one part empty is also considered legal.

We care whether the critical region is cut by this tearing path. If the entire closed rectangle of the critical region lies exactly on one side of the path (either entirely in the "upper-left" part or entirely in the "lower-right" part), we say the "critical region remains intact"; otherwise, it is considered cut by the tearing path.

We ask: among all possible legal paths, what is the probability that the "critical region remains intact"? Give the result modulo $$$998244353$$$ $$$^{\dagger}$$$.

$$$^{\dagger}$$$ Formally, let $$$M = 998\,244\,353$$$. It can be shown the answer can be expressed as a reduced fraction $$$\frac{p}{q}$$$ with integers $$$p,q$$$ and $$$q \not\equiv 0\pmod{M}$$$. Output the integer $$$p\cdot q^{-1}\bmod M$$$. In other words, output an integer $$$x$$$ with $$$0\le x \lt M$$$ such that $$$x\cdot q \equiv p \pmod{M}$$$.

The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Little L broke into a mysterious underground palace.

On the tightly closed palace door, Little L saw an inscription telling him that to open the door he needs to construct several convex polyhedra whose surfaces are tiled only by regular triangles and squares of side length $$$1$$$, and that a total of $$$x$$$ regular triangles and $$$y$$$ squares must be used.

Over time the power of the door has weakened. Now you only need to answer whether there exists at least one construction scheme such that the constructed several convex polyhedra satisfy the above conditions.

Note:

• A polyhedron is called convex if for any two points inside the polyhedron the segment joining them lies entirely inside the polyhedron.
• Each face of a convex polyhedron may be composed of several squares and regular triangles.

You are given a string $$$s = s_1 s_2 \dots s_n$$$ consisting of lowercase English letters.

For $$$1 \leq i \leq j \leq n$$$, let $$$s_{i,j}$$$ be the substring of $$$s$$$ from position $$$i$$$ to $$$j$$$ inclusive.

Consider the integer points on the number line: $$$0, 1, \dots, n$$$. From a position $$$x$$$, you may move to another position $$$y$$$ if and only if the substring $$$s_{\,\min(x,y)+1,\; \max(x,y)}$$$ is a palindrome.

You are given $$$q$$$ queries. In the $$$i$$$-th query, you start at position $$$a_i$$$. For each query, determine the minimum number of moves required to reach either position $$$0$$$ or position $$$n$$$.