נתונים היפר-כדור והיפר-תיבה $n$-ממדיים, המוגדרים באופן הבא:

היפר-כדור: $B \triangleq \{\mathbf{x} \mid \sum_{i=1}^n x_i^2 \le R^2; \mathbf{x} \in \mathbb{R}^n\}$;

היפר-תיבה: $C \triangleq \{\mathbf{x} \mid |x_i| \le l_i, \forall i \in [1, n]; \mathbf{x} \in \mathbb{R}^n\}$.

תהי $S \triangleq B \cap C$. בהינתן נקודה $\mathbf{x} = (x_1, x_2, \dots, x_n)$, מצא את הנקודה ב-$S$ (כולל השפה) הקרובה ביותר אל $\mathbf{x}$, המסומנת ב-$\mathbf{y} = (y_1, y_2, \dots, y_n)$.

נקודה $\mathbf{p}$ נחשבת קרובה יותר אל $\mathbf{x}$ מאשר נקודה $\mathbf{q}$ אם ורק אם $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

קלט

כל קובץ בדיקה מכיל מספר מקרי בדיקה. השורה הראשונה מכילה את מספר מקרי הבדיקה $T$ ($1 \le T \le 3 \times 10^4$). אחריה מופיע תיאור מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה שני מספרים שלמים $n$ ו-$a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), כאשר $a$ הוא הערך של $R^2$.

השורה השנייה מכילה $n$ מספרים שלמים $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

השורה השלישית מכילה $n$ מספרים שלמים $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

עבור כל קובץ בדיקה, מובטח כי סכום ערכי ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $10^5$.

פלט

עבור כל מקרה בדיקה, הדפס שורה אחת המכילה $n$ מספרים ממשיים $y_1, y_2, \dots, y_n$.

תשובתך תיחשב נכונה אם השגיאה המוחלטת או היחסית שלה אינה עולה על $10^{-6}$.

באופן פורמלי, תהי תשובתך $y_i$, ותשובת השופטים $y_i^*$. תשובתך תתקבל אם ורק אם $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ עבור כל $i \in [1, n]$.

דוגמאות

קלט 1

3
2 25
1 10
4 4
2 25
10 1
4 4
3 6
3 3 3
2 2 2

פלט 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624