Description：

给你一个串 $S$ 以及一个字符串数组 $T[1..m]$ ， $q$ 次询问，每次问 $S$ 的子串 $S[p_l..p_r]$ 在 $T[l..r]$ 中的哪个串里的出现次数最多，并输出出现次数。如有多解输出最靠前的那一个。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

首先把所有 $T$ 的串建出广义后缀自动机，在对应位置的线段树上插入 $i$ ， $Parent$ 树上做一遍线段树合并得到每个节点 $T$ 中每个字符串的出现次数，然后把 $S$ 在上面跑，记录一下每个位置跑到了自动机上的什么位置以及匹配长度，这个匹配长度在 $parent$ 树上显然是单调的，因为子节点匹配长度一定 $\geqslant $ 父节点，那么在查询的时候就可以从 $p_r$ 开始树上倍增求出 $len$ 包含 $p_r-p_l+1$ 的位置然后在对应线段树里统计一下就行了。

注意由于广义后缀自动机会破坏原本的结构所以不能用基数排序倒序递推了。

还要注意在求位置的时候顺便统计一下匹配的长度，如果 $mat[pr]<pr-pl+1$ 那显然是无解。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXL 500010

char T[MAXL];

int l;

int n,q;

char str[MAXL];

namespace SEG

{

	struct state

	{

		int maxv,pos;

		state(int a = 0,int b = 0){maxv = a;pos = b;}

		friend state operator + (state a,state b)

		{

			state res;

			if(a.maxv >= b.maxv){res.maxv = a.maxv;res.pos = a.pos;}

			else{res.maxv = b.maxv;res.pos = b.pos;}

			return res;

		}

	};

	struct node

	{

		int lc,rc;

		state s;

	}t[MAXL * 30];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root[MAXL << 1];

	#define mid ((l + r) >> 1)

	void insert(int &rt,int p,int l,int r)

	{

		if(rt == 0)rt = newnode();

		if(l == r)

		{

			++t[rt].s.maxv;t[rt].s.pos = l;

			return;

		}

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		t[rt].s = t[t[rt].lc].s + t[t[rt].rc].s;

		return;

	}

	int merge(int x,int y,int l,int r)

	{

		if(x == 0 || y == 0)return x + y;

		int rt = newnode();

		if(l == r)

		{

			t[rt].s.maxv = t[x].s.maxv + t[y].s.maxv;

			t[rt].s.pos = l;

			return rt;

		}

		t[rt].lc = merge(t[x].lc,t[y].lc,l,mid);

		t[rt].rc = merge(t[x].rc,t[y].rc,mid + 1,r);

		t[rt].s = t[t[rt].lc].s + t[t[rt].rc].s;

		return rt;

	}

	state query(int rt,int L,int R,int l,int r)

	{

		if(rt == 0)return (state){0,0};

		if(L <= l && r <= R)return t[rt].s;

		if(R <= mid)return query(t[rt].lc,L,R,l,mid);

		if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

		return query(t[rt].lc,L,R,l,mid) + query(t[rt].rc,L,R,mid + 1,r);

	}

}

namespace SAM

{

	struct node

	{

		int maxl,minl,par;

		int tr[26];

	}s[MAXL << 1];

	int ptr = 1,root = 1,last = 1;

	int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

	void extend(int k)

	{

		int p = last;

		int np = newnode(s[p].maxl + 1);

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)s[np].par = root;

		else

		{

			int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

			else

			{

				int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = s[np].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		last = np;

		return;

	}

}

struct edge

{

	int to,nxt;

}e[MAXL << 2];

int edgenum = 0;

int lin[MAXL << 1] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

bool vis[MAXL << 1];

void dfs(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to);

		SEG::root[k] = SEG::merge(SEG::root[k],SEG::root[e[i].to],1,n);

	}

	return;

}

int pos[MAXL],mat[MAXL];

int f[MAXL << 1][20];

int main()

{

	scanf("%s",T + 1);

	l = strlen(T + 1);

	scanf("%d",&n);

	int maxlen = 0;

	using namespace SAM;

	for(int i = 1;i <= n;++i)

	{

		scanf("%s",str + 1);

		int len = strlen(str + 1);

		maxlen = max(maxlen,len);

		last = 1;

		for(int x = 1;x <= len;++x)

		{

			extend(str[x] - 'a');

			SEG::insert(SEG::root[last],i,1,n);

		}

	}

	for(int i = 2;i <= ptr;++i)add(s[i].par,i);

	dfs(1);

	for(int i = 1,k = root,len = 0;i <= l;++i)

	{

		if(s[k].tr[T[i] - 'a'] != 0)

		{

			k = s[k].tr[T[i] - 'a'];

			++len;

		}

		else

		{

			while(k != root && s[k].tr[T[i] - 'a'] == 0)k = s[k].par;

			len = min(len,s[k].maxl);

			if(s[k].tr[T[i] - 'a'] != 0)

			{

				k = s[k].tr[T[i] - 'a'];

				++len;

			}

		}

		pos[i] = k;mat[i] = len;

	}

	for(int i = 1;i <= ptr;++i)s[i].minl = s[s[i].par].maxl + 1;

	for(int i = 1;i <= ptr;++i)f[i][0] = s[i].par;

	for(int k = 1;k <= 19;++k)

		for(int i = 1;i <= ptr;++i)

			f[i][k] = f[f[i][k - 1]][k - 1];

	scanf("%d",&q);

	int l,r,sl,sr;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d%d%d",&l,&r,&sl,&sr);

		int p = pos[sr];

		for(int k = 19;k >= 0;--k)

			if(s[f[p][k]].maxl >= sr - sl + 1)

				p = f[p][k];

		if(min(mat[sr],s[p].maxl) < sr - sl + 1)

		{

			printf("%d 0\n",l);

			continue;

		}

		SEG::state res = SEG::query(SEG::root[p],l,r,1,n);

		if(res.maxv == 0)res.pos = l;

		printf("%d %d\n",res.pos,res.maxv);

	}

	return 0;

}