Cho một siêu cầu và một siêu hình hộp chữ nhật $n$ chiều, được định nghĩa như sau:

Siêu cầu: $B \triangleq \{\mathbf{x} \mid \sum_{i=1}^n x_i^2 \le R^2; \mathbf{x} \in \mathbb{R}^n\}$;

Siêu hình hộp chữ nhật: $C \triangleq \{\mathbf{x} \mid |x_i| \le l_i, \forall i \in [1, n]; \mathbf{x} \in \mathbb{R}^n\}$.

Đặt $S \triangleq B \cap C$. Cho một điểm $\mathbf{x} = (x_1, x_2, \dots, x_n)$, hãy tìm điểm thuộc $S$ (bao gồm cả biên) gần với $\mathbf{x}$ nhất, ký hiệu là $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Một điểm $\mathbf{p}$ được coi là gần với $\mathbf{x}$ hơn một điểm $\mathbf{q}$ khi và chỉ khi $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Dữ liệu vào

Mỗi tệp dữ liệu chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $T$ ($1 \le T \le 3 \times 10^4$). Tiếp theo là mô tả của các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), trong đó $a$ là giá trị của $R^2$.

Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Dòng thứ ba chứa $n$ số nguyên $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Với mỗi tệp dữ liệu, đảm bảo rằng tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa $n$ số thực $y_1, y_2, \dots, y_n$.

Câu trả lời của bạn được coi là chính xác nếu sai số tuyệt đối hoặc tương đối của nó không vượt quá $10^{-6}$.

Một cách hình thức, gọi câu trả lời của bạn là $y_i$, và đáp án của ban giám khảo là $y_i^*$. Câu trả lời của bạn được chấp nhận khi và chỉ khi $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ với mọi $i \in [1, n]$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624