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)$$$.

Try to simplify graph $$$H$$$.

Look at strongly connected components of $$$G$$$, and what happens with them.

Use dp to find the answer.

The main observation is what $$$H$$$ looks like. All the strongly connected components (SCC) in $$$G$$$ will become fully connected subgraphs in $$$H$$$. Secondly, take any two vertices $$$a$$$ and $$$b$$$ such that $$$a$$$ and $$$b$$$ are not in the same SCC. We can let $$$S_a$$$ be a set of vertices that are in the same SCC as $$$a$$$ ($$$a$$$ included). Similarly, $$$S_b$$$ is a set of vertices that are in the same SCC as $$$b$$$. If there is an edge going from $$$a$$$ to $$$b$$$, then for any two vertices $$$x$$$ and $$$y$$$ such that $$$x$$$ belongs to $$$S_a$$$ and $$$y$$$ belongs to $$$S_b$$$, there is an edge going from $$$x$$$ to $$$y$$$. Both of the previously stated facts about the graph can be proven by induction.

Now, let's say that there is the longest path that goes through at least one vertex of an SCC. Then that path goes through all the vertices in the SCC, due to all vertices in SCC being connected to the same vertices outside the SCC and due to the fact that SCC is a complete subgraph.

Now we can construct the graph $$$H'$$$. Each of the SCCs from $$$H$$$ will be a vertex in $$$H'$$$. The number on the vertex will be equal to the sum of all numbers on the vertices of the SCC that it was constructed from. Edges between two new vertexes will be added if there was an edge between their original SCCs. The edge will have a weight equal to the size of the SCC that it is going into. An additional vertex will be added at index $$$0$$$ and an edge will be made between it and all other vertices with $$$0$$$ ingoing edges. Weight will be determined based on the size of the SCC of the vertex that the edge is going into.

Due to the previous observations, the answer for the $$$H'$$$ will be the same as the answer for the $$$H$$$. However, notice that $$$H'$$$ is a DAG. That means that the answer for it can be computed using DP after topological ordering.

Total time and memory complexity is $$$O(N)$$$.