Input
2 3 1 1 2 6 5 1 2 2 2 4
Output
2 2 3 4 4 4 4 5 6