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

Дан круг, состоящий из $$$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$$$.