Consider two binary sequences A and B of length n each.
Let us call these sequences compatible if A XOR B = A + B
where XOR is the element-wise exclusive OR operation.
Given an integer n and a pair of binary sequences p and q,
find the pair of compatible binary sequences a and b which comes
first after the pair (p, q). Pair (a, b) is said to be
lexicographically less that (c, d) if a is lexicographically less
than c, or a and c are equal and b is lexicographically less than d.
If there is no pair of compatible binary sequences lexicographically greater
than (p, q), output the lexicographically first compatible pair.
Input
There is a single integer n (1 ≤ n ≤ 100000) on the first line of
the input. The sequence p is given on the second line, and the sequence
q is on the third one. There are no spaces or other delimiters inside the
sequences; however, there could be trailing whitespace on these two lines.
Output
Output the sequences a and b on the first two lines of the output,
correspondingly. Use the same format as the input.
Samples
input | output |
---|
1
0
0
| 0
1
|
2
01
10
| 10
00
|
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007