You are given a positive integer $$$n \gt 1$$$. Your task is to partition the set $$$\{1, 2, ..., 3n\}$$$ into three sets $$$A$$$, $$$B$$$, and $$$C$$$, each containing $$$n$$$ elements. The sets $$$A$$$, $$$B$$$, and $$$C$$$ should have the same sum. It can be shown that under the given constraints, a valid partition always exists.

Due to budget reasons (the football team needs more DoorDash), Rutgers is working on updating its bus system. Currently, the bus system operates on an $$$n$$$ by $$$m$$$ rectangular grid, with bus stops in every cell and bus routes connecting horizontally or vertically adjacent stops. To do this and RUScrew over as many people as possible, Rutgers needs to remove 2 bus stops and all bus routes using those stops so that it's no longer possible to use the bus system to travel between every pair of remaining bus stops. Count the number of pairs of bus stops Rutgers can remove to do this.

Formally, given an $$$n$$$ by $$$m$$$ rectangular grid graph, count the number of pairs of vertices such that removing them and all incident edges makes the remaining graph disconnected.

Example of a 2 by 3 Rutgers bus system.

We define the function $$$F(N, M)$$$ to be the number of ordered pairs of integers $$$(a, b)$$$ such that $$$1 \leq a \leq N$$$, $$$1 \leq b \leq M$$$, and $$$\gcd \left( \frac{a}{\gcd(a, b)}, b \right) = \gcd(a, b)$$$.

You are given that $$$F(3, 3) = 7$$$, $$$F(10, 10^3) = 6947$$$, and $$$F(10^5, 10^3) = 69278063$$$.

Find $$$F(n, m)$$$ modulo $$$998\,244\,353$$$.

You enter the prompt "Build me a generator for infinite energy. Make no mistakes." Unfortunately, your free trial of astra has ended, and you have been given a generator for infinite sequences instead.

Define $$$G_m$$$ as the set of all sequences that can be generated using the integer $$$m$$$. A sequence $$$c$$$ belongs to $$$G_m$$$ if at least one of the following conditions holds:

1. The sequence $$$c=[1, 2, \ldots, m]$$$.

2. There exist two (not necessarily distinct) sequences $$$a=[a_1,a_2,\dots,a_{|a|}]\in G_m$$$ and $$$b=[b_1,b_2,\dots,b_{|b|}]\in G_m$$$, and an integer $$$k$$$ with $$$0\le k\le |a|$$$, such that the sequence is obtained by inserting $$$b$$$ into $$$a$$$ after its first $$$k$$$ elements. In other words, the resulting sequence $$$c=[a_1,a_2,\dots,a_k,b_1,b_2,\dots,b_{|b|},a_{k+1},a_{k+2},\dots,a_{|a|}]$$$.

You are given an integer $$$m$$$ and a sequence $$$a_1,a_2,\dots,a_n$$$. Find the maximum length of a subarray$$$^{\text{∗}}$$$ of $$$a$$$ that appears as a subarray of some sequence in $$$G_m$$$.

Formally, find the maximum integer $$$k$$$ such that there exist a sequence $$$x\in G_m$$$ and indices $$$1 \le l_1 \le r_1 \le |a|, 1 \le l_2 \le r_2 \le |x|$$$ satisfying $$$r_1-l_1+1=r_2-l_2+1=k$$$ and $$$a_{l_1+i}=x_{l_2+i}$$$ for every $$$0\le i \lt k$$$.

After years of research, you (Nick Belov) finally find your favorite biking place. You want to explore as many different bike paths as possible. However, you don't see a difference in exploring two bike paths that are very similar. You want to know how many bike paths you can explore such that each path is non-similar to any of your previously explored paths.

You are given an $$$n \times m$$$ grid. Each cell is either passable or impassable.

A valid path starts at the top-left cell $$$(1,1)$$$ and ends at the bottom-right cell $$$(n,m)$$$. At each step, you may move either right or down, and every cell visited by the path must be passable.

Represent each valid path by a string containing $$$m-1$$$ characters 'R' and $$$n-1$$$ characters 'D', denoting moves right and down, respectively.

Two valid paths $$$a$$$ and $$$b$$$ are called similar if there exists a sequence of valid paths $$$a=q_1,q_2,\ldots,q_{|q|}=b$$$ such that, for every $$$1 \le j \lt |q|$$$, the paths $$$q_j$$$ and $$$q_{j+1}$$$ differ in exactly 2 adjacent positions.

Let $$$S$$$ be a set of valid paths such that no two distinct paths in $$$S$$$ are similar.

Find the maximum possible size of $$$S$$$. Since the answer may be large, output it modulo $$$998\,244\,353$$$.

You are given two permutations$$$^{\text{∗}}$$$ and must compute the edit distance between them using only the following edits:

• Given a length $$$n$$$ permutation, insert $$$n+1$$$ anywhere into the array, resulting in a permutation of length $$$n+1$$$.
• Given a length $$$n$$$ permutation, delete $$$n$$$ from the array, resulting in a permutation of length $$$n-1$$$.

The edit distance between two permutations $$$p$$$ and $$$q$$$ is the minimum possible number of edits it takes to turn $$$p$$$ into $$$q$$$ or vice versa. It can be shown that, given the edits above, it does not matter which permutation you start with.

After years of training, you have finally awakened your true power and become a stringmaster, allowing you to perform the following operation on a string:

Choose a subsequence$$$^{\text{∗}}$$$ that is a palindrome$$$^{\text{†}}$$$ and arbitrarily permute the characters at the selected positions.

Here is an example of such an operation where we select the palindrome tst: $$$$$$ \mathtt{{\color{red}t}e{\color{red}{st}}ing} \;\to\; \mathtt{{\color{red}s}e{\color{red}{tt}}ing} $$$$$$

Now you have a string $$$x$$$, and you want to know if you can turn it into a string $$$y$$$ by performing the above operation any number of times (possibly zero).

Alice and Bob play a game by taking turns moving a token in a tree. Alice goes first. On their turn, the player moves the token from its current vertex $$$a$$$ to a vertex $$$b$$$. The length of the move is the number of edges on the unique simple path from $$$a$$$ to $$$b$$$. Each move must be strictly longer than the previous move, and Alice's first move must have positive length.

A player who has no legal move on their turn loses, and the other player wins. Given the tree and initial position of the token, determine who will win the game if both players play optimally.

The problemsetters of the Gennady Needs Your Rating contest have written $$$n$$$ problems, but they forgot that they still have to write solutions! You know that for the $$$i$$$-th problem, it takes them $$$a_i$$$ minutes to write a correct solution and $$$b_i$$$ minutes to write an incorrect solution.

You know that the problemsetters will write exactly one solution for each problem and spend at most $$$k$$$ minutes in total writing solutions for all problems. For how many problems is it possible that the problemsetters write a correct solution?

More formally, count the number of values $$$i$$$ among $$$1, 2, \ldots, n$$$ such that there exists some arrangement of correct and incorrect solutions for each problem, where a correct solution is written for problem $$$i$$$, and the total time spent writing all solutions does not exceed $$$k$$$. Note that the arrangements may differ for different values of $$$i$$$.

In a four-dimensional world, video games would take place on three-dimensional screens in the same way we humans play video games on two-dimensional screens. There are $$$k$$$ four-dimensional beings playing their favorite game on an $$$m \times n \times h$$$ grid. Each player has their own color.

The game has $$$r$$$ turns. Each turn results in some player coloring a rectangular prism subgrid with their color. If any of these cells had been previously colored, they are overwritten to have the new color.

Formally, a turn is defined by a player number $$$i$$$ and two triples $$$(x_1, y_1, z_1)$$$ and $$$(x_2, y_2, z_2)$$$, where $$$x_1 \le x_2$$$; $$$y_1 \le y_2$$$; and $$$z_1 \le z_2$$$. Player $$$i$$$ colors all $$$(x, y, z)$$$ such that $$$x_1 \le x \le x_2$$$; $$$y_1 \le y \le y_2$$$; and $$$z_1 \le z \le z_2$$$. Below is an example of a turn for $$$m = 4, n = 3, h = 2$$$. The player has colored the subgrid defined by corners $$$(0, 0, 0)$$$ and $$$(2, 1, 1)$$$.

Your task is to calculate, at the end of the game, how many cells in the grid were only ever colored by one player. Note that a cell might get colored by the same player multiple times across different turns.

You are given a function $$$f(b)$$$ that represents the maximum skyline achievable for an array $$$b$$$ of length $$$m$$$, defined as:

$$$$$$f(b) = \max(\min(b_i, b_{i+1}, \ldots, b_j) \cdot (j-i+1))\text{, where } 1 \leq i \leq j \leq m.$$$$$$

Given an array $$$a$$$ of length $$$n$$$, partition its elements into two nonempty subsequences $$$x$$$ and $$$y$$$ such that each element is contained in exactly one of $$$x$$$ or $$$y$$$, and $$$f(x)+f(y)$$$ is maximized.

A sequence $$$x$$$ is a subsequence of a sequence $$$a$$$ if $$$x$$$ can be obtained from $$$a$$$ by the deletion of several (possibly zero or all) elements from arbitrary positions.

Thomas has been studying physics, and recently he learned about levers and torque. As practice, he has been experimenting by placing identical weights on a lever to see what balances. Since the weights are identical, he can keep track of his setup with a binary string of odd length, where the 1s represent where weights are located, and the middle index is the position under which the lever's fulcrum is located. Thomas's current configuration of weights might not be balanced, and he wants to put in as little effort as possible to extend it to a configuration that will balance.

Formally, we define a binary string to be an equilibrium string if it has odd length and satisfies $$$\sum_{i \in W} (i-m) = 0$$$ where $$$m$$$ is the index of the midpoint of the string and $$$W$$$ is the set of indices having 1s. Given a binary string representing Thomas's current configuration of weights, your task is to find the length of the shortest equilibrium string of which the given string is a prefix.

Below is an example calculation of a binary string that is not an equilibrium string. However, by adding two characters onto the end, it can be made into one. In fact, we cannot turn the first string into an equilibrium string with any shorter extension.

The nonempty prefix XORs of an array of length $$$m$$$ are the values $$$a_1 \oplus a_2 \oplus \cdots \oplus a_k$$$ where $$$1 \le k \le m$$$ and $$$\oplus$$$ denotes the bitwise XOR operation.

You are given an integer $$$n$$$. Output a permutation$$$^{\text{∗}}$$$ of the integers from $$$0$$$ to $$$2^n-1$$$ such that the MEX$$$^{\text{†}}$$$ of all nonempty prefix XORs is maximized.

You are given two integers $$$m$$$ and $$$n$$$. Print a grid of integers with $$$m$$$ rows and $$$n$$$ columns such that the four corners of any rectangular subgrid add up to a perfect square. Each integer must lie in the range $$$[1, 10^9]$$$. Note that we are only interested in rectangular subgrids that have four corners. Your solution must contain at least two different numbers. It can be shown that under the given constraints, a solution always exists.

An example on a $$$3 \times 3$$$ grid is shown below. Several examples of rectangular subgrids are highlighted. The four corners of each rectangle are colored red. Note that the entire grid is also considered a subgrid.