To fight the Power Rangers, Rita Repulsa and Lord Zedd decided to unite the Clay and Zedd Patrols. For a more effective attack on Angel Grove, they want to build their army in two lines. The number of soldiers in the first rank is equal to the number of soldiers in the second.
Rita loves two questions:
- "Is it true that exactly x of your neighbors from Zedd Patrol?"
- "Is it true that exactly y of your Clay Patrol neighbors?"
Neighbors in this formation are soldiers on the left and right in the same line, as well as a soldier who is in the same position, but in a different line. Rita chose either one or both of these questions and asked each soldier. All soldiers were asked questions with the same x and/or y values.
Zordan, with the help of his magic power, watched the formation process all this time. He was very surprised that the answers of all the soldiers were positive. However, he remembers that the soldiers of the Zedd Patrol always tell the truth, and the soldiers of the Clay Patrol are sure to lie at least one question.
Since the Zedd Patrol soldiers are the most dangerous in Zordan's opinion, based on the answers, he wants to know what the smallest and largest number of Zedd Patrol soldiers could be in the combined army. He turned to you for help!
Input
The single line of the input file contains three integers k, x, y — the number of soldiers in one line and the number of questions (1 ≤ k ≤ 10
5; -1 ≤ x, y ≤ 3).
If x = -1, it means Rita didn't ask the first question.
If y = -1, it means that Rita didn't ask the second question.
Rita is guaranteed to have asked at least one question.
Imprint
If there is no construction method for given k, x and y, print -1.
Otherwise, the first line of the output file must contain a single number — the smallest possible number of soldiers from the Zedd Patrol in the army.
The next two lines should contain k characters "0" each. and "1" — line description:
- "0" means that a soldier from the Clay Patrol is in the corresponding position in the formation.
- "1" — soldier from Zedd Patrol.
The second line describes the first line, the third — second. Do not separate characters with spaces.
The fourth line of the output file should contain a single number — the largest possible number of soldiers from the Zedd Patrol in the army.
In the fifth and sixth lines, print a description of a possible construction in this case in a similar format.
If there are several ways to place soldiers, any one is allowed.
Examples
| # |
Input |
Output |
| 1 |
2 0 -1 |
2
01
10
2
01
10 |
| 2 |
5 1 2 |
0
00000
00000
4
01010
01010 |
| 3 |
1 2 2 |
0
0
0
0
0
0 |
| 4 |
10 0 3 |
5
0100010010
0001000100
8
0101010100
0010101010 |