VegiCat sedang menjalankan misi penyapuan ranjau. Terdapat $n$ ranjau pada sebuah garis bilangan. Ranjau $i$ berada pada koordinat bulat $a_i$. Ranjau-ranjau tersebut diberi nomor sesuai urutan koordinatnya, sehingga $a_1 \le a_2 \le \cdots \le a_n$. Koordinat ranjau dapat berulang.

VegiCat menguji setiap ranjau satu kali, dalam urutan $1, 2, \ldots, n$. Untuk ranjau $i$, ia memilih sebuah koordinat bulat $b_i$ sebagai lokasi pengujian, yang boleh bernilai negatif atau nol. Galat dari pengujian ini adalah $|a_i - b_i|$.

Untuk setiap $2 \le i \le n$, diberikan sebuah bilangan bulat $l_i$ yang menyatakan jarak minimum yang disyaratkan antara lokasi pengujian untuk ranjau $i - 1$ dan $i$. Lokasi-lokasi ini harus memenuhi

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

Bantulah VegiCat meminimalkan galat pengujian terbesar; yaitu, carilah

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

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $n$ ($2 \le n \le 10^5$), banyaknya ranjau.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), dengan $a_i$ menyatakan koordinat ranjau $i$. Dijamin bahwa $a_1 \le a_2 \le \cdots \le a_n$.

Baris ketiga berisi $n - 1$ bilangan bulat $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), dengan $l_i$ menyatakan jarak minimum antara lokasi pengujian untuk ranjau $i - 1$ dan $i$.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat — nilai minimum yang mungkin dari galat pengujian terbesar.

Contoh

Masukan 1

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

Keluaran 1

1
6

Catatan

Pada kasus uji pertama, memilih $b_1 = 1$ dan $b_2 = 2$ menghasilkan galat maksimum sebesar $1$. Galat sebesar $0$ mengharuskan $b_1 = b_2 = 1$, yang melanggar syarat jarak.

Pada kasus uji kedua, salah satu pilihan optimal adalah $b = [-4, 7, 15, 10, 8, 22, 13]$. Semua syarat jarak terpenuhi, dan galat maksimumnya adalah $6$.