这题的空间限制开不下空间 $O(q\log^2n)$ 的可持久化线段树，使用该代码生成的数据可以叉掉所有题解（未来姚班zyl的题解代码不全，但应该无法通过）。对于树剖加可持久化线段树的做法（不清楚是否有其他做法），为减小空间常数，可以对每个重链各开一棵可持久化线段树，此时在一定情况下每次修改会修改 $2\log n$ 条重链的树的前缀，和 $1$ 条重链的树的区间，大约会新增 $2\lfloor\log n\rfloor\times(\lceil\log\frac{n}{\log n}\rceil+1)$ 个结点，每个结点 24B，共约 1025 MB，然而此时需要一棵额外的可持久化线段树维护版本，每次修改需要约 $(2\lfloor\log n\rfloor-1)\times(\lceil\log n\rceil+1)$ 个结点，每个结点 8B，共约 426 MB。因此该题目空间限制开到 2GB 需要极限卡空间，建议尽可能开到 3GB，否则一般的树剖写法可能无法通过。hack 数据由该代码生成（卡不到上述上界，但可以卡掉所有题解）。

#include<bits/stdc++.h>
using namespace std;
mt19937 R(114514);
unsigned rnd(unsigned l,unsigned r){
	return R()%(r-l+1)+l;
}
int n,q;
int main(){
	freopen("P7671.in","w",stdout);
	n=100000,q=100000;
	printf("%d %d\n",n,q);
	for(int i=2;i<=n;++i) printf("%d %d\n",i/2,i);
	for(int i=1;i<=n;++i) printf("%d ",rnd(1,100000));
	while(--q) printf("\n1 %d %d %d",rnd(65536,n),rnd(65536,n),rnd(1,100000));
	printf("\n2 %d %d",65536,n);
	return 0;
}