VegiCat đang thực hiện một nhiệm vụ rà phá bom mìn. Có $n$ quả mìn trên một trục số. Quả mìn thứ $i$ nằm ở tọa độ nguyên $a_i$. Các quả mìn được đánh số theo thứ tự tọa độ của chúng, vì vậy $a_1 \le a_2 \le \cdots \le a_n$. Tọa độ của các quả mìn có thể trùng nhau.

VegiCat kiểm tra mỗi quả mìn một lần, theo thứ tự $1, 2, \ldots, n$. Đối với quả mìn $i$, anh ấy chọn một tọa độ nguyên $b_i$ làm vị trí kiểm tra, giá trị này có thể âm hoặc bằng không. Sai số của lần kiểm tra này là $|a_i - b_i|$.

Với mỗi $2 \le i \le n$, một số nguyên $l_i$ được cho trước, quy định khoảng cách tối thiểu bắt buộc giữa các vị trí kiểm tra của quả mìn $i - 1$ và quả mìn $i$. Các vị trí này phải thỏa mãn

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

Hãy giúp VegiCat cực tiểu hóa sai số kiểm tra lớn nhất; nghĩa là, tìm

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

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$), số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($2 \le n \le 10^5$), số lượng quả mìn.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), trong đó $a_i$ là tọa độ của quả mìn $i$. Dữ liệu đảm bảo rằng $a_1 \le a_2 \le \cdots \le a_n$.

Dòng thứ ba chứa $n - 1$ số nguyên $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), trong đó $l_i$ là khoảng cách tối thiểu giữa các vị trí kiểm tra của quả mìn $i - 1$ và quả mìn $i$.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy in ra một số nguyên — giá trị nhỏ nhất có thể của sai số kiểm tra lớn nhất.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
6

Ghi chú

Trong bộ dữ liệu đầu tiên, việc chọn $b_1 = 1$ và $b_2 = 2$ cho sai số lớn nhất là $1$. Để có sai số bằng $0$ thì cần $b_1 = b_2 = 1$, điều này vi phạm yêu cầu về khoảng cách.

Trong bộ dữ liệu thứ hai, một cách chọn tối ưu là $b = [-4, 7, 15, 10, 8, 22, 13]$. Tất cả các khoảng cách bắt buộc đều được thỏa mãn và sai số lớn nhất là $6$.