Gitt en $n$-dimensjonal hypersfære og et hyperrektangel, definert som følger:

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

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

La $S \triangleq B \cap C$. Gitt et punkt $\mathbf{x} = (x_1, x_2, \dots, x_n)$, finn punktet i $S$ (inkludert randen) som er nærmest $\mathbf{x}$, betegnet med $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Et punkt $\mathbf{p}$ regnes som nærmere $\mathbf{x}$ enn et punkt $\mathbf{q}$ hvis og bare hvis $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Inndata

Hver testfil inneholder flere testtilfeller. Den første linjen inneholder antall testtilfeller $T$ ($1 \le T \le 3 \times 10^4$). Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), der $a$ er verdien av $R^2$.

Den andre linjen inneholder $n$ heltall $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Den tredje linjen inneholder $n$ heltall $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

For hver testfil garanteres det at summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én linje som inneholder $n$ reelle tall $y_1, y_2, \dots, y_n$.

Svaret ditt regnes som riktig hvis den absolutte eller relative feilen ikke overstiger $10^{-6}$.

Formelt, la svaret ditt være $y_i$, og juryens svar være $y_i^*$. Svaret ditt godtas hvis og bare hvis $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ for alle $i \in [1, n]$.

Eksempler

Inndata 1

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

Utdata 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624