// 从未在意的名字永远不会被提起 - 雪葉/鹤见江野

/*
+
++
+++
++++
+++++
++++++
+++++++
++++++++
+++++++++
++++++++++
+++++++++++
++++++++++++
+++++++++++++
++++++++++++++
+++++++++++++++
++++++++++++++++
+++++++++++++++++
++++++++++++++++++
+ +++++++++++++++++
+  ++++++++++++++ ++
+   +++++++++++++  ++
+    ++++++++++++   ++
+     +++++++++++    ++
+      ++++++++++     ++
+       +++++++++      ++
+        ++++++++       ++
+         +++++++++++++++++
+          +++++++++++++++++
+           ++++++++++++++
+            +++++++++++
+             ++++++++
+              +++++
+               ++
+               +
+               +
+              ++
+             +++
+            ++++
+           +++++
+           +++++
+           +++++
+           +++++
+     +     +++++
+    +++    +++++
+   ++ ++   +++++
+  ++   ++  +++++
+ ++  +  ++ +++++
+++  +++  +++++++
++  ++ ++  ++++++
 
 
 ++++++++      +++++++++++     +++      +++        ++++++++        ++++++++
+++++++++     +++++++++++++    +++      +++       +++    +++      +++    +++
+++          +++   +++   +++   +++      +++      +++   ++++++    +++      +++
+++          +++   +++   +++   +++      +++      +++ +++  +++           +++
+++          +++   +++   +++   +++ ++   +++ ++   ++++++   +++         +++
+++++++++    +++   +++   +++   +++ ++   +++ ++    +++    +++        +++    ++
 ++++++++    +++   +++   +++   +++++    +++++      ++++++++       +++++++++++
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define rg(x) for(int i=1;i<=(x);i++){
#define rg_(i,x) for(int i=1;i<=(x);i++){
#define gr }
#define rrg(x) for(int i=0;i<(x);i++)
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
#define int long long
#define newe(n) struct Edge{int v,w,nxt;}e[n*2+5];\
typedef int arr[n+5];\
arr h;\
int cnt=1;\
inline void addedge(int u,int v,int w){e[cnt]=(Edge){v,w,h[u]};h[u]=cnt++;}
#define mgs int fa[1<<22],sz[1<<22],t[1<<22];\
inline int f(int x){return x==fa[x]?x:fa[x]=f(fa[x]);}\
inline int u(int x,int y)\
{\
    int fx=f(x),fy=f(y);\
    if(fx==fy)return 0;\
    if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;\
    fa[fx]=fy,sz[fy]+=sz[fx];\
    return 1;\
}
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
inline int re1d()
{
    char c=getchar();
    while(c<48||c>49)c=getchar();
    return c&1;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
int ans; 
int B;
int a[3000005],b[3000005],c[3000005];
struct qaq{
	int l,r,i,lB;
	bool operator<(const qaq& b)const
	{
		return (lB==b.lB)?(((lB)&1)?r<b.r:r>b.r):l<b.l;
	}
}q[3000005];
void rmv(int k)
{
	ans-=b[a[k]]-1;
	b[a[k]]--;
}
void add(int k)
{
	ans+=b[a[k]];
	b[a[k]]++;
}
int ans_[5000005];
int f[128];
char S[3000005];
int Q[3000005];
const int mod=2147483647;
const int T=9982443;
signed main()
{
	f['f']=1;
	f['o']=2;
	f['u']=3;
	f['z']=4;
	f['t']=5;
	f['s']=6;
	f['y']=7;
	int n=read(),m=read(),k=read();
	B=n/sqrt(m+3)+114;
	int q_=1;
	rg(k-1)q_=1ll*q_*T%mod;gr
	//puts("Pf");
	scanf("%s",S+1);
//	rg(n)a[i]=read();gr
	int s=0;
	rg(k-1)s=(s*T+f[S[i]])%mod;gr
	rg(n-k+1)
	s=(s*T+f[S[i+k-1]])%mod;
	Q[i]=a[i]=s;
	s=(s-1ll*q_*f[S[i]]%mod+mod)%mod;
	gr
	std::sort(Q+1,Q+1+n-k+1);
	int ss=std::unique(Q+1,Q+1+n-k+1)-Q-1;
	rg(n-k+1)a[i]=std::lower_bound(Q+1,Q+1+ss,a[i])-Q;gr
//	rg(n-k+1)odb(a[i]);gr puts("");
	rg(m)q[i].l=read(),q[i].lB=q[i].l/B,q[i].r=min(read(),n-k+1),q[i].i=i;
	if(q[i].r<q[i].l)q[i].r=q[i].l-1;
	gr
	std::sort(q+1,q+1+m);
	register int cl=1,cr=0;
	rg(m)
		int L=q[i].l,R=q[i].r;
//		odp(L,R);
		while(cl>L)add(--cl);
		while(cr<R)add(++cr);
	//	odb(ans);odb(b[1]);odb(b[2]);odp(b[3],b[4]);
		while(cl<L)rmv(cl++);
		while(cr>R)rmv(cr--);
//		odb(ans);odb(b[1]);odb(b[2]);odp(b[3],b[4]);
		//printf("%d\n",ans);
		ans_[q[i].i]=ans;
	gr
	rg(m)oldl(ans_[i]);gr
}