Berland有$$$n$$$个城市,它们由两条铁路连接——主铁路和辅助铁路。每个城市有两个火车站,一个连接主干铁路(称为主站),另一个连接辅助铁路。
铁路的结构相同。主要铁路由 $$$n-1$$$ 铁路段组成;第 $$$i$$$ 铁路段将 $$$i$$$ 城市的主站与 $$$i+1$$$ 城市的主站连接起来。同样,辅助铁路由 $$$n-1$$$ 铁路段组成;第$$$i$$$铁路段连接城市$$$i$$$辅助站与城市$$$i+1$$$辅助站。
这些铁路用于将不同的货物和资源从一个城市转移到另一个城市。能源部特别有兴趣利用这些铁路来运输煤炭。
该部估计了铁路的以下能力:
- 对于[1, n-1]$$$中的每$$$i,每天最多可以将$$$a_i$$$吨煤炭从主站$$$i$$$转移到主站$$$i+1$$$(仅在这个方向);
- 对于[1, n-1]$$$中的每$$$i,每天最多可以将$$$b_i$$$吨煤炭从辅助站$$$i$$$转移到辅助站$$$i+1$$$(仅在这个方向);
- 对于[1, n]$$$中的每$$$i,每天最多可以将$$$c_i$$$吨煤炭从主站$$$i$$$转移到辅助站$$$i$$$,或者反向转移。
为了分析整个铁路网的容量,该部需要一个能够处理和回答以下格式查询的软件:
- 计算每天可以从主站 $$$l_i$$$ 转移到主站 $$$r_i$$$ 的最大煤炭吨数。
您的任务是实现该软件。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 城市数量。
第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$)。
第三行包含 $$$n-1$$$ 整数 $$$b_1, b_2, \dots, b_{n-1}$$$ ($$$1 \le b_i \le 10^9$$$)。
第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_{n}$$$ ($$$1 \le c_i \le 10^9$$$)。
第五行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询数。
接下来是 $$$q$$$ 行,第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — 第 $$$i$$$ 查询的参数。
输出
打印 $$$q$$$ 整数,其中第 $$$i$$$ 个整数应该是第 $$$i$$$ 个查询的答案,i。 e.每天可以从主站 $$$l_i$$$ 转移到主站 $$$r_i$$$ 的最大煤炭吨数。
示例
输入 #1
5 3 4 7 4 8 5 3 5 10 5 3 4 10 4 1 4 1 2 3 4 2 4
输出 #1
9 8 10 9