input:

100 100000
0000011010101000111011110110000111110101101010111111101011011010111001111010111000001000011000001010
76 99 3
25 84 7
45 83 11
10 12 10
69 86 4
27 28 1
22 42 42
4 86 25
26 91 22
20 81 17
50 78 0
77 93 50
31 50 34
7 46 13
78 89 0
79 98 0
2 84 33
58 93 11
56 75 2
55 77 68
7 9 41
44 46 11
47 ...

output:

18
16
10
0
12
0
0
0
1
6
29
0
0
0
12
20
0
10
10
0
0
0
0
2
0
0
0
16
18
10
0
57
0
0
11
0
14
0
0
3
0
4
0
0
0
6
0
0
1
0
3
6
5
0
22
0
0
0
15
10
0
0
3
0
3
0
1
17
15
0
0
0
6
0
8
3
1
16
0
19
29
40
21
12
26
0
21
6
1
13
19
8
6
8
5
6
0
8
11
0
7
2
51
0
0
7
22
11
0
21
12
9
15
0
16
22
3
24
4
27
0
0
0
0
0
0
11
46
5...

result:

wrong answer 1st numbers differ - expected: '8', found: '18'