B. 最小交换(mins)

内存限制:256 MiB 时间限制:1000 ms 输入文件: mins.in 输出文件: mins.out
题目类型:传统 评测方式:文本比较

题目描述

你有四个长 n 的字符串 a,b,c,d 。你可以执行任意多次如下操作:

  • 选择一个 i ,交换 a_i,c_i ,然后交换 b_i,d_i

求在 a 的字典序尽量小的前提下, b 字典序最小是什么。


如果你不知道什么是字典序,看这里:

对于两个字符串 p,q ,称 p 的字典序小于 q (记为 p<q ),当且仅当存在自然数 k 使 p,q 的前 k 个字符相同且 p_{k+1} 的 ASCII 码小于 q_{k+1} 的 ASCII 码。

例如:

  • \texttt{abc}<\texttt{baa} (当 k=0
  • \texttt{bae}<\texttt{bbb} (当 k=1

输入格式

输入的第一行有一个正整数 n ,表示字符串 a,b,c,d 长度。

之后四行,每行一个字符串,分别表示 a,b,c,d

输出格式

输出一行一个字符串,表示题目要求的字符串 b

样例

样例输入 #1

8
westlake
yummyqaq
weabzzke
azazazaq

样例输出 #1

auazyqaq

【样例解释】

选择 i 1,3,4 可以让 a 取到最小的字典序 \texttt{weablake} ,此时字符串 b 也得到满足题意最小的字典序 \texttt{auazyqaq}

事实上如果 i=1 时不操作 a 的字典序也是最小的,但是此时字符串 b 就是 \texttt{yuazyqaq} ,不够小。

数据范围与提示

本题共 10 个测试点,每个测试点 10 分。

测试点编号 n\le 特殊性质
1\sim 2 15
3 10^5 a_i>c_i
4\sim 5 10^5 a_i\ne c_i
6\sim 7 10^5 b_i\ge d_i
8\sim 10 10^5

对于全体数据,保证 1\le n\le 10^5 ,字符串所有字符都是小写字母。

【入门】