Diberikan sebuah hipersfer dan hiperpersegi panjang berdimensi $n$, yang didefinisikan sebagai berikut:

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

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

Misalkan $S \triangleq B \cap C$. Diberikan sebuah titik $\mathbf{x} = (x_1, x_2, \dots, x_n)$, carilah titik di dalam $S$ (termasuk batasnya) yang paling dekat dengan $\mathbf{x}$, yang dinyatakan dengan $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

Sebuah titik $\mathbf{p}$ dianggap lebih dekat ke $\mathbf{x}$ daripada sebuah titik $\mathbf{q}$ jika dan hanya jika $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Format Masukan

Setiap berkas uji berisi beberapa kasus uji. Baris pertama berisi banyaknya kasus uji $T$ ($1 \le T \le 3 \times 10^4$). Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), dengan $a$ adalah nilai dari $R^2$.

Baris kedua berisi $n$ bilangan bulat $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

Baris ketiga berisi $n$ bilangan bulat $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

Untuk setiap berkas uji, dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $10^5$.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $n$ bilangan riil $y_1, y_2, \dots, y_n$.

Jawaban Anda dianggap benar jika galat mutlak atau relatifnya tidak melebihi $10^{-6}$.

Secara formal, misalkan jawaban Anda adalah $y_i$, dan jawaban juri adalah $y_i^*$. Jawaban Anda diterima jika dan hanya jika $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ untuk semua $i \in [1, n]$.

Contoh

Masukan 1

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

Keluaran 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624