本来以为能得60分的，但第二个测试点WA了

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
ll n,m,q;
string s;
int F0;
int F1;
ll nxt[50000010];
int main(){
	//freopen("kingdom4.in","r",stdin);
	//freopen("kingdom4.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='1') F1=1;
		if(s[i]=='0') F0=1;	
	}
	if(!F1){
		while(q--){
			ll st,k;
			cin>>st>>k;
			cout<<(st%MOD+k%MOD)%MOD<<endl;
		}
	}
	else if(!F0){
		while(q--){
			ll st,k;
			cin>>st>>k;
			cout<<(st%MOD+(k%MOD)*(m%MOD))%MOD<<endl;
		}
	}
	
	else if(n<=200){
		string ss;
		for(int i=1;i<=110;i++){
			ss+=s;			                                                                                                                    
		}
		ss="*"+ss; 
		while(q--){
			ll st,k;
			cin>>st>>k;
			while(k--){
				int f=0;
				for(int i=m+st;i>=st+1;i--){
					//cout<<ss[i]<<" ";
					if(ss[i]=='1'){
						f=1;
						st=i;
						break;
					}
				}
				if(!f){
					st++;
				}
			}
			cout<<st<<endl;		
		}
	}
	else if(n<=5000){
		string ss="";
		for(int i=1;i<=5000;i++){
			ss+=s;			
		}
		ss="*"+ss;
		int cnt=0;
		for(int i=1;i<=ss.size()-1;i++){
			if(ss[i]=='1'){
				nxt[++cnt]=i;
			}
		}
		while(q--){
			ll st,k;
			cin>>st>>k;
			while(k--){
				int p=lower_bound(nxt+1,nxt+1+cnt,st+m)-nxt;
				while(nxt[p]>st+m){
					p--;
				}
				if(nxt[p]<=st){
					st++;
				}
				else st=nxt[p];
			}
			cout<<st<<endl;
		}
	}
	else if(n<=300000){
		string ss=s;
		ss+=s;
		ss="*"+ss;
		int cnt=0;
		for(int i=1;i<=ss.size()-1;i++){
			if(ss[i]=='1'){
				nxt[++cnt]=i;
			}
		}
		while(q--){
			ll st,k;
			cin>>st>>k;
			while(k--){
				int p=lower_bound(nxt+1,nxt+1+cnt,st+m)-nxt;
				while(nxt[p]>st+m){
					p--;
				}
				if(nxt[p]<=st){
					st++;
				}
				else st=nxt[p];
			}
			cout<<st<<endl;
		}
	}
	else {
		while(q--){
			ll s,k;
			cin>>s>>k;
			if(k==0){
				cout<<s%MOD<<endl;
			}
		}
	}
}