Description

Alice 是一位魔术师，她创造了一个新魔术。她有 $n$ 张卡片，上面分别写着从 $1$ 到 $n$ 的不同数字。首先，她请一位观众洗牌，并将卡片排成一行。我们设从左数第 $i$ 张卡片上的数字是 $a_i$。

然后 Alice 选择两个排列 $p$ 和 $q$。对于 $p$ 和 $q$ 有一个限制——排列不能有不动点。这意味着 $\forall i: p_i \ne i$ 且 $q_i \ne i$。

在选定排列后，Alice 会根据它们来洗牌。现在，从左数第 $i$ 张卡片变成了 $a[p[q[i]]]$。如果经过洗牌后，从左数第 $i$ 张卡片上的数字恰好是 $i$，那么这个魔术就被认为是成功的。

请帮助 Alice 挑选出排列 $p$ 和 $q$，或者在对于给定的初始排列 $a$ 无解时指出这一点。

Input Format

输入的第一行包含测试数据的组数 $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$。

Output Format

对于每组测试数据，请按照它们在输入中出现的顺序输出答案。

对于每组测试数据，如果无解，则在单独的一行中输出 $\tt{Impossible}$。

否则，在第一行输出 $\tt{Possible}$，并在接下来的两行中分别输出排列 $p$ 和 $q$。

4
2
2 1
3
1 2 3
4
2 1 4 3
5
5 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

Hint

翻译由 gemini2.5pro 完成