VegiCat выполняет миссию по разминированию. На числовой прямой расположены $n$ мин. Мина $i$ находится в целой координате $a_i$. Мины занумерованы в порядке неубывания их координат, поэтому $a_1 \le a_2 \le \cdots \le a_n$. Координаты мин могут совпадать.

VegiCat проверяет каждую мину по одному разу в порядке $1, 2, \ldots, n$. Для мины $i$ он выбирает целую координату $b_i$ в качестве точки проверки (она может быть отрицательной или равной нулю). Погрешность этой проверки равна $|a_i - b_i|$.

Для каждого $2 \le i \le n$ задано целое число $l_i$, определяющее минимально допустимое расстояние между точками проверки для мин $i - 1$ и $i$. Эти точки должны удовлетворять условию

$$|b_i - b_{i-1}| \ge l_i.$$

Помогите VegiCat минимизировать наибольшую погрешность проверки; иными словами, найдите

$$\min_{\substack{b_1, \ldots, b_n \in \mathbb{Z} \\ |b_i - b_{i-1}| \ge l_i \ (2 \le i \le n)}} \left(\max_{1 \le i \le n} |a_i - b_i|\right).$$

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

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

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

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), где $a_i$ — координата мины $i$. Гарантируется, что $a_1 \le a_2 \le \cdots \le a_n$.

Третья строка содержит $n - 1$ целых чисел $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), где $l_i$ — минимальное расстояние между точками проверки для мин $i - 1$ и $i$.

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

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

Для каждого набора входных данных выведите одно целое число — минимально возможное значение наибольшей погрешности проверки.

Примеры

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

2
2
1 1
1
7
2 6 12 14 14 16 19
11 8 4 2 10 9

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

1
6

Примечание

В первом наборе входных данных выбор $b_1 = 1$ и $b_2 = 2$ дает максимальную погрешность $1$. Для погрешности $0$ потребовалось бы $b_1 = b_2 = 1$, что нарушает требование на расстояние.

Во втором наборе входных данных одним из оптимальных вариантов является $b = [-4, 7, 15, 10, 8, 22, 13]$. Все требования на расстояния выполнены, а максимальная погрешность равна $6$.