Input
5 7 2 4 5 1 2 3 3 4 4 1 5 3 3 5
Output
10 9 10 10 9
Input
2 3 1 2 1 2 1 2
Output
5 6