21544번 - Флешмоб 스페셜 저지다국어

Для участников олимпиады на главной площади города <<У>> планируется игра в форме флешмоба. Главная площадь замощена плитками, образующими клетчатое поле.

Сначала составляется план игры: каждый участник флешмоба получает номер в очереди выхода на площадь и координаты двух различных плиток, находящихся в одном ряду или столбце. После этого на площади раскладываются призы, затем участники выходят на площадь по очереди. Очередной участник забирает все призы, находящиеся в указанных ему клетках, и клетках, находящихся между ними.

Призы должны быть разложены так, чтобы каждому участнику достался по крайней мере один приз.

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

В первой строке входного файла содержится число $N$ --- количество участников флешмоба (\mbox{$1 \le N \le 123\,456$}). Каждая из последующих $N$ строк содержит четыре целых числа $x_{1i}$, $y_{1i}$, $x_{2i}$, $y_{2i}$ --- координаты плиток для $i$-го участника ($1 \le x_{1i},\, y_{1i},\, x_{2i},\, y_{2i} \le 10^9$; либо $x_{1i}=x_{2i}$, либо $y_{1i}=y_{2i}$). Участники перечислены в порядке выхода на площадь.

Первая строка выходного файла должна содержать число $M$ --- минимальное количество призов, которые должны быть разложены на площади. Каждая из последующих $M$ строк должна содержать два числа $px_i$ и $py_i$ --- координаты плитки, на которой должен лежать $i$-й приз.

Если вариантов размещения призов, удовлетворяющих условию задачи, несколько, то выведите любой из них. Если решения не существует, выведите единственное число $0$.

• $N \le 123\,456$