يقوم 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$.