← 返回题目列表

Codeforces · 522/B

B. 值得记住的照片

中文机器翻译题面 查看原题

有一天,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