PurpleCrayon has recently solved P=NP! He refused to share his proof (or his $$$1000000$$$ prize as part of the raffle prize pool) so we cannot use it as our Very Easy 1. Instead, we decided to create our own P=NP, so here it is. Count the number of solutions to the equation

$$$P=N \cdot P$$$

when $$$0 \leq P \leq X$$$ and $$$0 \leq N \leq Y$$$ where $$$X$$$ and $$$Y$$$ are given as input.

Elijah has taken some tests and he didn't do as well as he liked. So he decided to use his coding skills to hack into the grading system. The problem is, to be lowkey about it, he only will delete one test score.

What is the maximum average score he can get after deleting one test score (rounded down to the nearest tenth, i.e. $$$3.46$$$ would be rounded down to $$$3.4$$$).

Goma was busy picking flowers for Peach when he discovered a patch of flowers in the form of an $$$N$$$x$$$M$$$ lattice with one flower per point. Starting from point $$$(1, 1)$$$ of the lattice, Goma will walk in a straight line picking up all flowers in the points he passes through (including $$$(1, 1)$$$). He wants to find a path to maximize the number of flowers he picks, and he also wants to know the number of ways to walk that will maximize the number of flowers he picks up.

Elijah is playing against a computer in a game called 'ABCs', where each side takes turns playing the letter $$$A$$$, $$$B$$$, or $$$C$$$, with the computer going first. Every time Elijah plays a letter, he gets a point if and only if it is a card that the computer has played the most of up until that point (ties included). For example if the computer has played $$$AABC$$$, Elijah will only get a point if he plays $$$A$$$, but if the computer has played $$$ACBBC$$$ then Elijah will get a point whether he plays a $$$B$$$ or a $$$C$$$.

Being the trickster that he is, Elijah hacked into the game and found out the exact order the computer will play the letters. Unfortunately for him, the game found out about this trickery, and decided to punish him by only allowing him to play a single letter every turn (i.e. either all $$$A$$$s, all $$$B$$$s or all $$$C$$$s). Elijah wants to make the best of the situation, and wants to compute to maximum possible of points he can achieve.

Cameron is a cashier for a store and at the end of the day, Cameron wrote down the money he got from each customer throughout the day. His manager wants the mean, median, and mode of the list of money from each customer. The manager wants all numbers to be rounded down to the nearest integer, and if there are multiple modes, then the manager wants the largest mode. If the number of customers that day was even, then the manager wants the median to be the average of the two middle numbers, rounded down.

Ryan is a bookworm. He has many books on his shelf, and he wants to sort them alphabetically by their first letter. Furthermore, he wants to sort the books that have the same starting letter by their published years, from oldest to most recent. Note that all the book titles are one word, with all lowercase letters.

Cameron the cashier works as a cashier in a beverage store. The store manager wants the menu of the beverages to change weekly, however the sizes of the cups would stay the same as Small, Medium, Large. Over the week, every customer got 1 letter of each word of their order wrong (meaning that the word was the same, including it's length and all other letters of the word except for one letter), and mispronounced their order.

For example, one week the manager decided to sell Lemonade and Punch. A customer asked for a Smell Panch. The actual order the customer was asking for would be the Small Punch. Assuming all the names of the beverages are one word (in the order of size of cup then beverage name "Small Punch"), and assuming that a mispronunciation can't be a mispronunciation of more than one word, help Cameron understand what the customers were asking for.

Teamscode has created a problem set for the constants to solve. A problem set consists of $$$N$$$ different problems with each problem having a difficulty $$$d$$$ (not necessarily distinct) and the difficulty is nondecreasing from $$$1$$$ to $$$N$$$. However, the day before the contest, Bossologist messed up and scrambled the problem set into a random order. The rest of the problem writing team is now angry at Bossologist, and would like to compute the number of possible original problem sets to make a case to HR.

Chessbot owns a lawn which has $$$N$$$x$$$M$$$ $$$(1 \leq N, M \leq 1000)$$$ patches of grass, represented as a grid of squares, where the top left square is labeled $$$(1, 1)$$$ and the bottom right one is labeled $$$(N, M)$$$. Each patch of grass has a beauty value $$$b_{ij}$$$ associated with it, which denotes the beauty value for the square in the $$$i$$$th row and $$$j$$$th column $$$(1 \leq i \leq N, 1 \leq j \leq M)$$$. Because Chessbot is a negative person, he only cares about the least beauty value. He would like to survey parts of his lawn from the top left square $$$(1, 1)$$$ to a square $$$(x, y)$$$ to see what the minimum beauty value is of that part of his lawn.

Alex wants to make stonks so he creates his own company. He slowly hires more people over time as his company grows larger. Each person takes a certain amount of time to earn one dollar for the company, and they are not paid (Alex is a very demanding boss). He wants to buy a new campus for the company which costs $$$X$$$ dollars in order to further expand. Your job is to find how soon he is able to do so.

Because he was so grateful of the flowers he received, Peach wants to make a necklace for Goma (how sweet!) . He starts off with a straight line of $$$N$$$ beads labeled $$$1$$$ to $$$N$$$ $$$(1 \leq N \leq 4 \cdot 10^5)$$$ all held together with a string. Peach quickly realizes however, that the necklace would be way too long, so he decides to cut it at certain places to shorten the necklace. As he is cutting the necklace, he wants to know how many beads share a single string with a certain bead.

This is the easy version of the problem. The difference between the easy and hard versions is that for this problem (the easy version) $$$k = 1$$$ and $$$(1 \leq n \leq 10^{9})$$$.

Peach has finally taken Goma out to eat fried fish. There is an infinite amount of fish in the restaurant they are at. They are lined up in a way such that the $$$i$$$th fish from the entrance has flavor $$$i^k$$$. In other words, the fishes have flavor $$$1^k, 2^k, 3^k, 4^k, \cdots, \infty^k$$$. So when eating, Peach will pick a starting point and an ending point and eat all the fishes from the starting point to the ending point (excluding the ending point). The total flavor of those fishes will be the sum of the flavor of each individual fish, so if the starting point is $$$4$$$ and the ending point is $$$6$$$ (with $$$k = 1$$$), the total flavor is $$$9$$$ (excluding endpoint). They will visit the restaurant for the next $$$D$$$ days would like to eat a total flavor of $$$n[i]$$$ on day $$$i$$$ and would like you to find any pair of starting and ending points such that the total flavor is $$$n[i]$$$. Due to the fact they do not want to walk that far before eating, the ending point must be $$$\leq n$$$.

More formally, you will have to answer D queries with each query being two numbers $$$n$$$ and $$$k$$$ $$$(k = 1)$$$, and you have to find and output any two numbers $$$a$$$ and $$$b (1 \leq a \lt b \leq n)$$$ such that $$$\sum_{i=a}^{b-1} i^k $$$ is $$$n$$$. Remember again to exclude the right endpoint.

Shion is cooking an amazing feast for you—so amazing that her toxic food sometimes melts through the bowl! She uses $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ ingredients where the quantity of the $$$i$$$th ingredient is $$$A_i$$$ $$$(1 \leq A_i \leq 10^5)$$$. The tastiness of the meal is the maximum of $$$lcm(A_i, A_j)$$$ over all $$$i \lt j$$$. You don't want to acquire the poison resistance skill after eating her food, so you decide to sneak in an extra ingredient with quantity $$$B$$$ $$$(1 \leq B \leq K \cdot max(A_i), \, 2 \leq K \leq 10)$$$ for Shion to also use. Find the value of $$$B$$$ that maximizes the tastiness of your potentially final feast!

Chessbot would like to make it through his $$$N$$$x$$$M$$$ $$$(1 \leq N, M \leq 1000)$$$ yard in as little steps as possible going from the top left corner $$$(1, 1)$$$ to the bottom right $$$(N, M)$$$. A step consists of either going up, down, left, or right, and Chessbot cannot leave his yard. However there are a ton rocks in the way, which might hamper him, or even possibly prevent him from making it!

Fortunately for him, there are $$$K (1 \leq K \leq 3 \cdot 10^5)$$$ one way teleporters which go from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$. If Chessbot steps on $$$(x_1, y_1)$$$ for a teleporter then he automatically will be teleported to $$$(x_2, y_2) $$$(i.e. he must take the teleporter). Note that this means if there is another teleporter that goes from $$$(x_2, y_2)$$$ to another point $$$(x_3, y_3)$$$, he must go through that one as well. Each starting point for a teleporter is unique.

Kanna is playing a game with Saikawa! The game is played on an $$$N$$$ by $$$N$$$ $$$(1 \leq N \leq 2000)$$$ field of flowers. The flower at the $$$i$$$th row and $$$j$$$th column has color $$$C_{i,j}$$$ $$$(1 \leq C_{i,j} \leq 10^6)$$$.

A player can start at any flower and move to the right along the row until they choose to stop or they are at the edge of the field.

Let's say they started at column $$$A$$$ and ended at column $$$B$$$.

Then, they can repeatedly move one down along the column as long as each time they move both conditions are satisfied:

1. They are not at the edge of the field. 2. $$$C_{R+1,i} = C_{R,i}$$$ for all $$$A \leq i \leq B$$$ where $$$R$$$ is their current row (before moving).

The score for the player is the area of the rectangle with top left corner at their starting point and bottom right corner at their ending point. For example, if Ilulu starts at row $$$1$$$ and column $$$1$$$ and ends at row $$$2$$$ and column $$$3$$$, her score is $$$6$$$. After both players finish moving, the winner is the one with the higher score.

If Kanna wins, Saikawa needs to rub her tummy as a "penalty" game. Despite being hundreds of years old, Kanna never decided to do any cp, so she asks you to figure out the maximum score she can achieve.

there's supposed to be an anime image here but due to cf having a limit of 1mb you don't get to see it. go to the git to find it.

For a second time, Elijah is playing against a computer in a game called 'ABCs', where each side takes turns playing the letter $$$A$$$, $$$B$$$, or $$$C$$$, with the computer going first. Every time Elijah plays a letter, he gets a point if and only if it is a card that the computer has played the most of up until that point (ties included). For example if the computer has played $$$AABC$$$, Elijah will only get a point if he plays $$$A$$$, but if the computer has played $$$ACBBC$$$ then Elijah will get a point whether he plays a $$$B$$$ or a $$$C$$$.

Being the trickster that he is, Elijah hacked into the game and found out the exact order the computer will play the letters. Unfortunately for him, the game found out about this trickery, and this time decided to punish him by only allowing him switch letters after playing the same letter at least $$$K$$$ consecutive times. Elijah wants to make the best of the situation, and wants to compute to maximum possible of points he can achieve.

Peach and Goma were playing with trees, and Peach had a new idea. Note, all trees will be $$$0$$$-based, or all nodes of a tree with $$$n$$$ vertices will be [$$$0$$$, $$$n$$$). She defined the width of a rooted tree as the maximum number of nodes that have the same depth from the root. Consider the tree $$$(0, 1)$$$, $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(1, 4)$$$. The width of the tree rooted at node $$$0$$$ is $$$2$$$, (nodes $$$2$$$ and $$$4$$$ having a distance of $$$2$$$ away). However, the width of the same tree rooted at node $$$1$$$ has a width of $$$3$$$, (nodes $$$0$$$, $$$2$$$, and $$$4$$$ having a distance of $$$1$$$ away). Peach asked Goma to find the maximum width of a tree with $$$n$$$ nodes $$$(1 \leq n \leq 5 \cdot 10^{5})$$$ across all possible roots.

However, chessbot (the problemsetter), is lazy and decided to give you trees as input with the following format. A modtree with $$$n$$$ nodes is a tree defined by an integer $$$n$$$. For all nodes $$$i$$$ [$$$1$$$, $$$n$$$) there is an edge between $$$i$$$ and $$$n \mod i$$$. It can be proven that for all $$$n$$$, the modtree size $$$n$$$ will be connected and satisfy all the properties of a tree. Note $$$n \mod i$$$ is not $$$i \mod n$$$ and that the tree is labeled $$$0$$$-based.

A tree with $$$4$$$ nodes will have edges, $$$(1, 0)$$$, $$$(2, 0)$$$, $$$(3, 1)$$$.

Kakyoin is painting a picture on an $$$N$$$ by $$$N$$$ grid of cells $$$(1 \leq N \leq 10^6)$$$. At first every cell in the grid contains a $$$0$$$. With each stroke of his brush, he can paint a rectangle of $$$1$$$'s where the sides of the rectangle are parallel to the sides of the grid. However, the new rectangle of $$$1$$$'s cannot cover any previously painted $$$1$$$'s and every $$$1$$$ in the rectangle cannot share a row or column with any previously painted $$$1$$$'s. At some point Kakyoin was interesting in painting, but Araki forgot and now he's too busy using his emerald splash. So he asks you to find the sum of the number of strokes in his painting across all possible paintings that he can paint modulo $$$10^9 + 7$$$. Two paintings are considered different if the number in some cell differs between the two.

This is the revised version since i am too lazy to fix the checker.

This is the hard version of the problem. The difference between the easy and hard versions is that for this problem (the hard version) $$$ (2 \leq k \leq 20 ) $$$ and $$$ (1 \leq n \leq 10^{18}) $$$.

Peach has finally taken Goma out to eat fried fish. There is an infinite amount of fish in the restaurant they are at. They are lined up in a way such that the $$$i$$$th fish from the entrance has flavor $$$i^k$$$. In other words, the fishes have flavor $$$1^k, 2^k, 3^k, 4^k, \cdots, \infty^k$$$. So when eating, Peach will pick a starting point and an ending point and eat all the fishes from the starting point to the ending point (excluding the ending point). The total flavor of those fishes will be the sum of the flavor of each individual fish, so if the starting point is $$$4$$$ and the ending point is $$$6$$$ (with $$$k = 1$$$), the total flavor is 9 (excluding endpoint), if $$$k$$$ was equal to $$$3$$$, it would be $$$4^3 + 5^3$$$ or $$$189$$$. They will visit the restaurant for the next $$$Q$$$ days would like to eat a total flavor of $$$n[i]$$$ on day $$$i$$$ and would like you to find any pair of starting and ending points such that the total flavor is $$$n[i]$$$. Due to the fact they do not want to walk that far before eating, the ending point must be $$$\leq n$$$.

More formally, you will have to answer $$$D$$$ queries with each query being two numbers $$$n$$$ and $$$k$$$ and you have to find and output any two numbers $$$a$$$ and $$$b (1 \leq a \lt b \leq n) $$$ such that $$$\sum_{i=a}^{b-1} i^k $$$. Remember again to exclude the right endpoint.

Vivy is carrying out the singularity project! She is currently at the start of everything at event $$$0$$$. Unfortunately, $$$N$$$ $$$(1 \leq N \leq 10^5) $$$ more timeline changing events are about to occur. Luckily, Vivy has picked a special number $$$X$$$ $$$(1 \leq X \leq 10^9)$$$ to assist her project. When the $$$i$$$th event occurs, a random number $$$A$$$ from $$$0$$$ to $$$X-1$$$ is generated. Then, it becomes possible to go from event $$$(A \mod i)$$$ to event $$$i$$$ and event $$$i$$$ is considered a child of event $$$(A \mod i)$$$. If after all events occur, event $$$0$$$ has more than $$$2$$$ children or there exists an event $$$i$$$ such that $$$i \gt 0$$$ and it has more than $$$1$$$ child, the timeline becomes unstable and only a tragic future where AIs are bent on eradicating humanity awaits. If no such event exists, the singularity project is successful and humans and AIs live happily ever after. As Vivy's partner, you want to test the value of $$$X$$$ and determine the probability that the singularity project is successful.

Rengoku is battling a powerful demon! This demon has $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ hearts where the $$$i$$$th heart has health $$$H_i$$$ $$$(1 \leq H_i \leq N)$$$. Luckily for Rengoku, he practices Flame Breathing and knows $$$K$$$ $$$(2 \leq K \leq 2 \cdot 10^5)$$$ different forms. In one attack, he picks a random heart $$$i$$$ such that $$$H_i \gt 0$$$ and also picks a random form $$$F$$$ from $$$1$$$ to $$$K$$$. Then he uses the $$$F$$$th form on the $$$i$$$th heart, reducing its health to $$$\lfloor \frac{H_i}{F} \rfloor$$$ (floor division). The demon is slain after the health of all its hearts drops to $$$0$$$. As Rengoku's kouhai, he assigns you the task of finding the expected number of attacks he will use to slay the demon.

Thomas has been caught game! The game he is playing is defly, a game of flying a plane to connect dots, (Note this is slightly different from the actual game). In the game, you have a set of $$$N$$$ points $$$(5 \leq N \leq 5 \cdot 10^5)$$$ and you want to draw a convex polygon around the points such that all the points are contained within it. To use less effort, Thomas is using his skills to minimize the area of such a polygon (more formally these things are called convex hulls). Teacher got mad and destroyed two points in Thomas's set of points, but Thomas does not know which points these are. So he would like to ask you $$$Q$$$ queries $$$(1 \leq Q \leq 5 \cdot 10^5)$$$ where each query is defined as two indices $$$a$$$ and $$$b$$$ $$$(1 \leq a, b \leq N, a \neq b)$$$, and Thomas would like to know what the are of the convex hull of the entire array without those two points would be.

Also, note since the problem setter, chessbot, does not like making edge cases, all of the points will be randomly generated using the following code:

https://pastebin.com/LjfHKxtN

Sol is trying to get home at location $$$N$$$ from his office at location $$$1$$$ in time for the problem writing meeting which is in $$$K$$$ minutes. There are $$$M$$$ bidirectional roads which connect location $$$a$$$ to location $$$b$$$, each taking $$$w$$$ minutes to go through, and each raising his angriness to $$$f$$$ when passing through the road (Sol is very irritated by traffic). But because he is generally quite calm, at each location his angriness resets back to 0. To stop himself from road raging he wants to minimize his maximum angriness at any point in time.

However, this is not Sol's only challenge. The logistics team is trying to sabotage Sol's trip by making him as angry as possible (the problem writing team is their arch enemy). They do this by closing down a single road that will cause him to endure the most angriness on his drive to his home. Please output the minimal maximum angriness that Sol has to endure on his trip home given that he has to make it in $$$K$$$ minutes, and the logistics team has shut down one of the roads.

Endeavor is a great hero and wants to help keep his country, Japan, safe. Japan contains $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ cities numbered from $$$1$$$ to $$$N$$$. There are also $$$M$$$ $$$(0 \leq M \leq 5 \cdot 10^5)$$$ bidirectional roads where the $$$i$$$th connects city $$$M_{i,a}$$$ to city $$$M_{i,b} \, (M_{i,a} \neq M_{i,b})$$$ and makes the two cities neighbors. It is guaranteed that there is at most $$$1$$$ road between any pair of cities. Japan also has a peculiar feature. Consider a path that visits $$$w$$$ cities from city $$$u$$$ to city $$$v$$$, where the $$$i$$$th city on the path is $$$p_i$$$. Then if $$$p_i \lt p_{i+1}$$$ for all $$$i \lt w$$$, city $$$u$$$ and city $$$v$$$ are neighbors.

Endeavor decides to build a hero office in some cities. To ensure safety and efficiency, he wants at least one of the conditions to be satisfied for every city:

The city has no neighbors.

The city contains an office.

All neighbors of the city contain an office.

Japan is considered safe if this requirement is met.

Unfortunately, as great of a hero as Endeavor is, he still hasn't defeated the greatest villain—money! To cut down on costs, Endeavor's agency decides to build the minimal number of offices such that Japan is safe. Currently, Endeavor is busy roasting evildoers (literally), so he wants you to find this out for him.

Chessbot had a problem of finding the maximum spanning tree, but since he was too lazy to generate graphs, so he proposed to just use an $$$ N $$$ x $$$ M$$$ lattice where the distance between two points was the euclidian distance squared. PurpleCrayon decided this problem wasn't hard enough and decided to make it a d-dimensional lattice grid where the distance between two points $$$ p_{1} $$$ and $$$ p_{2} $$$, where each point is represented as a tuple length $$$ d $$$ , $$$ x_{1}, x_{2}, \cdots, x_{d} $$$ where $$$x_i$$$is the location on the $$$i$$$th dimension, is $$$ \sum_{i=1}^d | p_{1,i} - p_{2,i} |^k $$$, where $$$d$$$ and $$$k$$$ are given as input. So the question is given a d-dimensional lattice grid (with the i'th dimension being D[i]) and k, find the maximum spanning tree of the graph where there is an edge between all pairs of two points from $$$ (1, 1, \cdots, 1)$$$ and $$$(D[1], D[2], \cdots, D[d])$$$ of the lattice equivalent to the distance formula described above.