Drazil 是一只猴子。他住在一个圆形公园里。公园周围有n棵树。第 i 棵树与第 (i + 1) 棵树之间的距离为 di,第 n 棵树与第一棵树之间的距离为 dn。第 i 棵树的高度为 hi。
Drazil 每天从晨跑开始。晨跑包括以下步骤:
- Drazil 选择两棵不同的树
- 他从爬上第一棵树开始
- 然后他爬下第一棵树,绕着公园跑(沿着两个可能的方向之一)到第二棵树,然后爬上它
- 然后他终于爬下了第二棵树。
但是总是有孩子们在一些连续的树周围玩耍。德拉兹不能忍受孩子,所以他不能选择靠近孩子的树。他甚至无法靠近那些树。
如果 Drazil 选择的两棵树是第 x 棵树和第 y 棵树,我们可以将他晨跑消耗的能量估计为 2(hx + hy) + dist(x, y)。由于连接 x 和 y 的两条弧线之一上都有子节点,因此树 x 和 y 之间的距离 dist(x, y) 是唯一定义的。
现在,您知道在第 i 天,孩子们在第 ai 棵树和第 bi 棵树之间玩耍。更正式地说,如果 ai ≤ bi,孩子们会在树周围玩索引范围为 [ai, bi] 的树,否则他们会在树周围玩索引为 $${ \left[ a _ { i }, n \right] } \cup { \left[ 1, b _ { i } \right] }$$ 的树。
请帮助 Drazil 确定他应该选择哪两棵树来消耗最多的能量(因为他想成为健康且看起来很酷的猴子)并报告每天的能量消耗量。
输入
第一行包含两个整数n和m(3≤n≤105,1≤m≤105),分别表示树的数量和天数。
第二行包含 n 个整数 d1, d2, ..., dn (1 ≤ di ≤ 109),连续树之间的距离。
第三行包含 n 个整数 h1, h2, ..., hn (1 ≤ hi ≤ 109),即树的高度。
以下 m 行中的每一行都包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n) 描述每个新的一天。德拉齐尔总是可以选择至少两棵不受儿童影响的不同树木。
输出
每天在单独的行中打印答案。
示例
输入 #1
5 3 2 2 2 2 2 3 5 2 1 4 1 3 2 2 4 5
输出 #1
12 16 18
输入 #2
3 3 5 1 4 5 1 4 3 3 2 2 1 1
输出 #2
17 22 11