Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Pasha and Pipe

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputOn a certain meeting of a ruling party "A" minister Pavel suggested to improve the sewer system and to create a new pipe in the city.

The city is an *n* × *m* rectangular squared field. Each square of the field is either empty (then the pipe can go in it), or occupied (the pipe cannot go in such square). Empty squares are denoted by character '.', occupied squares are denoted by character '#'.

The pipe must meet the following criteria:

- the pipe is a polyline of width 1,
- the pipe goes in empty squares,
- the pipe starts from the edge of the field, but not from a corner square,
- the pipe ends at the edge of the field but not in a corner square,
- the pipe has at most 2 turns (90 degrees),
- the border squares of the field must share exactly two squares with the pipe,
- if the pipe looks like a single segment, then the end points of the pipe must lie on distinct edges of the field,
- for each non-border square of the pipe there are exacly two side-adjacent squares that also belong to the pipe,
- for each border square of the pipe there is exactly one side-adjacent cell that also belongs to the pipe.

Here are some samples of allowed piping routes:

....# ....# .*..#

***** ****. .***.

..#.. ..#*. ..#*.

#...# #..*# #..*#

..... ...*. ...*.

Here are some samples of forbidden piping routes:

.**.# *...# .*.*#

..... ****. .*.*.

..#.. ..#*. .*#*.

#...# #..*# #*.*#

..... ...*. .***.

In these samples the pipes are represented by characters ' * '.

You were asked to write a program that calculates the number of distinct ways to make exactly one pipe in the city.

The two ways to make a pipe are considered distinct if they are distinct in at least one square.

Input

The first line of the input contains two integers *n*, *m* (2 ≤ *n*, *m* ≤ 2000) — the height and width of Berland map.

Each of the next *n* lines contains *m* characters — the map of the city.

If the square of the map is marked by character '.', then the square is empty and the pipe can through it.

If the square of the map is marked by character '#', then the square is full and the pipe can't through it.

Output

In the first line of the output print a single integer — the number of distinct ways to create a pipe.

Examples

Input

3 3

...

..#

...

Output

3

Input

4 2

..

..

..

..

Output

2

Input

4 5

#...#

#...#

###.#

###.#

Output

4

Note

In the first sample there are 3 ways to make a pipe (the squares of the pipe are marked by characters ' * '):

.*. .*. ...

.*# **# **#

.*. ... .*.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 02:54:00 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|