VegiCat bierze udział w misji rozminowywania. Na osi liczbowej znajduje się $n$ min. Mina $i$ leży w punkcie o współrzędnej całkowitej $a_i$. Miny są ponumerowane w kolejności swoich współrzędnych, więc $a_1 \le a_2 \le \cdots \le a_n$. Współrzędne min mogą się powtarzać.

VegiCat testuje każdą minę dokładnie raz, w kolejności $1, 2, \ldots, n$. Dla miny $i$ wybiera współrzędną całkowitą $b_i$ jako pozycję testową, która może być ujemna lub równa zero. Błąd tego testu wynosi $|a_i - b_i|$.

Dla każdego $2 \le i \le n$ dana jest liczba całkowita $l_i$, określająca minimalną wymaganą odległość pomiędzy pozycjami testowymi dla min $i - 1$ oraz $i$. Pozycje te muszą spełniać warunek

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

Pomóż VegiCatowi zminimalizować największy błąd testu, to znaczy wyznacz

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

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Poniżej znajdują się opisy poszczególnych przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera liczbę całkowitą $n$ ($2 \le n \le 10^5$), oznaczającą liczbę min.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), gdzie $a_i$ jest współrzędną miny $i$. Zagwarantowane jest, że $a_1 \le a_2 \le \cdots \le a_n$.

Trzeci wiersz zawiera $n - 1$ liczb całkowitych $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), gdzie $l_i$ jest minimalną odległością pomiędzy pozycjami testowymi dla min $i - 1$ oraz $i$.

Zagwarantowane jest, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — minimalną możliwą wartość największego błędu testu.

Przykład

Wejście 1

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

Wyjście 1

1
6

Uwagi

W pierwszym przypadku testowym wybór $b_1 = 1$ oraz $b_2 = 2$ daje maksymalny błąd równy $1$. Błąd równy $0$ wymagałby $b_1 = b_2 = 1$, co narusza wymóg dotyczący odległości.

W drugim przypadku testowym jednym z optymalnych wyborów jest $b = [-4, 7, 15, 10, 8, 22, 13]$. Wszystkie wymagane odległości są zachowane, a maksymalny błąd wynosi $6$.