VegiCat on miinanraivaustehtävällä. Lukusuoralla on $n$ miinaa. Miina $i$ sijaitsee kokonaislukukoordinaatissa $a_i$. Miinat on numeroitu koordinaattiensa mukaisessa järjestyksessä, joten $a_1 \le a_2 \le \cdots \le a_n$. Miinojen koordinaatit voivat toistua.

VegiCat testaa jokaisen miinan kerran järjestyksessä $1, 2, \ldots, n$. Miinalle $i$ hän valitsee testauspaikaksi kokonaislukukoordinaatin $b_i$, joka voi olla negatiivinen tai nolla. Tämän testin virhe on $|a_i - b_i|$.

Jokaiselle $2 \le i \le n$ annetaan kokonaisluku $l_i$, joka määrittää pienimmän vaaditun etäisyyden miinojen $i - 1$ ja $i$ testauspaikkojen välillä. Näiden paikkojen on toteutettava ehto

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

Auta VegiCatia minimoimaan suurin testausvirhe; toisin sanoen etsi

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

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.

Kunkin testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 10^5$), miinojen lukumäärän.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), missä $a_i$ on miinan $i$ koordinaatti. On taattu, että $a_1 \le a_2 \le \cdots \le a_n$.

Kolmas rivi sisältää $n - 1$ kokonaislukua $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), missä $l_i$ on pienin etäisyys miinojen $i - 1$ ja $i$ testauspaikkojen välillä.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaista testitapausta kohden kokonaisluku — suurimman testausvirheen pienin mahdollinen arvo.

Esimerkit

Syöte 1

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

Tuloste 1

1
6

Huomautus

Ensimmäisessä testitapauksessa valinta $b_1 = 1$ ja $b_2 = 2$ antaa suurimmaksi virheeksi $1$. Virhe $0$ vaatisi $b_1 = b_2 = 1$, mikä rikkoo etäisyysvaatimuksen.

Toisessa testitapauksessa eräs optimaalinen valinta on $b = [-4, 7, 15, 10, 8, 22, 13]$. Kaikki vaaditut etäisyydet toteutuvat ja suurin virhe on $6$.