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
121
122
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=3010,Q=101000;
char a[N],b[N],s[N],t[N];
int ih[N][N],iv[N][N],c[N][N],cc[N][N],tmpr[N];
int ret[Q],na,nb,q;
VI qtmp[N];
array<int,4> qs[Q];
bitset<N> bt[101000],dd[N];
int T;

void query1(int na,int nb,vector<int> &q,int off) {
	for (int j=0;j<=nb;j++) ih[0][j]=j;
	for (int l=0;l<=na;l++) iv[l][0]=0;
	for (int l=1;l<=na;l++) for (int j=1;j<=nb;j++) {
		if (a[l]!=b[j]) {
			ih[l][j]=max(iv[l][j-1],ih[l-1][j]);
			iv[l][j]=min(iv[l][j-1],ih[l-1][j]);
		} else {
			ih[l][j]=iv[l][j-1];
			iv[l][j]=ih[l-1][j];
		}
	}
	for (int l=0;l<=na;l++) qtmp[l].clear();
	for (auto x:q) qtmp[qs[x][1]-off].pb(x);
	++T;
	for (int l=0;l<=na;l++) {
		for (int j=0;j<=nb;j++) dd[j].set(iv[l][j]);
		for (auto id:qtmp[l]) bt[id]=dd[qs[id][3]];
	}
	for (int l=0;l<=na;l++) for (int j=0;j<=nb;j++) dd[j].set(iv[l][j],0);
}

void query2(int na,int nb,vector<int> &q,int off) {
	for (int j=0;j<=nb;j++) ih[0][j]=j;
	for (int l=0;l<=na;l++) iv[l][0]=0;
	for (int l=1;l<=na;l++) for (int j=1;j<=nb;j++) {
		if (a[l]!=b[j]) {
			ih[l][j]=max(iv[l][j-1],ih[l-1][j]);
			iv[l][j]=min(iv[l][j-1],ih[l-1][j]);
		} else {
			ih[l][j]=iv[l][j-1];
			iv[l][j]=ih[l-1][j];
		}
	}
	++T;
	for (int l=0;l<=na;l++) qtmp[l].clear();
	for (auto x:q) {
		qtmp[off-qs[x][0]].pb(x);
	}
	for (int l=0;l<=na;l++) {
		for (int j=0;j<=nb;j++) dd[j].set(iv[l][j]);
		for (auto id:qtmp[l]) {
			int val=0;
			int ans=-1;
			for (int i=qs[id][3];i>=qs[id][2];i--) {
				tmpr[i]=val;
				val+=bt[id][i];
			}
			val=0;
			for (int i=nb-qs[id][2];nb-i<=qs[id][3];i--) {
				ans=max(ans,val+tmpr[nb-i]);
				val+=(dd[nb-qs[id][2]][i]);
			}
			ret[id]=ans;
		}
	}
	for (int l=0;l<=na;l++) for (int j=0;j<=nb;j++) dd[j].set(iv[l][j],0);
}

void solve(int l,int r,vector<int> que) {
	if (que.empty()) return;
	int md=(l+r)>>1;
	VI delq,lq,rq;
	for (auto x:que) {
		if (qs[x][1]<md) lq.pb(x);
		else if (qs[x][0]>md) rq.pb(x);
		else delq.pb(x);
	}
	for (int i=md+1;i<=r;i++) a[i-md]=s[i];
	for (int i=1;i<=nb;i++) b[i]=t[i];
	query1(r-md,nb,delq,md);
	for (int i=l+1;i<=md;i++) a[md-i+1]=s[i];
	for (int i=1;i<=nb;i++) b[i]=t[nb+1-i];
	query2(md-l,nb,delq,md);
	if (l<md-1) solve(l,md-1,lq);
	if (md+1<r) solve(md+1,r,rq);
}

int main() {
	scanf("%d%d%d",&na,&nb,&q);
	scanf("%s%s",s+1,t+1);
	VI que;
	rep(i,0,q) {
		int s1,s2,t1,t2;
		scanf("%d%d%d%d",&s1,&t1,&s2,&t2);
		--s1; --s2;
		qs[i]={s1,t1,s2,t2};
		que.pb(i);
	}
	solve(0,na,que);
	rep(i,0,q) printf("%d\n",ret[i]);
}