#include <bits/stdc++.h>
const int MK = 20, MN = 1e6 + 5;
int n, m, k, p[MK], f[1 << MK], g[1 << MK], dp[MN];
char s[30], t[30];
int main() {
  std::ios::sync_with_stdio(false);
  std::cin >> n >> m >> k;
  std::cin >> s >> t;
  memset(f, 0x3f, sizeof f);
  int res = 0;
  for (int i = 0; i < k; ++i) {
    res |= (s[i] ^ '0') << i;
    p[i] = i;
  }
  f[res] = 0;
  for (int i = 1; i <= n; ++i) {
    int x, y;
    std::cin >> x >> y;
    --x, --y;
    std::swap(p[x], p[y]);
    res = 0;
    for (int j = 0; j < k; ++j) res |= (s[j] ^ '0') << p[j];
    f[res] = std::min(f[res], i);
    res = 0;
    for (int j = 0; j < k; ++j) res |= (t[j] ^ '0') << p[j];
    dp[i] = res;
  }
  for (int kk = 0; kk <= k; ++kk) {
    for (int i = 1; i <= n; ++i)
      if (i - f[dp[i]] >= m) {
        std::cout << k - kk << std::endl
                  << f[dp[i]] + 1 << " " << i << std::endl;
        return 0;
      }
    for (int S = 0; S < (1 << k); ++S) {
      g[S] = f[S];
      for (int j = 0; j < k; ++j) g[S] = std::min(g[S], f[S ^ (1 << j)]);
    }
    for (int S = 0; S < (1 << k); ++S) f[S] = g[S];
  }
  return 0;
}
