我用过的数据

输入

15 5
0 1 1 0 1 0 1 1 1 1 0 1 0 1 0
4 6 9
3 2 9
3 12 12
1 3 10
4 4 13

输出

4
6
0
8

输入

10 10
1 0 0 0 1 0 1 1 0 1 
0 6 8
1 0 8
2 1 7
2 6 6
4 6 8
1 6 6
4 6 7
0 0 6
1 5 7
4 9 9

输出

1
1
1

输入

10 2
1 1 1 0 1 0 1 0 0 1
0 5 9
4 4 6

输出

1