Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令	参数限制	内容
\(1\,x\,y\,A\)	\(1\leqslant x,y\leqslant N\)，\(A\)是正整数	将格子\(x,y\)里的数字加上\(A\)
\(2\,x_1\,y_1\,x_2\,y_2\)	\(1\leqslant x_1\leqslant x_2\leqslant N\\1\leqslant y_1\leqslant y_2\leqslant N\)	输出\(x_1\,y_1\,x_2\,y_2\)这个矩形内的数字和
\(3\)	无	终止程序

Input

输入文件第一行一个正整数N。

接下来每行一个操作。每条命令除第一个数字之外，

均要异或上一次输出的答案last_ans，初始时last_ans=0。

Output

对于每个2操作，输出一个对应的答案。

Sample Input

4

1 2 3 3

2 1 1 3 3

1 1 1 1

2 1 1 0 7

3

Sample Output

3

5

HINT

\(1\leqslant N\leqslant500000\)，操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。

---

20M显然不能树套树……于是我们用一个简单的数据结构——KD-Tree

自信的写了一发，交上去TLE……一测数据发现极限数据跑了2m……

完全不会优化啊……还是%%%hzwer

定一个阀值，当KD-Tree插入操作达到这个阀值时，就暴力重构KD-Tree

然后就可以过了……

/*program from Wolfycz*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline char gc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline int frd(){ int x=0,f=1; char ch=gc(); for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0'; return x*f;}inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; return x*f;}inline void print(int x){ if (x<0) putchar('-'),x=-x; if (x>9) print(x/10); putchar(x%10+'0');}const int N=2e5,V=1e4;int T;struct S1{ #define ls(p) tree[p].ls #define rs(p) tree[p].rs struct node{ int v[2],Max[2],Min[2]; int ls,rs,type,val,sum; void insert(int type,int val){v[type]=Min[type]=Max[type]=val;} bool operator <(const node &tis)const{return v[T]
          
           >1,p=mid; nth_element(tree+l,tree+mid,tree+r+1); tree[p].type=type,tree[p].sum=0; tree[p].ls=tree[p].rs=0; if (l
           
            mid) rs(p)=rebuild(mid+1,r,type^1); updata(p); tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum+tree[p].val; return p; } void Modify(int &p,int x,int y,int v){ if (!p){ p=++tot; tree[p].insert(0,x); tree[p].insert(1,y); tree[p].type=rand()&1; tree[p].val=tree[p].sum=v; return; } (tree[p].type?y:x)
            
             tree[p].Max[0]||R[0] 
             
              tree[p].Max[1]||R[1]