The year 2021 marks the death of Adobe Flash, a multimedia software for animations, applications, games, and so on. Together with it, the era of Flash games (especially from 2005 to 2012) has started to fade away into history. Some good news on this front is that people have already been working on a way to preserve Flash content. Major efforts include Ruffle: an open source Flash player written in Rust, and Flashpoint: an archive of over 78,000 Flash applications.

In memory of the golden era of Flash games, we present a simplified variant of a famous Flash game called Factory Balls. You are tasked with painting a ball in a given pattern. The surface of a ball can be divided into $$$N$$$ distinct regions, enumerated with indices from 1 to $$$N$$$. You have $$$K$$$ paint cans full of paint, where the $$$i$$$-th paint can has the color $$$i$$$. You are also given $$$M$$$ pieces of equipment. Each piece of equipment is specified by a set of regions, and it precisely covers that subset of the regions of the ball.

In the beginning, all regions have color 1 and all pieces of equipment are unequipped. You may perform one of the following actions any number of times:

1. Immerse the ball into the $$$i$$$-th paint can. Every region not covered by any of the pieces of equipment on the ball will be painted with color $$$i$$$.
2. Pick one piece of equipment currently not equipped, and equip it. You can equip multiple pieces of equipment.
3. Pick one piece of equipment currently equipped, and unequip it.

In the end, each region of the ball should have a specific color, and all pieces of equipment should be unequipped. Find the minimum number of actions required to paint the ball, or report that it is impossible.

Consider a planar graph in the shape of a convex polygon with $$$2N$$$ vertices. Each vertex is numbered clockwise from $$$1$$$ to $$$2N$$$. Currently, there are $$$2N$$$ bidirectional edges along the perimeter of the convex polygon. In other words, for every $$$1 \le i \le 2N$$$, vertex $$$i$$$ and vertex $$$(i \pmod{2N}) + 1$$$ are connected by an edge.

Each vertex is colored with one of $$$N$$$ colors numbered from $$$1$$$ to $$$N$$$. For each color $$$i$$$ ($$$1 \le i \le N$$$), there are exactly two vertices with color $$$i$$$. The indices of vertices with color $$$i$$$ are $$$x_i$$$ and $$$y_i$$$.

We want to add exactly $$$2N-3$$$ bidirectional edges to this graph. After doing so, the following conditions must be satisfied:

• Each edge must connect two different vertices via a straight line segment.
• For any two distinct vertices, there can be at most one edge directly connecting the two vertices.
• The graph must still be planar.

Let $$$dist(a, b)$$$ be the length of the shortest path between two vertices $$$a$$$ and $$$b$$$. Among all possible edge additions satisfying the above conditions, find one that minimizes $$$\sum_{i = 1}^{N} dist(x_i, y_i)$$$.

Clustering algorithms are algorithms that partition data into subsets named clusters, intending to place similar data into the same cluster and different data into different clusters.

Professor Jihoon Ko discovered the revolutionary clustering algorithm UCP-Clustering. Given $$$N$$$ distinct points in a 2-dimensional space, the algorithm partitions the points into $$$K$$$ clusters with the following algorithm.

• Each cluster is assigned a representative coordinate (RC) which will be used later. Initially, $$$K$$$ points from the given $$$N$$$ points are chosen, and each cluster's RC corresponds to one of the chosen points. Even though the coordinates are chosen from the points, all clusters are empty at this point.
• Repeat the following algorithm recompute:
  • For each point, insert it into the cluster which minimizes the distance to its RC. If there is more than one such cluster, pick the one with the smallest RC per their lexicographic order.
  • For each cluster, recompute its RC. The $$$x$$$-coordinate of the new RC is the median of the $$$x$$$-coordinates of points in the cluster. Similarly, the $$$y$$$-coordinate is the median of the $$$y$$$-coordinates.
  • If none of the clusters had their RC change, the algorithm terminates. Otherwise, empty all the clusters and run the recompute algorithm again (emptying does not reinitialize the RC).

Here, the following definitions are used:

• Point $$$(x_1, y_1)$$$ is lexicographically smaller than $$$(x_2, y_2)$$$ if and only if $$$x_1 \lt x_2$$$ or $$$x_1 = x_2$$$ and $$$y_1 \lt y_2$$$.
• For a sequence of length $$$n \gt 0$$$, the median is defined as the $$$(n+1)/2$$$-th largest value if $$$n$$$ is odd, and as the average of the $$$n/2$$$-th and $$$n/2+1$$$-th largest values if $$$n$$$ is even.

For example, consider the case where $$$N = 3$$$ points $$$\{(1, 2), (3, 4), (5, 6)\}$$$ are clustered into $$$K = 2$$$ sets. Suppose that the points $$$(1, 2)$$$ and $$$(3, 4)$$$ are selected as RCs. The first iteration of the recompute algorithm clusters the points into $$$\{(1, 2)\}$$$ and $$$\{(3, 4), (5, 6)\}$$$ with their RCs being $$$(1, 2)$$$ and $$$(4, 5)$$$. The second iteration does not change the RCs, thus the recompute algorithm is executed twice. Suppose that the points $$$(1, 2)$$$ and $$$(5, 6)$$$ are selected as RCs. Then the first iteration of the recompute algorithm clusters the point into $$$\{(1, 2), (3, 4)\}$$$ and $$$\{(5, 6)\}$$$ with their RCs being $$$(2, 3)$$$ and $$$(5, 6)$$$. The second iteration does not change the RCs, thus the recompute algorithm is executed twice. From the above example, we can see that the initial choice of the RC may change the result of the clustering.

In this problem, let's focus on the case $$$K = 2$$$. Suppose that all $$$N(N-1)/2$$$ possible initial representative coordinates are chosen for each cluster equiprobably. Please find all the possible sets of representative coordinates at the end of the algorithm, and the expected value of execution count for recompute if the algorithm reaches this set of points.

There are $$$N$$$ monsters on a two-dimensional plane. Each monster has a value associated with it.

A sword strike is an action that slays all monsters along a line. If you slay a monster, the monster disappears. The line must be parallel to one of the coordinate axes.

Compute the maximum sum of values of monsters that you can slay given that you can perform up to three sword strikes.

Yihwan is a 5-year-old genius who enjoys rock-paper-scissors. He wanted to play rock-paper-scissors alone at his house, so he showed his creativity and made a game using some cards.

Yihwan places $$$N$$$ cards, each with one of scissors, rock, or paper, on positions $$$1, 2, \ldots, N$$$. Then, for each of $$$i = 1, 2, \ldots, N - 1$$$ in increasing order, Yihwan swaps the card at positions $$$i$$$ and $$$i + 1$$$ if the card in the $$$i$$$-th position beats the card in the $$$i+1$$$-th position. As the process of the game is similar to bubble sort, Yihwan named this game 'Rock-paper-scissors Bubble Sort'. The win-lose relationship of the cards is as follows:

• A card with scissors beats a card with paper.
• A card with paper beats a card with rock.
• A card with rock beats a card with scissors.

Yihwan is very good at calculating, so he played this game $$$T$$$ times and went to sleep. However, while Yihwan was sleeping, the cards were accidentally shuffled. Fortunately, since Yihwan is a genius with excellent memory, he remembered the arrangement of the initial cards before the game. However, he couldn't remember the final arrangement of cards after $$$T$$$ games and now needs your help.

Please help Yihwan by restoring the final arrangement of cards after playing the game $$$T$$$ times.

$$$N$$$ stones labeled from $$$1$$$ to $$$N$$$ are arranged in a row in increasing order. Each stone is colored either white or black. The weight of the $$$i$$$-th stone is $$$A_i$$$.

You will remove the stones one at a time until all the stones are removed.

When removing a stone, if the stone is not the leftmost or rightmost of all remaining stones, and neither stone adjacent to the stone being removed matches it in color, your score increases by the weight of the stone being removed. Two stones are adjacent if there are no stones in between those two.

Find a way to remove the stones to maximize your score.

$$$N$$$ stones labeled from $$$1$$$ to $$$N$$$ are arranged in a row in increasing order. Each stone is colored either white or black. The weight of the $$$i$$$-th stone is $$$A_i$$$.

You will remove the stones one at a time until all the stones are removed.

When removing a stone, if the stone is not the leftmost or rightmost of all remaining stones, and neither stone adjacent to the stone being removed matches it in color, your score increases by the weight of the stone being removed. Two stones are adjacent if there are no stones in between those two.

There are $$$N!$$$ possible ways to remove all the stones. Compute the sum of scores from each possible way, modulo $$$998\,244\,353$$$.

There are $$$N$$$ villages in a row, numbered from $$$1$$$ to $$$N$$$. Village $$$1$$$ is the leftmost village and village $$$N$$$ is the rightmost village. The heights of the villages are distinct integers ranging from $$$1$$$ to $$$N$$$.

You would like to divide the villages into several segments. Each segment must contain at least one village and every village should belong to exactly one segment. If two villages are in the same segment, then all villages in between them must also be in that segment.

In each segment, a beacon will be installed in the village with the highest height. For efficient mutual communication among beacon towers, the heights of the villages where the beacon towers are installed must form an increasing sequence from left to right.

Please count the number of possible segment divisions that will cause the beacon towers to satisfy the given constraints.

As a child, Jeyeon had $$$N$$$ marbles numbered from $$$1$$$ to $$$N$$$ and infinitely many bags. Each marble is either red or blue. Each marble belonged to its own bag by itself originally.

Jeyeon kept a diary of every change he made to the marbles. The diary consists of $$$M$$$ entries. There are three different types of entries:

• 1 i j : Combine the bag containing marble $$$i$$$ and the bag containing marble $$$j$$$. ($$$1\leq i, j \leq N$$$)
• 2 i : Lose marble $$$i$$$ forever. ($$$1\leq i \leq N$$$)
• 3 i l h : Observe that the bag containing marble $$$i$$$ contained at least $$$l$$$ and at most $$$h$$$ red marbles. ($$$1 \leq i \leq N, 0 \leq l \leq h \leq N$$$)

10 years later, Jeyeon, looked at his diary and tried to restore the color of each of his marbles. Please construct a sequence of colors that satisfies all entries of his diary, or state that no such sequence exists.

Professor Deokin lectures on algorithms. For the upcoming midterm exam, he decided to add the maximum subarray sum problem taught in his lecture, which is the following problem:

• Given the array $$$A=[a_1, a_2, \ldots , a_n]$$$, compute the value $$$MSS(A) = \max_{1 \leq i \leq j \leq n}(\sum_{k=i}^{j}a_k)$$$

Deokin wants to force the students to solve the maximum subarray sum problem by hand. For this, he uses the following procedure.

• Prepare a two-dimensional array of integers of size $$$N \times N$$$.
• Start from the cell $$$(1, 1)$$$, and repeatedly move either right or down to reach the cell $$$(N, N)$$$. If the current cell is $$$(i, j)$$$, he can move right to the cell $$$(i, j+1)$$$ if $$$j \lt N$$$, or move down to the cell $$$(i+1, j)$$$ if $$$i \lt N$$$.
• Write a sequence of length $$$2N-1$$$ which contains the elements of the cells in the order that the cells were visited.

Professor Deokin wants to add an inside joke to the problem so that the students who paid attention to his lectures can have confidence in their answers. He wants to create a sequence where the value of $$$MSS(A)$$$ is exactly $$$K$$$. Given a two-dimensional array of size $$$N \times N$$$, you need to find the number of different paths in the grid which yield sequences that have a maximum subarray sum value of exactly $$$K$$$.

Jeyeon and Deokin are addicted to problem-solving and they never want to retire. They developed a new board game, which they decided to not retire before they fully analyze.

The game consists of $$$K$$$ boards and $$$K$$$ pieces. The $$$i (i=1,\cdots,K)$$$th board is a grid of size $$$N_i \times M_i$$$. For each board, there are two fences that form a boundary. Fences are paths of length $$$N_i + M_i$$$ that start from the upper-left vertex and ends at the lower-right vertex, and can be traced by moving only right (R) or down (D) in steps of length 1. The two fences do not meet except at the upper-left and lower-right vertices.

For example, consider the case where $$$N_i = 5, M_i = 4$$$. In the case of (a), the two paths RRDRDDDRD, DDRRDDDRR do not meet except at the upper-left and lower-right vertices, so this can be a valid input. On the other hand, in the case of (b), the selected two fences RDRDRDRDD, DDRRDDDRR meet at a vertex other than the upper-left and lower-right vertices, so it is an invalid input. In the case of (c), one of the fences cannot be traced by moving only right and down, so it is also an invalid input.

The game starts with $$$K$$$ boards, and there are two fences on every board. Each board has a single piece that is placed on the upper left square. Jeyeon starts first, and then they alternate turns. In Jeyeon's turn, Jeyeon must select one of the $$$K$$$ pieces and move it to the square directly to the right of the current square; In Deokin's turn, Deokin must select one of the $$$K$$$ pieces and move it to the square directly below the current square; It is not allowed to move a piece across the fence. The player who is unable to make a move on their turn loses the game.

You are an avid problem solver and have a desperate desire to win. However, since Jeyeon and Deokin are very strong, you can never beat them. However, if you perfectly analyze this game, maybe they can consider retiring?

Given the $$$K$$$ boards, please determine the winner of the game if both players play optimally.

There are $$$N$$$ springs on a circular game board. There are two types of springs: red springs and blue springs. When the robot steps on a red spring, it can jump one spring left or right. When the robot steps on a blue spring, it can jump two springs left or right.

The case when the two robots are on springs 1 and 6 respectively, and a counterclockwise jump command is given.

You will play a game using two robots. In the beginning, you will place the two robots on different springs on the board. You can then issue a direction - either clockwise or counterclockwise. Both robots will jump simultaneously in the direction you command. The game ends when the robots step on springs of different colors.

You are given $$$Q$$$ queries. Each query contains the starting springs of the two robots. For each query, find the minimum number of commands needed to finish the game.

I have a question, could you please answer it?

You are given two sequences $$$(p_1, p_2, \ldots, p_N)$$$, $$$(q_1, q_2, \dots, q_N)$$$ of length $$$N$$$. What is the value of this sum?

$$$$$$\sum_{i=1}^{N} {\sum_{j=1}^{N} {\min(|p_i - p_j|, |q_i - q_j|)} }$$$$$$