← 返回题目列表

AtCoder · agc001_d

D. 数组和回文

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

分数: 1000 点

问题陈述

Snuke 在生日那天收到了母亲送给他的礼物。 现在是一对两个序列 a 和 b,由正整数组成。 他们满足以下所有属性:

  • 所有元素的总和 a is N.
  • 所有元素的总和 b is N.
  • 任何长度的字符串 满足以下两个条件(1)和(2)的 N 也将满足条件(3)。
    • (1) 以下任何一个都构成回文:第一个 a_1 字母,如下 a_2 字母,如下 a_3 字母等。
    • (2) 以下任何一个都构成回文:第一个 b_1 字母,如下 b_2 字母,如下 b_3 字母等。
    • (3) 全部 N 字母是相同的。

他很高兴,直到有一天他失去了这两个序列。 现在,他只记得顺序 a 是另一个序列的排列 A 长度 M.

为了给他再次带来幸福,他的妈妈决定再给他一对序列 a 和 b 满足他最喜欢的属性并且与他的记忆一致。

约束

  • 1≦N≦10^5
  • 1≦M≦100
  • 1≦A_i≦10^5
  • 所有的总和 A_i 等于 N.

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 ... A_M

输出

如果存在一对序列 a 和 b 满足属性并且与Snuke的记忆一致,打印三行。第一行必须包含序列 a,第二行必须包含序列的长度 b,第三行必须包含序列 b.

如果这样的一对不存在(因为 Snuke 的记忆错误或其他原因),则打印包含该单词的单行 Impossible (区分大小写)。


示例输入 1

3 2
2 1

示例输出 1

1 2
1
3

示例输入 2

6 1
6

示例输出 2

6
3
1 2 3

示例输入 3

55 10
1 2 3 4 5 6 7 8 9 10

示例输出 3

Impossible