Carlos has invented a new language! his new language is called aaegglnu. This new language has the weird characteristic that in each word, all letters are read at the same time! He now wants to teach aaegglnu to his students, and for this he first need to create an ordering for his language and he has decided on the following:

Lets define function $$$f$$$ which given a string $$$S$$$ returns another string $$$S'$$$ which has the same characters as $$$S$$$ but with the characters ordered. For example $$$f(\text{'language'}) = \text{'aaegglnu'}$$$. so in the ordering of aaegglnu, word $$$A$$$ goes before $$$B$$$ if lexicografically $$$f(A)$$$ goes before $$$f(B)$$$. In the case that $$$f(A)=f(B)$$$, $$$A$$$ goes before $$$B$$$ if lexicografically $$$A$$$ is smaller than $$$B$$$.

His students are however still a bit slow when looking for a word in the dictionary Carlos made, so they have asked for your help in this.

Geose is preparing another geometry problem. To complete his task, he needs to write the model solution and the test cases. Currently, he has a convex polygon $$$P$$$ with $$$n$$$ vertices, and he wants to generate additional tests using this polygon.

To create a new test, Geose selects a sub-polygon from $$$P$$$. A sub-polygon is defined as a polygon formed by a subsequence of at least $$$3$$$ vertices from the original polygon, without changing their order. In particular, the original polygon is also considered a sub-polygon.

Second example.

For example, in the figure above, the left polygon corresponds to the second sample, and all three polygons shown are valid sub-polygons of it.

Geose believes that the larger the area of a sub-polygon, the better the quality of the test. Since he is occupied with writing the solution for the problem, he asks for your help in designing the tests. Your task is to compute the areas of all possible sub-polygons of $$$P$$$ and print them in non-increasing order.

If the number of sub-polygons exceeds $$$2\cdot10^5$$$, only print the largest $$$2\cdot10^5$$$ areas, sorted in non-increasing order.

Conner is an avid reader. He knows there are two main reasons for reading a good book: first, to enjoy it, and second, to boast about having read it.

However, he faces a problem: every book he has takes time to read. Furthermore, his university library has adopted a policy that allows him to read any book, provided the following conditions are met:

1. At most, he can have one book on loan; for instance, to borrow a second book, he must have returned the first one.
2. A book can only be borrowed if it is within the librarian's working hours (from 8 am to 4 pm, for a total of 480 minutes).
3. If a book is borrowed and not finished by 4 pm, it can be returned later, but the library closes its doors at 9 pm (300 minutes after the librarian's working hours end).

Conner wishes to respect all the rules. He knows that it takes him 3 minutes to read one page (it can be assumed that all pages take the same amount of time to read).

Given a list of books, each with its number of pages, a value indicating how enjoyable it is for Conner, and a number indicating its fame (for which Conner could boast about having read it), you must calculate two values: first, the maximum enjoyment value Conner can achieve from reading, and second, the maximum fame value he can accumulate. All readings must be complete to count and must be done in a single day. If the enjoyment is greater than the fame, then indicate to Conner that he should read for enjoyment; if the opposite is the case, indicate that he should read for fame.

There is a circle drawn on the ground. The circle has $$$n$$$ equally spaced marks on its perimeter. The $$$i$$$-th mark is said to be adjacent to the $$$(i-1)$$$-th and $$$(i+1)$$$-th marks (if they exist). Marks $$$1$$$ and $$$n$$$ are adjacent as well.

$$$n$$$ ferrets numbered form $$$1$$$ to $$$n$$$ will perform a dance on this circle. Initially, the $$$i$$$-th ferret is standing on the $$$i$$$-th mark. They will dance for $$$2024!^{2024!}$$$ rounds. If a ferret is standing on mark $$$i$$$ at the beginning of a round, it will move to mark $$$p_i$$$ during that round. It is guaranteed that $$$[p_1, p_2, \dots, p_n]$$$ is a permutation.

Some pairs of ferrets are best friends and don't like to be too far from each other for a long time. For that reason, they want to know if they will be standing on adjacent marks at the beginning of any round. Write a program to answer $$$q$$$ queries and help the ferrets to know that. For each query, you are given two integers $$$a$$$ and $$$b$$$, and you must determine if ferrets $$$a$$$ and $$$b$$$ will stand on adjacent marks at the beginning of any round.

Jorge is a really friendly person, he is so friendly that he has $$$k$$$ friends! sadly he doesn't know where his friends live. He only knows they are all from a different city. The world of Jorge consist of $$$n$$$ cities enumerated from $$$0$$$ to $$$n-1$$$. Between them there are $$$m$$$ roads, with different lengths, that connect a pair of cities, such that at least one path between every pair of cities exist. Jorge lives in city $$$0$$$, and he wants to know the expected value of the distance to his closest friend (The distance to a friend is the length of the shortest path between city $$$0$$$ and his friend's city).

Given the description of the world, and the number of friends Jorge has, answer the value he wants. Assume all possible arrangements of his $$$k$$$ friends are equiprobable.

Alice and Bob each bought a bag of toys at the city fair. Each toy bag is supposed to contain exactly 5 different toys, and every bag sold at the fair has the same set of toys.

When they got home and opened their bags, Alice discovered that her bag had all 5 toys, as expected. However, Bob found that his bag only contained 4 toys! He wants to return to the fair to complain, but before doing so, he needs to figure out which toy is missing from his bag.

Your task is to help Bob identify the missing toy.

In the eccentric town of GCDland, there lives a mathematician named Theo, who has a wild and paranoid conspiracy theory. Theo is convinced that in certain mystical arrays, the greatest common divisor (GCD) of every possible pair of numbers is always the same. He believes that these arrays are messages from an ancient civilization trying to communicate with us through numbers.

Theo's friends think he's gone off the deep end, but he's determined to prove them wrong and uncover the truth behind these arrays. He needs your help to validate his theory. Given an array of integers, your task is to determine whether the GCD of every pair of numbers in the array is indeed the same. If Theo's theory holds true for the given array, you should confirm it; otherwise, you should debunk it.

The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder.

It is a well known fact that it's impossible to fill the plane with identical regular octagons, but the math mages didn't knew this till it was too late, they had already ordered an infinite number of them (And they only had to pay $$$-\frac{1}{12}$$$ dollars for them).

So, now, they want to try to fill the plane anyway! To do this they devised the following algorithm, they'll start by putting an octagone anywhere in the plane, they will call this octagon, octagon 0.

From octagon $$$0$$$, they choose one of its sides, and try to put another octagon next to it such that one of its faces coincide with the choosen face, this will be octagon $$$1$$$.

After that they will follow the next procedure:

- Let $$$n$$$ be the number of the last octagone that was put on the plane. From the side that coincides with the octagone $$$n-1$$$ we start trying to put octagone $$$n+1$$$ next to that side, if it is not possible, we try the next side counterclockwise, until it is possible to put a new octagone without overlapping another octagone that was put before.

It can be proven that this procedure allows you to put an infinite number of octagons in the plane.

Before starting, they want to know what is the squared distance from the center of octagone $$$k$$$ to the center of octagone $$$0$$$

The new girl in school Shikanoko is a bit weird, she has deer antlers and loves to eat deer cookies! Her friend Koshi has found out that the store next to the school has started selling packages of human and deer cookies. All packages have the same number of cookies, and both the human and deer cookies in the same order. A package can be expressed as a binary string where $$$1$$$ represents a deer cookie, and $$$0$$$ represents a human cookie, so for example $$$1101$$$ means the first and second cookie in the package will be deer cookies, and the third will be a human cookie.

Shikanoko wants Koshi to share a package with her, and she will be happy if she eats all of the deer cookies, and Koshi eats all the human cookies. She also wants, that at any moment, she has eaten at least the same number of cookies as Koshi.

Koshi, doesn't want to look violent, so she will only grab cookies from either ends of the packages. For example, Koshi won't eat or give the third cookie to Shikanoko if neither the second nor the fourth cookie has been eaten before.

Koshi knows she'll have to do this daily, so she has decided to try and pick a different order in which the cookies are eaten each day. An order is considered different than another if for at least two different cookies $$$i$$$ and $$$j$$$, the cookie $$$i$$$ is eaten before cookie $$$j$$$ in one order, and in the other cookie $$$j$$$ is eaten before cookie $$$i$$$.

Koshi will be bored the day that the order in which cookies are eaten has been repeated in another day before. Find the maximum possible day in which Koshi will be bored for the first time.

It's a busy evening at Chef Elisa's restaurant, and the kitchen is working tirelessly to fulfill the orders of hungry clients. Elisa is known for her creativity, using a wide variety of fresh ingredients to craft her famous dishes. The kitchen is stocked with $$$N$$$ different ingredients, each available in limited quantities, and the staff has prepared a menu of $$$M$$$ signature dishes, each requiring specific ingredients to make.

A large crowd has gathered, and the kitchen is being flooded with orders, each containing requests for multiple dishes. Elisa is determined to fulfill the orders in the order they are received, but there's a catch: the kitchen only has so many ingredients, and they must be used carefully.

As the evening progresses, Elisa notices that the ingredients are running low. The kitchen staff must figure out how many consecutive orders they can fulfill, starting from the first, before they can no longer make the requested dishes due to a lack of ingredients. If the kitchen does not have enough ingredients to plate all the dishes from an order, then that order can not be fulfilled, once an order cannot be fulfilled, the kitchen will close for the night

Your task is to help Elisa and her staff determine how many orders can be processed in the order they arrive, before they run out of ingredients and are unable to fulfill the next order.