4152: 汉明距离U找到字典序最小的那个

内存限制:1024 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:1 解决:1

题目描述

# Equal Hamming Distances ## 题目描述 小高和小李得到了两个长度为$N$的01序列$S$和$T$。他们想找到一个长度为$N$的01序列$U$,使得$U$与$S$的汉明距离等于$U$与$T$的汉明距离。在所有满足条件的序列中,他们希望找到字典序最小的那个。 1. 01序列是指仅由0和1组成的字符串。 2. 两个等长序列的汉明距离是指对应位置上字符不同的数量。 3. 字典序比较时,0被认为小于1。

输入

## 输入格式 输入包含三行分别是$N$,$S$,$T$。

输出

## 输出格式 如果存在满足条件的序列$U$,输出字典序最小的$U$。如果不存在,输出`-1`。

样例输入 复制

5
00100
10011

样例输出 复制

00001

提示

## 输入输出样例 ### 输入样例1 ``` 5 00100 10011 ``` ### 输出样例1 ``` 00001 ``` ### 输入样例2 ``` 1 0 1 ``` ### 输出样例2 ``` -1 ``` ## 数据范围与提示 【样例1说明】 对于$U = 00001$,$U$与$S$的汉明距离和$U$与$T$的汉明距离都是2。这是满足条件的字典序最小的序列。 【样例2说明】 不存在满足条件的序列$U$,因此输出`-1`。 【数据范围】 - $1 \leq N \leq 2 \times 10^5$ - $N$是整数。 - $S$和$T$都是长度为$N$的01序列。 ## 题目来源 ARC151A