Hide

Problem E
Joining Points

You have N points on a Cartesian coordinate plane. The i-th point is located at (Xi,Yi), where Xi and Yi are integers.

As a competitive programmer, you hate non-rectilinear geometrical objects. Therefore, you wish to connect all the points such that the resulting shape is a square, whose sides are either horizontal or vertical. All of the points must lie on the border of the square (inclusive of its vertices). Degenerate squares (i.e. squares with zero area) are allowed.

Can you find any such square, or report if it is impossible to do so?

Input

The first line of input contains an integer N (1N105), the number of points.

The next N lines each contains two integers Xi and Yi (108Xi,Yi108), the coordinates of the i-th point.

Output

If it is impossible to connect all the points such that the resulting shape is a square, output Impossible.

Otherwise, output four integers X1, X2, Y1, and Y2, the coordinates of two opposite corners of the square. The four integers must satisfy 109X1X2109 and 109Y1Y2109.

If there are multiple valid answers, you may output any of them. It can be proven that if a solution exists, there will be at least one solution that satisfies the constraints.

Sample Input 1 Sample Output 1
3
7 6
2 4
4 0
2 8 0 6
Sample Input 2 Sample Output 2
4
2 6
8 8
10 2
3 3
Impossible
Hide

Please log in to submit a solution to this problem

Log in