Vương quốc hamster

Gần sa mạc lớn của Byteland có một vương quốc chuột hamster với công nghệ rất tiên tiến. Năm 2020, để bảo vệ lãnh thổ tốt hơn, các chú hamster quyết định xây một bức tường lớn bao quanh những khu vực quan trọng của vương quốc.

Vương quốc được biểu diễn bằng một đa giác lồi $n$ đỉnh. Các đỉnh được đánh số từ $1$ đến $n$ theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Đỉnh thứ $i$ có tọa độ $(x_i,y_i)$. Các chú hamster muốn chọn $6$ đỉnh phân biệt (trong số $n$ đỉnh) và xây một bức tường hình lục giác lồi nối $6$ đỉnh này. Hơn nữa, họ muốn bức tường dài nhất có thể, tức là lục giác có chu vi lớn nhất.

Với mỗi đỉnh của vương quốc, các chú hamster muốn biết: nếu chọn đỉnh này làm một đỉnh của lục giác (cùng với $5$ đỉnh khác), thì bức tường dài nhất có thể xây là bao nhiêu?

Dù có công nghệ tiên tiến, máy tính của các chú hamster đã bị treo khi chạy chương trình vét cạn cho bài toán này. Hãy giúp họ!

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$.

Dữ liệu ra

In ra đúng $n$ dòng, dòng thứ $i$ chứa chu vi lớn nhất của một lục giác lồi có đỉnh thứ $i$ là một trong các đỉnh.

Đáp án được chấp nhận nếu sai số tương đối hoặc tuyệt đối không vượt quá ${10}^{-3}$. Cụ thể, nếu đáp án của bạn là $a$ và đáp án của ban giám khảo là $b$, đáp án được chấp nhận khi $\frac{|a-b|}{max(1,b)}\le {10}^{-3}$.

Ràng buộc

• $6\le n\le 2000$.
• $-{10}^9\le x_i,y_i\le {10}^9$.
• Các đỉnh tạo thành một đa giác lồi, liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Ví dụ