На плоскости нарисовано $$$n$$$ отрезков; $$$i$$$-й отрезок соединяет две точки ($$$x_{i, 1}$$$, $$$y_{i, 1}$$$) и ($$$x_{i, 2}$$$, $$$y_{i, 2}$$$). Каждый отрезок невырожден и является либо горизонтальным, либо вертикальным — формально, для любого $$$i \in [1, n]$$$ выполняется ровно одно из двух условий: $$$x_{i, 1} = x_{i, 2}$$$ или $$$y_{i, 1} = y_{i, 2}$$$ . Только отрезки разных типов могут пересекаться, т. е. горизонтальные отрезки не имеют общих точек, то же самое верно и для вертикальных.
Четыре отрезка с индексами $$$h_1$$$, $$$h_2$$$, $$$v_1$$$ и $$$v_2$$$, такие, что $$$h_1 < h_2$$$ и $$$v_1 < v_2$$$, образуют прямоугольник при выполнение следующих условий:
- отрезки $$$h_1$$$ и $$$h_2$$$ горизонтальные;
- отрезки $$$v_1$$$ и $$$v_2$$$ вертикальные;
- отрезок $$$h_1$$$ пересекается с отрезком $$$v_1$$$;
- отрезок $$$h_2$$$ пересекается с отрезком $$$v_1$$$;
- отрезок $$$h_1$$$ пересекается с отрезком $$$v_2$$$;
- отрезок $$$h_2$$$ пересекается с отрезком $$$v_2$$$.
Подсчитайте количество способов выбрать четыре отрезка так, чтобы они образовывали прямоугольник. Не забывайте, что условия $$$h_1 < h_2$$$ и $$$v_1 < v_2$$$ должны выполняться.
Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — количество отрезков.
Далее следуют $$$n$$$ строк. В $$$i$$$-й строке содержатся четыре целых числа $$$x_{i, 1}$$$, $$$y_{i, 1}$$$, $$$x_{i, 2}$$$ и $$$y_{i, 2}$$$, обозначающие концы $$$i$$$-го отрезка. Все координаты концов отрезков находятся в диапазоне $$$[-5000, 5000]$$$.
Гарантируется, что заданные отрезки невырожденные и являются либо горизонтальными, либо вертикальными. Более того, если пара отрезков имеют общую точку, то один из них горизонтальный, а другой вертикальный.
Выведите число — количество способов выбрать четыре отрезка так, чтобы они образовывали прямоугольник.
7 -1 4 -1 -2 6 -1 -2 -1 -2 3 6 3 2 -2 2 4 4 -1 4 3 5 3 5 1 5 2 1 2
7
5 1 5 1 0 0 1 5 1 5 4 0 4 4 2 4 0 4 3 4 5
0
На следующих картинках нарисованы тестовые примеры:
