問題文

HHWW 列のグリッドがあります。上から ii マス目、左から jj マス目を (i,j)(i,j) と表します。
(i,j)(i,j) には文字 Gi,jG_{i,j} が書かれており、UDLRのいずれかです。
viral君はグリッド外からグリッドのどこかにワープし、以下の行動を終えるまで行ないます。

(i,j)(i,j) にいるとすると、

  • Gi,jG_{i,j}Uかつ i1i \ne 1 ならば、(i1,j)(i-1, j) に移動する。
  • Gi,jG_{i,j}Dかつ iHi \ne H ならば、(i+1,j)(i+1, j) に移動する。
  • Gi,jG_{i,j}Lかつ j1j \ne 1 ならば、(i,j1)(i, j-1) に移動する。
  • Gi,jG_{i,j}Rかつ jWj \ne W ならば、(i,j+1)(i, j+1) に移動する。
  • それ以外なら行動を終える。

viral君が行動を終えることができないマス、すなわち無限に移動し続けてしまうような開始地点はいくつありますか?

制約

  • 1H,W5001 \le H,W \le 500
  • Gi,jG_{i,j}UDLRのいずれかである。
  • HHWW は整数である。

入力

HH WW
G1,1G_{1,1} \ldots G1,WG_{1,W}
\vdots
GH,1G_{H,1} \ldots GH,WG_{H,W}

出力

答えを出力してください。

入出力例1

入力
2 4
DLLU
RURU
出力
5

(1,1)(1,1)(1,2)(1,2)(1,3)(1,3)(2,1)(2,1)(2,2)(2,2) にワープするとviral君は無限に移動し続けます。

入出力例2

入力
2 4
DLLU
LURU
出力
0

どのマスでもviral君が行動を終えることができる場合もあります。

Submit


Go (1.21)