#include <bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
using namespace std;
const int inf = 1000000010;
const long long INF = 10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 1000010, K = 20;
int n, m, k, u, v, x, y, L, R, ans = -1;
int A[MAXN], B[MAXN];
int S[MAXN], T[MAXN];
int mn[1 << K], mx[1 << K], to[K];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  char ch;
  for (int i = 0; i < k; i++) cin >> ch, S[0] |= ((ch - '0') << i);
  for (int i = 0; i < k; i++) cin >> ch, T[0] |= ((ch - '0') << i), to[i] = i;
  for (int i = 1; i <= n; i++) {
    cin >> A[i] >> B[i];
    swap(to[--A[i]], to[--B[i]]);
    for (int j = 0; j < k; j++) {
      S[i] |= ((((S[0]) >> (j)) & 1) << to[j]);
      T[i] |= ((((T[0]) >> (j)) & 1) << to[j]);
    }
  }
  memset(mn, 31, sizeof(mn));
  memset(mx, -31, sizeof(mn));
  for (int i = 0; i <= n; i++) {
    mn[S[i]] = min(mn[S[i]], i);
    mx[T[i]] = max(mx[T[i]], i);
  }
  for (int j = 0; j < k; j++)
    for (int i = 0; i < (1 << k); i++)
      if ((((i) >> (j)) & 1)) {
        mn[i ^ (1 << j)] = min(mn[i ^ (1 << j)], mn[i]);
        mx[i ^ (1 << j)] = max(mx[i ^ (1 << j)], mx[i]);
      }
  for (int i = 0; i < (1 << k); i++)
    if (mx[i] - mn[i] >= m && __builtin_popcount(i) > ans) {
      ans = __builtin_popcount(i);
      L = mn[i];
      R = mx[i];
    }
  ans *= 2;
  for (int i = 0; i < k; i++)
    ans -= (((S[0]) >> (i)) & 1) + (((T[0]) >> (i)) & 1);
  cout << ans + k << "\n";
  cout << L + 1 << " " << R << "\n";
  return 0;
}
