Nahida is playing a game with her fungi friends, the Aranara, on the branches of the Divine Tree in Sumeru City. On the Divine Tree, there are $$$N$$$ ($$$2 \le N \le 10^5$$$) branches. Initially, Nahida starts at branch $$$a$$$ and the Aranara starts at branch $$$b$$$. In a single turn, Nahida will move from branch $$$a$$$ to $$$nxt_a$$$, and the Aranara will move from branch $$$b$$$ to $$$nxt_b$$$. The game ends when they move to the same position, allowing Nahida to finally catch the Aranara. It is guaranteed that $$$nxt_i \neq i$$$ for all $$$i$$$.

Note that Nahida and the Aranara move at the exact same time, so if in one turn Nahida is going from branch $$$1$$$ to $$$2$$$, and the Aranara is going from branch $$$2$$$ to $$$1$$$, then Nahida will not catch the Aranara.

Since the Aranara enjoy playing around in the beautiful nature of Sumeru, they want the game to never end. Thus, they ask you to find $$$N$$$ ordered pairs $$$(a, b)$$$ such that Nahida will never catch the Aranara. It can be shown that there always exists at least $$$N$$$ such ordered pairs.

Lazy Larry loves trees with a passion and wants to create the perfect natural park. However, his evil nemesis, Hardworking Harry, hatches a plan to ruin Larry's plan.

One aspect of Larry's plan is the perfect tree line. Larry has $$$N$$$ trees, with heights ranging from $$$1$$$ to $$$N$$$. Each tree has a distinct height, so for example, if $$$N$$$ is $$$5$$$, Larry has $$$5$$$ trees with heights $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$. Larry wants the tree heights to be in a specific order represented by array $$$a$$$ of length $$$N$$$.

Now, it is Harry's job to visit the park's site and place the trees in a way which angers Larry as much as possible. Larry's anger can be quantified as the minimum distance between his desired tree height for that location and the height of the tree placed at that location. In other words, if Harry places the trees in a manner given by an array $$$b$$$, Larry's anger will be $$$min(|a_i - b_i|)$$$ over all $$$i$$$. Find a way in which Harry can place trees such that Larry will be maximally angry, and print both his anger level and the tree placement.

A group of civil engineers are trying to model what will happen to a building if it experiences natural disasters. Using rulers to model the bricks of the building, they set up a column of $$$N$$$ rulers numbered from $$$1$$$ to $$$N$$$, lined up from end to end along the positive y-axis of the coordinate plane, with the first ruler starting at the origin. Each ruler has a length $$$L_i$$$. Consecutive rulers are connected by a "joint" that can turn. Initially, the angle between each consecutive ruler is $$$180$$$ degrees, so the first ruler has endpoints at ($$$0, 0$$$) and ($$$0, L_1$$$), the second ruler has endpoints at ($$$0, L_1$$$) and ($$$0, L_1+L_2$$$), and so on.

John receives a list of $$$K$$$ instructions. Each instruction contains an integer $$$S_i$$$ and an angle of degree $$$A_i$$$, telling him to turn the joint connecting ruler $$$S_i$$$ and ruler $$$S_i+1$$$ such that ruler $$$S_i+1$$$ is counterclockwise from $$$S_i$$$ by exactly $$$A_i$$$ degrees. When he turns this joint, all rulers with index $$$S_i+1$$$ and higher turn together (their relative angles remain the same) but rulers with lower index do not. After John finishes executing all the instructions, find the location of the endpoint of the last ruler.

Fast Sam and Cool Clyde decide to play a game. They have a barn that can be represented as a grid of dimensions $$$R$$$ by $$$C$$$. At the start of the game, each person stands on a specific position in the barn-grid, and they stand in different positions. They take turns moving to one of the adjacent squares (left, right, up, down) on the grid. Whoever makes the move such that they end up in the other person's square wins. Given that both people play optimally, output the result of the game.

Observation stations for early wildfire detection are being installed in a national park, each carrying a signaling device. A signaling device costing $$$P$$$ can connect to any other device within $$$\sqrt{P}$$$ distance. All observation stations contain a signaling device with the same power. Given a list of the coordinates of all $$$N$$$ observation stations in cartesian coordinates $$$(X_i, Y_i)$$$, find the minimum $$$P$$$ of the signaling devices in the observation stations so they are all connected (it counts as connected even if a transmission needs to pass through multiple stations).

Climate change is real, and polar bears are losing their habitats, causing them to migrate.

In the North Pole there are $$$N$$$ pillars of ice, standing in a line. As temperatures rise, some of the pillars of ice will start to melt. Now, time works differently at the North Pole, and the length of each day is $$$Q$$$ minutes.

In each of the $$$Q$$$ minutes, something will happen. During some minutes, the $$$l$$$th pillar, the $$$r$$$th pillar, and every pillar in between will shrink to $$$\lfloor {\frac{1}{x}} \rfloor$$$ of its height. In case no pillars melt in a given minute, a pizzly bear (grizzly polar bear abomination) will take the opportunity to ask you: what is the sum of the heights of the pillars in an interval?

Answer all of the pizzly bear's questions so it won't eat you.

Also, in case the new height of a pillar is a decimal, the pillar will continue melting until its height is an integer. So, there will never be any pillars with non-integer heights.

Nahida is playing a game with her fungi friends, the Aranara, on the branches of the Divine Tree in Sumeru City. On the Divine Tree, there are $$$N$$$ ($$$1 \le N \le 10^5$$$) branches. Initially, Nahida starts at branch $$$a$$$ and the Aranara starts at branch $$$b$$$. In a single turn, Nahida will move from branch $$$a$$$ to $$$nxt_a$$$, and the Aranara will move from branch $$$b$$$ to $$$nxt_b$$$. The game ends when they move to the same position, allowing Nahida to finally catch the Aranara. Unlike in the first version, $$$nxt_i \neq i$$$ is not guaranteed.

Note that Nahida and the Aranara move at the exact same time, so if in one turn Nahida is going from branch $$$1$$$ to $$$2$$$, and the Aranara is going from branch $$$2$$$ to $$$1$$$, then Nahida will not catch the Aranara.

Nahida enjoys playing games, but as the Dendro Archon, she has many duties she must attend to. Thus, she wants to know, for a given starting position $$$(a, b)$$$, if the game will go on forever or not.

Congress has a list of $$$N$$$ policies. Each policy is assigned an environmental impact score of $$$a_i$$$, which represents how much each policy benefits the environment. Help Congress determine the best policies to pass in order to protect the environment.

Congress is given $$$Q$$$ queries in the form of $$$l$$$ $$$r$$$ $$$x$$$ $$$y$$$. Define the "goodness" of a subarray $$$a_i \dots a_j$$$ ($$$1 \le i \le j \le N$$$) to be the average environmental impact score of the elements in that subarray. For each query, determine the maximum "goodness" among all subarrays $$$a_i \dots a_j$$$ whose $$$i$$$ and $$$j$$$ satisfy two constraints:

1. $$$[i, j]$$$ must be fully within the interval $$$[l, r]$$$. That is, $$$l \le i \le j \le r$$$

2. The length of the subarray must be in the range $$$[x, y]$$$. That is, $$$x \le j-i+1 \le y$$$.

For each query, output the floor of the maximum goodness.

Note that due to the large bounds, even fast solutions with an amortized complexity of around $$$O(N^2 log N)$$$ may exceed the time limit.

After finally constructing his natural park, Lazy Bob can rest. Or can he? Climate change is worsening everyday, so Bob feels like he needs to spread awareness about it!

There are $$$N$$$ different animals in Bob's natural park, each of which can be represented by two integers: $$$c_i$$$, and $$$s_i$$$. $$$i$$$ represents its index, $$$c_i$$$ represents the species of the animal, and $$$s_i$$$ represents the skill of the animal of spreading the news further.

Because Lazy Bob really hates doing work, he loves arranging awareness meetings, and animals love to attend them, too. There are free cookies—and of course, they get to meet with their friends. One day, Lazy Bob decides to ask himself: how much awareness could he spread if he arranged every possible awareness meeting?

A possible meeting is defined as some sequence of animals with consecutive indices, or in other words, a subarray of the $$$N$$$ animals. The awareness created in a possible meeting is the product of two values: the number of distinct species $$$c_i$$$ of animals at the meeting raised to the power of $$$3366$$$, and the sum of all of their skill values $$$s_i$$$.

If two animals had a meeting, and their categories were $$$[1,2]$$$ and skill values were $$$[7,12]$$$, the total awareness would be $$$2 \cdot (7+12) = 38$$$.

Because Lazy Bob is very curious, but lazy, he tasks you with finding this total awareness value. The sum can formally be written as:

$$$\sum_{i=1}^N \sum_{j=i}^N \left(\left(\sum_{k=i}^j s_k \right) \cdot f(i, j)^{3366} \right)$$$, where $$$f(i, j)$$$ is the number of distinct species, $$$c_i$$$, between indices $$$i$$$ and $$$j$$$.

Alice loves webbing through the forest, but has never been bitten by a radioactive spider, so she has decided to buy a grappling hook from the dollar store, which turns out to be very inconsistent.

The forest has $$$N$$$ trees, each a vertical line represented by two points: $$$x_i$$$ and $$$y_i$$$ from ($$$x_i, 0$$$) to ($$$x_i, y_i$$$), where all $$$x_i$$$ are distinct and all $$$y_i$$$ are distinct.

Alice's purpose is to grapple from treetop to treetop from left to right and to maximize the total area under her (she really loves being high up in the sky). When grappling between two treetops, she may not pass through any other tree, including the very top. However, her grappling hook might malfunction, but only when she is on a point on the original optimal path.

You are also given a number $$$K$$$, which is either $$$1$$$ or $$$2$$$. If $$$K = 1$$$, find the maximum area if the optimal path is taken with no errors. If $$$K = 2$$$, find the area if the optimal path is taken, but whenever Alice is at a point on the original optimal path, the grappling hook misses in the worst way possible for the total area (if there is no way to miss, e.g. the next point is also in the original optimal path, the grappling hook will work normally).