begin

sample input

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

sample output

2
4
2
5

std:标程看题解//禁止抄袭