VegiCat er på et mineryddingsoppdrag. Det er $n$ miner på en tallinje. Mine $i$ ligger på heltallskoordinaten $a_i$. Minene er nummerert i rekkefølge etter koordinatene sine, slik at $a_1 \le a_2 \le \cdots \le a_n$. Minekoordinater kan gjentas.

VegiCat tester hver mine én gang, i rekkefølgen $1, 2, \ldots, n$. For mine $i$ velger han en heltallskoordinat $b_i$ som testposisjon, som kan være negativ eller null. Feilen ved denne testen er $|a_i - b_i|$.

For hver $2 \le i \le n$ er det gitt et heltall $l_i$, som angir den minste påkrevde avstanden mellom testposisjonene for minene $i - 1$ og $i$. Disse posisjonene må tilfredsstille

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

Hjelp VegiCat med å minimere den største testfeilen; det vil si, finn

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

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder et heltall $n$ ($2 \le n \le 10^5$), antallet miner.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), der $a_i$ er koordinaten til mine $i$. Det garanteres at $a_1 \le a_2 \le \cdots \le a_n$.

Den tredje linjen inneholder $n - 1$ heltall $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), der $l_i$ er minsteavstanden mellom testposisjonene for minene $i - 1$ og $i$.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle skal du skrive ut et heltall — den minste mulige verdien av den største testfeilen.

Eksempler

Inndata 1

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

Utdata 1

1
6

Forklaring

I det første testtilfellet gir valget $b_1 = 1$ og $b_2 = 2$ en maksimal feil på $1$. En feil på $0$ ville krevd $b_1 = b_2 = 1$, noe som bryter avstandskravet.

I det andre testtilfellet er et optimalt valg $b = [-4, 7, 15, 10, 8, 22, 13]$. Alle påkrevde avstander er oppfylt, og den maksimale feilen er $6$.