Пусть на плоскости задано конечное множество точек M в декартовой системе координат. Правильной выпуклой оболочкой множества M называется минимальное по включению выпуклое множество, содержащее M и ограниченное замкнутой ломаной, звенья которой либо параллельны одной из осей координат, либо наклонены к ним под углом 45°.

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

В первой строке содержится число N – количество последующих строк. Число N не менее единицы и не более 100 000. Во второй и последующих строках содержатся координаты точек множества. В каждой строке записаны координаты одной вершины, абсцисса и ордината разделены одним или несколькими пробелами. Каждая координата – целое число от 0 до 1000 включительно. Координаты одной и той же точки могут повторяться несколько раз в разных строках (т.е., в процессе перечисления точек множества одна и та же точка может встретиться неоднократно).

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

Никакие три записанные в выходных данных подряд вершины не должны лежать на одной прямой, кроме того, на одной прямой не должны лежать тройки “первая и две последних перечисленных вершины”, “последняя и две первых перечисленных вершины”.