配点 : $300$ 点

問題文

以下では、0 と 1 のみからなる文字列を $01$ 列と呼びます。

$2$ つの長さ $N$ の $01$ 列 $S, T$ が与えられます。 下記の条件を満たす長さ $N$ の $01$ 列 $U$ のうち辞書順最小のものを出力してください。

• $S$ と $U$ のハミング距離は、$T$ と $U$ のハミング距離に等しい。

ただし、そのような長さ $N$ の $01$ 列 $U$ が存在しない場合は、代わりに $-1$ を出力してください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $N$ は整数
• $S, T$ は長さ $N$ の $01$ 列

入力

入力は以下の形式で標準入力から与えられる。

$N$

$S$

$T$

出力

問題文中の条件を満たす長さ $N$ の $01$ 列 $U$ のうち辞書順最小のものを出力せよ。 ただし、そのような $01$ 列 $U$ が存在しない場合は、代わりに $-1$ を出力せよ。

5
00100
10011

00001

$U =$ 00001とおくと、$S$ と $U$ のハミング距離と、$T$ と $U$ のハミング距離はどちらも $2$ です。 また、これが問題文中の条件を満たす長さ $N$ の $01$ 列 $U$ のうち辞書順最小です。

1
0
1

-1

問題文中の条件を満たす長さ $N$ の $01$ 列 $U$ が存在しないため、$-1$ を出力します。