#7147. 这一定是一个不同以往的浪漫故事

这一定是一个不同以往的浪漫故事

题目背景

旅行到了最后一夜。

明天,琪亚娜就要去很远很远的地方了——远到不能再回来。分别之前,她站在镜子前,看着镜子里的那个女孩:一样的白发,一样的脸,只有眼睛的颜色不太一样。那是最开始的那个她——那个还有很多东西不会、很多路没走过、却什么都不怕的女孩。

「当一个故事要结束的时候,我们总会想起它的开始。」

每年九月,这里都会上演同样的一幕:有人收拾好行李,把书合上,把座位让出来;有人背着包走进来,在空出来的位子上坐下,成为崭新的、还什么都不知道的自己。

学长们的故事讲完了。而你的故事,才刚刚写下第一行。

于是她说:那就再写一次吧——让现在的她,和最开始的那个她,隔着镜子一位一位对齐,把想说的话重新写一遍。

镜子不会说谎,也不偏心:它不在乎两张脸隔了多远,每一位上,它只留下更靠近开始的那一个字符。字母表是从 a 出发的一条路,越靠前的字母,离故事的开始越近。留下来的这一行,就是她们从头到尾都没有变过的那部分。

镜中的另一个她

题目描述

定义函数 f(s1,s2)f(s_1,s_2):它接受两个长度相同、都只由小写英文字母组成的字符串,返回一个同样长度的字符串 gg,满足

g[i]=min⁡(s1[i],s2[i])g[i]=\min\bigl(s_1[i],s_2[i]\bigr)

也就是说,逐位取两个字符中较小的那一个(按字符编码比较;对本题规定的小写字母来说,就是字母表里更靠前的那个)。

例如:f(ka,an)=aaf(\texttt{ka},\texttt{an})=\texttt{aa}。

现在给你两个长度为 nn 的字符串 xx 和 yy:xx 是镜子这一侧她写下的那一行,yy 是镜面留下的那一行。请你求出任意一个镜子另一侧可能写下的字符串 zz,使得

f(x,z)=yf(x,z)=y

如果不存在这样的 zz——那就是记忆出了错,镜子不会说谎——请输出 -1。

输入格式

  • 第一行一个整数 nn,表示字符串的长度;
  • 第二行一个长度为 nn 的字符串 xx;
  • 第三行一个长度为 nn 的字符串 yy。

保证 x,yx,y 都只由小写英文字母(a~z)组成。

输出格式

输出任意一个满足 f(x,z)=yf(x,z)=y 的、长度为 nn 的、只由小写英文字母组成的字符串 zz;

若不存在这样的 zz,输出 -1。

样例

2
ab
aa
ba
5
nzwzl
niwel
xiyez
2
ab
ba
-1

样例解释

样例 1:x=abx=\texttt{ab},y=aay=\texttt{aa},样例给出的答案是 z=baz=\texttt{ba}。逐位验证:min⁡(a,b)=a\min(\texttt{a},\texttt{b})=\texttt{a}、min⁡(b,a)=a\min(\texttt{b},\texttt{a})=\texttt{a},两处都等于 yy 上对应的字符,所以 f(ab,ba)=aa=yf(\texttt{ab},\texttt{ba})=\texttt{aa}=y,合法。

但请注意,这不是唯一的答案:第 2 位上 a 比 b 小,被逼死,只能填 a;第 1 位自由,随便换一个不小于 a 的字母,aa\texttt{aa}、ca\texttt{ca}、za\texttt{za} 全都成立。题面只要求你输出任意一个合法解,所以你输出的和样例不一样也没关系 —— 这题配有特殊校验器(Special Judge),只要每一位都满足 min⁡(x[i],z[i])=y[i]\min(x[i],z[i])=y[i] 就算对。

样例 2:x=nzwzlx=\texttt{nzwzl},y=niwely=\texttt{niwel},样例给出的答案是 z=xiyezz=\texttt{xiyez}。逐位看:min⁡(n,x)=n\min(\texttt{n},\texttt{x})=\texttt{n}、min⁡(z,i)=i\min(\texttt{z},\texttt{i})=\texttt{i}、min⁡(w,y)=w\min(\texttt{w},\texttt{y})=\texttt{w}、min⁡(z,e)=e\min(\texttt{z},\texttt{e})=\texttt{e}、min⁡(l,z)=l\min(\texttt{l},\texttt{z})=\texttt{l},连起来正好是 niwel\texttt{niwel},所以 xiyez\texttt{xiyez} 合法。

这一组里两种情形都有:第 2、4 位 yy 比 xx 小,被逼死;第 1、3、5 位 yy 和 xx 相同,是自由的。所以和样例 1 一样,答案远不止一个,比如 nixez\texttt{nixez}、niwez\texttt{niwez} 也都能通过。

数据范围与约定

  • 1≤n≤1001 \le n \le 100;
  • x,yx,y 均只由小写英文字母组成。

写在最后

  如果你才刚刚开始学编程,不必担心现在还什么都不会——所有后来很厉害的人,都是从写下第一行 Hello World 开始的。

  故事要结束的时候,我们总会想起它的开始。而你的故事才刚刚开头,这正是一件再好不过的事。

  很多年以后,你再回头看现在的自己:也许容貌变了,身边的人也变了——但总有些东西会一如既往。那是你从来没有丢掉过的本质,也是镜子唯一会留下来的东西。

  天穹的流星已经成为过去。而你们的故事,将在这座校园里延续,在教室与深夜里留存,在属于你们的明天闪耀。

  愿那时的你,还能对自己说:我一直都在为世界上所有的美好而战,而这一定是一个不同以往的浪漫故事。