将所有串（包括S）放一块建SAM。对于询问，倍增定位出该子串所在节点，然后要查询的就是该子串在区间内的哪个字符串出现最多。可以线段树合并求出该节点在每个字符串中的出现次数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
typedef pair<int,int> pii;
char s[N];
int n,m,Q,cnt=1,last,id[N],fail[N],len[N],root[N],f[N][22],q[N],tmp[N],tot=0;
map<int,int> son[N];
struct data{int l,r;pii t;
}tree[N*22];
pii operator +(const pii&a,const pii&b)
{
return make_pair(a.first+b.first,a.second);
}
pii Max(pii a,pii b){return a.first>b.first||a.first==b.first&&a.second<b.second?a:b;}
void ins(int &k,int l,int r,int x)
{
tree[++tot]=tree[k],k=tot;
if (l==r) {tree[k].t.first++;tree[k].t.second=x;return;}
int mid=l+r>>1;
if (x<=mid) ins(tree[k].l,l,mid,x);
else ins(tree[k].r,mid+1,r,x);
tree[k].t=Max(tree[tree[k].l].t,tree[tree[k].r].t);
}
int merge(int x,int y,int l,int r)
{
if (!x||!y) return x|y;
int k=++tot;
if (l==r) tree[k].t=tree[x].t+tree[y].t;
else
{
int mid=l+r>>1;
tree[k].l=merge(tree[x].l,tree[y].l,l,mid);
tree[k].r=merge(tree[x].r,tree[y].r,mid+1,r);
tree[k].t=Max(tree[tree[k].l].t,tree[tree[k].r].t);
}
return k;
}
pii query(int k,int l,int r,int x,int y)
{
if (!k||l==x&&r==y) return tree[k].t;
int mid=l+r>>1;
if (y<=mid) return query(tree[k].l,l,mid,x,y);
else if (x>mid) return query(tree[k].r,mid+1,r,x,y);
else return Max(query(tree[k].l,l,mid,x,mid),query(tree[k].r,mid+1,r,mid+1,y));
}
int extend(int p,int c,int i,int j)
{
int u;
if (son[p][c])
{
int q=son[p][c];
if (len[p]+1==len[q]) u=q;
else
{
int y=++cnt;
len[y]=len[p]+1;
son[y]=son[q];
fail[y]=fail[q],fail[q]=y;
while (son[p][c]==q) son[p][c]=y,p=fail[p];
u=y;
}
}
else
{
int x=++cnt;len[x]=len[p]+1;
while (!son[p][c]&&p) son[p][c]=x,p=fail[p];
if (!p) fail[x]=1;
else
{
int q=son[p][c];
if (len[p]+1==len[q]) fail[x]=q;
else
{
int y=++cnt;
len[y]=len[p]+1;
son[y]=son[q];
fail[y]=fail[q],fail[q]=fail[x]=y;
while (son[p][c]==q) son[p][c]=y,p=fail[p];
}
}
u=x;
}
if (i==0) id[j]=u;
else ins(root[u],1,m,i);
return u;
}
int getpos(int k,int x)
{
for (int j=21;~j;j--) if (len[f[k][j]]>=x) k=f[k][j];
return k;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%s",s+1);n=strlen(s+1);
last=1;for (int i=1;i<=n;i++) last=extend(last,s[i]-'a',0,i);
m=read();
for (int i=1;i<=m;i++)
{
scanf("%s",s+1);int _=strlen(s+1);
last=1;for (int j=1;j<=_;j++) last=extend(last,s[j]-'a',i,j);
}
for (int i=1;i<=cnt;i++) f[i][0]=fail[i];f[1][0]=1;
for (int j=1;j<=21;j++)
for (int i=1;i<=cnt;i++)
f[i][j]=f[f[i][j-1]][j-1];
for (int i=1;i<=cnt;i++) tmp[len[i]]++;
for (int i=1;i<=cnt;i++) tmp[i]+=tmp[i-1];
for (int i=1;i<=cnt;i++) q[tmp[len[i]]--]=i;
for (int i=cnt;i>=1;i--)
{
int x=q[i];
root[fail[x]]=merge(root[fail[x]],root[x],1,m);
}
Q=read();
while (Q--)
{
int l=read(),r=read(),pl=read(),pr=read();
int x=getpos(id[pr],pr-pl+1);
pii t=query(root[x],1,m,l,r);
printf("%d %d\n",max(l,t.second),t.first);
}
return 0;
}