Recently, Alice has come across an interesting game advertisement when scrolling through social media. The game involves a squad of soldiers going through gates with arithmetic operations that would apply to their fighting power.

The game advertisement.

Once she downloaded the game, she realized that the advertisement was fake and the actual gameplay was nowhere like what was portrayed in the ads. "What a pity!" She thought, "It would make a good mathematical game." Hence she decides to recreate one on her own.

The game she created is as follows:

• The character starts with a Power Level of $$$0$$$.
• There are $$$N$$$ stages. Each stage has a pair of Magic Gates.
• The character needs to pass through the $$$N$$$ stages in order by choosing 1 of the 2 gates to pass through at each stage.
• Each Magic Gate is associated with an arithmetic operation, for example, $$$+2$$$, $$$-(-3)$$$, $$$*7$$$. The operator must be one of add ($$$+$$$), subtract ($$$-$$$), or multiply ($$$*$$$), followed by an integer operand.
• Passing through the magic gate would apply the operation onto the character's current Power Level, for example, a character with Power Level $$$7$$$ passing through a $$$+2$$$ magic gate would turn his Power Level into $$$7 + 2 = 9$$$.

It should be noted that different from the original game, the character is allowed to have a negative Power Level.

Given the configurations of all Magic Gates, could you figure out what is the maximum final Power Level that can be achieved after passing through all $$$N$$$ gates when selecting optimally?

The author of this task dislikes long stories in task statements, so he is making the task statement of this task as concise as possible!

Given a 01-string $$$S$$$ of length $$$N$$$, you have to process $$$Q$$$ queries on it.

For the $$$i^{th}$$$ query, you are given $$$L_i$$$ and $$$R_i$$$, and you have to find any pair $$$(a, b)$$$ such that $$$L_i \le a \le b \le R_i$$$ and $$$S[a .. b]$$$ contains exactly half of the number of 0s and half of the number of 1s in $$$S[L_i .. R_i]$$$. If no such pair exist, output -1.

Percy is a student studying at Heung Shing Secondary School. On the ground floor of the school, there is a piece of land for building a carpark. The piece of land can be represented by a grid with $$$N$$$ rows and $$$M$$$ columns. The land is surrounded by roads on all 4 sides. One day, the school principal asks Percy to redesign the carpark's layout.

A parking spot requires 2 connected cells, i.e. a vertical or horizontal $$$1 \times 2$$$ region. Parking spots that touch the boundary of the land can be directly accessed by the external roads. Cells that are not part of a parking spot form the internal roads. A parking spot is also accessible if it is possible to reach the boundary of the land from the parking spot via some internal roads.

The principal has decided to give the Student of the Year award to Percy if he manages to design a layout that meets all of the following criteria:

• All parking spots are accessible.
• The total area of all parking spots is at least $$$80\%$$$ of the land's area.

For example, in the layout below, the parking spots are all accessible by external and internal roads and the total area is $$$30 / 36 \approx 83.3\%$$$. Therefore it is an acceptable layout.

As a friend of Percy, can you help him to win the Student of the Year award?

A long, long time ago, the Olympians resided in the idyllic Olympic village. The village was built in the form of a connected, undirected graph with $$$N$$$ houses (vertices) and $$$M$$$ roads (edges). Once every year, the Olympians gather in one of the houses and take part in a lavish feast.

Choosing which house to hold the feast in was not a straightforward task — instead of picking a house randomly, the Olympians were adamant that the inconvenience should be minimized. Since Olympians in every house were responsible for delivering food and gifts to the location of the feast, the inconvenience of holding the feast in house $$$i$$$ was defined to be the maximum number of roads that an Olympian travels along to reach house $$$i$$$, assuming everyone walks to the feast using the smallest possible number of roads.

Unfortunately, we still do not know much about the structure of the graph to this day. Careful inspection of an ancient scroll revealed a note which stated the largest and smallest inconvenience among all $$$N$$$ possible houses. Given these two numbers, can you reconstruct the layout of the Olympic village?

"XOR Merging" is a game created by Ethen. In the game, the player is given two 01-strings $$$S$$$ and $$$T$$$. The player can "xor merge" any two consecutive digits of $$$S$$$ multiple times, until $$$S$$$ becomes the target string $$$T$$$. When the player "xor merges" the two digits $$$S_i$$$ and $$$S_{i+1}$$$, they will be replaced by the result of $$$S_i$$$ xor $$$S_{i+1}$$$.

For example, let $$$S$$$ be $$$100010111$$$ and $$$T$$$ be $$$101010$$$, the player can convert $$$S$$$ to $$$T$$$ using three "xor merges".

1. First merge $$$S_2=0$$$ and $$$S_3=0$$$ into $$$0$$$, so that $$$S$$$ becomes $$$10010111$$$.

2. Then merge $$$S_3=0$$$ and $$$S_4=1$$$ into $$$1$$$, so that $$$S$$$ becomes $$$1010111$$$.

3. At last merge $$$S_6=1$$$ and $$$S_7=1$$$ into $$$0$$$, so that $$$S$$$ becomes $$$101010$$$, which is the same as $$$T$$$.

However, Ethen found that it is not always possible to convert a given $$$S$$$ to a given $$$T$$$ by "xor merging". Can you help Ethen determine if a solution exists?

In Fall Guys squads show, squads of 4 to compete against other teams. The show starts with 15 squads (60 players). In each round some squad(s) will be eliminated until one single squad remains which will be declared as the winner.

Now, your squad is competing in one of the rounds - Slime Climb. In Slime Climb, individual players race to the finish line as quick as possible while avoiding falling into the rising slime. Players who finish the race will score $$$(\text{number of players}) - (\text{individual rank}) + 1$$$ points. For example, when there are 60 players, the first player to reach the finish line will gain 60 points for their squad. The 2nd player will gain 59 points, etc. Other players who fall into the slime will score 0 points. Because the slime rises continuously, players who are slow will eventually fall into the slime. The total score of a squad is the sum of individual scores of the 4 members.

[video]fallguys_cut_2.mp4[/video]

There are $$$N$$$ squads ($$$4N$$$ players) including your squad. The squads are numbered from $$$1$$$ to $$$N$$$. There is a target number of qualifying teams $$$M$$$. Normally, if the squads at the $$$M^{th}$$$ and $$$(M + 1)^{th}$$$ positions have different scores, the top $$$M$$$ squads with the highest total score will qualify and the rest will be eliminated. If the squads at the $$$M^{th}$$$ and $$$(M + 1)^{th}$$$ positions have the same score, squads that tie for the $$$M^{th}$$$ position will all be eliminated. However, when top $$$M + 1$$$ squads all have the same score, the other squads that score less will be eliminated instead.

In the middle of the race, $$$F$$$ players have reached the finish line. The $$$i$$$-th player to reach the finish line is from squad $$$A_i$$$. Also, $$$S$$$ players fell into the slime. Their squad numbers are $$$B_1, B_2, \dots, B_S$$$.

You would like to know if the set of qualifying teams have been determined already, regardless of the outcome (order of finishing the race or whether they fall into the slime) of the remaining players. To save time, the game can end the round early if the set has been determined.

In the stock market, we like to analyse the change in price within some time intervals. Sometimes, it may provide insights for us to predict the price trends. In this task, you are required to analyse every ($$$M + 1$$$)-day interval over the $$$N + 1$$$ days of the market.

The $$$N$$$ changes in prices between days are given. Let $$$P_i$$$ be the stock price of Day $$$i$$$, $$$A_i$$$ denoted the change $$$P_{i + 1} - P_{i}$$$.

We are interested in finding the maximum continuous decline in the stock price at some time intervals. For each $$$1 \leq i \leq N$$$, we want to find that for the interval of last $$$M$$$ values up to $$$A_i$$$, i.e. the range $$$max(1, i - M + 1)$$$ to $$$i$$$ (inclusive) in $$$A$$$.

For example, if we are considering the interval with $$$7$$$ values $$$[-3, -5, 2, -3, -2, -2, 4]$$$. There are $$$2$$$ ranges of continuous decline, which are $$$[-3, -5]$$$ and $$$[-3, -2, -2]$$$. The sum of the first range evaluates to $$$-8$$$, and the sum of the second range evaluates to $$$-7$$$. Since the magnitude of $$$-8$$$ is larger than $$$-7$$$, the maximum continuous decline of this interval is $$$-8$$$.

If the interval only contains non-negative numbers, the maximum continuous decline should be considered as $$$0$$$.

Please find the answers to all intervals, $$$max(1, i - M + 1)$$$ to $$$i$$$ (inclusive) for all $$$1 \leq i \leq N$$$.

HDL is a multinational corporation which is renowned in logistics shipping service. You, a computer science student, would love to enroll their technology graduate trainee program. After 5 rounds of interview, you have made it to the final one, which is a technical round with the senior manager. He gave you an intricate problem that the company is encountering at the time:

In the HDL logistics network, there are $$$N$$$ shipping stations and $$$M$$$ 1-way shipping routes, meaning that station $$$U_i$$$ can send goods to $$$V_i$$$ with $$$D_i$$$ days. Among the $$$N$$$ shipping stations, there are $$$P$$$ gift's locations, $$$Q$$$ receive locations and 1 headquarter. Each of the $$$P$$$ gift's locations has $$$A_i$$$ gifts in the inventory and they can send the gifts to other stations through the network. Each of the $$$Q$$$ receive locations need to receive $$$B_i$$$ gifts. For the headquarter, it has unlimited number of gifts in the inventory but all gifts sent from headquarter spend double days to pass through a shipping route (all $$$D_i$$$ are doubled). Please note that one station can be headquarter, gift's location and receive location at the same time. Also you can send unlimited gifts through a shipping route at the same time. Find the earliest day that all $$$Q$$$ receive locations receive at least $$$B_i$$$ gifts, or tell it is impossible.

Struggling right after you heard the problem, the senior manager smirked, "Don't worry, many interviewees failed this task, you are just one of them…". To stand on your dignity, please solve the problem (and get the job).

Ian recently bought a Nintendo Switch using the consumption voucher. He wanted to buy games from Nintendo e-shop but found that the games are way too expensive. Fortunately, the games are discounted on e-shop from time to time.

Ian sees that there are $$$N$$$ games listed on e-shop, with a price of $$$A_1, A_2, \dots, A_{N-1}, A_N$$$ dollars respectively. He has $$$D$$$ days (Day $$$1$$$ to Day $$$D$$$) to buy games with a total budget of $$$K$$$ dollars. Since Ian needs time to play the game, he would buy a maximum of $$$1$$$ game each day (can be $$$0$$$). Also, he would not buy the same game more than once.

Noted that counting from Day $$$1$$$ (today), the $$$i$$$-th game would be put to a discounted price of $$$P_i$$$ (which is obviously smaller than $$$A_i$$$) if that day is a multiple of $$$i$$$. For example, the $$$3$$$-rd game would be sold at price $$$P_i$$$ at day $$$3$$$, $$$6$$$, $$$9$$$, ... and so on.

Please help Ian to find the maximum number of games he could buy within his budget.

Recently, Justin have learned the FFT (Fast Fourier Transform) algorithm. To show his understanding of the related topics, he creates the following problem for you to solve.

You are given two strings $$$S$$$ and $$$T$$$ containing only lowercase English letters. The length of the two strings can be defined as $$$|S|$$$ and $$$|T|$$$, respectively. The indices of $$$S$$$ and $$$T$$$ start at 1. We use $$$S_i$$$ to denote the $$$i^{th}$$$ character of $$$S$$$ and similarly $$$T_i$$$ for the $$$i^{th}$$$ character of $$$T$$$.

Justin defines a new operator $$$\otimes$$$, which can by applied to these two strings. The result of $$$S \otimes T$$$ is an array $$$A$$$ of length $$$|S| + |T| - 1$$$. The value of $$$A_i$$$ for $$$i = 1$$$ to $$$|S| + |T| - 1$$$ is:

$$$$$$ \large A_i = \sum_{k = \max(1, i - |T| + 1)}^{\min(i, |S|)} [S_{k} = T_{i - k + 1}] $$$$$$

Here $$$[...]$$$ is the Iverson bracket. $$$[P]$$$ is defined to be 1 if $$$P$$$ is true, and 0 if it is false.

Justin wants you to calculate the resulting array. For simplicity, he also gives you an integer $$$M$$$ to compress the array, so you only need to output a single integer $$$ans$$$, which can be calculated by the following formula:

$$$$$$ \large ans = (\sum_{k=1}^{|S| + |T| - 1} A_k \cdot M^{k - 1}) \mod 998244353 $$$$$$

In Karaoke, you are usually given a fixed amount of time to sing songs you like (e.g. 3 hours) and you can choose any songs that are available via the karaoke screen. Once time runs out, the screen will be automatically locked such that you can still finish your current song, but you would not be able to select any more songs nor proceed to the next songs.

In order to "extend" the singing time, people will usually choose the longest song available right before the screen is locked out so that they can still sing for the longest time after the screen is locked. In a popular karaoke chain, this song happened to be 勁歌金曲2 (For the sake of this task, let's call it "Golden Songs") by Leo Ku. The KTV of this song is 12 minutes and 48 seconds (or 768 seconds) long while a typical song is only about 3-5 minutes long. Therefore, if you pick Golden Songs as your last song right the screen is locked, instead of other songs, you would typically get to sing for at least an additional 7 minutes. Therefore, as a smart customer singing often in Karaoke, you look to maximize your singing time.

Formally, you have $$$T$$$ seconds of singing time remaining ($$$1 \le T \le 18,000$$$). The screen will be automatically locked at the $$$T$$$-th second, meaning that the latest time to start a new song would be the $$$T-1$$$ second. In addition to Golden Songs, you will have an additional 3 songs that you can choose before the screen is locked. The three songs will be $$$A$$$, $$$B$$$, and $$$C$$$ seconds long respectively ($$$180 \le A, B, C \le 300$$$). ALL songs can be played an unlimited number of times (as long as the screen is not locked) but must be played in full (i.e. it is not possible to play only part of the songs). For the sake of this task, assume that it will take no time to switch to the next song and there are currently no songs playing. Because you are too excited to sing, you would not leave any idle time in the karaoke (i.e. you must be playing a song at all times). Your task is to find out the maximum singing time possible.

Psychology has explained the fact that when people play the Rock-Paper-Scissors game, they tend to select moves repetitively. To experiment with this fact, Lucas has designed a Rock-Paper-Scissors game where each player always play the same move.

The game involves two teams, team A (with $$$N$$$ players) and team B (with $$$M$$$ players). Initially, all players are aligned on a straight line. All team $$$A$$$ players are positioned on the left while all team $$$B$$$ players are positioned on the right. Each player has a fixed move in the Rock-Paper-Scissors game, which is either rock, paper or scissors. All players do not change their moves throughout the game.

When the game starts, players will start moving continuously towards the other team, all with a common constant speed. Once two players meet head-to-head, they will play a Rock-Paper-Scissors game with their determined moves. The winner of the Rock-Paper-Scissors game can continue moving while the loser will be eliminated from the game. If there is a draw, the winner will be decided randomly.

You may have noticed that when all players from either team A or team B are eliminated, the remaining players will continue moving forever. Lucas is interested in investigating this scenario. Hence, he asks you to find the number of players from both teams who can possibly survive in the game and keep moving until the death of the universe.

In the Rock-Paper-Scissors game, Rock beats Scissors, Scissors beats Paper and Paper beats Rock. There is a draw if and only if two players make the same move.