using System;
using System.Linq;
using System.Security.Cryptography;
using System.Collections.Generic;
namespace C
{
    class Program
    {
        static void lr(int l, int r, ref char[] cn, ref int br0p, ref int br0k, ref List<int> b)
        {
            int rbr = 0;//redni broj - potreban za listu
            int x;
            if (cn[0] == '0')
            {
                b.Add(-1);
                x = -1;
            }
            else
            {
                b.Add(1);
                x = 1;
            }
            for (int i = 1; i < l - 1; i++)
            {
                if (cn[i] != cn[i - 1])
                {
                    x *= (-1);
                    b.Add(x);
                    rbr++;
                }
                else
                {
                    b[rbr] += x;
                }
            }
            for (int i = l - 1; i < r; i++)
            {
                if (cn[i] == '1')
                {
                    cn[i] = '0';
                }
                else
                {
                    cn[i] = '1';
                }
                if (i > 0)
                {
                    if (cn[i] != cn[i - 1])
                    {
                        x *= (-1);
                        b.Add(x);
                        rbr++;
                    }
                    else
                    {
                        b[rbr] += x;
                    }
                }
                else
                {
                    b.Clear();
                    rbr = 0;
                    if (cn[0] == '0')
                    {
                        b.Add(-1);
                        x = -1;
                    }
                    else
                    {
                        b.Add(1);
                        x = 1;
                    }
                }
            }
            for (int i = r; i < cn.Length; i++)
            {
                if (cn[i] != cn[i - 1])
                {
                    x *= (-1);
                    b.Add(x);
                    rbr++;
                }
                else
                {
                    b[rbr] += x;
                }
            }
            if (b[0] < 0)
            {
                br0p = b[0] * (-1);
                b.RemoveAt(0);
            }
            if (b[b.Count - 1] < 0)
            {
                br0k = b[b.Count - 1] * (-1);
                b.RemoveAt(b.Count - 1);
            }
        }
        static void lr2(ref List<int> b, int k1, int k2, ref int br0p, ref int br0k)//samo promena
        {
            int a2 = Math.Max(k1, k2);
            int a1 = Math.Min(k1, k2);
            for (int i = k1; i < k2 + 1; i++)
            {
                b[i] *= (-1);
            }
            for (int i = 0; i < b.Count; i++)
            {
                if (b[i] == 0)
                {
                    br0p++;
                }
                else
                {
                    i = b.Count;
                }
            }
            for (int i = b.Count - 1; i > -1; i--)
            {
                if (b[i] == 0)
                {
                    br0p++;
                }
                else
                {
                    i = -1;
                }
            }
        }
        static int brjedinicaunizu(List<int> b)//za odredjivanje broja jedinica u nizu	
        {
            int j = b.Count;
            int x = 0;
            for (int i = 0; i < j; i++)
            {
                if (b[i] > 0)
                {
                    x += b[i];
                }
            }
            return x;
        }
        static int pindeks(int br0p, List<int> b, int j)//za odredjivanje indeksa od kog se vrsi promena
        {
            for (int i = 0; i < j; i++)
            {
                br0p += Math.Abs(b[i]);
            }
            return br0p;
        }
        static int kindeks(int br0p, List<int> b, int j)//za odredjivanje indeksa do kog se vrsi promena
        {
            for (int i = 0; i <= j; i++)
            {
                br0p += Math.Abs(b[i]);
            }
            return br0p - 1;
        }
        static int dobitak(int k1, int k2, List<int> b, int c)//za odredjivanje dobitka pri promeni (broj novcica promenjenih u nulu - broj promenjenih u jedinicu - C)
        {
            int a2 = Math.Max(k1, k2);
            int a1 = Math.Min(k1, k2);
            int d = 0;
            for (int i = a1; i <= a2; i++)
            {
                d += b[i];
            }
            return d - c;
        }
        static void Main(string[] args)
        {
            string[] a = Console.ReadLine().Split();
            int n = int.Parse(a[0]);
            int c = int.Parse(a[1]);
            int q = int.Parse(a[2]);
            int br1 = 0;//broj jedinica u nizu
            string s = Console.ReadLine();
            char[] cn = s.ToCharArray();
            int[] brn = new int[q];//krajnji niz
            bool g = true;
            List<int> b = new List<int>();//sluzi za podelu na grupe ()
            int br0p = 0;//broj nula na pocetku niza
            int br0k = 0;//broj nula na kraju niza
            int br = 0;
            for (int i = 0; i < q; i++)
            {
                a = Console.ReadLine().Split();
                int l = int.Parse(a[0]);
                int r = int.Parse(a[1]);
                lr(l, r, ref cn, ref br0p, ref br0k, ref b);
                while (g)
                {
                    br1 = brjedinicaunizu(b);
                    if (br1 < c + 1)
                    {
                        brn[i] += br1;
                        g = false;
                    }
                    else
                    {
                        int x1 = b.Count;
                        int a1 = 0, b1;//pocetna i krajnja pozicija za promenu
                        int k1 = 0, k2 = 0;//pocetna grupa (od koje pocinje promena) i krajnja grupa (na kojoj se zavrsava promena)
                        int[] dobici = new int[x1];
                        int[] krajnjiindeksi = new int[x1];//pocetni indeks je uvek a1
                        bool v = true;
                        while (v)
                        {
                            for (int j = 0; j < x1; j++)
                            {
                                if (b[j] > c - br)
                                {
                                    a1 = pindeks(br0p, b, j);
                                    k1 = j;
                                    j = x1;
                                }
                            }
                            if (a1 == 0)
                            {
                                br++;
                            }
                            else
                            {
                                v = false;
                            }
                        }
                        for (int j = 0; j < x1; j++)//petlja za nalazenje druge pozicije
                        {
                            b1 = kindeks(br0p, b, j);
                            k2 = j;
                            dobici[j] = (dobitak(k1, k2, b, c));
                            krajnjiindeksi[j] = b1;
                        }
                        Array.Sort(dobici, krajnjiindeksi);
                        if (dobici[dobici.Length - 1] < 0)
                        {
                            brn[i] += br1;
                            g = false;
                            br1 = 0;
                        }
                        else
                        {
                            brn[i] += c;
                            lr2(ref b, k1, k2, ref br0p, ref br0k);
                        }
                    }
                }
                b.Clear();
                g = true;
            }
            for (int i = 0; i < brn.Length; i++)
            {
                Console.WriteLine("{0}", brn[i]);
            }
        }
    }
}