// Sample Input 1
4 2
2 2
1 -3

// Sample Input 2
2 4
-2 2
2 2
2 1
-1 2

// Sample Input 3
40 10
13 -12
6 4
-19 -17
-6 4
-10 -10
16 17
32 34
-3 -2
-11 -12
37 -36

// Sample Output 1
0
1
2
2
1

// Sample Output 2
0
1
1

// Sample Output 3
0
0
0
4
130
2052
20958
155678
896220
4160798
16004412
51999948
144776190
349181040
735692490
364558777
233997014
242620671
184707628
808271668
924963778
496489648
654440271
639886064
690035227
954668130
474278220
205649340
77168754
24784920
6715462
1505398
271728
37950
3848
252
8
0
0
0
0