考虑设 $T_i\le \sqrt{\sum T}$ 的为短周期门，$T_i>\sqrt{\sum T}$ 的为长周期门，可以视为我们拥有不超过 $\sqrt{\sum T}$ 个长周期门和 $O(n)$ 个短周期门。

考虑对于每个短周期门进行一遍 DP，求出其走 $1\sim \sqrt{\sum T}$ 步之后的终点，当然如果一个点走若干步之后到一个长周期的门就不需要再走了，因为每个短周期其出边不同。

然后对于每个短周期加入长周期的贡献，直接求出每个长周期位置走 $1\sim \sqrt{\sum T}$ 步的终点，此时所有转移都是已知的，显然可以直接求出。在处理完短周期的转移之后，我们就可以在 $O(n)$ 的时间内求出这个短周期的所有排列相乘后的结果。

因此，对于 $n$ 个排列的区间乘法的某一项，直接通过分块就可以 $O(\left(\sum T\right)^{1.5}+n\left(\sum T\right)^{0.5})$ 预处理，$O(\sqrt{\sum T})$ 单次求解。

然后考虑最后查询的内容，是一个前缀加一个后缀加若干个整段，于是我们只需要再预处理整段的信息，然后倍增求出跳 $2^k$ 次的结果即可。

总时间复杂度 $O(\left(\sum T\right)^{1.5}+n\left(\sum T\right)^{0.5}+(n+q)\log a)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int B=256,N=65536;
int a[256][100003];
int b[200][100003];
int tr[256][100003];
int to[256][100003];
short t[256][100003];
int sz[100003],id[100003];
int p[45][100003],cnt;
int n=read(),m=read();
int query(int l,int r,int x)
{
    int bl=l>>8,br=r>>8;
    if((l&255)==0) --bl;
    if((r&255)==255) ++br;
    if(bl==br)
    {
        for(int i=l; i<=r; ++i)
            if(id[x]) x=b[id[x]][i]; else x=a[i&255][x];
        return x;
    }
    for(int i=l,tr=(bl+1)<<8; i<tr; ++i)
        if(id[x]) x=b[id[x]][i]; else x=a[i&255][x];
    for(int i=bl+1; i<br; ++i) x=tr[i][x];
    for(int i=(br<<8); i<=r; ++i)
        if(id[x]) x=b[id[x]][i]; else x=a[i&255][x];
    return x;
}
signed main()
{
    vector<int> arr;
    for(int i=1; i<=n; ++i) sz[i]=read();
    for(int i=1; i<=n; ++i)
    {
        if(sz[i]<=B)
        {
            for(int j=0; j<sz[i]; ++j)
                a[j][i]=read();
            for(int j=sz[i]; j<B; ++j)
                a[j][i]=a[j-sz[i]][i];
        }
        else
        {
            arr.push_back(i),id[i]=++cnt;
            for(int j=0; j<sz[i]; ++j)
                b[cnt][j]=read();
            for(int j=sz[i]; j<N; ++j)
                b[cnt][j]=b[cnt][j-sz[i]];
        }
    }
    for(int i=1; i<=n; ++i) t[B-1][i]=B,to[B-1][i]=a[B-1][i];
    for(int i=B-2; i>=0; --i)
        for(int j=1; j<=n; ++j)
            if(id[a[i][j]]) t[i][j]=i+1,to[i][j]=a[i][j];
            else t[i][j]=t[i+1][a[i][j]],to[i][j]=to[i+1][a[i][j]];
    for(int i=0; i<B; ++i)
    {
        int pos=0;
        for(int k:arr)
            ++pos,to[B-1][k]=b[pos][i*B+B-1];
        for(int j=B-2,o; j>=0; --j)
        {
            int pos=0;
            for(int k:arr)
            {
                ++pos;
                if(id[b[pos][i*B+j]]) to[j][k]=to[j+1][b[pos][i*B+j]];
                else if(t[j+1][b[pos][i*B+j]]==B) to[j][k]=to[j+1][b[pos][i*B+j]];
                else o=b[pos][i*B+j],to[j][k]=to[t[j+1][o]][to[j+1][o]];
            }
        }
        for(int j=1; j<=n; ++j)
            if(id[j]) tr[i][j]=to[0][j];
            else if(t[0][j]==B) tr[i][j]=to[0][j];
            else tr[i][j]=to[t[0][j]][to[0][j]];
    }
    for(int i=1; i<=n; ++i) p[0][i]=query(0,N-1,i);
    for(int i=1; i<45; ++i)
        for(int j=1; j<=n; ++j)
            p[i][j]=p[i-1][p[i-1][j]];
    for(ll v,t,d; m--;)
    {
        v=read(),t=read()&(N-1),d=read();
        if(t+d>N)
        {
            d-=(N-t),v=query(t,N-1,v);
            for(ll i=d>>16,j=0; i; i>>=1,++j)
                if(i&1) v=p[j][v];
            d&=65535;
            if(d>0) v=query(0,d-1,v);
            printf("%lld\n",v);
        }
        else printf("%d\n",query(t,t+d-1,v));
    }
    return 0;
}