Isa, wanting to join the climbing group Climbing Camels, decided to start climbing mountains. In order to be accepted as a climbing camel, Isa must climb all the available $$$N$$$ mountains. However, for Isa to be allowed to climb the mountain of a certain level, she must have climbed other easier mountains first.

Your mission is: given the number of mountains and pairs of mountains $$$(A, B)$$$ where mountain of level $$$A$$$ must be climbed before mountain of level $$$B$$$ determine the lexicographically smallest order in which Isa can climb all the mountains and become a climbing camel.

An order $$$A$$$ is lexicographically smaller than another order $$$B$$$ if there exists an $$$i$$$ such that $$$A_i \lt B_i$$$ and for all $$$j$$$ with $$$1 \leq j \lt i$$$, $$$A_j = B_j$$$.

Henrique Ramos is very happy with his new purchase: a special deck with infinitely many cards!

Each card in this deck has a number written on it. When buying the deck, Henrique had to choose a positive integer $$$n$$$, which determines the numbers on the cards.

The number on the first card is $$$n^0$$$, the second card has $$$n^1$$$, the third has $$$n^2$$$, and in general, the $$$i$$$-th card has the number $$$n^i$$$. This way, each card is unique, and no two cards have the same number.

Henrique is going to play a game with his friends using his new deck. In this game, a move is defined as a finite subset of cards from the deck, and the value of each move is the sum of the numbers on the selected cards.

For example, Henrique's deck for $$$n = 3$$$ contains the cards $$$1, 3, 9, 27, 81$$$, and so on. In this same example, a few valid moves are:

• $$$1$$$, with value $$$1$$$;
• $$$1, 3$$$, with value $$$4$$$;
• $$$3, 243, 729$$$, with value $$$975$$$.

Henrique is interested in the moves with the smallest values, so he created a sequence of all possible move values, ordered by their value. For example, the first five terms of this sequence for $$$n = 3$$$ are: $$$1, 3, 4, 9, 10$$$.

Henrique wants to know the $$$k$$$-th term of this sequence. However, he's currently too busy reading the problem Collatz-Star of Pain and Suffering. Help Henrique by calculating the value of the $$$k$$$-th term in this sequence.

Since the answer can be a very large number, print only the remainder when it is divided by $$$10^9 + 7$$$.

Since the latest Great War, the Galaxy has been ruled by the Galatic Empire. Lord Edsidious was finally able to conquer the status of Emperor, after centuries of planning. In his Empire, the following definitions and conventions apply:

• $$$X \ \% \ Y$$$ (both integers) represents the remainder when dividing $$$X$$$ by $$$Y$$$ if $$$X \geq 0$$$ and $$$Y \gt 0$$$. Additionaly, $$$X \ \% \ Y = X$$$ if $$$X \lt 0$$$ and $$$Y \gt 0$$$, and $$$X \ \% \ Y = 0$$$ if $$$Y = 0$$$.
• $$$NCP(X, Y)$$$ is the smallest integer $$$K \geq X$$$ such that $$$gcd(K, Y) = 1$$$.
• The Super Shift Function, $$$SSF$$$, is defined as: $$$SSF(X, Y, Z) = ((X-Z) \ \% \ (Y-Z)) + Z$$$.
• The Collatz Function, $$$CF$$$, is defined as: $$$CF(X) = \begin{cases} \frac{X}{2} & \text{if } X \text{ is even} \\ \frac{3 \cdot X+1}{4} & \text{if } X \ \% \ 4 = 1 \\ 3 \cdot X+1 & \text{if } X \ \% \ 4 = 3 \end{cases}$$$.
• About the value of a fraction mod $$$X$$$: consider the fraction $$$\frac{P}{Q}$$$ with $$$Q$$$ coprime to $$$X$$$ (if it's not, the value is not defined). The value of this fraction mod $$$X$$$ is $$$(P \cdot Q^{-1}) \ \% \ X$$$, where $$$Q^{-1}$$$ is the value such that $$$(Q \cdot Q^{-1}) \ \% \ X = 1$$$ and $$$0 \leq Q^{-1} \lt X$$$ (it can be proven a unique $$$Q^{-1}$$$ exists if $$$Q$$$ is coprime to $$$X$$$).
• About grid notation: a $$$X$$$ x $$$Y$$$ grid has $$$X$$$ rows and $$$Y$$$ columns. A cell $$$(i, j)$$$ of the grid is at the $$$i$$$-th row and $$$j$$$ column. A subgrid $$$Z = (Z_{x1}, Z_{y1}, Z_{x2}, Z_{y2})$$$ is the set of cells $$$(i, j)$$$ with $$$Z_{x1} \leq i \leq Z_{x2}$$$ and $$$Z_{y1} \leq j \leq Z_{y2}$$$).

To maintain his dominance, Lord Edsidious hired the famous botanic Collatz (the creator of the Collatz Function) to build him a Collatz-Star of Pain and Suffering, which is a massive device able to exterminate whole planets with a single blast. And to protect this strategic weapon, he assigned his most prestigious general: Darth Caetanus. Caetanus recently became aware of a weakness in the Star: it's energy board.

The energy board is composed of independent cells disposed in a $$$H$$$ x $$$W$$$ grid, and it is associated with a fixed integer $$$M \gt 2$$$. A cell $$$(i, j)$$$, at any time $$$t$$$ (measured in some integer unit) has two positive integers associated with it: $$$A_{t,i,j}$$$ and $$$B_{t,i,j}$$$. These numbers describe the probability of a failure in the cell at that time, which is equal to $$$\frac{A'_{t,i,j}}{B'_{t,i,j}}$$$, where $$$B'_{t,i,j} = NCP(SSF(B_{t,i,j}, M, 2), M)$$$ and $$$A'_{t,i,j} = SSF(A_{t,i,j}, B'_{t,i,j}, 1)$$$. At any time, if a failure occurs in any cell, it shuts down, leaving the Collatz-Star with no power temporarily. These values $$$A$$$ and $$$B$$$ vary in time as follows: $$$A_{t+1,i,j} = CF(A_{t,i,j})$$$ and $$$B_{t+1,i,j} = CF(B_{t,i,j})$$$.

Vinicius Solo, an influent person in the fallen Galatic Republic, used his connections to find (at time $$$0$$$) all the numbers $$$A_{0,i,j}$$$ and $$$B_{0,i,j}$$$ and the fixed number $$$M$$$. He also became aware that, at a certain unknown time $$$T$$$, Lord Edsidius will order the Collatz-Star to fire against the poor U.n.Balloon planet. To prevent its destruction, Vinicius will need the help of his ally Daniel Skywalker, who can Mystic Focus on subgrids of the energy board grid.

Let's consider that Daniel tries to Mystic Focus on a subgrid $$$S$$$ in a period of time from $$$t_l$$$ to $$$t_r$$$ (inclusive), and let $$$Prob(S, t_l, t_r)$$$ be the probability that any cell in $$$S$$$ shuts down at any time between $$$t_l$$$ and $$$t_r$$$ (which means the Collatz-Star would lose power in this time interval). Daniel can explode the cells in $$$S$$$ using his ability, but only if the value of $$$Prob(S, t_l, t_r)$$$ mod $$$M$$$ is greater than $$$\lfloor \frac{M}{2} \rfloor$$$ (it can be proven $$$Prob(S, t_l, t_r)$$$ is always representable by a fraction $$$\frac{P}{Q}$$$ with $$$Q$$$ coprime to $$$M$$$). This explosion would provoke a chain reaction that would destroy the whole Collatz-Star!

However, saving U.n.Balloon will not be that easy. To protect the Collatz-Star, Darth Caetanus casted a spell which prevents Daniel from trying to Mystic Focus on subgrids $$$S$$$ not contained in a special unknown subgrid $$$K$$$. Also, if Daniel tries to Mystic Focus on some subgrid $$$S$$$, he will be forced to do so from $$$t_l = S_{x1} + S_{y1} + K_{x1} + K_{y1}$$$ to $$$t_r = T - (S_{x2} + S_{y2} + K_{x2} + K_{y2})$$$.

Vinicius and Daniel don't know what is the actual time $$$T$$$ or the special subgrid $$$K$$$, so they decided to prepare themselves. They will conduct $$$Q$$$ studies: in the study $$$i$$$, they will count, for chosen values of $$$T_i$$$ and $$$K_i$$$, the number of subgrids $$$S_i$$$ that Daniel would be able to Mystic Focus on and explode, causing the destruction of the Collatz-Star. Help them write a program that calculates this!

The members of Unballoon gathered at Isa's house after a marathon to celebrate and eat ice cream. Most people wanted to serve their ice cream in cones and then eat them. However, Lucas Sala does not like cones and therefore preferred to serve his ice cream in his water bottle. This caused a great controversy, as some of the marathon runners believed that Sala's bottle could hold more ice cream than a cone, but they were not sure.

Cone with height $$$h$$$ and base radius $$$r$$$, which is also the radius of the semi-sphere.

After several calculations with integrals and some crimes against basic physics, the programmers could not reach a conclusion; therefore, you must help them solve this mystery. For this, consider that the ice cream cones are circular base cones. Additionally, the cones will be filled with ice cream uniformly up to their top, where a solid semi-sphere of ice cream with a radius equal to the radius of the cone's base will be placed. Finally, assume that Lucas Sala's bottle is a cylinder, which will also be filled with ice cream uniformly to its top. A solid semi-sphere of ice cream will not be placed in Lucas Sala's bottle.

In a distant kingdom called Alfabétia, wizards did not use common spells — they used magical words. Each word was formed by lowercase letters of the alphabet, and its power did not lie in the letters themselves, but in the way they repeated.

The wisest of the wizards, Archmagus MagePetrus, noticed something curious: two words could be equally powerful, even if they had different letters, as long as they had the same pattern of repetition.

For example:

• The word "aba" had a pattern where the first and third letters were the same, and the second was different.
• The word "cbc" had the same pattern!
• Even the strange "zfz" was like that too!

MagePetrus called this letter symmetry. He decided that, for magical purposes, words with the same pattern of letter repetition were equivalent — it did not matter which letters were used, only how they repeated.

Intrigued by the possibilities, MagePetrus proposed a challenge to the young apprentices of Alfabétia:

Given a number $$$n$$$, how many different magical patterns (i.e., how many distinct classes of words by letter symmetry) can be formed with words of size $$$n$$$, using letters from "a-z"?

We consider two strings equal, by letter symmetry, if one can be obtained from the other through a permutation of its letters. Formally, let $$$s$$$ be the string formed by the concatenation of the characters $$$s_1, s_2, \dots, s_n$$$ in that order and $$$A = \{a, b, \dots, z\}$$$ the set of lowercase letters of the Latin alphabet. We say that $$$s$$$ is equal to a string $$$t$$$ by letter symmetry if and only if there exists an injective function $$$f : A \to A$$$ such that $$$t$$$ is the string formed by the concatenation of the characters $$$f(s_1), f(s_2), \dots, f(s_n)$$$. The function $$$f$$$ being injective means that, for all characters $$$x, y \in A$$$, if $$$x \neq y$$$, then $$$f(x) \neq f(y)$$$.

For example, the strings "aba", "cbc", and "zfz" are considered equivalent, as they all have the same structure of letter repetition, while the strings "aa" and "ab" are different.

The Fibonacci sequence $$$(f_n)$$$ is defined as follows:

$$$$$$f_n = \begin{cases} 0 & n = 0, \\ 1 & n = 1, \\ f_{n-1} + f_{n-2} & n \geq 2. \end{cases}$$$$$$

For example, the first $$$6$$$ terms of this sequence are $$$0, 1, 1, 2, 3$$$, and $$$5$$$, and $$$f_{9} = 34$$$.

Given two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq 10^9 + 9$$$) and an integer $$$M$$$ ($$$1 \leq M \leq 10^9+9$$$), compute the remainder of the division of $$$f_{a^b}$$$ by $$$M$$$. In other words, find the unique integer $$$A$$$ such that $$$f_{a^b} - A$$$ is a multiple of $$$M$$$ and $$$0 \leq A \lt M$$$.

Luiz Eduardo is one of the last remnants of an almost extinct race on Earth: the romantics. He believes that everyone in the world will eventually find their one and only true love, whoever they may be (in fact, their true love could even be themselves!).

He took a sabbatical year and traveled the world, talking to people and hearing about their true loves. Carrying his notebook, he wrote down the names of the people he spoke to or heard about and the corresponding name of their true love. After his long journey, he showed his notes to his colleague Iasmim (to protect people's privacy, he replaced names with numbers).

Iasmim did not find Luiz's notes very interesting, so she decided to turn them into something nicer: a graph! More specifically, she constructed a graph where there is a directed edge from $$$A$$$ to $$$B$$$ if and only if person $$$A$$$ truly loves person $$$B$$$.

She then challenged Luiz with a problem: what is the maximum number of partially happy monogamous marriages (P.H.M.M.s) that could happen simultaneously in this graph? A P.H.M.M. consists of two people, $$$A$$$ and $$$B$$$, such that:

• $$$A \neq B$$$
• There is an edge in Iasmim's graph from $$$A$$$ to $$$B$$$ or from $$$B$$$ to $$$A$$$.
• Neither $$$A$$$ nor $$$B$$$ are in another P.H.M.M.

Both Luiz and Iasmim have terrible memories of the last time they heard the words marriage and graph in the same sentence. Therefore, help them solve this problem.

Pedro Pacoca enjoys playing an online car racing game and recently discovered that his colleague Pedro Gallo also plays the game. Excited by this, the two Pedros decided to help each other.

In the game, each player drives a car around a circuit, and the player who completes the course in the shortest time wins. To achieve this, it is crucial for players to avoid crashing their cars into others.

Knowing this, the two Pedros decided to share the initial positions of their cars, their speeds, and the directions they were moving. They also agreed to maintain both their speeds and directions constant.

Now, they need your help to determine if there will be a collision between the two cars. Given the initial positions and the speeds in the $$$x$$$ and $$$y$$$ directions for each car, determine the moment in time when a collision will happen. If no collision occurs, output $$$-1$$$.

For the purposes of collision detection in this problem, each car is modeled as a triangle on the plane.

Quirino is an aspiring Pokémon professor. He has a specialization in Taxonomy, and one of his responsibilities as an assistant to the renowned Professor Rowan is to decide the names of new Pokémon that are discovered in the Sinnoh region.

Different Pokémon cannot have the same name, so Quirino received a list of the last $$$N$$$ names given to Pokémon to avoid repetitions. Additionally, due to restrictions in the naming system, names must have a maximum of $$$K$$$ characters.

Quirino is methodical and wishes to choose the lexicographically smallest possible name for every Pokémon he will name. However, since he climbed Mount Coronet to uncover the secrets of the Creation Trio, he has not been seen again. In the name of Arceus, help him write a program that names new Pokémon according to his restrictions and preferences while he is away!

Note: a word $$$A$$$ is lexicographically smaller than another $$$B$$$ if it would come before it in the dictionary. That is, if $$$A \neq B$$$ and one of the two holds:

1. $$$A$$$ is a prefix of $$$B$$$.
2. At the first position $$$i$$$ (from left to right) where they differ, $$$A_i \lt B_i$$$ (with $$$P_i$$$ being the $$$i$$$-th character of $$$P$$$ from left to right).

Tiago DFS is going to China!!

And, taking advantage of the trip, he decides to go to the largest ancestral store in the city to buy the pieces missing from his xego collection.

The xego section can be represented by an immense shelf with $$$N$$$ xegos available, in positions numbered from $$$1$$$ to $$$N$$$, for purchase.

But the eccentric Chinese owner of the store chooses a continuous interval $$$[L, R]$$$ every day and allows customers to buy only the items within that interval. Additionally, he only allows the customer to enter the store once a day, so always choose wisely which items you will buy before leaving the store.

After hours, the owner himself always restocks the items that were purchased that day with the same items.

Moreover, each xego piece has an identifier, which can be represented by a unique positive integer $$$a_i$$$.

And everyone knows that if we combine xegos, we can form other xegos, which can also, in turn, be combined into other xegos.

After playing a lot with xegos, Tiago noticed a curious property: the combination of two xegos $$$A$$$ and $$$B$$$ into another xego $$$C$$$ can be exactly described as the XOR operation of their identifiers. That is, $$$A \oplus B = C$$$.

Knowing that he will have $$$Q$$$ free days to buy xegos, help Tiago to answer, for each day, how many distinct combinations of shelf positions he can buy to form the xego $$$X$$$, knowing that on that day the owner allowed the sale only of the continuous interval $$$[L, R]$$$.

The great Pokémon trainer Koga has decided that his team of Poison-type Pokémon needs more variety. To achieve this, Koga needs to understand a bit more about Pokémon types. Koga has 3 different Pokémon: Torterra, Staraptor, and Luxray, and he is going to face one of these three Pokémon. You must help him by telling which Pokémon Koga should use.

Torterra has an advantage over Luxray, Luxray has an advantage over Staraptor, and Staraptor has an advantage over Torterra.

Lórien, the last of the wizards of the Kingdom of Lagrange, found a secret formula carved into the walls of an ancient tower. It represents the absolute value of a powerful polynomial that, according to legends, possesses magical properties when applied correctly. The formula is:

$$$$$$f(x) = |(A+C)x^3 - Bx^2 + BCx + (x+C)(x-A)|.$$$$$$

To protect this knowledge, Lórien needs to apply the function to several values and reveal only the final result of a disguise spell: the XOR ($$$\oplus$$$) of all the results of the evaluations $$$f(x)$$$ at these values.

The XOR between two numbers $$$a$$$ and $$$b$$$ is another number $$$c$$$. To calculate $$$a \oplus b = c$$$, write the binary representation of $$$a$$$ and $$$b$$$. Each bit (digit in binary representation) of $$$c$$$ will be $$$1$$$ if the corresponding bits in $$$a$$$ and $$$b$$$ are different, and $$$0$$$ otherwise.

Your mission is to help him calculate this final value.

After a successful expedition for a marathon at UFG, the competitors AlbertoTDNeto, duduFreire, EYZ, henriqueramos.qs, and MagePetrus made a pact: every time the 5 of them meet, they must roll a D100 (100-sided die). If the rolled number is 100, they must immediately go to Goiânia.

After many meetings, this finally happened, and the competitors will keep their promises. They all get into Henrique's car, which will drive them to Goiânia. The marathon runners want to take the shortest possible route from Brasília to Goiânia, of course. Additionally, since the car is quite heavy, Henrique is worried about the possibility of running out of fuel in the middle of the road. So, among the shortest paths, he wants a path that minimizes the longest distance the car will travel between two gas stations.

The gas stations are numbered from $$$1$$$ to $$$N$$$. Henrique will start from Brasília at gas station number $$$1$$$ and will finish his journey at gas station number $$$N$$$, in Goiânia. There are $$$M$$$ roads connecting pairs of distinct gas stations. For each $$$i$$$ from $$$1$$$ to $$$M$$$, road number $$$i$$$ starts from gas station $$$a_i$$$, leads to gas station $$$b_i$$$, and has a length of $$$w_i$$$ kilometers. It is only possible to travel this road in the direction from $$$a_i$$$ to $$$b_i$$$. It is guaranteed that there is a path from $$$1$$$ to $$$N$$$.

Help Henrique find a shortest path that minimizes the longest distance traveled between two consecutive gas stations.

Frank and his friends are playing a game at the little gas station. The game has a list of $$$n$$$ distinct languages $$$a_1, a_2, \ldots , a_n$$$. Each language is represented by a number from $$$1$$$ to $$$n$$$ and appears only once. Frank does not trust the competitive programming skills of Brazilians, so he wants you to answer $$$q$$$ queries. Each query contains two integers $$$l$$$ and $$$r$$$, and you need to tell Frank if the sublist $$$a_l, a_{l+1}, \ldots , a_r$$$ is a good drink. Since Frank only speaks Polish, respond with "TAK" if the list is a good drink and "NIE" otherwise.

A list of size $$$m$$$ is a good drink if it is a permutation, that is, it contains all the numbers from $$$1$$$ to $$$m$$$ exactly once.