예선 라운드 F번 문제

땅요정 폴이 땅요정 수학 컵 예선 라운드에 나갔다. F번 문제는 다음과 같다.

양의 정수 $n$개 $a_1, a_2, \ldots, a_n$과 양의 정수 $d$가 주어진다. 다음 식을 만족하면서 어느 것도 $0$이 아니고 $|x_i| \le 10^7$인 정수 $x_1, x_2, \ldots, x_n$을 구하라.

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

땅요정은 큰 수를 싫어하므로 모든 $a_i$와 $d$는 $10^6$ 이하이고, 어떤 $x_i$도 $0$이 될 수 없다.

식을 만족하는 수열은 여러 개일 수 있어서 정답으로 인정하는 수열은 하나로 정해져 있다. $s_{n+1} = 0$으로 두고 $i = n, n-1, \ldots, 1$ 순서로 $s_i = \gcd(a_i, s_{i+1})$을 정의한다. 즉 $s_i$는 $a_i, a_{i+1}, \ldots, a_n$의 최대공약수다. 구하는 수열이 존재할 필요충분조건은 $s_1$이 $d$를 나누는 것이다. 존재하면 왼쪽부터 차례로 값을 정한다. $D_0 = d$로 두고 $i = 1, 2, \ldots, n-1$에 대해 다음과 같이 $x_i$를 고른다.

1. $x_i$는 $0$이 아니고, $D_i = D_{i-1} - a_i x_i$는 $0$이 아닌 $s_{i+1}$의 배수다.
2. 그런 $x_i$ 중에서 $|D_i|$가 가장 작아지는 것을 고른다.
3. $|D_i|$가 같은 후보가 둘이면 더 작은 $x_i$를 고른다.

마지막 값은 $x_n = D_{n-1} / a_n$이다. $n = 1$이면 고르는 과정 없이 $x_1 = d / a_1$이다. 이 규칙이 만드는 값은 항상 $|x_i| \le 10^7$을 만족한다.

첫째 줄에 테스트의 개수 $t$가 주어진다 ($1 \le t \le 10^5$). 이어서 각 테스트가 주어진다.

각 테스트의 첫째 줄에는 두 정수 $n$과 $d$가 주어진다 ($1 \le n \le 10^5$, $1 \le d \le 10^6$). 둘째 줄에는 $n$개의 정수 $a_i$가 주어진다 ($1 \le a_i \le 10^6$). 모든 테스트의 $n$을 더한 값은 $10^5$을 넘지 않는다.

각 테스트마다 답을 출력한다. 구하는 수열이 존재하면 한 줄에 YES를 출력하고, 다음 줄에 $x_1, x_2, \ldots, x_n$을 공백 하나로 구분해 출력한다. 위에서 정의한 수열만 정답으로 인정한다. 그런 수열이 없으면 그 테스트의 출력으로 NO만 출력한다.