eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Страх

Страх

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Усі чогось бояться. Хтось боїться темряви, хтось боїться висоти, хтось боїться Вінні Джонса (всі ми боїмося Вінні Джонса), хтось боїться співати перед їжею.

Страху багато, але найбільший з усіх для Мірка – це вибір землі для посадки полуниці. Земля Мірко може бути описана як матриця з n рядками та m стовпцями. Частина полів у матриці підходять для посадки полуниці, а частина ні – там ростуть бур'яни. Мирко шукає прямокутні ділянки землі, повністю заповнені полями, придатними для посадки полуниці. Такі прямокутники називаються відповідними прямокутниками. Також Мірко цікавить потенційне значення всіх полів у матриці. Потенційне значення кожного поля в матриці визначається як кількість відповідних прямокутників, що містять це поле.

Оскільки у Мірко проблеми зі своїми страхами, він просить Вас обчислити лише суму потенційних значень усіх полів.

Вхідні дані

Перший рядок містить два цілі позитивні числа n і m (1 ≤ n, m ≤ 2000$) - розміри ділянки.

Наступні n рядків містять m символів, що позначають ландшафт. Кожен символ може бути або . (точка), що позначає поле, що підходить для посадки, або #, що позначає бур'яни.

Вихідні дані

Виведіть суму всіх можливих значень полів матриці.

Приклад

Вхідні дані #1
2 3
.#.
..#
Вихідні дані #1
8
Вхідні дані #2
3 3
...
...
...
Вихідні дані #2
100
Вхідні дані #3
3 4
..#.
#...
...#
Вихідні дані #3
40

Примітка

Наступна матриця визначає потенційну цінність полів ґрунту. Сума всіх потенційних значень дорівнює 8.

image
Джерело 2018 COCI Раунд 1, Октябрь 20