C. Заменяй и суммируй
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня у KQ экзамен в академии Граиля. Строгий учитель дал задачу, с которой KQ не смог справиться. Ему дали два массива $$$a$$$ и $$$b$$$ длины $$$n$$$. KQ разрешается выполнять следующие операции на массивах:

  • Выбрать индекс $$$i$$$ ($$$1\le i\lt n$$$) и заменить $$$a_i$$$ на $$$a_{i+1}$$$.
  • Выбрать индекс $$$i$$$ ($$$1\le i\le n$$$) и заменить $$$a_i$$$ на $$$b_i$$$.
Теперь ему дали $$$q$$$ запросов. Каждый запрос описывается двумя числами $$$l$$$ и $$$r$$$. Его задача — для каждого запроса найти максимальное значение суммы $$$(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$$$, если он может выполнить любое количество операций с любыми элементами массива. Поскольку он недостаточно умен для этого, он просит вас о помощи.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$q$$$ $$$(1\le n, q\le 2 \cdot 10^5)$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2,...,a_n$$$ $$$(1\le a_i\le 10^4)$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2,...,b_n$$$ $$$(1\le b_i\le 10^4)$$$.

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$r$$$ $$$(1\le l\le r\le n)$$$.

Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ чисел через пробел — максимальные значения сумм $$$(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$$$.

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

Рассмотрим первый набор входных данных. Замените $$$a_3$$$ на $$$b_3$$$, $$$a = [3, 2, 3]$$$. Замените $$$a_2$$$ на $$$a_3$$$, $$$a = [3, 3, 3]$$$. Сумма $$$a_1 + a_2 + a_3 = 9$$$.