CF515E.Drazil and Park

Drazil is a monkey. He lives in a circular park. There are n trees around the park. The distance between the i-th tree and (i + 1)-st trees is d__i, the distance between the n-th tree and the first tree is d__n. The height of the i-th tree is h__i.

Drazil starts each day with the morning run. The morning run consists of the following steps:

• Drazil chooses two different trees
• He starts with climbing up the first tree
• Then he climbs down the first tree, runs around the park (in one of two possible directions) to the second tree, and climbs on it
• Then he finally climbs down the second tree.

But there are always children playing around some consecutive trees. Drazil can't stand children, so he can't choose the trees close to children. He even can't stay close to those trees.

If the two trees Drazil chooses are x-th and y-th, we can estimate the energy the morning run takes to him as 2(h__x + h__y) + dist(x, y). Since there are children on exactly one of two arcs connecting x and y, the distance dist(x, y) between trees x and y is uniquely defined.

Now, you know that on the i-th day children play between a__i-th tree and b__i-th tree. More formally, if a__i ≤ b__i, children play around the trees with indices from range [a__i, b__i], otherwise they play around the trees with indices from .

Please help Drazil to determine which two trees he should choose in order to consume the most energy (since he wants to become fit and cool-looking monkey) and report the resulting amount of energy for each day.

达兹尔是一只猴子，生活在一座环形公园中。公园周围共有 $n$ 棵树。第 $i$ 棵树与第 $(i+1)$ 棵树之间的距离为 $d_i$，第 $n$ 棵树与第 $1$ 棵树之间的距离为 $d_n$。第 $i$ 棵树的高度为 $h_i$。

达兹尔每天清晨都会进行晨跑，晨跑过程如下：

• 达兹尔选择两棵不同的树；
• 他先爬上第一棵树；
• 然后从第一棵树下来，沿公园（顺时针或逆时针两个方向之一）跑到第二棵树，并爬上它；
• 最后，他从第二棵树上下来。

但总有一些孩子在若干连续编号的树周围玩耍。达兹尔讨厌孩子，因此他不能选择靠近这些树的树——甚至不能在这些树附近停留。

若达兹尔选择的是第 $x$ 棵树和第 $y$ 棵树，则此次晨跑所消耗的能量可估算为

$$2(h_x + h_y) + \text{dist}(x, y)$$

由于恰好有一段连接 $x$ 与 $y$ 的圆弧上有孩子玩耍，因此树 $x$ 与树 $y$ 之间的距离 $\text{dist}(x, y)$ 是唯一确定的。

现在已知：在第 $i$ 天，孩子们在第 $a_i$ 棵树与第 $b_i$ 棵树之间玩耍。更准确地说，若 $a_i \leq b_i$，则孩子们在编号属于区间 $[a_i,\, b_i]$ 的树周围玩耍；否则，孩子们在编号属于 的树周围玩耍。

请帮助达兹尔确定：每天他应选择哪两棵树，才能使晨跑消耗的能量最多（因为他想成为一只健壮又帅气的猴子），并报告每天所能达到的最大能量值。

The first line contains two integer n and m (3 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting number of trees and number of days, respectively.

The second line contains n integers _d_1, _d_2, ..., d__n (1 ≤ d__i ≤ 109), the distances between consecutive trees.

The third line contains n integers _h_1, _h_2, ..., h__n (1 ≤ h__i ≤ 109), the heights of trees.

Each of following m lines contains two integers a__i and b__i (1 ≤ a__i, b__i ≤ n) describing each new day. There are always at least two different trees Drazil can choose that are not affected by children.

第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 10^5$，$1 \leq m \leq 10^5$），分别表示树的数量和天数。

第二行包含 $n$ 个整数 $d_1,\,d_2,\,...,\,d_n$（$1 \leq d_i \leq 10^9$），表示相邻两棵树之间的距离。

第三行包含 $n$ 个整数 $h_1,\,h_2,\,...,\,h_n$（$1 \leq h_i \leq 10^9$），表示每棵树的高度。

接下来的 $m$ 行中，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i,\,b_i \leq n$），描述每一天的新情况。总存在至少两棵不同的树，Drazil 可以从中选择，且这些树未受儿童影响。

For each day print the answer in a separate line.

每天的答案分别打印在单独的一行中。