#include<bits/stdc++.h> using namespace std; #define int long long int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=2000010; int n,m,k,cnt,ans,L,R,a[MAXN],p[MAXN],u[MAXN],v[MAXN],to[MAXN],f[MAXN],g[MAXN]; char c[MAXN]; #define popcnt __builtin_popcount string ejz(int x){string res="";for(int i=0;i<k;i++)res+=x&(1<<i)?"1":"0";return res;} void slv(){ n=read(),m=read(),k=read(); scanf("%s",c+1); for(int i=1;i<=k;i++)a[i]=c[i]-'0',cnt-=a[i]; scanf("%s",c+1); for(int i=1;i<=k;i++)p[i]=c[i]-'0',cnt-=p[i];cnt+=k; for(int i=1;i<=n;i++)u[i]=read(),v[i]=read(); for(int i=1;i<=k;i++)to[i]=i; memset(f,0x3f,sizeof(f)); for(int i=n;i>=1;i--){ swap(to[u[i]],to[v[i]]); int s=0; for(int j=1;j<=k;j++)s+=a[j]<<to[j]-1; f[s]=i; // cout<<i<<" "<<ejz(s)<<endl; } for(int i=1;i<=k;i++)to[i]=i; for(int i=n;i>=1;i--){ swap(to[u[i]],to[v[i]]); int s=0; for(int j=1;j<=k;j++)s+=p[j]<<to[j]-1; if(!g[s])g[s]=i; } for(int i=0;i<k;i++){ for(int j=0;j<1<<k;j++)f[j]=min(f[j],f[j|(1<<i)]),g[j]=max(g[j],g[j|(1<<i)]); } for(int i=0;i<1<<k;i++){ if(g[i]-f[i]>=m&&popcnt(i)>=ans)ans=popcnt(i),L=f[i],R=g[i]-1; } printf("%lld\n%lld %lld\n",cnt+ans*2,L,R); } signed main(){ // freopen("game.in","r",stdin);freopen("game.out","w",stdout); slv(); return 0; }