#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
int main(){
    int N, C, Q;
    
    std::string s;
    std::cin >> N >> C >> Q ;
    std::cin >> s;
    
   
    int L,R;
    std::vector<int> niz_cena(Q);
    
    for(int i = 0; i < Q; i++){
        std::cin >> L >> R;
       
        for(int j = L - 1; j <= R - 1 ; j++){
            if(s[j] == '1')
            s[j] = '0';
            else
            s[j] = '1';
        }
        
        
        // pocinjemo drugi deo
        
        int broj_jedinica = 0;
        int duzina;
        
        
        int cena = 0;
        for(int j = 0; j < s.size(); j++)
            if(s[j] == '1')
            broj_jedinica++;
     
        
        int l1 = 0;
        int r1 = s.size() - 1;
        while(s[l1] == '0')
        l1++;
        while(s[r1] == '0')
        r1--;
        
        int broj_nula = s.size() - broj_jedinica;
        if(broj_jedinica <= C){
            cena = broj_jedinica;
        }
        else {
            int sum = r1 - l1 + 1;
            broj_nula = sum - broj_jedinica;
            if(broj_nula + C < broj_jedinica)
            cena = broj_nula + C;
            else 
            cena = broj_jedinica;
        }

        
        niz_cena[i] = cena;
    }
    
    for(int i = 0; i < Q; i++)
    std::cout << niz_cena[i] << std::endl;
    return 0;
}