1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define lson L,m,rt<<1
  5 #define rson m+1,R,rt<<1|1
  6 #define ll long long
  7 const int maxn=500010;
  8 const int mod=1008610010;
  9 using namespace std;
 10 
 11 ll pri[maxn<<2],sum[maxn<<2],add[maxn<<2];
 12 
 13 int n,m,rt;
 14 void pushup(int rt)
 15 {
 16     sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
 17     return ;
 18 }
 19 void pushdown(int rt)
 20 {
 21     if(add[rt])
 22     {
 23         add[rt<<1]=(add[rt<<1]+add[rt])%mod;
 24         add[rt<<1|1]=(add[rt<<1|1]+add[rt])%mod;
 25         sum[rt<<1]=(sum[rt<<1]+pri[rt<<1]*add[rt]%mod)%mod; 
 26          //错误示范：   sum[rt<<1]=(sum[rt<<1]+pri[rt<<1]*add[rt<<1]%mod)%mod; 
 27         sum[rt<<1|1]=(sum[rt<<1|1]+pri[rt<<1|1]*add[rt]%mod)%mod;
 28         //错误示范： sum[rt<<1|1]=(sum[rt<<1|1]+pri[rt<<1|1]*add[rt<<1|1]%mod)%mod;
 29         add[rt]=0;
 30     }
 31 }
 32 
 33 void build(int L,int R,int rt)
 34 {
 35     sum[rt]=0;
 36     add[rt]=0;
 37     if(L==R)
 38     {
 39         scanf("%lld",&pri[rt]);
 40         pri[rt]=pri[rt]%mod;
 41         return ;
 42     }
 43     int m=(L+R)>>1;
 44     build(lson);
 45     build(rson);
 46     pri[rt]=(pri[rt<<1]+pri[rt<<1|1])%mod;
 47     return ;
 48 }
 49 
 50 void update(int l,int r,int x,int L,int R,int rt)
 51 {
 52     if(l<=L&&R<=r) {
 53         add[rt]=(add[rt]+x)%mod;
 54         sum[rt]=(sum[rt]+pri[rt]*x%mod)%mod;    
 55         //开始写成了sum[rt]=(sum[rt]+pri[rt]*add[rt]%mod)%mod; 调试好久好久。。
 56         return ;
 57     }
 58     pushdown(rt);
 59     int m=(L+R)>>1;
 60     if(l<=m) update(l,r,x,lson);
 61     if(r>m) update(l,r,x,rson);
 62     pushup(rt);  //记得要向上更新！！！
 63     return ;
 64 }
 65 
 66 ll  query(int l,int r,int L,int R,int rt)
 67 {
 68     if(l<=L&&R<=r)
 69     {
 70         return sum[rt];
 71     }
 72     pushdown(rt);
 73     int m=(L+R)>>1;
 74     ll ans=0;
 75     if(l<=m) ans=(ans+query(l,r,lson))%mod;
 76     if(r>m) ans=(ans+query(l,r,rson))%mod;
 77     return ans;
 78 }
 79 int op,a,b,x;
 80 int main()
 81 {
 82     while(scanf("%d",&n)!=EOF)
 83     {
 84         build(1,n,1);
 85 
 86         scanf("%d",&m);
 87         while(m--)
 88         {
 89             scanf("%d",&op);
 90             if(op==1)
 91             {
 92                 scanf("%d%d%d",&a,&b,&x);
 93                 update(a,b,x,1,n,1);
 94             }
 95             else
 96             {
 97                 scanf("%d%d",&a,&b);
 98                 printf("%lld\n",query(a,b,1,n,1));
 99             }
100         }
101     }
102 }