Bear and Shuffled Points

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Bear Limak loves preparing problems for algorithmic contests. While his favorite part is inventing a story and writing the statement, he doesn't really like creating the test data. Not only it's hard to do, but also making a mistake may spoil a problem completely, likely making a problem easier.
Limak prepared the following problem for you. You start with an empty set of points on a twodimensional plane. There are N queries, each with one new point (x_{i}, y_{i}) to insert to the set. After each query you must find the diameter of the set, i.e. the maximum distance between two points in the set. To avoid printing floating numbers, after each query print the square of the diameter.
In many problems, in test generators an author should create some (possibly smart and tricky) data, and then shuffle it before printing. Limak did the same in this problem, not noticing how crucial it may be. You can assume that in every test the N points are randomly shuffled. In other words, generators have a line "random_shuffle(array with points)" just before printing. It isn't guaranteed that a problem is solvable within the time limit without this extra constraint.
Input
The first line of the input contains an integer N denoting the number of points.
The ith of N following lines contains two space separated integers x_{i} and y_{i} denoting coordinates of the ith point to insert.
Output
Output N lines. The ith line should contain the square of the diameter of the set with points (x_{1}, y_{1}), ..., (x_{i}, y_{i}).
Constraints
 2 ≤ N ≤ 750,000
 10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}
 Points are distinct.
 Points are shuffled.
Subtasks
 Subtask #1 (20 points) 2 ≤ N ≤ 1000
 Subtask #2 (30 points) Points are generated uniformly at random. In more detail: in each test file organizers chose two integers N and K, after which a generator finds N distinct points with coordinates generated randomly from interval [K, K]. All given original constraints are still satisfied.
 Subtask #3 (50 points) original constraints
Example
Input: 5 20 20 40 30 35 35 0 10 170 1000000000 Output: 0 500 500 2000 999999980000029000
Explanation
 After the first query, the set contains only one point (20, 20). You should print 0 because there are no two points with positive distance between them.
 After the second query, the set contains points (20, 20) and (40, 30). The distance between them is sqrt((4020)^2+(3020)^2) = sqrt(500) so the squared distance is 500.
 After the third query, the set is {(20,20), (40,30), (35,35)}. The maximum distance is sqrt(500).
 After the fourth query, the maximum distance is between (0,10) and (40,30). Note that the given points may be collinear.
 After the fifth query, the set contains all five points from the input. Watch out for overflows because the answer may be very big, as you can see here.
Author:  errichto 
Tester:  alex_2oo8 
Editorial  http://discuss.codechef.com/problems/GEOCHEAT 
Tags  convex, convexhull, errichto, geometry, hard, oct16, random 
Date Added:  6102016 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 