Guizinho has just bought a new pair of glasses and can finally see the stars! Very excited about this, he started noting down patterns he observed in the night sky.

After years of observation, Guizinho recorded in his notebook $$$N$$$ numbers $$$a_1, a_2, ..., a_N$$$, representing that star $$$i$$$ appears in Earth's sky every $$$a_i$$$ years. Gui says that this number represents the period of a star.

The year 2024 is a very lucky year for him because, while observing the sky, he noticed that all $$$N$$$ stars whose periods he recorded are visible at the same time! Guizinho named the years in which all these stars appear in the sky simultaneously as "stellar years."

After admiring the sky long enough, he started thinking about the future of star observation: Knowing that the current year is a stellar year, which stars will be visible in Earth's sky after $$$X$$$ more years?

Giovana and Julia, after becoming the champions of the Bit Tennis doubles tournament on Earth, decided to travel to another planet in search of more competition. During the trip, they remembered they had a holographic piece board that allows them to play various games. Since they were already bored of all the games (including Bit Tennis), they decided to invent a new game: Bit Tennis 2.

The rules of the game are as follows:

• The game starts with $$$N$$$ stacks of holographic pieces, where the $$$i$$$-th stack contains $$$a_i$$$ pieces;
• Julia starts the game, and after that, the turns alternate between Giovana and Julia;
• On each turn, the player must choose a stack and remove any number of pieces that is a power of 2;
• The player who cannot make a move loses the game.

For the game with stack sizes [5, 1, 3, 2], Julia, by starting, has a strategy that ensures Giovana cannot win the game.

They both realized that the game was very difficult for the second player, so they added a new rule: before the game begins, Giovana must perform the following operation exactly $$$X$$$ times:

• Choose a stack and double the number of pieces in it. That is, if Giovana chooses stack $$$i$$$, which has $$$a_i$$$ pieces, it now has $$$2 \cdot a_i$$$ pieces.

Both players, just like when they invented Bit Tennis, quickly learned to play optimally and noticed that the outcome of the game seems to be determined even before the first move is made. Curious about this fact, they asked for your help. Given $$$N$$$, $$$X$$$, and the size of each stack, they ask you to determine who will be the winner.

Lívia is the captain of a spaceship that was attacked by space pirates, and, as a last resort for survival, she had to eject herself from the ship.

Now, Lívia finds herself floating aimlessly through space, and the only things she has with her are her cellphone and a pair of headphones. Luckily, she managed to send an SOS before leaving the ship and knows that, although it may take a few days, help is on the way. To pass the time, she decided to listen to some songs by her favorite artist, Saylor Twift.

Lívia created her own musical notation for the melodies she listens to. She considers that a song contains at most 26 distinct musical notes, and, when listening to a melody, she represents each musical note by one of the letters of the Latin alphabet (from "a" to "z"). Therefore, a melody is represented by a sequence of letters.

Additionally, Lívia wrote down $$$N$$$ pairs of notes $$$(u, v)$$$ to represent that note $$$v$$$ sounds good after note $$$u$$$. Now, she wants to compile a playlist with all of Saylor Twift's beautiful songs, so she asked for your help. Lívia considers beautiful only the melodies where, for every note played (except the first), it sounds good after the previous note.

Lívia emphasizes that a certain note $$$v$$$ sounding good after note $$$u$$$ does not mean that note $$$u$$$ would also sound good after note $$$v$$$. Given a melody by Saylor Twift, determine whether Lívia will consider it beautiful or not.

Commander Rosso, renowned for his precise and safe landings, finds himself in a critical situation in the middle of the void of space during yet another mission. An unexpected solar storm interrupts his exploration mission, damaging the navigation systems of his ship, the Geometric Voyager, and forcing an emergency landing on the remote planet JOI-47.

The terrain of JOI-47 is notoriously uneven: there is a chain of kilometer-high mountains and only a small strip of land where the ship can land, located beyond the mountains.

Upon entering the planet's dense atmosphere, Rosso must carefully adjust the initial descent altitude of the Geometric Voyager, as the ship's automated altitude control system causes it to descend at a constant rate of one kilometer per second. Each second of descent corresponds to one kilometer of forward movement toward the landing strip. Since the available landing strip is short, Rosso wants to choose the smallest possible initial altitude that avoids all the mountains. The ship avoids a mountain if its altitude is strictly greater than the mountain's height when passing over it.

In the example above, the smallest initial altitude required to pass over the mountains is 5; if the initial altitude were lower, the ship would collide with the first or second mountain. The mountains have heights $$$[2, 2, 1]$$$ and the ship will have altitudes $$$[4, 3, 2]$$$ while passing over the mountains. Note that the height of the Geometric Voyager is measured by the number of squares below it, and when the ship is landed, its height is zero.

You are Rosso's co-pilot and he wants to test whether you are fit to pilot the Geometric Voyager alone. Mistakes are not an option, as a poorly calculated initial altitude could cause the ship to crash into the mountains or fail to land in time. Given the heights of the $$$N$$$ mountains, report the ideal height to enter the landing course.

Max and his older brother Min had an unbreakable bond throughout their lives. However, a few years ago, Min moved to the Sombrero Galaxy, where he opened a coffee shop, El Café, and became very successful.

Following his family's passion for coffee, Max applied for a job at his brother's coffee shop. The first stage of the selection process is a simulation of a normal working day, which would be straightforward if not for the unconventional way the café serves its customers.

At El Café, there is only one type of drink, the vainilla helada, which consists of a combination of ALL (yes, all) the available ingredients in the store at that moment. Furthermore, each ingredient must be equally distributed among the ordered drinks, based on the quantity of each. Thus, when a customer places an order at El Café, they only specify the number of vainillas heladas they want, and, if possible, the employee must prepare the order. If it is not possible, the customer should be informed that the requested quantity of drinks cannot be made at that time.

For example, if the current list of ingredient quantities is $$$[24, 12, 3]$$$ and a customer orders $$$3$$$ vainillas heladas, Max should inform them that he can fulfill the order, as he can prepare three drinks, each using ingredient quantities $$$[8, 4, 1]$$$. On the other hand, if the customer had requested 2 drinks, Max would have had to inform them that it is not possible at the moment.

During the shift, new ingredients may arrive, and some of the newest ingredients may expire, forcing Max to throw them away (expiration works differently in the Sombrero Galaxy).

To increase his chances of getting the job, Max decides to call you (since he knows your programming skills) and asks you to write a program to help him train for the selection process.

The program must handle $$$3$$$ types of requests:

• Type $$$1$$$: indicates that a new ingredient has arrived in quantity $$$G$$$. Note that each arriving ingredient is different from the others.
• Type $$$2$$$: indicates that the last $$$K$$$ ingredients, i.e., the $$$K$$$ newest ingredients, have expired and must be discarded.
• Type $$$3$$$: simulates a possible order of $$$X$$$ vainillas heladas from a customer. The program should only inform whether it is possible to fulfill such an order.

Given the number $$$N$$$ of different ingredients at the beginning of the shift, the quantity $$$a_i$$$ of each ingredient, and the $$$Q$$$ requests, write a program to help Max pass the test.

Eric has just bought a new game for his NES, called Battletoads. The objective of the game is to defeat the Dark Queen and her army of space mutants.

After spending a long time trying to beat the game, he realized that it was very difficult to kill the Dark Queen because his character had no weapons and needed to defeat her using only punches.

Frustrated by not being able to defeat the game's final boss, Eric decided to develop a new game, which he named Battlefrogs. In this game, the final boss is called Light Queen and the playable characters are always equipped with a laser weapon. The weapon works as follows:

Let $$$E$$$ be the weapon's energy.

• If $$$E \gt 0$$$, Eric can fire a laser beam and $$$E$$$ decreases by one unit. If Eric fires the beam at a space mutant, the mutant will die, and if he fires the beam at the Light Queen, her life decreases by one unit.
• If $$$E \le 0$$$, Eric can still fire a laser beam and $$$E$$$ decreases by one unit. However, if Eric fires the beam at a space mutant, the mutant will die, but if he fires the beam at the Light Queen, her life will not be affected.

Before reaching the Light Queen's level, Eric must pass through $$$N$$$ levels numbered from $$$1$$$ to $$$N$$$, starting from level $$$1$$$. Each level contains $$$s_i$$$ space mutants on the way and an energy bank with power $$$e_i$$$ that charges his weapon by $$$e_i$$$ units. Additionally, at the start of each level, there is an alternative route with a wormhole guarded by $$$X$$$ space mutants that allows Eric to skip $$$k$$$ levels ahead.

If Eric uses the wormhole at level $$$i$$$, he immediately jumps to level $$$i+k$$$, or, if the $$$(i+k)$$$-th level does not exist, to the Light Queen's level. When using the wormhole, Eric does not need to kill any of the $$$s_i$$$ mutants, but he will not be able to charge his weapon by $$$e_i$$$ units and is required to kill the $$$X$$$ mutants guarding the wormhole. If he decides not to use the wormhole at level $$$i$$$, he must defeat the $$$s_i$$$ space mutants, will be able to increase his weapon's energy by $$$e_i$$$ units, and will proceed to level $$$(i + 1)$$$, or to the Light Queen's level if the $$$(i + 1)$$$-th level does not exist.

Knowing that the Light Queen dies when her life reaches $$$0$$$ and that Eric's weapon starts with $$$0$$$ energy, he is now thinking about balancing the game and needs to decide how much life to assign to the final boss. He asked you: what is the maximum amount of life the Light Queen can have so that it is still possible to defeat her?

Léo and Ema are two astronauts living on Earth. One day, Ema was called on a mission to planet Miller, which orbits a black hole named Gargantua.

Because it orbits a black hole, time on Miller passes $$$X$$$ times slower than on Earth.

Knowing that Léo was $$$A$$$ years old before Ema traveled, and that Ema stayed $$$Y$$$ years (according to Miller's time) on Miller, what will be Léo's age when Ema returns to Earth?

Risa is the greatest thief in the GianParme Galaxy, and she is preparing for her biggest heist yet. The target is on planet Amorim, named after its fearless leader Matheus Amorim, who ruled the planet for many years until his tragic passing.

Risa's goal is to steal the planet's greatest relic, the crown that Matheus wore during his reign. The artifact is stored in a museum on planet Amorim. The first step of her plan is figuring out how to reach this planet.

The GianParme Galaxy can be modeled by $$$N$$$ planets numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ connections between them. Each connection is represented by two planets $$$(u, v)$$$ and a "Higgs level" $$$h$$$. The connections are designed such that it's possible to travel from any planet to any other planet using the galaxy's connections.

The Higgs level is a form of security in the galaxy; all residents of GianParme have their own Higgs level, and to use a connection between two planets, their Higgs level must be greater than or equal to the Higgs level of that connection.

Risa is currently on planet number $$$1$$$, and planet Amorim is planet number $$$N$$$. Since Risa is a well-known thief, her Higgs level is $$$0$$$, and to complete her journey to planet Amorim, she has two options:

• Bribe the guard of a connection to use it regardless of her Higgs level.
• Forge her identity to have any Higgs level she desires.

However, forging an identity is a very difficult task, so she needs to know: What is the minimal Higgs level she must forge in order to complete her journey to planet Amorim, knowing she has enough money to bribe $$$K$$$ guards?

João is visiting a planet far from Earth, the alien planet PEI-X40, governed by Nei, a peaceful leader who warmly welcomed João's arrival.

The inhabitants of this planet use binary representation to express numbers: for example, the number $$$6$$$ on Earth is represented as "$$$110$$$" there. In this representation, they refer to each digit as an "it", upon which they define operations called "itwise". Among these, the main ones are "band" and "bor".

The bor operation is particularly interesting to an astronomer like João because Nei has decreed that the beauty of a constellation is defined as the itwise bor of the brightness values of all the stars within it.

Curious, João studied a bit about bor and learned that it is represented by the symbol "$$$|$$$" and works as follows:

For each position $$$i$$$ in the binary representation of $$$X$$$ and $$$Y$$$, if $$$X$$$ has the $$$i$$$-th it equal to $$$1$$$ and/or $$$Y$$$ has the $$$i$$$-th it equal to $$$1$$$, then $$$X$$$ $$$|$$$ $$$Y$$$ has the $$$i$$$-th it equal to $$$1$$$. Otherwise, $$$X$$$ $$$|$$$ $$$Y$$$ has the $$$i$$$-th it equal to $$$0$$$.

For example, in binary, $$$101$$$ $$$|$$$ $$$010 = 111$$$. This is equivalent to $$$5$$$ $$$|$$$ $$$2 = 7$$$ in the Earth decimal system.

While gazing at the sky of PEI-X40, João noticed a peculiar constellation: there were $$$N$$$ stars in the sky, one next to the other. He then recorded the brightness of each star $$$b_1, b_2, \cdots, b_N$$$, in the order they appeared.

After jotting down some mathematical expressions, he realized that this constellation can be divided into several continuous constellations in such a way that the structure of the stars being next to each other is preserved.

Now, João wants to divide the constellation into several others so that the sum of the beauties of all these constellations is maximized, and, among all the ways that yield the maximum sum, he wants the division with the smallest number of constellations. Since the inhabitants of PEI-X40 didn't train him well enough for this, he asked for your help.

The billionaire explorer Granza, founder of the major space travel company Space-Y, enjoys exploring the Universe aboard his ship, the StarPuma-GTE.

During one of his trips through the Sombrero Galaxy, Granza discovered a planet called Guadalajara. This planet was famous not only for its breathtaking landscapes but also for its enormous casinos and a peculiar card game known as At-Poker.

At-Poker was considered the national pastime of Guadalajara, involving skill, luck, and strategy. On this planet, the casinos are luminous temples where fortunes are made and lost in a matter of rounds. Granza, always a man of challenges, couldn't resist the temptation to participate. As they say in Guadalajara, Granza "jugó fuerte" — he bet high — and unfortunately, his Earth poker skills were of little use against the complex strategies of At-Poker, and he soon found himself without a large part of his fortune.

In At-Poker, $$$N$$$ players numbered from $$$1$$$ to $$$N$$$ are arranged around a circular table in the order $$$1, 2, 3...N$$$, so that for every player $$$i$$$ from $$$1$$$ to $$$N-1$$$, they are to the left of player $$$i+1$$$, and player $$$N$$$ is to the left of player $$$1$$$.

In the game of At-Poker, each player receives a deck of cards represented by a string of lowercase letters and a number $$$G_i$$$. The official rulebook specifies the following:

Rules of At-Poker

1. Forming the Hand: Each player $$$i$$$ forms their hand by concatenating the decks of the $$$G_i$$$ players to their left, plus their own deck. This is done in a circular manner, where $$$N$$$ is the total number of players. For example, if $$$N = 5$$$ and $$$G_i = 3$$$ for player $$$i = 3$$$, then player 3's hand is formed by concatenating the decks of players $$$5$$$, $$$1$$$, $$$2$$$, and $$$3$$$, in that order.

2. Wildcards and Scores: There are several strings placed on the table, which are called wildcards. Each wildcard string $$$j$$$ has an associated value $$$X_j$$$.

3. Calculating the Score: A player's score is determined by the highest value among the wildcards that occur in their hand as a contiguous subsequence, where the occurrence of the wildcard must end within the player's original deck (i.e., it cannot be entirely within the decks of players to their left). If no wildcard occurs in the player's hand, their score is zero.

Determined not to leave Guadalajara as a loser, Granza set out to learn the strategies of At-Poker. He knew that the only way to return to Earth having recovered his losses would be if he could guarantee a win. To do so, he needed a system that could predict, based on the initial hands of each player, how many points each would score at the end of a round.

Machado, a renowned researcher at the BRUTE Space Agency, invented a device he believes can reveal important patterns for the trajectory of planetary orbits. This device, named "Kosmos", produced a revolutionary numeric sequence, but since it was programmed in pure C, a memory leak occurred which led to the device's self-destruction. After discovering this, Machado immediately started programming everything in Rust. Now, shaken by the loss of his invention, the only thing he remembers is that the sequence produced by the device was defined by the following recursive formula:

Kosmos had enough computational power to compute any term of this sequence from $$$1$$$ to $$$10^{18}$$$. Since the value of the term can be enormous, Machado is only interested in the remainder of this number modulo $$$998244353$$$. However, without Kosmos, Machado has no idea how to compute the $$$N$$$-th term of this sequence if $$$N$$$ is that large. Therefore, he has asked for your help.

Dudu is a great astronaut working for BRUTE — Brazilian Universal Technological Expeditions — and he has been given the difficult task of traveling to the planet "LK-4D4" to collect some precious rocks classified as "lango mocos."

After years in cryogenic sleep, Dudu finally arrived on this planet and began studying the lango mocos found there. After much research, he discovered that lango mocos contain chemical components never before seen by humans and that certain types of these rocks are toxic when in contact with certain other types.

He classified the lango mocos into $$$N$$$ types and wrote down $$$M$$$ pairs in his notebook. A pair $$$(u, v)$$$ written in Dudu's notebook means that lango moco type $$$u$$$ is toxic when in contact with lango moco type $$$v$$$ (and vice versa).

Fascinated by the lango mocos, Dudu decided he wants to bring all types of this precious rock back to Earth. Since the return trip is very long, Dudu must store the lango mocos in special bags that protect them from the dangers of space, and obviously, he doesn't want to place two lango mocos that are toxic to each other in the same bag. Each bag can hold an infinite quantity of lango mocos, as they are made from an expandable material developed by BRUTE.

More formally, if a bag contains types $$$a_1, a_2, \dots, a_k$$$, there must be no pair $$$(i, j)$$$ $$$(1 \le i, j \le k)$$$ such that $$$a_i$$$ is toxic to $$$a_j$$$.

Unfortunately, Dudu only has two special bags, and now he doesn't know how to separate the lango mocos.

To solve this problem, Dudu sent a message to you, one of BRUTE's best programmers, asking you to separate all the lango mocos into 2 bags, or tell him that the mission is impossible. If there is more than one way to make this separation, you can choose any of them.

Joãozinho is an astronomer who has just started his master's degree at UFMG, studying the "worms" of the multiverse.

The multiverse is the set of all universes that exist, and Joãozinho is researching a hierarchical way to represent it. In his studies, each universe in the multiverse is assigned an integer $$$u$$$ as its identifier, and in each universe, there are several giant worms that allow travel to other universes.

The first thing Joãozinho did was to write down all the facts he knows about the multiverse. Here is everything he recorded:

• If a universe $$$u$$$ has a giant worm that allows travel to universe $$$v$$$, then it is physically impossible for universe $$$v$$$ to have a worm that allows travel back to universe $$$u$$$.
• The multiverse can be modeled as a directed tree, where the nodes of the tree are universes and an edge from universe $$$u$$$ to $$$v$$$ represents a giant worm that allows travel from $$$u$$$ to $$$v$$$.
• There exists exactly one universe from which all other universes can be reached. Joãozinho labeled this universe with the number $$$1$$$.
• If universe $$$u$$$ has a worm that allows travel to universe $$$v$$$, then the number of stars in universe $$$u$$$ is strictly greater than the number of stars in universe $$$v$$$.

Joãozinho's master's advisor, Karina, gave him a task to simulate any multiverse that obeys the rules of the real multiverse, and this simulation must be able to answer very specific questions about any multiverse.

After weeks of hard work, Joãozinho is almost done, but one "sub-task" remains, and he can't solve it. It is defined as follows:

Given $$$K$$$ universes $$$a_1, a_2, \cdots, a_K$$$, calculate the following sum:

Where $$$f(i, j)$$$ is the number representing the universe with the smallest number of stars from which it is possible to travel to universes $$$a_i, a_{i + 1}, \cdots, a_{j - 1}, a_j$$$.

Joãozinho is out of ideas on how to solve this, so he asked for your help to write a program that receives $$$Q$$$ such queries and answers them.

Enzo is a big fan of the game Lemmings, and his favorite parts of the game are protecting the Lemmings from danger and when they build ramps to travel safely from one place to another.

Since Enzo finds Lemmings a bit outdated, he decided to create a futuristic version of the game. He named his game "Almeidings 3077" and made it in 2D, viewed from above.

In Almeidings 3077, there are several creatures — the Almeidings — that must travel from a starting point $$$(x_i, y_i)$$$ to an endpoint $$$(x_f, y_f)$$$ safely. To parallel the ramp-building mechanics of the original game, Enzo created the concept of Protective Shields. A Protective Shield is a structure built by the Almeidings that allows them to pass safely through dangerous areas.

Enzo defined the following rules for his game:

• The game is in 2D, and the space can be represented by an $$$N \times M$$$ matrix.
• A Protective Shield has the shape of a cross and is centered at $$$(x, y)$$$. A Protective Shield centered at $$$(x, y)$$$ protects all the cells in row $$$x$$$ and all the cells in column $$$y$$$.
• An Almeiding can occupy cell $$$(x, y)$$$ if and only if that cell is protected by a Protective Shield.
• The Almeidings can move in 4 directions (right, left, up, down):
  • From $$$(x, y)$$$ to $$$(x + 1, y)$$$.
  • From $$$(x, y)$$$ to $$$(x - 1, y)$$$.
  • From $$$(x, y)$$$ to $$$(x, y + 1)$$$.
  • From $$$(x, y)$$$ to $$$(x, y - 1)$$$.

After deciding that the goal of the game is to make the Almeidings conquer the space, Enzo decided to simulate it with your help. He will ask you $$$Q$$$ queries, and each query can be one of two types:

• Type $$$1$$$: Make an Almeiding build a Protective Shield centered at $$$(x, y)$$$.
• Type $$$2$$$: If there is an Almeiding at $$$(x_i, y_i)$$$, is it possible for it to reach $$$(x_f, y_f)$$$?

Your task is to answer all type $$$2$$$ queries correctly.

Malu is on a journey to the distant planet Osmos V aboard her spaceship, the HB-20000. Traveling at a speed close to the speed of light, Malu cannot determine her exact position in the universe. However, she knows that the total duration of the trip is exactly $$$X$$$ years and that $$$Y$$$ years have already passed.

How many years are left until Malu reaches her destination?