C++ :

#include<cstdio>
#include<algorithm>
#define N 280005
#define H 19
#define A 26
#define S 317
using namespace std;
int read()
{
	int r = 0; char c = getchar();
	for(; c < '0' || c > '9'; c = getchar());
	for(; c >='0' && c <='9'; r = r*10+c-'0', c = getchar());
	return r;
}
namespace runzhe2000
{	
	typedef long long ll;

	int happy, n, m, q, k, block;
	char s[N];
	
	struct inter
	{
		int l, r, len;
		bool operator < (const inter &that) const {return l == that.l ? r < that.r : l < that.l;}
		bool operator == (const inter &that) const {return l == that.l && r == that.r;}
	}in[N];

//////////
	
	int tot, pos[N], log[N], lm[N][H], rm[N][H], pre[N], a[N], b[N];
	int t1[N<<1], t2[N<<1], sa[N<<1], rank[N<<1], height[N<<1], sum[N<<1];
	
	void build_SA()
	{
		int *x = t1, *y = t2, m = q + 128;
		for(int i = 1; i <= tot; i++) sum[x[i] = s[i] + q]++;
		for(int i = 1; i <= m; i++) sum[i] += sum[i-1];
		for(int i = 1; i <= tot; i++) sa[sum[x[i]]--] = i;
		for(int k = 1; k < tot; k <<= 1)
		{
			int p = 0;
			for(int i = tot-k+1; i <= tot; i++) y[++p] = i;
			for(int i = 1; i <= tot; i++) if(sa[i]-k >= 1) y[++p] = sa[i]-k;
			for(int i = 1; i <= m; i++) sum[i] = 0;
			for(int i = 1; i <= tot; i++) sum[x[i]]++;
			for(int i = 1; i <= m; i++) sum[i] += sum[i-1];
			for(int i = tot; i >= 1; i--) sa[sum[x[y[i]]]--] = y[i];
			swap(x, y);
			for(int i = 1; i <= tot; i++)
				x[sa[i]] = x[sa[i-1]] + (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? 0 : 1);
			m = x[sa[tot]]; if(m == n) break;
		}
		for(int i = 1; i <= tot; i++) rank[sa[i]] = i;
		for(int i = 1, k = 0; i <= tot; height[rank[i++]] = k, k ? k-- : 0)
			for(; s[i+k] == s[sa[rank[i]-1]+k]; k++);
	}
	
	void init_ST()
	{
		log[1] = 0; for(int i = 2; i <= tot; i++) log[i] = log[i >> 1] + 1;
		for(int i = 1; i <= tot; i++) lm[i][0] = rm[i][0] = height[i];
		for(int h = 1; h < H; h++)
			for(int i = 1; i <= tot; i++)
			{
				lm[i][h] = min(lm[i][h-1], lm[i+(1<<(h-1))][h-1]);
				1 <= i-(1<<(h-1))
					? rm[i][h] = min(rm[i][h-1], rm[i-(1<<(h-1))][h-1])
					: rm[i][h] = min(rm[i-1][h], height[i]);
			}
	}
	int ST(int l, int r)
	{
		int d = log[r-l+1];
		return min(lm[l][d], rm[r][d]);
	}
	
	int find_l(int p, int lim)
	{
		int l = 1, r = p;
		for(; l < r; )
		{
			int mid = (l+r)>>1;
			if(ST(mid+1,p) < lim) l = mid + 1;
			else r = mid;
		}
		return l;
	}
	int find_r(int p, int lim)
	{
		int l = p, r = tot;
		for(; l < r; )
		{
			int mid = (l+r+1)>>1;
			if(ST(p+1, mid) < lim) r = mid - 1;
			else l = mid;
		}
		return l;
	}
	
	void solve1()
	{
		tot = n; s[++tot] = 0;
		for(int i = 1; i <= q; i++)
		{
			happy = scanf("%s",s+tot+1);
			pos[i] = tot + 1;
			s[tot += k + 1] = -i;
			a[i] = read()+1, b[i] = read()+1;
		}
		build_SA();
		for(int i = 1; i <= tot; i++) pre[i] = pre[i-1] + (sa[i] <= n);
		init_ST();
		for(int i = 1; i <= q; i++)
		{
			ll f = 0;
			for(int j = a[i]; j <= b[i]; j++)
			{
				int l = find_l(rank[pos[i]+in[j].l-1], in[j].len), r = find_r(rank[pos[i]+in[j].l-1], in[j].len);
				f += pre[r] - pre[l-1];
			}
			printf("%lld\n",f);
		}
	}
	
//////////

	struct sam
	{
		sam *next[A], *fail;
		int len, right;
	}mem[N], *totp, *null, *last, *root, *que[N];
	sam *newsam()
	{
		sam *x = ++totp; *x = *null; 
		return x;
	}
	void init_SAM()
	{
		null = totp = mem; for(int i = 0; i < A; i++) null->next[i] = null, null->fail = null; null->len = null->right = 0;
		last = root = newsam();
	}
	void extend(int i)
	{
		sam *p = last, *np = last = newsam(); np->len = p->len+1, np->right = 1; int v = s[i] - 'a';
		for(; p->next[v] == null && p != null; p = p->fail) p->next[v] = np;
		if(p == null) np->fail = root;
		else
		{
			if(p->next[v]->len == p->len+1) np->fail = p->next[v];
			else
			{
				sam *q = p->next[v], *nq = newsam(); *nq = *q; nq->len = p->len + 1; nq->right = 0;
				q->fail = np->fail = nq;
				for(; p->next[v] == q && p != null; p = p->fail) p->next[v] = nq;
			}
		}
	}
	bool cmp(sam *a, sam *b){return a->len < b->len;}
	
	struct event
	{
		int id, p, type;
		bool operator < (const event &that) const
		{
			return p < that.p;
		}
	}eve[N<<1]; 
	ll ans[N];
	int evecnt, tmp[N];
	char str[100001][S];
	
	struct seg
	{
		seg *ch[2]; int v;
	}memt[N*16], *tott, *nullt, *ro[S];
	seg *newseg()
	{
		seg *x = ++tott; *x = *nullt;
		return x;
	}
	void init_seg()
	{
		nullt = tott = memt; nullt->ch[0] = nullt->ch[1] = nullt;
		nullt->v = 0; for(int i = 1; i <= k; i++) ro[i] = newseg();
	}
	void insert(seg *x, int l, int r, int p)
	{
		if(l == r) {x->v++; return;} int mid = (l+r)>>1;
		if(p <= mid) 
		{
			if(x->ch[0] == nullt) x->ch[0] = newseg();
			insert(x->ch[0], l, mid, p);
		}
		else
		{
			if(x->ch[1] == nullt) x->ch[1] = newseg();
			insert(x->ch[1], mid+1, r, p);
		}
	}
	void push(seg *x, int l, int r)
	{
		if(l == r) {tmp[l] = x->v; return;}; int mid = (l+r)>>1;
		push(x->ch[0], l, mid);
		push(x->ch[1], mid+1, r);
	}
	
	void solve2()
	{
		init_seg(); init_SAM(); for(int i = 1; i <= n; i++) extend(i);
		for(sam *i = totp; i != mem; i--) que[i-mem] = i;
		sort(que+1, que+1+(totp-mem), cmp);
		for(int i = totp-mem; i > 1; i--) que[i]->fail->right += que[i]->right;
		for(int i = 1; i <= q; i++) 
		{
			happy = scanf("%s",str[i]+1);
			int a = read(), b = read();
			eve[++evecnt] = (event){i, a   , -1};
			eve[++evecnt] = (event){i, b+1 ,  1};
		}
		sort(eve+1, eve+1+evecnt);
		for(int i = 0, cur = 1; i <= m; i++)
		{
			if(i) insert(ro[in[i].l], 1, k, in[i].r);
			for(; cur <= evecnt && eve[cur].p == i; cur++)
			{
				ll f = 0;
				for(int l = 1; l <= k; l++)
				{
					push(ro[l], 1, k); sam *p = root;
					for(int r = l; r <= k; r++)
					{
						p = p->next[str[eve[cur].id][r]-'a'];
						f += p->right * tmp[r];
					}
				}
				ans[eve[cur].id] += eve[cur].type * f;
			}
		}
		for(int i = 1; i <= q; i++) printf("%lld\n",ans[i]);
	}
	
//////////
	
	void main()
	{
		n = read(), m = read(), q = read(), k = read();
		happy = scanf("%s",s+1);
		
		block = 316;
		
		for(int i = 1; i <= m; i++) in[i].l = read()+1, in[i].r = read()+1, in[i].len = in[i].r-in[i].l+1;
		if(q < block) solve1();
		else solve2();
	}
}
int main()
{
	runzhe2000::main();
}