The simplest approach to solving this task, which was enough for ~30\%~ of points, is to check for all possible trees if they are candidates for the closest tree per each query. This algorithm has the complexity of ~\mathcal O(GRS)~.

In order to reduce complexity per query, we need to reduce the number of candidates for the closest tree. Let's solve a simpler problem. For a given location of the fall of an apple ~(r, c)~, determine the closest tree located at column ~s~.

If we denote rows with ~r_1~ and ~r_2~ so that ~r_1~ is the first line above row ~r~ such that column ~s~ contains an apple, and ~r_2~ is the first line below row ~r~ such that column ~s~ contains an apple, it is clear that ~(r_1, s)~ and ~(r_2, s)~ are the only possible candidates for the closest tree in that column.

Therefore, in order to answer the initial question, we need to check ~2~ trees per column. If we had a quick way of determining exactly which two trees these are per column, the answer to each query could be found in complexity ~\mathcal O(S)~.

To quickly find all possible candidates per column, we can maintain two matrices ~g[r][s]~ and ~d[r][s]~. Matrix ~g[r][s]~ stores the first tree above position ~(r, s)~, and matrix ~d[r][s]~ stores the first tree below position ~(r, s)~, given the fact that both fields contain ~r~ if there is a tree located at field ~(r, s)~.

To maintain the matrices described above, when inserting a new tree, we need to update values in the column where the tree grew, which results in ~\mathcal O(R)~ operations per query.

The final complexity of this algorithm is ~\mathcal O(G(R+S))~, which was sufficient for all points.

There is an alternative solution that uses BFS.