#include <bits/stdc++.h>
using namespace std;
int app(int b, int x, int y) {
  if (x == y) return b;
  int bx = (b >> x) & 1;
  int by = (b >> y) & 1;
  if (bx == by) return b;
  return b ^ (1 << x) ^ (1 << y);
}
int N, M, K;
int Read() {
  char In[22];
  scanf("%s", In);
  int res = 0;
  for (int i = 0; i < K; i++) res |= (In[i] - '0') << i;
  return res;
}
int X[1000010], Y[1000010];
int C[1 << 20], D[1 << 20], TC[1 << 20];
int main() {
  scanf("%d%d%d", &N, &M, &K);
  int A = Read(), B = Read();
  for (int i = 1; i <= N; i++) {
    scanf("%d%d", X + i, Y + i);
    --X[i];
    --Y[i];
  }
  const int INF = 1e9;
  for (int i = 0; i < 1 << K; i++) C[i] = -INF, D[i] = INF;
  C[B] = N + 1;
  D[A] = N + 1;
  int perm[22];
  for (int i = 0; i < (K); i++) perm[i] = i;
  for (int i = N; i; i--) {
    swap(perm[X[i]], perm[Y[i]]);
    int ta = 0;
    for (int j = 0; j < (K); j++)
      if (1 << j & A) ta |= 1 << perm[j];
    D[ta] = min(D[ta], i);
    int tb = 0;
    for (int j = 0; j < (K); j++)
      if (1 << j & B) tb |= 1 << perm[j];
    C[tb] = max(C[tb], i);
  }
  for (int a = K; a >= 0; a--) {
    int ok = 0, fi = -1, fj = -1;
    for (int i = 0; i < (1 << K); i++)
      if (C[i] - D[i] >= M) {
        ok = 1;
        fi = D[i], fj = C[i] - 1;
        break;
      }
    if (ok) {
      printf("%d\n%d %d\n", a, fi, fj);
      break;
    }
    for (int i = 0; i < (1 << K); i++) {
      TC[i] = C[i];
      for (int j = 0; j < (K); j++) TC[i] = max(TC[i], C[i ^ 1 << j]);
    }
    for (int i = 0; i < (1 << K); i++) C[i] = TC[i];
  }
  return 0;
}
