Count Substrings

You are given a string S of length N consisting only of 0s and 1s. You are also given an integer K. You have to answer Q queries. In the ith query, two integers Li and Ri are given. Then you should print the number of substrings of S[L, R] which contain at most K 0s and at most K 1s where S[L, R] denotes the substring from Lth to Rth characters of the string S. In other words, you have to count n