Sono dati un'ipersfera e un iperrettangolo $n$-dimensionali, definiti come segue:

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

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

Sia $S \triangleq B \cap C$. Dato un punto $\mathbf{x} = (x_1, x_2, \dots, x_n)$, trova il punto in $S$ (incluso il bordo) più vicino a $\mathbf{x}$, indicato con $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Un punto $\mathbf{p}$ è considerato più vicino a $\mathbf{x}$ rispetto a un punto $\mathbf{q}$ se e solo se $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Input

Ogni file di test contiene più casi di test. La prima riga contiene il numero di casi di test $T$ ($1 \le T \le 3 \times 10^4$). Segue la descrizione dei casi di test.

La prima riga di ciascun caso di test contiene due interi $n$ e $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), dove $a$ è il valore di $R^2$.

La seconda riga contiene $n$ interi $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

La terza riga contiene $n$ interi $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Per ogni file di test, è garantito che la somma di $n$ su tutti i casi di test non supera $10^5$.

Output

Per ciascun caso di test, stampa una riga contenente $n$ numeri reali $y_1, y_2, \dots, y_n$.

La tua risposta è considerata corretta se il suo errore assoluto o relativo non supera $10^{-6}$.

Formalmente, sia $y_i$ la tua risposta e $y_i^*$ la risposta della giuria. La tua risposta è accettata se e solo se $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ per ogni $i \in [1, n]$.

Esempi

Input 1

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

Output 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624