#include
     
      #include
      
       #include
       
        #include
        
         int a[100005],p;static const int MAXN=400000;struct  Segment_tree///1.把一段区间变成同一个数，2求任意区间的和{    int size;///区间容量    struct Node    {        long long a;        long long b;        long long sum;        int len;        void fun(long long a1,long long b1)///复合一个新标记        {            a=a*a1%p;            b=(b*a1+b1)%p;        }        void use()        {            sum=(sum*a+b*len)%p;        }        void clear()        {            a=1;            b=0;        }        bool islazy()        {            return a!=1||b!=0;        }    } node[MAXN];    void update(int pos)///结点更新函数    {        if(pos>=size)///判断是叶子        {            node[pos].sum=a[pos-size]%p;        }        else        {            node[pos].sum=(node[pos<<1].sum+node[pos<<1^1].sum)%p;            node[pos].len=node[pos<<1].len+node[pos<<1^1].len;        }        if(node[pos].islazy())///注意如果有懒惰标记的话要把懒惰标记用掉            node[pos].use();    }    void build(int n)///申请空空间    {        n+=4;///保险起见，申请时，申请得稍微大一点        size=1;        while(size
         
          0; i--)        {            node[i].clear();            update(i);///数值更新上去        }    }    void putdown(int s,int t)///将标记放下    {        if(s>1)///判断是否到顶，没达到顶继续往上爬        {            putdown(s>>1,t>>1);        }        if(node[s].islazy())///判断有没有标记，如果有标记话，下放给孩子        {            node[s<<1].fun(node[s].a,node[s].b);            node[s<<1^1].fun(node[s].a,node[s].b);            node[s].clear();        }        if(node[t].islazy())        {            node[t<<1].fun(node[t].a,node[t].b);            node[t<<1^1].fun(node[t].a,node[t].b);            node[t].clear();        }    }    void add(int l,int r,int x)    {        int s=l+size-1;        int t=r+size+1;        putdown(s>>1,t>>1);        ///更新标记>更新值>查询查询值        for(; s^t^1; s>>=1,t>>=1)        {            // printf("[%d %d]\n",s,t);            if(~s&1)                node[s^1].fun(1,x);            if(t&1)                node[t^1].fun(1,x);            update(s);            update(t);            update(s^1);            update(t^1);        }        while(s)///一直更新到顶        {            update(s);            update(s^1);            s>>=1;        }    }    void mul(int l,int r,int x)    {        int s=l+size-1;        int t=r+size+1;        putdown(s>>1,t>>1);        ///更新标记>更新值>查询查询值        for(; s^t^1; s>>=1,t>>=1)        {            // printf("[%d %d]\n",s,t);            if(~s&1)                node[s^1].fun(x,0);            if(t&1)                node[t^1].fun(x,0);            update(s);            update(t);            update(s^1);            update(t^1);        }        while(s)///一直更新到顶        {            update(s);            update(s^1);            s>>=1;        }    }    int query(int l,int r)    {        int s=l+size-1;        int t=r+size+1;        putdown(s>>1,t>>1);        long long sum=0;        ///更新标记>更新值>查询查询值        for(; s^t^1; s>>=1,t>>=1)        {            update(s);            update(t);            update(s^1);            update(t^1);            //    printf("[%d %d]\n",s,t);            if(~s&1)            {                sum+=node[s^1].sum;            }            if(t&1)            {                sum+=node[t^1].sum;            }        }        while(s)///一直更新到顶        {            update(s);            update(s^1);            s>>=1;        }        return sum%p;    }    void put()    {        int i=1,j=1,s=size*4,k,len=3;        for(i=1; i<=2*size-1; i++)        {            if(i==j)            {                puts("");                j<<=1;                s>>=1;                for(k=0; k