Elimination Round, Problem F

Gnome Paul is competing in the elimination round of the Gnome Math Cup. Problem F reads as follows.

You are given $n$ positive integers $a_1, a_2, \ldots, a_n$ and a positive integer $d$. Find nonzero integers $x_1, x_2, \ldots, x_n$ with $|x_i| \le 10^7$ such that

$a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = d.$

Gnomes dislike big numbers, so every $a_i$ and $d$ is at most $10^6$, and no $x_i$ may be $0$.

Many sequences can satisfy the equation, so exactly one of them counts as the answer. Set $s_{n+1} = 0$ and, for $i = n, n-1, \ldots, 1$, set $s_i = \gcd(a_i, s_{i+1})$, so $s_i$ is the greatest common divisor of $a_i, a_{i+1}, \ldots, a_n$. A required sequence exists if and only if $s_1$ divides $d$. When it exists, build it from left to right. Put $D_0 = d$, and for $i = 1, 2, \ldots, n-1$ pick $x_i$ this way.

1. $x_i$ is not $0$, and $D_i = D_{i-1} - a_i x_i$ is not $0$ and is a multiple of $s_{i+1}$.
2. Among all such $x_i$, take one that makes $|D_i|$ as small as possible.
3. If two of them give the same $|D_i|$, take the smaller $x_i$.

The last value is $x_n = D_{n-1} / a_n$. For $n = 1$ nothing is picked and $x_1 = d / a_1$. Every value this rule produces satisfies $|x_i| \le 10^7$.

The first line contains one integer $t$, the number of tests ($1 \le t \le 10^5$). The tests follow.

The first line of each test contains two integers $n$ and $d$ ($1 \le n \le 10^5$, $1 \le d \le 10^6$). The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^6$). The sum of $n$ over all tests does not exceed $10^5$.

Print the answer for each test. If the required sequence exists, print YES on one line, then print $x_1, x_2, \ldots, x_n$ separated by single spaces on the next line. Only the sequence defined above is accepted. If there is no such sequence, print NO as the only line for that test.