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
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.
