It is a well-known fact that a group of Russian scientists discovered an alien civilization back in 2016. Their satellite managed to capture high-resolution square images that forever changed the course of human history. Today, half a decade later, almost every part of the world has its own space program that investigates aliens. Alas, in Croatia we have decided to tackle some more important problems, which leaves scientific research on the shoulders of few enthusiasts. Vladimir is one of them.
Unfortunately, Vladimir doesn't have enough resources for a spacecraft or an expensive telescope, but he can afford a hot-air balloon and a mobile phone. Instead of an alien civilization, he decided to search for signs of intelligent life on his home planet. Looking down from the balloon, Vladimir notices exactly people. He decided to capture exactly
square images of average resolution such that each person is seen on exactly one image. Also, he doesn't want any detail to be visible on more than one image. Furthermore, he finds it important that the largest area visible on some picture is as small as possible.
Vladimir is not a great programmer, so he sent you a formal specification and awaits your help.
Formal specification
There are integer points in the coordinate system. You need to find exactly
disjunct squares that cover all
points. The squares must have sides parallel with the coordinate axes and their vertices should lie on integer coordinates. The area of the largest square needs to be as small as possible.
We say that a square covers a point if the point is fully inside it or lies on its vertices or sides. Two squares are disjunct if their sides don't intersect or touch, and neither of the squares is fully contained in the other square.
Input Specification
The first line contains integers and
from the task description.
The -th of the next
lines contains integers
and
that represent the coordinates of the
-th point (person). All
points will be different.
Output Specification
The -th of the
lines should contain three integers
and
, that uniquely define the location of the
-th square, such that the point
denotes its lower-left vertex, and
denotes its side length.
If there are multiple correct solutions, output any of them.
Scoring
Subtask | Points | Constraints |
---|---|---|
Sample Input 1
3 1
1 1
1 3
2 2
Sample Output 1
0 1 2
Sample Input 2
5 2
1 3
3 1
5 5
5 10
7 7
Sample Output 2
1 1 4
5 7 3
Explanation for Sample Output 2
Sample Input 3
5 3
1 3
3 1
5 5
5 10
7 7
Sample Output 3
1 1 2
5 5 2
5 10 1
Comments