Background

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.)

Problem Description

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.

Input Format

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 Format

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

7 2 3
1 1 4 5 1 4 0
1 9 1 9 8 1 0
6 7
5 7
1 3

4
9
11

Hint

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.

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

$\text{Upd 2022.10.08}$: Updated one set of testdata, which invalidated an incorrect memoization-based solution. Thanks to

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