题目背景

The English statement for T5

You can also see the pdf at the bottom of the chinese problem statement.

感谢 ineverleft 为本题提供的本地调试 checker。

题目描述

小 $\zeta$ 在探险过程中看到了一个大锁。

这个大锁有 $n$ 个拨圈，第 $i$ 个拨圈的拨动范围为 $l_i$ 到 $r_i$ 之间（含两个边界）的所有整数（保证 $l_i \le r_i$）。

我们定义这个大锁的「自由度」为所有拨圈上的数的最大公约数，当锁的「自由度」大于等于 $k$ 时，会被打开。

请你找到一种锁的开启方案，或报告无解。

输入格式

本题单测试点内含有多组测试数据，第一行一个整数 $T$，代表数据组数。

对于每组数据：

第一行两个整数 $n,k$，分别代表拨圈数量和自由度限制。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，含义见题目描述。

输出格式

对于每组数据：

• 如果有解，第一行输出 Yes，下一行输出 $n$ 个空格分隔的整数，第 $i$ 个为你的构造方案中第 $i$ 个拨圈显示的数。本题使用了 Special Judge，符合要求的答案均判对。

• 否则，输出一行 No 表示无解。

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

提示

【样例 1 解释】

唯一的一组数据 $\gcd$ 为 $10$。

五个样例自测均可使用下发的附件。请注意部分样例可能存在多解，样例输出仅列举了一组可行解。

【数据规模与约定】

对于 $100\%$ 的数据，$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$。

本题开启子任务捆绑测试。

• 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$ 均在 $1 \le l_i \le r_i \le 10^9$ 范围内等概率随机生成，该子任务只有 $1$ 个测试点。
• Subtask 5（15 pts）：对于每组数据，$\exist 1 \le i \le n,l_i=r_i$。
• Subtask 6（35 pts）：无特殊限制。

【关于附加文件】

本题下发了 checker.cpp 作为自测器。checker_X.cpp 用不了的，可以用 checker_S.cpp，问题原因导致 stdin 的重定向失败，我们正在排查。

请将输入内容、你的程序输出、参考答案输出分别放置在 restore.in、restore.out、restore.ans 中，这三个文件必须与 checker.cpp 在同一目录下，运行 checker.cpp，终端上会给出自测结果。

你需要保证你的输入满足 $100\%$ 数据范围的要求。

注意，如果你的输入/输出/答案的格式和范围不正确的话，checker.cpp 出现的结果是不可预料的。因此，请先确保你的三个文件格式正确。