Tic-tac-toe is a two-player game played on an initially empty $$$3 \times 3$$$ board, where players take turns alternately. The first player plays with the letter X, and the second with the letter O. On their turn, each player must choose an empty cell on the board and write their letter in it. The first player to form a vertical, horizontal, or diagonal line with three occurrences of their letter is the winner. If there are no empty cells left on the board where a move can be made, the result is considered a draw. The images below show some examples of possible final results in a game of tic-tac-toe.

Xavier and Olivia were fans of tic-tac-toe, but after a while, both learned to play optimally, and now the game has become boring because every time they play, the result is a draw. However, they came up with a new variant of the game, where $$$N$$$ restrictions are added before starting, which must be followed throughout the game.

Each cell on the board is assigned a number from 1 to 9, as shown in the image below, and then each restriction is defined by two integers $$$A$$$ and $$$B$$$, indicating that cell $$$B$$$ on the board cannot be used by either player if cell $$$A$$$ is empty.

Given $$$N$$$ restrictions, if Xavier plays first and both players play optimally, determine who will be the winner or if the result will be a draw.

Adela and Bastian are fans of riddles, and they recently came up with a new game, but they need your help to play it.

In this game, Adela first chooses a secret word $$$s = s_1s_2\ldots s_N$$$ of length $$$N$$$, formed by $$$N$$$ lowercase letters of the English alphabet $$$s_1, s_2, \dots, s_N$$$. Bastian knows the length $$$N$$$ of the secret word, but not the word itself.

To win the game, Bastian must determine whether the word chosen by Adela is periodic or not. To do this, Bastian can choose two integers $$$L$$$ and $$$R$$$, and ask the following question: Is $$$t = s_Ls_{L+1}\ldots s_R$$$ a period of $$$s$$$? Adela will always answer each question truthfully.

Adela and Bastian consider that $$$t$$$ is a period of a word $$$s$$$ if and only if $$$s$$$ can be obtained by concatenating $$$c \geq 2$$$ copies of $$$t$$$.

A word $$$s$$$ is periodic if $$$t$$$ is a period of $$$s$$$ for some $$$t$$$. For example: ab is the only period of abab, and both a and aa are periods of aaaa, while on the other hand ab and ababa are not periodic.

To make the game fun, Adela must set a limit on the number of questions that Bastian can ask. This limit must depend on the initial information that Bastian receives: the value of $$$N$$$. In particular, she wants the limit on questions $$$K$$$ to be the minimum possible, but in such a way that Bastian can win the game if he asks the $$$K$$$ questions optimally, having absolute certainty of always being able to find the correct answer, regardless of which word of length $$$N$$$ Adela chooses.

Help them to play their game by writing a program that, given the value of $$$N$$$, finds the limit on questions $$$K$$$ that they should use. Additionally, so that Bastian does not think that Adela cheated in case he loses, the program must indicate a set of $$$K$$$ questions with which Bastian could win.

A group of archaeologists recently discovered an ancient civilization in Egypt called Ngipto. The civilization lived in a desert, which is modeled as an infinite two-dimensional plane. In this desert, the Ngiptians built a pyramid with a polygonal base. Given a description of the pyramid and the position of the sun $$$(X_{sun}, Y_{sun}, Z_{sun})$$$, the archaeologists want to determine if there is any point in the desert where they can set up their camp sheltered from the sun.

More precisely, the base of the pyramid consists of a simple not necessarily convex polygon formed by $$$N$$$ points

Where the first two coordinates represent Cartesian coordinates in the plane of the desert, and the third coordinate represents the height, which for the points of the base is $$$0$$$ since they are on the plane of the desert.

The pyramid's apex is located at the point $$$(X_{ape}, Y_{ape}, Z_{ape})$$$ with $$$Z_{ape} \gt 0$$$, i.e. located above the plane of the desert. The points of the pyramid are exactly those that lie on some segment with one endpoint inside or on the edge of the polygon, and the other endpoint at the apex.

You are asked to determine if there exists any point in the plane of the desert sheltered from the sun, that is, any point in the plane of the desert outside the polygon such that the segment connecting it to the sun intersects the pyramid.

Ana, Beto, and Carla are playing a Tournament of Alliances with Points. Each of them has a score, and two of them will ally to form a duo. If the sum of the points of the allies exceeds the points of the third player, the duo wins. Otherwise, the other player wins alone.

Given the scores of the players, can someone win alone?

Within a well-known video game, our hero faces "The Beast", the final boss of the game, and wants to know if he is capable of defeating her or not.

The hero has $$$P$$$ power points and has $$$N$$$ different weapons at his disposal. Each weapon is characterized by three integers $$$A$$$, $$$B$$$, and $$$C$$$. When attacking with a weapon, if the hero currently has $$$P$$$ power points, he will have $$$\displaystyle{\left \lfloor \frac{P-B}{A}\right \rfloor}$$$ power points after the attack, inflicting damage to The Beast such that she loses $$$C$$$ health points. After hitting The Beast, the weapons break. For this reason, each weapon can be used at most once.

The hero wins the confrontation if he manages to defeat The Beast. To achieve this, his power points must be non-negative, and The Beast's health points must be zero or negative.

What is the maximum amount of health points $$$V$$$ that The Beast can initially have for the hero to be able to defeat her?

Note: $$$\lfloor x \rfloor$$$ is the largest integer such that $$$\lfloor x \rfloor \leq x$$$. For example, $$$\lfloor 2.5 \rfloor=2, \lfloor \pi \rfloor=3, \lfloor -2.75 \rfloor=-3$$$.

Mati has the results of the $$$N$$$ matches he played during the last league of virtual tennis, an individual sport where there are no ties, meaning that in each match a player either wins or loses.

The league organization has a certain fascination with streaks, and the way to obtain a player's final score is somewhat peculiar. A player earns one point for each match won and loses one point for each match lost. Additionally, if after finishing a match a player has at least 3 consecutive matches won including the last match, then they receive an additional point.

Can you help Mati calculate how many points he obtained?

Lucía is organizing two very important competitions: the Argentinian Programming Tournament (TAP in Spanish) and the University Pasapalabra Tournament (TUP in Spanish). These tournaments are held simultaneously at multiple venues.

To decorate these venues, Lucía bought triangular paper banners with letters, like the ones shown in the following image:

Lucía realized that she can rearrange the banners to form different words. Once arranged, she plans to combine some banners to create garlands, which will be sent to the various venues. All these garlands must have exactly three banners, either forming the word "TAP" or the word "TUP". If a garland does not meet these criteria, then it cannot be sent to the venues. Below is an example of how she can do this with the previous banners:

What is the maximum number of garlands that she can send to the venues?

In a field, there are $$$N$$$ rectangular fences, with the sides of the rectangles aligned to the coordinate axes. Two distinct fences never intersect each other, not even at a point, and in particular, not even at a vertex. However, it is possible that some fences are "surrounded" or "enclosed" by other fences.

There are $$$M$$$ possible points in the field where a parachutist can land. A given parachutist always has the same probability of landing at each of the $$$M$$$ points. More specifically, two parachutists will land in this field, and the position where each lands is independent of the other. In other words, all $$$M \times M$$$ combinations of landing locations for the first and second parachutist, respectively, are equally probable. None of the $$$M$$$ locations is on an electrified fence, not even at a vertex.

The fences are made of electrified wire, which covers the entire perimeter of the rectangle, making it difficult to cross them without receiving an electric shock. Crossing a fence means passing through the perimeter of its corresponding rectangle, that is, passing through a point that belongs to one of the $$$4$$$ sides of the rectangle. To fulfill their mission, after landing, the parachutists can walk through the field until they meet at the same point in the field. Since crossing a fence is very complicated and dangerous, they will walk in such a way as to cross the minimum possible number of fences until they meet.

Your task is to calculate the expected number of fences they must cross in total to be able to meet.

Franco continues to learn robotics and is very happy because he built his second robot. His original plan was for this robot to be able to play Hopscotch, but since this is very difficult, he settles for a simpler version of this game.

On the floor, there is a board drawn with $$$N \times M$$$ squares. Let $$$(i,j)$$$ be the square located in row $$$i$$$ and column $$$j$$$. Due to the heavy rain lately, some of these squares are wet.

The robot can start its journey from any point outside the board and can only move horizontally and vertically, that is, in the directions parallel to the edges of the board. The robot can walk on both dry and wet squares. However, to change its direction of movement from vertical to horizontal (or vice versa), the robot must be inside a dry square. The robot can change its direction at most once in each square, but it can pass through it as many times as it wants. It can never change its direction by $$$180^\circ$$$. The journey must end outside the board.

For the journey to be valid, the robot must have changed its direction in all the dry squares. Below is a valid journey on a $$$3\times 3$$$ board, where the squares containing a circle are wet squares and the others are dry squares:

The goal is to determine a valid journey if it exists, for which each dry square must be assigned a distinct integer between $$$1$$$ and $$$s$$$ (where $$$s$$$ is the number of dry squares), so that the numbers indicate the order of the $$$s$$$ direction changes that the robot will make on the dry squares.

Máximo really enjoys collecting plushies. He has $$$N$$$ plushies, and he assigned a beauty value to each of them, which is a positive integer. He wants to arrange them all on his shelf in a row.

Since Máximo believes that the number $$$X$$$ brings bad luck, he wants to organize them on his shelf in such a way that there are no two plushies whose sum of beauties equals $$$X$$$ and that are adjacent in the row.

Can Máximo achieve his goal? If the answer is yes, you should indicate how he can do it.

You have an "ASCII Art" image formed by the characters '#' and '.', such as the following:

It is known that the image is actually formed by several copies of the letters T, A, and P that we see in the image above. These letters cannot be stretched or scaled; they must have exactly the same shape as those shown. Each character '#' in the image must belong to exactly one letter, and the letters must cover all the '#', without overlapping or covering a '.'.

For example, the following image:

Given a valid image, how many T's, how many A's, and how many P's are there?

Agustín and Brian play many games every weekend of the following game:

Given a list of $$$m$$$ positive integers $$$x_1, x_2, \dots, x_m$$$, each player starts with $$$0$$$ points, and alternately starting with Agustín, each player on their turn performs one of these two actions:

1. Choose one of the elements from the list that has not been chosen previously, and add the chosen number from the list to their score.
2. Pass the turn.

If both players pass in two consecutive turns, the game ends. Note that the fact that a player has no numbers available to choose on their turn does not necessarily imply that the game ends on that turn.

When the game ends, if one player has a higher score than the other, that player wins the game, and if both players have the same score, then the result of the game is a tie.

They are tired of always playing games of the same type, so in the last few weekends, they started to consider variants. In particular, this weekend they decided that Agustín can only choose values that are powers of 2 (i.e., values $$$x$$$ for which there exists a non-negative integer $$$k$$$ such that $$$x = 2^k$$$, such as $$$1$$$, $$$2$$$, $$$4$$$, $$$8, \dots$$$, etc.) and Brian can only choose odd values.

To avoid always playing with the same numbers, they play $$$Q$$$ games, each with a list of numbers generated from an original list of $$$N$$$ values $$$A_1, A_2, \dots A_N$$$. Each game is described with two numbers $$$L$$$ and $$$R$$$, and is played with the list of numbers that are between positions $$$L$$$ and $$$R$$$ of the original list, that is $$$A_{L}, A_{L+1}, \dots, A_{R}$$$ (including both extreme positions).

Given the $$$N$$$ values of the original list $$$A_1$$$, $$$A_2$$$, $$$\dots$$$, $$$A_N$$$ and the description of the $$$Q$$$ games, decide what the result will be for each of the $$$Q$$$ games if Agustín and Brian play optimally.

This year, Pedro was invited to participate in a programming competition that will take place in a very, very distant country. Fortunately, he has already secured his ticket, which includes $$$N$$$ layovers in different countries.

To cover the costs of the trip, he decided to take a suitcase in which he can carry a maximum of $$$K$$$ balloons that he has left over from a previous competition, in order to sell them during the layovers of the trip. Since obtaining balloons in other countries is not so easy, Pedro decided that he will not add more balloons into his suitcase at any of the layovers.

Pedro knows that in the country he will visit during the $$$i$$$-th layover, he can sell each balloon for $$$V_i$$$ pesos (Argentine currency), but there is a problem: he can only enter with up to $$$C_i$$$ balloons without having to pay taxes. For each extra balloon, he will have to pay the Carnival Products Trade Tax, which costs $$$P_i$$$ pesos per extra balloon.

Pedro wants to know what the maximum net profit he can obtain is.

Camila sells boxes in the shape of rectangular parallelepipeds, that is, the usual shape of a box.

If the height, width, and depth of a box are $$$a$$$, $$$b$$$, and $$$c$$$ respectively, Camila sells it for a price of $$$a^2+b^2+c^2$$$ pesos. The boxes are empty and are only made up of the surface. The material she uses costs half a peso (Argentine currency) per square unit. Therefore, manufacturing a box with height, width, and depth of $$$a$$$, $$$b$$$, and $$$c$$$ costs her $$$ab+bc+ca$$$ pesos.

Camila has a list of $$$N$$$ possible values for the height, width, or depth of the boxes. She only manufactures boxes such that each of its three dimensions belongs to this list of $$$N$$$ measurements she works with. There is no problem using the same value from the list for more than one of the three dimensions of a box.

If she chooses the dimensions $$$a,b,c$$$ of a box in such a way as to maximize her net profit (the difference between the selling price and the cost), how much can she earn at most from one sale?