A

考虑 dp。设 $f_{i,0/1}$ 表示考虑到根是 $i$ 前缀，最后一次删除的串长度为 $2/3$ 的方案数。

转移就判断一下两次长度相等是否子串相等即可。

B

这种最长的最短路链问题贪心超过两步都是错的。

首先 $O(n^2)$ 预处理 $dis_{i,j}$ 表示 $i \to j$ 的最短路，注意到贪心一步是正确的，我们去枚举 $b,c$，预处理最远，次远，第三远的点即可（因为路径不能重复）。

C

首先可以写出一个dp：设 $f_{i,j}$ 表示考虑填了前 $i$ 位，匹配了 $t$ 的前 $j$ 位的方案数。

转移：

$$ \begin{aligned} \text{if }j \neq m :\\ f_{i,j} \to 25f_{i+1,j}\\ f_{i,j} \to f_{i+1,j+1}\\ \text{if } j = m:\\ f_{i,j} \to 26f_{i+1,j} \end{aligned} $$

这种转移形式简单的计数问题可以抽象到网格图游走上：如果你当前在的坐标 $j \neq m$，可以选择走 $(1,0)$，方案 $25$，走 $(1,1)$ 方案数是 $1$；如果已经 $j=m$，那么只能走 $(1,0)$，方案数 $26$。

发现 $(1,1)$ 的数量恰为 $m$；考虑整个操作序列，在最后一个 $(1,1)$ 后的 $(1.0)$ 贡献都是 $26$，前面都是 $25$。考虑枚举最后一个 $(1,1)$：

$$ \sum_{i=m}^n \binom{i-1}{m-1}25^{i-m}26^{n-i} = \frac{26^n}{25^m}\sum_{i=0}^m \binom{i-1}{m-1} (\frac{25}{26})^i $$

注意 $\sum m \leq 10^5$，所以本质不同的 $m$ 只会有 $\sqrt m$ 个，每次都预处理所有答案，复杂度 $O(n \sqrt m)$。

D

这题暴力就行了。

我们先枚举每个点最终对应的点哪个坐标相等（可以看成是枚举在一条横线还是纵线上），然后分类讨论：

首先如果存在交点一定选交点要不然点就不够用了。

我们将所有的线去重之后分类讨论：

两横两纵

每个点都是确定的，判断是否是正方形后 $4!$ 枚举配对方案求答案即可。

两横一纵（或两纵一横）

我们确定了两个点和这个正方形的边长 $D$，所以另外两个点只有可能是坐标某一维 $\pm D$，对每一种情况 $4!$ 统计答案即可。

两横或两纵

我们考虑两横：

首先确定了正方形的边长 $D$，一个暴力的想法枚举一个点，就能确定所有的点。

假设现在上面的点是 $x_1,x_2$，下面的点是 $x_3,x_4$，不失一般性设当前枚举的两条竖线是 $x,x+D$。

不失一般性我们设 $x_1,x_3$ 匹配 $x$，$x_2,x_4$ 匹配 $x+D$（这里可以通过枚举完成所有情况），那么答案就是 $\max\{|x_1-x|,|x_3-x|,|x_2-(x+D)|,|x_4-(x+D)|\}$，拆开变成四个坐标 $x_1,x_3,x_2-D,x_4-D$，只需要取最大值和最小值的中点左右挨个判断一下即可。

代码太长了（170+），这里给出提交链接

E

先对所有的 $t$ 建出广义SAM，现在先考虑如何确定 $S[l,r]$ 对应的位置：我们先找到 $S[1,r]$ 对应的位置，不断跳 fail 并保证一直包含这个区间，需要用倍增预处理一下。

然后就直接线段树合并一发维护处最大值和最大值的位置就行了。

细节比较多，放一下代码：

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;

struct Node{
    int mx,ps;
    
    Node(int mx=0,int ps=-1) : mx(mx),ps(ps) {}
    
    friend Node operator + (const Node &x,const Node &y){
        Node res;
        if(x.mx >= y.mx) res.mx = x.mx,res.ps = x.ps;
        else res.mx = y.mx,res.ps = y.ps;
        return res;
    }
}sm[MAXN<<5];
// 最大值,非0位置个数
int lc[MAXN<<5],rc[MAXN<<5],tot;

inline Node query(int x,int l,int r,int L,int R){
    if(!x) return Node();
    if(l == L && r == R) return sm[x];
    int mid = (l + r) >> 1;
    if(R <= mid) return query(lc[x],l,mid,L,R);
    if(L > mid) return query(rc[x],mid+1,r,L,R);
    return query(lc[x],l,mid,L,mid)+query(rc[x],mid+1,r,mid+1,R);
}

inline void update(int &x,int l,int r,int p){
    if(!x) x = ++tot;
    if(l == r){
        sm[x].mx++;sm[x].ps = l;
        return;
    }
    int mid = (l + r) >> 1;
    if(p <= mid) update(lc[x],l,mid,p);
    else update(rc[x],mid+1,r,p);
    sm[x] = sm[lc[x]]+sm[rc[x]];
}

inline int merge(int x,int y,int l,int r){
    if(!x || !y) return x|y;
    int now = ++tot;
    if(l == r){
        sm[now] = sm[x];
        sm[now].mx += sm[y].mx;
        return now;
    }
    int mid = (l + r) >> 1;
    lc[now] = merge(lc[x],lc[y],l,mid);
    rc[now] = merge(rc[x],rc[y],mid+1,r);
    sm[now] = sm[lc[now]]+sm[rc[now]];
    return now;
}

int ch[MAXN][26],fail[MAXN],len[MAXN],_tot = 1,las = 1;
int rt[MAXN];

inline void copy(int x,int y){
    FOR(i,0,25) ch[x][i] = ch[y][i];
    fail[x] = fail[y];len[x] = len[y];
}

inline int work(int p,int c){
    int q = ch[p][c],nq = ++_tot;
    copy(nq,q);len[nq] = len[p]+1;fail[q] = nq;
    for(;p&&ch[p][c]==q;p=fail[p]) ch[p][c] = nq;
    return nq;
}

inline int insert(int p,int c){
    int q = ch[p][c];
    if(q){
        if(len[q] == len[p]+1) return q;
        return work(p,c);
    }
    int np = ++_tot;len[np] = len[p]+1;
    for(;p&&!ch[p][c];p=fail[p]) ch[p][c] = np;
    if(!p) fail[np] = 1;
    else{
        q = ch[p][c];
        if(len[q] == len[p]+1) fail[np] = q;
        else fail[np] = work(p,c);
    }
    return np;
}

const int MAXK = 5e5 + 5;

char S[MAXK],str[MAXN];
int n;
std::vector<int> G[MAXN];
const int MAXM = 16;
int f[MAXN][MAXM+1],m;

inline void dfs(int v){
    FOR(i,1,MAXM) f[v][i] = f[f[v][i-1]][i-1];
    for(auto x:G[v]){
        f[x][0] = v;dfs(x);
        rt[v] = merge(rt[v],rt[x],1,m);
    }
}

int to[MAXK],le[MAXK];

int main(){
    scanf("%s",S+1);n = strlen(S+1);
    scanf("%d",&m);
    FOR(i,1,m){
        las = 1;
        scanf("%s",str+1);int len = strlen(str+1);
        FOR(j,1,len) las = insert(las,str[j]-'a'),update(rt[las],1,m,i);
    }
    // DEBUG(query(rt[12],1,m,1,2).mx);
    // exit(0);
    FOR(i,2,_tot) G[fail[i]].pb(i);
    // for(auto x:G[81]){
        // DEBUG(x);
        // DEBUG(sm[rt[x]].mx);
        // for(auto y:G[x]){
            // DEBUG(y);
            // DEBUG(sm[rt[y]].mx);
        // }
    // }
    // exit(0);
    dfs(1);to[0] = 1;
    int now=1,len = 0;
    FOR(i,1,n){
        int c = S[i]-'a';
        if(ch[now][c]) len++,now = ch[now][c];
        else{
            while(now && !ch[now][c]) now = fail[now];
            if(!now) now = 1,len = 0;
            else len = ::len[now]+1,now = ch[now][c];
        }
        to[i] = now;le[i] = len;
    }
    int q;scanf("%d",&q);
    while(q--){
        int l,r,pl,pr;scanf("%d%d%d%d",&l,&r,&pl,&pr);
        int v = to[pr];
        if(le[pr] < pr-pl+1){
            printf("%d %d\n",l,0);
            continue;
        }
        ROF(i,MAXM,0){
            if(::len[f[v][i]] >= pr-pl+1){
                v = f[v][i];
            }
        }
        Node ans = query(rt[v],1,m,l,r);
        if(ans.ps == -1) printf("%d %d\n",l,0);
        else printf("%d %d\n",ans.ps,ans.mx);
    }
    return 0;
}