#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=300015,mod=998244353;

int Type,n,m,Q;

vector <int> e[N];

struct Gragh{

	static const int M=N;

	int cnt,y[M],nxt[M],fst[N];

	void clear(){

		cnt=1;

		memset(fst,0,sizeof fst);

	}

	void add(int a,int b){

		y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;

	}

}qs;

struct Point{

	int x,y;

	Point(){}

	Point(int _x,int _y){

		x=_x,y=_y;

	}

	Point operator - (Point a){

		return Point(x-a.x,y-a.y);

	}

};

LL Cross(Point a,Point b){

	return (LL)a.x*b.y-(LL)b.x*a.y;

}

struct Query{

	Point a;//a for cross

	int f,x,tmp;

	LL ans;

}q[N];

int depth[N],fa[N];

Point P[N];

int new_node(int f,int d){

	n++;

	e[n].clear(),fa[n]=f,depth[n]=d;

	e[f].push_back(n);

	e[n].push_back(f);

	return n;

}

void build_tree(){

	static int st[N],d;

	st[d=Q=0]=n=1;

	e[n].clear(),fa[n]=0,depth[n]=d;

	while (m--){

		int opt=read(),L,R,x,y;

		if (opt==1){

			x=read(),y=read();

			d++;

			st[d]=new_node(st[d-1],d);

			P[n]=Point(x,y);

		}

		else if (opt==2)

			d--;

		else if (opt==3){

			L=read(),R=read(),x=read(),y=read();

			Q++;

			q[Q].a=Point(x,y);

			q[Q].f=st[L],q[Q].x=st[R];

			q[Q].ans=-5e18;

		}

	}

	qs.clear();

	for (int i=1;i<=Q;i++)

		qs.add(q[i].x,i);

}

int Size,RT;

int size[N],Max[N],vis[N];

void get_root(int x,int pre){

	size[x]=1,Max[x]=0;

	for (auto y : e[x])

		if (y!=pre&&!vis[y]){

			get_root(y,x);

			size[x]+=size[y];

			Max[x]=max(Max[x],size[y]);

		}

	Max[x]=max(Max[x],Size-size[x]);

	if (Max[x]<Max[RT])

		RT=x;

}

void get_size(int x,int pre){

	size[x]=1;

	for (auto y : e[x])

		if (y!=pre&&!vis[y])

			get_root(y,x),size[x]+=size[y];

}

Point A[N];

int qid[N],qtot;

void get_query(int x){

	for (int id=qs.fst[x];id;id=qs.nxt[id])

		if (depth[q[qs.y[id]].f]<=depth[RT])

			qid[++qtot]=qs.y[id];

	for (auto y : e[x])

		if (y!=fa[x]&&!vis[y])

			get_query(y);

}

bool cmp(int a,int b){

	return q[a].tmp<q[b].tmp;

}

bool cmp2(int a,int b){

	return Cross(q[a].a,q[b].a)<0;

}

Point tmp[N];

int Tmp[N];

void Unknown(int *qid,int qt,Point *P,int &pt){

	if (pt<=1)

		return (void)sort(qid+1,qid+qt+1,cmp2);

	int mid=pt>>1,ls=mid,rs=pt-mid,kk=0;

	while (kk<qt&&q[qid[kk+1]].tmp<mid)

		kk++;

	for (int i=kk+1;i<=qt;i++)

		q[qid[i]].tmp-=mid;

	Unknown(qid,kk,P,ls);

	Unknown(qid+kk,qt-kk,P+mid,rs);

	for (int i=kk+1,j=1;i<=qt;i++){

		while (j<ls&&Cross(P[j+1]-P[j],q[qid[i]].a)<0)

			j++;

		q[qid[i]].ans=max(q[qid[i]].ans,Cross(q[qid[i]].a,P[j]));

	}

	int tot=0,j=1;

	for (int i=1;i<=ls;){

		Point now=j<=rs&&P[j+mid].x<=P[i].x?P[mid+(j++)]:P[i++];

		while (tot>1&&Cross(tmp[tot]-tmp[tot-1],now-tmp[tot-1])>=0)

			tot--;

		tmp[++tot]=now;

	}

	for (;j<=rs;j++){

		Point now=P[j+mid];

		while (tot>1&&Cross(tmp[tot]-tmp[tot-1],now-tmp[tot-1])>=0)

			tot--;

		tmp[++tot]=now;

	}

	while (tot>1&&tmp[tot].x==tmp[tot-1].x&&tmp[tot].y<=tmp[tot-1].y)

		tot--;

	int h=1;

	while (h<tot&&tmp[h].x==tmp[h+1].x&&tmp[h].y<=tmp[h+1].y)

		h++;

	for (int i=h;i<=tot;i++)

		P[i-h+1]=tmp[i];

	pt=tot-h+1;

	tot=0,j=kk+1;

	for (int i=1;i<=kk;)

		if (j<=qt&&Cross(q[qid[j]].a,q[qid[i]].a)<0)

			Tmp[++tot]=qid[j++];

		else

			Tmp[++tot]=qid[i++];

	for (;j<=qt;j++)

		Tmp[++tot]=qid[j];

	for (int i=1;i<=qt;i++)

		qid[i]=Tmp[i];

}

void solve(int x){

	Max[RT=0]=N,get_root(x,0),x=RT,get_size(x,0);

	int t=0;

	for (int i=x;!vis[i];i=fa[i])

		A[++t]=P[i];

	vis[x]=1,RT=x,qtot=0,get_query(x);

	for (int i=1;i<=qtot;i++)

		q[qid[i]].tmp=min(t,depth[x]-depth[q[qid[i]].f]+1);

	sort(qid+1,qid+qtot+1,cmp);

	int k=1;

	while (k<=qtot&&q[qid[k]].tmp<t)

		k++;

	Unknown(qid,k-1,A,t);

	sort(qid+k,qid+qtot+1,cmp2);

	for (int i=k,j=1;i<=qtot;i++){

		while (j<t&&Cross(A[j+1]-A[j],q[qid[i]].a)<0)

			j++;

		q[qid[i]].ans=max(q[qid[i]].ans,Cross(q[qid[i]].a,A[j]));

	}

	for (auto y : e[x])

		if (!vis[y])

			Size=size[y],solve(y);

}

int main(){

	Type=read();

	while (m=read()){

		build_tree(),Size=n;

		memset(vis,0,sizeof vis);

		vis[0]=1,solve(1);

		int ans=0;

		for (int i=1;i<=Q;i++)

			ans^=(int)((q[i].ans%mod+mod)%mod);

		cout << ans << endl;

	}

	return 0;

}