题目背景

你在月下独自行走，不禁想起了一道简单题。

（题目背景图片来自 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$ 行表示每个询问的答案。

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

提示

Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff

Eltaw - Fl00t (Insane14.4)

本题输入输出文件较大，请使用恰当的输入输出方式。

数据规模

本题采用捆绑测试。

对于 $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}$：更新了两组数据，分别卡掉了两种时间复杂度错误的做法。感谢 @二叉苹果树 指出。

$\text{upd 2022.10.08}$：更新了一组数据，卡掉了记忆化不正确的做法。感谢

如果你能通过现在的所有测试点，说明你的代码复杂度极可能是正确的。如果你仍认为你的复杂度是错误的，请联系出题人。