首先考虑暴力，显然，这个东西答案就是每条边的贡献的和，每条边的贡献就是这条边两边分别选的有点的方案数量。写出来就是

$$tot^k - siz^k - (tot - siz)^k$$

注意到这个题的性质：每个点的子树内点的值都是 $u$ 到某个值的一段区间。容易发现画出来后需要考虑的叶子总是这样的一些子树（图中橙色的子树）。

8TTM7J_QZN__4I_@_S8E_UM.png

我们考虑除开 $L$ 和 $R$ 的橙色子树。这些子树内的点的子树都必然会选完所有叶子。如何快速的查这些点向上的边的贡献？明显 $siz^k,tot^k$ 很容易计算，考虑怎么算最后那个式子。我们考虑对它二项式定理展开：

$$\sum_{i=0}^k\binom k i tot^{k-i} siz^{i}$$

对于这些点我们预处理出它们的 $siz^i$ 的和，再做前缀和即可。

考虑 $L,R$ 的最近的叶子。这些点向上一直到 LCA 形成的链就是叶子不一定全部选完的链。我们单独考虑这些位置的贡献。

比如考虑左边 $L$ 到 LCA 这条链，相当于是固定了每个位置的左端点，右端点就是子树内的右端点。

我们写成式子，就是

$$(S_r-S_{L-1})^k + (tot - ( S_r - S_{L-1} ))^k$$

其中 $S$ 是前缀的叶子个数。

我们换个方式拆成二项式定理

$$maroonrk S_r^i(-S_{L-1})^{k-i}\\ (tot+S_{L-1})^i(-S_r)^{k-i}\\$$

这两个东西分别对应左右分别拆成的二项式定理。

所以我们应当预处理出 $(S_r)^{k-i}$ 在链上的和，剩下的 $(-S_{L-1})^{k-i},(tot+S_{L-1})^i$ 对于同一个询问都是常量。

另一条链类似整即可。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353
int n , q;
int C[12][12];
int A[MAXN] , fa[MAXN];
vi G[MAXN];

struct poi {
	int s[11] , siz;
	poi( ) {
		mem( s ) , siz = 0;
	}
	poi operator + ( const poi& x ) const {
		poi ret;
		ret.siz = x.siz + siz;
		rep( i , 0 , 10 ) ret.s[i] = ( x.s[i] + s[i] ) % P;
		return ret;
	}
	poi operator - ( const poi& x ) const {
		poi ret;
		ret.siz = siz - x.siz;
		rep( i , 0 , 10 ) ret.s[i] = ( s[i] + P - x.s[i] ) % P;
		return ret;
	}
} ss[MAXN] , sl[MAXN] , sr[MAXN] , lu[MAXN] , ru[MAXN] , cr[MAXN] , cl[MAXN];

int S[MAXN] , siz[MAXN] , L[MAXN] , R[MAXN];
int g[MAXN][19] , dep[MAXN]; // For LCA & Jump
void afs( int u ) {
	siz[u] = 1;
	L[u] = R[u] = u;
	for( int v : G[u] ) {
		dep[v] = dep[u] + 1;
		g[v][0] = u;
		rep( k , 1 , 18 ) if( g[g[v][k - 1]][k - 1] ) g[v][k] = g[g[v][k - 1]][k - 1]; else break;
		afs( v );
		R[u] = R[v];
		siz[u] += siz[v];
	}
	S[u] = ( G[u].empty() );
}

vector<poi> st[MAXN];

void bfs( int u ) {
	ss[u].siz = cl[u].siz = cr[u].siz = 1;
	int t = 1;
	rep( k , 0 , 10 ) {
		ss[u].s[k] = t;
		t = t * 1ll * ( S[R[u]] - S[L[u] - 1] ) % P;
	}
	t = 1;
	rep( k , 0 , 10 ) {
		cr[u].s[k] = t;
		t = t * 1ll * ( S[R[u]] ) % P;
	}
	t = 1;
	rep( k , 0 , 10 ) {
		cl[u].s[k] = t;
		t = t * 1ll * ( S[L[u] - 1] ) % P;
	}
	poi pr;
	for( int v : G[u] ) {
		bfs( v );
		ss[u] = ss[u] + ss[v];
		pr = pr + ss[v];
		st[u].pb( pr );
	}
}

void cfs( int u ) {
	poi pr;
	for( int i = G[u].size() - 1 ; i >= 0 ; -- i ) {
		int v = G[u][i];
		sr[v] = sr[u] + pr;
		pr = pr + ss[v];
	}
	pr = poi();
	for( int v : G[u] ) {
		lu[v] = lu[u] + cr[v];
		ru[v] = ru[u] + cl[v];
		sl[v] = sl[u] + pr;
		cfs( v );
		pr = pr + ss[v];
	}
}

int LCA( int u , int v ) {
	if( dep[u] < dep[v] ) u ^= v ^= u ^= v;
	if( dep[u] != dep[v] ) 
		for( int k = 18 ; k >= 0 ; -- k ) if( dep[g[u][k]] >= dep[v] ) u = g[u][k];
	if( u == v ) return u;
	for( int k = 18 ; k >= 0 ; -- k ) if( g[u][k] != g[v][k] ) u = g[u][k] , v = g[v][k];
	return g[u][0];
}
int jump( int u , int v ) { // u -> son of v
	for( int k = 18 ; k >= 0 ; -- k ) if( dep[g[u][k]] > dep[v] ) u = g[u][k];
	return u;
}

vi LeaF;

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

void solve() {
	int typ; cin >> typ >> n >> q;
	C[0][0] = 1;
	rep( i , 1 , 10 ) {
		C[i][0] = 1;
		rep( j , 1 , i ) C[i][j] = ( C[i - 1][j - 1] + C[i - 1][j] ) % P;
	}
	rep( i , 2 , n ) 
		scanf("%d",fa + i) , G[fa[i]].pb( i );
	dep[1] = 1 , afs( 1 );
	rep( i , 1 , n ) ( S[i] && ( LeaF.pb( i ) , 0 ) ) , S[i] += S[i - 1];
	bfs( 1 ) , cfs( 1 );
	int l , r , k , ans = 0 , lp , rp , pr , L , R;
	rep( i , 1 , q ) {
		scanf("%d%d%d",&l,&r,&k);
		if( typ ) l ^= ans , r ^= ans;
		if( l > *LeaF.rbegin() || r < *LeaF.begin() || S[r] - S[l - 1] <= 0 ) {
			printf("%d\n",ans = 0); continue;
		}
		L = *lower_bound( all( LeaF ) , l ) , R = *( -- upper_bound( all( LeaF ) , r ) );
		if( L == R ) {
			printf("%d\n",ans = 0); continue;
		}
		pr = LCA( L , R );
		lp = jump( L , pr ) , rp = jump( R , pr );
		poi all , Ru , Lu;
		all = all + sr[L] - sr[lp] + sl[R] - sl[rp];
		int p1 = lower_bound( all( G[pr] ) , rp ) - G[pr].begin() - 1 , p2 = lower_bound( all( G[pr] ) , lp ) - G[pr].begin();
		all = all + st[pr][ lower_bound( all( G[pr] ) , rp ) - G[pr].begin() - 1 ] - st[pr][ lower_bound( all( G[pr] ) , lp ) - G[pr].begin() ];
		Lu = lu[L] - lu[pr] , Ru = ru[R] - ru[pr];
		ans = all.s[k];
		int tot = S[r] - S[l - 1];
		rep( i , 0 , k ) {
			int sgn = ( i & 1 ) ? P - 1 : 1;
			// In the middle
			ans = ( ans + C[k][i] * 1ll * sgn % P * all.s[i] % P * Pow( tot , k - i ) ) % P;
			// Left Chain siz^k
			ans = ( ans + C[k][i] * 1ll * Lu.s[i] % P * Pow( P - S[L - 1] , k - i ) ) % P;
			// Left Chain (tot - siz)^k
			ans = ( ans + C[k][i] * 1ll * sgn % P * Lu.s[i] % P * Pow( tot + S[L - 1] , k - i ) ) % P;
			// Right Chain siz^k
			ans = ( ans + C[k][i] * 1ll * sgn % P * Ru.s[i] % P * Pow( S[R] , k - i ) ) % P;
			// Right Chain (tot - siz)^k 
			ans = ( ans + C[k][i] * 1ll * Ru.s[i] % P * Pow( ( tot - S[R] + P ) % P , k - i ) ) % P;
		}
		ans = ans * 1ll * Pow( tot , (ll)k * (P - 2) % (P - 1) ) % P;
//		cout << ans << ' ' << all.siz + Ru.siz + Lu.siz << endl;
		printf( "%d\n",ans = ( ( all.siz + Ru.siz + Lu.siz - ans ) % P + P ) % P );
	}
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}