In Minecraft, there are three dimensions in the simple world, one of which is known as "The End". In this dimension, the Ender Dragon is usually symbolized as the final boss of Minecraft.

Now we, you, and Steve want to beat the dragon. However, we find that the dragon is telling a puzzle. We must solve it before fighting against the dragon. Please stand by our side to fight against the dragon. The puzzle goes as follows.

Given two positive integers $$$x$$$ and $$$y$$$, please find two integers $$$a$$$ and $$$b$$$, such that $$$$$$ \sqrt{\frac{{\rm lcm}(x,y)}{{\gcd}(x,y)}} = a \sqrt{b} $$$$$$and to maximize $$$a \cdot b$$$.

Here, $$$\gcd(a,b)$$$ represents the greatest common divisor of $$$a,b$$$, while $$$\rm lcm(a,b)$$$ represents the least common multiple of $$$a,b$$$.

Nana's electronic pet, MACARON, enjoys moving around in the room. Nana wants to create a bounded area where MACARON can roam within.

The positions in the room can be represented using a two-dimensional coordinate system, and Nana provides a set of vertices on it. Nana likes polygons and now wants to select a subset of vertices that can form a convex polygon as its endpoints. However, Nana also wants to ensure that the selected area is not too big.

Thus, she is going to determine the minimum possible area of the convex polygon ending on a subset of given vertices. If such a convex polygon doesn't exist, please output "$$$-1$$$"(without quotes).

Lili and Nana are weeding in the backyard of Lili's house. They are repeatedly selecting rectangular areas and removing all the grass within them.

The backyard can be visualized as a 2D grid, each square cell representing one unit area. They have performed a total of $$$n$$$ operations. During the $$$i$$$-th operation, they choose the left, bottom, right, and top sides of a rectangle, denoted as $$$l_i, b_i, r_i, t_i$$$, and clear all the cells within this rectangle using a lawnmower. Note that these rectangles may overlap with each other.

Let $$$[l_i, r_i]\times[b_i, t_i]$$$ denote a rectangle.

Here is an example illustrated in the following figure. They have selected 2 rectangles, with the first rectangle being $$$[1, 5]\times[2, 3]$$$ and the second rectangle being $$$[2, 3]\times[1, 4]$$$.

After the $$$n$$$ weeding operations, the union of the bare area may not be connected but all the sides are horizontal or vertical. Thus, the union becomes orthogonal polygon(s), some of which contain polygon holes. Moreover, there can be bare cells inner some holes. Please see the example inputs for more details and illustrations.

Now, they want to restore the land by planting some plants on the bare cells. Lili likes polygons, especially rectangles. Therefore, they want to select several rectangles, and these rectangles do not overlap with each other and exactly cover all the bare cells. Then, they plant different plants in different rectangles they selected.

For example, here is a feasible selection of rectangles for the aforementioned case: choose $$$[1, 1]\times [2, 3]$$$, $$$[2, 3]\times[1, 4]$$$ and $$$[4, 5]\times [2, 3]$$$.

After playing for a while, these two little girls have become tired, so they want to know the minimum number of non-overlapping rectangles that can cover all the bare cells.

MACARON is going to read a book, which contains $$$n$$$ chapters, and the $$$i$$$-th chapter has $$$a_i$$$ characters. MACARON wants to read this book in the next $$$k$$$ days. On each day, he either reads several chapters from the first unread chapter, or just takes a rest (does not read the book), but he should finish his reading in $$$k$$$ days.

MACARON enjoys his reading time and likes happy endings, so he does not want to be too sad during these days. He has an unlucky number $$$d$$$, because he thinks number $$$d$$$ will lead to a bad ending. We use a sadness value to quantify his mood on each day. On the $$$i$$$-th day, if he reads, suppose that he reads chapters from $$$L_i$$$ to $$$R_i$$$. The sadness value of this day is the number of intervals $$$[l, r]$$$ such that $$$L_i\leq l\leq r\leq R_i$$$ and $$$\bigoplus_{i=l}^r a_i=d$$$. The $$$\oplus$$$ denotes the bitwise XOR operator. If he doesn't read, let the sadness value be $$$0$$$.

MACARON wants to arrange his reading schedule to minimize the sum of sadness value in $$$k$$$ days. Can you help him find the minimum value?

Since a regular programming contest lasts for five hours, it's a big problem to prepare contestants' food during the contest.

In the 20XX International Collegiate Programming Contest in Hubei Province, China, there were $$$n$$$ contestants participating in the contest. The host wanted to prepare a Spicy Chicken Burger Set for every contestant, which was $$$a$$$ dollars per set at that time. But since there were some people who could not bear the spiciness like Walk Alone, a Grilled Chicken Burger Set was prepared for these people, which was $$$b$$$ dollars per set. Before the contest, the host had collected the number $$$x$$$ of people who wanted to eat a Grilled Chicken Burger Set.

But Walk Alone was too stupid and lazy to calculate how much the host would spend. Please help him to calculate.

In Minecraft, one way to become stronger is to have the armors and weapons enchanted. Enchanted books play an important role.

The most important attribute of an enchanted book is its level. The higher the level is, the better the book is. We could merge two books with the same level $$$l$$$ into one new book(the older two will disappear). The level of the new book is $$$l+1$$$ and the merger costs $$$2^{l+1}$$$.

Now, Steve has $$$n$$$ enchanted books numbered from $$$1$$$ to $$$n$$$. Initially, the $$$i$$$-th book's level is $$$a_i$$$. Steve asks you to help him with the following four operations.

1. Given two integers $$$l,r(1 \le l \le r \le n)$$$, calculate the maximum level Steve can reach by merging books numbered from $$$l$$$ to $$$r$$$.
2. Given three integers $$$l,r(1 \le l \le r \le n)$$$ and $$$k$$$, then follow the steps:

   Step $$$1$$$: Steve merges all the books numbered from $$$l$$$ to $$$r$$$ until there does not exist two books with the same level.

   Step $$$2$$$: Steve adds one new book with level $$$k$$$ to the books he gets in Step $$$1$$$.

   Step $$$3$$$: Steve needs to merge books he gets in Step $$$2$$$ and he wants to maximize the times he merges the books.

   Please calculate and output the total cost modulo $$$10^9+7$$$ in Step $$$3$$$.

   Note that, after calculating, the sequence is restored. That is, this operation does NOT actually change the sequence.

3. Given two integers $$$pos,k$$$, Steve changes the level of the book numbered $$$pos$$$ to $$$k$$$.
4. Given one integer $$$t$$$, Steve restores the sequence to the state after the $$$t$$$-th operation. If $$$t=0$$$, then Steve restores the sequence to the beginning state.

Blue-edged Shot is forbidden from playing Genshin Impact by LeavingZ, so she turned to Go game.

A game of Go involves two players, one playing with Black stones and the other with White stones. Two players take turns making moves, with the Black stones going first. The Go board is composed of a grid of $$$19\times 19$$$ intersections, and we use $$$(x,y)$$$ to represent the intersection at the $$$x$$$-th row and $$$y$$$-th column. The stones are placed on the intersections. The top left corner is $$$(1,1)$$$, while the bottom right corner is $$$(19,19)$$$.

The intersections $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ are adjacent if and only if $$$|x_1-x_2| + |y_1-y_2| = 1$$$. Adjacent intersections with stones of the same color belong to the same group of stones. The number of "liberties" for a stone is equal to the number of adjacent intersections to the stone's intersection that do not have any stones on them. The liberties of a group of stones equal the sum of the liberties of all the stones belonging to that group. A group of stones with zero liberties is considered dead and must be removed from the board.

Note that after Black plays, priority is given to removing any dead White stones, and then recalculating the liberties for Black stones. This is because there might be situations where, after Black plays, both Black and White stones have zero liberties, but removing the dead White stones increases the liberties for Black stones. As for White, process the stones similarly. After White plays, priority is given to removing any dead Black stones, and then recalculating the liberties for White stones.

Now there is a game of Go, starting with an empty board, and a total of $$$m$$$ moves have been made by both players. Given the positions where each stone is placed, output after each move, how many Black and White stones are removed respectively causing by this move. Obviously, black stones are played on odd-numbered moves, and white stones are played on even-numbered moves. It's guaranteed that stones are placed on empty intersections. Note that stones can be placed on any intersections that do not have stones on them at the moment, regardless of violating the Go rules in real life.

Blue-edged Shot is forbidden from playing Genshin Impact by LeavingZ. However, today LeavingZ went to Huazhong University of Science and Technology, School of Cyber Science and Engineering, to harvest the gold medal of the 2024 International Collegiate Programming Contest in Hubei Province, China.

An activity of Genshin Impact called "Dodoco's Bomb-Tastic Adventure" has begun. This is a single-player game, where each game involves a pond. The pond can be divided into an $$$n$$$ by $$$m$$$ grid, with the cell in the $$$i$$$-th row and $$$j$$$-th column represented by $$$(i,j)$$$. Among these, $$$k$$$ cells contain fish, and you will play as the Spark Knight Klee, who fishes with explosives.

If Klee drops a bomb at $$$(a,b)$$$, all the cells $$$(x,y)$$$ satisfying $$$|x-a|+|y-b|\le 1$$$ will be covered by the explosion. For every cell covered by the explosion, Klee will catch one fish from it. Klee can drop bombs at any location. The question is, to catch all the fish, how many "Jumpy Dumpty" bombs are needed at a minimum?

You are given a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$ and $$$n - 1$$$ edges. Each node has a color. Initially, all of them are white.

We are going to perform $$$q$$$ operations. In each operation, two vertices $$$u$$$ and $$$v$$$ will be given, and we will color black to the points along the simple path from $$$u$$$ to $$$v$$$ ($$$u,v$$$ inclusive). Note that a simple path in the tree is defined as a path that does not pass through any vertex more than once.

After each operation, you are required to determine the length of the longest simple path in the tree where all nodes on the path are the same color. The length of a path is defined as the number of nodes on the path.

Alice is playing a single-player game on the number axis.

There are $$$n$$$ points on the number axis. Each time, the player selects two points. The two points will be removed, and their midpoint will be added. When there is only one point on the axis, the game ends. Formally, if the two chosen points is $$$x_i$$$ and $$$x_j$$$, then $$$\dfrac{x_i+x_j}{2}$$$ will be added after the operation.

In order to play this game happily, Alice will always select two points randomly.

Now Alice have a question: where is the expected position of the last point.

It can be proven that the answer can be expressed in the form $$$\dfrac{p}{q}$$$, you only need to output the value of $$$p\cdot q^{-1} \bmod 998\,244\,353$$$.

Bob is playing a single-player game on the number axis.

There are $$$n$$$ points on the number axis. Each time, the player selects two points. The two points will be removed, and their midpoint will be added. When there is only one point on the axis, the game ends. Formally, if the two chosen points is $$$x_i$$$ and $$$x_j$$$, then $$$\dfrac{x_i+x_j}{2}$$$ will be added after the operation.

In order to play this game happily, Bob will always select two adjacent points randomly. Initially, the $$$i$$$-th point and the $$$(i+1)$$$-th point are adjacent. When Bob added a new point, it inherits its left point's left adjacent point and its right point's right adjacent point.

Now Bob have a question: where is the expected position of the last point.

It can be proven that the answer can be expressed in the form $$$\dfrac{p}{q}$$$, you only need to output the value of $$$p\cdot q^{-1} \bmod 998\,244\,353$$$.

Walk Alone has a number axis with only positive integers on it. The cost of walking from point on integer $$$a$$$ to point on integer $$$b$$$ is $$${\rm lcm}(a, b)$$$, where $$${\rm lcm}(a, b)$$$ means the least common multiple of integers $$$a$$$ and $$$b$$$. Due to the hatred of the integer $$$1$$$, Walk Alone forbids anyone from moving to points on integers smaller than or equal to $$$1$$$.

Given two integers $$$a$$$ and $$$b$$$, you need to calculate the minimal cost of walking from point on integer $$$a$$$ to $$$b$$$.