After the unforgettable episode with the El Café coffee shop, Max and his brother Min decided to take a well-deserved vacation — this time, away from coffee and closer to the big screen. Their love for cinema, especially the films of Martin Scorsese, led them to create a new tradition: continuous Scorsese marathons.

During their month of rest, the brothers organized $$$N$$$ of the director's films in chronological order, numbering them from $$$1$$$ to $$$N$$$. Each film received a score from film critics; the score of the $$$i$$$-th film is $$$a_i$$$.

Being as competitive and creative as always, Max and Min decided to evaluate the quality of each "continuous marathon" in a curious way:

• Max, unsurprisingly, cares about the maximum.
• Min, of course, is interested in the minimum.
• For them, the quality of a marathon is defined as the product of the maximum and the minimum values in the sequence of scores of the films watched in that marathon.

A continuous marathon is any contiguous subsequence of the original list of films — it can be a single film or all $$$N$$$ films.

Naturally, Max and Min became curious: what is the total sum of the qualities of all possible continuous marathons?

Since this value can be very large, they decided to only care about the result modulo $$$10^9 + 7$$$.

At the School of Magic and Witchcraft of Brutewarts, there is a library containing millennia-old magical knowledge. In the library, there are several bookshelves, each dedicated to a different book category. The librarian, Karina McGonagall, is very meticulous about the indexing of books on the shelves, and her favorite category is the one about the Three Little Pigs.

In a given category, she likes to keep the books sorted by their titles in lexicographic order—that is, the same order as they would appear in a dictionary. For instance, the word "abacate" comes before "abacaxi" in the dictionary, since when we look at the first position where they differ, the letter "t" comes before the letter "x" in the alphabet.

After a lot of effort, Karina finally finished organizing her most ambitious bookshelf: the shelf of all finite strings containing letters from "a" to "z". Although there are some books with repeated titles, books titled with every imaginable finite string are already there, perfectly sorted lexicographically.

On this shelf, she noticed that magic students almost always read one of the first books, located near the beginning, and it was rare for anyone to want to reach the end.

Karina's favorite book title is $$$S$$$, and she would like to reposition it in a place where it will be more frequently read. Since she cannot change the ordering, she only wants to slightly modify the title so that, when reinserted in its correct position, it will be as close to the beginning as possible. To avoid harming comprehension, she will make the following change at most once:

• Choose two positions $$$i, j$$$ $$$(1 \leq i, j \leq N)$$$ and swap the characters $$$S_i$$$ and $$$S_j$$$, that is, $$$S_i$$$ goes to position $$$j$$$ and vice versa.

As she is already very tired after grading Transfiguration exams, the poor librarian asks for your help.

Given the title of the book, what should its new title be in order to meet Karina's request?

Queliton Tarantino is a legendary figure in the world of cinema; his films are known for their sharp dialogue, spectacular plot twists, and above all, for using every possible cliché — always with that ironic touch.

Recently, Queliton has been working on the script for his new masterpiece: a film encoded as a word $$$S$$$, composed only of lowercase letters. Like any impactful screenwriter, he wants to make sure his film is full of classic cinematic clichés — each represented by a word.

But there's a twist: Queliton wants to make one bold move — reversing, at most once, a continuous segment of the film. He knows this trick can turn an ordinary scene into an iconic moment, creating new occurrences of the clichés and, who knows, securing his tenth Palme d'Or.

Your task is to help him determine the maximum number of cliché occurrences he can insert into the film after reversing, at most once, any continuous segment of the script.

Each occurrence counts, even if the same cliché appears multiple times, including overlapping with other occurrences or with itself.

Lucas Thomas Anderson used to work in an office and lived a normal life, except for the fact that he was a hacker in his spare time and discovered he is trapped inside an $$$N \times M$$$ matrix! He is currently at cell $$$(1,1)$$$ and, to escape the matrix, he needs to reach Morpheus, who is located at cell $$$(N,M)$$$.

However, Agent Gui also wants to find Morpheus to thwart Thomas's plans before he escapes the matrix. To do this, Gui alters reality, creating a challenge centered around the bitwise OR operation, because Gui knows that although Thomas is an experienced hacker, he is more familiar with other operations.

In this reality altered by Agent Gui, the time anyone takes to walk through a path in the matrix is the bitwise OR of the values in the cells traversed. Also, since Gui is an AI-powered program, he can easily traverse the matrix and find the fastest route to wherever he wants to go.

Now, Agent Gui is at cell $$$(X,Y)$$$ and wants to reach Morpheus before Thomas. Gui is not in the same position as Thomas or Morpheus. Both Gui and Thomas can move from one cell to another if the two share an edge (i.e., up, down, left, or right).

The fate of humanity is in your hands! Given Agent Gui's position and the value of each cell, write a program that tells Thomas the minimum time he can take to reach Morpheus and also the time it would take Gui.

Leo Turing is a scientist with incredible discoveries, one of the most renowned in Computer Science; his most influential work is his study on encryption in search engines.

At this very moment, he is trying to break the encryption code to uncover the enemy's search history during the Second World Hackathon and has encountered a new challenge.

Turing wants to find two unknown values $$$A$$$ and $$$B$$$, which are crucial for decoding the enemy's searches. However, the only known values are $$$X$$$ and $$$Y$$$, which represent the following:

• $$$X = A + B$$$
• $$$Y = |A - B|$$$

To find these values, he asked for your help. Given $$$X$$$ and $$$Y$$$, print two values $$$A$$$ and $$$B$$$ that satisfy the conditions above. Turing guarantees that $$$A$$$ and $$$B$$$ exist and are uniquely determined for the inputs he will provide to your program.

Frodo and Sam, the great hobbits of Middle-earth, are on an adventure to destroy the One Ring. Their journey takes them to the treacherous Mines of Moria, where a Balrog — one of Morgoth's most feared creatures — dwells.

As they descend into the depths of Moria, something extraordinary happens — this is where the plot twists! The Balrog awakens and casts a powerful spell on Frodo and Sam, transporting them to another plane of reality.

Frodo and Sam are taken to the top of a mountain, where there are two paths made of magical rocks. Frodo stands to the left of these paths, and Sam to the right. The paths can be represented by two permutations $$$P$$$ and $$$Q$$$ of length $$$N$$$, where the type of the $$$i$$$-th rock from left to right is $$$P_i$$$ on the first path and $$$Q_i$$$ on the second.

To escape this illusory world and continue their journey to Mordor, Frodo and Sam must destroy some of these rocks so that the two permutations $$$P$$$ and $$$Q$$$ of rock types become identical, but they cannot destroy all the rocks on both paths.

Frodo and Sam begin destroying the rocks simultaneously. For each of the two paths, Frodo may destroy as many rocks as he wants starting from the left side of both paths, and Sam can do the same starting from the right. More formally, Frodo will choose two integers $$$(a, b)$$$ and destroy the rocks $$$P_1, P_2, \cdots, P_a$$$ and $$$Q_1, Q_2, \cdots, Q_b$$$, while Sam will choose two integers $$$(c, d)$$$ and destroy the rocks $$$P_N, P_{N-1}, \cdots, P_c$$$ and $$$Q_N, Q_{N-1}, \cdots, Q_d$$$. Note that Frodo and/or Sam may choose not to destroy any rocks.

Given that Frodo takes $$$F$$$ time to destroy a rock, Sam takes $$$S$$$ time to destroy a rock, and the time to move between any two rocks is zero, what is the minimum time they need to spend destroying rocks to escape the Balrog's magical realm?

Joãozão and Eric, two renowned screenwriters, are working together on the movie Godfather. When they reached the stage of creating the climax of the story, they realized they needed a truly insane scene to surprise the audience.

Joãozão wants to make the scene as crazy as possible, trying to maximize the madness level of the story. On the other hand, Eric wants to maintain balance and prevent exaggeration, trying to minimize this level. Thus, the film's director — Bras — decided to use their differing ideas to reach a point of creative balance.

The creative process takes place over $$$N$$$ days. Bras uses a binary string $$$S$$$ to assist him. On the $$$i$$$-th day, Bras chooses who between Joãozão and Eric will make the change to the plot according to this string:

• If $$$S_i = 1$$$, Joãozão makes the change.
• If $$$S_i = 0$$$, Eric makes the change.

To start the process, Bras chose two plot twists: a main plot with madness level $$$A$$$, and an auxiliary plot with madness level $$$B$$$.

Whoever is chosen to make the change on day $$$i$$$ will begin the day with two values $$$X$$$ and $$$Y$$$, the current madness levels of the main and auxiliary plots, respectively. Then, this person creates a new main plot with value $$$X + Y$$$, and selects one of $$$X$$$ or $$$Y$$$ to continue as the auxiliary plot's value. Note that there is always exactly one main plot and one auxiliary plot.

Bras is still unsure how to choose who changes the plot on each day, so he wants to simulate possible scenarios. Given the initial $$$S$$$, he will perform $$$Q$$$ operations, each of which inverts the choices on the days in an interval $$$[L, R]$$$. That is, for all $$$i$$$ such that $$$L \le i \le R$$$, the value of $$$S_i$$$ is flipped: if it was $$$0$$$, it becomes $$$1$$$; if it was $$$1$$$, it becomes $$$0$$$.

Your task is to perform this simulation; after each of the $$$Q$$$ changes, determine what the final madness level of the main plot will be, knowing that Joãozão wants to maximize the final madness and Eric wants to minimize it. Since the madness level can be very large, Bras will be satisfied knowing just the result modulo $$$998244353$$$.

BRUTE, a group originally known for their performance in competitive programming contests, decided to change direction and venture into the world of cinema. Risa, a renowned director from the group, was tasked with selecting some actors from $$$N$$$ candidates for the first film produced by BRUTE.

To do this, Risa contacted all the actors and collected their conditions for participating in the project. Each actor, in addition to demanding a monetary value, indicated names of other more famous actors they would like to work with, requiring that these also be included in the cast. Each actor is identified by a number, where the $$$i$$$-th least famous actor is represented by the number $$$i$$$, meaning that the most famous actor is represented by the number $$$N$$$, the next most famous by $$$N - 1$$$, and so on.

After organizing all the requirements, Risa noticed two things:

• Each actor appears in at most one other actor's requirement.
• There is exactly one actor who is not required by any other, and this actor is the least famous among all.

Knowing that the $$$i$$$-th actor generates a profit of $$$a_i$$$ if hired (negative values represent a loss), what is the maximum possible profit that BRUTE can obtain if Risa optimally chooses which actors to hire? Note that Risa may choose to hire no actors at all.

Rondônia Jones is an archaeologist and explorer known for his extensive knowledge of ancient civilizations and their languages.

During one of his expeditions, he discovered a stone from the Brutense people (dated $$$998244353$$$ B.C.) containing a short introductory text followed by $$$N$$$ mysterious inscriptions: all of them were words made up of Latin alphabet letters (from "a" to "z"). The text explained, in a long-forgotten language, that all these words were non-decreasing. This led Jones to expect that they would look like "abcdef" or "aacgmz" — non-decreasing words, assuming the standard Latin alphabetical order. However, contrary to expectations, the letters appeared to follow a strange order unfamiliar to him.

Now, Jones wants to know whether there exists some ordering of the Latin alphabet letters that makes the inscribed words obey the rule stated in the text. If so, he asks you to print one such possible order of the alphabet, as it would be crucial for his studies of the Brutense people.

John Wick Fröhlich has finally managed to escape the mysterious labyrinth, but as he moved away, he realized he had dropped his navigation compass — a vital item — exactly in the central corridor, a narrow passage that is slowly closing. Now, he needs to be away for exactly $$$K$$$ seconds to retrieve the artifact and return before the passage becomes impassable.

The corridor is bounded by two walls, represented by the character "#". Between them, there are indestructible stones (character "o") and empty spaces (character "."), which were already part of the labyrinth.

Each second, the left wall advances one position to the right, immediately pushing any stone (o) that is in the space ahead.

Pushed stones can, in turn, push other stones in a chain reaction, but they are never destroyed or overlapped. The walls are also indestructible and cannot be overlapped.

Before setting out, John Fröhlich wants to know what the configuration of the corridor will look like after exactly $$$K$$$ seconds of wall movement, to ensure he can return safely.

When the Bride asked Hanzo, the greatest and finest katana forger the world has ever seen, to craft a new weapon, the master was hesitant, as it had been decades since his last creation and the process was rather complicated.

Nevertheless, sympathizing with the Bride's story and mission, Hanzo decided to call you — the smartest person he knows — and explain step-by-step his forging method:

• Hanzo initially builds the katana by attaching a Japanese steel blade to a hilt and sharpens the blade in the conventional way;
• After that, the master divides the blade into $$$N$$$ parts and assigns a value to each part based on its sharpness level;
• Now, Hanzo aims to minimize the number of distinct sharpness values on the blade by choosing two distinct parts of the blade that have the same sharpness level and modifying all parts between them to also have that same level.

More formally, let $$$a_i$$$ be the sharpness value of the $$$i$$$-th part of Hanzo's blade. The operation is defined as follows:

1. Choose two indices $$$i$$$ and $$$j$$$ $$$(1 \le i \lt j \le N)$$$ such that $$$a_i = a_j$$$;
2. For every $$$k$$$ $$$(i \lt k \le j)$$$, assign $$$a_k := a_i$$$.

Hanzo stated that the sharpness of the blade is the most important part of forging a great katana. However, it is also by far the most difficult step, and he feels he's not always making the most of the blade. Therefore, help him minimize the number of distinct sharpness values by developing a program that receives the initial sharpness levels of the blade and performs Hanzo's operation any number of times.

Dudu is on a magical journey inside the Fantastic Chocolate Factory and discovered a secret room full of machines that produce extremely rare candies called "Tortuguitas". This room contains $$$N$$$ machines numbered from $$$1$$$ to $$$N$$$, and each machine produces exactly $$$K$$$ Tortuguitas, numbered from $$$1$$$ to $$$K$$$.

A machine is represented by the rarity of the Tortuguitas it produces. More formally, the $$$i$$$-th machine produces $$$K$$$ Tortuguitas with rarities $$$r_{i, 1}, r_{i, 2}, \cdots, r_{i, K}$$$. Let $$$X$$$ be the rarity value of the simplest Tortuguita, and the rarity of a Tortuguita can be calculated as follows.

• $$$ \large r_{i, j} = j \cdot X$$$ for all $$$(1 \le j \le K)$$$, when $$$i = 1$$$.
• $$$ \large r_{i, j} = \displaystyle \sum_{t = 1}^{j} r_{i - 1, t}$$$, when $$$i \gt 1$$$.

Dudu was amazed by these magical machines and asked for your help to answer some questions about them.

He will give you $$$Q$$$ questions of the following type: In the $$$i$$$-th machine, what is the sum of the rarities of the Tortuguitas numbered greater than or equal to $$$L$$$ and less than or equal to $$$R$$$?

More formally, Dudu will ask for the result of $$$\displaystyle \sum_{j = L}^{R} r_{i, j}$$$.

Since this result can be absurdly large, he only wants you to return the remainder of this sum when divided by $$$998244353$$$.

The year is $$$62442$$$ and Machado and Marcel were playing their favorite game, Movieguessr.

Movieguessr is a famous game that teleports its players into the universe of a movie, where they have a limited time to figure out which work they are in.

When Machado and Marcel thought it was just another round of the game, the unbelievable happened — the Movieguessr servers crashed, and they became trapped inside one of the most iconic schools from ancient movies, Hogwarts.

The two were on the famous magical staircase of Hogwarts, but in different positions on it, more specifically:

• The staircase is represented by $$$N$$$ steps numbered from $$$1$$$ to $$$N$$$ and a list $$$a$$$ to represent them. The first step is at ground level $$$(a_1 = 0)$$$, and the rest can be above $$$(a_i = 1)$$$ or below $$$(a_i = -1)$$$ the previous step: going up a step increases a person's height by one unit; going down decreases it by one unit.
• Marcel is on the $$$K$$$-th step.
• Machado found a magic wand that allows him to teleport to any empty step on the staircase — that is, any step except the one Marcel is occupying.

Machado wants to use this magic to find his friend. Knowing that Machado can only see Marcel on the staircase if and only if his height is greater than or equal to Marcel's, and considering that Machado is $$$A$$$ units tall and Marcel is $$$B$$$, your mission is to help Machado: is there a step where Machado will be able to see Marcel? If so, to which step should he teleport in order to finally locate Marcel?

On a regular day walking through the forest, Luiza encounters a curious group of people: the Knights who say "Ni".

Luiza was stunned by how many times they said the word "Ni", but she noticed that they said "Ni" exactly $$$K$$$ times.

Write a program that prints exactly what they said.

Upon arriving on Mars, astronaut Mark Watney and his team discovered that the planet was not quite as they had expected. Its terrain was filled with large ravines—gaps in the ground—that made it very difficult for the team to traverse the red planet.

Fortunately, the astronauts brought along a set of ladders of various lengths; these ladders allowed them to cross the ravines when laid out horizontally, as long as their extended length was greater than or equal to the size of the gap.

The team has a schedule indicating one coordinate of interest to visit each day, and for these visits, they choose one ladder from their set to help cross the ravines. After reaching the point of interest, the astronauts must return via the same path they came from (back to the area where they reside), and the used ladder is then discarded due to wear and tear, making it unavailable for future days.

Given this, Mark was tasked with developing a program that, when provided with a map showing regions separated by ravines, the lengths of the ravines, the set of ladders brought by the team, and the cities the team wants to visit each day, maximizes the number of regions of interest visited during the entire mission. Mark, being a great biologist but not much of a programmer, called you for help.

The map of Mars is given as a graph with $$$N$$$ regions numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ ravines numbered from $$$1$$$ to $$$M$$$ connecting these regions, where the $$$i$$$-th ravine has a length of $$$w_i$$$ meters. It is also a fact that if it were possible to use a ladder of infinite length, one could travel from any region to any other region using only the ravines.

Additionally, the mission will last $$$D$$$ days, where the region to be visited on the $$$i$$$-th day is $$$d_i$$$, and the team has exactly $$$D$$$ ladders numbered from $$$1$$$ to $$$D$$$, where the length of the $$$i$$$-th ladder is $$$e_i$$$. Note that a ladder can be used on any day, but only once; and during a day, the chosen ladder can be reused as many times as necessary.

Knowing that the team resides in region $$$1$$$, write a program to help Mark's team with their mission!