题目描述

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

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

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

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

ハミング距離とは？$01$ 列 $X\ =\ X_1X_2\ldots\ X_N$ と $01$ 列 $Y\ =\ Y_1Y_2\ldots\ Y_N$ のハミング距離は、$X_i\ \neq\ Y_i$ を満たす整数 $1\ \leq\ i\ \leq\ N$ の個数です。

辞書順とは？$01$ 列 $X\ =\ X_1X_2\ldots\ X_N$ が $01$ 列 $Y\ =\ Y_1Y_2\ldots\ Y_N$ より辞書順で小さいとは、下記の $2$ つの条件をともに満たす整数 $1\ \leq\ i\ \leq\ N$ が存在することを言います。

• $X_1X_2\ldots\ X_{i-1}\ =\ Y_1Y_2\ldots\ Y_{i-1}$
• $X_i\ =$ 0 かつ $Y_i\ =$ 1

输入格式

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

$N$ $S$ $T$

输出格式

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

题目大意

题目描述

给定两个长度均为$N$的$01$序列$S$和$T$。求某一个字典序最小的$01$序列$U$,长度也为$N$，使$S$到$U$的汉明距离等于$T$到$U$的汉明距离。

若有解，输出字典序最小的解；若无解，输出$-1$。

汉明距离：两个长度相同的$01$序列的汉明距离定义为对应不相等的位置数量。

输入格式

共三行：

第一行一个整数$N$。

第二行一个长度为$N$的$01$序列$S$。

第二行一个长度为$N$的$01$序列$T$。

输出格式

若有解，输出字典序最小的解；若无解，输出$-1$。

样例1解释

当$U=00001$时,$S$和$U$的汉明距离、$T$和$U$的汉明距离都是$2$。

样例2解释

没有符合条件的$01$序列。

数据范围与提示

$1≤N≤2×10^5$。

$N$是整数。

$S$和$T$是长度均为$N$的$01$个序列。

5
00100
10011

00001

1
0
1

-1

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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