Множество точек на плоскости называется хорошим, если для любых двух точек выполняется хотя бы одно из трех условий:
- эти две точки лежат на одной горизонтали;
- эти две точки лежат на одной вертикали;
- внутри или на границе прямоугольника с углами в этих двух точках есть другие точки множества, помимо этих двух. Здесь имеется в виду прямоугольник со сторонами, параллельными осям координат, так называемый bounding box двух точек.
На плоскости задано множество из n точек. Найдите любое хорошее надмножество этого множества размером не более 2·105 точек.
Выходные данные
В первой строке выведите количество точек m (n ≤ m ≤ 2·105) в хорошем надмножестве, в следующих m строках выведите сами точки. Координаты точек не должны превосходить 109 по абсолютной величине. Обратите внимание, что минимизировать m не требуется, достаточно найти любое хорошее надмножество заданного множества, размер которого не превосходит 2·105.
Все точки в надмножестве должны иметь целые координаты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 1
2 2
|
3
1 1
2 2
1 2
|