#include<bits/stdc++.h> #define __pc __builtin_popcount using namespace std; const int S=1.2e6,N=1e6+10; int f[S],g[S]; int a[25],b[25]; int n,m,k; int ap[N],bp[N]; int avi[S]; int compress(int *arr,int len){ int res=0; for(int i=1;i<=k;i++) res<<=1,res+=arr[i]; return res; }int op(int x,int y){ return (!x)?y:x; } int p[25]; int main(){ cin>>n>>m>>k; string s1,s2;cin>>s1>>s2; for(int i=0;i<k;i++) a[i+1]=s1[i]-'0',b[i+1]=s2[i]-'0'; for(int i=1;i<=n;i++) cin>>ap[i]>>bp[i]; memset(f,0x3f,sizeof(f)); memset(g,0,sizeof(g)); int ca=0,cb=0; for(int i=1;i<=k;i++){ if(a[i]==1) ca++; if(b[i]==1) cb++; p[i]=i; } int as,bs; as=compress(a,k),bs=compress(b,k); f[as]=min(f[as],0);g[bs]=max(g[as],0); for(int i=1;i<=n;i++){ int pa=p[ap[i]],pb=p[bp[i]]; swap(p[ap[i]],p[bp[i]]); swap(a[pa],a[pb]); swap(b[pa],b[pb]); as=compress(a,k),bs=compress(b,k); //cout<<as<<' '<<bs<<endl; f[as]=min(f[as],i);g[bs]=max(g[as],i); }int tot=1<<k; /*for(int i=0;i<tot;i++){ //cout<<i<<' '<<f[i]<<' '<<g[i]<<endl; int tim=g[i]-f[i]; if(tim>=m) avi[i]=i; else avi[i]=0; }*/for(int i=0;i<k;i++){ for(int j=0;j<tot;j++){ if((j>>i)&1){ f[j^(1<<i)]=min(f[j^(1<<i)],f[j]); g[j^(1<<i)]=max(g[j^(1<<i)],g[j]); //avi[j^(1<<i)]=op(avi[j^(1<<i)],avi[j]); } } }int av=-1,al=0,ar=0; for(int i=0;i<tot;i++){ if((g[i]-f[i])<m) continue; int A=k+2*__pc(i)-ca-cb; if(A>av){ av=A; al=f[i]+1,ar=g[i]; } }cout<<av<<endl<<al<<' '<<ar<<endl; return 0; }