VegiCat está en una misión de desminado. Hay $n$ minas en una recta numérica. La mina $i$ está en la coordenada entera $a_i$. Las minas están numeradas en el orden de sus coordenadas, por lo que $a_1 \le a_2 \le \cdots \le a_n$. Las coordenadas de las minas pueden repetirse.

VegiCat prueba cada mina una vez, en el orden $1, 2, \ldots, n$. Para la mina $i$, elige una coordenada entera $b_i$ como ubicación de prueba, la cual puede ser negativa o cero. El error de esta prueba es $|a_i - b_i|$.

Para cada $2 \le i \le n$, se da un entero $l_i$, que especifica la distancia mínima requerida entre las ubicaciones de prueba para las minas $i - 1$ e $i$. Estas ubicaciones deben satisfacer

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

Ayuda a VegiCat a minimizar el mayor error de prueba; es decir, halla

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

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($2 \le n \le 10^5$), el número de minas.

La segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), donde $a_i$ es la coordenada de la mina $i$. Se garantiza que $a_1 \le a_2 \le \cdots \le a_n$.

La tercera línea contiene $n - 1$ enteros $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), donde $l_i$ es la distancia mínima entre las ubicaciones de prueba para las minas $i - 1$ e $i$.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime un entero: el mínimo valor posible del mayor error de prueba.

Ejemplos

Entrada 1

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

Salida 1

1
6

Nota

En el primer caso de prueba, elegir $b_1 = 1$ y $b_2 = 2$ da un error máximo de $1$. Un error de $0$ requeriría $b_1 = b_2 = 1$, lo cual incumple el requisito de distancia.

En el segundo caso de prueba, una elección óptima es $b = [-4, 7, 15, 10, 8, 22, 13]$. Se cumplen todas las distancias requeridas y el error máximo es $6$.