Description

Little ζ discovered a large lock during his adventure.

This lock has $n$ dials, where the $i$-th dial can be set to any integer from $l_i$ to $r_i$ (inclusive, and $l_i ≤ r_i$ is guaranteed).

We define the lock’s “degree of freedom” as the greatest common divisor (GCD) of all numbers shown on the dials. The lock opens when its “degree of freedom” is greater than or equal to $k$.

Your task is to find a valid combination to open the lock, or report if it’s impossible.

Input Format

Multiple test cases within a single test point. The first line contains an integer $T$, representing the number of test cases.

For each test case:

First line contains two integers $n, k$, representing the number of dials and the freedom degree requirement.

The next $n$ lines each contain two integers $l_i, r_i$, as described in the problem.

Output Format

For each test case:

• If a solution exists, output Yes on the first line, followed by a line containing n space-separated integers, where the i-th number represents the value shown on the $i$-th dial in your solution. This problem uses Special Judge, any answer meeting the requirements will be accepted.
• Otherwise, output a single line containing No to indicate no solution exists.

1
5 10
1 12
44 50
9 10
88 99
29 99

Yes
10 50 10 90 30

2
3 11
99 10003
39 299
39 10003
5 55
1 54
1 20
1 300
1 300
1 300

Yes
123 246 369
No

3
6 1
1 10
1 10
1 10
1 10
1 10
1 10
5 4
11 15
6 10
9 14
20 23
27 29
5 11
20 30
50 70
111 120
72 77
119 121

Yes
1 1 4 5 1 4
Yes
14 7 14 21 28
Yes
24 60 120 72 120

4
3 33
32 34
65 67
97 101
3 5
299 99494993
499 49992999
499 39999939
4 25
719 830
2194 2893
132 142
199 225
3 10
140 143
131 135
238 241

Yes
33 66 99
Yes
1919810 11400 51400
Yes
729 2700 135 216
No

1
10 7
77 77
82 174
77 77
82 174
77 77
82 174
77 77
82 174
77 77
82 174

Yes
77 154 77 154 77 154 77 154 77 154

Hint

「Sample 1 Explanation」

For the only test case, the $\gcd$ is 10.

All five samples can be tested using the provided attachment. Note that some samples may have multiple valid solutions; the sample output shows just one possible solution.

「Data Constraints」

For 100% of testcases：$1 \le T \le 5$，$2 \le n \le 10^4$，$1 \le l_i \le r_i \le 10^9$，$1 \le k \le 1000$。

This problem uses subtask scoring。

• Subtask 1（10 pts）：$k=1$。
• Subtask 2（15 pts）：$n \le 10$，$r_i - l_i + 1 \le 5$。
• Subtask 3（15 pts）：$r_i \le 10^3$。
• Subtask 4（10 pts）：$k \le 5$，$l_i, r_i$ are randomly generated with uniform distribution in range $[1, 10^9]$, this subtask has only one test point.
• Subtask 5（15 pts）：For all cases，$\exist 1 \le i \le n,l_i=r_i$。
• Subtask 6（35 pts）：No additional constraints.

「About Additional Files」

A checker.cpp is provided as a testing tool.

Place your input content, program output, and reference answer in restore.in, restore.out, and restore.ans respectively. These three files must be in the same directory as checker.cpp. Run checker.cpp to see the testing results.

Your input must satisfy the constraints for $100\%$ of test cases.

Note that if your input/output/answer format or range is incorrect, the results from checker.cpp are unpredictable. Therefore, please ensure your three files are correctly formatted first.