Find the Trinity

Agent Sue Thomas and her son are searching for a trinity in a grid. A trinity is defined as a right isosceles triangle shape formed by removing one half of a square subgrid along one of the two diagonals (either the main diagonal or the anti‐diagonal). More precisely, consider a square subgrid of side length \(L\) (with \(L\ge2\)). There are 4 ways to obtain a triangle as follows:

• Main diagonal lower: All cells \((i,j)\) (with \(0\le i,j<L\)) satisfying \(i\ge j\) are kept.
• Main diagonal upper: All cells with \(i\le j\) are kept.
• Anti-diagonal upper: All cells with \(i+j\le L-1\) are kept.
• Anti-diagonal lower: All cells with \(i+j\ge L-1\) are kept.

A trinity is valid if it contains at least 3 cells and all its cells contain the same character. Given a grid of characters, your task is to count the number of valid trinity shapes in the grid.

inputFormat

The first line contains two space‐separated integers (n) and (m), representing the number of rows and columns in the grid. Each of the next (n) lines contains a string of length (m) representing a row of the grid.

outputFormat

Output a single integer – the number of valid trinity shapes found in the grid.

sample

2 2
aa
aa

4