問題文
H 行 W 列のマス目があり、上から i 行目、左から j 列目のマスをマス (i,j) と表します。
マス (i,j) は、Sij が .
ならば白、#
ならば黒で塗られています。
正整数の組 (X1,Y1,X2,Y2) であって、以下の条件を満たすものの個数を求めてください。
- 1≤X1≤X2≤H
- 1≤Y1≤Y2≤W
- X1≤x≤X2, Y1≤y≤Y2 を満たすマス (x,y) はすべて白で塗られている
制約
- 1≤H,W≤400
- Sij は
.
または #
入力
入力は以下の形式で標準入力から与えられる。
出力
正整数の組 (X1,Y1,X2,Y2) であって、条件を満たすものの個数を出力せよ。
サンプル
(X1,Y1,X2,Y2)=(1,1,1,1), (1,1,1,2), (1,2,1,2), (1,2,2,2), (2,2,2,2) の 5 組が条件を満たします。
答えは 32 bit整数型に収まらない可能性があるので注意してください。