← 返回题目列表

AtCoder · icpc2013summer_warmingUp_h

H. 洗牌机

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

说明

KM 购买了一台新洗牌机。
根据他的假设,每次你设置 N 牌并按下开关,它以完全相同的方式洗牌。更准确地说,存在一个整数序列 a_1, a_2, ..., a_N 这样

  • 结果顺序中的第一张牌始终是 a_1初始顺序中的第张牌,
  • 结果顺序中的第二张牌始终是 a_2初始顺序中的第张牌,
  • ...,等等。

他想知道这个序列,所以他设置 N 卡按升序排列: 1, 2, ..., N。然而他不小心按下了开关 K 次,最终的卡片顺序是 b_1, b_2, ..., b_N.
但是KM说你可以猜 a_1, a_2, ..., a_N 来自 b_1, b_2, ..., b_N。你能做到吗?

输入

输入文件的第一行包含整数 N (1 \leq N \leq 10^5)和 K (1 \leq K \leq 10^{18}),用空格分隔。
输入文件的第二行包含 N 个不同的整数,表示 b_1, b_2, ..., b_N (1 \leq b_i \leq N) 按此顺序,用空格分隔。

输出

如果 KM 的假设似乎是错误的,只需打印 Impossible。如果有多种可能性,则打印 Ambiguous。否则,打印 N 整数表示 a_1, a_2, ..., a_N 按此顺序,用空格分隔。

示例输入

3 2
3 1 2

示例输出

2 3 1

示例输入

3 2
1 3 2

示例输出

Impossible

示例输入

4 2
2 1 4 3

示例输出

Ambiguous