2018.9 ECNU ICPC/CCPC Trial Round #3

D. 素数子序列

单点时限: 1.0 sec

内存限制: 512 MB

有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$,某些位置已经固定 ($a_i > 0$),其他位置允许乱填 ($a_i = 0$)。

现求一种填法,使得填完之后,序列的任意连续子序列的和都是质数。换句话说,对于一切 $1 \le l \le r \le n$,$a_l+a_{l+1}+\cdots+a_r$ 是质数。

输入格式

输入第一行一个整数 $n$ ($1 \le n \le 10^5$)。

第二行 $n$ 个整数用空格隔开 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)。$a_i > 0$ 表示该位置已经固定,$a_i = 0$ 表示该位置可以乱填。

输出格式

输出 $n$ 个整数,用空格隔开:$a_1’,a_2’,\ldots,a_n’$。填入的整数范围与输入相同,即 $1 \le a_i’ \le 10^9$。

如果有多解输出任意一解。如果无解输出 Impossible

样例

Input
3
2 0 2
Output
2 3 2
Input
5
2 3 3 3 3
Output
Impossible
Input
1
998244353
Output
998244353