Photo to Remember

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 ₁, b ₂, …, b _n, where b _i — the total number of pixels on the minimum photo containing all friends expect for the i-th one.

Examples

input

3
1 10
5 5
10 1

output

75 110 60 

input

3
2 1
1 2
2 1

output

6 4 6 

Solution:

#include <cstring>
#include <vector>
#include  	<list>
#include

<map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

using namespace std;

const int N = 1234567;

int w[N], h[N];

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
    scanf("%d %d", w + i, h + i);
  }
  h[n] = -1;
  int m1 = n, m2 = n;
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += w[i];
    if (h[i] > h[m1]) {
m2 = m1;
m1 = i;
} else {
if (h[i] > h[m2]) {
m2 = i;
}
}
}
for (int i = 0; i < n; i++) {
    if (i > 0) printf(" ");
printf("%d", (sum - w[i]) * (i == m1 ? h[m2] : h[m1]));
}
printf("\n");
return 0;
}