J. Харухи и путешествие на круге
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Харухи Судзумии было скучно, поэтому она решила принять участие в соревновании по спортивному программированию. Соревнование состоит из одной задачи:

Дан круг, состоящий из $$$2n$$$ секторов, пронумерованных от $$$1$$$ до $$$2n$$$ по часовой стрелке, начиная с некоторой точки. За сектором $$$1$$$ следует сектор $$$2$$$, за сектором $$$2$$$ — сектор $$$3$$$ и так далее, а за сектором $$$2n$$$ следует сектор $$$1$$$. Между любыми соседними$$$^{[1]}$$$ секторами можно передвигаться за $$$1$$$ единицу времени. Помимо этого, из сектора $$$i$$$ в сектор $$$j$$$, расположенный диаметрально противоположно$$$^{[2]}$$$ сектору $$$i$$$, можно сдвинуться за $$$a_i$$$ единиц времени. Заметим, что в данном случае время передвижения зависит от направления движения: $$$a_i$$$ из $$$i$$$ в $$$j$$$ и $$$a_j$$$ из $$$j$$$ в $$$i$$$.

Необходимо ответить на $$$q$$$ запросов. Каждый запрос задается двумя номерами секторов $$$u_i$$$ и $$$v_i$$$. Для каждого запроса необходимо найти минимальное количество времени, которое потребуется, чтобы попасть в сектор $$$v_i$$$, если начинать в секторе $$$u_i$$$.

$$$^{[1]}$$$ Два сектора $$$i$$$ и $$$j$$$ называются соседними, если $$$i$$$ следует сразу после $$$j$$$ или наоборот.

$$$^{[2]}$$$ Два сектора $$$i$$$ и $$$j$$$ называются диаметрально противоположными, если $$$|i - j| = n$$$.

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

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

В первой строке дано два числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 5 \cdot 10^4, 1 \leq q \leq 10^5$$$).

Во второй строке дано $$$2n$$$ чисел $$$a_1, a_2, a_3, \dots, a_{2n}$$$ ($$$1 \leq a_i \leq 10^5$$$).

В следующих $$$q$$$ строках описаны все запросы.

В $$$i$$$-й строке содержатся два числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq 2n$$$) — описание очередного запроса.

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

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

Для каждого набора входных данных выведите $$$q$$$ строк: число в $$$i$$$-й строке должно быть равно минимальному количеству времени для того, чтобы попасть из сектора $$$u_i$$$ в сектор $$$v_i$$$.

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