Your aunt brings you a cake consisting of $$$N$$$ pieces arranged in a straight line, labeled as cakes $$$1, 2, 3, \ldots, N$$$. Initially, each piece of cake has a deliciousness value of $$$0$$$. You can choose to eat the $$$i^{th}$$$ piece of cake, provided that neither of its adjacent pieces has been eaten and that the $$$i^{th}$$$ piece is not at the edge. Once you eat a piece of cake, it will distribute deliciousness to its adjacent pieces, keeping going until it hits the edge or its adjacent pieces have already been eaten. Once the cake distributes deliciousness to all the pieces it can, for every $$$j^{th}$$$ piece that got distributed in the previous step, its deliciousness value will increase by $$$|i-j|$$$ .

You will continue to eat cake until there are no more pieces that can be eaten under the given conditions. At that point, you can use a special ability that allows you to eat all the remaining pieces at once. Do you want to know how much deliciousness you can consume to maximize the total deliciousness of the cake?

Your father once shared with you a thrilling story from his days as a spy during a family reunion. He had traveled around the world gathering critical information, and one of his favorite memories was from a mission that required him to infiltrate a secret organization.

On that mission, his objective was to retrieve a report hidden in the deepest vault of a heavily secured basement. To access the vault, he had to crack a keypad, which required a passcode composed of English letters. Although he didn't know the passcode, luck was on his side. While hiding in a nearby vent, he overheard the organization's boss entering the code. He couldn't see the keypad, but he could still hear the sounds of the keys being pressed.

The keypad worked like the multi-tap system found on old phones, where pressing a key multiple times cycles through the letters associated with that key. If, for example, the passcode was $$$cat$$$, the boss would have to press the $$$2$$$ key three times for $$$c$$$, pause, press $$$2$$$ again for $$$a$$$, pause, and then press $$$7$$$ once for $$$t$$$.

Figure B.1: Examples of the keypad

Typically, pressing a key more times than the number of characters it represents will cycle back to the first character. However, the boss was extremely cautious and never pressed a key too many times. For instance, he would never press the $$$2$$$ key four times to type the letter $$$a$$$.

Each key produced a distinct pitch, and your father, with his keen ear, could identify which buttons were pressed. He jotted down the tapping sequence in his notebook but didn't record the pauses. For instance, if the passcode was $$$cat$$$, he would have written down $$$22228$$$.

Later, he realized he could simply have slipped into the vault before the door shut completely. Using his stealth skills, he managed to enter the vault, retrieve the report, and escape the building without being detected.

A few days after the mission, curiosity got the better of him. He looked back at the tapping sequence he had noted and wondered about the passcode. Now you are also intrigued; what passcode could it possibly be ?

Throughout heaven and earth, I alone am the catter one.

— Jack probably never said this.

After returning from catching grasshoppers, Jack finds his cat, Salmon, has brought $$$N$$$ of his friends(cats), numbered $$$1$$$ to $$$N$$$, to the house. He decides to prepare food for all the cats.

Aside from the food dedicated for Salmon, there are currently $$$M$$$ types of cat food in his house ($$$M \geq N$$$). Jack is a proud "catterer", a person who specializes in catering to cats. He can estimate how much happiness each cat has eating each type of food. Formally speaking, Jack can find a matrix $$$A$$$ size $$$N \times M$$$ where $$$A_{ij}$$$ is how much happiness cat $$$i$$$ has when eating food type $$$j$$$.

The problem is, cats refuse to have the same types of food. He must prepare one type of food among $$$M$$$ types for each of $$$N$$$ cats such that there are no pairs of cats that receive the same food. He wants to $$$\textbf{maximize the minimum happiness among all cats}$$$. That is, if cat $$$i$$$ gets the food type $$$p_i$$$, he wants to $$$\textbf{maximize}\ min(A_{1p_1},A_{2p_2},\dots,A_{Np_N})$$$. Help him find the way to prepare foods to achieve his objective.

Salmon blessed you good luck for the contest.

A hospital in some city has been researching technology which can completely revolutionize the current remedial methods. For this purpose, the simulation was created to evaluate the cost.

There is a disinfection patch with coordinate $$$(0,0)$$$ as the center of the patch. The $$$N$$$ drops of disinfection substances will be applied on the patch coordinate $$$(x_i,y_i)$$$. The $$$N$$$ types of bacteria have also been placed on coordinate $$$(a_i,b_i)$$$. All of the substances can disinfect any type of bacteria, but can only disinfect 1 type of bacteria per drop, and only disinfect at the point that the substances reside.

The disinfection patch can also be stretched out with the same non-negative integer $$$S$$$ both horizontally and vertically and can't be rotated or flipped. After that, the disinfection patch center can also be placed on any integer coordinates. The disinfection substances coordinate will also be changed as follows.

1. If the original coordinate for substance is $$$(p,q)$$$, then the new substance coordinate is $$$(S\cdot p,S\cdot q)$$$.

2. Assume that the center of the patch is $$$(X,Y)$$$, then the new substance coordinate is $$$(S\cdot p+X,S\cdot q+Y)$$$.

To simulate real-life situations for reducing cost, only one disinfection patch was given to you. Your task is to determine the value of $$$S,X,Y$$$ that can disinfect all of the bacteria for each simulation.

A company is in the process of designing a groundbreaking new game and has decided to hold several executive meetings to kick off the project.

Over the next $$$t$$$ days, the company needs to schedule $$$n$$$ executives to attend these meetings. On any given day, $$$i$$$, the company requires at least $$$a_i$$$ executives to be present.

Each executive's "satisfaction" is determined by the length of their longest continuous break from attending meetings. For instance, if an executive attends meetings on days $$$1$$$, $$$5$$$, and $$$7$$$ during a $$$7$$$-day period, their satisfaction value would be 3, representing the break they get from day $$$2$$$ to day $$$4$$$. If an executive does not attend any meetings during the entire period, their satisfaction value would be $$$t$$$.

You have been tasked by the CEO of the company to determine the maximum total satisfaction of all executives.

It is the last day of your summer break, and you currently have nothing to do, so you start daydreaming about a problem you had heard once before...

Given a grid with $$$R$$$ rows and $$$C$$$ columns, your task is to cover all the cells with some $$$T$$$-shapes so that each cell is covered by exactly one $$$T$$$-shape. $$$T$$$-shapes must not exceed the boundary of the grid.

More formally, a $$$T$$$-shape in the grid is uniquely determined by six non-negative integers $$$(x,y,u,l,d,r)$$$, where $$$(x,y)$$$ represents the center point of the $$$T$$$-shape, and $$$u$$$, $$$l$$$, $$$d$$$ and $$$r$$$ represent the lengths of the arms of the $$$T$$$-shape in the upward, leftward, downward and rightward directions, respectively.

The six integers must satisfy these conditions:

• $$$0 \le u,l,d,r$$$, $$$1 \le x \le C$$$, $$$1 \le y \le R$$$
• $$$1 \le x-l$$$ and $$$x+r \le C$$$
• $$$1 \le y-u$$$ and $$$y+d \le R$$$
• Exactly one of the values of $$$u$$$, $$$l$$$, $$$d$$$ and $$$r$$$ must be zero.

Figure F.1: Examples of some $$$T$$$-shapes

In ancient times, three neighboring kingdoms — Antheon, Beelor, and Cicadale —were ruled by close friends.

To symbolize their friendship, they constructed three straight roads linking the kingdoms together. The first road connecting Antheon to Beelor had Statue of Unity exactly at the halfway of it. The second road connecting Beelor to Cicadale had Statue of Friendship exactly at the halfway of it. The third road connecting Antheon to Cicadale had Statue of Harmony exactly at the halfway of it.

For example, if Antheon is located at $$$(1,2)$$$, Beelor at $$$(3,6)$$$ and Cicadale at $$$(7,4)$$$, then:

• Statue of Unity would be at $$$(\frac{1+3}{2},\frac{2+6}{2})=(2,4)$$$.
• Statue of Friendship would be at $$$(\frac{3+7}{2},\frac{6+4}{2})=(5,5)$$$.
• Statue of Harmony would be at $$$(\frac{1+7}{2},\frac{2+4}{2})=(4,3)$$$.

Figure G.1: Illustration of the location of the kingdoms and the statues corresponding to the example above

Tragically, the kingdoms were eventually wiped out by a devastating onslaught of pesticides, leading to their complete destruction. Yet, the three ancient statues somehow withstood the test of time, standing as the only surviving remnants of these lost civilizations.

Now, an archaeologist is determined to find the original locations of these lost kingdoms. He believes that the statues hold the clues to uncovering where the kingdoms once were. Your task is to help him figure out the locations of the kingdoms based on the positions of the surviving statues.

A sequence $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{good}$$$ if and only if, $$$n=1$$$ $$$\textbf{or}$$$, for some $$$\textbf{non-negative integers}$$$ $$$K$$$ and $$$X$$$, the sequence satisfies: $$$$$$\displaystyle K \cdot \min(b[1],b[2],\dots,b[n]) + X \cdot \max(b[1],b[2],\dots,b[n]) \geq b[n]^2 + \sum_{i=1}^{n-1} b[i] \cdot b[i+1]$$$$$$

A sequence $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{best}$$$ if and only if $$$\textbf{every subsequence}$$$ of $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{good}$$$.

A sequence $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{heavenly}$$$ if and only if $$$\textbf{every permutation}$$$ of $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{best}$$$.

Given the sequence $$$a[1],a[2],a[3],...,a[n]$$$, you have to answer $$$n-1$$$ questions. The $$$i$$$-th question is " Given integers $$$L$$$ and $$$R$$$, what is the minimum $$$\textbf{non-negative integer}$$$ $$$K$$$ that makes the sequence $$$a[1],a[2],a[3],\dots,a[i+1]$$$ $$$\textbf{heavenly}$$$, if you can choose any integer $$$X$$$ from the given range $$$L$$$ to $$$R$$$ ? "

The $$$\textbf{subsequence}$$$ of a sequence can be obtained by erasing some (possibly zero) elements from the array. (not necessary to remove consecutive elements)

A permutation of size $$$N$$$ is a sequence of $$$N$$$ positive integers containing the numbers $$$1$$$ to $$$N$$$ where each number appears exactly once in the sequence. For example, $$$[1,4,5,3,2]$$$ is a permutation of size $$$5$$$, while $$$[1,1,4,3,5]$$$ and $$$[1,6,2,3,4]$$$ are not.

We can compare two permutations using lexicographical order. For two permutations $$$p$$$ and $$$p$$$ of the same size $$$N$$$ where $$$p = [a_1,a_2,...,a_N]$$$ and $$$q = [b_1,b_2,...,b_N]$$$, we define $$$p$$$ is smaller than $$$q$$$ if and only if there exists an index $$$i$$$ such that $$$a_j=b_j$$$ for every $$$j \lt i$$$ and $$$a_i \lt b_i$$$. For example, $$$[1,3,4,2,5]$$$ is ordered before $$$[1,3,5,2,4]$$$.

Two permutations $$$p$$$ and $$$q$$$ of size $$$N$$$ are considered an ideal pair if, when all $$$N!$$$ permutations of size $$$N$$$ are arranged in a circle based on lexicographic order, permutation $$$p$$$ and permutation $$$q$$$ are positioned directly opposite each other in the circle.

Figure I.1: Example of the circle of permutations of size $$$3$$$.

Given a permutation $$$p$$$, your task is to identify the permutation $$$q$$$ that together forms an ideal pair.

A billionaire with a vast and diverse collection of jewels, each featuring up to two distinct colors, has decided to showcase his collection in a grand exhibition. His aim is to arrange the jewels so that every color present in his collection is prominently displayed.

He wants to ensure that every color is uniquely represented by one jewel. If a jewel has the color $$$c_1$$$ and $$$c_2$$$, and is used to represent the color $$$c_1$$$, it cannot be used again to represent the color $$$c_2$$$, and vice versa.

In addition to showcasing every color, the billionaire wants to flaunt his wealth by maximizing the total price of the displayed jewels as well.

Your task is to assist him in selecting the jewels for the exhibition according to these criteria.

The primary school main event for every year is field trips, mainly consisting of a group of energized kids, organizing a special activity for this year.

The activity is to rally to the different places on a map size $$$N\times M$$$ in order to collect the score; each position is assigned a score $$$S_{i,j}$$$ for position $$$(i,j)$$$. The position can be considered as a point in $$$XY$$$ coordinate. All of the kids will be given a map and choose a partner to form a pair. Each person in the pair will start in position $$$(1,1)$$$ and $$$(1,M)$$$ before venturing on their own.

With consideration of limited time and the risk of injury, the school imposes four special rules for the activity.

1. If the kid stays at position $$$(x,y)$$$, this kid mustn't rally to position $$$(a,b)$$$ when $$$(a \leq x)$$$.

2. The path to rally from one position to another position must be a straight line.

3. The pairs' rally paths mustn't intersect at any point of the path regardless of the time that they reach each position.

4. The kid must stay in the area of the map and can choose to finish their rally at any place on the map.

The score of an individual person is the sum of the score on the persons' rally path. The final score for this activity is calculated by the multiplication of the pairs' scores. Alice and Bob want to form a pair and have the highest score in order to boast to their friends.

Your task is to assist Alice and Bob in reporting the maximum possible score that Alice and Bob can achieve.

Let's put on our thinking caps! Hmm... hmmhmm, hmmhmm... ah, I got it! — Lulu

As the sun rose over Runeterra, Lulu the yordle skipped through the land, always on the lookout for magic and adventure. Today, she discovered something extraordinary — a glowing thread nestled in the roots of an ancient tree.

"This must be the Legendary String $$$T$$$!" Lulu gasped, remembering the tales of its magical properties. Holding the string, Lulu's mind flooded with memories of her adventures and the friends she'd met along the way.

But this wasn't just a simple discovery. The string held a puzzle, one tied to the names of her friends. Lulu could feel the magic in the air, urging her to solve it. For each of her friends names, she needs to solve this problem, "What's the minimum number of characters you need to delete from the legendary string $$$T$$$, so that it will contain her friend's name as a substring or determine if it's impossible?".

She turned to you, her eyes sparkling. "I need your help to figure this out! Let's unlock its secrets together!"

*A substring of string $$$s$$$ is a continuous segment of letters from $$$s$$$. For example, eter is a substring of runeterra and era is not.

In the town where Jack lives, there are $$$N$$$ villages and exactly $$$N - 1$$$ bidirectional roads which connect every village; there is $$$\textbf{exactly one}$$$ shortest path for commuting between any two villages. There is also $$$\textbf{exactly one}$$$ pearl shop in each road. Each shop sells $$$\textbf{exactly one}$$$ type of pearl. The shop on the $$$i^{th}$$$ road sells pearl type $$$a_i$$$ and is limited to $$$b_i$$$ balls of pearl for each person. It is guaranteed that the shop will be able to provide any customers up to $$$b_i$$$ balls.

In this town, there are $$$M$$$ types of pearls. For each type, the price per ball will be the same in any shop.

There is a custom in this town that when a man wants to propose to a woman in a different village, he will pick one type of pearl and buy that type $$$\textbf{as many balls as possible}$$$ from shops along the shortest path from his village to her village. He will pick a type of pearl that $$$\textbf{maximizes money spent}$$$. Later, the pearls will be made into a necklace.

Jack has recently become an accountant of the bachelor club of the town. The bachelor club mainly collects money from its members to support those who are going to make proposals. When he became the accountant, he just realized that the old accountant forgot to record the expenses during a period of time. Fortunate enough, there are records of events that occurred during that period, and also the records of pearl prices. Initially, the cost per ball of pearl type $$$j$$$ is $$$c_j$$$. Then, there are $$$Q$$$ following events in total which can be classified as two types:

• $$${Type\ 1:}$$$ A man in village $$$x$$$ proposed to a woman in village $$$y$$$.
• $$${Type\ 2:}$$$ The cost for a single ball of pearl type $$$j$$$ was changed to $$$c^{'}_{j}$$$ dollars. Pearl type $$$j$$$ will have price $$$c^{'}_{j}$$$ until there is an event that updates the price of pearl type $$$j$$$.

Help Jack find the expense for each proposal, and Jack will reward you with his grasshoppers!

After the disaster hack by the machine, the new YoRHa project decides to employ a new security system. This system is among the most sophisticated ever devised, employing advanced cryptographic algorithms to ensure that vital information remains secure. At the heart of this security lies a unique hashing mechanism, where each piece of data is represented by the mathematical operation $$$x^y \pmod{p}$$$, where $$$p$$$ is a prime number. This system transforms every input into a signature, a seemingly random sequence that only the YoRHa servers can decode.

However, as the war with the machine lifeforms drags on, concerns arise among the operators. What if multiple pieces of information, when processed by this hashing algorithm, result in the same signature? This could lead to a catastrophic failure in the security system, where critical data is overwritten or lost due to collisions in the hash function. To prevent this, operator 21O is tasked with an important mission: to compute how many different inputs could possibly hash into the same signature for every possible output.

For every $$$k=1,2,3,\dots,p-1$$$, the operator must analyze how many pairs of integers $$$1 \leq a,b \leq p-1$$$ satisfies $$$a^b \equiv k \pmod{p}$$$. By determining how many different combinations result in the same hash, they can assess the risk of collisions and adjust the security protocols accordingly. This analysis becomes a race against time, as the integrity of YoRHa's communication and data storage hinges on the successful execution of this mission. The fate of the war may very well depend on the operator's ability to ensure that the security system remains unbreakable.