#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

struct DS{
	int n1,n2;
	vector<int> x1,x2;
	vector<Data> val;
	void init(int N1,int N2){
		n1=N1,n2=N2;
		x1.resize(n1),x2.resize(n2),val.resize(n1*n2);
	}
	int size(){return max(0,n1+n2-2);}
	void init(int x,int dir,Data d1,Data d2){
		if(dir){
			init(1,2);
			x2[0]=x,x1[0]=x2[1]=inf;
		}else{
			init(2,1);
			x1[0]=x,x1[1]=x2[0]=inf;
		}
		val[0]=d1,val[1]=d2;
	}
   Data qval(int x,int y){
		return val[x*n2+y];
	}
	void upd(int x,int y,Data d){
		val[x*n2+y]=d;
	}
	Data ask(int x,int y){
		return qval(upper_bound(x1.begin(),x1.end(),x)-x1.begin(),
					upper_bound(x2.begin(),x2.end(),y)-x2.begin());
	}
}t[512];
int top;

pii p[261],q[261];
DS merge(DS a,DS b)
{
	DS c;
	c.init(a.n1+b.n1-1,a.n2+b.n2-1);
	int j=0,now=0;
	For(i,0,a.n1-1){
		while(j<b.n1&&b.x1[j]<a.x1[i]){
			p[now]=mkp(i,j);
			c.x1[now]=b.x1[j];
			++j,++now;
		}
		p[now]=mkp(i,j);
		c.x1[now]=a.x1[i];
		++now; 
	}
	j=0,now=0;
   For(i,0,a.n2-1){
		while(j<b.n2&&b.x2[j]<a.x2[i]){
			q[now]=mkp(i,j);
			c.x2[now]=b.x2[j];
			++j,++now;
		}
		q[now]=mkp(i,j);
		c.x2[now]=a.x2[i];
		++now;
	}
	For(i,0,c.n1-1)
		For(j,0,c.n2-1)
			c.upd(i,j,a.qval(p[i].fi,q[j].fi)*b.qval(p[i].se,q[j].se));
	return c;
}

void update(int x,int dir,Data d1,Data d2){
	t[++top].init(x,dir,d1,d2);
	while(top>1 && t[top].size()<256 && t[top-1].size()<=t[top].size()){
		t[top-1]=merge(t[top-1],t[top]);
		--top;
	}
}

Data query(int x,int y){
	Data ret; ret.clr();
	For(i,1,top) ret*=t[i].ask(x,y);
	return ret;
}