To solve this problem, notice that the sides of the Elijah's rectangle don't matter, only the area is considered. So he can use any number of squares to create a rectangle of size C × nC for any positive integer n.

The optimal n is the result of the division AB / C² rounded either up or down. So we just check two variants and choose the better one. Additionally, it is important to remember that n > 0, so sometimes it is impossible to round down.

First notice, that we can make inversions only in one string. Also notice that the order of inversions doesn't matter.

So the solution is greedy: consider characters of the first string from left to right. If the corresponding character s₁[i] ≠ s₂[i], we inverse characters i, i + 1 of the first string. In the end check that s₁[n] = s₂[n], if it's not, there is no solution, in the other case we have found the only, and therefore optimal, solution.

The solution is using special construction.

First, let us show how to create the track with maximal possible k. Starting with the horizontal segment, each vertical segment would cross all previous horizontal segments except the adjacent one. The example with 14 segments is shown in the picture.

To get exactly k segments first draw 2l segments such that l(l - 1) / 2 ≥ k > (l - 1)(l - 2) / 2, make a small track with k intersections. To do so, start creating the maximal example, but terminate the last segment after required number of intersections. The remaining n - 2l segments can be added in the beginning of the track to form the spiral around the smaller track. See picture below for example, where n = 17 and k = 9.

The constraint on k is really the maximal bound on the number of intersections of n segments. We omit the proof, but the hint is: look at the number of intersections of the pair of segments n and n - 1 with pairs n - 3 and n - 4, n - 5 and n - 6, ..., 2 and 1 (or only the segment 1, if n is even).

Let us add weights to tree edges, and set edge weight equal to 1 initially for all edges. Now instead of removing the vertex we would change the weight of the edge from it to its parent to 0. The distance between any pair of vertices would be equal to the distance that would be should we had actually removed the vertex.

We can solve the new problem as follows. For each vertex in the initial vertex find the distance from the root to the vertex, and put the distances to the array in DFS order. After changing some edge weight, we must change the distances in the continuous segment of the array. This can be implemented using, for example, range tree.

Now the distance between vertices can be found, using : d_ab = d_a + d_b - 2·d_lca, where lca — is the least common ancestor of a and b, d_v — is the distance from the root to v.

Notice that the angriness of all people in one connected component is equal to their initial angriness multiplied by some value, the same for all islands in this component.

Let us process edge removal in time proportional to the size of the smaller components that appears after its removal. In this case the time complexity of the algorithm would be . To prove the complexity notice that for each vertex when it is in the smaller component, the size of the component at least halves. So it can only happen times.

If removing the edge we could know which component is smaller, we could traverse it and move its vertices to a new component, leaving the vertices from the larger one in the old one. But we don't know which component is smaller. So let us run two BFS-s simultaneously in both components, and when one of them terminates, terminate the other one as well. This way the time for such BFS would be proportional to the size of the smaller component.