#include <bits/stdc++.h>
using namespace std;
const int mxk = 20;
int n, m, k;
int a[2][mxk], b[mxk];
int dp[2][1 << mxk];
function<int(int, int)> first[2] = {[](int x, int y) { return min(x, y); },
                                    [](int x, int y) { return max(x, y); }};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < k; j++) {
      char c;
      cin >> c;
      a[i][j] = c & 1;
    }
  for (int i = 0; i < k; i++) b[i] = i;
  memset(dp[0], 0x3f, sizeof(dp[0]));
  memset(dp[1], -1, sizeof(dp[1]));
  for (int i = 0; i <= n; i++) {
    if (i) {
      int x, y;
      cin >> x >> y;
      swap(b[--x], b[--y]);
    }
    for (int j = 0; j < 2; j++) {
      int x = 0;
      for (int l = 0; l < k; l++) x |= a[j][l] << b[l];
      dp[j][x] = first[j](dp[j][x], i);
    }
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < k; j++)
      for (int l = 0; l < (1 << k); l++) {
        if (!((l >> j) & 1)) dp[i][l] = first[i](dp[i][l], dp[i][l ^ (1 << j)]);
      }
  int ret = -1, l = 0, r = 0;
  for (int i = 0; i < (1 << k); i++) {
    int x = __builtin_popcount(i);
    if (dp[1][i] - dp[0][i] >= m && x > ret) {
      ret = x, l = dp[0][i] + 1, r = dp[1][i];
    }
  }
  ret = 2 * ret + k;
  for (int i = 0; i < 2; i++) ret -= count(a[i], a[i] + k, 1);
  cout << ret << '\n';
  cout << l << " " << r << '\n';
  return 0;
}
