Most of the properties in the village of Chavo in Mexico belong to Mr. Barriga, who charges high rental values. Kiko, the lover of square balls, is interested in buying a property with equal sides, but not in the real world, but in the metaverse!

Mr. Barriga follows an unconventional procedure to sell properties in the metaverse: First of all, the metaverse could be a $$$k$$$-dimensional universe. For a three-dimensional metaverse, that is, when $$$k$$$ equals 3, the sale is described as follows: Let a simple cube be a cube with faces parallel to the coordinate axes and with vertices of integer coordinates. Mr. Barriga owns a simple cube $$$A$$$ with side $$$n$$$, defined by the vertices at the origin and $$$(n,n,n)$$$. A simple cube $$$B$$$ entirely contained within $$$A$$$ will be chosen randomly for sale. All distinct valid cubes $$$B$$$ have the same probability of being chosen. Two cubes are distinct if they are defined by different vertices. Note that, for example, it is more likely that cube $$$B$$$ has side of 1 rather than 2, as there are more cubes with a side of 1 inside $$$A$$$ than there are with side of 2. The selling procedure can be extrapolated from the 3-dimensional case to the $$$k$$$-dimensional one. The hypercube $$$B$$$ to be sold has the same number of dimensions: $$$k$$$.

Given $$$n$$$, the side of the hypercube $$$A$$$, and $$$k$$$, the number of dimensions of the metaverse, help Kiko to determine the expected hipervolume of the cube $$$B$$$ to be sold. The answer can be represented as an irreducible fraction $$$p/q$$$. Print the fraction modulo $$$10^9+7$$$. Formally print $$$x$$$ such that $$$0 \leq x \lt 10^9+7$$$ and $$$x \cdot q \equiv p \mod (10^9+7)$$$. It is guaranteed that the fraction can be represented in this way. In particular, it is guaranteed that the number of distinct cubes $$$B$$$ is not congruent to $$$10^9+7$$$.

The most classic instrument in Mexican music is the maraca, which is made up of a handle and a ball on top containing seeds and it functions as a type of rattle. As everyone knows, the use of pairs of maracas is mandatory!

You have just arrived in Mexico and will participate in a maraca circle with exactly $$$N$$$ people. At the $$$i$$$-th position of the circle, there is a number of maracas $$$m_i$$$. Your task is to redistribute the maracas so that each position has an even number of maracas to be used; after all, there cannot be a maraca without its pair. Since the circle is really big, you can only take maracas from a position and move them to the position immediately to the left or right.

The time it takes to carry a maraca from one position to another is directly proportional to the number of maracas being carried, because the greater the quantity, the heavier the weight. The time to carry a maraca to the left is $$$A$$$ seconds, and to the right is $$$B$$$ seconds. Additionally, if you're not carrying any maracas, you can move very quickly between positions (in zero seconds).

Since everyone wants to start making music as soon as possible, your goal is to determine the minimum time needed to complete this task. If it's not possible to achieve the task, you should print $$$-1$$$.

Ana, affectionately called Anita, loves palindromes, but unfortunately she is constantly sad because palindromes are rare and she has little to no opportunity to exercise her passion. For example, Mexico, where Ana lives, is known for having no city whose name is a palindrome.

Instead of looking for another hobby, Ana is considering slightly extending her passion to include quasi-palindromes. A word is a quasi-palindrome if there are at most two positions that differ between the word and its reverse.

For example, the word $$$anita$$$ is a quasi-palindrome because $$$anita$$$ differs from $$$atina$$$ in only two positions. However, $$$mexico$$$ is not a quasi-palindrome, as it differs from $$$ocixem$$$ in 6 positions. Note that every palindrome is also a quasi-palindrome.

Ana realized that her life could greatly improve if she makes this decision. She has plans to move to Zapopan near Guadalajara and won't be bothered when her friends call her Anita.

Before making this decision, she needs to be sure that she won't regret it and wants to understand more about the properties of quasi-palindromes. For this, she wants you to write a program that, given a word, calculates how many substrings of that word are quasi-palindromes.

Tortillas are one of the most characteristic elements of Mexican cuisine. Made with wheat or corn flour, they are used in the preparation of various delicious foods, such as tacos, burritos, and quesadillas. The manager of a famous supermarket in Mexico City went crazy and decided to hold a mega promotion on different types of flour, which attracted many customers to his establishment.

The supermarket has the capacity for $$$k$$$ checkout queues. After finishing their shopping, a customer goes to one of these queues to make the payment. Since people are very stubborn, they never switch queues once they have entered one, even if it's taking too long to move.

A customer becomes sad if, while waiting in a queue, they observe someone entering and leaving another queue.

Considering that $$$n$$$ people are in the supermarket, numbered from 1 to $$$n$$$, you receive a list of $$$2n$$$ events in chronological order indicating the entry or exit of a customer from a queue. Determine which customers will be sad.

On September 15, 1810, Mexico begins its battle for independence. The date is celebrated with grand festivities, music, and fireworks. However, due to the pollution generated by the fireworks' explosions, Mexican citizens have been seeking an alternative to traditional fireworks.

With the popularization of drones, it is now common to use these devices to perform at events, creating complex figures in beautiful light shows. The drones are not real-time controlled. A program is loaded into one of the drones, called the primary drone, while the other drones, the servant drones, receive instructions from this single drone. The organizers of the festivities are concerned about whether the primary drone's battery will be sufficient to complete the entire show.

In this problem, we will represent each drone as a point in three-dimensional space $$$(x, y, z) \in \mathbb{Z}^3$$$. Consider that drone number 0 is the primary drone. Each servant drone is distinct, so each one has a cost $$$w_i$$$ to transmit the signal. The total transmission cost between the primary drone and a servant drone grows quadratically with the Euclidean distance between them, given by:

$$$$$$\operatorname{dist}(i, j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2}$$$$$$

To maximize the uptime of the primary drone, we want to minimize the total transmission cost, which is given by:

$$$$$$\sum_{j = 1}^{j \leq n}\operatorname{dist}(0, j)^2w_j.$$$$$$

The Latin American ICPC Final will be held in Mexico, and the organizers of the festivities have requested your help to solve this problem. Given the positions of the servant drones and the transmission costs of each one, determine the coordinates of the primary drone that minimizes the total transmission cost. The position of the primary drone must be integral. In case of multiple answers, print the lexicographically smallest one.

Every Brazilian knows Ryan Ochoa very well, the Mexican goalkeeper who park the bus the goal against Brazil in the 2014 World Cup. More than that, the guy becomes the best goalkeeper in history during any World Cup period and hibernates for the following 4 years. What nobody knows is that in reality, he is training his successor as the best goalkeeper in World Cups: you! Now you need to buy one pair for yourself and one pair for Ochoa. In the store, there are exactly $$$N$$$ gloves on display, arranged in a line. The glove in position $$$i$$$ has size $$$A_i$$$. The size you both wear doesn't matter, as you are the best in the world in your position. However, to not hinder the performance in training, it's crucial to choose the same size $$$X$$$ for both your gloves and the same size $$$Y$$$ for Ochoa's ($$$X$$$ and $$$Y$$$ can be different). Every day, the gloves available for sale can change! They are always defined by an interval $$$[l, r]$$$ that represents the positions of the gloves for sale at that moment. Moreover, the glove at position $$$i$$$ can be replaced by another of a different size. We have $$$Q$$$ changes in total, and they are described as follows:

• $$$1$$$ $$$\ell \, r$$$: The range of gloves for sale has changed to $$$[l, r]$$$, and at this moment, you must say whether it's possible to buy a pair of gloves for yourself and one for Ochoa;
• $$$0$$$ $$$i \, x$$$: the glove in position $$$i \in \{1 \ldots N\}$$$ was exchanged for a glove of size $$$1 \leq x \leq 10^9$$$.

It is a well known strategy for mobile game ads to show the gameplay of a game in which the player is very bad. This makes the viewer want to download the game to prove how easy it is. You are the tester of one such game: Choice hero.

The idea of the game is the following: you start with a hero with power $$$f$$$ and you are going to play $$$n$$$ levels, numbered from 1 to $$$n$$$, one after the other in ascending order. In the $$$i$$$-th level you fight exactly one of two available monsters. The monster from the left has power $$$a_i$$$ and the monster from the right power $$$b_i$$$. If you successfully beat exactly one of the monsters you proceed to the next level $$$i+1$$$, or you win the game in case it was the $$$n$$$-th and last level. The hero can only beat a monster with power smaller than or equal to his own power at the time. If the hero has power $$$x$$$ before the fight with a monster with power $$$y$$$ ($$$y \leq x$$$), the hero gains the power of the defeated monster, that is, his power becomes $$$x+y$$$. Your job as the tester is to report if it is possible to win the game given the list of $$$n$$$ levels.

Yan 'the globe-trotter" Soares continues his trips around the world. In a dream, he recalled that an ancestor of his was Latin American champion of a certain programming competition. Intrigued by this dream, he is heading to Mexico to attend one of these competitions.

Yan is a fan of role-playing games, so he is going to take advantage of this trip to attend the largest role-playing festival in the world. It takes place in the city of Guadalajara, and is composed of $$$N$$$ days where various events take place, and after these $$$N$$$ days, the festival repeats itself again. That's why it's called the "infinite festival".

As it is typical of this kind of festivals, each participant receives a level, in total there are $$$M$$$ levels and every participant starts at level $$$1$$$. Yan has two goals: $$$(a)$$$ to attend the $$$N$$$ days of the festival and, $$$(b)$$$ to reach the level $$$M$$$ during this time. As any good traveler, he would like to do this by spending as little money as possible.

Yan knows the cost $$$c_{ij}$$$ of reaching level $$$i + 1$$$, from level $$$i$$$, on day $$$j$$$. Note that he can go several levels up in one day (even all of them). Also, it knows the cost $$$d_{ij}$$$ of accommodation on day $$$j$$$ if he has level $$$i$$$. Note that the cost of accommodation is paid daily at the end of the day, when the events have finished.

Unfortunately, Yan did not inherit his ancestor's skills. Therefore, he asked you to make a program that calculates the minimum cost of attending the festival. Note that Yan can arrive on any of the $$$N$$$ days to the festival. For instance, if we represent the $$$i$$$-th day of the festival by the integer $$$i$$$ and Yan arrives on day $$$x$$$, then the sequence $$$x, x + 1, \ldots, N, 1, 2, \ldots, x - 1$$$ represents the days he attends to the festival. Note that Yan does not pay for the accommodation of the last day (day $$$x - 1$$$ in the previous example).

The Aztecs were a civilization that emerged around 1300 in regions that now belong to Mexico. The Aztec empire had city-states with elaborate urban planning, an expressive cultural production, and influence in different spheres of Mexican modern society, like language and cuisine.

The economy was centered on agriculture, especially corn and beans. Hence, we can consider the empire as being divided into $$$n$$$ plantation fields. Two fields may be connected by a road. We know the empire had $$$m$$$ roads in total.

Imagine now that you became the Aztec emperor, therefore you need to control the empire's economy and your people's happiness. Your counselors told you that if a road has one endpoint at a been field and another at a corn field, the population considers that road as being good because it shows the diversity of the agriculture. During your government $$$q$$$ events will happen, these events can be of two types. Events of type 1 happen when the rain god, Tlaloc, is angry with the empire and flood one of the fields together with all roads that reached the flooded field. After events of type 1 the destroyed field and roads never come back to existence. Events of type 2 happen when Tlaloc is happy and provides good weather for plantations, in this case, you should decide which fields will cultivate corn, and consequently, all others will cultivate beans. For your population to be satisfied is necessary that at least half of the existing empire's roads are good. Now you must play your role as the emperor to guarantee the happiness of your population, and that the empire can keep prospering!

In the remote corners of Mexico, hidden among the mystical ruins of the Temple of Kukulkan, lie the most well-guarded secrets of the ancient Mayan programmers. Legend has it that the transcendent knowledge of ancient algorithms is protected by a mysterious Encoded Chamber, access to which is safeguarded by a clever enigma.

The entrance to the Encoded Chamber does not resemble any ordinary door. A sequence of sacred symbols, initially representing the sun, adorns the facade of the passage. In front of it, a set of elaborately carved levers is arranged on a stone panel. Every time a lever is pulled, exactly two of the sacred symbols mysteriously change form: a sun transforms into a moon, and a moon transforms into a sun.

The guardian of this chamber is Indiana Jiang, a renowned archaeologist who, after years of tireless research, has discovered a sequence of symbols that, once obtained, will reveal the path to the ancestral knowledge. Exhausted from his investigations, Jiang requests your help to rescue the Mayan secrets before they fall into the wrong hands. Find a set of levers that, when pulled, will open the door to the Encoded Chamber.

Hi, welcome to Guadalajara! The first Latin American ICPC final is about to begin. After participating as a contestant for years today you will help the organization. You remember the rules, right? Each team has at most 3 people. Each team should have exactly one printed contest.

We have $$$n$$$ contestants subscribed, but we don't know how the teams are organized. Depending on how many teams we have we will need to print more or fewer contests. Even though the contest is in black and white you know how printers always complain about being low on cyan, so you want to know what the minimum number of contests printed you will need among all possible team divisions.

In 2024, the city of Guadalajara will host the 1st Latin American Final of the ICPC. For this reason, the city government is interested in promoting tourism. They have collected information about the $$$N$$$ most important tourist attractions in the city. The mayor wants to organize these attractions into tourist circuits. A tourist circuit is a sequence of distinct tourist sites, say $$$\langle p_1, p_2, \ldots, p_\ell \rangle$$$ such that $$$\ell \geq 3$$$. Tourists participating in the circuit, starting at $$$p_1$$$, visit the attractions of the circuit following the sequence until they reach the site $$$p_\ell$$$. After visiting $$$p_\ell$$$, tourists return to $$$p_1$$$ to finish the circuit. Therefore, to form the circuit, there must be a street that connects tourist sites that are consecutive in the sequence (including $$$p_1$$$ and $$$p_\ell$$$).

The city government calculates that maintaining a circuit will have a high cost. Therefore, they want to divide the $$$N$$$ tourist sites into as few circuits as possible. In other words, they want to find a set of circuits such that each tourist site belongs to a unique circuit, and the set is as small as possible. To solve this difficult task, the city government hired Marcel "the optimizer" Saito.

Marcel received information about the city's street network. After an analysis, he realized that the network satisfies the following property. For any four tourist sites $$$A$$$, $$$B$$$, $$$C$$$ and $$$D$$$, $$$$$$ d(A, B) + d(C, D) \leq \max\{ d(A, C) + d(B, D), d(A, D) + d(B, C) \}, $$$$$$ where $$$d(U, V)$$$ is the smallest number of streets we need to travel to get from $$$U$$$ to $$$V$$$.

Marcel is sure that this property is important to solve the problem at hand. Unfortunately, he needs to take care of his newest apprentice Daniel "the dynamic" Ito. Therefore, he has entrusted this task to you, the newest trainee.

Chavo lives in a barrel on the street. The street can be seen as a 2D plane and has two streetlights located at points $$$p1$$$ and $$$p2$$$. These streetlights illuminate discs directly beneath them, which means they generate two discs $$$c1$$$ and $$$c2$$$ with centers at $$$p1$$$ and $$$p2$$$ respectively.

Chavo lived with his barrel of radius $$$0$$$ at the point $$$(0, 0)$$$ on the street, where the edge of the discs generated by the two streetlights intersect. In other words, this is where the edge of $$$c1$$$ intersects with the edge of $$$c2$$$.

Chavo is tired of his tiny home and wants to move to a larger barrel, where every point in his barrel is illuminated by both streetlights. However, Chavo is afraid of change, so he doesn't want any point in his barrel to be more than a distance of $$$R$$$ away from his original home.

Help Chavo by figuring out the largest radius of a barrel that can be illuminated by both streetlights and still remain entirely within a distance of $$$R$$$ from his original home.