다음과 같이 정의되는 $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