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$.