Nguồn đề: thầy Nguyễn Thanh Tùng

Các nhà bác học thế giới dự định tạo một ngân hàng gien tất cả các động thực vật nằm trong danh sách đỏ. Tòa nhà lưu trữ gien phải được bảo vệ kép ở dạng hai phòng lồng vào nhau.

Hiện tại đang có máy in 3D cho phép in n loại phòng hình chữ nhật, loại thứ i có cạnh chạy từ tây sang đông có độ dài ~a_i~, cạnh kia có độ dài ~b_i~ chạy từ bắc xuống nam và không đổi hướng khi in.

Căn phòng kích thước ~a_i~ x ~b_i~ lồng được vào trong phòng kích thước ~a_j~ x ~b_j~ nếu ~a_i \leq a_j~ và ~b_i \leq b_j~. Để nâng cao hệ số bảo vệ phòng trong và phòng ngoài phải thuộc hai loại khác nhau.

Người ta được phép xây dựng phòng trong theo kiểu tùy chọn trong số n loại đã có. Nếu chọn loại phòng trong có kích thước ~a_i~ x ~b_i~ thì có thể chọn phòng ngoài loại ~a_j~ x ~b_j~ nào đó, mở rộng kích thước thành ~a~x~b~ để thỏa mãn điều kiện ~a \ge a_i~, ~b \ge b_i~. Nhưng như vậy phải viết thêm chương trình mới và cải tiến thiết bị in với chi phí là (a+b) - ~(a_j + b_j)~.

Chi phí cho dự án có hạn nên Hội đồng khoa học quyết định trước hết khảo sát, nếu chọn phòng trong là loại i với i = 1, 2, .. ,n thì chi phí bổ sung tối thiểu để có phòng ngoài thích hợp là bao nhiêu.

Hãy xác định chi phí bổ sung tối thiết cần thiết cho mỗi loại phòng trong với các mẫu hiện có.

Input

• Dòng đầu tiên chứa số nguyên n ~(2 \leq n \leq 10^{5} )~.
• Dòng thứ i trong n dòng tiếp theo chứa 2 số nguyên ~a_i~ và ~b_i~, ghi cách nhau một dấu cách ~( 1 \leq a_i, b_i \leq 10^9)~.

Output

• In ra một dòng gồm n số nguyên, số thứ i ứng với chi phí bổ sung tối thiểu nếu chọn phòng trong loại i, i = 1, 2, 3, .., n. Các số ghi cách nhau một dấu cách.

Sample Input 1

5
4 4
6 3
2 5
7 2
1 10

Sample Output 1

1 1 1 1 5