Akari, also known as Light Up, is a logic puzzle played on a rectangular grid. The player places light bulbs in empty cells until the entire grid is illuminated.

A light bulb lights up its own cell and all cells along the horizontal and vertical directions until its light hits an obstacle or the edge of the grid. No two light bulbs should be illuminated by each other. There are clue cells in the original rules indicating exactly how many bulbs must be placed in adjacent cells. However, determining whether a puzzle is solvable has been proven to be NP-complete.

Directions of the light. (a) The light illuminates all cells in the same row or column. (b) The light is blocked by '#' and no longer lights up the '.' cell.

Invalid placement.

In this problem, a puzzle without clue cells will be provided for each test case. Please find a solution to the puzzle.

Let's define that a string $$$s$$$ is considered better than another string $$$t$$$ if and only if both of the following conditions are met:

• $$$s$$$ is not a prefix of $$$t$$$
• $$$s$$$ is lexicographically smaller than $$$t$$$

Alice has a string $$$s$$$ of length $$$N$$$. She wants to split the string into $$$K$$$ continuous substrings $$$s[1 : p_1], s[p_1 + 1 : p_2], \dots, s[p_{K - 1} + 1 : p_K]$$$ such that:

• Define $$$p_0 = 0$$$
• For every $$$1 \leq i \lt K$$$, the substring $$$s[p_{i - 1} + 1 : p_i]$$$ is better than the substring $$$s[p_i + 1 : N]$$$
• $$$p_K=N$$$

Maggie discovers a large magical crystal deep within the cave. The crystal has a regular hexagonal shape, which is seen as a symbol of balance. In this world, there are $$$999$$$ types of magic particles. When these particles are arranged in a hexagonal pattern, a crystal is formed. However, if a crystal contains more than one type of particle, it is considered impure and may explode if someone attempts to release its power.

Maggie decides to extract a pure crystal, where all the magic particles are of the same type. For each potential center of the new crystal, help Maggie determine the side length of the largest pure crystal that can be extracted.

Side length: 1.	Side length: 2.	Not a crystal.

Given a set $$$P$$$ of the smallest $$$n$$$ primes $$$p_1 = 2 \le p_2 = 3\le \cdots \le p_n$$$. Partition the primes into two subsets $$$A$$$ and $$$B$$$ (which can be empty), such that the difference between the sums of two subsets is minimized.

Example

If $$$N = 9$$$, the set $$$P$$$ is $$$\{2, 3, 5, 7, 11, 13, 17, 19, 23\}$$$. The table below demonstrates an optimal solution:

ICPC Company has $$$N$$$ employees, with employee $$$1$$$ being the boss of the company. Each of the employees numbered $$$2$$$ through $$$N$$$ has a direct supervisor $$$s_i$$$, where $$$1 \leq s_i \lt i$$$. For employee $$$i$$$, all employees $$$s_i, s_{s_i}, \ldots, 1$$$ are considered to be supervisors of employee $$$i$$$.

Now, ICPC Company has a major project that requires sending some employees on a business trip. It is known that selecting the $$$i$$$-th employee will bring a profit of $$$p_i$$$ million dollars (if this value is negative, it means sending that employee on the trip will incur a loss).

However, selecting employees for the trip is not as simple as just choosing those with positive profits. Each employee also has a capability value $$$a_i$$$, where all capability values form a permutation of $$$1$$$ to $$$N$$$. For each employee $$$i$$$ sent on the business trip, if any of their supervisors is not sent, employee $$$i$$$ will need to handle that supervisor's tasks. But if there exists an unsent supervisor's capability value is higher than theirs, employee $$$i$$$ will feel pressure and cause a loss of $$$c_i$$$ million dollars, no matter how many unsent supervisors with higher capability value there are.

Additionally, there is another way losses can occur: for every $$$1 \leq i \lt N$$$, if the employee with capability values $$$i+1$$$ is selected for the trip but the employee with capability values $$$i$$$ is not, a further loss of $$$d_i$$$ million dollars will occur.

But wait! Before ICPC Company decides on the personnel to dispatch, they need to quickly inform the client whether they will accept the project. For this reason, ICPC Company has commissioned you, with your algorithmic expertise, to help them evaluate the maximum potential profit they could achieve.

However, ICPC Company knows an obvious upper bound: the total profit cannot exceed $$$T = \sum_{i=1}^{N}\max(p_i, 0)$$$ million dollars. After careful evaluation, ICPC Company has decided that if the maximum profit from this business trip is less than $$$T - 20$$$ million dollars, they will immediately reject the project; otherwise, they will begin planning for the trip.

Can you help ICPC Company determine whether they should take on the project? If they decide to take on the project, please also output the exact maximum profit that ICPC Company can achieve.

National Taiwan University's campus is quite large, and as a commuting student, Wiwiho doesn't want to walk 15 minutes to her department after a long commute. Therefore, she decides to use the Ubike facilities scattered around the campus.

However, there's a significant flaw she often overlooks. After successfully borrowing a Ubike from a station, she frequently finds that the stations near her department have no available slots when she arrives, forcing her to cycle to a more distant station and then walk a longer distance to her destination, defeating the purpose.

As a competitive programming contestant, Wiwiho decides to plan an optimal route to reach her department as quickly as possible. She selects $$$N$$$ stations on the NTU campus, numbered from $$$1$$$ to $$$N$$$, and plans $$$M$$$ routes between these stations. Each route is defined by three numbers $$$u_i, v_i, w_i$$$, representing a route between station $$$u_i$$$ and $$$v_i$$$ with a cycling time of $$$w_i$$$, regardless of direction.

Because returning a bike depends on luck, for each station, Wiwiho has estimated parameters $$$p_i, q_i, d_i$$$ through statistical data. Initially, all stations are in an "unknown state". When she arrives at station $$$i$$$ which is in an unknown state, she can try to observe the station and use the following strategy:

• Whenever Wiwiho observes at station $$$i$$$, there's a probability $$$p_i$$$ that the station has an available slot.
• If there's an available slot, she can return the bike and walk to her department in $$$d_i$$$ time.
• If there's no available slot, Wiwiho can choose to cycle away immediately. After this, she will turn that station into a "full state".
• If there's no available slot but Wiwiho chooses not to cycle away, she can wait an expected $$$q_i$$$ time for a slot to become available, then walk to her department in $$$d_i$$$ time. Note that during this $$$q_i$$$ time, Wiwiho cannot leave the station because returning a bike requires queuing.

Besides, when Wiwiho arrives at station $$$i$$$ which is in a full state, she can still choose not to cycle away, and wait an expected $$$q_i$$$ time for a slot to become available, then walk to her department in $$$d_i$$$ time.

Note that Wiwiho can choose not to observe a station when she passes through it.

To simplify the problem, assume that the probabilities and expected values for each station are independent, meaning stations do not influence each other's parameters.

Can you help Wiwiho find the minimum expected time to successfully return a bike and walk to her department if she borrows a Ubike from station $$$1$$$? Note that although Wiwiho can choose to return the bike at station $$$1$$$, she must follow the aforementioned rules, meaning she only has a probability $$$p_1$$$ of immediately returning the bike there.

There is a classic graph theory problem: given an undirected graph, find the largest subset of vertices such that the vertices form a clique. A clique is defined as a subset of vertices such that every two distinct vertices are adjacent in the given graph.

However, constructing the graph is troublesome. Now, for the $$$N$$$ vertices in the graph, we assign to the $$$i$$$-th vertex an interval $$$[l, r]$$$, representing a circular interval $$$[l, r]$$$.

What is a circular interval? Suppose the entire circle has a size of $$$2N$$$, which we can represent as coordinates $$$0$$$ to $$$2N-1$$$. A circular interval $$$[l, r]$$$ covers the coordinates: $$$$$$ \begin{cases} l\sim r & \text{if }l \lt r \\ 0\sim r\ \cup\ l\sim 2N-1 & \text{if } l \gt r \end{cases} $$$$$$

where $$$0\leq l, r \lt 2N, l\neq r$$$.

Given these intervals, we let there be an edge between any two vertices if and only if their intervals overlap at some coordinate.

Find any maximum clique.

Boluteshih and 2qbingquan are preparing the problems for Homework 0.514. Boluteshih selected $$$N$$$ problems, while 2qbingquan selected $$$M$$$ problems for the homework.

To make it harder to identify which problems were prepared by whom, Boluteshih wrote a Python script to shuffle the order of these problems randomly. As a coincidence, Boluteshih discovered that after shuffling, the problems chosen by 2qbingquan formed a contiguous subarray within the shuffled list.

Just out of curiosity, you are asked to answer the probability that the problems chosen by 2qbingquan just formed $$$k$$$ contiguous subarray within the shuffled list, for each $$$k$$$ from $$$1$$$ to $$$M$$$. All $$$(N + M)!$$$ permutations of the $$$N + M$$$ problems are considered equiprobable during the shuffle.

As usual, you are asked to output the answer modulo $$$998244353$$$ (see output section).

It's Cody's birthday! This year, instead of giving him a long string or an integer array with special properties, his friends surprised him with an interesting picture. Cody suspects that the image was cropped from a scene in a video he recently watched, but he can't remember the exact timestamp of the frame.

Cody has extracted all the frames in the video by FFmpeg, but he knows little about image matching. You, a helpful coder, decide to handle the task to earn an AC in return. Because the picture is stored in a lossy compression format, it is possible that an exact match cannot be found. The goal is to find a position with the smallest sum of squared difference (SSD) for the best match.

If the size of an image $$$I$$$ is $$$W \times H$$$ and the size of a (smaller) template image $$$T$$$ is $$$N \times M$$$, the SSD value of the position $$$(x, y)$$$ is defined as:

(a) $$$I$$$. (b) $$$T$$$. (c) Image difference. $$$\operatorname{SSD}(1,1) = 3^2 + 6^2 = 45$$$.

There is too much work to be done! The ICPC class now has an overwhelming amount of tasks that need to be handled. Each task requires a team of two people to complete. The ICPC class has $$$N$$$ people, and there are $$$M$$$ pairs of people who can work together (assigning incompatible pairs would cause awkwardness and complicate the tasks). Each pair can handle at most one task.

But if you think that means we can handle $$$M$$$ tasks, you are too naive! Each person also has their own workload limit. It is known that the $$$i$$$-th person is willing to handle at most $$$a_i$$$ tasks. This means that if the number of tasks assigned to the $$$i$$$-th person exceeds $$$a_i$$$, that person will refuse to do any work.

Can you help the ICPC class find the maximum number of task-handling pairs, such that no one exceeds their workload limit?

Alice and Bob are playing a cool new game called "King Game." The King Game consists of a $$$300 \times 300$$$ board and two pieces that can be placed on certain positions on the board. For convenience, we use 2D coordinates $$$(x, y)$$$ to represent the positions where pieces are placed, where $$$1 \leq x, y \leq 300$$$.

The rules of the King Game are as follows:

• At the start of the game, the two pieces are placed on different positions: $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.
• The players take turns to move, and each turn, the player must choose one of the pieces. Suppose the position of the chosen piece is $$$(x, y)$$$, the player can move it to any position $$$(p, q)$$$ such that $$$1\leq p \leq x$$$ and $$$1\leq q \leq y$$$. However, the new position $$$(p, q)$$$ cannot be $$$(x, y)$$$ or coincide with another piece.
• The player who cannot make a move loses.

Alice and Bob are going to play $$$T$$$ games, and they have already planned the starting coordinates for each game. Can you tell them, for each game, how many winning first moves the "first player" has under the condition that both players play optimally?

Ltf proposed an interesting board game, which is played on an $$$N \times N$$$ board by two players who take turns placing pieces on the board. The unique rule of the game is that each player, when placing a piece, must ensure that no two pieces are orthogonally adjacent, meaning that no two pieces can share a side. The player who cannot place a piece on their turn loses the game.

Ltf invited Ian to play this game with him, and Ltf will go first. Given the size of the board, determine who will win if both players play optimally.

It's so hot this summer!

Vasya is walking along the street, which can be viewed as an infinite two-dimensional plane. He is currently at the point $$$S = (s_x, s_y)$$$, while an ice cream truck is stationed at the point $$$T = (t_x, t_y)$$$.

Despite his eagerness to get some ice cream, the intense sunshine makes the journey uncomfortable. Fortunately, there are $$$N$$$ shaded areas created by trees and buildings blocking the sun, providing some cooler spots. For the purpose of this problem, these shaded areas are considered as convex polygons.

Vasya aims to find a path to the ice cream truck that minimizes the distance traveled outside these shaded areas. Please determine the minimum length Vasya needs to walk without shade.