VegiCat est en mission de déminage. Il y a $n$ mines sur une droite graduée. La mine $i$ se trouve à la coordonnée entière $a_i$. Les mines sont numérotées dans l'ordre de leurs coordonnées, de sorte que $a_1 \le a_2 \le \cdots \le a_n$. Les coordonnées des mines peuvent se répéter.

VegiCat teste chaque mine une fois, dans l'ordre $1, 2, \ldots, n$. Pour la mine $i$, il choisit une coordonnée entière $b_i$ comme position de test, qui peut être négative ou nulle. L'erreur de ce test est $|a_i - b_i|$.

Pour chaque $2 \le i \le n$, un entier $l_i$ est donné, spécifiant la distance minimale requise entre les positions de test pour les mines $i - 1$ et $i$. Ces positions doivent satisfaire

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

Aidez VegiCat à minimiser la plus grande erreur de test ; autrement dit, trouvez

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

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier $n$ ($2 \le n \le 10^5$), le nombre de mines.

La deuxième ligne contient $n$ entiers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), où $a_i$ est la coordonnée de la mine $i$. Il est garanti que $a_1 \le a_2 \le \cdots \le a_n$.

La troisième ligne contient $n - 1$ entiers $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), où $l_i$ est la distance minimale entre les positions de test pour les mines $i - 1$ et $i$.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez un entier — la valeur minimale possible de la plus grande erreur de test.

Exemples

Entrée 1

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

Sortie 1

1
6

Remarque

Dans le premier cas de test, choisir $b_1 = 1$ et $b_2 = 2$ donne une erreur maximale de $1$. Une erreur de $0$ nécessiterait $b_1 = b_2 = 1$, ce qui enfreint la contrainte de distance.

Dans le second cas de test, un choix optimal est $b = [-4, 7, 15, 10, 8, 22, 13]$. Toutes les distances requises sont respectées, et l'erreur maximale est $6$.