In order to maximize the raw total, each goose should fly to a cell covered by as many quadrats as possible so that it can be counted the maximum number of times. Thus, we seek $$\displaystyle \sum_{i=1}^K \max_{j \in [-T, T]} (cnt[a_i + j][b_i], cnt[a_i][b_i + j])$$ where ~cnt[a][b]~ is the number of quadrats covering the cell at row ~a~ and column ~b~.

For the first subtask, we can use a 2D prefix sum array to compute all ~cnt[a][b]~ in ~\mathcal O(1)~ per quadrat plus ~\mathcal O(NM)~ post-processing. Then, for each goose, we can go over all the ~\mathcal O(T)~ cells that it can reach to find the one covered by the most quadrats.

Time complexity: ~\mathcal O(NM + Q + KT)~

For the second subtask, we can sweep the rows from top to bottom, keeping a data structure such as a segment tree that allows for efficient range addition updates and range maximum queries. When we reach the beginning or the end of quadrat ~i~, we add 1 to or subtract 1 from the cells from ~c_{1i}~ to ~c_{2i}~. When we reach goose ~i~, we query the cells from ~b_i - T~ to ~b_i + T~ to find its ~\max(cnt[a_i][b_i + j])~.

We can then do a similar sweep from left to right to find ~\max(cnt[a_i + j][b_i])~ for each goose.

Time complexity: ~\mathcal O(N + M + (K + Q)(\log N + \log M))~

For the final subtask, we must first compress the coordinates so that the maximum row and column are ~\mathcal O(K + Q)~. Then, we can do the same thing as in the second subtask.

Time complexity: ~\mathcal O((K + Q)\log (K + Q))~