batman-vs-superman
Source: hackerearth
Difficulty: UNKNOWN_DIFFICULTY

The entire world faces the greatest danger as Batman and Superman confront each other. Lex Luthor , inclined to destroy Superman allies with Batman . Batman thinks that Superman has the power to wipe out the entire human race . Luthor gives him a piece of Kryptonite , which can be represented as a string S[] of length M , of only characters ‘a’ and  ‘b’.

Teja ensures Batman that he needs to choose continuous segment of S[] such that it has atleast X number of character ‘a’  and atleast Y number of character ‘b’ . As he is busy to devise the tactics , you need to tell him for Q queries the number of continuous segments between L and R which satisfy the above condition .

Input :-

Given the number of test cases ‘T’ , each test case has the following description.
First line has 3 numbers – M (the length of input string), X (the minimum required frequency of ‘a’ , Y(minimum  required frequency of  ‘b’ in the segment) , and Q(the number of queries).

Second line has the input string S.
Then follows Q lines each having two integers , L and R i.e the lower index and the upper index .

Output :-

For each query of each test case , print number of valid continuous segments between L and R.

Constraints-
1 ≤ T ≤ 100000
1 ≤ X ≤ N ≤ 100000
1 ≤ Y ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ L≤ R ≤ 100000

Sum of N over all test cases in one test file does not exceed 100000
Sum of Q over all test cases in one test file does not exceed 100000

Problem Setter:-
Shivam Garg
Problem Tester:-
Teja Vojjala

SAMPLE INPUT
1
7 2 2 3
aabbbaa
2 4
1 6
3 7

SAMPLE OUTPUT
0
4
2

Explanation

The length of given string is 7 , and we need continuous segments having atleast 2 ‘a’ and 2 ‘b’ . 
In the range 2 – 4, “abb” , we have only 1 ‘a’ . So the answer is 0.
In the range 1 – 6 , “aabbba” , we have valid “aabb” ,” aabbb”, “aabbba” ,”abbba” . So answer is 4. 
In the range 3 – 7  , “bbbaa” , we have “bbbaa” ,” bbaa”. So answer is 2.