กำหนดทรงกลมหลายมิติและทรงสี่เหลี่ยมมุมฉากหลายมิติขนาด $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