#include <bits/stdc++.h>
using namespace std;
char w1[40], w2[40];
int n, m, k, a[1000005], b[1000005], ans = -1, ansl, ansr, cnt[1 << 20], ofs;
int t1[40], t2[40], g[1 << 20], f[1 << 20][40];
int main() {
  scanf("%d%d%d%s%s", &n, &m, &k, w1 + 1, w2 + 1);
  for (int i = 1; i < 1 << k; i++) cnt[i] = cnt[i ^ (i & -i)] + 1;
  for (int j = 1; j <= k; j++)
    a[0] = (a[0] << 1) ^ w1[j] ^ '0', b[0] = (b[0] << 1) ^ w2[j] ^ '0',
    t1[j] = j;
  ofs = k - cnt[a[0]] - cnt[b[0]];
  for (int i = 0; i < 1 << k; g[i++] = n + 1)
    for (int j = 1; j <= k; j++) f[i][j] = n + 1;
  g[a[0]] = 0;
  for (int i = 1, x, y; i <= n; i++) {
    scanf("%d%d", &x, &y);
    swap(t1[x], t1[y]);
    for (int j = 1; j <= k; j++) t2[t1[j]] = j;
    for (int j = 1; j <= k; j++)
      a[i] = (a[i] << 1) ^ w1[t2[j]] ^ '0',
      b[i] = (b[i] << 1) ^ w2[t2[j]] ^ '0';
    g[a[i]] = min(g[a[i]], i);
  }
  for (int t = 0; t < k; t++)
    for (int j = 0; j < 1 << t; j++)
      for (int i = j; i < 1 << k; i += 1 << t + 1)
        g[i] = min(g[i], g[i ^ (1 << t)]);
  for (int i = 0; i < 1 << k; i++) f[i][cnt[i]] = g[i];
  for (int t = 0; t < k; t++)
    for (int j = 0; j < 1 << t; j++)
      for (int i = j; i < 1 << k; i += 1 << t + 1)
        for (int o = 1; o <= cnt[i]; o++)
          f[i ^ (1 << t)][o] = min(f[i ^ (1 << t)][o], f[i][o]);
  for (int i = 0; i < 1 << k; i++)
    for (int j = k; j; j--) f[i][j - 1] = min(f[i][j - 1], f[i][j]);
  for (int i = m; i <= n; i++) {
    int t = k;
    while (f[b[i]][t] > i - m) t--;
    if (t * 2 + ofs > ans) ans = t * 2 + ofs, ansl = f[b[i]][t] + 1, ansr = i;
  }
  printf("%d\n%d %d\n", ans, ansl, ansr);
  return 0;
}
