ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5016: 海绵宝宝和恶作剧

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：11 通过：7
提交提交记录统计Web Board

题目描述

当派大星去购物时，海绵宝宝决定对他的朋友玩一个恶作剧。顽皮的海绵宝宝浏览了派大星的个人物品，找到了一个长度为m的序列a1,a2,...,am，由1到n的整数组成，不一定是每个不同的。然后他挑选了一些长度为n的序列f1,f2,...,fn，对于每个数字ai都得到了数字bi=f[ai]。为了完成这个恶作剧，他抹去了最初的序列ai
当派大星买完东西回到家时，很难表达他有多伤心! 我们只想说，海绵宝宝立即对他所做的事情感到非常抱歉，他现在正试图恢复原来的序列。帮助他做到这一点或确定这是不可能的。


While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick's personal stuff and found a sequence a1,a2,...,am of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence f1,f2,...,fn of length n and for each number ai got number bi=fai. To finish the prank he erased the initial sequence ai.
It's hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.
Input
The first line of the input contains two integers n and m (1≤n,m≤100000)− the lengths of sequences fi and bi respectively.
The second line contains n integers, determining sequence f1,f2,...,fn (1≤fi≤n).
The last line contains m integers, determining sequence b1,b2,...,bm (1≤bi≤n).
Output
Print "Possible" if there is exactly one sequence ai, such that bi=fai for all i from 1 to m. Then print m integers a1,a2,...,am.
If there are multiple suitable sequences ai, print "Ambiguity".
If Spongebob has made a mistake in his calculations and no suitable sequence ai exists, print "Impossible".
Examples
Input 
3 3
3 2 1
1 2 3
Output 
Possible
3 2 1
Input 
3 3
1 1 1
1 1 1
Output 
Ambiguity
Input 
3 3
1 2 1
3 3 3
Output 
Impossible
Note
In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.
In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.
In the third sample fi≠3 for all i, so no sequence ai transforms into such bi and we can say for sure that Spongebob has made a mistake.

输入格式

输入的第一行包含两个整数n和m（1≤n,m≤100000）--分别是序列fi和bi的长度。
第二行包含n个整数，决定序列f1,f2,...,fn（1≤fi≤n）。
最后一行包含m个整数，确定序列b1,b2,...,bm（1≤bi≤n）。

输出格式

如果正好有一个序列ai，使bi=fai，对1到m中的所有i来说，打印 "Possible"，然后打印m个整数a1，a2，...，am。
如果有多个合适的序列ai，则打印 "Ambiguity"。
如果海绵宝宝在计算中犯了一个错误，并且不存在合适的序列ai，则打印 "Impossible"。

输入样例 复制 

3 3
3 2 1
1 2 3

输出样例 复制 

Possible
3 2 1

数据范围与提示

在第一个样例中，3被1取代，反之亦然，而2从未改变。答案是存在的，而且是唯一的。
在第二个样例中，所有的数字都被1取代，所以不可能明确地恢复原始序列。
在第三个样例中，所有i的fi≠3，所以没有任何序列ai转化为这样的bi，我们可以肯定地说，海绵宝宝犯了一个错误。

分类标签