Gegeben sind eine $n$-dimensionale Hypersphäre und ein Hyperrechteck, die wie folgt definiert sind:

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

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

Sei $S \triangleq B \cap C$. Gegeben einen Punkt $\mathbf{x} = (x_1, x_2, \dots, x_n)$, finde den Punkt in $S$ (einschließlich des Randes), der $\mathbf{x}$ am nächsten liegt, bezeichnet mit $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Ein Punkt $\mathbf{p}$ gilt genau dann als näher an $\mathbf{x}$ als ein Punkt $\mathbf{q}$, wenn $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$ gilt.

Eingabe

Jede Testdatei enthält mehrere Testfälle. Die erste Zeile enthält die Anzahl der Testfälle $T$ ($1 \le T \le 3 \times 10^4$). Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ und $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), wobei $a$ der Wert von $R^2$ ist.

Die zweite Zeile enthält $n$ ganze Zahlen $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Die dritte Zeile enthält $n$ ganze Zahlen $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Für jede Testdatei wird garantiert, dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile mit $n$ reellen Zahlen $y_1, y_2, \dots, y_n$ aus.

Deine Antwort gilt als korrekt, wenn ihr absoluter oder relativer Fehler $10^{-6}$ nicht überschreitet.

Formal sei deine Antwort $y_i$ und die Antwort der Jury $y_i^*$. Deine Antwort wird genau dann akzeptiert, wenn für alle $i \in [1, n]$ gilt: $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$.

Beispiele

Eingabe 1

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

Ausgabe 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624