Məsələlər
Ферзи High
Ферзи High
На \textbf{d}-мерной шахматной доске, каждое измерение которой составляет \textbf{N}, в различных ячейках стоят \textbf{K} ферзей. Ферзь может перемещаться на любое натуральное количество клеток в любом прямом или диагональном направлении. Более точно, ферзь может попасть из ячейки с координатами (\textbf{x_1}, \textbf{x_2}, ..., \textbf{x_d}) в ячейку с координатами (\textbf{x'_1}, \textbf{x'_2}, ..., \textbf{x'_d}) тогда и только тогда, когда среди чисел \textbf{|x_i - x'_i|} есть по крайней мере одно ненулевое, и все ненулевые значения равны между собой. Будем говорить, что один ферзь угрожает другому, если существует ход из ячейки первого ферзя в ячейку второго. Очевидно, что это отношение симметрично, то есть если один ферзь угрожает другому, то и другой первому. Будем говорить, что один ферзь находится под боем у другого, если второй угрожает первому и все ячейки между ними свободны. Это отношение также симметрично.
Требуется определить количество пар ферзей, угрожающих друг другу и находящихся под боем друг у друга.
\InputFile
В первой строке задаются три целых числа \textbf{d}, \textbf{N}, \textbf{K} (\textbf{1} ≤ \textbf{d} ≤ \textbf{5}, \textbf{1} ≤ \textbf{N} ≤ \textbf{1000}, \textbf{0} ≤ \textbf{K} ≤ \textbf{40000}, \textbf{1} ≤ \textbf{x_i} ≤ _N). В каждой из последующих \textbf{K} строк записано по \textbf{d} целых чисел \textbf{x_1}, ..., \textbf{x_d}, определяющих координаты ячейки соответствующего ферзя.
\OutputFile
В первой строке выведите количество пар ферзей, угрожающих друг другу, во второй -- количество пар ферзей, находящихся под боем друг у друга.
Giriş verilənləri #1
2 8 5 1 1 3 3 3 1 1 3 5 5
Çıxış verilənləri #1
8 7