Given an $n$-dimensional hypersphere and hyperrectangle, defined as follows:

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

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

Let $S \triangleq B \cap C$. Given a point $\mathbf{x} = (x_1, x_2, \dots, x_n)$, find the point in $S$ (including the boundary) that is closest to $\mathbf{x}$, denoted by $\mathbf{y} = (y_1, y_2, \dots, y_n)$.

A point $\mathbf{p}$ is considered closer to $\mathbf{x}$ than a point $\mathbf{q}$ if and only if $\sum_{i=1}^n (x_i - p_i)^2 \le \sum_{i=1}^n (x_i - q_i)^2$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 3 \times 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $a$ ($2 \le n \le 10^5$, $1 \le a \le 10^9$), where $a$ is the value of $R^2$.

The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($|x_i| \le 10^9$).

The third line contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \le l_i \le 100$).

For each test file, it is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output one line containing $n$ real numbers $y_1, y_2, \dots, y_n$.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $y_i$, and the jury's answer be $y_i^*$. Your answer is accepted if and only if $\frac{|y_i - y_i^*|}{\max(1, |y_i^*|)} \le 10^{-6}$ for all $i \in [1, n]$.

Examples

Input 1

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

Output 1

1.0000000000 4.0000000000
4.0000000000 1.0000000000
1.4142135624 1.4142135624 1.4142135624