eolymp
bolt
Try our new interface for solving problems
Problems

Ферзи Junior

Ферзи Junior

Time limit 1 second
Memory limit 128 MiB

На шахматной доске размера N×N в различных клетках стоят K ферзей. Ферзь может перемещаться на любое натуральное количество клеток в любом прямом или диагональном направлении. Более точно, ферзь может попасть из клетки с координатами (x, y) в клетку с координатами (x', y') тогда и только тогда, когда числа |x - x'| и |y - y'| равны между собой и отличны от нуля. Будем говорить, что один ферзь угрожает другому, если существует ход из клетки первого ферзя в клетку второго. Очевидно, что это отношение симметрично, то есть если один ферзь угрожает другому, то и другой первому. Будем говорить, что один ферзь находится под боем у другого, если второй угрожает первому и все клетки между ними свободны. Это отношение также симметрично.

Требуется определить количество пар ферзей, угрожающих друг другу и находящихся под боем друг у друга.

Input data

В первой строке задаются два целых числа N, K (1N10^6, 0K10^5, 1x, y ≤ _N). В каждой из последующих _K строк записано по два целых чисел x, y, определяющих координаты соответствующего ферзя.

Output data

В первой строке выведите количество пар ферзей, угрожающих друг другу, во второй – количество пар ферзей, находящихся под боем друг у друга.

Examples

Input example #1
8 5
1 1
3 3
3 1
1 3
5 5
Output example #1
8
7
Author Неспирный В.Н.