B. Фото на память
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На вечеринке встретились 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-го из них.

Примеры
Входные данные
3
1 10
5 5
10 1
Выходные данные
75 110 60
Входные данные
3
2 1
1 2
2 1
Выходные данные
6 4 6