← 返回题目列表

Codeforces · 193/C

C. 汉明距离

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

等长字符串 a 和 b 之间的汉明距离(用 h(a, b) 表示)等于不同整数 i (1 ≤ i ≤ |a|) 的数量,使得 ai ≠ bi,其中 ai 是字符串 a 的第 i 个符号,bi 是字符串 b 的第 i 个符号。例如,字符串“aba”和“bba”之间的汉明距离等于1,它们具有不同的第一个符号。对于字符串“bbba”和“aaab”,汉明距离等于 4。

John Doe 有一篇论文,上面写有四个长度相等的字符串 s1、s2、s3 和 s4。每个字符串 si 仅由小写字母“a”和“b”组成。约翰找到了他拥有的所有字符串对之间的汉明距离。然后他丢失了带有字符串的纸,但他没有丢失所有对之间的汉明距离。

帮助约翰恢复琴弦;找到仅由小写字母“a”和“b”组成的四个等长字符串 s'1、s'2、s'3、s'4,使得它们之间的成对汉明距离与 John 的字符串之间的汉明距离相同。更正式地说,集合 s'i 必须满足条件 $$$$。

为了使字符串更容易放在一张纸上,您应该在所有合适的字符串组中选择字符串长度最小的一组。

输入

第一行包含空格分隔的整数 h(s1, s2)、h(s1, s3)、h(s1, s4)。第二行包含空格分隔的整数 h(s2, s3) 和 h(s2, s4)。第三行包含单个整数 h(s3, s4)。

所有给定的整数 h(si, sj) 均为非负数且不超过 105。保证至少有一个数 h(si, sj) 为正数。

输出

如果没有合适的字符串集,则打印 -1。

否则在第一行打印数字 len — 每个字符串的长度。在接下来四行的第 i 行中打印字符串 s'i。如果存在多个具有最小字符串长度的集合,则打印其中的任何一个。

示例

输入 #1

4 4 4
4 4
4

输出 #1

6
aaaabb
aabbaa
bbaaaa
bbbbbb