Luiz, Carol, and Henrique agreed to meet at the park after the UnBalloon running club meeting to organize their team for the VII UnBalloon Marathon, the most anticipated race of the year. However, Luiz, being an excellent runner, finished the course before the rest of the team, coming in $$$3^{rd}$$$ place in the club (behind Maxwell and Arthur).

While waiting for Carol, who is slower due to a knee injury, and Henrique, who is still waiting for the bus, Luiz began observing the trees in the park. He noticed that one tree was quite different from the others, having several parts of distinct colors. Knowing that if he mentioned this, his team would rather investigate the colors instead of focusing on the upcoming marathon, help Luiz answer his teammates' various questions.

The tree observed by Luiz can be modeled as a connected acyclic undirected graph with $$$N$$$ nodes and $$$N-1$$$ edges, where the root is fixed at vertex $$$1$$$. Each node $$$i$$$ has an associated color, represented by an integer value $$$a_i$$$.

Your task is to help the team answer $$$Q$$$ queries. Each query consists of a node $$$x_i$$$, and you must determine the number of distinct colors present on the unique path between node $$$x_i$$$ and the root of the tree.

Nirva is one of Unballoon's newest talents. As everyone knows, one of the main pieces of advice we hear at the beginning of a competitive programming career is to focus on improving reasoning skills and leave learning more advanced topics, such as suffix automaton, flow, FFT, etc., for later. As everyone also knows, this advice is almost always completely ignored. Because of that, Nirva decided to learn "Segment Tree Beats". The author of this data structure himself has the following to say about it:

"In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorithms in these reports. And I find that some of them are quite new for competitors in CF although they are well known in China [...].

This blog is about my report which is written about two years ago. [...] the name "Segment tree beats" is given by C_SUNSHINE which is from a famous Japanese anime Angel Beats."

As expected, Nirva easily understood how Segment Tree Beats works and made her own implementation. To test whether it is correct, she thought it would be interesting to compare her implementation with yours.

You are given $$$n$$$ non-negative integers $$$a_1, \dots, a_n$$$. Your program must process $$$q$$$ operations of three types:

1. $$$\operatorname{chmod}(l,r,x)$$$ — For all indices $$$i$$$ such that $$$l \le i \le r$$$, replace the value of $$$a_i$$$ with $$$a_i \mathbin{\%} x$$$.
2. $$$\operatorname{chmax}(l,r,x)$$$ — For all indices $$$i$$$ such that $$$l \le i \le r$$$, replace the value of $$$a_i$$$ with $$$\max(a_i, x)$$$.
3. $$$\operatorname{sum}(l,r)$$$ — Print the sum of the elements $$$a_i$$$ such that $$$l \le i \le r$$$, that is, $$$a_l + a_{l+1} + \dots + a_r$$$.

Tiagodfs, a legendary competitive programmer, decided to hide his most valuable solutions in a rectangular field of dimensions $$$b \times h$$$.

The hiding spot was chosen completely at random: every point inside the field has the same probability of containing the treasure.

After a long investigation, the team Chappell Roan, vc tá jurada aqui em São Sebastião finally discovered the existence of this hiding spot. To recover the secret codes, they decided to use a special excavation machine capable of digging a region in the shape of a regular hexagon with side length $$$l$$$. The excavated region will be positioned so that it is entirely contained within the field.

Determine the probability that the team Chappell Roan, vc tá jurada aqui em São Sebastião finds the treasure with this kind of excavation.

In the Hidden Village of Balloons, those who seek to improve their skills are always close to the training field. The field area is vast, with a section containing $$$N$$$ logs lined up, all $$$N$$$ meters tall, numbered from $$$1$$$ to $$$N$$$. To use them as a kind of scale, each log numbered $$$i$$$ was marked exactly every $$$i$$$ meters (up to $$$N$$$). For example: if $$$N = 3$$$, log $$$1$$$ has marks at $$$1$$$, $$$2$$$, and $$$3$$$ meters, log $$$2$$$ has a mark at $$$2$$$ meters, and log $$$3$$$ has a mark at $$$3$$$ meters.

Among the ninjas in the training field on a certain day was Lucas Sala — a shuriken specialist, capable of throwing more than one billion shurikens simultaneously! He was seeking to perfect his Wind Style: Multiple Aerial Shurikens jutsu, which can hit several opponents with a large number of shurikens. To do this, he was using the logs in the training field as follows: he chose two integers $$$l$$$ and $$$r$$$, with $$$1 \leq l \leq r \leq N$$$, and threw $$$x$$$ shurikens at each of the logs from $$$l$$$ to $$$r$$$ inclusive — hitting them all, of course.

However, Lucas Sala's feat was not enough to impress his sensei, José. So he proposed a challenge for his student: José chose integers $$$l$$$, $$$r$$$, and $$$k$$$ $$$(1 \leq l, r, k \leq N)$$$, and, among the logs from $$$l$$$ to $$$r$$$, Lucas Sala should throw $$$x$$$ shurikens only at those with exactly $$$k$$$ marks. This challenge was performed several times, with different values of $$$l$$$, $$$r$$$, and $$$k$$$. However, José was not able to keep track of all the shurikens thrown to verify Lucas Sala's aim, so he stopped at some moments between challenges to choose other integers $$$l$$$ and $$$r$$$ and count the number of shurikens hit on each log from $$$l$$$ to $$$r$$$.

Thus, being very careful, José wrote down in his scroll two types of events related to that day's training, in the order they occurred:

1. $$$l \ r$$$: José counts the total number of shurikens hit on all logs from $$$l$$$ to $$$r$$$.
2. $$$l \ r \ k \ x$$$: Lucas Sala hits $$$x$$$ shurikens on every log $$$i$$$ such that $$$l \leq i \leq r$$$ and log $$$i$$$ has exactly $$$k$$$ marks.

That day was many years ago, and José remembers that time fondly. Looking at his scroll, he realizes that he did not write down, for the type $$$1$$$ events, the total number of shurikens he counted, which is a pity. Help him relive the old days and recover that information for him!

Since each counted quantity can be very large, you must print the remainder of each one when divided by $$$10^9+7$$$.

The secret society UnBalloon has many members, many contacts, and many agreements. Because of a bet lost in rock-paper-scissors during a trip, UnBalloon became responsible for sending, every full moon, a supply of mice to feed the forest witch's pet snake.

In a certain month, the full moon fell on Wednesday, Caleb's day off from work (one of UnBalloon's members). Because of this, he was chosen to deliver the supply of mice, instead of drinking Martinis at the bar as usual. Being very methodical, Caleb decided to take $$$N$$$ mice, where the $$$i$$$-th heaviest of these mice weighs exactly $$$i$$$ kilograms.

When entering the witch's cottage to make the delivery, he heard her saying something about "...not giving wings to the snake...". Perhaps because of that, as soon as she received the supply of mice, she enchanted them as follows: "After eating a mouse weighing $$$i$$$ kilograms, it will not be possible to eat mice weighing $$$i-1$$$ or $$$i+1$$$ kilograms.".

Caleb was astonished by this and thought: "What will then be the greatest total amount, in kilograms, that the snake will be able to eat under this restriction?". To his surprise, the snake heard his thoughts and replied (telepathically): "EZ...". Caleb knows that EZ is an abbreviation of easy. But is eating the greatest possible amount really that easy?

Calculate for Caleb the greatest total amount, in kilograms, that the snake will be able to eat, considering the restriction imposed by the witch's spell.

The secret organization UnBalloon has $$$N$$$ agents, numbered from $$$1$$$ to $$$N$$$. Using a secret algorithm, the organization calculated, for each of them, their value as a human being, so they could order the agents by this value (no two agents have the same value). From this, the list $$$L$$$ was created, where $$$L_i$$$ is the number of the $$$i$$$-th most valuable agent.

The organization must form a team of agents for the next mission, which is to infiltrate the Super Ultra Secret Pizza. But for the mission to be successful, the chosen agents must follow a special property. Let $$$S$$$ be the set of numbers of the chosen agents and $$$P$$$ be the set of positions of these agents in the list $$$L$$$. From these sets, we define the polynomials$$$^1$$$ $$$A(x) = \sum_{i \in S} x^i$$$ and $$$B(x) = \sum_{i \in P} x^i$$$. For this team of agents to be successful, it is necessary that $$$S$$$ is not an empty set and that there exists some polynomial $$$C(x)$$$ with all its coefficients being non-negative integers such that $$$A(x) \cdot C(x) = B(x)$$$.

As part of the organization's analysts, you must calculate how many ways there are to form a team of agents that would be successful in the mission. Since this quantity can be very large, calculate the remainder of this quantity when divided by $$$998244353$$$.

$$$^1$$$ A polynomial is a function of the form $$$P(x) = \sum\limits_{i=0}^\infty a_i \cdot x^i$$$ such that the number of non-zero values $$$a_i$$$ is finite. The $$$a_i$$$'s are called coefficients.

During the preparation for the UnBalloon Great Programming Contest, several coaches are testing strategies to assemble the best possible superteam.

The organizers of the event allow the formation of a superteam from a subset of $$$n$$$ available teams. Each team has four types of participants, corresponding to different skill profiles, with their quantities within team $$$i$$$ being represented by four integers $$$(a_i, b_i, c_i, d_i)$$$. To assemble a super team, the organizers can choose any subset of these teams.

After choosing a superteam, the organizers gather all participants from the selected teams and define:

• $$$A$$$ as the total number of participants of type $$$a$$$;
• $$$B$$$ as the total number of participants of type $$$b$$$;
• $$$C$$$ as the total number of participants of type $$$c$$$;
• $$$D$$$ as the total number of participants of type $$$d$$$.

Then, a training session is held with the members of the superteam, with an associated numeric penalty. The training consists of two independent stages:

• In the first stage, participants of types $$$a$$$ and $$$b$$$ in the superteam are paired against each other for a round of confrontations. Each participant faces exactly one opponent whenever possible. At the end, exactly $$$|A - B|$$$ participants remain unmatched, which will contribute to the penalty calculation;
• In the second stage, the same process occurs between participants of types $$$c$$$ and $$$d$$$.

Immediately after these two stages, two parameters $$$(k, l)$$$ are used to calculate the penalty of the training. The values $$$k$$$ and $$$l$$$ represent the weight of each training stage, and the penalty value is given by the sum of the contributions of both stages.

• The contribution of the first stage is the number of participants remaining after the confrontations between types $$$a$$$ and $$$b$$$, multiplied by $$$k$$$.
• The contribution of the second stage is the number of participants remaining after the confrontations between types $$$c$$$ and $$$d$$$, multiplied by $$$l$$$.

The coaches want to test different strategies. For this purpose, they will evaluate $$$q$$$ different pairs of weights $$$(k, l)$$$.

Your task is to help the coaches: for each pair of weights $$$(k, l)$$$, determine the maximum penalty that could be achieved by choosing a subset of the teams.

AnaLu spent the whole day at LINF studying Number Theory, so she decided to put her new knowledge into practice! Because of that, when she got home, she went straight to her room to solve problems. Then, after many ACs, she ended up falling asleep. And she had a dream...

In this dream, AnaLu was once again a 6th-grade student, and the class of the day was about multiplication, exponentiation, and divisibility. The teacher wrote the following definitions on the board:

1. Consider positive integers $$$A$$$ and $$$X$$$.
2. $$$A \cdot X$$$: $$$A$$$ multiplied by $$$X$$$.
3. $$$A ^ X$$$: $$$A$$$ raised to the power $$$X$$$ (which is the same as doing $$$A \cdot A \cdot A \cdot \ldots \cdot A$$$, with $$$X$$$ factors equal to $$$A$$$).
4. $$$A | X$$$: means that $$$A$$$ divides $$$X$$$, that is, there exists some positive integer $$$B$$$ such that $$$A \cdot B = X$$$.

But, not satisfied, the teacher decided to challenge her students. She asked each one to keep in their notebook the value of the number $$$A$$$, which initially is equal to $$$1$$$. The teacher will make $$$Q$$$ queries about this number $$$A$$$, in which a number $$$X$$$ will be written on the board and all students must either update the value of $$$A$$$ accordingly or answer a question, depending on the type of the query. There are three types:

1. All students must update the value of $$$A$$$ to $$$A = A \cdot X$$$ in their notebook.
2. All students must update the value of $$$A$$$ to $$$A = A^X$$$ in their notebook.
3. All students must answer (in English, with "Yes" or "No"): $$$X|A$$$?

AnaLu then realized that she was in a dream, since, depending on the teacher's queries, the number $$$A$$$ could become so large that it would be impossible to write it down even if all the notebooks in the universe were put together. Even so, she realized that it would still be possible to answer the teacher's divisibility queries (type $$$3$$$) correctly with the help of a computer.

But AnaLu did not bring any computer into the dream, so you must help her answer the queries!

Iasmim, Pedro, and Emerson are preparing to present their own encryption method to the International Committee for Poor Communication (ICPC), the leading organization that studies poor communication methods that "work".

They have developed a unique and innovative method for transmitting messages. Since the idea is to create a bad communication method, they send an encrypted sequence of numbers. To decrypt and find the original message, one must find the lexicographically smallest non-empty subsequence of the vector $$$V$$$ such that its hash is strictly less than the hash of its complement. If a subsequence (of size $$$k$$$) consists of the positions $$$p_0, p_1, \ldots , p_{k-1}$$$, its complement is the subsequence composed of all the positions in the vector that are not any of these $$$k$$$ positions.

We say that a sequence $$$A$$$ is lexicographically smaller than a sequence $$$B$$$ if, at the first position where they diverge, the element of $$$A$$$ is smaller than the element of $$$B$$$. If the sequences are identical until the shorter one ends, the sequence of shorter length is considered the lexicographically smaller one.

The hash calculation used by the trio follows a polynomial hash structure. Given a subsequence (or its complement) composed of the numbers $$$x_0, x_1, \ldots , x_{k-1}$$$ in the order in which they appear in the vector $$$V$$$, the hash value $$$H$$$ is calculated using the following formula:

$$$$$$H = (x_0 \cdot P^N + x_1 \cdot P^{N-1} + \ldots + x_{k-1} \cdot P^{N-k+1}) \% M$$$$$$

Where:

• $$$x_i$$$ is the value of the $$$i$$$-th element of the subsequence;
• $$$P = 100019$$$ is the polynomial base;
• $$$N$$$ is the total length of the vector $$$V$$$;
• $$$M = 998244353$$$ is the modulus;
• The index $$$i$$$ (from $$$0$$$ to $$$k-1$$$) represents the position of the number within the chosen subsequence.
• By convention, the hash of an empty sequence ($$$k=0$$$) is defined as $$$0$$$.

You will be given the vector $$$V$$$ and must recover the subsequence that represents the message communicated by Iasmim, Pedro, and Emerson.

Arthur has night classes at UnB every day, so he has to have dinner before going to class. He knows that most people usually have dinner at the RU, and he has nothing against the RU, but he thinks life is too short to miss out on different gastronomic experiences... However, not all of his friends share this point of view, so it is necessary to convince them.

Arthur and his friends have already not eaten at the RU on day $$$1$$$, because "on the first day it is fine". But now his friends are determined to go to the RU in the next days. To prevent this, Arthur had an idea. He will propose the following: "we can go to the RU every day, just not on days that are multiples of $$$X$$$", such that $$$X$$$ is a positive integer larger than $$$1$$$. This seems reasonable to his friends at first, but little do they know that Arthur will choose several values of $$$X$$$ so that they never go to the RU from day $$$1$$$ to day $$$N$$$...

But Arthur must be careful so that his friends do not realize what he is doing! For this, he must say the smallest possible number of values $$$X$$$ — otherwise, it would be too suspicious and he would be dragged to the RU!

Help him, and compute the smallest possible number of values $$$X$$$ that Arthur must tell his friends so that they end up not going to the RU on any of the days from $$$1$$$ to $$$N$$$.

Gus and Caio Fleury are two experienced Pokémon trainers. They are preparing for the next edition of the UnBalloon Pokémon League and, for that, they are running computerized battle simulations.

The simulation software they chose computes the damage of a single attack made by one Pokémon against another. To do this, it allows choosing the type of the attacking Pokémon, $$$T_a$$$, the power of the attack used, $$$P$$$, the type of the defending Pokémon, $$$T_d$$$, and the defending Pokémon's hit points, $$$H$$$. After this attack, the Pokémon's hit points are reduced to $$$max(0, H - P \cdot M(T_a, T_d))$$$, where $$$M$$$ is the type damage modifier function. If the hit points are reduced to $$$0$$$, the Pokémon is knocked out.

Gus and Caio Fleury prefer to use the most classic types: fire $$$(F)$$$, grass $$$(G)$$$, and water $$$(W)$$$. For these specific types, the function $$$M$$$ is defined as follows:

• If $$$(T_a, T_d)$$$ $$$=$$$ $$$(F, G)$$$, $$$(G, W)$$$, or $$$(W, F)$$$, then $$$M(T_a, T_d) = 2$$$.
• Otherwise, $$$M = \dfrac{1}{2}$$$.

Caio Fleury was using the simulator extensively to decide which strategy to use in the next battle. Meanwhile, Gus was thinking about contributing to the simulator with a custom message. Denoting by $$$X$$$ the defending Pokémon's hit points after the attack, he thought of printing "Nocaute!" if $$$X = 0$$$, and "Sobraram $$$X$$$ pontos de vida!" otherwise.

However, Caio Fleury has just challenged Gus to a battle, and now there is no time to implement this message. So now it is up to you to implement it!

Lady Gaga is a complete artist: unmatched in performances, extremely versatile, and full of diverse artistic references. Throughout her career, she has established herself as one of the most essential figures in the history of pop music, and as a voice for many who cannot find their own. To the delight of the Little Monsters, she constantly reinvents herself, always leaving her legion of fans eager for her next steps.

To further improve her songwriting skills, Lady Gaga studied a property of song lyrics called the Echoing Coefficient, which is simply the sum of the values of all Echoing Segments of a lyric. An Echoing Segment is a passage of a lyric that can be represented as the same passage repeated twice, and its value is the product of the number of lines that compose it and the total number of characters in those lines.

As an example, the following excerpt from Bad Romance is an Echoing Segment (because it can be represented as the repetition of the first three lines):

Formally, the lyrics of a song can be represented as a list $$$L$$$ of lines, where the $$$i$$$-th line can be represented as a string $$$L_i$$$. A passage of a lyric is a contiguous sublist of $$$L$$$ — if it is composed of all lines from the $$$i$$$-th to the $$$j$$$-th (with $$$j \geq i$$$), it is denoted by $$$L_i^j$$$. Thus, an Echoing Segment of $$$L$$$ is a passage $$$L_i^j$$$ such that there exists some list of lines $$$V$$$ for which $$$L_i^j = V + V$$$, where $$$+$$$ represents the list concatenation operation. Therefore, the value of an Echoing Segment $$$L_i^j$$$ is given by $$$(j-i+1) \cdot \sum_{k=i}^j |L_k|$$$, where $$$|L_k|$$$ is the length of the string representing the $$$k$$$-th line. Finally, the Echoing Coefficient of a lyric is the sum of the values of all Echoing Segments of that lyric.

In her studies, Lady Gaga wants to analyze song lyrics and their respective Echoing Coefficients. To make this process more convenient, she asked her team for a program that receives a simplified song lyric (without uppercase letters, punctuation, or special characters) and prints the Echoing Coefficient of that lyric.

Help Mother Monster with a program that performs this calculation efficiently!

Henrique wants to park his car in the parking lot of the University of Brasília (UnB).

The parking spots are numbered from $$$1$$$ to $$$n$$$. Spot number $$$i$$$ is characterized by two numbers: its distance $$$d_i$$$ from the main entrance and the probability $$$p_i$$$ that it is free. Henrique visits the spots sequentially, starting from spot $$$1$$$. Upon arriving at spot $$$i$$$, two situations may occur:

1. With probability $$$p_i$$$, spot $$$i$$$ is free. In this case, Henrique has two options: park in spot $$$i$$$ (Henrique is extremely fast, so we may consider that he takes $$$0$$$ seconds to park), or move on to the next spot, which is spot $$$i+1$$$ if $$$i \neq n$$$ and spot $$$1$$$ if $$$i = n$$$.

2. With probability $$$1-p_i$$$, spot $$$i$$$ is occupied. In this case, Henrique is forced to continue to the next spot.

Each time Henrique moves on to the next spot, he spends $$$1$$$ second. After visiting spot $$$i$$$ once, it is possible that in subsequent visits its state will be different, since the UnB parking lot is very busy and a driver may have occupied or vacated the spot during the time Henrique took to return to it. This behaviour will be dictated by the probability $$$p_i$$$, which remains fixed throughout the entire problem.

Henrique wants to act so that the expected value of the sum of the total time spent choosing a spot and the distance of the spot where he finally parks is as small as possible. If Henrique acts optimally, what is this value?

Luisa likes to practice on the UnBalloonforces website, where she solves problems and participates in contests. She follows the philosophy "Not Afraid to Fall", which says that one should participate in every contest, even if there is a risk of falling in title (equivalent to color on Codeforces), because that is the best way to train both skill and mindset. This worked so well that today she has the title of Super Programmer, which is the second highest on UnBalloonforces.

On UnBalloonforces, every problem has an integer rating between $$$1$$$ and $$$M$$$. As a form of training for Luisa, her coach, Ruan, prepared a list of $$$N$$$ problems with various ratings. He also sent a voice message saying: "Look, actually, just do the ones with rating greater than or equal to..." (Luisa could not hear the rating specified by Ruan).

Luisa has already solved all the problems, and now she is bored. Remembering the message, she wondered: "If the rating chosen by Ruan were $$$i$$$, what would be the sum of the ratings of the problems I should solve?" Help satisfy Luisa's curiosity by calculating this sum for every $$$i$$$ from $$$1$$$ to $$$M$$$!