One day $*n*$ friends met at a party, they hadn't seen each other for a long time and so they decided to make a group photo together.

Simply speaking, the process of taking photos can be described as follows. On the photo, each photographed friend occupies a rectangle of pixels: the $*i*$-th of them occupies the rectangle of width $*w*_{*i*}$ pixels and height $*h*_{*i*}$ pixels. On the group photo everybody stands in a line, thus the minimum pixel size of the photo including all the photographed friends, is $*W* × *H*$, where $*W*$ is the total sum of all widths and $*H*$ is the maximum height of all the photographed friends.

As is usually the case, the friends made $*n*$ photos — the $*j*$-th ($1 ≤ *j* ≤ *n*$) photo had everybody except for the $*j*$-th friend as he was the photographer.

Print the minimum size of each made photo in pixels.

Input

The first line contains integer $*n*$ ($2 ≤ *n* ≤ 200 000$) — the number of friends.

Then $*n*$ lines follow: the $*i*$-th line contains information about the $*i*$-th friend. The line contains a pair of integers $*w*_{*i*}, *h*_{*i*}$ ($1 ≤ *w*_{*i*} ≤ 10, 1 ≤ *h*_{*i*} ≤ 1000$) — the width and height in pixels of the corresponding rectangle.

Output

Print $*n*$ space-separated numbers $*b*_{1}, *b*_{2}, ..., *b*_{*n*}$, where $*b*_{*i*}$ — the total number of pixels on the minimum photo containing all friends expect for the $*i*$-th one.