题目描述

Ada 和 John 是最好的朋友。由于他们感到无聊，Ada 让 John 为她解决一个谜题。

一个集合 $S$ 被称为 宽松的，如果其中任意两个不同元素的绝对差至少为 $\mathbf{K}$，即对于所有 $x, y \in S$ 且 $x \neq y$，都有 $|x - y| \geq \mathbf{K}$。

Ada 有一个包含 $\mathbf{N}$ 个不同整数的列表 $\mathbf{A}$ 和一个整数 $\mathbf{K}$。对于每个 $\mathbf{A}_i$，她要求 John 找出由 $\mathbf{A}$ 中元素构成的最大尺寸的集合 $S_i$，使得 $S_i$ 包含 $\mathbf{A}_i$ 并且是宽松的。

注意：集合 $S_i$ 不需要由列表中连续的元素构成。

输入格式

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个整数 $\mathbf{N}$ 和 $\mathbf{K}$。第二行包含 $\mathbf{N}$ 个整数 $\mathbf{A}_1 \mathbf{A}_2 \ldots \mathbf{A}_{\mathbf{N}}$。

输出格式

对于每个测试用例，输出一行 Case #x: y_1 y_2 ... y_N，其中 $x$ 是测试用例编号（从 1 开始），$y_i$ 是包含 $\mathbf{A}_i$ 的最大宽松集合的尺寸。

2
3 2
1 2 3
6 4
2 7 11 19 5 3

Case #1: 2 1 2
Case #2: 4 4 4 4 3 4

提示

样例解释

在样例 #1 中，一个宽松集合不能同时包含 1 和 2，也不能同时包含 2 和 3。这意味着 $S_2 = \{2\}$，而使用 $S_1 = S_3 = \{1, 3\}$ 可以使它们的尺寸最大化。

在样例 #2 中，可能的尺寸最大集合为：

• $S_1 = S_2 = S_3 = S_4 = \{2, 7, 11, 19\}$，
• $S_5 = \{11, 19, 5\}$，
• $S_6 = \{7, 11, 19, 3\}$。

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• 对所有 $i$，$-10^9 \leq \mathbf{A}_i \leq 10^9$。
• 对所有 $i \neq j$，$\mathbf{A}_i \neq \mathbf{A}_j$。

测试集 1（4 分，可见判定）

• $1 \leq \mathbf{N} \leq 10$。
• $1 \leq \mathbf{K} \leq 100$。

测试集 2（10 分，可见判定）

• $1 \leq \mathbf{K} \leq 10^9$。

对于最多 15 个测试用例：

• $1 \leq \mathbf{N} \leq 10^5$。

对于其余测试用例：

• $1 \leq \mathbf{N} \leq 10^3$。

翻译由 DeepSeek V3 完成