Annetaan $n$-ulotteinen hyperpallo ja hypersuorakulmio, jotka määritellään seuraavasti:

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

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

Olkoon $S \triangleq B \cap C$. Kun annetaan piste $\mathbf{x} = (x_1, x_2, \dots, x_n)$, etsi joukon $S$ (reuna mukaan lukien) piste, joka on lähimpänä pistettä $\mathbf{x}$, merkittynä $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Pisteen $\mathbf{p}$ katsotaan olevan lähempänä pistettä $\mathbf{x}$ kuin pisteen $\mathbf{q}$ jos ja vain jos $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Syöte

Jokainen testitiedosto sisältää useita testitapauksia. Ensimmäinen rivi sisältää testitapausten määrän $T$ ($1 \le T \le 3 \times 10^4$). Seuraavaksi esitetään testitapausten kuvaukset.

Jokaisen testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), missä $a$ on luvun $R^2$ arvo.

Toinen rivi sisältää $n$ kokonaislukua $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Kolmas rivi sisältää $n$ kokonaislukua $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Jokaisessa testitiedostossa taataan, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $n$ reaalilukua $y_1, y_2, \dots, y_n$.

Vastauksesi katsotaan oikeaksi, jos sen absoluuttinen tai suhteellinen virhe on enintään $10^{-6}$.

Muodollisesti, olkoon vastauksesi $y_i$ ja tuomariston vastaus $y_i^*$. Vastauksesi hyväksytään jos ja vain jos $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ kaikilla $i \in [1, n]$.

Esimerkit

Syöte 1

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

Tuloste 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624