Margot Finch goes out to eat. A lot. Like, way too much. Birthdays, Fridays, random Wednesdays — she always finds a reason. And every time, the same thing happens: everyone at the table does their own math, puts their money in the middle, and walks out like everything is fine.

It is never fine.

The waiter always catches her at the door. Every. Single. Time. "Hey, we're still a little short." And because Margot cannot handle the embarrassment, she pays the difference. But here's the thing — paying the difference also makes her anxious. Now she's the one who paid more than everyone else, and that's awkward too. She replays the moment in her head the whole ride home.

And then one night she got home and realized the group had left the waiter zero tip. Zero pesos. The guy had been running back and forth all night. She thought about it for four days straight.

Look — Margot knows tips are not mandatory. She knows waiters should just earn a decent salary. She agrees! But her anxiety does not care about labor policy. If she doesn't leave at least 10%, she will think about it for the next three days.

So now she wants a program. Something she can check before anyone stands up from the table. Something that tells her: are we good, or is this about to be a whole thing?

Tomorrow is the Gran Premio de Mexico 2026 Primera Fecha, and you are in a hurry to finish setting all the problems for tomorrow's contest. Since two heads are better than one, you asked your friend Jimbo to help you out with the statements of the problems. However, this quote didn't end up being true — Jimbo wrote the statements but without respecting some writing style rules!

For an easier read, you want to ensure that the following rules are held:

• If an integer value is a power of $$$10$$$ with $$$k \geq 4$$$ zeros, you write them as a power of $$$10$$$ instead of its whole representation.

  For example, if Jimbo wrote $$$1000000000$$$, then you must transform it to $$$10^{9}$$$ in LaTeX, so the final text would be 10^{9}.

• If an integer value ends with $$$k \geq 4$$$ zeros, you write them in an special scientific notation: You write a truncated real equivalent of the value with only 1 digit in the integral part and then multiply this real by the corresponding power of ten.

  For example, if Jimbo wrote $$$123400000$$$, then you must transform it to $$$1.234 \cdot 10^{8}$$$ in LaTeX, so the final text would be 1.234\cdot10^{8}

• These rules only apply to integers that are not subscripts or superscripts or affected by any of them. Any other value is kept as it is.

Since you are very tired from setting up the solutions, validators and testcases, you will automatize this process by writing a program that applies these rules on the statements.

You are given a connected, undirected, simple cactus graph. A cactus graph is a connected graph in which every edge belongs to at most one simple cycle. Equivalently, any two simple cycles have at most one common vertex.

Each edge has an integer weight, and weights may be negative.

Then you have to answer $$$q$$$ queries. In each query, two vertices $$$u$$$ and $$$v$$$ are given, and you must find the minimum possible total weight of a simple path from $$$u$$$ to $$$v$$$.

Pick a door.

The door you choose will determine your fate for the next $$$N$$$ hours.

4, 3, 2, 1...

Door 1, "the ferret burrow".

You find yourself inside a vast underground labyrinth: tunnels branching in every direction, narrow passages, hidden chambers, and faint scratching sounds echoing through the walls. The air is warm, dense, and carries a faint earthy smell. In your hand, you carry a lamp.

You are not alone. This is a burrow inhabited by ferrets.

Some ferrets are harmless, timid creatures that scatter at the slightest noise. Others are not. There are also light-sensitive ferrets: if they spot you wandering through the dark tunnels, they will rush toward you unless you scare them away with your lamp. But the most dangerous of all is the giant ferret: silent, fast, and impossible to escape if you encounter it outside your hiding place.

Your lamp requires exactly two batteries to work, and both are consumed when it is used.

You carry a small bag that can hold at most $$$K$$$ batteries. Initially, you have $$$S$$$ batteries.

Every hour, you must choose exactly one action:

• Hide. You stay still in a safe chamber. No ferret can attack you while you are hiding.
• Search for a battery. You explore the tunnels, hoping to find a usable battery. During the $$$i$$$-th hour, you find exactly one battery with probability $$$b_i$$$.
• Search for food. You look for something edible. During the $$$i$$$-th hour, you find food with probability $$$c_i$$$. However, not all food is safe: if you find food, you die from poisoning with probability $$$v_i$$$. If you eat and survive, your hunger is reset.

Being outside your hiding place exposes you to the ferrets.

During the $$$i$$$-th hour, a light-sensitive ferret appears with probability $$$q_i$$$. If that happens while you are searching for a battery or food, you must use your lamp to survive. If you have fewer than two batteries before that hour, the ferret captures you, and you die. If you use your lamp, exactly two batteries are consumed.

The giant ferret appears during the $$$i$$$-th hour with probability $$$p$$$. Unfortunately, you do not know the exact value of $$$p$$$, but you know that it was chosen uniformly at random from $$$[0,1]$$$ before you entered the ferret burrow, and that it remains fixed for all $$$N$$$ hours. If it appears while you are searching for a battery or food, you are captured with certainty.

At the beginning of each hour, you must choose your action before knowing whether a light-sensitive ferret or the giant ferret will appear during that hour. If you choose to hide, you will still know whether the giant ferret appeared during that hour, although it cannot attack you.

Staying in these tunnels is exhausting. You must successfully eat at least once every $$$H$$$ hours. Otherwise, you die from exhaustion.

If you manage to survive for $$$N$$$ hours, you can escape.

You chose door 1. What is the maximum probability of survival if you act optimally?

Erasmus Valthorn is the Chief Archivist of the Celestial Library of Numeris — a vast hall where every integer from 1 to N exists as a physical tome, its spine engraved with the number it represents.

After decades of cataloguing by mere numeric order, Erasmus has grown restless. He believes that numbers have a true identity — not their face value, but their prime essence: the sorted sequence of prime factors that compose them.

He calls this the Canonical Form of a number. For example:

$$$48 = 2 \times 2 \times 2 \times 2 \times 3 \quad \Rightarrow \quad [ 2, 2, 2, 2, 3 ] $$$

$$$9 = 3 \times 3 \quad \Rightarrow \quad [ 3, 3 ] $$$

Erasmus now wishes to rearrange all tomes according to their Canonical Form, sorted lexicographically. Under this order, the tome of 48 precedes the tome of 9, since the first element of its sequence — 2 — is less than 3.

The number 1, having no prime factors, is represented by the empty sequence [ ], which is lexicographically smallest of all, and thus occupies the very first shelf.

However, Erasmus is old and forgetful. He keeps losing track of where specific tomes end up in the new arrangement. He has written down Q questions — each asking: "In this new order, which number sits at position K?"

Help Erasmus answer his queries before the next lunar eclipse!

You are given an array $$$[a_1,a_2,\dots,a_n]$$$ of length $$$n$$$ and an integer $$$k$$$.

In one operation, you can choose any integer $$$y$$$ and a range $$$[l,r]$$$, such that $$$1 \leq l \leq r \leq n$$$ and $$$r-l+1 \leq k$$$, and assign $$$a_i:=y$$$ for all $$$i \in [l,r]$$$.

Let's define $$$F(x,l,r)$$$ as the minimum number of operations to make $$$a_i\leq x$$$ for all $$$i \in [l,r]$$$. Find the following sum:

$$$$$$ \sum_{x=1}^n \sum_{l=1}^n \sum_{r=l}^n F(x,l,r) $$$$$$

As the answer can be very large, print it modulo $$$998244353$$$.

Deep in the marshes of Vvardenfell, there is a mudcrab. Not just any mudcrab — the mudcrab. The one with 10,000 gold and nothing to sell. Travelers come from across Morrowind just to stare at him.

His name, as far as anyone can tell, is Gerald.

Gerald has recently decided to expand his business. He has acquired exactly N soul gems, each engraved with a number by some bored Telvanni wizard. A complete collection means having exactly one gem for each number from 1 to N no duplicates, no missing numbers. The order on the shelf doesn't matter. Gerald just wants one of each.

The problem is the wizard was drunk. Some numbers were engraved twice. Some were skipped entirely. Gerald now has N soul gems, but the numbers are a mess.

Gerald can trade with a merchant in Balmora giving one of his gems for any other gem. But every trip through the swamp is exhausting, and Gerald, despite being a successful business-crab, would rather minimize travel.

Help Gerald figure out the minimum number of trades needed so that his collection contains exactly one gem of each number from 1 to N.

Deep beneath the Citadel of Eternal Letters lies the Whispering Archives — a vault sealed for millennia, whose enchanted doors open only to those who can recite two simultaneous palindromic incantations.

The vault's guardian, Valdris the Scribe, inscribed its secrets across two sacred scrolls: $$$A$$$ and $$$B$$$. To unseal the vault, a supplicant must pick a split point $$$i$$$ and a meeting index $$$j$$$, then chant both of the following at once:

$$$P_1 = A[1\ldots i] + B[j\ldots |B|]$$$

$$$P_2 = B[1\ldots i] + A[j\ldots |A|]$$$

Both $$$P_1$$$ and $$$P_2$$$ must be palindromes simultaneously. Centuries of failed attempts have filled the antechamber with very flat scholars. Help the next adventurer survive by counting every valid pair $$$(i, j)$$$ such that $$$1 \leq i,j \leq |A|$$$.

You are given a sequence of positive integers $$$a_1, a_2, \dots, a_n$$$ and a string $$$s$$$ of length $$$n - 1$$$.

For each $$$i$$$ from $$$1$$$ to $$$n - 1$$$:

• if $$$s_i \text{ is equal to } \lt $$$, then $$$b_i \lt b_{i + 1}$$$;
• if $$$s_i \text{ is equal to } =$$$, then $$$b_i = b_{i + 1}$$$;
• if $$$s_i \text{ is equal to } \gt $$$, then $$$b_i \gt b_{i + 1}$$$.

Your task is to choose a sequence of positive integers $$$b_1, b_2, \dots, b_n$$$ satisfying all these relations.

Among all valid sequences, minimize

$$$$$$a_1 b_1 + a_2 b_2 + \dots + a_n b_n.$$$$$$

For the given constraints, it can be proved that the optimal sequence is unique.

Seraphina Coldwater is the most celebrated pastry chef of the Arcane Confectionery Guild. Her legendary cakes are not merely delicious — they are magical. Each cake requires exactly three ingredients, chosen from her enchanted pantry, where every ingredient is labeled with an enchantment level from 1 to N.

However, Seraphina is a perfectionist. She insists that a cake is only worth baking if its total enchantment — the sum of the three chosen ingredients' levels — is an even number. An odd total, she claims, makes the frosting curdle and the candles flicker in an unsettling fashion.

Being a meticulous record-keeper, Seraphina wants to know exactly how many distinct valid combinations she can bake. Since she respects each ingredient's individuality, she always picks three different ingredients, and she considers two selections identical if they contain the exact same trio regardless of order.

Given the size of her pantry N, help Seraphina count the number of valid triples $$$(a, b, c)$$$ with $$$1 \leq a \lt b \lt c \leq N$$$ such that $$$a + b + c$$$ is even.

As pantries can grow astronomically large, the answer may be an enormous number. Seraphina's enchanted ledger can only record values modulo $$$10^9 + 7$$$ — print the answer modulo $$$10^9 + 7$$$.

You are given a point $$$P$$$ and $$$n$$$ closed disks on the plane.

Disk $$$i$$$ is centered at $$$(x_i, y_i)$$$ and has radius $$$r_i$$$. It contains all points $$$(x, y)$$$ such that $$$$$$ (x - x_i)^2 + (y - y_i)^2 \le r_i^2. $$$$$$

It is guaranteed that the intersection of all $$$n$$$ disks is non-empty.

Find the minimum possible Euclidean distance from $$$P$$$ to a point that belongs to all disks.

The Legendary Huron is learning about sorting algorithms. After studying Bubble Sort and Bogo Sort, he became so enthusiastic that he invented his own algorithm: the Legendary Sort. This algorithm sorts an array and consists of two phases:

1. First, rotate the array to the left by $$$k$$$ positions ($$$0 \leq k \lt n$$$). Formally, the array $$$[a_1,a_2,\dots,a_n]$$$ becomes $$$[a_{k+1},a_{k+2},\dots,a_n,a_1,a_2,\dots,a_k]$$$. For example, the array $$$[1,2,3,4,5]$$$ becomes $$$[3,4,5,1,2]$$$ when $$$k=2$$$.
2. Then, while the array is not sorted, repeatedly perform the following operation: find an index $$$i$$$ ($$$1 \leq i \lt n$$$) such that $$$a_i \gt a_{i+1}$$$ and swap these two elements. If there are multiple valid indices $$$i$$$, any of them can be chosen.

The Legendary Huron wants to test his new algorithm in different scenarios. For that, he considers a permutation $$$[p_1,p_2,\dots,p_n]$$$ of length $$$n$$$, and processes $$$q$$$ queries on this permutation. Each query is one of the following types:

1. Given an index $$$i$$$ ($$$1 \leq i \lt n$$$), swap the elements $$$p_i$$$ and $$$p_{i+1}$$$.
2. Given an integer $$$k$$$ ($$$0 \leq k \lt n$$$), execute the Legendary Sort on the current permutation, rotating it by $$$k$$$ positions to the left in the first phase. Compute the minimum number of swaps that can be performed in the second phase. Note that the rotation of the first phase does not persist for future queries.

Help the Legendary Huron to process these queries.