After finishing one task at work, Bob is getting bored. So he decides to count some patterns in the ~N~-pixel-high by ~M~-pixel-wide computer screen his employer gave him. Each pixel is either yellow (lit) or black (unlit).
Bob thinks a rectangle of pixels, with both dimensions at least ~2~, is ugly if its first and last rows are identical and its first and last columns are identical. (Note: this definition is the same as the one in Problem 5.) For example, the following rectangles are ugly:
Please help Bob count the number of ugly sub-rectangles in the ~N \times M~ screen!
~2 \le N, M~
~4 \le N \times M \le 200\,000~
Subtask 1 [10%]
~4 \le N \times M \le 500~
Subtask 2 [20%]
~4 \le N \times M \le 8000~
Subtask 3 [70%]
No additional constraints.
The first line contains two space-separated integers, ~N~ and ~M~.
The next ~N~ lines each contain a string of ~M~ characters—
Y for yellow and
B for black—representing the colours of the pixels on the screen.
Output one integer, the number of ugly sub-rectangles.
3 3 BYB YYY BYB