Есть город, который можно представить как квадрат на плоскости с концами в координатах \((0, 0)\) и \((10^6, 10^6)\).
В городе есть \(n\) вертикальных и \(m\) горизонтальных улиц, которые пересекают весь город, т. е. \(i\)-я вертикальная улица проходит от \((x_i, 0)\) до \((x_i, 10^6)\), а \(j\)-я горизонтальная улица проходит от \((0, y_j)\) до \((10^6, y_j)\).
Все улицы двухсторонние. Границы города также являются улицами.
В городе на некоторых улицах стоят \(k\) человек: \(p\)-й человек стоит в точке \((x_p, y_p)\) (таким образом, либо \(x_p\) равняется некоторому \(x_i\), либо \(y_p\) равняется некоторому \(y_j\), либо и то и другое).
Назовем пару человек неудачной парой, если кратчайший путь от одного человека до другого, если двигаться только по улицам, строго больше чем Манхеттенское расстояние между ними.
Посчитайте общее количество неудачных пар (пары \((x, y)\) и \((y, x)\) — это одна и та же пара).
Напомним, что Манхеттенское расстояние между точками \((x_1, y_1)\) и \((x_2, y_2)\) равно \(|x_1 - x_2| + |y_1 - y_2|\).
Выходные данные
Для каждого набора входных данных, выведите общее количество неудачных пар людей.
Примечание
Изображение второго набора входных данных представлено ниже:
Для примера, точки \(3\) и \(4\) образуют неудачную пару, потому что кратчайший путь между ними (отмечен красным и равен \(7\)) больше, чем их Манхеттенское расстояние (равное \(5\)).
Точки \(3\) и \(5\) также образуют неудачную пару: кратчайший путь равен \(1000001\) (отмечен зеленым) больше, чем Манхеттенское расстояние равное \(999999\).
Однако, точки \(5\) и \(9\) не образуют неудачную пару, потому что кратчайший путь (отмечен фиолетовым) равен их Манхеттенскому расстоянию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 2 4
0 1000000
0 1000000
1 0
1000000 1
999999 1000000
0 999999
5 4 9
0 1 2 6 1000000
0 4 8 1000000
4 4
2 5
2 2
6 3
1000000 1
3 8
5 8
8 8
6 8
|
2
5
|