Giải bài trực tuyến

Để chọn ra đội tuyển tham dự Olympic Tin học quốc tế (IOI), N thí sinh phải trải qua hai kỳ thi là thi học sinh giỏi quốc gia vòng 2 và Olympic Tin học châu Á Thái Bình Dương (APIO). Cả hai kỳ thi trên đều đã kết thúc, mỗi thí sinh đã biết kết quả của mình, trong đó với thí sinh thứ i, X_i là kết quả thi vòng 2 còn Y_i là kết quả thi APIO của thí sinh đó. Tuy nhiên, dù đã biết kết quả nhưng các thí sinh vẫn chưa thể biết chắc liệu mình có được chọn vào đội tuyển IOI hay không, bởi vì người ta xếp hạng thí sinh theo tổng số điểm của hai cuộc thi nhân với hai hệ số nào đó. Tức là, ban tổ chức sẽ chọn ra hệ số là một cặp số thực dương (a, b), sau đó điểm để xếp hạng IOI sẽ được tính bằng công thức: a * X_i + b * Y_i. 4 thí sinh có điểm xếp hạng cao nhất sẽ được chọn vào đội tuyển IOI.

Mỗi thí sinh đều đã biết điểm của mình và điểm của những người khác, tuy nhiên họ rất hoang mang vì không biết hệ số được chọn có lợi cho mình hay không. Mỗi người đều muốn biết là, mình sẽ đứng cao nhất là thứ mấy và thấp nhất là thứ mấy, với tất cả các bộ hệ số có thể. Thứ hạng của một người được tính bằng số người có điểm xếp hạng cao hơn họ cộng thêm 1, lưu ý là với một cặp hệ số mà có nhiều người bằng điểm nhau thì một người không đứng trên những người bằng điểm họ. Cặp hệ số được chọn cũng phải là số dương. Hãy viết chương trình giúp họ trả lời câu hỏi đó.

Input

            Dòng đầu gồm một số nguyên N, số thí sinh tham gia thi.

            N dòng tiếp theo, mỗi dòng gồm hai số nguyên X_i và Y_i, kết quả thi của các thí sinh.

Output

            In ra N dòng, mỗi dòng gồm hai số nguyên in cách nhau bởi dấu cách, lần lượt là thứ hạng cao nhất có thể và thứ hạng thấp nhất có thể của các thí sinh.

Giới hạn

            1 <= N <= 2000.

            0 <= X_i, Y_i <= 10⁶.

            30% số điểm có 1 <= N <= 20.

            30% số điểm khác có 1 <= N <= 100.

Example

Input:
5
1 3
5 2
1 4
2 5
3 3

Output:
4 5
1 5
2 4
1 3
2 3