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
#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;}
int gcd(int a,int b) { return b?gcd(b,a%b):a;}
// head

const int N=5e3+5,SIGMA=26,W=62;

#define INF 0x3f3f3f3f

template<class T> inline void read(T &x) {
    x=0; int c=getchar(),f=1;
    for (;!isdigit(c);c=getchar()) if (c==45) f=-1;
    for (;isdigit(c);c=getchar()) (x*=10)+=f*(c-'0');
}
int n,m,q,M=33;
char s[2][N];

struct Bitset {
  ll u[34];
  void clr() {
    memset(u,0,sizeof(u));
  }
  void set(int x) {
    u[x/W]|=1ll<<(x%W);
  }
  Bitset operator |(const Bitset &r) const {
    Bitset s;
    rep(i,0,M) s.u[i]=u[i]|r.u[i];
    return s;
  }
  void gao(const Bitset &r) {
  	rep(i,0,M) u[i]=(u[i]^r.u[i])&r.u[i];
  }
  void sub(const Bitset &r) {
  	rep(i,0,M) u[i]=r.u[i]-u[i];
  	rep(i,0,M) if (u[i]<0) u[i]+=1ll<<W,u[i+1]--;
  }
  void shl() {
    for (ll i=0,c(1);i<M;i++) {
      u[i]<<=1; u[i]|=c;
      c=u[i]>>W&1;
      u[i]^=c<<W;
    }
  }
  int cnt() const {
    int c(0);
    rep(i,0,M) c+=__builtin_popcountll(u[i]);
    return c;
  }
}row,as[SIGMA],x;

int main() {
	read(n); read(m); read(q);
	scanf("%s%s",s[0],s[1]);
	rep(i,0,q) {
		int i1,j1,i2,j2;
		read(i1); read(j1); read(i2); read(j2);
		rep(j,0,SIGMA) as[j].clr();
		int _n=j1-i1+1;
		rep(j,0,_n) as[s[0][j+i1-1]-'a'].set(j);
		M=_n/W+(_n%W!=0);
		row.clr();
		rep(j,0,j2-i2+1) {
			rep(k,0,M) x.u[k]=row.u[k]|as[s[1][j+i2-1]-'a'].u[k];
			row.shl();
			row.sub(x);
			row.gao(x);
		}
		printf("%d\n",row.cnt());
	}
}