На вечеринке встретились n друзей, они давно не собирались все вместе и поэтому решили сделать общее групповое фото.
Упрощённо процесс фотографирования можно описать следующим образом. На фотографии каждый из друзей занимает прямоугольник из пикселей: i-й из них занимает прямоугольник ширины wi пикселей и высоты hi пикселей. На групповом фото все фотографируемые стоят в ряд, таким образом минимальный размер в пикселях фотографии, включающей всех друзей, составляет W × H, где W — суммарная ширина всех фотографируемых, а H — максимальная из высот всех фотографируемых.
Как это обычно и бывает, друзья сфотографировались n раз — на j-й (1 ≤ j ≤ n) фотографии присутствовали все, кроме j-го из них, ведь он был фотографом.
Выведите минимальный размер в пикселях каждого из сделанных фото.
Выходные данные
Выведите n разделённых пробелами чисел b1, b2, ..., bn, где bi — общее количество пикселей на минимальной фотографии, вмещающей всех друзей, кроме i-го из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 10
5 5
10 1
|
75 110 60
|
|
2
|
3
2 1
1 2
2 1
|
6 4 6
|