On vous donne une hypersphère et un hyperrectangle de dimension $n$, définis comme suit :

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

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

Soit $S \triangleq B \cap C$. Étant donné un point $\mathbf{x} = (x_1, x_2, \dots, x_n)$, trouvez le point de $S$ (frontière comprise) qui est le plus proche de $\mathbf{x}$, noté $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Un point $\mathbf{p}$ est considéré comme plus proche de $\mathbf{x}$ qu'un point $\mathbf{q}$ si et seulement si $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Entrée

Chaque fichier de test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 3 \times 10^4$). La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $n$ et $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), où $a$ est la valeur de $R^2$.

La deuxième ligne contient $n$ entiers $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

La troisième ligne contient $n$ entiers $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Pour chaque fichier de test, il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant $n$ nombres réels $y_1, y_2, \dots, y_n$.

Votre réponse est considérée comme correcte si son erreur absolue ou relative ne dépasse pas $10^{-6}$.

Formellement, soit $y_i$ votre réponse et $y_i^*$ la réponse du jury. Votre réponse est acceptée si et seulement si $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ pour tout $i \in [1, n]$.

Exemples

Entrée 1

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

Sortie 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624