Alan 在一家专门从事计算机安全的公司工作。他最近想出了一个他认为很棒的公钥加密系统，其中私钥由两个 $\{1, \dots, n\}$ 的排列 $\pi$ 和 $\sigma$ 组成。公钥 $(a_1, \dots, a_n)$ 由 $a_i \equiv \pi_i + \sigma_i \pmod n$ 给出，其中 $1 \le i \le n$。表达式 $x \equiv y \pmod n$ 表示 $x$ 和 $y$ 除以 $n$ 后余数相同。

以 $n = 5$ 为例，考虑： $\pi = (3, 1, 5, 2, 4)$, $\sigma = (5, 1, 3, 4, 2)$, 且 $a = (3, 2, 3, 1, 1)$。

这里，例如 $a_5 \equiv 1 \equiv 4 + 2 \equiv \pi_5 + \sigma_5 \pmod 5$，且 $\pi$ 和 $\sigma$ 中的所有项分别是 $\{1, \dots, 5\}$，每个数字恰好出现一次。

Alan 的同事对该系统的安全性存有疑虑，因为找到与公钥对应的任何私钥都会破解该系统。你的任务是帮助他们。给定 $n$ 和一个序列 $a = (a_1, \dots, a_n)$，确定是否存在两个排列 $\pi$ 和 $\sigma$，使得对于每个 $i$ 都有 $\pi_i + \sigma_i \equiv a_i \pmod n$。如果存在多组这样的排列，输出其中任意一组即可。

输入格式

第一行包含序列的长度 $n$。第二行包含整数 $a_1, \dots, a_n$，满足 $1 \le a_i \le n$。长度 $n$ 满足 $1 \le n \le 1000$。

输出格式

如果没有解，输出 “impossible”。如果有解，输出其中任意一组，每行输出一个排列。

样例

样例输入 1

5
3 2 3 1 1

样例输出 1

1 4 3 5 2
2 3 5 1 4

样例输入 2

4
3 1 1 4

样例输出 2

impossible