1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<cstring>
  6 #define mod 9223372034707292160
  7 #define ll unsigned __int64
  8 using namespace std;
  9 ll n, m, a[1000006], sum;
 10 struct node{
 11     ll l, r, sum, lazy;
 12 }t[1001000*2];
 13 void pushup(ll i){
 14     t[i].sum = (t[i*2].sum + t[i*2+1].sum)%mod;
 15     t[i].lazy = min(t[i*2].lazy,t[i*2+1].lazy);
 16 }
 17 void build(ll i, ll l, ll r){
 18     t[i].l = l;
 19     t[i].r = r;
 20     if(l == r){
 21         t[i].sum = a[l];
 22         t[i].lazy = 0;
 23         return ;
 24     }
 25     ll mid = (l+r)/2;
 26     build(i*2, l, mid);
 27     build(i*2+1, mid+1, r);
 28     pushup(i);
 29 }
 30 ll fun(ll a, ll b){//快速加法防止a*b溢出
 31     ll sum = 0;
 32     while(b){
 33         if(b & 1){
 34             sum = (sum + a) % mod;
 35             printf(" %I64d\n",sum);
 36         }
 37         b /= 2;
 38         a = (a*2) % mod;
 39         //printf("  %I64d\n",a);
 40     }
 41     return sum;
 42 }
 43 
 44 void update(ll i, ll x, ll y){
 45     if(t[i].lazy == 30)
 46         return ;
 47     ll l = t[i].l;
 48     ll r = t[i].r;
 49     if(l == x && y == r && x == y){
 50         t[i].sum = fun(t[i].sum,t[i].sum);//快速加法防止a*b溢出
 51         t[i].lazy++;
 52         //printf(" %I64d\n",t[i].sum);
 53         return ;
 54     }
 55     ll mid = (l+r)/2;
 56     if(x > mid)
 57         update(i*2+1, x, y);
 58     else if(y <= mid)
 59         update(i*2, x, y);
 60     else{
 61         update(i*2+1, mid+1, y);
 62         update(i*2, x, mid);
 63     }
 64     pushup(i);
 65 }
 66 
 67 ll query(ll i, ll x, ll y){
 68     ll l = t[i].l;
 69     ll r = t[i].r;
 70     if(l == x && r == y)
 71         return t[i].sum;
 72     ll mid = (l+r)/2;
 73     if(y <= mid)
 74         return (query(i*2, x, y))%mod;
 75     else if(x > mid)
 76         return (query(i*2+1, x, y))%mod;
 77     else
 78         return (query(i*2, x, mid)+query(i*2+1, mid+1, y))%mod;
 79 }
 80 
 81 int main()
 82 {
 83     int i, j, T, x, y;
 84     int cas = 1;
 85     scanf("%d",&T);
 86     while(T--){
 87         scanf("%I64d%I64d",&n,&m);
 88         for(i = 1; i <= n; i++)
 89             scanf("%I64d",&a[i]);
 90         build(1, 1, n);
 91         printf("Case #%d:\n",cas++);
 92         sum = 0;
 93         while(m--){
 94             scanf("%d%d",&x,&y);
 95             sum = (sum + query(1, x, y))%mod;
 96             printf("%I64d\n",sum);
 97             update(1, x, y);
 98         }
 99     }
100     return 0;
101 }