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*<sub class="lower-index">*i*</sub> pixels and height *h*<sub class="lower-index">*i*</sub> 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.
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*<sub class="lower-index">*i*</sub>, *h*<sub class="lower-index">*i*</sub> (1 ≤ *w*<sub class="lower-index">*i*</sub> ≤ 10, 1 ≤ *h*<sub class="lower-index">*i*</sub> ≤ 1000) — the width and height in pixels of the corresponding rectangle.
def main():
    n = int(input())
    ww, hh = [0] * n, [0] * n
    for i in range(n):
        w, h = map(int, input().split())
        ww[i], hh[i] = w, h
    width = sum(ww)
    tree = [hh]
    l = hh
    while len(l) > 7:
        l = [max(l[_:_ + 8]) for _ in range(0, len(l), 8)]
        tree.append(l)
    tree1 = tree[1:]
    top = tree[-1]
    top.append(0)
    prewh = 1
    for i, w in enumerate(ww):
        h, hh[i], key = hh[i], 1, i
        for src, dest in zip(tree, tree1):
            key &= 0x7FFFFFF8
            value = max(src[key:key + 8])
            key //= 8
            dest[key] = value
        top[-1] = prewh
        ww[i] = (width - w) * max(top)
        hh[i] = prewh = h
    print(' '.join(map(str, ww)))


if __name__ == '__main__':
    main()