Codeforces Round 122 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

greedy

math

matrices

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Hamming Distance

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHamming distance between strings *a* and *b* of equal length (denoted by *h*(*a*, *b*)) is equal to the number of distinct integers *i* (1 ≤ *i* ≤ |*a*|), such that *a*_{i} ≠ *b*_{i}, where *a*_{i} is the *i*-th symbol of string *a*, *b*_{i} is the *i*-th symbol of string *b*. For example, the Hamming distance between strings "aba" and "bba" equals 1, they have different first symbols. For strings "bbba" and "aaab" the Hamming distance equals 4.

John Doe had a paper on which four strings of equal length *s*_{1}, *s*_{2}, *s*_{3} and *s*_{4} were written. Each string *s*_{i} consisted only of lowercase letters "a" and "b". John found the Hamming distances between all pairs of strings he had. Then he lost the paper with the strings but he didn't lose the Hamming distances between all pairs.

Help John restore the strings; find some four strings *s*'_{1}, *s*'_{2}, *s*'_{3}, *s*'_{4} of equal length that consist only of lowercase letters "a" and "b", such that the pairwise Hamming distances between them are the same as between John's strings. More formally, set *s*'_{i} must satisfy the condition .

To make the strings easier to put down on a piece of paper, you should choose among all suitable sets of strings the one that has strings of minimum length.

Input

The first line contains space-separated integers *h*(*s*_{1}, *s*_{2}), *h*(*s*_{1}, *s*_{3}), *h*(*s*_{1}, *s*_{4}). The second line contains space-separated integers *h*(*s*_{2}, *s*_{3}) and *h*(*s*_{2}, *s*_{4}). The third line contains the single integer *h*(*s*_{3}, *s*_{4}).

All given integers *h*(*s*_{i}, *s*_{j}) are non-negative and do not exceed 10^{5}. It is guaranteed that at least one number *h*(*s*_{i}, *s*_{j}) is positive.

Output

Print -1 if there's no suitable set of strings.

Otherwise print on the first line number *len* — the length of each string. On the *i*-th of the next four lines print string *s*'_{i}. If there are multiple sets with the minimum length of the strings, print any of them.

Examples

Input

4 4 4

4 4

4

Output

6

aaaabb

aabbaa

bbaaaa

bbbbbb

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 07:52:41 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|