408320: GYM103092 F Finding Diamonds

F. Finding Diamondsограничение по времени на тест4 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Диас недавно начал изучать машинное обучение. Особенно сильно ему понравилась сфера распознавания различных паттернов в фотографиях. Недавно ему пришлось работать с распознаванием так называемых алмазов с некоторыми свойствами. Алмазы, по своей сути, имеют форму обычной квадратной рамки, повернутой на $$$45$$$ градусов.

Диас справился со своей задачей в машинном обучении. Теперь ему стало интересно, а смогут ли решить эту задачу наши любимые ACM-щики? Поскольку в машинном обучении люди работают с настоящими фотографиями у которых могут быть разные неровности и размытости, Диас адаптировал свою задачу специально для наших ребят: они могут считать, что фотография является бинарной матрицей размера $$$n \times n$$$. Строки и столбцы матрицы пронумерованы от $$$1$$$ до $$$n$$$.

Определим понятие алмазов в данной задаче более подробно. Каждый алмаз можно описать тремя положительными целыми числами — его центром $$$(p, q)$$$ и его радиусом $$$r$$$. Все клетки $$$(x, y)$$$, образующие сам алмаз, будут соответствовать свойству $$$|x - p| + |y - q| = r$$$. На картинке ниже приведены алмазы $$$(2, 2, 1)$$$, $$$(4, 3, 1)$$$ и $$$(3, 3, 2)$$$.

Диас попросил ACM-щиков посчитать общее количество алмазов на фотографии со следующими свойствами:

1. Алмаз находится полностью внутри матрицы. Более формально, все клетки $$$(x, y)$$$ принадлежащие алмазу соответствуют условию $$$1 \le x, y \le n$$$.
2. Все клетки алмаза содержат только единицы.

Вы были одним из тех ребят, которые услышали эту задачу напрямую из уст Диаса. Сможете её решить?

Входные данные

В первой входного файла дано одно положительное целое число $$$n$$$ — размер матрицы ($$$4 \le n \le 5200$$$). Гарантируется, что $$$n$$$ нацело делится на $$$4$$$.

Далее следует описание матрицы. В каждой из $$$n$$$ следующих строк следуют по $$$\frac{n}{4}$$$ однозначных числа шестнадцатеричной системы счисления (то есть, эти числа могут задаваться либо как цифры от $$$0$$$ до $$$9$$$, либо как прописные латинские буквы от $$$A$$$ до $$$F$$$). Двоичная запись каждого из этих чисел задаёт очередные $$$4$$$ элемента матрицы в текущей строке. Например, если число равно $$$B$$$, то очередные четыре элемента матрицы равны 1011, а если число равно $$$5$$$, то очередные четыре элемента матрицы равны 0101.

Элементы в каждой строке задаются без пробелов.

Настоятельно рекомендуем использовать быстрые методы ввода/вывода данных.

Выходные данные

Выведите одно единственное целое число — количество алмазов в фотографии.

ПримерыВходные данные

4
7
D
F
7

Выходные данные

2

Входные данные

8
10
28
54
AA
54
28
10
00

Выходные данные

14

Примечание

Пояснение к первому примеру:

Бинарная матрица во втором примере с двумя выделенными алмазами: