Елка

Мальчику Васе родители поручили украсить елку к Новому Году. Специально для этого родители подарили Васе набор волшебных елочных шаров, обладающий следующим свойством: на какую бы елку его не вешали, в нем будет ровно столько шаров, сколько веток на елке. При этом, шары нужно вешать в особой последовательности: каждый шар нужно вешать на самый конец свободной ветки, чтобы расстояние от шара до ствола елки было равно длине ветки. При этом, $j + 1$-й шар можно повесить только на ту ветку, которая находится на $h_j$ ниже той, на которую повесили $j$-ый шар.

Однако Вася не знал, что шары волшебные потому, что в них живут маленькие гномы, которые каждый Новый Год ходят друг к другу в гости пить чай. И сейчас гномам интересно, какой путь нужно преодолеть гному из шара на $i$-ой ветке, чтобы добраться до шара на $k$-ой ветке.

Ветки на елке пронумерованы снизу вверх, при этом может быть несколько веток на одной высоте, которые могут иметь разные длины.

В первой строке находится целое число $N$ --- количество веток на елке ($2 \le N \le 10^5$).

В следующей строке находится $N$ целых чисел $l_i$ --- длины веток ($1 \le l_i \le 10^9$) в порядке нумерации веток.

В следующей строке находится $N - 1$ целое число $h_j$ --- разности высот веток на которых висят шары с номерами $j$ и $j + 1$ ($|h_j| \le 10^9$). Так, $h_j > 0$ обозначает, что шар с номером $j + 1$ расположен ниже шара с номером $j$ на $|h_j|$, а $h_j < 0$ обозначает, что шар с номером $j + 1$ расположен выше шара с номером $j$ на $|h_j|$.

В следующей строке находится число $M$ --- количество вопросов гномов ($1 \le M \le 10^5$).

В следующих $M$ строках находится по два числа $i$ и $k$ --- номера веток, про которые спрашивают гномы ($1 \le i, k \le N, i \ne k$).

В выходной файл выведите $M$ чисел --- ответы на вопросы гномов. Каждое число нужно вывести на отдельной строке.

Елка из первого примера:

Шар номер $1$ находится на нижней ветке длины $4$, имеющей номер $1$,

шар номер $2$ --- на средней ветке номер $2$, длина которой равна $5$,

шар номер $3$ --- на верхней ветке номер $3$, длина которой $2$.

Расстояние между шарами на $1$-ой и $2$-ой ветке равно $4 + 1 + 5 = 10$,

расстояние между шарами на $2$-ой и $3$-ой ветке равно $5 + 1 + 2 = 8$,

расстояние между шарами на $1$-ой и $3$-ой ветке равно $4 + 2 + 2 = 8$.

Елка из второго примера:

Шар номер $1$ находится на нижней ветке длины $1005$ (слева от ствола), имеющей номер $1$,

шар номер $2$ --- на верхней ветке номер $3$, длина которой $1$ (слева от ствола),

шар номер $3$ --- на верхней ветке номер $4$, длина которой равна $1$ (справа от ствола),

шар номер $4$ --- на нижней ветке длины $1006$ (справа от ствола), имеющей номер $2$.

Расстояние между шарами на $1$-ой и $2$-ой ветке равно $1005 + 1 + 1006 = 2012$,

расстояние между шарами на $4$-ой и $1$-ой ветке равно $1 + 1005 + 1005 = 2011$,

расстояние между шарами на $3$-ой и $4$-ой ветке равно $1 + 1 = 2$.