There's a sticker album very popular among the children of Pavussulandia. To fill the album, they need to find $$$M$$$ distinct stickers with identifiers from $$$1$$$ to $$$M$$$. The stickers are sold in packs, and there are $$$N$$$ packs available for purchase. Each pack $$$i$$$, such that $$$1 \leq i \leq N$$$, has $$$K_i$$$ stickers and costs $$$V_i$$$ reais.

In the store, the stickers are arranged on a shelf in order, and you have to choose an interval $$$[i, j]$$$ and buy all the packs from $$$i$$$ to $$$j$$$ (including $$$i$$$ and $$$j$$$). Since the stickers are highly sought after, you can only make one interval choice.

Little Biel is excited to fill his album; however, his family doesn't have much money. With that, he needs your help to spend as little as possible and complete the album. If there is no answer, you must inform Biel, preventing him from unnecessarily wasting money.

After participating in the MFP (Matchup of Finalists in Ping-pong) in Campinas, Giovana and Julia are tired of playing ping-pong and decide they need to devise a new sport. They want a sport that, besides physical performance, requires mathematical reasoning and strategy. As both are very fond of binary numbers, they thought of the following game, which they named "Bit Tennis", to play against each other:

• The game starts with a string $$$S$$$, of size $$$N$$$, that represents a number in binary;
• Giovana begins the game and thereafter they alternate turns between Julia and her;
• In each round, the current player can add one more digit ("0" or "1") to the end or the beginning of the string: for example, if the string is "110", the player can turn it into "1100", "1101", "0110" or "1110".
• If, after $$$K$$$ turns from each player, the number is a multiple of 3, Julia wins. Otherwise, Giovana wins.

Both quickly learned to play optimally and, after playing a few times, they noticed that the game's outcome is always determined before the first move is even made. Curious about this fact, they asked for your help to, given the initial string and number of turns, find out which one of them will win.

The traveling salesman Lex doesn't travel from city to city just because it's profitable to sell his exotic products in various different places. Most likely, due to the high availability of exotic items for sale on the Internet at very low prices, his business outcomes began to decline, and since then, Lex has been accumulating debts with loan sharks he meets in the cities.

With the help of an ancient technique taught by his ancestors, Lex has already solved the problem of visiting all the cities by making a route that goes through each of them only once. Now, Lex's problem is to return home while avoiding, as much as possible, the cities where he owes money.

Lex is currently in city $$$1$$$ and lives in city $$$N$$$. He knows exactly in which cities he has debts, and now he needs to find out which path he should take to avoid these cities as much as possible, and obviously, he wants to move as little as possible. Lex tried, but couldn't solve this problem, so he asked for your help.

Joãozão and Marcel are excited to practice weightlifting at the UDESC gym. The two of them take turns doing sets, where each set consists of exactly $$$M$$$ repetitions of the exercise. Marcel always starts. However, they have a peculiar way of counting the repetitions when they alternate: they count the total $$$N$$$ repetitions that both did, without counting individually how much each one did. Now, after spending a lot of time not knowing whose turn it is to exercise, they asked for your help.

Write a program that, given the total number of repetitions done so far and the number of exercises per set, says who is next to perform the exercise.

The email application that Enzo developed during his college days has now become one of the largest in the world in the electronic mail field. Although some users have complained about the lack of basic features, such as deleting emails and spam checking, the app is still a hit, thanks to its "simplicity", according to Enzo himself.

Enzo's next task is to implement a password recovery system in case a user forgets their password. However, the internal workings of Enzo's email app are anything but "simple":

• The app users' passwords consist only of the digits '0' and '1'; as unusual as it may seem, that's how it works. No one really knows why Enzo made it this way.
• The app encrypts the passwords by transforming '0's into the string "ab" and '1's into the string "aba".
• The database sometimes fails and saves corrupted passwords like "abb" or "abaaaab" (passwords that can't be obtained from a combination of "ab"s and "aba"s).

Enzo wants to create a program that, given a sequence of characters 'a' and 'b', retrieves the string of characters '0' and '1' that represents the user's original password, so he can send it directly to them via SMS (he didn't worry much about security, as long as it works). If it's not possible to retrieve the user's password due to corruption, the program should print ":(" to indicate there was a problem in the process.

However, as he's nearing retirement and has been spending most of his time watching Cruzeiro's soccer games, he's lost his touch and can't solve problems anymore. That's why he's asking for your help.

The "Festa Junina", a traditional celebration in Brazil, organized by BRUTE (Bureau for Realization of Unique and Triumphant Events), always features various notable personalities. In the 2023 edition, some of the attendees were acclaimed football players: Gasparinius Jr. and Karinen Sousa.

Upon seeing Gasparinius at the party, Karinen decides to pay a fee of R$ 2.00 to send him to "jail". The "jail" is a common game at Festas Juninas, but BRUTE came up with their own version. In it, whoever is jailed is kept in a locked room indefinitely and is only released when the bail is paid. This measure was necessary because the Bureau was out of budget for upcoming events after impulsively buying a sofa for their office.

Thus, Gasparinius was taken by the BRUTE guards to the jail, where he was eager to know the cost of his bail. The guards told him:

"The cost of your bail will be the cost of a sequence of exactly $$$N$$$ integers you present to us, being strictly ascending (each element is greater than the previous one) and only containing numbers greater than zero. The cost of a sequence is given by the sum of the costs of each of its elements. The cost of an element $$$x$$$ is determined by its binary representation, with each binary digit $$$i$$$ (corresponding to $$$2^i$$$) associated with a cost we call $$$C_i$$$, which will be added to the total if, and only if, the digit in that position is '1'. Again, the cost of the number $$$x$$$ will be the sum of the $$$C_i$$$ for all $$$i$$$ where the digit is '1' in the binary representation of $$$x$$$. We will give you $$$M$$$ cost values, which we guarantee will suffice for the binary representation of at least the $$$N$$$-th number."

Even though it wasn't a real jail, BRUTE is very strict about security and allows those jailed to make only one phone call. Gasparinius Jr. decides to use his call to contact you. Knowing your ability to solve problems like this, he asks you to write a program that calculates the lowest possible cost of a sequence to minimize his bail expenses.

The fearless explorer Eric is known for his countless adventures and has always been drawn to the unknown. From mysterious forests to towering mountains, he's faced them all. However, in a remote cave, he stumbled upon an object that promised an entirely new challenge: a magic lamp. Upon rubbing the dusty object, to his surprise, a genie emerged. But this was no ordinary genie. He didn't follow the standard rule of granting three wishes to whoever released him.

Instead, the genie was a fan of counting problems and posed a challenge to Eric: he showed Eric a series of opening and closing parentheses, but with a twist: some parentheses were replaced by '?'. With a sly smile, the genie proposed: "Eric, how many ways can you replace the ?'s with '(' or ')' such that the final sequence is balanced? That's the number of wishes you'll have from me."

A sequence of parentheses is considered balanced if it can be transformed into a valid mathematical expression by inserting only digits and operators between the parentheses. In other words, for every opening parenthesis, there must be a corresponding closing parenthesis in the correct order. For instance, "()()" and "(())()" are balanced sequences, but "())(" or "((()()" are not.

Eric needs to calculate how many wishes he has at his disposal by replacing '?' with '(' or ')' such that the resulting sequence is balanced, help him with this task. As this number of wishes can be quite large, print the remainder of the division of this number by $$$10^9+7$$$.

One evening, Eduardo was feeling hungry and decided to order a delivery of his favorite food: Shawarma. Upon opening the delivery app and selecting his favorite restaurant, Eduardo noticed a new intriguing option on the menu: the Hawarma. Although it seemed like a typo, he found out that it was a legitimate option. In the item's description, the restaurant had written: "Order the Hawarma, if you can." Curious, Eduardo continued, provided the delivery address, selected the payment method, and when everything seemed to be going smoothly, he encountered the following message:

The truth is that, at this point, most people look and think "What a prank!" and end up ordering something else. But not Eduardo: motivated by the challenge and curiosity, he won't give up on the Hawarma. Suppose you are Eduardo, inform how many values satisfy the condition for a certain value of $$$N$$$ and what those values are.

You are working on DJ software and need to simulate a virtual turntable. A vinyl disc is displayed on the screen, and the user can use mouse movements to make the disc move forward or backward. The simulated vinyl disc spins at $$$33+\frac{1}{3}$$$ RPM (rotations per minute) in a clockwise direction. The user can perform a drag-and-drop motion from any position on the disc to any other position. For instance, if the user initiates a movement from the bottom of the disc and goes upwards and to the right, the disc should rewind:

We aim to approximate the real world by considering only the angle formed by the two positions relative to the center of the disc. Note that there are two angles for any two starting and ending positions, and the program should use the smaller angle to determine how much the disc has rotated. If the user attempts a movement that starts or ends outside the disc, the disc will not be moved.

Mouse positions are given in the first quadrant of the Cartesian plane (meaning the position $$$(0, 0)$$$ is at the lower-left corner), and the disc is scaled on the screen from position $$$(0, 0)$$$ to position $$$(D, D)$$$. So, given the disc's size on the screen and the initial and final mouse positions during a drag-and-drop operation, determine how many seconds of music should be fast-forwarded or rewound.

Fernando is an avid party game player, as they are a great way to liven up social gatherings and facilitate interaction among participants. Many party games involve alternating turns among several players, with each person taking their turn. Therefore, when people want to play a party game, they need to decide on the order of players, which is usually resolved through some playful method that generates a random outcome. Among these decision-making games, Fernando's favorite is the game of "even or odd".

However, the math enthusiasts among the group are never satisfied with this decision method. When they show up at parties (which is rare), they can't help but complain about the lack of fairness in various methods. Even though Fernando and his friends enjoy playing party games just for fun, they decided to listen to the mathematicians' suggestions to achieve a more uniform outcome. They defined some requirements for a method to be truly fair:

• First player fairness: Every player has an equal chance of going first.
• Position fairness: For every position, all players have the same chance of ending up there. Therefore, everyone has the same chance of being first, the same chance of being second, and so on.
• Permutation fairness: All possible permutations of player orders have an equal chance of being chosen.

Note that it's possible for a method to uniformly determine each player's position, but not all permutations may have the same probability of occurring. One of the mathematicians' favorite methods of random selection is using dice, so they created sets of dice that satisfy some of these properties.

Each of the $$$N$$$ players receives a die identified by a letter of the alphabet, and each number from $$$1$$$ to $$$M$$$ appears on only one die. Thus, each player rolls their own die, and the order of the numbers rolled on the dice is used as the order of the players. The player with the highest-numbered die goes first, the one with the second-highest value goes second, and so on.

A set of dice is described by a string of $$$M$$$ letters, where each position assigns the value of the position index to one of the dice, and the dice are represented by the first $$$N$$$ letters of the lowercase Latin alphabet. For example, the set of dice dcbabccccbabcddddcbabccccbabcd satisfies the fairness property for 4 players:

Well... Fernando and I were also hoping that the dice would at least be of the same size. Apparently not, but anyway. Now, you're curious and want to know if a given set of dice satisfies both position fairness and permutation fairness. To determine that, you need to calculate the probability of each player obtaining each position and the probability of each permutation.

After disagreements with former team members, Guilherme, Igor, Pedro, and Victor have just recruited Thomas to their e-sports team focused on playing Balloorant. In this game, two teams of five people face each other, one as attackers and the other as defenders. The goal of the attackers is to pop all of the defenders' balloons, while the defenders try to gather as many balloons as possible in a 5-hour programming contest.

While playing a match with Thomas, the other team members became frustrated as they realized he doesn't understand the communication system used by the others. They communicate all of their strategies in the game's voice chat using Knock Code.

Knock Code is a code where each of the 26 letters of the alphabet is represented by a pair of numbers $$$(i,j)$$$ that indicate the position (row, column) of the letter in the 5x5 code matrix. In order to have 25 positions instead of 26, the letters C and K are represented by the same pair of numbers. The pairs of numbers are communicated through knocks (on a table, for example, in a way that can be picked up by the game's microphone). To communicate the number $$$X$$$, $$$X$$$ consecutive knocks are made without pauses. To communicate more than one number, pauses are made between consecutive knocks. We will represent a knock as an asterisk (*) and a pause (the time between sequences of consecutive knocks) as a space ( ).

For example, encoding "NTJ":

"N" is at position (3,3), therefore it is represented by: "*** ***".

"T" is at position (4,4), therefore it is represented by: "**** ****".

"J" is at position (2,5), therefore it is represented by: "** *****".

Thus, the entire encoded word is represented by: "*** *** **** **** ** *****".

Now, the team asks for your help in supporting Thomas in learning the code to be able to communicate with the rest of the team. For this, he needs you to write a program that takes a string representing the message to be communicated and encodes it into Knock Code.

You are the attendant of the best coffee shop in the world: Le Café (a French franchise). One day, near closing time, three students, Malu, Débora, and Lívia, enter the shop and get ready to place their orders. Malu, as she doesn't like coffee, orders only a brownie (world-renowned for being cheap and delicious). Débora and Lívia, on the other hand, order the Vanille Glacée, a mixture of coffee, vanilla essence, milk, and most importantly: SPRINKLES.

After ordering their drinks on the table's tablet, Débora and Lívia approach your counter and make an unusual demand: "We will only accept our Vanille Glacée if both have the exact same number of sprinkles, and that number is greater than zero. If not, cancel our order." After that, the two turn around and hurry back to their table. You, confused, open the sprinkle cabinet and see $$$N$$$ packages, fearing that you won't be able to fulfill the order. Like anyone in such a situation would do, you chat nicely with the two friends to try to reach a consensus you open your notebook and start programming a solution.

Note that each package can be used exactly once, and due to Le Café's policies, a package must be used entirely, and all the sprinkles must go into the same Vanille Glacée. The justification is that this prevents packages from being open for too long, thus affecting the texture of the sprinkles. Therefore, given the quantity of sprinkles contained in each of the packages, inform whether you will be able to serve Débora and Lívia's Vanille Glacée.

The mayor is trying to cut costs in the city, and one of his latest ideas is to use less powerful light bulbs in the lampposts. After all, each lamppost is wasting energy if its light bulb illuminates more than necessary! Of course, if the distance between the lampposts were uniform, the calculation would be simple. However, since the mayor also cut costs when placing the lampposts, they are in completely arbitrary positions on the city streets.

However, the mayor knows about economies of scale, so he wants to order all the light bulbs with the same power, the minimum needed to illuminate everything. We define the power of a light bulb as the distance it illuminates to the left and right. Now, the city's electricity department has approached you. Given the positions of the lampposts on the street, what power is needed in the light bulbs to illuminate the entire street?

After completing a 42-kilometer run in the XXVII Campo Grande Marathon, Granza, Joãozinho, and Machado were exhausted but were celebrating their 12th-place finish for their team. This achievement marked a special moment in UDESC's history, as it was their first time receiving a medal in an ICPC (Institute of Circuit Performance Competition) competition. However, as they crossed the finish line, a new rule was announced by the event organizers: only the top-performing teams would receive medals, provided they participated in the activity organized by BRUTE (Building Runners' Universal Trading Experience), the event's sponsor.

The activity involved the youngest team member, in this case, Machado, playing a game based on the classic Nim game against an employee named Cartinha from the BRUTE company. Cartinha was instructed to play optimally. Only teams that managed to defeat Cartinha would be awarded medals. The rules were explained by BRUTE on the event day as follows:

• The game starts with a pile containing $$$A\times B$$$ stones and is played between two players who take turns, with Machado going first;
• Cartinha can only add or remove (if possible) any number of stones that is a multiple of $$$A\times B$$$ from the pile;
• Machado can add or remove (if possible) any number of stones that is a multiple of either $$$A$$$ or $$$B$$$ from the pile;
• Machado loses if, at any point, the number of stones in the pile becomes 0 or if the game extends infinitely;
• Machado wins if, at any point, the number of stones in the pile falls between 1 and $$$K$$$ (inclusive).

Given values $$$A$$$, $$$B$$$, and $$$K$$$, determine whether Machado can secure the medal for the team or not.

Léo and Emanuel are ready to travel to Rio de Janeiro to watch the next football match Vasco da Gama will play, going from Joinville to Rio through the BR-101 highway. During the trip, Emanuel wondered why it was taking so long to reach the destination. They stopped to look at the map and realized they had taken the wrong route, driving in the opposite direction! They immediately stopped and turned around, returning to the correct path. Now, they want to know how many kilometers they will have traveled in total after reaching their destination. However, since they are on the road, they sent you a message asking you to write a program to calculate this for them.

Given the distance that the friends traveled in the wrong direction and the distance from the football stadium to their starting point, provide the total value, in kilometers, that the two will have traveled when they reach their destination.