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 wi pixels and height hi 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 wi, hi (1 ≤ wi ≤ 10, 1 ≤ hi ≤ 1000) — the width and height in pixels of the corresponding rectangle.

Output

Print n space-separated numbers b1, b2, ..., bn, where bi — 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 
import java.util.*;
import java.io.*;

public class Random {
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] w=new int[n];
        int[] h=new int[n];
        for(int i=0;i<n;i++){
            w[i]=sc.nextInt();
            h[i]=sc.nextInt();
        }

        int sum=0;
        for(int j=0;j<n;j++){
                sum+=w[j];
        }
        int maxh1=-1;
        int maxh2=-1;
        int a=-1;
        for(int j=0;j<n;j++){
            if(h[j]>maxh1){
                maxh1=h[j];
                a=j;
            }
        }
        for(int j=0;j<n;j++){
            if(h[j]>maxh2 && j!=a){
                maxh2=h[j];
            }
        }


        for(int i=0;i<n;i++){
            sum=sum-w[i];
            int height=-1;
            if(h[i]==maxh1)
                height=maxh2;
            else
                height=maxh1;
            System.out.println(sum*height);
            sum=sum+w[i];
        }

    }
}