#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define L 1<<20
#define MAXN 100005
#define P 1000000000
#define ll long long
char _buf[L],*S,*T,c;
inline char gc()
{
	if(S==T)
	{
		T=(S=_buf)+fread(_buf,1,L,stdin);
		if(S==T)return 0;
	}
	return *S++;
}
int get()
{
	for(c=gc();c<'0'||c>'9';c=gc());
	int x=c^'0';
	for(c=gc();c>='0'&&c<='9';c=gc())x=x*10+(c^'0');
	return x;
}
struct node
{
	int c[2],s,a,f;
}t[MAXN*200];
bool b[MAXN],bb;
int rx[2],ry[2],lr[2],n,m,i,j,k,l,o,u,v,r[MAXN],f[MAXN],h[MAXN],ne[MAXN<<1],p[MAXN<<1],w[MAXN<<1],s[MAXN],s1[MAXN],in[MAXN],id[MAXN],r1[MAXN],r2[MAXN],d[MAXN],D[MAXN],R[100][MAXN],q[MAXN],pr[MAXN],he,ta,top;
ll ans;
void rot(int &R,bool x)
{
	int y=t[R].c[x];
	t[R].c[x]=t[y].c[!x];
	t[y].c[!x]=R;
	t[y].s=t[R].s;
	t[R].s=t[t[R].c[0]].s+t[t[R].c[1]].s+1;
	R=y;
}
void ins(int &R,int x)
{
	if(!R)
	{
		R=++top;
		t[R].s=1;
		t[R].a=x;
		t[R].f=rand();
		return;
	}
	bool b=x>=t[R].a;
	ins(t[R].c[b],x);
	t[R].s++;
	if(t[t[R].c[b]].f<t[R].f)rot(R,b);
}
inline void del(int &R)
{
	R=0;
}
int ask(int R,int x)
{
	if(!R)return 0;
	if(t[R].a>=x)return t[t[R].c[1]].s+1+ask(t[R].c[0],x);
	return ask(t[R].c[1],x);;
}
int bfs(int X,int d1,int d2,int fa)
{
	int i,j,k;
	he=ta=0;
	D[q[ta++]=X]=d2;
	pr[X]=0;
	while(he!=ta)
	{
		for(j=h[i=q[he++]],s1[i]=b[i]=1,d[i]=d1+1;j;j=ne[j])if(p[j]!=pr[i]&&d[p[j]]>=d1)D[p[j]]=D[pr[q[ta++]=p[j]]=i]+w[j];
		if(d1)R[d1-1][i]=D[i];
	}
	for(i=ta-1;i>=0;i--)
	{
		s1[k=pr[q[i]]]+=s1[q[i]];
		if(s1[q[i]]<<1>ta)b[k]=0;
		if(s1[q[i]]<<1>=ta&&b[q[i]])break;
	}
	f[j=q[i]]=fa;
	s[j]=ta;
	if(d[j]=d1)
	{
		in[j]=X;
		id[j]=d2;
	}
	else  in[j]=id[j]=0;
	return j;
}
void dfs(int X)
{
	int i,j,k,l;
	R[d[X]][X]=0;
	del(r1[X]);
	ins(r1[X],r[X]);
	for(i=h[X];i;i=ne[i])if(d[p[i]]>=d[X])
	{
		del(r2[j=bfs(p[i],d[X]+1,w[i],X)]);
		for(k=0;k<s[j];k++)
		{
			l=q[k];
			ins(r1[X],r[l]-D[l]);
			ins(r2[j],r[l]-D[l]);
		}
		dfs(j);
	}
}
inline void add(int u,int v,int x)
{
	p[++m]=v;
	ne[m]=h[u];
	w[m]=x;
	h[u]=m;
	p[++m]=u;
	ne[m]=h[v];
	w[m]=x;
	h[v]=m;
}
void work(int i)
{
	add(i,f[i],j);
	d[i]=d[f[i]]+1;
	s[i]=1;
	in[i]=i;
	id[i]=j;
	ins(r1[i],r[i]);
	for(k=0;k<d[i];k++)R[k][i]=R[k][f[i]]+j;
	for(k=d[f[i]],l=f[o=i];l;k--,o=l,l=f[l])
	{
		u=R[k][i]-r[i];
		ans+=ask(r1[l],u)-ask(r2[o],u);
	}
	for(k=d[f[i]],v=0,l=f[o=i];l;k--,o=l,l=f[l])
	{
		u=r[i]-R[k][i];
		ins(r1[l],u);
		ins(r2[o],u);
		s[l]++;
		if(s[l]*0.88<s[o])v=l;
	}
	if(v)
	{
		if(d[v])u=bfs(in[v],d[v],id[v],f[v]);
		else u=bfs(1,0,0,0);
		r2[u]=r2[v];
		r2[v]=0;
		dfs(u);
	}
	printf("%lld\n",ans);
}
int main()
{
	freopen("flowera.in","r",stdin);
	freopen("flowera.out","w",stdout);
	get();
	n=get();
	get();
	get();
	r[1]=get();
	lr[0]=lr[1]=1;
	printf("0\n");
	ins(rx[0],r[1]);
	ins(rx[1],r[1]);
	ins(ry[0],r[1]);
	ins(ry[1],r[1]);
	for(i=2;i<=n;i++)
	{
		f[i]=get()^ans%P;
		j=get();
		r[i]=get();
		if(f[i]!=lr[0]&&f[i]!=lr[1])break;
		add(i,f[i],j);
		D[i]=D[f[i]]+j;
		bb=f[i]==lr[1];
		lr[bb]=i;
		ans+=ask(rx[bb],D[i]-r[i])+ask(ry[!bb],D[i]-r[i]);
		if(D[i]<=r[1]+r[i])ans--;
		ins(rx[bb],D[i]+r[i]);
		ins(ry[bb],r[i]-D[i]);
		printf("%lld\n",ans);
	}
	if(i<=n){
	for(k=1;k<=top;k++)t[k].c[0]=t[k].c[1]=0;
	top=0;
	memset(D,0,sizeof(D));
	k=bfs(1,0,0,0);
	dfs(k);
	for(work(i++);i<=n;i++)
	{
		f[i]=get()^ans%P;
		j=get();
		r[i]=get();
		work(i);
	}}
	return 0;
}