#840. T6

T6

题目描述

感受神的睿智吧。 𝑤ℎ𝑦今天非常愉悦,并赐予你一个考验,如果你能够通过这个考验,你就 能获得在卡密大人面前感受神的光辉的权利。

你的面前有一摞牌,第𝑖𝑖张牌上写着:下方的牌中至少有𝑎𝑖𝑎_𝑖张上记录的信息是错误的。你的 任务是对这一摞牌进行洗牌使得恰有𝐾𝐾张牌上记录的信息是错误的。

例如:如果从下到上牌上的数字依次是0,2,10,2,1。那么就有一张牌是错误的,即第二张,第一张 牌下面没有牌,自然只有00张牌是错误的,所以第一张牌正确。由于第一张牌正确,因此第二张牌下面没有牌是错误的,而第二张牌上写的是22,因此第二张牌错误。前两张牌只有一张是错误的, 因此第三张牌上写的11是正确的。 因此第三张牌正确,只有第二张牌错误。

当然这也许只是神大人对你的一次愚弄,你也需要具有判断解答是否存在的能力。

输入格式

输入的第一行包括两个正整数𝑁𝑁𝐾(1𝑁,𝐾5×105)𝐾(1 ≤ 𝑁, 𝐾 ≤ 5 × 10^5),含义见题意。

接下来的𝑁行,每行一个正整数,第𝑖行的正整数即为𝑎𝑖(0𝑎𝑖5×105)𝑎_𝑖(0 ≤ 𝑎_𝑖 ≤ 5 × 10^5)

输出格式

如果无解,输出一行一个整数1“-1”

如果存在解,输出一行𝑁𝑁个数,从第一个数到第𝑁𝑁个依次表示从上到下每一张牌上的𝑎𝑖𝑎𝑖

样例

输入样例

4 2
1
2
2
3

输出样例

2 3 1 2

输入样例2

5 3
2
1
3
0
3

输出样例2

3 3 0 1 2

数据范围与提示

存在3030%的测试数据,𝑁16 𝑁 ≤ 16

另有4040%的测试数据, 𝑁2000𝑁 ≤ 2 000