These tests have helped me to solve the problem.

Test #1
input:
A
1
1 1
output:
0

Test #2
input:
Aa
3
1 1
1 2
2 2
output:
010

Test #3
input:
AacCAa
5
1 6
1 2
1 4
2 3
5 6
output:
01001

Test #4
input:
AaCAac
6
1 6
1 2
3 6
4 5
2 3
1 5
output:
111100

But what is wrong with the Test 3 in your example?
The output is correct.