たのしく前処理 : 競プロ典型 90 問 004 - Cross Sum（★2）
問題
解説
H × Wの数字がはいったマスが与えられるので，それぞれのマスについてマスと列が等しいか行が等しい全てのマスの数字の総和を出力する問題です．
(実際には数字が各マスに入っています)
例えば赤のマスについて調べたいとき，赤のマスに書かれている数字と青のマスに書かれている数字の総和を出力します．
単純に計算すると，1度の計算でH+W回の操作が必要になり，全体でHW(H+W)回になります．
今回の入力では列の数と行の数の最大値が2000なため，単純な実装では現代のコンピュータでは2秒以内に計算できません．
そのため何らかの工夫が必要になります．
ここで次の場合を考えてみます．
左を計算すると，2 + 5 + 6 + 7 + 8 + 10 + 14です．
右を計算すると，3 + 5 + 6 + 7 + 8 + 11 + 15です．
両方に5 + 6 + 7 + 8 が入っていることがわかります．これは行が同じため，計算する必要のある場所がかぶっているためです．
また，これは列が同じときにも使うことができます．
この性質を利用して，予め各列についての総和，各行についての総和を求めることで計算を効率的に行えます．
i行j列のマスについて操作を行うとすると，i行目の総和 + j列目の総和 - i行j列の値 とすることで計算できます．
このように先に入力に対し何らかの処理を行うことを前処理といいます．
簡単な動作例
それぞれの行と列について総和を求めます．
答えは次のようになります．
