Input
4 2
10 4 10 15
1 2
4 3
Output
0 0 1 2
Input
10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5
Output
5 4 0 5 3 3 9 0 2 5