VegiCat мина тазарту миссиясын орындаپ жүр. Сан осінде $n$ мина орналасқан. $i$-ші мина $a_i$ бүтін координатасында жатыр. Миналар координаталарының өсу ретімен нөмірленген, сондықтан $a_1 \le a_2 \le \cdots \le a_n$. Мина координаталары қайталануы мүмкін.

VegiCat әр минаны $1, 2, \ldots, n$ ретімен бір реттен тексереді. $i$-ші мина үшін ол тексеру орны ретінде $b_i$ бүтін координатасын таңдайды, ол теріс немесе нөл болуы мүмкін. Бұл тексерудің қателігі $|a_i - b_i|$-ге тең.

Әрбір $2 \le i \le n$ үшін $i - 1$ және $i$ миналарын тексеру орындарының арасындағы талап етілетін ең аз қашықтықты білдіретін $l_i$ бүтін саны берілген. Бұл орындар келесі шартты қанағаттандыруы керек:

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

VegiCat-қа ең үлкен тексеру қателігін барынша азайтуға көмектесіңіз; яғни келесі мәнді табыңыз:

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

Кіріс деректер

Бірінші жолда тесттер санын білдіретін бір бүтін сан $T$ ($1 \le T \le 10^4$) берілген. Одан кейін тесттердің сипаттамасы беріледі.

Әр тесттің бірінші жолында миналар санын білдіретін бір бүтін сан $n$ ($2 \le n \le 10^5$) берілген.

Екінші жолда $n$ бүтін сан $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) берілген, мұндағы $a_i$ — $i$-ші минаның координатасы. $a_1 \le a_2 \le \cdots \le a_n$ екеніне кепілдік беріледі.

Үшінші жолда $n - 1$ бүтін сан $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$) берілген, мұндағы $l_i$ — $i - 1$ және $i$ миналарын тексеру орындарының арасындағы ең аз қашықтық.

Барлық тесттер бойынша $n$ мәндерінің қосындысы $10^5$-тен аспайтынына кепілдік беріледі.

Шығыс деректер

Әр тест үшін бір бүтін санды — ең үлкен тексеру қателігінің мүмкін болатын ең кіші мәнін шығарыңыз.

Мысалдар

Кіріс деректер 1

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

Шығыс деректер 1

1
6

Ескертпе

Бірінші тестте $b_1 = 1$ және $b_2 = 2$ деп таңдау ең үлкен қателікті $1$-ге тең етеді. Қателік $0$ болуы үшін $b_1 = b_2 = 1$ болуы керек еді, бірақ бұл қашықтық талабын бұзады.

Екінші тестте тиімді таңдаулардың бірі — $b = [-4, 7, 15, 10, 8, 22, 13]$. Барлық талап етілген қашықтықтар сақталады, ал ең үлкен қателік $6$-ға тең.