Gefin eru $n$-víð ofurkúla og ofurkassi, skilgreind sem hér segir:

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

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

Látum $S \triangleq B \cap C$. Gefinn er punktur $\mathbf{x} = (x_1, x_2, \dots, x_n)$, finndu punktinn í $S$ (að jaðrinum meðtöldum) sem er næstur $\mathbf{x}$, táknaður með $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Punktur $\mathbf{p}$ telst vera nær $\mathbf{x}$ en punktur $\mathbf{q}$ ef og aðeins ef $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Inntak

Hver prófunarskrá inniheldur mörg prófunartilvik. Fyrsta línan inniheldur fjölda prófunartilvika $T$ ($1 \le T \le 3 \times 10^4$). Lýsing á prófunartilvikunum fylgir á eftir.

Fyrsta línan í hverju prófunartilviki inniheldur tvær heiltölur $n$ og $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), þar sem $a$ er gildið á $R^2$.

Önnur línan inniheldur $n$ heiltölur $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Þriðja línan inniheldur $n$ heiltölur $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Fyrir hverja prófunarskrá er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta út eina línu sem inniheldur $n$ rauntölur $y_1, y_2, \dots, y_n$.

Svarið þitt telst rétt ef algildis- eða hlutfallsleg skekkja þess fer ekki yfir $10^{-6}$.

Formlega, látum svarið þitt vera $y_i$ og svar dómnefndar vera $y_i^*$. Svarið þitt er samþykkt ef og aðeins ef $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ fyrir öll $i \in [1, n]$.

Dæmi

Inntak 1

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

Úttak 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624