该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

摩耶，壹。

找到谁人的视线落在她身上的地方，她被带到另一个世界的地方。

如果有人哪天发现了这本日志：它存在的意义便是你。我会告诉你一切我所发现的事。

摩耶，捌。

她回想不起自己过去的模样。找到并珍藏一首反映她过去的歌曲。

我已死去，这毋庸置疑。我知道我的感受，我明白这都是我的错。

摩耶，肆拾贰。

找到将她带到另一个世界的人。

现在我可以肯定：这个地方的时间流逝的速度本身，以及和Arcaea世界时间流逝的关系均似乎有些诡异。这听起来很像时间膨胀。

Maya，壹零捌。最后的字句，最后的署名。谢谢你回应我的呼唤。

题目描述

给你 $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

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

数据规模

对于 $100\%$ 的数据:

$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$。

后记

摩耶劝慰维塔停止哭泣，维塔却斥责其言语是部队里愚蠢的陈词滥调。在逐渐稀薄的对话中，痛苦的低语与记忆的闪光交织——“我仍记得”、“我仍厌恶哭泣的自己”。

光芒自摩耶躯体的裂隙中淌出，水晶花瓣随之绽放。当两位少女闭上双眼，她们的记忆开始了深刻的交融。维塔，这位诞生于星际航行时代的天才，因轻信谗言开启了致命航道，走向了生命的终结。她的记忆被奇异造物Arcaea夺取，却无法被彻底驱散，最终这些携带着相同痛苦的情感，在另一副玻璃躯壳中苏醒为摩耶。

当周遭世界开始急促倾覆、崩塌撕裂，维塔奋力向前，紧紧抓住摩耶的肩膀，在毁灭的光潮中将另一半拥入怀中。她紧握着，目光牢牢锁在摩耶的微笑上，直至对方的身体碎裂崩解，星辰的嘶鸣被宇宙的寂静吞没，手中空无一物。

在另一个世界，殿堂重归沉寂。维塔睁开了双眼，脑海与心间充盈着新旧交织的回忆。她回到了Arcaea，成为这扭曲世界的寂静中心。她翻开书页，读着最后的感谢，双唇紧抿，最终以沉寂作为回应。合上书，她转身面对同伴，所有的记忆与告别，都已沉淀于心。

//谢谢你回应我的呼唤。//