题目描述

英小文字からなる二つの文字列 $s,$ $t$ と整数 $L$ が与えられます。

$s,$ $t$ を任意の順に一個以上並べて長さ $L$ の文字列を生成することを考えます。このとき、同じ文字列を複数回用いることもできます。

例えば、$s\ =$ at$,$ $t\ =$ code$,$ $L\ =\ 6$ のとき、文字列 atatat$,$ atcode$,$ codeat を生成することができます。

このようにして生成される長さ $L$ の文字列のうち、辞書順最小のものを求めてください。なお、入力として与えられるケースでは、長さ $L$ の文字列を生成することは必ず可能です。

输入格式

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

$L$ $s$ $t$

输出格式

問題文で述べた方法で生成される長さ $L$ の文字列のうち、辞書順最小のものを出力せよ。

题目大意

题目描述

给定一个正整数$N$和两个字符串$s,t$，你要求出长度为$N$的，字典序最小的字符串$A$，使得$A$可以由若干个$s$与若干个$t$拼接而成

输入格式

第一行：一个正整数$N$

第二行：字符串$s$

第三行：字符串$t$

输出格式

一行一个字符串$A$

限制范围

$1\le |s|,|t|\le N\le 200000$

$s,t$仅包含小写英文字母

数据保证有解

样例$1$解释

$s=$at，$t=$code，$N=6$

可以组成atatat、atcode、codeat，其中字典序最小的是atatat

6
at
code

atatat

8
coding
festival

festival

8
same
same

samesame

10
coin
age

ageagecoin

提示

制約

• $1\ <\ =\ L\ <\ =\ 2\ ×\ 10^5$
• $1\ <\ =\ |s|,\ |t|\ <\ =\ L$
• $s,$ $t$ は英小文字からなる。
• 問題文で述べた方法で、$s,$ $t$ から長さ $L$ の文字列を生成することが可能である。

Sample Explanation 1

この入力は問題文中で示した例に対応します。

Sample Explanation 2

$s,$ $t$ のうち一方が長さ $L$ の文字列を生成する上でまったく役に立たないことがあります。

Sample Explanation 3

$s\ =\ t$ であることもあります。