#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
const int maxn = 1e6 + 5e5, maxm = 5e3 + 10, lg = 20, mod = 998244353,
          inf = 1e18;
int n, m, k, mn[maxn], mx[maxn], s[maxn], t[maxn], we[lg + 1];
string second, T;
int gnum(string s) {
  int ret = 0;
  for (auto c : s) ret = ret * 2 + c - '0';
  return ret;
}
void mini(int &x, int y) {
  if (x > y) x = y;
}
void maxi(int &x, int y) {
  if (x < y) x = y;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  memset(mn, 69, sizeof(mn)), memset(mx, 0, sizeof(mx)),
      iota(we, we + lg + 1, 0);
  cin >> n >> m >> k >> second >> T;
  mini(mn[s[0] = gnum(second)], 0);
  maxi(mx[t[0] = gnum(T)], 0);
  for (int i = 1; i <= n; i++) {
    int A, B;
    cin >> A >> B;
    int a = we[k - A], b = we[k - B];
    if ((s[i - 1] >> a & 1) ^ (s[i - 1] >> b & 1)) s[i] ^= (1 << a) ^ (1 << b);
    if ((t[i - 1] >> a & 1) ^ (t[i - 1] >> b & 1)) t[i] ^= (1 << a) ^ (1 << b);
    mini(mn[s[i] ^= s[i - 1]], i);
    maxi(mx[t[i] ^= t[i - 1]], i);
    swap(we[k - A], we[k - B]);
  }
  int dd = 0;
  for (int msk = (1 << k); msk; msk--) {
    for (int i = 0; i < k; i++)
      if (msk >> i & 1) {
        mini(mn[msk ^ (1 << i)], mn[msk]);
        maxi(mx[msk ^ (1 << i)], mx[msk]);
      }
    if (mx[msk] - mn[msk] >= m &&
        (__builtin_popcount(msk)) > (__builtin_popcount(dd)))
      dd = msk;
  }
  cout << k - (__builtin_popcount(s[0])) - (__builtin_popcount(t[0])) +
              2 * (__builtin_popcount(dd))
       << endl
       << mn[dd] + 1 << ' ' << mx[dd];
  return 0;
}
