#include <bits/stdc++.h>
using namespace std;
template <typename T>
void rd(T& x) {
  int f = 0, c;
  while (!isdigit(c = getchar())) f ^= !(c ^ 45);
  x = (c & 15);
  while (isdigit(c = getchar())) x = x * 10 + (c & 15);
  if (f) x = -x;
}
template <typename T>
void pt(T x, int c = -1) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pt(x / 10);
  putchar(x % 10 + 48);
  if (c != -1) putchar(c);
}
template <typename T>
void umax(T& x, const T& y) {
  if (x < y) x = y;
}
template <typename T>
void umin(T& x, const T& y) {
  if (y < x) x = y;
}
const int N = 1000005;
int n, m, K, a[N], b[N], p[N];
int s, t, f[2][(1 << 20) + 5];
void input(int& x) {
  x = 0;
  for (int i = (0); i <= (K - 1); ++i) {
    int c;
    while (!isdigit(c = getchar()))
      ;
    if (c == '1') x |= 1 << i;
  }
}
int main() {
  rd(n), rd(m), rd(K);
  input(s), input(t);
  for (int i = (1); i <= (n); ++i) rd(a[i]), rd(b[i]);
  for (int i = (1); i <= (K); ++i) p[i] = i;
  memset(f[0], 63, sizeof(f[0]));
  memset(f[1], 192, sizeof(f[1]));
  f[0][s] = f[1][t] = n + 1;
  for (int i = (n); i >= (1); --i) {
    swap(p[a[i]], p[b[i]]);
    int x = 0, y = 0;
    for (int j = (1); j <= (K); ++j) {
      if (s >> (j - 1) & 1) x |= 1 << (p[j] - 1);
      if (t >> (j - 1) & 1) y |= 1 << (p[j] - 1);
    }
    umin(f[0][x], i);
    umax(f[1][y], i);
  }
  int w = K - __builtin_popcount(s) - __builtin_popcount(t);
  int ans = -1, ansl = -1, ansr = -1;
  for (int i = ((1 << K) - 1); i >= (0); --i) {
    for (int j = (0); j <= (K - 1); ++j)
      if (~i >> j & 1) {
        umin(f[0][i], f[0][i ^ (1 << j)]);
        umax(f[1][i], f[1][i ^ (1 << j)]);
      }
    if (f[1][i] - f[0][i] >= m) {
      int now = __builtin_popcount(i) * 2 + w;
      if (ans < now) {
        ans = now;
        ansl = f[0][i], ansr = f[1][i] - 1;
      }
    }
  }
  printf("%d\n%d %d\n", ans, ansl, ansr);
  return 0;
}
