阿块刚才突然问我有什么歌听，那就推一首我正在听的歌吧：終わりの世界から。大魔王麻枝准的歌，歌词直接讲了个故事。
这种前缀关系一看就是上$trie$树了。
如果知道集合$G$，答案就随便求了。记$f(n)$为区间$[1,n]$的子区间个数，$f(n)=\dfrac{n(n+1)}{2}$。把集合元素排序，用所有方案减去不合法方案就是答案，即$f(\max\{|s_i|\})-\sum\limits_{i=1}^{n+1}f(a_i-a_{i-1}-1)$，其中$a_0=0,a_{n+1}=\max\{|s_i|\}+1$
求$G$有一个暴力做法：用set维护$G$，把每个前缀代表的节点加上对应串的权值，如果某个节点满足要求就把对应的$g_{len(S)}$扔进set里，扫一遍就是答案。
这个做法可以用莫队优化，但是移动一次端点要把整个串都算一遍，复杂度不对劲。套路地把每个字符都从串里拆出来，拼成一个新串，在新串上跑莫队。这样单次转移是set的$O(\log n)$。
考虑去掉set的$\log$。如果换成链表，可以$O(1)$删除，但难添加，于是可以上回滚莫队。复杂度$O(m\sqrt {\sum|s_i|})$。
第一次写只删除的回滚莫队，细节有点多，代码丑的一批：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 300005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
#define son(x,y) son[x][y]
int son[maxn][26],len[maxn],pos[maxn],id[maxn],v[maxn],deep[maxn],g[maxn],be[maxn],a[maxn],sta[maxn][3],cnt=1,A,B,C,k,ml,top;
long long ans[maxn];
bool vis[maxn],flag;
char s[maxn];
struct query{
int l,r,id;
bool operator < (const query &x)const{
if(be[l]!=be[x.l])return be[l]<be[x.l];
return r>x.r;
}
}q[maxn];
void insert(int l,int r){
int node=1;
for(register int i=l;i<=r;++i){
if(!son(node,s[i]-'a'))deep[son(node,s[i]-'a')=++cnt]=deep[node]+1;
node=son(node,s[i]-'a'),pos[i]=node;
}
}
inline long long sec(int n){return 1ll*n*(n-1)>>1;}
struct Mo{
int tax[maxn],pre[maxn],nex[maxn];
long long sum[maxn],ans;
bool vis[maxn];
inline void erase(int x){
ans-=sec(x-pre[x])+sec(nex[x]-x)-sec(nex[x]-pre[x]);
pre[nex[x]]=pre[x],nex[pre[x]]=nex[x];
if(flag)sta[++top][0]=x,sta[top][1]=pre[x],sta[top][2]=nex[x];
}
void add(int x){
int node=pos[x];
sum[node]+=v[x];
if(!vis[node]&&sum[node]*B+1ll*A*deep[node]>=C){
vis[node]=1;
if(!tax[deep[node]])a[++k]=g[deep[node]];
++tax[deep[node]];
}
}
inline void del(int x){
int node=pos[x];
sum[node]-=v[x];
if(vis[node]&&(!sum[node]||sum[node]*B+1ll*A*deep[node]<C)){
vis[node]=0,--tax[deep[node]];
if(!tax[deep[node]])erase(g[deep[node]]);
}
}
inline void back(int x){
int node=pos[x];
sum[node]+=v[x];
if(!vis[node]&&sum[node]*B+1ll*A*deep[node]>=C)vis[node]=1,++tax[deep[node]];
}
inline void back(){
int x,l,r;
while(top){
x=sta[top][0],l=sta[top][1],r=sta[top][2];
ans-=sec(r-l)-sec(x-l)-sec(r-x);
nex[x]=r,pre[x]=l,pre[r]=x,nex[l]=x,--top;
}
}
void init(){
sort(a+1,a+1+k);
pre[a[k+1]=ml+1]=a[k],nex[0]=a[1];
for(register int i=1;i<=k;++i){
pre[a[i]]=a[i-1],nex[a[i]]=a[i+1];
ans+=sec(a[i]-a[i-1]);
}
ans+=sec(a[k+1]-a[k]);
}
}o,u;
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
int main(){
int m,sq,sl,n=read();
A=read(),B=read(),C=read();
for(register int i=1;i<=n;++i)a[i]=read();
for(register int i=1;i<=n;++i){
scanf("%s",s+len[i-1]+1),len[i]=strlen(s+len[i-1]+1),ml=max(ml,len[i]),len[i]+=len[i-1],insert(len[i-1]+1,len[i]);
for(register int j=len[i-1]+1;j<=len[i];++j)id[j]=i,v[j]=a[i];
}
for(register int i=1;i<=ml;++i)g[i]=read();
n=len[n],m=read(),sq=n/sqrt(m),sl=n/sq+bool(n%sq);
for(register int i=1;i<=m;++i)q[i].l=len[read()-1]+1,q[i].r=len[read()],q[i].id=i;
for(register int i=1;i<=sl;++i)
for(register int j=(i-1)*sq+1,r=min(j+sq-1,n);j<=r;++j)
be[j]=i;
sort(q+1,q+1+m);
for(register int i=1;i<=n;++i)o.add(i);
o.init();
int l,r;
for(register int i=1;i<=m;++i){
if(be[q[i].l]!=be[q[i-1].l]){
l=(be[q[i].l]-1)*sq+1,r=n;
for(register int j=max((be[q[i-1].l]-1)*sq+1,1);j<l;++j)o.del(j);
u=o;
}
while(r>q[i].r)u.del(r--);
flag=1;
for(register int j=l;j<q[i].l;++j)u.del(j);
flag=0;
ans[q[i].id]=u.ans;
for(register int j=l;j<q[i].l;++j)u.back(j);
u.back();
}
long long f=sec(ml+1);
for(register int i=1;i<=m;++i){
long long d=gcd(f-ans[i],f);
printf("%lld/%lld\n",(f-ans[i])/d,f/d);
}
}
