← 返回题目列表

AtCoder · relay2_g

G. 造币

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

给你两个字符串 s 和 t 由小写英文字母和整数组成 L.

我们将考虑生成一个长度的字符串 L 通过连接一个或多个副本 s 和 t。这里,允许多次使用同一个字符串。

例如,当 s = at, t = code 和 L = 6, 字符串 可以生成 atatat, atcode 和 codeat 。

在可以用这种方式生成的字符串中,找到字典顺序最小的一个。在作为输入给出的情况下,总是可以生成长度为 L.

约束

  • 1 ≤ L ≤ 2 × 10^5
  • 1 ≤ |s|, |t| ≤ L
  • s 和 t 由小写英文字母组成。
  • 可以生成长度为 L 按照问题陈述中描述的方式。

输入

输入由标准输入按以下格式给出:

N
x_1 s_1
x_2 s_2
:
x_N s_N

输出

打印按照问题陈述中描述的方式生成的字符串中按字典顺序最小的字符串。


示例输入 1

6
at
code

示例输出 1

atatat

此输入对应于问题陈述中显示的示例。


示例输入 2

8
coding
festival

示例输出 2

festival

有可能 s or t 根本不能用于生成长度的字符串 L.


示例输入 3

8
same
same

示例输出 3

samesame

也有可能 有 s = t.


示例输入 4

10
coin
age

示例输出 4

ageagecoin