{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/at23jtmh.png?x-oss-process=image)\n\n你在月下独自行走，不禁想起了一道简单题。\n\n（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）"},{"iden":"statement","content":"给你 $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]$ 的和的最大值。"},{"iden":"input","content":"第一行三个整数 $n,k,q$。\\\n接下来 $k$ 行，每行 $n$ 个整数 $a_{i,j}$。\\\n接下来 $q$ 行，每行两个整数 $l,r$ 表示一次询问。"},{"iden":"output","content":"输出 $q$ 行表示每个询问的答案。"},{"iden":"note","content":"Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff\n\n**Eltaw - Fl00t (IN Lv 14.8)**\n\n**本题输入输出文件较大，请使用恰当的输入输出方式。**\n### 数据规模\n本题采用捆绑测试。\n\n| $\\text{Subtask}$ | $n\\le$ | 特殊限制 | $\\text{Score}$ |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $5\\times10^3$ | $k\\le 100$ | $20$ |\n| $2$ | $5\\times10^5$ | 保证 $l=1$ | $30$ |\n| $3$ | $5\\times10^5$ | 无 | $50$ |\n\n对于 $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$。\n### 数据更新记录\n$\\text{Upd 2022.10.05}$：更新了两组数据，分别卡掉了两种时间复杂度错误的做法。感谢 @[二叉苹果树](https://www.luogu.com.cn/user/270854) 指出。\n\n$\\text{Upd 2022.10.08}$：更新了一组数据，卡掉了记忆化不正确的做法。感谢 @[SweetOrangeOvO](https://www.luogu.com.cn/user/236862) 指出。\n\n如果你能通过现在的所有测试点，说明你的代码复杂度极可能是正确的。如果你仍认为你的复杂度是错误的，请联系出题人。"}],"translated_statement":null,"sample_group":[["7 2 3\n1 1 4 5 1 4 0\n1 9 1 9 8 1 0\n6 7\n5 7\n1 3","4\n9\n11"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}