J. Две железные дороги
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии $$$n$$$ городов, соединенных двумя железными дорогами — Основной и Дополнительной. В каждом городе есть две железнодорожные станции — одна подсоединена к Основной железной дороге (эта станция называется Основной), а вторая подсоединена к Дополнительной железной дороге.

Структура железных дорог одинакова. Основная дорога состоит из $$$n-1$$$ сегментов; $$$i$$$-й сегмент соединяет Основную станцию города $$$i$$$ с Основной станцией города $$$i+1$$$. Аналогично, Дополнительная дорога состоит из $$$n-1$$$ сегментов; $$$i$$$-й сегмент соединяет Дополнительную станцию города $$$i$$$ с Дополнительной станцией города $$$i+1$$$.

Эти железные дороги используются, чтобы перевозить различные товары и грузы между городами. Например, Министерство энергетики интересует, насколько эффективно можно использовать эти дороги для перевозки угля.

Министерство, проведя измерения, установило, сколько угля в день можно перевозить между станциями:

  • для каждого $$$i \in [1, n-1]$$$, можно перевозить не более $$$a_i$$$ тонн угля в день с Основной станции города $$$i$$$ на Основную станцию города $$$i+1$$$ (только в этом направлении);
  • для каждого $$$i \in [1, n-1]$$$, можно перевозить не более $$$b_i$$$ тонн угля в день с Дополнительной станции города $$$i$$$ на Дополнительную станцию города $$$i+1$$$ (только в этом направлении);
  • для каждого $$$i \in [1, n]$$$, можно перевозить не более $$$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$$$-й запрос, т. е. оно должно быть равно максимальному количеству тонн угля, которое можно перевозить в день с Основной станции $$$l_i$$$ на Основную станцию $$$r_i$$$.

Пример
Входные данные
5
3 4 7 4
8 5 3 5
10 5 3 4 10
4
1 4
1 2
3 4
2 4
Выходные данные
9 8 10 9