Score : 100 points
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.
Input is given from Standard Input in the following format:
N x_1 s_1 x_2 s_2 : x_N s_N
Print the lexicographically smallest string among the ones that can be generated in the way described in Problem Statement.
6 at code
atatat
This input corresponds to the example shown in Problem Statement.
8 coding festival
festival
It is possible that either s or t cannot be used at all in generating a string of length L.
8 same same
samesame
It is also possible that s = t.
10 coin age
ageagecoin