Двумерные массивы

В некоторых клетках квадрата \( N\ х\ N\) живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через \(T\) секунд.

Примеры

 17  16   9   8   1 
 18  15  10   7   2 
 19  14  11   6   3 
 20  13  12   5   4 

У Фили есть квадратная матрица \(A\) размера \(N \times N\), но она кажется ему слишком большой. Ему гораздо больше нравятся матрицы размера \(k \times k\) (\(k < N\)).

Филя хочет получить матрицу нужного размера взяв некоторую подматрицу исходной матрицы. Подматрицей \(k \times k\) матрицы \(A\) в данном случае Филя считает матрицу \(B\) такую, что \(b_{i, j} = a_{i + x, j + y}\), для всех \(i\), \(j\) от \(1\) до \(k\). Из данного определения можно заметить, что подматрица исходной матрицы задается парой чисел (\(x\), \(y\)).

Для того, чтобы выбрать наиболее интересную для себя подматрицу, Филя хочет узнать, сколько есть способов выбрать из исходной матрицы две различные (характеризующие пары (\(x\), \(y\)) отличаются хотя бы в одной позиции) равные подматрицы \(k \times k\). Две матрицы \(Q\) и \(P\) размера \(k \times k\) считаются равными, если для любых \(i, j: 1 \le i, j \le k\) выполняется \(q_{i, j} = p_{i, j}\). Если условия равенства не выполняется, матрицы считаются неравными.

Формат входных данных
В первой строке входного файла содержатся два натуральных числа \(N\) и \(k\) — размеры исходной и нужной матрицы. (\(1 \le k < N \le 10\)). В следующих \(N\) строках заданы через пробел по \(N\) натуральных чисел \(a_{i, j}\) — элементы исходной матрицы (\(1 \le a_{i, j} < 10\)).

Формат выходных данных
В единственной строке выходного файла выведите одно число — количество способов выбрать из исходной матрицы две различные равные подматрицы размера \(k \times k\).

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

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

Примеры

2 0 0 0
2 0 0 0
2 0 0 0
0 0 0 0

4

2 0 0 0
2 0 0 0
2 0 0 0
2 0 0 0

8

2 2 4 0
0 0 0 0
0 0 0 0
0 0 0 0

4

2 2 4 0
0 2 2 2
0 2 4 0
2 4 4 0

16

Примечания

Примеры

Формат входных данных

Программа получает на вход два числа n и m (20<=n,m<=20), являющиеся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по m чисел, являющихся элементами массива.

Формат выходных данных

Программа должна вывести одно число - номер победителя соревнований. Не забудьте, что  строки  (спортсмены) нумеруются с 0.

Пример

 4 3
 8 8 8
 5 9 3
 9 4 7
 6 6 2

2