rt

submission

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>

#define N 500005
#define M 100005

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,char Extra=0) {
    if (x<0) putchar('-'),x=-x; if (x>9) W(x/10);
    putchar(x%10+'0'); if (Extra) putchar(Extra);
}

using namespace std;
int n,m; const int B=1505; string s[M];

int tot,ch[N][26],fail[N],pos[M];

void ins(string &s,int id) {
    int p=0;
    for (auto c:s) {
        if (!ch[p][c-'a']) ch[p][c-'a']=++tot;
        p=ch[p][c-'a'];
    }
    pos[id]=p;
}

void getfail() {
    queue<int> q;
    for (int i=0;i<26;i++)
        if (ch[0][i]) q.push(ch[0][i]);
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (int i=0;i<26;i++)
            if (ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
            else ch[u][i]=ch[fail[u]][i];
    }
}

int cnt,head[N];
struct Node { int to,nxt; }e[N<<1];

void add(int u,int v) { e[++cnt]=Node{v,head[u]},head[u]=cnt; }

int siz[N],dep[N],fa[N],son[N];

void dfs1(int u,int Fa) {
    siz[u]=1,dep[u]=dep[fa[u]=Fa]+1,son[u]=-1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        dfs1(v,u);
        siz[u]+=siz[v];
        if (son[u]==-1 or siz[v]>siz[son[u]]) son[u]=v;
    }
}

int top[N],dfncnt,dfn[N];

void dfs2(int u,int Top) {
    top[u]=Top,dfn[u]=++dfncnt;
    if (~son[u]) dfs2(son[u],Top);
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if (v==son[u]) continue;
        dfs2(v,v);
    }
}

inline int LCA(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

int num[N];

void dfs(int u) {
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        dfs(v);
        num[u]+=num[v];
    }
}

struct SGT {
    struct Tree { int mx; }t[M<<2];

    void build(int x,int l,int r) {
        if (l==r) return t[x].mx=num[pos[l]],void();
        int mid=(l+r>>1);
        build(x<<1,l,mid); build(x<<1|1,mid+1,r);
        t[x].mx=max(t[x<<1].mx,t[x<<1|1].mx);
    }

    int ask(int x,int l,int r,int L,int R) {
        if (L<=l and r<=R) return t[x].mx;
        int mid=(l+r>>1);
        if (R<=mid) return ask(x<<1,l,mid,L,R);
        else if (L>mid) return ask(x<<1|1,mid+1,r,L,R);
        else return max(ask(x<<1,l,mid,L,R),ask(x<<1|1,mid+1,r,L,R));
    }
}sgt;

int ans[M]; vector<int> Pos[M],Num[M];
struct Que { int l,r,k; }que[M];
struct Que1 { int l,r,id; }; vector<Que1> que1[M];

vector<int> ve[N];

void dfs3(int u) {
    for (int v:ve[u]) dfs3(v),num[u]+=num[v];
}

int block,mx[N],tag[N],bel[N],ll[N],rr[N];

void init() {
    block=sqrt(dfncnt);
    for (int i=1;i<=block;i++) {
        ll[i]=rr[i-1]+1,rr[i]=(i==block?dfncnt:ll[i]+block-1);
        for (int j=ll[i];j<=rr[i];j++) bel[j]=i;
    }
}

void upd(int l,int r,int k) {
    if (bel[l]==bel[r]) for (int i=l;i<=r;i++) mx[i]=max(mx[i],k);
    else {
        for (int i=l;i<=rr[bel[l]];i++) mx[i]=max(mx[i],k);
        for (int i=ll[bel[r]];i<=r;i++) mx[i]=max(mx[i],k);
        for (int i=bel[l]+1;i<bel[r];i++) tag[i]=max(tag[i],k);
    }
}

vector<int> que2[M];

int main() {
    n=R(),m=R();
    for (int i=1;i<=n;i++) cin>>s[i],ins(s[i],i);
    getfail();
    for (int i=1;i<=tot;i++) add(fail[i],i);
    dfs1(0,0); dfs2(0,0);
    for (int i=1;i<=m;i++) {
        int l=R(),r=R(),k=R(); que[i]=Que{l,r,k};
        if (s[k].size()>=B) que1[k].push_back({l,r,i});
        else que2[r].push_back(i);
    }
    for (int i=1;i<=n;i++)
        if (s[i].size()>=B and !que1[i].empty()) {
            int p=0;
            memset(num,0,(tot+1)*sizeof(int));
            for (auto c:s[i]) ++num[p=ch[p][c-'a']];
            dfs(0); sgt.build(1,1,n);
            for (auto [l,r,id]:que1[i]) ans[id]=sgt.ask(1,1,n,l,r);
        } else if (s[i].size()<B) {
            int p=0;
            for (auto c:s[i]) Pos[i].push_back(p=ch[p][c-'a']),++num[p];
            sort(Pos[i].begin(),Pos[i].end(),[](int tmp1,int tmp2) { return dfn[tmp1]<dfn[tmp2]; });
            Pos[i].erase(unique(Pos[i].begin(),Pos[i].end()),Pos[i].end());
            for (int j=1,k=Pos[i].size();j<k;j++) Pos[i].push_back(LCA(Pos[i][j-1],Pos[i][j]));
            Pos[i].push_back(0);
            sort(Pos[i].begin(),Pos[i].end(),[](int tmp1,int tmp2) { return dfn[tmp1]<dfn[tmp2]; });
            Pos[i].erase(unique(Pos[i].begin(),Pos[i].end()),Pos[i].end()); Num[i].resize(Pos[i].size());
            for (int j=1;j<Pos[i].size();j++) ve[LCA(Pos[i][j-1],Pos[i][j])].push_back(Pos[i][j]);
            dfs3(0);
            for (int j=0;j<Pos[i].size();j++) Num[i][j]=num[Pos[i][j]],num[Pos[i][j]]=0,ve[Pos[i][j]].clear();
        }
    init();
    for (int i=1;i<=n;i++) {
        upd(dfn[pos[i]],dfn[pos[i]]+siz[pos[i]]-1,i);
        for (auto id:que2[i]) for (int j=0;j<Pos[que[id].k].size();j++)
            if (max(tag[bel[dfn[Pos[que[id].k][j]]]],mx[dfn[Pos[que[id].k][j]]])>=que[id].l)
                ans[id]=max(ans[id],Num[que[id].k][j]);
    }
    for (int i=1;i<=m;i++) W(ans[i],'\n');
    return 0;
}