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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

const int N = 3030;
const int Q = 100100;

bool flag;
struct Data {
	int sl, sr, tl, tr;
	int id;
	int ans;
	bool operator < (const Data &d) const {
		if (flag) {
			return vector<int>({sl,tl,id}) < vector<int>({d.sl,d.tl,d.id});
		}
		return id < d.id;
	}
	void out() {
		cerr << "Answer to (" << sl << "--" << sr << "), (" << tl << "--" << tr << ") is " << ans << "\n";
	}
};

Data qs[Q];

int n,m,qn;
char s[N], t[N];
int dp[N][N];

void init(int sl, int sr, int tl, int tr) {
	//cerr << "Initializing (" << sl << "--" << sr << "), (" << tl << "--" << tr << ")\n";
	REP(i,sl-1,sr+1) REP(j,tl-1,tr+1) dp[i][j] = 0;
	REP(i,sl,sr) REP(j,tl,tr) {
		dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		if (s[i] == t[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
		//cerr << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n";
	}
}


int main() {
	scanf("%d%d%d %s %s", &n, &m, &qn, s+1, t+1);
	FOR(i,qn) {
		scanf("%d%d%d%d", &qs[i].sl, &qs[i].sr, &qs[i].tl, &qs[i].tr);
		qs[i].id = i;
		qs[i].ans = -1;
	}
	flag = true;
	sort(qs,qs+qn);
	FOR(i,qn) {
		int sc = qs[i].sl, tc = qs[i].tl;
		int sm = sc, tm = tc;
		int j;
		for (j = i; j < qn && sc==qs[j].sl && tc==qs[j].tl; j++) {
			sm = max(sm, qs[j].sr);
			tm = max(tm, qs[j].tr);
		}
		init(sc, sm, tc, tm);
		for (int k = i; k < j; k++) {
			qs[k].ans = dp[qs[k].sr][qs[k].tr];
			//qs[k].out();
		}
		i = j-1;
	}
	flag = false;
	sort(qs,qs+qn);
	FOR(i,qn) printf("%d\n", qs[i].ans);
	return 0;
}