using System;

namespace ConsoleApp1
{
    class Program
    {
        struct promena
        {
            public int l;
            public int d;
        }
        static int raz(char a)
        {
            if (a == 1)
                return 0;
            else
                return 1;
        }
        static void interval(char [] a, int n, out int l, out int d)
        {
            int br = 0;
            int[] pozicije1 = new int[n];
            for (int i = 0; i < n; i++)
            {
                if (a[i] == 1)
                {
                    pozicije1[br] = i;
                    br++;
                }
            }
            l = pozicije1[0];
            d = pozicije1[br - 1];     
        }
        static int radi(promena p, char [] a, int c, int n)
        {
            int br1 = 0;
            int br0 = 0;
            for (int i = p.l; i <= p.d; i++)
            {
                // razmeni u intervalu
                int k = raz(a[i]);
                a[i] = (char)k;
                // odredi broj jedinica i nula
                if (a[i] == 1)
                    br1 += 1;
                else
                    br0 += 1;
            }
            // proveri moze li odmah samo jedinice da se menja
            int l = 0;
            int d = 0;
            if (br1 < c)
                return br1;
            else
            {
                //ovde treba odrediti onaj interval
                interval(a, n, out l, out d);
                for (int i = l; i <= d; i++)
                {
                    // razmeni u intervalu
                    int k = raz(a[i]);
                    a[i] = (char)k;
                }
                int br2 = 0;
                for (int i = 0; i < n; i++)
                {
                    if (a[i] == 1)
                        br2 += 1;

                }
                int s = c + br2;
                return s;
            }
        }
        static void Main(string[] args)
        {
            String[] o = Console.ReadLine().Split();
            int n = int.Parse(o[0]);
            // broj cifara
            int c = int.Parse(o[1]);
            // cena da okrenes sve
            int q = int.Parse(o[2]);
            // broj promena
            string a1 = Console.ReadLine();
            char[] a = new char[n];
            // niz cifara
            for (int i = 0; i < n; i++)
            {
                a[i] = a1[i];
            }
            promena [] p = new promena[q];
            for (int i = 0; i < q; i++)
            {
                String[] o1 = Console.ReadLine().Split();
                p[i].l = int.Parse(o1[0]) - 1;
                p[i].d = int.Parse(o1[1]) - 1;
            }
            // sada prelazim preko svake promene
            int[] u = new int[q];
            for (int i = 0; i < q; i++)
            {
                u[i] = radi(p[i], a, c, n);
            }
            for (int i = 0; i < q; i++)
                Console.WriteLine(u[i]);

        }
    }
}