Description

 

After doing Ray a great favor to collect sticks for Ray, Poor Neal becomes very hungry. In return for Neal's help, Ray makes a great dinner for Neal. When it is time for dinner, Ray arranges all the dishes he makes in a single line (actually this line is very long ... <tex2html_verbatim_mark>, the dishes are represented by 1, 2, 3 ... <tex2html_verbatim_mark>). ``You make me work hard and don't pay me! You refuse to teach me Latin Dance! Now it is time for you to serve me", Neal says to himself.

Every dish has its own value represented by an integer whose absolute value is less than 1,000,000,000. Before having dinner, Neal is wondering about the total value of the dishes he will eat. So he raises many questions about the values of dishes he would have.

For each question Neal asks, he will first write down an interval [a, b] <tex2html_verbatim_mark>(inclusive) to represent all the dishes a, a + 1,..., b <tex2html_verbatim_mark>, where a <tex2html_verbatim_mark>and b <tex2html_verbatim_mark>are positive integers, and then asks Ray which sequence of consecutive dishes in the interval has the most total value. Now Ray needs your help.

Input

Output

Sample Input

3 1

1 2 3

1 1

Sample Output

Case 1:

1 1

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 typedef long long int LL;

 typedef pair<int,int> Interval;

 const int maxn=;

 LL pref_sum[maxn];

 LL sum(int a,int b){return pref_sum[b]-pref_sum[a-];}

 LL sum(Interval i){return sum(i.first,i.second);}

 Interval better(Interval a,Interval b)

 {

     LL A=sum(a),B=sum(b);

     if(A==B)

     {

         if(a<b) return a; else return b;

     }

     else if(A>B) return a;

     else if(A<B) return b;

 }

 struct IntervalTree

 {

     LL max_pref[maxn<<],max_suff[maxn<<];

     Interval max_sub[maxn<<];

     ///pushUP  build   query_suff query_pref  query

     void pushUP(int l,int r,int rt)

     {

         ///sub

         int lc=rt<<;

         int rc=rt<<|;

         max_sub[rt]=better(max_sub[lc],max_sub[rc]);

         max_sub[rt]=better(max_sub[rt],make_pair(max_suff[lc],max_pref[rc]));

         ///prex

         LL v1=sum(l,max_pref[lc]);

         LL v2=sum(l,max_pref[rc]);

         if(v1==v2)

             max_pref[rt]=max_pref[lc];

         else

             max_pref[rt]=v1>v2?max_pref[lc]:max_pref[rc];

         ///suffx

         v1=sum(max_suff[rc],r);

         v2=sum(max_suff[lc],r);

         if(v1==v2)

             max_suff[rt]=max_suff[lc];

         else

             max_suff[rt]=v1>v2?max_suff[rc]:max_suff[lc];

     }

     void build(int l,int r,int rt)

     {

         if(l==r)

         {

             max_suff[rt]=max_pref[rt]=l;

             max_sub[rt]=make_pair(l,l);

             return ;

         }

         int m=(l+r)>>;

         build(lson);

         build(rson);

         pushUP(l,r,rt);

     }

     Interval query_pref(int L,int R,int l,int r,int rt)

     {

         if(max_pref[rt]<=R) return make_pair(L,max_pref[rt]);

         int m=(l+r)>>;

         if(m>=R) return query_pref(L,R,lson);

         Interval i=query_pref(L,R,rson);

         i.first=L;

         return better(i,make_pair(L,max_pref[rt<<]));

     }

     Interval query_suff(int L,int R,int l,int r,int rt)

     {

         if(max_suff[rt]>=L) return make_pair(max_suff[rt],R);

         int m=(l+r)>>;

         if(m<L) return query_suff(L,R,rson);

         Interval i=query_suff(L,R,lson);

         i.second=R;

         return better(i,make_pair(max_suff[rt<<|],R));

     }

     Interval query(int L,int R,int l,int r,int rt)

     {

         if(L<=l&&r<=R) return max_sub[rt];

         int m=(l+r)>>;

         if(R<=m) return query(L,R,lson);

         if(L>m) return query(L,R,rson);

         Interval i1=query_pref(L,R,rson);

         Interval i2=query_suff(L,R,lson);

         Interval i3=better(query(L,R,lson),query(L,R,rson));

         return better(i3,make_pair(i2.first,i1.second));

     }

 };

 IntervalTree tree;

 int main()

 {

     int cas=,a,b,n,m;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         pref_sum[]=;

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a);

             pref_sum[i]=pref_sum[i-]+a;

         }

         tree.build(,n,);

         printf("Case %d:\n",cas++);

         while(m--)

         {

             scanf("%d%d",&a,&b);

             Interval ans=tree.query(a,b,,n,);

             printf("%d %d\n",ans.first,ans.second);

         }

     }

     return ;

 }