Se dan una hiperesfera y un hiperrectángulo de dimensión $n$, definidos como sigue:

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

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

Sea $S \triangleq B \cap C$. Dado un punto $\mathbf{x} = (x_1, x_2, \dots, x_n)$, encuentra el punto en $S$ (incluyendo la frontera) que esté más cerca de $\mathbf{x}$, denotado por $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Un punto $\mathbf{p}$ se considera más cercano a $\mathbf{x}$ que un punto $\mathbf{q}$ si y solo si $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Entrada

Cada archivo de prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 3 \times 10^4$). A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), donde $a$ es el valor de $R^2$.

La segunda línea contiene $n$ enteros $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

La tercera línea contiene $n$ enteros $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Para cada archivo de prueba, se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime una línea con $n$ números reales $y_1, y_2, \dots, y_n$.

Tu respuesta se considerará correcta si su error absoluto o relativo no supera $10^{-6}$.

Formalmente, sea $y_i$ tu respuesta e $y_i^*$ la respuesta del jurado. Tu respuesta es aceptada si y solo si $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ para todo $i \in [1, n]$.

Ejemplos

Entrada 1

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

Salida 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624