using System;

namespace Peti_Zadatak___01_niz
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, c, q, i, j, br = 0, cena;
            string s, unos;
            string[] razdvoj;

            unos = Console.ReadLine();
            razdvoj = unos.Split(' ');
            n = int.Parse(razdvoj[0]);
            c = int.Parse(razdvoj[1]);
            q = int.Parse(razdvoj[2]);

            int[] l = new int[q];
            int[] r = new int[q];

            s = Console.ReadLine();

            char[] novcici = s.ToCharArray();

            for (i = 0; i < q; i++)
            {
                unos = Console.ReadLine();
                razdvoj = unos.Split(' ');
                l[i] = int.Parse(razdvoj[0]);
                r[i] = int.Parse(razdvoj[1]);
            }

            for (i = 0; i < q; i++)
            {
                br = 0;
                for (j = l[i] - 1; j <= r[i] - 1; j++)
                {
                    if (novcici[j] == '0')
                        novcici[j] = '1';
                    else
                        novcici[j] = '0';
                }

                for(j = 0; j < n; j++)
                {
                    if (novcici[j] == '1')
                        br++;
                }

                if (br <= c)
                    cena = br;
                else
                {
                    br = 0;
                    for (j = 1; j < n - 1; j++)
                    {
                        if ((novcici[j - 1] == '1' || novcici[j + 1] == '1') && novcici[j] == '0')
                            br++;
                    }

                    for (j = 0; j < n - 1; j++)
                    {
                        if (novcici[j] == '1' && novcici[j + 1] == '0' && novcici[j + 2] == 0)
                            br--;
                        else
                            break;
                    }

                    for (j = n - 2; j > 0; j--)
                    {
                        if (novcici[j] == '0' && novcici[j - 1] == '0') {
                            br--;
                         }
                        else
                            break;
                    }
                    cena = c + br;
                }

                Console.WriteLine(cena);
            }
        }
    }
}