[JRKSJ R6] Eltaw
题目背景
你在月下独自行走，不禁想起了一道简单题。
（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）
题目描述
给你 $k$ 个长为 $n$ 的序列 $a_{1\dots k,1\dots n}$，有 $q$ 次询问，每次询问给出一个区间 $[l,r]$，要求出 $\displaystyle\max_{i=1}^k\sum_{j=l}^ra_{i,j}$，即求出所有序列中区间 $[l,r]$ 的和的最大值。
输入输出格式
输入格式
第一行三个整数 $n,k,q$。\
接下来 $k$ 行，每行 $n$ 个整数 $a_{i,j}$。\
接下来 $q$ 行，每行两个整数 $l,r$ 表示一次询问。
输出格式
输出 $q$ 行表示每个询问的答案。
输入输出样例
输入样例 #1
7 2 3
1 1 4 5 1 4 0
1 9 1 9 8 1 0
6 7
5 7
1 3输出样例 #1
4
9
11说明
Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff
**Eltaw - Fl00t (Insane14.4)**
**本题输入输出文件较大，请使用恰当的输入输出方式。**
### 数据规模
本题采用捆绑测试。
| $\text{Subtask}$ | $n\le$ | 特殊限制 | $\text{Score}$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $5\times10^3$ | $k\le 100$ | $20$ |
| $2$ | $5\times10^5$ | 保证 $l=1$ | $30$ |
| $3$ | $5\times10^5$ | 无 | $50$ |
对于 $100\%$ 的数据，$1\le n,k,q\le5\times 10^5$，$1\le n\times k\le 5\times10^5$，$1\le l\le r\le n$，$0\le a_{i,j}\le 10^9$。
### 数据更新记录
$\text{upd 2022.10.05}$：更新了两组数据，分别卡掉了两种时间复杂度错误的做法。感谢 @[二叉苹果树](https://www.luogu.com.cn/user/270854) 指出。
$\text{upd 2022.10.08}$：更新了一组数据，卡掉了记忆化不正确的做法。感谢 @[SweetOrangeOvO](https://www.luogu.com.cn/user/236862) 指出。
如果你能通过现在的所有测试点，说明你的代码复杂度极可能是正确的。如果你仍认为你的复杂度是错误的，请联系出题人。