爱丽丝是一位魔术师,她创造了一个新魔术。她有 $$$n$$$ 卡片,上面写着从 $$$1$$$ 到 $$$n$$$ 的不同数字。首先,她要求一位观众洗牌并将牌排成一排。假设左边第 $$$i$$$ 卡上有数字 $$$a_i$$$。
然后 Alice 选择两个排列 $$$p$$$ 和 $$$q$$$。 $$$p$$$ 和 $$$q$$$ 有限制 — 排列不能有固定点。这意味着$$$\forall i: p_i \ne i\ 和\ q_i \ne i$$$。
选择排列后,爱丽丝根据排列洗牌。现在从左边算起第$$$i$$$张牌是$$$a[p[q[i]]$$$。如果洗牌后左侧第 $$$i$$$ 张牌上有数字 $$$i$$$,则该技巧被视为成功。
帮助 Alice 选择排列 $$$p$$$ 和 $$$q$$$,或者说特定的起始排列 $$$a$$$ 是不可能的。
输入
输入的第一行包含测试数量 $$$t$$$ ($$$1 \leq t \leq 10^5$$$)。
每个测试都用两行描述。第一行包含一个整数 $$$n$$$ — 卡片数量 ($$$1 \leq n \leq 10^5$$$)。第二行包含 $$$n$$$ 整数 $$$a_i$$$ — 卡片的初始排列 ($$$1 \leq a_i \leq n$$$; $$$\forall i \neq j: a_i \neq a_j$$$)。
保证所有测试的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
按照案例在输入中出现的顺序打印每个测试案例的答案。
对于每个测试用例,打印“不可能" 在一行中,如果不存在解决方案。
否则,打印“可能" 在第一行,在接下来的两行中打印排列 $$$p$$$ 和 $$$q$$$。
示例
输入复制
422 131 2 342 1 4 355 1 4 2 3
输出复制
Impossible Possible 3 1 2 2 3 1 Possible 3 4 2 1 3 4 2 1 Possible 4 1 2 5 3 3 1 4 5 2