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