题目内容

一位登山爱好者沿着一条路线依次记录了若干地点的海拔高度。他制定了一条筛选规则：只有当一个地点的海拔相比于前一个地点（无论其是否被记录）上升了至少 $\delta$ 时，才将这个地点的海拔记入日志；否则，该地点将被忽略。登山者从第一个地点开始，总是记下起点的海拔。

某天，你捡到了他的日志，里面记录了一系列海拔 $c_1, c_2, \dots, c_n$，以及他设置的阈值 $\delta$。你想逆推出他可能实际经过的所有地点的海拔序列 $x_1, x_2, \dots, x_m$（$m \ge n$），使得按照上述规则筛选后恰好得到日志序列 $c$。在满足条件的前提下，你希望 $m$ 尽可能小；如果仍有多种方案，则希望 $x$ 的字典序尽可能小。

我们可以证明，对于给定的合法日志，一定存在符合全部要求的原始序列。

字典序的定义如下：从左到右逐项比较，找到第一个不同的位置，元素较小的序列字典序更小；若所有对应位置均相同，则较短的序列字典序更小。

数据范围与约定：

• 测试组数 $T$ 满足 $1 \le T \le 10^4$；
• 每组日志长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，且所有测试组的 $n$ 之和不超过 $2 \times 10^5$；
• 阈值 $\delta$ 满足 $0 \le \delta < 10^9$；
• 所有海拔值均为不超过 $10^9$ 的正整数。

输入描述

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据组数。 接下来每组数据由两行构成： 第一行包含两个整数 $n$ ($1 \le n \le 2 \times 10^5$) 和 $\delta$ ($0 \le \delta < 10^9$)，分别表示日志序列的长度和阈值。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)，表示日志记录的海拔序列。 保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出两行： 第一行输出一个整数 $m$ ($n \le m \le 2n$)，表示构造出的原始地点数量。 第二行输出 $m$ 个整数 $x_1, x_2, \dots, x_m$，用空格分隔，表示原始海拔序列，需要满足长度最小且字典序最小的要求。

样例1

输入

1
1 10
5

输出

1
5

说明

只有一组测试数据，日志中仅有一个海拔 5，阈值 $\delta = 10$。

第一个地点一定会被记录，所以原始序列只需包含该地点即可。此时 $m=1$ 达到最小，序列为 $[5]$。

样例2

输入

1
3 2
2 5 10

输出

3
2 5 10

说明

日志序列为 $c = [2, 5, 10]$，阈值 $\delta = 2$。

检查相邻日志项：$2 + 2 = 4 \le 5$，满足直接保留条件；$5 + 2 = 7 \le 10$，同样满足。因此所有地点都可以直接连接，不需要插入任何额外元素。得到最短原始序列 $x = [2, 5, 10]$，长度 $m = 3$。

样例3

输入

1
3 5
8 13 9

输出

4
8 13 1 9

说明

日志 $c = [8, 13, 9]$，阈值 $\delta = 5$。

首先 $8 + 5 = 13 \le 13$，13 可直接保留，无需插入。 接下来 $13 + 5 = 18 > 9$，若直接放置 9 则它会被跳过。为了在长度最短的前提下让 9 被记录，必须在中间插入恰好一个元素 $x$，要求 $x + 5 \le 9$ 且 $13 + 5 > x$。取最小正整数 $x = 1$ 即可满足。 最终序列为 $8, 13, 1, 9$，长度 $m = 4$，字典序最小。

样例4

输入

1
4 1
5 4 3 2

输出

7
5 1 4 1 3 1 2

说明

日志 $c = [5, 4, 3, 2]$，阈值 $\delta = 1$，呈递减趋势。

由于每个日志项都大于 $\delta$（即 $c_i > 1$），当 $c_{i-1} + 1 > c_i$ 时，可以在其间插入最小正整数 $1$，使得 $1 + 1 \le c_i$ 成立从而保留 $c_i$。

处理过程：

• 起点 5 直接保留；
• $5 + 1 > 4$，插入 1 和 4；
• $4 + 1 > 3$，插入 1 和 3；
• $3 + 1 > 2$，插入 1 和 2。 最终得到序列 $5, 1, 4, 1, 3, 1, 2$，长度 $m = 7$，且字典序最小（所有插入元素均为 $1$）。