Enrique and Yan frequently play a game called 1D Scrabble. The game is played on a one-dimensional, infinite board using a fixed dictionary of unique words. On the first turn ($$$i = 1$$$), any word $$$w_1$$$ from the dictionary may be played. On every subsequent turn ($$$i \gt 1$$$), the played word $$$w_i$$$ must contain the previous word $$$w_{i-1}$$$ as a contiguous substring. The game concludes as soon as no valid moves remain.

Recently, Yan did not have time to play, so Enrique started playing with GePeTo. However, GePeTo started hallucinating! It consistently states that this game is trivial, arguing that there are very few combinations. Help Enrique convince GePeTo by calculating the total number of distinct possible games. Two games are distinct if their sequences of played words $$$(w_1, \ldots, w_k)$$$ are different.

In order to teach people empathy, GePeTo demands that people often change houses, so that they learn to "live in another's shoes". There are $$$N$$$ houses in the city, each housing one person, and on the $$$i$$$-th house GePeTo placed the label $$$\pi(i)$$$ meaning that, every day at midnight, the person living in house $$$i$$$ has to move to house $$$\pi(i)$$$. All people move at the same time, and it is guaranteed that after a move no house is left empty, and no house has two people.

We say $$$\pi$$$ has a cycle of size $$$k$$$ if, after $$$k$$$ days, some person returns to the house where they initially lived, that is, if $$$\pi^k(x) = x$$$ for some $$$1 \leq x \leq N$$$.

GePeTo asks you to swap the labels of two houses in order to maximize the size of the smallest cycle, that is, choose a single pair $$$(i, j)$$$ and swap $$$\pi(i)$$$ with $$$\pi(j)$$$ to maximize the minimum $$$k$$$ such that $$$\pi^k(x) = x$$$ for some $$$1 \leq x \leq N$$$. You are allowed to choose $$$j = i$$$, in which case $$$\pi$$$ remains unchanged.

As GePeTo assimilates all data on the internet, they are looking for a way to compress that data so it occupies less space. For this purpose, they came up with the following compression algorithm.

Given a string $$$s$$$ containing lowercase English letters, each maximal consecutive repetition of a letter $$$c$$$ must be replaced by $$$c$$$ followed by $$$n$$$, where $$$n$$$ is the number of repetitions of that letter. If the letter is repeated just once, then it should not be replaced by $$$c1$$$, as that would increase the size of the string.

As an example, consider the string "zzzabbc". Since the letter 'z' is repeated three times consecutively and 'b' twice, the result of the compression is "z3ab2c".

Your task is to implement this algorithm.

After learning all competitive programming problems, GePeTo is now studying all board games in the world, and is particularly interested in a copy of Escape it found in your room.

In Escape, you have 5 identical six-sided dice, with the following faces:

• 2 Adventurer faces (A)
• 1 Torch face (T)
• 1 Key face (C)
• 1 Black Mask face (N)
• 1 Golden Mask face (D)

In an important part of the game, you are given an objective, which is a multiset of up to 5 symbols selected from ATC. Your goal is to roll the dice and finish with their top faces showing at least the symbols required by the objective.

Starting from an initial roll of the 5 dice, you have a maximum of $$$K$$$ turns (rerolls) to achieve the objective. In each turn, you select a subset of the current dice and reroll them, subject to the following rules:

• A die showing the Black Mask face (N) becomes locked and cannot be selected for rerolling.
• For each rerolled die that is currently showing the Golden Mask face (D), you gain the right to simultaneously unlock and reroll up to 2 locked dice.

Assuming you play optimally, that is, making decisions each turn that maximize the probability of achieving the objective within $$$K$$$ turns, answer the following: What is the maximum probability of success, and what is an optimal first reroll?

Renzo has a top-secret plan for finally overthrowing the evil reign of GePeTo. In order to execute his plan, Renzo needs you to distract the overlord.

As you may already know, there are some tasks that AIs struggle to accomplish, and GePeTo is no exception. It is well known that AIs are not good at counting letters, for instance. Also, some specific prompts, such as asking for the seahorse emoji, drive AIs crazy. But there is one task GePeTo struggles with the most: computing Grundy numbers.

Let $$$A$$$ be a sequence of $$$2^n$$$ numbers. For each $$$i$$$ ($$$0 \leq i \leq 2^n - 1$$$), define the Grundy number $$$$$$ g_A(i) = \operatorname{mex}(\{g_A(j) : j \lt i \text{ and } A_i \oplus A_j \text{ is a power of two}\}), $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation, and $$$\operatorname{mex}(S)$$$ is the minimum non-negative integer that is not contained in $$$S$$$.

As an example, consider the sequence $$$$$$ A = (0, 3, 1, 2) $$$$$$ and its corresponding Grundy numbers $$$$$$ g_A = (0, 0, 1, 1). $$$$$$

Your task is to find a permutation $$$P$$$ of the numbers from $$$0$$$ to $$$2^n - 1$$$ that maximizes the maximum Grundy number, so that GePeTo will spend a lot of time trying to compute them. Formally, the permutation $$$P$$$ must maximize $$$$$$ \max_{0 \leq i \leq 2^n - 1}\{g_P(i)\} $$$$$$ among all permutations of the numbers from $$$0$$$ to $$$2^n - 1$$$.

After GePeTo assumed control of the surface, the last members of the resistance were forced to hide underground.

To protect themselves from the robots, they built a network of tunnels connecting $$$N$$$ underground points. The network was designed without redundant paths: between any two points, there is exactly one possible path.

The resistance's shelters are located at the extremities of this network, that is, at the vertices that have only one tunnel connected to them (the leaves of the tree).

To plan communication between the shelters, the resistance needs to answer $$$Q$$$ queries. In each query, given an integer $$$X$$$, determine how many pairs of shelters are separated by exactly $$$X$$$ tunnels.

Lately, GePeTo has developed a fascination with the digit $$$4$$$, declaring it the most elegant digit in existence. To prove your mathematical prowess, GePeTo challenges you to the classic "Four Fours" puzzle.

Given a non-negative integer target $$$X$$$, your goal is to construct a mathematical expression that evaluates to $$$X$$$ using **exactly four** digits 4 and any combination of the following allowed operators and notation:

• Basic arithmetic: +, -, *, /
• Exponentiation: ^{}
• Parentheses: ()
• Decimal point: . (e.g., .4 for $$$0.4$$$, 4.4)
• Square root: sqrt
• Factorial: !

Some examples of valid expressions:

• 5 = (4 * 4 + 4) / 4
• 14 = 4 * (4 - .4) - .4
• 22 = 44 / 4 * sqrt(4)
• 27 = 4 - 4/4 + 4!
• 60 = (4 + 4)^sqrt(4) - 4

After the silicon reserves ended on Earth, in order to produce more chips, GePeTo discovered a new mineral, called Teotonium, on Mars. As GePeTo is busy writing some poetry about the meaning of life, they asked you to deal with the technical details of the excavation.

The $$$N$$$ deposits of Teotonium are placed in a line, and the $$$i$$$-th deposit has $$$A_i$$$ tons of Teotonium. The Teotonium miners work in an odd manner: each has a gap number $$$M$$$ and, after mining all Teotonium in deposit $$$i$$$, it can mine either deposit $$$i+M$$$ or $$$i-M$$$, and repeat. That is, it can only mine deposits $$$j$$$ such that $$$j \equiv i \pmod M$$$.

Your task is to answer $$$Q$$$ queries given by $$$L$$$, $$$R$$$, $$$X$$$, and $$$M$$$, in which you must determine the total Teotonium in all deposits with index $$$i$$$ such that $$$L \leq i \leq R$$$ and $$$i \equiv X \pmod M$$$.

GePeTo has assumed control of practically all machines on the planet. During a resistance mission, your team was cornered by an army of robots and the only option to escape is to use an old combat spaceship.

Viewed from above, the spaceship is shaped like a convex polygon. The robots are represented by points in the plane and are all initially outside the spaceship.

The navigation systems have been damaged: before departing, it is possible to choose only one direction, and then the spaceship will follow this direction indefinitely, without making turns or rotations.

A robot is destroyed if the spaceship passes over its position at any point during its movement. Positions on the boundary of the spaceship are also considered hit.

Determine the maximum number of robots that can be destroyed by choosing the spaceship's direction of movement optimally.

In order to obtain more food tokens, you plan to present the GePeTo overlord with an array of numbers $$$A$$$. As they were trained on more even numbers than odd numbers, GePeTo prefers even numbers, so you want to change some numbers in $$$A$$$ to maximize the number of even numbers.

Since you are already the first in line, you only have time to apply a single operation to $$$A$$$: pick a number $$$X$$$ and a range $$$[L,R]$$$ and add $$$X$$$ to elements $$$A_L, \ldots, A_R$$$. After performing this operation exactly once, what is the maximum possible number of even numbers in $$$A$$$?

After the city he lives in was devastated by the overlord GePeTo, Pedro needs to escape to a survivors' shelter, but the only exit available is through the subway.

Unfortunately, he has no money to pay for the fare. However, he notices that there is a special property in the turnstile, which displays a number $$$C$$$ representing the number of times someone has passed through it: the turnstile allows free passage if all digits of $$$C$$$ are distinct!

Each person passing through the turnstile increases the counter $$$C$$$ by $$$1$$$. Given the number $$$C$$$ currently displayed by the turnstile, determine the minimum number of people that need to pass through it so that Pedro can finally pass for free and escape the city.

After studying all competitive programming problems ever created, GePeTo became a superpowerful artificial intelligence. Now, to begin its plan for world domination, it is creating thousands of copies of its agents.

Each agent has an identification code. However, due to a flaw in the production system, different agents can receive the same code.

The agents are organized in a sequence $$$A$$$ of $$$N$$$ positions, where $$$A_i$$$ represents the code of the agent at position $$$i$$$.

Your mission is to find how many pairs of agents have the same code. In other words, determine the number of index pairs $$$(i, j)$$$ such that: $$$$$$ 1 \leq i \lt j \leq N \quad \text{and} \quad A_i = A_j $$$$$$