ll@n,@b,@q,x[q+1]{1%b},y[]{1%b},z[]{1%b};
fenwick<ll>f;
f.malloc(1d5+1,1);
rep(i,q){
	@[x,y,z][i+1]=(@[x[i]+1,3y[i]+2x[i+1]*z[i],3z[i]])%b;
	ll@l,@m,@r;
	f.add(l,1);
	f.add(r+1,-1);
	ll k=f.get(m);
	wt(x[k],y[k],z[k]);
}