有一天,n个朋友在聚会上相遇,他们已经很久没有见面了,所以他们决定一起拍一张合照。
简单来说,拍照的过程可以描述如下。在照片上,每个被拍照的朋友占据一个像素矩形:其中第 i 个占据宽度为 wi 像素、高度为 hi 像素的矩形。在集体照中,所有人站成一排,因此包含所有被拍照好友的照片的最小像素大小为 W × H,其中 W 是所有宽度的总和,H 是所有被拍照好友的最大高度。
通常情况下,朋友们拍了 n 张照片 - 第 j 张 (1 ≤ j ≤ n) 照片上除了第 j 张朋友之外的所有人,因为他是摄影师。
打印每张照片的最小尺寸(以像素为单位)。
输入
第一行包含整数 n (2 ≤ n ≤ 200 000) — 好友数量。
接下来是n行:第i行包含第i个好友的信息。该行包含一对整数 wi, hi (1 ≤ wi ≤ 10, 1 ≤ hi ≤ 1000) — 相应矩形的宽度和高度(以像素为单位)。
输出
打印 n 个以空格分隔的数字 b1, b2, ..., bn,其中 bi — 包含所有朋友期望第 i 张照片的最小照片上的像素总数。
示例
输入 #1
3 1 10 5 5 10 1
输出 #1
75 110 60
输入 #2
3 2 1 1 2 2 1
输出 #2
6 4 6