G - Coinage Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

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

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

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

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

制約

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

入力

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

L
s
t

出力

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

入力例 1

6
at
code

出力例 1

atatat

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

入力例 2

8
coding
festival

出力例 2

festival

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

入力例 3

8
same
same

出力例 3

samesame

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

入力例 4

10
coin
age

出力例 4

ageagecoin

Score : 100 points

Problem Statement

You are given two strings s and t consisting of lowercase English letters and an integer L.

We will consider generating a string of length L by concatenating one or more copies of s and t. Here, it is allowed to use the same string more than once.

For example, when s = at, t = code and L = 6, the strings atatat, atcode and codeat can be generated.

Among the strings that can be generated in this way, find the lexicographically smallest one. In the cases given as input, it is always possible to generate a string of length L.

Constraints

  • 1 ≤ L ≤ 2 × 10^5
  • 1 ≤ |s|, |t| ≤ L
  • s and t consist of lowercase English letters.
  • It is possible to generate a string of length L in the way described in Problem Statement.

Input

Input is given from Standard Input in the following format:

N
x_1 s_1
x_2 s_2
:
x_N s_N

Output

Print the lexicographically smallest string among the ones that can be generated in the way described in Problem Statement.

Sample Input 1

6
at
code

Sample Output 1

atatat

This input corresponds to the example shown in Problem Statement.

Sample Input 2

8
coding
festival

Sample Output 2

festival

It is possible that either s or t cannot be used at all in generating a string of length L.

Sample Input 3

8
same
same

Sample Output 3

samesame

It is also possible that s = t.

Sample Input 4

10
coin
age

Sample Output 4

ageagecoin