VegiCat befindet sich auf einer Minenräummission. Auf einer Zahlengeraden befinden sich $n$ Minen. Mine $i$ liegt bei der ganzzahligen Koordinate $a_i$. Die Minen sind in der Reihenfolge ihrer Koordinaten nummeriert, sodass $a_1 \le a_2 \le \cdots \le a_n$ gilt. Minenkoordinaten können sich wiederholen.

VegiCat testet jede Mine einmal, in der Reihenfolge $1, 2, \ldots, n$. Für Mine $i$ wählt er eine ganzzahlige Koordinate $b_i$ als Testposition, die auch negativ oder null sein darf. Der Fehler dieses Tests beträgt $|a_i - b_i|$.

Für jedes $2 \le i \le n$ ist eine ganze Zahl $l_i$ gegeben, die den minimal erforderlichen Abstand zwischen den Testpositionen für die Minen $i - 1$ und $i$ angibt. Diese Positionen müssen Folgendes erfüllen:

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

Hilf VegiCat, den größten Testfehler zu minimieren; das heißt, finde

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

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$ ($2 \le n \le 10^5$), die Anzahl der Minen.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), wobei $a_i$ die Koordinate von Mine $i$ ist. Es wird garantiert, dass $a_1 \le a_2 \le \cdots \le a_n$ gilt.

Die dritte Zeile enthält $n - 1$ ganze Zahlen $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), wobei $l_i$ der Mindestabstand zwischen den Testpositionen für die Minen $i - 1$ und $i$ ist.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine ganze Zahl aus — den minimal möglichen Wert des größten Testfehlers.

Beispiele

Eingabe 1

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

Ausgabe 1

1
6

Hinweis

Im ersten Testfall ergibt die Wahl von $b_1 = 1$ und $b_2 = 2$ einen maximalen Fehler von $1$. Ein Fehler von $0$ würde $b_1 = b_2 = 1$ erfordern, was die Abstandsanforderung verletzt.

Im zweiten Testfall ist eine optimale Wahl $b = [-4, 7, 15, 10, 8, 22, 13]$. Alle erforderlichen Abstände sind eingehalten, und der maximale Fehler beträgt $6$.