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\underset{j\in [-T,T]}{max}(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))$