#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int n,m,k; int l[2000300],r[2000300]; int p[21]; bool s[2000300][21],t[2000300][21]; int mns[1<<20],mxt[1<<20]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("c.in","r",stdin); // freopen("SS.out","w",stdout); cin>>n>>m>>k; int a=0,b=0; for(int i=0;i<k;i++){ char x; cin>>x; s[0][i]=x-'0'; a+=x-'0'; } for(int i=0;i<k;i++){ char x; cin>>x; t[0][i]=t[n+1][i]=x-'0'; b+=x-'0'; } for(int i=1;i<=n;i++){ cin>>l[i]>>r[i]; l[i]--,r[i]--; } for(int i=0;i<k;i++)p[i]=i; for(int i=n;i>=1;i--){ swap(p[l[i]],p[r[i]]); for(int j=0;j<k;j++) s[i][p[j]]=s[0][j], t[i][p[j]]=t[0][j]; } for(int i=n+1;i>=2;i--){ int w=0; for(int j=0;j<k;j++) w=w|(t[i][j]<<j); // cout<<"t"<<" "<<i<<" "<<w<<endl; mxt[w]=max(mxt[w],i); } memset(mns,0x3f,sizeof(mns)); for(int i=n;i>=1;i--){ int w=0; for(int j=0;j<k;j++) w=w|(s[i][j]<<j); // cout<<"s"<<" "<<i<<" "<<w<<endl; mns[w]=min(mns[w],i); } for(int i=2;i<=(1<<k);i<<=1) for(int j=0;j<(1<<k);j+=i) for(int p=j;p<j+(i>>1);p++){ // cout<<p<<" "<<(p+(i>>1))<<endl; mxt[p]=max(mxt[p],mxt[p+(i>>1)]); mns[p]=min(mns[p],mns[p+(i>>1)]); } int res=-1,l=0,r=0; for(int S=0;S<(1<<k);S++) if(mxt[S]-mns[S]>=m){ int w=__builtin_popcount(S); if(w>res){ res=w; // if(S==15)cout<<mxt[S]<<" "<<mns[S]<<endl; l=mns[S],r=mxt[S]-1; } } cout<<2*res+k-a-b<<endl; cout<<l<<" "<<r<<endl; // for(int i=1;i<=n;i++,cout<<endl){ // cout<<i<<" "; // for(int j=0;j<k;j++) // cout<<s[i][j];} // cout<<endl; // for(int i=2;i<=n+1;i++,cout<<endl){ // cout<<i<<" "; // for(int j=0;j<k;j++) // cout<<t[i][j]; // } cout.flush(); return 0; }