Задано $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