P8572 [JRKSJ R6] Eltaw

 As you walk alone under the moon, you cannot help but think of an easy problem. (The background image is from a Phigros illustration. If there is any infringement, please inform the problem setter.)

You are given $k$ sequences $a_{1\dots k,1\dots n}$, each of length $n$. There are $q$ queries. Each query gives an interval $[l,r]$, and you need to compute $\displaystyle\max_{i=1}^k\sum_{j=l}^ra_{i,j}$, i.e., the maximum interval sum over $[l,r]$ among all sequences.

The first line contains three integers $n,k,q$.\ Then follow $k$ lines, each containing $n$ integers $a_{i,j}$.\ Then follow $q$ lines, each containing two integers $l,r$ representing one query.

Output $q$ lines, each representing the answer to one query.

Idea: cyffff, Solution: cyffff, Code: cyffff, Data: cyffff **Eltaw - Fl00t (IN Lv 14.8)** **The input and output files of this problem are large. Please use appropriate input/output methods.** ### Constraints This problem uses bundled testdata. | $\text{Subtask}$ | $n\le$ | Special Constraints | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5\times10^3$ | $k\le 100$ | $20$ | | $2$ | $5\times10^5$ | Guaranteed $l=1$ | $30$ | | $3$ | $5\times10^5$ | None | $50$ | For $100\%$ of the data: $1\le n,k,q\le5\times 10^5$, $n\times k\le 5\times10^5$, $1\le l\le r\le n$, $0\le a_{i,j}\le 10^9$. ### Data Update Log $\text{Upd 2022.10.05}$: Updated two sets of testdata, which invalidated two incorrect solutions with wrong time complexity. Thanks to @[Binary Apple Tree](https://www.luogu.com.cn/user/270854) for pointing it out. $\text{Upd 2022.10.08}$: Updated one set of testdata, which invalidated an incorrect memoization-based solution. Thanks to @[SweetOrangeOvO](https://www.luogu.com.cn/user/236862) for pointing it out. If you can pass all current test points, then the complexity of your code is very likely correct. If you still think your complexity is wrong, please contact the problem setter. Translated by ChatGPT 5