C++ :

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
#define BLOCK 640
#define MAXN 200000
#define ll long long
#define c(x,y) t[x].c[y]
#define maxlen(x) t[x].maxlen
#define link(x) t[x].link
#define mx(x) t[x].mx
#define fa(i,j) fa[j][i]
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
#define BUF_SIZE 1000000
#define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob
#define oc(a) (*_O++ = a)
char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot;
inline void os(string s){_O += s.copy(_O,s.length(),0), _O-_Ob >= BUF_SIZE-50 ? _END : 0;}
template <typename T> inline void oi(T x)
{
	if(!x){oc('0'); return;} if(x < 0) oc('-'), x = -x;
	for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10);
	for(; _Ot != _Os; oc(*--_Ot)); _O-_Ob >= BUF_SIZE-50 ? _END : 0;
}
struct Node{int c[26],maxlen,link; ll mx;}t[MAXN+5]; char s[MAXN+5]; int book[MAXN+5], o[MAXN+5], L[MAXN+5], R[MAXN+5], last, tot, n, m, q, k;
#define New(p,v) (++tot, maxlen(tot)=p?maxlen(p)+1:0, mx(tot) = v, tot)
inline void Append(int x)
{
	rint p = last, np = last = New(p,1), q, nq; for(; p&&!c(p,x); c(p,x) = np, p = link(p));
	if(!p) link(np) = 1; else if(maxlen(q=c(p,x))==maxlen(p)+1) link(np) = q;
	else{for(nq = New(p,0), memcpy(t[nq].c,t[q].c,104); p&&c(p,x)==q; c(p,x) = nq, p = link(p)); link(nq) = link(q), link(q) = link(np) = nq;}
}
namespace SmallK
{
	int B, c[BLOCK+5][BLOCK+5], _c[BLOCK+5]; char s[MAXN+5][BLOCK+5]; ll Ans[MAXN+5];
	struct Q{int l,r,u,i; Q(){} Q(int _l, int _r, int _i){l=_l,r=_r,u=_l/B,i=_i;}}o[MAXN+5]; inline bool operator < (Q a, Q b){return a.u^b.u?a.u<b.u:(a.u&1)^(a.r>b.r);}
	void Calc()
	{
		B = sqrt(q*q/m)+5; for(rint i = 1, l, r; i <= q; scanf("%s",s[i]+1), l = -~read(), r = -~read(), o[i] = Q(l,r,i), i++); sort(o+1,o+q+1);
		for(rint i = 1, ql = 1, qr = 0, l, r, p; i <= q; i++)
		{
			for(; ql>o[i].l; --ql, ++c[L[ql]][R[ql]], ++_c[L[ql]]); for(; qr<o[i].r; ++qr, ++c[L[qr]][R[qr]], ++_c[L[qr]]);
			for(; ql<o[i].l; --c[L[ql]][R[ql]], --_c[L[ql]], ++ql); for(; qr>o[i].r; --c[L[qr]][R[qr]], --_c[L[qr]], --qr);
			for(l = 1; l <= k; l++) if(_c[l]) for(p = 1, r = l; (p=c(p,s[o[i].i][r]-'a')) && r <= k; c[l][r] ? Ans[o[i].i] += c[l][r]*mx(p) : 0, r++);
		}	for(rint i = 1; i <= q; oi(Ans[i]), oc('\n'), i++);
	}
}
namespace LargeK
{
	int LOG[MAXN+5], fa(MAXN+5,20), end[MAXN+5], len[MAXN+5]; ll Ans; inline ll FindL(int p, int l){for(rint j = LOG[maxlen(p)]; ~j; maxlen(fa(p,j))>=l ? p = fa(p,j) : 0, j--); return mx(p);}
	void Run(rint p=1){for(rint i = 1, l = 0; i <= k; p = p?++l,c(p,s[i]-'a'):1, len[i] = l, end[i] = p, i++) for(; p&&!c(p,s[i]-'a'); p = link(p), l = maxlen(p));}
	void Calc()
	{
		for(rint i = 2; i <= n; LOG[i] = -~LOG[i>>1], i++); for(rint i = 1; i <= tot; fa(i,0) = link(i), i++); for(rint j = 1, i; j <= LOG[n]; j++) for(i = 1; i <= tot; fa(i,j) = fa(fa(i,j-1),j-1), i++);
		for(rint i = 1, l, r; i <= q; oi(Ans), oc('\n'), i++) for(scanf("%s",s+1), Run(), Ans = 0, l = -~read(), r = -~read(); l <= r; len[R[l]]>=R[l]-L[l]+1 ? Ans += FindL(end[R[l]],R[l]-L[l]+1) : 0, l++);
	}
}
int main()
{
	n = read(), m = read(), q = read(), k = read(), tot = 0, last = New(0,0); scanf("%s",s+1); for(rint i = 1; i <= n; Append(s[i]-'a'), i++);
	for(rint i = 1; i <= tot; ++book[maxlen(i)], i++); for(rint i = 1; i <= n; book[i] += book[i-1], i++);
	for(rint i = tot; i; o[book[maxlen(i)]--] = i, i--); for(rint i = tot; i; mx(link(o[i])) += mx(o[i]), i--); mx(1) = 0;
	for(rint i = 1; i <= m; L[i] = -~read(), R[i] = -~read(), i++); k<=BLOCK?SmallK::Calc():LargeK::Calc(); _END; return 0;
}