#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m, kk, p[N], inv[N], popcnt[1 << 20];
char s[25], t[25];
int f[2][1 << 20];
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> kk >> (s + 1) >> (t + 1);
  for (int i = 1; i <= kk; i++) p[i] = i;
  int cnt = 0;
  for (int i = 1; i < (1 << kk); i++) popcnt[i] = popcnt[i >> 1] + (i & 1);
  for (int i = 1; i <= kk; i++) cnt += (s[i] == '1') + (t[i] == '1');
  memset(f[0], 63, sizeof(f[0]));
  memset(f[1], -1, sizeof(f[1]));
  for (int i = 0; i <= n; i++) {
    if (i) {
      int t1, t2;
      cin >> t1 >> t2;
      swap(p[t1], p[t2]);
    }
    for (int j = 1; j <= kk; j++) inv[p[j]] = j;
    int na = 0, nb = 0;
    for (int j = 1; j <= kk; j++)
      na += (1 << (kk - j)) * (s[inv[j]] == '1'),
          nb += (1 << (kk - j)) * (t[inv[j]] == '1');
    f[0][na] = min(f[0][na], i);
    f[1][nb] = max(f[1][nb], i);
  }
  int ans = INT_MIN, l = -1, r = -1;
  for (int i = (1 << kk) - 1; i >= 0; --i) {
    for (int j = 0; j < kk; j++)
      if (i & (1 << j))
        f[0][i ^ (1 << j)] = min(f[0][i ^ (1 << j)], f[0][i]),
                       f[1][i ^ (1 << j)] = max(f[1][i ^ (1 << j)], f[1][i]);
    if (f[1][i] - f[0][i] >= m && popcnt[i] > ans)
      ans = popcnt[i], l = f[0][i] + 1, r = f[1][i];
  }
  ans = ans * 2 + kk - cnt;
  cout << ans << '\n' << l << ' ' << r << endl;
  return 0;
}
