解题思路

题目给定阈值 $d$ 和最终保留下来的序列 $b$，要求构造一个正整数序列 $a$，按如下规则筛选后恰好得到 $b$：

• $a_1$ 一定保留；
• 对于 $i \ge 2$，若 $a_{i-1} + d \le a_i$，则 $a_i$ 被保留，否则被跳过。

并且还要满足：

题目内容

$TK$先写下一个正整数序列 {$a_1,a_2,…,a_m$}（$1≤a_i≤10^9$），随后，她按照如下带阈值的保留规则从左到右生成序列 {$b_1,b_2,…,b_n$}：

• 先保留 $a_1$；
• 当处理到$a_i(2≤i≤m)$时，将其与它在序列 $a$ 中的前一个元素 $a_{i−1 }$进行比较。若$a_{i−1}+d≤a_i$成立，则将 $a_i$保留下来；否则跳过 $a_i$。

现给出阈值 $d$与最终得到的序列 {$b_1,…,b_n$}。你的任务是构造任意一个原序列 {$a_1,…,a_m$}，使得按上述规则从 $a$ 生成的序列恰为$b$，并同时满足：

• $m$ 尽可能小；
• 在所有满足最小长度的解中，$a$的字典序尽可能小。

我们可以证明，一定存在至少一个符合全部要求的序列。

名词解释

序列的字典序比较：从左到右逐个比较两个序列的元素。如果在某个位置上元素不同，比较这两个元素的大小，元素小的序列字典序也小；如果一直比较到其中一个序列结束，则长度较短的序列字典序更小。例如：

• $[1,2,3]$ 的字典序小于 $[2,3,4]$，因为第一个位置上的元素$1<2$；
• $[1,2,3]$ 的字典序大于 $[1,2]$，因为第一、二个位置上的元素均相同，但是后者的长度更短。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下：

• 第一行输入两个整数$n,d(1≤n≤2×10^5，0≤d<10^9)$；
• 第二行输入 $n$ 个整数 $b_1,b_2,…,b_n(1≤b_i≤10^9)$。

除此之外，保证所有测试用例的 n 之和不超过 2×105。

输出描述

对于每组测试数据，输出两行：

• 第一行输出一个整数$m(n≤m≤2n)$；
• 第二行输出$m$个整数，为构造出的序列 {$a_1,a_2,…,a_m$}$(1≤a_i≤10^9)$，使得按规则生成的序列恰为 $b$，且$a$长度最小、在最小长度下字典序最小。

样例1

输入

2
3 2
3 5 6
4 0
2 1 1 3

输出

4
3 5 1 6
5
2 1 1 1 3

说明

样倒解释(对应第一组数据)：

• 构造$a$={$3,5,1,6$};
• 处理时先保留$3$因$3+2≤5$，保留$5$；因$5+2≤1$不成立，跳过$1$；因$1+2≤6$，保留$6$;
• 最终保留序列为{$3,5,6$}与$b$一致；长度$m=4$，且在最小长度下字典序最小。