以下のように定義される $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{q}$ よりも $\mathbf{x}$ に近いとは、$\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$ が成り立つことと同値です。

入力形式

各テストファイルには複数のテストケースが含まれます。1 行目にはテストケースの数を表す整数 $T$ ($1 \le T \le 3 \times 10^4$) が与えられます。続いて各テストケースが与えられます。

各テストケースの 1 行目には 2 つの整数 $n$, $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$) が与えられます。ここで $a$ は $R^2$ の値です。

2 行目には $n$ 個の整数 $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$) が与えられます。

3 行目には $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$ を含む 1 行を出力してください。

絶対誤差または相対誤差が $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