← 返回题目列表

Codeforces · 510/E

E. 狐狸和晚餐

中文机器翻译题面 查看原题

Fox Ciel 正在 Prime Kingdom 参加一场派对。那里有n只狐狸(包括Fox Ciel)。第 i 只狐狸已经 ai 岁了。

他们将在一些圆桌旁吃晚饭。您想要这样分发狐狸:

1. 每只狐狸都坐在某张桌子旁。
2. 每张桌子周围至少坐着 3 只狐狸。
3. 每张桌子周围任意两只相邻狐狸的年龄之和应为质数。

如果 k 只狐狸 f1, f2, ..., fk 按顺时针顺序坐在桌子周围,则对于 1 ≤ i ≤ k - 1: fi 和 fi + 1 相邻,并且 f1 和 fk 也相邻。

如果可以以所需的方式分配狐狸,请找到一种方法来做到这一点。

输入

第一行包含单个整数n (3 ≤ n ≤ 200):此方中狐狸的数量。

第二行包含 n 个整数 ai (2 ≤ ai ≤ 104)。

输出

如果不可能做到这一点,则输出“Impossible”。

否则,在第一行输出一个整数 m ($$1 \leq m \leq \frac{n}{3}$$):表的数量。

然后输出 m 行,每行应该以整数 k -=– 该桌子周围的狐狸数量开始,然后是 k 个数字 — 该桌子周围的狐狸按顺时针顺序排列的索引。

如果有多种可能的排列,则输出其中任何一种。

示例

输入 #1

4
3 4 8 9

输出 #1

1
4 1 2 4 3

输入 #2

5
2 2 2 2 2

输出 #2

Impossible

输入 #3

12
2 3 4 5 6 7 8 9 10 11 12 13

输出 #3

1
12 1 2 3 6 5 12 9 8 7 10 11 4

输入#4

24
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

输出#4

3
6 1 2 3 6 5 4
10 7 8 9 12 15 14 13 16 11 10
8 17 18 23 22 19 20 21 24

注意

在示例1中,他们可以围坐在一张桌子旁,他们的年龄是:3-8-9-4,相邻的和是:11、17、13和7,所有这些整数都是素数。

在示例 2 中,这是不可能的:2+2 = 4 的总和不是素数。