Даны $n$-мерные гиперсфера и гиперпрямоугольник, определённые следующим образом:

Гиперсфера: $B \triangleq \{\mathbf{x} \mid \sum_{i=1}^n x_i^2 \le R^2; \mathbf{x} \in \mathbb{R}^n\}$;

Гиперпрямоугольник: $C \triangleq \{\mathbf{x} \mid |x_i| \le l_i, \forall i \in [1, n]; \mathbf{x} \in \mathbb{R}^n\}$.

Пусть $S \triangleq B \cap C$. По заданной точке $\mathbf{x} = (x_1, x_2, \dots, x_n)$ найдите точку в $S$ (включая границу), ближайшую к $\mathbf{x}$, обозначим её $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Точка $\mathbf{p}$ считается более близкой к $\mathbf{x}$, чем точка $\mathbf{q}$, тогда и только тогда, когда $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Входные данные

Каждый тестовый файл содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $T$ ($1 \le T \le 3 \times 10^4$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $n$ и $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), где $a$ — значение $R^2$.

Вторая строка содержит $n$ целых чисел $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Третья строка содержит $n$ целых чисел $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Для каждого тестового файла гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $10^5$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую $n$ вещественных чисел $y_1, y_2, \dots, y_n$.

Ваш ответ считается правильным, если его абсолютная или относительная погрешность не превосходит $10^{-6}$.

Формально, пусть ваш ответ равен $y_i$, а ответ жюри равен $y_i^*$. Ваш ответ принимается тогда и только тогда, когда $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ для всех $i \in [1, n]$.

Примеры

Входные данные 1

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

Выходные данные 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624