"Ray, Pass me the dishes!"
题意翻译
### 题目描述
给出一个长度为 $n$ 的整数序列 $D$，你的任务是对 $m$ 个询问作出回答。对于询问 $(a,b)$，需要找到两个下标 $x$ 和 $y$，使得 $a\le x\le y\le b$，并且 $D_x+D_{x+1}+...+D_y$ 尽量大。如果有多组满足条件的 $x$ 和 $y$，$x$ 应尽量小。如果还有多解，$y$ 应该尽量小。
### 输入格式
输入包含多组数据。每组数据第一行为两个整数 $n$ 和$m$（$1\le n,m\le 5\times10^5$），即整数序列长度和查询的个数。第二行包含 $n$ 个整数，依次为 $D_1,D_2,...,D_n$ 的值。这些整数的绝对值不超过 $10^9$。以下 $m$ 行每行为一个查询，包含两个整数 $a$ 和 $b$。输入结束标志为文件结束符 `EOF`。
### 输出格式
对于每组数据，输出数据编号`Case xx:` ，然后为每个查询输出一行，包含两个整数 $x$ 和 $y$。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=447&page=show_problem&problem=4146
[PDF](https://uva.onlinejudge.org/external/14/p1400.pdf)