Келесідей анықталған $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{q}$ нүктесіне қарағанда $\mathbf{x}$-ке жақынырақ деп есептеледі сонда және тек сонда ғана, егер $\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^*$ болсын. Сіздің жауабыңыз тек барлық $i \in [1, n]$ үшін $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ шарты орындалғанда ғана қабылданады.

Мысалдар

Кіріс 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