E - Artist Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

ツバサくんの学科では、お絵描きが流行っています。ツバサくんは、すごく変わった絵を描くため周りの皆から「画伯」と呼ばれています。ツバサくんの絵の描き方とお手本の絵が与えられるので、彼がどんな絵を描くのか予想してみましょう。

絵の描き方:
絵は \(M \times N\) マスの長方形であり、上から \(i\) 行目、左から \(j\) 列目にあるマスを \((i,j)\) で表します。マス目の色は2次元配列 \(a\) で表され、 \(a_{ij}\) が 0 のとき白色、1 のとき黒色です。ツバサくんは、まず \(1 \leq x \leq M -1 \) および \(1 \leq y \leq N -1 \) を満たす \(1\) つのマス \((x,y)\) を選びます。その後、すべてのマス \((i,j)\) を、

  • \(1 \leq i \leq x\),\(1 \leq j \leq y \)
  • \(1 \leq i \leq x\),\(y \lt j \leq N \)
  • \(x \lt i \leq M\),\(1 \leq j \leq y \)
  • \(x \lt i \leq M\),\(y \lt j \leq N \)

で表される \(4\) つの長方形に切り分け、それぞれ \(180\) 度回転させます。最後に、それぞれの長方形を元のマスに戻して完成です。

例:
\(3 \times 3\) の長方形のお手本が以下のようであったとします。

101
010
100

ここで、ツバサくんがマス \((1,1)\) を選択した場合、以下のような4つの長方形に分割されます。

1|01
-+--
0|10
1|00

それぞれの長方形を \(180\) 度回転させると、以下のようになります。

1|10
-+--
1|00
0|01

最後にそれぞれの長方形を元のマスに戻すと、次のような絵が完成します。

110
100
001

そして、ツバサくんは次のようなことも言っていました。

  • 操作の前後で、それぞれの行、列にある黒いマスの個数は変化しない

さて、ツバサくんが選択しうるマスの個数はいくつでしょうか。

制約

  • \(2 \leq M, N \leq 10^5\)
  • \(4 \leq M \times N \leq 5 \times 10^5\)
  • \(a_{ij}\) は 0 あるいは 1
  • 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(M\) \(N\)
\(a_{11}\)\(\dots\)\(a_{1N}\)
\(\vdots\)
\(a_{M1}\)\(\dots\)\(a_{MN}\)

出力

選択しうるマスの個数を出力せよ。


入力例 1

3 3
101
010
100

出力例 1

1

ツバサくんが選択できるマスは \((1,1)\) のみです。

入力例 2

2 3
101
010

出力例 2

2

ツバサくんが選択できるマスは \((1,1)\) と \((1,2)\) の \(2\) つです。

入力例 3

16 26
00000000000000000000000000
00000000000000000000000000
00000000111111111111110000
00000011111111111111110000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00000011111111111111110000
00000000111111111111110000
00000000000000000000000000
00000000000000000000000000

出力例 3

0

ツバサくんが選択できるマスはありません。