← 返回题目列表

Codeforces · 238/B

B. 无聊的隔断

中文机器翻译题面 查看原题

这个问题是你见过的最无聊的问题。

给定一个整数序列 a1, a2, ..., an 和一个非负整数 h,我们的目标是将序列划分为两个子序列(不一定由连续元素组成)。原始序列的每个元素都应恰好包含在结果子序列之一中。请注意,结果子序列之一可以为空。

让我们在原始序列中的不同元素对(即 i ≠ j)上定义函数 f(ai, aj)。如果 ai 和 aj 在当前分区中位于同一子序列中,则 f(ai, aj) = ai + aj,否则 f(ai, aj) = ai + aj + h。

考虑某个分区的函数 f 的所有可能值。我们将这种划分的优点称为函数 f 的最大值与函数 f 的最小值之间的差。

您的任务是找到给定序列 a 的一个分区,该分区在所有可能的分区中具有尽可能小的优点。

输入

输入的第一行包含整数 n 和 h (2 ≤ n ≤ 105, 0 ≤ h ≤ 108)。第二行有一个由 n 个空格分隔的整数组成的列表,分别表示 a1、a2、...、an (0 ≤ ai ≤ 108)。

输出

输出的第一行应包含所需的最低质量。

第二行描述了最佳分区。您应该在第二行中打印 n 个以空格分隔的整数。如果 ai 在第一个子序列中,则第 i 个整数为 1,否则应为 2。

如果有多个可能的正确答案,您可以打印其中任何一个。

示例

输入 #1

3 2
1 2 3

输出 #1

1
1 2 2

输入 #2

5 10
0 1 0 2 1

输出 #2

3
2 2 2 2 2

注意

在第一个示例中,f 的值如下:f(1, 2) = 1 + 2 + 2 = 5、f(1, 3) = 1 + 3 + 2 = 6 和 f(2, 3) = 2 + 3 = 5。因此 f 的最大值和最小值之差为 1。

在第二个样本中,h 值很大,因此子序列之一最好为空。