была встречена критикой, она сделала новую, выбрав на плоскости \(1\le N\le 10^5\)
прямоугольников на плоскости со сторонами, что никакие две из них не коллинеарны.
Границы этих прямоугольников определяют границы раскрашенных регионов.
Будучи художницей-аванагардисткой, она решила, что прямоугольники
будут составлять коровы породы Holstein. Точнее, каждый регион, огороженный
прямоугольником, раскрашивается в белый или черный цвет. Никакие два соседние региона
не имеют один и тот же цвет. Регион снаружи всех прямоугольников, раскрашен
в белый цвет.
Беси просит вывести Вас одну из двух вещей в зависимости от параметра \(T\):
- Если \(T=1\), выведите общее количество регионов.
- Если \(T=2\), выведите количество белых регионов, за которым идёт количество
черных регионов.
**Замечание: время на тест для этой задачи увеличено до 4с (в два раза
больше обычного времени на тест).**
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(T\).
Каждая из последующих \(N\) строк содержит описания прямоугольника в виде
\((x_1,y_1), (x_2,y_2)\) где \(1\le x_1<x_2\le 2N\) и \(1\le y_1<y_2\le 2N\).
\((x_1, y_1)\) и \((x_2, y_2)\) это левый нижний и правый верхний углы прямоугольника
соответственно.
Гарантируется, что все \(x_i\) формируют перестановку \(1\ldots 2N\).
Аналогичное условие гарантируется и для всех \(y_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Одно целое, если \(T=1\), иначе два целых числа, разделённых пробелом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 1 3 3
2 2 4 4
|
4
|