В лагере, где летом отдыхал Вася, часто устраивали
математические бои. Частью таких боёв является игра на конкурс капитанов. Суть
игры состоит в следующем. Дано клетчатое поле размером M × N
клеток. Двое игроков по очереди ставят крестик в свободную клетку. Проигрывает
игрок, после хода которого на поле впервые образовался параллелограмм с
вершинами в центрах клеток, помеченных крестиками.
Вернувшись из лагеря, Вася решил написать программу,
позволяющую играть в такую игру на компьютере. Однако, у него возникли
сложности с проверкой, действительно ли на поле имеется параллелограмм. Более
того, он хочет узнать, а сколько различных параллелограммов имеется на поле.
Помогите ему − напишите программу, которая определяет количество
различных параллелограммов на поле.
Примечание: параллелограммы должны быть невырожденными, то
есть никакие три вершины никакого параллелограмма не лежат на одной прямой.
Входные данные
В первой строке записаны через пробел числа M и
N − размеры поля.
В следующих M строках записано по N
символов '.' (точка) или 'x' (маленькая
латинская буква "икс"), где символ '.'
означает пустую клетку, символ 'x' означает
клетку, помеченную крестиком.
Примечание: поле
не обязательно получено в ходе вышеописанной игры − оно может быть
заполнено крестиками произвольным образом.
Выходные данные
Одно целое число −
количество параллелограммов.
|
Пример ввода
5
6
...x..
.x....
..x..x
x..x..
......
Пример вывода
3
|
Система оценивания
Подзадача 1 (до 50 баллов): 2 ≤ M, N ≤ 10.
Подзадача 2 (до 50 баллов): 2 ≤ M, N ≤ 20.
