Consider a rectangular grid of points on a plane with N rows and M columns. Each of the points is colored in one of three possible colors: red, green or blue. If we take any three distinct points (even those lying on the same straight line) and join them by line segments, we'll obtain a triangle (possibly degenerate). Such a triangle is called *beautiful* if all its vertices have distinct colors.
A beautiful triangle A is called *extendable* if there exists a beautiful triangle B such that A and B have two common vertices and the area of B is strictly greater than the area of A. Note that the area of a degenerate triangle is equal to 0.
You will be given a String **grid**, containing exactly N elements, representing rows of the grid, from top to bottom. Each element of **grid** will contain exactly M characters, representing colors of points in the corresponding row, from left to right ('R' for red, 'G' for green and 'B' for blue). Return the number of distinct beautiful extendable triangles that can be formed from points on the given grid. Two triangles are considered distinct if their sets of vertices are distinct. |