Input
2 5 10 10 1 1 2 2 1 2 5 1 1 2 2 2 2 6 1 1 2
Output
20 10 5