We can divide the dominoes into two types:

• Horizontal dominoes. A domino is horizontal if and only if it consists of tiles that are on the same row.
• Vertical dominoes. A domino is vertical if and only if it consists of tiles that are on the same column.

For an arbitrary tile in the grid that is not on the rightmost column, the integer in it is always exactly $$$1$$$ less than the integer in the tile that is directly to the right of it. So we can see that all possible horizontal dominoes are always tight.

For an arbitrary tile in the grid that is not on the bottommost row, the integer in it is always exactly $$$M$$$ less than the integer in the tile that is directly to the bottom of it. So we can see that all possible vertical dominoes are tight if and only if $$$M=1$$$.

We can calculate that there are $$$N \times (M-1)$$$ horizontal dominoes and $$$(N-1) \times M$$$ vertical dominoes.

Therefore, we can get the following solution:

• If $$$M > 1$$$, then there are $$$N \times (M-1)$$$ tight dominoes.
• If $$$M = 1$$$, then there are $$$N-1$$$ tight dominoes.

Time complexity: $$$O(1)$$$

For a team of $$$c$$$ players with a biggest power of $$$b$$$, the total power of the team is $$$b \times c$$$. So for a team with a biggest power of $$$b$$$ to win, it needs to have at least $$$\lceil \frac{D+1}{b} \rceil$$$ players.

For each player $$$i$$$, we can calculate a value $$$f(i)$$$ which means a team that has player $$$i$$$ as its biggest power needs to have at least $$$f(i)$$$ players to win. We can see that the bigger the value of $$$P_i$$$, the smaller the value of $$$f(i)$$$.

We can also see that if a formed team is said to have a fixed biggest power and a fixed number of players, the powers of the players that are less than the biggest power do not affect the total power of the team. So those players can be anyone.

Using the above informations, we can form the teams using a greedy method. We iterate through each candidate player starting from the biggest $$$P_i$$$ and form new teams with each next biggest candidate player as its biggest power. We do that while maintaining the total number of extra players required to make all formed teams win. We stop once the number of remaining players is not enough for the total number of extra players required.

Time complexity: $$$O(N \log N)$$$

Let's represent the mirror as a circle with $$$N$$$ points at the circumference. First, one should notice that a circumscribed triangle (triangle whose vertices lie on the circumference of a circle) is a right triangle if only if one side of the triangle is the diameter of the circle. That means, for a single colour, there exists a right triangle with this colour if and only if both of the following conditions are satisfied:

• There exists two diametrically opposite points with this colour.
• This colour occurs in $$$3$$$ or more points.

Let's call a pair of diametrically opposite points as a diameter pair. From the above information, we can see that if we colour the points in a diameter pair with the same colour, all other points must not have that colour. If that condition is satisfied for all diameter pairs, there cannot be a right triangle with the same colour.

Let's find the number of diameter pairs in the circle and the number of points that do not belong to a diameter pair. Let the two values be $$$cntPair$$$ and $$$cntAlone$$$. One can find $$$cntPair$$$ and $$$cntAlone$$$ with two pointers or binary search using the prefix sum of the array $$$D$$$.

To find the number of colouring configurations, we can iterate $$$i$$$ from $$$0$$$ to $$$\min(cntPair, M)$$$. In each iteration, we calculate the number of configurations that have exactly $$$i$$$ diameter pairs with the same colour on both of its points. It is calculated as follows:

• There are $$$\binom{cntPair}{i}$$$ ways to choose which diameter pairs have the same colour.
• Notice that each diameter pair with the same colour must have a different colour from each other. So there are $$$\binom{M}{i} \times i!$$$ ways to choose which colour is assigned to each diameter pair with the same colour.
• There are only $$$M-i$$$ available colours for colouring the remaining points. Each diameter pair with different colours can be coloured in $$$(M-i) \times (M-i-1)$$$ ways and each of the remaining points can be coloured in $$$M-i$$$ ways.
• So the total number of ways is: \begin{align} \binom{cntPair}{i} \times \binom{M}{i} \times i! \times ((M-i) \times (M-i-1))^{cntPair-i} \times (M-i)^{cntAlone} \end{align}

Time complexity: $$$O((N+M) \log N)$$$

Define an array as distinctable if and only if Pak Chanek can do zero or more operations to make the elements of the array different from each other. Finding a sortable array $$$A$$$ of size $$$N$$$ with the minimum possible sum of elements is the same as finding a distinctable array $$$A$$$ of size $$$N$$$ with the minimum possible sum and permuting its elements.

Define a value $$$k'$$$ as being reachable from a value $$$k$$$ if and only if we can do zero or more operations to the value $$$k$$$ to turn it into $$$k'$$$.

To construct a distinctable array of size $$$N$$$ with the minimum possible sum, we can do a greedy method. Initially, the array $$$A$$$ is empty. Then, do the following iteration multiple times sequentially for each value $$$k$$$ from $$$1$$$, $$$2$$$, $$$3$$$, and so on until $$$A$$$ has $$$N$$$ elements:

1. Consider each value $$$k'$$$ that is reachable from $$$k$$$.
2. Let's say there are $$$w$$$ values $$$k'$$$ that has not been used as the final value for each of the previous elements of $$$A$$$.
3. Append $$$w$$$ new elements with value $$$k$$$ to $$$A$$$ and assign the final value for each of the new elements with each of the usable values of $$$k'$$$.
4. In the case where appending $$$w$$$ new elements makes the size of $$$A$$$ exceed $$$N$$$, we choose only some of the usable values of $$$k'$$$ to make the size of $$$A$$$ exactly $$$N$$$.

Notice that while choosing the final values for each value $$$k$$$, there is only one way to do it for each iteration except the last iteration. For the last iteration, it can be obtained that in order to get the lexicographically minimum array, we choose the usable final values that are the largest ones.

It can be obtained that each value that is reachable from $$$k$$$ is in the form of $$$x \times 2^y$$$ for some positive integer $$$x$$$ and some non-negative integer $$$y$$$ satisfying $$$x+y=k$$$.

For a pair $$$(x, y)$$$, if we choose an even integer for $$$x$$$, we can always find another pair $$$(x_2, y_2)$$$ such that $$$x_2 \times 2^{y_2} = x \times 2^y$$$ and $$$x_2+y_2 \leq x+y$$$. From the logic of the greedy method, we can see that choosing an even integer for $$$x$$$ is always not optimal.

For two distinct pairs $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, if both $$$x_1$$$ and $$$x_2$$$ are odd, then $$$x_1 \times 2^{y_1} \neq x_2 \times 2^{y_2}$$$ always holds.

Using the above knowledge, we can see that during the greedy method, the usable final values for a value $$$k$$$ are all the ones with odd values of $$$x$$$, which there are $$$\lceil \frac{k}{2} \rceil$$$ of them. From this, we can see that in our greedy method, we only do $$$O(\sqrt N)$$$ iterations. So, we can get the sum of elements in our constructed array $$$A$$$ in $$$O(\sqrt N)$$$.

To answer each query, we need to find the $$$P_i$$$-th smallest final value in the array and find which value produces it.

We can construct an array $$$F_0, F_1, F_2, \ldots$$$ of size $$$O(\sqrt N)$$$. This means for each $$$i$$$, there are $$$F_i$$$ values $$$x \times 2^y$$$ with $$$y=i$$$, namely the ones with the values of $$$x$$$ being the $$$F_i$$$ smallest positive odd integers.

We can convert each value $$$x \times 2^y$$$ into $$$x' \times 2^{y'}$$$ such that all values of $$$x'$$$ have the same MSB (Most Significant Bit). After converting, sorting the values $$$x' \times 2^{y'}$$$ is the same as sorting the pairs $$$(y', x')$$$.

We can construct a two-dimensional array $$$G$$$ of size $$$O(\sqrt N) \times O(\log N)$$$ with $$$G_{i,j}$$$ representing the number of final values with $$$y' = i$$$ and $$$y = i-j$$$.

To find the $$$P_i$$$-th smallest final value, firstly we find its value of $$$y'$$$ with binary search using array $$$G$$$.

Now, for some integer $$$d$$$, we need to find the $$$d$$$-th smallest value of $$$x'$$$ for all final values with a certain value of $$$y'$$$. To find it, we do a binary search on a value $$$m$$$ with each iteration checking whether there are at least $$$d$$$ values of $$$x'$$$ that are less than or equal to $$$m$$$. Each iteration of the binary search can be computed by iterating $$$O(\log N)$$$ values in $$$G$$$ and using simple math.

To find which value produces a certain final value, we just convert it back into $$$x \times 2^y$$$ and find the value of $$$x+y$$$.

Time complexity: $$$O(\sqrt N \log N + Q \log^2N)$$$

Challenge: find the solution for $$$N \leq 10^{18}$$$.

Note that $$$\sum_x \sum_y \sum_z f(x,y,z) \times g(x,y,z)$$$ can be alternatively expressed as the following:

• Iterate through every edge $$$e$$$ and every prime $$$p$$$.
• In each iteration, consider the set of vertices $$$S = {x \mid A_x \text{ is divisible by } p}$$$. Count how many triplets $$$a,b,c \in S$$$ such that each of the two components separated by $$$e$$$ contains at least one of $$$a,b,c$$$.
• Calculate the sum of those values for all possible $$$e$$$ and $$$p$$$.

Note that if we root the tree and consider the edge $$$(x,y)$$$ where $$$x$$$ is the parent of $$$y$$$ in the rooted tree, then the number of triplets we count in one iteration is equivalent to $$$\binom{|S|}{3} - \binom{s}{3} - \binom{|S|-s}{3}$$$, where $$$s$$$ is the number of vertices in $$$S$$$ in the subtree of $$$y$$$.

To calculate the answer, we can iterate through each prime $$$p$$$. For each prime, we only consider the vertices in $$$S$$$. We can build a sparse representation of a tree containing the vertices in $$$S$$$ (i.e. a virtual/auxiliary tree). More precisely, we only consider a set of vertices $$$S'$$$, where $$$x \in S'$$$ if and only if $$$x \in S$$$ or there exists $$$y,z \in S$$$ such that $$$\text{LCA}(y,z) = x$$$ (here, $$$\text{LCA}$$$ denotes the lowest common ancestor). It can be shown that $$$|S'| \leq 2|S|$$$. Each edge in the sparse tree connecting two vertices in $$$S'$$$ is a simple ancestor-descendant path consisting of one or more edges of the original tree.

Notice that the number of triplets we count for each edge in the original tree that is not used in the sparse tree is always $$$0$$$. Also, for the edges in the original tree that make up a single edge of the sparse tree, the number of triplets we count for each of them is the same.

Therefore, using the sparse tree we built, we can run a simple dynamic programming to count the answer for a single prime $$$p$$$.

Notice that there are at most $$$\log A_x$$$ distinct prime factors of $$$A_x$$$, so the sum of $$$|S|$$$ is $$$O(N \log \max(A))$$$.

Time complexity: $$$O(N \log N \log \max(A))$$$ or $$$O(N \log \max(A))$$$

Let's consider some value of $$$W_j$$$. Let $$$b$$$ be the LSB (Least Significant Bit) of $$$W_j$$$. Which means $$$b$$$ is the minimum number such that the bit in index $$$b$$$ in the binary representation of $$$W_j$$$ is active. Note: the bits are indexed from $$$0$$$ from the right.

For a sequence of operations, define $$$\text{dis}(i)$$$ as how many tiles to the east the final positions of the contestants in row $$$i$$$ compared to their initial position. Specifically, if their final positions are more to the west, then $$$\text{dis}(i)$$$ is negative.

Notice that each move we make must be a distance that is a multiple of $$$2^b$$$. Because if we move a distance that is not a multiple of $$$2^b$$$, at least one of the bits with indices smaller than $$$b$$$ will be activated, which we do not want. This means $$$\text{dis}(i)$$$ must be a multiple of $$$2^b$$$.

However, we can make each $$$\text{dis}(i)$$$ to be any integer that is a multiple of $$$2^b$$$ while making $$$Z = W_j$$$ by doing the following strategy:

1. Only do moves with distances of exactly $$$2^b$$$ to move the contestants in each row to their final positions.
2. Move one row with a distance of $$$W_j$$$ to the east, then to the west.

Using the above knowledge, we can see that for each row $$$i$$$, there are three cases:

• If $$$R_i-L_i+1 \geq 2^b$$$, then each column can be occupied.
• Else, if $$$L_i \mod 2^b \leq R_i \mod 2^b$$$, then only each column $$$c$$$ such that $$$L_i \mod 2^b \leq c \mod 2^b \leq R_i \mod 2^b$$$ can be occupied.
• Else, then only each column $$$c$$$ such that $$$L_i \mod 2^b \leq c \mod 2^b$$$ or $$$c \mod 2^b \leq R_i \mod 2^b$$$ can be occupied.

We can see that each row has at most two subsegments of the segment $$$[0, 2^b-1]$$$ denoting the occupiable columns modulo $$$2^b$$$. Now we just need to find the position that intersects the most subsegments. To solve this, we can use line sweep.

To handle the $$$Q$$$ queries, notice that the number of possible distinct values for the LSB of $$$W_j$$$ are only $$$\lfloor \log_2 10^9 \rfloor + 1 = 30$$$. So we can precompute the answer for each of the $$$30$$$ possible LSB, then answer the queries using the precomputed answers.

Time complexity: $$$O(N\log N \log MAXW + Q \log MAXW)$$$.

Let $$$c$$$ be the bottom side of the right triangle (the side that is not $$$a$$$ or $$$b$$$). From Pythagorean theorem, we know that $$$a^2+c^2 = b^2$$$, so $$$c^2 =b^2-a^2$$$.

We can see that the area of the square at the bottom is $$$c^2$$$. So an integer is appropriate if and only if it can be expressed as $$$b^2-a^2$$$ for some positive integers $$$a$$$ and $$$b$$$ ($$$a<b$$$).

Consider the case if $$$b=a+1$$$. Then $$$b^2-a^2 = (a+1)^2-a^2 = a^2+2a+1-a^2 = 2a+1$$$. Since $$$a$$$ must be a positive integer, then all possible results for this case are all odd integers that are greater than or equal to $$$3$$$.

Consider the case if $$$b=a+2$$$. Then $$$b^2-a^2 = (a+2)^2-a^2 = a^2+4a+4-a^2 = 4a+4$$$. Since $$$a$$$ must be a positive integer, then all possible results for this case are all integers that are multiples of $$$4$$$ that are greater than or equal to $$$8$$$.

Let's consider an integer that has a remainder of $$$2$$$ when divided by $$$4$$$. We can get that such an integer can never be expressed as $$$b^2-a^2$$$. This is because of the fact that any square number when divided by $$$4$$$ must have a remainder of either $$$0$$$ or $$$1$$$.

Using a simple brute force, we can get that $$$1$$$ and $$$4$$$ cannot be expressed as $$$b^2-a^2$$$.

Using all of the above informations, we can see that all appropriate numbers are only all odd integers that are greater than or equal to $$$3$$$ and all integers that are multiples of $$$4$$$ that are greater than or equal to $$$8$$$.

In order to find the $$$N$$$-th smallest appropriate number, we can do a binary search on a value $$$d$$$. In each iteration of the binary search, we check whether there are at least $$$N$$$ appropriate numbers that are less than or equal to $$$d$$$.

Alternatively, we can use a mathematical formula to find the $$$N$$$-th smallest appropriate number in $$$O(1)$$$ time complexity.

Time Complexity: $$$O(\log N)$$$ or $$$O(1)$$$

Notice that $$$10 \equiv 1 \mod 3$$$. Hence, if $$$k$$$ denotes the number of digits in $$$A_j$$$, $$$\text{concat}(A_i, A_j) \mod 3= (A_i \times 10^k + A_j) \mod 3 = (A_i \times 1^k + A_j) \mod 3 = (A_i + A_j) \mod 3$$$.

Then one can simplify the equation that determines the reaction of stone $$$i$$$ and stone $$$j$$$ as follows. \begin{align} \text{concat}(A_i, A_j) \times \text{concat}(A_j, A_i) + A_i A_j & \equiv Z \mod 3 \ (A_i + A_j) (A_i + A_j) + A_i A_j & \equiv Z \mod 3 \ A_i^2 + 2 A_i A_j + A_j^2 + A_i A_j & \equiv Z \mod 3 \ A_i^2 + A_j^2 + 3 A_i A_j & \equiv Z \mod 3 \ A_i^2 + A_j^2 & \equiv Z \mod 3 \ \end{align}

One can see that:

• $$$0^2 = 0 \equiv 0 \mod 3$$$.
• $$$1^2 = 1 \equiv 1 \mod 3$$$.
• $$$2^2 = 4 \equiv 1 \mod 3$$$.

So the value of $$$A_i^2 \mod 3$$$ is either $$$0$$$ or $$$1$$$.

We can get a construction that consists of the two following cases:

• If there are at least $$$\frac{N}{2}$$$ stones having $$$A_i^2 \equiv 0 \mod 3$$$, then we can colour the stones such that one of the colours only occurs in all stones with $$$A_i^2 \equiv 0 \mod 3$$$. In this construction, there is no pair of stones with different colours that both have $$$A_i^2 \equiv 1 \mod 3$$$. So we can assign $$$Z=2$$$.
• If there are less than $$$\frac{N}{2}$$$ stones having $$$A_i^2 \equiv 0 \mod 3$$$, then there are at least $$$\frac{N}{2}$$$ stones having $$$A_i^2 \equiv 1 \mod 3$$$, so we can colour the stones such that one of the colours only occurs in all stones with $$$A_i^2 \equiv 1 \mod 3$$$. In this construction, there is no pair of stones with different colours that both have $$$A_i^2 \equiv 0 \mod 3$$$. So we can assign $$$Z=0$$$.

Time complexity: $$$O(N)$$$

Let's say we have two graphs, each having $$$N$$$ vertices. Initially, there are no edges. We want to make the first graph into a graph that satisfies the condition of the problem and make the second graph into the key tree with a weight assignment that corresponds to the first graph.

Sequentially for each $$$k$$$ from $$$1$$$ to $$$2N-2$$$, do all of the following:

• Add an edge with weight $$$k$$$ to the first graph.
• Choose one of the following:
  • Add an edge with weight $$$k$$$ to the second graph.
  • Do nothing.

In order to make the second graph into the key tree, we must add exactly $$$N-1$$$ edges to it throughout the process and the $$$i$$$-th edge added is edge $$$i$$$ of the key tree.

In an iteration, if we choose to not add an edge to the second graph, it can be obtained that the edge added to the first graph must not merge any biconnected components. Let's call this type of edge in the first graph an idle edge.

Otherwise, if we choose to add an edge to the second graph, it can be obtained that the following must be satisfied:

• Let $$$c_1$$$ and $$$c_2$$$ be the connected components of the second graph that are merged by adding the new edge.
• The edge added to the first graph must merge exactly two biconnected components, each of them containing vertices with the same indices as the ones in each of $$$c_1$$$ and $$$c_2$$$.
• Let's call this type of edge in the first graph a connector edge. We can see that there must be exactly $$$N-1$$$ connector edges in the first graph.

The only way to make it such that adding an edge connects exactly two biconnected components is to already have exactly one existing edge connecting the two biconnected components. Let's call this type of existing edge a helper edge.

It can be obtained that an edge cannot be a helper edge of more than one connector edge. Because we only have $$$2N-2$$$ edges for the first graph, those edges must only consist of $$$N-1$$$ connector edges and $$$N-1$$$ helper edges. This means all helper edges must be idle edges. But it can be obtained that it always holds.

The $$$i$$$-th connector edge and its corresponding helper edge must connect the two biconnected components that correspond to the two connected components merged using edge $$$i$$$ of the key tree. If the sizes of the connected components are $$$s_1$$$ and $$$s_2$$$, then there are $$$(s_1 \times s_2)^2$$$ possible pairs of connector and helper edges.

The number of ways to choose which edge to add in each iteration is the same as the number of ways to colour a sequence of $$$2N-2$$$ elements with $$$N-1$$$ colours (numbered from $$$1$$$ to $$$N-1$$$) such that:

• Each colour occurs in exactly $$$2$$$ elements.
• For each pair of colours $$$(i, j)$$$, if $$$i<j$$$, then the latest element with colour $$$i$$$ must occur earlier than the latest element with colour $$$j$$$.

We can see that the number of ways is $$$\frac{(2N-2)!}{(2!)^{N-1}\times (N-1)!}$$$. To get the answer to the problem, we just multiply this value by each of the $$$(s_1 \times s_2)^2$$$ for each merged pair of connected components in the key tree.

Time complexity: $$$O(N)$$$