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

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