Couti 和他的同学很快就要上大学了。为了互相告别,班级策划了一场盛大的欢送会,同学、老师、家长载歌载舞。
Couti 记得有 $$$n$$$ 人参加了那个聚会。为了让聚会变得更有趣,每个人都戴着 $$$n$$$ 种奇怪帽子中的一顶帽子,编号为 $$$1、2、\ldots n$$$。可能有几个人戴着同一种帽子。有些种类的帽子可能无人认领。
聚会结束后,第 $$$i$$$ 人说有 $$$a_i$$$ 人戴着与他自己不同的帽子。
已经好几天了,Couti 已经忘记了别人的帽子,但他对此很好奇。令 $$$b_i$$$ 为第 $$$i$$$ 个人所戴的帽子类型的数量,Couti 希望你找到任何可能的 $$$b_1, b_2, \ldots, b_n$$$ 与任何人的陈述都不矛盾。因为有些人记忆力可能不好,根本就没有办法。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),即队伍中的人数。
第二行包含$$$n$$$整数$$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n-1$$$),人的陈述。
输出
如果没有解决方案,则打印一行“Impossible”。
否则,打印“可能”,然后打印 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$)。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 0 0 0
输出 #1
Possible 1 1 1
输入 #2
5 3 3 2 2 2
输出 #2
Possible 1 1 2 2 2
输入 #3
4 0 1 2 3
输出 #3
Impossible
注意
在第一个例子的答案中,所有帽子都是一样的,所以每个人都会说没有人戴着与 $$$1$$$ 不同的帽子。
在第二个示例的答案中,第一个人和第二个人戴着 $$$1$$$ 类型的帽子,其他所有人都戴着 $$$2$$$ 类型的帽子。
所以前两个人会说有三个人的帽子与他们自己的不同。同样,最后三个人会说有两个人戴着与他们自己不同的帽子。
在第三个示例中,可以证明不存在解。
在第一和第二示例中,其他可能的配置也是可能的。