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 ... , the dishes are represented by 1, 2, 3 ... ). ``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] (inclusive) to represent all the dishes a, a + 1,..., b , where a and b 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 

The input file contains multiple test cases. For each test case, there are two integers n and m in the first line (n, m < 500000) . n is the number of dishes and m is the number of questions Neal asks.

Then n numbers come in the second line, which are the values of the dishes from left to right. Next m lines are the questions and each line contains two numbers a , b as described above. Proceed to the end of the input file.

Output 

For each test case, output m lines. Each line contains two numbers, indicating the beginning position and end position of the sequence. If there are multiple solutions, output the one with the smallest beginning position. If there are still multiple solutions then, just output the one with the smallest end position. Please output the result as in the Sample Output.

Sample Input 

3 1 
1 2 3 
1 1

Sample Output 

Case 1: 
1 1

線段樹的區間是[i,j]，節點編號k，左右子樹lc, rc，我們將儲存
1. 由左至右 : 從i 開始，但小於 j 的 最大連續和 (lmax)
2. 由右至左 : 從j 開始，但大於 i 的 最大連續和 (rmax)
3. 中間 : 此區間存在的最大連續和 (midmax)
4. 區間總和 (sum)
得到
1. k.lmax = max(lc.lmax, lc.sum + rc.lmax);
2. k.rmax =  max(rc.rmax, rc.sum + lc.rmax);
3. k.midmax = max(lc.midmax, rc.midmax, lc.rmax + rc.lmax);
4. k.sum = lc.sum + rc.sum;

以前是這麼想的，不過後來發現只要維護 最大前綴 與 最大後綴，以及 記錄當前區間[l, r] 的區間答案，
在答案計算上，只保留答案的區間索引。

因此對於一個線段樹節點區間 [l, r] 畫分成兩個左右區間 [l, m]、[m+1, r]

維護區間答案：
得之答案會從左區間 [l, m] 又或者從右區間 [m+1, r] 又或者橫跨中間線。
前兩個是由節點記錄中取(不做說明)，最後一個是需要計算的，
橫跨中間線：會是左區間 [l, m] 的最大後綴 - 右區間 [m+1, r] 的最大前綴

維護區間最大前綴：
當不跨越中間線時，左區間的最大前綴也許是這區間的最大前綴，又或者跨越中心線－
整個左區間-右區間的最大前綴，這兩個取其一。

維護區間最大後綴：
當不跨越中間線時，右區間的最大後綴也許是這區間的最大後綴，又或者跨越中心線－
整個右區間-左區間的最大後綴，這兩個取其一。

詢問的處理部分：
由於會得到左右兩個區間的子答案，同時也要維護區間的最大前綴與最大後綴。
而這兩個最大前綴與最大後綴必須在詢問區間內，因此當區間合併時，利用左右兩邊的最大前綴與後綴，
兜成一個跨越中心線的子答案。

#include <stdio.h>
#include <algorithm>
using namespace std;
#define oo 1LL<<60
struct node {
    int l, r;
    long long v;
    bool operator<(const node &a) const {
        if(v != a.v)    return v < a.v;
        if(l != a.l)    return l > a.l;
        return r > a.r;
    }
    node(int a, int b, long long c):
        l(a), r(b), v(c) {}
    node():
        l(0), r(0), v(0) {}
};
struct STnode {
    int lmax, rmax; // by index record
    node ret;
};
STnode ST[1048576];
long long A[1048576], SUM[1048576];
void build(int k, int l, int r) {
    if(l == r) {
        ST[k].lmax = ST[k].rmax = l;
        ST[k].ret = node(l, r, A[l]);
        return ;
    }
    if(l > r) {
        ST[k].ret = node(-1, -1, -oo);
        return ;
    }
    int m = (l+r)/2;
    build(k<<1, l, m);
    build(k<<1|1, m+1, r);

    ST[k].ret = node(l, r, -oo);
    ST[k].ret = max(ST[k].ret, ST[k<<1].ret);
    ST[k].ret = max(ST[k].ret, ST[k<<1|1].ret);
    ST[k].ret = max(ST[k].ret,
            node(ST[k<<1].rmax, ST[k<<1|1].lmax, SUM[ST[k<<1|1].lmax]-SUM[ST[k<<1].rmax-1]));

    ST[k].lmax = ST[k<<1].lmax;
    if(SUM[ST[k].lmax]-SUM[l-1] < SUM[ST[k<<1|1].lmax]-SUM[l-1])
        ST[k].lmax = ST[k<<1|1].lmax;

    ST[k].rmax = ST[k<<1|1].rmax;
    if(SUM[r]-SUM[ST[k].rmax-1] <= SUM[r]-SUM[ST[k<<1].rmax-1])
        ST[k].rmax = ST[k<<1].rmax;
}
node query(int k, int l, int r, int ql, int qr, int &pl, int &pr) {
    if(ql <= l && r <= qr) {
        pl = ST[k].lmax;
        pr = ST[k].rmax;
        return ST[k].ret;
    }
    int m = (l+r)/2;
    node ans = node(l, r, -oo);
    int lpre, lsuf, rpre, rsuf;
    pl = -1, pr = -1;
    if(ql <= m && qr > m) {
        ans = max(ans, query(k<<1, l, m, ql, qr, lpre, lsuf));
        ans = max(ans, query(k<<1|1, m+1, r, ql, qr, rpre, rsuf));
        if(lsuf != -1 && rpre != -1)
            ans = max(ans, node(lsuf, rpre, SUM[rpre]-SUM[lsuf-1]));
        if(ql <= l) {
            pl = lpre;
            if(SUM[lpre]-SUM[l-1] < SUM[rpre]-SUM[l-1])
                pl = rpre;
        }
        if(qr >= r) {
            pr = rsuf;
            if(SUM[r]-SUM[rsuf-1] <= SUM[r]-SUM[lsuf-1])
                pr = lsuf;
        }
    } else if(qr <= m) {
        ans = max(ans, query(k<<1, l, m, ql, qr, lpre, lsuf));
        if(ql <= l) pl = lpre;
    } else if(ql > m){
        ans = max(ans, query(k<<1|1, m+1, r, ql, qr, rpre, rsuf));
        if(qr >= r) pr = rsuf;
    }
    return ans;
}
int main() {
    int n, q, l, r, cases = 0;
    int i, j;
    while(scanf("%d %d", &n, &q) == 2) {
        for(i = 1; i <= n; i++) {
            scanf("%lld", &A[i]);
            SUM[i] = SUM[i-1] + A[i];
        }
        build(1, 1, n);
        printf("Case %d:\n", ++cases);
        int tl, tr;
        while(q--) {
            scanf("%d %d", &l, &r);
            node ans = query(1, 1, n, l, r, tl, tr);
            printf("%d %d\n", ans.l, ans.r);
        }
    }
    return 0;
}