rt。

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define ll long long
using namespace std;
const int N = 4e5 + 5;
int n, fa[N][35], m, sz[N], belong[N], cnt;
int dis[N], lg[N];
template<typename T>inline void read(T &ff){
    T rr=1;ff=0;re char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')rr=-1;ch=getchar();}
    while(isdigit(ch)){ff=(ff<<1)+(ff<<3)+(ch^48);ch=getchar();}
    ff*=rr;
}
inline void dfs(int  u){
    if(belong[u]) return;
    sz[cnt]++;
    belong[u] = cnt;
    dfs(fa[u][0]);
}
inline int qpow(ll a, ll b, ll mod){
    ll now = 1;
    while(b){
        if(b & 1) now = (now * a) % mod;
        a = (a * a) % mod;
        b >>= 1; 
    }
    return  now;
}
inline int query(int u){
    if(belong[u]) return 0;
    dis[u] = query(fa[u][0]) + 1;
    return dis[u];
}
inline int pd(ll a, ll b){
    ll now = 1;
    while(b){
        if(b & 1) now = now * a;
        if(now >= n || a >= n) return 1e9;
        a = a*a;
        b >>= 1;
    }
    return now;
}
signed main(){
    read(n);
    lg[0] = -1;
    for(int i = 1; i <= n; i++) read(fa[i][0]), lg[i] = lg[i>>1] + 1;
    for(int j = 1; j <= 20; j++){
        for(int i = 1; i <= n; i++){
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    for(int i = 1; i <= n; i++){
        int x = n, now = i;
        for(int j = lg[n]; j >= 0; j--){
            if(x >= 1<<j) x -= 1<<j, now = fa[now][j];
        }
        if(!belong[now]) cnt++, dfs(now);
    }
    for(int i = 1; i <= n; i++) {
        if(!belong[i] && !dis[i]) query(i);
    }
    read(m);
    int s, t1, t2;
    for(int i = 1; i <= m; i++){
        read(s), read(t1), read(t2);
        int x = dis[s], now = s;
        int k = pd(t1, t2);
        if(k <= dis[s]){
            x = k, now = s;
            for(int j = lg[x]; j >= 0; j--){
                if(x >= (1<<j)) x -= (1<<j), now = fa[now][j]; 
            }
            printf("%d\n", now);
            continue;
        }
        for(int j = lg[x]; j >= 0; j--){
            if(x >= (1<<j)) x -= (1<<j), now = fa[now][j]; 
        }
        int mod = sz[belong[now]];
        x = qpow(t1%mod, t2, mod);
        x = ((x - dis[s])%mod + mod) % mod;
        for(int j = lg[x]; j >= 0; j--){
            if(x >= (1<<j)) x -= (1<<j), now = fa[now][j];
        }
        printf("%d\n", now);
    }
    return 0;
}