#arc151a. [arc151_a]Equal Hamming Distances
[arc151_a]Equal Hamming Distances
Problem Statement
Below, a -sequence is a string consisting of 0
and 1
.
You are given two -sequences and of length each. Print the lexicographically smallest -sequence of length that satisfies the condition below.
- The Hamming distance between and equals the Hamming distance between and .
If there is no such -sequence of length , print instead.
What is Hamming distance?
The Hamming distance between -sequences and is the number of integers such that .
What is lexicographical order?
A -sequence is lexicographically smaller than a -sequence when there is an integer that satisfies both of the conditions below.
- .
-
0
and1
.
Constraints
- is an integer.
- and are -sequences of length each.
Input
The input is given from Standard Input in the following format:
Output
Print the lexicographically smallest -sequence of length that satisfies the condition in the Problem Statement, or if there is no such -sequence .
Sample Input 1
5
00100
10011
Sample Output 1
00001
For 00001
, the Hamming distance between and and the Hamming distance between and are both . Additionally, this is the lexicographically smallest -sequence of length that satisfies the condition.
Sample Input 2
1
0
1
Sample Output 2
-1
No -sequence of length satisfies the condition, so should be printed.