| Codeforces Round 122 (Div. 1) |
|---|
| Закончено |
Расстоянием Хемминга между строками a и b равной длины называется число h(a, b) равное количеству различных целых i (1 ≤ i ≤ |a|) таких, что ai ≠ bi, где ai — i-й символ строки a, bi — i-й символ строки b. К примеру, расстояние Хемминга между строками «aba» и «bba» равно 1, в них различаются первые символы. Для строк «bbba» и «aaab» расстояние Хемминга равно 4.
У Джона Доу были записаны на бумажке четыре строки s1, s2, s3 и s4 равной длины. Каждая строка si состояла только из строчных букв «a» и «b». Джон нашел расстояния Хемминга между всеми парами имеющихся строк, после чего он потерял бумажку со строками. Расстояния Хемминга между всеми парами у него сохранились.
Помогите Джону восстановить строки; найдите какие-нибудь четыре строки s'1, s'2, s'3, s'4 равной длины, состоящие только из строчных букв «a» и «b», такие, что попарные расстояния Хемминга между ними такие же, как и у строк Джона. Более формально, набор 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. Если возможных наборов с минимальной длиной строк несколько — выведите любой из них.
4 4 4
4 4
4
6
aaaabb
aabbaa
bbaaaa
bbbbbb
