Một nhóm gồm N bạn rủ nhau chụp hình Giáng Sinh. Họ đã tìm được một địa điểm chụp hình dưới chân cầu Rồng-Tp Đà Nẵng, phong cảnh giáng sinh ở đây rất đẹp. Nhóm bạn này muốn ghi lại kỉ niệm mùa đông trong không khí tràn ngập Noel ở đây trong một số bức ảnh để làm kỷ niệm với mong muốn là trong những bức ảnh này phải có mặt tất cả mọi người trong nhóm. Nhưng không may cho họ là tại địa điểm này ai cũng đông đúc và họ ngại nhờ người ngoài nhóm để nhờ họ bấm máy giúp, cho nên mỗi người phải thay nhau chụp ảnh cho các thành viên còn lại của nhóm. Như vậy, để tất cả mọi người đều có mặt trong ảnh, họ phải chụp N tấm ảnh có chung một hậu cảnh. Bức ảnh thứ i (i=1…N) sẽ do người thứ i chụp vì vậy người này sẽ không có mặt trong bức ảnh này.

Trong mỗi bức ảnh, mọi người sẽ đứng theo một hàng ngang và mỗi người sẽ chiếm một diện tích được giới hạn bởi hình chữ nhật bao người đó. Hình chữ nhật giới hạn trong ảnh của người thứ i có chiều ngang là Wi và chiều cao là Hi. Các hình chữ nhật liền kề nhau không chồng lấn lên nhau và cũng không tách rời nhau theo chiều ngang. Diện tích tối thiểu của bức ảnh sẽ là W * H, trong đó W là tổng chiều ngang của tất cả các hình chữ nhật còn H là chiều cao lớn nhất của hình chữ nhật giới hạn của người cao nhất có mặt trong ảnh.

Yêu cầu: Bạn hãy tính diện tích tối thiểu của mỗi bức ảnh trong N bức ảnh đã chụp ở trên. Dữ liệu vào: Tệp văn bản PHOTO.INP gồm:

• Dòng đầu ghi số nguyên N (2≤N≤200000).

• Trong N dòng tiếp theo, với dòng thứ i ghi hai số nguyên Wi và Hi 1≤Wi≤10, 1 ≤ Hi≤1000).

Kết quả ra:

Tệp văn bản PHOTO.OUT ghi N số nguyên trên cùng một dòng, với số thứ i là diện tích tối thiểu của bức ảnh thứ i. Các số cách nhau đúng một dấu cách.

Ví dụ:

PHOTO.INP

3
2 1
1 2
2 1

PHOTO.OUT

6 4 6