#include <bits/stdc++.h>
using namespace std;
class permutation {
 public:
  vector<int> p, ip;
  permutation(int k) : p(vector<int>(k)), ip(vector<int>(k)) {
    for (int i = 0; i < k; i++) p[i] = ip[i] = i;
  }
  void myswap(int a, int b) {
    swap(p[a], p[b]);
    swap(ip[p[a]], ip[p[b]]);
  }
  int get(string s) {
    int ans = 0;
    for (int i = 0; i < s.size(); i++) ans |= (1 << i) * (s[p[i]] - '0');
    return ans;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  string s, t;
  cin >> s >> t;
  permutation p(k);
  vector<int> vs(n + 1), vt(n + 1);
  for (int i = 0, a, b; i <= n; i++) {
    vs[i] = p.get(s);
    vt[i] = p.get(t);
    if (i == n) continue;
    cin >> a >> b;
    p.myswap(p.ip[--a], p.ip[--b]);
  }
  vector<int> left((1 << k), n + 1), right((1 << k), -1);
  for (int i = 0; i <= n; i++) {
    left[vs[i]] = min(left[vs[i]], i);
    right[vt[i]] = max(right[vt[i]], i);
  }
  for (int i = (1 << k) - 1; i >= 0; i--) {
    for (int j = 0; j < k; j++) {
      if (!(i & (1 << j))) continue;
      left[i ^ (1 << j)] = min(left[i ^ (1 << j)], left[i]);
      right[i ^ (1 << j)] = max(right[i ^ (1 << j)], right[i]);
    }
  }
  pair<int, int> best(1, n);
  int ans = 0, s1 = count(s.begin(), s.end(), '1'),
      t1 = count(t.begin(), t.end(), '1');
  for (int i = 0; i < (1 << k); i++) {
    if (left[i] + m <= right[i]) {
      int bits = 0;
      for (int j = 0; j < k; j++)
        if (i & (1 << j)) bits++;
      if (bits > ans) {
        ans = bits;
        best.first = left[i] + 1, best.second = right[i];
      }
    }
  }
  ans = 2 * ans + k - s1 - t1;
  cout << ans << "\n" << best.first << " " << best.second << "\n";
  return 0;
}
