Square Tiling Construction

Given n integer points on the two‐dimensional plane. The i-th point has coordinates \( (x_i, y_i) \). You are required to construct n squares so that for the i-th square, its bottom‐left vertex is \( (x_i, y_i) \) and the following conditions hold:

• The union of the n squares is a rectangle.
• For every 1 \(\le\) i \(<\) j \(\le\) n, the intersection area of square \(i\) and square \(j\) is 0. (That is, the edges may touch but the interiors do not overlap.)

Your task is to assign a positive side length \(l_i\) to each square such that the above conditions are satisfied. Note that the squares must exactly tile the rectangle without any gaps or overlaps. It can be proved that if the given n points form a complete grid (i.e. they are all the bottom‐left corners of the unit squares covering a rectangle), then assigning \(l_i = 1\) for all \(i\) is a valid solution. Otherwise, output -1 to indicate that no valid tiling exists.

Input Format: The first line contains a single integer n. Each of the following n lines contains two space‐separated integers \(x_i\) and \(y_i\), denoting the coordinates of a point.

Output Format: If a valid tiling exists, output n positive integers where the i-th integer is the side length \(l_i\) of the square with bottom‐left corner \( (x_i, y_i) \). Otherwise, output a single line with -1.

Note: It is guaranteed that if a valid tiling exists, then the points form a complete rectangular grid. In that case, one valid solution is to assign \(l_i = 1\) for all i.

inputFormat

The first line contains an integer n (the number of points). Each of the next n lines contains two integers \(x_i\) and \(y_i\) (\(-10^9 \le x_i, y_i \le 10^9\)), representing the coordinates of a point.

The input is guaranteed to satisfy \(n \ge 3\). Moreover, if the points form a complete grid (i.e. every integer coordinate between the minimum and maximum values is present), then the tiling is possible by choosing \(l_i = 1\) for all i.

outputFormat

If a valid tiling exists, output n positive integers separated by spaces; the i-th number is the side length of the square with bottom‐left corner at \( (x_i, y_i) \). Otherwise, output -1.

sample

4
0 0
1 0
0 1
1 1

1 1 1 1