Ben heard about studies by Emmons and McCullough that suggest that intentionally practicing gratitude has a lasting effect on people's happiness. Since he wants to be happy too, he decided that at the end of each day he will think back over the past day and write down three things he is thankful for, one thing per line. At the end of $$$N$$$ days in which he practiced this exercise, he was curious to know which things appear the most on his list. Help Ben get the $$$K$$$ things he was grateful for most frequently.

Ann is decorating her office with the coolest arrangement of lights ever. She is using very long LED strips, where each individual cell is switched on or off every second, according to the following simple and pretty algorithm. At each step, the status of each cell (0 for off and 1 for on) is determined from the status of its two neighbor cells on the strip (left and right) and its own status, according to the following table:

$$$$$$ \begin{array}{l|c|c|c|c|c|c|c|c} \textbf{Current pattern} & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000 \\ \hline \textbf{New state for center cell} & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ \end{array} $$$$$$

Ann is choosing an initial configuration for the cells and she marvels at the resulting animation, which happens to be highly similar to Conway's Game of Life, with interesting behavior on the boundary between stability and chaos.

The past year has been difficult, with a virus spreading among the population. Fortunately, Alice knows that one of the keys to be healthy is to keep a safe distance from other people.

Alice is currently in a closed room, represented in the $$$2D$$$ plane, with width $$$X$$$ and height $$$Y$$$. There are $$$N$$$ other people inside the room, and we're given their $$$(x_i, y_i)$$$ coordinates.

We consider Alice and the $$$N$$$ people as points in the $$$2D$$$ plane. Alice's initial position is $$$(0, 0)$$$ and she wants to move to the exit at position $$$(X, Y)$$$. She can move freely in any direction inside the room, but can not step outside the room bounds.

Find the maximum distance Alice can keep from other people while moving from $$$(0, 0)$$$ to $$$(X, Y)$$$.

Pheobe has heard that exercise has a tremendous affect on both physical and mental health. She never went jogging before, and she wants to try it out. However, she knows that she gets bored quickly and it is difficult for her to repeatedly do the same thing. In order to get into the habit of jogging, Pheobe decided to take up a challenge: she will go out for a run every evening as long as she finds an interesting path to take. For her, a path is interesting if it goes through a street where she did not run before. Pheobe asks for your help in understanding what is the maximum number of days she can run if she plans well.

Pheobe gives you as input a description of her neighborhood. She lives on an intersection, and she describes all of the intersections in the neighborhood. She also tells you which intersections are connected by streets, and what is the length of each street in meters. Every street connects two different intersections, and it is not possible that two different streets connect the same two intersections. In addition, you may assume that Pheobe only describes streets that can be reached from her home and that streets can be traversed in both directions as Phoebe is on foot.

A valid run starts and ends in Pheobe's home, and its length should be within the range that Pheobe specifies. When Pheobe enters a street, she does not have to go through the entire street (she is allowed to turn around at any point), but even if she does that, it counts as if she has seen the entire street for the purpose of determining whether runs are interesting. A run is considered interesting if it includes a street (or a segment of it) that did not appear on previous runs. Reaching an intersection does not count as visiting all streets adjacent to it.

This summer, you plan to organize a large party and invite many friends. They have a sweet tooth, so you plan to bake nice cakes for them. You know the recipe for a nice chocolate cake, and you want to cook as many of them as possible.

Given the $$$N$$$ ingredients needed to make a single cake and the ingredients that you have in your kitchen, how many cakes can you make?

The Happy Tree Friends have gathered for their annual meeting, in which they take their most important decisions for the year to come. This year, they will set up a mentoring program to help each other take better care of their loved ones. This programme follows a tree-like hierarchical structure as follows.

The $$$N$$$ members of the programme are ranked from $$$1$$$ to $$$N$$$ (each rank is assigned once), by increasing seniority. For the mentorship programme to be efficient, a person ranked $$$A$$$ can mentor a person ranked $$$B$$$ only if $$$A \gt B$$$. The most senior Happy Tree Friend can have no mentor, but everybody else has a unique mentor. Conversely, everybody is allowed to mentor from zero to two people.

However, Mr. Pickles, who was assigned the rank $$$R$$$, plans to take a sabbatical this year. Thus, he will not be able to mentor anybody, and the Happy Tree Friends should choose their hierarchical structure among those trees in which the node labelled $$$R$$$ is a leaf.

Aiming to help his friends to choose such a tree, Mr. Pickles decides to first count how many trees would match his constraint. Unfortunately, he stopped school early, and thus did not learn how to manipulate integers of arbitrary size. Instead, he counts modulo $$$M$$$, where $$$M$$$ is a fixed positive integer: this is already enough for most purposes in life.

What is the number $$$L$$$ that Mr. Pickles will obtain after counting all suitable trees?

After all these months of lockdown, you are tired of the interior decoration of your home and decide to redesign it. Hence, you read many blog posts and magazines about Feng Shui decorating and other recent trends on home design. After some time of thinking, you decide to reproduce the idea of the famous designer Sweta Marc for replacing your bookcase with a new one you will build.

According to S. Marc, a harmonious bookcase always has several shelves spaced in an heterogeneous manner, and always following some very precise rules. More precisely, such a bookcase has a serenity value $$$N$$$ and is composed of $$$K+1$$$ shelves spaced by $$$s_1, \ldots, s_K$$$ millimeters between each other, from the bottom to the top. According to S. Marc ideals, these spaces should verify the following properties:

1. They should be heterogeneous, i.e., no two spaces have the same height.
2. They should be not too high, i.e., for all $$$i \in [1, K]$$$, we should have $$$0 \leq s_i \lt N$$$. Note that one of these spaces might actually have size $$$0$$$: this is one of the oddities which make Sweta's tastes so visually attractive (arguably, this is a loss of space, but you are ready for that in the name of elegance, well-being... and trendiness).
3. They should be serene, i.e., for all $$$i \in [1, K-1]$$$, Sweta prefers if $$$s_{i+1}$$$ is congruent modulo $$$N$$$ to $$$s_i$$$ plus the number of divisors of $$$s_i$$$. (Yes, Ms. Marc is sophisticated and loves arithmetic.)

You tried to design a bookcase according to the advice of Sweta Marc, but you find it hard to satisfy all the requirements. The only few solutions you found result in a bookcase which is too tall for your place.

Therefore, you decide to write a program which, given the number of shelves $$$K$$$ and the serenity value $$$N$$$, computes the values of the spaces $$$s_1, \ldots, s_K$$$ of one of the minimum height bookcases, i.e. a bookcase where the sum of spaces $$$s_1 + \cdots + s_K$$$ is the smallest.

Bob has a lot of mini figurines. He likes to display some of them on a shelf above his computer screen and he likes to regularly change which figurines appear. This ever-changing decoration is really enjoyable. Bob takes care of never adding the same mini figurine more than once. Bob has only $$$N$$$ mini figurines and after $$$N$$$ days he arrives at the point where each of the $$$N$$$ figurines have been added and then removed from the shelf (which is thus empty).

Bob has a very good memory. He is able to remember which mini figurines were displayed on each of the past days. So Bob wants to run a little mental exercise to test its memory and computation ability. For this purpose, Bob numbers his figurines with the numbers $$$0, \dots, N-1$$$ and selects a sequence of $$$N$$$ integers $$$d_0 \dots d_{N-1}$$$ all in the range $$$[0;N]$$$. Then, Bob computes a sequence $$$x_0,\dots, x_N$$$ in the following way: $$$x_0=0$$$ and $$$x_{i+1}=(x_i+y_i)\mbox{ mod } N$$$ where $$$\mbox{mod}$$$ is the modulo operation and $$$y_i$$$ is the number of figurines displayed on day $$$d_i$$$ that have a number higher or equal to $$$x_i$$$. The result of Bob's computation is $$$x_N$$$.

More formally, if we note $$$S(i)$$$ the subset of $$$\{0,\dots,N-1\}$$$ corresponding to figurines displayed on the shelf on day $$$i$$$, we have:

• $$$S(0)$$$ is the empty set;
• $$$S(i)$$$ is obtained from $$$S(i-1)$$$ by inserting and removing some elements.

$$$$$$ \begin{array}{l} x_0 \leftarrow 0 \\ \text{for } i \in [0;N-1] \\ \;\;\;\;\;\;\; x_{i+1} \leftarrow (x_i + \#\{y \in S(d_i) ~\mbox{ such that } ~ y \ge x_i\}) \mod N \\ \text{output } x_N \end{array} $$$$$$

Bob asks you to verify his computation. For that he gives you the numbers he used during its computation (the $$$d_0, \dots, d_{N-1}$$$) as well as the log of which figurines he added or removed every day. Note that a mini figurine added on day $$$i$$$ and removed on day $$$j$$$ is present on a day $$$k$$$ when $$$i\leq k \lt j$$$. You should tell him the number that you found at the end of the computation.

Ariadna's blog is filled with delicious recipes and sensible advice for a healthy and balanced lifestyle. Unsurprisingly, it has thus gathered an impressive number of readers. This reader base is now stable, and Ariadna feels that it would be useful for them to interact more and form a tighter community, one that is not solely anchored to the blog.

Ariadna knows that some of the readers are already friends or acquaintances, and therefore have each other's email addresses. She thinks that a good start for developing the community would be for everyone to have everyone else's email address, so that everyone would be able to reach out to the entire group. Since she knows her blog's readers also greatly enjoy doing things in a "decentralized" fashion, she therefore devises the following protocol, to be started on day $$$D$$$:

• Every day at 8am, everyone sends the current list of contacts in their address book to all of the contacts in their address book.
• Every day at 8pm, everyone updates their address book, adding any new received email addresses.

You are a skillful hacker and you have managed to get access to all of the blog readers' address books. You would like to surprise and impress Ariadna by notifying her of whether or not the process she proposes will lead to everyone getting everyone else's address. Moreover, if the process is meant to succeed, you want to give her a good estimate of how many days it would take. More precisely, if the process succeeds, you can either give her:

• the number $$$E$$$ of days (including the first day) elapsed until the last update takes place, or
• the number of days (including the first day) elapsed until the process has converged on everyone's side. Note that, according to Ariadna's definition, this is equal to $$$E$$$+1.

Daisy enjoys walking in mazes to evacuate the stress of a long day of work. The mazes that she likes are all composed of a set of rooms with one entry room, one exit room, and in each room there are several one-way doors leading to other rooms. Daisy's goal is to find a path from the entry to the exit.

Daisy has a technique to solve mazes. She has noticed that the different doors of any room have different colors and thus she can remember her path by keeping track of the colors of doors along her path. For that, she looks at the plan before entering the maze and builds a deck of colored cards corresponding to the colors of doors she needs to take. Whenever she enters a room, she goes through the door that has the color of the topmost card in her deck and then she discards this card.

It sometimes happens that Daisy's decks are "incomplete" and she arrives in a room with an empty deck or with a topmost card that has a color corresponding to none of the doors. In those cases, Daisy goes through one of the doors in the room and, instead of discarding the topmost card, she adds on top of her deck a card of the color of the door she took.

Let us consider the following example maze with three rooms and three doors: a red door from the entry to room 1, a second red door from room 1 back to the entry, and a blue door between room 1 and the exit. In this example maze (also depicted below) then:

• if Daisy starts with a deck containing a {red} card on top and a {blue} card below, she will go to room 1 and discard the red card, then go to the exit and discard the blue card;
• if Daisy starts with a deck containing a single {red} card then she will necessarily go to room 1 as a first step, discard the red card and from there she can choose to take the {blue} door and exit (it does not matter whether her deck is empty at the end) or she can choose to take the red door and goes back to her initial situation: in the entry room with a single red card;
• if she starts or arrives in the entry room with an empty deck, she will necessarily loop indefinitely. Indeed, the entry has only one door that leads to room 1. Once she arrives in room 1, her deck contains a {red} card on top and thus she has to take the {red} door and discard this card, which leads her back to the entry room with an empty deck.

Daisy knows that, in all of her labyrinths, she can always go from the entry room to the exit room with the right deck. However, some decks do not allow her to escape, whatever the choices she may ever do. She wonders: what is the minimal size of a deck that allows her to escape? Daisy gives you the plan of the maze and asks you to help her determine the minimal size of a deck that allows her go from the entry room to the exit if she makes the right choices.

Emily is tired of having studied at home throughout 2020. She has noticed the same tasks occur over and over: she has to cook and wash the dishes. Then it's time for her class; afterwards she resumes washing the dishes, has to attend another class, washes some more dishes before cooking and washing the dishes for the last time of the day.

There is a part of her day she loves, though: it's when the sequence of activities she is currently carrying out happens only once during her day. She rejoices the most when that activity sequence is unique and really short.

Each activity is represented by an uppercase letter. Given the list of activities Emily has to carry out today, help Emily find the best moment of her day by finding the shortest substring that only occurs once in the input.

If Cooking is C, Dishes is D, and Studying is S, the list of activities in the example above are C D S D S D C D, and the shortest substring that occurs only once is D C. (All the one-letter substrings and the other two-letter substrings occur at least twice).

Everybody is very happy to go back outside and to restaurants in Paris. However, for a while yet the restaurants have a very limited number of seats. We want to ensure that both restaurants can receive as many people as possible, and that customers go in their preferred seats.

We have $$$N$$$ customers, numbered from $$$1$$$ to $$$N$$$, and $$$M$$$ restaurants, numbered from $$$1$$$ to $$$M$$$. Each customer makes reservation in a subset of the restaurants, and give their list of reservations ordered by preference. Each restaurant ranks the reservations it received by some order of preference – for instance, the restaurant might wish customers who have signed up first to be ranked higher. Each restaurant $$$i$$$ also has a capacity $$$c_i$$$, i.e. the maximal number of customers it can support.

Your task is to find an allocation of some of the customers in restaurants such that the following conditions are fulfilled:

1. No restaurant places more customers than their capacity.
2. Each customer is given a table in at most one restaurant.
3. There is no restaurant $$$r$$$ and customer $$$c$$$ having made a reservation for $$$r$$$, such that:
   • $$$c$$$ has not been given a table or prefers $$$r$$$ to the restaurant he was given a table in, and
   • $$$r$$$ has some seats left or $$$r$$$ is full but prefers $$$c$$$ to at least one of the customers assigned to it.

Other remarks to note:

• Every customer has made at least one reservation.
• Restaurants only rank the customers having expressed a reservation for them. It is possible that a restaurant has no customers wishing to make a reservation.

Émile's dreams often feature people or animals who become distorted into others. Émile would like to show the enchanting world of his dreams to everybody by creating the very first animated cartoon, in black and white of course. After waking up, Émile only remembers the initial and final forms appearing in his dream, not the transformation itself, so he's asking you to reproduce these "morphings" by detailing the steps taken for transforming the first image into the second.

The images in Émile's dreams are not just any black and white image, they respect the following three constraints. First, all pixels on the border of the image – the leftmost and righmost columns, and the top and the bottom rows – have the same color. Second, the image does not contain any $$$2 \times 2$$$ square of the form

or .

The third constraint is more complex, and can be described as follows. Let us subdivide the image into regions, which are defined as the connected monochromatic areas of the image, i.e., they form the finest partition of the pixels such that any two adjacent pixels of the same color are in the same region. Two regions are considered adjacent if they contain adjacent pixels. In Émile's images, every region is adjacent to at most two other regions, and the region containing border pixels is adjacent to at most one other region.

You are given two black and white images of the same size $$$W \times H$$$, and your goal is to find a "morphing" transforming the first image into the second one. A morphing from image $$$A$$$ to image $$$B$$$ is a sequence of images starting with $$$A$$$ and ending with $$$B$$$ such that:

• each image (except the first) can be obtained from the previous one by flipping one bit;
• each image respects the three above constraints;
• the number of regions of each color does not change during the morphing.