1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <cstring>

#define REP(a,n) for (int a = 0; a<(n); ++a)
#define FOR(a,b,c) for (int a = (b); a<=(c); ++a)
#define FORD(a,b,c) for (int a = (b); a>=(c); --a)
#define FOREACH(a,v) for (auto a : v)

#define MP make_pair
#define PB push_back

template<class T> inline int size(const T&t) { return t.size(); }

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long LL;

///////////////////////////////

#define DEBUG 0

int XS, YS, Q;
string s1, s2;
int podnies[12][3001][3001];
int ans[100000];


int main() {
  cin >> XS >> YS >> Q >> s1 >> s2;
  FOR(i, 0, 11) {
    for (int sr = 1 << i; sr <= XS; sr += (1 << (i + 1))) {
      FORD(x, sr - 1, sr - (1 << i)) {
        int podn_dod_nad = YS;
        //podnies[i][x][YS] = YS;
        FORD(y, YS - 1, 0) {
          if (s1[x] == s2[y]) {
            podnies[i][x][y] = podn_dod_nad;
            podn_dod_nad = y;
          }
          else
            podnies[i][x][y] = max(y, min(podnies[i][x + 1][y], podn_dod_nad));
          podn_dod_nad = max(podn_dod_nad, podnies[i][x + 1][y]);
        }
      }
      REP(y, YS + 1)
        podnies[i][sr][y] = y;
      FOR(x, sr + 1, min(sr + (1 << i) - 1, XS)) {
        int podn_dod_pod = 0;
        //podnies[i][x][0] = 0;
        FOR(y, 1, YS) {
          if (s1[x - 1] == s2[y - 1]) {
            podnies[i][x][y] = podn_dod_pod;
            podn_dod_pod = y;
          }
          else
            podnies[i][x][y] = min(y, max(podnies[i][x - 1][y], podn_dod_pod));
          podn_dod_pod = min(podn_dod_pod, podnies[i][x - 1][y]);
        }
      }
    }
    #if DEBUG
    if ((1 << i) <= XS) {
      cerr << "i = " << i << endl;
      FORD(y, YS, 0) {
        REP(x, XS + 1)
          cerr << podnies[i][x][y] << " ";
        cerr << endl;
      }
    }
    #endif
  }
  REP(q, Q) {
    int x0, x1, y0, y1;
    cin >> x0 >> x1 >> y0 >> y1;
    --x0;
    --y0;
    int i = 11;
    while ((x0 & (1 << i)) == (x1 & (1 << i))) --i;
    #if DEBUG
    cerr << "zap: " << x0 << " " << y0 << " " << x1 << " " << y1 << "; i=" << i << endl << "gorne:" << endl;
    #endif
    //int sr = x1 & ~((1 << i) - 1);
    int gorne[YS + 1], dolne[YS + 1], wyn[YS + 1];
    memset(gorne, 0, (YS + 1) * sizeof(int));
    memset(dolne, 0, (YS + 1) * sizeof(int));
    FORD(y, YS - 1, y0)
      ++gorne[podnies[i][x0][y]];
    int ll = 0, best = 0;
    FORD(y, YS, y0) {
      ll += gorne[y];
      wyn[y] = ll;
      #if DEBUG
      cerr << ll << endl;
      #endif
      --ll;
    }
    FOR(y, 1, y1)
      ++dolne[podnies[i][x1][y]];
    ll = 0;
    FOR(y, 0, y1) {
      ll += dolne[y];
      if (y >= y0)
        best = max(best, ll + wyn[y]);
      --ll;
    }
    cout << best << endl;
  }
}