VegiCat är på ett minröjningsuppdrag. Det finns $n$ minor på en tallinje. Mina $i$ ligger på heltalskoordinaten $a_i$. Minorna är numrerade i ordning efter sina koordinater, så $a_1 \le a_2 \le \cdots \le a_n$. Minkoordinater kan upprepas.

VegiCat testar varje mina en gång, i ordningen $1, 2, \ldots, n$. För mina $i$ väljer han en heltalskoordinat $b_i$ som testplats, vilken kan vara negativ eller noll. Felet vid detta test är $|a_i - b_i|$.

För varje $2 \le i \le n$ ges ett heltal $l_i$, som anger det minsta tillåtna avståndet mellan testplatserna för minorna $i - 1$ och $i$. Dessa platser måste uppfylla

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

Hjälp VegiCat att minimera det största testfelet; det vill säga, beräkna

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

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^4$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller ett heltal $n$ ($2 \le n \le 10^5$), antalet minor.

Den andra raden innehåller $n$ heltal $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), där $a_i$ är koordinaten för mina $i$. Det garanteras att $a_1 \le a_2 \le \cdots \le a_n$.

Den tredje raden innehåller $n - 1$ heltal $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), där $l_i$ är det minsta avståndet mellan testplatserna för minorna $i - 1$ och $i$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut ett heltal — det minsta möjliga värdet på det största testfelet.

Exempel

Indata 1

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

Utdata 1

1
6

Förklaring

I det första testfallet ger valet $b_1 = 1$ och $b_2 = 2$ ett maximalt fel på $1$. Ett fel på $0$ skulle kräva $b_1 = b_2 = 1$, vilket bryter mot avståndskravet.

I det andra testfallet är ett optimalt val $b = [-4, 7, 15, 10, 8, 22, 13]$. Alla begärda avstånd är uppfyllda, och det maximala felet är $6$.