#include <bits/stdc++.h>
const int MAXN = 1e6 + 5;
int n, m, k;
char str[21];
int x[MAXN], y[MAXN];
int s[MAXN], t[MAXN];
int p[21];
int f[(1 << 20) + 3], g[(1 << 20) + 3];
inline void presum() {
  for (int i = 0; i <= k - 1; ++i) {
    for (int S = 0; S <= (1 << k) - 1; ++S) {
      if ((S >> i) & 1) continue;
      f[S] = std::min(f[S ^ (1 << i)], f[S]);
      g[S] = std::max(g[S ^ (1 << i)], g[S]);
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  scanf("%s", str);
  for (int i = 0; i <= k - 1; ++i)
    if (str[i] == '1') s[0] |= (1 << i);
  scanf("%s", str);
  for (int i = 0; i <= k - 1; ++i)
    if (str[i] == '1') t[0] |= (1 << i);
  for (int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
  for (int i = 1; i <= k; ++i) p[i] = i;
  for (int i = 1; i <= n; ++i) {
    int p1 = -1, p2 = -1;
    for (int j = 1; j <= k; ++j) {
      if (p[j] == x[i]) p1 = j;
      if (p[j] == y[i]) p2 = j;
    }
    std::swap(p[p1], p[p2]);
    for (int j = 0; j <= k - 1; ++j)
      if ((s[0] >> (p[j + 1] - 1)) & 1) s[i] |= 1 << j;
    for (int j = 0; j <= k - 1; ++j)
      if ((t[0] >> (p[j + 1] - 1)) & 1) t[i] |= 1 << j;
  }
  for (int i = 0; i <= (1 << k) - 1; ++i) f[i] = 1e9, g[i] = -1e9;
  for (int i = 0; i <= n; ++i)
    f[s[i]] = std::min(f[s[i]], i), g[t[i]] = std::max(g[t[i]], i);
  presum();
  int ans = -1e9, ansl = -1, ansr = -1;
  for (int S = 0; S <= (1 << k) - 1; ++S) {
    if (g[S] - f[S] >= m && __builtin_popcount(S) > ans) {
      ans = __builtin_popcount(S);
      ansl = f[S] + 1;
      ansr = g[S];
    }
  }
  ans = 2 * ans + k - __builtin_popcount(s[0]) - __builtin_popcount(t[0]);
  printf("%d\n%d %d\n", ans, ansl, ansr);
  return 0;
}
