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$，給定一個整數 $l_i$，指定地雷 $i - 1$ 與地雷 $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$。