A string $$$A = a_1 a_2 \cdots a_n$$$ of length $$$n$$$ is a concatenation of $$$n$$$ characters $$$a_1, a_2, \ldots, a_n$$$, and its length is denoted by $$$|A|$$$. Similarly, the concatenation of two strings $$$A = a_1 a_2 \cdots a_n$$$ and $$$B = b_1 b_2 \cdots b_m$$$ is $$$a_1 a_2 \cdots a_n b_1 b_2 \cdots b_m$$$, denoted by $$$A + B$$$.

The edit distance between two strings $$$A = a_1 a_2 \cdots a_n$$$ and $$$B = b_1 b_2 \cdots b_n$$$ of the same length $$$n$$$ is the number of indices $$$i$$$ such that $$$a_i \neq b_i$$$.

We call the string $$$A$$$ formed by the first $$$k$$$ characters of another string $$$B$$$ ($$$k \leq |B|$$$) as the $$$k$$$-th prefix of $$$B$$$, and a string $$$P$$$ as an almost prefix of another string $$$Q$$$ if $$$|P| \leq |Q|$$$ and the edit distance between $$$P$$$ and the $$$|P|$$$-th prefix of $$$Q$$$ is at most $$$1$$$.

Given two strings $$$S$$$ and $$$T$$$ consisting of lowercase English letters, you are asked to find all ways to split $$$S$$$ into many parts such that each part is a non-empty almost prefix of string $$$T$$$, and then report the sum of the squared number of parts of all ways in modulo $$$998244353$$$. More formally, let $$$S = P_1 + P_2 + \ldots + P_n$$$ be a possible way, you are asked to calculate $$$$$$\left(\sum_{\substack{S = P_1 + P_2 + \ldots + P_n \\ \forall_{i=1, 2, \ldots, n} P_i\text{ is an almost prefix of }T}}{n^2}\right) \bmod 998\,244\,353\text{.}$$$$$$

You are going to explore a cave full of beautiful beads. The cave consists of $$$n$$$ rooms labeled by $$$1,2,\dots,n$$$, connected by $$$(n-1)$$$ bidirectional tunnels like a tree. In the $$$i$$$-th room, there is exactly one bead colored $$$c_i$$$.

The cave is not owned by you, so your actions are restricted. Before your entrance to the cave, you need to select two rooms $$$x$$$ and $$$y$$$ (maybe $$$x=y$$$), and submit your application to the owner. Then you can enter the cave at the $$$x$$$-th room, and walk along the shortest path from the $$$x$$$-th room to the $$$y$$$-th room. Every time you visit a new room, including the first room $$$x$$$ and the last room $$$y$$$, you can choose to either pick the bead in that room up or not. Finally, you need to concatenate all the beads that you picked up into a string according to the order you picked them up. You must ensure the colors of each bead in the string is palindromic, otherwise you are not allowed to take these beads back home. Note that a string is palindromic if and only if it reads the same from left to right and vice versa.

You want to make the palindromic string as long as possible. What's the maximum possible number of beads that you can take away?

A clique of a graph $$$G$$$ is a set $$$X$$$ of vertices of $$$G$$$ with the property that every pair of distinct vertices in $$$X$$$ are adjacent in $$$G$$$. You are given an undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges, please find the number of distinct non-empty cliques of graph $$$G$$$.

Given a sequence of integer $$$f_0, f_1, \ldots, f_{n-1}$$$, the discrete Fourier transform gives a sequence of complex numbers $$$F_0, F_1, \ldots, F_{n-1}$$$ that

$$$$$$ F_t = \sum_{s=0}^{n-1} f_s\ e^{-2 \pi i s t / n}$$$$$$

for each $$$t=0,1,\ldots,n-1$$$, where $$$e^{i\theta} = \cos \theta + i \sin \theta$$$, and $$$i$$$ is the imaginary unit that $$$i^2=-1$$$.

You may reset $$$f_k$$$ to any integer value to minimize the maximum value among $$$|F_0|, |F_1|, \ldots, |F_{n-1}|$$$, where $$$|z|=|p+qi|=\sqrt{p^2+q^2}$$$ $$$(p, q \in \mathbb{R})$$$ is the modulus of the complex number $$$z$$$.

You are developing a type of lunar exploring robot. Now the robot is under experiment on a large field. The field can be regarded as an infinite 2D plane. Initially, the robot is at $$$(0,0)$$$. Then it will execute $$$n$$$ commands sequentially. Each command can be represented as a single upper-case English letter:

• "L": Move from $$$(x,y)$$$ to $$$(x-1,y)$$$.
• "R": Move from $$$(x,y)$$$ to $$$(x+1,y)$$$.
• "D": Move from $$$(x,y)$$$ to $$$(x,y-1)$$$.
• "U": Move from $$$(x,y)$$$ to $$$(x,y+1)$$$.

Note that there are some obstacles on the field except the origin point $$$(0,0)$$$. When the robot is trying to move to the next position, it will check whether there is an obstacle at the target coordinate. If there is an obstacle, the robot will stay at the current position, mark the current command as executed, and continue executing the following commands.

You have sent $$$n$$$ commands to the robot, but unfortunately, due to some bugs, the map of the field and the position of the robot can not be transmitted to you. Assume the robot has finished executing all the $$$n$$$ commands. Before going to the field, you are wondering which places may you find the robot. Please write a program to find all the possible positions the robot will finally locate at.

The memory limit of this problem (4 megabytes) is unusual!

There are many islands separated by the Byte Ocean. Clever people invented the flying ship such that they can travel to other lands. Today, millions of salesmen gather at Byteland to celebrate the annual international trading festival. You are maintaining the trading database here. Initially, the database is empty, then $$$q$$$ events will happen, each is one of the following two types:

• "1 x y w" ($$$1\leq x,y,w\leq 10^9$$$): A new good is on sale. It is from the $$$x$$$-th island, its type is numbered as $$$y$$$, and its price is $$$w$$$. Note that two goods can share the same type but from different islands.
• "2 x y" ($$$1\leq x,y\leq 10^9$$$): It is a query event. A salesman from the $$$x$$$-th island with the $$$y$$$-th type of good is searching for other types of goods from other islands. You need to report the price of the most expensive good, which is not from the $$$x$$$-th island, and the type of which is not $$$y$$$. When there is no finding, please report "0" instead. This is only for searching, the good that you find will not be deleted from the database.

Due to the low level of technology in Byteland, the space of the database is very limited, but you still need to maintain the database efficiently.

For any positive integer $$$x$$$, its $$$m$$$-based representation is a string of digits $$$d_{n - 1} d_{n - 2} \cdots d_1 d_0$$$ where $$$x = \sum_{i = 0}^{n - 1}{d_i m^i}$$$, $$$0 \lt d_{n - 1} \lt m$$$, and $$$\forall_{i = 0, 1, \ldots, n - 2} 0 \leq d_i \lt m$$$.

Let $$$\Sigma$$$ be the set of all possible characters. We call that a string $$$S = s_1 s_2 \cdots s_n$$$ matches with a pattern $$$P = p_1 p_2 \cdots p_n$$$ if and only if there exists a mapping function $$$f: \Sigma \to \Sigma$$$ such that $$$\forall_{i = 1, 2, \ldots, n} f(s_i) = p_i$$$ and $$$\forall_{a, b \in \Sigma, a \neq b} f(a) \neq f(b)$$$.

Given an integer $$$m$$$ and a pattern $$$P$$$ consisting of lowercase English letters, find all positive integers in $$$m$$$-based representation that match the pattern, and report their greatest common divisor (GCD) in 10-based representation.

It is guaranteed for each test case that there always exists at least one integer whose $$$m$$$-based representation matches the pattern.

Byteland has $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$, and $$$\frac{n(n-1)}{2}$$$ two-way roads connecting all pairs of cities directly. However, $$$m$$$ roads become impassable due to the recent severe hurricane.

To assess the disaster damage, you are asked to calculate the number of pairs of cities that the minimum number of roads on the paths containing only passable roads between the two cities is exactly $$$k$$$, for each $$$k = 1, 2, \ldots, n - 1$$$. Note that the pairs of cities that are not connected with passable roads should not be counted.

You are playing a computer game fighting against monsters. To become the master in the game, you decide to train yourself today and in the following $$$m$$$ days using the monster generator.

The generator will generate $$$n$$$ monsters every day for training. Assume it is the $$$k$$$-th ($$$0\leq k\leq m$$$) day now, you need to assign $$$s_k$$$ health points (HP) before fighting against monsters. Then you need to beat all the $$$n$$$ monsters generated by the generator. You can fight against these monsters in an arbitrary order that you like. During the fight with the $$$i$$$-th monster, the player will lose $$$a_i+\Delta a_i\times k$$$ HP. And when the player finally beats the monster, the player will be awarded $$$b_i+\Delta b_i\times k$$$ HP. Note that when HP becomes negative ($$$ \lt 0$$$), the training will fail, so never let this happen. Note that no matter how many HP you have, you still need to reassign your initial HP in the beginning of the next day's training.

The less initial HP you need, the more skilled you are. What's the minimum possible amount of total initial HP $$$s_0+s_1+s_2+\dots+s_{m-1}+s_m$$$ that can be achieved?

You are given $$$n$$$ points in the 3D space. Please find two parallel planes such that all the $$$n$$$ points are inside the gap of the two parallel planes, and the length of the gap is minimized.

You are given two sequences of length $$$n$$$: $$$[a_1,a_2,\dots,a_n]$$$ and $$$[b_1,b_2,\dots,b_n]$$$. The value of $$$f(a,b)$$$ is defined as $$$f(a,b)=\max\left\{a_i+b_i\right\}$$$, where $$$1\leq i\leq n$$$.

The sequence $$$b$$$ can be shifted. You will then be given $$$q$$$ operations, each operation can be divided into the following two steps:

• First, shift the sequence $$$b$$$ to the left by one position, and drop the first element, so the sequence $$$b'$$$ will be $$$[b'_1=b_2$$$, $$$b'_2=b_3$$$, $$$\dots$$$, $$$b'_{n-1}=b_n]$$$.
• Then, append $$$v$$$ to the rightmost place of $$$b$$$, so the sequence $$$b'$$$ will be $$$[b'_1=b_2$$$, $$$b'_2=b_3$$$, $$$\dots$$$, $$$b'_{n-1}=b_n$$$, $$$b'_n=v]$$$.

In this problem, your task is to figure out the value of $$$f(a,b)$$$ before/after each operation.

A new restaurant is opened in Byteland. To attract more customers, the meal is partially free. Specifically, there are $$$n$$$ types of dishes on sale, labeled by $$$1,2,\dots,n$$$. Each dish can not be ordered more than once. For the $$$i$$$-th dish, its basic price is $$$a_i$$$ dollars, and its event price is $$$b_i$$$ dollars. Assume you have ordered $$$k$$$ dishes $$$p_1,p_2,\dots,p_k$$$ ($$$1\leq p_i\leq n, p_i \lt p_{i+1}$$$), the total amount of dollars that you need to pay for is:

$$$$$$ \sum_{i=1}^k a_{p_i}+\max_{i=1}^k\left\{b_{p_i}\right\} $$$$$$

You are a customer at this restaurant, you decide to order exactly $$$k$$$ dishes, what's the minimum possible amount of dollars that you need to pay for?