تُعطى كرة فائقة ومتوازي مستطيلات فائق ذوا $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