畀定一個 $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)$。

當且僅當 $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$ 時，先至認為點 $\mathbf{p}$ 比點 $\mathbf{q}$ 更接近 $\mathbf{x}$。

輸入格式

每個測試檔案包含多個測試用例。第一行包含測試用例嘅數量 $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^*$。當且僅當對於所有 $i \in [1, n]$ 都有 $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ 時，你嘅答案先至會被接受。

樣例

輸入樣例 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