现在 Bitaro 准备用扫帚打扫房间。我们认为扫帚是放置在房间里的一条线段，并且将这条线段的长度称为扫帚的宽度。由于 Bitaro 很有条理，所以他只会用以下的两种方式打扫房间：
-
Bitaro 将扫帚平行于 \(y\) 轴放置，一端位于原点。然后他会垂直向右移动扫帚，直到不能移动为止。如果扫帚的宽度为 \(l\)，那么原来一堆满足 \(x<N-l,y\leq l\) 的灰尘 \((x,y)\) 将会被移动到 \((N-l,y)\)。（这个位置可能会存在多堆灰尘）我们称这个过程为过程 H。
-
Bitaro 将扫帚平行于 \(x\) 轴放置，一端位于原点。然后他会水平向上移动扫帚，直到不能移动为止。如果扫帚的宽度为 \(l\)，那么原来一堆满足 \(x\leq l,y<N-l\) 的灰尘 \((x,y)\) 将会被移动到 \((x,N-l)\)。（这个位置可能会存在多堆灰尘）我们称这个过程为过程 V。
在 Bitaro 的房间里，依次会发生 \(Q\) 个事件。第 \(i\) 个事件形如以下 \(4\) 种：
-
Bitaro 想要计算第 \(P_i\) 堆灰尘的位置坐标；
-
Bitaro 使用宽度为 \(L_i\) 的扫帚，进行了过程 H；
-
Bitaro 使用宽度为 \(L_i\) 的扫帚，进行了过程 V；
-
有一堆新的灰尘出现在点 \((A_i,B_i)\) 处。如果在这个事件之前一共有 \(c\) 堆灰尘，那么这堆灰尘就是房间中的第 \(c+1\) 堆灰尘。
由于 Bitaro 已经 AK 了 IOI，啥都不想干，所以你需要写一个程序，给出房间的腰长，每一堆灰尘的位置坐标和每个事件的细节，求出要求的某堆灰尘的位置坐标。
输入格式
第一行三个整数，分别为 \(N,M,Q\)。
接下来 \(m\) 行，每行两个整数 \(X_i,Y_i\)，表示第 \(i\) 堆灰尘一开始的位置。
接下来 \(Q\) 行，每行两到三个整数，表示一个事件。设 \(T_i\) 为第一个整数，每行含义如下：
-
如果 \(T_i=1\)，则这行有两个整数 \(T_i,P_i\)，表示 Bitaro 要计算第 \(P_i\) 堆灰尘的坐标；
-
如果 \(T_i=2\)，则这行有两个整数 \(T_i,L_i\)，表示 Bitaro 用宽度为 \(L_i\) 的扫帚进行了过程 H；
-
如果 \(T_i=3\)，则这行有两个整数 \(T_i,L_i\)，表示 Bitaro 用宽度为 \(L_i\) 的扫帚进行了过程 V；
-
如果 \(T_i=4\)，则这行有三个整数 \(T_i,A_i,B_i\)，表示一堆新的灰尘出现在 \((A_i,B_i)\) 位置。
输出格式
对于每个 \(T_i=1\) 的事件，输出一行两个整数，表示事件 \(i\) 发生时第 \(P_i\) 堆灰尘的位置坐标。
子任务
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| Subtask 1 | \(m\leq 2\times 10^3,Q\leq 5\times 10^3\) | \(1\) |
| Subtask 2 | \(T\in\{1,2,4\}\) | \(10\) |
| Subtask 3 | \(T\in\{1,2,3\},X_i\leq X_{i+1},Y_i\geq Y_{i+1}(1\leq i\leq m-1)\) | \(11\) |
| Subtask 4 | \(T\in\{1,2,3\}\) | \(53\) |
| Subtask 5 | 无 | \(25\) |
对于 \(100\%\) 的数据，\(1\leq n\leq 10^9,1\leq m\leq 5\times 10^5,1\leq Q\leq 10^6\)。保证：
-
\(0\leq X_i,Y_i\leq N,X_i+Y_i\leq N(1\leq i\leq m)\)；
-
\(1\leq P_i\leq M^\prime(1\leq i\leq Q)\)，其中 \(M^\prime\) 表示事件 \(i\) 发生时灰尘的堆数；
-
\(0\leq L_i\leq n-1(1\leq i\leq Q)\)；
-
\(0\leq A_i,B_i\leq n,A_i+B_i\leq n(1\leq i\leq Q)\)；
-
至少存在一个 \(T_i=1\) 的事件。
考虑 subtask1。直接线段树区间取 max 即可。
然后考虑 subtask3，如果比较直接的方法是用平衡树维护那条折线。因为修改是不改变相对顺序的，可以直接平衡树干。
考虑subtask4，这里写两种做法
-
继续平衡树。当一个点被操作后，就加入了那条折线上从。现在要想办法得到一个点第一次到那条直线上的时间。对于一个在 \((a,b)\) 上的点，查询是否有询问询问到他的。这个询问可以用线段树找。然后就像 subtask3 那样查询即可。
-
改用线段树。现在 x 轴和 y 轴会互相影响，非常麻烦。考虑把他们给分开处理。如果现在有一次修改H \([0,x]\times[0,n-x]\)，那么下一次修改V只会影响 \([x+1,y]\times[0,n-y]\)。这样子可以得到 \(x\) 坐标的操作只对 \(y\) 坐标超过某一个数的进行影响。倒着扫描 \(y\)，线段树维护 \(x\) 的操作就可以了。
至于subtask5，加上线段树分治把插入干掉就可以了。
这里的线段树分治和正常的不太一样，不过差不多。得到一个询问的物品存在的区间，然后线段树分治，每次把分治区间所有物品进行操作。
这里写了线段树。
#include<bits/stdc++.h>
using namespace std;
const int N=1.5e6+5,M=3e7+5;
int n,m,q,op[N],x[N],y[N],a[N],b[N],id[N],c[N],d[N],ix[N],iy[N],p[N],l[N];
vector<int>g[N<<2];
pair<int,int>sa[N],sb[N];
struct segment{
int lc[M],rc[M],tr[M],idx=1;
void clr()
{
for(int i=1;i<=idx;i++)
lc[i]=rc[i]=0,tr[i]=-1;
idx=1;
}
void upd(int&o,int l,int r,int x,int y,int z)
{
if(!o)
o=++idx;
if(x<=l&&r<=y)
return tr[o]=max(tr[o],z),void();
int md=l+r>>1;
if(md>=x)
upd(lc[o],l,md,x,y,z);
if(md<y)
upd(rc[o],md+1,r,x,y,z);
}
int ask(int o,int l,int r,int x)
{
if(!o)
return -1;
if(l==r)
return tr[o];
int md=l+r>>1;
if(md>=x)
return max(tr[o],ask(lc[o],l,md,x));
return max(tr[o],ask(rc[o],md+1,r,x));
}
}S,T;
void upd(int o,int l,int r,int x,int y,int z)
{
if(x<=l&&r<=y)
{
g[o].push_back(z);
return;
}
int md=l+r>>1;
if(md>=x)
upd(o<<1,l,md,x,y,z);
if(md<y)
upd(o<<1|1,md+1,r,x,y,z);
}
int cmpx(int x,int y)
{
return a[x]<a[y];
}
int cmpy(int x,int y)
{
return b[x]<b[y];
}
void solve(int o,int l,int r)
{
int X=0,Y=0,k,rt=1;
if(g[o].size())
{
// printf("%d %d\n",l,r);
S.clr(),T.clr();
for(int i=l;i<=r;i++)
{
if(op[i]==2)
{
k=S.ask(1,0,n,p[i]);
sa[++X]=make_pair(k,p[i]);
T.upd(rt,0,n,k,n-p[i]-1,p[i]+1);
}
else if(op[i]==3)
{
k=T.ask(1,0,n,p[i]);
sb[++Y]=make_pair(k,p[i]);
S.upd(rt,0,n,k,n-p[i]-1,p[i]+1);
}
}
S.clr(),T.clr();
for(int i=0;i<g[o].size();i++)
ix[i+1]=iy[i+1]=g[o][i],c[g[o][i]]=a[g[o][i]],d[g[o][i]]=b[g[o][i]];
// printf("%d\n",d[7]);
sort(ix+1,ix+g[o].size()+1,cmpx);
sort(sa+1,sa+X+1);
for(int i=1,l=1;i<=g[o].size();i++)
{
while(l<=X&&sa[l].first<=a[ix[i]])
S.upd(rt,0,n,0,sa[l].second,n-sa[l].second),++l;
c[ix[i]]=max(c[ix[i]],S.ask(1,0,n,b[ix[i]]));
}
sort(iy+1,iy+g[o].size()+1,cmpy);
sort(sb+1,sb+Y+1);
for(int i=1,l=1;i<=g[o].size();i++)
{
while(l<=Y&&sb[l].first<=b[iy[i]])
T.upd(rt,0,n,0,sb[l].second,n-sb[l].second),++l;
d[iy[i]]=max(d[iy[i]],T.ask(1,0,n,a[iy[i]]));
}
// printf("b:%d %d\n",l,r);
for(int i:g[o])
{
a[i]=c[i],b[i]=d[i];
// printf("a:%d %d %d %d\n",i,a[i],b[i],iy[1]);
}
// exit(0);
}
if(l^r)
{
int md=l+r>>1;
solve(o<<1,l,md);
solve(o<<1|1,md+1,r);
}
}
int main()
{
// freopen("P7220.in","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)
scanf("%d%d",x+i,y+i),l[i]=1;
for(int i=1,s,t;i<=q;i++)
{
scanf("%d%d",op+i,&s);
if(op[i]==1)
{
a[i]=x[s],b[i]=y[s];
upd(1,1,q,l[s],i,i);
}
else if(op[i]==4)
scanf("%d",&t),x[++m]=s,y[m]=t,l[m]=i;
else
p[i]=s;
}
solve(1,1,q);
for(int i=1;i<=q;i++)
if(op[i]==1)
printf("%d %d\n",a[i],b[i]);
}