Description

有一列元素，每一个元素有三个属性:标号、标识符、数值。这些元素按照标号从1~n排列，标识符也是1~n的一个排列，初始时数值为0。当然我们可以把每个元素看成一个多维数字，那么这列元素就是一个数列。

现在请你维护这个数列，使其能支持以下两种操作：1.将标号为l~r的所有元素的数值先乘上x，再加上y；2.将标识符为l~r的所有元素的数值先乘上x，再加上y。当然你还得回答某些询问：1.标号为l~r的所有元素的数值的和；2.标识符为l~r的所有元素的数值的和。

Input

第一行有两个正整数n、m，分别表示数列长度和操作与询问个数的总和。第二行有n个正整数，表示每个元素的标识符，保证这n个数是1~n的一个排列。接下来m行，每行的第一个数字为op。若op为0，则表示要进行第一个操作，接下去四个数字表示l,r,x,y;若op为1，则表示要进行第二个操作，接下去四个数字表示l,r,x,y;若op为2，则表示要回答第一个询问，接下去两个数字表示l,r;若op为3，则表示要回答第二个询问，接下去两个数字表示l,r。

Output

包含若干行，每行表示一个询问的答案。由于答案可能很大，只要请你输出答案对536870912取模后的值即可。

Sample Input

4 4

2 1 4 3

0 2 3 4 5

1 1 3 4 7

2 1 1

3 1 1

Sample Output

7

27

HINT

第一次操作后，数列变为0 5 5 0

第二次操作后，数列变为7 27 5 7

N,M<=50000, 1<=L<=R<=N 0<=X,Y<=2^31-1

---

KD-Tree裸题，将\(a_i\)看做平面上的点\((i,p_i)\)，每次操作都是一个矩形

支持打标记，复杂度\(O(n\sqrt{n})\)

然后你发现Bzoj死活过不去

卡了1h多的常无果……网上搜索取模优化……顺便看了一下膜数转二进制后的结果……

膜数=\(2^{29}\)……

我#$%&#&（脏话）

然后这题就过了……

/*program from Wolfycz*/#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=5e4,Mod=536870912;int n,m,T;struct S1{    #define ls(x) tree[x].ls    #define rs(x) tree[x].rs    int tot,root;    struct node{        int type,ls,rs,v[2],Max[2],Min[2],val;        int cnt,mlt,sum,len;        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].mlt=1,tree[p].len=r-l+1; if (l
          
           mid) rs(p)=build(mid+1,r,type^1); updata(p); return p; } void init(){ Add(tree[0].Max,-inf),Add(tree[0].Min,inf); for (int i=1;i<=n;i++) tree[i].v[0]=i,tree[i].v[1]=read(); root=build(1,tot=n,0); } void Add_mlt(int p,int v){ tree[p].val*=v; tree[p].sum*=v; tree[p].mlt*=v; tree[p].cnt*=v; } void Add_cnt(int p,int v){ tree[p].val+=v; tree[p].cnt+=v; tree[p].sum+=tree[p].len*v; } void pushdown(int p){ if (tree[p].mlt!=1){ Add_mlt(ls(p),tree[p].mlt); Add_mlt(rs(p),tree[p].mlt); tree[p].mlt=1; } if (tree[p].cnt){ Add_cnt(ls(p),tree[p].cnt); Add_cnt(rs(p),tree[p].cnt); tree[p].cnt=0; } } void Modify(int p,int x,int y,int mv,int cv){//cnt_v,mlt_v if (x>tree[p].Max[T]||y
           
            tree[p].Max[T]||y
            
             1){ int l=read(),r=read(); T=type-2; printf("%d\n",KD.Query(KD.root,l,r)&(Mod-1)); } } return 0;}