Triangles

Time limit6sMemory limit1024 MB

Summary

Count all triangles formed by drawn horizontal and diagonal edges in an ASCII picture of a triangular grid up to 3000 by 6000 vertices.

Level: Medium7 of 10
Topics: Geometry, Brute force, Dynamic programming
Solved: No attempts yet

Problem

You packed plenty of puzzle books for the trip to Beijing, and many of them ask questions like this one: how many triangles can you find in Figure 1?

Figure 1: the picture drawn by the second example input.

After a few of them you get bored and start working out how to solve the puzzle with a program instead. Today that program is exactly what you need.

Input

The first line contains two integers r and c ( $1 \le r \le 3000$ , $1 \le c \le 6000$ ), the size of the picture, where r is the number of rows of vertices and c is the number of columns of vertices.

The next $2r-1$ lines hold the picture, each with at most $2c-1$ characters. Odd lines contain grid vertices, written as the lowercase letter x, together with zero or more horizontal edges. Even lines contain zero or more diagonal edges. Picture lines numbered $4k+1$ have vertices in positions 1, 5, 9, 13, and so on, while lines numbered $4k+3$ have vertices in positions 3, 7, 11, 15, and so on. A vertex can therefore sit only in one of the c positions 1, 3, 5, ..., $2c-1$ . Every possible vertex appears in the input.

A horizontal edge between two neighboring vertices is drawn as three hyphens ---. A diagonal edge is drawn as a single forward slash / or a single backslash \. An edge character sits exactly between the two vertices it joins. Every other position holds a space. Trailing whitespace on a line may be omitted.

Output

Print the number of triangles of any size formed by the drawn edges. All three sides of a triangle must lie on drawn edges, and one side is a run of consecutive edges in the same direction.

Examples2

Example 1
Input
```
3 3
x---x
 \ /
  x
 / \
x   x
```
Expected output
```
1
```

Example 2

Input

4 10
x   x---x---x   x
     \ /   / \
  x   x---x   x   x
     / \ / \   \
x   x---x---x---x
   /   / \   \ / \
  x---x---x---x---x

Expected output