Задана сетка размера n × m, некоторые узлы которой черные, а остальные белые. Более того, сетка не совсем обычная — в каждом единичном квадрате сетки проведены диагонали.
На рисунке ниже изображен пример такой сетки размера 3 × 5. Четыре узла этой сетки черные, остальные 11 узлов белые.
Требуется посчитать количество таких треугольников на заданной сетке, что:
- их углы совпадают с белыми узлами, а площадь ненулевая;
- все стороны проходят по линиям сетки (горизонтальным, вертикальным или диагональным);
- никакая сторона не содержит черных узлов.
Выходные данные
Выведите единственное целое число — количество требуемых треугольников.
Примечание
На рисунке ниже красным и синим цветами выделены треугольники, которые считаются в ответе (это не все требуемые треугольники, а только два из них). Зеленым выделен один из неподходящих треугольников. Он не подходит, поскольку не все его стороны проходят по линиям сетки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
10000
10010
00001
|
20
|
|
2
|
2 2
00
00
|
4
|
|
3
|
2 2
11
11
|
0
|