input:

3 5
2 6
1 3
4 8
0
1
11
101
0011010

output:

1
6
7
2
2
1

result:

wrong answer 1st lines differ - expected: '6', found: '1'