In a faraway school early in the morning. The school manager asked the $$$n$$$ students to line up in a row at the top of the wall.

They lined up one after the other according to the time of their arrival. Each student has a length of $$$h_i$$$ centimeters.

Meanwhile, there was a student named Levi who was angry because he was the shortest among the students. When he was asked about the reason for his anger, it became clear that he did not want to be the shortest person between the person in front of him and the person behind him.

The manager decided to make everyone happy without changing their places, by removing stones below any student, or even by adding stones under any student. Each stone is only one centimeter long, so when a stone is added, the person becomes one centimeter taller, and vice versa when removed.

Adding a stone anywhere costs $$$x$$$ energy units, and removing a stone anywhere costs $$$y$$$ energy units.

You can consider the length of the wall to be infinite and you can remove any amount of stones you want.

You can consider that the first and last students are always happy.

You need to find the minimum cost to make all students happy.

Shaaban found the contestants eager to participate in the competition and solve educational problems, so he wanted to disappoint everyone and give them the following problem.

You are given a tree consisting of $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. You need to add the minimum number of vertices to the tree such that the following conditions are satisfied after all additions:

• the graph must still be a tree;
• the longest path in the tree must consist of an even number of vertices;
• there must be exactly $$$k$$$ distinct such longest paths.

Two paths are considered different if there exists at least one vertex which belongs to exactly one of the two paths.

Print the minimum number of vertices you have to add, then print the edges you added.

Given an array of integers $$$a$$$ of length $$$n$$$. Let's say that segment $$$[l,r]$$$ is $$$i$$$-$$$th \: good$$$ if:

• $$$1 \leq l \leq i \leq r \leq n$$$;
• $$$ a_{l}\, \& \, a_{l+1} \, \& \, ... \, a_{i} \, \& \, ... \, a_{r-1} \, \& \,a_{r}\, =\, a_{i}$$$.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, count all segments which are $$$i$$$-$$$th \: good$$$.

Here $$$\&$$$ denotes the bitwise AND operation.

Mouf, a little penguin from Aleppo, dreamed of sunny beaches and coconuts. One day, his penguin companions created a challenge for him to unravel, with a ticket to their island awaiting as the reward.

Mouf was given an array of integers $$$a$$$ of length $$$n$$$. Mouf's companions consider a pair of indices $$$\langle i, j \rangle$$$ $$$(1 \le i \lt j \le n)$$$ $$$\it{coconut}$$$ if there exists positive integers $$$x$$$ and $$$y$$$ such that:

• $$$a_i = \dfrac{x^2}{y}$$$;
• $$$a_j = \dfrac{y^2}{x}$$$.

Help Mouf find the number of $$$\it{coconut}$$$ pairs in the array $$$a$$$ to win a trip to the magical island and enjoy sunny days and coconut feasts with his companions.

Fouad has just moved to a new city that contains $$$n$$$ houses and $$$m$$$ schools. In this problem, the city is represented as an infinite $$$2D$$$ plane, with both the schools and the houses represented as lattice points$$$^\dagger$$$ on this plane. Being a lazy person, Fouad wants to choose exactly one house and exactly one school in such a way that minimizes the Manhattan distance$$$^\ddagger$$$ between them. Please help him calculate the minimum Manhattan distance between any of the $$$n$$$ houses and any of the $$$m$$$ schools.

$$$^\dagger$$$ A lattice point is a point $$$p = (x, y)$$$ with integer coordinates $$$x$$$ and $$$y$$$.

$$$^\ddagger$$$ The Manhattan distance between two points $$$p_1 = (x_1, y_1)$$$ and $$$p_2 = (x_2, y_2)$$$ is equal to: $$$$$$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|$$$$$$

After a long ACPC contest, Mouf could finally buy a new Yu-Gi-Oh structure deck "Fire Kings". He was amazed by how strong this deck is, and now he is ready to duel with Jack Atlas, The Crimson King.

However, during the duel, Mouf found a little problem. Calculating the damage he inflicted on Jack is very complicated as Fire Kings monsters are burning the field! Mouf has $$$n$$$ monsters on the field, and each of them has the following five parameters:

Level $$$l$$$, strength $$$s$$$, developing rate $$$x$$$, damage suppression $$$ds$$$, and $$$t$$$, the number of turns it will remain on the field before it will be destroyed.

Every monster will do the following until the end of the $$$t_{th}$$$ turn, respectively:

• It attacks Jack, causing $$$l \cdot s$$$ damage to him. But the attack will not disappear; instead, it will last until the $$$t_{th}$$$ turn and continue burning Jack every turn by $$$\left (\frac{l \cdot s}{ds^{tt}} \right)$$$, where $$$tt$$$ is the number of turns that have passed since the attack time.

• The level of the monster will increase by $$$x$$$.

It took Mouf a few minutes to calculate damage fast, and now he is challenging you -yes, you bot! For every monster given in the input, output the total damage it causes during all $$$t$$$ turns modulo $$$10^9+7$$$.

For an array $$$a$$$, let's define the function $$$f(a)$$$ as the sum of the bitwise XOR sum of each non-empty subsequence$$$^\dagger$$$ of it.

For example, if $$$a$$$ = $$$[5 , 2 , 4]$$$, then $$$f(a) = (5 \oplus 2 \oplus 4) + (5 \oplus 2) + (5 \oplus 4) + (2 \oplus 4) + 5 + 2 + 4$$$.

Let's define an array of arrays $$$A$$$, which contains all non-empty subsequences$$$^\dagger$$$ of the array $$$a$$$.

You are given an array of $$$a$$$ of length $$$n$$$. You have to process the following $$$q$$$ updates:

• given and index $$$i$$$ and a value $$$x$$$, set $$$a_i := x$$$;
• print the value of $$$\displaystyle\sum_{s \in A} f(s)$$$.

Since this value could be too large, find it modulo $$$10^9 + 7$$$.

Here $$$\oplus$$$ denotes the bitwise XOR operation.

$$$\dagger$$$ A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) elements. For example, $$$[3,1]$$$ is a subsequence of $$$[3,2,1]$$$ and $$$[4,3,1]$$$, but not a subsequence of $$$[1,3,3,7]$$$ and $$$[3,10,4]$$$.

Besher and his wife are playing a game on $$$n$$$ piles of stones, each one contains $$$a_i$$$ stones. On each player's turn, they can do one of these actions:

• choose $$$1$$$ non-empty pile and take $$$1$$$ stone from it.
• choose $$$3$$$ non-empty piles of same parity of numbers of stones and take $$$1$$$ stone from each of them.

The first player who is unable to make a move loses (all piles are empty).

Given that Besher goes first, who will win the game if both players play optimally?

Our lovely judge Fofo loves "bitset" very much, and when the judges were discussing the problems to be put in this contest, he sometimes heard the word "bitset" being mentioned.

As he loves "bitset" very much, he usually says his favorite word "7as" when the solution includes "bitset" as a substring$$$^\dagger$$$, and when he does not find "bitset", he gets sad and says "no 7as for you today".

Fofo wants to automate this procedure, so can you help him do that?

$$$\dagger$$$ A string $$$t$$$ is a substring of another string $$$s$$$ if you can obtain $$$t$$$ from $$$s$$$ by deleting (several, maybe $$$0$$$) characters from the beginning of $$$s$$$ and deleting (several, maybe $$$0$$$) characters from the end of $$$s$$$.

In this problem, you are given $$$2$$$ points describing a square (i.e. the upper right and lower left corners) such that the sides of the square are parallel to either $$$x$$$-axis and $$$y$$$-axis.

You are also given $$$n$$$ segments such that each segment is strictly inside the square and parallel to one of the axes.

You need to find whether there exist two segments $$$i$$$ and $$$j$$$ ($$$i \neq j$$$) such that if both were extended to a line, they divide the square into multiple rectangles, where only two of them are equal$$$^\dagger$$$.

$$$^\dagger$$$ Two rectangles are considered equal if their sides are equal apart from the vertical or horizontal alignment.

There are $$$n$$$ water tanks, each one liter in size. Water tanks are connected by pipes, where a pipe connects tank $$$v$$$ to parent tank $$$p_v$$$. Tank $$$1$$$ is the root.

Let's define the process of filling water tank $$$v$$$ with $$$x$$$ liters as follows:

• water fills tank $$$v$$$ with one liter;
• if there's more water left, then while there are unfilled child tanks, water flows in the direction of the smallest (i.e., by index) tank and repeats the same process;
• if there's more water left, it goes up and starts filling the parent tank with the same process.

Here are some examples of the process described above:

filling tank 5 with 2 liters	filling tank 6 with 4 liters

Given $$$q$$$ queries of the form $$$(v, x, u)$$$, you should answer the following task:

If $$$x$$$ liters are added to tank $$$v$$$, will tank $$$u$$$ be filled as well?

Given an integer $$$n \ge 3$$$, determine if there exists a non-self-intersecting$$$^\dagger$$$ polygon with $$$n$$$ distinct vertices of integer coordinates such that:

• no three consecutive vertices of the polygon are collinear;
• all $$$n$$$ sides are equal.

In case such a polygon exists, provide a construction.

$$$^\dagger$$$ A polygon with $$$n$$$ distinct vertices is non-self-intersecting if no two distinct sides intersect except in the vertices.

Given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ where $$$|a_i| = 1$$$ for each index $$$i$$$ $$$(1 \le i \le n)$$$, and two integers $$$l$$$ and $$$r$$$ $$$(l \le r)$$$.

We have a real-valued function $$$f$$$ defined as follows:

$$$$$$f(x) = \sum_{i=1}^{n} |a_i \cdot x + b_i|.$$$$$$

Suppose we randomly pick a real value $$$m$$$ in the range $$$(l \le m \le r)$$$. What is the probability that $$$f(m)$$$ equals the minimum value of $$$f$$$ in the given range $$$[l, r]$$$. More formally,

$$$$$$f(m) = \displaystyle\min_{l \le x \le r} f(x).$$$$$$

Given an integer $$$x$$$. Find the smallest integer $$$y$$$ that satisfy the following:

• $$$y \gt x$$$
• $$$string(y) \lt string(x)$$$

Here, $$$string(x)$$$ is the decimal representation of $$$x$$$ (without leading zeros) as a string.

Strings are compared lexicographically$$$^\dagger$$$. For example,

• $$$string(1111) \lt string(123)$$$;
• $$$string(123456789) \lt string(9)$$$;
• $$$string(33) \lt string(333)$$$.

If such an integer $$$y$$$ does not exist, print $$$-1$$$.

$$$^\dagger$$$ A string $$$s$$$ is lexicographically larger than a string $$$t$$$ if and only if one of the following holds:

• $$$t$$$ is a prefix of $$$s$$$, but $$$s \neq t$$$;
• in the first position where $$$s$$$ and $$$t$$$ differ, the string $$$s$$$ has a larger character (digit) than the corresponding character (digit) in $$$t$$$.