Input
3
1 10
5 5
10 1
Output
75 110 60
Input
3
2 1
1 2
2 1
Output
6 4 6