#include <bits/stdc++.h>
using namespace std;
const unsigned seed =
    std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
const int MOD = 998244353;
int getMask(string s) {
  int r = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '1') {
      r |= (1 << i);
    }
  }
  return r;
}
int swapBit(int p, int a, int b) {
  int r = p;
  r = r - (p & (1 << a)) - (p & (1 << b));
  if (p & (1 << a)) {
    r |= (1 << b);
  }
  if (p & (1 << b)) {
    r |= (1 << a);
  }
  return r;
}
void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  string s, t;
  cin >> s >> t;
  vector<pair<int, int>> sw(n);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    sw[i] = {a, b};
  }
  vector<int> dp1((1 << k), 1e9);
  vector<int> dp2((1 << k), -1e9);
  int ma1 = getMask(s);
  int ma2 = getMask(t);
  int dk = __builtin_popcount(ma1) + __builtin_popcount(ma2);
  vector<int> pos(k);
  for (int i = 0; i < k; i++) pos[i] = i;
  for (int i = 0; i <= n; i++) {
    dp1[ma1] = min(dp1[ma1], i);
    dp2[ma2] = max(dp2[ma2], i);
    if (i < n) {
      int a, b;
      for (int j = 0; j < k; j++) {
        if (pos[j] == sw[i].first) a = j;
        if (pos[j] == sw[i].second) b = j;
      }
      swap(pos[a], pos[b]);
      ma1 = swapBit(ma1, a, b);
      ma2 = swapBit(ma2, a, b);
    }
  }
  int ans = -1;
  int al, ar;
  for (int i = (1 << k) - 1; i >= 0; i--) {
    if (dp2[i] - dp1[i] >= m) {
      int r = 2 * __builtin_popcount(i) + k - dk;
      if (r > ans) {
        ans = r;
        al = dp1[i] + 1;
        ar = dp2[i];
      }
    }
    for (int j = 0; j < k; j++) {
      if (i & (1 << j)) {
        int t = i ^ (1 << j);
        dp1[t] = min(dp1[t], dp1[i]);
        dp2[t] = max(dp2[t], dp2[i]);
      }
    }
  }
  cout << ans << "\n";
  cout << al << " " << ar << "\n";
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.precision(10);
  int T = 1;
  for (int i = 1; i <= T; i++) {
    solve();
  }
  cout.flush();
  return 0;
}
