Description

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

Input

第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

Output

对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

Sample Input

7 43

1 2 3 4 5 6 7

5

1 2 5 5

3 2 4

2 3 7 9

3 1 3

3 4 7

Sample Output

2

35

8

HINT

【样例说明】

初始时数列为(1,2,3,4,5,6,7)。

经过第1次操作后，数列为(1,10,15,20,25,6,7)。

对第2次操作，和为10+15+20=45，模43的结果是2。

经过第3次操作后，数列为(1,10,24,29,34,15,16}

对第4次操作，和为1+10+24=35，模43的结果是35。

对第5次操作，和为29+34+15+16=94,模43的结果是8。

测试数据规模如下表所示

数据编号 1 2 3 4 5 6 7 8 9 10

N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

 

题解：

　　码来当板子咯qwq

　　需要注意的是在维护add和mul两个lazy标记时，它们的优先级总为mul先于add标记。

　　在区间乘的时候，add标记和区间val也要跟着乘，在下传标记时mul的优先级也总是高于add标记。

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #define ll long long  7 using namespace std;  8 const int maxn=100009;  9 int n,m,mod,a[maxn]; 10 struct tree 11 { 12     int l,r; 13     ll val,add,mul; 14 }tr[maxn<<2]; 15  16 void build(int x,int la,int ra) 17 { 18     tr[x].l=la;tr[x].r=ra; 19     tr[x].add=0;tr[x].mul=1;//加和乘的性质,add为0，mul为1 20     if(la==ra) 21     { 22         tr[x].val=a[la]%mod; 23         return; 24     } 25     int mid=(la+ra)>>1; 26     build(x<<1,la,mid);build(x<<1|1,mid+1,ra); 27     tr[x].val=(tr[x<<1].val+tr[x<<1|1].val)%mod; 28     return; 29 } 30  31 void down(int x) 32 { 33     if(tr[x].mul==1&&tr[x].add==0)return; 34  35     tr[x<<1].mul=(tr[x<<1].mul*tr[x].mul)%mod; 36     tr[x<<1|1].mul=(tr[x<<1|1].mul*tr[x].mul)%mod; 37      38     tr[x<<1].add=(tr[x<<1].add*tr[x].mul+tr[x].add)%mod; 39     tr[x<<1|1].add=(tr[x<<1|1].add*tr[x].mul+tr[x].add)%mod; 40      41     tr[x<<1].val=(tr[x<<1].val*tr[x].mul + tr[x].add*(tr[x<<1].r-tr[x<<1].l+1))%mod; 42     tr[x<<1|1].val=(tr[x<<1|1].val*tr[x].mul + tr[x].add*(tr[x<<1|1].r-tr[x<<1|1].l+1))%mod; 43      44     tr[x].add=0;tr[x].mul=1; 45 } 46  47 void multiply(int x,int la,int ra,int num) 48 { 49     if(tr[x].l>ra||tr[x].r
            
             ra||tr[x].r
             
              ra||tr[x].r