VegiCat er í jarðsprengjuleit. Það eru $n$ jarðsprengjur á talnalínu. Jarðsprengja $i$ er í heiltöluhnitinu $a_i$. Jarðsprengjurnar eru númeraðar í röð eftir hnitum sínum, þannig að $a_1 \le a_2 \le \cdots \le a_n$. Hnit jarðsprengja geta endurtekið sig.

VegiCat prófar hverja jarðsprengju einu sinni, í röðinni $1, 2, \ldots, n$. Fyrir jarðsprengju $i$ velur hann heiltöluhnit $b_i$ sem prófunarstað, sem má vera neikvætt eða núll. Skekkjan í þessari prófun er $|a_i - b_i|$.

Fyrir hvert $2 \le i \le n$ er gefin heiltala $l_i$, sem tilgreinir lágmarksfjarlægð sem krafist er á milli prófunarstaða fyrir jarðsprengjur $i - 1$ og $i$. Þessir staðir verða að uppfylla

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

Hjálpaðu VegiCat að lágmarka mestu prófunarskekkju; það er að segja, finndu

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

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir.

Fyrsta línan í hverju prófunartilviki inniheldur heiltölu $n$ ($2 \le n \le 10^5$), fjölda jarðsprengja.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), þar sem $a_i$ er hnitið á jarðsprengju $i$. Það er tryggt að $a_1 \le a_2 \le \cdots \le a_n$.

Þriðja línan inniheldur $n - 1$ heiltölur $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), þar sem $l_i$ er lágmarksfjarlægðin á milli prófunarstaða fyrir jarðsprengjur $i - 1$ og $i$.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta út heiltölu — minnsta mögulega gildi á mestu prófunarskekkju.

Dæmi

Inntak 1

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

Úttak 1

1
6

Athugasemd

Í fyrsta prófunartilvikinu gefur valið $b_1 = 1$ og $b_2 = 2$ hámarksskekkju upp á $1$. Skekkja upp á $0$ myndi krefjast $b_1 = b_2 = 1$, sem brýtur í bága við fjarlægðarskilyrðið.

Í öðru prófunartilvikinu er eitt besta valið $b = [-4, 7, 15, 10, 8, 22, 13]$. Öll fjarlægðarskilyrði eru uppfyllt og hámarksskekkjan er $6$.