Dr. Cristina Yang is one of the best cardiologists in the world and you are her new student! To get you started, she has given you an easy task. You'll be given an example of how the heartbeat of a healthy heart looks in the form of a string $$$S$$$, and $$$N$$$ electrocardiograms, each one is a string $$$P$$$, your task is to say if it's healthy or not. A healthy electrocardiogram is one which is made by concatenating multiple times the string $$$S$$$.

Osvaldo and his friend Rogelio are looking to buy some paints to add some color to his house. He knows each color he uses to paint his house will add a beauty $$$x$$$ (not necessarily positive) to the house. The store is having a special offer; the paints are placed in a square matrix, and if you buy a set of paints such that you can draw a spiral in the matrix beginning in one of the corners and filling the whole matrix, where the set is contiguous in the spiral, the paint is free! Since Rogelio is in a hurry to start training for ICPC, they have asked you to help them find the best sum of beauty one can add to the house if the paint is free, notice you can decide to buy no paints.

The city of Celaya is installing new street signs, and the mayor has appointed you to supervise the work. You have received a sign containing a string $$$A$$$ made of english uppercase characters, and you suspect it might be incorrect. However, you are clever and have discovered that you can perform the following operation on the sign without damaging it:

1. First, partition the string $$$A$$$ into four contiguous substrings $$$P_1, P_2, P_3, P_4$$$. For example, for the text ABCD, the partitions $$$$$$ \texttt{A},\;\texttt{B},\;\texttt{C},\;\texttt{D} $$$$$$ and $$$$$$ \texttt{AB},\;\texttt{}\,\varepsilon,\;\texttt{CD},\;\texttt{}\,\varepsilon $$$$$$ are valid, while $$$$$$ \texttt{A},\;\texttt{C},\;\texttt{BD},\;\varepsilon $$$$$$ is not. We denote the empty string as $$$\varepsilon$$$.
2. Then, create the string $$$$$$ A' = P_1\,P_3\,P_2\,P_4 $$$$$$ by concatenation, and replace $$$A$$$ with $$$A'$$$.

Unfortunately, there is not much time left before the deadline, so you may apply the operation at most once on the sign.

Given the current string on the sign and the correct one, determine whether it is possible to fix the sign or not.

Iván has just embarked in his newest entrepreneurship: a charbroiled burgers stand. The unique seasoning that he uses has attracted a lot of customers, so he's figuring out new ways to expand his business.

Since he has really loyal customers he knows that each day he will receive $$$N$$$ burger orders, always being requested in the same order (sequence) as in previous days. Every order asks for certain quantities of each of the $$$K$$$ ingredients that are available in the stand. Iván can only fulfill an order if, for each ingredient, he has an available amount greater than or equal to the amount that is being requested.

To minimize costs Iván wants to start buying items in bulk, for this he will start having a large inventory for each of the $$$K$$$ ingredients. As he has bought his first batch in bulk, he would like to know how much time will they last.

Help Iván find out when will he run out of his current inventory and won't be able to fulfill another one. Hurry up, a hoard of hungry customers is waiting!

In the quaint village of BoxTown, Elisa, the clever organizer, has been tasked with arranging a shipment of magical artifacts. There are $$$N$$$ enchanted boxes, each with its own capacity. Elisa's goal is to fit $$$M$$$ artifacts into one of these boxes, ensuring the safety and organization of the village's treasures. Each box $$$i$$$ can hold up to $$$a_i$$$ artifacts. Elisa needs to find a box that can accommodate all $$$M$$$ artifacts. If multiple boxes can fit the artifacts, Elisa prefers the box with the smallest index to keep things tidy.

Germán is new to writing programming problems. To get started, he decided to create a simple one (this is the very first problem he has written).

You are given a list of numbers $$$B$$$ of length $$$N$$$, and $$$K$$$ operations that can be of any of the following three types:

• Q l r — Query the maximum number in the range $$$[l, r]$$$ of the list $$$B$$$.
• A l r — Add one to every number in the range $$$[l, r]$$$ of the list $$$B$$$.
• R l r — In the range $$$[l, r]$$$ of the list $$$B$$$, reset to 0 every number that is equal to the global maximum value of the entire list $$$B$$$ (not just the maximum in [$$$l, r$$$]).

Your task is to process all the given operations.

Geosé is preparing a problem for the upcoming ICPC Grand Prix of Solidland competition. He is busy writing the model solution and needs your help generating the tests.

The test should consist of a simple polygon with $$$n$$$ vertices of integer coordinates and area equal to $$$A$$$. Recall that a polygon is simple if it has no holes and its boundary does not intersect itself. Additionally, the polygon should not contain any internal angle equal to $$$180^{\circ}$$$.

Build a polygon that satisfies the required constraints, or determine that it does not exist.

Tony works in Huron Designs, a website that receives requests for advertising design projects. Right now, Tony has $$$n$$$ open requests, where the deadline of the $$$i$$$-th request is $$$d_i$$$ seconds from now, the base profit of it is $$$p_i$$$, and the time to complete it is $$$c_i$$$ after Tony starts working on it. Tony can work on at most one request at the same time.

A feature of Huron Designs is that the clients can give an optional bonus to the designers to recognize their work. You, as the assistant of Tony, have analyzed the previous transactions of the clients, and you have estimated that the client of the $$$i$$$-th request would pay $$$x_i$$$ of bonus if Tony completes the $$$i$$$-th request on or before $$$y_i$$$ seconds from now. You don't know the exact value of $$$x_i$$$ and $$$y_i$$$, but you know that $$$x_i$$$ is a real number chosen uniformly at random from the range $$$[lx_i,rx_i]$$$ and $$$y_i$$$ is a real number chosen uniformly at random from the range $$$[ly_i,ry_i]$$$.

Your task is to find a subset of the requests that Tony should accept and the order in which the chosen requests should be completed to maximize the expected value of Tony's profit. Each one of the chosen requests should be completed on or before its respective deadline.

German had always dreamed of joining the legendary tech company known as Infinite Compilation, Perpetual Confusion (ICPC). It was a company surrounded by mystery and challenge, where logic was king and only the brightest minds could find their place.

One day, German discovered something unusual about how the company worked. Every employee reported to exactly one other person, except for the CEO, who stood at the very top and had employee ID 1. From the CEO down, each person could have multiple people working under them, forming a giant organizational chart that branched out in every direction.

To join the company, German didn't need to submit a resume or pass a technical test. Instead, there was a unique challenge: he had to answer a series of questions about how the employees were organized and what they knew.

Each employee at ICPC was an expert in one specific topic. The questions German would face went something like this: "For a given employee x, how many people under their supervision—including themselves—know a specific topic k?"

His friend Sebastian, who had once tried to join ICPC, remembered these questions clearly. Before he was caught snooping through the company's systems, he managed to get a copy of the entire employee structure—who reports to whom—and the exact list of questions German would be asked.

Unfortunately, Sebastian was discovered before he could find and share the answers.

Now it's up to you to help German. With the structure and questions in hand, he just needs the correct answers so he can memorize them before his interview.

Will you help him prepare and finally enter the world of Infinite Compilation, Perpetual Confusion?

In the mystical realm of Spellbound, a powerful wizard named JuPael has discovered a magical string that holds the key to creating powerful incantations. This string is composed of characters from the english alphabet. The wizards aim to find the largest segment of this string that can be rearranged to form a palindrome, a word that reads the same forwards and backwards.

Your task is to assist the wizards by determining the length of the longest contiguous segment of the string that can be rearranged into a palindrome.

Bausffs, known as the Killable Demon, was a fearless tactician who thrived on taking risks. He had a unique playstyle: he deliberately placed himself in difficult positions where every move could result in either great reward or crushing loss. His goal was simple — always come out with more gold than his opponent, no matter the odds.

But even Bausffs had limits.

That's where we come in. We are the Unkillable Demon eternal, analytical, and all-seeing. We know every decision that could be made in the game. We know their outcomes, the relation between them, and the true value they offer.

Each decision $$$i$$$ is characterized by an integer:

$$$$$$ D_i = (\text{Amount of Gold that Bausffs gains}) - (\text{Amount of Gold that Bausffs' enemy gains}) $$$$$$

Some decisions depend on others. That is, there exist some pair $$$(A, B)$$$ such that Bausffs cannot make decision $$$A$$$ unless he has already made decision $$$B$$$. Decisions can only be made once and, if necessary, several decisions can be made simultaneously.

Bausffs, eager to win and outplay his enemy, comes to us for help.

"Tell me," he says, "what is the maximum gold advantage I can gain if I choose my decisions wisely?"

And we, the Unkillable Demon, must answer.

La Vaca Saturno Saturnita and Tung Tung Tung Sahur will have a battle in the Base-$$$b$$$ Game.

The Base-$$$b$$$ Game is played with a collection of piles of stones and an integer $$$b$$$ chosen before the game starts. The two players of the game take turns. On each turn, a player selects a pile of stones and adds a positive number of stones such that the following two conditions are satisfied:

1. Let $$$a$$$ be the current size of the pile and $$$x$$$ the stones added. The number of digits of $$$x$$$ in base $$$b$$$ doesn't exceed the number of digits of $$$a$$$ in base $$$b$$$. For example, $$$11$$$ has $$$2$$$ digits in base $$$10$$$, $$$9$$$ has $$$4$$$ digits in base $$$2$$$, and $$$0$$$ has $$$1$$$ digit in any base.
2. The sum $$$a+x$$$ doesn't produce any carry when the sum is performed with the basic addition method in base $$$b$$$.

For example, if $$$b=10$$$, a player can't add $$$28$$$ stones to a pile of size $$$57$$$ since the sum $$$57+28$$$ produces a carry from the units to the tens when performing the sum in base $$$10$$$, as shown in the image below. On the other hand, if $$$b=100$$$, a player can add $$$28$$$ stones to a pile of size $$$57$$$.

The player who can't make a move loses the game. If the game continues for more than $$$2025!^{2025!}$$$ turns, it is declared a tie.

La Vaca Saturno Saturnita will take the first turn. Tung Tung Tung Sahur considered that this was unfair, so he was allowed to choose the sizes of the piles. Sahur can choose any subset (possibly empty) of $$$\{l, l+1, l+2, \dots, r\}$$$ as the sizes of the piles. Note that Sahur can't take multiple piles of the same size.

Tung Tung Tung Sahur is not good at strategy games, so he asks for your help to count the number of ways to choose the sizes of the piles such that he (the second player) has a winning strategy if both of them play optimally. Since the answer can be huge, find it modulo $$$998244353$$$. The order of sizes does not matter, only the chosen subset.