The city of Aetherrain is notorious for its unpredictable weather. To protect students from dangerous floods, the mayor has announced:

"If the rainfall of any day is higher than or equal to 200 mm, classes the next day are suspended!"

Importantly, if classes are suspended and that day's rainfall is also $$$\geq 200$$$ mm, then the next day's classes are suspended too.

When classes were suspended but the day had $$$0$$$ mm rainfall, it's a Failed Prediction — angry parents complain about taking a day off for nothing while still paying school fees.

You, as a Raincaller, want to create as much chaos as possible. Your task is to plan a rainfall schedule that maximizes the number of days of Failed Predictions for the next $$$N$$$ days with a total rainfall of exactly $$$S$$$ mm, and the amount of rainfall on each day must be a non-negative integer. To avoid severe flooding, the rainfall on a single day should not exceed $$$350$$$ mm.

Any schedule that maximizes the number of Failed Predictions would be accepted.

Ben is playing Mario Kart World on his brand new Nintendo Switch 2! In a moment of excitement, Ben accidentally dropped his Joy-Con, and now both the joystick and the gyroscope are broken. This means his character can only move forward in a straight line from now on. Ben wants to know if it's still possible to complete certain tracks with this limited control scheme.

You are given a map of a race track, which is represented as a rectangular grid with $$$R$$$ rows and $$$C$$$ columns. Let's define $$$(X, Y)$$$ as the cell located at the $$$X$$$-th row and the $$$Y$$$-th column. Ben starts at the cell $$$(1, 1)$$$ and is initially facing east, meaning that he travels towards increasing column indices. The finishing line is located at cell $$$(R, C)$$$. Due to his broken controller, Ben can only perform the following move: advance a cell forward in the direction he is currently facing.

The grid contains $$$K$$$ pairs of linked portals. When Ben drives onto one portal of a pair, he is instantly transported to the location of the other portal in that same pair. After teleporting, Ben continues moving forward from his new location in the same direction he was already traveling. He does not get teleported back immediately. If Ben's path would take him off the grid, he hits a wall. His kart stops permanently at his last valid cell, and his run is over. He has failed to reach the finish line.

Figure 1

The image above shows a racing track with 3 pairs of teleporter portals. It illustrates how Ben reaches the finishing cell by moving in one direction only.

As Ben's friend, your task is to help him determine if it is possible to reach the finishing line at cell $$$(R, C)$$$.

Steve is a professional miner who is trying to mine copper ores! Steve is currently in a mine which can be represented as an $$$N \times N$$$ grid. Each cell in the grid is identified by a pair $$$(R, C)$$$, meaning that the cell is in the $$$R$$$-th row from top to bottom and the $$$C$$$-th column from left to right. Two cells are said to be adjacent if they share a common edge (in the direction of up, down, left, or right). Formally, $$$(R, C)$$$ is adjacent to $$$(R-1, C)$$$, $$$(R+1, C)$$$, $$$(R, C-1)$$$, and $$$(R, C+1)$$$, if any exist. In the mine, there are exactly $$$3$$$ copper cells, and all the remaining cells are stone cells.

Steve is trying to mine a mine shaft to connect all $$$3$$$ copper cells by mining some (possibly, zero or all) stone cells only. The copper cells are said to be connected if there exists a path of adjacent cells consisting of copper cells and mined cells between any two copper cells.

Please help Steve find a way to connect all $$$3$$$ copper cells by mining the minimum number of stone cells. If there are multiple ways to achieve this minimum, any of them is accepted.

Ben and his $$$N$$$ groupmates, numbered from $$$1$$$ to $$$N$$$, are collaborating on a heavy school project that consists of $$$M$$$ tasks, numbered from $$$1$$$ to $$$M$$$. To complete the project efficiently and meet the project deadline, Ben decides to assign the $$$M$$$ tasks to his $$$N$$$ groupmates. For each task $$$i$$$ ($$$1 \leq i \leq M$$$), there is exactly one groupmate who will be the Person-in-Charge $$$PIC_i$$$ ($$$1 \leq PIC_i \leq N$$$), responsible for ensuring the task gets done. Additionally, each task $$$i$$$ has $$$P_i$$$ "peanuters" ("花生友" in Cantonese) — groupmates who prefer to observe the progress and give comments without actively contributing.

To ensure the tasks are completed on time, Ben has to send reminder messages in the group chat, one for each task. The behavior when Ben sends a reminder for task $$$i$$$ is as follows:

• The Person-in-Charge $$$PIC_i$$$ dives — pretends to be unavailable and ignores the reminder message for task $$$i$$$.
• All peanuters of task $$$i$$$ upwater — pop online and read all messages currently in the group chat. Note that a groupmate can be both Person-in-Charge of some tasks and peanuters of some other tasks. In this case, once they read the message, they will be forced to handle all tasks for which they are the Person-in-Charge among the tasks mentioned in those messages.

Ben's goal is to maximize the number of tasks that are handled by their respective Person-in-Charge. A task is considered handled if the Person-in-Charge reads the reminder message for that task. To achieve this, Ben can carefully decide the order in which he sends reminders for the $$$M$$$ tasks. Your task is to help Ben determine the optimal order for sending reminders so that the number of tasks handled by their respective Person-in-Charge is maximized.

Bob, a railway enthusiast, is excited about the city's new train line. However, he finds the planned service too slow and has devised his own proposal to improve travel times.

In Bob's proposal, the train line consists of $$$N$$$ stations numbered sequentially from $$$1$$$ to $$$N$$$. Every train station will have an integer level $$$A_i$$$, where $$$1 \le A_i \le M$$$. There will also be $$$M$$$ train types numbered from $$$1$$$ to $$$M$$$. A train of type $$$j$$$ stops only at stations $$$i$$$ where the station's level $$$A_i \le j$$$. All trains travel only in the direction of increasing station numbers.

Figure 1: An example of $$$4$$$ train types. In this example, a train of type $$$2$$$ stops at stations $$$3$$$, $$$4$$$, $$$6$$$ and $$$9$$$ in order.

The time to travel between any two consecutive stops on any train's route is exactly $$$1$$$ minute. Passengers can also switch between different train types at any station. These transfers are instantaneous, with no waiting time. In the example below, travelling from station $$$2$$$ to station $$$7$$$ takes $$$4$$$ minutes.

Figure 2: Travelling from station $$$2$$$ to station $$$7$$$.

Now, Bob wants to test the effectiveness of his proposal. He has collected data for $$$Q$$$ potential passenger trips. For each trip $$$i$$$, from a starting station $$$U_i$$$ to a destination station $$$V_i$$$, your task is to calculate the minimum possible travel time under his proposal.

Alice and Bob want to travel from Pui Ching Middle School (PCMS) to La Salle College (LSC).

In this world, PCMS and LSC are located on opposite sides of the same road. PCMS is located at the start of the road, while LSC is located at the end of the road. There are two pedestrian crossings with traffic lights in front of both schools. Both traffic lights just turned from green to red at time 0.

Refer to the following figure for the layout.

It takes 1 unit time to cross the road, and takes $$$C$$$ unit time to walk from the start of the road to the end of the road. The traffic light of the pedestrian crossing in front of PCMS operates in a period of $$$A$$$ unit time. It means that the traffic light would be red for $$$A$$$ unit time, then green for $$$A$$$ unit time, and so on, alternating every $$$A$$$ units.

Formally, you may cross the road if you arrive at the crossing in front of PCMS in time $$$A$$$, $$$A+1$$$, ..., $$$2A-1$$$, $$$3A$$$, $$$3A+1$$$, ..., $$$4A-1$$$, ...

Similarly, the traffic light of the pedestrian crossing in front of LSC operates in a period of $$$B$$$ unit time.

Alice would take the pedestrian crossing in front of PCMS to cross the road first, then travel along the road to LSC, while Bob would travel along the road to LSC first, then take the pedestrian crossing in front of LSC.

Find the number of pairs $$$(u, v)$$$ where $$$0 \leq u \leq U$$$, $$$0 \leq v \leq V$$$ and satisfies the following conditions:

• Alice starts at time $$$u$$$.
• Bob starts at time $$$v$$$.
• The person who starts strictly later, arrives at LSC strictly earlier.

In a market, there are $$$N$$$ merchants numbered from $$$1$$$ to $$$N$$$ and $$$N$$$ items numbered from $$$1$$$ to $$$N$$$. Each merchant possesses an item. Initially, merchant $$$i$$$ owns item $$$i$$$.

Each item has a value $$$V_i$$$ and a cost $$$C_i$$$. A merchant who owns item $$$i$$$ is willing to trade it for another item $$$j$$$ if the value of item $$$j$$$ is greater than or equal to the cost of item $$$i$$$. A trade between two merchants is fair if both merchants involved are willing to trade their current item for another. Formally, a trade between the merchant who owns item $$$i$$$ and the merchant who owns item $$$j$$$ is fair if and only if $$$V_i\geq C_j$$$ and $$$V_j\geq C_i$$$. Upon a fair trade, the two merchants swap their items, while the values and costs of the items remain unchanged. Note that the value of an item may not necessarily be greater than its cost.

There are $$$Q$$$ independent queries from the merchants. In the $$$i$$$-th query, merchant $$$u$$$, who initially owns item $$$u$$$, wishes to obtain item $$$v$$$ through a sequence of fair trades. Hence, he would like to know whether it is possible for him to obtain item $$$v$$$ and, if so, the minimum number of trades required. Note that trades can occur between any pair of merchants, neither merchant $$$u$$$ nor merchant $$$v$$$ are necessarily involved in the trades. Since the queries are made before any trades begin, each query should be considered independently based on the initial state of the market.

Write a program to answer the queries made by the merchants.

The Heung Shing Observatory has recently discovered a new hurricane approaching Heung Shing!

The world can be viewed as an infinite 2D Cartesian plane, and Heung Shing is located at coordinates $$$(H_x, H_y)$$$. The hurricane is currently located at coordinates $$$(C_x, C_y)$$$. It is predicted to move along a straight line that forms an angle of $$$D$$$ degrees counterclockwise with the positive x-axis, however, the angle formed by the actual trajectory may be different due to a multitude of factors – it can be any real value between $$$D - U$$$ and $$$D + U$$$ degrees with uniform probability. When the hurricane comes within a 1 unit radius (inclusive) of Heung Shing, measured in Euclidean distance, a Hurricane Signal is issued.

Consider the two sample scenarios shown in Figures 1 and 2. In both figures, Heung Shing is at point $$$H$$$ and the hurricane is currently at point $$$C$$$. The predicted trajectory of the hurricane is indicated by the green arrow. The actual trajectory of the hurricane must be within the sector formed by the red lines.

Figure 1:	Figure 2:
$$$H = (3, 2), C = (2, 1), D = 45^\circ, U = 75^\circ$$$	$$$H = (-1, 3), C = (1, 1), D = 210^\circ, U = 15^\circ$$$

A Hurricane Signal is issued when the hurricane enters the blue circle. In Figure 1, the Hurricane Signal may or may not be issued in the future depending on its actual trajectory. In Figure 2, the Hurricane Signal is never issued.

Charlie is now interested in finding the probability that the hurricane will trigger a Hurricane Signal, either at its current position or somewhere along its future trajectory. Help Charlie find the answer!

Today, in the year 2025, marks the 9th Pui Ching-La Salle Programming Challenge (referred to as PuiLaTiu below) ever held! PuiLaTiu was first held in 2016 and paused for a year in 2020 due to COVID restrictions (and hence the 5th PuiLaTiu was held in 2021).

Alice is fascinated because both the edition number (9) and the year (2025) of this PuiLaTiu are perfect squares. She defines an interesting PuiLaTiu as one where both the edition number and the year it is held are perfect squares. She wonders: assuming PuiLaTius will be held once every year in the future, how many PuiLaTius held in years $$$L$$$ to $$$R$$$ (inclusive) are interesting?

Alice is distracted thinking about this during the contest. As Alice's teammate, you should answer her question to keep her from being distracted.

Froggy the frog is playing a jumping game. In the game, there are $$$1$$$ starting platform, followed by $$$N$$$ jumping platforms, numbered from $$$1$$$ to $$$N$$$, arranged in a line. The starting platform is $$$1$$$ block wide and the $$$i$$$-th jumping platform is $$$A_i$$$ blocks wide, where $$$A_i$$$ is always an odd number. For each jumping platform, the exact middle block, which is the $$$\lceil \frac{A_i}{2} \rceil$$$-th block, is a scoring block. The distance between the starting platform and the $$$1$$$-st jumping platform is $$$D_1$$$ blocks, and the distance between the $$$(i - 1)$$$-th jumping platform and the $$$i$$$-th jumping platform is $$$D_i$$$ blocks for $$$2 \le i \le N$$$.

Figure 1: An example where $$$N = 3$$$, $$$A = [3, 5, 1]$$$ and $$$D = [1, 3, 2]$$$. The starting platform is green, and the scoring blocks are red.

Froggy starts by standing on the starting platform, and his goal is to reach the $$$N$$$-th jumping platform by performing exactly $$$N$$$ jumps, landing on each platform exactly once. If he successfully lands all $$$N$$$ jumps, he completes the game. Additionally, he can jump at most $$$K_i$$$ blocks for his $$$i$$$-th jump.

Figure 2: For $$$K = [4, 10, 3]$$$, a valid jump sequence could have distances of $$$3, 9, 3$$$ blocks.

Froggy can also earn points by landing on scoring blocks. For each scoring block he lands on, he will earn $$$1$$$ point. However, he gets points only if he completes the game. In the example above, he completes the game with $$$2$$$ points, which is the maximum achievable score.

Your task is to determine if Froggy can complete the game, and if so, determine the maximum possible score he can achieve.

In Linear Sorting Process Computational Programming City (LSPCPC), a crucial component of the city's data systems is the Linear-Sorting Machine. This machine is designed to sort permutations of length $$$3N$$$.

A permutation of length $$$3N$$$ is an array consisting of $$$3N$$$ distinct integers from $$$1$$$ to $$$3N$$$ in arbitrary order. For example, $$$[6, 2, 5, 1, 3, 4]$$$ is a permutation of length $$$6$$$ ($$$N=2$$$), but $$$[1, 3, 3]$$$ is not a permutation.

Disaster struck when yesterday's hurricane caused severe flooding, damaging the machine's circuitry. While still operational, the machine's capabilities are now limited. It can only sort continuous segments of at most $$$2N$$$ numbers per operation.

An operation can be defined by a pair of integers $$$L$$$ and $$$R$$$, which sorts the subarray $$$A_L, A_{L+1} \ldots A_R$$$ in ascending order. As the segment can contain at most $$$2N$$$ numbers, for any operation $$$(L, R)$$$, the condition $$$R - L + 1 \le 2N$$$ must hold.

The Mayor has declared a state of emergency as the city's data arrays have become scrambled. You've been tasked with sorting a critical permutation of $$$3N$$$ integers that was being processed when the disaster hit, returning it to perfect ascending order (i.e., $$$A_i = i$$$ for all $$$1 \le i \le 3N$$$). Your goal is to find a sequence of operations to sort the permutation and determine the minimum number of sorting operations required to achieve this.

Alice is an amateur Linesweeper player who is learning how to play the game!

In Linesweeper, mines are randomly placed on a board that consists of a single row with $$$N$$$ cells, numbered from $$$1$$$ to $$$N$$$ from left to right. Some cells contain mines while some cells do not contain mines.

Initially, all cells are unopened, and no information will be displayed. In each move, a player selects an unopened cell to open it. If the chosen cell contains a mine, the player loses immediately. Otherwise, a number is displayed in the opened cell, indicating how many adjacent cells contain mines. Two cells are considered adjacent if they share a side. As each cell has at most two adjacent cells, the number displayed in an opened cell will be 0, 1, or 2.

Alice has not lost yet. Thus, all opened cells do not contain mines. However, she is struggling to solve her Linesweeper; therefore, she shares the current board and seeks your help. Can you determine how many unopened cells she can open in her next move that are guaranteed not to contain mines?