Clutch or kick

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \leq t \leq 4 \cdot 1 0^{5}$ 1 \le t \le 4 \cdot 10^5). The description of the test cases follows.

The first line of each test case contains two integers $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6) and $s$ ( $- 1 0^{9} \leq s \leq 1 0^{9}$ -10^9 \leq s \leq 10^9).

The second line contains $n$ integers $a_{i}$ a_i ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \leq a_i \leq 10^9) representing the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1 0^{6}$ 10^6.

Output

For each test case, for each $i$ ( $1 \leq i \leq n$ 1 \le i \le n), output either an integer — the answer for this $i$ , or $x$ if it is impossible.

Examples

Example 1

Loading

Scoring

Here, $N$ is the sum of $n$ in all test cases.

( $21$ points): $N \leq 500$ N \le 500;
( $20$ points): $N \leq 1000$ N \le 1000;
( $21$ points): $a_{i} \geq 0$ a_i \ge 0;
( $42$ points): $s > 0$ s > 0;
( $61$ points): $N \leq 5 \cdot 1 0^{4}$ N \le 5 \cdot 10^4;
( $61$ points): $N \leq 1 0^{5}$ N \le 10^5;
( $62$ points): $N \leq 6 \cdot 1 0^{5}$ N \le 6 \cdot 10^5;
( $62$ points): no additional constraints