Assume that cells $$$i-1$$$, $$$i$$$ and $$$i+1$$$ are covered in water. What happens if you remove water from cell $$$i$$$?

The water at position $$$i$$$ is replaced as both cells $$$i-1$$$ and $$$i+1$$$ have water in them.

Read the hints.

If there are 3 consecutive empty cells $$$i-1$$$, $$$i$$$, $$$i+1$$$, we can place water in cells $$$i-1$$$ and $$$i+1$$$ and then move water from cell $$$i$$$ to all other cells. If there are no such cells, we have to place water on every empty cell.

So if we find substring ''...'' in the array, the answer is $$$2$$$, otherwise the answer is the number of empty cells.

Check if only digits $$$1$$$ can remain. The situation is similar for checking if only digits $$$2$$$ or only digits $$$3$$$ can remain.

Try to find something that stays the same after each operation.

Look at the parity of the numbers.

The parity of each number changes after an operation. That means that if $$$2$$$ numbers have the same parity, they will always have the same parity. If they had different parity, their parities stay different.

Read the hints.

If the parity of $$$b$$$ and $$$c$$$ is not the same, then it is impossible for only digits $$$1$$$ to remain on the board, as it would require $$$b = c = 0$$$. Otherwise, the following construction will leave only digits $$$1$$$ on the board.

First remove digits $$$2$$$ and $$$3$$$ and write digit $$$1$$$ while $$$b>0$$$ and $$$c>0$$$. If $$$b=c$$$, then we are done. Otherwise, without loss of generality assume $$$b>c$$$. That means that after the operations $$$c=0$$$ and $$$b$$$ is even (Because $$$b$$$ and $$$c$$$ are the same parity). Now we perform the following $$$2$$$ operations $$$\frac{b}{2}$$$ times to get only digits $$$1$$$ left. Remove digits $$$1$$$ and $$$2$$$ and add digit $$$3$$$. After that remove digits $$$2$$$ and $$$3$$$ and add digit $$$1$$$. An effective change of these $$$2$$$ operations is the reduction of $$$b$$$ by $$$2$$$.

Solve the problem if all of the characters on vertices are 'U'.

We can run DFS from the root. Using it we can calculate the number of vertices that we have to traverse to get to every edge. Just output the smallest value among all the leaves.

Modify the DFS such that it takes into account that traversing some edges does not require an operation.

Add weights to the edges.

Read the hints.

We will make edges from a vertex to its children. The weight of that edge will be $$$1$$$, unless one of the following holds:

• The weight of an edge between a vertex and its left child will be $$$0$$$ if the letter written on that vertex is 'L'.

• The weight of an edge between a vertex and its right child will be $$$0$$$ if the letter written on that vertex is 'R'.

Now we run a modified DFS to find the distance of each vertex from the root, but with weighted edges. We output the minimal value among all the leaves.

Let $$$m$$$ be the biggest value in the array. Calculate array $$$x$$$ such that $$$x_i$$$ ($$$1 \le i \le m$$$) is the number of triples which have $$$\gcd$$$ of $$$i$$$. Then the answer is the sum of $$$i /cdot x_i$$$ over all $$$i$$$ ($$$1 \le i \le m$$$).

Value of $$$\lfloor \frac{M}{1} \rfloor + \lfloor \frac{M}{2} \rfloor + \lfloor \frac{M}{3} \rfloor + \ldots + \lfloor \frac{M}{M} \rfloor$$$ is around $$$M log M$$$.

We calculate $$$x_i$$$ from $$$x_m$$$ to $$$x_1$$$. For some $$$i$$$, we can first calculate the number of triples that have a value of function $$$f$$$ that is an integer multiple of $$$i$$$, and then from it subtract $$$x_{2i}, x_{3i}, x_{4i} \ldots$$$. Because of previous hint, the subtractions will be quite fast.

Now the question is how to calculate the number of triples that have value of function $$$f$$$ that is an integer multiple of $$$i$$$.

Number up to $$$100/,000$$$ can have at most $$$128$$$ divisors.

As the order in which numbers are given does not matter, we can sort the array. Now for each number $$$d$$$ ($$$1 \le d \le M$$$) store indicies of all numbers that are divisble by $$$d$$$ in an array of vectors. Now we will for each number $$$d$$$ ($$$1 \le d \le M$$$) count the number of triples.

To find the number of triples that have gcd value that is an integer multiple of $$$d$$$, we can do the following. We go over the index of the number that will be value $$$b$$$ in the function. We can utilize the vectors we calculated in previous step for that. Say that current index is $$$i$$$. Then for value $$$c$$$ we can pick any number with index larger than $$$i$$$ as the array is sorted. For value $$$a$$$, we can pick any of the numbers divisible by $$$d$$$ with index less than $$$i$$$, the number of which we can get from the vector. By multiplying those $$$2$$$ numbers we get the number of triples that have $$$a_i$$$ as their middle value.

As numbers can have up to $$$128$$$ divisors, the step above is quite fast.

Total time complexity is $$$O(M log M + N log N + 128 /cdot N)$$$. Total memory complexity is $$$O(M + 128 /cdot N)$$$.