这个问题是你见过的最无聊的问题。
给定一个整数序列 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 值很大,因此子序列之一最好为空。