using System;

namespace ConsoleApp4
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] u = Console.ReadLine().Split();
            int n = int.Parse(u[0]);
            int c = int.Parse(u[1]);
            int q = int.Parse(u[2]);
            string s = Console.ReadLine();
            int[] l = new int[q];
            int[] r = new int[q];
            for (int i = 0; i < q; i++)
            {
                string[] p = Console.ReadLine().Split();
                l[i] = int.Parse(p[0]);
                r[i] = int.Parse(p[1]);
            }
            char[] a = new char[s.Length];
            int br = 0;
            foreach (char k in s)
            {
                a[br] = k;
                br++;
            }
            int x, y = 0;
            int broj1 = 0; 
            int broj0=0;
            for (int i = 0; i < q; i++)
            {
                for (int j = l[i] - 1; j < r[i]; j++)
                {                
                        if (a[j]=='1')
                        {
                            a[j] = '0';
                        }
                        else
                        {
                            a[j] = '1';
                        }
                }
                
                for (int j = 0; j < s.Length-1; j++)
                {
                    x = j + 1;
                    
                    if (a[j] == 1 && a[j] == a[x] )
                    {
                        if (y==0)
                        {
                            broj1++;
                        }
                        
                        y = 1;
                    }
                    if (a[j]==1 && a[x]==0)
                    {
                        broj1++;
                    }
                    if (a[j] == 0 && a[j] == a[x])
                    {
                        if (y==1)
                        {
                            broj0++;
                        }
                        y = 0;
                    }
                    if (a[j] == 0 && a[x] == 1)
                    {
                        broj0++;
                    }
                }
                if (broj0+2<broj1)
                {
                    Console.WriteLine(broj0+2);
                }
                else
                {
                    Console.WriteLine(broj1);
                }
            }
        }
    }
}