Before Domeniko throws in the first rock, let's calculate and remember, for each column, the path a rock would take if Domeniko threw it in that column.

Now, when Domeniko says which column he wants to throw a rock into, we know exactly where the rock will settle – the last cell on the path we previously calculated for that column.

In order to be able to do the same for each subsequent rock, we must refresh each path on which the last cell is the one the thrown rock ended at. We can do that by simulating the effect of gravity from the second last cell in the path (as the path before that didn't change).

Time complexity: ~\mathcal O(C(R+N))~