#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void ckmin(T &a, T b) {
  a = min(a, b);
}
template <class T>
inline void ckmax(T &a, T b) {
  a = max(a, b);
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
using uint = unsigned int;
using int64 = long long;
using uint64 = unsigned long long;
using ipair = pair<int, int>;
using VI = vector<int>;
using VD = vector<double>;
inline int op(int set, int a, int b) {
  if ((((set) & (1 << (a))) != 0) != (((set) & (1 << (b))) != 0))
    set ^= (1 << (a)) ^ (1 << (b));
  return set;
}
int main() {
  std::ios::sync_with_stdio(false);
  int n, m, k;
  while (cin >> n >> m >> k) {
    string s1, s2;
    cin >> s1 >> s2;
    int set1 = 0, set2 = 0;
    for (int i = 0; i < (k); ++i)
      if (s1[i] == '1') set1 |= (1 << (i));
    for (int i = 0; i < (k); ++i)
      if (s2[i] == '1') set2 |= (1 << (i));
    VI p1(n), p2(n);
    for (int i = 0; i < (n); ++i) {
      cin >> p1[i] >> p2[i];
      --p1[i];
      --p2[i];
    }
    VI f((1 << (k)), k + 1);
    VI g((1 << (k)), -1);
    VI que;
    auto add = [&](int set, int d, int key) {
      if (d >= f[set]) return;
      f[set] = d;
      g[set] = key;
      que.push_back(set);
    };
    VI ret{k + 1};
    vector<VI> pets(n + 1, VI(k));
    for (int i = 0; i < (k); ++i) pets[n][i] = i;
    for (int i = n - 1; i >= 0; i--) {
      pets[i] = pets[i + 1];
      swap(pets[i][p1[i]], pets[i][p2[i]]);
    }
    for (int i = n - 1; i >= 0; i--) {
      if (i + m <= n) {
        int keyset2 = 0;
        for (int p = 0; p < (k); ++p)
          if ((((set2) & (1 << (p))) != 0)) keyset2 |= (1 << (pets[i + m][p]));
        que.clear();
        add(keyset2, 0, i + m - 1);
        for (int cl = 0; cl < (((int)que.size())); ++cl) {
          int set = que[cl];
          for (int p = 0; p < (k); ++p)
            add(set ^ (1 << (p)), f[set] + 1, g[set]);
        }
      }
      int keyset1 = 0;
      for (int p = 0; p < (k); ++p)
        if ((((set1) & (1 << (p))) != 0)) keyset1 |= (1 << (pets[i][p]));
      ret = min(ret, VI{f[keyset1], i, g[keyset1]});
    }
    printf("%d\n%d %d\n", k - ret[0], ret[1] + 1, ret[2] + 1);
    break;
  }
  return 0;
}
