Input
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4
Output
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8