\(O(MN)\) による二次元累積和を前準備として行うことで、各クエリについて \(O(1)\) で答えることができます。

よって、この問題は \(O(MN+K)\) で解くことができます。