Dane są $n$-wymiarowa hipersfera oraz hiperprostokąt, zdefiniowane następująco:

Hipersfera: $B \triangleq \{\mathbf{x} \mid \sum_{i=1}^n x_i^2 \le R^2; \mathbf{x} \in \mathbb{R}^n\}$;

Hiperprostokąt: $C \triangleq \{\mathbf{x} \mid |x_i| \le l_i, \forall i \in [1, n]; \mathbf{x} \in \mathbb{R}^n\}$.

Niech $S \triangleq B \cap C$. Dla danego punktu $\mathbf{x} = (x_1, x_2, \dots, x_n)$ znajdź punkt w $S$ (wliczając brzeg), który leży najbliżej punktu $\mathbf{x}$, oznaczany przez $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Punkt $\mathbf{p}$ uważa się za bliższy punktowi $\mathbf{x}$ niż punkt $\mathbf{q}$ wtedy i tylko wtedy, gdy $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Wejście

Każdy plik testowy zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $T$ ($1 \le T \le 3 \times 10^4$). Poniżej znajduje się opis przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), gdzie $a$ jest wartością $R^2$.

Drugi wiersz zawiera $n$ liczb całkowitych $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Trzeci wiersz zawiera $n$ liczb całkowitych $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Dla każdego pliku testowego gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ liczb rzeczywistych $y_1, y_2, \dots, y_n$.

Twoja odpowiedź zostanie uznana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekroczy $10^{-6}$.

Formalnie, niech twoją odpowiedzią będzie $y_i$, a odpowiedzią jury $y_i^*$. Twoja odpowiedź zostanie zaakceptowana wtedy i tylko wtedy, gdy $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ dla każdego $i \in [1, n]$.

Przykłady

Wejście 1

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

Wyjście 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624